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

daisytuner / sdfglib / 20283073339

16 Dec 2025 09:20PM UTC coverage: 40.075% (-0.01%) from 40.086%
20283073339

push

github

web-flow
Merge pull request #395 from daisytuner/perf-improvs

Various performance improvements

13514 of 43711 branches covered (30.92%)

Branch coverage included in aggregate %.

132 of 169 new or added lines in 9 files covered. (78.11%)

11 existing lines in 5 files now uncovered.

11632 of 19037 relevant lines covered (61.1%)

87.78 hits per line

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

70.57
/src/analysis/data_dependency_analysis.cpp
1
#include "sdfg/analysis/data_dependency_analysis.h"
2

3
#include <cassert>
4
#include <string>
5
#include <unordered_map>
6
#include <unordered_set>
7
#include <vector>
8

9
#include "sdfg/analysis/analysis.h"
10
#include "sdfg/analysis/loop_analysis.h"
11
#include "sdfg/structured_sdfg.h"
12
#include "sdfg/symbolic/maps.h"
13
#include "sdfg/symbolic/sets.h"
14

15
namespace sdfg {
16
namespace analysis {
17

18
DataDependencyAnalysis::DataDependencyAnalysis(StructuredSDFG& sdfg, bool detailed)
100✔
19
    : Analysis(sdfg), node_(sdfg.root()), detailed_(detailed) {
100!
20

21
      };
100✔
22

23
DataDependencyAnalysis::DataDependencyAnalysis(StructuredSDFG& sdfg, structured_control_flow::Sequence& node, bool detailed)
×
24
    : Analysis(sdfg), node_(node), detailed_(detailed) {
×
25

26
      };
×
27

28
void DataDependencyAnalysis::run(analysis::AnalysisManager& analysis_manager) {
75✔
29
    results_.clear();
75✔
30
    undefined_users_.clear();
75✔
31
    loop_carried_dependencies_.clear();
75✔
32

33
    std::unordered_set<User*> undefined;
75✔
34
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions;
75✔
35
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions;
75✔
36

37
    auto& assumptions_analysis = analysis_manager.get<AssumptionsAnalysis>();
75!
38
    auto& users = analysis_manager.get<Users>();
75!
39
    auto& dominance_analysis = analysis_manager.get<DominanceAnalysis>();
75!
40

41
    visit_sequence(users, assumptions_analysis, dominance_analysis, node_, undefined, open_definitions, closed_definitions);
75!
42

43
    for (auto& entry : open_definitions) {
297✔
44
        closed_definitions.insert(entry);
222!
45
    }
46

47
    for (auto& entry : closed_definitions) {
308✔
48
        if (results_.find(entry.first->container()) == results_.end()) {
233!
49
            results_.insert({entry.first->container(), {}});
149!
50
        }
149✔
51
        results_.at(entry.first->container()).insert(entry);
233!
52
    }
53
};
75✔
54

55
/****** Visitor API ******/
56

57
void DataDependencyAnalysis::visit_block(
175✔
58
    analysis::Users& users,
59
    analysis::AssumptionsAnalysis& assumptions_analysis,
60
    analysis::DominanceAnalysis& dominance_analysis,
61
    structured_control_flow::Block& block,
62
    std::unordered_set<User*>& undefined,
63
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
64
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
65
) {
66
    auto& dataflow = block.dataflow();
175✔
67

68
    for (auto node : dataflow.topological_sort()) {
430✔
69
        if (dynamic_cast<data_flow::ConstantNode*>(node) != nullptr) {
255!
70
            continue;
17✔
71
        }
72

73
        if (auto access_node = dynamic_cast<data_flow::AccessNode*>(node)) {
238!
74
            if (!symbolic::is_pointer(symbolic::symbol(access_node->data()))) {
150!
75
                if (dataflow.in_degree(*node) > 0) {
150!
76
                    Use use = Use::WRITE;
89✔
77
                    for (auto& iedge : dataflow.in_edges(*access_node)) {
177!
78
                        if (iedge.type() == data_flow::MemletType::Reference ||
178!
79
                            iedge.type() == data_flow::MemletType::Dereference_Src) {
89!
80
                            use = Use::MOVE;
1✔
81
                            break;
1✔
82
                        }
83
                    }
84

85
                    if (use == Use::WRITE) {
89✔
86
                        auto current_user = users.get_user(access_node->data(), access_node, use);
88!
87

88
                        // Close open definitions if possible
89
                        std::unordered_map<User*, std::unordered_set<User*>> to_close;
88✔
90
                        for (auto& user : open_definitions) {
127✔
91
                            if (this->closes(assumptions_analysis, dominance_analysis, *user.first, *current_user, false)) {
39!
92
                                to_close.insert(user);
7!
93
                            }
7✔
94
                        }
95
                        for (auto& user : to_close) {
95✔
96
                            open_definitions.erase(user.first);
7!
97
                            closed_definitions.insert(user);
7!
98
                        }
99

100
                        // Start new open definition
101
                        open_definitions.insert({current_user, {}});
88!
102
                    }
88✔
103
                }
89✔
104
                if (dataflow.out_degree(*access_node) > 0) {
150!
105
                    Use use = Use::READ;
64✔
106
                    for (auto& oedge : dataflow.out_edges(*access_node)) {
129!
107
                        if (oedge.type() == data_flow::MemletType::Reference ||
130!
108
                            oedge.type() == data_flow::MemletType::Dereference_Dst) {
65!
109
                            use = Use::VIEW;
×
110
                            break;
×
111
                        }
112
                    }
113

114
                    if (use == Use::READ) {
64!
115
                        auto current_user = users.get_user(access_node->data(), access_node, use);
64!
116

117
                        // Assign to open definitions
118
                        bool found_user = false;
64✔
119
                        bool found_undefined_user = false;
64✔
120
                        for (auto& user : open_definitions) {
90✔
121
                            if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
26!
122
                                user.second.insert(current_user);
12!
123
                                found_user = true;
12✔
124
                                found_undefined_user = this->is_undefined_user(*user.first);
12!
125
                            }
12✔
126
                        }
127
                        // If no definition found or undefined user found, mark as undefined
128
                        if (!found_user || found_undefined_user) {
64✔
129
                            undefined.insert(current_user);
55!
130
                        }
55✔
131
                    }
64✔
132
                }
64✔
133
            }
150✔
134
        } else if (auto library_node = dynamic_cast<data_flow::LibraryNode*>(node)) {
238!
135
            for (auto& symbol : library_node->symbols()) {
×
136
                auto current_user = users.get_user(symbol->get_name(), library_node, Use::READ);
×
137

138
                // Assign to open definitions
139
                bool found_user = false;
×
140
                bool found_undefined_user = false;
×
141
                for (auto& user : open_definitions) {
×
142
                    if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
×
143
                        user.second.insert(current_user);
×
144
                        found_user = true;
×
145
                        found_undefined_user = this->is_undefined_user(*current_user);
×
146
                    }
×
147
                }
148
                // If no definition found or undefined user found, mark as undefined
149
                if (!found_user || found_undefined_user) {
×
150
                    undefined.insert(current_user);
×
151
                }
×
152
            }
153
        }
×
154

155
        for (auto& oedge : dataflow.out_edges(*node)) {
391!
156
            std::unordered_set<std::string> used;
153✔
157
            for (auto& dim : oedge.subset()) {
290!
158
                for (auto atom : symbolic::atoms(dim)) {
237!
159
                    used.insert(atom->get_name());
100!
160
                }
100✔
161
            }
162
            for (auto& atom : used) {
253✔
163
                auto current_user = users.get_user(atom, &oedge, Use::READ);
100!
164

165
                // Assign to open definitions
166
                bool found_user = false;
100✔
167
                bool found_undefined_user = false;
100✔
168
                for (auto& user : open_definitions) {
121✔
169
                    if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
21!
170
                        user.second.insert(current_user);
4!
171
                        found_user = true;
4✔
172
                        found_undefined_user = this->is_undefined_user(*user.first);
4!
173
                    }
4✔
174
                }
175
                // If no definition found or undefined user found, mark as undefined
176
                if (!found_user || found_undefined_user) {
100!
177
                    undefined.insert(current_user);
96!
178
                }
96✔
179
            }
180
        }
153✔
181
    }
