15512041711

Committed 07 Jun 2025 09:59PM UTC coverage: 57.416% (+0.1%) from 57.315%

Build # 15512041711

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #44 from daisytuner/StructuredLoops

Add Structured Loops

Run Details

51 of 102 new or added lines in 20 files covered. (50.0%)

10 existing lines in 8 files now uncovered.

7618 of 13268 relevant lines covered (57.42%)

116.01 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/data_parallelism_analysis.h"
#include "sdfg/structured_control_flow/structured_loop.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();

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

daisytuner / sdfglib / 15512041711

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