clang  3.9.0svn
RangeConstraintManager.cpp
Go to the documentation of this file.
1 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines RangeConstraintManager, a class that tracks simple
11 // equality and inequality constraints on symbolic values of ProgramState.
12 //
13 //===----------------------------------------------------------------------===//
14 
19 #include "llvm/ADT/FoldingSet.h"
20 #include "llvm/ADT/ImmutableSet.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 /// A Range represents the closed range [from, to]. The caller must
28 /// guarantee that from <= to. Note that Range is immutable, so as not
29 /// to subvert RangeSet's immutability.
30 namespace {
31 class Range : public std::pair<const llvm::APSInt*,
32  const llvm::APSInt*> {
33 public:
34  Range(const llvm::APSInt &from, const llvm::APSInt &to)
35  : std::pair<const llvm::APSInt*, const llvm::APSInt*>(&from, &to) {
36  assert(from <= to);
37  }
38  bool Includes(const llvm::APSInt &v) const {
39  return *first <= v && v <= *second;
40  }
41  const llvm::APSInt &From() const {
42  return *first;
43  }
44  const llvm::APSInt &To() const {
45  return *second;
46  }
47  const llvm::APSInt *getConcreteValue() const {
48  return &From() == &To() ? &From() : nullptr;
49  }
50 
51  void Profile(llvm::FoldingSetNodeID &ID) const {
52  ID.AddPointer(&From());
53  ID.AddPointer(&To());
54  }
55 };
56 
57 
58 class RangeTrait : public llvm::ImutContainerInfo<Range> {
59 public:
60  // When comparing if one Range is less than another, we should compare
61  // the actual APSInt values instead of their pointers. This keeps the order
62  // consistent (instead of comparing by pointer values) and can potentially
63  // be used to speed up some of the operations in RangeSet.
64  static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
65  return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) &&
66  *lhs.second < *rhs.second);
67  }
68 };
69 
70 /// RangeSet contains a set of ranges. If the set is empty, then
71 /// there the value of a symbol is overly constrained and there are no
72 /// possible values for that symbol.
73 class RangeSet {
74  typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
75  PrimRangeSet ranges; // no need to make const, since it is an
76  // ImmutableSet - this allows default operator=
77  // to work.
78 public:
79  typedef PrimRangeSet::Factory Factory;
80  typedef PrimRangeSet::iterator iterator;
81 
82  RangeSet(PrimRangeSet RS) : ranges(RS) {}
83 
84  /// Create a new set with all ranges of this set and RS.
85  /// Possible intersections are not checked here.
86  RangeSet addRange(Factory &F, const RangeSet &RS) {
87  PrimRangeSet Ranges(RS.ranges);
88  for (const auto &range : ranges)
89  Ranges = F.add(Ranges, range);
90  return RangeSet(Ranges);
91  }
92 
93  iterator begin() const { return ranges.begin(); }
94  iterator end() const { return ranges.end(); }
95 
96  bool isEmpty() const { return ranges.isEmpty(); }
97 
98  /// Construct a new RangeSet representing '{ [from, to] }'.
99  RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
100  : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
101 
102  /// Profile - Generates a hash profile of this RangeSet for use
103  /// by FoldingSet.
104  void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
105 
106  /// getConcreteValue - If a symbol is contrained to equal a specific integer
107  /// constant then this method returns that value. Otherwise, it returns
108  /// NULL.
109  const llvm::APSInt* getConcreteValue() const {
110  return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
111  }
112 
113 private:
114  void IntersectInRange(BasicValueFactory &BV, Factory &F,
115  const llvm::APSInt &Lower,
116  const llvm::APSInt &Upper,
117  PrimRangeSet &newRanges,
118  PrimRangeSet::iterator &i,
119  PrimRangeSet::iterator &e) const {
120  // There are six cases for each range R in the set:
121  // 1. R is entirely before the intersection range.
122  // 2. R is entirely after the intersection range.
123  // 3. R contains the entire intersection range.
124  // 4. R starts before the intersection range and ends in the middle.
125  // 5. R starts in the middle of the intersection range and ends after it.
126  // 6. R is entirely contained in the intersection range.
127  // These correspond to each of the conditions below.
128  for (/* i = begin(), e = end() */; i != e; ++i) {
129  if (i->To() < Lower) {
130  continue;
131  }
132  if (i->From() > Upper) {
133  break;
134  }
135 
136  if (i->Includes(Lower)) {
137  if (i->Includes(Upper)) {
138  newRanges = F.add(newRanges, Range(BV.getValue(Lower),
139  BV.getValue(Upper)));
140  break;
141  } else
142  newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
143  } else {
144  if (i->Includes(Upper)) {
145  newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
146  break;
147  } else
148  newRanges = F.add(newRanges, *i);
149  }
150  }
151  }
152 
153  const llvm::APSInt &getMinValue() const {
154  assert(!isEmpty());
155  return ranges.begin()->From();
156  }
157 
158  bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
159  // This function has nine cases, the cartesian product of range-testing
160  // both the upper and lower bounds against the symbol's type.
161  // Each case requires a different pinning operation.
162  // The function returns false if the described range is entirely outside
163  // the range of values for the associated symbol.
164  APSIntType Type(getMinValue());
165  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
166  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
167 
168  switch (LowerTest) {
170  switch (UpperTest) {
172  // The entire range is outside the symbol's set of possible values.
173  // If this is a conventionally-ordered range, the state is infeasible.
174  if (Lower <= Upper)
175  return false;
176 
177  // However, if the range wraps around, it spans all possible values.
178  Lower = Type.getMinValue();
179  Upper = Type.getMaxValue();
180  break;
182  // The range starts below what's possible but ends within it. Pin.
183  Lower = Type.getMinValue();
184  Type.apply(Upper);
185  break;
187  // The range spans all possible values for the symbol. Pin.
188  Lower = Type.getMinValue();
189  Upper = Type.getMaxValue();
190  break;
191  }
192  break;
194  switch (UpperTest) {
196  // The range wraps around, but all lower values are not possible.
197  Type.apply(Lower);
198  Upper = Type.getMaxValue();
199  break;
201  // The range may or may not wrap around, but both limits are valid.
202  Type.apply(Lower);
203  Type.apply(Upper);
204  break;
206  // The range starts within what's possible but ends above it. Pin.
207  Type.apply(Lower);
208  Upper = Type.getMaxValue();
209  break;
210  }
211  break;
213  switch (UpperTest) {
215  // The range wraps but is outside the symbol's set of possible values.
216  return false;
218  // The range starts above what's possible but ends within it (wrap).
219  Lower = Type.getMinValue();
220  Type.apply(Upper);
221  break;
223  // The entire range is outside the symbol's set of possible values.
224  // If this is a conventionally-ordered range, the state is infeasible.
225  if (Lower <= Upper)
226  return false;
227 
228  // However, if the range wraps around, it spans all possible values.
229  Lower = Type.getMinValue();
230  Upper = Type.getMaxValue();
231  break;
232  }
233  break;
234  }
235 
236  return true;
237  }
238 
239 public:
240  // Returns a set containing the values in the receiving set, intersected with
241  // the closed range [Lower, Upper]. Unlike the Range type, this range uses
242  // modular arithmetic, corresponding to the common treatment of C integer
243  // overflow. Thus, if the Lower bound is greater than the Upper bound, the
244  // range is taken to wrap around. This is equivalent to taking the
245  // intersection with the two ranges [Min, Upper] and [Lower, Max],
246  // or, alternatively, /removing/ all integers between Upper and Lower.
247  RangeSet Intersect(BasicValueFactory &BV, Factory &F,
248  llvm::APSInt Lower, llvm::APSInt Upper) const {
249  if (!pin(Lower, Upper))
250  return F.getEmptySet();
251 
252  PrimRangeSet newRanges = F.getEmptySet();
253 
254  PrimRangeSet::iterator i = begin(), e = end();
255  if (Lower <= Upper)
256  IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
257  else {
258  // The order of the next two statements is important!
259  // IntersectInRange() does not reset the iteration state for i and e.
260  // Therefore, the lower range most be handled first.
261  IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
262  IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
263  }
264 
265  return newRanges;
266  }
267 
268  void print(raw_ostream &os) const {
269  bool isFirst = true;
270  os << "{ ";
271  for (iterator i = begin(), e = end(); i != e; ++i) {
272  if (isFirst)
273  isFirst = false;
274  else
275  os << ", ";
276 
277  os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
278  << ']';
279  }
280  os << " }";
281  }
282 
283  bool operator==(const RangeSet &other) const {
284  return ranges == other.ranges;
285  }
286 };
287 } // end anonymous namespace
288 
291  RangeSet))
292 
293 namespace {
294 class RangeConstraintManager : public SimpleConstraintManager{
295  RangeSet GetRange(ProgramStateRef state, SymbolRef sym);
296 public:
297  RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB)
298  : SimpleConstraintManager(subengine, SVB) {}
299 
300  ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym,
301  const llvm::APSInt& Int,
302  const llvm::APSInt& Adjustment) override;
303 
304  ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym,
305  const llvm::APSInt& Int,
306  const llvm::APSInt& Adjustment) override;
307 
308  ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym,
309  const llvm::APSInt& Int,
310  const llvm::APSInt& Adjustment) override;
311 
312  ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym,
313  const llvm::APSInt& Int,
314  const llvm::APSInt& Adjustment) override;
315 
316  ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym,
317  const llvm::APSInt& Int,
318  const llvm::APSInt& Adjustment) override;
319 
320  ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym,
321  const llvm::APSInt& Int,
322  const llvm::APSInt& Adjustment) override;
323 
324  ProgramStateRef assumeSymbolWithinInclusiveRange(
325  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
326  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
327 
328  ProgramStateRef assumeSymbolOutOfInclusiveRange(
329  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
330  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
331 
332  const llvm::APSInt* getSymVal(ProgramStateRef St,
333  SymbolRef sym) const override;
334  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
335 
336  ProgramStateRef removeDeadBindings(ProgramStateRef St,
337  SymbolReaper& SymReaper) override;
338 
339  void print(ProgramStateRef St, raw_ostream &Out,
340  const char* nl, const char *sep) override;
341 
342 private:
343  RangeSet::Factory F;
344  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
345  const llvm::APSInt &Int,
346  const llvm::APSInt &Adjustment);
347  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
348  const llvm::APSInt &Int,
349  const llvm::APSInt &Adjustment);
350  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
351  const llvm::APSInt &Int,
352  const llvm::APSInt &Adjustment);
353  RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int,
354  const llvm::APSInt &Adjustment);
355  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
356  const llvm::APSInt &Int,
357  const llvm::APSInt &Adjustment);
358 };
359 
360 } // end anonymous namespace
361 
362 std::unique_ptr<ConstraintManager>
364  return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
365 }
366 
367 const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St,
368  SymbolRef sym) const {
369  const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(sym);
370  return T ? T->getConcreteValue() : nullptr;
371 }
372 
373 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
374  SymbolRef Sym) {
375  const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
376 
377  // If we don't have any information about this symbol, it's underconstrained.
378  if (!Ranges)
379  return ConditionTruthVal();
380 
381  // If we have a concrete value, see if it's zero.
382  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
383  return *Value == 0;
384 
385  BasicValueFactory &BV = getBasicVals();
386  APSIntType IntType = BV.getAPSIntType(Sym->getType());
387  llvm::APSInt Zero = IntType.getZeroValue();
388 
389  // Check if zero is in the set of possible values.
390  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
391  return false;
392 
393  // Zero is a possible value, but it is not the /only/ possible value.
394  return ConditionTruthVal();
395 }
396 
397 /// Scan all symbols referenced by the constraints. If the symbol is not alive
398 /// as marked in LSymbols, mark it as dead in DSymbols.
400 RangeConstraintManager::removeDeadBindings(ProgramStateRef state,
401  SymbolReaper& SymReaper) {
402 
403  ConstraintRangeTy CR = state->get<ConstraintRange>();
404  ConstraintRangeTy::Factory& CRFactory = state->get_context<ConstraintRange>();
405 
406  for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
407  SymbolRef sym = I.getKey();
408  if (SymReaper.maybeDead(sym))
409  CR = CRFactory.remove(CR, sym);
410  }
411 
412  return state->set<ConstraintRange>(CR);
413 }
414 
415 RangeSet
416 RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) {
417  if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym))
418  return *V;
419 
420  // Lazily generate a new RangeSet representing all possible values for the
421  // given symbol type.
422  BasicValueFactory &BV = getBasicVals();
423  QualType T = sym->getType();
424 
425  RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
426 
427  // Special case: references are known to be non-zero.
428  if (T->isReferenceType()) {
429  APSIntType IntType = BV.getAPSIntType(T);
430  Result = Result.Intersect(BV, F, ++IntType.getZeroValue(),
431  --IntType.getZeroValue());
432  }
433 
434  return Result;
435 }
436 
437 //===------------------------------------------------------------------------===
438 // assumeSymX methods: public interface for RangeConstraintManager.
439 //===------------------------------------------------------------------------===/
440 
441 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
442 // and (x, y) for open ranges. These ranges are modular, corresponding with
443 // a common treatment of C integer overflow. This means that these methods
444 // do not have to worry about overflow; RangeSet::Intersect can handle such a
445 // "wraparound" range.
446 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
447 // UINT_MAX, 0, 1, and 2.
448 
450 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
451  const llvm::APSInt &Int,
452  const llvm::APSInt &Adjustment) {
453  // Before we do any real work, see if the value can even show up.
454  APSIntType AdjustmentType(Adjustment);
455  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
456  return St;
457 
458  llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
459  llvm::APSInt Upper = Lower;
460  --Lower;
461  ++Upper;
462 
463  // [Int-Adjustment+1, Int-Adjustment-1]
464  // Notice that the lower bound is greater than the upper bound.
465  RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
466  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
467 }
468 
470 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
471  const llvm::APSInt &Int,
472  const llvm::APSInt &Adjustment) {
473  // Before we do any real work, see if the value can even show up.
474  APSIntType AdjustmentType(Adjustment);
475  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
476  return nullptr;
477 
478  // [Int-Adjustment, Int-Adjustment]
479  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
480  RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
481  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
482 }
483 
484 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
485  SymbolRef Sym,
486  const llvm::APSInt &Int,
487  const llvm::APSInt &Adjustment) {
488  // Before we do any real work, see if the value can even show up.
489  APSIntType AdjustmentType(Adjustment);
490  switch (AdjustmentType.testInRange(Int, true)) {
492  return F.getEmptySet();
494  break;
496  return GetRange(St, Sym);
497  }
498 
499  // Special case for Int == Min. This is always false.
500  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
501  llvm::APSInt Min = AdjustmentType.getMinValue();
502  if (ComparisonVal == Min)
503  return F.getEmptySet();
504 
505  llvm::APSInt Lower = Min - Adjustment;
506  llvm::APSInt Upper = ComparisonVal - Adjustment;
507  --Upper;
508 
509  return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
510 }
511 
513 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
514  const llvm::APSInt &Int,
515  const llvm::APSInt &Adjustment) {
516  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
517  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
518 }
519 
520 RangeSet
521 RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym,
522  const llvm::APSInt &Int,
523  const llvm::APSInt &Adjustment) {
524  // Before we do any real work, see if the value can even show up.
525  APSIntType AdjustmentType(Adjustment);
526  switch (AdjustmentType.testInRange(Int, true)) {
528  return GetRange(St, Sym);
530  break;
532  return F.getEmptySet();
533  }
534 
535  // Special case for Int == Max. This is always false.
536  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
537  llvm::APSInt Max = AdjustmentType.getMaxValue();
538  if (ComparisonVal == Max)
539  return F.getEmptySet();
540 
541  llvm::APSInt Lower = ComparisonVal - Adjustment;
542  llvm::APSInt Upper = Max - Adjustment;
543  ++Lower;
544 
545  return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
546 }
547 
549 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
550  const llvm::APSInt &Int,
551  const llvm::APSInt &Adjustment) {
552  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
553  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
554 }
555 
556 RangeSet
557 RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym,
558  const llvm::APSInt &Int,
559  const llvm::APSInt &Adjustment) {
560  // Before we do any real work, see if the value can even show up.
561  APSIntType AdjustmentType(Adjustment);
562  switch (AdjustmentType.testInRange(Int, true)) {
564  return GetRange(St, Sym);
566  break;
568  return F.getEmptySet();
569  }
570 
571  // Special case for Int == Min. This is always feasible.
572  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
573  llvm::APSInt Min = AdjustmentType.getMinValue();
574  if (ComparisonVal == Min)
575  return GetRange(St, Sym);
576 
577  llvm::APSInt Max = AdjustmentType.getMaxValue();
578  llvm::APSInt Lower = ComparisonVal - Adjustment;
579  llvm::APSInt Upper = Max - Adjustment;
580 
581  return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
582 }
583 
585 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
586  const llvm::APSInt &Int,
587  const llvm::APSInt &Adjustment) {
588  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
589  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
590 }
591 
592 RangeSet
593 RangeConstraintManager::getSymLERange(const RangeSet &RS,
594  const llvm::APSInt &Int,
595  const llvm::APSInt &Adjustment) {
596  // Before we do any real work, see if the value can even show up.
597  APSIntType AdjustmentType(Adjustment);
598  switch (AdjustmentType.testInRange(Int, true)) {
600  return F.getEmptySet();
602  break;
604  return RS;
605  }
606 
607  // Special case for Int == Max. This is always feasible.
608  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
609  llvm::APSInt Max = AdjustmentType.getMaxValue();
610  if (ComparisonVal == Max)
611  return RS;
612 
613  llvm::APSInt Min = AdjustmentType.getMinValue();
614  llvm::APSInt Lower = Min - Adjustment;
615  llvm::APSInt Upper = ComparisonVal - Adjustment;
616 
617  return RS.Intersect(getBasicVals(), F, Lower, Upper);
618 }
619 
620 RangeSet
621 RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym,
622  const llvm::APSInt &Int,
623  const llvm::APSInt &Adjustment) {
624  // Before we do any real work, see if the value can even show up.
625  APSIntType AdjustmentType(Adjustment);
626  switch (AdjustmentType.testInRange(Int, true)) {
628  return F.getEmptySet();
630  break;
632  return GetRange(St, Sym);
633  }
634 
635  // Special case for Int == Max. This is always feasible.
636  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
637  llvm::APSInt Max = AdjustmentType.getMaxValue();
638  if (ComparisonVal == Max)
639  return GetRange(St, Sym);
640 
641  llvm::APSInt Min = AdjustmentType.getMinValue();
642  llvm::APSInt Lower = Min - Adjustment;
643  llvm::APSInt Upper = ComparisonVal - Adjustment;
644 
645  return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
646 }
647 
649 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
650  const llvm::APSInt &Int,
651  const llvm::APSInt &Adjustment) {
652  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
653  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
654 }
655 
657 RangeConstraintManager::assumeSymbolWithinInclusiveRange(
658  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
659  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
660  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
661  if (New.isEmpty())
662  return nullptr;
663  New = getSymLERange(New, To, Adjustment);
664  return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
665 }
666 
668 RangeConstraintManager::assumeSymbolOutOfInclusiveRange(
669  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
670  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
671  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
672  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
673  RangeSet New(RangeLT.addRange(F, RangeGT));
674  return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
675 }
676 
677 //===------------------------------------------------------------------------===
678 // Pretty-printing.
679 //===------------------------------------------------------------------------===/
680 
681 void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out,
682  const char* nl, const char *sep) {
683 
684  ConstraintRangeTy Ranges = St->get<ConstraintRange>();
685 
686  if (Ranges.isEmpty()) {
687  Out << nl << sep << "Ranges are empty." << nl;
688  return;
689  }
690 
691  Out << nl << sep << "Ranges of symbol values:";
692  for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){
693  Out << nl << ' ' << I.getKey() << " : ";
694  I.getData().print(Out);
695  }
696  Out << nl;
697 }
A (possibly-)qualified type.
Definition: Type.h:598
Value is less than the minimum representable value.
Definition: APSIntType.h:78
bool operator==(CanQual< T > x, CanQual< U > y)
REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, RangeSet)) namespace
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
bool maybeDead(SymbolRef sym)
If a symbol is known to be live, marks the symbol as live.
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, SubEngine *subengine)
The base class of the type hierarchy.
Definition: Type.h:1281
Symbolic value.
Definition: SymExpr.h:27
LineState State
bool isReferenceType() const
Definition: Type.h:5484
Definition: Format.h:880
Value is representable using this type.
Definition: APSIntType.h:79
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:20
RangeTestResultKind testInRange(const llvm::APSInt &Val, bool AllowMixedSign) const LLVM_READONLY
Tests whether a given value is losslessly representable using this type.
Definition: APSIntType.cpp:16
llvm::APSInt getZeroValue() const LLVM_READONLY
Returns an all-zero value for this type.
Definition: APSIntType.h:56
ID
Defines the set of possible language-specific address spaces.
Definition: AddressSpaces.h:27
llvm::APSInt getMinValue() const LLVM_READONLY
Returns the minimum value for this type.
Definition: APSIntType.h:61
The result type of a method or function.
do v
Definition: arm_acle.h:78
and static some checkers Checker The latter are built on top of the former via the Checker and CheckerVisitor and attempts to isolate them from much of the gore of the internal analysis the analyzer is basically a source code simulator that traces out possible paths of execution The state of the and the combination of state and program point is a node in an exploded which has the entry program point and initial state
llvm::APSInt getMaxValue() const LLVM_READONLY
Returns the maximum value for this type.
Definition: APSIntType.h:66
#define CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value)
Helper for registering a map trait.
A class responsible for cleaning up unused symbols.
Value is greater than the maximum representable value.
Definition: APSIntType.h:80
RangeTestResultKind
Used to classify whether a value is representable using this type.
Definition: APSIntType.h:77
llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY
Convert and return a new APSInt with the given value, but this type&#39;s bit width and signedness...
Definition: APSIntType.h:49
Dataflow Directional Tag Classes.
virtual QualType getType() const =0
const llvm::APSInt & getMinValue(const llvm::APSInt &v)
const llvm::APSInt & getMaxValue(const llvm::APSInt &v)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.