182
}
175✔
183

184
void DataDependencyAnalysis::visit_for(
61✔
185
    analysis::Users& users,
186
    analysis::AssumptionsAnalysis& assumptions_analysis,
187
    analysis::DominanceAnalysis& dominance_analysis,
188
    structured_control_flow::StructuredLoop& for_loop,
189
    std::unordered_set<User*>& undefined,
190
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
191
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
192
) {
193
    // Init - Read
194
    for (auto atom : symbolic::atoms(for_loop.init())) {
66!
195
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, true);
5!
196

197
        // Assign to open definitions
198
        bool found_user = false;
5✔
199
        bool found_undefined_user = false;
5✔
200
        for (auto& user : open_definitions) {
6✔
201
            if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
1!
202
                user.second.insert(current_user);
1!
203
                found_user = true;
1✔
204
                found_undefined_user = this->is_undefined_user(*user.first);
1!
205
            }
1✔
206
        }
207
        // If no definition found or undefined user found, mark as undefined
208
        if (!found_user || found_undefined_user) {
5!
209
            undefined.insert(current_user);
4!
210
        }
4✔
211
    }
5✔
212

213
    // Init - Write
214
    {
215
        // Write Induction Variable
216
        auto current_user = users.get_user(for_loop.indvar()->get_name(), &for_loop, Use::WRITE, true);
61!
217

218
        // Close open definitions if possible
219
        std::unordered_map<User*, std::unordered_set<User*>> to_close;
61✔
220
        for (auto& user : open_definitions) {
76✔
221
            if (this->closes(assumptions_analysis, dominance_analysis, *user.first, *current_user, true)) {
15!
222
                to_close.insert(user);
2!
223
            }
2✔
224
        }
225
        for (auto& user : to_close) {
63✔
226
            open_definitions.erase(user.first);
2!
227
            closed_definitions.insert(user);
2!
228
        }
229

230
        // Start new open definition
231
        open_definitions.insert({current_user, {}});
61!
232
    }
61✔
233

234
    // Update - Write
235
    {
236
        auto current_user = users.get_user(for_loop.indvar()->get_name(), &for_loop, Use::WRITE, false, false, true);
61!
237
        open_definitions.insert({current_user, {}});
61!
238
    }
239

240
    // Condition - Read
241
    for (auto atom : symbolic::atoms(for_loop.condition())) {
174!
242
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, false, true);
113!
243

244
        // Assign to open definitions
245
        bool found_user = false;
