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

daisytuner / docc / 27263464741

10 Jun 2026 08:27AM UTC coverage: 61.383% (+0.1%) from 61.275%
27263464741

push

github

web-flow
Merge pull request #741 from daisytuner/mem-access-range-replacement

replaces MemAccessRangeAnalysis with MemoryLayoutAnalysis

481 of 523 new or added lines in 12 files covered. (91.97%)

44 existing lines in 11 files now uncovered.

35745 of 58233 relevant lines covered (61.38%)

757.21 hits per line

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

72.0
/sdfg/src/analysis/arguments_analysis.cpp
1
#include "sdfg/analysis/arguments_analysis.h"
2
#include "sdfg/analysis/memory_layout_analysis.h"
3
#include "sdfg/analysis/type_analysis.h"
4
#include "sdfg/analysis/users.h"
5
#include "sdfg/codegen/utils.h"
6
#include "sdfg/data_flow/library_nodes/stdlib/malloc.h"
7
#include "sdfg/helpers/helpers.h"
8
#include "sdfg/types/utils.h"
9

10
namespace sdfg {
11
namespace analysis {
12

13
void ArgumentsAnalysis::find_arguments_and_locals(
14
    analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node
15
) {
124✔
16
    auto& users = analysis_manager.get<analysis::Users>();
124✔
17
    analysis::UsersView scope_users(users, node);
124✔
18

19
    analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);
124✔
20

21
    std::unordered_map<std::string, DataRwFlags> all_containers;
124✔
22
    for (auto& user : scope_users.uses()) {
1,720✔
23
        if (user->container() == symbolic::__nullptr__()->get_name()) {
1,720✔
24
            continue;
×
25
        }
×
26

27
        DataRwFlags meta;
1,720✔
28
        switch (user->use()) {
1,720✔
29
            case analysis::READ:
1,185✔
30
                meta.found_explicit_read();
1,185✔
31
                break;
1,185✔
32
            case analysis::WRITE:
535✔
33
                meta.found_explicit_write();
535✔
34
                break;
535✔
35
            case analysis::MOVE:
×
36
            case analysis::VIEW:
×
37
            default:
×
38
                meta.found_analysis_escape();
×
39
        }
1,720✔
40
        auto it = all_containers.insert({user->container(), meta});
1,720✔
41
        if (!it.second) {
1,720✔
42
            it.first->second.merge(meta);
1,127✔
43
        }
1,127✔
44
    }
1,720✔
45

46
    bool inferred_types = true;
124✔
47
    std::map<std::string, RegionArgument> arguments;
124✔
48
    std::unordered_set<std::string> locals;
124✔
49
    for (auto& [container, rwFlags] : all_containers) {
593✔
50
        bool is_scalar = false;
593✔
51
        bool is_ptr = false;
593✔
52

53
        auto type = type_analysis.get_outer_type(container);
593✔
54
        if (type == nullptr) {
593✔
55
            inferred_types = false;
×
56
            is_ptr = true;
×
57
            is_scalar = false;
×
58
        } else {
593✔
59
            // Unwrap Reference types to check the underlying type
60
            const types::IType* effective_type = type;
593✔
61
            if (type->type_id() == types::TypeID::Reference) {
593✔
62
                auto* reference = dynamic_cast<const codegen::Reference*>(type);
4✔
63
                assert(reference != nullptr);
4✔
64
                effective_type = &reference->reference_type();
4✔
65
            }
4✔
66
            is_scalar = effective_type->type_id() == types::TypeID::Scalar;
593✔
67
            is_ptr = effective_type->type_id() == types::TypeID::Pointer ||
593✔
68
                     effective_type->type_id() == types::TypeID::Array;
593✔
69
        }
593✔
70

71
        if (sdfg_.is_argument(container) || sdfg_.is_external(container)) {
593✔
72
            arguments.insert({container, {rwFlags, is_scalar, is_ptr}});
276✔
73
            continue;
276✔
74
        }
276✔
75

76
        size_t total_uses = users.uses(container).size();
317✔
77
        size_t scope_uses = scope_users.uses(container).size();
317✔
78

79
        if (scope_uses < total_uses) {
317✔
80
            arguments.insert({container, {rwFlags, is_scalar, is_ptr}});
85✔
81
        } else {
232✔
82
            locals.insert(container);
232✔
83
        }
232✔
84
    }
317✔
85

86
    node_arguments_.insert({&node, arguments});
124✔
87
    node_locals_.insert({&node, locals});
124✔
88
    node_inferred_types_.insert({&node, inferred_types});
124✔
89
}
124✔
90

91
void ArgumentsAnalysis::collect_arg_sizes(
92
    analysis::AnalysisManager& analysis_manager,
93
    structured_control_flow::ControlFlowNode& node,
94
    bool allow_dynamic_sizes_,
95
    bool do_not_throw
96
) {
19✔
97
    argument_sizes_.insert({&node, {}});
19✔
98
    argument_element_sizes_.insert({&node, {}});
19✔
99

100
    auto& memory_layout_analysis = analysis_manager.get<analysis::MemoryLayoutAnalysis>();
19✔
101
    auto& users = analysis_manager.get<analysis::Users>();
19✔
102

103
    auto arguments = this->arguments(analysis_manager, node);
19✔
104
    auto locals = this->locals(analysis_manager, node);
19✔
105

106
    analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);
19✔
107

108
    for (auto& [argument, meta] : arguments) {
25✔
109
        if (!meta.is_scalar) {
25✔
110
            // Check if a Malloc node provides a known host allocation size
111
            symbolic::Expression malloc_size = SymEngine::null;
12✔
112
            for (auto* user : users.writes(argument)) {
12✔
113
                auto* access_node = dynamic_cast<data_flow::AccessNode*>(user->element());
6✔
114
                if (!access_node) continue;
6✔
115
                auto& graph = access_node->get_parent();
6✔
116
                for (auto& iedge : graph.in_edges(*access_node)) {
6✔
117
                    auto* malloc_node = dynamic_cast<const stdlib::MallocNode*>(&iedge.src());
6✔
118
                    if (!malloc_node) continue;
6✔
119
                    malloc_size = malloc_node->size();
×
120
                    break;
×
121
                }
6✔
122
                if (!malloc_size.is_null()) break;
6✔
123
            }
6✔
124

125
            // If malloc size is known, use it directly — skip range analysis
126
            if (!malloc_size.is_null()) {
12✔
127
                auto base_type = type_analysis.get_outer_type(argument);
×
128
                auto elem_size = types::get_contiguous_element_size(*base_type, true);
×
129
                argument_sizes_.at(&node).insert({argument, malloc_size});
×
130
                argument_element_sizes_.at(&node).insert({argument, elem_size});
×
131
                continue;
×
132
            }
×
133

134
            auto tile = memory_layout_analysis.tile(node, argument);
12✔
135
            if (tile == nullptr) {
12✔
136
                if (do_not_throw) {
4✔
137
                    known_sizes_.insert({&node, false});
4✔
138
                    return;
4✔
139
                } else {
4✔
NEW
140
                    throw std::runtime_error("Tile not found for " + argument);
×
141
                }
×
142
            }
4✔
143
            auto range = tile->contiguous_range();
8✔
144
            // contiguous_range returns {null, null} when the tile's extent would depend on
145
            // an unbounded leading dimension; treat that as "size unknown" rather than
146
            // dereferencing a null expression.
147
            if (range.first.is_null() || range.second.is_null()) {
8✔
NEW
148
                if (do_not_throw) {
×
NEW
149
                    known_sizes_.insert({&node, false});
×
NEW
150
                    return;
×
NEW
151
                } else {
×
NEW
152
                    throw std::runtime_error("Tile size unknown (unbounded dimension) for " + argument);
×
153
                }
×
154
            }
×
155
            symbolic::Expression size = range.second;
8✔
156
            size = symbolic::add(size, symbolic::one()); // Inclusive range, so add 1
8✔
157

158
            auto base_type = type_analysis.get_outer_type(argument);
8✔
159
            auto elem_size = types::get_contiguous_element_size(*base_type, true);
8✔
160

161
            bool is_nested_type = true;
8✔
162
            auto peeled_type = types::peel_to_next_element(*base_type);
8✔
163
            while (is_nested_type) {
18✔
164
                if (peeled_type == nullptr) {
10✔
165
                    if (do_not_throw) {
×
166
                        known_sizes_.insert({&node, false});
×
167
                        return;
×
168
                    } else {
×
169
                        throw std::runtime_error("Could not infer type for argument: " + argument);
×
170
                    }
×
171
                }
×
172
                if (peeled_type->type_id() == types::TypeID::Array) {
10✔
173
                    auto array_type = dynamic_cast<const types::Array*>(peeled_type);
2✔
174
                    size = symbolic::mul(size, array_type->num_elements());
2✔
175
                    peeled_type = &array_type->element_type();
2✔
176
                } else if (peeled_type->type_id() == types::TypeID::Pointer) {
8✔
177
                    if (do_not_throw) {
×
178
                        known_sizes_.insert({&node, false});
×
179
                        return;
×
180
                    } else {
×
181
                        throw std::runtime_error("Non-contiguous pointer type: " + argument);
×
182
                    }
×
183
                } else {
8✔
184
                    is_nested_type = false;
8✔
185
                }
8✔
186
            }
10✔
187

188

189
            size = symbolic::mul(size, elem_size);
8✔
190

191
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
8✔
192
            if (size.is_null()) {
8✔
193
                if (do_not_throw) {
×
194
                    known_sizes_.insert({&node, false});
×
195
                    return;
×
196
                } else {
×
197
                    throw std::runtime_error("Cannot figure out access size of " + argument);
×
198
                }
×
199
            } else {
8✔
200
                argument_sizes_.at(&node).insert({argument, size});
8✔
201
                argument_element_sizes_.at(&node).insert({argument, elem_size});
8✔
202
            }
8✔
203
        } else {
13✔
204
            auto type = type_analysis.get_outer_type(argument);
13✔
205
            if (type == nullptr) {
13✔
206
                if (do_not_throw) {
×
207
                    known_sizes_.insert({&node, false});
×
208
                    return;
×
209
                } else {
×
210
                    throw std::runtime_error("Could not infer type for argument: " + argument);
×
211
                }
×
212
            }
×
213
            DEBUG_PRINTLN("type of argument: " << type->print());
13✔
214
            auto size = types::get_contiguous_element_size(*type);
13✔
215
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
13✔
216
            argument_sizes_.at(&node).insert({argument, size});
13✔
217
            argument_element_sizes_.at(&node).insert({argument, size});
13✔
218
        }
13✔
219
    }
25✔
220

221
    known_sizes_.insert({&node, true});
15✔
222
}
15✔
223

