15781182351

Committed 20 Jun 2025 02:27PM UTC coverage: 62.978% (-1.6%) from 64.591%

Build # 15781182351

Build Type

Pull #95

github

Committed by

web-flow

Commit Message

Merge 3b6e445ac into 37b47b09d

Pull Request Pull Request #95: Extends Data Dependency Analysis

Run Details

393 of 500 new or added lines in 10 files covered. (78.6%)

114 existing lines in 7 files now uncovered.

7752 of 12309 relevant lines covered (62.98%)

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

daisytuner / sdfglib / 15781182351

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