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/common_assignment_elimination.cpp

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

namespace sdfg {
namespace passes {

CommonAssignmentElimination::CommonAssignmentElimination()
    : Pass() {

      };

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

bool CommonAssignmentElimination::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 if_else_stmt =
                        dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
                    if (if_else_stmt->size() < 2) {
                        continue;
                    }
                    auto& first_branch = if_else_stmt->at(0).first;
                    if (first_branch.size() == 0) {
                        continue;
                    }
                    auto& last_transition = first_branch.at(first_branch.size() - 1).second;
                    if (last_transition.assignments().size() == 0) {
                        continue;
                    }

                    // Check waw dependencies
                    for (auto& entry : last_transition.assignments()) {
                        auto& first_assign = entry.first;
                        auto& first_assignment = entry.second;
                        if (child.second.assignments().find(first_assign) !=
                            child.second.assignments().end()) {
                            continue;
                        }

                        // Check if all branches end with same assignment
                        bool all_branches_same = true;
                        for (size_t j = 1; j < if_else_stmt->size(); j++) {
                            auto& branch = if_else_stmt->at(j).first;
                            if (branch.size() == 0) {
                                all_branches_same = false;
                                break;
                            }

                            auto& transition = branch.at(branch.size() - 1).second;
                            if (transition.assignments().find(first_assign) ==
                                transition.assignments().end()) {
                                all_branches_same = false;
                                break;
                            }
                            if (!symbolic::eq(first_assignment,
                                              transition.assignments().at(first_assign))) {
                                all_branches_same = false;
                                break;
                            }
                        }

                        if (!all_branches_same) {
                            continue;
                        }

                        child.second.assignments().insert({first_assign, first_assignment});
                        applied = true;
                    }
                }
            }

            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<const structured_control_flow::Map*>(current)) {
            queue.push_back(&map_stmt->root());
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/common_assignment_elimination.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	CommonAssignmentElimination::CommonAssignmentElimination()	×
NEW 7	: Pass() {	×
8
9	};	×
10
11	std::string CommonAssignmentElimination::name() { return "CommonAssignmentElimination"; };	×
12
13	bool CommonAssignmentElimination::run_pass(builder::StructuredSDFGBuilder& builder,	×
14	analysis::AnalysisManager& analysis_manager) {
15	bool applied = false;	×
16
17	// Traverse structured SDFG
18	std::list<structured_control_flow::ControlFlowNode*> queue = {&builder.subject().root()};	×
19	while (!queue.empty()) {	×
20	auto current = queue.front();	×
21	queue.pop_front();	×
22
23	// Add children to queue
24	if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {	×
25	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
26	auto child = sequence_stmt->at(i);	×
27	if (auto if_else_stmt =	×
28	dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {	×
29	if (if_else_stmt->size() < 2) {	×
30	continue;	×
31	}
32	auto& first_branch = if_else_stmt->at(0).first;	×
33	if (first_branch.size() == 0) {	×
34	continue;	×
35	}
36	auto& last_transition = first_branch.at(first_branch.size() - 1).second;	×
37	if (last_transition.assignments().size() == 0) {	×
38	continue;	×
39	}
40
41	// Check waw dependencies
42	for (auto& entry : last_transition.assignments()) {	×
43	auto& first_assign = entry.first;	×
44	auto& first_assignment = entry.second;	×
45	if (child.second.assignments().find(first_assign) !=	×
46	child.second.assignments().end()) {	×
47	continue;	×
48	}
49
50	// Check if all branches end with same assignment
51	bool all_branches_same = true;	×
52	for (size_t j = 1; j < if_else_stmt->size(); j++) {	×
53	auto& branch = if_else_stmt->at(j).first;	×
54	if (branch.size() == 0) {	×
55	all_branches_same = false;	×
56	break;	×
57	}
58
59	auto& transition = branch.at(branch.size() - 1).second;	×
60	if (transition.assignments().find(first_assign) ==	×
61	transition.assignments().end()) {	×
62	all_branches_same = false;	×
63	break;	×
64	}
65	if (!symbolic::eq(first_assignment,	×
66	transition.assignments().at(first_assign))) {	×
67	all_branches_same = false;	×
68	break;	×
69	}
70	}	×
71
72	if (!all_branches_same) {	×
73	continue;	×
74	}
75
76	child.second.assignments().insert({first_assign, first_assignment});	×
77	applied = true;	×
78	}
79	}	×
80	}	×
81
82	for (size_t i = 0; i < sequence_stmt->size(); i++) {	×
83	queue.push_back(&sequence_stmt->at(i).first);	×
84	}	×
85	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {	×
86	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
87	queue.push_back(&if_else_stmt->at(i).first);	×
88	}	×
89	} else if (auto loop_stmt = dynamic_cast<structured_control_flow::While*>(current)) {	×
90	queue.push_back(&loop_stmt->root());	×
91	} else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {	×
92	queue.push_back(&for_stmt->root());	×
93	} else if (auto kern_stmt = dynamic_cast<const structured_control_flow::Kernel*>(current)) {	×
94	queue.push_back(&kern_stmt->root());	×
NEW 95	} else if (auto map_stmt = dynamic_cast<const structured_control_flow::Map*>(current)) {	×
NEW 96	queue.push_back(&map_stmt->root());	×
UNCOV 97	}	×
98	}
99
100	return applied;	×
101	};	×
102
103	} // namespace passes
104	} // 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