25459771247

Committed 06 May 2026 08:37PM UTC coverage: 65.659% (+0.4%) from 65.223%

Build # 25459771247

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #704 from daisytuner/lcd-analysis

Refactors LoopCarriedDependencyAnalysis into standalone analysis

Coverage Stats

731 of 828 new or added lines in 13 files covered. (88.29%)

42 existing lines in 5 files now uncovered.

32175 of 49003 relevant lines covered (65.66%)

12934.86 hits per line

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

67.16

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

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

daisytuner / docc / 25459771247

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