15340968114

Committed 30 May 2025 06:47AM UTC coverage: 58.553% (+0.2%) from 58.324%

Build # 15340968114

Build Type

push

github

Committed by

web-flow

Commit Message

Add parallel Map node

* Introduce Map data structure

* Prepare infrastructure

* implement analysis support

* Add basic infrastructure

* visualizer/serializer

* include fix

* update from main

* remove default

* happens before test + fixes

* builder test

* dispatcher test

* visitor, copy and serializer tests

* for2map structures

* for2map conversion draft

* add tests

* Bug fixes

* small updates from feedback

* Visitor style pass implementation

* cleanup

* fixes linting errors

---------

Co-authored-by: Lukas Truemper <lukas.truemper@outlook.de>

Run Details

258 of 381 new or added lines in 26 files covered. (67.72%)

17 existing lines in 14 files now uncovered.

8184 of 13977 relevant lines covered (58.55%)

109.83 hits per line

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

85.42

/src/passes/structured_control_flow/for2map.cpp

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

#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"
#include "symengine/basic.h"
#include "symengine/logic.h"
#include "symengine/symengine_rcp.h"

namespace sdfg {
namespace passes {

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

      };

bool For2Map::can_be_applied(const structured_control_flow::For& for_stmt,
                             analysis::AnalysisManager& analysis_manager) {
    // Criterion: loop must be data-parallel w.r.t containers
    auto& analysis = analysis_manager.get<analysis::DataParallelismAnalysis>();
    auto& dependencies = analysis.get(for_stmt);
    if (dependencies.size() == 0) {
        return false;
    }

    // Criterion: update must be normalizable (i.e., it may not be involved in anything but an
    // addition during the update)
    auto& index_var = for_stmt.indvar();
    auto& update = for_stmt.update();

    bool normalizable_update = symbolic::eq(
        symbolic::subs(update, index_var, symbolic::one()),
        symbolic::add(symbolic::subs(update, index_var, symbolic::zero()), symbolic::one()));

    if (!normalizable_update) {
        return false;
    }

    auto stride = symbolic::subs(update, index_var, symbolic::zero());

    // Criterion: loop bound must be simple, less than or equal statement (e.g., i < N)

    auto condition = symbolic::rearrange_simple_condition(for_stmt.condition(), index_var);

    symbolic::Expression bound;
    symbolic::Expression lhs;
    symbolic::Expression rhs;
    if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {
        auto condition_LE = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(condition);
        lhs = condition_LE->get_arg1();
        rhs = condition_LE->get_arg2();
    } else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        auto condition_LT = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(condition);
        lhs = condition_LT->get_arg1();
        rhs = condition_LT->get_arg2();
    } else {
        return false;
    }

    if (!symbolic::eq(lhs, index_var)) {
        return false;
    }

    return true;
}

symbolic::Expression For2Map::num_iterations(const structured_control_flow::For& for_stmt,
                                             analysis::AnalysisManager& analysis_manager) const {
    // Criterion: update must be normalizable (i.e., it may not be involved in anything but an
    // addition during the update)
    auto& index_var = for_stmt.indvar();
    auto& update = for_stmt.update();
    auto& init = for_stmt.init();

    bool normalizable_update = symbolic::eq(
        symbolic::subs(update, index_var, symbolic::one()),
        symbolic::add(symbolic::subs(update, index_var, symbolic::zero()), symbolic::one()));

    if (!normalizable_update) {
        return symbolic::zero();
    }

    auto stride = symbolic::subs(update, index_var, symbolic::zero());

    // Criterion: loop bound must be simple, less than or equal statement (e.g., i < N)

    auto condition = symbolic::rearrange_simple_condition(for_stmt.condition(), index_var);

    symbolic::Expression bound;
    bool is_strict = false;
    symbolic::Expression lhs;
    symbolic::Expression rhs;
    if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {
        auto condition_LE = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(condition);
        lhs = condition_LE->get_arg1();
        rhs = condition_LE->get_arg2();
    } else if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        auto condition_LT = SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(condition);
        lhs = condition_LT->get_arg1();
        rhs = condition_LT->get_arg2();
        is_strict = true;
    } else {
        return symbolic::zero();
    }

    if (symbolic::eq(lhs, index_var)) {
        bound = rhs;
    } else {
        return symbolic::zero();
    }

    if (!is_strict) {
        bound = symbolic::add(bound, symbolic::one());
    }

    // subtract the init value from the bound
    bound = symbolic::sub(bound, init);

    symbolic::Expression num_iterations;

    if (symbolic::eq(stride, symbolic::one())) {
        num_iterations = bound;
    } else if (symbolic::eq(stride, symbolic::zero())) {
        throw std::runtime_error("Stride is zero");
    } else {
        num_iterations = symbolic::ceil(symbolic::div(bound, stride));
    }

    return num_iterations;
}

void For2Map::apply(structured_control_flow::For& for_stmt, builder::StructuredSDFGBuilder& builder,
                    analysis::AnalysisManager& analysis_manager) {
    auto num_iterations = this->num_iterations(for_stmt, analysis_manager);

    auto init = for_stmt.init();
    auto indvar = for_stmt.indvar();
    auto update = for_stmt.update();

    auto& parent = builder.parent(for_stmt);

    // Create map
    auto& map = builder.convert_for(parent, for_stmt, num_iterations);
    auto& root = map.root();
    auto stride = symbolic::subs(update, indvar, symbolic::zero());

    auto replacement = symbolic::add(symbolic::mul(map.indvar(), stride), init);
    root.replace(map.indvar(), replacement);

    auto successor = builder.add_block_after(parent, map);
    successor.second.assignments().insert({indvar, num_iterations});
}

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

daisytuner / sdfglib / 15340968114

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