20034653178

Committed 08 Dec 2025 04:10PM UTC coverage: 61.892% (+0.1%) from 61.765%

Build # 20034653178

Build Type

push

github

Committed by

web-flow

Commit Message

Rework BlockSorting (#370)

* Rework BlockSorting

* Bugfixes for BlockSorting

Run Details

84 of 113 new or added lines in 1 file covered. (74.34%)

6 existing lines in 1 file now uncovered.

11473 of 18537 relevant lines covered (61.89%)

104.02 hits per line

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

73.2

/src/passes/code_motion/block_sorting.cpp

#include "sdfg/passes/code_motion/block_sorting.h"

#include <climits>
#include <string>
#include <unordered_set>
#include <utility>

#include "sdfg/analysis/analysis.h"
#include "sdfg/analysis/users.h"
#include "sdfg/builder/structured_sdfg_builder.h"
#include "sdfg/data_flow/access_node.h"
#include "sdfg/data_flow/data_flow_graph.h"
#include "sdfg/data_flow/library_node.h"
#include "sdfg/data_flow/library_nodes/stdlib/alloca.h"
#include "sdfg/data_flow/library_nodes/stdlib/calloc.h"
#include "sdfg/data_flow/library_nodes/stdlib/free.h"
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
#include "sdfg/data_flow/library_nodes/stdlib/memset.h"
#include "sdfg/data_flow/memlet.h"
#include "sdfg/data_flow/tasklet.h"
#include "sdfg/element.h"
#include "sdfg/structured_control_flow/block.h"
#include "sdfg/structured_control_flow/control_flow_node.h"
#include "sdfg/structured_control_flow/if_else.h"
#include "sdfg/structured_control_flow/return.h"
#include "sdfg/structured_control_flow/sequence.h"
#include "sdfg/structured_control_flow/structured_loop.h"
#include "sdfg/structured_control_flow/while.h"
#include "sdfg/visitor/structured_sdfg_visitor.h"

namespace sdfg {
namespace passes {

BlockSorting::BlockSorting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
    : visitor::StructuredSDFGVisitor(builder, analysis_manager) {};

bool BlockSorting::accept(structured_control_flow::Sequence& sequence) {
    if (sequence.size() == 0) {
        return false;
    }

    // Bubble up:
    size_t i;
    for (i = 0; i < sequence.size() - 1; i++) {
        // Skip assignments
        auto current_child = sequence.at(i);
        if (!current_child.second.empty()) {
            continue;
        }
        auto next_child = sequence.at(i + 1);
        if (!next_child.second.empty()) {
            continue;
        }

        // Sorting after return, break, and continue is useless
        if (dynamic_cast<structured_control_flow::Return*>(&current_child.first) ||
            dynamic_cast<structured_control_flow::Break*>(&current_child.first) ||
            dynamic_cast<structured_control_flow::Continue*>(&current_child.first)) {
            break;
        }

        // Childs must be a blocks
        auto* current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first);
        if (!current_block) {
            continue;
        }
        auto* next_block = dynamic_cast<structured_control_flow::Block*>(&next_child.first);
        if (!next_block) {
            continue;
        }

        // Check if current block has side-effects
        bool side_effect = false;
        for (auto* libnode : current_block->dataflow().library_nodes()) {
            if (this->is_libnode_side_effect_white_listed(libnode)) {
                continue;
            }
            if (libnode->side_effect()) {
                side_effect = true;
                break;
            }
        }
        if (side_effect) {
            continue;
        }

        // Check if happens-before relation allows swapping
        auto& users_analysis = this->analysis_manager_.get<analysis::Users>();
        analysis::UsersView current_users(users_analysis, *current_block);
        analysis::UsersView next_users(users_analysis, *next_block);
        bool safe = true;
        for (auto user : next_users.uses()) {
            if (current_users.uses(user->container()).size() > 0) {
                safe = false;
                break;
            }
        }
        if (!safe) {
            continue;
        }

        // Check if libnode/reference can be bubbled up
        if (!this->can_be_bubbled_up(*next_block)) {
            continue;
        }

        // Compare priority and order
        auto [current_prio, current_order] = this->get_prio_and_order(current_block);
        auto [next_prio, next_order] = this->get_prio_and_order(next_block);
        if (current_prio > next_prio) {
            continue;
        }
        if (current_prio == next_prio && current_order <= next_order) {
            continue;
        }

        // Swap blocks
        builder_.move_child(sequence, i + 1, sequence, i);
        return true; // Restart after modification
    }

    // Bubble down:
    for (size_t j = i; j > 0; j--) {
        // Skip assignments
        auto current_child = sequence.at(j);
        if (!current_child.second.empty()) {
            continue;
        }
        auto next_child = sequence.at(j - 1);
        if (!next_child.second.empty()) {
            continue;
        }

        // Childs must be a blocks
        auto* current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first);
        if (!current_block) {
            continue;
        }
        auto* next_block = dynamic_cast<structured_control_flow::Block*>(&next_child.first);
        if (!next_block) {
            continue;
        }

        // Check if current block has side-effects
        bool side_effect = false;
        for (auto* libnode : current_block->dataflow().library_nodes()) {
            if (this->is_libnode_side_effect_white_listed(libnode)) {
                continue;
            }
            if (libnode->side_effect()) {
                side_effect = true;
                break;
            }
        }
        if (side_effect) {
            continue;
        }

        // Check if happens-before relation allows swapping
        auto& users_analysis = this->analysis_manager_.get<analysis::Users>();
        analysis::UsersView current_users(users_analysis, *current_block);
        analysis::UsersView next_users(users_analysis, *next_block);
        bool safe = true;
        for (auto user : next_users.uses()) {
            if (current_users.uses(user->container()).size() > 0) {
                safe = false;
                break;
            }
        }
        if (!safe) {
            continue;
        }

        // Check if libnode can be bubbled down
        if (!this->can_be_bubbled_down(*next_block)) {
            continue;
        }

        // Compare priority and order
        auto [current_prio, current_order] = this->get_prio_and_order(current_block);
        auto [next_prio, next_order] = this->get_prio_and_order(next_block);
        if (current_prio > next_prio) {
            continue;
        }
        if (current_prio == next_prio && current_order <= next_order) {
            continue;
        }

        // Swap blocks
        builder_.move_child(sequence, j - 1, sequence, j);
        return true; // Restart after modification
    }

    return false;
}

bool BlockSorting::is_libnode_side_effect_white_listed(data_flow::LibraryNode* libnode) {
    return dynamic_cast<stdlib::AllocaNode*>(libnode) || dynamic_cast<stdlib::CallocNode*>(libnode) ||
           dynamic_cast<stdlib::FreeNode*>(libnode) || dynamic_cast<stdlib::MallocNode*>(libnode) ||
           dynamic_cast<stdlib::MemsetNode*>(libnode);
}

bool BlockSorting::can_be_bubbled_up(structured_control_flow::Block& block) {
    if (this->is_reference_block(block)) {
        return true;
    }

    if (this->is_libnode_block(block)) {
        auto* libnode = *block.dataflow().library_nodes().begin();
        return dynamic_cast<stdlib::AllocaNode*>(libnode) || dynamic_cast<stdlib::CallocNode*>(libnode) ||
               dynamic_cast<stdlib::MallocNode*>(libnode) || dynamic_cast<stdlib::MemsetNode*>(libnode);
    }

    return false;
}

bool BlockSorting::can_be_bubbled_down(structured_control_flow::Block& block) {
    if (!this->is_libnode_block(block)) {
        return false;
    }
    auto* libnode = *block.dataflow().library_nodes().begin();
    return dynamic_cast<stdlib::FreeNode*>(libnode);
}

std::pair<int, std::string> BlockSorting::get_prio_and_order(structured_control_flow::Block* block) {
    if (this->is_libnode_block(*block)) {
        auto* libnode = *block->dataflow().library_nodes().begin();
        if (dynamic_cast<stdlib::AllocaNode*>(libnode) || dynamic_cast<stdlib::CallocNode*>(libnode) ||
            dynamic_cast<stdlib::FreeNode*>(libnode) || dynamic_cast<stdlib::MallocNode*>(libnode)) {
            auto& oedge = *block->dataflow().out_edges(*libnode).begin();
            auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
            return {300, dst.data()};
        } else if (dynamic_cast<stdlib::MemsetNode*>(libnode)) {
            auto& oedge = *block->dataflow().out_edges(*libnode).begin();
            auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
            return {200, dst.data()};
        }
    } else if (this->is_reference_block(*block)) {
        return {100, ""};
    }

    return {INT_MIN, ""};
}

bool BlockSorting::is_reference_block(structured_control_flow::Block& block) {
    auto& dfg = block.dataflow();
    if (dfg.nodes().size() != 2) {
        return false;
    }
    if (dfg.edges().size() != 1) {
        return false;
    }
    auto& edge = *dfg.edges().begin();
    if (edge.type() != data_flow::MemletType::Reference && edge.type() != data_flow::MemletType::Dereference_Src &&
        edge.type() != data_flow::MemletType::Dereference_Dst) {
        return false;
    }
    return true;
}

bool BlockSorting::is_libnode_block(structured_control_flow::Block& next_block) {
    auto& next_dfg = next_block.dataflow();
    if (next_dfg.library_nodes().size() != 1) {
        return false;
    }
    auto* libnode = *next_dfg.library_nodes().begin();
    if (next_dfg.edges().size() != libnode->inputs().size() + libnode->outputs().size()) {
        return false;
    }
    return true;
}

} // namespace passes
} // namespace sdfg

