14931341690

Committed 09 May 2025 02:36PM UTC coverage: 61.65% (-0.02%) from 61.666%

Build # 14931341690

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #6 from Moehre2/improve-tests

Improved test case compilation by compiling each file separately.

Run Details

7602 of 12331 relevant lines covered (61.65%)

528.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.54

/src/transformations/loop_distribute.cpp

#include "sdfg/transformations/loop_distribute.h"

namespace sdfg {
namespace transformations {

LoopDistribute::LoopDistribute(structured_control_flow::Sequence& parent,
                               structured_control_flow::For& loop)
    : parent_(parent),
      loop_(loop){

      };

std::string LoopDistribute::name() { return "LoopDistribute"; };

bool LoopDistribute::can_be_applied(Schedule& schedule) {
    auto& builder = schedule.builder();
    auto& sdfg = builder.subject();
    auto indvar = this->loop_.indvar();

    // Criterion: Block -> Loop
    auto& body = this->loop_.root();
    if (body.size() < 2) {
        return false;
    }
    auto& block = body.at(0).first;
    if (!body.at(0).second.assignments().empty()) {
        return false;
    }

    auto& analysis_manager = schedule.analysis_manager();
    auto& users = analysis_manager.get<analysis::Users>();

    // Determine block-related containers
    std::unordered_set<std::string> containers;
    analysis::UsersView block_users(users, block);
    for (auto& user : block_users.uses()) {
        containers.insert(user->container());
    }

    // Criterion: loop is data-parallel w.r.t containers
    auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();
    auto& dependencies = analysis.get(loop_);
    if (dependencies.size() == 0) {
        return false;
    }

    // Determine body- and block-local variables
    auto body_locals = users.locals(sdfg, body);

    analysis::UsersView body_users(users, body);
    auto block_locals = body_users.locals(sdfg, block);

    // Check if all dependencies can be resolved
    bool can_be_distributed = true;
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        auto& dep_type = dep.second;

        // Criterion: If container not used in block, ignore
        if (containers.find(container) == containers.end()) {
            continue;
        }

        // Criterion: Containers must be parallel
        if (dep_type < analysis::Parallelism::PARALLEL) {
            can_be_distributed = false;
            break;
        }

        // Criterion: Readonly and parallel containers -> no action
        if (dep_type == analysis::Parallelism::READONLY ||
            dep_type == analysis::Parallelism::PARALLEL) {
            continue;
        }

        // We are left with private containers

        // Criterion: If container is only used inside block, no action
        if (block_locals.find(container) != block_locals.end()) {
            continue;
        }
        // Criterion: If container is used outside the loop, we fail
        if (body_locals.find(container) == body_locals.end()) {
            can_be_distributed = false;
            break;
        }

        // Criterion: Container must only be used as access node
        for (auto& user : body_users.uses(container)) {
            if (dynamic_cast<data_flow::AccessNode*>(user->element()) == nullptr) {
                can_be_distributed = false;
                break;
            }
        }
        if (!can_be_distributed) {
            break;
        }

        // Criterion: Bound must be integer
        auto bound = analysis::DataParallelismAnalysis::bound(this->loop_);
        if (bound == SymEngine::null || !SymEngine::is_a<SymEngine::Integer>(*bound)) {
            can_be_distributed = false;
            break;
        }
    }
    if (!can_be_distributed) {
        return false;
    }

    return true;
};

void LoopDistribute::apply(Schedule& schedule) {
    auto& builder = schedule.builder();
    auto& sdfg = builder.subject();

    auto indvar = this->loop_.indvar();
    auto condition = this->loop_.condition();
    auto update = this->loop_.update();
    auto init = this->loop_.init();

    auto& body = this->loop_.root();
    auto& block = body.at(0).first;

    // We might need to extend containers to loop dimension

    auto& analysis_manager = schedule.analysis_manager();
    auto& users = analysis_manager.get<analysis::Users>();
    auto body_locals = users.locals(sdfg, body);

    analysis::UsersView body_users(users, body);
    auto block_locals = body_users.locals(sdfg, block);

    analysis::UsersView block_users(users, block);

    // Determine block-related containers
    std::unordered_set<std::string> containers;
    for (auto& user : block_users.uses()) {
        containers.insert(user->container());
    }

    std::unordered_set<std::string> shared_containers;
    auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();
    auto& dependencies = analysis.get(loop_);
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        auto& dep_type = dep.second;

        if (containers.find(container) == containers.end()) {
            continue;
        }
        if (dep_type == analysis::Parallelism::READONLY ||
            dep_type == analysis::Parallelism::PARALLEL) {
            continue;
        }
        if (block_locals.find(container) != block_locals.end()) {
            continue;
        }

        shared_containers.insert(container);
    }

