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/structured_control_flow/for2map.cpp

1	#include "sdfg/passes/structured_control_flow/for2map.h"
2
3	#include "sdfg/analysis/data_parallelism_analysis.h"
4	#include "sdfg/structured_control_flow/for.h"
5	#include "sdfg/structured_control_flow/map.h"
6	#include "sdfg/structured_control_flow/sequence.h"
7	#include "sdfg/symbolic/symbolic.h"
8	#include "sdfg/visitor/structured_sdfg_visitor.h"
9	#include "symengine/basic.h"
10	#include "symengine/logic.h"
11	#include "symengine/symengine_rcp.h"
12
13	namespace sdfg {
14	namespace passes {
15
UNCOV 16	For2Map::For2Map(builder::StructuredSDFGBuilder& builder,	×
17	analysis::AnalysisManager& analysis_manager)
UNCOV 18	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {	×
19
UNCOV 20	};	×
21
UNCOV 22	bool For2Map::can_be_applied(const structured_control_flow::For& for_stmt,	×
23	analysis::AnalysisManager& analysis_manager) {
24	// Criterion: loop must be data-parallel w.r.t containers
UNCOV 25	auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();	×
UNCOV 26	auto& dependencies = analysis.get(for_stmt);	×
UNCOV 27	if (dependencies.size() == 0) {	×
UNCOV 28	return false;	×
29	}
30
31	// Criterion: update must be normalizable (i.e., it may not be involved in anything but an
32	// addition during the update)
UNCOV 33	auto& index_var = for_stmt.indvar();	×
UNCOV 34	auto& update = for_stmt.update();	×
35
UNCOV 36	bool normalizable_update = symbolic::eq(	×
UNCOV 37	symbolic::subs(update, index_var, symbolic::one()),	×
UNCOV 38	symbolic::add(symbolic::subs(update, index_var, symbolic::zero()), symbolic::one()));	×
39
UNCOV 40	if (!normalizable_update) {	×
41	return false;	×
42	}
43
UNCOV 44	auto stride = symbolic::subs(update, index_var, symbolic::zero());	×
45
46	// Criterion: loop bound must be simple, less than or equal statement (e.g., i < N)
47
UNCOV 48	auto condition = symbolic::rearrange_simple_condition(for_stmt.condition(), index_var);	×
49
UNCOV 50	symbolic::Expression bound;	×
UNCOV 51	symbolic::Expression lhs;	×
UNCOV 52	symbolic::Expression rhs;	×
UNCOV 53	if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {	×
54	auto condition_LE = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(condition);	×
55	lhs = condition_LE->get_arg1();	×
56	rhs = condition_LE->get_arg2();	×
UNCOV 57	} else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
UNCOV 58	auto condition_LT = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(condition);	×
UNCOV 59	lhs = condition_LT->get_arg1();	×
UNCOV 60	rhs = condition_LT->get_arg2();	×
UNCOV 61	} else {	×
62	return false;	×
63	}
64
UNCOV 65	if (!symbolic::eq(lhs, index_var)) {	×
UNCOV 66	return false;	×
67	}
68
UNCOV 69	return true;	×
UNCOV 70	}	×
71
UNCOV 72	symbolic::Expression For2Map::num_iterations(const structured_control_flow::For& for_stmt,	×
73	analysis::AnalysisManager& analysis_manager) const {
74	// Criterion: update must be normalizable (i.e., it may not be involved in anything but an
75	// addition during the update)
UNCOV 76	auto& index_var = for_stmt.indvar();	×
UNCOV 77	auto& update = for_stmt.update();	×
UNCOV 78	auto& init = for_stmt.init();	×
79
UNCOV 80	bool normalizable_update = symbolic::eq(	×
UNCOV 81	symbolic::subs(update, index_var, symbolic::one()),	×
UNCOV 82	symbolic::add(symbolic::subs(update, index_var, symbolic::zero()), symbolic::one()));	×
83
UNCOV 84	if (!normalizable_update) {	×
85	return symbolic::zero();	×
86	}
87
UNCOV 88	auto stride = symbolic::subs(update, index_var, symbolic::zero());	×
89
90	// Criterion: loop bound must be simple, less than or equal statement (e.g., i < N)
91
UNCOV 92	auto condition = symbolic::rearrange_simple_condition(for_stmt.condition(), index_var);	×
93
UNCOV 94	symbolic::Expression bound;	×
UNCOV 95	bool is_strict = false;	×
UNCOV 96	symbolic::Expression lhs;	×
UNCOV 97	symbolic::Expression rhs;	×
UNCOV 98	if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {	×
99	auto condition_LE = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(condition);	×
100	lhs = condition_LE->get_arg1();	×
101	rhs = condition_LE->get_arg2();	×
UNCOV 102	} else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
UNCOV 103	auto condition_LT = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(condition);	×
UNCOV 104	lhs = condition_LT->get_arg1();	×
UNCOV 105	rhs = condition_LT->get_arg2();	×
UNCOV 106	is_strict = true;	×
UNCOV 107	} else {	×
108	return symbolic::zero();	×
109	}
110
UNCOV 111	if (symbolic::eq(lhs, index_var)) {	×
UNCOV 112	bound = rhs;	×
UNCOV 113	} else {	×
114	return symbolic::zero();	×
115	}
116
UNCOV 117	if (!is_strict) {	×
118	bound = symbolic::add(bound, symbolic::one());	×
119	}	×
120
121	// subtract the init value from the bound
UNCOV 122	bound = symbolic::sub(bound, init);	×
123
UNCOV 124	symbolic::Expression num_iterations;	×
125
UNCOV 126	if (symbolic::eq(stride, symbolic::one())) {	×
UNCOV 127	num_iterations = bound;	×
UNCOV 128	} else if (symbolic::eq(stride, symbolic::zero())) {	×
129	throw std::runtime_error("Stride is zero");	×
130	} else {
131	num_iterations = symbolic::ceil(symbolic::div(bound, stride));	×
132	}
133
UNCOV 134	return num_iterations;	×
UNCOV 135	}	×
136
UNCOV 137	void For2Map::apply(structured_control_flow::For& for_stmt, builder::StructuredSDFGBuilder& builder,	×
138	analysis::AnalysisManager& analysis_manager) {
UNCOV 139	auto num_iterations = this->num_iterations(for_stmt, analysis_manager);	×
140
UNCOV 141	auto init = for_stmt.init();	×
UNCOV 142	auto indvar = for_stmt.indvar();	×
UNCOV 143	auto update = for_stmt.update();	×
144
UNCOV 145	auto& parent = builder.parent(for_stmt);	×
146
147	// Create map
UNCOV 148	auto& map = builder.convert_for(parent, for_stmt, num_iterations);	×
UNCOV 149	auto& root = map.root();	×
UNCOV 150	auto stride = symbolic::subs(update, indvar, symbolic::zero());	×
151
UNCOV 152	auto replacement = symbolic::add(symbolic::mul(map.indvar(), stride), init);	×
UNCOV 153	root.replace(map.indvar(), replacement);	×
154
UNCOV 155	auto successor = builder.add_block_after(parent, map);	×
UNCOV 156	successor.second.assignments().insert({indvar, num_iterations});	×
UNCOV 157	}	×
158
UNCOV 159	bool For2Map::accept(structured_control_flow::Sequence& parent,	×
160	structured_control_flow::For& node) {
UNCOV 161	if (!this->can_be_applied(node, analysis_manager_)) {	×
UNCOV 162	return false;	×
163	}
164
UNCOV 165	this->apply(node, builder_, analysis_manager_);	×
UNCOV 166	return true;	×
UNCOV 167	}	×
168
169	} // namespace passes
170	} // 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