20192137438

Committed 13 Dec 2025 12:37PM UTC coverage: 40.251% (+0.07%) from 40.179%

Build # 20192137438

Build Type

Pull #391

github

Committed by

web-flow

Commit Message

Merge 216088a35 into 5583a0335

Pull Request Pull Request #391: Improvements for unstructured control flow conversion

Run Details

13648 of 43878 branches covered (31.1%)

Branch coverage included in aggregate %.

129 of 182 new or added lines in 2 files covered. (70.88%)

1 existing line in 1 file now uncovered.

11664 of 19008 relevant lines covered (61.36%)

94.79 hits per line

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

46.72

/src/sdfg.cpp

#include "sdfg/sdfg.h"

#include "sdfg/codegen/language_extensions/c_language_extension.h"
#include "sdfg/element.h"
#include "sdfg/symbolic/symbolic.h"

namespace sdfg {

SDFG::SDFG(const std::string& name, FunctionType type, const types::IType& return_type)
    : Function(name, type, return_type), start_state_(nullptr) {};

SDFG::SDFG(const std::string& name, FunctionType type) : SDFG(name, type, types::Scalar(types::PrimitiveType::Void)) {};

void SDFG::validate() const {
    // Call parent validate
    Function::validate();

    // Validate states and edges
    for (auto& state : this->states()) {
        state.validate(*this);
    }
    for (auto& edge : this->edges()) {
        edge.validate(*this);
    }

    for (auto& term : this->terminal_states()) {
        if (!dynamic_cast<const control_flow::ReturnState*>(&term)) {
            throw InvalidSDFGException("Terminal state is not a valid State");
        }
    }
};

size_t SDFG::in_degree(const control_flow::State& state) const {
    return boost::in_degree(state.vertex(), this->graph_);
};

size_t SDFG::out_degree(const control_flow::State& state) const {
    return boost::out_degree(state.vertex(), this->graph_);
};

bool SDFG::is_adjacent(const control_flow::State& src, const control_flow::State& dst) const {
    return boost::edge(src.vertex(), dst.vertex(), this->graph_).second;
};

const control_flow::InterstateEdge& SDFG::edge(const control_flow::State& src, const control_flow::State& dst) const {
    auto e = boost::edge(src.vertex(), dst.vertex(), this->graph_);
    if (!e.second) {
        throw InvalidSDFGException("Edge does not exist");
    }
    return *this->edges_.at(e.first);
};

const control_flow::State& SDFG::start_state() const {
    if (this->start_state_ == nullptr) {
        throw InvalidSDFGException("Start state not set");
    }
    return *this->start_state_;
};

std::unordered_map<const control_flow::State*, const control_flow::State*> SDFG::dominator_tree() const {
    auto dom_tree_ = graph::dominator_tree(this->graph_, this->start_state_->vertex());

    std::unordered_map<const control_flow::State*, const control_flow::State*> dom_tree;
    for (auto& entry : dom_tree_) {
        if (entry.first == boost::graph_traits<graph::Graph>::null_vertex() ||
            this->states_.find(entry.first) == this->states_.end()) {
            // This is the synthetic super-root, skip it
            continue;
        }
        control_flow::State* first = this->states_.at(entry.first).get();
        control_flow::State* second = nullptr;
        if (entry.second != boost::graph_traits<graph::Graph>::null_vertex()) {
            second = this->states_.at(entry.second).get();
        }
        dom_tree.insert({first, second});
    }

    return dom_tree;
};

std::unordered_map<const control_flow::State*, const control_flow::State*> SDFG::post_dominator_tree() {
    auto pdom_tree_ = graph::post_dominator_tree(this->graph_);

    std::unordered_map<const control_flow::State*, const control_flow::State*> pdom_tree;
    for (auto& entry : pdom_tree_) {
        if (this->states_.find(entry.first) == this->states_.end()) {
            // This is the synthetic super-terminal, skip it
            continue;
        }

        control_flow::State* first = this->states_.at(entry.first).get();
        control_flow::State* second = nullptr;
        if (entry.second != boost::graph_traits<graph::Graph>::null_vertex() &&
            this->states_.find(entry.second) != this->states_.end()) {
            second = this->states_.at(entry.second).get();
        }
        pdom_tree.insert({first, second});
    }

    return pdom_tree;
};

std::list<const control_flow::InterstateEdge*> SDFG::back_edges() const {
    std::list<const control_flow::InterstateEdge*> bedges;
    for (const auto& edge : graph::back_edges(this->graph_, this->start_state_->vertex())) {
        bedges.push_back(this->edges_.find(edge)->second.get());
    }

    return bedges;
};

std::list<std::list<const control_flow::InterstateEdge*>> SDFG::
    all_simple_paths(const control_flow::State& src, const control_flow::State& dst) const {
    std::list<std::list<const control_flow::InterstateEdge*>> all_paths;

    std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());
    for (auto& path_raw : all_paths_raw) {
        std::list<const control_flow::InterstateEdge*> path;
        for (auto& edge : path_raw) {
            path.push_back(this->edges_.find(edge)->second.get());
        }
        all_paths.push_back(path);
    }

