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

daisytuner / sdfglib / 15717109772

17 Jun 2025 08:16PM UTC coverage: 64.66% (+0.08%) from 64.576%
15717109772

push

github

web-flow
Merge pull request #89 from daisytuner/leftover-logs

removes leftover logs

7992 of 12360 relevant lines covered (64.66%)

142.43 hits per line

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

76.14
/src/analysis/assumptions_analysis.cpp
1
#include "sdfg/analysis/assumptions_analysis.h"
2

3
#include <utility>
4
#include <vector>
5

6
#include "sdfg/analysis/scope_analysis.h"
7
#include "sdfg/analysis/users.h"
8
#include "sdfg/structured_control_flow/sequence.h"
9
#include "sdfg/symbolic/assumptions.h"
10
#include "sdfg/symbolic/conjunctive_normal_form.h"
11
#include "sdfg/symbolic/extreme_values.h"
12
#include "sdfg/symbolic/polynomials.h"
13
#include "sdfg/symbolic/series.h"
14

15
namespace sdfg {
16
namespace analysis {
17

18
AssumptionsAnalysis::AssumptionsAnalysis(StructuredSDFG& sdfg)
332✔
19
    : Analysis(sdfg) {
166✔
20

21
      };
166✔
22

23
void AssumptionsAnalysis::visit_block(structured_control_flow::Block* block,
227✔
24
                                      analysis::AnalysisManager& analysis_manager) {
25
    return;
227✔
26
};
27

28
void AssumptionsAnalysis::visit_sequence(structured_control_flow::Sequence* sequence,
407✔
29
                                         analysis::AnalysisManager& analysis_manager) {
30
    return;
407✔
31
};
32

33
void AssumptionsAnalysis::visit_if_else(structured_control_flow::IfElse* if_else,
5✔
34
                                        analysis::AnalysisManager& analysis_manager) {
35
    auto& users = analysis_manager.get<analysis::Users>();
5✔
36
    for (size_t i = 0; i < if_else->size(); i++) {
11✔
37
        auto& scope = if_else->at(i).first;
6✔
38
        auto condition = if_else->at(i).second;
6✔
39
        auto symbols = symbolic::atoms(condition);
6✔
40

41
        // Assumption: symbols are read-only in scope
42
        bool read_only = true;
6✔
43
        analysis::UsersView scope_users(users, scope);
6✔
44
        for (auto& sym : symbols) {
17✔
45
            if (scope_users.writes(sym->get_name()).size() > 0) {
11✔
46
                read_only = false;
×
47
                break;
×
48
            }
49
        }
50
        if (!read_only) {
6✔
51
            continue;
×
52
        }
53

54
        try {
55
            auto cnf = symbolic::conjunctive_normal_form(condition);
6✔
56

57
            // Assumption: no or conditions
58
            bool has_complex_clauses = false;
6✔
59
            for (auto& clause : cnf) {
13✔
60
                if (clause.size() > 1) {
7✔
61
                    has_complex_clauses = true;
×
62
                    break;
×
63
                }
64
            }
65
            if (has_complex_clauses) {
6✔
66
                continue;
×
67
            }
68

69
            for (auto& sym : symbols) {
17✔
70
                symbolic::Expression ub = symbolic::infty(1);
11✔
71
                symbolic::Expression lb = symbolic::infty(-1);
11✔
72
                for (auto& clause : cnf) {
20✔
73
                    auto& literal = clause[0];
14✔
74
                    // Literal does not use symbol
75
                    if (!symbolic::uses(literal, sym)) {
14✔
76
                        continue;
2✔
77
                    }
78

79
                    if (SymEngine::is_a<SymEngine::Equality>(*literal)) {
12✔
80
                        auto eq = SymEngine::rcp_dynamic_cast<const SymEngine::Equality>(literal);
5✔
81
                        auto lhs = eq->get_args()[0];
5✔
82
                        auto rhs = eq->get_args()[1];
5✔
83
                        if (SymEngine::eq(*lhs, *sym) && !symbolic::uses(rhs, sym)) {
5✔
84
                            ub = rhs;
2✔
85
                            lb = rhs;
2✔
86
                            break;
2✔
87
                        } else if (SymEngine::eq(*rhs, *sym) && !symbolic::uses(lhs, sym)) {
3✔
88
                            ub = lhs;
3✔
89
                            lb = lhs;
3✔
90
                            break;
3✔
91
                        }
92
                    } else if (SymEngine::is_a<SymEngine::StrictLessThan>(*literal)) {
12✔
93
                        auto lt =
94
                            SymEngine::rcp_dynamic_cast<const SymEngine::StrictLessThan>(literal);
6✔
95
                        auto lhs = lt->get_args()[0];
6✔
96
                        auto rhs = lt->get_args()[1];
6✔
97
                        if (SymEngine::eq(*lhs, *sym) && !symbolic::uses(rhs, sym)) {
6✔
98
                            if (symbolic::eq(ub, symbolic::infty(1))) {
3✔
99
                                ub = rhs;
3✔
100
                            } else {
3✔
101
                                ub = symbolic::min(ub, rhs);
×
102
                            }
103
                        } else if (SymEngine::eq(*rhs, *sym) && !symbolic::uses(lhs, sym)) {
6✔
104
                            if (symbolic::eq(lb, symbolic::infty(-1))) {
3✔
105
                                lb = lhs;
3✔
106
                            } else {
3✔
107
                                lb = symbolic::max(lb, lhs);
×
108
                            }
109
                        }
3✔
110
                    } else if (SymEngine::is_a<SymEngine::LessThan>(*literal)) {
7✔
111
                        auto lt = SymEngine::rcp_dynamic_cast<const SymEngine::LessThan>(literal);
×
112
                        auto lhs = lt->get_args()[0];
×
113
                        auto rhs = lt->get_args()[1];
×
114
                        if (SymEngine::eq(*lhs, *sym) && !symbolic::uses(rhs, sym)) {
×
115
                            if (symbolic::eq(ub, symbolic::infty(1))) {
×
116
                                ub = rhs;
×
117
                            } else {
×
118
                                ub = symbolic::min(ub, rhs);
×
119
                            }
120
                        } else if (SymEngine::eq(*rhs, *sym) && !symbolic::uses(lhs, sym)) {
×
121
                            if (symbolic::eq(lb, symbolic::infty(-1))) {
×
122
                                lb = lhs;
×
123
                            } else {
×
124
                                lb = symbolic::max(lb, lhs);
×
125
                            }
126
                        }
×
127
                    }
×
128
                }
129

130
                // Failed to infer anything
131
                if (symbolic::eq(ub, symbolic::infty(1)) && symbolic::eq(lb, symbolic::infty(-1))) {
14✔
132
                    continue;
1✔
133
                }
134

135
                if (this->assumptions_.find(&scope) == this->assumptions_.end()) {
10✔
136
                    this->assumptions_.insert({&scope, symbolic::Assumptions()});
5✔
137
                }
5✔
138
                auto& scope_assumptions = this->assumptions_[&scope];
10✔
139
                if (scope_assumptions.find(sym) == scope_assumptions.end()) {
10✔
140
                    scope_assumptions.insert({sym, symbolic::Assumption(sym)});
10✔
141
                }
10✔
142

143
                if (!symbolic::eq(ub, symbolic::infty(1))) {
10✔
144
                    scope_assumptions[sym].upper_bound(ub);
8✔
145
                }
8✔
146
                if (!symbolic::eq(lb, symbolic::infty(-1))) {
10✔
147
                    scope_assumptions[sym].lower_bound(lb);
8✔
148
                }
8✔
149
            }
11✔
150
        } catch (const symbolic::CNFException& e) {
6✔
151
            continue;
152
        }
×
153
    }
6✔
154
};
5✔
155

156
void AssumptionsAnalysis::visit_while(structured_control_flow::While* while_loop,
×
157
                                      analysis::AnalysisManager& analysis_manager) {
158
    return;
×
159
};
160

161
void AssumptionsAnalysis::visit_for(structured_control_flow::For* for_loop,
235✔
162
                                    analysis::AnalysisManager& analysis_manager) {
163
    auto& assums = this->get(*for_loop);
235✔
164

165
    // Prove that update is monotonic
166
    auto indvar = for_loop->indvar();
235✔
167
    auto update = for_loop->update();
235✔
168
    if (!symbolic::is_monotonic(update, indvar, assums)) {
235✔
169
        return;
×
170
    }
171

172
    // Add new assumptions
173
    auto& body = for_loop->root();
235✔
174
    if (this->assumptions_.find(&body) == this->assumptions_.end()) {
235✔
175
        this->assumptions_.insert({&body, symbolic::Assumptions()});
235✔
176
    }
235✔
177
    auto& body_assumptions = this->assumptions_[&body];
235✔
178
    if (body_assumptions.find(indvar) == body_assumptions.end()) {
235✔
179
        body_assumptions.insert({indvar, symbolic::Assumption(indvar)});
235✔
180
    }
235✔
181

182
    // monotonic => init is lower bound
183
    body_assumptions[indvar].lower_bound(for_loop->init());
235✔
184
    try {
185
        auto cnf = symbolic::conjunctive_normal_form(for_loop->condition());
235✔
186
        auto ub = symbolic::upper_bound(cnf, indvar);
235✔
187
        if (ub == SymEngine::null) {
235✔
188
            return;
5✔
189
        }
190
        body_assumptions[indvar].upper_bound(ub);
230✔
191
    } catch (const symbolic::CNFException& e) {
235✔
192
        return;
193
    }
×
194
}
235✔
195

196
void AssumptionsAnalysis::visit_map(structured_control_flow::Map* map,
×
197
                                    analysis::AnalysisManager& analysis_manager) {
198
    auto indvar = map->indvar();
×
199

200
    auto& body = map->root();
×
201
    if (this->assumptions_.find(&body) == this->assumptions_.end()) {
×
202
        this->assumptions_.insert({&body, symbolic::Assumptions()});
×
203
    }
×
204
    auto& body_assumptions = this->assumptions_[&body];
×
205
    if (body_assumptions.find(indvar) == body_assumptions.end()) {
×
206
        body_assumptions.insert({indvar, symbolic::Assumption(indvar)});
×
207
    }
×
208
    body_assumptions[indvar].lower_bound(symbolic::zero());
×
209
    body_assumptions[indvar].upper_bound(symbolic::sub(map->num_iterations(), symbolic::one()));
×
210
};
×
211

212
void AssumptionsAnalysis::traverse(structured_control_flow::Sequence& root,
166✔
213
                                   analysis::AnalysisManager& analysis_manager) {
214
    std::list<structured_control_flow::ControlFlowNode*> queue = {&root};
166✔
215
    while (!queue.empty()) {
1,040✔
216
        auto current = queue.front();
874✔
217
        queue.pop_front();
874✔
218

219
        if (auto block_stmt = dynamic_cast<structured_control_flow::Block*>(current)) {
874✔
220
            this->visit_block(block_stmt, analysis_manager);
227✔
221
        } else if (auto sequence_stmt = dynamic_cast<structured_control_flow::Sequence*>(current)) {
874✔
222
            this->visit_sequence(sequence_stmt, analysis_manager);
407✔
223
            for (size_t i = 0; i < sequence_stmt->size(); i++) {
874✔
224
                queue.push_back(&sequence_stmt->at(i).first);
467✔
225
            }
467✔
226
        } else if (auto if_else_stmt = dynamic_cast<structured_control_flow::IfElse*>(current)) {
647✔
227
            this->visit_if_else(if_else_stmt, analysis_manager);
5✔
228
            for (size_t i = 0; i < if_else_stmt->size(); i++) {
11✔
229
                queue.push_back(&if_else_stmt->at(i).first);
6✔
230
            }
6✔
231
        } else if (auto while_stmt = dynamic_cast<structured_control_flow::While*>(current)) {
240✔
232
            this->visit_while(while_stmt, analysis_manager);
×
233
            queue.push_back(&while_stmt->root());
×
234
        } else if (auto for_stmt = dynamic_cast<structured_control_flow::For*>(current)) {
235✔
235
            this->visit_for(for_stmt, analysis_manager);
235✔
236
            queue.push_back(&for_stmt->root());
235✔
237
        } else if (auto map_stmt = dynamic_cast<structured_control_flow::Map*>(current)) {
235✔
238
            this->visit_map(map_stmt, analysis_manager);
×
239
            queue.push_back(&map_stmt->root());
×
240
        }
×
241
    }
242
};
166✔
243

244
void AssumptionsAnalysis::run(analysis::AnalysisManager& analysis_manager) {
166✔
245
    this->assumptions_.clear();
166✔
246

247
    // Add sdfg assumptions
248
    this->assumptions_.insert({&sdfg_.root(), symbolic::Assumptions()});
166✔
249

250
    // Add additional assumptions
251
    for (auto& entry : this->additional_assumptions_) {
166✔
252
        this->assumptions_[&sdfg_.root()][entry.first] = entry.second;
×
253
    }
254

255
    // Forward propagate for each node
256
    this->traverse(sdfg_.root(), analysis_manager);
166✔
257
};
166✔
258

259
const symbolic::Assumptions AssumptionsAnalysis::get(structured_control_flow::ControlFlowNode& node,
474✔
260
                                                     bool include_trivial_bounds) {
261
    // Compute assumptions on the fly
262

263
    // Node-level assumptions
264
    symbolic::Assumptions assums;
474✔
265
    if (this->assumptions_.find(&node) != this->assumptions_.end()) {
474✔
266
        for (auto& entry : this->assumptions_[&node]) {
172✔
267
            assums.insert({entry.first, entry.second});
86✔
268
        }
269
    }
86✔
270

271
    AnalysisManager manager(this->sdfg_);
474✔
272
    auto& scope_analysis = manager.get<ScopeAnalysis>();
474✔
273

274
    auto scope = scope_analysis.parent_scope(&node);
474✔
275
    while (scope != nullptr) {
1,500✔
276
        // Don't overwrite lower scopes' assumptions
277
        if (this->assumptions_.find(scope) != this->assumptions_.end()) {
1,026✔
278
            for (auto& entry : this->assumptions_[scope]) {
945✔
279
                if (assums.find(entry.first) == assums.end()) {
238✔
280
                    assums.insert({entry.first, entry.second});
238✔
281
                }
238✔
282
            }
283
        }
707✔
284
        scope = scope_analysis.parent_scope(scope);
1,026✔
285
    }
286

287
    if (include_trivial_bounds) {
474✔
288
        for (auto& entry : sdfg_.assumptions()) {
1,022✔
289
            if (assums.find(entry.first) == assums.end()) {
789✔
290
                assums.insert({entry.first, entry.second});
584✔
291
            }
584✔
292
        }
293
    }
233✔
294

295
    return assums;
474✔
296
};
474✔
297

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