19479431007

Committed 18 Nov 2025 07:56PM UTC coverage: 62.184% (+0.02%) from 62.167%

Build # 19479431007

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #355 from daisytuner/loop-rotate

enables loop rotation for the simplest cases

Run Details

11 of 13 new or added lines in 2 files covered. (84.62%)

4 existing lines in 1 file now uncovered.

11116 of 17876 relevant lines covered (62.18%)

112.36 hits per line

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

83.48

/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
    auto condition = loop.condition();
    sdfg::symbolic::CNF cnf;
    try {
        cnf = symbolic::conjunctive_normal_form(condition);
    } catch (const symbolic::CNFException e) {
        return false;
    }
    {
        symbolic::Condition new_condition = symbolic::__true__();
        for (auto& clause : 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;
    }

    // Step 2: Normalize bound
    auto indvar = loop.indvar();
    auto update = loop.update();

    // check if update is affine in indvar
    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();

    // Convert inequality-literals into comparisons with loop variable on LHS
    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)) {
                new_clause.push_back(literal);
                continue;
            }
            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;
            }

            // TODO: Modulo case: stride != +/-1
            new_clause.push_back(symbolic::Ne(new_lhs, new_rhs));
        }
        new_cnf.push_back(new_clause);
    }
    {
        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;
        }
    }

    // Step 3: 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;
    }

    // Criterion: Body is invariant to iteration order
    // I.e., a map or an associative/commutative reduction
    // Since all data-dependency analysis depend on positive stride
    // we do cheap approximations:
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
    analysis::UsersView body_users(users_analysis, loop.root());
    if (!body_users.uses(indvar->get_name()).empty()) {
        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);
    applied = 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)	7✔
13	: NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {	7✔
14
15	};	7✔
16
17	bool LoopNormalization::accept(structured_control_flow::For& loop) {	7✔
18	bool applied = false;	7✔
19
20	// Step 1: Bring condition to CNF
21	auto condition = loop.condition();	7✔
22	sdfg::symbolic::CNF cnf;	7✔
23	try {
24	cnf = symbolic::conjunctive_normal_form(condition);	7✔
25	} catch (const symbolic::CNFException e) {	7✔
26	return false;	×
27	}	×
28	{
29	symbolic::Condition new_condition = symbolic::__true__();	7✔
30	for (auto& clause : cnf) {	15✔
31	symbolic::Condition new_clause = symbolic::__false__();	8✔
32	for (auto& literal : clause) {	17✔
33	new_clause = symbolic::Or(new_clause, literal);	9✔
34	}
35	new_condition = symbolic::And(new_condition, new_clause);	8✔
36	}	8✔
37	if (!symbolic::eq(new_condition, condition)) {	7✔
NEW 38	builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	×
39	applied = true;	×
40	}	×
41	condition = new_condition;	7✔
42	}	7✔
43
44	// Step 2: Normalize bound
45	auto indvar = loop.indvar();	7✔
46	auto update = loop.update();	7✔
47
48	// check if update is affine in indvar
49	auto& assumptions_analysis = analysis_manager_.get<analysis::AssumptionsAnalysis>();	7✔
50	auto assums = assumptions_analysis.get(loop, true);	7✔
51	auto [success, coeffs] = symbolic::series::affine_int_coeffs(update, indvar, assums);	7✔
52	if (!success) {	7✔
53	return applied;	×
54	}
55	auto [mul_coeff, add_coeff] = coeffs;	14✔
56	if (mul_coeff->as_int() != 1) {	7✔
57	return applied;	×
58	}
59	int stride = add_coeff->as_int();	7✔
60
61	// Convert inequality-literals into comparisons with loop variable on LHS
62	symbolic::CNF new_cnf;	7✔
63	for (auto& clause : cnf) {	15✔
64	std::vector<symbolic::Condition> new_clause;	8✔
65	for (auto& literal : clause) {	17✔
66	if (!SymEngine::is_a<SymEngine::Unequality>(*literal)) {	9✔
67	new_clause.push_back(literal);	1✔
68	continue;	1✔
69	}
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;
110	} else if (stride == -1) {	8✔
111	auto new_literal = symbolic::Gt(new_lhs, new_rhs);	1✔
112	new_clause.push_back(new_literal);	1✔
113	continue;
114	}	1✔
115
116	// TODO: Modulo case: stride != +/-1
117	new_clause.push_back(symbolic::Ne(new_lhs, new_rhs));	2✔
118	}	8✔
119	new_cnf.push_back(new_clause);	8✔
120	}	8✔
121	{
122	symbolic::Condition new_condition = symbolic::__true__();	7✔
123	for (auto& clause : new_cnf) {	15✔
124	symbolic::Condition new_clause = symbolic::__false__();	8✔
125	for (auto& literal : clause) {	17✔
126	new_clause = symbolic::Or(new_clause, literal);	9✔
127	}
128	new_condition = symbolic::And(new_condition, new_clause);	8✔
129	}	8✔
130	if (!symbolic::eq(new_condition, condition)) {	7✔
131	builder_.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	4✔
132	applied = true;	4✔
133	}	4✔
134	}	7✔
135
136	// Step 3: Rotate loop if stride is negative
137	if (stride != -1) {	7✔
138	return applied;	5✔
139	}
140	if (new_cnf.size() != 1) {	2✔
UNCOV 141	return applied;	×
142	}
143	auto& clause = new_cnf[0];	2✔
144	if (clause.size() != 1) {	2✔
UNCOV 145	return applied;	×
146	}
147	auto literal = clause[0];	2✔
148	if (!SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	2✔
UNCOV 149	return applied;	×
150	}
151	auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	2✔
152	auto lhs = slt->get_args().at(0);	2✔
153	auto rhs = slt->get_args().at(1);	2✔
154	if (!symbolic::eq(rhs, indvar)) {	2✔
UNCOV 155	return applied;	×
156	}
157
158	// Criterion: Body is invariant to iteration order
159	// I.e., a map or an associative/commutative reduction
160	// Since all data-dependency analysis depend on positive stride
161	// we do cheap approximations:
162	auto& users_analysis = analysis_manager_.get<analysis::Users>();	2✔
163	analysis::UsersView body_users(users_analysis, loop.root());	2✔
164	if (!body_users.uses(indvar->get_name()).empty()) {	2✔
165	return applied;	1✔
166	}
167
168	// Update loop parameters
169	auto new_init = symbolic::add(lhs, symbolic::one());	1✔
170	auto new_update = symbolic::add(indvar, symbolic::one());	1✔
171	auto new_condition = symbolic::Lt(indvar, symbolic::add(loop.init(), symbolic::one()));	1✔
172
173	// Replace indvar by (init - indvar) in loop body
174	loop.root().replace(indvar, symbolic::sub(loop.init(), symbolic::sub(indvar, new_init)));	1✔
175
176	builder_.update_loop(loop, loop.indvar(), new_condition, new_init, new_update);	1✔
177	applied = true;	1✔
178
179	return applied;	1✔
180	};	7✔
181
182	} // namespace passes
183	} // namespace sdfg

daisytuner / sdfglib / 19479431007

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