20263852258

Committed 16 Dec 2025 09:58AM UTC coverage: 40.086% (-0.2%) from 40.252%

Build # 20263852258

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #392 from daisytuner/for2map-performance

refactors passes to improve performance

Run Details

13621 of 43972 branches covered (30.98%)

Branch coverage included in aggregate %.

126 of 173 new or added lines in 14 files covered. (72.83%)

55 existing lines in 8 files now uncovered.

11633 of 19027 relevant lines covered (61.14%)

90.79 hits per line

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

0.0

/src/passes/symbolic/symbol_evolution.cpp

#include "sdfg/passes/symbolic/symbol_evolution.h"

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/dominance_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/scope_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/symbolic/polynomials.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

symbolic::Expression scalar_evolution(
    structured_control_flow::StructuredLoop& loop,
    symbolic::Symbol indvar,
    symbolic::Expression indvar_update,
    symbolic::Expression indvar_init,
    symbolic::Symbol sym,
    symbolic::Expression sym_update,
    symbolic::Expression sym_init,
    const std::unordered_set<std::string>& moving_symbols
) {
    // Check if expr is safe
    for (auto& atom : symbolic::atoms(sym_update)) {
        if (symbolic::eq(atom, sym)) {
            continue;
        }
        if (moving_symbols.find(atom->get_name()) != moving_symbols.end()) {
            return SymEngine::null;
        }
    }

    // Pattern 1: Constant
    if (!symbolic::uses(sym_update, sym) && symbolic::eq(sym_update, sym_init)) {
        return sym_update;
    }

    // Pattern 2: Loop Alias
    if (symbolic::eq(sym_update, indvar_update) && symbolic::eq(sym_init, indvar_init)) {
        return indvar;
    }

    auto stride = analysis::LoopAnalysis::stride(&loop);
    if (stride == SymEngine::null) {
        return SymEngine::null;
    }

    // Pattern 3: Loop Alias for indvar_(n-1)
    if (symbolic::uses(sym_update, indvar) && !symbolic::uses(sym_update, sym)) {
        if (stride->as_int() <= 0) {
            return SymEngine::null;
        }

        // Hypothesis: sym_update = f(indvar_(n-1)) = f(indvar - stride)
        auto sym_update_prev = symbolic::subs(sym_update, indvar, symbolic::sub(indvar, stride));

        // Condition: that iter_0 equals sym init
        auto sym_update_0 = symbolic::subs(sym_update, indvar, symbolic::sub(indvar_init, stride));
        if (!symbolic::eq(sym_update_0, sym_init)) {
            return SymEngine::null;
        }

        return sym_update_prev;
    }

    // Pattern 3: Affine update
    symbolic::SymbolVec gens = {sym};
    auto poly = symbolic::polynomial(sym_update, gens);
    auto coeffs = symbolic::affine_coefficients(poly, gens);
    if (coeffs.empty()) {
        return SymEngine::null;
    }
    auto mul = coeffs.at(sym);
    if (!symbolic::eq(mul, symbolic::one())) {
        return SymEngine::null;
    }
    auto offset = coeffs.at(symbolic::symbol("__daisy_constant__"));

    auto iter = symbolic::div(symbolic::sub(indvar, indvar_init), stride);
    auto inv = symbolic::add(symbolic::mul(iter, offset), sym_init);
    return inv;
}

