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/passes/dataflow/redundant_array_elimination.cpp

1	#include "sdfg/passes/dataflow/redundant_array_elimination.h"
2
3	#include "sdfg/analysis/users.h"
4	#include "sdfg/types/utils.h"
5
6	namespace sdfg {
7	namespace passes {
8
UNCOV 9	RedundantArrayElimination::RedundantArrayElimination()	×
UNCOV 10	: Pass() {	×
11
UNCOV 12	};	×
13
14	std::string RedundantArrayElimination::name() { return "RedundantArrayElimination"; };	×
15
UNCOV 16	bool RedundantArrayElimination::run_pass(builder::StructuredSDFGBuilder& builder,	×
17	analysis::AnalysisManager& analysis_manager) {
UNCOV 18	bool applied = false;	×
19
UNCOV 20	auto& sdfg = builder.subject();	×
UNCOV 21	auto& users = analysis_manager.get<analysis::Users>();	×
UNCOV 22	for (auto& name : sdfg.containers()) {	×
23	// Criterion: Only transients
UNCOV 24	if (!sdfg.is_transient(name)) {	×
UNCOV 25	continue;	×
26	}
UNCOV 27	if (!users.moves(name).empty() \|\| !users.views(name).empty()) {	×
28	continue;	×
29	}
UNCOV 30	if (users.writes(name).size() != 1) {	×
UNCOV 31	continue;	×
32	}
UNCOV 33	std::unique_ptr<types::IType> type = sdfg.type(name).clone();	×
UNCOV 34	if (dynamic_cast<const types::Array*>(type.get()) == nullptr) {	×
35	continue;	×
36	}
37
38	// Criterion: Data must depend on externals
UNCOV 39	auto write = users.writes(name)[0];	×
UNCOV 40	auto write_node = dynamic_cast<data_flow::AccessNode*>(write->element());	×
UNCOV 41	auto& graph = write_node->get_parent();	×
UNCOV 42	if (graph.in_degree(*write_node) == 0) {	×
43	continue;	×
44	}
UNCOV 45	auto& write_edge = graph.in_edges(write_node).begin();	×
UNCOV 46	auto& write_subset = write_edge.subset();	×
47
48	// Access nodes for write
UNCOV 49	std::vector<symbolic::Symbol> input_symbols;	×
UNCOV 50	for (auto& e : graph.in_edges(write_edge.src())) {	×
UNCOV 51	auto& src = e.src();	×
UNCOV 52	if (graph.in_degree(src) != 0) {	×
53	continue;	×
54	}
UNCOV 55	auto access_node = dynamic_cast<data_flow::AccessNode*>(&src);	×
UNCOV 56	input_symbols.push_back(symbolic::symbol(access_node->data()));	×
UNCOV 57	for (auto& subset : e.subset()) {	×
UNCOV 58	auto atoms = symbolic::atoms(subset);	×
UNCOV 59	for (auto& atom : atoms) {	×
UNCOV 60	if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {	×
UNCOV 61	auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
UNCOV 62	input_symbols.push_back(symbol);	×
UNCOV 63	}	×
64	}
UNCOV 65	}	×
66	}
67
UNCOV 68	bool has_redundant_dimension = false;	×
69	// Criterion: Data must be an Array
UNCOV 70	uint depth = 0;	×
UNCOV 71	while (auto atype = dynamic_cast<const types::Array*>(type.get())) {	×
UNCOV 72	auto subset = write_subset[depth];	×
UNCOV 73	auto atoms = symbolic::atoms(subset);	×
UNCOV 74	bool dependency_exists = false;	×
75
UNCOV 76	for (auto& atom : atoms) {	×
UNCOV 77	if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {	×
UNCOV 78	auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
UNCOV 79	for (auto& input_symbol : input_symbols) {	×
UNCOV 80	if (symbolic::eq(symbol, input_symbol)) {	×
UNCOV 81	dependency_exists = true;	×
UNCOV 82	break;	×
83	}
84	}
UNCOV 85	if (dependency_exists) {	×
UNCOV 86	break;	×
87	}
UNCOV 88	}	×
89	}
UNCOV 90	if (!dependency_exists) {	×
UNCOV 91	has_redundant_dimension = true;	×
UNCOV 92	break;	×
93	}
UNCOV 94	type = atype->element_type().clone();	×
UNCOV 95	depth++;	×
UNCOV 96	}	×
97
UNCOV 98	if (!has_redundant_dimension) {	×
UNCOV 99	continue;	×
100	}
101
102	// Construct new type
UNCOV 103	auto atype = static_cast<const types::Array*>(type.get());	×
UNCOV 104	std::unique_ptr<types::IType> inner_type = atype->element_type().clone();	×
105	std::unique_ptr<types::IType> new_type =
UNCOV 106	types::recombine_array_type(sdfg.type(name), depth, *inner_type.get());	×
107
108	// Replace data type
UNCOV 109	builder.change_type(name, *new_type.get());	×
110
111	// Replace all reads
UNCOV 112	for (auto& user : users.reads(name)) {	×
113	auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());	×
114	if (access_node == nullptr) {	×
115	throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");	×
116	}
117
118	auto& graph = access_node->get_parent();	×
119	for (auto& oedge : graph.out_edges(*access_node)) {	×
120	auto& subset = oedge.subset();	×
121	subset.erase(subset.begin() + depth);	×
122	}
123	}
124	// Replace all writes
UNCOV 125	for (auto& user : users.writes(name)) {	×
UNCOV 126	auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());	×
UNCOV 127	if (access_node == nullptr) {	×
128	throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");	×
129	}
130
UNCOV 131	auto& graph = access_node->get_parent();	×
UNCOV 132	for (auto& iedge : graph.in_edges(*access_node)) {	×
UNCOV 133	auto& subset = iedge.subset();	×
UNCOV 134	subset.erase(subset.begin() + depth);	×
135	}
136	}
137
UNCOV 138	applied = true;	×
UNCOV 139	}	×
140
UNCOV 141	analysis_manager.invalidate_all();	×
142
UNCOV 143	return applied;	×
144	};	×
145
146	} // namespace passes
147	} // 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