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

78.26

/src/analysis/assumptions_analysis.cpp

#include "sdfg/analysis/assumptions_analysis.h"

#include <utility>
#include <vector>

#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/symbolic/analysis.h"
#include "sdfg/symbolic/assumptions.h"
#include "sdfg/symbolic/symbolic.h"
#include "symengine/basic.h"
#include "symengine/symbol.h"

namespace sdfg {
namespace analysis {

void AssumptionsAnalysis::traverse(structured_control_flow::Sequence& root) {
    std::list<structured_control_flow::ControlFlowNode*> queue = {&root};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(current)) {
            this->visit_block(block_stmt);
        } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            this->visit_sequence(sequence_stmt);
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            this->visit_if_else(if_else_stmt);
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
                queue.push_back(&if_else_stmt->at(i).first);
            }
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            this->visit_while(while_stmt);
            queue.push_back(&while_stmt->root());
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
            this->visit_for(for_stmt);
            queue.push_back(&for_stmt->root());
        } else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {
            this->visit_kernel(kern_stmt);
            queue.push_back(&kern_stmt->root());
        } else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {
            this->visit_map(map_stmt);
            queue.push_back(&map_stmt->root());
        }
    }
};

void AssumptionsAnalysis::visit_block(structured_control_flow::Block* block) { return; };

void AssumptionsAnalysis::visit_sequence(structured_control_flow::Sequence* sequence) { return; };

void AssumptionsAnalysis::visit_if_else(structured_control_flow::IfElse* if_else) { return; };

void AssumptionsAnalysis::visit_while(structured_control_flow::While* while_loop) { return; };

void AssumptionsAnalysis::visit_for(structured_control_flow::For* for_loop) {
    if (symbolic::strict_monotonicity(for_loop->update(), for_loop->indvar()) !=
        symbolic::Sign::POSITIVE) {
        return;
    }

    auto& body = for_loop->root();
    if (this->assumptions_.find(&body) == this->assumptions_.end()) {
        this->assumptions_.insert({&body, symbolic::Assumptions()});
    }
    auto& body_assumptions = this->assumptions_[&body];

    auto indvar = for_loop->indvar();
    this->iterators_.push_back(indvar->get_name());
    auto sym = indvar;

    auto update = for_loop->update();
    if (body_assumptions.find(sym) == body_assumptions.end()) {
        body_assumptions.insert({sym, symbolic::Assumption(sym)});
    }
    body_assumptions[sym].map(update);

    auto init = for_loop->init();
    body_assumptions[sym].lower_bound(init);

    auto condition = for_loop->condition();
    auto args = condition->get_args();
    if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        auto arg_0 = args[0];
        auto arg_1 = args[1];
        if (symbolic::eq(arg_0, indvar)) {
            body_assumptions[sym].upper_bound(symbolic::sub(arg_1, symbolic::integer(1)));
        }
    } else if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {
        auto arg_0 = args[0];
        auto arg_1 = args[1];
        if (symbolic::eq(arg_0, indvar)) {
            body_assumptions[sym].upper_bound(arg_1);
        }
    } else if (SymEngine::is_a<SymEngine::And>(*condition)) {
        auto args = condition->get_args();
        body_assumptions[sym].upper_bound(symbolic::infty(1));
        for (auto arg : args) {
            if (SymEngine::is_a<SymEngine::StrictLessThan>(*arg)) {
                auto args = arg->get_args();
                auto arg_0 = args[0];
                auto arg_1 = args[1];
                if (symbolic::eq(arg_0, indvar)) {
                    auto old_ub = body_assumptions[sym].upper_bound();
                    auto new_ub = symbolic::min(old_ub, symbolic::sub(arg_1, symbolic::integer(1)));
                    body_assumptions[sym].upper_bound(new_ub);
                }
            } else if (SymEngine::is_a<SymEngine::LessThan>(*arg)) {
                auto args = arg->get_args();
                auto arg_0 = args[0];
                auto arg_1 = args[1];
                if (symbolic::eq(arg_0, indvar)) {
                    auto old_ub = body_assumptions[sym].upper_bound();
                    auto new_ub = symbolic::min(old_ub, arg_1);
                    body_assumptions[sym].upper_bound(new_ub);
                }
            }
        }
    }
};

