Build has been canceled!

15946294632

Committed 28 Jun 2025 04:59PM UTC coverage: 64.97% (-0.03%) from 65.002%

Build # 15946294632

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #115 from daisytuner/conditional-sdfgs

Overall improvements for conditional sdfg features

Run Details

43 of 82 new or added lines in 2 files covered. (52.44%)

6 existing lines in 1 file now uncovered.

8552 of 13163 relevant lines covered (64.97%)

144.49 hits per line

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

56.69

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

daisytuner / sdfglib / 15946294632

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