/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file defines RangeConstraintManager, a class that tracks simple |
10 | | // equality and inequality constraints on symbolic values of ProgramState. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "clang/Basic/JsonSupport.h" |
15 | | #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" |
16 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
17 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" |
18 | | #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" |
19 | | #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" |
20 | | #include "llvm/ADT/FoldingSet.h" |
21 | | #include "llvm/ADT/ImmutableSet.h" |
22 | | #include "llvm/ADT/STLExtras.h" |
23 | | #include "llvm/Support/Compiler.h" |
24 | | #include "llvm/Support/raw_ostream.h" |
25 | | #include <algorithm> |
26 | | #include <iterator> |
27 | | |
28 | | using namespace clang; |
29 | | using namespace ento; |
30 | | |
31 | | // This class can be extended with other tables which will help to reason |
32 | | // about ranges more precisely. |
33 | | class OperatorRelationsTable { |
34 | | static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE && |
35 | | BO_GE < BO_EQ && BO_EQ < BO_NE, |
36 | | "This class relies on operators order. Rework it otherwise."); |
37 | | |
38 | | public: |
39 | | enum TriStateKind { |
40 | | False = 0, |
41 | | True, |
42 | | Unknown, |
43 | | }; |
44 | | |
45 | | private: |
46 | | // CmpOpTable holds states which represent the corresponding range for |
47 | | // branching an exploded graph. We can reason about the branch if there is |
48 | | // a previously known fact of the existence of a comparison expression with |
49 | | // operands used in the current expression. |
50 | | // E.g. assuming (x < y) is true that means (x != y) is surely true. |
51 | | // if (x previous_operation y) // < | != | > |
52 | | // if (x operation y) // != | > | < |
53 | | // tristate // True | Unknown | False |
54 | | // |
55 | | // CmpOpTable represents next: |
56 | | // __|< |> |<=|>=|==|!=|UnknownX2| |
57 | | // < |1 |0 |* |0 |0 |* |1 | |
58 | | // > |0 |1 |0 |* |0 |* |1 | |
59 | | // <=|1 |0 |1 |* |1 |* |0 | |
60 | | // >=|0 |1 |* |1 |1 |* |0 | |
61 | | // ==|0 |0 |* |* |1 |0 |1 | |
62 | | // !=|1 |1 |* |* |0 |1 |0 | |
63 | | // |
64 | | // Columns stands for a previous operator. |
65 | | // Rows stands for a current operator. |
66 | | // Each row has exactly two `Unknown` cases. |
67 | | // UnknownX2 means that both `Unknown` previous operators are met in code, |
68 | | // and there is a special column for that, for example: |
69 | | // if (x >= y) |
70 | | // if (x != y) |
71 | | // if (x <= y) |
72 | | // False only |
73 | | static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1; |
74 | | const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = { |
75 | | // < > <= >= == != UnknownX2 |
76 | | {True, False, Unknown, False, False, Unknown, True}, // < |
77 | | {False, True, False, Unknown, False, Unknown, True}, // > |
78 | | {True, False, True, Unknown, True, Unknown, False}, // <= |
79 | | {False, True, Unknown, True, True, Unknown, False}, // >= |
80 | | {False, False, Unknown, Unknown, True, False, True}, // == |
81 | | {True, True, Unknown, Unknown, False, True, False}, // != |
82 | | }; |
83 | | |
84 | 1.04k | static size_t getIndexFromOp(BinaryOperatorKind OP) { |
85 | 1.04k | return static_cast<size_t>(OP - BO_LT); |
86 | 1.04k | } |
87 | | |
88 | | public: |
89 | 18.8k | constexpr size_t getCmpOpCount() const { return CmpOpCount; } |
90 | | |
91 | 16.2k | static BinaryOperatorKind getOpFromIndex(size_t Index) { |
92 | 16.2k | return static_cast<BinaryOperatorKind>(Index + BO_LT); |
93 | 16.2k | } |
94 | | |
95 | | TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, |
96 | 494 | BinaryOperatorKind QueriedOP) const { |
97 | 494 | return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)]; |
98 | 494 | } |
99 | | |
100 | 54 | TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const { |
101 | 54 | return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount]; |
102 | 54 | } |
103 | | }; |
104 | | |
105 | | //===----------------------------------------------------------------------===// |
106 | | // RangeSet implementation |
107 | | //===----------------------------------------------------------------------===// |
108 | | |
109 | | RangeSet::ContainerType RangeSet::Factory::EmptySet{}; |
110 | | |
111 | 1.68k | RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) { |
112 | 1.68k | ContainerType Result; |
113 | 1.68k | Result.reserve(Original.size() + 1); |
114 | | |
115 | 1.68k | const_iterator Lower = llvm::lower_bound(Original, Element); |
116 | 1.68k | Result.insert(Result.end(), Original.begin(), Lower); |
117 | 1.68k | Result.push_back(Element); |
118 | 1.68k | Result.insert(Result.end(), Lower, Original.end()); |
119 | | |
120 | 1.68k | return makePersistent(std::move(Result)); |
121 | 1.68k | } |
122 | | |
123 | 24 | RangeSet RangeSet::Factory::add(RangeSet Original, const llvm::APSInt &Point) { |
124 | 24 | return add(Original, Range(Point)); |
125 | 24 | } |
126 | | |
127 | 225k | RangeSet RangeSet::Factory::getRangeSet(Range From) { |
128 | 225k | ContainerType Result; |
129 | 225k | Result.push_back(From); |
130 | 225k | return makePersistent(std::move(Result)); |
131 | 225k | } |
132 | | |
133 | 307k | RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) { |
134 | 307k | llvm::FoldingSetNodeID ID; |
135 | 307k | void *InsertPos; |
136 | | |
137 | 307k | From.Profile(ID); |
138 | 307k | ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos); |
139 | | |
140 | 307k | if (!Result) { |
141 | | // It is cheaper to fully construct the resulting range on stack |
142 | | // and move it to the freshly allocated buffer if we don't have |
143 | | // a set like this already. |
144 | 37.6k | Result = construct(std::move(From)); |
145 | 37.6k | Cache.InsertNode(Result, InsertPos); |
146 | 37.6k | } |
147 | | |
148 | 307k | return Result; |
149 | 307k | } |
150 | | |
151 | 37.6k | RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) { |
152 | 37.6k | void *Buffer = Arena.Allocate(); |
153 | 37.6k | return new (Buffer) ContainerType(std::move(From)); |
154 | 37.6k | } |
155 | | |
156 | 1.66k | RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) { |
157 | 1.66k | ContainerType Result; |
158 | 1.66k | std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(), |
159 | 1.66k | std::back_inserter(Result)); |
160 | 1.66k | return makePersistent(std::move(Result)); |
161 | 1.66k | } |
162 | | |
163 | 412k | const llvm::APSInt &RangeSet::getMinValue() const { |
164 | 412k | assert(!isEmpty()); |
165 | 0 | return begin()->From(); |
166 | 412k | } |
167 | | |
168 | 164k | const llvm::APSInt &RangeSet::getMaxValue() const { |
169 | 164k | assert(!isEmpty()); |
170 | 0 | return std::prev(end())->To(); |
171 | 164k | } |
172 | | |
173 | 194k | bool RangeSet::containsImpl(llvm::APSInt &Point) const { |
174 | 194k | if (isEmpty() || !pin(Point)194k ) |
175 | 27 | return false; |
176 | | |
177 | 194k | Range Dummy(Point); |
178 | 194k | const_iterator It = llvm::upper_bound(*this, Dummy); |
179 | 194k | if (It == begin()) |
180 | 96.9k | return false; |
181 | | |
182 | 97.4k | return std::prev(It)->Includes(Point); |
183 | 194k | } |
184 | | |
185 | 194k | bool RangeSet::pin(llvm::APSInt &Point) const { |
186 | 194k | APSIntType Type(getMinValue()); |
187 | 194k | if (Type.testInRange(Point, true) != APSIntType::RTR_Within) |
188 | 3 | return false; |
189 | | |
190 | 194k | Type.apply(Point); |
191 | 194k | return true; |
192 | 194k | } |
193 | | |
194 | 87.9k | bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { |
195 | | // This function has nine cases, the cartesian product of range-testing |
196 | | // both the upper and lower bounds against the symbol's type. |
197 | | // Each case requires a different pinning operation. |
198 | | // The function returns false if the described range is entirely outside |
199 | | // the range of values for the associated symbol. |
200 | 87.9k | APSIntType Type(getMinValue()); |
201 | 87.9k | APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); |
202 | 87.9k | APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); |
203 | | |
204 | 87.9k | switch (LowerTest) { |
205 | 26 | case APSIntType::RTR_Below: |
206 | 26 | switch (UpperTest) { |
207 | 2 | case APSIntType::RTR_Below: |
208 | | // The entire range is outside the symbol's set of possible values. |
209 | | // If this is a conventionally-ordered range, the state is infeasible. |
210 | 2 | if (Lower <= Upper) |
211 | 1 | return false; |
212 | | |
213 | | // However, if the range wraps around, it spans all possible values. |
214 | 1 | Lower = Type.getMinValue(); |
215 | 1 | Upper = Type.getMaxValue(); |
216 | 1 | break; |
217 | 20 | case APSIntType::RTR_Within: |
218 | | // The range starts below what's possible but ends within it. Pin. |
219 | 20 | Lower = Type.getMinValue(); |
220 | 20 | Type.apply(Upper); |
221 | 20 | break; |
222 | 4 | case APSIntType::RTR_Above: |
223 | | // The range spans all possible values for the symbol. Pin. |
224 | 4 | Lower = Type.getMinValue(); |
225 | 4 | Upper = Type.getMaxValue(); |
226 | 4 | break; |
227 | 26 | } |
228 | 25 | break; |
229 | 87.8k | case APSIntType::RTR_Within: |
230 | 87.8k | switch (UpperTest) { |
231 | 37 | case APSIntType::RTR_Below: |
232 | | // The range wraps around, but all lower values are not possible. |
233 | 37 | Type.apply(Lower); |
234 | 37 | Upper = Type.getMaxValue(); |
235 | 37 | break; |
236 | 87.8k | case APSIntType::RTR_Within: |
237 | | // The range may or may not wrap around, but both limits are valid. |
238 | 87.8k | Type.apply(Lower); |
239 | 87.8k | Type.apply(Upper); |
240 | 87.8k | break; |
241 | 6 | case APSIntType::RTR_Above: |
242 | | // The range starts within what's possible but ends above it. Pin. |
243 | 6 | Type.apply(Lower); |
244 | 6 | Upper = Type.getMaxValue(); |
245 | 6 | break; |
246 | 87.8k | } |
247 | 87.8k | break; |
248 | 87.8k | case APSIntType::RTR_Above: |
249 | 12 | switch (UpperTest) { |
250 | 4 | case APSIntType::RTR_Below: |
251 | | // The range wraps but is outside the symbol's set of possible values. |
252 | 4 | return false; |
253 | 6 | case APSIntType::RTR_Within: |
254 | | // The range starts above what's possible but ends within it (wrap). |
255 | 6 | Lower = Type.getMinValue(); |
256 | 6 | Type.apply(Upper); |
257 | 6 | break; |
258 | 2 | case APSIntType::RTR_Above: |
259 | | // The entire range is outside the symbol's set of possible values. |
260 | | // If this is a conventionally-ordered range, the state is infeasible. |
261 | 2 | if (Lower <= Upper) |
262 | 1 | return false; |
263 | | |
264 | | // However, if the range wraps around, it spans all possible values. |
265 | 1 | Lower = Type.getMinValue(); |
266 | 1 | Upper = Type.getMaxValue(); |
267 | 1 | break; |
268 | 12 | } |
269 | 7 | break; |
270 | 87.9k | } |
271 | | |
272 | 87.9k | return true; |
273 | 87.9k | } |
274 | | |
275 | | RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower, |
276 | 87.9k | llvm::APSInt Upper) { |
277 | 87.9k | if (What.isEmpty() || !What.pin(Lower, Upper)87.9k ) |
278 | 22 | return getEmptySet(); |
279 | | |
280 | 87.9k | ContainerType DummyContainer; |
281 | | |
282 | 87.9k | if (Lower <= Upper) { |
283 | | // [Lower, Upper] is a regular range. |
284 | | // |
285 | | // Shortcut: check that there is even a possibility of the intersection |
286 | | // by checking the two following situations: |
287 | | // |
288 | | // <---[ What ]---[------]------> |
289 | | // Lower Upper |
290 | | // -or- |
291 | | // <----[------]----[ What ]----> |
292 | | // Lower Upper |
293 | 58.6k | if (What.getMaxValue() < Lower || Upper < What.getMinValue()52.9k ) |
294 | 11.1k | return getEmptySet(); |
295 | | |
296 | 47.4k | DummyContainer.push_back( |
297 | 47.4k | Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper))); |
298 | 47.4k | } else { |
299 | | // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX] |
300 | | // |
301 | | // Shortcut: check that there is even a possibility of the intersection |
302 | | // by checking the following situation: |
303 | | // |
304 | | // <------]---[ What ]---[------> |
305 | | // Upper Lower |
306 | 29.3k | if (What.getMaxValue() < Lower && Upper < What.getMinValue()373 ) |
307 | 310 | return getEmptySet(); |
308 | | |
309 | 29.0k | DummyContainer.push_back( |
310 | 29.0k | Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper))); |
311 | 29.0k | DummyContainer.push_back( |
312 | 29.0k | Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower))); |
313 | 29.0k | } |
314 | | |
315 | 76.4k | return intersect(*What.Impl, DummyContainer); |
316 | 87.9k | } |
317 | | |
318 | | RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS, |
319 | 78.2k | const RangeSet::ContainerType &RHS) { |
320 | 78.2k | ContainerType Result; |
321 | 78.2k | Result.reserve(std::max(LHS.size(), RHS.size())); |
322 | | |
323 | 78.2k | const_iterator First = LHS.begin(), Second = RHS.begin(), |
324 | 78.2k | FirstEnd = LHS.end(), SecondEnd = RHS.end(); |
325 | | |
326 | 78.2k | const auto SwapIterators = [&First, &FirstEnd, &Second, &SecondEnd]() { |
327 | 65.8k | std::swap(First, Second); |
328 | 65.8k | std::swap(FirstEnd, SecondEnd); |
329 | 65.8k | }; |
330 | | |
331 | | // If we ran out of ranges in one set, but not in the other, |
332 | | // it means that those elements are definitely not in the |
333 | | // intersection. |
334 | 177k | while (First != FirstEnd && Second != SecondEnd176k ) { |
335 | | // We want to keep the following invariant at all times: |
336 | | // |
337 | | // ----[ First ----------------------> |
338 | | // --------[ Second -----------------> |
339 | 99.2k | if (Second->From() < First->From()) |
340 | 40.6k | SwapIterators(); |
341 | | |
342 | | // Loop where the invariant holds: |
343 | 112k | do { |
344 | | // Check for the following situation: |
345 | | // |
346 | | // ----[ First ]---------------------> |
347 | | // ---------------[ Second ]---------> |
348 | | // |
349 | | // which means that... |
350 | 112k | if (Second->From() > First->To()) { |
351 | | // ...First is not in the intersection. |
352 | | // |
353 | | // We should move on to the next range after First and break out of the |
354 | | // loop because the invariant might not be true. |
355 | 21.4k | ++First; |
356 | 21.4k | break; |
357 | 21.4k | } |
358 | | |
359 | | // We have a guaranteed intersection at this point! |
360 | | // And this is the current situation: |
361 | | // |
362 | | // ----[ First ]-----------------> |
363 | | // -------[ Second ------------------> |
364 | | // |
365 | | // Additionally, it definitely starts with Second->From(). |
366 | 90.9k | const llvm::APSInt &IntersectionStart = Second->From(); |
367 | | |
368 | | // It is important to know which of the two ranges' ends |
369 | | // is greater. That "longer" range might have some other |
370 | | // intersections, while the "shorter" range might not. |
371 | 90.9k | if (Second->To() > First->To()) { |
372 | | // Here we make a decision to keep First as the "longer" |
373 | | // range. |
374 | 25.1k | SwapIterators(); |
375 | 25.1k | } |
376 | | |
377 | | // At this point, we have the following situation: |
378 | | // |
379 | | // ---- First ]--------------------> |
380 | | // ---- Second ]--[ Second+1 ----------> |
381 | | // |
382 | | // We don't know the relationship between First->From and |
383 | | // Second->From and we don't know whether Second+1 intersects |
384 | | // with First. |
385 | | // |
386 | | // However, we know that [IntersectionStart, Second->To] is |
387 | | // a part of the intersection... |
388 | 90.9k | Result.push_back(Range(IntersectionStart, Second->To())); |
389 | 90.9k | ++Second; |
390 | | // ...and that the invariant will hold for a valid Second+1 |
391 | | // because First->From <= Second->To < (Second+1)->From. |
392 | 90.9k | } while (Second != SecondEnd); |
393 | 99.2k | } |
394 | | |
395 | 78.2k | if (Result.empty()) |
396 | 19 | return getEmptySet(); |
397 | | |
398 | 78.2k | return makePersistent(std::move(Result)); |
399 | 78.2k | } |
400 | | |
401 | 1.82k | RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) { |
402 | | // Shortcut: let's see if the intersection is even possible. |
403 | 1.82k | if (LHS.isEmpty() || RHS.isEmpty()1.80k || LHS.getMaxValue() < RHS.getMinValue()1.79k || |
404 | 1.82k | RHS.getMaxValue() < LHS.getMinValue()1.79k ) |
405 | 27 | return getEmptySet(); |
406 | | |
407 | 1.79k | return intersect(*LHS.Impl, *RHS.Impl); |
408 | 1.82k | } |
409 | | |
410 | 81.2k | RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) { |
411 | 81.2k | if (LHS.containsImpl(Point)) |
412 | 37.2k | return getRangeSet(ValueFactory.getValue(Point)); |
413 | | |
414 | 44.0k | return getEmptySet(); |
415 | 81.2k | } |
416 | | |
417 | 634 | RangeSet RangeSet::Factory::negate(RangeSet What) { |
418 | 634 | if (What.isEmpty()) |
419 | 0 | return getEmptySet(); |
420 | | |
421 | 634 | const llvm::APSInt SampleValue = What.getMinValue(); |
422 | 634 | const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue); |
423 | 634 | const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue); |
424 | | |
425 | 634 | ContainerType Result; |
426 | 634 | Result.reserve(What.size() + (SampleValue == MIN)); |
427 | | |
428 | | // Handle a special case for MIN value. |
429 | 634 | const_iterator It = What.begin(); |
430 | 634 | const_iterator End = What.end(); |
431 | | |
432 | 634 | const llvm::APSInt &From = It->From(); |
433 | 634 | const llvm::APSInt &To = It->To(); |
434 | | |
435 | 634 | if (From == MIN) { |
436 | | // If the range [From, To] is [MIN, MAX], then result is also [MIN, MAX]. |
437 | 172 | if (To == MAX) { |
438 | 16 | return What; |
439 | 16 | } |
440 | | |
441 | 156 | const_iterator Last = std::prev(End); |
442 | | |
443 | | // Try to find and unite the following ranges: |
444 | | // [MIN, MIN] & [MIN + 1, N] => [MIN, N]. |
445 | 156 | if (Last->To() == MAX) { |
446 | | // It means that in the original range we have ranges |
447 | | // [MIN, A], ... , [B, MAX] |
448 | | // And the result should be [MIN, -B], ..., [-A, MAX] |
449 | 90 | Result.emplace_back(MIN, ValueFactory.getValue(-Last->From())); |
450 | | // We already negated Last, so we can skip it. |
451 | 90 | End = Last; |
452 | 90 | } else { |
453 | | // Add a separate range for the lowest value. |
454 | 66 | Result.emplace_back(MIN, MIN); |
455 | 66 | } |
456 | | |
457 | | // Skip adding the second range in case when [From, To] are [MIN, MIN]. |
458 | 156 | if (To != MIN) { |
459 | 104 | Result.emplace_back(ValueFactory.getValue(-To), MAX); |
460 | 104 | } |
461 | | |
462 | | // Skip the first range in the loop. |
463 | 156 | ++It; |
464 | 156 | } |
465 | | |
466 | | // Negate all other ranges. |
467 | 1.44k | for (; 618 It != End; ++It831 ) { |
468 | | // Negate int values. |
469 | 831 | const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To()); |
470 | 831 | const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From()); |
471 | | |
472 | | // Add a negated range. |
473 | 831 | Result.emplace_back(NewFrom, NewTo); |
474 | 831 | } |
475 | | |
476 | 618 | llvm::sort(Result); |
477 | 618 | return makePersistent(std::move(Result)); |
478 | 634 | } |
479 | | |
480 | | RangeSet RangeSet::Factory::deletePoint(RangeSet From, |
481 | 101k | const llvm::APSInt &Point) { |
482 | 101k | if (!From.contains(Point)) |
483 | 42.9k | return From; |
484 | | |
485 | 58.5k | llvm::APSInt Upper = Point; |
486 | 58.5k | llvm::APSInt Lower = Point; |
487 | | |
488 | 58.5k | ++Upper; |
489 | 58.5k | --Lower; |
490 | | |
491 | | // Notice that the lower bound is greater than the upper bound. |
492 | 58.5k | return intersect(From, Upper, Lower); |
493 | 101k | } |
494 | | |
495 | 46 | void Range::dump(raw_ostream &OS) const { |
496 | 46 | OS << '[' << From().toString(10) << ", " << To().toString(10) << ']'; |
497 | 46 | } |
498 | | |
499 | 46 | void RangeSet::dump(raw_ostream &OS) const { |
500 | 46 | OS << "{ "; |
501 | 46 | llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); }); |
502 | 46 | OS << " }"; |
503 | 46 | } |
504 | | |
505 | | REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef) |
506 | | |
507 | | namespace { |
508 | | class EquivalenceClass; |
509 | | } // end anonymous namespace |
510 | | |
511 | | REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass) |
512 | | REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet) |
513 | | REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet) |
514 | | |
515 | | REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass) |
516 | | REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet) |
517 | | |
518 | | namespace { |
519 | | /// This class encapsulates a set of symbols equal to each other. |
520 | | /// |
521 | | /// The main idea of the approach requiring such classes is in narrowing |
522 | | /// and sharing constraints between symbols within the class. Also we can |
523 | | /// conclude that there is no practical need in storing constraints for |
524 | | /// every member of the class separately. |
525 | | /// |
526 | | /// Main terminology: |
527 | | /// |
528 | | /// * "Equivalence class" is an object of this class, which can be efficiently |
529 | | /// compared to other classes. It represents the whole class without |
530 | | /// storing the actual in it. The members of the class however can be |
531 | | /// retrieved from the state. |
532 | | /// |
533 | | /// * "Class members" are the symbols corresponding to the class. This means |
534 | | /// that A == B for every member symbols A and B from the class. Members of |
535 | | /// each class are stored in the state. |
536 | | /// |
537 | | /// * "Trivial class" is a class that has and ever had only one same symbol. |
538 | | /// |
539 | | /// * "Merge operation" merges two classes into one. It is the main operation |
540 | | /// to produce non-trivial classes. |
541 | | /// If, at some point, we can assume that two symbols from two distinct |
542 | | /// classes are equal, we can merge these classes. |
543 | | class EquivalenceClass : public llvm::FoldingSetNode { |
544 | | public: |
545 | | /// Find equivalence class for the given symbol in the given state. |
546 | | LLVM_NODISCARD static inline EquivalenceClass find(ProgramStateRef State, |
547 | | SymbolRef Sym); |
548 | | |
549 | | /// Merge classes for the given symbols and return a new state. |
550 | | LLVM_NODISCARD static inline ProgramStateRef |
551 | | merge(BasicValueFactory &BV, RangeSet::Factory &F, ProgramStateRef State, |
552 | | SymbolRef First, SymbolRef Second); |
553 | | // Merge this class with the given class and return a new state. |
554 | | LLVM_NODISCARD inline ProgramStateRef merge(BasicValueFactory &BV, |
555 | | RangeSet::Factory &F, |
556 | | ProgramStateRef State, |
557 | | EquivalenceClass Other); |
558 | | |
559 | | /// Return a set of class members for the given state. |
560 | | LLVM_NODISCARD inline SymbolSet getClassMembers(ProgramStateRef State) const; |
561 | | /// Return true if the current class is trivial in the given state. |
562 | | LLVM_NODISCARD inline bool isTrivial(ProgramStateRef State) const; |
563 | | /// Return true if the current class is trivial and its only member is dead. |
564 | | LLVM_NODISCARD inline bool isTriviallyDead(ProgramStateRef State, |
565 | | SymbolReaper &Reaper) const; |
566 | | |
567 | | LLVM_NODISCARD static inline ProgramStateRef |
568 | | markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, |
569 | | ProgramStateRef State, SymbolRef First, SymbolRef Second); |
570 | | LLVM_NODISCARD static inline ProgramStateRef |
571 | | markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, |
572 | | ProgramStateRef State, EquivalenceClass First, |
573 | | EquivalenceClass Second); |
574 | | LLVM_NODISCARD inline ProgramStateRef |
575 | | markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, |
576 | | ProgramStateRef State, EquivalenceClass Other) const; |
577 | | LLVM_NODISCARD static inline ClassSet |
578 | | getDisequalClasses(ProgramStateRef State, SymbolRef Sym); |
579 | | LLVM_NODISCARD inline ClassSet |
580 | | getDisequalClasses(ProgramStateRef State) const; |
581 | | LLVM_NODISCARD inline ClassSet |
582 | | getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const; |
583 | | |
584 | | LLVM_NODISCARD static inline Optional<bool> |
585 | | areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second); |
586 | | |
587 | | /// Check equivalence data for consistency. |
588 | | LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED static bool |
589 | | isClassDataConsistent(ProgramStateRef State); |
590 | | |
591 | 1.49k | LLVM_NODISCARD QualType getType() const { |
592 | 1.49k | return getRepresentativeSymbol()->getType(); |
593 | 1.49k | } |
594 | | |
595 | | EquivalenceClass() = delete; |
596 | | EquivalenceClass(const EquivalenceClass &) = default; |
597 | | EquivalenceClass &operator=(const EquivalenceClass &) = delete; |
598 | | EquivalenceClass(EquivalenceClass &&) = default; |
599 | | EquivalenceClass &operator=(EquivalenceClass &&) = delete; |
600 | | |
601 | 2.98M | bool operator==(const EquivalenceClass &Other) const { |
602 | 2.98M | return ID == Other.ID; |
603 | 2.98M | } |
604 | 1.96M | bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; } |
605 | 0 | bool operator!=(const EquivalenceClass &Other) const { |
606 | 0 | return !operator==(Other); |
607 | 0 | } |
608 | | |
609 | 610k | static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) { |
610 | 610k | ID.AddInteger(CID); |
611 | 610k | } |
612 | | |
613 | 610k | void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); } |
614 | | |
615 | | private: |
616 | | /* implicit */ EquivalenceClass(SymbolRef Sym) |
617 | 702k | : ID(reinterpret_cast<uintptr_t>(Sym)) {} |
618 | | |
619 | | /// This function is intended to be used ONLY within the class. |
620 | | /// The fact that ID is a pointer to a symbol is an implementation detail |
621 | | /// and should stay that way. |
622 | | /// In the current implementation, we use it to retrieve the only member |
623 | | /// of the trivial class. |
624 | 1.86M | SymbolRef getRepresentativeSymbol() const { |
625 | 1.86M | return reinterpret_cast<SymbolRef>(ID); |
626 | 1.86M | } |
627 | | static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State); |
628 | | |
629 | | inline ProgramStateRef mergeImpl(BasicValueFactory &BV, RangeSet::Factory &F, |
630 | | ProgramStateRef State, SymbolSet Members, |
631 | | EquivalenceClass Other, |
632 | | SymbolSet OtherMembers); |
633 | | static inline bool |
634 | | addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints, |
635 | | BasicValueFactory &BV, RangeSet::Factory &F, |
636 | | ProgramStateRef State, EquivalenceClass First, |
637 | | EquivalenceClass Second); |
638 | | |
639 | | /// This is a unique identifier of the class. |
640 | | uintptr_t ID; |
641 | | }; |
642 | | |
643 | | //===----------------------------------------------------------------------===// |
644 | | // Constraint functions |
645 | | //===----------------------------------------------------------------------===// |
646 | | |
647 | | LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED bool |
648 | 140k | areFeasible(ConstraintRangeTy Constraints) { |
649 | 140k | return llvm::none_of( |
650 | 140k | Constraints, |
651 | 1.38M | [](const std::pair<EquivalenceClass, RangeSet> &ClassConstraint) { |
652 | 1.38M | return ClassConstraint.second.isEmpty(); |
653 | 1.38M | }); |
654 | 140k | } |
655 | | |
656 | | LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State, |
657 | 551k | EquivalenceClass Class) { |
658 | 551k | return State->get<ConstraintRange>(Class); |
659 | 551k | } |
660 | | |
661 | | LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State, |
662 | 549k | SymbolRef Sym) { |
663 | 549k | return getConstraint(State, EquivalenceClass::find(State, Sym)); |
664 | 549k | } |
665 | | |
666 | | //===----------------------------------------------------------------------===// |
667 | | // Equality/diseqiality abstraction |
668 | | //===----------------------------------------------------------------------===// |
669 | | |
670 | | /// A small helper structure representing symbolic equality. |
671 | | /// |
672 | | /// Equality check can have different forms (like a == b or a - b) and this |
673 | | /// class encapsulates those away if the only thing the user wants to check - |
674 | | /// whether it's equality/diseqiality or not and have an easy access to the |
675 | | /// compared symbols. |
676 | | struct EqualityInfo { |
677 | | public: |
678 | | SymbolRef Left, Right; |
679 | | // true for equality and false for disequality. |
680 | | bool IsEquality = true; |
681 | | |
682 | 0 | void invert() { IsEquality = !IsEquality; } |
683 | | /// Extract equality information from the given symbol and the constants. |
684 | | /// |
685 | | /// This function assumes the following expression Sym + Adjustment != Int. |
686 | | /// It is a default because the most widespread case of the equality check |
687 | | /// is (A == B) + 0 != 0. |
688 | | static Optional<EqualityInfo> extract(SymbolRef Sym, const llvm::APSInt &Int, |
689 | 126k | const llvm::APSInt &Adjustment) { |
690 | | // As of now, the only equality form supported is Sym + 0 != 0. |
691 | 126k | if (!Int.isNullValue() || !Adjustment.isNullValue()119k ) |
692 | 7.11k | return llvm::None; |
693 | | |
694 | 118k | return extract(Sym); |
695 | 126k | } |
696 | | /// Extract equality information from the given symbol. |
697 | 362k | static Optional<EqualityInfo> extract(SymbolRef Sym) { |
698 | 362k | return EqualityExtractor().Visit(Sym); |
699 | 362k | } |
700 | | |
701 | | private: |
702 | | class EqualityExtractor |
703 | | : public SymExprVisitor<EqualityExtractor, Optional<EqualityInfo>> { |
704 | | public: |
705 | 11.4k | Optional<EqualityInfo> VisitSymSymExpr(const SymSymExpr *Sym) const { |
706 | 11.4k | switch (Sym->getOpcode()) { |
707 | 5.15k | case BO_Sub: |
708 | | // This case is: A - B != 0 -> disequality check. |
709 | 5.15k | return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false}; |
710 | 666 | case BO_EQ: |
711 | | // This case is: A == B != 0 -> equality check. |
712 | 666 | return EqualityInfo{Sym->getLHS(), Sym->getRHS(), true}; |
713 | 325 | case BO_NE: |
714 | | // This case is: A != B != 0 -> diseqiality check. |
715 | 325 | return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false}; |
716 | 5.32k | default: |
717 | 5.32k | return llvm::None; |
718 | 11.4k | } |
719 | 11.4k | } |
720 | | }; |
721 | | }; |
722 | | |
723 | | //===----------------------------------------------------------------------===// |
724 | | // Intersection functions |
725 | | //===----------------------------------------------------------------------===// |
726 | | |
727 | | template <class SecondTy, class... RestTy> |
728 | | LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, |
729 | | RangeSet::Factory &F, RangeSet Head, |
730 | | SecondTy Second, RestTy... Tail); |
731 | | |
732 | | template <class... RangeTy> struct IntersectionTraits; |
733 | | |
734 | | template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> { |
735 | | // Found RangeSet, no need to check any further |
736 | | using Type = RangeSet; |
737 | | }; |
738 | | |
739 | | template <> struct IntersectionTraits<> { |
740 | | // We ran out of types, and we didn't find any RangeSet, so the result should |
741 | | // be optional. |
742 | | using Type = Optional<RangeSet>; |
743 | | }; |
744 | | |
745 | | template <class OptionalOrPointer, class... TailTy> |
746 | | struct IntersectionTraits<OptionalOrPointer, TailTy...> { |
747 | | // If current type is Optional or a raw pointer, we should keep looking. |
748 | | using Type = typename IntersectionTraits<TailTy...>::Type; |
749 | | }; |
750 | | |
751 | | template <class EndTy> |
752 | | LLVM_NODISCARD inline EndTy intersect(BasicValueFactory &BV, |
753 | 243k | RangeSet::Factory &F, EndTy End) { |
754 | | // If the list contains only RangeSet or Optional<RangeSet>, simply return |
755 | | // that range set. |
756 | 243k | return End; |
757 | 243k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet) Line | Count | Source | 753 | 95.8k | RangeSet::Factory &F, EndTy End) { | 754 | | // If the list contains only RangeSet or Optional<RangeSet>, simply return | 755 | | // that range set. | 756 | 95.8k | return End; | 757 | 95.8k | } |
RangeConstraintManager.cpp:llvm::Optional<clang::ento::RangeSet> (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 753 | 147k | RangeSet::Factory &F, EndTy End) { | 754 | | // If the list contains only RangeSet or Optional<RangeSet>, simply return | 755 | | // that range set. | 756 | 147k | return End; | 757 | 147k | } |
|
758 | | |
759 | | LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional<RangeSet> |
760 | 396 | intersect(BasicValueFactory &BV, RangeSet::Factory &F, const RangeSet *End) { |
761 | | // This is an extraneous conversion from a raw pointer into Optional<RangeSet> |
762 | 396 | if (End) { |
763 | 71 | return *End; |
764 | 71 | } |
765 | 325 | return llvm::None; |
766 | 396 | } |
767 | | |
768 | | template <class... RestTy> |
769 | | LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, |
770 | | RangeSet::Factory &F, RangeSet Head, |
771 | 1.75k | RangeSet Second, RestTy... Tail) { |
772 | | // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version |
773 | | // of the function and can be sure that the result is RangeSet. |
774 | 1.75k | return intersect(BV, F, F.intersect(Head, Second), Tail...); |
775 | 1.75k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 771 | 274 | RangeSet Second, RestTy... Tail) { | 772 | | // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version | 773 | | // of the function and can be sure that the result is RangeSet. | 774 | 274 | return intersect(BV, F, F.intersect(Head, Second), Tail...); | 775 | 274 | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet) Line | Count | Source | 771 | 1.47k | RangeSet Second, RestTy... Tail) { | 772 | | // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version | 773 | | // of the function and can be sure that the result is RangeSet. | 774 | 1.47k | return intersect(BV, F, F.intersect(Head, Second), Tail...); | 775 | 1.47k | } |
|
776 | | |
777 | | template <class SecondTy, class... RestTy> |
778 | | LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, |
779 | | RangeSet::Factory &F, RangeSet Head, |
780 | 191k | SecondTy Second, RestTy... Tail) { |
781 | 191k | if (Second) { |
782 | | // Here we call the <RangeSet,RangeSet,...> version of the function... |
783 | 1.75k | return intersect(BV, F, Head, *Second, Tail...); |
784 | 1.75k | } |
785 | | // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which |
786 | | // means that the result is definitely RangeSet. |
787 | 189k | return intersect(BV, F, Head, Tail...); |
788 | 191k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 780 | 95.5k | SecondTy Second, RestTy... Tail) { | 781 | 95.5k | if (Second) { | 782 | | // Here we call the <RangeSet,RangeSet,...> version of the function... | 783 | 274 | return intersect(BV, F, Head, *Second, Tail...); | 784 | 274 | } | 785 | | // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which | 786 | | // means that the result is definitely RangeSet. | 787 | 95.3k | return intersect(BV, F, Head, Tail...); | 788 | 95.5k | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 780 | 95.7k | SecondTy Second, RestTy... Tail) { | 781 | 95.7k | if (Second) { | 782 | | // Here we call the <RangeSet,RangeSet,...> version of the function... | 783 | 1.34k | return intersect(BV, F, Head, *Second, Tail...); | 784 | 1.34k | } | 785 | | // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which | 786 | | // means that the result is definitely RangeSet. | 787 | 94.3k | return intersect(BV, F, Head, Tail...); | 788 | 95.7k | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::intersect<clang::ento::RangeSet const*>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet, clang::ento::RangeSet const*) Line | Count | Source | 780 | 135 | SecondTy Second, RestTy... Tail) { | 781 | 135 | if (Second) { | 782 | | // Here we call the <RangeSet,RangeSet,...> version of the function... | 783 | 132 | return intersect(BV, F, Head, *Second, Tail...); | 784 | 132 | } | 785 | | // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which | 786 | | // means that the result is definitely RangeSet. | 787 | 3 | return intersect(BV, F, Head, Tail...); | 788 | 135 | } |
|
789 | | |
790 | | /// Main generic intersect function. |
791 | | /// It intersects all of the given range sets. If some of the given arguments |
792 | | /// don't hold a range set (nullptr or llvm::None), the function will skip them. |
793 | | /// |
794 | | /// Available representations for the arguments are: |
795 | | /// * RangeSet |
796 | | /// * Optional<RangeSet> |
797 | | /// * RangeSet * |
798 | | /// Pointer to a RangeSet is automatically assumed to be nullable and will get |
799 | | /// checked as well as the optional version. If this behaviour is undesired, |
800 | | /// please dereference the pointer in the call. |
801 | | /// |
802 | | /// Return type depends on the arguments' types. If we can be sure in compile |
803 | | /// time that there will be a range set as a result, the returning type is |
804 | | /// simply RangeSet, in other cases we have to back off to Optional<RangeSet>. |
805 | | /// |
806 | | /// Please, prefer optional range sets to raw pointers. If the last argument is |
807 | | /// a raw pointer and all previous arguments are None, it will cost one |
808 | | /// additional check to convert RangeSet * into Optional<RangeSet>. |
809 | | template <class HeadTy, class SecondTy, class... RestTy> |
810 | | LLVM_NODISCARD inline |
811 | | typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type |
812 | | intersect(BasicValueFactory &BV, RangeSet::Factory &F, HeadTy Head, |
813 | 391k | SecondTy Second, RestTy... Tail) { |
814 | 391k | if (Head) { |
815 | 95.8k | return intersect(BV, F, *Head, Second, Tail...); |
816 | 95.8k | } |
817 | 295k | return intersect(BV, F, Second, Tail...); |
818 | 391k | } RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >::Type (anonymous namespace)::intersect<clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet const*, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 813 | 243k | SecondTy Second, RestTy... Tail) { | 814 | 243k | if (Head) { | 815 | 95.5k | return intersect(BV, F, *Head, Second, Tail...); | 816 | 95.5k | } | 817 | 147k | return intersect(BV, F, Second, Tail...); | 818 | 243k | } |
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >::Type (anonymous namespace)::intersect<llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet> >(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, llvm::Optional<clang::ento::RangeSet>, llvm::Optional<clang::ento::RangeSet>) Line | Count | Source | 813 | 147k | SecondTy Second, RestTy... Tail) { | 814 | 147k | if (Head) { | 815 | 136 | return intersect(BV, F, *Head, Second, Tail...); | 816 | 136 | } | 817 | 147k | return intersect(BV, F, Second, Tail...); | 818 | 147k | } |
RangeConstraintManager.cpp:(anonymous namespace)::IntersectionTraits<clang::ento::RangeSet const*, clang::ento::RangeSet const*>::Type (anonymous namespace)::intersect<clang::ento::RangeSet const*, clang::ento::RangeSet const*>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, clang::ento::RangeSet const*, clang::ento::RangeSet const*) Line | Count | Source | 813 | 531 | SecondTy Second, RestTy... Tail) { | 814 | 531 | if (Head) { | 815 | 135 | return intersect(BV, F, *Head, Second, Tail...); | 816 | 135 | } | 817 | 396 | return intersect(BV, F, Second, Tail...); | 818 | 531 | } |
|
819 | | |
820 | | //===----------------------------------------------------------------------===// |
821 | | // Symbolic reasoning logic |
822 | | //===----------------------------------------------------------------------===// |
823 | | |
824 | | /// A little component aggregating all of the reasoning we have about |
825 | | /// the ranges of symbolic expressions. |
826 | | /// |
827 | | /// Even when we don't know the exact values of the operands, we still |
828 | | /// can get a pretty good estimate of the result's range. |
829 | | class SymbolicRangeInferrer |
830 | | : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> { |
831 | | public: |
832 | | template <class SourceType> |
833 | | static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F, |
834 | 194k | ProgramStateRef State, SourceType Origin) { |
835 | 194k | SymbolicRangeInferrer Inferrer(BV, F, State); |
836 | 194k | return Inferrer.infer(Origin); |
837 | 194k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<clang::ento::SymExpr const*>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*) Line | Count | Source | 834 | 194k | ProgramStateRef State, SourceType Origin) { | 835 | 194k | SymbolicRangeInferrer Inferrer(BV, F, State); | 836 | 194k | return Inferrer.infer(Origin); | 837 | 194k | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::inferRange<(anonymous namespace)::EquivalenceClass>(clang::ento::BasicValueFactory&, clang::ento::RangeSet::Factory&, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::EquivalenceClass) Line | Count | Source | 834 | 161 | ProgramStateRef State, SourceType Origin) { | 835 | 161 | SymbolicRangeInferrer Inferrer(BV, F, State); | 836 | 161 | return Inferrer.infer(Origin); | 837 | 161 | } |
|
838 | | |
839 | 103k | RangeSet VisitSymExpr(SymbolRef Sym) { |
840 | | // If we got to this function, the actual type of the symbolic |
841 | | // expression is not supported for advanced inference. |
842 | | // In this case, we simply backoff to the default "let's simply |
843 | | // infer the range from the expression's type". |
844 | 103k | return infer(Sym->getType()); |
845 | 103k | } |
846 | | |
847 | 38.7k | RangeSet VisitSymIntExpr(const SymIntExpr *Sym) { |
848 | 38.7k | return VisitBinaryOperator(Sym); |
849 | 38.7k | } |
850 | | |
851 | 176 | RangeSet VisitIntSymExpr(const IntSymExpr *Sym) { |
852 | 176 | return VisitBinaryOperator(Sym); |
853 | 176 | } |
854 | | |
855 | 4.92k | RangeSet VisitSymSymExpr(const SymSymExpr *Sym) { |
856 | 4.92k | return VisitBinaryOperator(Sym); |
857 | 4.92k | } |
858 | | |
859 | | private: |
860 | | SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F, |
861 | | ProgramStateRef S) |
862 | 194k | : ValueFactory(BV), RangeFactory(F), State(S) {} |
863 | | |
864 | | /// Infer range information from the given integer constant. |
865 | | /// |
866 | | /// It's not a real "inference", but is here for operating with |
867 | | /// sub-expressions in a more polymorphic manner. |
868 | 38.9k | RangeSet inferAs(const llvm::APSInt &Val, QualType) { |
869 | 38.9k | return {RangeFactory, Val}; |
870 | 38.9k | } |
871 | | |
872 | | /// Infer range information from symbol in the context of the given type. |
873 | 48.7k | RangeSet inferAs(SymbolRef Sym, QualType DestType) { |
874 | 48.7k | QualType ActualType = Sym->getType(); |
875 | | // Check that we can reason about the symbol at all. |
876 | 48.7k | if (ActualType->isIntegralOrEnumerationType() || |
877 | 48.7k | Loc::isLocType(ActualType)1.60k ) { |
878 | 48.7k | return infer(Sym); |
879 | 48.7k | } |
880 | | // Otherwise, let's simply infer from the destination type. |
881 | | // We couldn't figure out nothing else about that expression. |
882 | 4 | return infer(DestType); |
883 | 48.7k | } |
884 | | |
885 | 243k | RangeSet infer(SymbolRef Sym) { |
886 | 243k | if (Optional<RangeSet> ConstraintBasedRange = intersect( |
887 | 243k | ValueFactory, RangeFactory, getConstraint(State, Sym), |
888 | | // If Sym is a difference of symbols A - B, then maybe we have range |
889 | | // set stored for B - A. |
890 | | // |
891 | | // If we have range set stored for both A - B and B - A then |
892 | | // calculate the effective range set by intersecting the range set |
893 | | // for A - B and the negated range set of B - A. |
894 | 243k | getRangeForNegatedSub(Sym), getRangeForEqualities(Sym))) { |
895 | 95.7k | return *ConstraintBasedRange; |
896 | 95.7k | } |
897 | | |
898 | | // If Sym is a comparison expression (except <=>), |
899 | | // find any other comparisons with the same operands. |
900 | | // See function description. |
901 | 147k | if (Optional<RangeSet> CmpRangeSet = getRangeForComparisonSymbol(Sym)) { |
902 | 307 | return *CmpRangeSet; |
903 | 307 | } |
904 | | |
905 | 147k | return Visit(Sym); |
906 | 147k | } |
907 | | |
908 | 161 | RangeSet infer(EquivalenceClass Class) { |
909 | 161 | if (const RangeSet *AssociatedConstraint = getConstraint(State, Class)) |
910 | 31 | return *AssociatedConstraint; |
911 | | |
912 | 130 | return infer(Class.getType()); |
913 | 161 | } |
914 | | |
915 | | /// Infer range information solely from the type. |
916 | 112k | RangeSet infer(QualType T) { |
917 | | // Lazily generate a new RangeSet representing all possible values for the |
918 | | // given symbol type. |
919 | 112k | RangeSet Result(RangeFactory, ValueFactory.getMinValue(T), |
920 | 112k | ValueFactory.getMaxValue(T)); |
921 | | |
922 | | // References are known to be non-zero. |
923 | 112k | if (T->isReferenceType()) |
924 | 15.7k | return assumeNonZero(Result, T); |
925 | | |
926 | 96.5k | return Result; |
927 | 112k | } |
928 | | |
929 | | template <class BinarySymExprTy> |
930 | 43.8k | RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { |
931 | | // TODO #1: VisitBinaryOperator implementation might not make a good |
932 | | // use of the inferred ranges. In this case, we might be calculating |
933 | | // everything for nothing. This being said, we should introduce some |
934 | | // sort of laziness mechanism here. |
935 | | // |
936 | | // TODO #2: We didn't go into the nested expressions before, so it |
937 | | // might cause us spending much more time doing the inference. |
938 | | // This can be a problem for deeply nested expressions that are |
939 | | // involved in conditions and get tested continuously. We definitely |
940 | | // need to address this issue and introduce some sort of caching |
941 | | // in here. |
942 | 43.8k | QualType ResultType = Sym->getType(); |
943 | 43.8k | return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), |
944 | 43.8k | Sym->getOpcode(), |
945 | 43.8k | inferAs(Sym->getRHS(), ResultType), ResultType); |
946 | 43.8k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0> >(clang::ento::BinarySymExprImpl<llvm::APSInt const&, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)0> const*) Line | Count | Source | 930 | 176 | RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { | 931 | | // TODO #1: VisitBinaryOperator implementation might not make a good | 932 | | // use of the inferred ranges. In this case, we might be calculating | 933 | | // everything for nothing. This being said, we should introduce some | 934 | | // sort of laziness mechanism here. | 935 | | // | 936 | | // TODO #2: We didn't go into the nested expressions before, so it | 937 | | // might cause us spending much more time doing the inference. | 938 | | // This can be a problem for deeply nested expressions that are | 939 | | // involved in conditions and get tested continuously. We definitely | 940 | | // need to address this issue and introduce some sort of caching | 941 | | // in here. | 942 | 176 | QualType ResultType = Sym->getType(); | 943 | 176 | return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), | 944 | 176 | Sym->getOpcode(), | 945 | 176 | inferAs(Sym->getRHS(), ResultType), ResultType); | 946 | 176 | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, llvm::APSInt const&, (clang::ento::SymExpr::Kind)1> const*) Line | Count | Source | 930 | 38.7k | RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { | 931 | | // TODO #1: VisitBinaryOperator implementation might not make a good | 932 | | // use of the inferred ranges. In this case, we might be calculating | 933 | | // everything for nothing. This being said, we should introduce some | 934 | | // sort of laziness mechanism here. | 935 | | // | 936 | | // TODO #2: We didn't go into the nested expressions before, so it | 937 | | // might cause us spending much more time doing the inference. | 938 | | // This can be a problem for deeply nested expressions that are | 939 | | // involved in conditions and get tested continuously. We definitely | 940 | | // need to address this issue and introduce some sort of caching | 941 | | // in here. | 942 | 38.7k | QualType ResultType = Sym->getType(); | 943 | 38.7k | return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), | 944 | 38.7k | Sym->getOpcode(), | 945 | 38.7k | inferAs(Sym->getRHS(), ResultType), ResultType); | 946 | 38.7k | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2> >(clang::ento::BinarySymExprImpl<clang::ento::SymExpr const*, clang::ento::SymExpr const*, (clang::ento::SymExpr::Kind)2> const*) Line | Count | Source | 930 | 4.92k | RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { | 931 | | // TODO #1: VisitBinaryOperator implementation might not make a good | 932 | | // use of the inferred ranges. In this case, we might be calculating | 933 | | // everything for nothing. This being said, we should introduce some | 934 | | // sort of laziness mechanism here. | 935 | | // | 936 | | // TODO #2: We didn't go into the nested expressions before, so it | 937 | | // might cause us spending much more time doing the inference. | 938 | | // This can be a problem for deeply nested expressions that are | 939 | | // involved in conditions and get tested continuously. We definitely | 940 | | // need to address this issue and introduce some sort of caching | 941 | | // in here. | 942 | 4.92k | QualType ResultType = Sym->getType(); | 943 | 4.92k | return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), | 944 | 4.92k | Sym->getOpcode(), | 945 | 4.92k | inferAs(Sym->getRHS(), ResultType), ResultType); | 946 | 4.92k | } |
|
947 | | |
948 | | RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op, |
949 | 43.8k | RangeSet RHS, QualType T) { |
950 | 43.8k | switch (Op) { |
951 | 85 | case BO_Or: |
952 | 85 | return VisitBinaryOperator<BO_Or>(LHS, RHS, T); |
953 | 36.2k | case BO_And: |
954 | 36.2k | return VisitBinaryOperator<BO_And>(LHS, RHS, T); |
955 | 244 | case BO_Rem: |
956 | 244 | return VisitBinaryOperator<BO_Rem>(LHS, RHS, T); |
957 | 7.28k | default: |
958 | 7.28k | return infer(T); |
959 | 43.8k | } |
960 | 43.8k | } |
961 | | |
962 | | //===----------------------------------------------------------------------===// |
963 | | // Ranges and operators |
964 | | //===----------------------------------------------------------------------===// |
965 | | |
966 | | /// Return a rough approximation of the given range set. |
967 | | /// |
968 | | /// For the range set: |
969 | | /// { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] } |
970 | | /// it will return the range [x_0, y_N]. |
971 | 73.0k | static Range fillGaps(RangeSet Origin) { |
972 | 73.0k | assert(!Origin.isEmpty()); |
973 | 0 | return {Origin.getMinValue(), Origin.getMaxValue()}; |
974 | 73.0k | } |
975 | | |
976 | | /// Try to convert given range into the given type. |
977 | | /// |
978 | | /// It will return llvm::None only when the trivial conversion is possible. |
979 | 73.0k | llvm::Optional<Range> convert(const Range &Origin, APSIntType To) { |
980 | 73.0k | if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within || |
981 | 73.0k | To.testInRange(Origin.To(), false) != APSIntType::RTR_Within73.0k ) { |
982 | 28 | return llvm::None; |
983 | 28 | } |
984 | 73.0k | return Range(ValueFactory.Convert(To, Origin.From()), |
985 | 73.0k | ValueFactory.Convert(To, Origin.To())); |
986 | 73.0k | } |
987 | | |
988 | | template <BinaryOperator::Opcode Op> |
989 | 36.5k | RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { |
990 | | // We should propagate information about unfeasbility of one of the |
991 | | // operands to the resulting range. |
992 | 36.5k | if (LHS.isEmpty() || RHS.isEmpty()) { |
993 | 0 | return RangeFactory.getEmptySet(); |
994 | 0 | } |
995 | | |
996 | 36.5k | Range CoarseLHS = fillGaps(LHS); |
997 | 36.5k | Range CoarseRHS = fillGaps(RHS); |
998 | | |
999 | 36.5k | APSIntType ResultType = ValueFactory.getAPSIntType(T); |
1000 | | |
1001 | | // We need to convert ranges to the resulting type, so we can compare values |
1002 | | // and combine them in a meaningful (in terms of the given operation) way. |
1003 | 36.5k | auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); |
1004 | 36.5k | auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); |
1005 | | |
1006 | | // It is hard to reason about ranges when conversion changes |
1007 | | // borders of the ranges. |
1008 | 36.5k | if (!ConvertedCoarseLHS || !ConvertedCoarseRHS36.5k ) { |
1009 | 28 | return infer(T); |
1010 | 28 | } |
1011 | | |
1012 | 36.5k | return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); |
1013 | 36.5k | } RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)18>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType) Line | Count | Source | 989 | 85 | RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { | 990 | | // We should propagate information about unfeasbility of one of the | 991 | | // operands to the resulting range. | 992 | 85 | if (LHS.isEmpty() || RHS.isEmpty()) { | 993 | 0 | return RangeFactory.getEmptySet(); | 994 | 0 | } | 995 | | | 996 | 85 | Range CoarseLHS = fillGaps(LHS); | 997 | 85 | Range CoarseRHS = fillGaps(RHS); | 998 | | | 999 | 85 | APSIntType ResultType = ValueFactory.getAPSIntType(T); | 1000 | | | 1001 | | // We need to convert ranges to the resulting type, so we can compare values | 1002 | | // and combine them in a meaningful (in terms of the given operation) way. | 1003 | 85 | auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); | 1004 | 85 | auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); | 1005 | | | 1006 | | // It is hard to reason about ranges when conversion changes | 1007 | | // borders of the ranges. | 1008 | 85 | if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) { | 1009 | 0 | return infer(T); | 1010 | 0 | } | 1011 | | | 1012 | 85 | return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); | 1013 | 85 | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)16>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType) Line | Count | Source | 989 | 36.2k | RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { | 990 | | // We should propagate information about unfeasbility of one of the | 991 | | // operands to the resulting range. | 992 | 36.2k | if (LHS.isEmpty() || RHS.isEmpty()) { | 993 | 0 | return RangeFactory.getEmptySet(); | 994 | 0 | } | 995 | | | 996 | 36.2k | Range CoarseLHS = fillGaps(LHS); | 997 | 36.2k | Range CoarseRHS = fillGaps(RHS); | 998 | | | 999 | 36.2k | APSIntType ResultType = ValueFactory.getAPSIntType(T); | 1000 | | | 1001 | | // We need to convert ranges to the resulting type, so we can compare values | 1002 | | // and combine them in a meaningful (in terms of the given operation) way. | 1003 | 36.2k | auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); | 1004 | 36.2k | auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); | 1005 | | | 1006 | | // It is hard to reason about ranges when conversion changes | 1007 | | // borders of the ranges. | 1008 | 36.2k | if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) { | 1009 | 0 | return infer(T); | 1010 | 0 | } | 1011 | | | 1012 | 36.2k | return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); | 1013 | 36.2k | } |
RangeConstraintManager.cpp:clang::ento::RangeSet (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator<(clang::BinaryOperatorKind)4>(clang::ento::RangeSet, clang::ento::RangeSet, clang::QualType) Line | Count | Source | 989 | 244 | RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { | 990 | | // We should propagate information about unfeasbility of one of the | 991 | | // operands to the resulting range. | 992 | 244 | if (LHS.isEmpty() || RHS.isEmpty()) { | 993 | 0 | return RangeFactory.getEmptySet(); | 994 | 0 | } | 995 | | | 996 | 244 | Range CoarseLHS = fillGaps(LHS); | 997 | 244 | Range CoarseRHS = fillGaps(RHS); | 998 | | | 999 | 244 | APSIntType ResultType = ValueFactory.getAPSIntType(T); | 1000 | | | 1001 | | // We need to convert ranges to the resulting type, so we can compare values | 1002 | | // and combine them in a meaningful (in terms of the given operation) way. | 1003 | 244 | auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); | 1004 | 244 | auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); | 1005 | | | 1006 | | // It is hard to reason about ranges when conversion changes | 1007 | | // borders of the ranges. | 1008 | 244 | if (!ConvertedCoarseLHS || !ConvertedCoarseRHS228 ) { | 1009 | 28 | return infer(T); | 1010 | 28 | } | 1011 | | | 1012 | 216 | return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); | 1013 | 244 | } |
|
1014 | | |
1015 | | template <BinaryOperator::Opcode Op> |
1016 | | RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) { |
1017 | | return infer(T); |
1018 | | } |
1019 | | |
1020 | | /// Return a symmetrical range for the given range and type. |
1021 | | /// |
1022 | | /// If T is signed, return the smallest range [-x..x] that covers the original |
1023 | | /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't |
1024 | | /// exist due to original range covering min(T)). |
1025 | | /// |
1026 | | /// If T is unsigned, return the smallest range [0..x] that covers the |
1027 | | /// original range. |
1028 | 216 | Range getSymmetricalRange(Range Origin, QualType T) { |
1029 | 216 | APSIntType RangeType = ValueFactory.getAPSIntType(T); |
1030 | | |
1031 | 216 | if (RangeType.isUnsigned()) { |
1032 | 48 | return Range(ValueFactory.getMinValue(RangeType), Origin.To()); |
1033 | 48 | } |
1034 | | |
1035 | 168 | if (Origin.From().isMinSignedValue()) { |
1036 | | // If mini is a minimal signed value, absolute value of it is greater |
1037 | | // than the maximal signed value. In order to avoid these |
1038 | | // complications, we simply return the whole range. |
1039 | 16 | return {ValueFactory.getMinValue(RangeType), |
1040 | 16 | ValueFactory.getMaxValue(RangeType)}; |
1041 | 16 | } |
1042 | | |
1043 | | // At this point, we are sure that the type is signed and we can safely |
1044 | | // use unary - operator. |
1045 | | // |
1046 | | // While calculating absolute maximum, we can use the following formula |
1047 | | // because of these reasons: |
1048 | | // * If From >= 0 then To >= From and To >= -From. |
1049 | | // AbsMax == To == max(To, -From) |
1050 | | // * If To <= 0 then -From >= -To and -From >= From. |
1051 | | // AbsMax == -From == max(-From, To) |
1052 | | // * Otherwise, From <= 0, To >= 0, and |
1053 | | // AbsMax == max(abs(From), abs(To)) |
1054 | 152 | llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To()); |
1055 | | |
1056 | | // Intersection is guaranteed to be non-empty. |
1057 | 152 | return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)}; |
1058 | 168 | } |
1059 | | |
1060 | | /// Return a range set subtracting zero from \p Domain. |
1061 | 17.0k | RangeSet assumeNonZero(RangeSet Domain, QualType T) { |
1062 | 17.0k | APSIntType IntType = ValueFactory.getAPSIntType(T); |
1063 | 17.0k | return RangeFactory.deletePoint(Domain, IntType.getZeroValue()); |
1064 | 17.0k | } |
1065 | | |
1066 | | // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to |
1067 | | // obtain the negated symbolic expression instead of constructing the |
1068 | | // symbol manually. This will allow us to support finding ranges of not |
1069 | | // only negated SymSymExpr-type expressions, but also of other, simpler |
1070 | | // expressions which we currently do not know how to negate. |
1071 | 243k | Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) { |
1072 | 243k | if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { |
1073 | 7.01k | if (SSE->getOpcode() == BO_Sub) { |
1074 | 3.46k | QualType T = Sym->getType(); |
1075 | | |
1076 | | // Do not negate unsigned ranges |
1077 | 3.46k | if (!T->isUnsignedIntegerOrEnumerationType() && |
1078 | 3.46k | !T->isSignedIntegerOrEnumerationType()3.37k ) |
1079 | 0 | return llvm::None; |
1080 | | |
1081 | 3.46k | SymbolManager &SymMgr = State->getSymbolManager(); |
1082 | 3.46k | SymbolRef NegatedSym = |
1083 | 3.46k | SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); |
1084 | | |
1085 | 3.46k | if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) { |
1086 | 410 | return RangeFactory.negate(*NegatedRange); |
1087 | 410 | } |
1088 | 3.46k | } |
1089 | 7.01k | } |
1090 | 242k | return llvm::None; |
1091 | 243k | } |
1092 | | |
1093 | | // Returns ranges only for binary comparison operators (except <=>) |
1094 | | // when left and right operands are symbolic values. |
1095 | | // Finds any other comparisons with the same operands. |
1096 | | // Then do logical calculations and refuse impossible branches. |
1097 | | // E.g. (x < y) and (x > y) at the same time are impossible. |
1098 | | // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only. |
1099 | | // E.g. (x == y) and (y == x) are just reversed but the same. |
1100 | | // It covers all possible combinations (see CmpOpTable description). |
1101 | | // Note that `x` and `y` can also stand for subexpressions, |
1102 | | // not only for actual symbols. |
1103 | 147k | Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) { |
1104 | 147k | const auto *SSE = dyn_cast<SymSymExpr>(Sym); |
1105 | 147k | if (!SSE) |
1106 | 142k | return llvm::None; |
1107 | | |
1108 | 5.23k | BinaryOperatorKind CurrentOP = SSE->getOpcode(); |
1109 | | |
1110 | | // We currently do not support <=> (C++20). |
1111 | 5.23k | if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp)2.88k ) |
1112 | 2.34k | return llvm::None; |
1113 | | |
1114 | 2.88k | static const OperatorRelationsTable CmpOpTable{}; |
1115 | | |
1116 | 2.88k | const SymExpr *LHS = SSE->getLHS(); |
1117 | 2.88k | const SymExpr *RHS = SSE->getRHS(); |
1118 | 2.88k | QualType T = SSE->getType(); |
1119 | | |
1120 | 2.88k | SymbolManager &SymMgr = State->getSymbolManager(); |
1121 | | |
1122 | 2.88k | int UnknownStates = 0; |
1123 | | |
1124 | | // Loop goes through all of the columns exept the last one ('UnknownX2'). |
1125 | | // We treat `UnknownX2` column separately at the end of the loop body. |
1126 | 18.8k | for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i15.9k ) { |
1127 | | |
1128 | | // Let's find an expression e.g. (x < y). |
1129 | 16.2k | BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i); |
1130 | 16.2k | const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T); |
1131 | 16.2k | const RangeSet *QueriedRangeSet = getConstraint(State, SymSym); |
1132 | | |
1133 | | // If ranges were not previously found, |
1134 | | // try to find a reversed expression (y > x). |
1135 | 16.2k | if (!QueriedRangeSet) { |
1136 | 15.9k | const BinaryOperatorKind ROP = |
1137 | 15.9k | BinaryOperator::reverseComparisonOp(QueriedOP); |
1138 | 15.9k | SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T); |
1139 | 15.9k | QueriedRangeSet = getConstraint(State, SymSym); |
1140 | 15.9k | } |
1141 | | |
1142 | 16.2k | if (!QueriedRangeSet || QueriedRangeSet->isEmpty()494 ) |
1143 | 15.7k | continue; |
1144 | | |
1145 | 494 | const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue(); |
1146 | 494 | const bool isInFalseBranch = |
1147 | 494 | ConcreteValue ? (*ConcreteValue == 0)444 : false50 ; |
1148 | | |
1149 | | // If it is a false branch, we shall be guided by opposite operator, |
1150 | | // because the table is made assuming we are in the true branch. |
1151 | | // E.g. when (x <= y) is false, then (x > y) is true. |
1152 | 494 | if (isInFalseBranch) |
1153 | 256 | QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP); |
1154 | | |
1155 | 494 | OperatorRelationsTable::TriStateKind BranchState = |
1156 | 494 | CmpOpTable.getCmpOpState(CurrentOP, QueriedOP); |
1157 | | |
1158 | 494 | if (BranchState == OperatorRelationsTable::Unknown) { |
1159 | 241 | if (++UnknownStates == 2) |
1160 | | // If we met both Unknown states. |
1161 | | // if (x <= y) // assume true |
1162 | | // if (x != y) // assume true |
1163 | | // if (x < y) // would be also true |
1164 | | // Get a state from `UnknownX2` column. |
1165 | 54 | BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP); |
1166 | 187 | else |
1167 | 187 | continue; |
1168 | 241 | } |
1169 | | |
1170 | 307 | return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T)180 |
1171 | 307 | : getFalseRange(T)127 ; |
1172 | 494 | } |
1173 | | |
1174 | 2.58k | return llvm::None; |
1175 | 2.88k | } |
1176 | | |
1177 | 243k | Optional<RangeSet> getRangeForEqualities(SymbolRef Sym) { |
1178 | 243k | Optional<EqualityInfo> Equality = EqualityInfo::extract(Sym); |
1179 | | |
1180 | 243k | if (!Equality) |
1181 | 239k | return llvm::None; |
1182 | | |
1183 | 4.00k | if (Optional<bool> AreEqual = EquivalenceClass::areEqual( |
1184 | 4.00k | State, Equality->Left, Equality->Right)) { |
1185 | 1.40k | if (*AreEqual == Equality->IsEquality) { |
1186 | 1.16k | return getTrueRange(Sym->getType()); |
1187 | 1.16k | } |
1188 | 234 | return getFalseRange(Sym->getType()); |
1189 | 1.40k | } |
1190 | | |
1191 | 2.60k | return llvm::None; |
1192 | 4.00k | } |
1193 | | |
1194 | 1.34k | RangeSet getTrueRange(QualType T) { |
1195 | 1.34k | RangeSet TypeRange = infer(T); |
1196 | 1.34k | return assumeNonZero(TypeRange, T); |
1197 | 1.34k | } |
1198 | | |
1199 | 361 | RangeSet getFalseRange(QualType T) { |
1200 | 361 | const llvm::APSInt &Zero = ValueFactory.getValue(0, T); |
1201 | 361 | return RangeSet(RangeFactory, Zero); |
1202 | 361 | } |
1203 | | |
1204 | | BasicValueFactory &ValueFactory; |
1205 | | RangeSet::Factory &RangeFactory; |
1206 | | ProgramStateRef State; |
1207 | | }; |
1208 | | |
1209 | | //===----------------------------------------------------------------------===// |
1210 | | // Range-based reasoning about symbolic operations |
1211 | | //===----------------------------------------------------------------------===// |
1212 | | |
1213 | | template <> |
1214 | | RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS, |
1215 | 85 | QualType T) { |
1216 | 85 | APSIntType ResultType = ValueFactory.getAPSIntType(T); |
1217 | 85 | llvm::APSInt Zero = ResultType.getZeroValue(); |
1218 | | |
1219 | 85 | bool IsLHSPositiveOrZero = LHS.From() >= Zero; |
1220 | 85 | bool IsRHSPositiveOrZero = RHS.From() >= Zero; |
1221 | | |
1222 | 85 | bool IsLHSNegative = LHS.To() < Zero; |
1223 | 85 | bool IsRHSNegative = RHS.To() < Zero; |
1224 | | |
1225 | | // Check if both ranges have the same sign. |
1226 | 85 | if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero49 ) || |
1227 | 85 | (36 IsLHSNegative36 && IsRHSNegative28 )) { |
1228 | | // The result is definitely greater or equal than any of the operands. |
1229 | 69 | const llvm::APSInt &Min = std::max(LHS.From(), RHS.From()); |
1230 | | |
1231 | | // We estimate maximal value for positives as the maximal value for the |
1232 | | // given type. For negatives, we estimate it with -1 (e.g. 0x11111111). |
1233 | | // |
1234 | | // TODO: We basically, limit the resulting range from below, but don't do |
1235 | | // anything with the upper bound. |
1236 | | // |
1237 | | // For positive operands, it can be done as follows: for the upper |
1238 | | // bound of LHS and RHS we calculate the most significant bit set. |
1239 | | // Let's call it the N-th bit. Then we can estimate the maximal |
1240 | | // number to be 2^(N+1)-1, i.e. the number with all the bits up to |
1241 | | // the N-th bit set. |
1242 | 69 | const llvm::APSInt &Max = IsLHSNegative |
1243 | 69 | ? ValueFactory.getValue(--Zero)20 |
1244 | 69 | : ValueFactory.getMaxValue(ResultType)49 ; |
1245 | | |
1246 | 69 | return {RangeFactory, ValueFactory.getValue(Min), Max}; |
1247 | 69 | } |
1248 | | |
1249 | | // Otherwise, let's check if at least one of the operands is negative. |
1250 | 16 | if (IsLHSNegative || IsRHSNegative8 ) { |
1251 | | // This means that the result is definitely negative as well. |
1252 | 10 | return {RangeFactory, ValueFactory.getMinValue(ResultType), |
1253 | 10 | ValueFactory.getValue(--Zero)}; |
1254 | 10 | } |
1255 | | |
1256 | 6 | RangeSet DefaultRange = infer(T); |
1257 | | |
1258 | | // It is pretty hard to reason about operands with different signs |
1259 | | // (and especially with possibly different signs). We simply check if it |
1260 | | // can be zero. In order to conclude that the result could not be zero, |
1261 | | // at least one of the operands should be definitely not zero itself. |
1262 | 6 | if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) { |
1263 | 4 | return assumeNonZero(DefaultRange, T); |
1264 | 4 | } |
1265 | | |
1266 | | // Nothing much else to do here. |
1267 | 2 | return DefaultRange; |
1268 | 6 | } |
1269 | | |
1270 | | template <> |
1271 | | RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS, |
1272 | | Range RHS, |
1273 | 36.2k | QualType T) { |
1274 | 36.2k | APSIntType ResultType = ValueFactory.getAPSIntType(T); |
1275 | 36.2k | llvm::APSInt Zero = ResultType.getZeroValue(); |
1276 | | |
1277 | 36.2k | bool IsLHSPositiveOrZero = LHS.From() >= Zero; |
1278 | 36.2k | bool IsRHSPositiveOrZero = RHS.From() >= Zero; |
1279 | | |
1280 | 36.2k | bool IsLHSNegative = LHS.To() < Zero; |
1281 | 36.2k | bool IsRHSNegative = RHS.To() < Zero; |
1282 | | |
1283 | | // Check if both ranges have the same sign. |
1284 | 36.2k | if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero53 ) || |
1285 | 36.2k | (36.1k IsLHSNegative36.1k && IsRHSNegative12 )) { |
1286 | | // The result is definitely less or equal than any of the operands. |
1287 | 47 | const llvm::APSInt &Max = std::min(LHS.To(), RHS.To()); |
1288 | | |
1289 | | // We conservatively estimate lower bound to be the smallest positive |
1290 | | // or negative value corresponding to the sign of the operands. |
1291 | 47 | const llvm::APSInt &Min = IsLHSNegative |
1292 | 47 | ? ValueFactory.getMinValue(ResultType)10 |
1293 | 47 | : ValueFactory.getValue(Zero)37 ; |
1294 | | |
1295 | 47 | return {RangeFactory, Min, Max}; |
1296 | 47 | } |
1297 | | |
1298 | | // Otherwise, let's check if at least one of the operands is positive. |
1299 | 36.1k | if (IsLHSPositiveOrZero || IsRHSPositiveOrZero36.1k ) { |
1300 | | // This makes result definitely positive. |
1301 | | // |
1302 | | // We can also reason about a maximal value by finding the maximal |
1303 | | // value of the positive operand. |
1304 | 36.0k | const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To()16 : RHS.To()36.0k ; |
1305 | | |
1306 | | // The minimal value on the other hand is much harder to reason about. |
1307 | | // The only thing we know for sure is that the result is positive. |
1308 | 36.0k | return {RangeFactory, ValueFactory.getValue(Zero), |
1309 | 36.0k | ValueFactory.getValue(Max)}; |
1310 | 36.0k | } |
1311 | | |
1312 | | // Nothing much else to do here. |
1313 | 137 | return infer(T); |
1314 | 36.1k | } |
1315 | | |
1316 | | template <> |
1317 | | RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS, |
1318 | | Range RHS, |
1319 | 216 | QualType T) { |
1320 | 216 | llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue(); |
1321 | | |
1322 | 216 | Range ConservativeRange = getSymmetricalRange(RHS, T); |
1323 | | |
1324 | 216 | llvm::APSInt Max = ConservativeRange.To(); |
1325 | 216 | llvm::APSInt Min = ConservativeRange.From(); |
1326 | | |
1327 | 216 | if (Max == Zero) { |
1328 | | // It's an undefined behaviour to divide by 0 and it seems like we know |
1329 | | // for sure that RHS is 0. Let's say that the resulting range is |
1330 | | // simply infeasible for that matter. |
1331 | 0 | return RangeFactory.getEmptySet(); |
1332 | 0 | } |
1333 | | |
1334 | | // At this point, our conservative range is closed. The result, however, |
1335 | | // couldn't be greater than the RHS' maximal absolute value. Because of |
1336 | | // this reason, we turn the range into open (or half-open in case of |
1337 | | // unsigned integers). |
1338 | | // |
1339 | | // While we operate on integer values, an open interval (a, b) can be easily |
1340 | | // represented by the closed interval [a + 1, b - 1]. And this is exactly |
1341 | | // what we do next. |
1342 | | // |
1343 | | // If we are dealing with unsigned case, we shouldn't move the lower bound. |
1344 | 216 | if (Min.isSigned()) { |
1345 | 168 | ++Min; |
1346 | 168 | } |
1347 | 216 | --Max; |
1348 | | |
1349 | 216 | bool IsLHSPositiveOrZero = LHS.From() >= Zero; |
1350 | 216 | bool IsRHSPositiveOrZero = RHS.From() >= Zero; |
1351 | | |
1352 | | // Remainder operator results with negative operands is implementation |
1353 | | // defined. Positive cases are much easier to reason about though. |
1354 | 216 | if (IsLHSPositiveOrZero && IsRHSPositiveOrZero134 ) { |
1355 | | // If maximal value of LHS is less than maximal value of RHS, |
1356 | | // the result won't get greater than LHS.To(). |
1357 | 98 | Max = std::min(LHS.To(), Max); |
1358 | | // We want to check if it is a situation similar to the following: |
1359 | | // |
1360 | | // <------------|---[ LHS ]--------[ RHS ]-----> |
1361 | | // -INF 0 +INF |
1362 | | // |
1363 | | // In this situation, we can conclude that (LHS / RHS) == 0 and |
1364 | | // (LHS % RHS) == LHS. |
1365 | 98 | Min = LHS.To() < RHS.From() ? LHS.From()14 : Zero84 ; |
1366 | 98 | } |
1367 | | |
1368 | | // Nevertheless, the symmetrical range for RHS is a conservative estimate |
1369 | | // for any sign of either LHS, or RHS. |
1370 | 216 | return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; |
1371 | 216 | } |
1372 | | |
1373 | | //===----------------------------------------------------------------------===// |
1374 | | // Constraint manager implementation details |
1375 | | //===----------------------------------------------------------------------===// |
1376 | | |
1377 | | class RangeConstraintManager : public RangedConstraintManager { |
1378 | | public: |
1379 | | RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) |
1380 | 13.8k | : RangedConstraintManager(EE, SVB), F(getBasicVals()) {} |
1381 | | |
1382 | | //===------------------------------------------------------------------===// |
1383 | | // Implementation for interface from ConstraintManager. |
1384 | | //===------------------------------------------------------------------===// |
1385 | | |
1386 | | bool haveEqualConstraints(ProgramStateRef S1, |
1387 | 8.49k | ProgramStateRef S2) const override { |
1388 | | // NOTE: ClassMembers are as simple as back pointers for ClassMap, |
1389 | | // so comparing constraint ranges and class maps should be |
1390 | | // sufficient. |
1391 | 8.49k | return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() && |
1392 | 8.49k | S1->get<ClassMap>() == S2->get<ClassMap>()3.84k ; |
1393 | 8.49k | } |
1394 | | |
1395 | | bool canReasonAbout(SVal X) const override; |
1396 | | |
1397 | | ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; |
1398 | | |
1399 | | const llvm::APSInt *getSymVal(ProgramStateRef State, |
1400 | | SymbolRef Sym) const override; |
1401 | | |
1402 | | ProgramStateRef removeDeadBindings(ProgramStateRef State, |
1403 | | SymbolReaper &SymReaper) override; |
1404 | | |
1405 | | void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", |
1406 | | unsigned int Space = 0, bool IsDot = false) const override; |
1407 | | |
1408 | | //===------------------------------------------------------------------===// |
1409 | | // Implementation for interface from RangedConstraintManager. |
1410 | | //===------------------------------------------------------------------===// |
1411 | | |
1412 | | ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, |
1413 | | const llvm::APSInt &V, |
1414 | | const llvm::APSInt &Adjustment) override; |
1415 | | |
1416 | | ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, |
1417 | | const llvm::APSInt &V, |
1418 | | const llvm::APSInt &Adjustment) override; |
1419 | | |
1420 | | ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, |
1421 | | const llvm::APSInt &V, |
1422 | | const llvm::APSInt &Adjustment) override; |
1423 | | |
1424 | | ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, |
1425 | | const llvm::APSInt &V, |
1426 | | const llvm::APSInt &Adjustment) override; |
1427 | | |
1428 | | ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, |
1429 | | const llvm::APSInt &V, |
1430 | | const llvm::APSInt &Adjustment) override; |
1431 | | |
1432 | | ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, |
1433 | | const llvm::APSInt &V, |
1434 | | const llvm::APSInt &Adjustment) override; |
1435 | | |
1436 | | ProgramStateRef assumeSymWithinInclusiveRange( |
1437 | | ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, |
1438 | | const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; |
1439 | | |
1440 | | ProgramStateRef assumeSymOutsideInclusiveRange( |
1441 | | ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, |
1442 | | const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; |
1443 | | |
1444 | | private: |
1445 | | RangeSet::Factory F; |
1446 | | |
1447 | | RangeSet getRange(ProgramStateRef State, SymbolRef Sym); |
1448 | | RangeSet getRange(ProgramStateRef State, EquivalenceClass Class); |
1449 | | |
1450 | | RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, |
1451 | | const llvm::APSInt &Int, |
1452 | | const llvm::APSInt &Adjustment); |
1453 | | RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, |
1454 | | const llvm::APSInt &Int, |
1455 | | const llvm::APSInt &Adjustment); |
1456 | | RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, |
1457 | | const llvm::APSInt &Int, |
1458 | | const llvm::APSInt &Adjustment); |
1459 | | RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, |
1460 | | const llvm::APSInt &Int, |
1461 | | const llvm::APSInt &Adjustment); |
1462 | | RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, |
1463 | | const llvm::APSInt &Int, |
1464 | | const llvm::APSInt &Adjustment); |
1465 | | |
1466 | | //===------------------------------------------------------------------===// |
1467 | | // Equality tracking implementation |
1468 | | //===------------------------------------------------------------------===// |
1469 | | |
1470 | | ProgramStateRef trackEQ(RangeSet NewConstraint, ProgramStateRef State, |
1471 | | SymbolRef Sym, const llvm::APSInt &Int, |
1472 | 81.2k | const llvm::APSInt &Adjustment) { |
1473 | 81.2k | return track<true>(NewConstraint, State, Sym, Int, Adjustment); |
1474 | 81.2k | } |
1475 | | |
1476 | | ProgramStateRef trackNE(RangeSet NewConstraint, ProgramStateRef State, |
1477 | | SymbolRef Sym, const llvm::APSInt &Int, |
1478 | 99.2k | const llvm::APSInt &Adjustment) { |
1479 | 99.2k | return track<false>(NewConstraint, State, Sym, Int, Adjustment); |
1480 | 99.2k | } |
1481 | | |
1482 | | template <bool EQ> |
1483 | | ProgramStateRef track(RangeSet NewConstraint, ProgramStateRef State, |
1484 | | SymbolRef Sym, const llvm::APSInt &Int, |
1485 | 180k | const llvm::APSInt &Adjustment) { |
1486 | 180k | if (NewConstraint.isEmpty()) |
1487 | | // This is an infeasible assumption. |
1488 | 54.4k | return nullptr; |
1489 | | |
1490 | 126k | ProgramStateRef NewState = setConstraint(State, Sym, NewConstraint); |
1491 | 126k | if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) { |
1492 | | // If the original assumption is not Sym + Adjustment !=/</> Int, |
1493 | | // we should invert IsEquality flag. |
1494 | 2.14k | Equality->IsEquality = Equality->IsEquality != EQ; |
1495 | 2.14k | return track(NewState, *Equality); |
1496 | 2.14k | } |
1497 | | |
1498 | 123k | return NewState; |
1499 | 126k | } RangeConstraintManager.cpp:llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const> (anonymous namespace)::RangeConstraintManager::track<false>(clang::ento::RangeSet, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, llvm::APSInt const&, llvm::APSInt const&) Line | Count | Source | 1485 | 99.2k | const llvm::APSInt &Adjustment) { | 1486 | 99.2k | if (NewConstraint.isEmpty()) | 1487 | | // This is an infeasible assumption. | 1488 | 10.4k | return nullptr; | 1489 | | | 1490 | 88.7k | ProgramStateRef NewState = setConstraint(State, Sym, NewConstraint); | 1491 | 88.7k | if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) { | 1492 | | // If the original assumption is not Sym + Adjustment !=/</> Int, | 1493 | | // we should invert IsEquality flag. | 1494 | 1.44k | Equality->IsEquality = Equality->IsEquality != EQ; | 1495 | 1.44k | return track(NewState, *Equality); | 1496 | 1.44k | } | 1497 | | | 1498 | 87.3k | return NewState; | 1499 | 88.7k | } |
RangeConstraintManager.cpp:llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const> (anonymous namespace)::RangeConstraintManager::track<true>(clang::ento::RangeSet, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, llvm::APSInt const&, llvm::APSInt const&) Line | Count | Source | 1485 | 81.2k | const llvm::APSInt &Adjustment) { | 1486 | 81.2k | if (NewConstraint.isEmpty()) | 1487 | | // This is an infeasible assumption. | 1488 | 44.0k | return nullptr; | 1489 | | | 1490 | 37.2k | ProgramStateRef NewState = setConstraint(State, Sym, NewConstraint); | 1491 | 37.2k | if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) { | 1492 | | // If the original assumption is not Sym + Adjustment !=/</> Int, | 1493 | | // we should invert IsEquality flag. | 1494 | 695 | Equality->IsEquality = Equality->IsEquality != EQ; | 1495 | 695 | return track(NewState, *Equality); | 1496 | 695 | } | 1497 | | | 1498 | 36.5k | return NewState; | 1499 | 37.2k | } |
|
1500 | | |
1501 | 2.14k | ProgramStateRef track(ProgramStateRef State, EqualityInfo ToTrack) { |
1502 | 2.14k | if (ToTrack.IsEquality) { |
1503 | 718 | return trackEquality(State, ToTrack.Left, ToTrack.Right); |
1504 | 718 | } |
1505 | 1.42k | return trackDisequality(State, ToTrack.Left, ToTrack.Right); |
1506 | 2.14k | } |
1507 | | |
1508 | | ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS, |
1509 | 1.42k | SymbolRef RHS) { |
1510 | 1.42k | return EquivalenceClass::markDisequal(getBasicVals(), F, State, LHS, RHS); |
1511 | 1.42k | } |
1512 | | |
1513 | | ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS, |
1514 | 718 | SymbolRef RHS) { |
1515 | 718 | return EquivalenceClass::merge(getBasicVals(), F, State, LHS, RHS); |
1516 | 718 | } |
1517 | | |
1518 | | LLVM_NODISCARD ProgramStateRef setConstraint(ProgramStateRef State, |
1519 | | EquivalenceClass Class, |
1520 | 138k | RangeSet Constraint) { |
1521 | 138k | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
1522 | 138k | ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>(); |
1523 | | |
1524 | 138k | assert(!Constraint.isEmpty() && "New constraint should not be empty"); |
1525 | | |
1526 | | // Add new constraint. |
1527 | 0 | Constraints = CF.add(Constraints, Class, Constraint); |
1528 | | |
1529 | | // There is a chance that we might need to update constraints for the |
1530 | | // classes that are known to be disequal to Class. |
1531 | | // |
1532 | | // In order for this to be even possible, the new constraint should |
1533 | | // be simply a constant because we can't reason about range disequalities. |
1534 | 138k | if (const llvm::APSInt *Point = Constraint.getConcreteValue()) |
1535 | 40.2k | for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) { |
1536 | 161 | RangeSet UpdatedConstraint = getRange(State, DisequalClass); |
1537 | 161 | UpdatedConstraint = F.deletePoint(UpdatedConstraint, *Point); |
1538 | | |
1539 | | // If we end up with at least one of the disequal classes to be |
1540 | | // constrained with an empty range-set, the state is infeasible. |
1541 | 161 | if (UpdatedConstraint.isEmpty()) |
1542 | 15 | return nullptr; |
1543 | | |
1544 | 146 | Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint); |
1545 | 146 | } |
1546 | | |
1547 | 138k | assert(areFeasible(Constraints) && "Constraint manager shouldn't produce " |
1548 | 138k | "a state with infeasible constraints"); |
1549 | | |
1550 | 0 | return State->set<ConstraintRange>(Constraints); |
1551 | 138k | } |
1552 | | |
1553 | | LLVM_NODISCARD inline ProgramStateRef |
1554 | 138k | setConstraint(ProgramStateRef State, SymbolRef Sym, RangeSet Constraint) { |
1555 | 138k | return setConstraint(State, EquivalenceClass::find(State, Sym), Constraint); |
1556 | 138k | } |
1557 | | }; |
1558 | | |
1559 | | } // end anonymous namespace |
1560 | | |
1561 | | std::unique_ptr<ConstraintManager> |
1562 | | ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, |
1563 | 13.8k | ExprEngine *Eng) { |
1564 | 13.8k | return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder()); |
1565 | 13.8k | } |
1566 | | |
1567 | 0 | ConstraintMap ento::getConstraintMap(ProgramStateRef State) { |
1568 | 0 | ConstraintMap::Factory &F = State->get_context<ConstraintMap>(); |
1569 | 0 | ConstraintMap Result = F.getEmptyMap(); |
1570 | |
|
1571 | 0 | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
1572 | 0 | for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) { |
1573 | 0 | EquivalenceClass Class = ClassConstraint.first; |
1574 | 0 | SymbolSet ClassMembers = Class.getClassMembers(State); |
1575 | 0 | assert(!ClassMembers.isEmpty() && |
1576 | 0 | "Class must always have at least one member!"); |
1577 | | |
1578 | 0 | SymbolRef Representative = *ClassMembers.begin(); |
1579 | 0 | Result = F.add(Result, Representative, ClassConstraint.second); |
1580 | 0 | } |
1581 | |
|
1582 | 0 | return Result; |
1583 | 0 | } |
1584 | | |
1585 | | //===----------------------------------------------------------------------===// |
1586 | | // EqualityClass implementation details |
1587 | | //===----------------------------------------------------------------------===// |
1588 | | |
1589 | | inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State, |
1590 | 710k | SymbolRef Sym) { |
1591 | | // We store far from all Symbol -> Class mappings |
1592 | 710k | if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym)) |
1593 | 7.67k | return *NontrivialClass; |
1594 | | |
1595 | | // This is a trivial class of Sym. |
1596 | 702k | return Sym; |
1597 | 710k | } |
1598 | | |
1599 | | inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV, |
1600 | | RangeSet::Factory &F, |
1601 | | ProgramStateRef State, |
1602 | | SymbolRef First, |
1603 | 718 | SymbolRef Second) { |
1604 | 718 | EquivalenceClass FirstClass = find(State, First); |
1605 | 718 | EquivalenceClass SecondClass = find(State, Second); |
1606 | | |
1607 | 718 | return FirstClass.merge(BV, F, State, SecondClass); |
1608 | 718 | } |
1609 | | |
1610 | | inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV, |
1611 | | RangeSet::Factory &F, |
1612 | | ProgramStateRef State, |
1613 | 718 | EquivalenceClass Other) { |
1614 | | // It is already the same class. |
1615 | 718 | if (*this == Other) |
1616 | 38 | return State; |
1617 | | |
1618 | | // FIXME: As of now, we support only equivalence classes of the same type. |
1619 | | // This limitation is connected to the lack of explicit casts in |
1620 | | // our symbolic expression model. |
1621 | | // |
1622 | | // That means that for `int x` and `char y` we don't distinguish |
1623 | | // between these two very different cases: |
1624 | | // * `x == y` |
1625 | | // * `(char)x == y` |
1626 | | // |
1627 | | // The moment we introduce symbolic casts, this restriction can be |
1628 | | // lifted. |
1629 | 680 | if (getType() != Other.getType()) |
1630 | 149 | return State; |
1631 | | |
1632 | 531 | SymbolSet Members = getClassMembers(State); |
1633 | 531 | SymbolSet OtherMembers = Other.getClassMembers(State); |
1634 | | |
1635 | | // We estimate the size of the class by the height of tree containing |
1636 | | // its members. Merging is not a trivial operation, so it's easier to |
1637 | | // merge the smaller class into the bigger one. |
1638 | 531 | if (Members.getHeight() >= OtherMembers.getHeight()) { |
1639 | 530 | return mergeImpl(BV, F, State, Members, Other, OtherMembers); |
1640 | 530 | } else { |
1641 | 1 | return Other.mergeImpl(BV, F, State, OtherMembers, *this, Members); |
1642 | 1 | } |
1643 | 531 | } |
1644 | | |
1645 | | inline ProgramStateRef |
1646 | | EquivalenceClass::mergeImpl(BasicValueFactory &ValueFactory, |
1647 | | RangeSet::Factory &RangeFactory, |
1648 | | ProgramStateRef State, SymbolSet MyMembers, |
1649 | 531 | EquivalenceClass Other, SymbolSet OtherMembers) { |
1650 | | // Essentially what we try to recreate here is some kind of union-find |
1651 | | // data structure. It does have certain limitations due to persistence |
1652 | | // and the need to remove elements from classes. |
1653 | | // |
1654 | | // In this setting, EquialityClass object is the representative of the class |
1655 | | // or the parent element. ClassMap is a mapping of class members to their |
1656 | | // parent. Unlike the union-find structure, they all point directly to the |
1657 | | // class representative because we don't have an opportunity to actually do |
1658 | | // path compression when dealing with immutability. This means that we |
1659 | | // compress paths every time we do merges. It also means that we lose |
1660 | | // the main amortized complexity benefit from the original data structure. |
1661 | 531 | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
1662 | 531 | ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>(); |
1663 | | |
1664 | | // 1. If the merged classes have any constraints associated with them, we |
1665 | | // need to transfer them to the class we have left. |
1666 | | // |
1667 | | // Intersection here makes perfect sense because both of these constraints |
1668 | | // must hold for the whole new class. |
1669 | 531 | if (Optional<RangeSet> NewClassConstraint = |
1670 | 531 | intersect(ValueFactory, RangeFactory, getConstraint(State, *this), |
1671 | 531 | getConstraint(State, Other))) { |
1672 | | // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because |
1673 | | // range inferrer shouldn't generate ranges incompatible with |
1674 | | // equivalence classes. However, at the moment, due to imperfections |
1675 | | // in the solver, it is possible and the merge function can also |
1676 | | // return infeasible states aka null states. |
1677 | 206 | if (NewClassConstraint->isEmpty()) |
1678 | | // Infeasible state |
1679 | 3 | return nullptr; |
1680 | | |
1681 | | // No need in tracking constraints of a now-dissolved class. |
1682 | 203 | Constraints = CRF.remove(Constraints, Other); |
1683 | | // Assign new constraints for this class. |
1684 | 203 | Constraints = CRF.add(Constraints, *this, *NewClassConstraint); |
1685 | | |
1686 | 203 | assert(areFeasible(Constraints) && "Constraint manager shouldn't produce " |
1687 | 203 | "a state with infeasible constraints"); |
1688 | | |
1689 | 0 | State = State->set<ConstraintRange>(Constraints); |
1690 | 203 | } |
1691 | | |
1692 | | // 2. Get ALL equivalence-related maps |
1693 | 528 | ClassMapTy Classes = State->get<ClassMap>(); |
1694 | 528 | ClassMapTy::Factory &CMF = State->get_context<ClassMap>(); |
1695 | | |
1696 | 528 | ClassMembersTy Members = State->get<ClassMembers>(); |
1697 | 528 | ClassMembersTy::Factory &MF = State->get_context<ClassMembers>(); |
1698 | | |
1699 | 528 | DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>(); |
1700 | 528 | DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>(); |
1701 | | |
1702 | 528 | ClassSet::Factory &CF = State->get_context<ClassSet>(); |
1703 | 528 | SymbolSet::Factory &F = getMembersFactory(State); |
1704 | | |
1705 | | // 2. Merge members of the Other class into the current class. |
1706 | 528 | SymbolSet NewClassMembers = MyMembers; |
1707 | 529 | for (SymbolRef Sym : OtherMembers) { |
1708 | 529 | NewClassMembers = F.add(NewClassMembers, Sym); |
1709 | | // *this is now the class for all these new symbols. |
1710 | 529 | Classes = CMF.add(Classes, Sym, *this); |
1711 | 529 | } |
1712 | | |
1713 | | // 3. Adjust member mapping. |
1714 | | // |
1715 | | // No need in tracking members of a now-dissolved class. |
1716 | 528 | Members = MF.remove(Members, Other); |
1717 | | // Now only the current class is mapped to all the symbols. |
1718 | 528 | Members = MF.add(Members, *this, NewClassMembers); |
1719 | | |
1720 | | // 4. Update disequality relations |
1721 | 528 | ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF); |
1722 | 528 | if (!DisequalToOther.isEmpty()) { |
1723 | 62 | ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF); |
1724 | 62 | DisequalityInfo = DF.remove(DisequalityInfo, Other); |
1725 | | |
1726 | 123 | for (EquivalenceClass DisequalClass : DisequalToOther) { |
1727 | 123 | DisequalToThis = CF.add(DisequalToThis, DisequalClass); |
1728 | | |
1729 | | // Disequality is a symmetric relation meaning that if |
1730 | | // DisequalToOther not null then the set for DisequalClass is not |
1731 | | // empty and has at least Other. |
1732 | 123 | ClassSet OriginalSetLinkedToOther = |
1733 | 123 | *DisequalityInfo.lookup(DisequalClass); |
1734 | | |
1735 | | // Other will be eliminated and we should replace it with the bigger |
1736 | | // united class. |
1737 | 123 | ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other); |
1738 | 123 | NewSet = CF.add(NewSet, *this); |
1739 | | |
1740 | 123 | DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet); |
1741 | 123 | } |
1742 | | |
1743 | 62 | DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis); |
1744 | 62 | State = State->set<DisequalityMap>(DisequalityInfo); |
1745 | 62 | } |
1746 | | |
1747 | | // 5. Update the state |
1748 | 528 | State = State->set<ClassMap>(Classes); |
1749 | 528 | State = State->set<ClassMembers>(Members); |
1750 | | |
1751 | 528 | return State; |
1752 | 531 | } |
1753 | | |
1754 | | inline SymbolSet::Factory & |
1755 | 1.62k | EquivalenceClass::getMembersFactory(ProgramStateRef State) { |
1756 | 1.62k | return State->get_context<SymbolSet>(); |
1757 | 1.62k | } |
1758 | | |
1759 | 1.10k | SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) const { |
1760 | 1.10k | if (const SymbolSet *Members = State->get<ClassMembers>(*this)) |
1761 | 11 | return *Members; |
1762 | | |
1763 | | // This class is trivial, so we need to construct a set |
1764 | | // with just that one symbol from the class. |
1765 | 1.09k | SymbolSet::Factory &F = getMembersFactory(State); |
1766 | 1.09k | return F.add(F.getEmptySet(), getRepresentativeSymbol()); |
1767 | 1.10k | } |
1768 | | |
1769 | 1.87M | bool EquivalenceClass::isTrivial(ProgramStateRef State) const { |
1770 | 1.87M | return State->get<ClassMembers>(*this) == nullptr; |
1771 | 1.87M | } |
1772 | | |
1773 | | bool EquivalenceClass::isTriviallyDead(ProgramStateRef State, |
1774 | 1.87M | SymbolReaper &Reaper) const { |
1775 | 1.87M | return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol())1.86M ; |
1776 | 1.87M | } |
1777 | | |
1778 | | inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF, |
1779 | | RangeSet::Factory &RF, |
1780 | | ProgramStateRef State, |
1781 | | SymbolRef First, |
1782 | 1.42k | SymbolRef Second) { |
1783 | 1.42k | return markDisequal(VF, RF, State, find(State, First), find(State, Second)); |
1784 | 1.42k | } |
1785 | | |
1786 | | inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF, |
1787 | | RangeSet::Factory &RF, |
1788 | | ProgramStateRef State, |
1789 | | EquivalenceClass First, |
1790 | 1.42k | EquivalenceClass Second) { |
1791 | 1.42k | return First.markDisequal(VF, RF, State, Second); |
1792 | 1.42k | } |
1793 | | |
1794 | | inline ProgramStateRef |
1795 | | EquivalenceClass::markDisequal(BasicValueFactory &VF, RangeSet::Factory &RF, |
1796 | | ProgramStateRef State, |
1797 | 1.42k | EquivalenceClass Other) const { |
1798 | | // If we know that two classes are equal, we can only produce an infeasible |
1799 | | // state. |
1800 | 1.42k | if (*this == Other) { |
1801 | 0 | return nullptr; |
1802 | 0 | } |
1803 | | |
1804 | 1.42k | DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>(); |
1805 | 1.42k | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
1806 | | |
1807 | | // Disequality is a symmetric relation, so if we mark A as disequal to B, |
1808 | | // we should also mark B as disequalt to A. |
1809 | 1.42k | if (!addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, *this, |
1810 | 1.42k | Other) || |
1811 | 1.42k | !addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, Other, |
1812 | 1.41k | *this)) |
1813 | 5 | return nullptr; |
1814 | | |
1815 | 1.41k | assert(areFeasible(Constraints) && "Constraint manager shouldn't produce " |
1816 | 1.41k | "a state with infeasible constraints"); |
1817 | | |
1818 | 0 | State = State->set<DisequalityMap>(DisequalityInfo); |
1819 | 1.41k | State = State->set<ConstraintRange>(Constraints); |
1820 | | |
1821 | 1.41k | return State; |
1822 | 1.42k | } |
1823 | | |
1824 | | inline bool EquivalenceClass::addToDisequalityInfo( |
1825 | | DisequalityMapTy &Info, ConstraintRangeTy &Constraints, |
1826 | | BasicValueFactory &VF, RangeSet::Factory &RF, ProgramStateRef State, |
1827 | 2.84k | EquivalenceClass First, EquivalenceClass Second) { |
1828 | | |
1829 | | // 1. Get all of the required factories. |
1830 | 2.84k | DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>(); |
1831 | 2.84k | ClassSet::Factory &CF = State->get_context<ClassSet>(); |
1832 | 2.84k | ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>(); |
1833 | | |
1834 | | // 2. Add Second to the set of classes disequal to First. |
1835 | 2.84k | const ClassSet *CurrentSet = Info.lookup(First); |
1836 | 2.84k | ClassSet NewSet = CurrentSet ? *CurrentSet509 : CF.getEmptySet()2.33k ; |
1837 | 2.84k | NewSet = CF.add(NewSet, Second); |
1838 | | |
1839 | 2.84k | Info = F.add(Info, First, NewSet); |
1840 | | |
1841 | | // 3. If Second is known to be a constant, we can delete this point |
1842 | | // from the constraint asociated with First. |
1843 | | // |
1844 | | // So, if Second == 10, it means that First != 10. |
1845 | | // At the same time, the same logic does not apply to ranges. |
1846 | 2.84k | if (const RangeSet *SecondConstraint = Constraints.lookup(Second)) |
1847 | 1.79k | if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) { |
1848 | | |
1849 | 5 | RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange( |
1850 | 5 | VF, RF, State, First.getRepresentativeSymbol()); |
1851 | | |
1852 | 5 | FirstConstraint = RF.deletePoint(FirstConstraint, *Point); |
1853 | | |
1854 | | // If the First class is about to be constrained with an empty |
1855 | | // range-set, the state is infeasible. |
1856 | 5 | if (FirstConstraint.isEmpty()) |
1857 | 5 | return false; |
1858 | | |
1859 | 0 | Constraints = CRF.add(Constraints, First, FirstConstraint); |
1860 | 0 | } |
1861 | | |
1862 | 2.83k | return true; |
1863 | 2.84k | } |
1864 | | |
1865 | | inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State, |
1866 | | SymbolRef FirstSym, |
1867 | 4.00k | SymbolRef SecondSym) { |
1868 | 4.00k | EquivalenceClass First = find(State, FirstSym); |
1869 | 4.00k | EquivalenceClass Second = find(State, SecondSym); |
1870 | | |
1871 | | // The same equivalence class => symbols are equal. |
1872 | 4.00k | if (First == Second) |
1873 | 244 | return true; |
1874 | | |
1875 | | // Let's check if we know anything about these two classes being not equal to |
1876 | | // each other. |
1877 | 3.76k | ClassSet DisequalToFirst = First.getDisequalClasses(State); |
1878 | 3.76k | if (DisequalToFirst.contains(Second)) |
1879 | 1.15k | return false; |
1880 | | |
1881 | | // It is not clear. |
1882 | 2.60k | return llvm::None; |
1883 | 3.76k | } |
1884 | | |
1885 | | inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State, |
1886 | 0 | SymbolRef Sym) { |
1887 | 0 | return find(State, Sym).getDisequalClasses(State); |
1888 | 0 | } |
1889 | | |
1890 | | inline ClassSet |
1891 | 44.0k | EquivalenceClass::getDisequalClasses(ProgramStateRef State) const { |
1892 | 44.0k | return getDisequalClasses(State->get<DisequalityMap>(), |
1893 | 44.0k | State->get_context<ClassSet>()); |
1894 | 44.0k | } |
1895 | | |
1896 | | inline ClassSet |
1897 | | EquivalenceClass::getDisequalClasses(DisequalityMapTy Map, |
1898 | 97.5k | ClassSet::Factory &Factory) const { |
1899 | 97.5k | if (const ClassSet *DisequalClasses = Map.lookup(*this)) |
1900 | 2.45k | return *DisequalClasses; |
1901 | | |
1902 | 95.0k | return Factory.getEmptySet(); |
1903 | 97.5k | } |
1904 | | |
1905 | 365k | bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) { |
1906 | 365k | ClassMembersTy Members = State->get<ClassMembers>(); |
1907 | | |
1908 | 365k | for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) { |
1909 | 9.83k | for (SymbolRef Member : ClassMembersPair.second) { |
1910 | | // Every member of the class should have a mapping back to the class. |
1911 | 9.83k | if (find(State, Member) == ClassMembersPair.first) { |
1912 | 9.83k | continue; |
1913 | 9.83k | } |
1914 | | |
1915 | 0 | return false; |
1916 | 9.83k | } |
1917 | 8.48k | } |
1918 | | |
1919 | 365k | DisequalityMapTy Disequalities = State->get<DisequalityMap>(); |
1920 | 365k | for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) { |
1921 | 26.5k | EquivalenceClass Class = DisequalityInfo.first; |
1922 | 26.5k | ClassSet DisequalClasses = DisequalityInfo.second; |
1923 | | |
1924 | | // There is no use in keeping empty sets in the map. |
1925 | 26.5k | if (DisequalClasses.isEmpty()) |
1926 | 0 | return false; |
1927 | | |
1928 | | // Disequality is symmetrical, i.e. for every Class A and B that A != B, |
1929 | | // B != A should also be true. |
1930 | 30.7k | for (EquivalenceClass DisequalClass : DisequalClasses)26.5k { |
1931 | 30.7k | const ClassSet *DisequalToDisequalClasses = |
1932 | 30.7k | Disequalities.lookup(DisequalClass); |
1933 | | |
1934 | | // It should be a set of at least one element: Class |
1935 | 30.7k | if (!DisequalToDisequalClasses || |
1936 | 30.7k | !DisequalToDisequalClasses->contains(Class)) |
1937 | 0 | return false; |
1938 | 30.7k | } |
1939 | 26.5k | } |
1940 | | |
1941 | 365k | return true; |
1942 | 365k | } |
1943 | | |
1944 | | //===----------------------------------------------------------------------===// |
1945 | | // RangeConstraintManager implementation |
1946 | | //===----------------------------------------------------------------------===// |
1947 | | |
1948 | 744k | bool RangeConstraintManager::canReasonAbout(SVal X) const { |
1949 | 744k | Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); |
1950 | 744k | if (SymVal && SymVal->isExpression()193k ) { |
1951 | 187k | const SymExpr *SE = SymVal->getSymbol(); |
1952 | | |
1953 | 187k | if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) { |
1954 | 183k | switch (SIE->getOpcode()) { |
1955 | | // We don't reason yet about bitwise-constraints on symbolic values. |
1956 | 33 | case BO_And: |
1957 | 33 | case BO_Or: |
1958 | 33 | case BO_Xor: |
1959 | 33 | return false; |
1960 | | // We don't reason yet about these arithmetic constraints on |
1961 | | // symbolic values. |
1962 | 28 | case BO_Mul: |
1963 | 28 | case BO_Div: |
1964 | 28 | case BO_Rem: |
1965 | 28 | case BO_Shl: |
1966 | 28 | case BO_Shr: |
1967 | 28 | return false; |
1968 | | // All other cases. |
1969 | 183k | default: |
1970 | 183k | return true; |
1971 | 183k | } |
1972 | 183k | } |
1973 | | |
1974 | 3.97k | if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { |
1975 | | // FIXME: Handle <=> here. |
1976 | 3.95k | if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || |
1977 | 3.95k | BinaryOperator::isRelationalOp(SSE->getOpcode())2.58k ) { |
1978 | | // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. |
1979 | | // We've recently started producing Loc <> NonLoc comparisons (that |
1980 | | // result from casts of one of the operands between eg. intptr_t and |
1981 | | // void *), but we can't reason about them yet. |
1982 | 3.91k | if (Loc::isLocType(SSE->getLHS()->getType())) { |
1983 | 924 | return Loc::isLocType(SSE->getRHS()->getType()); |
1984 | 924 | } |
1985 | 3.91k | } |
1986 | 3.95k | } |
1987 | | |
1988 | 3.05k | return false; |
1989 | 3.97k | } |
1990 | | |
1991 | 557k | return true; |
1992 | 744k | } |
1993 | | |
1994 | | ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, |
1995 | 56.5k | SymbolRef Sym) { |
1996 | 56.5k | const RangeSet *Ranges = getConstraint(State, Sym); |
1997 | | |
1998 | | // If we don't have any information about this symbol, it's underconstrained. |
1999 | 56.5k | if (!Ranges) |
2000 | 30.8k | return ConditionTruthVal(); |
2001 | | |
2002 | | // If we have a concrete value, see if it's zero. |
2003 | 25.6k | if (const llvm::APSInt *Value = Ranges->getConcreteValue()) |
2004 | 14.2k | return *Value == 0; |
2005 | | |
2006 | 11.3k | BasicValueFactory &BV = getBasicVals(); |
2007 | 11.3k | APSIntType IntType = BV.getAPSIntType(Sym->getType()); |
2008 | 11.3k | llvm::APSInt Zero = IntType.getZeroValue(); |
2009 | | |
2010 | | // Check if zero is in the set of possible values. |
2011 | 11.3k | if (!Ranges->contains(Zero)) |
2012 | 11.3k | return false; |
2013 | | |
2014 | | // Zero is a possible value, but it is not the /only/ possible value. |
2015 | 4 | return ConditionTruthVal(); |
2016 | 11.3k | } |
2017 | | |
2018 | | const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, |
2019 | 214k | SymbolRef Sym) const { |
2020 | 214k | const RangeSet *T = getConstraint(St, Sym); |
2021 | 214k | return T ? T->getConcreteValue()49.2k : nullptr165k ; |
2022 | 214k | } |
2023 | | |
2024 | | //===----------------------------------------------------------------------===// |
2025 | | // Remove dead symbols from existing constraints |
2026 | | //===----------------------------------------------------------------------===// |
2027 | | |
2028 | | /// Scan all symbols referenced by the constraints. If the symbol is not alive |
2029 | | /// as marked in LSymbols, mark it as dead in DSymbols. |
2030 | | ProgramStateRef |
2031 | | RangeConstraintManager::removeDeadBindings(ProgramStateRef State, |
2032 | 365k | SymbolReaper &SymReaper) { |
2033 | 365k | ClassMembersTy ClassMembersMap = State->get<ClassMembers>(); |
2034 | 365k | ClassMembersTy NewClassMembersMap = ClassMembersMap; |
2035 | 365k | ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>(); |
2036 | 365k | SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>(); |
2037 | | |
2038 | 365k | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
2039 | 365k | ConstraintRangeTy NewConstraints = Constraints; |
2040 | 365k | ConstraintRangeTy::Factory &ConstraintFactory = |
2041 | 365k | State->get_context<ConstraintRange>(); |
2042 | | |
2043 | 365k | ClassMapTy Map = State->get<ClassMap>(); |
2044 | 365k | ClassMapTy NewMap = Map; |
2045 | 365k | ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>(); |
2046 | | |
2047 | 365k | DisequalityMapTy Disequalities = State->get<DisequalityMap>(); |
2048 | 365k | DisequalityMapTy::Factory &DisequalityFactory = |
2049 | 365k | State->get_context<DisequalityMap>(); |
2050 | 365k | ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>(); |
2051 | | |
2052 | 365k | bool ClassMapChanged = false; |
2053 | 365k | bool MembersMapChanged = false; |
2054 | 365k | bool ConstraintMapChanged = false; |
2055 | 365k | bool DisequalitiesChanged = false; |
2056 | | |
2057 | 365k | auto removeDeadClass = [&](EquivalenceClass Class) { |
2058 | | // Remove associated constraint ranges. |
2059 | 52.3k | Constraints = ConstraintFactory.remove(Constraints, Class); |
2060 | 52.3k | ConstraintMapChanged = true; |
2061 | | |
2062 | | // Update disequality information to not hold any information on the |
2063 | | // removed class. |
2064 | 52.3k | ClassSet DisequalClasses = |
2065 | 52.3k | Class.getDisequalClasses(Disequalities, ClassSetFactory); |
2066 | 52.3k | if (!DisequalClasses.isEmpty()) { |
2067 | 475 | for (EquivalenceClass DisequalClass : DisequalClasses) { |
2068 | 475 | ClassSet DisequalToDisequalSet = |
2069 | 475 | DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory); |
2070 | | // DisequalToDisequalSet is guaranteed to be non-empty for consistent |
2071 | | // disequality info. |
2072 | 475 | assert(!DisequalToDisequalSet.isEmpty()); |
2073 | 0 | ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class); |
2074 | | |
2075 | | // No need in keeping an empty set. |
2076 | 475 | if (NewSet.isEmpty()) { |
2077 | 418 | Disequalities = |
2078 | 418 | DisequalityFactory.remove(Disequalities, DisequalClass); |
2079 | 418 | } else { |
2080 | 57 | Disequalities = |
2081 | 57 | DisequalityFactory.add(Disequalities, DisequalClass, NewSet); |
2082 | 57 | } |
2083 | 475 | } |
2084 | | // Remove the data for the class |
2085 | 451 | Disequalities = DisequalityFactory.remove(Disequalities, Class); |
2086 | 451 | DisequalitiesChanged = true; |
2087 | 451 | } |
2088 | 52.3k | }; |
2089 | | |
2090 | | // 1. Let's see if dead symbols are trivial and have associated constraints. |
2091 | 365k | for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair : |
2092 | 1.87M | Constraints) { |
2093 | 1.87M | EquivalenceClass Class = ClassConstraintPair.first; |
2094 | 1.87M | if (Class.isTriviallyDead(State, SymReaper)) { |
2095 | | // If this class is trivial, we can remove its constraints right away. |
2096 | 52.1k | removeDeadClass(Class); |
2097 | 52.1k | } |
2098 | 1.87M | } |
2099 | | |
2100 | | // 2. We don't need to track classes for dead symbols. |
2101 | 365k | for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) { |
2102 | 6.92k | SymbolRef Sym = SymbolClassPair.first; |
2103 | | |
2104 | 6.92k | if (SymReaper.isDead(Sym)) { |
2105 | 255 | ClassMapChanged = true; |
2106 | 255 | NewMap = ClassFactory.remove(NewMap, Sym); |
2107 | 255 | } |
2108 | 6.92k | } |
2109 | | |
2110 | | // 3. Remove dead members from classes and remove dead non-trivial classes |
2111 | | // and their constraints. |
2112 | 365k | for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : |
2113 | 365k | ClassMembersMap) { |
2114 | 8.73k | EquivalenceClass Class = ClassMembersPair.first; |
2115 | 8.73k | SymbolSet LiveMembers = ClassMembersPair.second; |
2116 | 8.73k | bool MembersChanged = false; |
2117 | | |
2118 | 10.4k | for (SymbolRef Member : ClassMembersPair.second) { |
2119 | 10.4k | if (SymReaper.isDead(Member)) { |
2120 | 609 | MembersChanged = true; |
2121 | 609 | LiveMembers = SetFactory.remove(LiveMembers, Member); |
2122 | 609 | } |
2123 | 10.4k | } |
2124 | | |
2125 | | // Check if the class changed. |
2126 | 8.73k | if (!MembersChanged) |
2127 | 8.28k | continue; |
2128 | | |
2129 | 454 | MembersMapChanged = true; |
2130 | | |
2131 | 454 | if (LiveMembers.isEmpty()) { |
2132 | | // The class is dead now, we need to wipe it out of the members map... |
2133 | 253 | NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class); |
2134 | | |
2135 | | // ...and remove all of its constraints. |
2136 | 253 | removeDeadClass(Class); |
2137 | 253 | } else { |
2138 | | // We need to change the members associated with the class. |
2139 | 201 | NewClassMembersMap = |
2140 | 201 | EMFactory.add(NewClassMembersMap, Class, LiveMembers); |
2141 | 201 | } |
2142 | 454 | } |
2143 | | |
2144 | | // 4. Update the state with new maps. |
2145 | | // |
2146 | | // Here we try to be humble and update a map only if it really changed. |
2147 | 365k | if (ClassMapChanged) |
2148 | 248 | State = State->set<ClassMap>(NewMap); |
2149 | | |
2150 | 365k | if (MembersMapChanged) |
2151 | 446 | State = State->set<ClassMembers>(NewClassMembersMap); |
2152 | | |
2153 | 365k | if (ConstraintMapChanged) |
2154 | 29.3k | State = State->set<ConstraintRange>(Constraints); |
2155 | | |
2156 | 365k | if (DisequalitiesChanged) |
2157 | 369 | State = State->set<DisequalityMap>(Disequalities); |
2158 | | |
2159 | 365k | assert(EquivalenceClass::isClassDataConsistent(State)); |
2160 | | |
2161 | 0 | return State; |
2162 | 365k | } |
2163 | | |
2164 | | RangeSet RangeConstraintManager::getRange(ProgramStateRef State, |
2165 | 194k | SymbolRef Sym) { |
2166 | 194k | return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym); |
2167 | 194k | } |
2168 | | |
2169 | | RangeSet RangeConstraintManager::getRange(ProgramStateRef State, |
2170 | 161 | EquivalenceClass Class) { |
2171 | 161 | return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Class); |
2172 | 161 | } |
2173 | | |
2174 | | //===------------------------------------------------------------------------=== |
2175 | | // assumeSymX methods: protected interface for RangeConstraintManager. |
2176 | | //===------------------------------------------------------------------------===/ |
2177 | | |
2178 | | // The syntax for ranges below is mathematical, using [x, y] for closed ranges |
2179 | | // and (x, y) for open ranges. These ranges are modular, corresponding with |
2180 | | // a common treatment of C integer overflow. This means that these methods |
2181 | | // do not have to worry about overflow; RangeSet::Intersect can handle such a |
2182 | | // "wraparound" range. |
2183 | | // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, |
2184 | | // UINT_MAX, 0, 1, and 2. |
2185 | | |
2186 | | ProgramStateRef |
2187 | | RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, |
2188 | | const llvm::APSInt &Int, |
2189 | 84.2k | const llvm::APSInt &Adjustment) { |
2190 | | // Before we do any real work, see if the value can even show up. |
2191 | 84.2k | APSIntType AdjustmentType(Adjustment); |
2192 | 84.2k | if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) |
2193 | 3 | return St; |
2194 | | |
2195 | 84.2k | llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment; |
2196 | | |
2197 | 84.2k | RangeSet New = getRange(St, Sym); |
2198 | 84.2k | New = F.deletePoint(New, Point); |
2199 | | |
2200 | 84.2k | return trackNE(New, St, Sym, Int, Adjustment); |
2201 | 84.2k | } |
2202 | | |
2203 | | ProgramStateRef |
2204 | | RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, |
2205 | | const llvm::APSInt &Int, |
2206 | 81.2k | const llvm::APSInt &Adjustment) { |
2207 | | // Before we do any real work, see if the value can even show up. |
2208 | 81.2k | APSIntType AdjustmentType(Adjustment); |
2209 | 81.2k | if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) |
2210 | 3 | return nullptr; |
2211 | | |
2212 | | // [Int-Adjustment, Int-Adjustment] |
2213 | 81.2k | llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; |
2214 | 81.2k | RangeSet New = getRange(St, Sym); |
2215 | 81.2k | New = F.intersect(New, AdjInt); |
2216 | | |
2217 | 81.2k | return trackEQ(New, St, Sym, Int, Adjustment); |
2218 | 81.2k | } |
2219 | | |
2220 | | RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, |
2221 | | SymbolRef Sym, |
2222 | | const llvm::APSInt &Int, |
2223 | 8.63k | const llvm::APSInt &Adjustment) { |
2224 | | // Before we do any real work, see if the value can even show up. |
2225 | 8.63k | APSIntType AdjustmentType(Adjustment); |
2226 | 8.63k | switch (AdjustmentType.testInRange(Int, true)) { |
2227 | 3 | case APSIntType::RTR_Below: |
2228 | 3 | return F.getEmptySet(); |
2229 | 8.63k | case APSIntType::RTR_Within: |
2230 | 8.63k | break; |
2231 | 2 | case APSIntType::RTR_Above: |
2232 | 2 | return getRange(St, Sym); |
2233 | 8.63k | } |
2234 | | |
2235 | | // Special case for Int == Min. This is always false. |
2236 | 8.63k | llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); |
2237 | 8.63k | llvm::APSInt Min = AdjustmentType.getMinValue(); |
2238 | 8.63k | if (ComparisonVal == Min) |
2239 | 512 | return F.getEmptySet(); |
2240 | | |
2241 | 8.11k | llvm::APSInt Lower = Min - Adjustment; |
2242 | 8.11k | llvm::APSInt Upper = ComparisonVal - Adjustment; |
2243 | 8.11k | --Upper; |
2244 | | |
2245 | 8.11k | RangeSet Result = getRange(St, Sym); |
2246 | 8.11k | return F.intersect(Result, Lower, Upper); |
2247 | 8.63k | } |
2248 | | |
2249 | | ProgramStateRef |
2250 | | RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, |
2251 | | const llvm::APSInt &Int, |
2252 | 7.00k | const llvm::APSInt &Adjustment) { |
2253 | 7.00k | RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); |
2254 | 7.00k | return trackNE(New, St, Sym, Int, Adjustment); |
2255 | 7.00k | } |
2256 | | |
2257 | | RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, |
2258 | | SymbolRef Sym, |
2259 | | const llvm::APSInt &Int, |
2260 | 9.58k | const llvm::APSInt &Adjustment) { |
2261 | | // Before we do any real work, see if the value can even show up. |
2262 | 9.58k | APSIntType AdjustmentType(Adjustment); |
2263 | 9.58k | switch (AdjustmentType.testInRange(Int, true)) { |
2264 | 2 | case APSIntType::RTR_Below: |
2265 | 2 | return getRange(St, Sym); |
2266 | 9.58k | case APSIntType::RTR_Within: |
2267 | 9.58k | break; |
2268 | 2 | case APSIntType::RTR_Above: |
2269 | 2 | return F.getEmptySet(); |
2270 | 9.58k | } |
2271 | | |
2272 | | // Special case for Int == Max. This is always false. |
2273 | 9.58k | llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); |
2274 | 9.58k | llvm::APSInt Max = AdjustmentType.getMaxValue(); |
2275 | 9.58k | if (ComparisonVal == Max) |
2276 | 415 | return F.getEmptySet(); |
2277 | | |
2278 | 9.17k | llvm::APSInt Lower = ComparisonVal - Adjustment; |
2279 | 9.17k | llvm::APSInt Upper = Max - Adjustment; |
2280 | 9.17k | ++Lower; |
2281 | | |
2282 | 9.17k | RangeSet SymRange = getRange(St, Sym); |
2283 | 9.17k | return F.intersect(SymRange, Lower, Upper); |
2284 | 9.58k | } |
2285 | | |
2286 | | ProgramStateRef |
2287 | | RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, |
2288 | | const llvm::APSInt &Int, |
2289 | 7.95k | const llvm::APSInt &Adjustment) { |
2290 | 7.95k | RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); |
2291 | 7.95k | return trackNE(New, St, Sym, Int, Adjustment); |
2292 | 7.95k | } |
2293 | | |
2294 | | RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, |
2295 | | SymbolRef Sym, |
2296 | | const llvm::APSInt &Int, |
2297 | 5.20k | const llvm::APSInt &Adjustment) { |
2298 | | // Before we do any real work, see if the value can even show up. |
2299 | 5.20k | APSIntType AdjustmentType(Adjustment); |
2300 | 5.20k | switch (AdjustmentType.testInRange(Int, true)) { |
2301 | 2 | case APSIntType::RTR_Below: |
2302 | 2 | return getRange(St, Sym); |
2303 | 5.19k | case APSIntType::RTR_Within: |
2304 | 5.19k | break; |
2305 | 2 | case APSIntType::RTR_Above: |
2306 | 2 | return F.getEmptySet(); |
2307 | 5.20k | } |
2308 | | |
2309 | | // Special case for Int == Min. This is always feasible. |
2310 | 5.19k | llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); |
2311 | 5.19k | llvm::APSInt Min = AdjustmentType.getMinValue(); |
2312 | 5.19k | if (ComparisonVal == Min) |
2313 | 56 | return getRange(St, Sym); |
2314 | | |
2315 | 5.14k | llvm::APSInt Max = AdjustmentType.getMaxValue(); |
2316 | 5.14k | llvm::APSInt Lower = ComparisonVal - Adjustment; |
2317 | 5.14k | llvm::APSInt Upper = Max - Adjustment; |
2318 | | |
2319 | 5.14k | RangeSet SymRange = getRange(St, Sym); |
2320 | 5.14k | return F.intersect(SymRange, Lower, Upper); |
2321 | 5.19k | } |
2322 | | |
2323 | | ProgramStateRef |
2324 | | RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, |
2325 | | const llvm::APSInt &Int, |
2326 | 4.70k | const llvm::APSInt &Adjustment) { |
2327 | 4.70k | RangeSet New = getSymGERange(St, Sym, Int, Adjustment); |
2328 | 4.70k | return New.isEmpty() ? nullptr364 : setConstraint(St, Sym, New)4.34k ; |
2329 | 4.70k | } |
2330 | | |
2331 | | RangeSet |
2332 | | RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS, |
2333 | | const llvm::APSInt &Int, |
2334 | 6.87k | const llvm::APSInt &Adjustment) { |
2335 | | // Before we do any real work, see if the value can even show up. |
2336 | 6.87k | APSIntType AdjustmentType(Adjustment); |
2337 | 6.87k | switch (AdjustmentType.testInRange(Int, true)) { |
2338 | 2 | case APSIntType::RTR_Below: |
2339 | 2 | return F.getEmptySet(); |
2340 | 6.86k | case APSIntType::RTR_Within: |
2341 | 6.86k | break; |
2342 | 2 | case APSIntType::RTR_Above: |
2343 | 2 | return RS(); |
2344 | 6.87k | } |
2345 | | |
2346 | | // Special case for Int == Max. This is always feasible. |
2347 | 6.86k | llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); |
2348 | 6.86k | llvm::APSInt Max = AdjustmentType.getMaxValue(); |
2349 | 6.86k | if (ComparisonVal == Max) |
2350 | 22 | return RS(); |
2351 | | |
2352 | 6.84k | llvm::APSInt Min = AdjustmentType.getMinValue(); |
2353 | 6.84k | llvm::APSInt Lower = Min - Adjustment; |
2354 | 6.84k | llvm::APSInt Upper = ComparisonVal - Adjustment; |
2355 | | |
2356 | 6.84k | RangeSet Default = RS(); |
2357 | 6.84k | return F.intersect(Default, Lower, Upper); |
2358 | 6.86k | } |
2359 | | |
2360 | | RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, |
2361 | | SymbolRef Sym, |
2362 | | const llvm::APSInt &Int, |
2363 | 6.46k | const llvm::APSInt &Adjustment) { |
2364 | 6.46k | return getSymLERange([&] { return getRange(St, Sym); }6.45k , Int, Adjustment); |
2365 | 6.46k | } |
2366 | | |
2367 | | ProgramStateRef |
2368 | | RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, |
2369 | | const llvm::APSInt &Int, |
2370 | 6.46k | const llvm::APSInt &Adjustment) { |
2371 | 6.46k | RangeSet New = getSymLERange(St, Sym, Int, Adjustment); |
2372 | 6.46k | return New.isEmpty() ? nullptr275 : setConstraint(St, Sym, New)6.18k ; |
2373 | 6.46k | } |
2374 | | |
2375 | | ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( |
2376 | | ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, |
2377 | 499 | const llvm::APSInt &To, const llvm::APSInt &Adjustment) { |
2378 | 499 | RangeSet New = getSymGERange(State, Sym, From, Adjustment); |
2379 | 499 | if (New.isEmpty()) |
2380 | 87 | return nullptr; |
2381 | 412 | RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); |
2382 | 412 | return Out.isEmpty() ? nullptr52 : setConstraint(State, Sym, Out)360 ; |
2383 | 499 | } |
2384 | | |
2385 | | ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( |
2386 | | ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, |
2387 | 1.63k | const llvm::APSInt &To, const llvm::APSInt &Adjustment) { |
2388 | 1.63k | RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); |
2389 | 1.63k | RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); |
2390 | 1.63k | RangeSet New(F.add(RangeLT, RangeGT)); |
2391 | 1.63k | return New.isEmpty() ? nullptr78 : setConstraint(State, Sym, New)1.55k ; |
2392 | 1.63k | } |
2393 | | |
2394 | | //===----------------------------------------------------------------------===// |
2395 | | // Pretty-printing. |
2396 | | //===----------------------------------------------------------------------===// |
2397 | | |
2398 | | void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, |
2399 | | const char *NL, unsigned int Space, |
2400 | 133 | bool IsDot) const { |
2401 | 133 | ConstraintRangeTy Constraints = State->get<ConstraintRange>(); |
2402 | | |
2403 | 133 | Indent(Out, Space, IsDot) << "\"constraints\": "; |
2404 | 133 | if (Constraints.isEmpty()) { |
2405 | 96 | Out << "null," << NL; |
2406 | 96 | return; |
2407 | 96 | } |
2408 | | |
2409 | 37 | ++Space; |
2410 | 37 | Out << '[' << NL; |
2411 | 37 | bool First = true; |
2412 | 46 | for (std::pair<EquivalenceClass, RangeSet> P : Constraints) { |
2413 | 46 | SymbolSet ClassMembers = P.first.getClassMembers(State); |
2414 | | |
2415 | | // We can print the same constraint for every class member. |
2416 | 46 | for (SymbolRef ClassMember : ClassMembers) { |
2417 | 46 | if (First) { |
2418 | 37 | First = false; |
2419 | 37 | } else { |
2420 | 9 | Out << ','; |
2421 | 9 | Out << NL; |
2422 | 9 | } |
2423 | 46 | Indent(Out, Space, IsDot) |
2424 | 46 | << "{ \"symbol\": \"" << ClassMember << "\", \"range\": \""; |
2425 | 46 | P.second.dump(Out); |
2426 | 46 | Out << "\" }"; |
2427 | 46 | } |
2428 | 46 | } |
2429 | 37 | Out << NL; |
2430 | | |
2431 | 37 | --Space; |
2432 | 37 | Indent(Out, Space, IsDot) << "]," << NL; |
2433 | 37 | } |