bool SymbolEvolution::eliminate_symbols(
    builder::StructuredSDFGBuilder& builder,
    analysis::AnalysisManager& analysis_manager,
    structured_control_flow::StructuredLoop& loop,
    structured_control_flow::Transition& transition
) {
    if (loop.root().size() == 0) {
        return false;
    }

    bool applied = false;

    auto indvar = loop.indvar();
    auto update = loop.update();
    auto init = loop.init();
    auto condition = loop.condition();

    auto& users = analysis_manager.get<analysis::Users>();
    auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();
    analysis::UsersView body_users(users, loop.root());

    // Loop-dependent symbols are written in the loop body
    std::unordered_set<std::string> candidates;
    for (auto& entry : body_users.writes()) {
        auto& type = builder.subject().type(entry->container());
        if (!dynamic_cast<const types::Scalar*>(&type)) {
            continue;
        }
        if (!types::is_integer(type.primitive_type())) {
            continue;
        }
        candidates.insert(entry->container());
    }

    // Try to eliminate each candidate
    for (auto& sym : candidates) {
        // Criterion: We need to set the final value after the loop
        if (transition.assignments().find(symbolic::symbol(sym)) != transition.assignments().end()) {
            continue;
        }

        // Criterion: Must be written once
        if (body_users.writes(sym).size() != 1) {
            continue;
        }
        // Criterion: Must be read to avoid infinite loop
        if (body_users.reads(sym).size() == 0) {
            continue;
        }

        // Criterion: Write must be a symbolic assignment
        auto update_write = body_users.writes(sym).at(0);
        auto update_write_element = update_write->element();
        if (!dynamic_cast<structured_control_flow::Transition*>(update_write_element)) {
            continue;
        }
        auto& update_transition = static_cast<structured_control_flow::Transition&>(*update_write_element);
        auto update_sym = update_transition.assignments().at(symbolic::symbol(sym));

        // Criterion: Not in a nested loop
        bool nested_loop = false;
        auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
        structured_control_flow::ControlFlowNode* scope = &update_transition.parent();
        while (scope != nullptr && scope != &loop.root()) {
            if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(scope)) {
                nested_loop = true;
                break;
            } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(scope)) {
                nested_loop = true;
                break;
            }
            scope = scope_analysis.parent_scope(scope);
        }
        if (nested_loop) {
            continue;
        }

        // Criterion: Candidate is not read after the update
        auto uses = body_users.all_uses_after(*update_write);
        bool used_after_update = false;
        for (auto& use : uses) {
            if (use->container() == sym) {
                used_after_update = true;
                break;
            }
        }
        if (used_after_update) {
            continue;
        }

        // Criterion: Candidate is initialized before the loop
        auto all_writes = users.writes(sym);
        if (all_writes.size() != 2) {
            continue;
        }
        auto init_write = *all_writes.begin();
        if (init_write == update_write) {
            init_write = *(++all_writes.begin());
        }
        if (!dominance_analysis.dominates(*init_write, *update_write)) {
            continue;
        }
        if (!dynamic_cast<structured_control_flow::Transition*>(init_write->element())) {
            continue;
        }
        auto& init_transition = static_cast<structured_control_flow::Transition&>(*init_write->element());
        auto init_sym = init_transition.assignments().at(symbolic::symbol(sym));

        // Criterion: Infer scalar evolution
        auto evolution =
            scalar_evolution(loop, indvar, update, init, symbolic::symbol(sym), update_sym, init_sym, candidates);
        if (evolution == SymEngine::null) {
            continue;
        }

        // Apply by inserting redefinition before the loop body
        auto& old_first_block = loop.root().at(0).first;
        builder.add_block_before(
            loop.root(), old_first_block, {{symbolic::symbol(sym), evolution}}, old_first_block.debug_info()
        );
        update_transition.assignments().erase(symbolic::symbol(sym));
        transition.assignments().insert({symbolic::symbol(sym), update_sym});

        applied = true;
    }

    return applied;
};

