23950367934

Committed 03 Apr 2026 02:50PM UTC coverage: 64.61% (-0.09%) from 64.695%

Build # 23950367934

Build Type

Pull #639

github

Committed by

web-flow

Commit Message

Merge ee7ab8ea5 into 5408219aa

Pull Request Pull Request #639: adds new normal form utility methods to structured loops

Coverage Stats

133 of 269 new or added lines in 1 file covered. (49.44%)

28919 of 44759 relevant lines covered (64.61%)

468.66 hits per line

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

51.97

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

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

daisytuner / docc / 23950367934

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