15786981077

Committed 20 Jun 2025 08:10PM UTC coverage: 63.099% (-1.5%) from 64.591%

Build # 15786981077

Build Type

Pull #95

github

Committed by

web-flow

Commit Message

Merge 5ba871611 into 37b47b09d

Pull Request Pull Request #95: Extends Data Dependency Analysis

Run Details

716 of 894 new or added lines in 19 files covered. (80.09%)

95 existing lines in 7 files now uncovered.

7787 of 12341 relevant lines covered (63.1%)

134.34 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/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/analysis/scope_analysis.h"
6
7	namespace sdfg {
8	namespace passes {
9
UNCOV 10	For2Map::For2Map(builder::StructuredSDFGBuilder& builder,	×
11	analysis::AnalysisManager& analysis_manager)
UNCOV 12	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {	×
13
UNCOV 14	};	×
15
UNCOV 16	bool For2Map::can_be_applied(structured_control_flow::For& for_stmt,	×
17	analysis::AnalysisManager& analysis_manager) {
NEW 18	std::cout << "For2Map: " << for_stmt.indvar()->get_name() << std::endl;	×
19
20	// Criterion: loop must be contiguous
21	// Simplification to reason about memory offsets and bounds
NEW 22	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	×
NEW 23	if (!analysis::LoopAnalysis::is_contiguous(&for_stmt, assumptions_analysis)) {	×
NEW 24	std::cout << "Loop is not contiguous" << std::endl;	×
UNCOV 25	return false;	×
26	}
27
28	// Criterion: loop condition can be written as a closed-form expression.
29	// Closed-form: i < expression_no_i
30	// Example: i < N && i < M -> i < min(N, M)
NEW 31	auto bound = analysis::LoopAnalysis::canonical_bound(&for_stmt, assumptions_analysis);	×
UNCOV 32	if (bound == SymEngine::null) {	×
NEW 33	std::cout << "Loop has no canonical bound" << std::endl;	×
UNCOV 34	return false;	×
35	}
36
37	// Criterion: loop must be data-parallel w.r.t containers
NEW 38	return false;	×
39
40	/*
41	auto& loop_dependency_analysis = analysis_manager.get<analysis::LoopDependencyAnalysis>();
42	auto dependencies = loop_dependency_analysis.get(for_stmt);
43
44	// a. No true dependencies (RAW) between iterations
45	for (auto& dep : dependencies) {
46	if (dep.second == analysis::LoopCarriedDependency::RAW) {
47	std::cout << "Loop has true dependency: " << dep.first << std::endl;
48	return false;
49	}
50	}
51
52	// b. False dependencies (WAW) are limited to loop-local variables
53	auto& users = analysis_manager.get<analysis::Users>();
54	auto locals = users.locals(for_stmt.root());
55	for (auto& dep : dependencies) {
56	auto& container = dep.first;
57	if (locals.find(container) == locals.end()) {
58	std::cout << "Loop has false dependency: " << container << " is a local variable"
59	<< std::endl;
60	return false;
61	}
62	}
63	*/
64
65	return true;
UNCOV 66	}	×
67
UNCOV 68	void For2Map::apply(structured_control_flow::For& for_stmt, builder::StructuredSDFGBuilder& builder,	×
69	analysis::AnalysisManager& analysis_manager) {
70	// Contiguous and canonical bound -> we can compute the number of iterations
UNCOV 71	auto init = for_stmt.init();	×
NEW 72	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	×
NEW 73	auto num_iterations = symbolic::sub(	×
NEW 74	analysis::LoopAnalysis::canonical_bound(&for_stmt, assumptions_analysis), init);	×
75
UNCOV 76	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
UNCOV 77	auto parent =	×
UNCOV 78	static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));	×
79
80	// convert for to map
UNCOV 81	auto& map = builder.convert_for(*parent, for_stmt, num_iterations);	×
UNCOV 82	auto& indvar = map.indvar();	×
83
84	// Shift indvar by init in body
UNCOV 85	auto shift = symbolic::add(indvar, init);	×
UNCOV 86	map.root().replace(indvar, shift);	×
87
88	// set indvar to last value of a sequential loop
UNCOV 89	auto successor = builder.add_block_after(*parent, map);	×
UNCOV 90	auto last_value = symbolic::add(init, num_iterations);	×
UNCOV 91	successor.second.assignments().insert({indvar, last_value});	×
UNCOV 92	}	×
93
UNCOV 94	bool For2Map::accept(structured_control_flow::Sequence& parent,	×
95	structured_control_flow::For& node) {
UNCOV 96	if (!this->can_be_applied(node, analysis_manager_)) {	×
UNCOV 97	return false;	×
98	}
99
UNCOV 100	this->apply(node, builder_, analysis_manager_);	×
UNCOV 101	return true;	×
UNCOV 102	}	×
103
104	} // namespace passes
105	} // namespace sdfg

daisytuner / sdfglib / 15786981077

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