SymbolEvolution::SymbolEvolution()
    : Pass() {

      };

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

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

    // Traverse structured SDFG
    std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};
    while (!queue.empty()) {
        auto current = queue.front();
        queue.pop_front();

        // Add children to queue
        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                auto child = sequence_stmt->at(i);
                if (auto match = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {
                    applied |= this->eliminate_symbols(builder, analysis_manager, *match, child.second);
                }
            }
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
                queue.push_back(&sequence_stmt->at(i).first);
            }
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
                queue.push_back(&if_else_stmt->at(i).first);
            }
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
            queue.push_back(&loop_stmt->root());
        } else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
            queue.push_back(&sloop_stmt->root());
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/symbolic/symbol_evolution.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/dominance_analysis.h"
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/analysis/scope_analysis.h"
7	#include "sdfg/analysis/users.h"
8	#include "sdfg/symbolic/polynomials.h"
9	#include "sdfg/symbolic/series.h"
10
11	namespace sdfg {
12	namespace passes {
13
14	symbolic::Expression scalar_evolution(	×
15	structured_control_flow::StructuredLoop& loop,
16	symbolic::Symbol indvar,
17	symbolic::Expression indvar_update,
18	symbolic::Expression indvar_init,
19	symbolic::Symbol sym,
20	symbolic::Expression sym_update,
21	symbolic::Expression sym_init,
22	const std::unordered_set<std::string>& moving_symbols
23	) {
24	// Check if expr is safe
25	for (auto& atom : symbolic::atoms(sym_update)) {	×
26	if (symbolic::eq(atom, sym)) {	×
27	continue;	×
28	}
29	if (moving_symbols.find(atom->get_name()) != moving_symbols.end()) {	×
30	return SymEngine::null;	×
31	}
32	}
33
34	// Pattern 1: Constant
35	if (!symbolic::uses(sym_update, sym) && symbolic::eq(sym_update, sym_init)) {	×
36	return sym_update;	×
37	}
38
39	// Pattern 2: Loop Alias
40	if (symbolic::eq(sym_update, indvar_update) && symbolic::eq(sym_init, indvar_init)) {	×
41	return indvar;	×
42	}
43
44	auto stride = analysis::LoopAnalysis::stride(&loop);	×
45	if (stride == SymEngine::null) {	×
46	return SymEngine::null;	×
47	}
48
49	// Pattern 3: Loop Alias for indvar_(n-1)
50	if (symbolic::uses(sym_update, indvar) && !symbolic::uses(sym_update, sym)) {	×
51	if (stride->as_int() <= 0) {	×
52	return SymEngine::null;	×
53	}
54
55	// Hypothesis: sym_update = f(indvar_(n-1)) = f(indvar - stride)
56	auto sym_update_prev = symbolic::subs(sym_update, indvar, symbolic::sub(indvar, stride));	×
57
58	// Condition: that iter_0 equals sym init
59	auto sym_update_0 = symbolic::subs(sym_update, indvar, symbolic::sub(indvar_init, stride));	×
60	if (!symbolic::eq(sym_update_0, sym_init)) {	×
61	return SymEngine::null;	×
62	}
63
64	return sym_update_prev;	×
65	}	×
66
67	// Pattern 3: Affine update
68	symbolic::SymbolVec gens = {sym};	×
69	auto poly = symbolic::polynomial(sym_update, gens);	×
70	auto coeffs = symbolic::affine_coefficients(poly, gens);	×
71	if (coeffs.empty()) {	×
72	return SymEngine::null;	×
73	}
74	auto mul = coeffs.at(sym);	×
75	if (!symbolic::eq(mul, symbolic::one())) {	×
76	return SymEngine::null;	×
77	}
78	auto offset = coeffs.at(symbolic::symbol("__daisy_constant__"));	×
79
80	auto iter = symbolic::div(symbolic::sub(indvar, indvar_init), stride);	×
81	auto inv = symbolic::add(symbolic::mul(iter, offset), sym_init);	×
82	return inv;	×
83	}	×
84
85	bool SymbolEvolution::eliminate_symbols(	×
86	builder::StructuredSDFGBuilder& builder,
87	analysis::AnalysisManager& analysis_manager,
88	structured_control_flow::StructuredLoop& loop,
89	structured_control_flow::Transition& transition
90	) {
91	if (loop.root().size() == 0) {	×
92	return false;	×
93	}
94
95	bool applied = false;	×
96
97	auto indvar = loop.indvar();	×
98	auto update = loop.update();	×
99	auto init = loop.init();	×
100	auto condition = loop.condition();	×
101
102	auto& users = analysis_manager.get<analysis::Users>();	×
103	auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();	×
104	analysis::UsersView body_users(users, loop.root());	×
105
106	// Loop-dependent symbols are written in the loop body
107	std::unordered_set<std::string> candidates;	×
108	for (auto& entry : body_users.writes()) {	×
109	auto& type = builder.subject().type(entry->container());	×
110	if (!dynamic_cast<const types::Scalar*>(&type)) {	×
111	continue;	×
112	}
113	if (!types::is_integer(type.primitive_type())) {	×
114	continue;	×
115	}
116	candidates.insert(entry->container());	×
117	}
118
119	// Try to eliminate each candidate
120	for (auto& sym : candidates) {	×
121	// Criterion: We need to set the final value after the loop
122	if (transition.assignments().find(symbolic::symbol(sym)) != transition.assignments().end()) {	×
123	continue;	×
124	}
125
126	// Criterion: Must be written once
127	if (body_users.writes(sym).size() != 1) {	×
128	continue;	×
129	}
130	// Criterion: Must be read to avoid infinite loop
131	if (body_users.reads(sym).size() == 0) {	×
132	continue;	×
133	}
134
135	// Criterion: Write must be a symbolic assignment
136	auto update_write = body_users.writes(sym).at(0);	×
137	auto update_write_element = update_write->element();	×
138	if (!dynamic_cast<structured_control_flow::Transition*>(update_write_element)) {	×
139	continue;	×
140	}
141	auto& update_transition = static_cast<structured_control_flow::Transition&>(*update_write_element);	×
142	auto update_sym = update_transition.assignments().at(symbolic::symbol(sym));	×
143
144	// Criterion: Not in a nested loop
145	bool nested_loop = false;	×
146	auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();	×
147	structured_control_flow::ControlFlowNode* scope = &update_transition.parent();	×
148	while (scope != nullptr && scope != &loop.root()) {	×
149	if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(scope)) {	×
150	nested_loop = true;	×
151	break;	×
152	} else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(scope)) {	×
153	nested_loop = true;	×
154	break;	×
155	}
156	scope = scope_analysis.parent_scope(scope);	×
157	}
158	if (nested_loop) {	×
159	continue;	×
160	}
161
162	// Criterion: Candidate is not read after the update
163	auto uses = body_users.all_uses_after(*update_write);	×
164	bool used_after_update = false;	×
165	for (auto& use : uses) {	×
166	if (use->container() == sym) {	×
167	used_after_update = true;	×
168	break;	×
169	}
170	}
171	if (used_after_update) {	×
172	continue;	×
173	}
174
175	// Criterion: Candidate is initialized before the loop
176	auto all_writes = users.writes(sym);	×
177	if (all_writes.size() != 2) {	×
178	continue;	×
179	}
NEW 180	auto init_write = *all_writes.begin();	×
181	if (init_write == update_write) {	×
NEW 182	init_write = *(++all_writes.begin());	×
183	}	×
184	if (!dominance_analysis.dominates(init_write, update_write)) {	×
185	continue;	×
186	}
187	if (!dynamic_cast<structured_control_flow::Transition*>(init_write->element())) {	×
188	continue;	×
189	}
190	auto& init_transition = static_cast<structured_control_flow::Transition&>(*init_write->element());	×
191	auto init_sym = init_transition.assignments().at(symbolic::symbol(sym));	×
192
193	// Criterion: Infer scalar evolution
194	auto evolution =
195	scalar_evolution(loop, indvar, update, init, symbolic::symbol(sym), update_sym, init_sym, candidates);	×
196	if (evolution == SymEngine::null) {	×
197	continue;	×
198	}
199
200	// Apply by inserting redefinition before the loop body
201	auto& old_first_block = loop.root().at(0).first;	×
202	builder.add_block_before(	×
203	loop.root(), old_first_block, {{symbolic::symbol(sym), evolution}}, old_first_block.debug_info()	×
204	);
205	update_transition.assignments().erase(symbolic::symbol(sym));	×
206	transition.assignments().insert({symbolic::symbol(sym), update_sym});	×
207
208	applied = true;	×
209	}	×
210
211	return applied;	×
212	};	×
213
UNCOV 214	SymbolEvolution::SymbolEvolution()	×
UNCOV 215	: Pass() {	×
216
UNCOV 217	};	×
218
219	std::string SymbolEvolution::name() { return "SymbolEvolution"; };	×
220
221	bool SymbolEvolution::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	×
222	bool applied = false;	×
223
224	// Traverse structured SDFG
225	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
226	while (!queue.empty()) {	×
227	auto current = queue.front();	×
228	queue.pop_front();	×
229
230	// Add children to queue
231	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
232	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
233	auto child = sequence_stmt->at(i);	×
234	if (auto match = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {	×
235	applied \|= this->eliminate_symbols(builder, analysis_manager, *match, child.second);	×
236	}	×
237	}	×
238	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
239	queue.push_back(&sequence_stmt->at(i).first);	×
240	}	×
241	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
242	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
243	queue.push_back(&if_else_stmt->at(i).first);	×
244	}	×
245	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
246	queue.push_back(&loop_stmt->root());	×
247	} else if (auto sloop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	×
248	queue.push_back(&sloop_stmt->root());	×
249	}	×
250	}
251
252	return applied;	×
253	};	×
254
255	} // namespace passes
256	} // namespace sdfg

daisytuner / sdfglib / 20263852258

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