113✔
246
        bool found_undefined_user = false;
113✔
247
        for (auto& user : open_definitions) {
356✔
248
            if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
243!
249
                user.second.insert(current_user);
123!
250
                found_user = true;
123✔
251
                found_undefined_user = this->is_undefined_user(*user.first);
123!
252
            }
123✔
253
        }
254
        // If no definition found or undefined user found, mark as undefined
255
        if (!found_user || found_undefined_user) {
113!
256
            undefined.insert(current_user);
51!
257
        }
51✔
258
    }
113✔
259

260
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_for;
61✔
261
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_for;
61✔
262
    std::unordered_set<User*> undefined_for;
61✔
263

264
    // Add assumptions for body
265
    visit_sequence(
61!
266
        users,
61✔
267
        assumptions_analysis,
61✔
268
        dominance_analysis,
61✔
269
        for_loop.root(),
61!
270
        undefined_for,
271
        open_definitions_for,
272
        closed_definitions_for
273
    );
274

275
    // Update - Read
276
    for (auto atom : symbolic::atoms(for_loop.update())) {
122!
277
        auto current_user = users.get_user(atom->get_name(), &for_loop, Use::READ, false, false, true);
61!
278

279
        // Assign to open definitions
280
        bool found_user = false;
61✔
281
        bool found_undefined_user = false;
61✔
282
        for (auto& user : open_definitions_for) {
154✔
283
            if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
93!
284
                user.second.insert(current_user);
1!
285
                found_user = true;
1✔
286
                found_undefined_user = this->is_undefined_user(*user.first);
1!
287
            }
1✔
288
        }
289
        // If no definition found or undefined user found, mark as undefined
290
        if (!found_user || found_undefined_user) {
61!
291
            undefined_for.insert(current_user);
60!
292
        }
60✔
293
    }
61✔
294

295
    // Merge for with outside
296

297
    // Closed definitions are simply merged
298
    for (auto& entry : closed_definitions_for) {
63✔
299
        closed_definitions.insert(entry);
2!
300
    }
301

302
    // Undefined reads are matched or forwarded
303
    for (auto open_read : undefined_for) {
312✔
304
        // Simple check: no match or undefined user
305
        std::unordered_set<User*> frontier;
251✔
306
        bool found = false;
251✔
307
        bool found_undefined_user = false;
251✔
308
        for (auto& entry : open_definitions) {
788✔
309
            if (intersects(*entry.first, *open_read, assumptions_analysis)) {
537!
310
                entry.second.insert(open_read);
329!
311
                found = true;
329✔
312
                found_undefined_user = this->is_undefined_user(*entry.first);
329!
313
                frontier.insert(entry.first);
329!
314
            }
329✔
315
        }
316
        if (!found || found_undefined_user) {
251!
317
            undefined.insert(open_read);
85!
318
            continue;
85✔
319
        }
320

321
        // Users found, check if they fully cover the read
322
        bool covered = false;
166✔
323
        for (auto& entry : frontier) {
167✔
324
            if (!dominance_analysis.dominates(*entry, *open_read)) {
166!
NEW
325
                continue;
×
326
            }
327
            bool covers = supersedes_restrictive(*open_read, *entry, assumptions_analysis);
166!
328
            if (covers) {
166✔
329
                covered = true;
165✔
330
                break;
165✔
331
            }
332
        }
333
        if (!covered) {
166✔
334
            undefined.insert(open_read);
1!
335
        }
1✔
336
    }
251!
337

338
    // Open definitions may close outside open definitions after loop
339
    std::unordered_set<User*> to_close;
61✔
340
    for (auto& previous : open_definitions) {
196✔
341
        for (auto& user : open_definitions_for) {
330✔
342
            if (this->closes(assumptions_analysis, dominance_analysis, *previous.first, *user.first, false)) {
199!
343
                to_close.insert(previous.first);
4!
344
                break;
4✔
345
            }
346
        }
347
    }
348
    for (auto& user : to_close) {
65✔
349
        closed_definitions.insert({user, open_definitions.at(user)});
4!
350
        open_definitions.erase(user);
4!
351
    }
352

353
    // Add loop-carried dependencies
354
    bool is_monotonic = LoopAnalysis::is_monotonic(&for_loop, assumptions_analysis);
