20141104835

Committed 11 Dec 2025 05:03PM UTC coverage: 40.351% (-0.03%) from 40.379%

Build # 20141104835

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #387 from daisytuner/cleanup

Minor improvements in symbolic analysis

Run Details

13653 of 43801 branches covered (31.17%)

Branch coverage included in aggregate %.

10 of 17 new or added lines in 4 files covered. (58.82%)

6 existing lines in 4 files now uncovered.

11688 of 19000 relevant lines covered (61.52%)

94.14 hits per line

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

44.2

/src/passes/dataflow/constant_propagation.cpp

#include "sdfg/passes/dataflow/constant_propagation.h"

#include "sdfg/analysis/data_dependency_analysis.h"
#include "sdfg/analysis/dominance_analysis.h"
#include "sdfg/analysis/users.h"

namespace sdfg {
namespace passes {

ConstantPropagation::ConstantPropagation() : Pass() {};

std::string ConstantPropagation::name() { return "ConstantPropagation"; };

std::unordered_set<analysis::User*>
inputs(const std::string& container, data_flow::AccessNode* access_node, analysis::Users& users) {
    std::unordered_set<analysis::User*> inputs;

    auto& graph = access_node->get_parent();
    if (graph.in_degree(*access_node) != 1) {
        return {};
    }
    auto& iedge = *graph.in_edges(*access_node).begin();

    auto& src = iedge.src();
    if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&src)) {
        for (auto& iedge : graph.in_edges(*tasklet)) {
            auto& src_node = static_cast<data_flow::AccessNode&>(iedge.src());
            if (dynamic_cast<data_flow::ConstantNode*>(&src_node) != nullptr) {
                continue;
            }

            inputs.insert(users.get_user(src_node.data(), &src_node, analysis::Use::READ));
        }
    } else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&src)) {
        if (iedge.type() == data_flow::MemletType::Dereference_Src) {
            inputs.insert(users.get_user(access_node->data(), access_node, analysis::Use::READ));
        } else if (iedge.type() == data_flow::MemletType::Reference) {
            inputs.insert(users.get_user(access_node->data(), access_node, analysis::Use::VIEW));
        }
    }

    return inputs;
}

std::unordered_set<analysis::User*>
inputs(const std::string& container, structured_control_flow::Transition* transition, analysis::Users& users) {
    std::unordered_set<analysis::User*> inputs;
    auto& assign = transition->assignments().at(symbolic::symbol(container));
    for (auto& sym : symbolic::atoms(assign)) {
        if (symbolic::eq(sym, symbolic::__nullptr__())) {
            continue;
        }
        inputs.insert(users.get_user(sym->get_name(), transition, analysis::Use::READ));
    }
    return inputs;
}

std::unordered_set<analysis::User*> inputs(analysis::User& user, analysis::Users& users) {
    if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user.element())) {
        return inputs(user.container(), access_node, users);
    } else if (auto transition = dynamic_cast<structured_control_flow::Transition*>(user.element())) {
        return inputs(user.container(), transition, users);
    } else {
        return {};
    }
}