    return all_paths;
};

void SDFG::as_dot(std::ostream& out) const {
    out << "digraph SDFG {\n";

    // States as nodes
    for (auto& state : this->states()) {
        out << "  S" << state.element_id() << " [label=\""
            << "State " << state.element_id() << "\"];\n";
    }

    // Edges
    for (auto& edge : this->edges()) {
        out << "  S" << edge.src().element_id() << " -> S" << edge.dst().element_id();
        out << " [label=\"";
        // Condition
        out << edge.condition()->__str__() << ",";
        // Assignments
        if (!edge.assignments().empty()) {
            out << "\\n{";
            bool first = true;
            for (auto& [var, expr] : edge.assignments()) {
                if (!first) {
                    out << "; ";
                }
                out << var->get_name() << " = " << expr->__str__();
                ;
                first = false;
            }
            out << "}";
        }
        out << "\"];\n";
    }

    out << "}\n";
};

} // namespace sdfg

1	#include "sdfg/sdfg.h"
2
3	#include "sdfg/codegen/language_extensions/c_language_extension.h"
4	#include "sdfg/element.h"
5	#include "sdfg/symbolic/symbolic.h"
6
7	namespace sdfg {
8
9	SDFG::SDFG(const std::string& name, FunctionType type, const types::IType& return_type)	1,036!
10	: Function(name, type, return_type), start_state_(nullptr) {};	1,036!
11
12	SDFG::SDFG(const std::string& name, FunctionType type) : SDFG(name, type, types::Scalar(types::PrimitiveType::Void)) {};	1,036!
13
14	void SDFG::validate() const {	×
15	// Call parent validate
16	Function::validate();	×
17
18	// Validate states and edges
19	for (auto& state : this->states()) {	×
20	state.validate(*this);	×
21	}
22	for (auto& edge : this->edges()) {	×
23	edge.validate(*this);	×
24	}
25
26	for (auto& term : this->terminal_states()) {	×
27	if (!dynamic_cast<const control_flow::ReturnState*>(&term)) {	×
28	throw InvalidSDFGException("Terminal state is not a valid State");	×
29	}
30	}
31	};	×
32
33	size_t SDFG::in_degree(const control_flow::State& state) const {	15✔
34	return boost::in_degree(state.vertex(), this->graph_);	15✔
35	};
36
37	size_t SDFG::out_degree(const control_flow::State& state) const {	106✔
38	return boost::out_degree(state.vertex(), this->graph_);	106✔
39	};
40
41	bool SDFG::is_adjacent(const control_flow::State& src, const control_flow::State& dst) const {	6✔
42	return boost::edge(src.vertex(), dst.vertex(), this->graph_).second;	6✔
43	};
44
45	const control_flow::InterstateEdge& SDFG::edge(const control_flow::State& src, const control_flow::State& dst) const {	4✔
46	auto e = boost::edge(src.vertex(), dst.vertex(), this->graph_);	4✔
47	if (!e.second) {	4!
48	throw InvalidSDFGException("Edge does not exist");	×
49	}
50	return *this->edges_.at(e.first);	4✔
51	};	×
52
53	const control_flow::State& SDFG::start_state() const {	18✔
54	if (this->start_state_ == nullptr) {	18!
55	throw InvalidSDFGException("Start state not set");	×
56	}
57	return *this->start_state_;	18✔
58	};	×
59
60	std::unordered_map<const control_flow::State, const control_flow::State> SDFG::dominator_tree() const {	14✔
61	auto dom_tree_ = graph::dominator_tree(this->graph_, this->start_state_->vertex());	14✔
62
63	std::unordered_map<const control_flow::State, const control_flow::State> dom_tree;	14✔
64	for (auto& entry : dom_tree_) {	105✔
65	if (entry.first == boost::graph_traits<graph::Graph>::null_vertex() \|\|	182!
66	this->states_.find(entry.first) == this->states_.end()) {	91!
67	// This is the synthetic super-root, skip it
NEW 68	continue;	×
69	}
70	control_flow::State* first = this->states_.at(entry.first).get();	91!
71	control_flow::State* second = nullptr;	91✔
72	if (entry.second != boost::graph_traits<graph::Graph>::null_vertex()) {	91!
73	second = this->states_.at(entry.second).get();	77!
74	}	77✔
75	dom_tree.insert({first, second});	91!
76	}
77
78	return dom_tree;	14✔
79	};	14!
80
81	std::unordered_map<const control_flow::State, const control_flow::State> SDFG::post_dominator_tree() {	17✔
82	auto pdom_tree_ = graph::post_dominator_tree(this->graph_);	17✔
83
84	std::unordered_map<const control_flow::State, const control_flow::State> pdom_tree;	17✔
85	for (auto& entry : pdom_tree_) {	112✔
86	if (this->states_.find(entry.first) == this->states_.end()) {	95!
87	// This is the synthetic super-terminal, skip it
88	continue;	1✔
89	}
90
91	control_flow::State* first = this->states_.at(entry.first).get();	94!
92	control_flow::State* second = nullptr;	94✔
93	if (entry.second != boost::graph_traits<graph::Graph>::null_vertex() &&	172!
94	this->states_.find(entry.second) != this->states_.end()) {	78!
95	second = this->states_.at(entry.second).get();	75!
96	}	75✔
97	pdom_tree.insert({first, second});	94!
98	}
99
100	return pdom_tree;	17✔
101	};	17!
102
103	std::list<const control_flow::InterstateEdge*> SDFG::back_edges() const {	16✔
104	std::list<const control_flow::InterstateEdge*> bedges;	16✔
105	for (const auto& edge : graph::back_edges(this->graph_, this->start_state_->vertex())) {	29!
106	bedges.push_back(this->edges_.find(edge)->second.get());	13!
107	}
108
109	return bedges;	16✔
110	};	16!
111
112	std::list<std::list<const control_flow::InterstateEdge*>> SDFG::
113	all_simple_paths(const control_flow::State& src, const control_flow::State& dst) const {	1✔
114	std::list<std::list<const control_flow::InterstateEdge*>> all_paths;	1✔
115
116	std::list<std::list<graph::Edge>> all_paths_raw = graph::all_simple_paths(this->graph_, src.vertex(), dst.vertex());	1!
117	for (auto& path_raw : all_paths_raw) {	3✔
118	std::list<const control_flow::InterstateEdge*> path;	2✔
119	for (auto& edge : path_raw) {	8✔
120	path.push_back(this->edges_.find(edge)->second.get());	6!
121	}
122	all_paths.push_back(path);	2!
123	}	2✔
124
125	return all_paths;	1✔
126	};	1!
127
NEW 128	void SDFG::as_dot(std::ostream& out) const {	×
NEW 129	out << "digraph SDFG {\n";	×
130
131	// States as nodes
NEW 132	for (auto& state : this->states()) {	×
NEW 133	out << " S" << state.element_id() << " [label=\""	×
NEW 134	<< "State " << state.element_id() << "\"];\n";	×
135	}
136
137	// Edges
NEW 138	for (auto& edge : this->edges()) {	×
NEW 139	out << " S" << edge.src().element_id() << " -> S" << edge.dst().element_id();	×
NEW 140	out << " [label=\"";	×
141	// Condition
NEW 142	out << edge.condition()->__str__() << ",";	×
143	// Assignments
NEW 144	if (!edge.assignments().empty()) {	×
NEW 145	out << "\\n{";	×
NEW 146	bool first = true;	×
NEW 147	for (auto& [var, expr] : edge.assignments()) {	×
NEW 148	if (!first) {	×
NEW 149	out << "; ";	×
NEW 150	}	×
NEW 151	out << var->get_name() << " = " << expr->__str__();	×
152	;
NEW 153	first = false;	×
154	}
NEW 155	out << "}";	×
NEW 156	}	×
NEW 157	out << "\"];\n";	×
158	}
159
NEW 160	out << "}\n";	×
NEW 161	};	×
162
163	} // namespace sdfg

daisytuner / sdfglib / 20192137438

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