15241626882

Committed 25 May 2025 08:19PM UTC coverage: 60.336% (-0.006%) from 60.342%

Build # 15241626882

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #34 from daisytuner/users-analysis

Releaxes domination and post-domination requirements of users analysis

Run Details

7 of 19 new or added lines in 1 file covered. (36.84%)

2 existing lines in 1 file now uncovered.

8050 of 13342 relevant lines covered (60.34%)

97.38 hits per line

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

61.39

/src/passes/dataflow/view_propagation.cpp

#include "sdfg/passes/dataflow/view_propagation.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 by their original pointers
    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;
        }
        auto& type = sdfg.type(container);
        if (!dynamic_cast<const types::Pointer*>(&type)) {
            continue;
        }
        if (sdfg.is_external(container)) {
            continue;
        }

        // Collect all moves of the pointer
        auto moves = users.moves(container);
        if (moves.empty() || !users.views(container).empty()) {
            continue;
        }
        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& graph = *move->parent();
            auto& edge = *graph.in_edges(access_node).begin();

            // The original pointer
            auto& viewed_node = dynamic_cast<const data_flow::AccessNode&>(edge.src());
            auto& viewed_container = viewed_node.data();
            auto& viewed_subset = edge.subset();
            if (edge.src_conn() != "void") {
                continue;
            }
            if (symbolic::is_pointer(symbolic::symbol(viewed_container))) {
                continue;
            }
            types::Pointer viewed_type(
                types::infer_type(sdfg, sdfg.type(viewed_container), viewed_subset));
            if (viewed_type != type) {
                continue;
            }

            // Iterate over all uses of the viewing container
            // Replace the view by the original pointer if possible
            for (auto& user : uses) {
                if (user->use() == analysis::Use::MOVE || user->use() == analysis::Use::VIEW) {
                    continue;
                }
                // Criterion: The assignment of the view must dominate the use of the view
                if (!users.dominates(*move, *user)) {
                    continue;
                }
                // Criterion: No pointer operations between the assignment and the use
                auto uses_between = users.all_uses_between(*move, *user);
                bool moving_pointers = false;
                for (auto& use : uses_between) {
                    if (use->use() != analysis::Use::MOVE) {
                        continue;
                    }
                    // Viewed container is not constant
                    if (use->container() == viewed_container) {
                        moving_pointers = true;
                        break;
                    }
                    // Moved container is not constant
                    if (use->container() == container) {
                        moving_pointers = true;
                        break;
                    }

                    // Unsafe pointer operations
                    auto& move_node = dynamic_cast<data_flow::AccessNode&>(*use->element());
                    auto& move_graph = *use->parent();
                    auto& move_edge = *move_graph.in_edges(move_node).begin();
                    auto& view_node = dynamic_cast<data_flow::AccessNode&>(move_edge.src());
                    if (move_edge.dst_conn() == "void" ||
                        symbolic::is_pointer(symbolic::symbol(view_node.data()))) {
                        moving_pointers = true;
                        break;
                    }
                }
                if (moving_pointers) {
                    continue;
                }

                // Replace the view by the original pointer
                if (auto use_node = dynamic_cast<data_flow::AccessNode*>(user->element())) {
                    auto use_graph = user->parent();
                    use_node->data() = viewed_container;

                    // Update subsets
                    for (auto& oedge : use_graph->out_edges(*use_node)) {
                        auto& old_subset = oedge.subset();

                        // Add leading dimensions
                        data_flow::Subset new_subset(viewed_subset.begin(),
                                                     viewed_subset.end() - 1);

                        // Accumulate overlapping dimension
                        auto& dim = old_subset[0];
                        auto& alias_dim = viewed_subset.back();
                        auto new_dim = symbolic::add(alias_dim, dim);
                        new_subset.push_back(new_dim);

                        // Add trailing dimensions
                        for (size_t i = 1; i < old_subset.size(); i++) {
                            auto& old_dim = old_subset[i];
                            new_subset.push_back(old_dim);
                        }

                        oedge.subset() = new_subset;
                    }
                    for (auto& iedge : use_graph->in_edges(*use_node)) {
                        auto& old_subset = iedge.subset();

                        // Add leading dimensions
                        data_flow::Subset new_subset(viewed_subset.begin(),
                                                     viewed_subset.end() - 1);

                        // Accumulate overlapping dimension
                        auto& dim = old_subset[0];
                        auto& alias_dim = viewed_subset.back();
                        auto new_dim = symbolic::add(alias_dim, dim);
                        new_subset.push_back(new_dim);

                        // Add trailing dimensions
                        for (size_t i = 1; i < old_subset.size(); i++) {
                            auto& old_dim = old_subset[i];
                            new_subset.push_back(old_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	namespace sdfg {
4	namespace passes {
5
6	ViewPropagation::ViewPropagation()	4✔
7	: Pass(){	4✔
8
9	};	4✔
10
11	std::string ViewPropagation::name() { return "ViewPropagation"; };	×
12
13	bool ViewPropagation::run_pass(builder::StructuredSDFGBuilder& builder,	4✔
14	analysis::AnalysisManager& analysis_manager) {
15	bool applied = false;	4✔
16
17	auto& sdfg = builder.subject();	4✔
18
19	// Replaces all views by their original pointers
20	auto& users = analysis_manager.get<analysis::Users>();	4✔
21	std::unordered_set<std::string> reduced;	4✔
22	for (auto& container : sdfg.containers()) {	27✔
23	if (reduced.find(container) != reduced.end()) {	23✔
24	continue;	1✔
25	}
26	auto& type = sdfg.type(container);	22✔
27	if (!dynamic_cast<const types::Pointer*>(&type)) {	22✔
28	continue;	15✔
29	}
30	if (sdfg.is_external(container)) {	7✔
31	continue;	×
32	}
33
34	// Collect all moves of the pointer
35	auto moves = users.moves(container);	7✔
36	if (moves.empty() \|\| !users.views(container).empty()) {	7✔
37	continue;	6✔
38	}
39	auto uses = users.uses(container);	1✔
40	for (auto& move : moves) {	2✔
41	// Location of where the view is created
42	auto& access_node = dynamic_cast<data_flow::AccessNode&>(*move->element());	1✔
43	auto& graph = *move->parent();	1✔
44	auto& edge = *graph.in_edges(access_node).begin();	1✔
45
46	// The original pointer
47	auto& viewed_node = dynamic_cast<const data_flow::AccessNode&>(edge.src());	1✔
48	auto& viewed_container = viewed_node.data();	1✔
49	auto& viewed_subset = edge.subset();	1✔
50	if (edge.src_conn() != "void") {	1✔
51	continue;	×
52	}
53	if (symbolic::is_pointer(symbolic::symbol(viewed_container))) {	1✔
54	continue;	×
55	}
56	types::Pointer viewed_type(	1✔
57	types::infer_type(sdfg, sdfg.type(viewed_container), viewed_subset));	1✔
58	if (viewed_type != type) {	1✔
59	continue;	×
60	}
61
62	// Iterate over all uses of the viewing container
63	// Replace the view by the original pointer if possible
64	for (auto& user : uses) {	3✔
65	if (user->use() == analysis::Use::MOVE \|\| user->use() == analysis::Use::VIEW) {	2✔
66	continue;	1✔
67	}
68	// Criterion: The assignment of the view must dominate the use of the view
69	if (!users.dominates(move, user)) {	1✔
70	continue;	×
71	}
72	// Criterion: No pointer operations between the assignment and the use
73	auto uses_between = users.all_uses_between(move, user);	1✔
74	bool moving_pointers = false;	1✔
75	for (auto& use : uses_between) {	1✔
UNCOV 76	if (use->use() != analysis::Use::MOVE) {	×
UNCOV 77	continue;	×
78	}
79	// Viewed container is not constant
80	if (use->container() == viewed_container) {	×
81	moving_pointers = true;	×
82	break;	×
83	}
84	// Moved container is not constant
85	if (use->container() == container) {	×
86	moving_pointers = true;	×
87	break;	×
88	}
89
90	// Unsafe pointer operations
91	auto& move_node = dynamic_cast<data_flow::AccessNode&>(*use->element());	×
92	auto& move_graph = *use->parent();	×
93	auto& move_edge = *move_graph.in_edges(move_node).begin();	×
94	auto& view_node = dynamic_cast<data_flow::AccessNode&>(move_edge.src());	×
95	if (move_edge.dst_conn() == "void" \|\|	×
96	symbolic::is_pointer(symbolic::symbol(view_node.data()))) {	×
97	moving_pointers = true;	×
98	break;	×
99	}
100	}
101	if (moving_pointers) {	1✔
102	continue;	×
103	}
104
105	// Replace the view by the original pointer
106	if (auto use_node = dynamic_cast<data_flow::AccessNode*>(user->element())) {	1✔
107	auto use_graph = user->parent();	1✔
108	use_node->data() = viewed_container;	1✔
109
110	// Update subsets
111	for (auto& oedge : use_graph->out_edges(*use_node)) {	1✔
112	auto& old_subset = oedge.subset();	×
113
114	// Add leading dimensions
115	data_flow::Subset new_subset(viewed_subset.begin(),	×
116	viewed_subset.end() - 1);	×
117
118	// Accumulate overlapping dimension
119	auto& dim = old_subset[0];	×
120	auto& alias_dim = viewed_subset.back();	×
121	auto new_dim = symbolic::add(alias_dim, dim);	×
122	new_subset.push_back(new_dim);	×
123
124	// Add trailing dimensions
125	for (size_t i = 1; i < old_subset.size(); i++) {	×
126	auto& old_dim = old_subset[i];	×
127	new_subset.push_back(old_dim);	×
128	}	×
129
130	oedge.subset() = new_subset;	×
131	}	×
132	for (auto& iedge : use_graph->in_edges(*use_node)) {	2✔
133	auto& old_subset = iedge.subset();	1✔
134
135	// Add leading dimensions
136	data_flow::Subset new_subset(viewed_subset.begin(),	2✔
137	viewed_subset.end() - 1);	1✔
138
139	// Accumulate overlapping dimension
140	auto& dim = old_subset[0];	1✔
141	auto& alias_dim = viewed_subset.back();	1✔
142	auto new_dim = symbolic::add(alias_dim, dim);	1✔
143	new_subset.push_back(new_dim);	1✔
144
145	// Add trailing dimensions
146	for (size_t i = 1; i < old_subset.size(); i++) {	1✔
147	auto& old_dim = old_subset[i];	×
148	new_subset.push_back(old_dim);	×
149	}	×
150
151	iedge.subset() = new_subset;	1✔
152	}	1✔
153
154	applied = true;	1✔
155	reduced.insert(viewed_container);	1✔
156	}	1✔
157	}	1✔
158	}	1✔
159	}	7✔
160
161	return applied;	4✔
162	};	4✔
163
164	} // namespace passes
165	} // namespace sdfg

daisytuner / sdfglib / 15241626882

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