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