20764569418

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20764569418

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

65.4

/src/passes/structured_control_flow/loop_normalization.cpp

#include "sdfg/passes/structured_control_flow/loop_normalization.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/symbolic/conjunctive_normal_form.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

LoopNormalization::LoopNormalization(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {

      };

bool LoopNormalization::accept(structured_control_flow::For& loop) {
    bool applied = false;

    // Step 1: Bring condition to CNF
    symbolic::Condition condition = loop.condition();
    sdfg::symbolic::CNF cnf;
    try {
        cnf = symbolic::conjunctive_normal_form(condition);
    } catch (const symbolic::CNFException e) {
        return false;
    }
    // Update if changed
    {
        symbolic::Condition new_condition = symbolic::__true__();
        for (auto& clause : cnf) {
            symbolic::Condition new_clause = symbolic::__false__();
            for (auto& literal : clause) {
                auto new_literal = SymEngine::rcp_dynamic_cast<const SymEngine::Boolean>(symbolic::simplify(literal));
                new_clause = symbolic::Or(new_clause, new_literal);
            }
            new_condition = symbolic::And(new_condition, new_clause);
        }
        if (!symbolic::eq(new_condition, condition)) {
            builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());
            applied = true;
        }
        condition = new_condition;
    }

    // Following steps require affine update
    auto indvar = loop.indvar();
    auto update = loop.update();
    auto& assumptions_analysis = analysis_manager_.get<analysis::AssumptionsAnalysis>();
    auto& assums = assumptions_analysis.get(loop, true);
    auto [success, coeffs] = symbolic::series::affine_int_coeffs(update, indvar, assums);
    if (!success) {
        return applied;
    }
    auto [mul_coeff, add_coeff] = coeffs;
    if (mul_coeff->as_int() != 1) {
        return applied;
    }
    int stride = add_coeff->as_int();
    if (stride == 0) {
        return applied;
    }

    // Step 2: Simplify literals of CNF that involve the induction variable
    symbolic::CNF new_cnf;
    for (auto& clause : cnf) {
        std::vector<symbolic::Condition> new_clause;
        for (auto& literal : clause) {
            if (SymEngine::is_a<SymEngine::Unequality>(*literal)) {
                auto old_literal = SymEngine::rcp_static_cast<const SymEngine::Unequality>(literal);
                auto lhs = old_literal->get_args().at(0);
                auto rhs = old_literal->get_args().at(1);
                if (symbolic::uses(lhs, indvar) && symbolic::uses(rhs, indvar)) {
                    new_clause.push_back(literal);
                    continue;
                }
                if (!symbolic::uses(rhs, indvar)) {
                    std::swap(lhs, rhs);
                }
                if (!symbolic::uses(rhs, indvar)) {
                    new_clause.push_back(literal);
                    continue;
                }

                // RHS is now guranteed to use the indvar

                // 1. Solve inequality for indvar (affine case)
                symbolic::SymbolVec syms = {indvar};
                auto poly_rhs = symbolic::polynomial(rhs, syms);
                if (poly_rhs == SymEngine::null) {
                    new_clause.push_back(literal);
                    continue;
                }
                auto coeffs_rhs = symbolic::affine_coefficients(poly_rhs, syms);
                auto mul_coeff_rhs = coeffs_rhs[indvar];
                auto add_coeff_rhs = coeffs_rhs[symbolic::symbol("__daisy_constant__")];

                auto new_rhs = symbolic::sub(lhs, add_coeff_rhs);
                // TODO: integer division
                new_rhs = symbolic::div(new_rhs, mul_coeff_rhs);
                auto new_lhs = indvar;

                // 2. Convert to comparison based on stride sign

                // Special cases: |stride| == 1
                if (stride == 1) {
                    auto new_literal = symbolic::Lt(new_lhs, new_rhs);
                    new_clause.push_back(new_literal);
                    continue;
                } else if (stride == -1) {
                    auto new_literal = symbolic::Gt(new_lhs, new_rhs);
                    new_clause.push_back(new_literal);
                    continue;
                }

                // Fallback general case
                new_clause.push_back(symbolic::Ne(new_lhs, new_rhs));
            } else if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
                // Remove trivial max expressions
                auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);
                auto lhs = slt->get_args().at(0);
                auto rhs = slt->get_args().at(1);
                if (!symbolic::eq(lhs, indvar)) {
                    new_clause.push_back(literal);
                    continue;
                }
                if (!SymEngine::is_a<SymEngine::Max>(*rhs)) {
                    new_clause.push_back(literal);
                    continue;
                }
                auto max_expr = SymEngine::rcp_static_cast<const SymEngine::Max>(rhs);
                auto args = max_expr->get_args();
                if (args.size() != 2) {
                    new_clause.push_back(literal);
                    continue;
                }
                auto arg1 = args.at(0);
                auto arg2 = args.at(1);
                if (!symbolic::eq(arg1, loop.init())) {
                    std::swap(arg1, arg2);
                }
                if (!symbolic::eq(arg1, loop.init())) {
                    new_clause.push_back(literal);
                    continue;
                }
                auto new_literal = symbolic::Lt(indvar, arg2);
                new_clause.push_back(new_literal);
            } else {
                new_clause.push_back(literal);
            }
        }
        new_cnf.push_back(new_clause);
    }
    // Update if changed
    {
        symbolic::Condition new_condition = symbolic::__true__();
        for (auto& clause : new_cnf) {
            symbolic::Condition new_clause = symbolic::__false__();
            for (auto& literal : clause) {
                new_clause = symbolic::Or(new_clause, literal);
            }
            new_condition = symbolic::And(new_condition, new_clause);
        }
        if (!symbolic::eq(new_condition, condition)) {
            builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());
            applied = true;
            condition = new_condition;
        }
    }

    // Check uses of indvar in loop body are all memlets for further steps
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
    analysis::UsersView body_users(users_analysis, loop.root());
    bool all_subsets = true;
    for (auto& user : body_users.uses(indvar->get_name())) {
        if (!dynamic_cast<data_flow::Memlet*>(user->element())) {
            all_subsets = false;
            break;
        }
    }
    if (!all_subsets) {
        return applied;
    }

    try {
        new_cnf = symbolic::conjunctive_normal_form(condition);
    } catch (const symbolic::CNFException e) {
        return applied;
    }

    if (stride > 0) {
        // Step 3: Shift loop to start from zero if possible
        if (!symbolic::eq(loop.init(), symbolic::zero())) {
            // Require integer initial value for following steps
            if (!SymEngine::is_a<SymEngine::Integer>(*loop.init())) {
                return applied;
            }

            auto new_init = symbolic::zero();
            auto actual_indvar = symbolic::add(indvar, loop.init());

            // T
            bool canonical_condition = false;
            if (new_cnf.size() == 1) {
                auto& clause = new_cnf[0];
                if (clause.size() == 1) {
                    auto literal = clause[0];
                    if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
                        auto lhs = literal->get_args().at(0);
                        auto rhs = literal->get_args().at(1);
                        if (symbolic::eq(lhs, indvar) && !symbolic::uses(rhs, indvar)) {
                            condition = symbolic::Lt(indvar, symbolic::sub(rhs, loop.init()));
                            canonical_condition = true;
                        }
                    }
                }
            }
            if (!canonical_condition) {
                condition = symbolic::subs(condition, indvar, actual_indvar);
            }
            builder_.update_loop(loop, indvar, condition, new_init, loop.update());
            auto& root = loop.root();
            root.replace(indvar, actual_indvar);

            return true;
        }
    } else if (stride < 0) {
        // Step 4: Rotate loop if stride is negative
        if (stride != -1) {
            return applied;
        }
        if (new_cnf.size() != 1) {
            return applied;
        }
        auto& clause = new_cnf[0];
        if (clause.size() != 1) {
            return applied;
        }
        auto literal = clause[0];
        if (!SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
            return applied;
        }
        auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);
        auto lhs = slt->get_args().at(0);
        auto rhs = slt->get_args().at(1);
        if (!symbolic::eq(rhs, indvar)) {
            return applied;
        }

        // Update loop parameters
        auto new_init = symbolic::add(lhs, symbolic::one());
        auto new_update = symbolic::add(indvar, symbolic::one());
        auto new_condition = symbolic::Lt(indvar, symbolic::add(loop.init(), symbolic::one()));

        // Replace indvar by (init - indvar) in loop body
        loop.root().replace(indvar, symbolic::sub(loop.init(), symbolic::sub(indvar, new_init)));

        builder_.update_loop(loop, loop.indvar(), new_condition, new_init, new_update);
        return true;
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_normalization.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/loop_analysis.h"
5	#include "sdfg/symbolic/conjunctive_normal_form.h"
6	#include "sdfg/symbolic/polynomials.h"
7	#include "sdfg/symbolic/series.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	LoopNormalization::LoopNormalization(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
13	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {	8✔
14
15	};	8✔
16
17	bool LoopNormalization::accept(structured_control_flow::For& loop) {	8✔
18	bool applied = false;	8✔
19
20	// Step 1: Bring condition to CNF
21	symbolic::Condition condition = loop.condition();	8✔
22	sdfg::symbolic::CNF cnf;	8✔
23	try {	8✔
24	cnf = symbolic::conjunctive_normal_form(condition);	8✔
25	} catch (const symbolic::CNFException e) {	8✔
26	return false;	×
27	}	×
28	// Update if changed
29	{	8✔
30	symbolic::Condition new_condition = symbolic::__true__();	8✔
31	for (auto& clause : cnf) {	9✔
32	symbolic::Condition new_clause = symbolic::__false__();	9✔
33	for (auto& literal : clause) {	10✔
34	auto new_literal = SymEngine::rcp_dynamic_cast<const SymEngine::Boolean>(symbolic::simplify(literal));	10✔
35	new_clause = symbolic::Or(new_clause, new_literal);	10✔
36	}	10✔
37	new_condition = symbolic::And(new_condition, new_clause);	9✔
38	}	9✔
39	if (!symbolic::eq(new_condition, condition)) {	8✔
40	builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	×
41	applied = true;	×
42	}	×
43	condition = new_condition;	8✔
44	}	8✔
45
46	// Following steps require affine update
47	auto indvar = loop.indvar();	8✔
48	auto update = loop.update();	8✔
49	auto& assumptions_analysis = analysis_manager_.get<analysis::AssumptionsAnalysis>();	8✔
50	auto& assums = assumptions_analysis.get(loop, true);	8✔
51	auto [success, coeffs] = symbolic::series::affine_int_coeffs(update, indvar, assums);	8✔
52	if (!success) {	8✔
53	return applied;	×
54	}	×
55	auto [mul_coeff, add_coeff] = coeffs;	8✔
56	if (mul_coeff->as_int() != 1) {	8✔
57	return applied;	×
58	}	×
59	int stride = add_coeff->as_int();	8✔
60	if (stride == 0) {	8✔
61	return applied;	×
62	}	×
63
64	// Step 2: Simplify literals of CNF that involve the induction variable
65	symbolic::CNF new_cnf;	8✔
66	for (auto& clause : cnf) {	9✔
67	std::vector<symbolic::Condition> new_clause;	9✔
68	for (auto& literal : clause) {	10✔
69	if (SymEngine::is_a<SymEngine::Unequality>(*literal)) {	10✔
70	auto old_literal = SymEngine::rcp_static_cast<const SymEngine::Unequality>(literal);	8✔
71	auto lhs = old_literal->get_args().at(0);	8✔
72	auto rhs = old_literal->get_args().at(1);	8✔
73	if (symbolic::uses(lhs, indvar) && symbolic::uses(rhs, indvar)) {	8✔
74	new_clause.push_back(literal);	×
75	continue;	×
76	}	×
77	if (!symbolic::uses(rhs, indvar)) {	8✔
78	std::swap(lhs, rhs);	×
79	}	×
80	if (!symbolic::uses(rhs, indvar)) {	8✔
81	new_clause.push_back(literal);	×
82	continue;	×
83	}	×
84
85	// RHS is now guranteed to use the indvar
86
87	// 1. Solve inequality for indvar (affine case)
88	symbolic::SymbolVec syms = {indvar};	8✔
89	auto poly_rhs = symbolic::polynomial(rhs, syms);	8✔
90	if (poly_rhs == SymEngine::null) {	8✔
91	new_clause.push_back(literal);	×
92	continue;	×
93	}	×
94	auto coeffs_rhs = symbolic::affine_coefficients(poly_rhs, syms);	8✔
95	auto mul_coeff_rhs = coeffs_rhs[indvar];	8✔
96	auto add_coeff_rhs = coeffs_rhs[symbolic::symbol("__daisy_constant__")];	8✔
97
98	auto new_rhs = symbolic::sub(lhs, add_coeff_rhs);	8✔
99	// TODO: integer division
100	new_rhs = symbolic::div(new_rhs, mul_coeff_rhs);	8✔
101	auto new_lhs = indvar;	8✔
102
103	// 2. Convert to comparison based on stride sign
104
105	// Special cases: \|stride\| == 1
106	if (stride == 1) {	8✔
107	auto new_literal = symbolic::Lt(new_lhs, new_rhs);	5✔
108	new_clause.push_back(new_literal);	5✔
109	continue;	5✔
110	} else if (stride == -1) {	5✔
111	auto new_literal = symbolic::Gt(new_lhs, new_rhs);	1✔
112	new_clause.push_back(new_literal);	1✔
113	continue;	1✔
114	}	1✔
115
116	// Fallback general case
117	new_clause.push_back(symbolic::Ne(new_lhs, new_rhs));	2✔
118	} else if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	2✔
119	// Remove trivial max expressions
120	auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	2✔
121	auto lhs = slt->get_args().at(0);	2✔
122	auto rhs = slt->get_args().at(1);	2✔
123	if (!symbolic::eq(lhs, indvar)) {	2✔
124	new_clause.push_back(literal);	1✔
125	continue;	1✔
126	}	1✔
127	if (!SymEngine::is_a<SymEngine::Max>(*rhs)) {	1✔
128	new_clause.push_back(literal);	×
129	continue;	×
130	}	×
131	auto max_expr = SymEngine::rcp_static_cast<const SymEngine::Max>(rhs);	1✔
132	auto args = max_expr->get_args();	1✔
133	if (args.size() != 2) {	1✔
134	new_clause.push_back(literal);	×
135	continue;	×
136	}	×
137	auto arg1 = args.at(0);	1✔
138	auto arg2 = args.at(1);	1✔
139	if (!symbolic::eq(arg1, loop.init())) {	1✔
140	std::swap(arg1, arg2);	×
141	}	×
142	if (!symbolic::eq(arg1, loop.init())) {	1✔
143	new_clause.push_back(literal);	×
144	continue;	×
145	}	×
146	auto new_literal = symbolic::Lt(indvar, arg2);	1✔
147	new_clause.push_back(new_literal);	1✔
148	} else {	1✔
149	new_clause.push_back(literal);	×
150	}	×
151	}	10✔
152	new_cnf.push_back(new_clause);	9✔
153	}	9✔
154	// Update if changed
155	{	8✔
156	symbolic::Condition new_condition = symbolic::__true__();	8✔
157	for (auto& clause : new_cnf) {	9✔
158	symbolic::Condition new_clause = symbolic::__false__();	9✔
159	for (auto& literal : clause) {	10✔
160	new_clause = symbolic::Or(new_clause, literal);	10✔
161	}	10✔
162	new_condition = symbolic::And(new_condition, new_clause);	9✔
163	}	9✔
164	if (!symbolic::eq(new_condition, condition)) {	8✔
165	builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	5✔
166	applied = true;	5✔
167	condition = new_condition;	5✔
168	}	5✔
169	}	8✔
170
171	// Check uses of indvar in loop body are all memlets for further steps
172	auto& users_analysis = analysis_manager_.get<analysis::Users>();	8✔
173	analysis::UsersView body_users(users_analysis, loop.root());	8✔
174	bool all_subsets = true;	8✔
175	for (auto& user : body_users.uses(indvar->get_name())) {	8✔
176	if (!dynamic_cast<data_flow::Memlet*>(user->element())) {	1✔
177	all_subsets = false;	1✔
178	break;	1✔
179	}	1✔
180	}	1✔
181	if (!all_subsets) {	8✔
182	return applied;	1✔
183	}	1✔
184
185	try {	7✔
186	new_cnf = symbolic::conjunctive_normal_form(condition);	7✔
187	} catch (const symbolic::CNFException e) {	7✔
188	return applied;	×
189	}	×
190
191	if (stride > 0) {	7✔
192	// Step 3: Shift loop to start from zero if possible
193	if (!symbolic::eq(loop.init(), symbolic::zero())) {	5✔
194	// Require integer initial value for following steps
195	if (!SymEngine::is_a<SymEngine::Integer>(*loop.init())) {	×
196	return applied;	×
197	}	×
198
199	auto new_init = symbolic::zero();	×
200	auto actual_indvar = symbolic::add(indvar, loop.init());	×
201
202	// T
203	bool canonical_condition = false;	×
204	if (new_cnf.size() == 1) {	×
205	auto& clause = new_cnf[0];	×
206	if (clause.size() == 1) {	×
207	auto literal = clause[0];	×
208	if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	×
209	auto lhs = literal->get_args().at(0);	×
210	auto rhs = literal->get_args().at(1);	×
211	if (symbolic::eq(lhs, indvar) && !symbolic::uses(rhs, indvar)) {	×
212	condition = symbolic::Lt(indvar, symbolic::sub(rhs, loop.init()));	×
213	canonical_condition = true;	×
214	}	×
215	}	×
216	}	×
217	}	×
218	if (!canonical_condition) {	×
219	condition = symbolic::subs(condition, indvar, actual_indvar);	×
220	}	×
221	builder_.update_loop(loop, indvar, condition, new_init, loop.update());	×
222	auto& root = loop.root();	×
223	root.replace(indvar, actual_indvar);	×
224
225	return true;	×
226	}	×
227	} else if (stride < 0) {	5✔
228	// Step 4: Rotate loop if stride is negative
229	if (stride != -1) {	2✔
230	return applied;	1✔
231	}	1✔
232	if (new_cnf.size() != 1) {	1✔
233	return applied;	×
234	}	×
235	auto& clause = new_cnf[0];	1✔
236	if (clause.size() != 1) {	1✔
237	return applied;	×
238	}	×
239	auto literal = clause[0];	1✔
240	if (!SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	1✔
241	return applied;	×
242	}	×
243	auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	1✔
244	auto lhs = slt->get_args().at(0);	1✔
245	auto rhs = slt->get_args().at(1);	1✔
246	if (!symbolic::eq(rhs, indvar)) {	1✔
247	return applied;	×
248	}	×
249
250	// Update loop parameters
251	auto new_init = symbolic::add(lhs, symbolic::one());	1✔
252	auto new_update = symbolic::add(indvar, symbolic::one());	1✔
253	auto new_condition = symbolic::Lt(indvar, symbolic::add(loop.init(), symbolic::one()));	1✔
254
255	// Replace indvar by (init - indvar) in loop body
256	loop.root().replace(indvar, symbolic::sub(loop.init(), symbolic::sub(indvar, new_init)));	1✔
257
258	builder_.update_loop(loop, loop.indvar(), new_condition, new_init, new_update);	1✔
259	return true;	1✔
260	}	1✔
261
262	return applied;	5✔
263	};	7✔
264
265	} // namespace passes
266	} // namespace sdfg

daisytuner / sdfglib / 20764569418

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