20776975256

Committed 07 Jan 2026 09:35AM UTC coverage: 61.778% (-0.4%) from 62.168%

Build # 20776975256

Build Type

Pull #436

github

Committed by

web-flow

Commit Message

Merge 6d744fbf4 into 0c34ccd02

Pull Request Pull Request #436: Add comprehensive tests and Doxygen documentation for SDFG transformations

Run Details

14894 of 24109 relevant lines covered (61.78%)

88.74 hits per line

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

0.0

/src/transformations/out_local_storage.cpp

#include "sdfg/transformations/out_local_storage.h"

#include <cassert>
#include <cstddef>
#include <string>

#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/transformations/utils.h"
#include "sdfg/types/array.h"
#include "sdfg/types/scalar.h"

namespace sdfg {
namespace transformations {

OutLocalStorage::OutLocalStorage(structured_control_flow::StructuredLoop& loop, std::string container)
    : loop_(loop), container_(container) {};

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

bool OutLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& body = this->loop_.root();
    this->requires_array_ = false;

    // Criterion: Check if container exists and is used in the loop
    auto& users = analysis_manager.get<analysis::Users>();
    analysis::UsersView body_users(users, body);
    if (body_users.uses(this->container_).size() == 0) {
        return false;
    }

    // Criterion: Check if all accesses to the container within the loop are identical
    auto accesses = body_users.uses(this->container_);
    auto first_access = accesses.at(0);
    auto first_subset = first_access->subsets().at(0);
    if (accesses.size() > 1) {
        for (auto access : accesses) {
            if (first_access->subsets().size() != access->subsets().size()) {
                return false;
            }
            for (size_t i = 0; i < first_access->subsets().size(); i++) {
                auto subset = access->subsets().at(i);
                if (first_subset.size() != subset.size()) {
                    return false;
                }
                for (size_t j = 0; j < first_subset.size(); j++) {
                    if (!symbolic::eq(first_subset.at(j), subset.at(j))) {
                        return false;
                    }
                }
            }
        }
    }

    // Criterion: Check if accesses do not depend on containers written in the loop
    auto writes = body_users.writes();
    symbolic::SymbolSet written_containers;
    for (auto write : writes) {
        written_containers.insert(symbolic::symbol(write->container()));
    }
    for (auto subset : first_access->subsets()) {
        for (auto access : subset) {
            for (auto atom : symbolic::atoms(access)) {
                if (written_containers.contains(atom)) {
                    return false;
                }
            }
        }
    }

    // Soft Criterion: Check if the accesses do not depend on the loop iteration
    // Decide if an array or scalar is required
    for (auto subset : first_access->subsets()) {
        for (auto access : subset) {
            for (auto atom : symbolic::atoms(access)) {
                if (symbolic::eq(atom, this->loop_.indvar())) {
                    this->requires_array_ = true;
                    break;
                }
            }
            if (this->requires_array_) {
                break;
            }
        }
        if (this->requires_array_) {
            break;
        }
    }

    // Criterion: Check if the loop iteration count is known and an Integer when an array is
    // required
    if (this->requires_array_) {
        auto iteration_count = get_iteration_count(this->loop_);
        if (iteration_count == SymEngine::null) {
            return false;
        }
    }

    return true;
};

void OutLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (requires_array_) {
        apply_array(builder, analysis_manager);
    } else {
        apply_scalar(builder, analysis_manager);
    }

    // End of transformation

    analysis_manager.invalidate_all();

    passes::SequenceFusion sf_pass;
    passes::DeadCFGElimination dce_pass;
    bool applies = false;
    do {
        applies = false;
        applies |= dce_pass.run(builder, analysis_manager);
        applies |= sf_pass.run(builder, analysis_manager);
    } while (applies);
};

