19982732738

Committed 05 Dec 2025 03:22PM UTC coverage: 61.811% (-0.01%) from 61.822%

Build # 19982732738

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #373 from daisytuner/constant-elimination

extends constant elimination to apply more often

Run Details

12 of 16 new or added lines in 3 files covered. (75.0%)

4 existing lines in 1 file now uncovered.

11254 of 18207 relevant lines covered (61.81%)

110.73 hits per line

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

70.47

/src/passes/dataflow/constant_elimination.cpp

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

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

namespace sdfg {
namespace passes {

ConstantElimination::ConstantElimination() : Pass() {};

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

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();
    data_flow::Tasklet* tasklet = nullptr;
    for (auto& iedge : graph.in_edges(*access_node)) {
        tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());
    }
    if (tasklet == nullptr) {
        return {};
    }
    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));
    }
    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 ConstantElimination::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>();

    std::unordered_set<std::string> dead;
    for (auto& name : sdfg.containers()) {
        // Criterion: No aliases
        if (!users.views(name).empty() || !users.moves(name).empty()) {
            continue;
        }

        // Criterion: Two definitions
        // Filter our undefined user
        auto definitions = data_dependency_analysis.definitions(name);
        std::unordered_set<analysis::User*> defines;
        for (auto& def : definitions) {
            if (data_dependency_analysis.is_undefined_user(*def.first)) {
                continue;
            }
            defines.insert(def.first);
        }
        if (defines.size() != 2) {
            continue;
        }
        auto define1 = *defines.begin();
        auto define2 = *(++defines.begin());

        // Criterion: Identical define
        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 constant_write = 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)) {
                constant_write = false;
                break;
            }
            if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {
                constant_write = false;
                break;
            }
        }
        if (!constant_write) {
            continue;
        }

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

        // Criterion: Inputs of definition are constant
        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 constant_inputs = true;
        for (auto& input : inputs1) {
            // Recursion
            if (input->container() == name) {
                constant_inputs = false;
                break;
            }

            // input1 is constant
            if (users.views(input->container()).size() > 0) {
                constant_inputs = false;
                break;
            }
            for (auto& write_user : users.writes(input->container())) {
                if (!dominance_analysis.dominates(*write_user, *define1)) {
                    constant_inputs = false;
                    break;
                }
            }
            for (auto& move_user : users.moves(input->container())) {
                if (!dominance_analysis.dominates(*move_user, *define1)) {
                    constant_inputs = false;
                    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) {
                constant_inputs = false;
                break;
            }

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

            auto subset1 = *input->subsets().begin();
            auto subset2 = *input2->subsets().begin();
            if (subset1.size() != subset2.size()) {
                constant_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)) {
                    constant_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()) {
                        constant_inputs = false;
                        break;
                    }
                }
            }
        }
        if (!constant_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_elimination.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	ConstantElimination::ConstantElimination() : Pass() {};	7✔
11
12	std::string ConstantElimination::name() { return "ConstantElimination"; };	×
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	data_flow::Tasklet* tasklet = nullptr;	4✔
20	for (auto& iedge : graph.in_edges(*access_node)) {	8✔
21	tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());	4✔
22	}
23	if (tasklet == nullptr) {	4✔
24	return {};	×
25	}
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	return inputs;	4✔
35	}	4✔
36
37	std::unordered_set<analysis::User*>
38	inputs(const std::string& container, structured_control_flow::Transition* transition, analysis::Users& users) {	8✔
39	std::unordered_set<analysis::User*> inputs;	8✔
40	auto& assign = transition->assignments().at(symbolic::symbol(container));	8✔
41	for (auto& sym : symbolic::atoms(assign)) {	16✔
42	if (symbolic::eq(sym, symbolic::__nullptr__())) {	8✔
43	continue;	×
44	}
45	inputs.insert(users.get_user(sym->get_name(), transition, analysis::Use::READ));	8✔
46	}
47	return inputs;	8✔
48	}	8✔
49
50	std::unordered_set<analysis::User*> inputs(analysis::User& user, analysis::Users& users) {	12✔
51	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user.element())) {	12✔
52	return inputs(user.container(), access_node, users);	4✔
53	} else if (auto transition = dynamic_cast<structured_control_flow::Transition*>(user.element())) {	8✔
54	return inputs(user.container(), transition, users);	8✔
55	} else {
56	return {};	×
57	}
58	}	12✔
59
60	bool ConstantElimination::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	6✔
61	bool applied = false;	6✔
62
63	auto& sdfg = builder.subject();	6✔
64	auto& users = analysis_manager.get<analysis::Users>();	6✔
65	auto& dominance_analysis = analysis_manager.get<analysis::DominanceAnalysis>();	6✔
66	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	6✔
67
68	std::unordered_set<std::string> dead;	6✔
69	for (auto& name : sdfg.containers()) {	18✔
70	// Criterion: No aliases
71	if (!users.views(name).empty() \|\| !users.moves(name).empty()) {	12✔
72	continue;	×
73	}
74
75	// Criterion: Two definitions
76	// Filter our undefined user
77	auto definitions = data_dependency_analysis.definitions(name);	12✔
78	std::unordered_set<analysis::User*> defines;	12✔
79	for (auto& def : definitions) {	29✔
80	if (data_dependency_analysis.is_undefined_user(*def.first)) {	17✔
81	continue;	1✔
82	}
83	defines.insert(def.first);	16✔
84	}
85	if (defines.size() != 2) {	12✔
86	continue;	6✔
87	}
88	auto define1 = *defines.begin();	6✔
89	auto define2 = *(++defines.begin());	6✔
90
91	// Criterion: Identical define
92	auto subsets1 = define1->subsets();	6✔
93	auto subsets2 = define2->subsets();	6✔
94	if (subsets1.size() != 1 \|\| subsets2.size() != 1) {	6✔
95	continue;	×
96	}
97	if (subsets1.begin()->size() != subsets2.begin()->size()) {	6✔
98	continue;	×
99	}
100	bool constant_write = true;	6✔
101	for (size_t i = 0; i < subsets1.begin()->size(); i++) {	6✔
102	auto dim1 = subsets1.begin()->at(i);	×
103	auto dim2 = subsets2.begin()->at(i);	×
104	if (!symbolic::eq(dim1, dim2)) {	×
105	constant_write = false;	×
106	break;	×
107	}
108	if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {	×
109	constant_write = false;	×
110	break;	×
111	}
112	}	×
113	if (!constant_write) {	6✔
114	continue;	×
115	}
116
117	// Criterion: One dominates the other
118	if (!dominance_analysis.dominates(define1, define2)) {	6✔
119	std::swap(define1, define2);	4✔
120	}	4✔
121	if (!dominance_analysis.dominates(define1, define2)) {	6✔
122	continue;	×
123	}
124
125	// Criterion: Inputs of definition are constant
126	auto inputs1 = inputs(*define1, users);	6✔
127	if (inputs1.empty()) {	6✔
128	continue;	×
129	}
130	auto inputs2 = inputs(*define2, users);	6✔
131	if (inputs2.empty()) {	6✔
132	continue;	×
133	}
134	if (inputs1.size() != inputs2.size()) {	6✔
135	continue;	×
136	}
137	bool constant_inputs = true;	6✔
138	for (auto& input : inputs1) {	12✔
139	// Recursion
140	if (input->container() == name) {	6✔
141	constant_inputs = false;	×
142	break;	×
143	}
144
145	// input1 is constant
146	if (users.views(input->container()).size() > 0) {	6✔
147	constant_inputs = false;	×
148	break;	×
149	}
150	for (auto& write_user : users.writes(input->container())) {	10✔
151	if (!dominance_analysis.dominates(write_user, define1)) {	4✔
152	constant_inputs = false;	×
153	break;	×
154	}
155	}
156	for (auto& move_user : users.moves(input->container())) {	6✔
157	if (!dominance_analysis.dominates(move_user, define1)) {	×
158	constant_inputs = false;	×
159	break;	×
160	}
161	}
162
163	// Find identical input in inputs2
164	analysis::User* input2 = nullptr;	6✔
165	for (auto& inp : inputs2) {	6✔
166	if (input->container() == inp->container()) {	6✔
167	input2 = inp;	6✔
168	break;	6✔
169	}
170	}
171	if (input2 == nullptr) {	6✔
172	constant_inputs = false;	×
173	break;	×
174	}
175
176	// same subsets
177	if (input->subsets().size() != 1 \|\| input2->subsets().size() != 1) {	6✔
178	constant_inputs = false;	×
179	break;	×
180	}
181
182	auto subset1 = *input->subsets().begin();	6✔
183	auto subset2 = *input2->subsets().begin();	6✔
184	if (subset1.size() != subset2.size()) {	6✔
185	constant_inputs = false;	×
186	break;	×
187	}
188	for (size_t i = 0; i < subset1.size(); i++) {	8✔
189	auto dim1 = subset1[i];	2✔
190	auto dim2 = subset2[i];	2✔
191	if (!symbolic::eq(dim1, dim2)) {	2✔
192	constant_inputs = false;	×
193	break;	×
194	}
195	std::unordered_set<std::string> symbols;	2✔
196	for (auto& sym : symbolic::atoms(dim1)) {	2✔
NEW 197	symbols.insert(sym->get_name());	×
198	}
199	for (auto& user : users.all_uses_between(define1, define2)) {	4✔
200	if (user->use() == analysis::Use::READ) {	2✔
201	continue;	2✔
202	}
NEW 203	if (symbols.find(user->container()) != symbols.end()) {	×
NEW 204	constant_inputs = false;	×
NEW 205	break;	×
206	}
207	}
208	}	2✔
209	}	6✔
210	if (!constant_inputs) {	6✔
211	continue;	×
212	}
213
214	// Eliminate the dominated definition
215	auto write = define2->element();	6✔
216	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write)) {	6✔
217	transition->assignments().erase(symbolic::symbol(name));	4✔
218	applied = true;	4✔
219	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write)) {	6✔
220	auto& graph = access_node->get_parent();	2✔
221	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	2✔
222	builder.clear_node(block, *access_node);	2✔
223	applied = true;	2✔
224	}	2✔
225	}	12✔
226
227	return applied;	6✔
228	};	6✔
229
230	} // namespace passes
231	} // namespace sdfg

daisytuner / sdfglib / 19982732738

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