15656007340

Committed 14 Jun 2025 08:51PM UTC coverage: 13.234% (-49.9%) from 63.144%

Build # 15656007340

Build Type

Pull #76

github

Committed by

web-flow

Commit Message

Merge 9586c8161 into 413c53212

Pull Request Pull Request #76: New Loop Dependency Analysis

Run Details

361 of 465 new or added lines in 7 files covered. (77.63%)

6215 existing lines in 110 files now uncovered.

1612 of 12181 relevant lines covered (13.23%)

13.64 hits per line

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

0.0

/src/transformations/out_local_storage.cpp

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

daisytuner / sdfglib / 15656007340

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