• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

daisytuner / sdfglib / 20146754559

11 Dec 2025 08:39PM UTC coverage: 40.268% (-0.08%) from 40.351%
20146754559

push

github

web-flow
Merge pull request #390 from daisytuner/block-hoisting-fix

checks false dependencies in block hoisting

13624 of 43811 branches covered (31.1%)

Branch coverage included in aggregate %.

7 of 11 new or added lines in 2 files covered. (63.64%)

17 existing lines in 2 files now uncovered.

11645 of 18941 relevant lines covered (61.48%)

93.48 hits per line

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

56.41
/src/passes/code_motion/block_hoisting.cpp
1
#include "sdfg/passes/code_motion/block_hoisting.h"
2
#include <cstddef>
3
#include <string>
4
#include <unordered_map>
5
#include <vector>
6

7
#include "sdfg/analysis/analysis.h"
8
#include "sdfg/analysis/scope_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/memcpy.h"
16
#include "sdfg/data_flow/library_nodes/stdlib/memmove.h"
17
#include "sdfg/data_flow/library_nodes/stdlib/memset.h"
18
#include "sdfg/data_flow/memlet.h"
19
#include "sdfg/data_flow/tasklet.h"
20
#include "sdfg/element.h"
21
#include "sdfg/structured_control_flow/block.h"
22
#include "sdfg/structured_control_flow/control_flow_node.h"
23
#include "sdfg/structured_control_flow/for.h"
24
#include "sdfg/structured_control_flow/if_else.h"
25
#include "sdfg/structured_control_flow/map.h"
26
#include "sdfg/structured_control_flow/sequence.h"
27
#include "sdfg/structured_control_flow/structured_loop.h"
28
#include "sdfg/symbolic/symbolic.h"
29
#include "sdfg/visitor/structured_sdfg_visitor.h"
30

31
namespace sdfg {
32
namespace passes {
33

34
BlockHoisting::BlockHoisting(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager)
20✔
35
    : visitor::NonStoppingStructuredSDFGVisitor(builder, analysis_manager) {};
20✔
36

37
bool BlockHoisting::accept(structured_control_flow::Map& map_stmt) {
12✔
38
    auto& scope_analysis = analysis_manager_.get<analysis::ScopeAnalysis>();
12✔
39
    auto& parent = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&map_stmt));
12✔
40

41
    bool applied = false;
12✔
42
    applied |= this->map_invariant_front(parent, map_stmt);
12✔
43
    applied |= this->map_invariant_back(parent, map_stmt);
12✔
44

45
    return applied;
12✔
46
}
47

48
bool BlockHoisting::accept(structured_control_flow::IfElse& if_else) {
15✔
49
    // Ignore incomplete branches for now
50
    if (if_else.size() == 0 || !if_else.is_complete()) {
15!
51
        return false;
×
52
    }
53

54
    auto& scope_analysis = analysis_manager_.get<analysis::ScopeAnalysis>();
15✔
55
    auto& parent = static_cast<structured_control_flow::Sequence&>(*scope_analysis.parent_scope(&if_else));
15✔
56

57
    bool applied = false;
15✔
58
    applied |= this->if_else_invariant_front(parent, if_else);
15✔
59
    applied |= this->if_else_invariant_back(parent, if_else);
15✔
60

61
    return applied;
15✔
62
}
15✔
63

64
bool BlockHoisting::is_libnode_allowed(
18✔
65
    structured_control_flow::Sequence& body, data_flow::DataFlowGraph& dfg, data_flow::LibraryNode* libnode
66
) {
67
    if (dynamic_cast<stdlib::AllocaNode*>(libnode)) {
18!
68
        return true;
3✔
69
    } else if (dynamic_cast<stdlib::MemcpyNode*>(libnode)) {
15!
70
        return true;
6✔
71
    } else if (dynamic_cast<stdlib::MemmoveNode*>(libnode)) {
9!
72
        return true;
6✔
73
    } else if (dynamic_cast<stdlib::MemsetNode*>(libnode)) {
3!
74
        return true;
3✔
75
    } else {
76
        return false;
×
77
    }
78
}
18✔
79

