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

75.94

/sdfg/src/structured_control_flow/structured_loop.cpp

#include "sdfg/structured_control_flow/structured_loop.h"

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

namespace sdfg {
namespace structured_control_flow {

StructuredLoop::StructuredLoop(
    size_t element_id,
    const DebugInfo& debug_info,
    ControlFlowNode* parent,
    symbolic::Symbol indvar,
    symbolic::Expression init,
    symbolic::Expression update,
    symbolic::Condition condition
)
    : ControlFlowNode(element_id, debug_info, parent), indvar_(indvar), init_(init), update_(update),
      condition_(condition) {
    this->root_ = std::unique_ptr<Sequence>(new Sequence(++element_id, debug_info, this));
}

void StructuredLoop::validate(const Function& function) const {
    if (this->indvar_.is_null()) {
        throw InvalidSDFGException("StructuredLoop: Induction variable cannot be null");
    }
    if (this->init_.is_null()) {
        throw InvalidSDFGException("StructuredLoop: Initialization expression cannot be null");
    }
    if (this->update_.is_null()) {
        throw InvalidSDFGException("StructuredLoop: Update expression cannot be null");
    }
    if (this->condition_.is_null()) {
        throw InvalidSDFGException("StructuredLoop: Condition expression cannot be null");
    }
    if (!SymEngine::is_a_Boolean(*this->condition_)) {
        throw InvalidSDFGException("StructuredLoop: Condition expression must be a boolean expression");
    }

    this->root_->validate(function);
};

const symbolic::Symbol StructuredLoop::indvar() const { return this->indvar_; };

const symbolic::Expression StructuredLoop::init() const { return this->init_; };

const symbolic::Expression StructuredLoop::update() const { return this->update_; };

const symbolic::Condition StructuredLoop::condition() const { return this->condition_; };

Sequence& StructuredLoop::root() const { return *this->root_; };

void StructuredLoop::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {
    if (symbolic::eq(this->indvar_, old_expression) && SymEngine::is_a<SymEngine::Symbol>(*new_expression)) {
        this->indvar_ = SymEngine::rcp_static_cast<const SymEngine::Symbol>(new_expression);
    }
    this->init_ = symbolic::subs(this->init_, old_expression, new_expression);
    this->update_ = symbolic::subs(this->update_, old_expression, new_expression);
    this->condition_ = symbolic::subs(this->condition_, old_expression, new_expression);

    this->root_->replace(old_expression, new_expression);
}

void StructuredLoop::replace(const symbolic::ExpressionMapping& replacements) {
    auto indvar_repl = replacements.find(this->indvar_);
    if (indvar_repl != replacements.end()) {
        this->indvar_ = SymEngine::rcp_static_cast<const SymEngine::Symbol>(indvar_repl->second);
    }

    this->init_ = SymEngine::subs(this->init_, replacements);
    this->update_ = SymEngine::subs(this->update_, replacements);
    this->condition_ = symbolic::subs(this->condition_, replacements);

    this->root_->replace(replacements);
}

symbolic::Integer StructuredLoop::stride() {
    auto expr = this->update();
    auto indvar = this->indvar();

    symbolic::SymbolVec gens = {indvar};
    auto polynomial = symbolic::polynomial(expr, gens);
    if (polynomial.is_null()) {
        return SymEngine::null;
    }
    auto coeffs = symbolic::affine_coefficients(polynomial);
    if (coeffs.empty()) {
        return SymEngine::null;
    }
    if (coeffs.size() > 2 || coeffs.find(indvar) == coeffs.end() ||
        coeffs.find(symbolic::symbol("__daisy_constant__")) == coeffs.end()) {
        return SymEngine::null;
    }

    // Exponential strides (e.g., i = i * 2) are not supported, so the coefficient must be a positive integer
    auto mul_coeff = coeffs.at(indvar);
    if (!SymEngine::is_a<SymEngine::Integer>(*mul_coeff)) {
        return SymEngine::null;
    }
    auto int_mul_coeff = SymEngine::rcp_static_cast<const SymEngine::Integer>(mul_coeff)->as_int();
    if (int_mul_coeff != 1) {
        return SymEngine::null;
    }

    auto add_coeff = coeffs.at(symbolic::symbol("__daisy_constant__"));
    if (!SymEngine::is_a<SymEngine::Integer>(*add_coeff)) {
        return SymEngine::null;
    }
    auto int_add_coeff = SymEngine::rcp_static_cast<const SymEngine::Integer>(add_coeff)->as_int();
    if (int_add_coeff == 0) {
        return SymEngine::null;
    }
    return SymEngine::integer(int_add_coeff);
};

bool StructuredLoop::is_contiguous() {
    auto stride = this->stride();
    if (stride.is_null()) {
        return false;
    }
    auto stride_int = stride->as_int();
    return stride_int == 1;
}

bool StructuredLoop::is_monotonic() {
    auto stride = this->stride();
    if (stride.is_null()) {
        return false;
    }
    auto stride_int = stride->as_int();
    return stride_int > 0;
}

symbolic::Expression StructuredLoop::canonical_bound() {
    auto stride = this->stride();
    if (stride.is_null()) {
        return SymEngine::null;
    }
    auto stride_int = stride->as_int();
    if (stride_int < 0) {
        return this->canonical_bound_lower();
    } else {
        return this->canonical_bound_upper();
    }
}

symbolic::Expression StructuredLoop::canonical_bound_upper() {
    symbolic::CNF cnf;
    try {
        cnf = symbolic::conjunctive_normal_form(condition_);
    } catch (...) {
        return SymEngine::null;
    }

    symbolic::Expression min_bound = SymEngine::null;

    // Helper to extract upper bound from lhs < rhs_value (or lhs <= rhs_value)
    // For lhs = coeff * indvar + offset, returns (rhs_value - offset) / coeff
    auto extract_upper_bound = [&](const symbolic::Expression& lhs,
                                   const symbolic::Expression& rhs_value) -> symbolic::Expression {
        auto decomp = symbolic::affine_decomposition(lhs, indvar_);
        if (!decomp.success) {
            return SymEngine::null;
        }
        auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(decomp.coeff)->as_int();
        if (coeff_int <= 0) {
            return SymEngine::null;
        }
        symbolic::Expression result = symbolic::expand(symbolic::sub(rhs_value, decomp.offset));
        if (coeff_int != 1) {
            result = symbolic::expand(symbolic::div(result, decomp.coeff));
        }
        return result;
    };

    for (const auto& clause : cnf) {
        // For upper bound extraction, we require unit clauses (single literal per clause)
        // Multi-clause disjunctions like (i < N || i < M) are not supported
        if (clause.size() != 1) {
            return SymEngine::null;
        }

        auto literal = clause[0];
        symbolic::Expression bound = SymEngine::null;
        if (!symbolic::uses(literal, indvar_)) {
            // Dead check
            continue;
        }

        if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
            // Handle: lhs < rhs
            auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);
            auto lhs = lt->get_arg1();
            auto rhs = lt->get_arg2();

            // Check if indvar is on LHS
            if (!symbolic::uses(lhs, indvar_->get_name())) {
                // indvar not on LHS - this is a lower bound constraint, skip it
                continue;
            }
            if (symbolic::uses(rhs, indvar_->get_name())) {
                // indvar on both sides, can't extract
                return SymEngine::null;
            }

            // Extract: coeff * indvar + offset < rhs  =>  indvar < (rhs - offset) / coeff
            bound = extract_upper_bound(lhs, rhs);
            if (bound.is_null()) {
                return SymEngine::null;
            }

        } else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {
            // Handle: lhs <= rhs  =>  lhs < rhs + 1
            auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(literal);
            auto lhs = le->get_arg1();
            auto rhs = le->get_arg2();

            if (!symbolic::uses(lhs, indvar_->get_name())) {
                // indvar not on LHS - this is a lower bound constraint, skip it
                continue;
            }
            if (symbolic::uses(rhs, indvar_->get_name())) {
                return SymEngine::null;
            }

            // Extract: coeff * indvar + offset <= rhs  =>  indvar < (rhs + 1 - offset) / coeff
            bound = extract_upper_bound(lhs, symbolic::add(rhs, symbolic::one()));
            if (bound.is_null()) {
                return SymEngine::null;
            }

        } else {
            // Other comparison types don't give upper bounds
            return SymEngine::null;
        }

