20764569418

Committed 06 Jan 2026 10:50PM UTC coverage: 62.168% (+21.4%) from 40.764%

Build # 20764569418

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #433 from daisytuner/clang-coverage

updates clang coverage flags

Run Details

14988 of 24109 relevant lines covered (62.17%)

88.57 hits per line

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

79.46

/src/passes/dataflow/redundant_array_elimination.cpp

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

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

namespace sdfg {
namespace passes {

RedundantArrayElimination::RedundantArrayElimination()
    : Pass() {

      };

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

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

    auto& sdfg = builder.subject();
    auto& users = analysis_manager.get<analysis::Users>();
    for (auto& name : sdfg.containers()) {
        // Criterion: Only transients
        if (!sdfg.is_transient(name)) {
            continue;
        }
        if (users.num_moves(name) > 0 || users.num_views(name) > 0) {
            continue;
        }
        if (users.num_writes(name) != 1) {
            continue;
        }
        std::unique_ptr<types::IType> type = sdfg.type(name).clone();
        if (dynamic_cast<const types::Array*>(type.get()) == nullptr) {
            continue;
        }

        // Criterion: Data must depend on externals
        auto write = *users.writes(name).begin();
        auto write_node = dynamic_cast<data_flow::AccessNode*>(write->element());
        auto& graph = write_node->get_parent();
        if (graph.in_degree(*write_node) == 0) {
            continue;
        }
        auto& write_edge = *graph.in_edges(*write_node).begin();
        auto& write_subset = write_edge.subset();

        // Access nodes for write
        std::vector<symbolic::Symbol> input_symbols;
        for (auto& e : graph.in_edges(write_edge.src())) {
            auto& src = e.src();
            if (graph.in_degree(src) != 0) {
                continue;
            }
            auto access_node = dynamic_cast<data_flow::AccessNode*>(&src);
            input_symbols.push_back(symbolic::symbol(access_node->data()));
            for (auto& subset : e.subset()) {
                auto atoms = symbolic::atoms(subset);
                for (auto& atom : atoms) {
                    if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {
                        auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
                        input_symbols.push_back(symbol);
                    }
                }
            }
        }

        bool has_redundant_dimension = false;
        // Criterion: Data must be an Array
        uint depth = 0;
        while (auto atype = dynamic_cast<const types::Array*>(type.get())) {
            auto subset = write_subset[depth];
            auto atoms = symbolic::atoms(subset);
            bool dependency_exists = false;

            for (auto& atom : atoms) {
                if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {
                    auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);
                    for (auto& input_symbol : input_symbols) {
                        if (symbolic::eq(symbol, input_symbol)) {
                            dependency_exists = true;
                            break;
                        }
                    }
                    if (dependency_exists) {
                        break;
                    }
                }
            }
            if (!dependency_exists) {
                has_redundant_dimension = true;
                break;
            }
            type = atype->element_type().clone();
            depth++;
        }

        if (!has_redundant_dimension) {
            continue;
        }

        // Construct new type
        auto atype = static_cast<const types::Array*>(type.get());
        std::unique_ptr<types::IType> inner_type = atype->element_type().clone();
        std::unique_ptr<types::IType> new_type = types::recombine_array_type(sdfg.type(name), depth, *inner_type.get());

        // Replace data type
        builder.change_type(name, *new_type.get());

        // Replace all reads
        for (auto& user : users.reads(name)) {
            auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());
            if (access_node == nullptr) {
                throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");
            }

            auto& graph = access_node->get_parent();
            for (auto& oedge : graph.out_edges(*access_node)) {
                auto subset = oedge.subset();
                subset.erase(subset.begin() + depth);
                oedge.set_subset(subset);
                oedge.set_base_type(*new_type);
            }
        }
        // Replace all writes
        for (auto& user : users.writes(name)) {
            auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());
            if (access_node == nullptr) {
                throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");
            }