    if (!shared_containers.empty()) {
        auto bound = analysis::DataParallelismAnalysis::bound(this->loop_);
        for (auto& shared_container : shared_containers) {
            auto& type = sdfg.type(shared_container);

            // Add loop dimension to subset
            for (auto& user : body_users.uses(shared_container)) {
                auto& access_node = static_cast<data_flow::AccessNode&>(*user->element());
                auto& graph = access_node.get_parent();
                for (auto& edge : graph.in_edges(access_node)) {
                    data_flow::Subset new_subset = {indvar};
                    if (!dynamic_cast<const types::Scalar*>(&type)) {
                        for (auto& dim : edge.subset()) {
                            new_subset.push_back(dim);
                        }
                    }
                    edge.subset() = new_subset;
                }
                for (auto& edge : graph.out_edges(access_node)) {
                    data_flow::Subset new_subset = {indvar};
                    if (!dynamic_cast<const types::Scalar*>(&type)) {
                        for (auto& dim : edge.subset()) {
                            new_subset.push_back(dim);
                        }
                    }
                    edge.subset() = new_subset;
                }
            }

            // Make array
            builder.make_array(shared_container, bound);
        }
    }

    // Copy loop
    auto& new_loop =
        builder.add_for_before(parent_, this->loop_, indvar, condition, init, update).first;

    auto& new_body = new_loop.root();
    deepcopy::StructuredSDFGDeepCopy copies(builder, new_body, block);
    copies.copy();

    // Replace indvar in new loop
    std::string new_indvar = builder.find_new_name(indvar->get_name());
    builder.add_container(new_indvar, sdfg.type(indvar->get_name()));
    new_loop.replace(indvar, symbolic::symbol(new_indvar));

    // Remove block from loop
    builder.remove_child(body, block);

    analysis_manager.invalidate_all();
};

}  // namespace transformations
}  // namespace sdfg