        if (bound != SymEngine::null) {
            if (min_bound.is_null()) {
                min_bound = bound;
            } else {
                min_bound = symbolic::min(min_bound, bound);
            }
        }
    }
    return min_bound;
}

symbolic::Expression StructuredLoop::canonical_bound_lower() {
    symbolic::CNF cnf;
    try {
        cnf = symbolic::conjunctive_normal_form(condition_);
    } catch (...) {
        return SymEngine::null;
    }

    symbolic::Expression max_bound = SymEngine::null;

    // Helper to extract lower bound from lhs_value < rhs (or lhs_value <= rhs)
    // For rhs = coeff * indvar + offset, returns (lhs_value - offset) / coeff
    auto extract_lower_bound = [&](const symbolic::Expression& rhs,
                                   const symbolic::Expression& lhs_value) -> symbolic::Expression {
        auto decomp = symbolic::affine_decomposition(rhs, indvar_);
        if (!decomp.success) {
            return SymEngine::null;
        }
        auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(decomp.coeff)->as_int();
        if (coeff_int <= 0) {
            return SymEngine::null;
        }
        symbolic::Expression result = symbolic::expand(symbolic::sub(lhs_value, decomp.offset));
        if (coeff_int != 1) {
            result = symbolic::expand(symbolic::div(result, decomp.coeff));
        }
        return result;
    };

    for (const auto& clause : cnf) {
        // For lower bound extraction, we require unit clauses
        if (clause.size() != 1) {
            return SymEngine::null;
        }

        auto literal = clause[0];
        symbolic::Expression bound = SymEngine::null;
        if (!symbolic::uses(literal, indvar_)) {
            // Dead check
            continue;
        }

        if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
            // Handle: lhs < rhs where rhs contains indvar => indvar > lhs (lower bound)
            auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);
            auto lhs = lt->get_arg1();
            auto rhs = lt->get_arg2();

            // For lower bound, indvar should be on RHS: bound < indvar
            if (!symbolic::uses(rhs, indvar_->get_name())) {
                // indvar not on RHS - this is an upper bound constraint, skip it
                continue;
            }
            if (symbolic::uses(lhs, indvar_->get_name())) {
                return SymEngine::null;
            }

            // Extract: lhs < coeff * indvar + offset  =>  indvar > (lhs - offset) / coeff
            bound = extract_lower_bound(rhs, lhs);
            if (bound.is_null()) {
                return SymEngine::null;
            }

        } else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {
            // Handle: lhs <= rhs where rhs contains indvar => indvar >= lhs => indvar > lhs - 1
            auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(literal);
            auto lhs = le->get_arg1();
            auto rhs = le->get_arg2();

            if (!symbolic::uses(rhs, indvar_->get_name())) {
                // indvar not on RHS - this is an upper bound constraint, skip it
                continue;
            }
            if (symbolic::uses(lhs, indvar_->get_name())) {
                return SymEngine::null;
            }

            // Extract: lhs <= coeff * indvar + offset  =>  indvar > (lhs - 1 - offset) / coeff
            bound = extract_lower_bound(rhs, symbolic::sub(lhs, symbolic::one()));
            if (bound.is_null()) {
                return SymEngine::null;
            }

        } else {
            return SymEngine::null;
        }

        if (bound != SymEngine::null) {
            if (max_bound.is_null()) {
                max_bound = bound;
            } else {
                max_bound = symbolic::max(max_bound, bound);
            }
        }
    }
    return max_bound;
}