80
bool BlockHoisting::equal_libnodes(structured_control_flow::Block& block1, structured_control_flow::Block& block2) {
6✔
81
    auto& dfg1 = block1.dataflow();
6✔
82
    auto& dfg2 = block2.dataflow();
6✔
83

84
    // Get library nodes
85
    auto* libnode1 = *dfg1.library_nodes().begin();
6✔
86
    auto* libnode2 = *dfg2.library_nodes().begin();
6✔
87

88
    // Collect in edges
89
    std::unordered_map<std::string, data_flow::Memlet*> iedges1, iedges2;
6✔
90
    for (auto& iedge : dfg1.in_edges(*libnode1)) {
10!
91
        iedges1.insert({iedge.dst_conn(), &iedge});
4!
92
    }
93
    for (auto& iedge : dfg2.in_edges(*libnode2)) {
10!
94
        iedges2.insert({iedge.dst_conn(), &iedge});
4!
95
    }
96

97
    // In edges must have the same type, subset, and container
98
    if (iedges1.size() != iedges2.size()) {
6!
99
        return false;
×
100
    }
101
    for (auto [conn, iedge1] : iedges1) {
26!
102
        if (!iedges2.contains(conn)) {
4!
103
            return false;
×
104
        }
105
        auto* iedge2 = iedges2.at(conn);
4!
106

107
        // Compare types
108
        if (iedge1->type() != iedge2->type()) {
4!
109
            return false;
×
110
        }
111

112
        // Compare subsets
113
        if (iedge1->subset().size() != iedge2->subset().size()) {
4!
114
            return false;
×
115
        }
116
        for (size_t i = 0; i < iedge1->subset().size(); i++) {
4!
117
            if (!symbolic::eq(iedge1->subset().at(i), iedge2->subset().at(i))) {
×
118
                return false;
×
119
            }
120
        }
×
121

122
        // Compare containers
123
        auto& src1 = static_cast<data_flow::AccessNode&>(iedge1->src());
4!
124
        auto& src2 = static_cast<data_flow::AccessNode&>(iedge2->src());
4!
125
        if (src1.data() != src2.data()) {
4!
126
            return false;
×
127
        }
128
    }
4!
129

130
    // Collect out edges
131
    std::unordered_map<std::string, data_flow::Memlet*> oedges1, oedges2;
6✔
132
    for (auto& oedge : dfg1.out_edges(*libnode1)) {
12!
133
        oedges1.insert({oedge.src_conn(), &oedge});
6!
134
    }
135
    for (auto& oedge : dfg2.out_edges(*libnode2)) {
12!
136
        oedges2.insert({oedge.src_conn(), &oedge});
6!
137
    }
138

139
    // Out edges must have the same type, subset, and container
140
    if (oedges1.size() != oedges2.size()) {
6!
141
        return false;
×
142
    }
143
    for (auto [conn, oedge1] : oedges1) {
36!
144
        if (!oedges2.contains(conn)) {
6!
145
            return false;
×
146
        }
147
        auto& oedge2 = oedges2.at(conn);
6!
148

149
        // Compare types
150
        if (oedge1->type() != oedge2->type()) {
6!
151
            return false;
×
152
        }
153

154
        // Compare subsets
155
        if (oedge1->subset().size() != oedge2->subset().size()) {
6!
156
            return false;
×
157
        }
158
        for (size_t i = 0; i < oedge1->subset().size(); i++) {
6!
159
            if (!symbolic::eq(oedge1->subset().at(i), oedge2->subset().at(i))) {
×
160
                return false;
×
161
            }
162
        }
×
163

164
        // Compare containers
165
        auto& dst1 = static_cast<data_flow::AccessNode&>(oedge1->dst());
6!
166
        auto& dst2 = static_cast<data_flow::AccessNode&>(oedge2->dst());
6!
167
        if (dst1.data() != dst2.data()) {
6!
168
            return false;
×
169
        }
170
    }
6!
171

172
    // Checks library node internals
173
    return this->equal_libnodes(libnode1, libnode2);
6!
174
}
6✔
175

176
void BlockHoisting::if_else_extract_invariant_libnode_front(
4✔
177
    structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else
178
) {
179
    // This function is a wrapper that can be overridden in sub-classes
180
    this->if_else_extract_invariant_front(parent, if_else);
4✔
181
}
4✔
182

183
void BlockHoisting::if_else_extract_invariant_libnode_back(
2✔
184
    structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else
185
) {
186
    // This function is a wrapper that can be overridden in sub-classes
187
    this->if_else_extract_invariant_back(parent, if_else);
2✔
188
}
2✔
189