1	#include "sdfg/transformations/loop_distribute.h"
2
3	namespace sdfg {
4	namespace transformations {
5
6	LoopDistribute::LoopDistribute(structured_control_flow::Sequence& parent,	106✔
7	structured_control_flow::For& loop)	106✔
8	: parent_(parent),	106✔
9	loop_(loop){	106✔
10
11	};	106✔
12
13	std::string LoopDistribute::name() { return "LoopDistribute"; };	×
14
15	bool LoopDistribute::can_be_applied(Schedule& schedule) {	60✔
16	auto& builder = schedule.builder();	60✔
17	auto& sdfg = builder.subject();	60✔
18	auto indvar = this->loop_.indvar();	60✔
19
20	// Criterion: Block -> Loop
21	auto& body = this->loop_.root();	60✔
22	if (body.size() < 2) {	60✔
23	return false;	×
24	}
25	auto& block = body.at(0).first;	60✔
26	if (!body.at(0).second.assignments().empty()) {	60✔
27	return false;	×
28	}
29
30	auto& analysis_manager = schedule.analysis_manager();	60✔
31	auto& users = analysis_manager.get<analysis::Users>();	60✔
32
33	// Determine block-related containers
34	std::unordered_set<std::string> containers;	60✔
35	analysis::UsersView block_users(users, block);	60✔
36	for (auto& user : block_users.uses()) {	852✔
37	containers.insert(user->container());	792✔
38	}	60✔
39
40	// Criterion: loop is data-parallel w.r.t containers
41	auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();	60✔
42	auto& dependencies = analysis.get(loop_);	60✔
43	if (dependencies.size() == 0) {	60✔
44	return false;	×
45	}
46
47	// Determine body- and block-local variables
48	auto body_locals = users.locals(sdfg, body);	60✔
49
50	analysis::UsersView body_users(users, body);	60✔
51	auto block_locals = body_users.locals(sdfg, block);	60✔
52
53	// Check if all dependencies can be resolved
54	bool can_be_distributed = true;	60✔
55	for (auto& dep : dependencies) {	422✔
56	auto& container = dep.first;	376✔
57	auto& dep_type = dep.second;	376✔
58
59	// Criterion: If container not used in block, ignore
60	if (containers.find(container) == containers.end()) {	376✔
61	continue;	358✔
62	}
63
64	// Criterion: Containers must be parallel
65	if (dep_type < analysis::Parallelism::PARALLEL) {	185✔
66	can_be_distributed = false;	14✔
67	break;	14✔
68	}
69
70	// Criterion: Readonly and parallel containers -> no action
71	if (dep_type == analysis::Parallelism::READONLY \|\|	171✔
72	dep_type == analysis::Parallelism::PARALLEL) {	98✔
73	continue;	117✔
74	}
75
76	// We are left with private containers
77
78	// Criterion: If container is only used inside block, no action
79	if (block_locals.find(container) != block_locals.end()) {	54✔
80	continue;	50✔
81	}
82	// Criterion: If container is used outside the loop, we fail
83	if (body_locals.find(container) == body_locals.end()) {	4✔
84	can_be_distributed = false;	×
85	break;	×
86	}
87
88	// Criterion: Container must only be used as access node
89	for (auto& user : body_users.uses(container)) {	16✔
90	if (dynamic_cast<data_flow::AccessNode*>(user->element()) == nullptr) {	12✔
91	can_be_distributed = false;	×
92	break;	×
93	}
94	}	4✔
95	if (!can_be_distributed) {	4✔
96	break;	×
97	}
98
99	// Criterion: Bound must be integer
100	auto bound = analysis::DataParallelismAnalysis::bound(this->loop_);	4✔
101	if (bound == SymEngine::null \|\| !SymEngine::is_a<SymEngine::Integer>(*bound)) {	4✔
102	can_be_distributed = false;	×
103	break;	×
104	}
105	}	4✔
106	if (!can_be_distributed) {	60✔
107	return false;	14✔
108	}
109
110	return true;	46✔
111	};	60✔
112
113	void LoopDistribute::apply(Schedule& schedule) {	46✔
114	auto& builder = schedule.builder();	46✔
115	auto& sdfg = builder.subject();	46✔
116
117	auto indvar = this->loop_.indvar();	46✔
118	auto condition = this->loop_.condition();	46✔
119	auto update = this->loop_.update();	46✔
120	auto init = this->loop_.init();	46✔
121
122	auto& body = this->loop_.root();	46✔
123	auto& block = body.at(0).first;	46✔
124
125	// We might need to extend containers to loop dimension
126
127	auto& analysis_manager = schedule.analysis_manager();	46✔
128	auto& users = analysis_manager.get<analysis::Users>();	46✔
129	auto body_locals = users.locals(sdfg, body);	46✔
130
131	analysis::UsersView body_users(users, body);	46✔
132	auto block_locals = body_users.locals(sdfg, block);	46✔
133
134	analysis::UsersView block_users(users, block);	46✔
135
136	// Determine block-related containers
137	std::unordered_set<std::string> containers;	46✔
138	for (auto& user : block_users.uses()) {	546✔
139	containers.insert(user->container());	500✔
140	}	46✔
141
142	std::unordered_set<std::string> shared_containers;	46✔
143	auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();	46✔
144	auto& dependencies = analysis.get(loop_);	46✔
145	for (auto& dep : dependencies) {	392✔
146	auto& container = dep.first;	346✔
147	auto& dep_type = dep.second;	346✔
148
149	if (containers.find(container) == containers.end()) {	346✔
150	continue;	184✔
151	}
152	if (dep_type == analysis::Parallelism::READONLY \|\|	162✔
153	dep_type == analysis::Parallelism::PARALLEL) {	96✔
154	continue;	110✔
155	}
156	if (block_locals.find(container) != block_locals.end()) {	52✔
157	continue;	48✔
158	}
159
160	shared_containers.insert(container);	4✔
161	}
162
163	if (!shared_containers.empty()) {	46✔
164	auto bound = analysis::DataParallelismAnalysis::bound(this->loop_);	4✔
165	for (auto& shared_container : shared_containers) {	8✔
166	auto& type = sdfg.type(shared_container);	4✔
167
168	// Add loop dimension to subset
169	for (auto& user : body_users.uses(shared_container)) {	16✔
170	auto& access_node = static_cast<data_flow::AccessNode&>(*user->element());	12✔
171	auto& graph = access_node.get_parent();	12✔
172	for (auto& edge : graph.in_edges(access_node)) {	16✔
173	data_flow::Subset new_subset = {indvar};	12✔
174	if (!dynamic_cast<const types::Scalar*>(&type)) {	4✔
175	for (auto& dim : edge.subset()) {	4✔
176	new_subset.push_back(dim);	2✔
177	}
178	}
179	edge.subset() = new_subset;	4✔
180	}	4✔
181	for (auto& edge : graph.out_edges(access_node)) {	20✔
182	data_flow::Subset new_subset = {indvar};	24✔
183	if (!dynamic_cast<const types::Scalar*>(&type)) {	8✔
184	for (auto& dim : edge.subset()) {	8✔
185	new_subset.push_back(dim);	4✔
186	}
187	}
188	edge.subset() = new_subset;	8✔
189	}	8✔
190	}	4✔
191
192	// Make array
193	builder.make_array(shared_container, bound);	4✔
194	}
195	}	4✔
196
197	// Copy loop
198	auto& new_loop =
199	builder.add_for_before(parent_, this->loop_, indvar, condition, init, update).first;	46✔
200
201	auto& new_body = new_loop.root();	46✔
202	deepcopy::StructuredSDFGDeepCopy copies(builder, new_body, block);	46✔
203	copies.copy();	46✔
204
205	// Replace indvar in new loop
206	std::string new_indvar = builder.find_new_name(indvar->get_name());	46✔
207	builder.add_container(new_indvar, sdfg.type(indvar->get_name()));	46✔
208	new_loop.replace(indvar, symbolic::symbol(new_indvar));	46✔
209
210	// Remove block from loop
211	builder.remove_child(body, block);	46✔
212
213	analysis_manager.invalidate_all();	46✔
214	};	46✔
215
216	} // namespace transformations
217	} // namespace sdfg

daisytuner / sdfglib / 14931341690

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous