27481026029

Committed 13 Jun 2026 10:29PM UTC coverage: 61.381%. First build

Build # 27481026029

Build Type

Pull #763

github

Committed by

web-flow

Commit Message

Merge 680a2a528 into 9754c0592

Pull Request Pull Request #763: Generalized API for estimating iteration count of loops

Coverage Stats

62 of 71 new or added lines in 4 files covered. (87.32%)

36320 of 59171 relevant lines covered (61.38%)

1125.25 hits per line

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

78.39

/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"

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

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

daisytuner / docc / 27481026029

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