clang  9.0.0svn
RangeConstraintManager.cpp
Go to the documentation of this file.
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 
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 void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
27  const llvm::APSInt &Lower, const llvm::APSInt &Upper,
28  PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
29  PrimRangeSet::iterator &e) const {
30  // There are six cases for each range R in the set:
31  // 1. R is entirely before the intersection range.
32  // 2. R is entirely after the intersection range.
33  // 3. R contains the entire intersection range.
34  // 4. R starts before the intersection range and ends in the middle.
35  // 5. R starts in the middle of the intersection range and ends after it.
36  // 6. R is entirely contained in the intersection range.
37  // These correspond to each of the conditions below.
38  for (/* i = begin(), e = end() */; i != e; ++i) {
39  if (i->To() < Lower) {
40  continue;
41  }
42  if (i->From() > Upper) {
43  break;
44  }
45 
46  if (i->Includes(Lower)) {
47  if (i->Includes(Upper)) {
48  newRanges =
49  F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
50  break;
51  } else
52  newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
53  } else {
54  if (i->Includes(Upper)) {
55  newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
56  break;
57  } else
58  newRanges = F.add(newRanges, *i);
59  }
60  }
61 }
62 
63 const llvm::APSInt &RangeSet::getMinValue() const {
64  assert(!isEmpty());
65  return ranges.begin()->From();
66 }
67 
68 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
69  // This function has nine cases, the cartesian product of range-testing
70  // both the upper and lower bounds against the symbol's type.
71  // Each case requires a different pinning operation.
72  // The function returns false if the described range is entirely outside
73  // the range of values for the associated symbol.
74  APSIntType Type(getMinValue());
75  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
76  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
77 
78  switch (LowerTest) {
80  switch (UpperTest) {
82  // The entire range is outside the symbol's set of possible values.
83  // If this is a conventionally-ordered range, the state is infeasible.
84  if (Lower <= Upper)
85  return false;
86 
87  // However, if the range wraps around, it spans all possible values.
88  Lower = Type.getMinValue();
89  Upper = Type.getMaxValue();
90  break;
92  // The range starts below what's possible but ends within it. Pin.
93  Lower = Type.getMinValue();
94  Type.apply(Upper);
95  break;
97  // The range spans all possible values for the symbol. Pin.
98  Lower = Type.getMinValue();
99  Upper = Type.getMaxValue();
100  break;
101  }
102  break;
104  switch (UpperTest) {
106  // The range wraps around, but all lower values are not possible.
107  Type.apply(Lower);
108  Upper = Type.getMaxValue();
109  break;
111  // The range may or may not wrap around, but both limits are valid.
112  Type.apply(Lower);
113  Type.apply(Upper);
114  break;
116  // The range starts within what's possible but ends above it. Pin.
117  Type.apply(Lower);
118  Upper = Type.getMaxValue();
119  break;
120  }
121  break;
123  switch (UpperTest) {
125  // The range wraps but is outside the symbol's set of possible values.
126  return false;
128  // The range starts above what's possible but ends within it (wrap).
129  Lower = Type.getMinValue();
130  Type.apply(Upper);
131  break;
133  // The entire range is outside the symbol's set of possible values.
134  // If this is a conventionally-ordered range, the state is infeasible.
135  if (Lower <= Upper)
136  return false;
137 
138  // However, if the range wraps around, it spans all possible values.
139  Lower = Type.getMinValue();
140  Upper = Type.getMaxValue();
141  break;
142  }
143  break;
144  }
145 
146  return true;
147 }
148 
149 // Returns a set containing the values in the receiving set, intersected with
150 // the closed range [Lower, Upper]. Unlike the Range type, this range uses
151 // modular arithmetic, corresponding to the common treatment of C integer
152 // overflow. Thus, if the Lower bound is greater than the Upper bound, the
153 // range is taken to wrap around. This is equivalent to taking the
154 // intersection with the two ranges [Min, Upper] and [Lower, Max],
155 // or, alternatively, /removing/ all integers between Upper and Lower.
157  llvm::APSInt Lower, llvm::APSInt Upper) const {
158  if (!pin(Lower, Upper))
159  return F.getEmptySet();
160 
161  PrimRangeSet newRanges = F.getEmptySet();
162 
163  PrimRangeSet::iterator i = begin(), e = end();
164  if (Lower <= Upper)
165  IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
166  else {
167  // The order of the next two statements is important!
168  // IntersectInRange() does not reset the iteration state for i and e.
169  // Therefore, the lower range most be handled first.
170  IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
171  IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
172  }
173 
174  return newRanges;
175 }
176 
177 // Returns a set containing the values in the receiving set, intersected with
178 // the range set passed as parameter.
180  const RangeSet &Other) const {
181  PrimRangeSet newRanges = F.getEmptySet();
182 
183  for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
184  RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
185  for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
186  newRanges = F.add(newRanges, *j);
187  }
188  }
189 
190  return newRanges;
191 }
192 
193 // Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
194 // [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
195 // signed values of the type.
197  PrimRangeSet newRanges = F.getEmptySet();
198 
199  for (iterator i = begin(), e = end(); i != e; ++i) {
200  const llvm::APSInt &from = i->From(), &to = i->To();
201  const llvm::APSInt &newTo = (from.isMinSignedValue() ?
202  BV.getMaxValue(from) :
203  BV.getValue(- from));
204  if (to.isMaxSignedValue() && !newRanges.isEmpty() &&
205  newRanges.begin()->From().isMinSignedValue()) {
206  assert(newRanges.begin()->To().isMinSignedValue() &&
207  "Ranges should not overlap");
208  assert(!from.isMinSignedValue() && "Ranges should not overlap");
209  const llvm::APSInt &newFrom = newRanges.begin()->From();
210  newRanges =
211  F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
212  } else if (!to.isMinSignedValue()) {
213  const llvm::APSInt &newFrom = BV.getValue(- to);
214  newRanges = F.add(newRanges, Range(newFrom, newTo));
215  }
216  if (from.isMinSignedValue()) {
217  newRanges = F.add(newRanges, Range(BV.getMinValue(from),
218  BV.getMinValue(from)));
219  }
220  }
221 
222  return newRanges;
223 }
224 
225 void RangeSet::print(raw_ostream &os) const {
226  bool isFirst = true;
227  os << "{ ";
228  for (iterator i = begin(), e = end(); i != e; ++i) {
229  if (isFirst)
230  isFirst = false;
231  else
232  os << ", ";
233 
234  os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
235  << ']';
236  }
237  os << " }";
238 }
239 
240 namespace {
241 class RangeConstraintManager : public RangedConstraintManager {
242 public:
243  RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
244  : RangedConstraintManager(SE, SVB) {}
245 
246  //===------------------------------------------------------------------===//
247  // Implementation for interface from ConstraintManager.
248  //===------------------------------------------------------------------===//
249 
250  bool haveEqualConstraints(ProgramStateRef S1,
251  ProgramStateRef S2) const override {
252  return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
253  }
254 
255  bool canReasonAbout(SVal X) const override;
256 
257  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
258 
259  const llvm::APSInt *getSymVal(ProgramStateRef State,
260  SymbolRef Sym) const override;
261 
262  ProgramStateRef removeDeadBindings(ProgramStateRef State,
263  SymbolReaper &SymReaper) override;
264 
265  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
266  unsigned int Space = 0, bool IsDot = false) const override;
267 
268  //===------------------------------------------------------------------===//
269  // Implementation for interface from RangedConstraintManager.
270  //===------------------------------------------------------------------===//
271 
272  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
273  const llvm::APSInt &V,
274  const llvm::APSInt &Adjustment) override;
275 
276  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
277  const llvm::APSInt &V,
278  const llvm::APSInt &Adjustment) override;
279 
280  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
281  const llvm::APSInt &V,
282  const llvm::APSInt &Adjustment) override;
283 
284  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
285  const llvm::APSInt &V,
286  const llvm::APSInt &Adjustment) override;
287 
288  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
289  const llvm::APSInt &V,
290  const llvm::APSInt &Adjustment) override;
291 
292  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
293  const llvm::APSInt &V,
294  const llvm::APSInt &Adjustment) override;
295 
296  ProgramStateRef assumeSymWithinInclusiveRange(
297  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
298  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
299 
300  ProgramStateRef assumeSymOutsideInclusiveRange(
301  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
302  const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
303 
304 private:
306 
307  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
308  const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
309  SymbolRef Sym);
310 
311  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
312  const llvm::APSInt &Int,
313  const llvm::APSInt &Adjustment);
314  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
315  const llvm::APSInt &Int,
316  const llvm::APSInt &Adjustment);
317  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
318  const llvm::APSInt &Int,
319  const llvm::APSInt &Adjustment);
320  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
321  const llvm::APSInt &Int,
322  const llvm::APSInt &Adjustment);
323  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
324  const llvm::APSInt &Int,
325  const llvm::APSInt &Adjustment);
326 
327 };
328 
329 } // end anonymous namespace
330 
331 std::unique_ptr<ConstraintManager>
333  return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
334 }
335 
336 bool RangeConstraintManager::canReasonAbout(SVal X) const {
338  if (SymVal && SymVal->isExpression()) {
339  const SymExpr *SE = SymVal->getSymbol();
340 
341  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
342  switch (SIE->getOpcode()) {
343  // We don't reason yet about bitwise-constraints on symbolic values.
344  case BO_And:
345  case BO_Or:
346  case BO_Xor:
347  return false;
348  // We don't reason yet about these arithmetic constraints on
349  // symbolic values.
350  case BO_Mul:
351  case BO_Div:
352  case BO_Rem:
353  case BO_Shl:
354  case BO_Shr:
355  return false;
356  // All other cases.
357  default:
358  return true;
359  }
360  }
361 
362  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
363  // FIXME: Handle <=> here.
364  if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
365  BinaryOperator::isRelationalOp(SSE->getOpcode())) {
366  // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
367  // We've recently started producing Loc <> NonLoc comparisons (that
368  // result from casts of one of the operands between eg. intptr_t and
369  // void *), but we can't reason about them yet.
370  if (Loc::isLocType(SSE->getLHS()->getType())) {
371  return Loc::isLocType(SSE->getRHS()->getType());
372  }
373  }
374  }
375 
376  return false;
377  }
378 
379  return true;
380 }
381 
382 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
383  SymbolRef Sym) {
384  const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
385 
386  // If we don't have any information about this symbol, it's underconstrained.
387  if (!Ranges)
388  return ConditionTruthVal();
389 
390  // If we have a concrete value, see if it's zero.
391  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
392  return *Value == 0;
393 
394  BasicValueFactory &BV = getBasicVals();
395  APSIntType IntType = BV.getAPSIntType(Sym->getType());
396  llvm::APSInt Zero = IntType.getZeroValue();
397 
398  // Check if zero is in the set of possible values.
399  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
400  return false;
401 
402  // Zero is a possible value, but it is not the /only/ possible value.
403  return ConditionTruthVal();
404 }
405 
406 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
407  SymbolRef Sym) const {
408  const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
409  return T ? T->getConcreteValue() : nullptr;
410 }
411 
412 /// Scan all symbols referenced by the constraints. If the symbol is not alive
413 /// as marked in LSymbols, mark it as dead in DSymbols.
415 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
416  SymbolReaper &SymReaper) {
417  bool Changed = false;
418  ConstraintRangeTy CR = State->get<ConstraintRange>();
419  ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
420 
421  for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
422  SymbolRef Sym = I.getKey();
423  if (SymReaper.isDead(Sym)) {
424  Changed = true;
425  CR = CRFactory.remove(CR, Sym);
426  }
427  }
428 
429  return Changed ? State->set<ConstraintRange>(CR) : State;
430 }
431 
432 /// Return a range set subtracting zero from \p Domain.
434  BasicValueFactory &BV,
436  SymbolRef Sym,
437  RangeSet Domain) {
438  APSIntType IntType = BV.getAPSIntType(Sym->getType());
439  return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
440  --IntType.getZeroValue());
441 }
442 
443 /// Apply implicit constraints for bitwise OR- and AND-.
444 /// For unsigned types, bitwise OR with a constant always returns
445 /// a value greater-or-equal than the constant, and bitwise AND
446 /// returns a value less-or-equal then the constant.
447 ///
448 /// Pattern matches the expression \p Sym against those rule,
449 /// and applies the required constraints.
450 /// \p Input Previously established expression range set
452  BasicValueFactory &BV,
454  RangeSet Input,
455  const SymIntExpr* SIE) {
456  QualType T = SIE->getType();
457  bool IsUnsigned = T->isUnsignedIntegerType();
458  const llvm::APSInt &RHS = SIE->getRHS();
459  const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
460  BinaryOperator::Opcode Operator = SIE->getOpcode();
461 
462  // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
463  if (Operator == BO_Or && IsUnsigned)
464  return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
465 
466  // Bitwise-or with a non-zero constant is always non-zero.
467  if (Operator == BO_Or && RHS != Zero)
468  return assumeNonZero(BV, F, SIE, Input);
469 
470  // For unsigned types, or positive RHS,
471  // bitwise-and output is always smaller-or-equal than RHS (assuming two's
472  // complement representation of signed types).
473  if (Operator == BO_And && (IsUnsigned || RHS >= Zero))
474  return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
475 
476  return Input;
477 }
478 
479 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
480  SymbolRef Sym) {
481  ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
482 
483  // If Sym is a difference of symbols A - B, then maybe we have range set
484  // stored for B - A.
485  BasicValueFactory &BV = getBasicVals();
486  const RangeSet *R = getRangeForMinusSymbol(State, Sym);
487 
488  // If we have range set stored for both A - B and B - A then calculate the
489  // effective range set by intersecting the range set for A - B and the
490  // negated range set of B - A.
491  if (V && R)
492  return V->Intersect(BV, F, R->Negate(BV, F));
493  if (V)
494  return *V;
495  if (R)
496  return R->Negate(BV, F);
497 
498  // Lazily generate a new RangeSet representing all possible values for the
499  // given symbol type.
500  QualType T = Sym->getType();
501 
502  RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
503 
504  // References are known to be non-zero.
505  if (T->isReferenceType())
506  return assumeNonZero(BV, F, Sym, Result);
507 
508  // Known constraints on ranges of bitwise expressions.
509  if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
510  return applyBitwiseConstraints(BV, F, Result, SIE);
511 
512  return Result;
513 }
514 
515 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
516 // obtain the negated symbolic expression instead of constructing the
517 // symbol manually. This will allow us to support finding ranges of not
518 // only negated SymSymExpr-type expressions, but also of other, simpler
519 // expressions which we currently do not know how to negate.
520 const RangeSet*
521 RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
522  SymbolRef Sym) {
523  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
524  if (SSE->getOpcode() == BO_Sub) {
525  QualType T = Sym->getType();
526  SymbolManager &SymMgr = State->getSymbolManager();
527  SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
528  SSE->getLHS(), T);
529  if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
530  // Unsigned range set cannot be negated, unless it is [0, 0].
531  if ((negV->getConcreteValue() &&
532  (*negV->getConcreteValue() == 0)) ||
534  return negV;
535  }
536  }
537  }
538  return nullptr;
539 }
540 
541 //===------------------------------------------------------------------------===
542 // assumeSymX methods: protected interface for RangeConstraintManager.
543 //===------------------------------------------------------------------------===/
544 
545 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
546 // and (x, y) for open ranges. These ranges are modular, corresponding with
547 // a common treatment of C integer overflow. This means that these methods
548 // do not have to worry about overflow; RangeSet::Intersect can handle such a
549 // "wraparound" range.
550 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
551 // UINT_MAX, 0, 1, and 2.
552 
554 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
555  const llvm::APSInt &Int,
556  const llvm::APSInt &Adjustment) {
557  // Before we do any real work, see if the value can even show up.
558  APSIntType AdjustmentType(Adjustment);
559  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
560  return St;
561 
562  llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
563  llvm::APSInt Upper = Lower;
564  --Lower;
565  ++Upper;
566 
567  // [Int-Adjustment+1, Int-Adjustment-1]
568  // Notice that the lower bound is greater than the upper bound.
569  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
570  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
571 }
572 
574 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
575  const llvm::APSInt &Int,
576  const llvm::APSInt &Adjustment) {
577  // Before we do any real work, see if the value can even show up.
578  APSIntType AdjustmentType(Adjustment);
579  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
580  return nullptr;
581 
582  // [Int-Adjustment, Int-Adjustment]
583  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
584  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
585  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
586 }
587 
588 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
589  SymbolRef Sym,
590  const llvm::APSInt &Int,
591  const llvm::APSInt &Adjustment) {
592  // Before we do any real work, see if the value can even show up.
593  APSIntType AdjustmentType(Adjustment);
594  switch (AdjustmentType.testInRange(Int, true)) {
596  return F.getEmptySet();
598  break;
600  return getRange(St, Sym);
601  }
602 
603  // Special case for Int == Min. This is always false.
604  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
605  llvm::APSInt Min = AdjustmentType.getMinValue();
606  if (ComparisonVal == Min)
607  return F.getEmptySet();
608 
609  llvm::APSInt Lower = Min - Adjustment;
610  llvm::APSInt Upper = ComparisonVal - Adjustment;
611  --Upper;
612 
613  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
614 }
615 
617 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
618  const llvm::APSInt &Int,
619  const llvm::APSInt &Adjustment) {
620  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
621  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
622 }
623 
624 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
625  SymbolRef Sym,
626  const llvm::APSInt &Int,
627  const llvm::APSInt &Adjustment) {
628  // Before we do any real work, see if the value can even show up.
629  APSIntType AdjustmentType(Adjustment);
630  switch (AdjustmentType.testInRange(Int, true)) {
632  return getRange(St, Sym);
634  break;
636  return F.getEmptySet();
637  }
638 
639  // Special case for Int == Max. This is always false.
640  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
641  llvm::APSInt Max = AdjustmentType.getMaxValue();
642  if (ComparisonVal == Max)
643  return F.getEmptySet();
644 
645  llvm::APSInt Lower = ComparisonVal - Adjustment;
646  llvm::APSInt Upper = Max - Adjustment;
647  ++Lower;
648 
649  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
650 }
651 
653 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
654  const llvm::APSInt &Int,
655  const llvm::APSInt &Adjustment) {
656  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
657  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
658 }
659 
660 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
661  SymbolRef Sym,
662  const llvm::APSInt &Int,
663  const llvm::APSInt &Adjustment) {
664  // Before we do any real work, see if the value can even show up.
665  APSIntType AdjustmentType(Adjustment);
666  switch (AdjustmentType.testInRange(Int, true)) {
668  return getRange(St, Sym);
670  break;
672  return F.getEmptySet();
673  }
674 
675  // Special case for Int == Min. This is always feasible.
676  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
677  llvm::APSInt Min = AdjustmentType.getMinValue();
678  if (ComparisonVal == Min)
679  return getRange(St, Sym);
680 
681  llvm::APSInt Max = AdjustmentType.getMaxValue();
682  llvm::APSInt Lower = ComparisonVal - Adjustment;
683  llvm::APSInt Upper = Max - Adjustment;
684 
685  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
686 }
687 
689 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
690  const llvm::APSInt &Int,
691  const llvm::APSInt &Adjustment) {
692  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
693  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
694 }
695 
696 RangeSet RangeConstraintManager::getSymLERange(
697  llvm::function_ref<RangeSet()> RS,
698  const llvm::APSInt &Int,
699  const llvm::APSInt &Adjustment) {
700  // Before we do any real work, see if the value can even show up.
701  APSIntType AdjustmentType(Adjustment);
702  switch (AdjustmentType.testInRange(Int, true)) {
704  return F.getEmptySet();
706  break;
708  return RS();
709  }
710 
711  // Special case for Int == Max. This is always feasible.
712  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
713  llvm::APSInt Max = AdjustmentType.getMaxValue();
714  if (ComparisonVal == Max)
715  return RS();
716 
717  llvm::APSInt Min = AdjustmentType.getMinValue();
718  llvm::APSInt Lower = Min - Adjustment;
719  llvm::APSInt Upper = ComparisonVal - Adjustment;
720 
721  return RS().Intersect(getBasicVals(), F, Lower, Upper);
722 }
723 
724 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
725  SymbolRef Sym,
726  const llvm::APSInt &Int,
727  const llvm::APSInt &Adjustment) {
728  return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
729 }
730 
732 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
733  const llvm::APSInt &Int,
734  const llvm::APSInt &Adjustment) {
735  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
736  return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
737 }
738 
739 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
740  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
741  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
742  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
743  if (New.isEmpty())
744  return nullptr;
745  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
746  return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out);
747 }
748 
749 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
750  ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
751  const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
752  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
753  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
754  RangeSet New(RangeLT.addRange(F, RangeGT));
755  return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
756 }
757 
758 //===----------------------------------------------------------------------===//
759 // Pretty-printing.
760 //===----------------------------------------------------------------------===//
761 
762 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
763  const char *NL, unsigned int Space,
764  bool IsDot) const {
765  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
766 
767  Indent(Out, Space, IsDot) << "\"constraints\": ";
768  if (Constraints.isEmpty()) {
769  Out << "null," << NL;
770  return;
771  }
772 
773  ++Space;
774  Out << '[' << NL;
775  for (ConstraintRangeTy::iterator I = Constraints.begin();
776  I != Constraints.end(); ++I) {
777  Indent(Out, Space, IsDot)
778  << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \"";
779  I.getData().print(Out);
780  Out << "\" }";
781 
782  if (std::next(I) != Constraints.end())
783  Out << ',';
784  Out << NL;
785  }
786 
787  --Space;
788  Indent(Out, Space, IsDot) << "]," << NL;
789 }
A (possibly-)qualified type.
Definition: Type.h:643
Value is less than the minimum representable value.
Definition: APSIntType.h:77
bool isDead(SymbolRef sym)
Returns whether or not a symbol has been confirmed dead.
const SymExpr * SymbolRef
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, SubEngine *subengine)
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
The base class of the type hierarchy.
Definition: Type.h:1418
A Range represents the closed range [from, to].
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintRangeTy
bool isUnsignedIntegerType() const
Return true if this is an integer type that is unsigned, according to C99 6.2.5p6 [which returns true...
Definition: Type.cpp:1915
RangeSet contains a set of ranges.
long i
Definition: xmmintrin.h:1456
bool isEqualityOp() const
Definition: Expr.h:3495
Symbolic value.
Definition: SymExpr.h:29
LineState State
bool isReferenceType() const
Definition: Type.h:6363
RangeSet Negate(BasicValueFactory &BV, Factory &F) const
static bool isLocType(QualType T)
Definition: SVals.h:329
BinaryOperatorKind
PrimRangeSet::Factory Factory
Value is representable using this type.
Definition: APSIntType.h:78
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
Represents a symbolic expression like &#39;x&#39; + 3.
bool isRelationalOp() const
Definition: Expr.h:3492
llvm::APSInt getZeroValue() const LLVM_READONLY
Returns an all-zero value for this type.
Definition: APSIntType.h:55
virtual QualType getType() const =0
void print(raw_ostream &os) const
#define V(N, I)
Definition: ASTContext.h:2912
const llvm::APSInt * getConcreteValue() const
getConcreteValue - If a symbol is contrained to equal a specific integer constant then this method re...
static RangeSet assumeNonZero(BasicValueFactory &BV, RangeSet::Factory &F, SymbolRef Sym, RangeSet Domain)
Return a range set subtracting zero from Domain.
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type...
Definition: SVals.h:111
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:75
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:1891
A class responsible for cleaning up unused symbols.
Value is greater than the maximum representable value.
Definition: APSIntType.h:79
RangeTestResultKind
Used to classify whether a value is representable using this type.
Definition: APSIntType.h:76
Dataflow Directional Tag Classes.
Represents symbolic expression that isn&#39;t a location.
Definition: SVals.h:349
const llvm::APSInt & getMinValue(const llvm::APSInt &v)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const
PrimRangeSet::iterator iterator
static RangeSet applyBitwiseConstraints(BasicValueFactory &BV, RangeSet::Factory &F, RangeSet Input, const SymIntExpr *SIE)
Apply implicit constraints for bitwise OR- and AND-.
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:14125
const llvm::APSInt & getMaxValue(const llvm::APSInt &v)
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:19
Represents a symbolic expression like &#39;x&#39; + &#39;y&#39;.