symbolic::Expression StructuredLoop::num_iterations() {
    auto stride = this->stride();
    if (stride.is_null()) {
        return SymEngine::null;
    }
    auto stride_int = stride->as_int();

    auto bound = this->canonical_bound();
    if (bound.is_null()) {
        return SymEngine::null;
    }

    symbolic::Expression numerator;
    symbolic::Expression divisor;
    if (stride_int > 0) {
        numerator = symbolic::expand(symbolic::sub(bound, this->init()));
        divisor = stride;
    } else {
        numerator = symbolic::expand(symbolic::sub(this->init(), bound));
        divisor = symbolic::integer(-stride_int);
    }

    auto num_iters = symbolic::divide_ceil(numerator, divisor);
    num_iters = symbolic::simplify(symbolic::max(symbolic::zero(), num_iters));
    return num_iters;
}

symbolic::Expression StructuredLoop::num_iterations_approx() {
    // Conservative upper bound on the iteration count. Same formula as
    // num_iterations(), but the numerator (bound - init for positive stride,
    // init - bound for negative stride) is fed through symbolic::overapproximate
    // before the ceiling division. This distributes the init term inside any
    // top-level min/max in the bound, exposing tile-style cancellations such as
    // min(global, init + T) - init  --(distribute)-->  min(global - init, T)
    //                              --(overapproximate)-->  T
    // when T is a plain integer constant.
    auto stride = this->stride();
    if (stride.is_null()) {
        return SymEngine::null;
    }
    auto stride_int = stride->as_int();
    if (stride_int == 0) {
        return SymEngine::null;
    }

    auto bound = this->canonical_bound();
    if (bound.is_null()) {
        return SymEngine::null;
    }

    symbolic::Expression numerator;
    symbolic::Expression divisor;
    if (stride_int > 0) {
        numerator = symbolic::sub(bound, this->init());
        divisor = stride;
    } else {
        numerator = symbolic::sub(this->init(), bound);
        divisor = symbolic::integer(-stride_int);
    }
    numerator = symbolic::simplify(symbolic::expand(symbolic::overapproximate(numerator)));

    auto num_iters = symbolic::divide_ceil(numerator, divisor);
    num_iters = symbolic::simplify(symbolic::max(symbolic::zero(), num_iters));
    return num_iters;
}

