28228448983

Committed 26 Jun 2026 09:06AM UTC coverage: 61.824% (+0.2%) from 61.644%

Build # 28228448983

Build Type

Pull #806

github

Committed by

web-flow

Commit Message

Merge 14f513ee8 into a0c38ffa1

Pull Request Pull Request #806: Map Collapse for Multiple targets in a neste sequence

Coverage Stats

165 of 185 new or added lines in 2 files covered. (89.19%)

844 existing lines in 25 files now uncovered.

39002 of 63086 relevant lines covered (61.82%)

977.72 hits per line

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

76.01

/sdfg/src/structured_control_flow/structured_loop.cpp

#include "sdfg/structured_control_flow/structured_loop.h"

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

namespace sdfg {
namespace structured_control_flow {

StructuredLoop::StructuredLoop(
    size_t element_id,
    const DebugInfo& debug_info,
    ControlFlowNode* parent,
    symbolic::Symbol indvar,
    symbolic::Expression init,
    symbolic::Expression update,
    symbolic::Condition condition,
    const ScheduleType& schedule_type
)
    : ControlFlowNode(element_id, debug_info, parent), indvar_(indvar), init_(init), update_(update),
      condition_(condition), schedule_type_(schedule_type) {
    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_; };

const ScheduleType& StructuredLoop::schedule_type() const { return this->schedule_type_; };

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

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

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

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

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

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

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

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

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

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

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

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

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

    symbolic::Expression min_bound = SymEngine::null;

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

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

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

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

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

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

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

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

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

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

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

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

    symbolic::Expression max_bound = SymEngine::null;

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

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

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

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

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

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

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

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

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

        } else {
            return SymEngine::null;
        }

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

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

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

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

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

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

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

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

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

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

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

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

    return true;
}

} // namespace structured_control_flow
} // namespace sdfg

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

daisytuner / docc / 28228448983

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