27898444386

Committed 21 Jun 2026 08:18AM UTC coverage: 61.843% (-0.03%) from 61.87%

Build # 27898444386

Build Type

push

github

Committed by

web-flow

Commit Message

enable transfer elimination to work on simple host bounces (#790)

Coverage Stats

31 of 66 new or added lines in 5 files covered. (46.97%)

2 existing lines in 2 files now uncovered.

37038 of 59890 relevant lines covered (61.84%)

1018.08 hits per line

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

81.53

/sdfg/src/analysis/control_flow_analysis.cpp

#include "sdfg/analysis/control_flow_analysis.h"

#include <cassert>
#include <list>
#include <memory>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "sdfg/data_flow/memlet.h"
#include "sdfg/element.h"
#include "sdfg/graph/graph.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/structured_control_flow/map.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_sdfg.h"
#include "sdfg/symbolic/sets.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {
namespace analysis {
ControlFlowAnalysis::ControlFlowAnalysis(StructuredSDFG& sdfg)
    : Analysis(sdfg) {

      };

std::pair<graph::Vertex, graph::Vertex> ControlFlowAnalysis::traverse(structured_control_flow::ControlFlowNode& current
) {
    // Leaf nodes
    if (auto block_node = dynamic_cast<structured_control_flow::Block*>(&current)) {
        auto v = boost::add_vertex(graph_);
        nodes_[v] = &current;
        return {v, v};
    } else if (auto return_node = dynamic_cast<structured_control_flow::Return*>(&current)) {
        auto v = boost::add_vertex(graph_);
        nodes_[v] = &current;
        return {v, boost::graph_traits<graph::Graph>::null_vertex()};
    } else if (auto continue_node = dynamic_cast<structured_control_flow::Continue*>(&current)) {
        auto v = boost::add_vertex(graph_);
        nodes_[v] = &current;
        boost::add_edge(v, last_loop_, graph_);
        return {v, boost::graph_traits<graph::Graph>::null_vertex()};
    } else if (auto break_node = dynamic_cast<structured_control_flow::Break*>(&current)) {
        auto v = boost::add_vertex(graph_);
        nodes_[v] = &current;
        boost::add_edge(v, last_loop_, graph_);
        return {v, boost::graph_traits<graph::Graph>::null_vertex()};
    } else if (auto if_else_node = dynamic_cast<structured_control_flow::IfElse*>(&current)) {
        auto start_v = boost::add_vertex(graph_);
        nodes_[start_v] = &current;

        graph::Vertex end_v = boost::graph_traits<graph::Graph>::null_vertex();
        for (size_t i = 0; i < if_else_node->size(); i++) {
            auto [case_start, case_end] = this->traverse(if_else_node->at(i).first);
            if (case_start != boost::graph_traits<graph::Graph>::null_vertex()) {
                boost::add_edge(start_v, case_start, graph_);
            }
            if (case_end != boost::graph_traits<graph::Graph>::null_vertex()) {
                if (end_v == boost::graph_traits<graph::Graph>::null_vertex()) {
                    end_v = boost::add_vertex(graph_);
                    nodes_[end_v] = nullptr;
                }
                boost::add_edge(case_end, end_v, graph_);
            }
        }

        if (!if_else_node->is_complete()) {
            if (end_v == boost::graph_traits<graph::Graph>::null_vertex()) {
                end_v = boost::add_vertex(graph_);
                nodes_[end_v] = nullptr;
            }
            boost::add_edge(start_v, end_v, graph_);
        }

        return {start_v, end_v};
    } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&current)) {
        auto header_v = boost::add_vertex(graph_);
        nodes_[header_v] = &current;

        auto previous_loop_ = last_loop_;
        last_loop_ = header_v;

        auto [body_start, body_end] = this->traverse(while_loop->root());
        if (body_start != boost::graph_traits<graph::Graph>::null_vertex()) {
            boost::add_edge(header_v, body_start, graph_);
        }
        if (body_end != boost::graph_traits<graph::Graph>::null_vertex()) {
            boost::add_edge(body_end, header_v, graph_);
        }

        last_loop_ = previous_loop_;

        return {header_v, header_v};
    } else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&current)) {
        auto header_v = boost::add_vertex(graph_);
        nodes_[header_v] = &current;

        auto previous_loop_ = last_loop_;
        last_loop_ = header_v;

        auto [body_start, body_end] = this->traverse(structured_loop->root());
        if (body_start != boost::graph_traits<graph::Graph>::null_vertex()) {
            boost::add_edge(header_v, body_start, graph_);
        }
        if (body_end != boost::graph_traits<graph::Graph>::null_vertex()) {
            boost::add_edge(body_end, header_v, graph_);
        }

        last_loop_ = previous_loop_;

        return {header_v, header_v};
    } else if (auto sequence_node = dynamic_cast<structured_control_flow::Sequence*>(&current)) {
        graph::Vertex seq_start = boost::graph_traits<graph::Graph>::null_vertex();
        graph::Vertex seq_end = boost::graph_traits<graph::Graph>::null_vertex();

        for (size_t i = 0; i < sequence_node->size(); i++) {
            auto& child = sequence_node->at(i).first;
            auto [child_start, child_end] = this->traverse(child);
            if (child_start != boost::graph_traits<graph::Graph>::null_vertex()) {
                if (seq_start == boost::graph_traits<graph::Graph>::null_vertex()) {
                    seq_start = child_start;
                }
                if (seq_end != boost::graph_traits<graph::Graph>::null_vertex()) {
                    boost::add_edge(seq_end, child_start, graph_);
                }
            }

            seq_end = child_end;
            if (seq_end == boost::graph_traits<graph::Graph>::null_vertex()) {
                break;
            }
        }

        return {seq_start, seq_end};
    } else {
        throw InvalidSDFGException("Unknown control flow node type encountered during control flow analysis.");
    }
};