224
ArgumentsAnalysis::ArgumentsAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}
77✔
225

226
void ArgumentsAnalysis::run(analysis::AnalysisManager& analysis_manager) {}
77✔
227

228
const std::map<std::string, RegionArgument>& ArgumentsAnalysis::
229
    arguments(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
149✔
230
    if (node_arguments_.find(&node) != node_arguments_.end()) {
149✔
231
        return node_arguments_.at(&node);
46✔
232
    } else {
103✔
233
        find_arguments_and_locals(analysis_manager, node);
103✔
234
        return node_arguments_.at(&node);
103✔
235
    }
103✔
236
}
149✔
237

238
const std::unordered_set<std::string>& ArgumentsAnalysis::
239
    locals(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
44✔
240
    if (node_locals_.find(&node) != node_locals_.end()) {
44✔
241
        return node_locals_.at(&node);
44✔
242
    } else {
44✔
243
        find_arguments_and_locals(analysis_manager, node);
×
244
        return node_locals_.at(&node);
×
245
    }
×
246
}
44✔
247

248
bool ArgumentsAnalysis::
249
    inferred_types(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
21✔
250
    if (node_inferred_types_.find(&node) != node_inferred_types_.end()) {
21✔
251
        return node_inferred_types_.at(&node);
×
252
    } else {
21✔
253
        find_arguments_and_locals(analysis_manager, node);
21✔
254
        return node_inferred_types_.at(&node);
21✔
255
    }
21✔
256
}
21✔
257

