15238257521

Committed 25 May 2025 01:14PM UTC coverage: 60.342% (-0.1%) from 60.473%

Build # 15238257521

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #31 from daisytuner/exception-handling

Exception handling

Run Details

18 of 60 new or added lines in 17 files covered. (30.0%)

1 existing line in 1 file now uncovered.

8052 of 13344 relevant lines covered (60.34%)

102.27 hits per line

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

84.27

/src/passes/dataflow/redundant_array_elimination.cpp

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

#include <cassert>

#include "sdfg/data_flow/access_node.h"
#include "sdfg/structured_control_flow/for.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/types/array.h"
#include "sdfg/types/type.h"
#include "sdfg/types/utils.h"
#include "symengine/symbol.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.moves(name).empty() || !users.views(name).empty()) {
            continue;
        }
        if (users.writes(name).size() != 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)[0];
        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);
            }
        }
        // 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);
            }
        }

        applied = true;
    }

    analysis_manager.invalidate_all();

    return applied;
};

}  // namespace passes
}  // namespace sdfg

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

daisytuner / sdfglib / 15238257521

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