void ControlFlowAnalysis::run(analysis::AnalysisManager& analysis_manager) {
    nodes_.clear();
    graph_.clear();
    dom_tree_.clear();
    pdom_tree_.clear();

    auto [root_start, root_end] = this->traverse(sdfg_.root());

    graph::Vertex entry_vertex = root_start;
    if (entry_vertex == boost::graph_traits<graph::Graph>::null_vertex()) {
        return;
    }

    auto dom_tree = graph::dominator_tree(graph_, entry_vertex);
    for (const auto& [node, dom_node] : dom_tree) {
        if (nodes_.find(node) != nodes_.end() && nodes_.find(dom_node) != nodes_.end()) {
            dom_tree_[nodes_.at(node)] = nodes_.at(dom_node);
        }
    }

    auto pdom_tree = graph::post_dominator_tree(graph_);
    for (const auto& [node, pdom_node] : pdom_tree) {
        if (nodes_.find(node) != nodes_.end() && nodes_.find(pdom_node) != nodes_.end()) {
            pdom_tree_[nodes_.at(node)] = nodes_.at(pdom_node);
        }
    }
};

std::unordered_set<structured_control_flow::ControlFlowNode*> ControlFlowAnalysis::exits() const {
    std::unordered_set<structured_control_flow::ControlFlowNode*> exit_nodes;

    for (auto v : boost::make_iterator_range(boost::vertices(graph_))) {
        if (boost::out_degree(v, graph_) == 0) {
            assert(nodes_.find(v) != nodes_.end());
            exit_nodes.insert(nodes_.at(v));
        }
    }

    return exit_nodes;
}

const std::unordered_map<structured_control_flow::ControlFlowNode*, structured_control_flow::ControlFlowNode*>&
ControlFlowAnalysis::dom_tree() const {
    return dom_tree_;
}

const std::unordered_map<structured_control_flow::ControlFlowNode*, structured_control_flow::ControlFlowNode*>&
ControlFlowAnalysis::pdom_tree() const {
    return pdom_tree_;
}

bool ControlFlowAnalysis::
    dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {
    auto it = dom_tree_.find(&b);
    while (it != dom_tree_.end()) {
        if (it->second == &a) {
            return true;
        }
        it = dom_tree_.find(it->second);
    }
    return false;
}

bool ControlFlowAnalysis::
    post_dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {
    auto it = pdom_tree_.find(&b);
    while (it != pdom_tree_.end()) {
        if (it->second == &a) {
            return true;
        }
        it = pdom_tree_.find(it->second);
    }
    return false;
}

} // namespace analysis
} // namespace sdfg

