15744620952

Committed 18 Jun 2025 10:07PM UTC coverage: 64.591% (+0.005%) from 64.586%

Build # 15744620952

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #86 from daisytuner/add-optimizer

Add optimizer functionality

Run Details

122 of 201 new or added lines in 9 files covered. (60.7%)

2 existing lines in 1 file now uncovered.

8141 of 12604 relevant lines covered (64.59%)

153.84 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"

#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/deepcopy/structured_sdfg_deep_copy.h"

namespace sdfg {
namespace transformations {

LoopDistribute::LoopDistribute(structured_control_flow::StructuredLoop& loop)
    : loop_(loop) {

      };

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

bool LoopDistribute::can_be_applied(builder::StructuredSDFGBuilder& builder,
                                    analysis::AnalysisManager& analysis_manager) {
    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& 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(body);
    auto block_locals = users.locals(block);

    analysis::UsersView body_users(users, body);

    // 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(builder::StructuredSDFGBuilder& builder,
                           analysis::AnalysisManager& analysis_manager) {
    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& users = analysis_manager.get<analysis::Users>();
    auto body_locals = users.locals(body);
    auto block_locals = users.locals(block);

    analysis::UsersView body_users(users, body);
    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);
        }
    }

    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent =
        static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&loop_));

    // 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();
};

void LoopDistribute::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["loop_element_id"] = loop_.element_id();
};

LoopDistribute LoopDistribute::from_json(builder::StructuredSDFGBuilder& builder,
                                         const nlohmann::json& desc) {
    auto loop_id = desc["loop_element_id"].get<size_t>();
    auto element = builder.find_element_by_id(loop_id);
    if (!element) {
        throw InvalidTransformationDescriptionException("Element with ID " +
                                                        std::to_string(loop_id) + " not found.");
    }
    auto loop = dynamic_cast<structured_control_flow::For*>(element);

    return LoopDistribute(*loop);
};

}  // namespace transformations
}  // namespace sdfg

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

daisytuner / sdfglib / 15744620952

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