17948757733

Committed 23 Sep 2025 02:05PM UTC coverage: 61.239% (+0.07%) from 61.165%

Build # 17948757733

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #239 from daisytuner/loop-normalization-rotation

extends loop normalization to rotate loops

Run Details

75 of 97 new or added lines in 2 files covered. (77.32%)

19 existing lines in 3 files now uncovered.

9557 of 15606 relevant lines covered (61.24%)

108.78 hits per line

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

80.83

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

bool LoopNormalization::apply(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    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;
    }

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

LoopNormalization::LoopNormalization()
    : Pass() {

      };

std::string LoopNormalization::name() { return "LoopNormalization"; };

bool LoopNormalization::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    for (const auto& loop : loop_analysis.loops()) {
        if (auto for_loop = dynamic_cast<structured_control_flow::For*>(loop)) {
            applied |= this->apply(builder, analysis_manager, *for_loop);
        }
    }

    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	bool LoopNormalization::apply(	6✔
13	builder::StructuredSDFGBuilder& builder,
14	analysis::AnalysisManager& analysis_manager,
15	structured_control_flow::For& loop
16	) {
17	bool applied = false;	6✔
18
19	// Step 1: Bring condition to CNF
20	auto condition = loop.condition();	6✔
21	sdfg::symbolic::CNF cnf;	6✔
22	try {
23	cnf = symbolic::conjunctive_normal_form(condition);	6✔
24	} catch (const symbolic::CNFException e) {	6✔
NEW 25	return false;	×
NEW 26	}	×
27	{
28	symbolic::Condition new_condition = symbolic::__true__();	6✔
29	for (auto& clause : cnf) {	13✔
30	symbolic::Condition new_clause = symbolic::__false__();	7✔
31	for (auto& literal : clause) {	15✔
32	new_clause = symbolic::Or(new_clause, literal);	8✔
33	}
34	new_condition = symbolic::And(new_condition, new_clause);	7✔
35	}	7✔
36	if (!symbolic::eq(new_condition, condition)) {	6✔
37	builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	×
38	applied = true;	×
39	}	×
40	condition = new_condition;	6✔
41	}	6✔
42
43	// Step 2: Normalize bound
44	auto indvar = loop.indvar();	6✔
45	auto update = loop.update();	6✔
46
47	// check if update is affine in indvar
48	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	6✔
49	auto assums = assumptions_analysis.get(loop, true);	6✔
50	auto [success, coeffs] = symbolic::series::affine_int_coeffs(update, indvar, assums);	6✔
51	if (!success) {	6✔
NEW 52	return applied;	×
53	}
54	auto [mul_coeff, add_coeff] = coeffs;	12✔
55	if (mul_coeff->as_int() != 1) {	6✔
UNCOV 56	return applied;	×
57	}
58	int stride = add_coeff->as_int();	6✔
59
60	// Convert inequality-literals into comparisons with loop variable on LHS
61	symbolic::CNF new_cnf;	6✔
62	for (auto& clause : cnf) {	13✔
63	std::vector<symbolic::Condition> new_clause;	7✔
64	for (auto& literal : clause) {	15✔
65	if (!SymEngine::is_a<SymEngine::Unequality>(*literal)) {	8✔
NEW 66	new_clause.push_back(literal);	×
NEW 67	continue;	×
68	}
69	auto old_literal = SymEngine::rcp_static_cast<const SymEngine::Unequality>(literal);	8✔
70	auto lhs = old_literal->get_args().at(0);	8✔
71	auto rhs = old_literal->get_args().at(1);	8✔
72	if (symbolic::uses(lhs, indvar) && symbolic::uses(rhs, indvar)) {	8✔
NEW 73	new_clause.push_back(literal);	×
NEW 74	continue;	×
75	}
76	if (!symbolic::uses(rhs, indvar)) {	8✔
NEW 77	std::swap(lhs, rhs);	×
NEW 78	}	×
79	if (!symbolic::uses(rhs, indvar)) {	8✔
NEW 80	new_clause.push_back(literal);	×
NEW 81	continue;	×
82	}
83
84	// RHS is now guranteed to use the indvar
85
86	// 1. Solve inequality for indvar (affine case)
87	symbolic::SymbolVec syms = {indvar};	8✔
88	auto poly_rhs = symbolic::polynomial(rhs, syms);	8✔
89	if (poly_rhs == SymEngine::null) {	8✔
NEW 90	new_clause.push_back(literal);	×
NEW 91	continue;	×
92	}
93	auto coeffs_rhs = symbolic::affine_coefficients(poly_rhs, syms);	8✔
94	auto mul_coeff_rhs = coeffs_rhs[indvar];	8✔
95	auto add_coeff_rhs = coeffs_rhs[symbolic::symbol("__daisy_constant__")];	8✔
96
97	auto new_rhs = symbolic::sub(lhs, add_coeff_rhs);	8✔
98	// TODO: integer division
99	new_rhs = symbolic::div(new_rhs, mul_coeff_rhs);	8✔
100	auto new_lhs = indvar;	8✔
101
102	// 2. Convert to comparison based on stride sign
103
104	// Special cases: \|stride\| == 1
105	if (stride == 1) {	8✔
106	auto new_literal = symbolic::Lt(new_lhs, new_rhs);	5✔
107	new_clause.push_back(new_literal);	5✔
108	continue;
109	} else if (stride == -1) {	8✔
110	auto new_literal = symbolic::Gt(new_lhs, new_rhs);	1✔
111	new_clause.push_back(new_literal);	1✔
112	continue;
113	}	1✔
114
115	// TODO: Modulo case: stride != +/-1
116	new_clause.push_back(symbolic::Ne(new_lhs, new_rhs));	2✔
117	}	8✔
118	new_cnf.push_back(new_clause);	7✔
119	}	7✔
120	{
121	symbolic::Condition new_condition = symbolic::__true__();	6✔
122	for (auto& clause : new_cnf) {	13✔
123	symbolic::Condition new_clause = symbolic::__false__();	7✔
124	for (auto& literal : clause) {	15✔
125	new_clause = symbolic::Or(new_clause, literal);	8✔
126	}
127	new_condition = symbolic::And(new_condition, new_clause);	7✔
128	}	7✔
129	if (!symbolic::eq(new_condition, condition)) {	6✔
130	builder.update_loop(loop, loop.indvar(), new_condition, loop.init(), loop.update());	4✔
131	applied = true;	4✔
132	}	4✔
133	}	6✔
134
135	// Step 3: Rotate loop if stride is negative
136	if (stride != -1) {	6✔
137	return applied;	5✔
138	}
139	if (new_cnf.size() != 1) {	1✔
NEW 140	return applied;	×
141	}
142	auto& clause = new_cnf[0];	1✔
143	if (clause.size() != 1) {	1✔
NEW 144	return applied;	×
145	}
146	auto literal = clause[0];	1✔
147	if (!SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {	1✔
NEW 148	return applied;	×
149	}
150	auto slt = SymEngine::rcp_static_cast<const SymEngine::StrictLessThan>(literal);	1✔
151	auto lhs = slt->get_args().at(0);	1✔
152	auto rhs = slt->get_args().at(1);	1✔
153	if (!symbolic::eq(rhs, indvar)) {	1✔
NEW 154	return applied;	×
155	}
156
157	// Update loop parameters
158	auto new_init = symbolic::add(lhs, symbolic::one());	1✔
159	auto new_update = symbolic::add(indvar, symbolic::one());	1✔
160	auto new_condition = symbolic::Lt(indvar, symbolic::add(loop.init(), symbolic::one()));	1✔
161
162	// Replace indvar by (init - indvar) in loop body
163	loop.root().replace(indvar, symbolic::sub(loop.init(), symbolic::sub(indvar, new_init)));	1✔
164
165	builder.update_loop(loop, loop.indvar(), new_condition, new_init, new_update);	1✔
166
167	return applied;	1✔
168	};	6✔
169
170	LoopNormalization::LoopNormalization()	6✔
171	: Pass() {	6✔
172
173	};	6✔
174
175	std::string LoopNormalization::name() { return "LoopNormalization"; };	×
176
177	bool LoopNormalization::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	6✔
178	bool applied = false;	6✔
179
180	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	6✔
181	for (const auto& loop : loop_analysis.loops()) {	12✔
182	if (auto for_loop = dynamic_cast<structured_control_flow::For*>(loop)) {	6✔
183	applied \|= this->apply(builder, analysis_manager, *for_loop);	6✔
184	}	6✔
185	}
186
187	return applied;	6✔
188	};	×
189
190	} // namespace passes
191	} // namespace sdfg

daisytuner / sdfglib / 17948757733

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