190
bool BlockHoisting::is_invariant_move(
28✔
191
    structured_control_flow::Sequence& body, data_flow::DataFlowGraph& dfg, bool no_loop_carried_dependencies
192
) {
193
    if (dfg.nodes().size() != 2) {
28✔
194
        return false;
17✔
195
    }
196
    if (dfg.edges().size() != 1) {
11!
197
        return false;
×
198
    }
199
    auto& edge = *dfg.edges().begin();
11✔
200
    if (edge.type() != data_flow::MemletType::Dereference_Src) {
11✔
201
        return false;
8✔
202
    }
203

204
    if (no_loop_carried_dependencies) {
3!
205
        return true;
3✔
206
    }
UNCOV
207
    auto& src = static_cast<data_flow::AccessNode&>(edge.src());
×
208

UNCOV
209
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
×
UNCOV
210
    analysis::UsersView body_view(users_analysis, body);
×
UNCOV
211
    if (!body_view.writes(src.data()).empty() || !body_view.moves(src.data()).empty()) {
×
212
        return false;
×
213
    }
214

UNCOV
215
    return true;
×
216
}
28✔
217

218
bool BlockHoisting::is_invariant_view(
28✔
219
    structured_control_flow::Sequence& body,
220
    data_flow::DataFlowGraph& dfg,
221
    symbolic::Symbol indvar,
222
    bool no_loop_carried_dependencies
223
) {
224
    if (dfg.nodes().size() != 2) {
28✔
225
        return false;
17✔
226
    }
227
    if (dfg.edges().size() != 1) {
11!
228
        return false;
×
229
    }
230
    auto& edge = *dfg.edges().begin();
11✔
231
    if (edge.type() != data_flow::MemletType::Reference) {
11✔
232
        return false;
4✔
233
    }
234

235
    if (!indvar.is_null()) {
7✔
236
        auto& subset = edge.subset();
1✔
237
        for (const auto& dim : subset) {
2✔
238
            if (symbolic::uses(dim, indvar)) {
1!
239
                return false;
×
240
            }
241
        }
242
    }
1!
243

244
    if (no_loop_carried_dependencies) {
7!
245
        return true;
7✔
246
    }
UNCOV
247
    auto& src = static_cast<data_flow::AccessNode&>(edge.src());
×
248

UNCOV
249
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
×
UNCOV
250
    analysis::UsersView body_view(users_analysis, body);
×
UNCOV
251
    if (!body_view.writes(src.data()).empty() || !body_view.moves(src.data()).empty()) {
×
252
        return false;
×
253
    }
254

UNCOV
255
    return true;
×
256
}
28✔
257

258
bool BlockHoisting::is_invariant_libnode(
54✔
259
    structured_control_flow::Sequence& body,
260
    data_flow::DataFlowGraph& dfg,
261
    symbolic::Symbol indvar,
262
    bool no_loop_carried_dependencies
263
) {
264
    if (dfg.library_nodes().size() != 1) {
54✔
265
        return false;
36✔
266
    }
267
    if (dfg.tasklets().size() != 0) {
18!
268
        return false;
×
269
    }
270
    auto* libnode = *dfg.library_nodes().begin();
18✔
271
    if (!libnode) {
18!
272
        return false;
×
273
    }
274
    if (dfg.data_nodes().size() != libnode->outputs().size() + libnode->inputs().size()) {
18!
275
        return false;
×
276
    }
277

278
    if (!this->is_libnode_allowed(body, dfg, libnode)) {
18!
279
        return false;
×
280
    }
281

282
    if (!indvar.is_null()) {
18✔
283
        if (libnode->symbols().contains(indvar)) {
6!
284
            return false;
×
285
        }
286
        for (auto& oedge : dfg.out_edges(*libnode)) {
12✔
287
            for (const auto& dim : oedge.subset()) {
6!
288
                if (symbolic::uses(dim, indvar)) {
×
289
                    return false;
×
290
                }
291
            }
292
        }
293
        for (auto& iedge : dfg.in_edges(*libnode)) {
10✔
294
            for (const auto& dim : iedge.subset()) {
4!
295
                if (symbolic::uses(dim, indvar)) {
×
296
                    return false;
×
297
                }
298
            }
299
        }
300
    }
6✔
301

302
    if (no_loop_carried_dependencies) {
18!
303
        return true;
18✔
304
    }
305

UNCOV
306
    auto& users_analysis = analysis_manager_.get<analysis::Users>();
×
UNCOV
307
    analysis::UsersView body_view(users_analysis, body);
×
UNCOV
308
    for (auto& iedge : dfg.in_edges(*libnode)) {
×
UNCOV
309
        auto& src = static_cast<data_flow::AccessNode&>(iedge.src());
×
UNCOV
310
        if (!body_view.writes(src.data()).empty() || !body_view.moves(src.data()).empty()) {
×
311
            return false;
×
312
        }
313
    }
NEW
314
    for (auto& oedge : dfg.out_edges(*libnode)) {
×
NEW
315
        auto& dst = static_cast<data_flow::AccessNode&>(oedge.dst());
×
NEW
316
        if (!body_view.writes(dst.data()).empty() || !body_view.moves(dst.data()).empty()) {
×
NEW
317
            return false;
×
318
        }
319
    }
320

UNCOV
321
    return true;
×
322
}
54✔
323

