17656823807

Committed 11 Sep 2025 08:42PM UTC coverage: 60.447% (+1.1%) from 59.335%

Build # 17656823807

Build Type

Pull #219

github

Committed by

web-flow

Commit Message

Merge d5416236f into 6c1992b40

Pull Request Pull Request #219: stdlib Library Nodes and ConstantNodes

Run Details

460 of 1635 new or added lines in 81 files covered. (28.13%)

93 existing lines in 35 files now uncovered.

9385 of 15526 relevant lines covered (60.45%)

107.21 hits per line

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

0.79

/src/passes/dataflow/constant_elimination.cpp

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

#include "sdfg/analysis/data_dependency_analysis.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)) {
        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& 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
        auto defines = data_dependency_analysis.definitions(name);
        if (defines.size() != 2) {
            continue;
        }

        auto define1 = defines.begin()->first;
        auto define2 = (++defines.begin())->first;

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

daisytuner / sdfglib / 17656823807

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