27932125879

Committed 21 Jun 2026 08:39PM UTC coverage: 61.782% (+0.02%) from 61.763%

Build # 27932125879

Build Type

push

github

Committed by

web-flow

Commit Message

enables cleanup passes after device residency promotion (#799)

* adds dead transfer elimination after residency promotion and fixes bug in transfer minimization

* fixes non-SSA buffer naming in OffloadTransform

* propagate references before promotion

* fixes postdom analysis via boost

Coverage Stats

42 of 43 new or added lines in 3 files covered. (97.67%)

1 existing line in 1 file now uncovered.

37141 of 60116 relevant lines covered (61.78%)

1014.29 hits per line

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

83.68

/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_;

        // Model the loop-exit (condition false) as a fall-through from the header to a synthetic exit vertex. Without
        // it a loop that is the last node in its scope is an exitless cycle whose body can never reach the CFG
        // terminal, leaving every body node without a post-dominator.
        auto exit_v = boost::add_vertex(graph_);
        nodes_[exit_v] = nullptr;
        boost::add_edge(header_v, exit_v, graph_);

        return {header_v, exit_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_;

        // Model the loop-exit (condition false) as a fall-through from the header to a synthetic exit vertex. Without
        // it a loop that is the last node in its scope is an exitless cycle whose body can never reach the CFG
        // terminal, leaving every body node without a post-dominator.
        auto exit_v = boost::add_vertex(graph_);
        nodes_[exit_v] = nullptr;
        boost::add_edge(header_v, exit_v, graph_);

        return {header_v, exit_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) {
        auto node_it = nodes_.find(node);
        if (node_it == nodes_.end() || node_it->second == nullptr) {
            continue; // only key real control-flow nodes
        }
        auto* real_dom = resolve_real_ancestor(dom_tree, dom_node);
        if (real_dom != nullptr) {
            dom_tree_[node_it->second] = real_dom;
        }
    }

    auto pdom_tree = graph::post_dominator_tree(graph_);
    for (const auto& [node, pdom_node] : pdom_tree) {
        auto node_it = nodes_.find(node);
        if (node_it == nodes_.end() || node_it->second == nullptr) {
            continue; // only key real control-flow nodes
        }
        auto* real_pdom = resolve_real_ancestor(pdom_tree, pdom_node);
        if (real_pdom != nullptr) {
            pdom_tree_[node_it->second] = real_pdom;
        }
    }
};

structured_control_flow::ControlFlowNode* ControlFlowAnalysis::
    resolve_real_ancestor(const std::unordered_map<graph::Vertex, graph::Vertex>& tree, graph::Vertex start) const {
    // The boost (post)dominator tree contains synthetic vertices that carry no real control-flow node: IfElse merge
    // points (stored in nodes_ with a nullptr value) and the super-terminal added for post-dominance. A real node's
    // immediate (post)dominator may be one of these synthetics, which previously left the tree pointing at a nullptr
    // and silently truncated the dominates()/post_dominates() walk. Skip the synthetics and return the first real
    // ancestor instead so the relation stays transitively walkable.
    auto null_vertex = boost::graph_traits<graph::Graph>::null_vertex();
    graph::Vertex cur = start;
    std::unordered_set<graph::Vertex> seen;
    while (cur != null_vertex && seen.insert(cur).second) {
        auto it = nodes_.find(cur);
        if (it != nodes_.end() && it->second != nullptr) {
            return it->second;
        }
        auto next_it = tree.find(cur);
        if (next_it == tree.end() || next_it->second == cur) {
            break; // root maps to itself or has no parent
        }
        cur = next_it->second;
    }
    return nullptr;
};

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	// Model the loop-exit (condition false) as a fall-through from the header to a synthetic exit vertex. Without
95	// it a loop that is the last node in its scope is an exitless cycle whose body can never reach the CFG
96	// terminal, leaving every body node without a post-dominator.
97	auto exit_v = boost::add_vertex(graph_);	1✔
98	nodes_[exit_v] = nullptr;	1✔
99	boost::add_edge(header_v, exit_v, graph_);	1✔
100
101	return {header_v, exit_v};	1✔
102	} else if (auto structured_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&current)) {	21✔
103	auto header_v = boost::add_vertex(graph_);	3✔
104	nodes_[header_v] = &current;	3✔
105
106	auto previous_loop_ = last_loop_;	3✔
107	last_loop_ = header_v;	3✔
108
109	auto [body_start, body_end] = this->traverse(structured_loop->root());	3✔
110	if (body_start != boost::graph_traits<graph::Graph>::null_vertex()) {	3✔
111	boost::add_edge(header_v, body_start, graph_);	3✔
112	}	3✔
113	if (body_end != boost::graph_traits<graph::Graph>::null_vertex()) {	3✔
114	boost::add_edge(body_end, header_v, graph_);	3✔
115	}	3✔
116
117	last_loop_ = previous_loop_;	3✔
118
119	// Model the loop-exit (condition false) as a fall-through from the header to a synthetic exit vertex. Without
120	// it a loop that is the last node in its scope is an exitless cycle whose body can never reach the CFG
121	// terminal, leaving every body node without a post-dominator.
122	auto exit_v = boost::add_vertex(graph_);	3✔
123	nodes_[exit_v] = nullptr;	3✔
124	boost::add_edge(header_v, exit_v, graph_);	3✔
125
126	return {header_v, exit_v};	3✔
127	} else if (auto sequence_node = dynamic_cast<structured_control_flow::Sequence*>(&current)) {	18✔
128	graph::Vertex seq_start = boost::graph_traits<graph::Graph>::null_vertex();	18✔
129	graph::Vertex seq_end = boost::graph_traits<graph::Graph>::null_vertex();	18✔
130
131	for (size_t i = 0; i < sequence_node->size(); i++) {	73✔
132	auto& child = sequence_node->at(i).first;	55✔
133	auto [child_start, child_end] = this->traverse(child);	55✔
134	if (child_start != boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
135	if (seq_start == boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
136	seq_start = child_start;	18✔
137	}	18✔
138	if (seq_end != boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
139	boost::add_edge(seq_end, child_start, graph_);	37✔
140	}	37✔
141	}	55✔
142
143	seq_end = child_end;	55✔
144	if (seq_end == boost::graph_traits<graph::Graph>::null_vertex()) {	55✔
145	break;	×
146	}	×
147	}	55✔
148
149	return {seq_start, seq_end};	18✔
150	} else {	18✔
151	throw InvalidSDFGException("Unknown control flow node type encountered during control flow analysis.");	×
152	}	×
153	};	73✔
154
155	void ControlFlowAnalysis::run(analysis::AnalysisManager& analysis_manager) {	12✔
156	nodes_.clear();	12✔
157	graph_.clear();	12✔
158	dom_tree_.clear();	12✔
159	pdom_tree_.clear();	12✔
160
161	auto [root_start, root_end] = this->traverse(sdfg_.root());	12✔
162
163	graph::Vertex entry_vertex = root_start;	12✔
164	if (entry_vertex == boost::graph_traits<graph::Graph>::null_vertex()) {	12✔
165	return;	×
166	}	×
167
168	auto dom_tree = graph::dominator_tree(graph_, entry_vertex);	12✔
169	for (const auto& [node, dom_node] : dom_tree) {	60✔
170	auto node_it = nodes_.find(node);	60✔
171	if (node_it == nodes_.end() \|\| node_it->second == nullptr) {	60✔
172	continue; // only key real control-flow nodes	5✔
173	}	5✔
174	auto* real_dom = resolve_real_ancestor(dom_tree, dom_node);	55✔
175	if (real_dom != nullptr) {	55✔
176	dom_tree_[node_it->second] = real_dom;	43✔
177	}	43✔
178	}	55✔
179
180	auto pdom_tree = graph::post_dominator_tree(graph_);	12✔
181	for (const auto& [node, pdom_node] : pdom_tree) {	60✔
182	auto node_it = nodes_.find(node);	60✔
183	if (node_it == nodes_.end() \|\| node_it->second == nullptr) {	60✔
184	continue; // only key real control-flow nodes	5✔
185	}	5✔
186	auto* real_pdom = resolve_real_ancestor(pdom_tree, pdom_node);	55✔
187	if (real_pdom != nullptr) {	55✔
188	pdom_tree_[node_it->second] = real_pdom;	43✔
189	}	43✔
190	}	55✔
191	};	12✔
192
193	structured_control_flow::ControlFlowNode* ControlFlowAnalysis::
194	resolve_real_ancestor(const std::unordered_map<graph::Vertex, graph::Vertex>& tree, graph::Vertex start) const {	110✔
195	// The boost (post)dominator tree contains synthetic vertices that carry no real control-flow node: IfElse merge
196	// points (stored in nodes_ with a nullptr value) and the super-terminal added for post-dominance. A real node's
197	// immediate (post)dominator may be one of these synthetics, which previously left the tree pointing at a nullptr
198	// and silently truncated the dominates()/post_dominates() walk. Skip the synthetics and return the first real
199	// ancestor instead so the relation stays transitively walkable.
200	auto null_vertex = boost::graph_traits<graph::Graph>::null_vertex();	110✔
201	graph::Vertex cur = start;	110✔
202	std::unordered_set<graph::Vertex> seen;	110✔
203	while (cur != null_vertex && seen.insert(cur).second) {	122✔
204	auto it = nodes_.find(cur);	98✔
205	if (it != nodes_.end() && it->second != nullptr) {	98✔
206	return it->second;	86✔
207	}	86✔
208	auto next_it = tree.find(cur);	12✔
209	if (next_it == tree.end() \|\| next_it->second == cur) {	12✔
NEW 210	break; // root maps to itself or has no parent	×
UNCOV 211	}	×
212	cur = next_it->second;	12✔
213	}	12✔
214	return nullptr;	24✔
215	};	110✔
216
217	std::unordered_set<structured_control_flow::ControlFlowNode*> ControlFlowAnalysis::exits() const {	12✔
218	std::unordered_set<structured_control_flow::ControlFlowNode*> exit_nodes;	12✔
219
220	for (auto v : boost::make_iterator_range(boost::vertices(graph_))) {	54✔
221	if (boost::out_degree(v, graph_) == 0) {	54✔
222	assert(nodes_.find(v) != nodes_.end());	12✔
223	exit_nodes.insert(nodes_.at(v));	12✔
224	}	12✔
225	}	54✔
226
227	return exit_nodes;	12✔
228	}	12✔
229
230	const std::unordered_map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode>&
231	ControlFlowAnalysis::dom_tree() const {	×
232	return dom_tree_;	×
233	}	×
234
235	const std::unordered_map<structured_control_flow::ControlFlowNode, structured_control_flow::ControlFlowNode>&
236	ControlFlowAnalysis::pdom_tree() const {	×
237	return pdom_tree_;	×
238	}	×
239
240	bool ControlFlowAnalysis::
241	dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {	13✔
242	auto it = dom_tree_.find(&b);	13✔
243	while (it != dom_tree_.end()) {	28✔
244	if (it->second == &a) {	23✔
245	return true;	8✔
246	}	8✔
247	it = dom_tree_.find(it->second);	15✔
248	}	15✔
249	return false;	5✔
250	}	13✔
251
252	bool ControlFlowAnalysis::
253	post_dominates(structured_control_flow::ControlFlowNode& a, structured_control_flow::ControlFlowNode& b) const {	13✔
254	auto it = pdom_tree_.find(&b);	13✔
255	while (it != pdom_tree_.end()) {	26✔
256	if (it->second == &a) {	21✔
257	return true;	8✔
258	}	8✔
259	it = pdom_tree_.find(it->second);	13✔
260	}	13✔
261	return false;	5✔
262	}	13✔
263
264	} // namespace analysis
265	} // namespace sdfg

daisytuner / docc / 27932125879

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