16440807098

Committed 22 Jul 2025 09:49AM UTC coverage: 66.011% (+0.9%) from 65.094%

Build # 16440807098

Build Type

Pull #153

github

Committed by

web-flow

Commit Message

Merge 194f87ac9 into abe57c083

Pull Request Pull Request #153: Introduces different memlet types for computation, references and dereferencing

Run Details

244 of 352 new or added lines in 30 files covered. (69.32%)

70 existing lines in 7 files now uncovered.

8322 of 12607 relevant lines covered (66.01%)

133.98 hits per line

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

78.76

/src/passes/dataflow/reference_propagation.cpp

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

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

namespace sdfg {
namespace passes {

ReferencePropagation::ReferencePropagation()
    : Pass() {

      };

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

bool ReferencePropagation::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 (type.type_id() != types::TypeID::Pointer) {
            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) {
            auto& access_node = static_cast<data_flow::AccessNode&>(*move->element());
            auto& dataflow = *move->parent();
            auto& move_edge = *dataflow.in_edges(access_node).begin();

            // Criterion: Must be a reference memlet
            if (move_edge.type() != data_flow::MemletType::Reference) {
                continue;
            }

            // Retrieve underlying container
            auto& viewed_node = static_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 reinterpret cast
            auto& move_subset = move_edge.subset();
            auto& viewed_type = types::infer_type(sdfg, sdfg.type(viewed_container), move_subset);
            types::Pointer final_type(viewed_type);
            if (type != final_type) {
                continue;
            }

            // Replace all uses of the view by the pointer
            for (auto& user : uses) {
                // Criterion: Must be dominated by the move
                if (!users.dominates(*move, *user)) {
                    continue;
                }
                // Criterion: Pointer and view are constant
                auto uses_between = users.all_uses_between(*move, *user);
                bool unsafe = false;
                for (auto& use : uses_between) {
                    if (use->use() != analysis::Use::MOVE) {
                        continue;
                    }
                    // Pointer is not constant
                    if (use->container() == viewed_container) {
                        unsafe = true;
                        break;
                    }
                    // View is reassigned
                    if (use->container() == container) {
                        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());

                auto use_graph = user->parent();

                // Criterion: Must not be a dereference memlet
                bool deref = false;
                for (auto& oedge : use_graph->out_edges(use_node)) {
                    if (oedge.type() == data_flow::MemletType::Dereference_Src ||
                        oedge.type() == data_flow::MemletType::Dereference_Dst) {
                        deref = true;
                        break;
                    }
                }
                if (deref) {
                    continue;
                }
                for (auto& iedge : use_graph->in_edges(use_node)) {
                    if (iedge.type() == data_flow::MemletType::Dereference_Src ||
                        iedge.type() == data_flow::MemletType::Dereference_Dst) {
                        deref = true;
                        break;
                    }
                }
                if (deref) {
                    continue;
                }

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

                // Step 2: Update edges
                for (auto& oedge : use_graph->out_edges(use_node)) {
                    // Compute new subset
                    data_flow::Subset new_subset;
                    for (auto dim : move_subset) {
                        new_subset.push_back(dim);
                    }

                    auto old_subset = oedge.subset();

                    // Handle first trailing dimensions
                    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;
                    for (auto dim : move_subset) {
                        new_subset.push_back(dim);
                    }

                    auto old_subset = iedge.subset();

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

daisytuner / sdfglib / 16440807098

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