61!
355
    if (this->detailed_ && is_monotonic) {
61!
356
        // Case: Can analyze
357
        bool success = this->loop_carried_dependencies_.insert({&for_loop, {}}).second;
56!
358
        assert(success);
56!
359
        auto& dependencies = this->loop_carried_dependencies_.at(&for_loop);
56!
360

361
        // We can focus on written containers
362

363
        // Case 1: Read-Write between iterations
364
        for (auto& read : undefined_for) {
302✔
365
            for (auto& write : open_definitions_for) {
683✔
366
                if (loop_depends(*write.first, *read, assumptions_analysis, for_loop)) {
437!
367
                    dependencies[read->container()] = LOOP_CARRIED_DEPENDENCY_READ_WRITE;
14!
368
                    write.second.insert(read);
14!
369
                }
14✔
370
            }
371
        }
372

373
        // Case 2: Write-Write between iterations
374
        for (auto& write : open_definitions_for) {
148✔
375
            if (dependencies.find(write.first->container()) != dependencies.end()) {
92!
376
                continue;
27✔
377
            }
378
            for (auto& write_2 : open_definitions_for) {
168✔
379
                if (loop_depends(*write.first, *write_2.first, assumptions_analysis, for_loop)) {
126!
380
                    dependencies.insert({write.first->container(), LOOP_CARRIED_DEPENDENCY_WRITE_WRITE});
23!
381
                    break;
23✔
382
                }
383
            }
384
        }
385
    } else {
56✔
386
        // Case: Cannot analyze
387
        bool success = this->loop_carried_dependencies_.insert({&for_loop, {}}).second;
5!
388
        assert(success);
5!
389
        auto& dependencies = this->loop_carried_dependencies_.at(&for_loop);
5!
390

391
        // Over-Approximation:
392
        // Add loop-carried dependencies for all open reads to all open writes
393
        for (auto& read : undefined_for) {
10✔
394
            for (auto& write : open_definitions_for) {
6✔
395
                if (this->depends(assumptions_analysis, dominance_analysis, *write.first, *read)) {
1!
396
                    write.second.insert(read);
×
397
                    dependencies.insert({read->container(), LOOP_CARRIED_DEPENDENCY_READ_WRITE});
×
398
                }
×
399
            }
400
        }
401
        // Add loop-carried dependencies for writes
402
        for (auto& write : open_definitions_for) {
6✔
403
            if (dependencies.find(write.first->container()) == dependencies.end()) {
1!
404
                dependencies.insert({write.first->container(), LOOP_CARRIED_DEPENDENCY_WRITE_WRITE});
1!
405
            }
1✔
406
        }
407
    }
408

409
    // Add open definitions from for to outside
410
    for (auto& entry : open_definitions_for) {
154✔
411
        open_definitions.insert(entry);
93!
412
    }
413
}
61✔
414

415
void DataDependencyAnalysis::visit_if_else(
22✔
416
    analysis::Users& users,
417
    analysis::AssumptionsAnalysis& assumptions_analysis,
418
    analysis::DominanceAnalysis& dominance_analysis,
419
    structured_control_flow::IfElse& if_else,
420
    std::unordered_set<User*>& undefined,
421
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
422
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
423
) {
424
    // Read Conditions
425
    for (size_t i = 0; i < if_else.size(); i++) {
59✔
426
        auto child = if_else.at(i).second;
37!
427
        for (auto atom : symbolic::atoms(child)) {
63!
428
            auto current_user = users.get_user(atom->get_name(), &if_else, Use::READ);
26!
429

430
            bool found_user = false;
26✔
431
            bool found_undefined_user = false;
26✔
432
            for (auto& user : open_definitions) {
44✔
433
                if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *current_user)) {
18!
434
                    user.second.insert(current_user);
9!
435
                    found_user = true;
9✔
436
                    found_undefined_user = this->is_undefined_user(*user.first);
9!
437
                }
9✔
438
            }
439
            // If no definition found or undefined user found, mark as undefined
440
            if (!found_user || found_undefined_user) {
26!
441
                undefined.insert(current_user);
17!
442
            }
17✔
443
        }
26✔
444
    }
37✔
445

446
    std::vector<std::unordered_set<User*>> undefined_branches(if_else.size());
22!
447
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> open_definitions_branches(if_else.size());
22!
448
    std::vector<std::unordered_map<User*, std::unordered_set<User*>>> closed_definitionss_branches(if_else.size());
22!
449
    for (size_t i = 0; i < if_else.size(); i++) {
59!
450
        auto& child = if_else.at(i).first;
37!
451
        visit_sequence(
37!
452
            users,
37✔
453
            assumptions_analysis,
37✔
454
            dominance_analysis,
37✔
455
            child,
37✔
456
            undefined_branches.at(i),
37!
457
            open_definitions_branches.at(i),
37!
458
            closed_definitionss_branches.at(i)
37!
459
        );
460
    }
37✔
461

462
    // merge partial open reads
463
    for (size_t i = 0; i < if_else.size(); i++) {
59!
464
        for (auto& entry : undefined_branches.at(i)) {
44!
465
            bool found_user = false;
7✔
466
            bool found_undefined_user = false;
7✔
467
            for (auto& user : open_definitions) {
17✔
468
                if (this->depends(assumptions_analysis, dominance_analysis, *user.first, *entry)) {
10!
469
                    user.second.insert(entry);
6!
470
                    found_user = true;
6✔
471
                    found_undefined_user = this->is_undefined_user(*user.first);
6!
472
                }
6✔
473
            }
474
            // If no definition found or undefined user found, mark as undefined
475
            if (!found_user || found_undefined_user) {
7!
476
                undefined.insert(entry);
1!
477
            }
1✔
478
        }
479
    }
37✔
480

481
    // merge closed writes
482
    for (auto& closing : closed_definitionss_branches) {
59✔
483
        for (auto& entry : closing) {
37!
484
            closed_definitions.insert(entry);
×
485
        }
486
    }
487

488
    // Close open reads_after_writes for complete branches
