contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

   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
  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 "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) {
  79   case APSIntType::RTR_Below:
  80     switch (UpperTest) {
  81     case APSIntType::RTR_Below:
  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;
  91     case APSIntType::RTR_Within:
  92       // The range starts below what's possible but ends within it. Pin.
  93       Lower = Type.getMinValue();
  94       Type.apply(Upper);
  95       break;
  96     case APSIntType::RTR_Above:
  97       // The range spans all possible values for the symbol. Pin.
  98       Lower = Type.getMinValue();
  99       Upper = Type.getMaxValue();
 100       break;
 101     }
 102     break;
 103   case APSIntType::RTR_Within:
 104     switch (UpperTest) {
 105     case APSIntType::RTR_Below:
 106       // The range wraps around, but all lower values are not possible.
 107       Type.apply(Lower);
 108       Upper = Type.getMaxValue();
 109       break;
 110     case APSIntType::RTR_Within:
 111       // The range may or may not wrap around, but both limits are valid.
 112       Type.apply(Lower);
 113       Type.apply(Upper);
 114       break;
 115     case APSIntType::RTR_Above:
 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;
 122   case APSIntType::RTR_Above:
 123     switch (UpperTest) {
 124     case APSIntType::RTR_Below:
 125       // The range wraps but is outside the symbol's set of possible values.
 126       return false;
 127     case APSIntType::RTR_Within:
 128       // The range starts above what's possible but ends within it (wrap).
 129       Lower = Type.getMinValue();
 130       Type.apply(Upper);
 131       break;
 132     case APSIntType::RTR_Above:
 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.
 156 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
 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 // Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
 178 // [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
 179 // signed values of the type.
 180 RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
 181   PrimRangeSet newRanges = F.getEmptySet();
 182
 183   for (iterator i = begin(), e = end(); i != e; ++i) {
 184     const llvm::APSInt &from = i->From(), &to = i->To();
 185     const llvm::APSInt &newTo = (from.isMinSignedValue() ?
 186                                  BV.getMaxValue(from) :
 187                                  BV.getValue(- from));
 188     if (to.isMaxSignedValue() && !newRanges.isEmpty() &&
 189         newRanges.begin()->From().isMinSignedValue()) {
 190       assert(newRanges.begin()->To().isMinSignedValue() &&
 191              "Ranges should not overlap");
 192       assert(!from.isMinSignedValue() && "Ranges should not overlap");
 193       const llvm::APSInt &newFrom = newRanges.begin()->From();
 194       newRanges =
 195         F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
 196     } else if (!to.isMinSignedValue()) {
 197       const llvm::APSInt &newFrom = BV.getValue(- to);
 198       newRanges = F.add(newRanges, Range(newFrom, newTo));
 199     }
 200     if (from.isMinSignedValue()) {
 201       newRanges = F.add(newRanges, Range(BV.getMinValue(from),
 202                                          BV.getMinValue(from)));
 203     }
 204   }
 205
 206   return newRanges;
 207 }
 208
 209 void RangeSet::print(raw_ostream &os) const {
 210   bool isFirst = true;
 211   os << "{ ";
 212   for (iterator i = begin(), e = end(); i != e; ++i) {
 213     if (isFirst)
 214       isFirst = false;
 215     else
 216       os << ", ";
 217
 218     os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
 219        << ']';
 220   }
 221   os << " }";
 222 }
 223
 224 namespace {
 225 class RangeConstraintManager : public RangedConstraintManager {
 226 public:
 227   RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
 228       : RangedConstraintManager(SE, SVB) {}
 229
 230   //===------------------------------------------------------------------===//
 231   // Implementation for interface from ConstraintManager.
 232   //===------------------------------------------------------------------===//
 233
 234   bool canReasonAbout(SVal X) const override;
 235
 236   ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
 237
 238   const llvm::APSInt *getSymVal(ProgramStateRef State,
 239                                 SymbolRef Sym) const override;
 240
 241   ProgramStateRef removeDeadBindings(ProgramStateRef State,
 242                                      SymbolReaper &SymReaper) override;
 243
 244   void print(ProgramStateRef State, raw_ostream &Out, const char *nl,
 245              const char *sep) override;
 246
 247   //===------------------------------------------------------------------===//
 248   // Implementation for interface from RangedConstraintManager.
 249   //===------------------------------------------------------------------===//
 250
 251   ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
 252                               const llvm::APSInt &V,
 253                               const llvm::APSInt &Adjustment) override;
 254
 255   ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
 256                               const llvm::APSInt &V,
 257                               const llvm::APSInt &Adjustment) override;
 258
 259   ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
 260                               const llvm::APSInt &V,
 261                               const llvm::APSInt &Adjustment) override;
 262
 263   ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
 264                               const llvm::APSInt &V,
 265                               const llvm::APSInt &Adjustment) override;
 266
 267   ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
 268                               const llvm::APSInt &V,
 269                               const llvm::APSInt &Adjustment) override;
 270
 271   ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
 272                               const llvm::APSInt &V,
 273                               const llvm::APSInt &Adjustment) override;
 274
 275   ProgramStateRef assumeSymWithinInclusiveRange(
 276       ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 277       const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
 278
 279   ProgramStateRef assumeSymOutsideInclusiveRange(
 280       ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 281       const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
 282
 283 private:
 284   RangeSet::Factory F;
 285
 286   RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
 287   const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
 288                                          SymbolRef Sym);
 289
 290   RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
 291                          const llvm::APSInt &Int,
 292                          const llvm::APSInt &Adjustment);
 293   RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
 294                          const llvm::APSInt &Int,
 295                          const llvm::APSInt &Adjustment);
 296   RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
 297                          const llvm::APSInt &Int,
 298                          const llvm::APSInt &Adjustment);
 299   RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
 300                          const llvm::APSInt &Int,
 301                          const llvm::APSInt &Adjustment);
 302   RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
 303                          const llvm::APSInt &Int,
 304                          const llvm::APSInt &Adjustment);
 305
 306 };
 307
 308 } // end anonymous namespace
 309
 310 std::unique_ptr<ConstraintManager>
 311 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) {
 312   return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
 313 }
 314
 315 bool RangeConstraintManager::canReasonAbout(SVal X) const {
 316   Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
 317   if (SymVal && SymVal->isExpression()) {
 318     const SymExpr *SE = SymVal->getSymbol();
 319
 320     if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
 321       switch (SIE->getOpcode()) {
 322       // We don't reason yet about bitwise-constraints on symbolic values.
 323       case BO_And:
 324       case BO_Or:
 325       case BO_Xor:
 326         return false;
 327       // We don't reason yet about these arithmetic constraints on
 328       // symbolic values.
 329       case BO_Mul:
 330       case BO_Div:
 331       case BO_Rem:
 332       case BO_Shl:
 333       case BO_Shr:
 334         return false;
 335       // All other cases.
 336       default:
 337         return true;
 338       }
 339     }
 340
 341     if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
 342       // FIXME: Handle <=> here.
 343       if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
 344           BinaryOperator::isRelationalOp(SSE->getOpcode())) {
 345         // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
 346         // We've recently started producing Loc <> NonLoc comparisons (that
 347         // result from casts of one of the operands between eg. intptr_t and
 348         // void *), but we can't reason about them yet.
 349         if (Loc::isLocType(SSE->getLHS()->getType())) {
 350           return Loc::isLocType(SSE->getRHS()->getType());
 351         }
 352       }
 353     }
 354
 355     return false;
 356   }
 357
 358   return true;
 359 }
 360
 361 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
 362                                                     SymbolRef Sym) {
 363   const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
 364
 365   // If we don't have any information about this symbol, it's underconstrained.
 366   if (!Ranges)
 367     return ConditionTruthVal();
 368
 369   // If we have a concrete value, see if it's zero.
 370   if (const llvm::APSInt *Value = Ranges->getConcreteValue())
 371     return *Value == 0;
 372
 373   BasicValueFactory &BV = getBasicVals();
 374   APSIntType IntType = BV.getAPSIntType(Sym->getType());
 375   llvm::APSInt Zero = IntType.getZeroValue();
 376
 377   // Check if zero is in the set of possible values.
 378   if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
 379     return false;
 380
 381   // Zero is a possible value, but it is not the /only/ possible value.
 382   return ConditionTruthVal();
 383 }
 384
 385 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
 386                                                       SymbolRef Sym) const {
 387   const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
 388   return T ? T->getConcreteValue() : nullptr;
 389 }
 390
 391 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 392 /// as marked in LSymbols, mark it as dead in DSymbols.
 393 ProgramStateRef
 394 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
 395                                            SymbolReaper &SymReaper) {
 396   bool Changed = false;
 397   ConstraintRangeTy CR = State->get<ConstraintRange>();
 398   ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
 399
 400   for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
 401     SymbolRef Sym = I.getKey();
 402     if (SymReaper.isDead(Sym)) {
 403       Changed = true;
 404       CR = CRFactory.remove(CR, Sym);
 405     }
 406   }
 407
 408   return Changed ? State->set<ConstraintRange>(CR) : State;
 409 }
 410
 411 /// Return a range set subtracting zero from \p Domain.
 412 static RangeSet assumeNonZero(
 413     BasicValueFactory &BV,
 414     RangeSet::Factory &F,
 415     SymbolRef Sym,
 416     RangeSet Domain) {
 417   APSIntType IntType = BV.getAPSIntType(Sym->getType());
 418   return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
 419       --IntType.getZeroValue());
 420 }
 421
 422 /// Apply implicit constraints for bitwise OR- and AND-.
 423 /// For unsigned types, bitwise OR with a constant always returns
 424 /// a value greater-or-equal than the constant, and bitwise AND
 425 /// returns a value less-or-equal then the constant.
 426 ///
 427 /// Pattern matches the expression \p Sym against those rule,
 428 /// and applies the required constraints.
 429 /// \p Input Previously established expression range set
 430 static RangeSet applyBitwiseConstraints(
 431     BasicValueFactory &BV,
 432     RangeSet::Factory &F,
 433     RangeSet Input,
 434     const SymIntExpr* SIE) {
 435   QualType T = SIE->getType();
 436   bool IsUnsigned = T->isUnsignedIntegerType();
 437   const llvm::APSInt &RHS = SIE->getRHS();
 438   const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
 439   BinaryOperator::Opcode Operator = SIE->getOpcode();
 440
 441   // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
 442   if (Operator == BO_Or && IsUnsigned)
 443     return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
 444
 445   // Bitwise-or with a non-zero constant is always non-zero.
 446   if (Operator == BO_Or && RHS != Zero)
 447     return assumeNonZero(BV, F, SIE, Input);
 448
 449   // For unsigned types, or positive RHS,
 450   // bitwise-and output is always smaller-or-equal than RHS (assuming two's
 451   // complement representation of signed types).
 452   if (Operator == BO_And && (IsUnsigned || RHS >= Zero))
 453     return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
 454
 455   return Input;
 456 }
 457
 458 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
 459                                           SymbolRef Sym) {
 460   if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym))
 461     return *V;
 462
 463   BasicValueFactory &BV = getBasicVals();
 464
 465   // If Sym is a difference of symbols A - B, then maybe we have range set
 466   // stored for B - A.
 467   if (const RangeSet *R = getRangeForMinusSymbol(State, Sym))
 468     return R->Negate(BV, F);
 469
 470   // Lazily generate a new RangeSet representing all possible values for the
 471   // given symbol type.
 472   QualType T = Sym->getType();
 473
 474   RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
 475
 476   // References are known to be non-zero.
 477   if (T->isReferenceType())
 478     return assumeNonZero(BV, F, Sym, Result);
 479
 480   // Known constraints on ranges of bitwise expressions.
 481   if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
 482     return applyBitwiseConstraints(BV, F, Result, SIE);
 483
 484   return Result;
 485 }
 486
 487 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
 488 //        obtain the negated symbolic expression instead of constructing the
 489 //        symbol manually. This will allow us to support finding ranges of not
 490 //        only negated SymSymExpr-type expressions, but also of other, simpler
 491 //        expressions which we currently do not know how to negate.
 492 const RangeSet*
 493 RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
 494                                                SymbolRef Sym) {
 495   if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
 496     if (SSE->getOpcode() == BO_Sub) {
 497       QualType T = Sym->getType();
 498       SymbolManager &SymMgr = State->getSymbolManager();
 499       SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
 500                                               SSE->getLHS(), T);
 501       if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
 502         // Unsigned range set cannot be negated, unless it is [0, 0].
 503         if ((negV->getConcreteValue() &&
 504              (*negV->getConcreteValue() == 0)) ||
 505             T->isSignedIntegerOrEnumerationType())
 506           return negV;
 507       }
 508     }
 509   }
 510   return nullptr;
 511 }
 512
 513 //===------------------------------------------------------------------------===
 514 // assumeSymX methods: protected interface for RangeConstraintManager.
 515 //===------------------------------------------------------------------------===/
 516
 517 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
 518 // and (x, y) for open ranges. These ranges are modular, corresponding with
 519 // a common treatment of C integer overflow. This means that these methods
 520 // do not have to worry about overflow; RangeSet::Intersect can handle such a
 521 // "wraparound" range.
 522 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
 523 // UINT_MAX, 0, 1, and 2.
 524
 525 ProgramStateRef
 526 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
 527                                     const llvm::APSInt &Int,
 528                                     const llvm::APSInt &Adjustment) {
 529   // Before we do any real work, see if the value can even show up.
 530   APSIntType AdjustmentType(Adjustment);
 531   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
 532     return St;
 533
 534   llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
 535   llvm::APSInt Upper = Lower;
 536   --Lower;
 537   ++Upper;
 538
 539   // [Int-Adjustment+1, Int-Adjustment-1]
 540   // Notice that the lower bound is greater than the upper bound.
 541   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
 542   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 543 }
 544
 545 ProgramStateRef
 546 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
 547                                     const llvm::APSInt &Int,
 548                                     const llvm::APSInt &Adjustment) {
 549   // Before we do any real work, see if the value can even show up.
 550   APSIntType AdjustmentType(Adjustment);
 551   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
 552     return nullptr;
 553
 554   // [Int-Adjustment, Int-Adjustment]
 555   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
 556   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
 557   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 558 }
 559
 560 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
 561                                                SymbolRef Sym,
 562                                                const llvm::APSInt &Int,
 563                                                const llvm::APSInt &Adjustment) {
 564   // Before we do any real work, see if the value can even show up.
 565   APSIntType AdjustmentType(Adjustment);
 566   switch (AdjustmentType.testInRange(Int, true)) {
 567   case APSIntType::RTR_Below:
 568     return F.getEmptySet();
 569   case APSIntType::RTR_Within:
 570     break;
 571   case APSIntType::RTR_Above:
 572     return getRange(St, Sym);
 573   }
 574
 575   // Special case for Int == Min. This is always false.
 576   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 577   llvm::APSInt Min = AdjustmentType.getMinValue();
 578   if (ComparisonVal == Min)
 579     return F.getEmptySet();
 580
 581   llvm::APSInt Lower = Min - Adjustment;
 582   llvm::APSInt Upper = ComparisonVal - Adjustment;
 583   --Upper;
 584
 585   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 586 }
 587
 588 ProgramStateRef
 589 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
 590                                     const llvm::APSInt &Int,
 591                                     const llvm::APSInt &Adjustment) {
 592   RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
 593   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 594 }
 595
 596 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
 597                                                SymbolRef Sym,
 598                                                const llvm::APSInt &Int,
 599                                                const llvm::APSInt &Adjustment) {
 600   // Before we do any real work, see if the value can even show up.
 601   APSIntType AdjustmentType(Adjustment);
 602   switch (AdjustmentType.testInRange(Int, true)) {
 603   case APSIntType::RTR_Below:
 604     return getRange(St, Sym);
 605   case APSIntType::RTR_Within:
 606     break;
 607   case APSIntType::RTR_Above:
 608     return F.getEmptySet();
 609   }
 610
 611   // Special case for Int == Max. This is always false.
 612   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 613   llvm::APSInt Max = AdjustmentType.getMaxValue();
 614   if (ComparisonVal == Max)
 615     return F.getEmptySet();
 616
 617   llvm::APSInt Lower = ComparisonVal - Adjustment;
 618   llvm::APSInt Upper = Max - Adjustment;
 619   ++Lower;
 620
 621   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 622 }
 623
 624 ProgramStateRef
 625 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
 626                                     const llvm::APSInt &Int,
 627                                     const llvm::APSInt &Adjustment) {
 628   RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
 629   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 630 }
 631
 632 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
 633                                                SymbolRef Sym,
 634                                                const llvm::APSInt &Int,
 635                                                const llvm::APSInt &Adjustment) {
 636   // Before we do any real work, see if the value can even show up.
 637   APSIntType AdjustmentType(Adjustment);
 638   switch (AdjustmentType.testInRange(Int, true)) {
 639   case APSIntType::RTR_Below:
 640     return getRange(St, Sym);
 641   case APSIntType::RTR_Within:
 642     break;
 643   case APSIntType::RTR_Above:
 644     return F.getEmptySet();
 645   }
 646
 647   // Special case for Int == Min. This is always feasible.
 648   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 649   llvm::APSInt Min = AdjustmentType.getMinValue();
 650   if (ComparisonVal == Min)
 651     return getRange(St, Sym);
 652
 653   llvm::APSInt Max = AdjustmentType.getMaxValue();
 654   llvm::APSInt Lower = ComparisonVal - Adjustment;
 655   llvm::APSInt Upper = Max - Adjustment;
 656
 657   return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
 658 }
 659
 660 ProgramStateRef
 661 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
 662                                     const llvm::APSInt &Int,
 663                                     const llvm::APSInt &Adjustment) {
 664   RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
 665   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 666 }
 667
 668 RangeSet RangeConstraintManager::getSymLERange(
 669       llvm::function_ref<RangeSet()> RS,
 670       const llvm::APSInt &Int,
 671       const llvm::APSInt &Adjustment) {
 672   // Before we do any real work, see if the value can even show up.
 673   APSIntType AdjustmentType(Adjustment);
 674   switch (AdjustmentType.testInRange(Int, true)) {
 675   case APSIntType::RTR_Below:
 676     return F.getEmptySet();
 677   case APSIntType::RTR_Within:
 678     break;
 679   case APSIntType::RTR_Above:
 680     return RS();
 681   }
 682
 683   // Special case for Int == Max. This is always feasible.
 684   llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
 685   llvm::APSInt Max = AdjustmentType.getMaxValue();
 686   if (ComparisonVal == Max)
 687     return RS();
 688
 689   llvm::APSInt Min = AdjustmentType.getMinValue();
 690   llvm::APSInt Lower = Min - Adjustment;
 691   llvm::APSInt Upper = ComparisonVal - Adjustment;
 692
 693   return RS().Intersect(getBasicVals(), F, Lower, Upper);
 694 }
 695
 696 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
 697                                                SymbolRef Sym,
 698                                                const llvm::APSInt &Int,
 699                                                const llvm::APSInt &Adjustment) {
 700   return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);
 701 }
 702
 703 ProgramStateRef
 704 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
 705                                     const llvm::APSInt &Int,
 706                                     const llvm::APSInt &Adjustment) {
 707   RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
 708   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 709 }
 710
 711 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
 712     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 713     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
 714   RangeSet New = getSymGERange(State, Sym, From, Adjustment);
 715   if (New.isEmpty())
 716     return nullptr;
 717   RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
 718   return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out);
 719 }
 720
 721 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
 722     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 723     const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
 724   RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
 725   RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
 726   RangeSet New(RangeLT.addRange(F, RangeGT));
 727   return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
 728 }
 729
 730 //===------------------------------------------------------------------------===
 731 // Pretty-printing.
 732 //===------------------------------------------------------------------------===/
 733
 734 void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out,
 735                                    const char *nl, const char *sep) {
 736
 737   ConstraintRangeTy Ranges = St->get<ConstraintRange>();
 738
 739   if (Ranges.isEmpty()) {
 740     Out << nl << sep << "Ranges are empty." << nl;
 741     return;
 742   }
 743
 744   Out << nl << sep << "Ranges of symbol values:";
 745   for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E;
 746        ++I) {
 747     Out << nl << ' ' << I.getKey() << " : ";
 748     I.getData().print(Out);
 749   }
 750   Out << nl;
 751 }