15238257521

Committed 25 May 2025 01:14PM UTC coverage: 60.342% (-0.1%) from 60.473%

Build # 15238257521

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #31 from daisytuner/exception-handling

Exception handling

Run Details

18 of 60 new or added lines in 17 files covered. (30.0%)

1 existing line in 1 file now uncovered.

8052 of 13344 relevant lines covered (60.34%)

102.27 hits per line

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

84.78

/src/passes/structured_control_flow/block_fusion.cpp

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

namespace sdfg {
namespace passes {

BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder,
                         analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {}

bool BlockFusion::can_be_applied(data_flow::DataFlowGraph& first_graph,
                                 symbolic::Assignments& first_assignments,
                                 data_flow::DataFlowGraph& second_graph,
                                 symbolic::Assignments& second_assignments) {
    // Criterion: no pointer ref fusions
    for (auto& edge : first_graph.edges()) {
        if (edge.src_conn() == "refs" || edge.dst_conn() == "refs") {
            return false;
        }
    }
    for (auto& edge : second_graph.edges()) {
        if (edge.src_conn() == "refs" || edge.dst_conn() == "refs") {
            return false;
        }
    }

    // Criterion: No conditional tasklets
    for (auto& tasklet : first_graph.tasklets()) {
        if (tasklet->is_conditional()) {
            return false;
        }
    }
    for (auto& tasklet : second_graph.tasklets()) {
        if (tasklet->is_conditional()) {
            return false;
        }
    }

    // Criterion: No data races cause by transition
    if (!first_assignments.empty()) {
        return false;
    }

    // Numerical stability: Unique order of nodes
    auto pdoms = first_graph.post_dominators();
    bool has_connector = false;
    for (auto& node : second_graph.sources()) {
        if (!dynamic_cast<const data_flow::AccessNode*>(node)) {
            return false;
        }
        auto access_node = static_cast<const data_flow::AccessNode*>(node);
        auto data = access_node->data();

        // Connects to first block
        if (pdoms.find(data) == pdoms.end()) {
            continue;
        }
        has_connector = true;
        // Is unique successor in first block
        if (first_graph.out_degree(*pdoms.at(data)) > 0) {
            return false;
        }
    }
    if (!has_connector) {
        return false;
    }

    return true;
};

void BlockFusion::apply(structured_control_flow::Block& first_block,
                        symbolic::Assignments& first_assignments,
                        structured_control_flow::Block& second_block,
                        symbolic::Assignments& second_assignments) {
    data_flow::DataFlowGraph& first_graph = first_block.dataflow();
    data_flow::DataFlowGraph& second_graph = second_block.dataflow();

    // Update symbols
    for (auto& entry : second_assignments) {
        first_assignments[entry.first] = entry.second;
    }

    // Collect nodes to connect to,
    // i.e., last access node for each container
    auto pdoms = first_graph.post_dominators();

    // Collect nodes which need to be connected,
    // i.e., sources of the second graph
    std::unordered_map<data_flow::DataFlowNode*, std::unordered_set<data_flow::DataFlowNode*>>
        connectors;
    for (auto& node : second_graph.sources()) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {
            if (pdoms.find(access_node->data()) != pdoms.end()) {
                connectors.insert({node, {pdoms[access_node->data()]}});
            }
        }
    }

    // Copy nodes from second to first
    std::unordered_map<data_flow::DataFlowNode*, data_flow::DataFlowNode*> node_mapping;
    for (auto& node : second_graph.nodes()) {
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&node)) {
            if (connectors.find(access_node) != connectors.end()) {
                if (connectors[access_node].size() != 1) {
                    throw InvalidSDFGException("BlockFusion: Expected exactly one connector");
                }
                // Connect by replacement
                node_mapping[access_node] = *connectors[access_node].begin();
            } else {
                // Add new
                node_mapping[access_node] = &builder_.add_access(first_block, access_node->data());
            }
        } else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {
            node_mapping[tasklet] = &builder_.add_tasklet(first_block, tasklet->code(),
                                                          tasklet->output(0), tasklet->inputs());
        }
    }

    // Connect new nodes according to edges of second graph
    for (auto& edge : second_graph.edges()) {
        auto& src_node = edge.src();
        auto& dst_node = edge.dst();

        builder_.add_memlet(first_block, *node_mapping[&src_node], edge.src_conn(),
                            *node_mapping[&dst_node], edge.dst_conn(), edge.subset());
    }
};

