15777275738

Committed 20 Jun 2025 10:49AM UTC coverage: 64.573% (-0.02%) from 64.591%

Build # 15777275738

Build Type

Pull #95

github

Committed by

web-flow

Commit Message

Merge 8fc903d42 into 37b47b09d

Pull Request Pull Request #95: Extends Data Dependency Analysis

Run Details

215 of 298 new or added lines in 8 files covered. (72.15%)

22 existing lines in 3 files now uncovered.

8213 of 12719 relevant lines covered (64.57%)

152.49 hits per line

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

84.0

/src/passes/structured_control_flow/for2map.cpp

#include "sdfg/passes/structured_control_flow/for2map.h"

#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/loop_dependency_analysis.h"
#include "sdfg/analysis/scope_analysis.h"

namespace sdfg {
namespace passes {

For2Map::For2Map(builder::StructuredSDFGBuilder& builder,
                 analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {

      };

bool For2Map::can_be_applied(structured_control_flow::For& for_stmt,
                             analysis::AnalysisManager& analysis_manager) {
    std::cout << "For2Map: " << for_stmt.indvar()->get_name() << std::endl;

    // Criterion: loop must be contiguous
    // Simplification to reason about memory offsets and bounds
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    if (!loop_analysis.is_contiguous(&for_stmt)) {
        std::cout << "Loop is not contiguous" << std::endl;
        return false;
    }

    // Criterion: loop condition can be written as a closed-form expression.
    // Closed-form: i < expression_no_i
    // Example: i < N && i < M -> i < min(N, M)
    auto bound = loop_analysis.canonical_bound(&for_stmt);
    if (bound == SymEngine::null) {
        std::cout << "Loop has no canonical bound" << std::endl;
        return false;
    }

    // Criterion: loop must be data-parallel w.r.t containers
    auto& loop_dependency_analysis = analysis_manager.get<analysis::LoopDependencyAnalysis>();
    auto dependencies = loop_dependency_analysis.get(for_stmt);

    // a. No true dependencies (RAW) between iterations
    for (auto& dep : dependencies) {
        if (dep.second == analysis::LoopCarriedDependency::RAW) {
            std::cout << "Loop has true dependency: " << dep.first << std::endl;
            return false;
        }
    }

    // b. False dependencies (WAW) are limited to loop-local variables
    auto& users = analysis_manager.get<analysis::Users>();
    auto locals = users.locals(for_stmt.root());
    for (auto& dep : dependencies) {
        auto& container = dep.first;
        if (locals.find(container) == locals.end()) {
            std::cout << "Loop has false dependency: " << container << " is a local variable"
                      << std::endl;
            return false;
        }
    }

    return true;
}

void For2Map::apply(structured_control_flow::For& for_stmt, builder::StructuredSDFGBuilder& builder,
                    analysis::AnalysisManager& analysis_manager) {
    // Contiguous and canonical bound -> we can compute the number of iterations
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto init = for_stmt.init();
    auto num_iterations = symbolic::sub(loop_analysis.canonical_bound(&for_stmt), init);

    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
    auto parent =
        static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(&for_stmt));

    // convert for to map
    auto& map = builder.convert_for(*parent, for_stmt, num_iterations);
    auto& indvar = map.indvar();

    // Shift indvar by init in body
    auto shift = symbolic::add(indvar, init);
    map.root().replace(indvar, shift);

    // set indvar to last value of a sequential loop
    auto successor = builder.add_block_after(*parent, map);
    auto last_value = symbolic::add(init, num_iterations);
    successor.second.assignments().insert({indvar, last_value});
}

bool For2Map::accept(structured_control_flow::Sequence& parent,
                     structured_control_flow::For& node) {
    if (!this->can_be_applied(node, analysis_manager_)) {
        return false;
    }

    this->apply(node, builder_, analysis_manager_);
    return true;
}

}  // namespace passes
}  // namespace sdfg

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

daisytuner / sdfglib / 15777275738

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