daisytuner/sdfglib | Build 16006022003 | src/passes/dataflow/constant_elimination.cpp | Coveralls

NEW

10

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

×

NEW

12

std::unordered_set<analysis::User*> inputs(const std::string& container,

×

NEW

15

    std::unordered_set<analysis::User*> inputs;

×

NEW

17

    auto& graph = access_node->get_parent();

×

NEW

18

    data_flow::Tasklet* tasklet = nullptr;

×

NEW

19

    for (auto& iedge : graph.in_edges(*access_node)) {

×

NEW

20

        tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());

×

NEW

22

    if (tasklet == nullptr) {

×

NEW

23

        return {};

×

NEW

25

    for (auto& iedge : graph.in_edges(*tasklet)) {

×

NEW

26

        auto& src_node = static_cast<data_flow::AccessNode&>(iedge.src());

×

NEW

27

        inputs.insert(users.get_user(src_node.data(), &src_node, analysis::Use::READ));

×

NEW

29

    return inputs;

×

NEW

30

×

NEW

32

std::unordered_set<analysis::User*> inputs(const std::string& container,

×

NEW

35

    std::unordered_set<analysis::User*> inputs;

×

NEW

36

    auto& assign = transition->assignments().at(symbolic::symbol(container));

×

NEW

37

    for (auto& sym : symbolic::atoms(assign)) {

×

NEW

38

        inputs.insert(users.get_user(sym->get_name(), transition, analysis::Use::READ));

×

NEW

40

    return inputs;

×

NEW

41

×

NEW

43

std::unordered_set<analysis::User*> inputs(analysis::User& user, analysis::Users& users) {

×

NEW

44

    if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user.element())) {

×

NEW

45

        return inputs(user.container(), access_node, users);

×

NEW

46

    } else if (auto transition =

×

NEW

47

                   dynamic_cast<structured_control_flow::Transition*>(user.element())) {

×

NEW

48

        return inputs(user.container(), transition, users);

×

NEW

50

        return {};

×

NEW

52

×

NEW

54

bool ConstantElimination::run_pass(builder::StructuredSDFGBuilder& builder,

×

NEW

56

    bool applied = false;

×

NEW

58

    auto& sdfg = builder.subject();

×

NEW

59

    auto& users = analysis_manager.get<analysis::Users>();

×

NEW

60

    auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();

×

NEW

62

    std::unordered_set<std::string> dead;

×

NEW

63

    for (auto& name : sdfg.containers()) {

×

NEW

65

        if (!users.views(name).empty() || !users.moves(name).empty()) {

×

NEW

66

            continue;

×

NEW

70

        auto defines = data_dependency_analysis.definitions(name);

×

NEW

71

        if (defines.size() != 2) {

×

NEW

72

            continue;

×

NEW

75

        auto define1 = defines.begin()->first;

×

NEW

76

        auto define2 = (++defines.begin())->first;

×

NEW

79

        auto subsets1 = define1->subsets();

×

NEW

80

        auto subsets2 = define2->subsets();

×

NEW

81

        if (subsets1.size() != 1 || subsets2.size() != 1) {

×

NEW

82

            continue;

×

NEW

84

        if (subsets1.begin()->size() != subsets2.begin()->size()) {

×

NEW

85

            continue;

×

NEW

87

        bool constant_write = true;

×

NEW

88

        for (size_t i = 0; i < subsets1.begin()->size(); i++) {

×

NEW

89

            auto dim1 = subsets1.begin()->at(i);

×

NEW

90

            auto dim2 = subsets2.begin()->at(i);

×

NEW

91

            if (!symbolic::eq(dim1, dim2)) {

×

NEW

92

                constant_write = false;

×

NEW

93

                break;

×

NEW

95

            if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {

×

NEW

96

                constant_write = false;

×

NEW

97

                break;

×

NEW

99

×

NEW

100

        if (!constant_write) {

×

NEW

101

            continue;

×

NEW

105

        if (!users.dominates(*define1, *define2)) {

×

NEW

106

            std::swap(define1, define2);

×

NEW

107

×

NEW

108

        if (!users.dominates(*define1, *define2)) {

×

NEW

109

            continue;

×

NEW

113

        auto inputs1 = inputs(*define1, users);

×

NEW

114

        if (inputs1.empty()) {

×

NEW

115

            continue;

×

NEW

117

        auto inputs2 = inputs(*define2, users);

×

NEW

118

        if (inputs2.empty()) {

×

NEW

119

            continue;

×

NEW

121

        if (inputs1.size() != inputs2.size()) {

×

NEW

122

            continue;

×

NEW

124

        bool constant_inputs = true;

×

NEW

125

        for (auto& input : inputs1) {

×

NEW

127

            if (input->container() == name) {

×

NEW

128

                constant_inputs = false;

×

NEW

129

                break;

×

NEW

133

            if (!users.writes(input->container()).empty() ||

×

NEW

134

                !users.moves(input->container()).empty() ||

×

NEW

135

                !users.views(input->container()).empty()) {

×

NEW

136

                constant_inputs = false;

×

NEW

137

                break;

×

NEW

141

            analysis::User* input2 = nullptr;

×

NEW

142

            for (auto& inp : inputs2) {

×

NEW

143

                if (input->container() == inp->container()) {

×

NEW

144

                    input2 = inp;

×

NEW

145

                    break;

×

NEW

148

            if (input2 == nullptr) {

×

NEW

149

                constant_inputs = false;

×

NEW

150

                break;

×

NEW

154

            if (input->subsets().size() != 1 || input2->subsets().size() != 1) {

×

NEW

155

                constant_inputs = false;

×

NEW

156

                break;

×

NEW

159

            auto subset1 = *input->subsets().begin();

×

NEW

160

            auto subset2 = *input2->subsets().begin();

×

NEW

161

            if (subset1.size() != subset2.size()) {

×

NEW

162

                constant_inputs = false;

×

NEW

163

                break;

×

NEW

165

            for (size_t i = 0; i < subset1.size(); i++) {

×

NEW

166

                auto dim1 = subset1[i];

×

NEW

167

                auto dim2 = subset2[i];

×

NEW

168

                if (!symbolic::eq(dim1, dim2)) {

×

NEW

169

                    constant_inputs = false;

×

NEW

170

                    break;

×

NEW

172

                if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {

×

NEW

173

                    constant_inputs = false;

×

NEW

174

                    break;

×

NEW

176

×

NEW

177

×

NEW

178

        if (!constant_inputs) {

×

NEW

179

            continue;

×

NEW

183

        auto write = define2->element();

×

NEW

184

        if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write)) {

×

NEW

185

            transition->assignments().erase(symbolic::symbol(name));

×

NEW

186

        } else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write)) {

×

NEW

187

            auto& graph = access_node->get_parent();

×

NEW

188

            auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());

×

NEW

189

            builder.clear_node(block, *access_node);

×

NEW

190

×

NEW

191

        applied = true;

×

NEW

192

×

NEW

194

    return applied;

×

NEW

195

};

×

daisytuner / sdfglib / 16006022003

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

1	#include "sdfg/passes/dataflow/constant_elimination.h"
2
3	#include "sdfg/analysis/data_dependency_analysis.h"
4
5	namespace sdfg {
6	namespace passes {
7
8	ConstantElimination::ConstantElimination() : Pass() {};	1✔
9
NEW 10	std::string ConstantElimination::name() { return "ConstantElimination"; };	×
11
NEW 12	std::unordered_set<analysis::User*> inputs(const std::string& container,	×
13	data_flow::AccessNode* access_node,
14	analysis::Users& users) {
NEW 15	std::unordered_set<analysis::User*> inputs;	×
16
NEW 17	auto& graph = access_node->get_parent();	×
NEW 18	data_flow::Tasklet* tasklet = nullptr;	×
NEW 19	for (auto& iedge : graph.in_edges(*access_node)) {	×
NEW 20	tasklet = dynamic_cast<data_flow::Tasklet*>(&iedge.src());	×
21	}
NEW 22	if (tasklet == nullptr) {	×
NEW 23	return {};	×
24	}
NEW 25	for (auto& iedge : graph.in_edges(*tasklet)) {	×
NEW 26	auto& src_node = static_cast<data_flow::AccessNode&>(iedge.src());	×
NEW 27	inputs.insert(users.get_user(src_node.data(), &src_node, analysis::Use::READ));	×
28	}
NEW 29	return inputs;	×
NEW 30	}	×
31
NEW 32	std::unordered_set<analysis::User*> inputs(const std::string& container,	×
33	structured_control_flow::Transition* transition,
34	analysis::Users& users) {
NEW 35	std::unordered_set<analysis::User*> inputs;	×
NEW 36	auto& assign = transition->assignments().at(symbolic::symbol(container));	×
NEW 37	for (auto& sym : symbolic::atoms(assign)) {	×
NEW 38	inputs.insert(users.get_user(sym->get_name(), transition, analysis::Use::READ));	×
39	}
NEW 40	return inputs;	×
NEW 41	}	×
42
NEW 43	std::unordered_set<analysis::User*> inputs(analysis::User& user, analysis::Users& users) {	×
NEW 44	if (auto access_node = dynamic_cast<data_flow::AccessNode*>(user.element())) {	×
NEW 45	return inputs(user.container(), access_node, users);	×
NEW 46	} else if (auto transition =	×
NEW 47	dynamic_cast<structured_control_flow::Transition*>(user.element())) {	×
NEW 48	return inputs(user.container(), transition, users);	×
49	} else {
NEW 50	return {};	×
51	}
NEW 52	}	×
53
NEW 54	bool ConstantElimination::run_pass(builder::StructuredSDFGBuilder& builder,	×
55	analysis::AnalysisManager& analysis_manager) {
NEW 56	bool applied = false;	×
57
NEW 58	auto& sdfg = builder.subject();	×
NEW 59	auto& users = analysis_manager.get<analysis::Users>();	×
NEW 60	auto& data_dependency_analysis = analysis_manager.get<analysis::DataDependencyAnalysis>();	×
61
NEW 62	std::unordered_set<std::string> dead;	×
NEW 63	for (auto& name : sdfg.containers()) {	×
64	// Criterion: No aliases
NEW 65	if (!users.views(name).empty() \|\| !users.moves(name).empty()) {	×
NEW 66	continue;	×
67	}
68
69	// Criterion: Two definitions
NEW 70	auto defines = data_dependency_analysis.definitions(name);	×
NEW 71	if (defines.size() != 2) {	×
NEW 72	continue;	×
73	}
74
NEW 75	auto define1 = defines.begin()->first;	×
NEW 76	auto define2 = (++defines.begin())->first;	×
77
78	// Criterion: Identical define
NEW 79	auto subsets1 = define1->subsets();	×
NEW 80	auto subsets2 = define2->subsets();	×
NEW 81	if (subsets1.size() != 1 \|\| subsets2.size() != 1) {	×
NEW 82	continue;	×
83	}
NEW 84	if (subsets1.begin()->size() != subsets2.begin()->size()) {	×
NEW 85	continue;	×
86	}
NEW 87	bool constant_write = true;	×
NEW 88	for (size_t i = 0; i < subsets1.begin()->size(); i++) {	×
NEW 89	auto dim1 = subsets1.begin()->at(i);	×
NEW 90	auto dim2 = subsets2.begin()->at(i);	×
NEW 91	if (!symbolic::eq(dim1, dim2)) {	×
NEW 92	constant_write = false;	×
NEW 93	break;	×
94	}
NEW 95	if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {	×
NEW 96	constant_write = false;	×
NEW 97	break;	×
98	}
NEW 99	}	×
NEW 100	if (!constant_write) {	×
NEW 101	continue;	×
102	}
103
104	// Criterion: One dominates the other
NEW 105	if (!users.dominates(define1, define2)) {	×
NEW 106	std::swap(define1, define2);	×
NEW 107	}	×
NEW 108	if (!users.dominates(define1, define2)) {	×
NEW 109	continue;	×
110	}
111
112	// Criterion: Inputs of definition are constant
NEW 113	auto inputs1 = inputs(*define1, users);	×
NEW 114	if (inputs1.empty()) {	×
NEW 115	continue;	×
116	}
NEW 117	auto inputs2 = inputs(*define2, users);	×
NEW 118	if (inputs2.empty()) {	×
NEW 119	continue;	×
120	}
NEW 121	if (inputs1.size() != inputs2.size()) {	×
NEW 122	continue;	×
123	}
NEW 124	bool constant_inputs = true;	×
NEW 125	for (auto& input : inputs1) {	×
126	// Recursion
NEW 127	if (input->container() == name) {	×
NEW 128	constant_inputs = false;	×
NEW 129	break;	×
130	}
131
132	// input1 is constant
NEW 133	if (!users.writes(input->container()).empty() \|\|	×
NEW 134	!users.moves(input->container()).empty() \|\|	×
NEW 135	!users.views(input->container()).empty()) {	×
NEW 136	constant_inputs = false;	×
NEW 137	break;	×
138	}
139
140	// Find identical input in inputs2
NEW 141	analysis::User* input2 = nullptr;	×
NEW 142	for (auto& inp : inputs2) {	×
NEW 143	if (input->container() == inp->container()) {	×
NEW 144	input2 = inp;	×
NEW 145	break;	×
146	}
147	}
NEW 148	if (input2 == nullptr) {	×
NEW 149	constant_inputs = false;	×
NEW 150	break;	×
151	}
152
153	// same subsets
NEW 154	if (input->subsets().size() != 1 \|\| input2->subsets().size() != 1) {	×
NEW 155	constant_inputs = false;	×
NEW 156	break;	×
157	}
158
NEW 159	auto subset1 = *input->subsets().begin();	×
NEW 160	auto subset2 = *input2->subsets().begin();	×
NEW 161	if (subset1.size() != subset2.size()) {	×
NEW 162	constant_inputs = false;	×
NEW 163	break;	×
164	}
NEW 165	for (size_t i = 0; i < subset1.size(); i++) {	×
NEW 166	auto dim1 = subset1[i];	×
NEW 167	auto dim2 = subset2[i];	×
NEW 168	if (!symbolic::eq(dim1, dim2)) {	×
NEW 169	constant_inputs = false;	×
NEW 170	break;	×
171	}
NEW 172	if (!SymEngine::is_a<SymEngine::Integer>(*dim1)) {	×
NEW 173	constant_inputs = false;	×
NEW 174	break;	×
175	}
NEW 176	}	×
NEW 177	}	×
NEW 178	if (!constant_inputs) {	×
NEW 179	continue;	×
180	}
181
182	// Eliminate the dominated definition
NEW 183	auto write = define2->element();	×
NEW 184	if (auto transition = dynamic_cast<structured_control_flow::Transition*>(write)) {	×
NEW 185	transition->assignments().erase(symbolic::symbol(name));	×
NEW 186	} else if (auto access_node = dynamic_cast<data_flow::AccessNode*>(write)) {	×
NEW 187	auto& graph = access_node->get_parent();	×
NEW 188	auto& block = dynamic_cast<structured_control_flow::Block&>(*graph.get_parent());	×
NEW 189	builder.clear_node(block, *access_node);	×
NEW 190	}	×
NEW 191	applied = true;	×
NEW 192	}	×
193
NEW 194	return applied;	×
NEW 195	};	×
196
197	} // namespace passes
198	} // namespace sdfg

daisytuner / sdfglib / 16006022003

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