            auto& graph = access_node->get_parent();
            for (auto& iedge : graph.in_edges(*access_node)) {
                auto subset = iedge.subset();
                subset.erase(subset.begin() + depth);
                iedge.set_subset(subset);
                iedge.set_base_type(*new_type);
            }
        }

        applied = true;
    }

    analysis_manager.invalidate_all();

    return applied;
};

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/dataflow/redundant_array_elimination.h"
2
3	#include "sdfg/analysis/users.h"
4	#include "sdfg/types/utils.h"
5
6	namespace sdfg {
7	namespace passes {
8
9	RedundantArrayElimination::RedundantArrayElimination()
10	: Pass() {	4✔
11
12	};	4✔
13
14	std::string RedundantArrayElimination::name() { return "RedundantArrayElimination"; };	×
15
16	bool RedundantArrayElimination::
17	run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	4✔
18	bool applied = false;	4✔
19
20	auto& sdfg = builder.subject();	4✔
21	auto& users = analysis_manager.get<analysis::Users>();	4✔
22	for (auto& name : sdfg.containers()) {	27✔
23	// Criterion: Only transients
24	if (!sdfg.is_transient(name)) {	27✔
25	continue;	4✔
26	}	4✔
27	if (users.num_moves(name) > 0 \|\| users.num_views(name) > 0) {	23✔
28	continue;	×
29	}	×
30	if (users.num_writes(name) != 1) {	23✔
31	continue;	19✔
32	}	19✔
33	std::unique_ptr<types::IType> type = sdfg.type(name).clone();	4✔
34	if (dynamic_cast<const types::Array*>(type.get()) == nullptr) {	4✔
35	continue;	×
36	}	×
37
38	// Criterion: Data must depend on externals
39	auto write = *users.writes(name).begin();	4✔
40	auto write_node = dynamic_cast<data_flow::AccessNode*>(write->element());	4✔
41	auto& graph = write_node->get_parent();	4✔
42	if (graph.in_degree(*write_node) == 0) {	4✔
43	continue;	×
44	}	×
45	auto& write_edge = graph.in_edges(write_node).begin();	4✔
46	auto& write_subset = write_edge.subset();	4✔
47
48	// Access nodes for write
49	std::vector<symbolic::Symbol> input_symbols;	4✔
50	for (auto& e : graph.in_edges(write_edge.src())) {	4✔
51	auto& src = e.src();	4✔
52	if (graph.in_degree(src) != 0) {	4✔
53	continue;	×
54	}	×
55	auto access_node = dynamic_cast<data_flow::AccessNode*>(&src);	4✔
56	input_symbols.push_back(symbolic::symbol(access_node->data()));	4✔
57	for (auto& subset : e.subset()) {	16✔
58	auto atoms = symbolic::atoms(subset);	16✔
59	for (auto& atom : atoms) {	16✔
60	if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {	16✔
61	auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	16✔
62	input_symbols.push_back(symbol);	16✔
63	}	16✔
64	}	16✔
65	}	16✔
66	}	4✔
67
68	bool has_redundant_dimension = false;	4✔
69	// Criterion: Data must be an Array
70	uint depth = 0;	4✔
71	while (auto atype = dynamic_cast<const types::Array*>(type.get())) {	12✔
72	auto subset = write_subset[depth];	11✔
73	auto atoms = symbolic::atoms(subset);	11✔
74	bool dependency_exists = false;	11✔
75
76	for (auto& atom : atoms) {	11✔
77	if (SymEngine::is_a<SymEngine::Symbol>(*atom)) {	11✔
78	auto symbol = SymEngine::rcp_static_cast<const SymEngine::Symbol>(atom);	11✔
79	for (auto& input_symbol : input_symbols) {	40✔
80	if (symbolic::eq(symbol, input_symbol)) {	40✔
81	dependency_exists = true;	8✔
82	break;	8✔
83	}	8✔
84	}	40✔
85	if (dependency_exists) {	11✔
86	break;	8✔
87	}	8✔
88	}	11✔
89	}	11✔
90	if (!dependency_exists) {	11✔
91	has_redundant_dimension = true;	3✔
92	break;	3✔
93	}	3✔
94	type = atype->element_type().clone();	8✔
95	depth++;	8✔
96	}	8✔
97
98	if (!has_redundant_dimension) {	4✔
99	continue;	1✔
100	}	1✔
101
102	// Construct new type
103	auto atype = static_cast<const types::Array*>(type.get());	3✔
104	std::unique_ptr<types::IType> inner_type = atype->element_type().clone();	3✔
105	std::unique_ptr<types::IType> new_type = types::recombine_array_type(sdfg.type(name), depth, *inner_type.get());	3✔
106
107	// Replace data type
108	builder.change_type(name, *new_type.get());	3✔
109
110	// Replace all reads
111	for (auto& user : users.reads(name)) {	3✔
112	auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());	×
113	if (access_node == nullptr) {	×
114	throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");	×
115	}	×
116
117	auto& graph = access_node->get_parent();	×
118	for (auto& oedge : graph.out_edges(*access_node)) {	×
119	auto subset = oedge.subset();	×
120	subset.erase(subset.begin() + depth);	×
121	oedge.set_subset(subset);	×
122	oedge.set_base_type(*new_type);	×
123	}	×
124	}	×
125	// Replace all writes
126	for (auto& user : users.writes(name)) {	3✔
127	auto access_node = dynamic_cast<data_flow::AccessNode*>(user->element());	3✔
128	if (access_node == nullptr) {	3✔
129	throw InvalidSDFGException("RedundantArrayElimination: Expected AccessNode");	×
130	}	×
131
132	auto& graph = access_node->get_parent();	3✔
133	for (auto& iedge : graph.in_edges(*access_node)) {	3✔
134	auto subset = iedge.subset();	3✔
135	subset.erase(subset.begin() + depth);	3✔
136	iedge.set_subset(subset);	3✔
137	iedge.set_base_type(*new_type);	3✔
138	}	3✔
139	}	3✔
140
141	applied = true;	3✔
142	}	3✔
143
144	analysis_manager.invalidate_all();	4✔
145
146	return applied;	4✔
147	};	4✔
148
149	} // namespace passes
150	} // namespace sdfg

daisytuner / sdfglib / 20764569418

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