489
    if (if_else.is_complete()) {
22!
490
        std::unordered_map<User*, std::unordered_set<User*>> to_close;
15✔
491
        std::unordered_set<std::string> candidates;
15✔
492
        std::unordered_set<std::string> candidates_tmp;
15✔
493

494
        /* Complete close open reads_after_writes
495
        1. get candidates from first iteration
496
        2. iterate over all branches and prune candidates
497
        3. find prior writes for remaining candidates
498
        4. close open reads_after_writes for all candidates
499
        */
500
        for (auto& entry : open_definitions_branches.at(0)) {
29!
501
            candidates.insert(entry.first->container());
14!
502
        }
503
        for (auto& entry : closed_definitionss_branches.at(0)) {
15!
504
            candidates.insert(entry.first->container());
×
505
        }
506

507
        for (size_t i = 1; i < if_else.size(); i++) {
30!
508
            for (auto& entry : open_definitions_branches.at(i)) {
28!
509
                if (candidates.find(entry.first->container()) != candidates.end()) {
13!
510
                    candidates_tmp.insert(entry.first->container());
13!
511
                }
13✔
512
            }
513
            candidates.swap(candidates_tmp);
15✔
514
            candidates_tmp.clear();
15✔
515
        }
15✔
516

517
        for (auto& entry : open_definitions) {
23✔
518
            if (candidates.find(entry.first->container()) != candidates.end()) {
8!
519
                to_close.insert(entry);
4!
520
            }
4✔
521
        }
522

523
        for (auto& entry : to_close) {
19✔
524
            open_definitions.erase(entry.first);
4!
525
            closed_definitions.insert(entry);
4!
526
        }
527
    } else {
15✔
528
        // Incomplete if-else
529

530
        // In order to determine whether a new read is undefined
531
        // we would need to check whether all open definitions
532
        // jointly dominate the read.
533
        // Since this is expensive, we apply a trick:
534
        // For incomplete if-elses and any newly opened definition in
535
        // any branch, we add an artificial undefined user for that container.
536
        // If we encounter this user later, we know that not all branches defined it.
537
        // Hence, we can mark the read as (partially) undefined.
538

539
        for (auto& branch : open_definitions_branches) {
14✔
540
            for (auto& open_definition : branch) {
12✔
541
                auto write = open_definition.first;
5✔
542
                auto artificial_user = std::make_unique<
5!
543
                    User>(boost::graph_traits<graph::Graph>::null_vertex(), write->container(), nullptr, Use::WRITE);
5!
544
                this->undefined_users_.push_back(std::move(artificial_user));
5!
545
                open_definitions.insert({this->undefined_users_.back().get(), {}});
5!
546
            }
5✔
547
        }
548
    }
549

550
    // Add open definitions from branches to outside
551
    for (auto& branch : open_definitions_branches) {
59✔
552
        for (auto& entry : branch) {
69✔
553
            open_definitions.insert(entry);
32!
554
        }
555
    }
556
}
22✔
557

558
void DataDependencyAnalysis::visit_while(
8✔
559
    analysis::Users& users,
560
    analysis::AssumptionsAnalysis& assumptions_analysis,
561
    analysis::DominanceAnalysis& dominance_analysis,
562
    structured_control_flow::While& while_loop,
563
    std::unordered_set<User*>& undefined,
564
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
565
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
566
) {
567
    std::unordered_map<User*, std::unordered_set<User*>> open_definitions_while;
8✔
568
    std::unordered_map<User*, std::unordered_set<User*>> closed_definitions_while;
8✔
569
    std::unordered_set<User*> undefined_while;
8✔
570

571
    visit_sequence(
8!
572
        users,
8✔
573
        assumptions_analysis,
8✔
574
        dominance_analysis,
8✔
575
        while_loop.root(),
8!
576
        undefined_while,
577
        open_definitions_while,
578
        closed_definitions_while
579
    );
580

581
    // Scope-local closed definitions
582
    for (auto& entry : closed_definitions_while) {
10✔
583
        closed_definitions.insert(entry);
2!
584
    }
585

586
    for (auto open_read : undefined_while) {
11✔
587
        // Over-Approximation: Add loop-carried dependencies for all open reads
588
        for (auto& entry : open_definitions_while) {
7✔
589
            if (entry.first->container() == open_read->container()) {
4!
590
                entry.second.insert(open_read);
2!
591
            }
2✔
592
        }
593

594
        // Connect to outside
595
        bool found = false;
3✔
596
        for (auto& entry : open_definitions) {
6✔
597
            if (entry.first->container() == open_read->container()) {
3!
598
                entry.second.insert(open_read);
2!
599
                found = true;
2✔
600
            }
2✔
601
        }
602
        if (!found) {
3✔
603
            undefined.insert(open_read);
1!
604
        }
1✔
605
    }
606

607
    // Add open definitions from while to outside
608
    for (auto& entry : open_definitions_while) {
21✔
609
        open_definitions.insert(entry);
13!
610
    }
611
}
8✔
612

613
void DataDependencyAnalysis::visit_return(
×
614
    analysis::Users& users,
615
    analysis::AssumptionsAnalysis& assumptions_analysis,
616
    analysis::DominanceAnalysis& dominance_analysis,
617
    structured_control_flow::Return& return_statement,
618
    std::unordered_set<User*>& undefined,
619
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
620
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
621
) {
622
    if (return_statement.is_data() && !return_statement.data().empty()) {
×
623
        auto current_user = users.get_user(return_statement.data(), &return_statement, Use::READ);
×
624

625
        bool found = false;
×
626
        for (auto& user : open_definitions) {
×
627
            if (user.first->container() == return_statement.data()) {
×
628
                user.second.insert(current_user);
×
629
                found = true;
×
630
            }
×
631
        }
632
        if (!found) {
×
633
            undefined.insert(current_user);
×
634
        }
×
635
    }
×
636

637
    // close all open reads_after_writes
638
    for (auto& entry : open_definitions) {
×
639
        closed_definitions.insert(entry);
×
640
    }
641
    open_definitions.clear();
×
642
}
×
643

