16312353091

Committed 16 Jul 2025 06:41AM UTC coverage: 64.622% (-0.2%) from 64.843%

Build # 16312353091

Build Type

Pull #141

github

Committed by

web-flow

Commit Message

Merge 750219df9 into 9bcea5e19

Pull Request Pull Request #141: Several convenience improvements for library nodes

Run Details

60 of 141 new or added lines in 14 files covered. (42.55%)

8 existing lines in 7 files now uncovered.

8556 of 13240 relevant lines covered (64.62%)

178.39 hits per line

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

56.35

/src/passes/dataflow/view_propagation.cpp

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

#include "sdfg/analysis/users.h"
#include "sdfg/types/utils.h"

namespace sdfg {
namespace passes {

ViewPropagation::ViewPropagation()
    : Pass() {

      };

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

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

    auto& sdfg = builder.subject();

    // Replaces all views
    auto& users = analysis_manager.get<analysis::Users>();
    std::unordered_set<std::string> reduced;
    for (auto& container : sdfg.containers()) {
        if (reduced.find(container) != reduced.end()) {
            continue;
        }
        if (sdfg.is_external(container)) {
            continue;
        }

        // By definition, a view is a pointer
        auto& type = sdfg.type(container);
        if (!dynamic_cast<const types::Pointer*>(&type)) {
            continue;
        }

        // Criterion: Must have at least one move
        auto moves = users.moves(container);
        if (moves.empty()) {
            continue;
        }

        // Criterion: No sub-views (will be eliminated iteratively)
        if (users.views(container).size() > 0) {
            continue;
        }

        // Eliminate views
        auto uses = users.uses(container);
        for (auto& move : moves) {
            // Location of where the view is created
            auto& access_node = dynamic_cast<data_flow::AccessNode&>(*move->element());
            auto& dataflow = *move->parent();
            auto& move_edge = *dataflow.in_edges(access_node).begin();
            auto& move_subset = move_edge.subset();

            // Retrieve underlying container
            auto& viewed_node = dynamic_cast<const data_flow::AccessNode&>(move_edge.src());
            auto& viewed_container = viewed_node.data();

            // Criterion: Must not be raw memory address
            if (helpers::is_number(viewed_container) || symbolic::is_nullptr(symbolic::symbol(viewed_container))) {
                continue;
            }

            // Criterion: Must not be nested pointer
            if (move_edge.dst_conn() == "void" && !move_subset.empty()) {
                continue;
            }

            // Criterion: Must not be reinterpret cast
            auto viewed_type = &sdfg.type(viewed_container);
            if (move_edge.src_conn() == "void") {
                viewed_type = &types::infer_type(sdfg, *viewed_type, move_subset);
            }
            types::Pointer final_type(*viewed_type);
            if (type != final_type) {
                continue;
            }

            // Replace all uses of the view by the original container
            for (auto& user : uses) {
                // Criterion: Must be read or write
                if (user->use() != analysis::Use::READ && user->use() != analysis::Use::WRITE) {
                    continue;
                }
                // Criterion: Must be dominated by the move
                if (!users.dominates(*move, *user)) {
                    continue;
                }
                // Criterion: Safety - View is not reassigned between the move and the user
                auto uses_between = users.all_uses_between(*move, *user);
                bool unsafe = false;
                for (auto& use : uses_between) {
                    if (use->use() != analysis::Use::MOVE) {
                        continue;
                    }
                    // View is not constant
                    if (use->container() == viewed_container) {
                        unsafe = true;
                        break;
                    }
                    // Another alias of the view
                    if (use->container() == container) {
                        unsafe = true;
                        break;
                    }

                    // Raw memory access
                    auto& use_node = dynamic_cast<data_flow::AccessNode&>(*use->element());
                    auto& use_graph = *use->parent();
                    auto& use_edge = *use_graph.in_edges(use_node).begin();
                    auto& src_node = dynamic_cast<data_flow::AccessNode&>(use_edge.src());
                    if (helpers::is_number(src_node.data())) {
                        unsafe = true;
                        break;
                    }
                }
                if (unsafe) {
                    continue;
                }

                // Can only replace access nodes
                if (!dynamic_cast<data_flow::AccessNode*>(user->element())) {
                    continue;
                }
                auto& use_node = static_cast<data_flow::AccessNode&>(*user->element());

                // Step 1: Replace container
                use_node.data() = viewed_container;

                // Step 2: Update edges
                auto use_graph = user->parent();
                for (auto& oedge : use_graph->out_edges(use_node)) {
                    // Compute new subset
                    data_flow::Subset new_subset;

                    // Add leading dimensions from move
                    if (move_edge.src_conn() == "void") {
                        for (size_t i = 0; i < move_subset.size(); i++) {
                            new_subset.push_back(move_subset[i]);
                        }
                    }

                    auto old_subset = oedge.subset();

                    // Handle first trailing dimensions
                    if (new_subset.empty()) {
                        auto& trail_dim = old_subset.front();
                        if (!symbolic::eq(trail_dim, symbolic::zero())) {
                            throw std::runtime_error("View propagation not implemented for non-void source connection");
                        }
                        old_subset.erase(old_subset.begin());
                    } else {
                        auto& trail_dim = old_subset.front();
                        auto& current_dim = new_subset.back();
                        auto new_dim = symbolic::add(current_dim, trail_dim);
                        new_subset.back() = new_dim;
                        old_subset.erase(old_subset.begin());
                    }

                    // Add remaining trailing dimensions
                    for (auto& dim : old_subset) {
                        new_subset.push_back(dim);
                    }
                    oedge.set_subset(new_subset);
                }
                for (auto& iedge : use_graph->in_edges(use_node)) {
                    // Compute new subset
                    data_flow::Subset new_subset;

                    // Add leading dimensions from move
                    if (move_edge.src_conn() == "void") {
                        for (size_t i = 0; i < move_subset.size(); i++) {
                            new_subset.push_back(move_subset[i]);
                        }
                    }

                    auto old_subset = iedge.subset();

                    // Handle first trailing dimensions
                    if (new_subset.empty()) {
                        auto& trail_dim = old_subset.front();
                        if (!symbolic::eq(trail_dim, symbolic::zero())) {
                            throw std::runtime_error("View propagation not implemented for non-void source connection");
                        }
                        old_subset.erase(old_subset.begin());
                    } else {
                        auto& trail_dim = old_subset.front();
                        auto& current_dim = new_subset.back();
                        auto new_dim = symbolic::add(current_dim, trail_dim);
                        new_subset.back() = new_dim;
                        old_subset.erase(old_subset.begin());
                    }

                    // Add remaining trailing dimensions
                    for (auto& dim : old_subset) {
                        new_subset.push_back(dim);
                    }
                    iedge.set_subset(new_subset);
                }

                applied = true;
                reduced.insert(viewed_container);
            }
        }
    }

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/view_propagation.h"
2
3	#include "sdfg/analysis/users.h"
4	#include "sdfg/types/utils.h"
5
6	namespace sdfg {
7	namespace passes {
8
9	ViewPropagation::ViewPropagation()	2✔
10	: Pass() {	2✔
11
12	};	2✔
13
14	std::string ViewPropagation::name() { return "ViewPropagation"; };	×
15
16	bool ViewPropagation::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	1✔
17	bool applied = false;	1✔
18
19	auto& sdfg = builder.subject();	1✔
20
21	// Replaces all views
22	auto& users = analysis_manager.get<analysis::Users>();	1✔
23	std::unordered_set<std::string> reduced;	1✔
24	for (auto& container : sdfg.containers()) {	3✔
25	if (reduced.find(container) != reduced.end()) {	2✔
26	continue;	1✔
27	}
28	if (sdfg.is_external(container)) {	1✔
29	continue;	×
30	}
31
32	// By definition, a view is a pointer
33	auto& type = sdfg.type(container);	1✔
34	if (!dynamic_cast<const types::Pointer*>(&type)) {	1✔
35	continue;	×
36	}
37
38	// Criterion: Must have at least one move
39	auto moves = users.moves(container);	1✔
40	if (moves.empty()) {	1✔
41	continue;	×
42	}
43
44	// Criterion: No sub-views (will be eliminated iteratively)
45	if (users.views(container).size() > 0) {	1✔
46	continue;	×
47	}
48
49	// Eliminate views
50	auto uses = users.uses(container);	1✔
51	for (auto& move : moves) {	2✔
52	// Location of where the view is created
53	auto& access_node = dynamic_cast<data_flow::AccessNode&>(*move->element());	1✔
54	auto& dataflow = *move->parent();	1✔
55	auto& move_edge = *dataflow.in_edges(access_node).begin();	1✔
56	auto& move_subset = move_edge.subset();	1✔
57
58	// Retrieve underlying container
59	auto& viewed_node = dynamic_cast<const data_flow::AccessNode&>(move_edge.src());	1✔
60	auto& viewed_container = viewed_node.data();	1✔
61
62	// Criterion: Must not be raw memory address
63	if (helpers::is_number(viewed_container) \|\| symbolic::is_nullptr(symbolic::symbol(viewed_container))) {	1✔
UNCOV 64	continue;	×
65	}
66
67	// Criterion: Must not be nested pointer
68	if (move_edge.dst_conn() == "void" && !move_subset.empty()) {	1✔
69	continue;	×
70	}
71
72	// Criterion: Must not be reinterpret cast
73	auto viewed_type = &sdfg.type(viewed_container);	1✔
74	if (move_edge.src_conn() == "void") {	1✔
75	viewed_type = &types::infer_type(sdfg, *viewed_type, move_subset);	1✔
76	}	1✔
77	types::Pointer final_type(*viewed_type);	1✔
78	if (type != final_type) {	1✔
79	continue;	×
80	}
81
82	// Replace all uses of the view by the original container
83	for (auto& user : uses) {	3✔
84	// Criterion: Must be read or write
85	if (user->use() != analysis::Use::READ && user->use() != analysis::Use::WRITE) {	2✔
86	continue;	1✔
87	}
88	// Criterion: Must be dominated by the move
89	if (!users.dominates(move, user)) {	1✔
90	continue;	×
91	}
92	// Criterion: Safety - View is not reassigned between the move and the user
93	auto uses_between = users.all_uses_between(move, user);	1✔
94	bool unsafe = false;	1✔
95	for (auto& use : uses_between) {	1✔
96	if (use->use() != analysis::Use::MOVE) {	×
97	continue;	×
98	}
99	// View is not constant
100	if (use->container() == viewed_container) {	×
101	unsafe = true;	×
102	break;	×
103	}
104	// Another alias of the view
105	if (use->container() == container) {	×
106	unsafe = true;	×
107	break;	×
108	}
109
110	// Raw memory access
111	auto& use_node = dynamic_cast<data_flow::AccessNode&>(*use->element());	×
112	auto& use_graph = *use->parent();	×
113	auto& use_edge = *use_graph.in_edges(use_node).begin();	×
114	auto& src_node = dynamic_cast<data_flow::AccessNode&>(use_edge.src());	×
115	if (helpers::is_number(src_node.data())) {	×
116	unsafe = true;	×
117	break;	×
118	}
119	}
120	if (unsafe) {	1✔
121	continue;	×
122	}
123
124	// Can only replace access nodes
125	if (!dynamic_cast<data_flow::AccessNode*>(user->element())) {	1✔
126	continue;	×
127	}
128	auto& use_node = static_cast<data_flow::AccessNode&>(*user->element());	1✔
129
130	// Step 1: Replace container
131	use_node.data() = viewed_container;	1✔
132
133	// Step 2: Update edges
134	auto use_graph = user->parent();	1✔
135	for (auto& oedge : use_graph->out_edges(use_node)) {	1✔
136	// Compute new subset
137	data_flow::Subset new_subset;	×
138
139	// Add leading dimensions from move
140	if (move_edge.src_conn() == "void") {	×
141	for (size_t i = 0; i < move_subset.size(); i++) {	×
142	new_subset.push_back(move_subset[i]);	×
143	}	×
144	}	×
145
NEW 146	auto old_subset = oedge.subset();	×
147
148	// Handle first trailing dimensions
149	if (new_subset.empty()) {	×
150	auto& trail_dim = old_subset.front();	×
151	if (!symbolic::eq(trail_dim, symbolic::zero())) {	×
NEW 152	throw std::runtime_error("View propagation not implemented for non-void source connection");	×
153	}
154	old_subset.erase(old_subset.begin());	×
155	} else {	×
156	auto& trail_dim = old_subset.front();	×
157	auto& current_dim = new_subset.back();	×
158	auto new_dim = symbolic::add(current_dim, trail_dim);	×
159	new_subset.back() = new_dim;	×
160	old_subset.erase(old_subset.begin());	×
161	}	×
162
163	// Add remaining trailing dimensions
164	for (auto& dim : old_subset) {	×
165	new_subset.push_back(dim);	×
166	}
NEW 167	oedge.set_subset(new_subset);	×
168	}	×
169	for (auto& iedge : use_graph->in_edges(use_node)) {	2✔
170	// Compute new subset
171	data_flow::Subset new_subset;	1✔
172
173	// Add leading dimensions from move
174	if (move_edge.src_conn() == "void") {	1✔
175	for (size_t i = 0; i < move_subset.size(); i++) {	2✔
176	new_subset.push_back(move_subset[i]);	1✔
177	}	1✔
178	}	1✔
179
180	auto old_subset = iedge.subset();	1✔
181
182	// Handle first trailing dimensions
183	if (new_subset.empty()) {	1✔
184	auto& trail_dim = old_subset.front();	×
185	if (!symbolic::eq(trail_dim, symbolic::zero())) {	×
NEW 186	throw std::runtime_error("View propagation not implemented for non-void source connection");	×
187	}
188	old_subset.erase(old_subset.begin());	×
189	} else {	×
190	auto& trail_dim = old_subset.front();	1✔
191	auto& current_dim = new_subset.back();	1✔
192	auto new_dim = symbolic::add(current_dim, trail_dim);	1✔
193	new_subset.back() = new_dim;	1✔
194	old_subset.erase(old_subset.begin());	1✔
195	}	1✔
196
197	// Add remaining trailing dimensions
198	for (auto& dim : old_subset) {	1✔
199	new_subset.push_back(dim);	×
200	}
201	iedge.set_subset(new_subset);	1✔
202	}	1✔
203
204	applied = true;	1✔
205	reduced.insert(viewed_container);	1✔
206	}	1✔
207	}	1✔
208	}	1✔
209
210	return applied;	1✔
211	};	1✔
212
213	} // namespace passes
214	} // namespace sdfg

daisytuner / sdfglib / 16312353091

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