258
const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_sizes(
259
    analysis::AnalysisManager& analysis_manager,
260
    structured_control_flow::ControlFlowNode& node,
261
    bool allow_dynamic_sizes_
262
) {
17✔
263
    if (argument_sizes_.find(&node) != argument_sizes_.end() && known_sizes_.at(&node)) {
17✔
264
        return argument_sizes_.at(&node);
17✔
265
    } else {
17✔
266
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
×
267
        return argument_sizes_.at(&node);
×
268
    }
×
269
}
17✔
270

271
const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_element_sizes(
272
    analysis::AnalysisManager& analysis_manager,
273
    structured_control_flow::ControlFlowNode& node,
274
    bool allow_dynamic_sizes_
275
) {
1✔
276
    if (argument_element_sizes_.find(&node) != argument_element_sizes_.end() && known_sizes_.at(&node)) {
1✔
277
        return argument_element_sizes_.at(&node);
1✔
278
    } else {
1✔
279
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
×
280
        return argument_element_sizes_.at(&node);
×
281
    }
×
282
}
1✔
283

284
bool ArgumentsAnalysis::argument_size_known(
285
    analysis::AnalysisManager& analysis_manager,
286
    structured_control_flow::ControlFlowNode& node,
287
    bool allow_dynamic_sizes_
288
) {
19✔
289
    if (known_sizes_.find(&node) != known_sizes_.end()) {
19✔
290
        return known_sizes_.at(&node);
×
291
    } else {
19✔
292
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, true);
19✔
293
        return known_sizes_.at(&node);
19✔
294
    }
19✔
295
}
19✔
296

297
} // namespace analysis
298
} // 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