324
bool BlockHoisting::equal_moves(structured_control_flow::Block& block1, structured_control_flow::Block& block2) {
1✔
325
    // Edges must have same type and subset
326
    auto& edge1 = *block1.dataflow().edges().begin();
1✔
327
    auto& edge2 = *block2.dataflow().edges().begin();
1✔
328
    if (edge1.type() != edge2.type()) {
1!
329
        return false;
×
330
    }
331
    if (edge1.subset().size() != edge2.subset().size()) {
1!
332
        return false;
×
333
    }
334
    for (size_t i = 0; i < edge1.subset().size(); i++) {
2✔
335
        if (!symbolic::eq(edge1.subset().at(i), edge2.subset().at(i))) {
1!
336
            return false;
×
337
        }
338
    }
1✔
339

340
    // Directions must be the same
341
    if (edge1.src_conn() != edge2.src_conn()) {
1!
342
        return false;
×
343
    }
344
    if (edge1.dst_conn() != edge2.dst_conn()) {
1!
345
        return false;
×
346
    }
347

348
    // src's must have the same containers
349
    auto& src1 = static_cast<data_flow::AccessNode&>(edge1.src());
1✔
350
    auto& src2 = static_cast<data_flow::AccessNode&>(edge2.src());
1✔
351
    if (src1.data() != src2.data()) {
1!
352
        return false;
×
353
    }
354

355
    // dst's must have the same containers
356
    auto& dst1 = static_cast<data_flow::AccessNode&>(edge1.dst());
1✔
357
    auto& dst2 = static_cast<data_flow::AccessNode&>(edge2.dst());
1✔
358
    if (dst1.data() != dst2.data()) {
1!
359
        return false;
×
360
    }
361

362
    return true;
1✔
363
}
1✔
364

365
bool BlockHoisting::equal_views(structured_control_flow::Block& block1, structured_control_flow::Block& block2) {
3✔
366
    // Edges must have same type and subset
367
    auto& edge1 = *block1.dataflow().edges().begin();
3✔
368
    auto& edge2 = *block2.dataflow().edges().begin();
3✔
369
    if (edge1.type() != edge2.type()) {
3!
370
        return false;
×
371
    }
372
    if (edge1.subset().size() != edge2.subset().size()) {
3!
373
        return false;
×
374
    }
375
    for (size_t i = 0; i < edge1.subset().size(); i++) {
6✔
376
        if (!symbolic::eq(edge1.subset().at(i), edge2.subset().at(i))) {
3!
377
            return false;
×
378
        }
379
    }
3✔
380

381
    // src's must have the same containers
382
    auto& src1 = static_cast<data_flow::AccessNode&>(edge1.src());
3✔
383
    auto& src2 = static_cast<data_flow::AccessNode&>(edge2.src());
3✔
384
    if (src1.data() != src2.data()) {
3!
385
        return false;
×
386
    }
387

388
    // dst's must have the same containers
389
    auto& dst1 = static_cast<data_flow::AccessNode&>(edge1.dst());
3✔
390
    auto& dst2 = static_cast<data_flow::AccessNode&>(edge2.dst());
3✔
391
    if (dst1.data() != dst2.data()) {
3!
392
        return false;
×
393
    }
394

395
    return true;
3✔
396
}
3✔
397

