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

daisytuner / sdfglib / 16905344671

12 Aug 2025 09:52AM UTC coverage: 65.353%. Remained the same
16905344671

push

github

web-flow
Merge pull request #191 from Moehre2/fix-sdfg-builder-parent

Bugfix: StructuredSDFGBuilder::parent did not handle Maps

0 of 2 new or added lines in 1 file covered. (0.0%)

1 existing line in 1 file now uncovered.

9169 of 14030 relevant lines covered (65.35%)

128.27 hits per line

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

80.03
/src/builder/structured_sdfg_builder.cpp
1
#include "sdfg/builder/structured_sdfg_builder.h"
2

3
#include <cstddef>
4

5
#include "sdfg/analysis/scope_analysis.h"
6
#include "sdfg/codegen/language_extensions/cpp_language_extension.h"
7
#include "sdfg/data_flow/library_node.h"
8
#include "sdfg/structured_control_flow/map.h"
9
#include "sdfg/structured_control_flow/sequence.h"
10
#include "sdfg/structured_control_flow/structured_loop.h"
11
#include "sdfg/types/utils.h"
12

13
using namespace sdfg::control_flow;
14
using namespace sdfg::structured_control_flow;
15

16
namespace sdfg {
17
namespace builder {
18

19
std::unordered_set<const control_flow::State*> StructuredSDFGBuilder::
20
    determine_loop_nodes(const SDFG& sdfg, const control_flow::State& start, const control_flow::State& end) const {
1✔
21
    std::unordered_set<const control_flow::State*> nodes;
1✔
22
    std::unordered_set<const control_flow::State*> visited;
1✔
23
    std::list<const control_flow::State*> queue = {&start};
1✔
24
    while (!queue.empty()) {
4✔
25
        auto curr = queue.front();
3✔
26
        queue.pop_front();
3✔
27
        if (visited.find(curr) != visited.end()) {
3✔
28
            continue;
×
29
        }
30
        visited.insert(curr);
3✔
31

32
        nodes.insert(curr);
3✔
33
        if (curr == &end) {
3✔
34
            continue;
1✔
35
        }
36

37
        for (auto& iedge : sdfg.in_edges(*curr)) {
4✔
38
            queue.push_back(&iedge.src());
2✔
39
        }
40
    }
41

42
    return nodes;
1✔
43
};
1✔
44

45
bool post_dominates(
6✔
46
    const State* pdom,
47
    const State* node,
48
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree
49
) {
50
    if (pdom == node) {
6✔
51
        return true;
1✔
52
    }
53

54
    auto current = pdom_tree.at(node);
5✔
55
    while (current != nullptr) {
9✔
56
        if (current == pdom) {
9✔
57
            return true;
5✔
58
        }
59
        current = pdom_tree.at(current);
4✔
60
    }
61

62
    return false;
×
63
}
6✔
64

65
const control_flow::State* StructuredSDFGBuilder::find_end_of_if_else(
3✔
66
    const SDFG& sdfg,
67
    const State* current,
68
    std::vector<const InterstateEdge*>& out_edges,
69
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree
70
) {
71
    // Best-effort approach: Check if post-dominator of current dominates all out edges
72
    auto pdom = pdom_tree.at(current);
3✔
73
    for (auto& edge : out_edges) {
9✔
74
        if (!post_dominates(pdom, &edge->dst(), pdom_tree)) {
6✔
75
            return nullptr;
×
76
        }
77
    }
78

79
    return pdom;
3✔
80
}
3✔
81

82
void StructuredSDFGBuilder::traverse(const SDFG& sdfg) {
4✔
83
    // Start of SDFGS
84
    Sequence& root = *structured_sdfg_->root_;
4✔
85
    const State* start_state = &sdfg.start_state();
4✔
86

87
    auto pdom_tree = sdfg.post_dominator_tree();
4✔
88

89
    std::unordered_set<const InterstateEdge*> breaks;
4✔
90
    std::unordered_set<const InterstateEdge*> continues;
4✔
91
    for (auto& edge : sdfg.back_edges()) {
5✔
92
        continues.insert(edge);
1✔
93
    }
94

95
    std::unordered_set<const control_flow::State*> visited;
4✔
96
    this->traverse_with_loop_detection(sdfg, root, start_state, nullptr, continues, breaks, pdom_tree, visited);
4✔
97
};
4✔
98

99
void StructuredSDFGBuilder::traverse_with_loop_detection(
9✔
100
    const SDFG& sdfg,
101
    Sequence& scope,
102
    const State* current,
103
    const State* end,
104
    const std::unordered_set<const InterstateEdge*>& continues,
105
    const std::unordered_set<const InterstateEdge*>& breaks,
106
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree,
107
    std::unordered_set<const control_flow::State*>& visited
108
) {
109
    if (current == end) {
9✔
110
        return;
1✔
111
    }
112

113
    auto in_edges = sdfg.in_edges(*current);
8✔
114

115
    // Loop detection
116
    std::unordered_set<const InterstateEdge*> loop_edges;
8✔
117
    for (auto& iedge : in_edges) {
13✔
118
        if (continues.find(&iedge) != continues.end()) {
5✔
119
            loop_edges.insert(&iedge);
1✔
120
        }
1✔
121
    }
122
    if (!loop_edges.empty()) {
8✔
123
        // 1. Determine nodes of loop body
124
        std::unordered_set<const control_flow::State*> body;
1✔
125
        for (auto back_edge : loop_edges) {
2✔
126
            auto loop_nodes = this->determine_loop_nodes(sdfg, back_edge->src(), back_edge->dst());
1✔
127
            body.insert(loop_nodes.begin(), loop_nodes.end());
1✔
128
        }
1✔
129

130
        // 2. Determine exit states and exit edges
131
        std::unordered_set<const control_flow::State*> exit_states;
1✔
132
        std::unordered_set<const control_flow::InterstateEdge*> exit_edges;
1✔
133
        for (auto node : body) {
4✔
134
            for (auto& edge : sdfg.out_edges(*node)) {
7✔
135
                if (body.find(&edge.dst()) == body.end()) {
4✔
136
                    exit_edges.insert(&edge);
1✔
137
                    exit_states.insert(&edge.dst());
1✔
138
                }
1✔
139
            }
140
        }
141
        if (exit_states.size() != 1) {
1✔
142
            throw UnstructuredControlFlowException();
×
143
        }
144
        const control_flow::State* exit_state = *exit_states.begin();
1✔
145

146
        for (auto& edge : breaks) {
1✔
147
            exit_edges.insert(edge);
×
148
        }
149

150
        // Collect debug information (could be removed when this is computed dynamically)
151
        DebugInfo dbg_info = current->debug_info();
1✔
152
        for (auto& edge : in_edges) {
3✔
153
            dbg_info = DebugInfo::merge(dbg_info, edge.debug_info());
2✔
154
        }
155
        for (auto node : body) {
4✔
156
            dbg_info = DebugInfo::merge(dbg_info, node->debug_info());
3✔
157
        }
158
        for (auto edge : exit_edges) {
2✔
159
            dbg_info = DebugInfo::merge(dbg_info, edge->debug_info());
1✔
160
        }
161

162
        // 3. Add while loop
163
        While& loop = this->add_while(scope, {}, dbg_info);
1✔
164

165
        std::unordered_set<const control_flow::State*> loop_visited(visited);
1✔
166
        this->traverse_without_loop_detection(
1✔
167
            sdfg, loop.root(), current, exit_state, continues, exit_edges, pdom_tree, loop_visited
1✔
168
        );
169

170
        this->traverse_with_loop_detection(sdfg, scope, exit_state, end, continues, breaks, pdom_tree, visited);
1✔
171
    } else {
1✔
172
        this->traverse_without_loop_detection(sdfg, scope, current, end, continues, breaks, pdom_tree, visited);
7✔
173
    }
174
};
9✔
175

176
void StructuredSDFGBuilder::traverse_without_loop_detection(
8✔
177
    const SDFG& sdfg,
178
    Sequence& scope,
179
    const State* current,
180
    const State* end,
181
    const std::unordered_set<const InterstateEdge*>& continues,
182
    const std::unordered_set<const InterstateEdge*>& breaks,
183
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree,
184
    std::unordered_set<const control_flow::State*>& visited
185
) {
186
    std::list<const State*> queue = {current};
8✔
187
    while (!queue.empty()) {
26✔
188
        auto curr = queue.front();
18✔
189
        queue.pop_front();
18✔
190
        if (curr == end) {
18✔
191
            continue;
3✔
192
        }
193

194
        if (visited.find(curr) != visited.end()) {
15✔
195
            throw UnstructuredControlFlowException();
×
196
        }
197
        visited.insert(curr);
15✔
198

199
        auto out_edges = sdfg.out_edges(*curr);
15✔
200
        auto out_degree = sdfg.out_degree(*curr);
15✔
201

202
        // Case 1: Sink node
203
        if (out_degree == 0) {
15✔
204
            this->add_block(scope, curr->dataflow(), {}, curr->debug_info());
4✔
205
            this->add_return(scope, {}, curr->debug_info());
4✔
206
            continue;
4✔
207
        }
208

209
        // Case 2: Transition
210
        if (out_degree == 1) {
11✔
211
            auto& oedge = *out_edges.begin();
8✔
212
            if (!oedge.is_unconditional()) {
8✔
213
                throw UnstructuredControlFlowException();
×
214
            }
215
            this->add_block(scope, curr->dataflow(), oedge.assignments(), curr->debug_info());
8✔
216

217
            if (continues.find(&oedge) != continues.end()) {
8✔
218
                this->add_continue(scope, oedge.debug_info());
×
219
            } else if (breaks.find(&oedge) != breaks.end()) {
8✔
220
                this->add_break(scope, oedge.debug_info());
×
221
            } else {
×
222
                bool starts_loop = false;
8✔
223
                for (auto& iedge : sdfg.in_edges(oedge.dst())) {
19✔
224
                    if (continues.find(&iedge) != continues.end()) {
11✔
225
                        starts_loop = true;
×
226
                        break;
×
227
                    }
228
                }
229
                if (!starts_loop) {
8✔
230
                    queue.push_back(&oedge.dst());
8✔
231
                } else {
8✔
232
                    this->traverse_with_loop_detection(
×
233
                        sdfg, scope, &oedge.dst(), end, continues, breaks, pdom_tree, visited
×
234
                    );
235
                }
236
            }
237
            continue;
8✔
238
        }
239

240
        // Case 3: Branches
241
        if (out_degree > 1) {
3✔
242
            this->add_block(scope, curr->dataflow(), {}, curr->debug_info());
3✔
243

244
            std::vector<const InterstateEdge*> out_edges_vec;
3✔
245
            for (auto& edge : out_edges) {
9✔
246
                out_edges_vec.push_back(&edge);
6✔
247
            }
248

249
            // Best-effort approach: Find end of if-else
250
            // If not found, the branches may repeat paths yielding a large SDFG
251
            const control_flow::State* local_end = this->find_end_of_if_else(sdfg, curr, out_edges_vec, pdom_tree);
3✔
252
            if (local_end == nullptr) {
3✔
253
                local_end = end;
×
254
            }
×
255

256
            auto& if_else = this->add_if_else(scope, curr->debug_info());
3✔
257
            for (size_t i = 0; i < out_degree; i++) {
9✔
258
                auto& out_edge = out_edges_vec[i];
6✔
259

260
                auto& branch = this->add_case(if_else, out_edge->condition(), out_edge->debug_info());
6✔
261
                if (!out_edge->assignments().empty()) {
6✔
262
                    this->add_block(branch, out_edge->assignments(), out_edge->debug_info());
2✔
263
                }
2✔
264
                if (continues.find(out_edge) != continues.end()) {
6✔
265
                    this->add_continue(branch, out_edge->debug_info());
1✔
266
                } else if (breaks.find(out_edge) != breaks.end()) {
6✔
267
                    this->add_break(branch, out_edge->debug_info());
1✔
268
                } else {
1✔
269
                    std::unordered_set<const control_flow::State*> branch_visited(visited);
4✔
270
                    this->traverse_with_loop_detection(
4✔
271
                        sdfg, branch, &out_edge->dst(), local_end, continues, breaks, pdom_tree, branch_visited
4✔
272
                    );
273
                }
4✔
274
            }
6✔
275

276
            if (local_end != end) {
3✔
277
                bool starts_loop = false;
2✔
278
                for (auto& iedge : sdfg.in_edges(*local_end)) {
6✔
279
                    if (continues.find(&iedge) != continues.end()) {
4✔
280
                        starts_loop = true;
×
281
                        break;
×
282
                    }
283
                }
284
                if (!starts_loop) {
2✔
285
                    queue.push_back(local_end);
2✔
286
                } else {
2✔
287
                    this->traverse_with_loop_detection(sdfg, scope, local_end, end, continues, breaks, pdom_tree, visited);
×
288
                }
289
            }
2✔
290
            continue;
291
        }
3✔
292
    }
293
}
8✔
294

295
Function& StructuredSDFGBuilder::function() const { return static_cast<Function&>(*this->structured_sdfg_); };
5,575✔
296

297
StructuredSDFGBuilder::StructuredSDFGBuilder(std::unique_ptr<StructuredSDFG>& sdfg)
78✔
298
    : FunctionBuilder(), structured_sdfg_(std::move(sdfg)) {};
78✔
299

300
StructuredSDFGBuilder::StructuredSDFGBuilder(const std::string& name, FunctionType type)
506✔
301
    : FunctionBuilder(), structured_sdfg_(new StructuredSDFG(name, type)) {};
506✔
302

303
StructuredSDFGBuilder::StructuredSDFGBuilder(const SDFG& sdfg)
4✔
304
    : FunctionBuilder(), structured_sdfg_(new StructuredSDFG(sdfg.name(), sdfg.type())) {
4✔
305
    for (auto& entry : sdfg.structures_) {
4✔
306
        this->structured_sdfg_->structures_.insert({entry.first, entry.second->clone()});
×
307
    }
308

309
    for (auto& entry : sdfg.containers_) {
11✔
310
        this->structured_sdfg_->containers_.insert({entry.first, entry.second->clone()});
7✔
311
    }
312

313
    for (auto& arg : sdfg.arguments_) {
6✔
314
        this->structured_sdfg_->arguments_.push_back(arg);
2✔
315
    }
316

317
    for (auto& ext : sdfg.externals_) {
5✔
318
        this->structured_sdfg_->externals_.push_back(ext);
1✔
319
        this->structured_sdfg_->externals_linkage_types_[ext] = sdfg.linkage_type(ext);
1✔
320
    }
321

322
    for (auto& entry : sdfg.assumptions_) {
9✔
323
        this->structured_sdfg_->assumptions_.insert({entry.first, entry.second});
5✔
324
    }
325

326
    for (auto& entry : sdfg.metadata_) {
6✔
327
        this->structured_sdfg_->metadata_[entry.first] = entry.second;
2✔
328
    }
329

330
    this->traverse(sdfg);
4✔
331
};
4✔
332

333
StructuredSDFG& StructuredSDFGBuilder::subject() const { return *this->structured_sdfg_; };
948✔
334

335
std::unique_ptr<StructuredSDFG> StructuredSDFGBuilder::move() {
420✔
336
#ifndef NDEBUG
337
    this->structured_sdfg_->validate();
420✔
338
#endif
339

340
    return std::move(this->structured_sdfg_);
420✔
341
};
342

343
Element* StructuredSDFGBuilder::find_element_by_id(const size_t& element_id) const {
14✔
344
    auto& sdfg = this->subject();
14✔
345
    std::list<Element*> queue = {&sdfg.root()};
14✔
346
    while (!queue.empty()) {
57✔
347
        auto current = queue.front();
57✔
348
        queue.pop_front();
57✔
349

350
        if (current->element_id() == element_id) {
57✔
351
            return current;
14✔
352
        }
353

354
        if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(current)) {
43✔
355
            auto& dataflow = block_stmt->dataflow();
×
356
            for (auto& node : dataflow.nodes()) {
×
357
                queue.push_back(&node);
×
358
            }
359
            for (auto& edge : dataflow.edges()) {
×
360
                queue.push_back(&edge);
×
361
            }
362
        } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
43✔
363
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
46✔
364
                queue.push_back(&sequence_stmt->at(i).first);
23✔
365
                queue.push_back(&sequence_stmt->at(i).second);
23✔
366
            }
23✔
367
        } else if (dynamic_cast<structured_control_flow::Return*>(current)) {
43✔
368
            // Do nothing
369
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
20✔
370
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
×
371
                queue.push_back(&if_else_stmt->at(i).first);
×
372
            }
×
373
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
20✔
374
            queue.push_back(&for_stmt->root());
×
375
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
20✔
376
            queue.push_back(&while_stmt->root());
×
377
        } else if (dynamic_cast<structured_control_flow::Continue*>(current)) {
20✔
378
            // Do nothing
379
        } else if (dynamic_cast<structured_control_flow::Break*>(current)) {
20✔
380
            // Do nothing
381
        } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {
20✔
382
            queue.push_back(&map_stmt->root());
10✔
383
        }