644
void DataDependencyAnalysis::visit_sequence(
198✔
645
    analysis::Users& users,
646
    analysis::AssumptionsAnalysis& assumptions_analysis,
647
    analysis::DominanceAnalysis& dominance_analysis,
648
    structured_control_flow::Sequence& sequence,
649
    std::unordered_set<User*>& undefined,
650
    std::unordered_map<User*, std::unordered_set<User*>>& open_definitions,
651
    std::unordered_map<User*, std::unordered_set<User*>>& closed_definitions
652
) {
653
    for (size_t i = 0; i < sequence.size(); i++) {
464✔
654
        auto child = sequence.at(i);
266✔
655
        if (auto block = dynamic_cast<structured_control_flow::Block*>(&child.first)) {
266!
656
            visit_block(
167✔
657
                users, assumptions_analysis, dominance_analysis, *block, undefined, open_definitions, closed_definitions
167✔
658
            );
659
        } else if (auto for_loop = dynamic_cast<structured_control_flow::StructuredLoop*>(&child.first)) {
266!
660
            visit_for(
61✔
661
                users,
61✔
662
                assumptions_analysis,
61✔
663
                dominance_analysis,
61✔
664
                *for_loop,
61✔
665
                undefined,
61✔
666
                open_definitions,
61✔
667
                closed_definitions
61✔
668
            );
669
        } else if (auto if_else = dynamic_cast<structured_control_flow::IfElse*>(&child.first)) {
99!
670
            visit_if_else(
22✔
671
                users, assumptions_analysis, dominance_analysis, *if_else, undefined, open_definitions, closed_definitions
22✔
672
            );
673
        } else if (auto while_loop = dynamic_cast<structured_control_flow::While*>(&child.first)) {
38!
674
            visit_while(
8✔
675
                users,
8✔
676
                assumptions_analysis,
8✔
677
                dominance_analysis,
8✔
678
                *while_loop,
8✔
679
                undefined,
8✔
680
                open_definitions,
8✔
681
                closed_definitions
8✔
682
            );
683
        } else if (auto return_statement = dynamic_cast<structured_control_flow::Return*>(&child.first)) {
16!
684
            visit_return(
×
685
                users,
×
686
                assumptions_analysis,
×
687
                dominance_analysis,
×
688
                *return_statement,
×
689
                undefined,
×
690
                open_definitions,
×
691
                closed_definitions
×
692
            );
693
        } else if (auto sequence = dynamic_cast<structured_control_flow::Sequence*>(&child.first)) {
8!
694
            visit_sequence(
×
695
                users,
×
696
                assumptions_analysis,
×
697
                dominance_analysis,
×
698
                *sequence,
×
699
                undefined,
×
700
                open_definitions,
×
701
                closed_definitions
×
702
            );
703
        }
×
704

705
        // handle transitions read
706
        for (auto& entry : child.second.assignments()) {
346✔
707
            for (auto& atom : symbolic::atoms(entry.second)) {
112!
708
                if (symbolic::is_pointer(atom)) {
32!
709
                    continue;
×
710
                }
711
                auto current_user = users.get_user(atom->get_name(), &child.second, Use::READ);
32!
712

713
                bool found = false;
32✔
714
                for (auto& user : open_definitions) {
63✔
715
                    if (user.first->container() == atom->get_name()) {
31!
716
                        user.second.insert(current_user);
28!
717
                        found = true;
28✔
718
                    }
28✔
719
                }
720
                if (!found) {
32✔
721
                    undefined.insert(current_user);
14!
722
                }
14✔
723
            }
724
        }
725

726
        // handle transitions write
727
        for (auto& entry : child.second.assignments()) {
346✔
728
            auto current_user = users.get_user(entry.first->get_name(), &child.second, Use::WRITE);
80✔
729

730
            std::unordered_set<User*> to_close;
80✔
731
            for (auto& user : open_definitions) {
113✔
732
                if (user.first->container() == entry.first->get_name()) {
33!
733
                    to_close.insert(user.first);
3!
734
                }
3✔
735
            }
736
            for (auto& user : to_close) {
83✔
737
                closed_definitions.insert({user, open_definitions.at(user)});
3!
738
                open_definitions.erase(user);
3!
739
            }
740
            open_definitions.insert({current_user, {}});
80!
741
        }
80✔
742
    }
266✔
743
}
198✔
744

745
bool DataDependencyAnalysis::loop_depends(
563✔
746
    User& previous,
747
    User& current,
748
    analysis::AssumptionsAnalysis& assumptions_analysis,
749
    structured_control_flow::StructuredLoop& loop
750
) {
751
    if (previous.container() != current.container()) {
563✔
752
        return false;
460✔
753
    }
754
    // Shortcut for scalars
755
    auto& type = this->sdfg_.type(previous.container());
103✔
756
    if (dynamic_cast<const types::Scalar*>(&type)) {
103!
757
        return true;
22✔
758
    }
759

760
    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
81✔
761
        return false;
4✔
762
    }
763

764
    auto& previous_subsets = previous.subsets();
77✔
765
    auto& current_subsets = current.subsets();
77✔
766

767
    auto previous_scope = Users::scope(&previous);
77✔
768
    auto& previous_assumptions = assumptions_analysis.get(loop.root(), *previous_scope, true);