398
bool BlockHoisting::equal_libnodes(data_flow::LibraryNode* libnode1, data_flow::LibraryNode* libnode2) {
6✔
399
    if (auto* alloca_node1 = dynamic_cast<stdlib::AllocaNode*>(libnode1)) {
6!
400
        if (auto* alloca_node2 = dynamic_cast<stdlib::AllocaNode*>(libnode2)) {
1!
401
            return symbolic::eq(alloca_node1->size(), alloca_node2->size());
1!
402
        }
403
    }
×
404
    if (auto* memcpy_node1 = dynamic_cast<stdlib::MemcpyNode*>(libnode1)) {
5!
405
        if (auto* memcpy_node2 = dynamic_cast<stdlib::MemcpyNode*>(libnode2)) {
2!
406
            return symbolic::eq(memcpy_node1->count(), memcpy_node2->count());
2!
407
        }
408
    }
×
409
    if (auto* memmove_node1 = dynamic_cast<stdlib::MemmoveNode*>(libnode1)) {
3!
410
        if (auto* memmove_node2 = dynamic_cast<stdlib::MemmoveNode*>(libnode2)) {
2!
411
            return symbolic::eq(memmove_node1->count(), memmove_node2->count());
2!
412
        }
413
    }
×
414
    if (auto* memset_node1 = dynamic_cast<stdlib::MemsetNode*>(libnode1)) {
1!
415
        if (auto* memset_node2 = dynamic_cast<stdlib::MemsetNode*>(libnode2)) {
1!
416
            return symbolic::eq(memset_node1->value(), memset_node2->value()) &&
2!
417
                   symbolic::eq(memset_node1->num(), memset_node2->num());
1!
418
        }
419
    }
×
420
    return false;
×
421
}
6✔
422

423
bool BlockHoisting::map_invariant_front(structured_control_flow::Sequence& parent, structured_control_flow::Map& map_stmt) {
12✔
424
    // Extract first child
425
    auto& body = map_stmt.root();
12✔
426
    if (body.size() == 0) {
12!
427
        return false;
×
428
    }
429
    auto first_child = body.at(0);
12✔
430
    if (!first_child.second.assignments().empty()) {
12!
431
        return false;
×
432
    }
433
    auto& first_node = first_child.first;
12✔
434

435
    auto* block = dynamic_cast<structured_control_flow::Block*>(&first_node);
12!
436
    if (!block) {
12!
437
        return false;
×
438
    }
439
    if (this->map_invariant_move(parent, map_stmt, *block)) {
12✔
440
        return true;
1✔
441
    }
442
    if (this->map_invariant_view(parent, map_stmt, *block)) {
11✔
443
        return true;
1✔
444
    }
445
    if (this->map_invariant_libnode_front(parent, map_stmt, *block)) {
10✔
446
        return true;
4✔
447
    }
448

449
    return false;
6✔
450
}
12✔
451

452
bool BlockHoisting::map_invariant_back(structured_control_flow::Sequence& parent, structured_control_flow::Map& map_stmt) {
12✔
453
    // Extract last child
454
    auto& body = map_stmt.root();
12✔
455
    if (body.size() == 0) {
12!
456
        return false;
×
457
    }
458
    auto last_child = body.at(body.size() - 1);
12✔
459
    if (!last_child.second.assignments().empty()) {
12!
460
        return false;
×
461
    }
462
    auto& last_node = last_child.first;
12✔
463

464
    auto* block = dynamic_cast<structured_control_flow::Block*>(&last_node);
12!
465
    if (!block) {
12!
466
        return false;
×
467
    }
468
    return this->map_invariant_libnode_back(parent, map_stmt, *block);
12✔
469
}
12✔
470

471
bool BlockHoisting::map_invariant_move(
12✔
472
    structured_control_flow::Sequence& parent,
473
    structured_control_flow::Map& map_stmt,
474
    structured_control_flow::Block& block
475
) {
476
    auto& body = map_stmt.root();
12✔
477
    if (!this->is_invariant_move(body, block.dataflow())) {
12✔
478
        return false;
11✔
479
    }
480

481
    size_t map_index = parent.index(map_stmt);
1✔
482
    builder_.move_child(body, 0, parent, map_index);
1✔
483
    return true;
1✔
484
}
12✔
485