1	#include "sdfg/analysis/control_flow_analysis.h"
2
3	#include <cassert>
4	#include <list>
5	#include <memory>
6	#include <string>
7	#include <unordered_map>
8	#include <unordered_set>
9	#include <vector>
10
11	#include "sdfg/data_flow/memlet.h"
12	#include "sdfg/element.h"
13	#include "sdfg/graph/graph.h"
14	#include "sdfg/structured_control_flow/for.h"
15	#include "sdfg/structured_control_flow/map.h"
16	#include "sdfg/structured_control_flow/sequence.h"
17	#include "sdfg/structured_sdfg.h"
18	#include "sdfg/symbolic/sets.h"
19	#include "sdfg/symbolic/symbolic.h"
20
21	namespace sdfg {
22	namespace analysis {
23	ControlFlowAnalysis::ControlFlowAnalysis(StructuredSDFG& sdfg)
24	: Analysis(sdfg) {	12✔
25
26	};	12✔
27
28	std::pair<graph::Vertex, graph::Vertex> ControlFlowAnalysis::traverse(structured_control_flow::ControlFlowNode& current
29	) {	73✔
30	// Leaf nodes
31	if (auto block_node = dynamic_cast<structured_control_flow::Block*>(&current)) {	73✔
32	auto v = boost::add_vertex(graph_);	50✔
33	nodes_[v] = &current;	50✔
34	return {v, v};	50✔
35	} else if (auto return_node = dynamic_cast<structured_control_flow::Return*>(&current)) {	50✔
36	auto v = boost::add_vertex(graph_);	×
37	nodes_[v] = &current;	×
38	return {v, boost::graph_traits<graph::Graph>::null_vertex()};	×
39	} else if (auto continue_node = dynamic_cast<structured_control_flow::Continue*>(&current)) {	23✔
40	auto v = boost::add_vertex(graph_);	×
41	nodes_[v] = &current;	×
42	boost::add_edge(v, last_loop_, graph_);	×
43	return {v, boost::graph_traits<graph::Graph>::null_vertex()};	×
44	} else if (auto break_node = dynamic_cast<structured_control_flow::Break*>(&current)) {	23✔
45	auto v = boost::add_vertex(graph_);	×
46	nodes_[v] = &current;	×
47	boost::add_edge(v, last_loop_, graph_);	×
48	return {v, boost::graph_traits<graph::Graph>::null_vertex()};	×
49	} else if (auto if_else_node = dynamic_cast<structured_control_flow::IfElse*>(&current)) {	23✔
50	auto start_v = boost::add_vertex(graph_);	1✔
51	nodes_[start_v] = &current;	1✔
52
53	graph::Vertex end_v = boost::graph_traits<graph::Graph>::null_vertex();	1✔
54	for (size_t i = 0; i < if_else_node->size(); i++) {	3✔
55	auto [case_start, case_end] = this->traverse(if_else_node->at(i).first);	2✔
56	if (case_start != boost::graph_traits<graph::Graph>::null_vertex()) {	2✔
57	boost::add_edge(start_v, case_start, graph_);	2✔
58	}	2✔
59	if (case_end != boost::graph_traits<graph::Graph>::null_vertex()) {	2✔
60	if (end_v == boost::graph_traits<graph::Graph>::null_vertex()) {	2✔
61	end_v = boost::add_vertex(graph_);	1✔
62	nodes_[end_v] = nullptr;	1✔
63	}	1✔
64	boost::add_edge(case_end, end_v, graph_);	2✔
65	}	2✔
66	}	2✔
67
68	if (!if_else_node->is_complete()) {	1✔
69	if (end_v == boost::graph_traits<graph::Graph>::null_vertex()) {	×
70	end_v = boost::add_vertex(graph_);	×
71	nodes_[end_v] = nullptr;	×
72	}	×
73	boost::add_edge(start_v, end_v, graph_);	×
74	}	×
75
76	return {start_v, end_v};	1✔
77	} else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&current)) {	22✔
78	auto header_v = boost::add_vertex(graph_);	1✔
79	nodes_[header_v] = &current;	1✔
80
81	auto previous_loop_ = last_loop_;	1✔
82	last_loop_ = header_v;	1✔
83
84	auto [body_start, body_end] = this->traverse(while_loop->root());	1✔
85	if (body_start != boost::graph_traits<graph::Graph>::null_vertex()) {	1✔
86	boost::add_edge(header_v, body_start, graph_);	1✔
87	}	1✔
88	if (body_end != boost::graph_traits<graph::Graph>::null_vertex()) {	1✔
89	boost::add_edge(body_end, header_v, graph_);	1✔
90	}	1✔
91
92	last_loop_ = previous_loop_;	1✔
93
94	return {header_v, header_v};	1✔
95	} else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&current)) {	21✔
96	auto header_v = boost::add_vertex(graph_);	3✔
97	nodes_[header_v] = &current;	3✔
98
99	auto previous_loop_ = last_loop_;	3✔
100	last_loop_ = header_v;	3✔
101
102	auto [body_start, body_end] = this->traverse(structured_loop->root());	3✔
103	if (body_start != boost::graph_traits<graph::Graph>::null_vertex()) {	3✔
104	boost::add_edge(header_v, body_start, graph_);	3✔
105	}	3✔
106	if (body_end != boost::graph_traits<graph::Graph>::null_vertex()) {	3✔
107	boost::add_edge(body_end, header_v, graph_);	3✔
108	}	3✔
109
110	last_loop_ = previous_loop_;	3✔
111
112	return {header_v, header_v};	3✔
113	} else if (auto sequence_node = dynamic_cast<structured_control_flow::Sequence*>(&current)) {	18✔
114	graph::Vertex seq_start = boost::graph_traits<graph::Graph>::null_vertex();	18✔
115	graph::Vertex seq_end = boost::graph_traits<graph::Graph>::null_vertex();	18✔
116
117	for (size_t i = 0; i < sequence_node->size(); i++) {	73✔
118	auto& child = sequence_node->at(i).first;	55✔
119	auto [child_start, child_end] = this->traverse(child);	55✔
120	if (child_start != boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
121	if (seq_start == boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
122	seq_start = child_start;	18✔
123	}	18✔
124	if (seq_end != boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
125	boost::add_edge(seq_end, child_start, graph_);	37✔
126	}	37✔
127	}	55✔
128
129	seq_end = child_end;	55✔
130	if (seq_end == boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
131	break;	×
132	}	×
133	}	55✔
134
135	return {seq_start, seq_end};	18✔
136	} else {	18✔
137	throw InvalidSDFGException("Unknown control flow node type encountered during control flow analysis.");	×
138	}	×
139	};	73✔
140
141	void ControlFlowAnalysis::run(analysis::AnalysisManager& analysis_manager) {	12✔
142	nodes_.clear();	12✔
143	graph_.clear();	12✔
144	dom_tree_.clear();	12✔
145	pdom_tree_.clear();	12✔
146
147	auto [root_start, root_end] = this->traverse(sdfg_.root());	12✔
148
149	graph::Vertex entry_vertex = root_start;	12✔
150	if (entry_vertex == boost::graph_traits<graph::Graph>::null_vertex()) {	12✔
NEW 151	return;	×
UNCOV 152	}	×
153
154	auto dom_tree = graph::dominator_tree(graph_, entry_vertex);	12✔
155	for (const auto& [node, dom_node] : dom_tree) {	56✔
156	if (nodes_.find(node) != nodes_.end() && nodes_.find(dom_node) != nodes_.end()) {	56✔
157	dom_tree_[nodes_.at(node)] = nodes_.at(dom_node);	44✔
158	}	44✔
159	}	56✔
160
161	auto pdom_tree = graph::post_dominator_tree(graph_);	12✔
162	for (const auto& [node, pdom_node] : pdom_tree) {	56✔
163	if (nodes_.find(node) != nodes_.end() && nodes_.find(pdom_node) != nodes_.end()) {	56✔
164	pdom_tree_[nodes_.at(node)] = nodes_.at(pdom_node);	44✔
165	}	44✔
166	}	56✔
167	};	12✔
168
169	std::unordered_set<structured_control_flow::ControlFlowNode*> ControlFlowAnalysis::exits() const {	12✔
170	std::unordered_set<structured_control_flow::ControlFlowNode*> exit_nodes;	12✔
171
172	for (auto v : boost::make_iterator_range(boost::vertices(graph_))) {	48✔
173	if (boost::out_degree(v, graph_) == 0) {	48✔
174	assert(nodes_.find(v) != nodes_.end());	12✔
175	exit_nodes.insert(nodes_.at(v));	12✔
176	}	12✔
177	}	48✔
178
179	return exit_nodes;	12✔
180	}	12✔
181
182	const std::unordered_map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode>&
183	ControlFlowAnalysis::dom_tree() const {	×
184	return dom_tree_;	×
185	}	×
186
187	const std::unordered_map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode>&
188	ControlFlowAnalysis::pdom_tree() const {	×
189	return pdom_tree_;	×
190	}	×
191
192	bool ControlFlowAnalysis::
193	dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {	13✔
194	auto it = dom_tree_.find(&b);	13✔
195	while (it != dom_tree_.end()) {	31✔
196	if (it->second == &a) {	26✔
197	return true;	8✔
198	}	8✔
199	it = dom_tree_.find(it->second);	18✔
200	}	18✔
201	return false;	5✔
202	}	13✔
203
204	bool ControlFlowAnalysis::
205	post_dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {	13✔
206	auto it = pdom_tree_.find(&b);	13✔
207	while (it != pdom_tree_.end()) {	31✔
208	if (it->second == &a) {	26✔
209	return true;	8✔
210	}	8✔
211	it = pdom_tree_.find(it->second);	18✔
212	}	18✔
213	return false;	5✔
214	}	13✔
215
216	} // namespace analysis
217	} // namespace sdfg

daisytuner / docc / 27898444386

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