77✔
769
    auto current_scope = Users::scope(&current);
77✔
770
    auto& current_assumptions = assumptions_analysis.get(loop.root(), *current_scope, true);
77✔
771

772
    // Check if previous subset is subset of any current subset
773
    for (auto& previous_subset : previous_subsets) {
139✔
774
        for (auto& current_subset : current_subsets) {
140✔
775
            if (symbolic::maps::intersects(
78!
776
                    previous_subset, current_subset, loop.indvar(), previous_assumptions, current_assumptions
78✔
777
                )) {
778
                return true;
15✔
779
            }
780
        }
781
    }
782

783
    return false;
62✔
784
}
563✔
785

786
bool DataDependencyAnalysis::
787
    supersedes_restrictive(User& previous, User& current, analysis::AssumptionsAnalysis& assumptions_analysis) {
166✔
788
    if (previous.container() != current.container()) {
166!
789
        return false;
×
790
    }
791
    // Shortcut for scalars
792
    auto& type = this->sdfg_.type(previous.container());
166✔
793
    if (dynamic_cast<const types::Scalar*>(&type)) {
166!
794
        return true;
163✔
795
    }
796

797
    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
3!
798
        return false;
×
799
    }
800

801
    auto& previous_subsets = previous.subsets();
3✔
802
    auto& current_subsets = current.subsets();
3✔
803
    auto previous_scope = Users::scope(&previous);
3✔
804
    auto& previous_assumptions = assumptions_analysis.get(*previous_scope, true);
3✔
805
    auto current_scope = Users::scope(&current);
3✔
806
    auto& current_assumptions = assumptions_analysis.get(*current_scope, true);
3✔
807

808
    // Check if previous subset is subset of any current subset
809
    for (auto& previous_subset : previous_subsets) {
5✔
810
        bool found = false;
3✔
811
        for (auto& current_subset : current_subsets) {
4✔
812
            if (symbolic::is_subset(previous_subset, current_subset, previous_assumptions, previous_assumptions)) {
3✔
813
                found = true;
2✔
814
                break;
2✔
815
            }
816
        }
817
        if (!found) {
3✔
818
            return false;
1✔
819
        }
820
    }
821

822
    return true;
2✔
823
}
166✔
824

825
bool DataDependencyAnalysis::intersects(User& previous, User& current, analysis::AssumptionsAnalysis& assumptions_analysis) {
537✔
826
    if (previous.container() != current.container()) {
537✔
827
        return false;
206✔
828
    }
829
    // Shortcut for scalars
830
    auto& type = this->sdfg_.type(previous.container());
331✔
831
    if (dynamic_cast<const types::Scalar*>(&type)) {
331!
832
        return true;
326✔
833
    }
834

835
    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
5!
836
        return true;
×
837
    }
838

839
    if (!this->detailed_) {
5!
840
        return true;
×
841
    }
842

843
    auto& previous_subsets = previous.subsets();
5✔
844
    auto& current_subsets = current.subsets();
5✔
845

846
    auto previous_scope = Users::scope(&previous);
5✔
847
    auto& previous_assumptions = assumptions_analysis.get(*previous_scope, true);
5✔
848
    auto current_scope = Users::scope(&current);
5✔
849
    auto& current_assumptions = assumptions_analysis.get(*current_scope, true);
5✔
850

851
    // Check if any current subset intersects with any previous subset
852
    bool found = false;
5✔
853
    for (auto& current_subset : current_subsets) {
7✔
854
        for (auto& previous_subset : previous_subsets) {
7✔
855
            if (!symbolic::is_disjoint(current_subset, previous_subset, current_assumptions, previous_assumptions)) {
5✔
856
                found = true;
3✔
857
                break;
3✔
858
            }
859
        }
860
        if (found) {
5✔
861
            break;
3✔
862
        }
863
    }
864

865
    return found;
5✔
866
}
537✔
867

868
bool DataDependencyAnalysis::closes(
253✔
869
    analysis::AssumptionsAnalysis& assumptions_analysis,
870
    analysis::DominanceAnalysis& dominance_analysis,
871
    User& previous,
872
    User& current,
873
    bool requires_dominance
874
) {
875
    if (previous.container() != current.container()) {
253✔
876
        return false;
231✔
877
    }
878

879
    // Check dominance
880
    if (requires_dominance && !dominance_analysis.post_dominates(current, previous)) {
22!
881
        return false;
×
882
    }
883

884
    // Previous memlets are subsets of current memlets
885
    auto& type = sdfg_.type(previous.container());
22✔
886
    if (type.type_id() == types::TypeID::Scalar) {
22✔
887
        return true;
5✔
888
    }
889

890
    if (this->is_undefined_user(previous) || this->is_undefined_user(current)) {
17!
891
        return false;
×
892
    }
893

894
    if (!this->detailed_) {
17!
895
        return false;
×
896
    }
897

898
    // Collect memlets and assumptions
899
    auto previous_scope = Users::scope(&previous);
17✔
900
    auto current_scope = Users::scope(&current);
17✔
901
    auto& previous_assumptions = assumptions_analysis.get(*previous_scope, true);
17✔
902
    auto& current_assumptions = assumptions_analysis.get(*current_scope, true);
17✔
903

904
    auto& previous_memlets = previous.subsets();
17✔
905
    auto& current_memlets = current.subsets();
17✔
906

907
    for (auto& subset_ : previous_memlets) {
25✔
908
        bool overwritten = false;
17✔
909
        for (auto& subset : current_memlets) {
26✔
910
            if (symbolic::is_subset(subset_, subset, previous_assumptions, current_assumptions)) {
17✔
911
                overwritten = true;
8✔
912
                break;
8✔
913
            }
914
        }
915
        if (!overwritten) {
17✔
916
            return false;
9✔
917
        }
918
    }
919

920
    return true;
8✔
921
}
253✔
922