486
bool BlockHoisting::map_invariant_view(
11✔
487
    structured_control_flow::Sequence& parent,
488
    structured_control_flow::Map& map_stmt,
489
    structured_control_flow::Block& block
490
) {
491
    auto& body = map_stmt.root();
11✔
492
    if (!this->is_invariant_view(body, block.dataflow(), map_stmt.indvar())) {
11!
493
        return false;
10✔
494
    }
495

496
    size_t map_index = parent.index(map_stmt);
1✔
497
    builder_.move_child(body, 0, parent, map_index);
1✔
498
    return true;
1✔
499
}
11✔
500

501
bool BlockHoisting::map_invariant_libnode_front(
10✔
502
    structured_control_flow::Sequence& parent,
503
    structured_control_flow::Map& map_stmt,
504
    structured_control_flow::Block& block
505
) {
506
    // For now, only allow libnode hoisting on sequential maps
507
    if (map_stmt.schedule_type().value() != ScheduleType_Sequential::value()) {
10!
508
        return false;
×
509
    }
510

511
    auto& body = map_stmt.root();
10✔
512
    if (!this->is_invariant_libnode(body, block.dataflow(), map_stmt.indvar())) {
10!
513
        return false;
6✔
514
    }
515

516
    size_t map_index = parent.index(map_stmt);
4✔
517
    builder_.move_child(body, 0, parent, map_index);
4✔
518
    return true;
4✔
519
}
10✔
520

521
bool BlockHoisting::map_invariant_libnode_back(
12✔
522
    structured_control_flow::Sequence& parent,
523
    structured_control_flow::Map& map_stmt,
524
    structured_control_flow::Block& block
525
) {
526
    // For now, only allow libnode hoisting on sequential maps
527
    if (map_stmt.schedule_type().value() != ScheduleType_Sequential::value()) {
12!
528
        return false;
×
529
    }
530

531
    auto& body = map_stmt.root();
12✔
532
    if (!this->is_invariant_libnode(body, block.dataflow(), map_stmt.indvar())) {
12!
533
        return false;
10✔
534
    }
535

536
    size_t map_index = parent.index(map_stmt);
2✔
537
    builder_.move_child(body, body.size() - 1, parent, map_index + 1);
2✔
538
    return true;
2✔
539
}
12✔
540

541
bool BlockHoisting::
542
    if_else_invariant_front(structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else) {
15✔
543
    // Extract the first block of first case
544
    if (if_else.at(0).first.size() == 0) {
15!
545
        return false;
×
546
    }
547
    auto first_child = if_else.at(0).first.at(0);
15!
548
    if (!first_child.second.assignments().empty()) {
15!
549
        return false;
×
550
    }
551
    auto* first_block = dynamic_cast<structured_control_flow::Block*>(&first_child.first);
15!
552
    if (!first_block) {
15!
553
        return false;
×
554
    }
555

556
    // Collect the first block of all other cases
557
    std::vector<structured_control_flow::Block*> other_blocks;
15✔
558
    for (size_t i = 1; i < if_else.size(); i++) {
30!
559
        if (if_else.at(i).first.size() == 0) {
15!
560
            return false;
×
561
        }
562
        auto other_child = if_else.at(i).first.at(0);
15!
563
        if (!other_child.second.assignments().empty()) {
15!
564
            return false;
×
565
        }
566
        auto* other_block = dynamic_cast<structured_control_flow::Block*>(&other_child.first);
15!
567
        if (!other_block) {
15!
568
            return false;
×
569
        }
570
        other_blocks.push_back(other_block);
15!
571
    }
15✔
572

573
    // Check the first block of all cases for invariant move / view / libnode
574
    if (this->is_invariant_move(if_else.at(0).first, first_block->dataflow())) {
15!
575
        for (size_t i = 0; i < other_blocks.size(); i++) {
2✔
576
            if (!this->is_invariant_move(if_else.at(i + 1).first, other_blocks[i]->dataflow())) {
1!
577
                return false;
×
578
            }
579
            if (!this->equal_moves(*first_block, *other_blocks[i])) {
1!
580
                return false;
×
581
            }
582
        }
1✔
583
        this->if_else_extract_invariant_front(parent, if_else);
1!
584
        return true;
1✔
585
    } else if (this->is_invariant_view(if_else.at(0).first, first_block->dataflow())) {
14!
586
        for (size_t i = 0; i < other_blocks.size(); i++) {
6✔
587
            if (!this->is_invariant_view(if_else.at(i + 1).first, other_blocks[i]->dataflow())) {
3!
588
                return false;
×
589
            }
590
            if (!this->equal_views(*first_block, *other_blocks[i])) {
3!
591
                return false;
×
592
            }
593
        }
3✔
594
        this->if_else_extract_invariant_front(parent, if_else);
3!
595
        return true;
3✔
596
    } else if (this->is_invariant_libnode(if_else.at(0).first, first_block->dataflow())) {
11!
597
        for (size_t i = 0; i < other_blocks.size(); i++) {
8✔
598
            if (!this->is_invariant_libnode(if_else.at(i + 1).first, other_blocks[i]->dataflow())) {
4!
599
                return false;
×
600
            }
601
            if (!this->equal_libnodes(*first_block, *other_blocks[i])) {
4!
602
                return false;
×
603
            }
604
        }
4✔
605
        this->if_else_extract_invariant_libnode_front(parent, if_else);
4!
606
        return true;
4✔
607
    }
608

609
    return false;
7✔
610
}
15✔
611