10✔
384
    }
385

386
    return nullptr;
×
387
};
14✔
388

389
Sequence& StructuredSDFGBuilder::
390
    add_sequence(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
39✔
391
    parent.children_.push_back(std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info)));
39✔
392

393
    parent.transitions_
78✔
394
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
39✔
395
        );
396

397
    return static_cast<Sequence&>(*parent.children_.back().get());
39✔
398
};
×
399

400
std::pair<Sequence&, Transition&> StructuredSDFGBuilder::
401
    add_sequence_before(Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
18✔
402
    // Insert block before current block
403
    int index = -1;
18✔
404
    for (size_t i = 0; i < parent.children_.size(); i++) {
18✔
405
        if (parent.children_.at(i).get() == &block) {
18✔
406
            index = i;
18✔
407
            break;
18✔
408
        }
409
    }
×
410
    if (index == -1) {
18✔
411
        throw InvalidSDFGException("StructuredSDFGBuilder: Block not found");
×
412
    }
413

414
    parent.children_.insert(
36✔
415
        parent.children_.begin() + index, std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info))
18✔
416
    );
417

418
    parent.transitions_.insert(
36✔
419
        parent.transitions_.begin() + index,
18✔
420
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
18✔
421
    );
422

423
    auto new_entry = parent.at(index);
