15744033896

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

Build # 15744033896

Build Type

Pull #86

github

Committed by

web-flow

Commit Message

Merge aa8215c5a into fca4db8e8

Pull Request Pull Request #86: 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

85.03

/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).first;
    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", scalar_type}, {{"_in", scalar_type}});
    auto& init_memlet_in =
        builder.add_memlet(init_block, init_access_read, "void", init_tasklet, "_in", first_subset);
    init_memlet_in.replace(loop_.indvar(), indvar);
    builder.add_memlet(init_block, init_tasklet, "_out", init_access_write, "void", {indvar});

    auto& reset_loop = builder.add_for_after(parent, loop_, indvar, condition, init, update).first;
    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", scalar_type}, {{"_in", scalar_type}});
    builder.add_memlet(reset_block, reset_access_read, "void", reset_tasklet, "_in", {indvar});
    auto& reset_memlet_out = builder.add_memlet(reset_block, reset_tasklet, "_out",
                                                reset_access_write, "void", 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());
        }
    }
    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_).first;
    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", scalar_type}, {{"_in", scalar_type}});
    builder.add_memlet(init_block, init_access_read, "void", init_tasklet, "_in", first_subset);
    builder.add_memlet(init_block, init_tasklet, "_out", init_access_write, "void", {});

    auto& reset_block = builder.add_block_after(parent, loop_).first;
    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", scalar_type}, {{"_in", scalar_type}});
    builder.add_memlet(reset_block, reset_access_read, "void", reset_tasklet, "_in", {});
    builder.add_memlet(reset_block, reset_tasklet, "_out", reset_access_write, "void",
                       first_subset);

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

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

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

daisytuner / sdfglib / 15744033896

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