15494289007

Committed 06 Jun 2025 03:36PM UTC coverage: 57.304% (-0.4%) from 57.704%

Build # 15494289007

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #60 from daisytuner/kernels

removes kernel node in favor of function types

Run Details

78 of 99 new or added lines in 11 files covered. (78.79%)

91 existing lines in 14 files now uncovered.

7583 of 13233 relevant lines covered (57.3%)

116.04 hits per line

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

74.24

/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 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::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()) {	356✔
19	auto current = queue.front();	303✔
20	queue.pop_front();	303✔
21
22	if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(current)) {	303✔
23	this->visit_block(block_stmt);	80✔
24	} else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	303✔
25	this->visit_sequence(sequence_stmt);	138✔
26	for (size_t i = 0; i < sequence_stmt->size(); i++) {	303✔
27	queue.push_back(&sequence_stmt->at(i).first);	165✔
28	}	165✔
29	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	223✔
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)) {	85✔
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)) {	85✔
38	this->visit_for(for_stmt);	85✔
39	queue.push_back(&for_stmt->root());	85✔
40	} else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {	85✔
UNCOV 41	this->visit_map(map_stmt);	×
42	queue.push_back(&map_stmt->root());	×
43	}	×
44	}
45	};	53✔
46
47	void AssumptionsAnalysis::visit_block(structured_control_flow::Block* block) { return; };	80✔
48
49	void AssumptionsAnalysis::visit_sequence(structured_control_flow::Sequence* sequence) { return; };	138✔
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) {	85✔
56	if (symbolic::strict_monotonicity(for_loop->update(), for_loop->indvar()) !=	85✔
57	symbolic::Sign::POSITIVE) {
58	return;	×
59	}
60
61	auto& body = for_loop->root();	85✔
62	if (this->assumptions_.find(&body) == this->assumptions_.end()) {	85✔
63	this->assumptions_.insert({&body, symbolic::Assumptions()});	85✔
64	}	85✔
65	auto& body_assumptions = this->assumptions_[&body];	85✔
66
67	auto indvar = for_loop->indvar();	85✔
68	this->iterators_.push_back(indvar->get_name());	85✔
69	auto sym = indvar;	85✔
70
71	auto update = for_loop->update();	85✔
72	if (body_assumptions.find(sym) == body_assumptions.end()) {	85✔
73	body_assumptions.insert({sym, symbolic::Assumption(sym)});	85✔
74	}	85✔
75	body_assumptions[sym].map(update);	85✔
76
77	auto init = for_loop->init();	85✔
78	body_assumptions[sym].lower_bound(init);	85✔
79
80	auto condition = for_loop->condition();	85✔
81	auto args = condition->get_args();	85✔
82	if (SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	85✔
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)));	63✔
87	}	63✔
88	} else if (SymEngine::is_a<SymEngine::LessThan>(*condition)) {	85✔
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)) {	20✔
95	auto args = condition->get_args();	20✔
96	body_assumptions[sym].upper_bound(symbolic::infty(1));	20✔
97	for (auto arg : args) {	60✔
98	if (SymEngine::is_a<SymEngine::StrictLessThan>(*arg)) {	40✔
99	auto args = arg->get_args();	38✔
100	auto arg_0 = args[0];	38✔
101	auto arg_1 = args[1];	38✔
102	if (symbolic::eq(arg_0, indvar)) {	38✔
103	auto old_ub = body_assumptions[sym].upper_bound();	38✔
104	auto new_ub = symbolic::min(old_ub, symbolic::sub(arg_1, symbolic::integer(1)));	38✔
105	body_assumptions[sym].upper_bound(new_ub);	38✔
106	}	38✔
107	} else if (SymEngine::is_a<SymEngine::LessThan>(*arg)) {	40✔
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	}	40✔
118	}	20✔
119	};	85✔
120
121	void AssumptionsAnalysis::visit_map(const structured_control_flow::Map* map) {	×
122	auto& body = map->root();	×
123	if (this->assumptions_.find(&body) == this->assumptions_.end()) {	×
124	this->assumptions_.insert({&body, symbolic::Assumptions()});	×
125	}	×
126
127	auto& body_assumptions = this->assumptions_[&body];	×
128	auto indvar = map->indvar();	×
129	this->iterators_.push_back(indvar->get_name());	×
130	auto sym = indvar;	×
131	auto num_iterations = map->num_iterations();	×
132
133	if (body_assumptions.find(sym) == body_assumptions.end()) {	×
134	body_assumptions.insert({sym, symbolic::Assumption(sym)});	×
135	}	×
136
137	body_assumptions[sym].lower_bound(symbolic::zero());	×
138	body_assumptions[sym].upper_bound(num_iterations);	×
139	}	×
140
141	void AssumptionsAnalysis::run(analysis::AnalysisManager& analysis_manager) {	53✔
142	this->assumptions_.clear();	53✔
143
144	this->assumptions_.insert({&sdfg_.root(), symbolic::Assumptions()});	53✔
145	for (auto& entry : sdfg_.assumptions()) {	310✔
146	this->assumptions_[&sdfg_.root()][entry.first] = entry.second;	257✔
147	}
148	for (auto& entry : this->additional_assumptions_) {	53✔
149	this->assumptions_[&sdfg_.root()][entry.first] = entry.second;	×
150	}
151
152	this->traverse(sdfg_.root());	53✔
153	};	53✔
154
155	AssumptionsAnalysis::AssumptionsAnalysis(StructuredSDFG& sdfg)	106✔
156	: Analysis(sdfg) {	53✔
157
158	};	53✔
159
160	const symbolic::Assumptions AssumptionsAnalysis::get(	85✔
161	structured_control_flow::ControlFlowNode& node) {
162	// TODO: Proper inference based on scope nesting
163	symbolic::Assumptions assums;	85✔
164	for (auto& entry : this->assumptions_) {	377✔
165	if (entry.first == &sdfg_.root()) {	292✔
166	continue;	85✔
167	}
168	for (auto& entry_ : entry.second) {	414✔
169	assums[entry_.first] = entry_.second;	207✔
170	}
171	}
172	for (auto entry : this->assumptions_[&sdfg_.root()]) {	592✔
173	if (assums.find(entry.first) != assums.end()) {	507✔
174	continue;	207✔
175	}
176	assums[entry.first] = entry.second;	300✔
177	}	507✔
178
179	return assums;	85✔
180	};	85✔
181
182	} // namespace analysis
183	} // namespace sdfg

daisytuner / sdfglib / 15494289007

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