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

daisytuner / docc / 24217063461

09 Apr 2026 10:47PM UTC coverage: 64.393% (-0.006%) from 64.399%
24217063461

Pull #661

github

web-flow
Merge ff19845f9 into bb3981349
Pull Request #661: Reduce Maximum Collapsable Depth to Collapseable Maps

22 of 34 new or added lines in 2 files covered. (64.71%)

3 existing lines in 1 file now uncovered.

29727 of 46165 relevant lines covered (64.39%)

588.09 hits per line

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

70.21
/sdfg/src/analysis/arguments_analysis.cpp
1
#include "sdfg/analysis/arguments_analysis.h"
2
#include "sdfg/analysis/mem_access_range_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
) {
128✔
16
    auto& users = analysis_manager.get<analysis::Users>();
128✔
17
    analysis::UsersView scope_users(users, node);
128✔
18

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

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

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

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

53
        auto type = type_analysis.get_outer_type(container);
613✔
54
        if (type == nullptr) {
613✔
55
            inferred_types = false;
×
56
            is_ptr = true;
×
57
            is_scalar = false;
×
58
        } else {
613✔
59
            // Unwrap Reference types to check the underlying type
60
            const types::IType* effective_type = type;
613✔
61
            if (type->type_id() == types::TypeID::Reference) {
613✔
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;
613✔
67
            is_ptr = effective_type->type_id() == types::TypeID::Pointer ||
613✔
68
                     effective_type->type_id() == types::TypeID::Array;
613✔
69
        }
613✔
70

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

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

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

86
    node_arguments_.insert({&node, arguments});
128✔
87
    node_locals_.insert({&node, locals});
128✔
88
    node_inferred_types_.insert({&node, inferred_types});
128✔
89
}
128✔
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
) {
17✔
97
    std::unordered_set<std::string> internal_vars;
17✔
98
    argument_sizes_.insert({&node, {}});
17✔
99
    argument_element_sizes_.insert({&node, {}});
17✔
100

101
    auto& mem_access_ranges = analysis_manager.get<analysis::MemAccessRanges>();
17✔
102
    auto& users = analysis_manager.get<analysis::Users>();
17✔
103

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

107
    internal_vars.insert(locals.begin(), locals.end());
17✔
108
    std::ranges::for_each(arguments, [&internal_vars](const auto& pair) { internal_vars.insert(pair.first); });
23✔
109

110
    analysis::TypeAnalysis type_analysis(sdfg_, &node, analysis_manager);
17✔
111

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

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

138
            auto range = mem_access_ranges.get(argument, node, internal_vars);
10✔
139
            if (range == nullptr) {
10✔
140
                if (do_not_throw) {
×
141
                    known_sizes_.insert({&node, false});
×
142
                    return;
×
143
                } else {
×
144
                    throw std::runtime_error("Range not found for " + argument);
×
145
                }
×
146
            }
×
147

148
            auto base_type = type_analysis.get_outer_type(argument);
10✔
149
            auto elem_size = types::get_contiguous_element_size(*base_type, true);
10✔
150
            if (range->is_undefined()) {
10✔
151
                if (!allow_dynamic_sizes_) {
×
152
                    if (do_not_throw) {
×
153
                        known_sizes_.insert({&node, false});
×
154
                        return;
×
155
                    } else {
×
156
                        throw std::runtime_error("Argument " + argument + " has undefined range");
×
157
                    }
×
158
                }
×
159
                DEBUG_PRINTLN("Argument " << argument << " has undefined range, using malloc_usable_size");
×
160
                argument_sizes_.at(&node).insert({argument, symbolic::malloc_usable_size(symbolic::symbol(argument))});
×
161
                argument_element_sizes_.at(&node).insert({argument, elem_size});
×
162
                continue;
×
163
            }
×
164

165
            symbolic::Expression size = symbolic::one();
10✔
166
            if (!range->dims().empty()) {
10✔
167
                size = symbolic::add(range->dims().at(0).second, symbolic::one());
10✔
168
            }
10✔
169

170
            bool is_nested_type = true;
10✔
171
            auto peeled_type = types::peel_to_next_element(*base_type);
10✔
172
            while (is_nested_type) {
22✔
173
                if (peeled_type == nullptr) {
12✔
174
                    if (do_not_throw) {
×
175
                        known_sizes_.insert({&node, false});
×
176
                        return;
×
177
                    } else {
×
178
                        throw std::runtime_error("Could not infer type for argument: " + argument);
×
179
                    }
×
180
                }
×
181
                if (peeled_type->type_id() == types::TypeID::Array) {
12✔
182
                    auto array_type = dynamic_cast<const types::Array*>(peeled_type);
2✔
183
                    size = symbolic::mul(size, array_type->num_elements());
2✔
184
                    peeled_type = &array_type->element_type();
2✔
185
                } else if (peeled_type->type_id() == types::TypeID::Pointer) {
10✔
186
                    if (do_not_throw) {
×
187
                        known_sizes_.insert({&node, false});
×
188
                        return;
×
189
                    } else {
×
190
                        throw std::runtime_error("Non-contiguous pointer type: " + argument);
×
191
                    }
×
192
                } else {
10✔
193
                    is_nested_type = false;
10✔
194
                }
10✔
195
            }
12✔
196

197

198
            size = symbolic::mul(size, elem_size);
10✔
199

200
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
10✔
201
            if (size.is_null()) {
10✔
202
                if (do_not_throw) {
×
203
                    known_sizes_.insert({&node, false});
×
204
                    return;
×
205
                } else {
×
206
                    throw std::runtime_error("Cannot figure out access size of " + argument);
×
207
                }
×
208
            } else {
10✔
209
                argument_sizes_.at(&node).insert({argument, size});
10✔
210
                argument_element_sizes_.at(&node).insert({argument, elem_size});
10✔
211
            }
10✔
212
        } else {
13✔
213
            auto type = type_analysis.get_outer_type(argument);
13✔
214
            if (type == nullptr) {
13✔
215
                if (do_not_throw) {
×
216
                    known_sizes_.insert({&node, false});
×
217
                    return;
×
218
                } else {
×
219
                    throw std::runtime_error("Could not infer type for argument: " + argument);
×
220
                }
×
221
            }
×
222
            DEBUG_PRINTLN("type of argument: " << type->print());
13✔
223
            auto size = types::get_contiguous_element_size(*type);
13✔
224
            DEBUG_PRINTLN("Size of " << argument << " is " << size->__str__());
13✔
225
            argument_sizes_.at(&node).insert({argument, size});
13✔
226
            argument_element_sizes_.at(&node).insert({argument, size});
13✔
227
        }
