18812703264

Committed 25 Oct 2025 01:57PM UTC coverage: 62.033% (+0.2%) from 61.823%

Build # 18812703264

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #304 from daisytuner/control-flow-analysis

adds control flow analysis

Run Details

125 of 148 new or added lines in 1 file covered. (84.46%)

9937 of 16019 relevant lines covered (62.03%)

102.78 hits per line

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

84.46

/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();

    this->traverse(sdfg_.root());

    graph::Vertex entry_vertex = boost::graph_traits<graph::Graph>::null_vertex();
    for (auto v : boost::make_iterator_range(boost::vertices(graph_))) {
        if (boost::in_degree(v, graph_) == 0) {
            assert(entry_vertex == boost::graph_traits<graph::Graph>::null_vertex());
            entry_vertex = v;
        }
    }

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

daisytuner / sdfglib / 18812703264

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