923
bool DataDependencyAnalysis::depends(
413✔
924
    analysis::AssumptionsAnalysis& assumptions_analysis,
925
    analysis::DominanceAnalysis& dominance_analysis,
926
    User& previous,
927
    User& current
928
) {
929
    if (previous.container() != current.container()) {
413✔
930
        return false;
253✔
931
    }
932

933
    // Previous memlets are subsets of current memlets
934
    auto& type = sdfg_.type(previous.container());
160✔
935
    if (type.type_id() == types::TypeID::Scalar) {
160✔
936
        return true;
151✔
937
    }
938

939
    if (this->is_undefined_user(previous)) {
9!
940
        return true;
×
941
    }
942

943
    if (!this->detailed_) {
9✔
944
        return true;
2✔
945
    }
946

947
    // Collect memlets and assumptions
948
    auto previous_scope = Users::scope(&previous);
7✔
949
    auto current_scope = Users::scope(&current);
7✔
950
    auto& previous_assumptions = assumptions_analysis.get(*previous_scope, true);
7✔
951
    auto& current_assumptions = assumptions_analysis.get(*current_scope, true);
7✔
952

953
    auto& previous_memlets = previous.subsets();
7✔
954
    auto& current_memlets = current.subsets();
7✔
955

956
    bool intersect_any = false;
7✔
957
    for (auto& current_subset : current_memlets) {
11✔
958
        for (auto& previous_subset : previous_memlets) {
11✔
959
            if (!symbolic::is_disjoint(current_subset, previous_subset, current_assumptions, previous_assumptions)) {
7✔
960
                intersect_any = true;
3✔
961
                break;
3✔
962
            }
963
        }
964
        if (intersect_any) {
7✔
965
            break;
3✔
966
        }
967
    }
968

969
    return intersect_any;
7✔
970
}
413✔
971

972
/****** Public API ******/
973

974
std::unordered_set<User*> DataDependencyAnalysis::defines(User& write) {
×
975
    assert(write.use() == Use::WRITE);
×
976
    if (results_.find(write.container()) == results_.end()) {
×
977
        return {};
×
978
    }
979
    auto& raws = results_.at(write.container());
×
980
    assert(raws.find(&write) != raws.end());
×
981

982
    auto& reads_for_write = raws.at(&write);
×
983

984
    std::unordered_set<User*> reads;
×
985
    for (auto& entry : reads_for_write) {
×
986
        reads.insert(entry);
×
987
    }
988

989
    return reads;
×
990
};
×
991

992
std::unordered_map<User*, std::unordered_set<User*>> DataDependencyAnalysis::definitions(const std::string& container) {
33✔
993
    if (results_.find(container) == results_.end()) {
33!
994
        return {};
×
995
    }
996
    return results_.at(container);
33✔
997
};
33✔
998

999
std::unordered_map<User*, std::unordered_set<User*>> DataDependencyAnalysis::defined_by(const std::string& container) {
19✔
1000
    auto reads = this->definitions(container);
19✔
1001

1002
    std::unordered_map<User*, std::unordered_set<User*>> read_to_writes_map;
19✔
1003
    for (auto& entry : reads) {
43✔
1004
        for (auto& read : entry.second) {
51✔
1005
            if (read_to_writes_map.find(read) == read_to_writes_map.end()) {
27!
1006
                read_to_writes_map[read] = {};
20!
1007
            }
20✔
1008
            read_to_writes_map[read].insert(entry.first);
27!
1009
        }
1010
    }
1011
    return read_to_writes_map;
19✔
1012
};
19!
1013

1014
std::unordered_set<User*> DataDependencyAnalysis::defined_by(User& read) {
×
1015
    assert(read.use() == Use::READ);
×
1016
    auto definitions = this->definitions(read.container());
×
1017

1018
    std::unordered_set<User*> writes;
×
1019
    for (auto& entry : definitions) {
×
1020
        for (auto& r : entry.second) {
×
1021
            if (&read == r) {
×
1022
                writes.insert(entry.first);
×
1023
            }
×
1024
        }
1025
    }
1026
    return writes;
×
1027
};
×
1028

1029
bool DataDependencyAnalysis::is_undefined_user(User& user) const {
723✔
1030
    return user.vertex_ == boost::graph_traits<graph::Graph>::null_vertex();
723✔
1031
};
1032

1033
bool DataDependencyAnalysis::available(structured_control_flow::StructuredLoop& loop) const {
×
1034
    return this->loop_carried_dependencies_.find(&loop) != this->loop_carried_dependencies_.end();
×
1035
};
1036

1037
const std::unordered_map<std::string, LoopCarriedDependency>& DataDependencyAnalysis::
1038
    dependencies(structured_control_flow::StructuredLoop& loop) const {
48✔
1039
    return this->loop_carried_dependencies_.at(&loop);
48✔
1040
};
1041

1042
} // namespace analysis
1043
} // 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