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

daisytuner / sdfglib / 20263852258

16 Dec 2025 09:58AM UTC coverage: 40.086% (-0.2%) from 40.252%
20263852258

push

github

web-flow
Merge pull request #392 from daisytuner/for2map-performance

refactors passes to improve performance

13621 of 43972 branches covered (30.98%)

Branch coverage included in aggregate %.

126 of 173 new or added lines in 14 files covered. (72.83%)

55 existing lines in 8 files now uncovered.

11633 of 19027 relevant lines covered (61.14%)

90.79 hits per line

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

43.25
/src/passes/structured_control_flow/for2map.cpp
1
#include "sdfg/passes/structured_control_flow/for2map.h"
2

3
#include "sdfg/analysis/assumptions_analysis.h"
4
#include "sdfg/analysis/loop_analysis.h"
5
#include "sdfg/analysis/scope_analysis.h"
6
#include "sdfg/analysis/users.h"
7
#include "sdfg/passes/pipeline.h"
8

9
namespace sdfg {
10
namespace passes {
11

NEW
12
std::string For2MapPass::name() { return "For2Map"; }
×
13

14
bool For2MapPass::can_be_applied(
9✔
15
    builder::StructuredSDFGBuilder& builder,
16
    analysis::AnalysisManager& analysis_manager,
17
    structured_control_flow::For& for_stmt
18
) {
19
    auto& assumptions_analysis = analysis_manager.get<analysis::AssumptionsAnalysis>();
9✔
20
    bool is_monotonic = analysis::LoopAnalysis::is_monotonic(&for_stmt, assumptions_analysis);
9✔
21
    if (!is_monotonic) {
9!
22
        return false;
×
23
    }
24

25
    // Criterion: Loop must not have side-effecting body
26
    std::list<const structured_control_flow::ControlFlowNode*> queue = {&for_stmt.root()};
9!
27
    while (!queue.empty()) {
30✔
28
        auto current = queue.front();
21✔
29
        queue.pop_front();
21✔
30

31
        if (auto block = dynamic_cast<const structured_control_flow::Block*>(current)) {
21!
32
            for (auto& node : block->dataflow().nodes()) {
41!
33
                if (auto library_node = dynamic_cast<const data_flow::LibraryNode*>(&node)) {
31!
34
                    if (library_node->side_effect()) {
×
35
                        return false;
×
36
                    }
37
                }
×
38
            }
39
        } else if (auto seq = dynamic_cast<const structured_control_flow::Sequence*>(current)) {
21!
40
            for (size_t i = 0; i < seq->size(); i++) {
21!
41
                auto& child = seq->at(i).first;
11!
42
                queue.push_back(&child);
11!
43
            }
11✔
44
        } else if (auto ifelse = dynamic_cast<const structured_control_flow::IfElse*>(current)) {
11!
45
            for (size_t i = 0; i < ifelse->size(); i++) {
×
46
                auto& branch = ifelse->at(i).first;
×
47
                queue.push_back(&branch);
×
48
            }
×
49
        } else if (auto loop = dynamic_cast<const structured_control_flow::StructuredLoop*>(current)) {
1!
50
            queue.push_back(&loop->root());
1!
51
        } else if (auto while_stmt = dynamic_cast<const structured_control_flow::While*>(current)) {
1!
52
            queue.push_back(&while_stmt->root());
×
53
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Break*>(current)) {
×
54
            // Do nothing
55
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Continue*>(current)) {
×
56
            // Do nothing
57
        } else if (auto for_stmt = dynamic_cast<const structured_control_flow::Return*>(current)) {
×
58
            return false;
×
59
        } else {
60
            throw InvalidSDFGException("Unknown control flow node type in For2Map pass.");
×
61
        }
62
    }
63

64
    // Criterion: loop must be data-parallel w.r.t containers
65
    auto dependencies = data_dependency_analysis_->dependencies(for_stmt);
9!
66

67
    // a. No true dependencies (RAW) between iterations
68
    for (auto& dep : dependencies) {
10✔
69
        if (dep.second == analysis::LoopCarriedDependency::LOOP_CARRIED_DEPENDENCY_READ_WRITE) {
1!
70
            return false;
×
71
        }
72
    }
73

74
    // b. False dependencies (WAW) are limited to loop-local variables
75
    auto& users = analysis_manager.get<analysis::Users>();
9!
76
    auto locals = users.locals(for_stmt.root());
9!
77
    for (auto& dep : dependencies) {
10✔
78
        auto& container = dep.first;
1✔
79

80
        // Must be loop-local variable
81
        if (locals.find(container) == locals.end()) {
1!
82
            return false;
×
83
        }
84

85
        // Check for pointers that they point to loop-local storage
86
        auto& type = builder.subject().type(container);
1!
87
        if (type.type_id() != types::TypeID::Pointer) {
1!
88
            continue;
1✔
89
        }
90
        if (type.storage_type().allocation() == types::StorageType::AllocationType::Managed) {
×
91
            continue;
×
92
        }
93

94
        // or alias of loop-local storage
95
        if (users.moves(container).size() != 1) {
×
96
            return false;
×
97
        }
98
        auto move = users.moves(container).front();
×
99
        auto move_node = static_cast<const data_flow::AccessNode*>(move->element());
×
100
        auto& move_graph = move_node->get_parent();
×
101
        auto& move_edge = *move_graph.in_edges(*move_node).begin();
×
102
        auto& move_src = static_cast<const data_flow::AccessNode&>(move_edge.src());
×
103
        if (locals.find(move_src.data()) == locals.end()) {
×
104
            return false;
×
105
        }
NEW
106
        auto& move_type = builder.subject().type(move_src.data());
×
107
        if (move_type.storage_type().allocation() == types::StorageType::AllocationType::Unmanaged) {
×
108
            return false;
×
109
        }
110
    }
111

112
    // c. indvar not used after for
113
    if (locals.find(for_stmt.indvar()->get_name()) != locals.end()) {
9!
114
        return false;
×
115
    }
116

117
    return true;
9✔
118
}
9✔
119

120
bool For2MapPass::run_pass(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
8✔
121
    this->data_dependency_analysis_ = std::make_unique<analysis::DataDependencyAnalysis>(builder.subject(), true);
8✔
122
    this->data_dependency_analysis_->run(analysis_manager);
8✔
123

124
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
8✔
125
    auto& loop_tree = loop_analysis.loop_tree();
8✔
126

127
    // Traverse loops in bottom-up fashion (reverse loop)
128
    std::list<structured_control_flow::For*> for_queue;
8✔
129
    for (auto& entry : loop_tree) {
17✔
130
        if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(entry.first)) {
9!
131
            for_queue.push_front(for_stmt);
9!
132
        }
9✔
133
    }
134

135
    // Mark for loops that can be converted
136
    std::list<structured_control_flow::For*> map_queue;
8✔
137
    for (auto& for_loop : for_queue) {
17✔
138
        if (this->can_be_applied(builder, analysis_manager, *for_loop)) {
9!
139
            map_queue.push_back(for_loop);
9!
140
        }
9✔
141
    }
142

143
    // Convert marked for loops
144
    bool applied = false;
8✔
145
    auto& scope_analysis = analysis_manager.get<analysis::ScopeAnalysis>();
8!
146
    for (auto& for_stmt : map_queue) {
17✔
147
        auto parent = static_cast<structured_control_flow::Sequence*>(scope_analysis.parent_scope(for_stmt));
9!
148
        builder.convert_for(*parent, *for_stmt);
9!
149
        applied = true;
9✔
150
    }
151

152
    return applied;
8✔
153
}
8✔
154

155
} // namespace passes
156
} // 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