1	#include "sdfg/passes/code_motion/block_sorting.h"
2
3	#include <climits>
4	#include <string>
5	#include <unordered_set>
6	#include <utility>
7
8	#include "sdfg/analysis/analysis.h"
9	#include "sdfg/analysis/users.h"
10	#include "sdfg/builder/structured_sdfg_builder.h"
11	#include "sdfg/data_flow/access_node.h"
12	#include "sdfg/data_flow/data_flow_graph.h"
13	#include "sdfg/data_flow/library_node.h"
14	#include "sdfg/data_flow/library_nodes/stdlib/alloca.h"
15	#include "sdfg/data_flow/library_nodes/stdlib/calloc.h"
16	#include "sdfg/data_flow/library_nodes/stdlib/free.h"
17	#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
18	#include "sdfg/data_flow/library_nodes/stdlib/memset.h"
19	#include "sdfg/data_flow/memlet.h"
20	#include "sdfg/data_flow/tasklet.h"
21	#include "sdfg/element.h"
22	#include "sdfg/structured_control_flow/block.h"
23	#include "sdfg/structured_control_flow/control_flow_node.h"
24	#include "sdfg/structured_control_flow/if_else.h"
25	#include "sdfg/structured_control_flow/return.h"
26	#include "sdfg/structured_control_flow/sequence.h"
27	#include "sdfg/structured_control_flow/structured_loop.h"
28	#include "sdfg/structured_control_flow/while.h"
29	#include "sdfg/visitor/structured_sdfg_visitor.h"
30
31	namespace sdfg {
32	namespace passes {
33
34	BlockSorting::BlockSorting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)	5✔
35	: visitor::StructuredSDFGVisitor(builder, analysis_manager) {};	5✔
36
37	bool BlockSorting::accept(structured_control_flow::Sequence& sequence) {	5✔
38	if (sequence.size() == 0) {	5✔
39	return false;	×
40	}
41
42	// Bubble up:
43	size_t i;
44	for (i = 0; i < sequence.size() - 1; i++) {	6✔
45	// Skip assignments
46	auto current_child = sequence.at(i);	5✔
47	if (!current_child.second.empty()) {	5✔
NEW 48	continue;	×
49	}
50	auto next_child = sequence.at(i + 1);	5✔
51	if (!next_child.second.empty()) {	5✔
NEW 52	continue;	×
53	}
54
55	// Sorting after return, break, and continue is useless
56	if (dynamic_cast<structured_control_flow::Return*>(&current_child.first) \|\|	10✔
57	dynamic_cast<structured_control_flow::Break*>(&current_child.first) \|\|	5✔
58	dynamic_cast<structured_control_flow::Continue*>(&current_child.first)) {	5✔
NEW 59	break;	×
60	}
61
62	// Childs must be a blocks
63	auto* current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first);	5✔
64	if (!current_block) {	5✔
UNCOV 65	continue;	×
66	}
67	auto* next_block = dynamic_cast<structured_control_flow::Block*>(&next_child.first);	5✔
68	if (!next_block) {	5✔
69	continue;	×
70	}
71
72	// Check if current block has side-effects
73	bool side_effect = false;	5✔
74	for (auto* libnode : current_block->dataflow().library_nodes()) {	7✔
75	if (this->is_libnode_side_effect_white_listed(libnode)) {	2✔
76	continue;	2✔
77	}
NEW 78	if (libnode->side_effect()) {	×
NEW 79	side_effect = true;	×
NEW 80	break;	×
81	}
82	}
83	if (side_effect) {	5✔
UNCOV 84	continue;	×
85	}
86
87	// Check if happens-before relation allows swapping
88	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	5✔
89	analysis::UsersView current_users(users_analysis, *current_block);	5✔
90	analysis::UsersView next_users(users_analysis, *next_block);	5✔
91	bool safe = true;	5✔
92	for (auto user : next_users.uses()) {	12✔
93	if (current_users.uses(user->container()).size() > 0) {	7✔
NEW 94	safe = false;	×
NEW 95	break;	×
96	}
97	}
98	if (!safe) {	5✔
NEW 99	continue;	×
100	}
101
102	// Check if libnode/reference can be bubbled up
103	if (!this->can_be_bubbled_up(*next_block)) {	5✔
NEW 104	continue;	×
105	}
106
107	// Compare priority and order
108	auto [current_prio, current_order] = this->get_prio_and_order(current_block);	5✔
109	auto [next_prio, next_order] = this->get_prio_and_order(next_block);	5✔
110	if (current_prio > next_prio) {	10✔
111	continue;	1✔
112	}
113	if (current_prio == next_prio && current_order <= next_order) {	8✔
NEW 114	continue;	×
115	}
116
117	// Swap blocks
118	builder_.move_child(sequence, i + 1, sequence, i);	4✔
119	return true; // Restart after modification	4✔
120	}	5✔
121
122	// Bubble down:
123	for (size_t j = i; j > 0; j--) {	1✔
124	// Skip assignments
125	auto current_child = sequence.at(j);	1✔
126	if (!current_child.second.empty()) {	1✔
NEW 127	continue;	×
128	}
129	auto next_child = sequence.at(j - 1);	1✔
130	if (!next_child.second.empty()) {	1✔
NEW 131	continue;	×
132	}
133
134	// Childs must be a blocks
135	auto* current_block = dynamic_cast<structured_control_flow::Block*>(&current_child.first);	1✔
136	if (!current_block) {	1✔
NEW 137	continue;	×
138	}
139	auto* next_block = dynamic_cast<structured_control_flow::Block*>(&next_child.first);	1✔
140	if (!next_block) {	1✔
NEW 141	continue;	×
142	}
143
144	// Check if current block has side-effects
145	bool side_effect = false;	1✔
146	for (auto* libnode : current_block->dataflow().library_nodes()) {	1✔
NEW 147	if (this->is_libnode_side_effect_white_listed(libnode)) {	×
UNCOV 148	continue;	×
149	}
NEW 150	if (libnode->side_effect()) {	×
NEW 151	side_effect = true;	×
NEW 152	break;	×
153	}
154	}
155	if (side_effect) {	1✔
UNCOV 156	continue;	×
157	}
158
159	// Check if happens-before relation allows swapping
160	auto& users_analysis = this->analysis_manager_.get<analysis::Users>();	1✔
161	analysis::UsersView current_users(users_analysis, *current_block);	1✔
162	analysis::UsersView next_users(users_analysis, *next_block);	1✔
163	bool safe = true;	1✔
164	for (auto user : next_users.uses()) {	3✔
165	if (current_users.uses(user->container()).size() > 0) {	2✔
166	safe = false;	×
167	break;	×
168	}
169	}
170	if (!safe) {	1✔
171	continue;	×
172	}
173
174	// Check if libnode can be bubbled down
175	if (!this->can_be_bubbled_down(*next_block)) {	1✔
NEW 176	continue;	×
177	}
178
179	// Compare priority and order
180	auto [current_prio, current_order] = this->get_prio_and_order(current_block);	1✔
181	auto [next_prio, next_order] = this->get_prio_and_order(next_block);	1✔
182	if (current_prio > next_prio) {	2✔
NEW 183	continue;	×
184	}
185	if (current_prio == next_prio && current_order <= next_order) {	2✔
NEW 186	continue;	×
187	}
188
189	// Swap blocks
190	builder_.move_child(sequence, j - 1, sequence, j);	1✔
191	return true; // Restart after modification	1✔
192	}	1✔
193
NEW 194	return false;	×
195	}	5✔
196
197	bool BlockSorting::is_libnode_side_effect_white_listed(data_flow::LibraryNode* libnode) {	2✔
198	return dynamic_cast<stdlib::AllocaNode>(libnode) \|\| dynamic_cast<stdlib::CallocNode>(libnode) \|\|	4✔
199	dynamic_cast<stdlib::FreeNode>(libnode) \|\| dynamic_cast<stdlib::MallocNode>(libnode) \|\|	2✔
NEW 200	dynamic_cast<stdlib::MemsetNode*>(libnode);	×
201	}
202
203	bool BlockSorting::can_be_bubbled_up(structured_control_flow::Block& block) {	5✔
204	if (this->is_reference_block(block)) {	5✔
205	return true;	2✔
206	}
207
208	if (this->is_libnode_block(block)) {	3✔
209	auto* libnode = *block.dataflow().library_nodes().begin();	3✔
210	return dynamic_cast<stdlib::AllocaNode>(libnode) \|\| dynamic_cast<stdlib::CallocNode>(libnode) \|\|	6✔
211	dynamic_cast<stdlib::MallocNode>(libnode) \|\| dynamic_cast<stdlib::MemsetNode>(libnode);	3✔
212	}
213
NEW 214	return false;	×
215	}	5✔
216
217	bool BlockSorting::can_be_bubbled_down(structured_control_flow::Block& block) {	1✔
218	if (!this->is_libnode_block(block)) {	1✔
UNCOV 219	return false;	×
220	}
221	auto* libnode = *block.dataflow().library_nodes().begin();	1✔
222	return dynamic_cast<stdlib::FreeNode*>(libnode);	1✔
223	}	1✔
224
225	std::pair<int, std::string> BlockSorting::get_prio_and_order(structured_control_flow::Block* block) {	12✔
226	if (this->is_libnode_block(*block)) {	12✔
227	auto* libnode = *block->dataflow().library_nodes().begin();	6✔
228	if (dynamic_cast<stdlib::AllocaNode>(libnode) \|\| dynamic_cast<stdlib::CallocNode>(libnode) \|\|	9✔
229	dynamic_cast<stdlib::FreeNode>(libnode) \|\| dynamic_cast<stdlib::MallocNode>(libnode)) {	6✔
230	auto& oedge = block->dataflow().out_edges(libnode).begin();	6✔
231	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	6✔
232	return {300, dst.data()};	6✔
NEW 233	} else if (dynamic_cast<stdlib::MemsetNode*>(libnode)) {	×
NEW 234	auto& oedge = block->dataflow().out_edges(libnode).begin();	×
NEW 235	auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());	×
NEW 236	return {200, dst.data()};	×
237	}
238	} else if (this->is_reference_block(*block)) {	6✔
239	return {100, ""};	4✔
240	}
241
242	return {INT_MIN, ""};	2✔
243	}	12✔
244
245	bool BlockSorting::is_reference_block(structured_control_flow::Block& block) {	11✔
246	auto& dfg = block.dataflow();	11✔
247	if (dfg.nodes().size() != 2) {	11✔
248	return false;	2✔
249	}
250	if (dfg.edges().size() != 1) {	9✔
UNCOV 251	return false;	×
252	}
253	auto& edge = *dfg.edges().begin();	9✔
254	if (edge.type() != data_flow::MemletType::Reference && edge.type() != data_flow::MemletType::Dereference_Src &&	9✔
255	edge.type() != data_flow::MemletType::Dereference_Dst) {	3✔
256	return false;	3✔
257	}
258	return true;	6✔
259	}	11✔
260
261	bool BlockSorting::is_libnode_block(structured_control_flow::Block& next_block) {	16✔
262	auto& next_dfg = next_block.dataflow();	16✔
263	if (next_dfg.library_nodes().size() != 1) {	16✔
264	return false;	6✔
265	}
266	auto* libnode = *next_dfg.library_nodes().begin();	10✔
267	if (next_dfg.edges().size() != libnode->inputs().size() + libnode->outputs().size()) {	10✔
268	return false;	×
269	}
270	return true;	10✔
271	}	16✔
272
273	} // namespace passes
274	} // namespace sdfg

daisytuner / sdfglib / 20034653178

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