18✔
424
    auto& new_block = dynamic_cast<structured_control_flow::Sequence&>(new_entry.first);
18✔
425

426
    return {new_block, new_entry.second};
18✔
427
};
×
428

429
void StructuredSDFGBuilder::remove_child(Sequence& parent, size_t i) {
11✔
430
    parent.children_.erase(parent.children_.begin() + i);
11✔
431
    parent.transitions_.erase(parent.transitions_.begin() + i);
11✔
432
};
11✔
433

434
void StructuredSDFGBuilder::remove_child(Sequence& parent, ControlFlowNode& child) {
24✔
435
    int index = -1;
24✔
436
    for (size_t i = 0; i < parent.children_.size(); i++) {
38✔
437
        if (parent.children_.at(i).get() == &child) {
38✔
438
            index = i;
24✔
439
            break;
24✔
440
        }
441
    }
14✔
442

443
    parent.children_.erase(parent.children_.begin() + index);
24✔
444
    parent.transitions_.erase(parent.transitions_.begin() + index);
24✔
445
};
24✔
446

447
void StructuredSDFGBuilder::insert_children(Sequence& parent, Sequence& other, size_t i) {
25✔
448
    parent.children_.insert(
50✔
449
        parent.children_.begin() + i,
25✔
450
        std::make_move_iterator(other.children_.begin()),
25✔
451
        std::make_move_iterator(other.children_.end())
25✔
452
    );
453
    parent.transitions_.insert(
50✔
454
        parent.transitions_.begin() + i,
25✔
455
        std::make_move_iterator(other.transitions_.begin()),
25✔
456
        std::make_move_iterator(other.transitions_.end())
25✔
457
    );
458
    for (auto& trans : parent.transitions_) {
55✔
459
        trans->parent_ = &parent;
30✔
460
    }
461
    other.children_.clear();
25✔
462
    other.transitions_.clear();
25✔
463
};
25✔
464

465
void StructuredSDFGBuilder::insert(ControlFlowNode& node, Sequence& source, Sequence& target, const DebugInfo& debug_info) {
9✔
466
    // Insert node into target sequence
467
    int index = -1;
9✔
468
    for (size_t i = 0; i < source.children_.size(); i++) {
18✔
469
        if (source.children_.at(i).get() == &node) {
18✔
470
            index = i;
9✔
471
            break;
9✔
472
        }
473
    }
9✔
474
    if (index == -1) {
9✔
475
        throw InvalidSDFGException("StructuredSDFGBuilder: Node not found in source sequence");
×
476
    }
477

478
    auto node_ptr = std::move(source.children_.at(index));
9✔
479
    source.children_.erase(source.children_.begin() + index);
9✔
480
    source.transitions_.erase(source.transitions_.begin() + index);
9✔
481

482
    target.children_.push_back(std::move(node_ptr));
9✔
483
    target.transitions_.push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, target)
9✔
484
    ));
485
};
9✔
486

487
Block& StructuredSDFGBuilder::
488
    add_block(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
491✔
489
    parent.children_.push_back(std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
491✔
490

491
    parent.transitions_
982✔
492
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
491✔
493
        );
494

495
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());
491✔
496
    (*new_block.dataflow_).parent_ = &new_block;
491✔
497

498
    return new_block;
491✔
499
};
×
500

501
Block& StructuredSDFGBuilder::add_block(
18✔
502
    Sequence& parent,
503
    const data_flow::DataFlowGraph& data_flow_graph,
504
    const sdfg::control_flow::Assignments& assignments,
505
    const DebugInfo& debug_info
506
) {
507
    parent.children_.push_back(std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
18✔
508

509
    parent.transitions_
36✔
510
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
18✔
511
        );
512

513
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());
18✔
514
    (*new_block.dataflow_).parent_ = &new_block;