bool StructuredLoop::is_loop_normal_form() {
    // Check if init is zero
    if (!symbolic::eq(this->init_, symbolic::zero())) {
        return false;
    }

    // Check if it has positive unit stride
    auto stride = this->stride();
    if (stride.is_null() || stride->as_int() != 1) {
        return false;
    }

    // Check if condition has a canonical bound
    auto bound = this->canonical_bound();
    if (bound.is_null()) {
        return false;
    }

    return true;
}

} // namespace structured_control_flow
} // namespace sdfg

1	#include "sdfg/structured_control_flow/structured_loop.h"
2
3	#include "sdfg/symbolic/conjunctive_normal_form.h"
4	#include "sdfg/symbolic/polynomials.h"
5	#include "symengine/subs.h"
6
7	namespace sdfg {
8	namespace structured_control_flow {
9
10	StructuredLoop::StructuredLoop(
11	size_t element_id,
12	const DebugInfo& debug_info,
13	ControlFlowNode* parent,
14	symbolic::Symbol indvar,
15	symbolic::Expression init,
16	symbolic::Expression update,
17	symbolic::Condition condition
18	)
19	: ControlFlowNode(element_id, debug_info, parent), indvar_(indvar), init_(init), update_(update),	3,335✔
20	condition_(condition) {	3,335✔
21	this->root_ = std::unique_ptr<Sequence>(new Sequence(++element_id, debug_info, this));	3,335✔
22	}	3,335✔
23
24	void StructuredLoop::validate(const Function& function) const {	5,274✔
25	if (this->indvar_.is_null()) {	5,274✔
26	throw InvalidSDFGException("StructuredLoop: Induction variable cannot be null");	×
27	}	×
28	if (this->init_.is_null()) {	5,274✔
29	throw InvalidSDFGException("StructuredLoop: Initialization expression cannot be null");	×
30	}	×
31	if (this->update_.is_null()) {	5,274✔
32	throw InvalidSDFGException("StructuredLoop: Update expression cannot be null");	×
33	}	×
34	if (this->condition_.is_null()) {	5,274✔
35	throw InvalidSDFGException("StructuredLoop: Condition expression cannot be null");	×
36	}	×
37	if (!SymEngine::is_a_Boolean(*this->condition_)) {	5,274✔
38	throw InvalidSDFGException("StructuredLoop: Condition expression must be a boolean expression");	×
39	}	×
40
41	this->root_->validate(function);	5,274✔
42	};	5,274✔
43
44	const symbolic::Symbol StructuredLoop::indvar() const { return this->indvar_; };	40,283✔
45
46	const symbolic::Expression StructuredLoop::init() const { return this->init_; };	9,116✔
47
48	const symbolic::Expression StructuredLoop::update() const { return this->update_; };	15,620✔
49
50	const symbolic::Condition StructuredLoop::condition() const { return this->condition_; };	7,481✔
51
52	Sequence& StructuredLoop::root() const { return *this->root_; };	24,116✔
53
54	void StructuredLoop::replace(const symbolic::Expression old_expression, const symbolic::Expression new_expression) {	182✔
55	if (symbolic::eq(this->indvar_, old_expression) && SymEngine::is_a<SymEngine::Symbol>(*new_expression)) {	182✔
56	this->indvar_ = SymEngine::rcp_static_cast<const SymEngine::Symbol>(new_expression);	50✔
57	}	50✔
58	this->init_ = symbolic::subs(this->init_, old_expression, new_expression);	182✔
59	this->update_ = symbolic::subs(this->update_, old_expression, new_expression);	182✔
60	this->condition_ = symbolic::subs(this->condition_, old_expression, new_expression);	182✔
61
62	this->root_->replace(old_expression, new_expression);	182✔
63	}	182✔
64
NEW 65	void StructuredLoop::replace(const symbolic::ExpressionMapping& replacements) {	×
NEW 66	auto indvar_repl = replacements.find(this->indvar_);	×
NEW 67	if (indvar_repl != replacements.end()) {	×
NEW 68	this->indvar_ = SymEngine::rcp_static_cast<const SymEngine::Symbol>(indvar_repl->second);	×
NEW 69	}	×
70
NEW 71	this->init_ = SymEngine::subs(this->init_, replacements);	×
NEW 72	this->update_ = SymEngine::subs(this->update_, replacements);	×
NEW 73	this->condition_ = symbolic::subs(this->condition_, replacements);	×
74
NEW 75	this->root_->replace(replacements);	×
NEW 76	}	×
77
78	symbolic::Integer StructuredLoop::stride() {	8,400✔
79	auto expr = this->update();	8,400✔
80	auto indvar = this->indvar();	8,400✔
81
82	symbolic::SymbolVec gens = {indvar};	8,400✔
83	auto polynomial = symbolic::polynomial(expr, gens);	8,400✔
84	if (polynomial.is_null()) {	8,400✔
85	return SymEngine::null;	×
86	}	×
87	auto coeffs = symbolic::affine_coefficients(polynomial);	8,400✔
88	if (coeffs.empty()) {	8,400✔
89	return SymEngine::null;	×
90	}	×
91	if (coeffs.size() > 2 \|\| coeffs.find(indvar) == coeffs.end() \|\|	8,400✔
92	coeffs.find(symbolic::symbol("__daisy_constant__")) == coeffs.end()) {	8,400✔
93	return SymEngine::null;	×
94	}	×
95
96	// Exponential strides (e.g., i = i * 2) are not supported, so the coefficient must be a positive integer
97	auto mul_coeff = coeffs.at(indvar);	8,400✔
98	if (!SymEngine::is_a<SymEngine::Integer>(*mul_coeff)) {	8,400✔
99	return SymEngine::null;	×
100	}	×
101	auto int_mul_coeff = SymEngine::rcp_static_cast<const SymEngine::Integer>(mul_coeff)->as_int();	8,400✔
102	if (int_mul_coeff != 1) {	8,400✔
103	return SymEngine::null;	7✔
104	}	7✔
105
106	auto add_coeff = coeffs.at(symbolic::symbol("__daisy_constant__"));	8,393✔
107	if (!SymEngine::is_a<SymEngine::Integer>(*add_coeff)) {	8,393✔
108	return SymEngine::null;	2✔
109	}	2✔
110	auto int_add_coeff = SymEngine::rcp_static_cast<const SymEngine::Integer>(add_coeff)->as_int();	8,391✔
111	if (int_add_coeff == 0) {	8,391✔
112	return SymEngine::null;	×
113	}	×
114	return SymEngine::integer(int_add_coeff);	8,391✔
115	};	8,391✔
116
117	bool StructuredLoop::is_contiguous() {	1,394✔
118	auto stride = this->stride();	1,394✔
119	if (stride.is_null()) {	1,394✔
120	return false;	1✔
121	}	1✔
122	auto stride_int = stride->as_int();	1,393✔
123	return stride_int == 1;	1,393✔
124	}	1,394✔
125
126	bool StructuredLoop::is_monotonic() {	3,145✔
127	auto stride = this->stride();	3,145✔
128	if (stride.is_null()) {	3,145✔
129	return false;	1✔
130	}	1✔
131	auto stride_int = stride->as_int();	3,144✔
132	return stride_int > 0;	3,144✔
133	}	3,145✔
134
135	symbolic::Expression StructuredLoop::canonical_bound() {	740✔
136	auto stride = this->stride();	740✔
137	if (stride.is_null()) {	740✔
138	return SymEngine::null;	1✔
139	}	1✔
140	auto stride_int = stride->as_int();	739✔
141	if (stride_int < 0) {	739✔
142	return this->canonical_bound_lower();	4✔
143	} else {	735✔
144	return this->canonical_bound_upper();	735✔
145	}	735✔
146	}	739✔
147
148	symbolic::Expression StructuredLoop::canonical_bound_upper() {	3,046✔
149	symbolic::CNF cnf;	3,046✔
150	try {	3,046✔
151	cnf = symbolic::conjunctive_normal_form(condition_);	3,046✔
152	} catch (...) {	3,046✔
153	return SymEngine::null;	×
154	}	×
155
156	symbolic::Expression min_bound = SymEngine::null;	3,046✔
157
158	// Helper to extract upper bound from lhs < rhs_value (or lhs <= rhs_value)
159	// For lhs = coeff * indvar + offset, returns (rhs_value - offset) / coeff
160	auto extract_upper_bound = [&](const symbolic::Expression& lhs,	3,046✔
161	const symbolic::Expression& rhs_value) -> symbolic::Expression {	3,361✔
162	auto decomp = symbolic::affine_decomposition(lhs, indvar_);	3,361✔
163	if (!decomp.success) {	3,361✔
164	return SymEngine::null;	×
165	}	×
166	auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(decomp.coeff)->as_int();	3,361✔
167	if (coeff_int <= 0) {	3,361✔
168	return SymEngine::null;	×
169	}	×
170	symbolic::Expression result = symbolic::expand(symbolic::sub(rhs_value, decomp.offset));	3,361✔
171	if (coeff_int != 1) {	3,361✔
172	result = symbolic::expand(symbolic::div(result, decomp.coeff));	13✔
173	}	13✔
174	return result;	3,361✔
175	};	3,361✔
176
177	for (const auto& clause : cnf) {	3,372✔
178	// For upper bound extraction, we require unit clauses (single literal per clause)
179	// Multi-clause disjunctions like (i < N \|\| i < M) are not supported
180	if (clause.size() != 1) {	3,372✔
181	return SymEngine::null;	×
182	}	×
183
184	auto literal = clause[0];	3,372✔
185	symbolic::Expression bound = SymEngine::null;	3,372✔
186	if (!symbolic::uses(literal, indvar_)) {	3,372✔
187	// Dead check
188	continue;	2✔
189	}	2✔
190
191	if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	3,370✔
192	// Handle: lhs < rhs
193	auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	3,276✔
194	auto lhs = lt->get_arg1();	3,276✔
195	auto rhs = lt->get_arg2();	3,276✔
196
197	// Check if indvar is on LHS
198	if (!symbolic::uses(lhs, indvar_->get_name())) {	3,276✔
199	// indvar not on LHS - this is a lower bound constraint, skip it
200	continue;	1✔
201	}	1✔
202	if (symbolic::uses(rhs, indvar_->get_name())) {	3,275✔
203	// indvar on both sides, can't extract
204	return SymEngine::null;	6✔
205	}	6✔
206
207	// Extract: coeff * indvar + offset < rhs => indvar < (rhs - offset) / coeff
208	bound = extract_upper_bound(lhs, rhs);	3,269✔
209	if (bound.is_null()) {	3,269✔
210	return SymEngine::null;	×
211	}	×
212
213	} else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {	3,269✔
214	// Handle: lhs <= rhs => lhs < rhs + 1
215	auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(literal);	94✔
216	auto lhs = le->get_arg1();	94✔
217	auto rhs = le->get_arg2();	94✔
218
219	if (!symbolic::uses(lhs, indvar_->get_name())) {	94✔
220	// indvar not on LHS - this is a lower bound constraint, skip it
221	continue;	2✔
222	}	2✔
223	if (symbolic::uses(rhs, indvar_->get_name())) {	92✔
224	return SymEngine::null;	×
225	}	×
226
227	// Extract: coeff * indvar + offset <= rhs => indvar < (rhs + 1 - offset) / coeff
228	bound = extract_upper_bound(lhs, symbolic::add(rhs, symbolic::one()));	92✔
229	if (bound.is_null()) {	92✔
230	return SymEngine::null;	×
231	}	×
232
233	} else {	92✔
234	// Other comparison types don't give upper bounds
235	return SymEngine::null;	×
236	}	×
237
238	if (bound != SymEngine::null) {	3,361✔
239	if (min_bound.is_null()) {	3,361✔
240	min_bound = bound;	3,037✔
241	} else {	3,037✔
242	min_bound = symbolic::min(min_bound, bound);	324✔
243	}	324✔
244	}	3,361✔
245	}	3,361✔
246	return min_bound;	3,040✔
247	}	3,046✔
248
249	symbolic::Expression StructuredLoop::canonical_bound_lower() {	22✔
250	symbolic::CNF cnf;	22✔
251	try {	22✔
252	cnf = symbolic::conjunctive_normal_form(condition_);	22✔
253	} catch (...) {	22✔
254	return SymEngine::null;	×
255	}	×
256
257	symbolic::Expression max_bound = SymEngine::null;	22✔
258
259	// Helper to extract lower bound from lhs_value < rhs (or lhs_value <= rhs)
260	// For rhs = coeff * indvar + offset, returns (lhs_value - offset) / coeff
261	auto extract_lower_bound = [&](const symbolic::Expression& rhs,	22✔
262	const symbolic::Expression& lhs_value) -> symbolic::Expression {	22✔
263	auto decomp = symbolic::affine_decomposition(rhs, indvar_);	21✔
264	if (!decomp.success) {	21✔
265	return SymEngine::null;	×
266	}	×
267	auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(decomp.coeff)->as_int();	21✔
268	if (coeff_int <= 0) {	21✔
269	return SymEngine::null;	×
270	}	×
271	symbolic::Expression result = symbolic::expand(symbolic::sub(lhs_value, decomp.offset));	21✔
272	if (coeff_int != 1) {	21✔
273	result = symbolic::expand(symbolic::div(result, decomp.coeff));	2✔
274	}	2✔
275	return result;	21✔
276	};	21✔
277
278	for (const auto& clause : cnf) {	22✔
279	// For lower bound extraction, we require unit clauses
280	if (clause.size() != 1) {	22✔
281	return SymEngine::null;	×
282	}	×
283
284	auto literal = clause[0];	22✔
285	symbolic::Expression bound = SymEngine::null;	22✔
286	if (!symbolic::uses(literal, indvar_)) {	22✔
287	// Dead check
288	continue;	×
289	}	×
290
291	if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	22✔
292	// Handle: lhs < rhs where rhs contains indvar => indvar > lhs (lower bound)
293	auto lt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	21✔
294	auto lhs = lt->get_arg1();	21✔
295	auto rhs = lt->get_arg2();	21✔
296
297	// For lower bound, indvar should be on RHS: bound < indvar
298	if (!symbolic::uses(rhs, indvar_->get_name())) {	21✔
299	// indvar not on RHS - this is an upper bound constraint, skip it
300	continue;	1✔
301	}	1✔
302	if (symbolic::uses(lhs, indvar_->get_name())) {	20✔
303	return SymEngine::null;	×
304	}	×
305
306	// Extract: lhs < coeff * indvar + offset => indvar > (lhs - offset) / coeff
307	bound = extract_lower_bound(rhs, lhs);	20✔
308	if (bound.is_null()) {	20✔
309	return SymEngine::null;	×
310	}	×
311
312	} else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {	20✔
313	// Handle: lhs <= rhs where rhs contains indvar => indvar >= lhs => indvar > lhs - 1
314	auto le = SymEngine::rcp_static_cast<const SymEngine::LessThan>(literal);	1✔
315	auto lhs = le->get_arg1();	1✔
316	auto rhs = le->get_arg2();	1✔
317
318	if (!symbolic::uses(rhs, indvar_->get_name())) {	1✔
319	// indvar not on RHS - this is an upper bound constraint, skip it
320	continue;	×
321	}	×
322	if (symbolic::uses(lhs, indvar_->get_name())) {	1✔
323	return SymEngine::null;	×
324	}	×
325
326	// Extract: lhs <= coeff * indvar + offset => indvar > (lhs - 1 - offset) / coeff
327	bound = extract_lower_bound(rhs, symbolic::sub(lhs, symbolic::one()));	1✔
328	if (bound.is_null()) {	1✔
329	return SymEngine::null;	×
330	}	×
331
332	} else {	1✔
333	return SymEngine::null;	×
334	}	×
335
336	if (bound != SymEngine::null) {	21✔
337	if (max_bound.is_null()) {	21✔
338	max_bound = bound;	21✔
339	} else {	21✔
340	max_bound = symbolic::max(max_bound, bound);	×
341	}	×
342	}	21✔
343	}	21✔
344	return max_bound;	22✔
345	}	22✔
346
347	symbolic::Expression StructuredLoop::num_iterations() {	520✔
348	auto stride = this->stride();	520✔
349	if (stride.is_null()) {	520✔
350	return SymEngine::null;	1✔
351	}	1✔
352	auto stride_int = stride->as_int();	519✔
353
354	auto bound = this->canonical_bound();	519✔
355	if (bound.is_null()) {	519✔
356	return SymEngine::null;	1✔
357	}	1✔
358
359	symbolic::Expression numerator;	518✔
360	symbolic::Expression divisor;	518✔
361	if (stride_int > 0) {	518✔
362	numerator = symbolic::expand(symbolic::sub(bound, this->init()));	516✔
363	divisor = stride;	516✔
364	} else {	516✔
365	numerator = symbolic::expand(symbolic::sub(this->init(), bound));	2✔
366	divisor = symbolic::integer(-stride_int);	2✔
367	}	2✔
368
369	auto num_iters = symbolic::divide_ceil(numerator, divisor);	518✔
370	num_iters = symbolic::simplify(symbolic::max(symbolic::zero(), num_iters));	518✔
371	return num_iters;	518✔
372	}	519✔
373
374	symbolic::Expression StructuredLoop::num_iterations_approx() {	25✔
375	// Conservative upper bound on the iteration count. Same formula as
376	// num_iterations(), but the numerator (bound - init for positive stride,
377	// init - bound for negative stride) is fed through symbolic::overapproximate
378	// before the ceiling division. This distributes the init term inside any
379	// top-level min/max in the bound, exposing tile-style cancellations such as
380	// min(global, init + T) - init --(distribute)--> min(global - init, T)
381	// --(overapproximate)--> T
382	// when T is a plain integer constant.
383	auto stride = this->stride();	25✔
384	if (stride.is_null()) {	25✔
385	return SymEngine::null;	1✔
386	}	1✔
387	auto stride_int = stride->as_int();	24✔
388	if (stride_int == 0) {	24✔
389	return SymEngine::null;	×
390	}	×
391
392	auto bound = this->canonical_bound();	24✔
393	if (bound.is_null()) {	24✔
394	return SymEngine::null;	×
395	}	×
396
397	symbolic::Expression numerator;	24✔
398	symbolic::Expression divisor;	24✔
399	if (stride_int > 0) {	24✔
400	numerator = symbolic::sub(bound, this->init());	24✔
401	divisor = stride;	24✔
402	} else {	24✔
403	numerator = symbolic::sub(this->init(), bound);	×
404	divisor = symbolic::integer(-stride_int);	×
405	}	×
406	numerator = symbolic::simplify(symbolic::expand(symbolic::overapproximate(numerator)));	24✔
407
408	auto num_iters = symbolic::divide_ceil(numerator, divisor);	24✔
409	num_iters = symbolic::simplify(symbolic::max(symbolic::zero(), num_iters));	24✔
410	return num_iters;	24✔
411	}	24✔
412
413	bool StructuredLoop::is_loop_normal_form() {	48✔
414	// Check if init is zero
415	if (!symbolic::eq(this->init_, symbolic::zero())) {	48✔
416	return false;	4✔
417	}	4✔
418
419	// Check if it has positive unit stride
420	auto stride = this->stride();	44✔
421	if (stride.is_null() \|\| stride->as_int() != 1) {	44✔
422	return false;	1✔
423	}	1✔
424
425	// Check if condition has a canonical bound
426	auto bound = this->canonical_bound();	43✔
427	if (bound.is_null()) {	43✔
428	return false;	1✔
429	}	1✔
430
431	return true;	42✔
432	}	43✔
433
434	} // namespace structured_control_flow
435	} // 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