15133758385

Committed 20 May 2025 09:19AM UTC coverage: 60.543% (-3.0%) from 63.542%

Build # 15133758385

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #22 from daisytuner/normalization

Removes normalization passes

Run Details

7922 of 13085 relevant lines covered (60.54%)

104.24 hits per line

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

87.27

/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());
        }
    }
};

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

daisytuner / sdfglib / 15133758385

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