bool BlockFusion::accept(structured_control_flow::Sequence& parent,
                         structured_control_flow::Sequence& node) {
    bool applied = false;

    if (node.size() == 0) {
        return applied;
    }

    // Traverse node to find pairs of blocks
    size_t i = 0;
    while (i < (node.size() - 1)) {
        auto current_entry = node.at(i);
        if (dynamic_cast<structured_control_flow::Block*>(&current_entry.first) == nullptr) {
            i++;
            continue;
        }
        auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_entry.first);

        auto next_entry = node.at(i + 1);
        if (dynamic_cast<structured_control_flow::Block*>(&next_entry.first) == nullptr) {
            i++;
            continue;
        }
        auto next_block = dynamic_cast<structured_control_flow::Block*>(&next_entry.first);

        if (this->can_be_applied(current_block->dataflow(), current_entry.second.assignments(),
                                 next_block->dataflow(), next_entry.second.assignments())) {
            this->apply(*current_block, current_entry.second.assignments(), *next_block,
                        next_entry.second.assignments());
            builder_.remove_child(node, i + 1);
            applied = true;
        } else {
            i++;
        }
    }

    return applied;
};

}  // namespace passes
}  // namespace sdfg

1	#include "sdfg/passes/structured_control_flow/block_fusion.h"
2
3	namespace sdfg {
4	namespace passes {
5
6	BlockFusion::BlockFusion(builder::StructuredSDFGBuilder& builder,	2✔
7	analysis::AnalysisManager& analysis_manager)
8	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {}	2✔
9
10	bool BlockFusion::can_be_applied(data_flow::DataFlowGraph& first_graph,	2✔
11	symbolic::Assignments& first_assignments,
12	data_flow::DataFlowGraph& second_graph,
13	symbolic::Assignments& second_assignments) {
14	// Criterion: no pointer ref fusions
15	for (auto& edge : first_graph.edges()) {	6✔
16	if (edge.src_conn() == "refs" \|\| edge.dst_conn() == "refs") {	4✔
17	return false;	×
18	}
19	}
20	for (auto& edge : second_graph.edges()) {	6✔
21	if (edge.src_conn() == "refs" \|\| edge.dst_conn() == "refs") {	4✔
22	return false;	×
23	}
24	}
25
26	// Criterion: No conditional tasklets
27	for (auto& tasklet : first_graph.tasklets()) {	4✔
28	if (tasklet->is_conditional()) {	2✔
29	return false;	×
30	}
31	}
32	for (auto& tasklet : second_graph.tasklets()) {	4✔
33	if (tasklet->is_conditional()) {	2✔
34	return false;	×
35	}
36	}
37
38	// Criterion: No data races cause by transition
39	if (!first_assignments.empty()) {	2✔
40	return false;	×
41	}
42
43	// Numerical stability: Unique order of nodes
44	auto pdoms = first_graph.post_dominators();	2✔
45	bool has_connector = false;	2✔
46	for (auto& node : second_graph.sources()) {	4✔
47	if (!dynamic_cast<const data_flow::AccessNode*>(node)) {	2✔
48	return false;	×
49	}
50	auto access_node = static_cast<const data_flow::AccessNode*>(node);	2✔
51	auto data = access_node->data();	2✔
52
53	// Connects to first block
54	if (pdoms.find(data) == pdoms.end()) {	2✔
55	continue;	1✔
56	}
57	has_connector = true;	1✔
58	// Is unique successor in first block
59	if (first_graph.out_degree(*pdoms.at(data)) > 0) {	1✔
60	return false;	×
61	}
62	}	2✔
63	if (!has_connector) {	2✔
64	return false;	1✔
65	}
66
67	return true;	1✔
68	};	2✔
69
70	void BlockFusion::apply(structured_control_flow::Block& first_block,	1✔
71	symbolic::Assignments& first_assignments,
72	structured_control_flow::Block& second_block,
73	symbolic::Assignments& second_assignments) {
74	data_flow::DataFlowGraph& first_graph = first_block.dataflow();	1✔
75	data_flow::DataFlowGraph& second_graph = second_block.dataflow();	1✔
76
77	// Update symbols
78	for (auto& entry : second_assignments) {	1✔
79	first_assignments[entry.first] = entry.second;	×
80	}
81
82	// Collect nodes to connect to,
83	// i.e., last access node for each container
84	auto pdoms = first_graph.post_dominators();	1✔
85
86	// Collect nodes which need to be connected,
87	// i.e., sources of the second graph
88	std::unordered_map<data_flow::DataFlowNode, std::unordered_set<data_flow::DataFlowNode>>
89	connectors;	1✔
90	for (auto& node : second_graph.sources()) {	2✔
91	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {	1✔
92	if (pdoms.find(access_node->data()) != pdoms.end()) {	1✔
93	connectors.insert({node, {pdoms[access_node->data()]}});	1✔
94	}	1✔
95	}	1✔
96	}
97
98	// Copy nodes from second to first
99	std::unordered_map<data_flow::DataFlowNode, data_flow::DataFlowNode> node_mapping;	1✔
100	for (auto& node : second_graph.nodes()) {	4✔
101	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&node)) {	3✔
102	if (connectors.find(access_node) != connectors.end()) {	2✔
103	if (connectors[access_node].size() != 1) {	1✔
NEW 104	throw InvalidSDFGException("BlockFusion: Expected exactly one connector");	×
105	}
106	// Connect by replacement
107	node_mapping[access_node] = *connectors[access_node].begin();	1✔
108	} else {	1✔
109	// Add new
110	node_mapping[access_node] = &builder_.add_access(first_block, access_node->data());	1✔
111	}
112	} else if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&node)) {	3✔
113	node_mapping[tasklet] = &builder_.add_tasklet(first_block, tasklet->code(),	2✔
114	tasklet->output(0), tasklet->inputs());	1✔
115	}	1✔
116	}
117
118	// Connect new nodes according to edges of second graph
119	for (auto& edge : second_graph.edges()) {	3✔
120	auto& src_node = edge.src();	2✔
121	auto& dst_node = edge.dst();	2✔
122
123	builder_.add_memlet(first_block, *node_mapping[&src_node], edge.src_conn(),	4✔
124	*node_mapping[&dst_node], edge.dst_conn(), edge.subset());	2✔
125	}
126	};	1✔
127
128	bool BlockFusion::accept(structured_control_flow::Sequence& parent,	2✔
129	structured_control_flow::Sequence& node) {
130	bool applied = false;	2✔
131
132	if (node.size() == 0) {	2✔
133	return applied;	×
134	}
135
136	// Traverse node to find pairs of blocks
137	size_t i = 0;	2✔
138	while (i < (node.size() - 1)) {	4✔
139	auto current_entry = node.at(i);	2✔
140	if (dynamic_cast<structured_control_flow::Block*>(&current_entry.first) == nullptr) {	2✔
141	i++;	×
142	continue;	×
143	}
144	auto current_block = dynamic_cast<structured_control_flow::Block*>(&current_entry.first);	2✔
145
146	auto next_entry = node.at(i + 1);	2✔
147	if (dynamic_cast<structured_control_flow::Block*>(&next_entry.first) == nullptr) {	2✔
148	i++;	×
149	continue;	×
150	}
151	auto next_block = dynamic_cast<structured_control_flow::Block*>(&next_entry.first);	2✔
152
153	if (this->can_be_applied(current_block->dataflow(), current_entry.second.assignments(),	4✔
154	next_block->dataflow(), next_entry.second.assignments())) {	2✔
155	this->apply(current_block, current_entry.second.assignments(), next_block,	2✔
156	next_entry.second.assignments());	1✔
157	builder_.remove_child(node, i + 1);	1✔
158	applied = true;	1✔
159	} else {	1✔
160	i++;	1✔
161	}
162	}
163
164	return applied;	2✔
165	};	2✔
166
167	} // namespace passes
168	} // namespace sdfg

daisytuner / sdfglib / 15238257521

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