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

daisytuner / sdfglib / 15612270835

12 Jun 2025 01:44PM UTC coverage: 60.871% (-0.8%) from 61.71%
15612270835

push

github

web-flow
Merge pull request #68 from daisytuner/loop-types

refactors symbolic analysis into polynomials, extreme values and cnf

638 of 862 new or added lines in 24 files covered. (74.01%)

334 existing lines in 20 files now uncovered.

6571 of 10795 relevant lines covered (60.87%)

100.35 hits per line

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

75.13
/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)
166✔
19
    : Analysis(sdfg) {
83✔
20

21
      };
83✔
22

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NEW
196
void AssumptionsAnalysis::visit_map(structured_control_flow::Map* map,
×
197
                                    analysis::AnalysisManager& analysis_manager) {
NEW
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
    }
×
UNCOV
204
    auto& body_assumptions = this->assumptions_[&body];
×
NEW
205
    if (body_assumptions.find(indvar) == body_assumptions.end()) {
×
NEW
206
        body_assumptions.insert({indvar, symbolic::Assumption(indvar)});
×
UNCOV
207
    }
×
NEW
208
    body_assumptions[indvar].lower_bound(symbolic::zero());
×
NEW
209
    body_assumptions[indvar].upper_bound(symbolic::sub(map->num_iterations(), symbolic::one()));
×
NEW
210
};
×
211

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

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

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

247
    // Add sdfg assumptions
248
    this->assumptions_.insert({&sdfg_.root(), symbolic::Assumptions()});
83✔
249
    for (auto& entry : sdfg_.assumptions()) {
392✔
250
        this->assumptions_[&sdfg_.root()][entry.first] = entry.second;
309✔
251
    }
252

253
    // Add additional assumptions
254
    for (auto& entry : this->additional_assumptions_) {
83✔
255
        this->assumptions_[&sdfg_.root()][entry.first] = entry.second;
×
256
    }
257

258
    // Forward propagate for each node
259
    this->traverse(sdfg_.root(), analysis_manager);
83✔
260
};
83✔
261

262
const symbolic::Assumptions AssumptionsAnalysis::get(
193✔
263
    structured_control_flow::ControlFlowNode& node) {
264
    // Compute assumptions on the fly
265

266
    // Node-level assumptions
267
    symbolic::Assumptions assums;
193✔
268
    if (this->assumptions_.find(&node) != this->assumptions_.end()) {
193✔
269
        for (auto& entry : this->assumptions_[&node]) {
100✔
270
            assums.insert({entry.first, entry.second});
54✔
271
        }
272
    }
46✔
273

274
    AnalysisManager manager(this->sdfg_);
193✔
275
    auto& scope_analysis = manager.get<ScopeAnalysis>();
193✔
276

277
    auto scope = scope_analysis.parent_scope(&node);
193✔
278
    while (scope != nullptr) {
510✔
279
        // Don't overwrite lower scopes' assumptions
280
        if (this->assumptions_.find(scope) != this->assumptions_.end()) {
317✔
281
            for (auto& entry : this->assumptions_[scope]) {
1,022✔
282
                if (assums.find(entry.first) == assums.end()) {
790✔
283
                    assums.insert({entry.first, entry.second});
701✔
284
                }
701✔
285
            }
286
        }
232✔
287
        scope = scope_analysis.parent_scope(scope);
317✔
288
    }
289

290
    return assums;
193✔
291
};
193✔
292

293
}  // namespace analysis
294
}  // 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