void OutLocalStorage::apply_array(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    auto& parent = builder.parent(loop_);
    auto replacement_name = "__daisy_out_local_storage_" + this->container_;

    auto iteration_count = get_iteration_count(this->loop_);
    types::Scalar scalar_type(sdfg.type(this->container_).primitive_type());
    types::Array array_type(scalar_type, iteration_count);
    builder.add_container(replacement_name, array_type);

    auto indvar_name = "__daisy_out_local_storage_" + this->loop_.indvar()->get_name();
    types::Scalar indvar_type(sdfg.type(loop_.indvar()->get_name()).primitive_type());
    builder.add_container(indvar_name, indvar_type);
    auto indvar = symbolic::symbol(indvar_name);
    auto init = loop_.init();
    auto update = symbolic::subs(loop_.update(), loop_.indvar(), indvar);
    auto condition = symbolic::subs(loop_.condition(), loop_.indvar(), indvar);

    analysis::UsersView body_users(users, loop_.root());
    auto accesses = body_users.uses(this->container_);
    auto first_access = accesses.at(0);
    auto first_subset = first_access->subsets().at(0);
    auto& init_loop = builder.add_for_before(parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());
    auto& init_body = init_loop.root();
    auto& init_block = builder.add_block(init_body);
    auto& init_access_read = builder.add_access(init_block, this->container_);
    auto& init_access_write = builder.add_access(init_block, replacement_name);
    auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});
    auto& init_memlet_in =
        builder.add_computational_memlet(init_block, init_access_read, init_tasklet, "_in", first_subset);
    init_memlet_in.replace(loop_.indvar(), indvar);
    builder.add_computational_memlet(init_block, init_tasklet, "_out", init_access_write, {indvar});

    auto& reset_loop = builder.add_for_after(parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());
    auto& reset_body = reset_loop.root();
    auto& reset_block = builder.add_block(reset_body);
    auto& reset_access_read = builder.add_access(reset_block, replacement_name);
    auto& reset_access_write = builder.add_access(reset_block, this->container_);
    auto& reset_tasklet = builder.add_tasklet(reset_block, data_flow::TaskletCode::assign, "_out", {"_in"});
    builder.add_computational_memlet(reset_block, reset_access_read, reset_tasklet, "_in", {indvar});
    auto& reset_memlet_out =
        builder.add_computational_memlet(reset_block, reset_tasklet, "_out", reset_access_write, first_subset);
    reset_memlet_out.replace(loop_.indvar(), indvar);

    for (auto user : body_users.uses(this->container_)) {
        auto element = user->element();
        if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {
            auto subset = memlet->subset();
            subset.clear();
            subset.push_back(this->loop_.indvar());
            memlet->set_subset(subset);
        }
    }
    loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(replacement_name));
};

void OutLocalStorage::apply_scalar(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    auto& parent = builder.parent(loop_);
    auto replacement_name = "__daisy_out_local_storage_" + this->container_;

    types::Scalar scalar_type(sdfg.type(this->container_).primitive_type());
    builder.add_container(replacement_name, scalar_type);

    analysis::UsersView body_users(users, loop_.root());
    auto accesses = body_users.uses(this->container_);
    auto first_access = accesses.at(0);
    auto first_subset = first_access->subsets().at(0);
    auto& init_block = builder.add_block_before(parent, loop_, {}, loop_.debug_info());
    auto& init_access_read = builder.add_access(init_block, this->container_);
    auto& init_access_write = builder.add_access(init_block, replacement_name);
    auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});
    builder.add_computational_memlet(init_block, init_access_read, init_tasklet, "_in", first_subset);
    builder.add_computational_memlet(init_block, init_tasklet, "_out", init_access_write, {});

    auto& reset_block = builder.add_block_after(parent, loop_, {}, loop_.debug_info());
    auto& reset_access_read = builder.add_access(reset_block, replacement_name);
    auto& reset_access_write = builder.add_access(reset_block, this->container_);
    auto& reset_tasklet = builder.add_tasklet(reset_block, data_flow::TaskletCode::assign, "_out", {"_in"});
    builder.add_computational_memlet(reset_block, reset_access_read, reset_tasklet, "_in", {});
    builder.add_computational_memlet(reset_block, reset_tasklet, "_out", reset_access_write, first_subset);

    this->loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(replacement_name));
};

