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

49.51

/src/passes/symbolic/symbol_propagation.cpp

#include "sdfg/passes/symbolic/symbol_propagation.h"

#include "sdfg/analysis/data_dependency_analysis.h"

namespace sdfg {
namespace passes {

symbolic::Expression inverse(const symbolic::Symbol& lhs, const symbolic::Expression& rhs) {
    if (!symbolic::uses(rhs, lhs)) {
        return SymEngine::null;
    }

    if (SymEngine::is_a<SymEngine::Add>(*rhs)) {
        auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(rhs);
        auto arg_0 = add->get_args()[0];
        auto arg_1 = add->get_args()[1];
        if (!symbolic::eq(arg_0, lhs)) {
            std::swap(arg_0, arg_1);
        }
        if (!symbolic::eq(arg_0, lhs)) {
            return SymEngine::null;
        }
        if (!SymEngine::is_a<SymEngine::Integer>(*arg_1)) {
            return SymEngine::null;
        }
        return symbolic::sub(lhs, arg_1);
    } else if (SymEngine::is_a<SymEngine::Mul>(*rhs)) {
        auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(rhs);
        auto arg_0 = mul->get_args()[0];
        auto arg_1 = mul->get_args()[1];
        if (!symbolic::eq(arg_0, lhs)) {
            std::swap(arg_0, arg_1);
        }
        if (!symbolic::eq(arg_0, lhs)) {
            return SymEngine::null;
        }
        if (!SymEngine::is_a<SymEngine::Integer>(*arg_1)) {
            return SymEngine::null;
        }
        return symbolic::div(lhs, arg_1);
    }

    return SymEngine::null;
};

SymbolPropagation::SymbolPropagation()
    : Pass() {

      };

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

bool SymbolPropagation::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>();
    for (auto& name : sdfg.containers()) {
        // Criterion: Only transients
        if (!sdfg.is_transient(name)) {
            continue;
        }

        // Criterion: Only integers
        auto& type = builder.subject().type(name);
        auto scalar = dynamic_cast<const types::Scalar*>(&type);
        if (!scalar || !types::is_integer(scalar->primitive_type())) {
            continue;
        }

        // The symbol will become the LHS (to be replaced)
        auto lhs = symbolic::symbol(name);

        // Collect all reads of the symbol w.r.t to their writes
        auto raw_groups = data_dependency_analysis.defined_by(name);
        for (auto& entry : raw_groups) {
            // If not exclusive write, skip
            if (entry.second.size() != 1) {
                continue;
            }
            if (entry.first->use() != analysis::Use::READ) {
                continue;
            }
            auto read = entry.first;

            // Criterion: Write must be a transition
            auto write = *entry.second.begin();
            auto transition = dynamic_cast<structured_control_flow::Transition*>(write->element());
            if (!transition) {
                continue;
            }

            // We now define the rhs (to be propagated expression)
            auto rhs = transition->assignments().at(lhs);

            // Criterion: RHS is not trivial and not recursive
            if (symbolic::eq(lhs, rhs) || symbolic::uses(rhs, lhs)) {
                continue;
            }

            // Criterion: Write dominates read to not cause data races
            if (!users.dominates(*write, *read)) {
                continue;
            }

            // Collect all symbols used in the RHS
            std::unordered_set<std::string> rhs_symbols;
            for (auto& atom : symbolic::atoms(rhs)) {
                auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
                rhs_symbols.insert(sym->get_name());
            }

            // RHS' symbols may be written between write and read
            // We attempt to create the new RHS
            bool success = true;
            auto rhs_modified = rhs;
            std::unordered_set<std::string> modified_symbols;

            auto middle_users = users.all_uses_between(*write, *read);
            for (auto& user : middle_users) {
                if (user->use() != analysis::Use::WRITE) {
                    continue;
                }
                if (rhs_symbols.find(user->container()) == rhs_symbols.end()) {
                    continue;
                }

                // Criterion: Symbol is only modified once
                if (modified_symbols.find(user->container()) != modified_symbols.end()) {
                    success = false;
                    break;
                }

                // Criterion: RHS must dominate modification
                if (!users.dominates(*write, *user)) {
                    success = false;
                    break;
                }

                // Criterion: Modification must dominate read
                if (!users.dominates(*user, *read)) {
                    success = false;
                    break;
                }

                // Criterion: Only transitions
                if (!dynamic_cast<structured_control_flow::Transition*>(user->element())) {
                    success = false;
                    break;
                }
                auto sym_transition = dynamic_cast<structured_control_flow::Transition*>(user->element());
                auto sym_lhs = symbolic::symbol(user->container());
                auto sym_rhs = sym_transition->assignments().at(sym_lhs);

                // Limited to constants
                for (auto& atom : symbolic::atoms(sym_rhs)) {
                    if (!symbolic::eq(atom, sym_lhs)) {
                        success = false;
                        break;
                    }
                }
                if (!success) {
                    break;
                }

                auto inv = inverse(sym_lhs, sym_rhs);
                if (inv == SymEngine::null) {
                    success = false;
                    break;
                }

                rhs_modified = symbolic::subs(rhs_modified, sym_lhs, inv);
                modified_symbols.insert(user->container());
            }
            if (!success) {
                continue;
            }
            rhs_modified = symbolic::simplify(rhs_modified);

            if (auto transition_stmt = dynamic_cast<structured_control_flow::Transition*>(read->element())) {
                auto& assignments = transition_stmt->assignments();
                for (auto& entry : assignments) {
                    if (symbolic::uses(entry.second, lhs)) {
                        entry.second = symbolic::subs(entry.second, lhs, rhs_modified);
                        applied = true;
                    }
                }
            } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(read->element())) {
                // Criterion: RHS does not use nvptx symbols
                bool nvptx = false;
                for (auto& atom : symbolic::atoms(rhs_modified)) {
                    if (symbolic::is_nv(atom)) {
                        nvptx = true;
                        break;
                    }
                }
                if (nvptx) {
                    continue;
                }

                for (size_t i = 0; i < if_else_stmt->size(); i++) {
                    auto child = if_else_stmt->at(i);
                    if (symbolic::uses(child.second, lhs)) {
                        child.second = symbolic::subs(child.second, lhs, rhs_modified);
                        applied = true;
                    }
                }
            } else if (auto memlet = dynamic_cast<data_flow::Memlet*>(read->element())) {
                bool used = false;
                auto subset = memlet->subset();
                for (auto& dim : subset) {
                    if (symbolic::uses(dim, lhs)) {
                        dim = symbolic::subs(dim, lhs, rhs_modified);
                        used = true;
                    }
                }
                if (used) {
                    memlet->set_subset(subset);
                    applied = true;
                }
            } else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(read->element())) {
                if (SymEngine::is_a<SymEngine::Symbol>(*rhs_modified)) {
                    auto new_symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(rhs_modified);
                    access_node->data() = new_symbol->get_name();
                    applied = true;
                } else if (SymEngine::is_a<SymEngine::Integer>(*rhs_modified)) {
                    auto new_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(rhs_modified);
                    auto graph = read->parent();
                    auto block = static_cast<structured_control_flow::Block*>(graph->get_parent());

                    // Replace with const node
                    auto& const_node =
                        builder
                            .add_constant(*block, std::to_string(new_int->as_int()), type, read->element()->debug_info());

                    std::unordered_set<data_flow::Memlet*> replace_edges;
                    for (auto& oedge : graph->out_edges(*access_node)) {
                        builder.add_memlet(
                            *block,
                            const_node,
                            oedge.src_conn(),
                            oedge.dst(),
                            oedge.dst_conn(),
                            oedge.subset(),
                            oedge.base_type(),
                            oedge.debug_info()
                        );
                        replace_edges.insert(&oedge);
                    }
                    for (auto& iedge : graph->in_edges(*access_node)) {
                        builder.add_memlet(
                            *block,
                            iedge.src(),
                            iedge.src_conn(),
                            const_node,
                            iedge.dst_conn(),
                            iedge.subset(),
                            iedge.base_type(),
                            iedge.debug_info()
                        );
                    }

                    for (auto& edge : replace_edges) {
                        builder.remove_memlet(*block, *edge);
                    }
                    builder.remove_node(*block, *access_node);
                    applied = true;
                }
            } else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(read->element())) {
                for (auto& symbol : library_node->symbols()) {
                    if (symbolic::eq(symbol, lhs)) {
                        library_node->replace(symbol, rhs_modified);
                        applied = true;
                    }
                }
            } else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(read->element())) {
                auto for_user = dynamic_cast<analysis::ForUser*>(read);
                if (for_user->is_init() && symbolic::uses(for_loop->init(), lhs)) {
                    for_loop->init() = symbolic::subs(for_loop->init(), lhs, rhs_modified);
                    applied = true;
                } else if (for_user->is_condition() && symbolic::uses(for_loop->condition(), lhs)) {
                    for_loop->condition() = symbolic::subs(for_loop->condition(), lhs, rhs_modified);
                    applied = true;
                } else if (for_user->is_update() && symbolic::uses(for_loop->update(), lhs)) {
                    for_loop->update() = symbolic::subs(for_loop->update(), lhs, rhs_modified);
                    applied = true;
                }
            }
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/symbolic/symbol_propagation.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4
5	namespace sdfg {
6	namespace passes {
7
8	symbolic::Expression inverse(const symbolic::Symbol& lhs, const symbolic::Expression& rhs) {	1✔
9	if (!symbolic::uses(rhs, lhs)) {	1✔
10	return SymEngine::null;	1✔
11	}
12
13	if (SymEngine::is_a<SymEngine::Add>(*rhs)) {	×
14	auto add = SymEngine::rcp_static_cast<const SymEngine::Add>(rhs);	×
15	auto arg_0 = add->get_args()[0];	×
16	auto arg_1 = add->get_args()[1];	×
17	if (!symbolic::eq(arg_0, lhs)) {	×
18	std::swap(arg_0, arg_1);	×
19	}	×
20	if (!symbolic::eq(arg_0, lhs)) {	×
21	return SymEngine::null;	×
22	}
23	if (!SymEngine::is_a<SymEngine::Integer>(*arg_1)) {	×
24	return SymEngine::null;	×
25	}
26	return symbolic::sub(lhs, arg_1);	×
27	} else if (SymEngine::is_a<SymEngine::Mul>(*rhs)) {	×
28	auto mul = SymEngine::rcp_static_cast<const SymEngine::Mul>(rhs);	×
29	auto arg_0 = mul->get_args()[0];	×
30	auto arg_1 = mul->get_args()[1];	×
31	if (!symbolic::eq(arg_0, lhs)) {	×
32	std::swap(arg_0, arg_1);	×
33	}	×
34	if (!symbolic::eq(arg_0, lhs)) {	×
35	return SymEngine::null;	×
36	}
37	if (!SymEngine::is_a<SymEngine::Integer>(*arg_1)) {	×
38	return SymEngine::null;	×
39	}
40	return symbolic::div(lhs, arg_1);	×
41	}	×
42
43	return SymEngine::null;	×
44	};	1✔
45
46	SymbolPropagation::SymbolPropagation()	14✔
47	: Pass() {	14✔
48
49	};	14✔
50
51	std::string SymbolPropagation::name() { return "SymbolPropagation"; };	×
52
53	bool SymbolPropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	12✔
54	bool applied = false;	12✔
55
56	auto& sdfg = builder.subject();	12✔
57	auto& users = analysis_manager.get<analysis::Users>();	12✔
58	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	12✔
59	for (auto& name : sdfg.containers()) {	39✔
60	// Criterion: Only transients
61	if (!sdfg.is_transient(name)) {	27✔
62	continue;	6✔
63	}
64
65	// Criterion: Only integers
66	auto& type = builder.subject().type(name);	21✔
67	auto scalar = dynamic_cast<const types::Scalar*>(&type);	21✔
68	if (!scalar \|\| !types::is_integer(scalar->primitive_type())) {	21✔
69	continue;	2✔
70	}
71
72	// The symbol will become the LHS (to be replaced)
73	auto lhs = symbolic::symbol(name);	19✔
74
75	// Collect all reads of the symbol w.r.t to their writes
76	auto raw_groups = data_dependency_analysis.defined_by(name);	19✔
77	for (auto& entry : raw_groups) {	39✔
78	// If not exclusive write, skip
79	if (entry.second.size() != 1) {	20✔
80	continue;	7✔
81	}
82	if (entry.first->use() != analysis::Use::READ) {	13✔
83	continue;	×
84	}
85	auto read = entry.first;	13✔
86
87	// Criterion: Write must be a transition
88	auto write = *entry.second.begin();	13✔
89	auto transition = dynamic_cast<structured_control_flow::Transition*>(write->element());	13✔
90	if (!transition) {	13✔
91	continue;	×
92	}
93
94	// We now define the rhs (to be propagated expression)
95	auto rhs = transition->assignments().at(lhs);	13✔
96
97	// Criterion: RHS is not trivial and not recursive
98	if (symbolic::eq(lhs, rhs) \|\| symbolic::uses(rhs, lhs)) {	13✔
99	continue;	×
100	}
101
102	// Criterion: Write dominates read to not cause data races
103	if (!users.dominates(write, read)) {	13✔
104	continue;	×
105	}
106
107	// Collect all symbols used in the RHS
108	std::unordered_set<std::string> rhs_symbols;	13✔
109	for (auto& atom : symbolic::atoms(rhs)) {	19✔
110	auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	6✔
111	rhs_symbols.insert(sym->get_name());	6✔
112	}	6✔
113
114	// RHS' symbols may be written between write and read
115	// We attempt to create the new RHS
116	bool success = true;	13✔
117	auto rhs_modified = rhs;	13✔
118	std::unordered_set<std::string> modified_symbols;	13✔
119
120	auto middle_users = users.all_uses_between(write, read);	13✔
121	for (auto& user : middle_users) {	21✔
122	if (user->use() != analysis::Use::WRITE) {	9✔
123	continue;	6✔
124	}
125	if (rhs_symbols.find(user->container()) == rhs_symbols.end()) {	3✔
126	continue;	2✔
127	}
128
129	// Criterion: Symbol is only modified once
130	if (modified_symbols.find(user->container()) != modified_symbols.end()) {	1✔
131	success = false;	×
132	break;	×
133	}
134
135	// Criterion: RHS must dominate modification
136	if (!users.dominates(write, user)) {	1✔
137	success = false;	×
138	break;	×
139	}
140
141	// Criterion: Modification must dominate read
142	if (!users.dominates(user, read)) {	1✔
143	success = false;	×
144	break;	×
145	}
146
147	// Criterion: Only transitions
148	if (!dynamic_cast<structured_control_flow::Transition*>(user->element())) {	1✔
149	success = false;	×
150	break;	×
151	}
152	auto sym_transition = dynamic_cast<structured_control_flow::Transition*>(user->element());	1✔
153	auto sym_lhs = symbolic::symbol(user->container());	1✔
154	auto sym_rhs = sym_transition->assignments().at(sym_lhs);	1✔
155
156	// Limited to constants
157	for (auto& atom : symbolic::atoms(sym_rhs)) {	1✔
158	if (!symbolic::eq(atom, sym_lhs)) {	×
159	success = false;	×
160	break;	×
161	}
162	}
163	if (!success) {	1✔
164	break;	×
165	}
166
167	auto inv = inverse(sym_lhs, sym_rhs);	1✔
168	if (inv == SymEngine::null) {	1✔
169	success = false;	1✔
170	break;	1✔
171	}
172
173	rhs_modified = symbolic::subs(rhs_modified, sym_lhs, inv);	×
174	modified_symbols.insert(user->container());	×
175	}	1✔
176	if (!success) {	13✔
177	continue;	1✔
178	}
179	rhs_modified = symbolic::simplify(rhs_modified);	12✔
180
181	if (auto transition_stmt = dynamic_cast<structured_control_flow::Transition*>(read->element())) {	12✔
182	auto& assignments = transition_stmt->assignments();	7✔
183	for (auto& entry : assignments) {	14✔
184	if (symbolic::uses(entry.second, lhs)) {	7✔
185	entry.second = symbolic::subs(entry.second, lhs, rhs_modified);	7✔
186	applied = true;	7✔
187	}	7✔
188	}
189	} else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(read->element())) {	12✔
190	// Criterion: RHS does not use nvptx symbols
191	bool nvptx = false;	×
192	for (auto& atom : symbolic::atoms(rhs_modified)) {	×
193	if (symbolic::is_nv(atom)) {	×
194	nvptx = true;	×
195	break;	×
196	}
197	}
198	if (nvptx) {	×
199	continue;	×
200	}
201
202	for (size_t i = 0; i < if_else_stmt->size(); i++) {	×
203	auto child = if_else_stmt->at(i);	×
204	if (symbolic::uses(child.second, lhs)) {	×
205	child.second = symbolic::subs(child.second, lhs, rhs_modified);	×
206	applied = true;	×
207	}	×
208	}	×
209	} else if (auto memlet = dynamic_cast<data_flow::Memlet*>(read->element())) {	5✔
210	bool used = false;	2✔
211	auto subset = memlet->subset();	2✔
212	for (auto& dim : subset) {	4✔
213	if (symbolic::uses(dim, lhs)) {	2✔
214	dim = symbolic::subs(dim, lhs, rhs_modified);	2✔
215	used = true;	2✔
216	}	2✔
217	}
218	if (used) {	2✔
219	memlet->set_subset(subset);	2✔
220	applied = true;	2✔
221	}	2✔
222	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(read->element())) {	5✔
223	if (SymEngine::is_a<SymEngine::Symbol>(*rhs_modified)) {	×
224	auto new_symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(rhs_modified);	×
225	access_node->data() = new_symbol->get_name();	×
226	applied = true;	×
227	} else if (SymEngine::is_a<SymEngine::Integer>(*rhs_modified)) {	×
228	auto new_int = SymEngine::rcp_static_cast<const SymEngine::Integer>(rhs_modified);	×
229	auto graph = read->parent();	×
230	auto block = static_cast<structured_control_flow::Block*>(graph->get_parent());	×
231
232	// Replace with const node
NEW 233	auto& const_node =	×
NEW 234	builder	×
NEW 235	.add_constant(*block, std::to_string(new_int->as_int()), type, read->element()->debug_info());	×
236
NEW 237	std::unordered_set<data_flow::Memlet*> replace_edges;	×
238	for (auto& oedge : graph->out_edges(*access_node)) {	×
NEW 239	builder.add_memlet(	×
NEW 240	*block,	×
NEW 241	const_node,	×
NEW 242	oedge.src_conn(),	×
NEW 243	oedge.dst(),	×
NEW 244	oedge.dst_conn(),	×
NEW 245	oedge.subset(),	×
NEW 246	oedge.base_type(),	×
NEW 247	oedge.debug_info()	×
248	);
NEW 249	replace_edges.insert(&oedge);	×
250	}
NEW 251	for (auto& iedge : graph->in_edges(*access_node)) {	×
NEW 252	builder.add_memlet(	×
NEW 253	*block,	×
NEW 254	iedge.src(),	×
NEW 255	iedge.src_conn(),	×
NEW 256	const_node,	×
NEW 257	iedge.dst_conn(),	×
NEW 258	iedge.subset(),	×
NEW 259	iedge.base_type(),	×
NEW 260	iedge.debug_info()	×
261	);
262	}
263
NEW 264	for (auto& edge : replace_edges) {	×
NEW 265	builder.remove_memlet(block, edge);	×
266	}
NEW 267	builder.remove_node(block, access_node);	×
UNCOV 268	applied = true;	×
269	}	×
270	} else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(read->element())) {	3✔
271	for (auto& symbol : library_node->symbols()) {	×
272	if (symbolic::eq(symbol, lhs)) {	×
273	library_node->replace(symbol, rhs_modified);	×
274	applied = true;	×
275	}	×
276	}
277	} else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(read->element())) {	3✔
278	auto for_user = dynamic_cast<analysis::ForUser*>(read);	3✔
279	if (for_user->is_init() && symbolic::uses(for_loop->init(), lhs)) {	3✔
280	for_loop->init() = symbolic::subs(for_loop->init(), lhs, rhs_modified);	1✔
281	applied = true;	1✔
282	} else if (for_user->is_condition() && symbolic::uses(for_loop->condition(), lhs)) {	4✔
283	for_loop->condition() = symbolic::subs(for_loop->condition(), lhs, rhs_modified);	1✔
284	applied = true;	1✔
285	} else if (for_user->is_update() && symbolic::uses(for_loop->update(), lhs)) {	2✔
286	for_loop->update() = symbolic::subs(for_loop->update(), lhs, rhs_modified);	1✔
287	applied = true;	1✔
288	}	1✔
289	}	3✔
290	}	13✔
291	}	19✔
292
293	return applied;	12✔
294	};	×
295
296	} // namespace passes
297	} // 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