18✔
515

516
    this->add_dataflow(data_flow_graph, new_block);
18✔
517

518
    return new_block;
18✔
519
};
×
520

521
std::pair<Block&, Transition&> StructuredSDFGBuilder::
522
    add_block_before(Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
11✔
523
    // Insert block before current block
524
    int index = -1;
11✔
525
    for (size_t i = 0; i < parent.children_.size(); i++) {
11✔
526
        if (parent.children_.at(i).get() == &block) {
11✔
527
            index = i;
11✔
528
            break;
11✔
529
        }
530
    }
×
531
    assert(index > -1);
11✔
532

533
    parent.children_
22✔
534
        .insert(parent.children_.begin() + index, std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
11✔
535

536
    parent.transitions_.insert(
22✔
537
        parent.transitions_.begin() + index,
11✔
538
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
11✔
539
    );
540

541
    auto new_entry = parent.at(index);
11✔
542
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
11✔
543
    (*new_block.dataflow_).parent_ = &new_block;
11✔
544

545
    return {new_block, new_entry.second};
11✔
546
};
×
547

548
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_before(
×
549
    Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph, const DebugInfo& debug_info
550
) {
551
    // Insert block before current block
552
    int index = -1;
×
553
    for (size_t i = 0; i < parent.children_.size(); i++) {
×
554
        if (parent.children_.at(i).get() == &block) {
×
555
            index = i;
×
556
            break;
×
557
        }
558
    }
×
559
    assert(index > -1);
×
560

561
    parent.children_
×
562
        .insert(parent.children_.begin() + index, std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
×
563

564
    parent.transitions_.insert(
×
565
        parent.transitions_.begin() + index,
×
566
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
×
567
    );
568

569
    auto new_entry = parent.at(index);
×
570
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
×
571
    (*new_block.dataflow_).parent_ = &new_block;
×
572

573
    this->add_dataflow(data_flow_graph, new_block);
×
574

575
    return {new_block, new_entry.second};
×
576
};
×
577

578
std::pair<Block&, Transition&> StructuredSDFGBuilder::
579
    add_block_after(Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
3✔
580
    // Insert block before current block
581
    int index = -1;
3✔
582
    for (size_t i = 0; i < parent.children_.size(); i++) {
5✔
583
        if (parent.children_.at(i).get() == &block) {
5✔
584
            index = i;
3✔
585
            break;
3✔
586
        }
587
    }
2✔
588
    assert(index > -1);
3✔
589

590
    parent.children_.insert(
6✔
591
        parent.children_.begin() + index + 1, std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info))
3✔
592
    );
593

594
    parent.transitions_.insert(
6✔
595
        parent.transitions_.begin() + index + 1,
3✔
596
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
3✔
597
    );
598

599
    auto new_entry = parent.at(index + 1);
3✔
600
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
3✔
601
    (*new_block.dataflow_).parent_ = &new_block;
3✔
602

603
    return {new_block, new_entry.second};
3✔
604
};
×
605

606
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_after(
×
607
    Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph, const DebugInfo& debug_info
608
) {
609
    int index = -1;
×
610
    for (size_t i = 0; i < parent.children_.size(); i++) {
×
611
        if (parent.children_.at(i).get() == &block) {
×
612
            index = i;
×
613
            break;
×
614
        }
615
    }
×
616
    assert(index > -1);
×
617

618
    parent.children_.insert(
×
619
        parent.children_.begin() + index + 1, std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info))
×
620
    );
621

622
    parent.transitions_.insert(
×
623
        parent.transitions_.begin() + index + 1,
×
624
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
×
625
    );
626

627
    auto new_entry = parent.at(index + 1);
×
628
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
×
629
    (*new_block.dataflow_).parent_ = &new_block;
×
630

631
    this->add_dataflow(data_flow_graph, new_block);
×
632

633
    return {new_block, new_entry.second};
×
634
};
×
635

636
For& StructuredSDFGBuilder::add_for(
122✔
637
    Sequence& parent,
638
    const symbolic::Symbol& indvar,
639
    const symbolic::Condition& condition,
640
    const symbolic::Expression& init,
641
    const symbolic::Expression& update,
642
    const sdfg::control_flow::Assignments& assignments,
643
    const DebugInfo& debug_info
644
) {
645
    parent.children_
244✔
646
        .push_back(std::unique_ptr<For>(new For(this->new_element_id(), debug_info, indvar, init, update, condition)));
122✔
647

648
    // Increment element id for body node
649
    this->new_element_id();
122✔
650

651
    parent.transitions_
244✔
652
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
122✔
653
        );
654

655
    return static_cast<For&>(*parent.children_.back().get());
122✔
656
};
×
657

658
std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_before(
9✔
659
    Sequence& parent,
660
    ControlFlowNode& block,
661
    const symbolic::Symbol& indvar,
662
    const symbolic::Condition& condition,
663
    const symbolic::Expression& init,
664
    const symbolic::Expression& update,
665
    const DebugInfo& debug_info
666
) {
667
    // Insert block before current block
668
    int index = -1;
9✔
669
    for (size_t i = 0; i < parent.children_.size(); i++) {
9✔
670
        if (parent.children_.at(i).get() == &block) {
9✔
671
            index = i;
9✔
672
            break;
9✔
673
        }
674
    }
×
675
    assert(index > -1);
9✔
676

677
    parent.children_.insert(
18✔
678
        parent.children_.begin() + index,
9✔
679
        std::unique_ptr<For>(new For(this->new_element_id(), debug_info, indvar, init, update, condition))
9✔
680
    );
681

682
    // Increment element id for body node
683
    this->new_element_id();
9✔
684

685
    parent.transitions_.insert(
18✔
686
        parent.transitions_.begin() + index,
9✔
687
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
9✔
688
    );
689

690
    auto new_entry = parent.at(index);
9✔
691
    auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);
9✔
692

693
    return {new_block, new_entry.second};
9✔
694
};
×
695

696
std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_after(
6✔
697
    Sequence& parent,
698
    ControlFlowNode& block,
699
    const symbolic::Symbol& indvar,
700
    const symbolic::Condition& condition,
701
    const symbolic::Expression& init,
702
    const symbolic::Expression& update,
703
    const DebugInfo& debug_info
704
) {
705
    // Insert block before current block
706
    int index = -1;
6✔
707
    for (size_t i = 0; i < parent.children_.size(); i++) {
11✔
708
        if (parent.children_.at(i).get() == &block) {
11✔
709
            index = i;
6✔
710
            break;
6✔
711
        }
712
    }
5✔
713
    assert(index > -1);
6✔
714

715
    parent.children_.insert(
12✔
716
        parent.children_.begin() + index + 1,
6✔
717
        std::unique_ptr<For>(new For(this->new_element_id(), debug_info, indvar, init, update, condition))
6✔
718
    );
719

720
    // Increment element id for body node
721
    this->new_element_id();
6✔
722

723
    parent.transitions_.insert(
12✔
724
        parent.transitions_.begin() + index + 1,
6✔
725
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
6✔
726
    );
727

728
    auto new_entry = parent.at(index + 1);
6✔
729
    auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);
6✔
730

731
    return {new_block, new_entry.second};
6✔
732
};
×
733