void OutLocalStorage::to_json(nlohmann::json& j) const {
    std::string loop_type;
    if (dynamic_cast<structured_control_flow::For*>(&loop_)) {
        loop_type = "for";
    } else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {
        loop_type = "map";
    } else {
        throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());
    }
    j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};
    j["transformation_type"] = this->name();
    j["container"] = container_;
};

OutLocalStorage OutLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {
    auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();
    std::string container = desc["container"].get<std::string>();
    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::StructuredLoop*>(element);

    return OutLocalStorage(*loop, container);
};

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/out_local_storage.h"
2
3	#include <cassert>
4	#include <cstddef>
5	#include <string>
6
7	#include "sdfg/builder/structured_sdfg_builder.h"
8	#include "sdfg/data_flow/memlet.h"
9	#include "sdfg/passes/structured_control_flow/dead_cfg_elimination.h"
10	#include "sdfg/passes/structured_control_flow/sequence_fusion.h"
11	#include "sdfg/structured_control_flow/structured_loop.h"
12	#include "sdfg/symbolic/symbolic.h"
13	#include "sdfg/transformations/utils.h"
14	#include "sdfg/types/array.h"
15	#include "sdfg/types/scalar.h"
16
17	namespace sdfg {
18	namespace transformations {
19
20	OutLocalStorage::OutLocalStorage(structured_control_flow::StructuredLoop& loop, std::string container)
21	: loop_(loop), container_(container) {};	×
22
23	std::string OutLocalStorage::name() const { return "OutLocalStorage"; };	×
24
25	bool OutLocalStorage::can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
26	auto& body = this->loop_.root();	×
27	this->requires_array_ = false;	×
28
29	// Criterion: Check if container exists and is used in the loop
30	auto& users = analysis_manager.get<analysis::Users>();	×
31	analysis::UsersView body_users(users, body);	×
32	if (body_users.uses(this->container_).size() == 0) {	×
33	return false;	×
34	}	×
35
36	// Criterion: Check if all accesses to the container within the loop are identical
37	auto accesses = body_users.uses(this->container_);	×
38	auto first_access = accesses.at(0);	×
39	auto first_subset = first_access->subsets().at(0);	×
40	if (accesses.size() > 1) {	×
41	for (auto access : accesses) {	×
42	if (first_access->subsets().size() != access->subsets().size()) {	×
43	return false;	×
44	}	×
45	for (size_t i = 0; i < first_access->subsets().size(); i++) {	×
46	auto subset = access->subsets().at(i);	×
47	if (first_subset.size() != subset.size()) {	×
48	return false;	×
49	}	×
50	for (size_t j = 0; j < first_subset.size(); j++) {	×
51	if (!symbolic::eq(first_subset.at(j), subset.at(j))) {	×
52	return false;	×
53	}	×
54	}	×
55	}	×
56	}	×
57	}	×
58
59	// Criterion: Check if accesses do not depend on containers written in the loop
60	auto writes = body_users.writes();	×
61	symbolic::SymbolSet written_containers;	×
62	for (auto write : writes) {	×
63	written_containers.insert(symbolic::symbol(write->container()));	×
64	}	×
65	for (auto subset : first_access->subsets()) {	×
66	for (auto access : subset) {	×
67	for (auto atom : symbolic::atoms(access)) {	×
68	if (written_containers.contains(atom)) {	×
69	return false;	×
70	}	×
71	}	×
72	}	×
73	}	×
74
75	// Soft Criterion: Check if the accesses do not depend on the loop iteration
76	// Decide if an array or scalar is required
77	for (auto subset : first_access->subsets()) {	×
78	for (auto access : subset) {	×
79	for (auto atom : symbolic::atoms(access)) {	×
80	if (symbolic::eq(atom, this->loop_.indvar())) {	×
81	this->requires_array_ = true;	×
82	break;	×
83	}	×
84	}	×
85	if (this->requires_array_) {	×
86	break;	×
87	}	×
88	}	×
89	if (this->requires_array_) {	×
90	break;	×
91	}	×
92	}	×
93
94	// Criterion: Check if the loop iteration count is known and an Integer when an array is
95	// required
96	if (this->requires_array_) {	×
97	auto iteration_count = get_iteration_count(this->loop_);	×
98	if (iteration_count == SymEngine::null) {	×
99	return false;	×
100	}	×
101	}	×
102
103	return true;	×
104	};	×
105
106	void OutLocalStorage::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
107	if (requires_array_) {	×
108	apply_array(builder, analysis_manager);	×
109	} else {	×
110	apply_scalar(builder, analysis_manager);	×
111	}	×
112
113	// End of transformation
114
115	analysis_manager.invalidate_all();	×
116
117	passes::SequenceFusion sf_pass;	×
118	passes::DeadCFGElimination dce_pass;	×
119	bool applies = false;	×
120	do {	×
121	applies = false;	×
122	applies \|= dce_pass.run(builder, analysis_manager);	×
123	applies \|= sf_pass.run(builder, analysis_manager);	×
124	} while (applies);	×
125	};	×
126
127	void OutLocalStorage::apply_array(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
128	auto& sdfg = builder.subject();	×
129	auto& users = analysis_manager.get<analysis::Users>();	×
130	auto& parent = builder.parent(loop_);	×
131	auto replacement_name = "__daisy_out_local_storage_" + this->container_;	×
132
133	auto iteration_count = get_iteration_count(this->loop_);	×
134	types::Scalar scalar_type(sdfg.type(this->container_).primitive_type());	×
135	types::Array array_type(scalar_type, iteration_count);	×
136	builder.add_container(replacement_name, array_type);	×
137
138	auto indvar_name = "__daisy_out_local_storage_" + this->loop_.indvar()->get_name();	×
139	types::Scalar indvar_type(sdfg.type(loop_.indvar()->get_name()).primitive_type());	×
140	builder.add_container(indvar_name, indvar_type);	×
141	auto indvar = symbolic::symbol(indvar_name);	×
142	auto init = loop_.init();	×
143	auto update = symbolic::subs(loop_.update(), loop_.indvar(), indvar);	×
144	auto condition = symbolic::subs(loop_.condition(), loop_.indvar(), indvar);	×
145
146	analysis::UsersView body_users(users, loop_.root());	×
147	auto accesses = body_users.uses(this->container_);	×
148	auto first_access = accesses.at(0);	×
149	auto first_subset = first_access->subsets().at(0);	×
150	auto& init_loop = builder.add_for_before(parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());	×
151	auto& init_body = init_loop.root();	×
152	auto& init_block = builder.add_block(init_body);	×
153	auto& init_access_read = builder.add_access(init_block, this->container_);	×
154	auto& init_access_write = builder.add_access(init_block, replacement_name);	×
155	auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});	×
156	auto& init_memlet_in =	×
157	builder.add_computational_memlet(init_block, init_access_read, init_tasklet, "_in", first_subset);	×
158	init_memlet_in.replace(loop_.indvar(), indvar);	×
159	builder.add_computational_memlet(init_block, init_tasklet, "_out", init_access_write, {indvar});	×
160
161	auto& reset_loop = builder.add_for_after(parent, loop_, indvar, condition, init, update, {}, loop_.debug_info());	×
162	auto& reset_body = reset_loop.root();	×
163	auto& reset_block = builder.add_block(reset_body);	×
164	auto& reset_access_read = builder.add_access(reset_block, replacement_name);	×
165	auto& reset_access_write = builder.add_access(reset_block, this->container_);	×
166	auto& reset_tasklet = builder.add_tasklet(reset_block, data_flow::TaskletCode::assign, "_out", {"_in"});	×
167	builder.add_computational_memlet(reset_block, reset_access_read, reset_tasklet, "_in", {indvar});	×
168	auto& reset_memlet_out =	×
169	builder.add_computational_memlet(reset_block, reset_tasklet, "_out", reset_access_write, first_subset);	×
170	reset_memlet_out.replace(loop_.indvar(), indvar);	×
171
172	for (auto user : body_users.uses(this->container_)) {	×
173	auto element = user->element();	×
174	if (auto memlet = dynamic_cast<data_flow::Memlet*>(element)) {	×
175	auto subset = memlet->subset();	×
176	subset.clear();	×
177	subset.push_back(this->loop_.indvar());	×
178	memlet->set_subset(subset);	×
179	}	×
180	}	×
181	loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(replacement_name));	×
182	};	×
183
184	void OutLocalStorage::apply_scalar(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
185	auto& sdfg = builder.subject();	×
186	auto& users = analysis_manager.get<analysis::Users>();	×
187	auto& parent = builder.parent(loop_);	×
188	auto replacement_name = "__daisy_out_local_storage_" + this->container_;	×
189
190	types::Scalar scalar_type(sdfg.type(this->container_).primitive_type());	×
191	builder.add_container(replacement_name, scalar_type);	×
192
193	analysis::UsersView body_users(users, loop_.root());	×
194	auto accesses = body_users.uses(this->container_);	×
195	auto first_access = accesses.at(0);	×
196	auto first_subset = first_access->subsets().at(0);	×
197	auto& init_block = builder.add_block_before(parent, loop_, {}, loop_.debug_info());	×
198	auto& init_access_read = builder.add_access(init_block, this->container_);	×
199	auto& init_access_write = builder.add_access(init_block, replacement_name);	×
200	auto& init_tasklet = builder.add_tasklet(init_block, data_flow::TaskletCode::assign, "_out", {"_in"});	×
201	builder.add_computational_memlet(init_block, init_access_read, init_tasklet, "_in", first_subset);	×
202	builder.add_computational_memlet(init_block, init_tasklet, "_out", init_access_write, {});	×
203
204	auto& reset_block = builder.add_block_after(parent, loop_, {}, loop_.debug_info());	×
205	auto& reset_access_read = builder.add_access(reset_block, replacement_name);	×
206	auto& reset_access_write = builder.add_access(reset_block, this->container_);	×
207	auto& reset_tasklet = builder.add_tasklet(reset_block, data_flow::TaskletCode::assign, "_out", {"_in"});	×
208	builder.add_computational_memlet(reset_block, reset_access_read, reset_tasklet, "_in", {});	×
209	builder.add_computational_memlet(reset_block, reset_tasklet, "_out", reset_access_write, first_subset);	×
210
211	this->loop_.replace(symbolic::symbol(this->container_), symbolic::symbol(replacement_name));	×
212	};	×
213
214	void OutLocalStorage::to_json(nlohmann::json& j) const {	×
215	std::string loop_type;	×
216	if (dynamic_cast<structured_control_flow::For*>(&loop_)) {	×
217	loop_type = "for";	×
218	} else if (dynamic_cast<structured_control_flow::Map*>(&loop_)) {	×
219	loop_type = "map";	×
220	} else {	×
221	throw std::runtime_error("Unsupported loop type for serialization of loop: " + loop_.indvar()->get_name());	×
222	}	×
223	j["subgraph"] = {{"0", {{"element_id", this->loop_.element_id()}, {"type", loop_type}}}};	×
224	j["transformation_type"] = this->name();	×
225	j["container"] = container_;	×
226	};	×
227
228	OutLocalStorage OutLocalStorage::from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& desc) {	×
229	auto loop_id = desc["subgraph"]["0"]["element_id"].get<size_t>();	×
230	std::string container = desc["container"].get<std::string>();	×
231	auto element = builder.find_element_by_id(loop_id);	×
232	if (!element) {	×
233	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " not found.");	×
234	}	×
235	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(element);	×
236
237	return OutLocalStorage(*loop, container);	×
238	};	×
239
240	} // namespace transformations
241	} // namespace sdfg

daisytuner / sdfglib / 20776975256

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