23978459061

Committed 04 Apr 2026 12:00PM UTC coverage: 64.742%. First build

Build # 23978459061

Build Type

Pull #644

github

Committed by

web-flow

Commit Message

Merge 6d8b19c63 into 811a5c32e

Pull Request Pull Request #644: adapts new loop analysis api

Run Details

39 of 44 new or added lines in 16 files covered. (88.64%)

29101 of 44949 relevant lines covered (64.74%)

532.86 hits per line

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

57.81

/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,
    symbolic::Symbol indvar,
    symbolic::Expression init,
    symbolic::Expression update,
    symbolic::Condition condition
)
    : ControlFlowNode(element_id, debug_info), indvar_(indvar), init_(init), update_(update), condition_(condition) {
    this->root_ = std::unique_ptr<Sequence>(new Sequence(++element_id, debug_info));
}

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, gens);
    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();
    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 || stride_int > 1 || stride_int < -1) {
        return SymEngine::null;
    }
    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;
    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
            symbolic::SymbolVec syms = {indvar_};
            auto poly = symbolic::polynomial(lhs, syms);
            if (poly.is_null()) {
                return SymEngine::null;
            }
            auto coeffs = symbolic::affine_coefficients(poly, syms);
            if (coeffs.empty() || coeffs.find(indvar_) == coeffs.end()) {
                return SymEngine::null;
            }

            auto coeff = coeffs.at(indvar_);
            symbolic::Expression offset = symbolic::zero();
            if (coeffs.count(symbolic::symbol("__daisy_constant__"))) {
                offset = coeffs.at(symbolic::symbol("__daisy_constant__"));
            }

            // Coefficient must be a positive integer for upper bound
            if (!SymEngine::is_a<SymEngine::Integer>(*coeff)) {
                return SymEngine::null;
            }
            auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(coeff)->as_int();
            if (coeff_int <= 0) {
                return SymEngine::null;
            }

            // bound = (rhs - offset) / coeff
            bound = symbolic::expand(symbolic::sub(rhs, offset));
            if (coeff_int != 1) {
                bound = symbolic::expand(symbolic::div(bound, coeff));
            }

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

            symbolic::SymbolVec syms = {indvar_};
            auto poly = symbolic::polynomial(lhs, syms);
            if (poly.is_null()) {
                return SymEngine::null;
            }
            auto coeffs = symbolic::affine_coefficients(poly, syms);
            if (coeffs.empty() || coeffs.find(indvar_) == coeffs.end()) {
                return SymEngine::null;
            }

            auto coeff = coeffs.at(indvar_);
            symbolic::Expression offset = symbolic::zero();
            if (coeffs.count(symbolic::symbol("__daisy_constant__"))) {
                offset = coeffs.at(symbolic::symbol("__daisy_constant__"));
            }

            if (!SymEngine::is_a<SymEngine::Integer>(*coeff)) {
                return SymEngine::null;
            }
            auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(coeff)->as_int();
            if (coeff_int <= 0) {
                return SymEngine::null;
            }

            // bound = (rhs + 1 - offset) / coeff
            bound = symbolic::expand(symbolic::sub(symbolic::add(rhs, symbolic::one()), offset));
            if (coeff_int != 1) {
                bound = symbolic::expand(symbolic::div(bound, coeff));
            }

        } 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;
    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
            symbolic::SymbolVec syms = {indvar_};
            auto poly = symbolic::polynomial(rhs, syms);
            if (poly.is_null()) {
                return SymEngine::null;
            }
            auto coeffs = symbolic::affine_coefficients(poly, syms);
            if (coeffs.empty() || coeffs.find(indvar_) == coeffs.end()) {
                return SymEngine::null;
            }

            auto coeff = coeffs.at(indvar_);
            symbolic::Expression offset = symbolic::zero();
            if (coeffs.count(symbolic::symbol("__daisy_constant__"))) {
                offset = coeffs.at(symbolic::symbol("__daisy_constant__"));
            }

            if (!SymEngine::is_a<SymEngine::Integer>(*coeff)) {
                return SymEngine::null;
            }
            auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(coeff)->as_int();
            if (coeff_int <= 0) {
                return SymEngine::null;
            }

            // bound = (lhs - offset) / coeff
            bound = symbolic::expand(symbolic::sub(lhs, offset));
            if (coeff_int != 1) {
                bound = symbolic::expand(symbolic::div(bound, coeff));
            }

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

            symbolic::SymbolVec syms = {indvar_};
            auto poly = symbolic::polynomial(rhs, syms);
            if (poly.is_null()) {
                return SymEngine::null;
            }
            auto coeffs = symbolic::affine_coefficients(poly, syms);
            if (coeffs.empty() || coeffs.find(indvar_) == coeffs.end()) {
                return SymEngine::null;
            }

            auto coeff = coeffs.at(indvar_);
            symbolic::Expression offset = symbolic::zero();
            if (coeffs.count(symbolic::symbol("__daisy_constant__"))) {
                offset = coeffs.at(symbolic::symbol("__daisy_constant__"));
            }

            if (!SymEngine::is_a<SymEngine::Integer>(*coeff)) {
                return SymEngine::null;
            }
            auto coeff_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(coeff)->as_int();
            if (coeff_int <= 0) {
                return SymEngine::null;
            }

            // bound = (lhs - 1 - offset) / coeff
            bound = symbolic::expand(symbolic::sub(symbolic::sub(lhs, symbolic::one()), offset));
            if (coeff_int != 1) {
                bound = symbolic::expand(symbolic::div(bound, coeff));
            }

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

daisytuner / docc / 23978459061

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