13✔
228
    }
23✔
229

230
    known_sizes_.insert({&node, true});
17✔
231
}
17✔
232

233
ArgumentsAnalysis::ArgumentsAnalysis(StructuredSDFG& sdfg) : Analysis(sdfg) {}
81✔
234

235
void ArgumentsAnalysis::run(analysis::AnalysisManager& analysis_manager) {}
81✔
236

237
const std::map<std::string, RegionArgument>& ArgumentsAnalysis::
238
    arguments(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
149✔
239
    if (node_arguments_.find(&node) != node_arguments_.end()) {
149✔
240
        return node_arguments_.at(&node);
40✔
241
    } else {
109✔
242
        find_arguments_and_locals(analysis_manager, node);
109✔
243
        return node_arguments_.at(&node);
109✔
244
    }
109✔
245
}
149✔
246

247
const std::unordered_set<std::string>& ArgumentsAnalysis::
248
    locals(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
52✔
249
    if (node_locals_.find(&node) != node_locals_.end()) {
52✔
250
        return node_locals_.at(&node);
52✔
251
    } else {
52✔
252
        find_arguments_and_locals(analysis_manager, node);
×
253
        return node_locals_.at(&node);
×
254
    }
×
255
}
52✔
256

257
bool ArgumentsAnalysis::
258
    inferred_types(analysis::AnalysisManager& analysis_manager, structured_control_flow::ControlFlowNode& node) {
19✔
259
    if (node_inferred_types_.find(&node) != node_inferred_types_.end()) {
19✔
260
        return node_inferred_types_.at(&node);
×
261
    } else {
19✔
262
        find_arguments_and_locals(analysis_manager, node);
19✔
263
        return node_inferred_types_.at(&node);
19✔
264
    }
19✔
265
}
19✔
266

267
const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_sizes(
268
    analysis::AnalysisManager& analysis_manager,
269
    structured_control_flow::ControlFlowNode& node,
270
    bool allow_dynamic_sizes_
271
) {
19✔
272
    if (argument_sizes_.find(&node) != argument_sizes_.end() && known_sizes_.at(&node)) {
19✔
273
        return argument_sizes_.at(&node);
19✔
274
    } else {
19✔
275
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
×
276
        return argument_sizes_.at(&node);
×
277
    }
×
278
}
19✔
279

280
const std::unordered_map<std::string, symbolic::Expression>& ArgumentsAnalysis::argument_element_sizes(
281
    analysis::AnalysisManager& analysis_manager,
282
    structured_control_flow::ControlFlowNode& node,
283
    bool allow_dynamic_sizes_
284
) {
1✔
285
    if (argument_element_sizes_.find(&node) != argument_element_sizes_.end() && known_sizes_.at(&node)) {
1✔
286
        return argument_element_sizes_.at(&node);
1✔
287
    } else {
1✔
288
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, false);
×
289
        return argument_element_sizes_.at(&node);
×
290
    }
×
291
}
1✔
292

293
bool ArgumentsAnalysis::argument_size_known(
294
    analysis::AnalysisManager& analysis_manager,
295
    structured_control_flow::ControlFlowNode& node,
296
    bool allow_dynamic_sizes_
297
) {
17✔
298
    if (known_sizes_.find(&node) != known_sizes_.end()) {
17✔
299
        return known_sizes_.at(&node);
×
300
    } else {
17✔
301
        collect_arg_sizes(analysis_manager, node, allow_dynamic_sizes_, true);
17✔
302
        return known_sizes_.at(&node);
17✔
303
    }
17✔
304
}
17✔
305

306
} // namespace analysis
307
} // 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