15822095523

Committed 23 Jun 2025 10:43AM UTC coverage: 63.824% (-0.02%) from 63.84%

Build # 15822095523

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #99 from daisytuner/delinearization

adds support for delinearizing affine expressions

Run Details

69 of 103 new or added lines in 8 files covered. (66.99%)

3 existing lines in 2 files now uncovered.

8084 of 12666 relevant lines covered (63.82%)

149.74 hits per line

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

0.0

/src/passes/structured_control_flow/loop_dependent_symbol_elimination.cpp

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

#include "sdfg/analysis/assumptions_analysis.h"
#include "sdfg/analysis/data_parallelism_analysis.h"
#include "sdfg/analysis/loop_analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/symbolic/series.h"

namespace sdfg {
namespace passes {

bool LoopDependentSymbolElimination::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& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
    auto assumptions = assumptions_analysis.get(loop.root(), true);

    // Assume simple loops: i = 0; i < N; i++
    if (!SymEngine::eq(*init, *symbolic::integer(0))) {
        return false;
    }
    if (!analysis::LoopAnalysis::is_contiguous(&loop, assumptions_analysis)) {
        return false;
    }
    auto bound = analysis::DataParallelismAnalysis::bound(loop);
    if (bound == SymEngine::null || !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {
        return false;
    }
    for (auto atom : symbolic::atoms(bound)) {
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
        if (transition.assignments().find(sym) != transition.assignments().end()) {
            return false;
        }
    }

    // Find all symbolic upates
    auto& last_transition = loop.root().at(loop.root().size() - 1).second;
    auto& last_assignments = last_transition.assignments();
    std::unordered_set<std::string> loop_dependent_symbols;
    for (auto& entry : last_assignments) {
        auto& sym = entry.first;
        auto& assign = entry.second;
        if (!symbolic::series::is_contiguous(assign, sym, assumptions)) {
            continue;
        }
        loop_dependent_symbols.insert(sym->get_name());
    }
    if (loop_dependent_symbols.empty()) {
        return false;
    }

    auto& all_users = analysis_manager.get<analysis::Users>();
    analysis::UsersView users(all_users, loop.root());
    for (auto& cand : loop_dependent_symbols) {
        auto writes = users.writes(cand);
        if (writes.size() != 1) {
            continue;
        }
        auto reads = users.reads(cand);
        bool has_dataflow = false;
        for (auto& read : reads) {
            if (dynamic_cast<data_flow::AccessNode*>(read->element())) {
                has_dataflow = true;
                break;
            }
        }
        if (has_dataflow) {
            continue;
        }
        auto sym = symbolic::symbol(cand);
        last_assignments.erase(sym);
        loop.root().replace(sym, symbolic::add(indvar, sym));

        transition.assignments().insert({sym, symbolic::add(sym, bound)});

        applied = true;
    }

    return applied;
};

LoopDependentSymbolElimination::LoopDependentSymbolElimination()
    : Pass() {

      };

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

bool LoopDependentSymbolElimination::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::For*>(&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/structured_control_flow/loop_dependent_symbol_elimination.h"
2
3	#include "sdfg/analysis/assumptions_analysis.h"
4	#include "sdfg/analysis/data_parallelism_analysis.h"
5	#include "sdfg/analysis/loop_analysis.h"
6	#include "sdfg/analysis/users.h"
7	#include "sdfg/symbolic/series.h"
8
9	namespace sdfg {
10	namespace passes {
11
12	bool LoopDependentSymbolElimination::eliminate_symbols(	×
13	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
14	structured_control_flow::StructuredLoop& loop,
15	structured_control_flow::Transition& transition) {
16	if (loop.root().size() == 0) {	×
17	return false;	×
18	}
19
20	bool applied = false;	×
21
22	auto indvar = loop.indvar();	×
23	auto update = loop.update();	×
24	auto init = loop.init();	×
25	auto condition = loop.condition();	×
26
27	auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();	×
28	auto assumptions = assumptions_analysis.get(loop.root(), true);	×
29
30	// Assume simple loops: i = 0; i < N; i++
31	if (!SymEngine::eq(init, symbolic::integer(0))) {	×
32	return false;	×
33	}
34	if (!analysis::LoopAnalysis::is_contiguous(&loop, assumptions_analysis)) {	×
35	return false;	×
36	}
37	auto bound = analysis::DataParallelismAnalysis::bound(loop);	×
38	if (bound == SymEngine::null \|\| !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
39	return false;	×
40	}
41	for (auto atom : symbolic::atoms(bound)) {	×
42	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
43	if (transition.assignments().find(sym) != transition.assignments().end()) {	×
44	return false;	×
45	}
46	}	×
47
48	// Find all symbolic upates
49	auto& last_transition = loop.root().at(loop.root().size() - 1).second;	×
50	auto& last_assignments = last_transition.assignments();	×
51	std::unordered_set<std::string> loop_dependent_symbols;	×
52	for (auto& entry : last_assignments) {	×
53	auto& sym = entry.first;	×
54	auto& assign = entry.second;	×
NEW 55	if (!symbolic::series::is_contiguous(assign, sym, assumptions)) {	×
56	continue;	×
57	}
58	loop_dependent_symbols.insert(sym->get_name());	×
59	}
60	if (loop_dependent_symbols.empty()) {	×
61	return false;	×
62	}
63
64	auto& all_users = analysis_manager.get<analysis::Users>();	×
65	analysis::UsersView users(all_users, loop.root());	×
66	for (auto& cand : loop_dependent_symbols) {	×
67	auto writes = users.writes(cand);	×
68	if (writes.size() != 1) {	×
69	continue;	×
70	}
71	auto reads = users.reads(cand);	×
72	bool has_dataflow = false;	×
73	for (auto& read : reads) {	×
74	if (dynamic_cast<data_flow::AccessNode*>(read->element())) {	×
75	has_dataflow = true;	×
76	break;	×
77	}
78	}
79	if (has_dataflow) {	×
80	continue;	×
81	}
82	auto sym = symbolic::symbol(cand);	×
83	last_assignments.erase(sym);	×
84	loop.root().replace(sym, symbolic::add(indvar, sym));	×
85
86	transition.assignments().insert({sym, symbolic::add(sym, bound)});	×
87
88	applied = true;	×
89	}	×
90
91	return applied;	×
92	};	×
93
94	LoopDependentSymbolElimination::LoopDependentSymbolElimination()	×
95	: Pass() {	×
96
97	};	×
98
99	std::string LoopDependentSymbolElimination::name() { return "LoopDependentSymbolElimination"; };	×
100
101	bool LoopDependentSymbolElimination::run_pass(builder::StructuredSDFGBuilder& builder,	×
102	analysis::AnalysisManager& analysis_manager) {
103	bool applied = false;	×
104
105	// Traverse structured SDFG
106	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
107	while (!queue.empty()) {	×
108	auto current = queue.front();	×
109	queue.pop_front();	×
110
111	// Add children to queue
112	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
113	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
114	auto child = sequence_stmt->at(i);	×
115	if (auto match = dynamic_cast<structured_control_flow::For*>(&child.first)) {	×
116	applied \|=	×
117	this->eliminate_symbols(builder, analysis_manager, *match, child.second);	×
118	}	×
119	}	×
120	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
121	queue.push_back(&sequence_stmt->at(i).first);	×
122	}	×
123	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
124	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
125	queue.push_back(&if_else_stmt->at(i).first);	×
126	}	×
127	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
128	queue.push_back(&loop_stmt->root());	×
129	} else if (auto sloop_stmt =	×
130	dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {	×
131	queue.push_back(&sloop_stmt->root());	×
132	}	×
133	}
134
135	return applied;	×
136	};	×
137
138	} // namespace passes
139	} // namespace sdfg

daisytuner / sdfglib / 15822095523

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