28158800507

Committed 25 Jun 2026 08:57AM UTC coverage: 61.644% (+0.06%) from 61.582%

Build # 28158800507

Build Type

push

github

Committed by

web-flow

Commit Message

MapFusionByDomain (#771)

 + New Map fusion caches data about iteration domain and map candidates
 + only matches up iteration domain exactly, per loop level.
 + Can support fusing non-leaf stacks of loops (stack ends where the shallower stack stops being perfectly nested & parallel)
 + new Element::replace for bulk replacements
 + New PatternMatcher visitor supports descending into replaced or modified nodes to allow for single-pass nested loop fusings
 + LoopAnalysis can now be kept up-to-date with changes done by Map-fusion
 + unit tests for the updating of LoopAnalysis
 * updated LoopAnalysis to be easier to keep up-to-date with changes. LoopTree is no longer ordered, if you want to iterate in pre-order, use the specific method for that
 + convenience StructuredSDFGBuilder.remove_from_parent()
 + RedundantLoadElim pass to skip reading from memory locations that have just been written (same block). Fusing no longer needs to do this
     RedundantLoadElimination does a simple check for other writes to the same structure. Can skip writes if redundant or not modify, if their are writes to different indices
* Updated verifiers to match new fusion
~ moved verifier checks behind correctness checks in npbench harness. Its more critical if we do not even get the expected results
* Added MapFusionByDomain also to loop-norm stage (currently inactive, causes more kernels that currently cannot be safely offloaded to CUDA.
---------

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

Coverage Stats

771 of 1186 new or added lines in 55 files covered. (65.01%)

6 existing lines in 6 files now uncovered.

38302 of 62134 relevant lines covered (61.64%)

987.24 hits per line

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

76.0

/sdfg/src/structured_control_flow/if_else.cpp

#include "sdfg/structured_control_flow/if_else.h"

#include "sdfg/symbolic/conjunctive_normal_form.h"
#include "sdfg/symbolic/symbolic.h"
#include "symengine/subs.h"

namespace sdfg {
namespace structured_control_flow {

IfElse::IfElse(size_t element_id, const DebugInfo& debug_info, ControlFlowNode* parent)
    : ControlFlowNode(element_id, debug_info, parent) {}

void IfElse::validate(const Function& function) const {
    for (auto& entry : this->cases_) {
        entry->validate(function);
    }
    for (auto& entry : this->conditions_) {
        if (entry.is_null()) {
            throw InvalidSDFGException("IfElse: Conditions cannot be null");
        }
        if (!SymEngine::is_a_Boolean(*entry)) {
            throw InvalidSDFGException("IfElse: Conditions must be boolean expressions");
        }
    }
    if (this->cases_.size() != this->conditions_.size()) {
        throw InvalidSDFGException("IfElse: Number of cases must be equal to number of conditions");
    }
};

size_t IfElse::size() const { return this->cases_.size(); };

std::pair<const Sequence&, const symbolic::Condition> IfElse::at(size_t i) const {
    return {*this->cases_.at(i), this->conditions_.at(i)};
};

std::pair<Sequence&, const symbolic::Condition> IfElse::at(size_t i) {
    return {*this->cases_.at(i), this->conditions_.at(i)};
};

bool IfElse::is_complete() const {
    auto condition = symbolic::__false__();
    for (auto& entry : this->conditions_) {
        condition = symbolic::Or(condition, entry);
    }
    if (symbolic::is_true(condition)) return true;

    symbolic::CNF cnf_cond = symbolic::conjunctive_normal_form(condition);
    for (auto& clause : cnf_cond) {
        if (!symbolic::is_tautology(clause)) {
            return false;
        }
    }
    return true;
};

void IfElse::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    for (size_t i = 0; i < this->cases_.size(); ++i) {
        this->cases_.at(i)->replace(old_expression, new_expression);
        this->conditions_.at(i) = symbolic::subs(this->conditions_.at(i), old_expression, new_expression);
    }
}

void IfElse::replace(const symbolic::ExpressionMapping& replacements) {
    for (size_t i = 0; i < this->cases_.size(); ++i) {
        this->cases_.at(i)->replace(replacements);
        this->conditions_.at(i) = symbolic::subs(this->conditions_.at(i), replacements);
    }
};

} // namespace structured_control_flow
} // namespace sdfg

1	#include "sdfg/structured_control_flow/if_else.h"
2
3	#include "sdfg/symbolic/conjunctive_normal_form.h"
4	#include "sdfg/symbolic/symbolic.h"
5	#include "symengine/subs.h"
6
7	namespace sdfg {
8	namespace structured_control_flow {
9
10	IfElse::IfElse(size_t element_id, const DebugInfo& debug_info, ControlFlowNode* parent)
11	: ControlFlowNode(element_id, debug_info, parent) {}	161✔
12
13	void IfElse::validate(const Function& function) const {	169✔
14	for (auto& entry : this->cases_) {	252✔
15	entry->validate(function);	252✔
16	}	252✔
17	for (auto& entry : this->conditions_) {	252✔
18	if (entry.is_null()) {	252✔
19	throw InvalidSDFGException("IfElse: Conditions cannot be null");	×
20	}	×
21	if (!SymEngine::is_a_Boolean(*entry)) {	252✔
22	throw InvalidSDFGException("IfElse: Conditions must be boolean expressions");	×
23	}	×
24	}	252✔
25	if (this->cases_.size() != this->conditions_.size()) {	169✔
26	throw InvalidSDFGException("IfElse: Number of cases must be equal to number of conditions");	×
27	}	×
28	};	169✔
29
30	size_t IfElse::size() const { return this->cases_.size(); };	1,707✔
31
32	std::pair<const Sequence&, const symbolic::Condition> IfElse::at(size_t i) const {	49✔
33	return {*this->cases_.at(i), this->conditions_.at(i)};	49✔
34	};	49✔
35
36	std::pair<Sequence&, const symbolic::Condition> IfElse::at(size_t i) {	1,172✔
37	return {*this->cases_.at(i), this->conditions_.at(i)};	1,172✔
38	};	1,172✔
39
40	bool IfElse::is_complete() const {	141✔
41	auto condition = symbolic::__false__();	141✔
42	for (auto& entry : this->conditions_) {	223✔
43	condition = symbolic::Or(condition, entry);	223✔
44	}	223✔
45	if (symbolic::is_true(condition)) return true;	141✔
46
47	symbolic::CNF cnf_cond = symbolic::conjunctive_normal_form(condition);	72✔
48	for (auto& clause : cnf_cond) {	82✔
49	if (!symbolic::is_tautology(clause)) {	82✔
50	return false;	65✔
51	}	65✔
52	}	82✔
53	return true;	7✔
54	};	72✔
55
56	void IfElse::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	2✔
57	for (size_t i = 0; i < this->cases_.size(); ++i) {	6✔
58	this->cases_.at(i)->replace(old_expression, new_expression);	4✔
59	this->conditions_.at(i) = symbolic::subs(this->conditions_.at(i), old_expression, new_expression);	4✔
60	}	4✔
61	}	2✔
62
NEW 63	void IfElse::replace(const symbolic::ExpressionMapping& replacements) {	×
NEW 64	for (size_t i = 0; i < this->cases_.size(); ++i) {	×
NEW 65	this->cases_.at(i)->replace(replacements);	×
NEW 66	this->conditions_.at(i) = symbolic::subs(this->conditions_.at(i), replacements);	×
NEW 67	}	×
UNCOV 68	};	×
69
70	} // namespace structured_control_flow
71	} // namespace sdfg

daisytuner / docc / 28158800507

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