15133758385

Committed 20 May 2025 09:19AM UTC coverage: 60.543% (-3.0%) from 63.542%

Build # 15133758385

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #22 from daisytuner/normalization

Removes normalization passes

Run Details

7922 of 13085 relevant lines covered (60.54%)

104.24 hits per line

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

0.0

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

daisytuner / sdfglib / 15133758385

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