void AssumptionsAnalysis::visit_map(const structured_control_flow::Map* map) {
    auto& body = map->root();
    if (this->assumptions_.find(&body) == this->assumptions_.end()) {
        this->assumptions_.insert({&body, symbolic::Assumptions()});
    }

    auto& body_assumptions = this->assumptions_[&body];
    auto indvar = map->indvar();
    this->iterators_.push_back(indvar->get_name());
    auto sym = indvar;
    auto num_iterations = map->num_iterations();

    if (body_assumptions.find(sym) == body_assumptions.end()) {
        body_assumptions.insert({sym, symbolic::Assumption(sym)});
    }

    body_assumptions[sym].lower_bound(symbolic::zero());
    body_assumptions[sym].upper_bound(num_iterations);
}

void AssumptionsAnalysis::visit_kernel(const structured_control_flow::Kernel* kernel) {
    auto& body = kernel->root();
    if (this->assumptions_.find(&body) == this->assumptions_.end()) {
        this->assumptions_.insert({&body, symbolic::Assumptions()});
    }
    auto& body_assumptions = this->assumptions_[&body];

    auto global_assumptions = this->assumptions_[&sdfg_.root()];

    std::vector<std::pair<symbolic::Symbol, symbolic::Expression>> dimensions = {
        {kernel->blockDim_x(), kernel->blockDim_x_init()},
        {kernel->blockDim_y(), kernel->blockDim_y_init()},
        {kernel->blockDim_z(), kernel->blockDim_z_init()},
        {kernel->gridDim_x(), kernel->gridDim_x_init()},
        {kernel->gridDim_y(), kernel->gridDim_y_init()},
        {kernel->gridDim_z(), kernel->gridDim_z_init()},
    };

    // Augment body assumptions by global assumptions
    for (auto& entry : dimensions) {
        for (auto& atom : symbolic::atoms(entry.second)) {
            auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
            if (global_assumptions.find(sym) != global_assumptions.end()) {
                if (body_assumptions.find(sym) == body_assumptions.end()) {
                    body_assumptions.insert({sym, symbolic::Assumption(sym)});
                    body_assumptions[sym].lower_bound(global_assumptions[sym].lower_bound());
                    body_assumptions[sym].upper_bound(global_assumptions[sym].upper_bound());
                }
            }
        }
    }

    for (auto& entry : dimensions) {
        auto& dim = entry.first;
        auto& init = entry.second;
        body_assumptions[dim].lower_bound(symbolic::lower_bound_analysis(init, body_assumptions));
        body_assumptions[dim].upper_bound(symbolic::upper_bound_analysis(init, body_assumptions));
    }

    body_assumptions[kernel->blockIdx_x()].lower_bound(symbolic::zero());
    body_assumptions[kernel->blockIdx_y()].lower_bound(symbolic::zero());
    body_assumptions[kernel->blockIdx_z()].lower_bound(symbolic::zero());

    body_assumptions[kernel->blockIdx_x()].upper_bound(
        symbolic::sub(kernel->gridDim_x(), symbolic::integer(1)));
    body_assumptions[kernel->blockIdx_y()].upper_bound(
        symbolic::sub(kernel->gridDim_y(), symbolic::integer(1)));
    body_assumptions[kernel->blockIdx_z()].upper_bound(
        symbolic::sub(kernel->gridDim_z(), symbolic::integer(1)));

    body_assumptions[kernel->threadIdx_x()].lower_bound(symbolic::zero());
    body_assumptions[kernel->threadIdx_y()].lower_bound(symbolic::zero());
    body_assumptions[kernel->threadIdx_z()].lower_bound(symbolic::zero());

    body_assumptions[kernel->threadIdx_x()].upper_bound(
        symbolic::sub(kernel->blockDim_x(), symbolic::integer(1)));
    body_assumptions[kernel->threadIdx_y()].upper_bound(
        symbolic::sub(kernel->blockDim_y(), symbolic::integer(1)));
    body_assumptions[kernel->threadIdx_z()].upper_bound(
        symbolic::sub(kernel->blockDim_z(), symbolic::integer(1)));
}

void AssumptionsAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    this->assumptions_.clear();

    this->assumptions_.insert({&sdfg_.root(), symbolic::Assumptions()});
    for (auto& entry : sdfg_.assumptions()) {
        this->assumptions_[&sdfg_.root()][entry.first] = entry.second;
    }
    for (auto& entry : this->additional_assumptions_) {
        this->assumptions_[&sdfg_.root()][entry.first] = entry.second;
    }

    this->traverse(sdfg_.root());
};

AssumptionsAnalysis::AssumptionsAnalysis(StructuredSDFG& sdfg)
    : Analysis(sdfg) {

      };