bool ConstantPropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    bool applied = false;

    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();
    auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();

    // We seek to find two identical definitions of the same container
    for (auto& name : sdfg.containers()) {
        std::unordered_set<analysis::User*> defines;
        if (users.writes(name).size() == 2 && users.moves(name).size() == 0) {
            for (auto& write : users.writes(name)) {
                defines.insert(write);
            }
        } else if (users.moves(name).size() == 2 && users.writes(name).size() == 0) {
            for (auto& move : users.moves(name)) {
                defines.insert(move);
            }
        } else {
            continue;
        }
        auto define1 = *defines.begin();
        auto define2 = *(++defines.begin());

        // Criterion: One dominates the other
        if (!dominance_analysis.dominates(*define1, *define2)) {
            std::swap(define1, define2);
        }
        if (!dominance_analysis.dominates(*define1, *define2)) {
            continue;
        }

        // Criterion: Prove identical subsets of definitions
        auto subsets1 = define1->subsets();
        auto subsets2 = define2->subsets();
        if (subsets1.size() != 1 || subsets2.size() != 1) {
            continue;
        }
        if (subsets1.begin()->size() != subsets2.begin()->size()) {
            continue;
        }
        bool identical_subsets = true;
        for (size_t i = 0; i < subsets1.begin()->size(); i++) {
            auto dim1 = subsets1.begin()->at(i);
            auto dim2 = subsets2.begin()->at(i);
            if (!symbolic::eq(dim1, dim2)) {
                identical_subsets = false;
                break;
            }
            std::unordered_set<std::string> symbols;
            for (auto& sym : symbolic::atoms(dim1)) {
                symbols.insert(sym->get_name());
            }
            for (auto& user : users.all_uses_between(*define1, *define2)) {
                if (user->use() == analysis::Use::READ) {
                    continue;
                }
                if (symbols.find(user->container()) != symbols.end()) {
                    identical_subsets = false;
                    break;
                }
            }
        }
        if (!identical_subsets) {
            continue;
        }

        // Criterion: Provide identical rhs/inputs of definitions
        auto inputs1 = inputs(*define1, users);
        if (inputs1.empty()) {
            continue;
        }
        auto inputs2 = inputs(*define2, users);
        if (inputs2.empty()) {
            continue;
        }
        if (inputs1.size() != inputs2.size()) {
            continue;
        }

        bool identical_inputs = true;
        for (auto& input : inputs1) {
            // Recursion
            if (input->container() == name) {
                identical_inputs = false;
                break;
            }

            // If input is written, it must happen before define1
            for (auto& write_user : users.writes(input->container())) {
                if (!dominance_analysis.dominates(*write_user, *define1)) {
                    identical_inputs = false;
                    break;
                }
            }

            // If input is moved, it must happen before define1
            for (auto& move_user : users.moves(input->container())) {
                if (!dominance_analysis.dominates(*move_user, *define1)) {
                    identical_inputs = false;
                    break;
                }
            }

            // If input has views, it must be the definitions
            for (auto& view : users.views(input->container())) {
                auto& viewed_node = dynamic_cast<data_flow::AccessNode&>(*view->element());
                auto& graph = viewed_node.get_parent();
                if (graph.out_degree(viewed_node) != 1) {
                    continue;
                }
                auto& viewing_node = (*graph.out_edges(viewed_node).begin()).dst();
                if (&viewing_node != define1->element() && &viewing_node != define2->element()) {
                    identical_inputs = false;
                }
            }
            if (!identical_inputs) {
                break;
            }

            // Find identical input in inputs2
            analysis::User* input2 = nullptr;
            for (auto& inp : inputs2) {
                if (input->container() == inp->container()) {
                    input2 = inp;
                    break;
                }
            }
            if (input2 == nullptr) {
                identical_inputs = false;
                break;
            }

            // same subsets
            if (input->subsets().size() != 1 || input2->subsets().size() != 1) {
                identical_inputs = false;
                break;
            }

            auto subset1 = *input->subsets().begin();
            auto subset2 = *input2->subsets().begin();
            if (subset1.size() != subset2.size()) {
                identical_inputs = false;
                break;
            }
            for (size_t i = 0; i < subset1.size(); i++) {
                auto dim1 = subset1[i];
                auto dim2 = subset2[i];
                if (!symbolic::eq(dim1, dim2)) {
                    identical_inputs = false;
                    break;
                }
                std::unordered_set<std::string> symbols;
                for (auto& sym : symbolic::atoms(dim1)) {
                    symbols.insert(sym->get_name());
                }
                for (auto& user : users.all_uses_between(*define1, *define2)) {
                    if (user->use() == analysis::Use::READ) {
                        continue;
                    }
                    if (symbols.find(user->container()) != symbols.end()) {
                        identical_inputs = false;
                        break;
                    }
                }
            }
        }
        if (!identical_inputs) {
            continue;
        }

        // Eliminate the dominated definition
        auto write = define2->element();
        if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write)) {
            transition->assignments().erase(symbolic::symbol(name));
            applied = true;
        } else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write)) {
            auto& graph = access_node->get_parent();
            auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());
            builder.clear_node(block, *access_node);
            applied = true;
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/constant_propagation.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4	#include "sdfg/analysis/dominance_analysis.h"
5	#include "sdfg/analysis/users.h"
6
7	namespace sdfg {
8	namespace passes {
9
10	ConstantPropagation::ConstantPropagation() : Pass() {};	7✔
11
12	std::string ConstantPropagation::name() { return "ConstantPropagation"; };	×
13
14	std::unordered_set<analysis::User*>
15	inputs(const std::string& container, data_flow::AccessNode* access_node, analysis::Users& users) {	4✔
16	std::unordered_set<analysis::User*> inputs;	4✔
17
18	auto& graph = access_node->get_parent();	4!
19	if (graph.in_degree(*access_node) != 1) {	4!
20	return {};	×
21	}
22	auto& iedge = graph.in_edges(access_node).begin();	4!
23
24	auto& src = iedge.src();	4!
25	if (auto tasklet = dynamic_cast<data_flow::Tasklet*>(&src)) {	4!
26	for (auto& iedge : graph.in_edges(*tasklet)) {	8!
27	auto& src_node = static_cast<data_flow::AccessNode&>(iedge.src());	4!
28	if (dynamic_cast<data_flow::ConstantNode*>(&src_node) != nullptr) {	4!
29	continue;	×
30	}
31
32	inputs.insert(users.get_user(src_node.data(), &src_node, analysis::Use::READ));	4!
33	}
34	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(&src)) {	4!
35	if (iedge.type() == data_flow::MemletType::Dereference_Src) {	×
36	inputs.insert(users.get_user(access_node->data(), access_node, analysis::Use::READ));	×
37	} else if (iedge.type() == data_flow::MemletType::Reference) {	×
38	inputs.insert(users.get_user(access_node->data(), access_node, analysis::Use::VIEW));	×
39	}	×
40	}	×
41
42	return inputs;	4✔
43	}	4✔
44
45	std::unordered_set<analysis::User*>
46	inputs(const std::string& container, structured_control_flow::Transition* transition, analysis::Users& users) {	8✔
47	std::unordered_set<analysis::User*> inputs;	8✔
48	auto& assign = transition->assignments().at(symbolic::symbol(container));	8!
49	for (auto& sym : symbolic::atoms(assign)) {	16!
50	if (symbolic::eq(sym, symbolic::__nullptr__())) {	8!
51	continue;	×
52	}
53	inputs.insert(users.get_user(sym->get_name(), transition, analysis::Use::READ));	8!
54	}
55	return inputs;	8✔
56	}	8!
57
58	std::unordered_set<analysis::User*> inputs(analysis::User& user, analysis::Users& users) {	12✔
59	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user.element())) {	12!
60	return inputs(user.container(), access_node, users);	4✔
61	} else if (auto transition = dynamic_cast<structured_control_flow::Transition*>(user.element())) {	8!
62	return inputs(user.container(), transition, users);	8✔
63	} else {
64	return {};	×
65	}
66	}	12✔
67
68	bool ConstantPropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	6✔
69	bool applied = false;	6✔
70
71	auto& sdfg = builder.subject();	6✔
72	auto& users = analysis_manager.get<analysis::Users>();	6✔
73	auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();	6✔
74	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	6✔
75
76	// We seek to find two identical definitions of the same container
77	for (auto& name : sdfg.containers()) {	18✔
78	std::unordered_set<analysis::User*> defines;	12✔
79	if (users.writes(name).size() == 2 && users.moves(name).size() == 0) {	12!
80	for (auto& write : users.writes(name)) {	18!
81	defines.insert(write);	12!
82	}
83	} else if (users.moves(name).size() == 2 && users.writes(name).size() == 0) {	12!
84	for (auto& move : users.moves(name)) {	×
85	defines.insert(move);	×
86	}
87	} else {	×
88	continue;	6✔
89	}
90	auto define1 = *defines.begin();	6✔
91	auto define2 = *(++defines.begin());	6✔
92
93	// Criterion: One dominates the other
94	if (!dominance_analysis.dominates(define1, define2)) {	6!
UNCOV 95	std::swap(define1, define2);	×
UNCOV 96	}	×
97	if (!dominance_analysis.dominates(define1, define2)) {	6!
98	continue;	×
99	}
100
101	// Criterion: Prove identical subsets of definitions
102	auto subsets1 = define1->subsets();	6!
103	auto subsets2 = define2->subsets();	6!
104	if (subsets1.size() != 1 \|\| subsets2.size() != 1) {	6!
105	continue;	×
106	}
107	if (subsets1.begin()->size() != subsets2.begin()->size()) {	6!
108	continue;	×
109	}
110	bool identical_subsets = true;	6✔
111	for (size_t i = 0; i < subsets1.begin()->size(); i++) {	6!
112	auto dim1 = subsets1.begin()->at(i);	×
113	auto dim2 = subsets2.begin()->at(i);	×
114	if (!symbolic::eq(dim1, dim2)) {	×
115	identical_subsets = false;	×
116	break;	×
117	}
118	std::unordered_set<std::string> symbols;	×
119	for (auto& sym : symbolic::atoms(dim1)) {	×
120	symbols.insert(sym->get_name());	×
121	}
122	for (auto& user : users.all_uses_between(define1, define2)) {	×
123	if (user->use() == analysis::Use::READ) {	×
124	continue;	×
125	}
126	if (symbols.find(user->container()) != symbols.end()) {	×
127	identical_subsets = false;	×
128	break;	×
129	}
130	}
131	}	×
132	if (!identical_subsets) {	6!
133	continue;	×
134	}
135
136	// Criterion: Provide identical rhs/inputs of definitions
137	auto inputs1 = inputs(*define1, users);	6!
138	if (inputs1.empty()) {	6!
139	continue;	×
140	}
141	auto inputs2 = inputs(*define2, users);	6!
142	if (inputs2.empty()) {	6!
143	continue;	×
144	}
145	if (inputs1.size() != inputs2.size()) {	6!
146	continue;	×
147	}
148
149	bool identical_inputs = true;	6✔
150	for (auto& input : inputs1) {	12✔
151	// Recursion
152	if (input->container() == name) {	6!
153	identical_inputs = false;	×
154	break;	×
155	}
156
157	// If input is written, it must happen before define1
158	for (auto& write_user : users.writes(input->container())) {	10!
159	if (!dominance_analysis.dominates(write_user, define1)) {	4!
160	identical_inputs = false;	×
161	break;	×
162	}
163	}
164
165	// If input is moved, it must happen before define1
166	for (auto& move_user : users.moves(input->container())) {	6!
167	if (!dominance_analysis.dominates(move_user, define1)) {	×
168	identical_inputs = false;	×
169	break;	×
170	}
171	}
172
173	// If input has views, it must be the definitions
174	for (auto& view : users.views(input->container())) {	6!
175	auto& viewed_node = dynamic_cast<data_flow::AccessNode&>(*view->element());	×
176	auto& graph = viewed_node.get_parent();	×
177	if (graph.out_degree(viewed_node) != 1) {	×
178	continue;	×
179	}
180	auto& viewing_node = (*graph.out_edges(viewed_node).begin()).dst();	×
181	if (&viewing_node != define1->element() && &viewing_node != define2->element()) {	×
182	identical_inputs = false;	×
183	}	×
184	}
185	if (!identical_inputs) {	6!
186	break;	×
187	}
188
189	// Find identical input in inputs2
190	analysis::User* input2 = nullptr;	6✔
191	for (auto& inp : inputs2) {	6!
192	if (input->container() == inp->container()) {	6!
193	input2 = inp;	6✔
194	break;	6✔
195	}
196	}
197	if (input2 == nullptr) {	6!
198	identical_inputs = false;	×
199	break;	×
200	}
201
202	// same subsets
203	if (input->subsets().size() != 1 \|\| input2->subsets().size() != 1) {	6!
204	identical_inputs = false;	×
205	break;	×
206	}
207
208	auto subset1 = *input->subsets().begin();	6!
209	auto subset2 = *input2->subsets().begin();	6!
210	if (subset1.size() != subset2.size()) {	6!
211	identical_inputs = false;	×
212	break;	×
213	}
214	for (size_t i = 0; i < subset1.size(); i++) {	8✔
215	auto dim1 = subset1[i];	2!
216	auto dim2 = subset2[i];	2!
217	if (!symbolic::eq(dim1, dim2)) {	2!
218	identical_inputs = false;	×
219	break;	×
220	}
221	std::unordered_set<std::string> symbols;	2✔
222	for (auto& sym : symbolic::atoms(dim1)) {	2!
223	symbols.insert(sym->get_name());	×
224	}
225	for (auto& user : users.all_uses_between(define1, define2)) {	4!
226	if (user->use() == analysis::Use::READ) {	2!
227	continue;	2✔
228	}
229	if (symbols.find(user->container()) != symbols.end()) {	×
230	identical_inputs = false;	×
231	break;	×
232	}
233	}
234	}	2!
235	}	6!
236	if (!identical_inputs) {	6!
237	continue;	×
238	}
239
240	// Eliminate the dominated definition
241	auto write = define2->element();	6!
242	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write)) {	6!
243	transition->assignments().erase(symbolic::symbol(name));	4!
244	applied = true;	4✔
245	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write)) {	6!
246	auto& graph = access_node->get_parent();	2!
247	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	2!
248	builder.clear_node(block, *access_node);	2!
249	applied = true;	2✔
250	}	2✔
251	}	12✔
252
253	return applied;	6✔
254	};	×
255
256	} // namespace passes
257	} // namespace sdfg

daisytuner / sdfglib / 20141104835

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