734
IfElse& StructuredSDFGBuilder::add_if_else(Sequence& parent, const DebugInfo& debug_info) {
41✔
735
    return this->add_if_else(parent, control_flow::Assignments{}, debug_info);
41✔
736
};
×
737

738
IfElse& StructuredSDFGBuilder::
739
    add_if_else(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
48✔
740
    parent.children_.push_back(std::unique_ptr<IfElse>(new IfElse(this->new_element_id(), debug_info)));
48✔
741

742
    parent.transitions_
96✔
743
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
48✔
744
        );
745

746
    return static_cast<IfElse&>(*parent.children_.back().get());
48✔
747
};
×
748

749
std::pair<IfElse&, Transition&> StructuredSDFGBuilder::
750
    add_if_else_before(Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
1✔
751
    // Insert block before current block
752
    int index = -1;
1✔
753
    for (size_t i = 0; i < parent.children_.size(); i++) {
1✔
754
        if (parent.children_.at(i).get() == &block) {
1✔
755
            index = i;
1✔
756
            break;
1✔
757
        }
758
    }
×
759
    assert(index > -1);
1✔
760

761
    parent.children_
2✔
762
        .insert(parent.children_.begin() + index, std::unique_ptr<IfElse>(new IfElse(this->new_element_id(), debug_info)));
1✔
763

764
    parent.transitions_.insert(
2✔
765
        parent.transitions_.begin() + index,
1✔
766
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
1✔
767
    );
768

769
    auto new_entry = parent.at(index);
1✔
770
    auto& new_block = dynamic_cast<structured_control_flow::IfElse&>(new_entry.first);
1✔
771

772
    return {new_block, new_entry.second};
1✔
773
};
×
774

775
Sequence& StructuredSDFGBuilder::add_case(IfElse& scope, const sdfg::symbolic::Condition cond, const DebugInfo& debug_info) {
80✔
776
    scope.cases_.push_back(std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info)));
80✔
777

778
    scope.conditions_.push_back(cond);
80✔
779
    return *scope.cases_.back();
80✔
780
};
×
781

782
void StructuredSDFGBuilder::remove_case(IfElse& scope, size_t i, const DebugInfo& debug_info) {
4✔
783
    scope.cases_.erase(scope.cases_.begin() + i);
4✔
784
    scope.conditions_.erase(scope.conditions_.begin() + i);
4✔
785
};
4✔
786

787
While& StructuredSDFGBuilder::
788
    add_while(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
33✔
789
    parent.children_.push_back(std::unique_ptr<While>(new While(this->new_element_id(), debug_info)));
33✔
790

791
    // Increment element id for body node
792
    this->new_element_id();
33✔
793

794
    parent.transitions_
66✔
795
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
33✔
796
        );
797

798
    return static_cast<While&>(*parent.children_.back().get());
33✔
799
};
×
800

801
Continue& StructuredSDFGBuilder::add_continue(Sequence& parent, const DebugInfo& debug_info) {
12✔
802
    return this->add_continue(parent, control_flow::Assignments{}, debug_info);
12✔
803
};
×
804

805
Continue& StructuredSDFGBuilder::
806
    add_continue(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
14✔
807
    // Check if continue is in a loop
808
    analysis::AnalysisManager analysis_manager(this->subject());
14✔
809
    auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
14✔
810
    auto current_scope = scope_tree_analysis.parent_scope(&parent);
14✔
811
    bool in_loop = false;
14✔
812
    while (current_scope != nullptr) {
24✔
813
        if (dynamic_cast<structured_control_flow::While*>(current_scope)) {
24✔
814
            in_loop = true;
14✔
815
            break;
14✔
816
        } else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {
10✔
817
            throw UnstructuredControlFlowException();
×
818
        }
819
        current_scope = scope_tree_analysis.parent_scope(current_scope);
10✔
820
    }
821
    if (!in_loop) {
14✔
822
        throw UnstructuredControlFlowException();
×
823
    }
824

825
    parent.children_.push_back(std::unique_ptr<Continue>(new Continue(this->new_element_id(), debug_info)));
14✔
826

827
    parent.transitions_
28✔
828
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
14✔
829
        );
830

831
    return static_cast<Continue&>(*parent.children_.back().get());
14✔
832
};
14✔
833

834
Break& StructuredSDFGBuilder::add_break(Sequence& parent, const DebugInfo& debug_info) {
13✔
835
    return this->add_break(parent, control_flow::Assignments{}, debug_info);
13✔
836
};
×
837

838
Break& StructuredSDFGBuilder::
839
    add_break(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
15✔
840
    // Check if break is in a loop
841
    analysis::AnalysisManager analysis_manager(this->subject());
15✔
842
    auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
15✔
843
    auto current_scope = scope_tree_analysis.parent_scope(&parent);
15✔
844
    bool in_loop = false;
15✔
845
    while (current_scope != nullptr) {
25✔
846
        if (dynamic_cast<structured_control_flow::While*>(current_scope)) {
25✔
847
            in_loop = true;
15✔
848
            break;
15✔
849
        } else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {
10✔
850
            throw UnstructuredControlFlowException();
×
851
        }
852
        current_scope = scope_tree_analysis.parent_scope(current_scope);
10✔
853
    }
854
    if (!in_loop) {
15✔
855
        throw UnstructuredControlFlowException();
×
856
    }
857

858
    parent.children_.push_back(std::unique_ptr<Break>(new Break(this->new_element_id(), debug_info)));
15✔
859

860
    parent.transitions_
30✔
861
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
15✔
862
        );
863

864
    return static_cast<Break&>(*parent.children_.back().get());
15✔
865
};
15✔
866

867
Return& StructuredSDFGBuilder::
868
    add_return(Sequence& parent, const sdfg::control_flow::Assignments& assignments, const DebugInfo& debug_info) {
14✔
869
    parent.children_.push_back(std::unique_ptr<Return>(new Return(this->new_element_id(), debug_info)));
14✔
870

871
    parent.transitions_
28✔
872
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
14✔
873
        );
874

875
    return static_cast<Return&>(*parent.children_.back().get());
14✔
876
};
×
877

878
Map& StructuredSDFGBuilder::add_map(
48✔
879
    Sequence& parent,
880
    const symbolic::Symbol& indvar,
881
    const symbolic::Condition& condition,
882
    const symbolic::Expression& init,
883
    const symbolic::Expression& update,
884
    const ScheduleType& schedule_type,
885
    const sdfg::control_flow::Assignments& assignments,
886
    const DebugInfo& debug_info
887
) {
888
    parent.children_
96✔
889
        .push_back(std::unique_ptr<
48✔
890
                   Map>(new Map(this->new_element_id(), debug_info, indvar, init, update, condition, schedule_type)));
48✔
891

892
    // Increment element id for body node
893
    this->new_element_id();
48✔
894

895
    parent.transitions_
96✔
896
        .push_back(std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent, assignments))
48✔
897
        );
898

899
    return static_cast<Map&>(*parent.children_.back().get());
48✔
900
};
×
901

902
std::pair<Map&, Transition&> StructuredSDFGBuilder::add_map_before(
6✔
903
    Sequence& parent,
904
    ControlFlowNode& block,
905
    const symbolic::Symbol& indvar,
906
    const symbolic::Condition& condition,
907
    const symbolic::Expression& init,
908
    const symbolic::Expression& update,
909
    const ScheduleType& schedule_type,
910
    const sdfg::control_flow::Assignments& assignments,
911
    const DebugInfo& debug_info
912
) {
913
    // Insert block before current block
914
    int index = -1;
6✔
915
    for (size_t i = 0; i < parent.children_.size(); i++) {
6✔
916
        if (parent.children_.at(i).get() == &block) {
6✔
917
            index = i;
6✔
918
            break;
6✔
919
        }
920
    }
×
921
    assert(index > -1);
6✔
922

923
    parent.children_.insert(
12✔
924
        parent.children_.begin() + index,
6✔
925
        std::unique_ptr<Map>(new Map(this->new_element_id(), debug_info, indvar, init, update, condition, schedule_type)
6✔
926
        )
927
    );
928

929
    // Increment element id for body node
930
    this->new_element_id();
6✔
931

932
    parent.transitions_.insert(
12✔
933
        parent.transitions_.begin() + index,
6✔
934
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
6✔
935
    );
936

937
    auto new_entry = parent.at(index);
6✔
938
    auto& new_block = dynamic_cast<structured_control_flow::Map&>(new_entry.first);
6✔
939

940
    return {new_block, new_entry.second};
6✔
941
};
×
942

943
std::pair<Map&, Transition&> StructuredSDFGBuilder::add_map_after(
10✔
944
    Sequence& parent,
945
    ControlFlowNode& block,
946
    const symbolic::Symbol& indvar,
947
    const symbolic::Condition& condition,
948
    const symbolic::Expression& init,
949
    const symbolic::Expression& update,
950
    const ScheduleType& schedule_type,
951
    const sdfg::control_flow::Assignments& assignments,
952
    const DebugInfo& debug_info
953
) {
954
    // Insert block before current block
955
    int index = -1;
10✔
956
    for (size_t i = 0; i < parent.children_.size(); i++) {
10✔
957
        if (parent.children_.at(i).get() == &block) {
10✔
958
            index = i;
10✔
959
            break;
10✔
960
        }
961
    }
×
962
    assert(index > -1);
10✔
963

964
    parent.children_.insert(
20✔
965
        parent.children_.begin() + index + 1,
10✔
966
        std::unique_ptr<Map>(new Map(this->new_element_id(), debug_info, indvar, init, update, condition, schedule_type)
10✔
967
        )
968
    );
969

970
    // Increment element id for body node
971
    this->new_element_id();
10✔
972

973
    parent.transitions_.insert(
20✔
974
        parent.transitions_.begin() + index + 1,
10✔
975
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent))
10✔
976
    );
977

978
    auto new_entry = parent.at(index + 1);
10✔
979
    auto& new_block = dynamic_cast<structured_control_flow::Map&>(new_entry.first);
10✔
980

981
    return {new_block, new_entry.second};
10✔
982
};
×
983

984
For& StructuredSDFGBuilder::convert_while(
×
985
    Sequence& parent,
986
    While& loop,
987
    const symbolic::Symbol& indvar,
988
    const symbolic::Condition& condition,
989
    const symbolic::Expression& init,
990
    const symbolic::Expression& update
991
) {
992
    // Insert for loop
993
    size_t index = 0;
×
994
    for (auto& entry : parent.children_) {
×
995
        if (entry.get() == &loop) {
×
996
            break;
×
997
        }
998
        index++;
×
999
    }
1000
    auto iter = parent.children_.begin() + index;
×
1001
    auto& new_iter = *parent.children_.insert(
×
1002
        iter + 1,
×
1003
        std::unique_ptr<For>(new For(this->new_element_id(), loop.debug_info(), indvar, init, update, condition))
×
1004
    );
1005

1006
    // Increment element id for body node
1007
    this->new_element_id();
×
1008

1009
    auto& for_loop = dynamic_cast<For&>(*new_iter);
×
1010
    this->insert_children(for_loop.root(), loop.root(), 0);
×
1011

1012
    // Remove while loop
1013
    parent.children_.erase(parent.children_.begin() + index);
×
1014

1015
    return for_loop;
×
1016
};
×
1017

1018
Map& StructuredSDFGBuilder::convert_for(Sequence& parent, For& loop) {
8✔
1019
    // Insert for loop
1020
    size_t index = 0;
8✔
1021
    for (auto& entry : parent.children_) {
8✔
1022
        if (entry.get() == &loop) {
8✔
1023
            break;
8✔
1024
        }
1025
        index++;
×
1026
    }
1027
    auto iter = parent.children_.begin() + index;
8✔
1028
    auto& new_iter = *parent.children_.insert(
16✔
1029
        iter + 1,
8✔
1030
        std::unique_ptr<Map>(new Map(
16✔
1031
            this->new_element_id(),
8✔
1032
            loop.debug_info(),
8✔
1033
            loop.indvar(),
8✔
1034
            loop.init(),
8✔
1035
            loop.update(),
8✔
1036
            loop.condition(),
8✔
1037
            ScheduleType_Sequential
1038
        ))
1039
    );
1040

1041
    // Increment element id for body node
1042
    this->new_element_id();
8✔
1043

1044
    auto& map = dynamic_cast<Map&>(*new_iter);
8✔
1045
    this->insert_children(map.root(), loop.root(), 0);
8✔
1046

1047
    // Remove for loop
1048
    parent.children_.erase(parent.children_.begin() + index);
8✔
1049

1050
    return map;
8✔
1051
};
×
1052

1053
void StructuredSDFGBuilder::clear_sequence(Sequence& parent) {
×
1054
    parent.children_.clear();
×
1055
    parent.transitions_.clear();
×
1056
};
×
1057

1058
Sequence& StructuredSDFGBuilder::parent(const ControlFlowNode& node) {
2✔
1059
    std::list<structured_control_flow::ControlFlowNode*> queue = {&this->structured_sdfg_->root()};
2✔
1060
    while (!queue.empty()) {
2✔
1061
        auto current = queue.front();
2✔
1062
        queue.pop_front();
2✔
1063

1064
        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
2✔
1065
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
2✔
1066
                if (&sequence_stmt->at(i).first == &node) {
2✔
1067
                    return *sequence_stmt;
2✔
1068
                }
1069
                queue.push_back(&sequence_stmt->at(i).first);
×
1070
            }
×
1071
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
×
1072
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
×
1073
                queue.push_back(&if_else_stmt->at(i).first);
×
1074
            }
×
1075
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
×
1076
            queue.push_back(&while_stmt->root());
×
NEW
1077
        } else if (auto loop_stmt = dynamic_cast<structured_control_flow::StructuredLoop*>(current)) {
×
NEW
1078
            queue.push_back(&loop_stmt->root());
×
UNCOV
1079
        }
×
1080
    }
1081

1082
    return this->structured_sdfg_->root();
×
1083
};
2✔
1084

1085
/***** Section: Dataflow Graph *****/
1086

1087
data_flow::AccessNode& StructuredSDFGBuilder::
1088
    add_access(structured_control_flow::Block& block, const std::string& data, const DebugInfo& debug_info) {
584✔
1089
    auto vertex = boost::add_vertex(block.dataflow_->graph_);
584✔
1090
    auto res = block.dataflow_->nodes_.insert(
1,168✔
1091
        {vertex,
584✔
1092
         std::unique_ptr<data_flow::AccessNode>(
584✔
1093
             new data_flow::AccessNode(this->new_element_id(), debug_info, vertex, block.dataflow(), data)
584✔
1094
         )}
1095
    );
1096

1097
    return dynamic_cast<data_flow::AccessNode&>(*(res.first->second));
584✔
1098
};
×
1099

1100
data_flow::Tasklet& StructuredSDFGBuilder::add_tasklet(
352✔
1101
    structured_control_flow::Block& block,
1102
    const data_flow::TaskletCode code,
1103
    const std::string& output,
1104
    const std::vector<std::string>& inputs,
1105
    const DebugInfo& debug_info
1106
) {
1107
    auto vertex = boost::add_vertex(block.dataflow_->graph_);
352✔
1108
    auto res = block.dataflow_->nodes_.insert(
704✔
1109
        {vertex,
352✔
1110
         std::unique_ptr<data_flow::Tasklet>(new data_flow::Tasklet(
704✔
1111
             this->new_element_id(), debug_info, vertex, block.dataflow(), code, output, inputs, symbolic::__true__()
352✔
1112
         ))}
1113
    );
1114

1115
    return dynamic_cast<data_flow::Tasklet&>(*(res.first->second));
352✔
1116
};
×
1117

1118
data_flow::Memlet& StructuredSDFGBuilder::add_memlet(
540✔
1119
    structured_control_flow::Block& block,
1120
    data_flow::DataFlowNode& src,
1121
    const std::string& src_conn,
1122
    data_flow::DataFlowNode& dst,
1123
    const std::string& dst_conn,
1124
    const data_flow::Subset& subset,
1125
    const types::IType& base_type,
1126
    const DebugInfo& debug_info
1127
) {
1128
    auto edge = boost::add_edge(src.vertex_, dst.vertex_, block.dataflow_->graph_);
540✔
1129
    auto res = block.dataflow_->edges_.insert(
1,080✔
1130
        {edge.first,
1,080✔
1131
         std::unique_ptr<data_flow::Memlet>(new data_flow::Memlet(
1,080✔
1132
             this->new_element_id(), debug_info, edge.first, block.dataflow(), src, src_conn, dst, dst_conn, subset, base_type
540✔
1133
         ))}
1134
    );
1135

1136
    auto& memlet = dynamic_cast<data_flow::Memlet&>(*(res.first->second));
540✔
1137
#ifndef NDEBUG
1138
    memlet.validate(*this->structured_sdfg_);
540✔
1139
#endif
1140

1141
    return memlet;
540✔
1142
};
×
1143

1144
data_flow::Memlet& StructuredSDFGBuilder::add_memlet(
41✔
1145
    structured_control_flow::Block& block,
1146
    data_flow::DataFlowNode& src,
1147
    const std::string& src_conn,
1148
    data_flow::DataFlowNode& dst,
1149
    const std::string& dst_conn,
1150
    const data_flow::Subset& begin_subset,
1151
    const data_flow::Subset& end_subset,
1152
    const types::IType& base_type,
1153
    const DebugInfo& debug_info
1154
) {
1155
    auto edge = boost::add_edge(src.vertex_, dst.vertex_, block.dataflow_->graph_);
41✔
1156
    auto res = block.dataflow_->edges_.insert(
82✔
1157
        {edge.first,
82✔
1158
         std::unique_ptr<data_flow::Memlet>(new data_flow::Memlet(
82✔
1159
             this->new_element_id(),
41✔
1160
             debug_info,
41✔
1161
             edge.first,
41✔
1162
             block.dataflow(),
41✔
1163
             src,
41✔
1164
             src_conn,
41✔
1165
             dst,
41✔
1166
             dst_conn,
41✔
1167
             begin_subset,
41✔
1168
             end_subset,
41✔
1169
             base_type
41✔
1170
         ))}
1171
    );
1172

1173
    auto& memlet = dynamic_cast<data_flow::Memlet&>(*(res.first->second));
41✔
1174
#ifndef NDEBUG
1175
    memlet.validate(*this->structured_sdfg_);
41✔
1176
#endif
1177

1178
    return memlet;
41✔
1179
};
×
1180

1181
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
92✔
1182
    structured_control_flow::Block& block,
1183
    data_flow::AccessNode& src,
1184
    data_flow::Tasklet& dst,
1185
    const std::string& dst_conn,
1186
    const data_flow::Subset& subset,
1187
    const types::IType& base_type,
1188
    const DebugInfo& debug_info
1189
) {
1190
    return this->add_memlet(block, src, "void", dst, dst_conn, subset, base_type, debug_info);
92✔
1191
};
×
1192

1193
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
82✔
1194
    structured_control_flow::Block& block,
1195
    data_flow::Tasklet& src,
1196
    const std::string& src_conn,
1197
    data_flow::AccessNode& dst,
1198
    const data_flow::Subset& subset,
1199
    const types::IType& base_type,
1200
    const DebugInfo& debug_info
1201
) {
1202
    return this->add_memlet(block, src, src_conn, dst, "void", subset, base_type, debug_info);
82✔
1203
};
×
1204

1205
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
88✔
1206
    structured_control_flow::Block& block,
1207
    data_flow::AccessNode& src,
1208
    data_flow::Tasklet& dst,
1209
    const std::string& dst_conn,
1210
    const data_flow::Subset& subset,
1211
    const DebugInfo& debug_info
1212
) {
1213
    auto& src_type = this->structured_sdfg_->type(src.data());
88✔
1214
    auto& base_type = types::infer_type(*this->structured_sdfg_, src_type, subset);
88✔
1215
    if (base_type.type_id() != types::TypeID::Scalar) {
88✔
1216
        throw InvalidSDFGException("Computational memlet must have a scalar type");
×
1217
    }
1218
    return this->add_memlet(block, src, "void", dst, dst_conn, subset, src_type, debug_info);
88✔
1219
};
×
1220

1221
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
265✔
1222
    structured_control_flow::Block& block,
1223
    data_flow::Tasklet& src,
1224
    const std::string& src_conn,
1225
    data_flow::AccessNode& dst,
1226
    const data_flow::Subset& subset,
1227
    const DebugInfo& debug_info
1228
) {
1229
    auto& dst_type = this->structured_sdfg_->type(dst.data());
265✔
1230
    auto& base_type = types::infer_type(*this->structured_sdfg_, dst_type, subset);
265✔
1231
    if (base_type.type_id() != types::TypeID::Scalar) {
265✔
1232
        throw InvalidSDFGException("Computational memlet must have a scalar type");
×
1233
    }
1234
    return this->add_memlet(block, src, src_conn, dst, "void", subset, dst_type, debug_info);
265✔
1235
};
×
1236

1237
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
14✔
1238
    structured_control_flow::Block& block,
1239
    data_flow::AccessNode& src,
1240
    data_flow::LibraryNode& dst,
1241
    const std::string& dst_conn,
1242
    const data_flow::Subset& begin_subset,
1243
    const data_flow::Subset& end_subset,
1244
    const types::IType& base_type,
1245
    const DebugInfo& debug_info
1246
) {
1247
    return this->add_memlet(block, src, "void", dst, dst_conn, begin_subset, end_subset, base_type, debug_info);
14✔
1248
};
×
1249

1250
data_flow::Memlet& StructuredSDFGBuilder::add_computational_memlet(
9✔
1251
    structured_control_flow::Block& block,
1252
    data_flow::LibraryNode& src,
1253
    const std::string& src_conn,
1254
    data_flow::AccessNode& dst,
1255
    const data_flow::Subset& begin_subset,
1256
    const data_flow::Subset& end_subset,
1257
    const types::IType& base_type,
1258
    const DebugInfo& debug_info
1259
) {
1260
    return this->add_memlet(block, src, src_conn, dst, "void", begin_subset, end_subset, base_type, debug_info);
9✔
1261
};
×
1262

1263
data_flow::Memlet& StructuredSDFGBuilder::add_reference_memlet(
7✔
1264
    structured_control_flow::Block& block,
1265
    data_flow::AccessNode& src,
1266
    data_flow::AccessNode& dst,
1267
    const data_flow::Subset& subset,
1268
    const types::IType& base_type,
1269
    const DebugInfo& debug_info
1270
) {
1271
    return this->add_memlet(block, src, "void", dst, "ref", subset, base_type, debug_info);
7✔
1272
};
×
1273

1274
data_flow::Memlet& StructuredSDFGBuilder::add_dereference_memlet(
6✔
1275
    structured_control_flow::Block& block,
1276
    data_flow::AccessNode& src,
1277
    data_flow::AccessNode& dst,
1278
    bool derefs_src,
1279
    const types::IType& base_type,
1280
    const DebugInfo& debug_info
1281
) {
1282
    if (derefs_src) {
6✔
1283
        return this->add_memlet(block, src, "void", dst, "deref", {symbolic::zero()}, base_type, debug_info);
3✔
1284
    } else {
1285
        return this->add_memlet(block, src, "deref", dst, "void", {symbolic::zero()}, base_type, debug_info);
3✔
1286
    }
1287
};
6✔
1288

1289
void StructuredSDFGBuilder::remove_memlet(structured_control_flow::Block& block, const data_flow::Memlet& edge) {
19✔
1290
    auto& graph = block.dataflow();
19✔
1291
    auto e = edge.edge();
19✔
1292
    boost::remove_edge(e, graph.graph_);
19✔
1293
    graph.edges_.erase(e);
19✔
1294
};
19✔
1295

1296
void StructuredSDFGBuilder::remove_node(structured_control_flow::Block& block, const data_flow::DataFlowNode& node) {
18✔
1297
    auto& graph = block.dataflow();
18✔
1298
    auto v = node.vertex();
18✔
1299
    boost::remove_vertex(v, graph.graph_);
18✔
1300
    graph.nodes_.erase(v);
18✔
1301
};
18✔
1302

1303
void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block, const data_flow::CodeNode& node) {
8✔
1304
    auto& graph = block.dataflow();
8✔
1305

1306
    std::unordered_set<const data_flow::DataFlowNode*> to_delete = {&node};
8✔
1307

1308
    // Delete incoming
1309
    std::list<const data_flow::Memlet*> iedges;
8✔
1310
    for (auto& iedge : graph.in_edges(node)) {
15✔
1311
        iedges.push_back(&iedge);
7✔
1312
    }
1313
    for (auto iedge : iedges) {
15✔
1314
        auto& src = iedge->src();
7✔
1315
        to_delete.insert(&src);
7✔
1316

1317
        auto edge = iedge->edge();
7✔
1318
        graph.edges_.erase(edge);
7✔
1319
        boost::remove_edge(edge, graph.graph_);
7✔
1320
    }
1321

1322
    // Delete outgoing
1323
    std::list<const data_flow::Memlet*> oedges;
8✔
1324
    for (auto& oedge : graph.out_edges(node)) {
16✔
1325
        oedges.push_back(&oedge);
8✔
1326
    }
1327
    for (auto oedge : oedges) {
16✔
1328
        auto& dst = oedge->dst();
8✔
1329
        to_delete.insert(&dst);
8✔
1330

1331
        auto edge = oedge->edge();
8✔
1332
        graph.edges_.erase(edge);
8✔
1333
        boost::remove_edge(edge, graph.graph_);
8✔
1334
    }
1335

1336
    // Delete nodes
1337
    for (auto obsolete_node : to_delete) {
31✔
1338
        if (graph.in_degree(*obsolete_node) == 0 && graph.out_degree(*obsolete_node) == 0) {
23✔
1339
            auto vertex = obsolete_node->vertex();
23✔
1340
            graph.nodes_.erase(vertex);
23✔
1341
            boost::remove_vertex(vertex, graph.graph_);
23✔
1342
        }
23✔
1343
    }
1344
};
8✔
1345

1346
void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block, const data_flow::AccessNode& node) {
1✔
1347
    auto& graph = block.dataflow();
1✔
1348
    if (graph.out_degree(node) != 0) {
1✔
1349
        throw InvalidSDFGException("StructuredSDFGBuilder: Access node has outgoing edges");
×
1350
    }
1351

1352
    std::list<const data_flow::Memlet*> tmp;
1✔
1353
    std::list<const data_flow::DataFlowNode*> queue = {&node};
1✔
1354
    while (!queue.empty()) {
3✔
1355
        auto current = queue.front();
2✔
1356
        queue.pop_front();
2✔
1357
        if (current != &node) {
2✔
1358
            if (dynamic_cast<const data_flow::AccessNode*>(current)) {
1✔
1359
                if (graph.in_degree(*current) > 0 || graph.out_degree(*current) > 0) {
×
1360
                    continue;
×
1361
                }
1362
            }
×
1363
        }
1✔
1364

1365
        tmp.clear();
2✔
1366
        for (auto& iedge : graph.in_edges(*current)) {
3✔
1367
            tmp.push_back(&iedge);
1✔
1368
        }
1369
        for (auto iedge : tmp) {
3✔
1370
            auto& src = iedge->src();
1✔
1371
            queue.push_back(&src);
1✔
1372

1373
            auto edge = iedge->edge();
1✔
1374
            graph.edges_.erase(edge);
1✔
1375
            boost::remove_edge(edge, graph.graph_);
1✔
1376
        }
1377

1378
        auto vertex = current->vertex();
2✔
1379
        graph.nodes_.erase(vertex);
2✔
1380
        boost::remove_vertex(vertex, graph.graph_);
2✔
1381
    }
1382
};
1✔
1383

1384
void StructuredSDFGBuilder::add_dataflow(const data_flow::DataFlowGraph& from, Block& to) {
18✔
1385
    auto& to_dataflow = to.dataflow();
18✔
1386

1387
    std::unordered_map<graph::Vertex, graph::Vertex> node_mapping;
18✔
1388
    for (auto& entry : from.nodes_) {
19✔
1389
        auto vertex = boost::add_vertex(to_dataflow.graph_);
1✔
1390
        to_dataflow.nodes_.insert({vertex, entry.second->clone(this->new_element_id(), vertex, to_dataflow)});
1✔
1391
        node_mapping.insert({entry.first, vertex});
1✔
1392
    }
1393

1394
    for (auto& entry : from.edges_) {
18✔
1395
        auto src = node_mapping[entry.second->src().vertex()];
×
1396
        auto dst = node_mapping[entry.second->dst().vertex()];
×
1397

1398
        auto edge = boost::add_edge(src, dst, to_dataflow.graph_);
×
1399

1400
        to_dataflow.edges_.insert(
×
1401
            {edge.first,
×
1402
             entry.second->clone(
×
1403
                 this->new_element_id(), edge.first, to_dataflow, *to_dataflow.nodes_[src], *to_dataflow.nodes_[dst]
×
1404
             )}
1405
        );
1406
    }
1407
};
18✔
1408

1409
} // namespace builder
1410
} // 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