const symbolic::Assumptions AssumptionsAnalysis::get(
    structured_control_flow::ControlFlowNode& node) {
    // TODO: Proper inference based on scope nesting
    symbolic::Assumptions assums;
    for (auto& entry : this->assumptions_) {
        if (entry.first == &sdfg_.root()) {
            continue;
        }
        for (auto& entry_ : entry.second) {
            assums[entry_.first] = entry_.second;
        }
    }
    for (auto entry : this->assumptions_[&sdfg_.root()]) {
        if (assums.find(entry.first) != assums.end()) {
            continue;
        }
        assums[entry.first] = entry.second;
    }

    return assums;
};

}  // namespace analysis
}  // namespace sdfg

1	#include "sdfg/analysis/assumptions_analysis.h"
2
3	#include <utility>
4	#include <vector>
5
6	#include "sdfg/structured_control_flow/sequence.h"
7	#include "sdfg/symbolic/analysis.h"
8	#include "sdfg/symbolic/assumptions.h"
9	#include "sdfg/symbolic/symbolic.h"
10	#include "symengine/basic.h"
11	#include "symengine/symbol.h"
12
13	namespace sdfg {
14	namespace analysis {
15
16	void AssumptionsAnalysis::traverse(structured_control_flow::Sequence& root) {	53✔
17	std::list<structured_control_flow::ControlFlowNode*> queue = {&root};	53✔
18	while (!queue.empty()) {	372✔
19	auto current = queue.front();	319✔
20	queue.pop_front();	319✔
21
22	if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(current)) {	319✔
23	this->visit_block(block_stmt);	80✔
24	} else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	319✔
25	this->visit_sequence(sequence_stmt);	146✔
26	for (size_t i = 0; i < sequence_stmt->size(); i++) {	319✔
27	queue.push_back(&sequence_stmt->at(i).first);	173✔
28	}	173✔
29	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	239✔
30	this->visit_if_else(if_else_stmt);	×
31	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
32	queue.push_back(&if_else_stmt->at(i).first);	×
33	}	×
34	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	93✔
35	this->visit_while(while_stmt);	×
36	queue.push_back(&while_stmt->root());	×
37	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	93✔
38	this->visit_for(for_stmt);	85✔
39	queue.push_back(&for_stmt->root());	85✔
40	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	93✔
41	this->visit_kernel(kern_stmt);	8✔
42	queue.push_back(&kern_stmt->root());	8✔
43	} else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {	8✔
NEW 44	this->visit_map(map_stmt);	×
NEW 45	queue.push_back(&map_stmt->root());	×
UNCOV 46	}	×
47	}
48	};	53✔
49
50	void AssumptionsAnalysis::visit_block(structured_control_flow::Block* block) { return; };	80✔
51
52	void AssumptionsAnalysis::visit_sequence(structured_control_flow::Sequence* sequence) { return; };	146✔
53
54	void AssumptionsAnalysis::visit_if_else(structured_control_flow::IfElse* if_else) { return; };	×
55
56	void AssumptionsAnalysis::visit_while(structured_control_flow::While* while_loop) { return; };	×
57
58	void AssumptionsAnalysis::visit_for(structured_control_flow::For* for_loop) {	85✔
59	if (symbolic::strict_monotonicity(for_loop->update(), for_loop->indvar()) !=	85✔
60	symbolic::Sign::POSITIVE) {
61	return;	×
62	}
63
64	auto& body = for_loop->root();	85✔
65	if (this->assumptions_.find(&body) == this->assumptions_.end()) {	85✔
66	this->assumptions_.insert({&body, symbolic::Assumptions()});	85✔
67	}	85✔
68	auto& body_assumptions = this->assumptions_[&body];	85✔
69
70	auto indvar = for_loop->indvar();	85✔
71	this->iterators_.push_back(indvar->get_name());	85✔
72	auto sym = indvar;	85✔
73
74	auto update = for_loop->update();	85✔
75	if (body_assumptions.find(sym) == body_assumptions.end()) {	85✔
76	body_assumptions.insert({sym, symbolic::Assumption(sym)});	85✔
77	}	85✔
78	body_assumptions[sym].map(update);	85✔
79
80	auto init = for_loop->init();	85✔
81	body_assumptions[sym].lower_bound(init);	85✔
82
83	auto condition = for_loop->condition();	85✔
84	auto args = condition->get_args();	85✔
85	if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	85✔
86	auto arg_0 = args[0];	65✔
87	auto arg_1 = args[1];	65✔
88	if (symbolic::eq(arg_0, indvar)) {	65✔
89	body_assumptions[sym].upper_bound(symbolic::sub(arg_1, symbolic::integer(1)));	63✔
90	}	63✔
91	} else if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {	85✔
92	auto arg_0 = args[0];	×
93	auto arg_1 = args[1];	×
94	if (symbolic::eq(arg_0, indvar)) {	×
95	body_assumptions[sym].upper_bound(arg_1);	×
96	}	×
97	} else if (SymEngine::is_a<SymEngine::And>(*condition)) {	20✔
98	auto args = condition->get_args();	20✔
99	body_assumptions[sym].upper_bound(symbolic::infty(1));	20✔
100	for (auto arg : args) {	60✔
101	if (SymEngine::is_a<SymEngine::StrictLessThan>(*arg)) {	40✔
102	auto args = arg->get_args();	38✔
103	auto arg_0 = args[0];	38✔
104	auto arg_1 = args[1];	38✔
105	if (symbolic::eq(arg_0, indvar)) {	38✔
106	auto old_ub = body_assumptions[sym].upper_bound();	38✔
107	auto new_ub = symbolic::min(old_ub, symbolic::sub(arg_1, symbolic::integer(1)));	38✔
108	body_assumptions[sym].upper_bound(new_ub);	38✔
109	}	38✔
110	} else if (SymEngine::is_a<SymEngine::LessThan>(*arg)) {	40✔
111	auto args = arg->get_args();	2✔
112	auto arg_0 = args[0];	2✔
113	auto arg_1 = args[1];	2✔
114	if (symbolic::eq(arg_0, indvar)) {	2✔
115	auto old_ub = body_assumptions[sym].upper_bound();	2✔
116	auto new_ub = symbolic::min(old_ub, arg_1);	2✔
117	body_assumptions[sym].upper_bound(new_ub);	2✔
118	}	2✔
119	}	2✔
120	}	40✔
121	}	20✔
122	};	85✔
123
NEW 124	void AssumptionsAnalysis::visit_map(const structured_control_flow::Map* map) {	×
NEW 125	auto& body = map->root();	×
NEW 126	if (this->assumptions_.find(&body) == this->assumptions_.end()) {	×
NEW 127	this->assumptions_.insert({&body, symbolic::Assumptions()});	×
NEW 128	}	×
129
NEW 130	auto& body_assumptions = this->assumptions_[&body];	×
NEW 131	auto indvar = map->indvar();	×
NEW 132	this->iterators_.push_back(indvar->get_name());	×
NEW 133	auto sym = indvar;	×
NEW 134	auto num_iterations = map->num_iterations();	×
135
NEW 136	if (body_assumptions.find(sym) == body_assumptions.end()) {	×
NEW 137	body_assumptions.insert({sym, symbolic::Assumption(sym)});	×
NEW 138	}	×
139
NEW 140	body_assumptions[sym].lower_bound(symbolic::zero());	×
NEW 141	body_assumptions[sym].upper_bound(num_iterations);	×
NEW 142	}	×
143
144	void AssumptionsAnalysis::visit_kernel(const structured_control_flow::Kernel* kernel) {	8✔
145	auto& body = kernel->root();	8✔
146	if (this->assumptions_.find(&body) == this->assumptions_.end()) {	8✔
147	this->assumptions_.insert({&body, symbolic::Assumptions()});	8✔
148	}	8✔
149	auto& body_assumptions = this->assumptions_[&body];	8✔
150
151	auto global_assumptions = this->assumptions_[&sdfg_.root()];	8✔
152
153	std::vector<std::pair<symbolic::Symbol, symbolic::Expression>> dimensions = {	56✔
154	{kernel->blockDim_x(), kernel->blockDim_x_init()},	8✔
155	{kernel->blockDim_y(), kernel->blockDim_y_init()},	8✔
156	{kernel->blockDim_z(), kernel->blockDim_z_init()},	8✔
157	{kernel->gridDim_x(), kernel->gridDim_x_init()},	8✔
158	{kernel->gridDim_y(), kernel->gridDim_y_init()},	8✔
159	{kernel->gridDim_z(), kernel->gridDim_z_init()},	8✔
160	};
161
162	// Augment body assumptions by global assumptions
163	for (auto& entry : dimensions) {	56✔
164	for (auto& atom : symbolic::atoms(entry.second)) {	72✔
165	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	24✔
166	if (global_assumptions.find(sym) != global_assumptions.end()) {	24✔
167	if (body_assumptions.find(sym) == body_assumptions.end()) {	×
168	body_assumptions.insert({sym, symbolic::Assumption(sym)});	×
169	body_assumptions[sym].lower_bound(global_assumptions[sym].lower_bound());	×
170	body_assumptions[sym].upper_bound(global_assumptions[sym].upper_bound());	×
171	}	×
172	}	×
173	}	24✔
174	}
175
176	for (auto& entry : dimensions) {	56✔
177	auto& dim = entry.first;	48✔
178	auto& init = entry.second;	48✔
179	body_assumptions[dim].lower_bound(symbolic::lower_bound_analysis(init, body_assumptions));	48✔
180	body_assumptions[dim].upper_bound(symbolic::upper_bound_analysis(init, body_assumptions));	48✔
181	}
182
183	body_assumptions[kernel->blockIdx_x()].lower_bound(symbolic::zero());	8✔
184	body_assumptions[kernel->blockIdx_y()].lower_bound(symbolic::zero());	8✔
185	body_assumptions[kernel->blockIdx_z()].lower_bound(symbolic::zero());	8✔
186
187	body_assumptions[kernel->blockIdx_x()].upper_bound(	16✔
188	symbolic::sub(kernel->gridDim_x(), symbolic::integer(1)));	8✔
189	body_assumptions[kernel->blockIdx_y()].upper_bound(	16✔
190	symbolic::sub(kernel->gridDim_y(), symbolic::integer(1)));	8✔
191	body_assumptions[kernel->blockIdx_z()].upper_bound(	16✔
192	symbolic::sub(kernel->gridDim_z(), symbolic::integer(1)));	8✔
193
194	body_assumptions[kernel->threadIdx_x()].lower_bound(symbolic::zero());	8✔
195	body_assumptions[kernel->threadIdx_y()].lower_bound(symbolic::zero());	8✔
196	body_assumptions[kernel->threadIdx_z()].lower_bound(symbolic::zero());	8✔
197
198	body_assumptions[kernel->threadIdx_x()].upper_bound(	16✔
199	symbolic::sub(kernel->blockDim_x(), symbolic::integer(1)));	8✔
200	body_assumptions[kernel->threadIdx_y()].upper_bound(	16✔
201	symbolic::sub(kernel->blockDim_y(), symbolic::integer(1)));	8✔
202	body_assumptions[kernel->threadIdx_z()].upper_bound(	16✔
203	symbolic::sub(kernel->blockDim_z(), symbolic::integer(1)));	8✔
204	}	8✔
205
206	void AssumptionsAnalysis::run(analysis::AnalysisManager& analysis_manager) {	53✔
207	this->assumptions_.clear();	53✔
208
209	this->assumptions_.insert({&sdfg_.root(), symbolic::Assumptions()});	53✔
210	for (auto& entry : sdfg_.assumptions()) {	262✔
211	this->assumptions_[&sdfg_.root()][entry.first] = entry.second;	209✔
212	}
213	for (auto& entry : this->additional_assumptions_) {	53✔
214	this->assumptions_[&sdfg_.root()][entry.first] = entry.second;	×
215	}
216
217	this->traverse(sdfg_.root());	53✔
218	};	53✔
219
220	AssumptionsAnalysis::AssumptionsAnalysis(StructuredSDFG& sdfg)	106✔
221	: Analysis(sdfg) {	53✔
222
223	};	53✔
224
225	const symbolic::Assumptions AssumptionsAnalysis::get(	88✔
226	structured_control_flow::ControlFlowNode& node) {
227	// TODO: Proper inference based on scope nesting
228	symbolic::Assumptions assums;	88✔
229	for (auto& entry : this->assumptions_) {	408✔
230	if (entry.first == &sdfg_.root()) {	320✔
231	continue;	88✔
232	}
233	for (auto& entry_ : entry.second) {	640✔
234	assums[entry_.first] = entry_.second;	408✔
235	}
236	}
237	for (auto entry : this->assumptions_[&sdfg_.root()]) {	547✔
238	if (assums.find(entry.first) != assums.end()) {	459✔
239	continue;	312✔
240	}
241	assums[entry.first] = entry.second;	147✔
242	}	459✔
243
244	return assums;	88✔
245	};	88✔
246
247	} // namespace analysis
248	} // 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