15340968114

Committed 30 May 2025 06:47AM UTC coverage: 58.553% (+0.2%) from 58.324%

Build # 15340968114

Build Type

push

github

Committed by

web-flow

Commit Message

Add parallel Map node

* Introduce Map data structure

* Prepare infrastructure

* implement analysis support

* Add basic infrastructure

* visualizer/serializer

* include fix

* update from main

* remove default

* happens before test + fixes

* builder test

* dispatcher test

* visitor, copy and serializer tests

* for2map structures

* for2map conversion draft

* add tests

* Bug fixes

* small updates from feedback

* Visitor style pass implementation

* cleanup

* fixes linting errors

---------

Co-authored-by: Lukas Truemper <lukas.truemper@outlook.de>

Run Details

258 of 381 new or added lines in 26 files covered. (67.72%)

17 existing lines in 14 files now uncovered.

8184 of 13977 relevant lines covered (58.55%)

109.83 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"

namespace sdfg {
namespace passes {

bool LoopDependentSymbolElimination::eliminate_symbols(
    builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
    structured_control_flow::For& 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 for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
            queue.push_back(&for_stmt->root());
        } else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {
            queue.push_back(&kern_stmt->root());
        } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {
            queue.push_back(&map_stmt->root());
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/loop_dependent_symbol_elimination.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	bool LoopDependentSymbolElimination::eliminate_symbols(	×
7	builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager,
8	structured_control_flow::For& loop, structured_control_flow::Transition& transition) {
9	if (loop.root().size() == 0) {	×
10	return false;	×
11	}
12
13	bool applied = false;	×
14
15	auto indvar = loop.indvar();	×
16	auto update = loop.update();	×
17	auto init = loop.init();	×
18	auto condition = loop.condition();	×
19
20	// Assume simple loops: i = 0; i < N; i++
21	if (!SymEngine::eq(init, symbolic::integer(0))) {	×
22	return false;	×
23	}
24	auto match = symbolic::affine(update, indvar);	×
25	if (match.first == SymEngine::null) {	×
26	return false;	×
27	}
28	if (!SymEngine::eq(match.first, symbolic::integer(1)) \|\|	×
29	!SymEngine::eq(match.second, symbolic::integer(1))) {	×
30	return false;	×
31	}
32	auto bound = analysis::DataParallelismAnalysis::bound(loop);	×
33	if (bound == SymEngine::null \|\| !SymEngine::is_a<SymEngine::StrictLessThan>(*condition)) {	×
34	return false;	×
35	}
36	for (auto atom : symbolic::atoms(bound)) {	×
37	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	×
38	if (transition.assignments().find(sym) != transition.assignments().end()) {	×
39	return false;	×
40	}
41	}	×
42
43	// Find all symbolic upates
44	auto& last_transition = loop.root().at(loop.root().size() - 1).second;	×
45	auto& last_assignments = last_transition.assignments();	×
46	std::unordered_set<std::string> loop_dependent_symbols;	×
47	for (auto& entry : last_assignments) {	×
48	auto& sym = entry.first;	×
49	auto& assign = entry.second;	×
50	auto sym_match = symbolic::affine(assign, sym);	×
51	if (sym_match.first == SymEngine::null) {	×
52	continue;	×
53	}
54	if (!SymEngine::eq(sym_match.first, symbolic::integer(1)) \|\|	×
55	!SymEngine::eq(sym_match.second, symbolic::integer(1))) {	×
56	return false;	×
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()	×
NEW 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 for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
130	queue.push_back(&for_stmt->root());	×
131	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	×
132	queue.push_back(&kern_stmt->root());	×
NEW 133	} else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {	×
NEW 134	queue.push_back(&map_stmt->root());	×
UNCOV 135	}	×
136	}
137
138	return applied;	×
139	};	×
140
141	} // namespace passes
142	} // namespace sdfg

daisytuner / sdfglib / 15340968114

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