612
bool BlockHoisting::
613
    if_else_invariant_back(structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else) {
15✔
614
    // Extract the last block of first case
615
    if (if_else.at(0).first.size() == 0) {
15!
616
        return false;
×
617
    }
618
    auto last_child = if_else.at(0).first.at(if_else.at(0).first.size() - 1);
15!
619
    if (!last_child.second.assignments().empty()) {
15!
620
        return false;
×
621
    }
622
    auto* last_block = dynamic_cast<structured_control_flow::Block*>(&last_child.first);
15!
623
    if (!last_block) {
15!
624
        return false;
×
625
    }
626

627
    // Collect the last block of all other cases
628
    std::vector<structured_control_flow::Block*> other_blocks;
15✔
629
    for (size_t i = 1; i < if_else.size(); i++) {
30!
630
        if (if_else.at(i).first.size() == 0) {
15!
631
            return false;
×
632
        }
633
        auto other_child = if_else.at(i).first.at(if_else.at(i).first.size() - 1);
15!
634
        if (!other_child.second.assignments().empty()) {
15!
635
            return false;
×
636
        }
637
        auto* other_block = dynamic_cast<structured_control_flow::Block*>(&other_child.first);
15!
638
        if (!other_block) {
15!
639
            return false;
×
640
        }
641
        other_blocks.push_back(other_block);
15!
642
    }
15✔
643

644
    // Check the first block of all cases for invariant move / view / libnode
645
    if (this->is_invariant_libnode(if_else.at(0).first, last_block->dataflow())) {
15!
646
        for (size_t i = 0; i < other_blocks.size(); i++) {
4✔
647
            if (!this->is_invariant_libnode(if_else.at(i + 1).first, other_blocks[i]->dataflow())) {
2!
648
                return false;
×
649
            }
650
            if (!this->equal_libnodes(*last_block, *other_blocks[i])) {
2!
651
                return false;
×
652
            }
653
        }
2✔
654
        this->if_else_extract_invariant_libnode_back(parent, if_else);
2!
655
        return true;
2✔
656
    }
657

658
    return false;
13✔
659
}
15✔
660

661
void BlockHoisting::if_else_extract_invariant_front(
8✔
662
    structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else
663
) {
664
    size_t if_else_index = parent.index(if_else);
8✔
665
    builder_.move_child(if_else.at(0).first, 0, parent, if_else_index);
8!
666

667
    for (size_t i = 1; i < if_else.size(); i++) {
16✔
668
        builder_.remove_child(if_else.at(i).first, 0);
8!
669
    }
8✔
670
}
8✔
671

672
void BlockHoisting::if_else_extract_invariant_back(
2✔
673
    structured_control_flow::Sequence& parent, structured_control_flow::IfElse& if_else
674
) {
675
    size_t if_else_index = parent.index(if_else);
2✔
676
    builder_.move_child(if_else.at(0).first, if_else.at(0).first.size() - 1, parent, if_else_index + 1);
2!
677

678
    for (size_t i = 1; i < if_else.size(); i++) {
4✔
679
        builder_.remove_child(if_else.at(i).first, if_else.at(i).first.size() - 1);
2!
680
    }
2✔
681
}
2✔
682

683
} // namespace passes
684
} // namespace sdfg
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc