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

daisytuner / sdfglib / 15703389463

17 Jun 2025 09:23AM UTC coverage: 64.573% (-0.4%) from 64.973%
15703389463

Pull #84

github

web-flow
Merge f041a27cb into 647162bdc
Pull Request #84: Use counter-based element ids

189 of 211 new or added lines in 29 files covered. (89.57%)

125 existing lines in 6 files now uncovered.

8040 of 12451 relevant lines covered (64.57%)

117.69 hits per line

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

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

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

10
using namespace sdfg::control_flow;
11
using namespace sdfg::structured_control_flow;
12

13
namespace sdfg {
14
namespace builder {
15

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

29
        nodes.insert(curr);
3✔
30
        if (curr == &end) {
3✔
31
            continue;
1✔
32
        }
33

34
        for (auto& iedge : sdfg.in_edges(*curr)) {
4✔
35
            queue.push_back(&iedge.src());
2✔
36
        }
37
    }
38

39
    return nodes;
1✔
40
};
1✔
41

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

49
    auto current = pdom_tree.at(node);
5✔
50
    while (current != nullptr) {
9✔
51
        if (current == pdom) {
9✔
52
            return true;
5✔
53
        }
54
        current = pdom_tree.at(current);
4✔
55
    }
56

57
    return false;
×
58
}
6✔
59

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

71
    return pdom;
3✔
72
}
3✔
73

74
void StructuredSDFGBuilder::traverse(const SDFG& sdfg) {
4✔
75
    // Start of SDFGS
76
    Sequence& root = *structured_sdfg_->root_;
4✔
77
    const State* start_state = &sdfg.start_state();
4✔
78

79
    auto pdom_tree = sdfg.post_dominator_tree();
4✔
80

81
    std::unordered_set<const InterstateEdge*> breaks;
4✔
82
    std::unordered_set<const InterstateEdge*> continues;
4✔
83
    for (auto& edge : sdfg.back_edges()) {
5✔
84
        continues.insert(edge);
1✔
85
    }
86

87
    std::unordered_set<const control_flow::State*> visited;
4✔
88
    this->traverse_with_loop_detection(sdfg, root, start_state, nullptr, continues, breaks,
4✔
89
                                       pdom_tree, visited);
90
};
4✔
91

92
void StructuredSDFGBuilder::traverse_with_loop_detection(
9✔
93
    const SDFG& sdfg, Sequence& scope, const State* current, const State* end,
94
    const std::unordered_set<const InterstateEdge*>& continues,
95
    const std::unordered_set<const InterstateEdge*>& breaks,
96
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree,
97
    std::unordered_set<const control_flow::State*>& visited) {
98
    if (current == end) {
9✔
99
        return;
1✔
100
    }
101

102
    auto in_edges = sdfg.in_edges(*current);
8✔
103

104
    // Loop detection
105
    std::unordered_set<const InterstateEdge*> loop_edges;
8✔
106
    for (auto& iedge : in_edges) {
13✔
107
        if (continues.find(&iedge) != continues.end()) {
5✔
108
            loop_edges.insert(&iedge);
1✔
109
        }
1✔
110
    }
111
    if (!loop_edges.empty()) {
8✔
112
        // 1. Determine nodes of loop body
113
        std::unordered_set<const control_flow::State*> body;
1✔
114
        for (auto back_edge : loop_edges) {
2✔
115
            auto loop_nodes = this->determine_loop_nodes(sdfg, back_edge->src(), back_edge->dst());
1✔
116
            body.insert(loop_nodes.begin(), loop_nodes.end());
1✔
117
        }
1✔
118

119
        // 2. Determine exit states and exit edges
120
        std::unordered_set<const control_flow::State*> exit_states;
1✔
121
        std::unordered_set<const control_flow::InterstateEdge*> exit_edges;
1✔
122
        for (auto node : body) {
4✔
123
            for (auto& edge : sdfg.out_edges(*node)) {
7✔
124
                if (body.find(&edge.dst()) == body.end()) {
4✔
125
                    exit_edges.insert(&edge);
1✔
126
                    exit_states.insert(&edge.dst());
1✔
127
                }
1✔
128
            }
129
        }
130
        if (exit_states.size() != 1) {
1✔
131
            throw UnstructuredControlFlowException();
×
132
        }
133
        const control_flow::State* exit_state = *exit_states.begin();
1✔
134

135
        for (auto& edge : breaks) {
1✔
136
            exit_edges.insert(edge);
×
137
        }
138

139
        // Collect debug information (could be removed when this is computed dynamically)
140
        DebugInfo dbg_info = current->debug_info();
1✔
141
        for (auto& edge : in_edges) {
3✔
142
            dbg_info = DebugInfo::merge(dbg_info, edge.debug_info());
2✔
143
        }
144
        for (auto node : body) {
4✔
145
            dbg_info = DebugInfo::merge(dbg_info, node->debug_info());
3✔
146
        }
147
        for (auto edge : exit_edges) {
2✔
148
            dbg_info = DebugInfo::merge(dbg_info, edge->debug_info());
1✔
149
        }
150

151
        // 3. Add while loop
152
        While& loop = this->add_while(scope, {}, dbg_info);
1✔
153

154
        std::unordered_set<const control_flow::State*> loop_visited(visited);
1✔
155
        this->traverse_without_loop_detection(sdfg, loop.root(), current, exit_state, continues,
1✔
156
                                              exit_edges, pdom_tree, loop_visited);
1✔
157

158
        this->traverse_with_loop_detection(sdfg, scope, exit_state, end, continues, breaks,
2✔
159
                                           pdom_tree, visited);
1✔
160
    } else {
1✔
161
        this->traverse_without_loop_detection(sdfg, scope, current, end, continues, breaks,
14✔
162
                                              pdom_tree, visited);
7✔
163
    }
164
};
9✔
165

166
void StructuredSDFGBuilder::traverse_without_loop_detection(
8✔
167
    const SDFG& sdfg, Sequence& scope, const State* current, const State* end,
168
    const std::unordered_set<const InterstateEdge*>& continues,
169
    const std::unordered_set<const InterstateEdge*>& breaks,
170
    const std::unordered_map<const control_flow::State*, const control_flow::State*>& pdom_tree,
171
    std::unordered_set<const control_flow::State*>& visited) {
172
    std::list<const State*> queue = {current};
8✔
173
    while (!queue.empty()) {
26✔
174
        auto curr = queue.front();
18✔
175
        queue.pop_front();
18✔
176
        if (curr == end) {
18✔
177
            continue;
3✔
178
        }
179

180
        if (visited.find(curr) != visited.end()) {
15✔
181
            throw UnstructuredControlFlowException();
×
182
        }
183
        visited.insert(curr);
15✔
184

185
        auto out_edges = sdfg.out_edges(*curr);
15✔
186
        auto out_degree = sdfg.out_degree(*curr);
15✔
187

188
        // Case 1: Sink node
189
        if (out_degree == 0) {
15✔
190
            this->add_block(scope, curr->dataflow(), {}, curr->debug_info());
4✔
191
            this->add_return(scope, {}, curr->debug_info());
4✔
192
            continue;
4✔
193
        }
194

195
        // Case 2: Transition
196
        if (out_degree == 1) {
11✔
197
            auto& oedge = *out_edges.begin();
8✔
198
            if (!oedge.is_unconditional()) {
8✔
199
                throw UnstructuredControlFlowException();
×
200
            }
201
            this->add_block(scope, curr->dataflow(), oedge.assignments(), curr->debug_info());
8✔
202

203
            if (continues.find(&oedge) != continues.end()) {
8✔
204
                this->add_continue(scope, oedge.debug_info());
×
205
            } else if (breaks.find(&oedge) != breaks.end()) {
8✔
206
                this->add_break(scope, oedge.debug_info());
×
207
            } else {
×
208
                bool starts_loop = false;
8✔
209
                for (auto& iedge : sdfg.in_edges(oedge.dst())) {
19✔
210
                    if (continues.find(&iedge) != continues.end()) {
11✔
211
                        starts_loop = true;
×
212
                        break;
×
213
                    }
214
                }
215
                if (!starts_loop) {
8✔
216
                    queue.push_back(&oedge.dst());
8✔
217
                } else {
8✔
218
                    this->traverse_with_loop_detection(sdfg, scope, &oedge.dst(), end, continues,
×
219
                                                       breaks, pdom_tree, visited);
×
220
                }
221
            }
222
            continue;
8✔
223
        }
224

225
        // Case 3: Branches
226
        if (out_degree > 1) {
3✔
227
            this->add_block(scope, curr->dataflow(), {}, curr->debug_info());
3✔
228

229
            std::vector<const InterstateEdge*> out_edges_vec;
3✔
230
            for (auto& edge : out_edges) {
9✔
231
                out_edges_vec.push_back(&edge);
6✔
232
            }
233

234
            // Best-effort approach: Find end of if-else
235
            // If not found, the branches may repeat paths yielding a large SDFG
236
            const control_flow::State* local_end =
3✔
237
                this->find_end_of_if_else(sdfg, curr, out_edges_vec, pdom_tree);
3✔
238
            if (local_end == nullptr) {
3✔
239
                local_end = end;
×
240
            }
×
241

242
            auto& if_else = this->add_if_else(scope, curr->debug_info());
3✔
243
            for (size_t i = 0; i < out_degree; i++) {
9✔
244
                auto& out_edge = out_edges_vec[i];
6✔
245

246
                auto& branch =
6✔
247
                    this->add_case(if_else, out_edge->condition(), out_edge->debug_info());
6✔
248
                if (!out_edge->assignments().empty()) {
6✔
249
                    this->add_block(branch, out_edge->assignments(), out_edge->debug_info());
2✔
250
                }
2✔
251
                if (continues.find(out_edge) != continues.end()) {
6✔
252
                    this->add_continue(branch, out_edge->debug_info());
1✔
253
                } else if (breaks.find(out_edge) != breaks.end()) {
6✔
254
                    this->add_break(branch, out_edge->debug_info());
1✔
255
                } else {
1✔
256
                    std::unordered_set<const control_flow::State*> branch_visited(visited);
4✔
257
                    this->traverse_with_loop_detection(sdfg, branch, &out_edge->dst(), local_end,
4✔
258
                                                       continues, breaks, pdom_tree,
4✔
259
                                                       branch_visited);
260
                }
4✔
261
            }
6✔
262

263
            if (local_end != end) {
3✔
264
                bool starts_loop = false;
2✔
265
                for (auto& iedge : sdfg.in_edges(*local_end)) {
6✔
266
                    if (continues.find(&iedge) != continues.end()) {
4✔
267
                        starts_loop = true;
×
268
                        break;
×
269
                    }
270
                }
271
                if (!starts_loop) {
2✔
272
                    queue.push_back(local_end);
2✔
273
                } else {
2✔
274
                    this->traverse_with_loop_detection(sdfg, scope, local_end, end, continues,
×
275
                                                       breaks, pdom_tree, visited);
×
276
                }
277
            }
2✔
278
            continue;
279
        }
3✔
280
    }
281
}
8✔
282

283
Function& StructuredSDFGBuilder::function() const {
5,345✔
284
    return static_cast<Function&>(*this->structured_sdfg_);
5,345✔
285
};
286

287
StructuredSDFGBuilder::StructuredSDFGBuilder(std::unique_ptr<StructuredSDFG>& sdfg)
86✔
288
    : FunctionBuilder(), structured_sdfg_(std::move(sdfg)) {};
86✔
289

290
StructuredSDFGBuilder::StructuredSDFGBuilder(const std::string& name, FunctionType type)
457✔
291
    : FunctionBuilder(), structured_sdfg_(new StructuredSDFG(name, type)) {};
457✔
292

293
StructuredSDFGBuilder::StructuredSDFGBuilder(const SDFG& sdfg)
4✔
294
    : FunctionBuilder(), structured_sdfg_(new StructuredSDFG(sdfg.name(), sdfg.type())) {
4✔
295
    for (auto& entry : sdfg.structures_) {
4✔
296
        this->structured_sdfg_->structures_.insert({entry.first, entry.second->clone()});
×
297
    }
298

299
    for (auto& entry : sdfg.containers_) {
11✔
300
        this->structured_sdfg_->containers_.insert({entry.first, entry.second->clone()});
7✔
301
    }
302

303
    for (auto& arg : sdfg.arguments_) {
6✔
304
        this->structured_sdfg_->arguments_.push_back(arg);
2✔
305
    }
306

307
    for (auto& ext : sdfg.externals_) {
5✔
308
        this->structured_sdfg_->externals_.push_back(ext);
1✔
309
    }
310

311
    for (auto& entry : sdfg.assumptions_) {
9✔
312
        this->structured_sdfg_->assumptions_.insert({entry.first, entry.second});
5✔
313
    }
314

315
    for (auto& entry : sdfg.metadata_) {
6✔
316
        this->structured_sdfg_->metadata_[entry.first] = entry.second;
2✔
317
    }
318

319
    this->traverse(sdfg);
4✔
320
};
4✔
321

322
StructuredSDFG& StructuredSDFGBuilder::subject() const { return *this->structured_sdfg_; };
1,288✔
323

324
std::unique_ptr<StructuredSDFG> StructuredSDFGBuilder::move() {
408✔
325
    return std::move(this->structured_sdfg_);
408✔
326
};
327

328
Sequence& StructuredSDFGBuilder::add_sequence(Sequence& parent,
29✔
329
                                              const sdfg::control_flow::Assignments& assignments,
330
                                              const DebugInfo& debug_info) {
331
    parent.children_.push_back(
58✔
332
        std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info)));
29✔
333

334
    parent.transitions_.push_back(std::unique_ptr<Transition>(
58✔
335
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
29✔
336

337
    return static_cast<Sequence&>(*parent.children_.back().get());
29✔
338
};
×
339

340
std::pair<Sequence&, Transition&> StructuredSDFGBuilder::add_sequence_before(
3✔
341
    Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
342
    // Insert block before current block
343
    int index = -1;
3✔
344
    for (size_t i = 0; i < parent.children_.size(); i++) {
4✔
345
        if (parent.children_.at(i).get() == &block) {
4✔
346
            index = i;
3✔
347
            break;
3✔
348
        }
349
    }
1✔
350
    if (index == -1) {
3✔
351
        throw InvalidSDFGException("StructuredSDFGBuilder: Block not found");
×
352
    }
353

354
    parent.children_.insert(
6✔
355
        parent.children_.begin() + index,
3✔
356
        std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info)));
3✔
357

358
    parent.transitions_.insert(
6✔
359
        parent.transitions_.begin() + index,
3✔
360
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
3✔
361

362
    auto new_entry = parent.at(index);
3✔
363
    auto& new_block = dynamic_cast<structured_control_flow::Sequence&>(new_entry.first);
3✔
364

365
    return {new_block, new_entry.second};
3✔
366
};
×
367

368
void StructuredSDFGBuilder::remove_child(Sequence& parent, size_t i) {
5✔
369
    parent.children_.erase(parent.children_.begin() + i);
5✔
370
    parent.transitions_.erase(parent.transitions_.begin() + i);
5✔
371
};
5✔
372

373
void StructuredSDFGBuilder::remove_child(Sequence& parent, ControlFlowNode& child) {
7✔
374
    int index = -1;
7✔
375
    for (size_t i = 0; i < parent.children_.size(); i++) {
10✔
376
        if (parent.children_.at(i).get() == &child) {
10✔
377
            index = i;
7✔
378
            break;
7✔
379
        }
380
    }
3✔
381

382
    parent.children_.erase(parent.children_.begin() + index);
7✔
383
    parent.transitions_.erase(parent.transitions_.begin() + index);
7✔
384
};
7✔
385

386
void StructuredSDFGBuilder::insert_children(Sequence& parent, Sequence& other, size_t i) {
10✔
387
    parent.children_.insert(parent.children_.begin() + i,
20✔
388
                            std::make_move_iterator(other.children_.begin()),
10✔
389
                            std::make_move_iterator(other.children_.end()));
10✔
390
    parent.transitions_.insert(parent.transitions_.begin() + i,
20✔
391
                               std::make_move_iterator(other.transitions_.begin()),
10✔
392
                               std::make_move_iterator(other.transitions_.end()));
10✔
393
    other.children_.clear();
10✔
394
    other.transitions_.clear();
10✔
395
};
10✔
396

397
Block& StructuredSDFGBuilder::add_block(Sequence& parent,
444✔
398
                                        const sdfg::control_flow::Assignments& assignments,
399
                                        const DebugInfo& debug_info) {
400
    parent.children_.push_back(
888✔
401
        std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
444✔
402

403
    parent.transitions_.push_back(std::unique_ptr<Transition>(
888✔
404
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
444✔
405

406
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());
444✔
407
    (*new_block.dataflow_).parent_ = &new_block;
444✔
408

409
    return new_block;
444✔
410
};
×
411

412
Block& StructuredSDFGBuilder::add_block(Sequence& parent,
21✔
413
                                        const data_flow::DataFlowGraph& data_flow_graph,
414
                                        const sdfg::control_flow::Assignments& assignments,
415
                                        const DebugInfo& debug_info) {
416
    parent.children_.push_back(
42✔
417
        std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
21✔
418

419
    parent.transitions_.push_back(std::unique_ptr<Transition>(
42✔
420
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
21✔
421

422
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(*parent.children_.back().get());
21✔
423
    (*new_block.dataflow_).parent_ = &new_block;
21✔
424

425
    this->add_dataflow(data_flow_graph, new_block);
21✔
426

427
    return new_block;
21✔
428
};
×
429

430
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_before(
10✔
431
    Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
432
    // Insert block before current block
433
    int index = -1;
10✔
434
    for (size_t i = 0; i < parent.children_.size(); i++) {
10✔
435
        if (parent.children_.at(i).get() == &block) {
10✔
436
            index = i;
10✔
437
            break;
10✔
438
        }
439
    }
×
440
    assert(index > -1);
10✔
441

442
    parent.children_.insert(parent.children_.begin() + index,
20✔
443
                            std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
10✔
444

445
    parent.transitions_.insert(
20✔
446
        parent.transitions_.begin() + index,
10✔
447
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
10✔
448

449
    auto new_entry = parent.at(index);
10✔
450
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
10✔
451
    (*new_block.dataflow_).parent_ = &new_block;
10✔
452

453
    return {new_block, new_entry.second};
10✔
454
};
×
455

456
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_before(
×
457
    Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph,
458
    const DebugInfo& debug_info) {
459
    // Insert block before current block
460
    int index = -1;
×
461
    for (size_t i = 0; i < parent.children_.size(); i++) {
×
462
        if (parent.children_.at(i).get() == &block) {
×
463
            index = i;
×
464
            break;
×
465
        }
466
    }
×
467
    assert(index > -1);
×
468

469
    parent.children_.insert(parent.children_.begin() + index,
×
NEW
470
                            std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
×
471

NEW
472
    parent.transitions_.insert(
×
NEW
473
        parent.transitions_.begin() + index,
×
NEW
474
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
×
475

476
    auto new_entry = parent.at(index);
×
477
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
×
478
    (*new_block.dataflow_).parent_ = &new_block;
×
479

NEW
480
    this->add_dataflow(data_flow_graph, new_block);
×
481

482
    return {new_block, new_entry.second};
×
483
};
×
484

485
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_after(Sequence& parent,
5✔
486
                                                                      ControlFlowNode& block,
487
                                                                      const DebugInfo& debug_info) {
488
    // Insert block before current block
489
    int index = -1;
5✔
490
    for (size_t i = 0; i < parent.children_.size(); i++) {
6✔
491
        if (parent.children_.at(i).get() == &block) {
6✔
492
            index = i;
5✔
493
            break;
5✔
494
        }
495
    }
1✔
496
    assert(index > -1);
5✔
497

498
    parent.children_.insert(parent.children_.begin() + index + 1,
10✔
499
                            std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
5✔
500

501
    parent.transitions_.insert(
10✔
502
        parent.transitions_.begin() + index + 1,
5✔
503
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
5✔
504

505
    auto new_entry = parent.at(index + 1);
5✔
506
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
5✔
507
    (*new_block.dataflow_).parent_ = &new_block;
5✔
508

509
    return {new_block, new_entry.second};
5✔
510
};
×
511

512
std::pair<Block&, Transition&> StructuredSDFGBuilder::add_block_after(
×
513
    Sequence& parent, ControlFlowNode& block, data_flow::DataFlowGraph& data_flow_graph,
514
    const DebugInfo& debug_info) {
515
    int index = -1;
×
516
    for (size_t i = 0; i < parent.children_.size(); i++) {
×
517
        if (parent.children_.at(i).get() == &block) {
×
518
            index = i;
×
519
            break;
×
520
        }
521
    }
×
522
    assert(index > -1);
×
523

524
    parent.children_.insert(parent.children_.begin() + index + 1,
×
NEW
525
                            std::unique_ptr<Block>(new Block(this->new_element_id(), debug_info)));
×
526

NEW
527
    parent.transitions_.insert(
×
NEW
528
        parent.transitions_.begin() + index + 1,
×
NEW
529
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
×
530

531
    auto new_entry = parent.at(index + 1);
×
532
    auto& new_block = dynamic_cast<structured_control_flow::Block&>(new_entry.first);
×
533
    (*new_block.dataflow_).parent_ = &new_block;
×
534

NEW
535
    this->add_dataflow(data_flow_graph, new_block);
×
536

537
    return {new_block, new_entry.second};
×
538
};
×
539

540
For& StructuredSDFGBuilder::add_for(Sequence& parent, const symbolic::Symbol& indvar,
110✔
541
                                    const symbolic::Condition& condition,
542
                                    const symbolic::Expression& init,
543
                                    const symbolic::Expression& update,
544
                                    const sdfg::control_flow::Assignments& assignments,
545
                                    const DebugInfo& debug_info) {
546
    parent.children_.push_back(std::unique_ptr<For>(
220✔
547
        new For(this->new_element_id(), debug_info, indvar, init, update, condition)));
110✔
548

549
    // Increment element id for body node
550
    this->new_element_id();
110✔
551

552
    parent.transitions_.push_back(std::unique_ptr<Transition>(
220✔
553
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
110✔
554

555
    return static_cast<For&>(*parent.children_.back().get());
110✔
556
};
×
557

558
std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_before(
4✔
559
    Sequence& parent, ControlFlowNode& block, const symbolic::Symbol& indvar,
560
    const symbolic::Condition& condition, const symbolic::Expression& init,
561
    const symbolic::Expression& update, const DebugInfo& debug_info) {
562
    // Insert block before current block
563
    int index = -1;
4✔
564
    for (size_t i = 0; i < parent.children_.size(); i++) {
4✔
565
        if (parent.children_.at(i).get() == &block) {
4✔
566
            index = i;
4✔
567
            break;
4✔
568
        }
569
    }
×
570
    assert(index > -1);
4✔
571

572
    parent.children_.insert(parent.children_.begin() + index,
8✔
573
                            std::unique_ptr<For>(new For(this->new_element_id(), debug_info, indvar,
8✔
574
                                                         init, update, condition)));
4✔
575

576
    // Increment element id for body node
577
    this->new_element_id();
4✔
578

579
    parent.transitions_.insert(
8✔
580
        parent.transitions_.begin() + index,
4✔
581
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
4✔
582

583
    auto new_entry = parent.at(index);
4✔
584
    auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);
4✔
585

586
    return {new_block, new_entry.second};
4✔
587
};
×
588

589
std::pair<For&, Transition&> StructuredSDFGBuilder::add_for_after(
7✔
590
    Sequence& parent, ControlFlowNode& block, const symbolic::Symbol& indvar,
591
    const symbolic::Condition& condition, const symbolic::Expression& init,
592
    const symbolic::Expression& update, const DebugInfo& debug_info) {
593
    // Insert block before current block
594
    int index = -1;
7✔
595
    for (size_t i = 0; i < parent.children_.size(); i++) {
9✔
596
        if (parent.children_.at(i).get() == &block) {
9✔
597
            index = i;
7✔
598
            break;
7✔
599
        }
600
    }
2✔
601
    assert(index > -1);
7✔
602

603
    parent.children_.insert(parent.children_.begin() + index + 1,
14✔
604
                            std::unique_ptr<For>(new For(this->new_element_id(), debug_info, indvar,
14✔
605
                                                         init, update, condition)));
7✔
606

607
    // Increment element id for body node
608
    this->new_element_id();
7✔
609

610
    parent.transitions_.insert(
14✔
611
        parent.transitions_.begin() + index + 1,
7✔
612
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
7✔
613

614
    auto new_entry = parent.at(index + 1);
7✔
615
    auto& new_block = dynamic_cast<structured_control_flow::For&>(new_entry.first);
7✔
616

617
    return {new_block, new_entry.second};
7✔
618
};
×
619

620
IfElse& StructuredSDFGBuilder::add_if_else(Sequence& parent, const DebugInfo& debug_info) {
31✔
621
    return this->add_if_else(parent, control_flow::Assignments{}, debug_info);
31✔
622
};
×
623

624
IfElse& StructuredSDFGBuilder::add_if_else(Sequence& parent,
33✔
625
                                           const sdfg::control_flow::Assignments& assignments,
626
                                           const DebugInfo& debug_info) {
627
    parent.children_.push_back(
66✔
628
        std::unique_ptr<IfElse>(new IfElse(this->new_element_id(), debug_info)));
33✔
629

630
    parent.transitions_.push_back(std::unique_ptr<Transition>(
66✔
631
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
33✔
632

633
    return static_cast<IfElse&>(*parent.children_.back().get());
33✔
634
};
×
635

636
std::pair<IfElse&, Transition&> StructuredSDFGBuilder::add_if_else_before(
1✔
637
    Sequence& parent, ControlFlowNode& block, const DebugInfo& debug_info) {
638
    // Insert block before current block
639
    int index = -1;
1✔
640
    for (size_t i = 0; i < parent.children_.size(); i++) {
1✔
641
        if (parent.children_.at(i).get() == &block) {
1✔
642
            index = i;
1✔
643
            break;
1✔
644
        }
645
    }
×
646
    assert(index > -1);
1✔
647

648
    parent.children_.insert(
2✔
649
        parent.children_.begin() + index,
1✔
650
        std::unique_ptr<IfElse>(new IfElse(this->new_element_id(), debug_info)));
1✔
651

652
    parent.transitions_.insert(
2✔
653
        parent.transitions_.begin() + index,
1✔
654
        std::unique_ptr<Transition>(new Transition(this->new_element_id(), debug_info, parent)));
1✔
655

656
    auto new_entry = parent.at(index);
1✔
657
    auto& new_block = dynamic_cast<structured_control_flow::IfElse&>(new_entry.first);
1✔
658

659
    return {new_block, new_entry.second};
1✔
660
};
×
661

662
Sequence& StructuredSDFGBuilder::add_case(IfElse& scope, const sdfg::symbolic::Condition cond,
57✔
663
                                          const DebugInfo& debug_info) {
664
    scope.cases_.push_back(
114✔
665
        std::unique_ptr<Sequence>(new Sequence(this->new_element_id(), debug_info)));
57✔
666

667
    scope.conditions_.push_back(cond);
57✔
668
    return *scope.cases_.back();
57✔
669
};
×
670

671
void StructuredSDFGBuilder::remove_case(IfElse& scope, size_t i, const DebugInfo& debug_info) {
1✔
672
    scope.cases_.erase(scope.cases_.begin() + i);
1✔
673
    scope.conditions_.erase(scope.conditions_.begin() + i);
1✔
674
};
1✔
675

676
While& StructuredSDFGBuilder::add_while(Sequence& parent,
34✔
677
                                        const sdfg::control_flow::Assignments& assignments,
678
                                        const DebugInfo& debug_info) {
679
    parent.children_.push_back(
68✔
680
        std::unique_ptr<While>(new While(this->new_element_id(), debug_info)));
34✔
681

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

685
    parent.transitions_.push_back(std::unique_ptr<Transition>(
68✔
686
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
34✔
687

688
    return static_cast<While&>(*parent.children_.back().get());
34✔
689
};
×
690

691
Continue& StructuredSDFGBuilder::add_continue(Sequence& parent, const DebugInfo& debug_info) {
12✔
692
    return this->add_continue(parent, control_flow::Assignments{}, debug_info);
12✔
693
};
×
694

695
Continue& StructuredSDFGBuilder::add_continue(Sequence& parent,
14✔
696
                                              const sdfg::control_flow::Assignments& assignments,
697
                                              const DebugInfo& debug_info) {
698
    // Check if continue is in a loop
699
    analysis::AnalysisManager analysis_manager(this->subject());
14✔
700
    auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
14✔
701
    auto current_scope = scope_tree_analysis.parent_scope(&parent);
14✔
702
    bool in_loop = false;
14✔
703
    while (current_scope != nullptr) {
24✔
704
        if (dynamic_cast<structured_control_flow::While*>(current_scope)) {
24✔
705
            in_loop = true;
14✔
706
            break;
14✔
707
        } else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {
10✔
708
            throw UnstructuredControlFlowException();
×
709
        }
710
        current_scope = scope_tree_analysis.parent_scope(current_scope);
10✔
711
    }
712
    if (!in_loop) {
14✔
713
        throw UnstructuredControlFlowException();
×
714
    }
715

716
    parent.children_.push_back(
28✔
717
        std::unique_ptr<Continue>(new Continue(this->new_element_id(), debug_info)));
14✔
718

719
    parent.transitions_.push_back(std::unique_ptr<Transition>(
28✔
720
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
14✔
721

722
    return static_cast<Continue&>(*parent.children_.back().get());
14✔
723
};
14✔
724

725
Break& StructuredSDFGBuilder::add_break(Sequence& parent, const DebugInfo& debug_info) {
13✔
726
    return this->add_break(parent, control_flow::Assignments{}, debug_info);
13✔
727
};
×
728

729
Break& StructuredSDFGBuilder::add_break(Sequence& parent,
15✔
730
                                        const sdfg::control_flow::Assignments& assignments,
731
                                        const DebugInfo& debug_info) {
732
    // Check if break is in a loop
733
    analysis::AnalysisManager analysis_manager(this->subject());
15✔
734
    auto& scope_tree_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
15✔
735
    auto current_scope = scope_tree_analysis.parent_scope(&parent);
15✔
736
    bool in_loop = false;
15✔
737
    while (current_scope != nullptr) {
25✔
738
        if (dynamic_cast<structured_control_flow::While*>(current_scope)) {
25✔
739
            in_loop = true;
15✔
740
            break;
15✔
741
        } else if (dynamic_cast<structured_control_flow::For*>(current_scope)) {
10✔
742
            throw UnstructuredControlFlowException();
×
743
        }
744
        current_scope = scope_tree_analysis.parent_scope(current_scope);
10✔
745
    }
746
    if (!in_loop) {
15✔
747
        throw UnstructuredControlFlowException();
×
748
    }
749

750
    parent.children_.push_back(
30✔
751
        std::unique_ptr<Break>(new Break(this->new_element_id(), debug_info)));
15✔
752

753
    parent.transitions_.push_back(std::unique_ptr<Transition>(
30✔
754
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
15✔
755

756
    return static_cast<Break&>(*parent.children_.back().get());
15✔
757
};
15✔
758

759
Return& StructuredSDFGBuilder::add_return(Sequence& parent,
13✔
760
                                          const sdfg::control_flow::Assignments& assignments,
761
                                          const DebugInfo& debug_info) {
762
    parent.children_.push_back(
26✔
763
        std::unique_ptr<Return>(new Return(this->new_element_id(), debug_info)));
13✔
764

765
    parent.transitions_.push_back(std::unique_ptr<Transition>(
26✔
766
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
13✔
767

768
    return static_cast<Return&>(*parent.children_.back().get());
13✔
769
};
×
770

771
Map& StructuredSDFGBuilder::add_map(Sequence& parent, const symbolic::Symbol& indvar,
9✔
772
                                    const symbolic::Expression& num_iterations,
773
                                    const ScheduleType& schedule_type,
774
                                    const sdfg::control_flow::Assignments& assignments,
775
                                    const DebugInfo& debug_info) {
776
    parent.children_.push_back(std::unique_ptr<Map>(
18✔
777
        new Map(this->new_element_id(), debug_info, indvar, num_iterations, schedule_type)));
9✔
778

779
    parent.transitions_.push_back(std::unique_ptr<Transition>(
18✔
780
        new Transition(this->new_element_id(), debug_info, parent, assignments)));
9✔
781

782
    return static_cast<Map&>(*parent.children_.back().get());
9✔
NEW
783
};
×
784

UNCOV
785
For& StructuredSDFGBuilder::convert_while(Sequence& parent, While& loop,
×
786
                                          const symbolic::Symbol& indvar,
787
                                          const symbolic::Condition& condition,
788
                                          const symbolic::Expression& init,
789
                                          const symbolic::Expression& update) {
790
    // Insert for loop
UNCOV
791
    size_t index = 0;
×
UNCOV
792
    for (auto& entry : parent.children_) {
×
UNCOV
793
        if (entry.get() == &loop) {
×
794
            break;
×
795
        }
796
        index++;
×
797
    }
UNCOV
798
    auto iter = parent.children_.begin() + index;
×
799
    auto& new_iter = *parent.children_.insert(
×
UNCOV
800
        iter + 1, std::unique_ptr<For>(new For(this->new_element_id(), loop.debug_info(), indvar,
×
801
                                               init, update, condition)));
×
802

803
    // Increment element id for body node
NEW
804
    this->new_element_id();
×
805

NEW
806
    auto& for_loop = dynamic_cast<For&>(*new_iter);
×
NEW
807
    this->insert_children(for_loop.root(), loop.root(), 0);
×
808

809
    // Remove while loop
810
    parent.children_.erase(parent.children_.begin() + index);
×
811

UNCOV
812
    return for_loop;
×
813
};
×
814

815
Map& StructuredSDFGBuilder::convert_for(Sequence& parent, For& loop,
3✔
816
                                        const symbolic::Expression& num_iterations) {
817
    // Insert for loop
818
    size_t index = 0;
3✔
819
    for (auto& entry : parent.children_) {
3✔
820
        if (entry.get() == &loop) {
3✔
821
            break;
3✔
822
        }
UNCOV
823
        index++;
×
824
    }
825
    auto iter = parent.children_.begin() + index;
3✔
826
    auto& new_iter = *parent.children_.insert(
6✔
827
        iter + 1,
3✔
828
        std::unique_ptr<Map>(new Map(this->new_element_id(), loop.debug_info(), loop.indvar(),
6✔
829
                                     num_iterations, ScheduleType_Sequential)));
3✔
830

831
    // Increment element id for body node
832
    this->new_element_id();
3✔
833

834
    auto& map = dynamic_cast<Map&>(*new_iter);
3✔
835
    this->insert_children(map.root(), loop.root(), 0);
3✔
836

837
    // Remove for loop
838
    parent.children_.erase(parent.children_.begin() + index);
3✔
839

840
    return map;
3✔
UNCOV
841
};
×
842

843
void StructuredSDFGBuilder::clear_sequence(Sequence& parent) {
1✔
844
    parent.children_.clear();
1✔
845
    parent.transitions_.clear();
1✔
846
};
1✔
847

848
Sequence& StructuredSDFGBuilder::parent(const ControlFlowNode& node) {
13✔
849
    std::list<structured_control_flow::ControlFlowNode*> queue = {&this->structured_sdfg_->root()};
13✔
850
    while (!queue.empty()) {
41✔
851
        auto current = queue.front();
41✔
852
        queue.pop_front();
41✔
853

854
        if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
41✔
855
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
41✔
856
                if (&sequence_stmt->at(i).first == &node) {
27✔
857
                    return *sequence_stmt;
13✔
858
                }
859
                queue.push_back(&sequence_stmt->at(i).first);
14✔
860
            }
14✔
861
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
28✔
UNCOV
862
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
×
UNCOV
863
                queue.push_back(&if_else_stmt->at(i).first);
×
UNCOV
864
            }
×
865
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
14✔
866
            queue.push_back(&while_stmt->root());
×
867
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
14✔
868
            queue.push_back(&for_stmt->root());
14✔
869
        }
14✔
870
    }
871

UNCOV
872
    return this->structured_sdfg_->root();
×
873
};
13✔
874

875
/***** Section: Dataflow Graph *****/
876

877
data_flow::AccessNode& StructuredSDFGBuilder::add_access(structured_control_flow::Block& block,
550✔
878
                                                         const std::string& data,
879
                                                         const DebugInfo& debug_info) {
880
    // Check: Data exists
881
    if (!this->subject().exists(data)) {
550✔
UNCOV
882
        throw InvalidSDFGException("Data does not exist in SDFG: " + data);
×
883
    }
884

885
    auto vertex = boost::add_vertex(block.dataflow_->graph_);
550✔
886
    auto res = block.dataflow_->nodes_.insert(
1,100✔
887
        {vertex, std::unique_ptr<data_flow::AccessNode>(new data_flow::AccessNode(
1,100✔
888
                     this->new_element_id(), debug_info, vertex, block.dataflow(), data))});
550✔
889

890
    return dynamic_cast<data_flow::AccessNode&>(*(res.first->second));
550✔
NEW
891
};
×
892

893
data_flow::Tasklet& StructuredSDFGBuilder::add_tasklet(
348✔
894
    structured_control_flow::Block& block, const data_flow::TaskletCode code,
895
    const std::pair<std::string, sdfg::types::Scalar>& output,
896
    const std::vector<std::pair<std::string, sdfg::types::Scalar>>& inputs,
897
    const DebugInfo& debug_info) {
898
    // Check: Duplicate inputs
899
    std::unordered_set<std::string> input_names;
348✔
900
    for (auto& input : inputs) {
801✔
901
        if (!input.first.starts_with("_in")) {
453✔
902
            continue;
242✔
903
        }
904
        if (input_names.find(input.first) != input_names.end()) {
211✔
UNCOV
905
            throw InvalidSDFGException("Input " + input.first + " already exists in SDFG");
×
906
        }
907
        input_names.insert(input.first);
211✔
908
    }
909

910
    auto vertex = boost::add_vertex(block.dataflow_->graph_);
348✔
911
    auto res = block.dataflow_->nodes_.insert(
696✔
912
        {vertex, std::unique_ptr<data_flow::Tasklet>(new data_flow::Tasklet(
696✔
913
                     this->new_element_id(), debug_info, vertex, block.dataflow(), code, output,
348✔
914
                     inputs, symbolic::__true__()))});
348✔
915

916
    return dynamic_cast<data_flow::Tasklet&>(*(res.first->second));
348✔
917
};
348✔
918

919
data_flow::Memlet& StructuredSDFGBuilder::add_memlet(
561✔
920
    structured_control_flow::Block& block, data_flow::DataFlowNode& src,
921
    const std::string& src_conn, data_flow::DataFlowNode& dst, const std::string& dst_conn,
922
    const data_flow::Subset& subset, const DebugInfo& debug_info) {
923
    auto& function_ = this->function();
561✔
924

925
    // Check - Case 1: Access Node -> Access Node
926
    // - src_conn or dst_conn must be refs. The other must be void.
927
    // - The side of the memlet that is void, is dereferenced.
928
    // - The dst type must always be a pointer after potential dereferencing.
929
    // - The src type can be any type after dereferecing (&dereferenced_src_type).
930
    if (dynamic_cast<data_flow::AccessNode*>(&src) && dynamic_cast<data_flow::AccessNode*>(&dst)) {
561✔
931
        auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);
2✔
932
        auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);
2✔
933
        if (src_conn == "refs") {
2✔
UNCOV
934
            if (dst_conn != "void") {
×
UNCOV
935
                throw InvalidSDFGException("Invalid dst connector: " + dst_conn);
×
936
            }
937

938
            auto& dst_type = types::infer_type(function_, function_.type(dst_node.data()), subset);
×
UNCOV
939
            if (!dynamic_cast<const types::Pointer*>(&dst_type)) {
×
UNCOV
940
                throw InvalidSDFGException("dst type must be a pointer");
×
941
            }
942

943
            auto& src_type = function_.type(src_node.data());
×
UNCOV
944
            if (!dynamic_cast<const types::Pointer*>(&src_type)) {
×
UNCOV
945
                throw InvalidSDFGException("src type must be a pointer");
×
946
            }
947
        } else if (src_conn == "void") {
2✔
948
            if (dst_conn != "refs") {
2✔
UNCOV
949
                throw InvalidSDFGException("Invalid dst connector: " + dst_conn);
×
950
            }
951

952
            if (symbolic::is_pointer(symbolic::symbol(src_node.data()))) {
2✔
UNCOV
953
                throw InvalidSDFGException("src_conn is void: src cannot be a raw pointer");
×
954
            }
955

956
            // Trivially correct but checks inference
957
            auto& src_type = types::infer_type(function_, function_.type(src_node.data()), subset);
2✔
958
            types::Pointer ref_type(src_type);
2✔
959
            if (!dynamic_cast<const types::Pointer*>(&ref_type)) {
960
                throw InvalidSDFGException("src type must be a pointer");
961
            }
962

963
            auto& dst_type = function_.type(dst_node.data());
2✔
964
            if (!dynamic_cast<const types::Pointer*>(&dst_type)) {
2✔
UNCOV
965
                throw InvalidSDFGException("dst type must be a pointer");
×
966
            }
967
        } else {
2✔
968
            throw InvalidSDFGException("Invalid src connector: " + src_conn);
×
969
        }
970
    } else if (dynamic_cast<data_flow::AccessNode*>(&src) &&
772✔
971
               dynamic_cast<data_flow::Tasklet*>(&dst)) {
211✔
972
        auto& src_node = dynamic_cast<data_flow::AccessNode&>(src);
211✔
973
        auto& dst_node = dynamic_cast<data_flow::Tasklet&>(dst);
211✔
974
        if (src_conn != "void") {
211✔
UNCOV
975
            throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);
×
976
        }
977
        bool found = false;
211✔
978
        for (auto& input : dst_node.inputs()) {
270✔
979
            if (input.first == dst_conn) {
270✔
980
                found = true;
211✔
981
                break;
211✔
982
            }
983
        }
984
        if (!found) {
211✔
UNCOV
985
            throw InvalidSDFGException("dst_conn not found in tasklet: " + dst_conn);
×
986
        }
987
        auto& element_type = types::infer_type(function_, function_.type(src_node.data()), subset);
211✔
988
        if (!dynamic_cast<const types::Scalar*>(&element_type)) {
211✔
UNCOV
989
            throw InvalidSDFGException("Tasklets inputs must be scalars");
×
990
        }
991
    } else if (dynamic_cast<data_flow::Tasklet*>(&src) &&
907✔
992
               dynamic_cast<data_flow::AccessNode*>(&dst)) {
348✔
993
        auto& src_node = dynamic_cast<data_flow::Tasklet&>(src);
348✔
994
        auto& dst_node = dynamic_cast<data_flow::AccessNode&>(dst);
348✔
995
        if (src_conn != src_node.output().first) {
348✔
UNCOV
996
            throw InvalidSDFGException("src_conn must match tasklet output name");
×
997
        }
998
        if (dst_conn != "void") {
348✔
999
            throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);
×
1000
        }
1001

1002
        auto& element_type = types::infer_type(function_, function_.type(dst_node.data()), subset);
348✔
1003
        if (!dynamic_cast<const types::Scalar*>(&element_type)) {
348✔
UNCOV
1004
            throw InvalidSDFGException("Tasklet output must be a scalar");
×
1005
        }
1006
    } else if (dynamic_cast<data_flow::AccessNode*>(&src) &&
348✔
1007
               dynamic_cast<data_flow::LibraryNode*>(&dst)) {
×
UNCOV
1008
        auto& dst_node = dynamic_cast<data_flow::LibraryNode&>(dst);
×
UNCOV
1009
        if (src_conn != "void") {
×
1010
            throw InvalidSDFGException("src_conn must be void. Found: " + src_conn);
×
1011
        }
1012
        bool found = false;
×
1013
        for (auto& input : dst_node.inputs()) {
×
UNCOV
1014
            if (input == dst_conn) {
×
1015
                found = true;
×
1016
                break;
×
1017
            }
1018
        }
1019
        if (!found) {
×
UNCOV
1020
            throw InvalidSDFGException("dst_conn not found in library node: " + dst_conn);
×
1021
        }
1022
    } else if (dynamic_cast<data_flow::LibraryNode*>(&src) &&
×
1023
               dynamic_cast<data_flow::AccessNode*>(&dst)) {
×
UNCOV
1024
        auto& src_node = dynamic_cast<data_flow::LibraryNode&>(src);
×
1025
        if (dst_conn != "void") {
×
1026
            throw InvalidSDFGException("dst_conn must be void. Found: " + dst_conn);
×
1027
        }
1028
        bool found = false;
×
1029
        for (auto& output : src_node.outputs()) {
×
UNCOV
1030
            if (output == src_conn) {
×
1031
                found = true;
×
1032
                break;
×
1033
            }
1034
        }
1035
        if (!found) {
×
UNCOV
1036
            throw InvalidSDFGException("src_conn not found in library node: " + src_conn);
×
1037
        }
1038
    } else {
×
1039
        throw InvalidSDFGException("Invalid src or dst node type");
×
1040
    }
1041

1042
    auto edge = boost::add_edge(src.vertex_, dst.vertex_, block.dataflow_->graph_);
561✔
1043
    auto res = block.dataflow_->edges_.insert(
1,122✔
1044
        {edge.first, std::unique_ptr<data_flow::Memlet>(new data_flow::Memlet(
1,122✔
1045
                         this->new_element_id(), debug_info, edge.first, block.dataflow(), src,
561✔
1046
                         src_conn, dst, dst_conn, subset))});
561✔
1047

1048
    return dynamic_cast<data_flow::Memlet&>(*(res.first->second));
561✔
NEW
1049
};
×
1050

UNCOV
1051
void StructuredSDFGBuilder::remove_memlet(structured_control_flow::Block& block,
×
1052
                                          const data_flow::Memlet& edge) {
UNCOV
1053
    auto& graph = block.dataflow();
×
1054
    auto e = edge.edge();
×
UNCOV
1055
    boost::remove_edge(e, graph.graph_);
×
1056
    graph.edges_.erase(e);
×
1057
};
×
1058

1059
void StructuredSDFGBuilder::remove_node(structured_control_flow::Block& block,
×
1060
                                        const data_flow::DataFlowNode& node) {
UNCOV
1061
    auto& graph = block.dataflow();
×
1062
    auto v = node.vertex();
×
UNCOV
1063
    boost::remove_vertex(v, graph.graph_);
×
1064
    graph.nodes_.erase(v);
×
1065
};
×
1066

1067
void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block,
8✔
1068
                                       const data_flow::Tasklet& node) {
1069
    auto& graph = block.dataflow();
8✔
1070

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

1073
    // Delete incoming
1074
    std::list<const data_flow::Memlet*> iedges;
8✔
1075
    for (auto& iedge : graph.in_edges(node)) {
15✔
1076
        iedges.push_back(&iedge);
7✔
1077
    }
1078
    for (auto iedge : iedges) {
15✔
1079
        auto& src = iedge->src();
7✔
1080
        to_delete.insert(&src);
7✔
1081

1082
        auto edge = iedge->edge();
7✔
1083
        graph.edges_.erase(edge);
7✔
1084
        boost::remove_edge(edge, graph.graph_);
7✔
1085
    }
1086

1087
    // Delete outgoing
1088
    std::list<const data_flow::Memlet*> oedges;
8✔
1089
    for (auto& oedge : graph.out_edges(node)) {
16✔
1090
        oedges.push_back(&oedge);
8✔
1091
    }
1092
    for (auto oedge : oedges) {
16✔
1093
        auto& dst = oedge->dst();
8✔
1094
        to_delete.insert(&dst);
8✔
1095

1096
        auto edge = oedge->edge();
8✔
1097
        graph.edges_.erase(edge);
8✔
1098
        boost::remove_edge(edge, graph.graph_);
8✔
1099
    }
1100

1101
    // Delete nodes
1102
    for (auto obsolete_node : to_delete) {
31✔
1103
        if (graph.in_degree(*obsolete_node) == 0 && graph.out_degree(*obsolete_node) == 0) {
23✔
1104
            auto vertex = obsolete_node->vertex();
23✔
1105
            graph.nodes_.erase(vertex);
23✔
1106
            boost::remove_vertex(vertex, graph.graph_);
23✔
1107
        }
23✔
1108
    }
1109
};
8✔
1110

1111
void StructuredSDFGBuilder::clear_node(structured_control_flow::Block& block,
1✔
1112
                                       const data_flow::AccessNode& node) {
1113
    auto& graph = block.dataflow();
1✔
1114
    if (graph.out_degree(node) != 0) {
1✔
UNCOV
1115
        throw InvalidSDFGException("StructuredSDFGBuilder: Access node has outgoing edges");
×
1116
    }
1117

1118
    std::list<const data_flow::Memlet*> tmp;
1✔
1119
    std::list<const data_flow::DataFlowNode*> queue = {&node};
1✔
1120
    while (!queue.empty()) {
3✔
1121
        auto current = queue.front();
2✔
1122
        queue.pop_front();
2✔
1123
        if (current != &node) {
2✔
1124
            if (dynamic_cast<const data_flow::AccessNode*>(current)) {
1✔
UNCOV
1125
                if (graph.in_degree(*current) > 0 || graph.out_degree(*current) > 0) {
×
UNCOV
1126
                    continue;
×
1127
                }
1128
            }
×
1129
        }
1✔
1130

1131
        tmp.clear();
2✔
1132
        for (auto& iedge : graph.in_edges(*current)) {
3✔
1133
            tmp.push_back(&iedge);
1✔
1134
        }
1135
        for (auto iedge : tmp) {
3✔
1136
            auto& src = iedge->src();
1✔
1137
            queue.push_back(&src);
1✔
1138

1139
            auto edge = iedge->edge();
1✔
1140
            graph.edges_.erase(edge);
1✔
1141
            boost::remove_edge(edge, graph.graph_);
1✔
1142
        }
1143

1144
        auto vertex = current->vertex();
2✔
1145
        graph.nodes_.erase(vertex);
2✔
1146
        boost::remove_vertex(vertex, graph.graph_);
2✔
1147
    }
1148
};
1✔
1149

UNCOV
1150
data_flow::AccessNode& StructuredSDFGBuilder::symbolic_expression_to_dataflow(
×
1151
    structured_control_flow::Block& parent, const symbolic::Expression& expr) {
UNCOV
1152
    auto& sdfg = this->subject();
×
1153

UNCOV
1154
    codegen::CPPLanguageExtension language_extension;
×
1155

1156
    // Base cases
1157
    if (SymEngine::is_a<SymEngine::Symbol>(*expr)) {
×
UNCOV
1158
        auto sym = SymEngine::rcp_static_cast<const SymEngine::Symbol>(expr);
×
1159

1160
        // Determine type
1161
        types::Scalar sym_type = types::Scalar(types::PrimitiveType::Void);
×
UNCOV
1162
        if (symbolic::is_nv(sym)) {
×
UNCOV
1163
            sym_type = types::Scalar(types::PrimitiveType::Int32);
×
1164
        } else {
×
1165
            sym_type = static_cast<const types::Scalar&>(sdfg.type(sym->get_name()));
×
1166
        }
1167

1168
        // Add new container for intermediate result
UNCOV
1169
        auto tmp = this->find_new_name();
×
UNCOV
1170
        this->add_container(tmp, sym_type);
×
1171

1172
        // Create dataflow graph
1173
        auto& input_node = this->add_access(parent, sym->get_name());
×
UNCOV
1174
        auto& output_node = this->add_access(parent, tmp);
×
UNCOV
1175
        auto& tasklet = this->add_tasklet(parent, data_flow::TaskletCode::assign,
×
1176
                                          {"_out", sym_type}, {{"_in", sym_type}});
×
1177
        this->add_memlet(parent, input_node, "void", tasklet, "_in", {});
×
1178
        this->add_memlet(parent, tasklet, "_out", output_node, "void", {});
×
1179

1180
        return output_node;
×
1181
    } else if (SymEngine::is_a<SymEngine::Integer>(*expr)) {
×
UNCOV
1182
        auto tmp = this->find_new_name();
×
1183
        this->add_container(tmp, types::Scalar(types::PrimitiveType::Int64));
×
1184

1185
        auto& output_node = this->add_access(parent, tmp);
×
1186
        auto& tasklet = this->add_tasklet(
×
UNCOV
1187
            parent, data_flow::TaskletCode::assign,
×
1188
            {"_out", types::Scalar(types::PrimitiveType::Int64)},
×
1189
            {{language_extension.expression(expr), types::Scalar(types::PrimitiveType::Int64)}});
×
1190
        this->add_memlet(parent, tasklet, "_out", output_node, "void", {});
×
1191
        return output_node;
×
1192
    } else if (SymEngine::is_a<SymEngine::BooleanAtom>(*expr)) {
×
1193
        auto tmp = this->find_new_name();
×
1194
        this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));
×
1195

1196
        auto& output_node = this->add_access(parent, tmp);
×
1197
        auto& tasklet = this->add_tasklet(
×
UNCOV
1198
            parent, data_flow::TaskletCode::assign,
×
1199
            {"_out", types::Scalar(types::PrimitiveType::Bool)},
×
1200
            {{language_extension.expression(expr), types::Scalar(types::PrimitiveType::Bool)}});
×
1201
        this->add_memlet(parent, tasklet, "_out", output_node, "void", {});
×
1202
        return output_node;
×
1203
    } else if (SymEngine::is_a<SymEngine::Or>(*expr)) {
×
1204
        auto or_expr = SymEngine::rcp_static_cast<const SymEngine::Or>(expr);
×
1205
        if (or_expr->get_container().size() != 2) {
×
1206
            throw InvalidSDFGException(
×
1207
                "StructuredSDFGBuilder: Or expression must have exactly two arguments");
×
1208
        }
1209

1210
        std::vector<data_flow::AccessNode*> input_nodes;
×
UNCOV
1211
        std::vector<std::pair<std::string, types::Scalar>> input_types;
×
UNCOV
1212
        for (auto& arg : or_expr->get_container()) {
×
1213
            auto& input_node = symbolic_expression_to_dataflow(parent, arg);
×
1214
            input_nodes.push_back(&input_node);
×
1215
            input_types.push_back(
×
1216
                {"_in" + std::to_string(input_types.size() + 1),
×
1217
                 static_cast<const types::Scalar&>(sdfg.type(input_node.data()))});
×
1218
        }
1219

1220
        // Add new container for intermediate result
UNCOV
1221
        auto tmp = this->find_new_name();
×
UNCOV
1222
        this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));
×
1223

1224
        auto& output_node = this->add_access(parent, tmp);
×
1225
        auto& tasklet =
×
UNCOV
1226
            this->add_tasklet(parent, data_flow::TaskletCode::logical_or,
×
1227
                              {"_out", types::Scalar(types::PrimitiveType::Bool)}, input_types);
×
1228
        for (size_t i = 0; i < input_nodes.size(); i++) {
×
1229
            this->add_memlet(parent, *input_nodes.at(i), "void", tasklet, input_types.at(i).first,
×
1230
                             {});
×
1231
        }
×
1232
        this->add_memlet(parent, tasklet, "_out", output_node, "void", {});
×
1233
        return output_node;
×
1234
    } else if (SymEngine::is_a<SymEngine::And>(*expr)) {
×
1235
        auto and_expr = SymEngine::rcp_static_cast<const SymEngine::And>(expr);
×
1236
        if (and_expr->get_container().size() != 2) {
×
1237
            throw InvalidSDFGException(
×
1238
                "StructuredSDFGBuilder: And expression must have exactly two arguments");
×
1239
        }
1240

1241
        std::vector<data_flow::AccessNode*> input_nodes;
×
UNCOV
1242
        std::vector<std::pair<std::string, types::Scalar>> input_types;
×
UNCOV
1243
        for (auto& arg : and_expr->get_container()) {
×
1244
            auto& input_node = symbolic_expression_to_dataflow(parent, arg);
×
1245
            input_nodes.push_back(&input_node);
×
1246
            input_types.push_back(
×
1247
                {"_in" + std::to_string(input_types.size() + 1),
×
1248
                 static_cast<const types::Scalar&>(sdfg.type(input_node.data()))});
×
1249
        }
1250

1251
        // Add new container for intermediate result
UNCOV
1252
        auto tmp = this->find_new_name();
×
UNCOV
1253
        this->add_container(tmp, types::Scalar(types::PrimitiveType::Bool));
×
1254

1255
        auto& output_node = this->add_access(parent, tmp);
×
1256
        auto& tasklet =
×
UNCOV
1257
            this->add_tasklet(parent, data_flow::TaskletCode::logical_and,
×
1258
                              {"_out", types::Scalar(types::PrimitiveType::Bool)}, input_types);
×
1259
        for (size_t i = 0; i < input_nodes.size(); i++) {
×
1260
            this->add_memlet(parent, *input_nodes.at(i), "void", tasklet, input_types.at(i).first,
×
1261
                             {});
×
1262
        }
×
1263
        this->add_memlet(parent, tasklet, "_out", output_node, "void", {});
×
1264
        return output_node;
×
1265
    } else {
×
1266
        throw std::runtime_error("Unsupported expression type");
×
1267
    }
1268
};
×
1269

1270
void StructuredSDFGBuilder::add_dataflow(const data_flow::DataFlowGraph& from, Block& to) {
21✔
1271
    auto& to_dataflow = to.dataflow();
21✔
1272

1273
    std::unordered_map<graph::Vertex, graph::Vertex> node_mapping;
21✔
1274
    for (auto& entry : from.nodes_) {
28✔
1275
        auto vertex = boost::add_vertex(to_dataflow.graph_);
7✔
1276
        to_dataflow.nodes_.insert(
14✔
1277
            {vertex, entry.second->clone(this->new_element_id(), vertex, to_dataflow)});
7✔
1278
        node_mapping.insert({entry.first, vertex});
7✔
1279
    }
1280

1281
    for (auto& entry : from.edges_) {
25✔
1282
        auto src = node_mapping[entry.second->src().vertex()];
4✔
1283
        auto dst = node_mapping[entry.second->dst().vertex()];
4✔
1284

1285
        auto edge = boost::add_edge(src, dst, to_dataflow.graph_);
4✔
1286

1287
        to_dataflow.edges_.insert(
8✔
1288
            {edge.first, entry.second->clone(this->new_element_id(), edge.first, to_dataflow,
8✔
1289
                                             *to_dataflow.nodes_[src], *to_dataflow.nodes_[dst])});
4✔
1290
    }
1291
};
21✔
1292

1293
}  // namespace builder
1294
}  // 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