contrib/llvm-project/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

   1 // SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- 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 SimpleSValBuilder, a basic implementation of SValBuilder.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
  19
  20 using namespace clang;
  21 using namespace ento;
  22
  23 namespace {
  24 class SimpleSValBuilder : public SValBuilder {
  25 protected:
  26   SVal dispatchCast(SVal val, QualType castTy) override;
  27   SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override;
  28   SVal evalCastFromLoc(Loc val, QualType castTy) override;
  29
  30 public:
  31   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
  32                     ProgramStateManager &stateMgr)
  33                     : SValBuilder(alloc, context, stateMgr) {}
  34   ~SimpleSValBuilder() override {}
  35
  36   SVal evalMinus(NonLoc val) override;
  37   SVal evalComplement(NonLoc val) override;
  38   SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
  39                    NonLoc lhs, NonLoc rhs, QualType resultTy) override;
  40   SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
  41                    Loc lhs, Loc rhs, QualType resultTy) override;
  42   SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
  43                    Loc lhs, NonLoc rhs, QualType resultTy) override;
  44
  45   /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
  46   ///  (integer) value, that value is returned. Otherwise, returns NULL.
  47   const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
  48
  49   /// Recursively descends into symbolic expressions and replaces symbols
  50   /// with their known values (in the sense of the getKnownValue() method).
  51   SVal simplifySVal(ProgramStateRef State, SVal V) override;
  52
  53   SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
  54                      const llvm::APSInt &RHS, QualType resultTy);
  55 };
  56 } // end anonymous namespace
  57
  58 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
  59                                            ASTContext &context,
  60                                            ProgramStateManager &stateMgr) {
  61   return new SimpleSValBuilder(alloc, context, stateMgr);
  62 }
  63
  64 //===----------------------------------------------------------------------===//
  65 // Transfer function for Casts.
  66 //===----------------------------------------------------------------------===//
  67
  68 SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
  69   assert(Val.getAs<Loc>() || Val.getAs<NonLoc>());
  70   return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy)
  71                            : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy);
  72 }
  73
  74 SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
  75   bool isLocType = Loc::isLocType(castTy);
  76   if (val.getAs<nonloc::PointerToMember>())
  77     return val;
  78
  79   if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) {
  80     if (isLocType)
  81       return LI->getLoc();
  82     // FIXME: Correctly support promotions/truncations.
  83     unsigned castSize = Context.getIntWidth(castTy);
  84     if (castSize == LI->getNumBits())
  85       return val;
  86     return makeLocAsInteger(LI->getLoc(), castSize);
  87   }
  88
  89   if (const SymExpr *se = val.getAsSymbolicExpression()) {
  90     QualType T = Context.getCanonicalType(se->getType());
  91     // If types are the same or both are integers, ignore the cast.
  92     // FIXME: Remove this hack when we support symbolic truncation/extension.
  93     // HACK: If both castTy and T are integers, ignore the cast.  This is
  94     // not a permanent solution.  Eventually we want to precisely handle
  95     // extension/truncation of symbolic integers.  This prevents us from losing
  96     // precision when we assign 'x = y' and 'y' is symbolic and x and y are
  97     // different integer types.
  98    if (haveSameType(T, castTy))
  99       return val;
 100
 101     if (!isLocType)
 102       return makeNonLoc(se, T, castTy);
 103     return UnknownVal();
 104   }
 105
 106   // If value is a non-integer constant, produce unknown.
 107   if (!val.getAs<nonloc::ConcreteInt>())
 108     return UnknownVal();
 109
 110   // Handle casts to a boolean type.
 111   if (castTy->isBooleanType()) {
 112     bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue();
 113     return makeTruthVal(b, castTy);
 114   }
 115
 116   // Only handle casts from integers to integers - if val is an integer constant
 117   // being cast to a non-integer type, produce unknown.
 118   if (!isLocType && !castTy->isIntegralOrEnumerationType())
 119     return UnknownVal();
 120
 121   llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue();
 122   BasicVals.getAPSIntType(castTy).apply(i);
 123
 124   if (isLocType)
 125     return makeIntLocVal(i);
 126   else
 127     return makeIntVal(i);
 128 }
 129
 130 SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
 131
 132   // Casts from pointers -> pointers, just return the lval.
 133   //
 134   // Casts from pointers -> references, just return the lval.  These
 135   //   can be introduced by the frontend for corner cases, e.g
 136   //   casting from va_list* to __builtin_va_list&.
 137   //
 138   if (Loc::isLocType(castTy) || castTy->isReferenceType())
 139     return val;
 140
 141   // FIXME: Handle transparent unions where a value can be "transparently"
 142   //  lifted into a union type.
 143   if (castTy->isUnionType())
 144     return UnknownVal();
 145
 146   // Casting a Loc to a bool will almost always be true,
 147   // unless this is a weak function or a symbolic region.
 148   if (castTy->isBooleanType()) {
 149     switch (val.getSubKind()) {
 150       case loc::MemRegionValKind: {
 151         const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion();
 152         if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
 153           if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
 154             if (FD->isWeak())
 155               // FIXME: Currently we are using an extent symbol here,
 156               // because there are no generic region address metadata
 157               // symbols to use, only content metadata.
 158               return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
 159
 160         if (const SymbolicRegion *SymR = R->getSymbolicBase())
 161           return makeNonLoc(SymR->getSymbol(), BO_NE,
 162                             BasicVals.getZeroWithPtrWidth(), castTy);
 163
 164         // FALL-THROUGH
 165         LLVM_FALLTHROUGH;
 166       }
 167
 168       case loc::GotoLabelKind:
 169         // Labels and non-symbolic memory regions are always true.
 170         return makeTruthVal(true, castTy);
 171     }
 172   }
 173
 174   if (castTy->isIntegralOrEnumerationType()) {
 175     unsigned BitWidth = Context.getIntWidth(castTy);
 176
 177     if (!val.getAs<loc::ConcreteInt>())
 178       return makeLocAsInteger(val, BitWidth);
 179
 180     llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue();
 181     BasicVals.getAPSIntType(castTy).apply(i);
 182     return makeIntVal(i);
 183   }
 184
 185   // All other cases: return 'UnknownVal'.  This includes casting pointers
 186   // to floats, which is probably badness it itself, but this is a good
 187   // intermediate solution until we do something better.
 188   return UnknownVal();
 189 }
 190
 191 //===----------------------------------------------------------------------===//
 192 // Transfer function for unary operators.
 193 //===----------------------------------------------------------------------===//
 194
 195 SVal SimpleSValBuilder::evalMinus(NonLoc val) {
 196   switch (val.getSubKind()) {
 197   case nonloc::ConcreteIntKind:
 198     return val.castAs<nonloc::ConcreteInt>().evalMinus(*this);
 199   default:
 200     return UnknownVal();
 201   }
 202 }
 203
 204 SVal SimpleSValBuilder::evalComplement(NonLoc X) {
 205   switch (X.getSubKind()) {
 206   case nonloc::ConcreteIntKind:
 207     return X.castAs<nonloc::ConcreteInt>().evalComplement(*this);
 208   default:
 209     return UnknownVal();
 210   }
 211 }
 212
 213 //===----------------------------------------------------------------------===//
 214 // Transfer function for binary operators.
 215 //===----------------------------------------------------------------------===//
 216
 217 SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
 218                                     BinaryOperator::Opcode op,
 219                                     const llvm::APSInt &RHS,
 220                                     QualType resultTy) {
 221   bool isIdempotent = false;
 222
 223   // Check for a few special cases with known reductions first.
 224   switch (op) {
 225   default:
 226     // We can't reduce this case; just treat it normally.
 227     break;
 228   case BO_Mul:
 229     // a*0 and a*1
 230     if (RHS == 0)
 231       return makeIntVal(0, resultTy);
 232     else if (RHS == 1)
 233       isIdempotent = true;
 234     break;
 235   case BO_Div:
 236     // a/0 and a/1
 237     if (RHS == 0)
 238       // This is also handled elsewhere.
 239       return UndefinedVal();
 240     else if (RHS == 1)
 241       isIdempotent = true;
 242     break;
 243   case BO_Rem:
 244     // a%0 and a%1
 245     if (RHS == 0)
 246       // This is also handled elsewhere.
 247       return UndefinedVal();
 248     else if (RHS == 1)
 249       return makeIntVal(0, resultTy);
 250     break;
 251   case BO_Add:
 252   case BO_Sub:
 253   case BO_Shl:
 254   case BO_Shr:
 255   case BO_Xor:
 256     // a+0, a-0, a<<0, a>>0, a^0
 257     if (RHS == 0)
 258       isIdempotent = true;
 259     break;
 260   case BO_And:
 261     // a&0 and a&(~0)
 262     if (RHS == 0)
 263       return makeIntVal(0, resultTy);
 264     else if (RHS.isAllOnesValue())
 265       isIdempotent = true;
 266     break;
 267   case BO_Or:
 268     // a|0 and a|(~0)
 269     if (RHS == 0)
 270       isIdempotent = true;
 271     else if (RHS.isAllOnesValue()) {
 272       const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
 273       return nonloc::ConcreteInt(Result);
 274     }
 275     break;
 276   }
 277
 278   // Idempotent ops (like a*1) can still change the type of an expression.
 279   // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the
 280   // dirty work.
 281   if (isIdempotent)
 282       return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
 283
 284   // If we reach this point, the expression cannot be simplified.
 285   // Make a SymbolVal for the entire expression, after converting the RHS.
 286   const llvm::APSInt *ConvertedRHS = &RHS;
 287   if (BinaryOperator::isComparisonOp(op)) {
 288     // We're looking for a type big enough to compare the symbolic value
 289     // with the given constant.
 290     // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
 291     ASTContext &Ctx = getContext();
 292     QualType SymbolType = LHS->getType();
 293     uint64_t ValWidth = RHS.getBitWidth();
 294     uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
 295
 296     if (ValWidth < TypeWidth) {
 297       // If the value is too small, extend it.
 298       ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
 299     } else if (ValWidth == TypeWidth) {
 300       // If the value is signed but the symbol is unsigned, do the comparison
 301       // in unsigned space. [C99 6.3.1.8]
 302       // (For the opposite case, the value is already unsigned.)
 303       if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
 304         ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
 305     }
 306   } else
 307     ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
 308
 309   return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
 310 }
 311
 312 // See if Sym is known to be a relation Rel with Bound.
 313 static bool isInRelation(BinaryOperator::Opcode Rel, SymbolRef Sym,
 314                          llvm::APSInt Bound, ProgramStateRef State) {
 315   SValBuilder &SVB = State->getStateManager().getSValBuilder();
 316   SVal Result =
 317       SVB.evalBinOpNN(State, Rel, nonloc::SymbolVal(Sym),
 318                       nonloc::ConcreteInt(Bound), SVB.getConditionType());
 319   if (auto DV = Result.getAs<DefinedSVal>()) {
 320     return !State->assume(*DV, false);
 321   }
 322   return false;
 323 }
 324
 325 // See if Sym is known to be within [min/4, max/4], where min and max
 326 // are the bounds of the symbol's integral type. With such symbols,
 327 // some manipulations can be performed without the risk of overflow.
 328 // assume() doesn't cause infinite recursion because we should be dealing
 329 // with simpler symbols on every recursive call.
 330 static bool isWithinConstantOverflowBounds(SymbolRef Sym,
 331                                            ProgramStateRef State) {
 332   SValBuilder &SVB = State->getStateManager().getSValBuilder();
 333   BasicValueFactory &BV = SVB.getBasicValueFactory();
 334
 335   QualType T = Sym->getType();
 336   assert(T->isSignedIntegerOrEnumerationType() &&
 337          "This only works with signed integers!");
 338   APSIntType AT = BV.getAPSIntType(T);
 339
 340   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
 341   return isInRelation(BO_LE, Sym, Max, State) &&
 342          isInRelation(BO_GE, Sym, Min, State);
 343 }
 344
 345 // Same for the concrete integers: see if I is within [min/4, max/4].
 346 static bool isWithinConstantOverflowBounds(llvm::APSInt I) {
 347   APSIntType AT(I);
 348   assert(!AT.isUnsigned() &&
 349          "This only works with signed integers!");
 350
 351   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
 352   return (I <= Max) && (I >= -Max);
 353 }
 354
 355 static std::pair<SymbolRef, llvm::APSInt>
 356 decomposeSymbol(SymbolRef Sym, BasicValueFactory &BV) {
 357   if (const auto *SymInt = dyn_cast<SymIntExpr>(Sym))
 358     if (BinaryOperator::isAdditiveOp(SymInt->getOpcode()))
 359       return std::make_pair(SymInt->getLHS(),
 360                             (SymInt->getOpcode() == BO_Add) ?
 361                             (SymInt->getRHS()) :
 362                             (-SymInt->getRHS()));
 363
 364   // Fail to decompose: "reduce" the problem to the "$x + 0" case.
 365   return std::make_pair(Sym, BV.getValue(0, Sym->getType()));
 366 }
 367
 368 // Simplify "(LSym + LInt) Op (RSym + RInt)" assuming all values are of the
 369 // same signed integral type and no overflows occur (which should be checked
 370 // by the caller).
 371 static NonLoc doRearrangeUnchecked(ProgramStateRef State,
 372                                    BinaryOperator::Opcode Op,
 373                                    SymbolRef LSym, llvm::APSInt LInt,
 374                                    SymbolRef RSym, llvm::APSInt RInt) {
 375   SValBuilder &SVB = State->getStateManager().getSValBuilder();
 376   BasicValueFactory &BV = SVB.getBasicValueFactory();
 377   SymbolManager &SymMgr = SVB.getSymbolManager();
 378
 379   QualType SymTy = LSym->getType();
 380   assert(SymTy == RSym->getType() &&
 381          "Symbols are not of the same type!");
 382   assert(APSIntType(LInt) == BV.getAPSIntType(SymTy) &&
 383          "Integers are not of the same type as symbols!");
 384   assert(APSIntType(RInt) == BV.getAPSIntType(SymTy) &&
 385          "Integers are not of the same type as symbols!");
 386
 387   QualType ResultTy;
 388   if (BinaryOperator::isComparisonOp(Op))
 389     ResultTy = SVB.getConditionType();
 390   else if (BinaryOperator::isAdditiveOp(Op))
 391     ResultTy = SymTy;
 392   else
 393     llvm_unreachable("Operation not suitable for unchecked rearrangement!");
 394
 395   // FIXME: Can we use assume() without getting into an infinite recursion?
 396   if (LSym == RSym)
 397     return SVB.evalBinOpNN(State, Op, nonloc::ConcreteInt(LInt),
 398                            nonloc::ConcreteInt(RInt), ResultTy)
 399         .castAs<NonLoc>();
 400
 401   SymbolRef ResultSym = nullptr;
 402   BinaryOperator::Opcode ResultOp;
 403   llvm::APSInt ResultInt;
 404   if (BinaryOperator::isComparisonOp(Op)) {
 405     // Prefer comparing to a non-negative number.
 406     // FIXME: Maybe it'd be better to have consistency in
 407     // "$x - $y" vs. "$y - $x" because those are solver's keys.
 408     if (LInt > RInt) {
 409       ResultSym = SymMgr.getSymSymExpr(RSym, BO_Sub, LSym, SymTy);
 410       ResultOp = BinaryOperator::reverseComparisonOp(Op);
 411       ResultInt = LInt - RInt; // Opposite order!
 412     } else {
 413       ResultSym = SymMgr.getSymSymExpr(LSym, BO_Sub, RSym, SymTy);
 414       ResultOp = Op;
 415       ResultInt = RInt - LInt; // Opposite order!
 416     }
 417   } else {
 418     ResultSym = SymMgr.getSymSymExpr(LSym, Op, RSym, SymTy);
 419     ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt);
 420     ResultOp = BO_Add;
 421     // Bring back the cosmetic difference.
 422     if (ResultInt < 0) {
 423       ResultInt = -ResultInt;
 424       ResultOp = BO_Sub;
 425     } else if (ResultInt == 0) {
 426       // Shortcut: Simplify "$x + 0" to "$x".
 427       return nonloc::SymbolVal(ResultSym);
 428     }
 429   }
 430   const llvm::APSInt &PersistentResultInt = BV.getValue(ResultInt);
 431   return nonloc::SymbolVal(
 432       SymMgr.getSymIntExpr(ResultSym, ResultOp, PersistentResultInt, ResultTy));
 433 }
 434
 435 // Rearrange if symbol type matches the result type and if the operator is a
 436 // comparison operator, both symbol and constant must be within constant
 437 // overflow bounds.
 438 static bool shouldRearrange(ProgramStateRef State, BinaryOperator::Opcode Op,
 439                             SymbolRef Sym, llvm::APSInt Int, QualType Ty) {
 440   return Sym->getType() == Ty &&
 441     (!BinaryOperator::isComparisonOp(Op) ||
 442      (isWithinConstantOverflowBounds(Sym, State) &&
 443       isWithinConstantOverflowBounds(Int)));
 444 }
 445
 446 static Optional<NonLoc> tryRearrange(ProgramStateRef State,
 447                                      BinaryOperator::Opcode Op, NonLoc Lhs,
 448                                      NonLoc Rhs, QualType ResultTy) {
 449   ProgramStateManager &StateMgr = State->getStateManager();
 450   SValBuilder &SVB = StateMgr.getSValBuilder();
 451
 452   // We expect everything to be of the same type - this type.
 453   QualType SingleTy;
 454
 455   auto &Opts =
 456     StateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions();
 457
 458   // FIXME: After putting complexity threshold to the symbols we can always
 459   //        rearrange additive operations but rearrange comparisons only if
 460   //        option is set.
 461   if(!Opts.ShouldAggressivelySimplifyBinaryOperation)
 462     return None;
 463
 464   SymbolRef LSym = Lhs.getAsSymbol();
 465   if (!LSym)
 466     return None;
 467
 468   if (BinaryOperator::isComparisonOp(Op)) {
 469     SingleTy = LSym->getType();
 470     if (ResultTy != SVB.getConditionType())
 471       return None;
 472     // Initialize SingleTy later with a symbol's type.
 473   } else if (BinaryOperator::isAdditiveOp(Op)) {
 474     SingleTy = ResultTy;
 475     if (LSym->getType() != SingleTy)
 476       return None;
 477   } else {
 478     // Don't rearrange other operations.
 479     return None;
 480   }
 481
 482   assert(!SingleTy.isNull() && "We should have figured out the type by now!");
 483
 484   // Rearrange signed symbolic expressions only
 485   if (!SingleTy->isSignedIntegerOrEnumerationType())
 486     return None;
 487
 488   SymbolRef RSym = Rhs.getAsSymbol();
 489   if (!RSym || RSym->getType() != SingleTy)
 490     return None;
 491
 492   BasicValueFactory &BV = State->getBasicVals();
 493   llvm::APSInt LInt, RInt;
 494   std::tie(LSym, LInt) = decomposeSymbol(LSym, BV);
 495   std::tie(RSym, RInt) = decomposeSymbol(RSym, BV);
 496   if (!shouldRearrange(State, Op, LSym, LInt, SingleTy) ||
 497       !shouldRearrange(State, Op, RSym, RInt, SingleTy))
 498     return None;
 499
 500   // We know that no overflows can occur anymore.
 501   return doRearrangeUnchecked(State, Op, LSym, LInt, RSym, RInt);
 502 }
 503
 504 SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
 505                                   BinaryOperator::Opcode op,
 506                                   NonLoc lhs, NonLoc rhs,
 507                                   QualType resultTy)  {
 508   NonLoc InputLHS = lhs;
 509   NonLoc InputRHS = rhs;
 510
 511   // Handle trivial case where left-side and right-side are the same.
 512   if (lhs == rhs)
 513     switch (op) {
 514       default:
 515         break;
 516       case BO_EQ:
 517       case BO_LE:
 518       case BO_GE:
 519         return makeTruthVal(true, resultTy);
 520       case BO_LT:
 521       case BO_GT:
 522       case BO_NE:
 523         return makeTruthVal(false, resultTy);
 524       case BO_Xor:
 525       case BO_Sub:
 526         if (resultTy->isIntegralOrEnumerationType())
 527           return makeIntVal(0, resultTy);
 528         return evalCastFromNonLoc(makeIntVal(0, /*isUnsigned=*/false), resultTy);
 529       case BO_Or:
 530       case BO_And:
 531         return evalCastFromNonLoc(lhs, resultTy);
 532     }
 533
 534   while (1) {
 535     switch (lhs.getSubKind()) {
 536     default:
 537       return makeSymExprValNN(op, lhs, rhs, resultTy);
 538     case nonloc::PointerToMemberKind: {
 539       assert(rhs.getSubKind() == nonloc::PointerToMemberKind &&
 540              "Both SVals should have pointer-to-member-type");
 541       auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
 542            RPTM = rhs.castAs<nonloc::PointerToMember>();
 543       auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
 544       switch (op) {
 545         case BO_EQ:
 546           return makeTruthVal(LPTMD == RPTMD, resultTy);
 547         case BO_NE:
 548           return makeTruthVal(LPTMD != RPTMD, resultTy);
 549         default:
 550           return UnknownVal();
 551       }
 552     }
 553     case nonloc::LocAsIntegerKind: {
 554       Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
 555       switch (rhs.getSubKind()) {
 556         case nonloc::LocAsIntegerKind:
 557           // FIXME: at the moment the implementation
 558           // of modeling "pointers as integers" is not complete.
 559           if (!BinaryOperator::isComparisonOp(op))
 560             return UnknownVal();
 561           return evalBinOpLL(state, op, lhsL,
 562                              rhs.castAs<nonloc::LocAsInteger>().getLoc(),
 563                              resultTy);
 564         case nonloc::ConcreteIntKind: {
 565           // FIXME: at the moment the implementation
 566           // of modeling "pointers as integers" is not complete.
 567           if (!BinaryOperator::isComparisonOp(op))
 568             return UnknownVal();
 569           // Transform the integer into a location and compare.
 570           // FIXME: This only makes sense for comparisons. If we want to, say,
 571           // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
 572           // then pack it back into a LocAsInteger.
 573           llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
 574           // If the region has a symbolic base, pay attention to the type; it
 575           // might be coming from a non-default address space. For non-symbolic
 576           // regions it doesn't matter that much because such comparisons would
 577           // most likely evaluate to concrete false anyway. FIXME: We might
 578           // still need to handle the non-comparison case.
 579           if (SymbolRef lSym = lhs.getAsLocSymbol(true))
 580             BasicVals.getAPSIntType(lSym->getType()).apply(i);
 581           else
 582             BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
 583           return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
 584         }
 585         default:
 586           switch (op) {
 587             case BO_EQ:
 588               return makeTruthVal(false, resultTy);
 589             case BO_NE:
 590               return makeTruthVal(true, resultTy);
 591             default:
 592               // This case also handles pointer arithmetic.
 593               return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
 594           }
 595       }
 596     }
 597     case nonloc::ConcreteIntKind: {
 598       llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
 599
 600       // If we're dealing with two known constants, just perform the operation.
 601       if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
 602         llvm::APSInt RHSValue = *KnownRHSValue;
 603         if (BinaryOperator::isComparisonOp(op)) {
 604           // We're looking for a type big enough to compare the two values.
 605           // FIXME: This is not correct. char + short will result in a promotion
 606           // to int. Unfortunately we have lost types by this point.
 607           APSIntType CompareType = std::max(APSIntType(LHSValue),
 608                                             APSIntType(RHSValue));
 609           CompareType.apply(LHSValue);
 610           CompareType.apply(RHSValue);
 611         } else if (!BinaryOperator::isShiftOp(op)) {
 612           APSIntType IntType = BasicVals.getAPSIntType(resultTy);
 613           IntType.apply(LHSValue);
 614           IntType.apply(RHSValue);
 615         }
 616
 617         const llvm::APSInt *Result =
 618           BasicVals.evalAPSInt(op, LHSValue, RHSValue);
 619         if (!Result)
 620           return UndefinedVal();
 621
 622         return nonloc::ConcreteInt(*Result);
 623       }
 624
 625       // Swap the left and right sides and flip the operator if doing so
 626       // allows us to better reason about the expression (this is a form
 627       // of expression canonicalization).
 628       // While we're at it, catch some special cases for non-commutative ops.
 629       switch (op) {
 630       case BO_LT:
 631       case BO_GT:
 632       case BO_LE:
 633       case BO_GE:
 634         op = BinaryOperator::reverseComparisonOp(op);
 635         LLVM_FALLTHROUGH;
 636       case BO_EQ:
 637       case BO_NE:
 638       case BO_Add:
 639       case BO_Mul:
 640       case BO_And:
 641       case BO_Xor:
 642       case BO_Or:
 643         std::swap(lhs, rhs);
 644         continue;
 645       case BO_Shr:
 646         // (~0)>>a
 647         if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
 648           return evalCastFromNonLoc(lhs, resultTy);
 649         LLVM_FALLTHROUGH;
 650       case BO_Shl:
 651         // 0<<a and 0>>a
 652         if (LHSValue == 0)
 653           return evalCastFromNonLoc(lhs, resultTy);
 654         return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
 655       default:
 656         return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
 657       }
 658     }
 659     case nonloc::SymbolValKind: {
 660       // We only handle LHS as simple symbols or SymIntExprs.
 661       SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
 662
 663       // LHS is a symbolic expression.
 664       if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
 665
 666         // Is this a logical not? (!x is represented as x == 0.)
 667         if (op == BO_EQ && rhs.isZeroConstant()) {
 668           // We know how to negate certain expressions. Simplify them here.
 669
 670           BinaryOperator::Opcode opc = symIntExpr->getOpcode();
 671           switch (opc) {
 672           default:
 673             // We don't know how to negate this operation.
 674             // Just handle it as if it were a normal comparison to 0.
 675             break;
 676           case BO_LAnd:
 677           case BO_LOr:
 678             llvm_unreachable("Logical operators handled by branching logic.");
 679           case BO_Assign:
 680           case BO_MulAssign:
 681           case BO_DivAssign:
 682           case BO_RemAssign:
 683           case BO_AddAssign:
 684           case BO_SubAssign:
 685           case BO_ShlAssign:
 686           case BO_ShrAssign:
 687           case BO_AndAssign:
 688           case BO_XorAssign:
 689           case BO_OrAssign:
 690           case BO_Comma:
 691             llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
 692           case BO_PtrMemD:
 693           case BO_PtrMemI:
 694             llvm_unreachable("Pointer arithmetic not handled here.");
 695           case BO_LT:
 696           case BO_GT:
 697           case BO_LE:
 698           case BO_GE:
 699           case BO_EQ:
 700           case BO_NE:
 701             assert(resultTy->isBooleanType() ||
 702                    resultTy == getConditionType());
 703             assert(symIntExpr->getType()->isBooleanType() ||
 704                    getContext().hasSameUnqualifiedType(symIntExpr->getType(),
 705                                                        getConditionType()));
 706             // Negate the comparison and make a value.
 707             opc = BinaryOperator::negateComparisonOp(opc);
 708             return makeNonLoc(symIntExpr->getLHS(), opc,
 709                 symIntExpr->getRHS(), resultTy);
 710           }
 711         }
 712
 713         // For now, only handle expressions whose RHS is a constant.
 714         if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
 715           // If both the LHS and the current expression are additive,
 716           // fold their constants and try again.
 717           if (BinaryOperator::isAdditiveOp(op)) {
 718             BinaryOperator::Opcode lop = symIntExpr->getOpcode();
 719             if (BinaryOperator::isAdditiveOp(lop)) {
 720               // Convert the two constants to a common type, then combine them.
 721
 722               // resultTy may not be the best type to convert to, but it's
 723               // probably the best choice in expressions with mixed type
 724               // (such as x+1U+2LL). The rules for implicit conversions should
 725               // choose a reasonable type to preserve the expression, and will
 726               // at least match how the value is going to be used.
 727               APSIntType IntType = BasicVals.getAPSIntType(resultTy);
 728               const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
 729               const llvm::APSInt &second = IntType.convert(*RHSValue);
 730
 731               const llvm::APSInt *newRHS;
 732               if (lop == op)
 733                 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
 734               else
 735                 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
 736
 737               assert(newRHS && "Invalid operation despite common type!");
 738               rhs = nonloc::ConcreteInt(*newRHS);
 739               lhs = nonloc::SymbolVal(symIntExpr->getLHS());
 740               op = lop;
 741               continue;
 742             }
 743           }
 744
 745           // Otherwise, make a SymIntExpr out of the expression.
 746           return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
 747         }
 748       }
 749
 750       // Does the symbolic expression simplify to a constant?
 751       // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
 752       // and try again.
 753       SVal simplifiedLhs = simplifySVal(state, lhs);
 754       if (simplifiedLhs != lhs)
 755         if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>()) {
 756           lhs = *simplifiedLhsAsNonLoc;
 757           continue;
 758         }
 759
 760       // Is the RHS a constant?
 761       if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
 762         return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
 763
 764       if (Optional<NonLoc> V = tryRearrange(state, op, lhs, rhs, resultTy))
 765         return *V;
 766
 767       // Give up -- this is not a symbolic expression we can handle.
 768       return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
 769     }
 770     }
 771   }
 772 }
 773
 774 static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
 775                                             const FieldRegion *RightFR,
 776                                             BinaryOperator::Opcode op,
 777                                             QualType resultTy,
 778                                             SimpleSValBuilder &SVB) {
 779   // Only comparisons are meaningful here!
 780   if (!BinaryOperator::isComparisonOp(op))
 781     return UnknownVal();
 782
 783   // Next, see if the two FRs have the same super-region.
 784   // FIXME: This doesn't handle casts yet, and simply stripping the casts
 785   // doesn't help.
 786   if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
 787     return UnknownVal();
 788
 789   const FieldDecl *LeftFD = LeftFR->getDecl();
 790   const FieldDecl *RightFD = RightFR->getDecl();
 791   const RecordDecl *RD = LeftFD->getParent();
 792
 793   // Make sure the two FRs are from the same kind of record. Just in case!
 794   // FIXME: This is probably where inheritance would be a problem.
 795   if (RD != RightFD->getParent())
 796     return UnknownVal();
 797
 798   // We know for sure that the two fields are not the same, since that
 799   // would have given us the same SVal.
 800   if (op == BO_EQ)
 801     return SVB.makeTruthVal(false, resultTy);
 802   if (op == BO_NE)
 803     return SVB.makeTruthVal(true, resultTy);
 804
 805   // Iterate through the fields and see which one comes first.
 806   // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
 807   // members and the units in which bit-fields reside have addresses that
 808   // increase in the order in which they are declared."
 809   bool leftFirst = (op == BO_LT || op == BO_LE);
 810   for (const auto *I : RD->fields()) {
 811     if (I == LeftFD)
 812       return SVB.makeTruthVal(leftFirst, resultTy);
 813     if (I == RightFD)
 814       return SVB.makeTruthVal(!leftFirst, resultTy);
 815   }
 816
 817   llvm_unreachable("Fields not found in parent record's definition");
 818 }
 819
 820 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 821 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
 822                                   BinaryOperator::Opcode op,
 823                                   Loc lhs, Loc rhs,
 824                                   QualType resultTy) {
 825   // Only comparisons and subtractions are valid operations on two pointers.
 826   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
 827   // However, if a pointer is casted to an integer, evalBinOpNN may end up
 828   // calling this function with another operation (PR7527). We don't attempt to
 829   // model this for now, but it could be useful, particularly when the
 830   // "location" is actually an integer value that's been passed through a void*.
 831   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
 832     return UnknownVal();
 833
 834   // Special cases for when both sides are identical.
 835   if (lhs == rhs) {
 836     switch (op) {
 837     default:
 838       llvm_unreachable("Unimplemented operation for two identical values");
 839     case BO_Sub:
 840       return makeZeroVal(resultTy);
 841     case BO_EQ:
 842     case BO_LE:
 843     case BO_GE:
 844       return makeTruthVal(true, resultTy);
 845     case BO_NE:
 846     case BO_LT:
 847     case BO_GT:
 848       return makeTruthVal(false, resultTy);
 849     }
 850   }
 851
 852   switch (lhs.getSubKind()) {
 853   default:
 854     llvm_unreachable("Ordering not implemented for this Loc.");
 855
 856   case loc::GotoLabelKind:
 857     // The only thing we know about labels is that they're non-null.
 858     if (rhs.isZeroConstant()) {
 859       switch (op) {
 860       default:
 861         break;
 862       case BO_Sub:
 863         return evalCastFromLoc(lhs, resultTy);
 864       case BO_EQ:
 865       case BO_LE:
 866       case BO_LT:
 867         return makeTruthVal(false, resultTy);
 868       case BO_NE:
 869       case BO_GT:
 870       case BO_GE:
 871         return makeTruthVal(true, resultTy);
 872       }
 873     }
 874     // There may be two labels for the same location, and a function region may
 875     // have the same address as a label at the start of the function (depending
 876     // on the ABI).
 877     // FIXME: we can probably do a comparison against other MemRegions, though.
 878     // FIXME: is there a way to tell if two labels refer to the same location?
 879     return UnknownVal();
 880
 881   case loc::ConcreteIntKind: {
 882     // If one of the operands is a symbol and the other is a constant,
 883     // build an expression for use by the constraint manager.
 884     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
 885       // We can only build expressions with symbols on the left,
 886       // so we need a reversible operator.
 887       if (!BinaryOperator::isComparisonOp(op) || op == BO_Cmp)
 888         return UnknownVal();
 889
 890       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
 891       op = BinaryOperator::reverseComparisonOp(op);
 892       return makeNonLoc(rSym, op, lVal, resultTy);
 893     }
 894
 895     // If both operands are constants, just perform the operation.
 896     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 897       SVal ResultVal =
 898           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
 899       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
 900         return evalCastFromNonLoc(*Result, resultTy);
 901
 902       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
 903       return UnknownVal();
 904     }
 905
 906     // Special case comparisons against NULL.
 907     // This must come after the test if the RHS is a symbol, which is used to
 908     // build constraints. The address of any non-symbolic region is guaranteed
 909     // to be non-NULL, as is any label.
 910     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
 911     if (lhs.isZeroConstant()) {
 912       switch (op) {
 913       default:
 914         break;
 915       case BO_EQ:
 916       case BO_GT:
 917       case BO_GE:
 918         return makeTruthVal(false, resultTy);
 919       case BO_NE:
 920       case BO_LT:
 921       case BO_LE:
 922         return makeTruthVal(true, resultTy);
 923       }
 924     }
 925
 926     // Comparing an arbitrary integer to a region or label address is
 927     // completely unknowable.
 928     return UnknownVal();
 929   }
 930   case loc::MemRegionValKind: {
 931     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 932       // If one of the operands is a symbol and the other is a constant,
 933       // build an expression for use by the constraint manager.
 934       if (SymbolRef lSym = lhs.getAsLocSymbol(true)) {
 935         if (BinaryOperator::isComparisonOp(op))
 936           return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
 937         return UnknownVal();
 938       }
 939       // Special case comparisons to NULL.
 940       // This must come after the test if the LHS is a symbol, which is used to
 941       // build constraints. The address of any non-symbolic region is guaranteed
 942       // to be non-NULL.
 943       if (rInt->isZeroConstant()) {
 944         if (op == BO_Sub)
 945           return evalCastFromLoc(lhs, resultTy);
 946
 947         if (BinaryOperator::isComparisonOp(op)) {
 948           QualType boolType = getContext().BoolTy;
 949           NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
 950           NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
 951           return evalBinOpNN(state, op, l, r, resultTy);
 952         }
 953       }
 954
 955       // Comparing a region to an arbitrary integer is completely unknowable.
 956       return UnknownVal();
 957     }
 958
 959     // Get both values as regions, if possible.
 960     const MemRegion *LeftMR = lhs.getAsRegion();
 961     assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
 962
 963     const MemRegion *RightMR = rhs.getAsRegion();
 964     if (!RightMR)
 965       // The RHS is probably a label, which in theory could address a region.
 966       // FIXME: we can probably make a more useful statement about non-code
 967       // regions, though.
 968       return UnknownVal();
 969
 970     const MemRegion *LeftBase = LeftMR->getBaseRegion();
 971     const MemRegion *RightBase = RightMR->getBaseRegion();
 972     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
 973     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
 974     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
 975
 976     // If the two regions are from different known memory spaces they cannot be
 977     // equal. Also, assume that no symbolic region (whose memory space is
 978     // unknown) is on the stack.
 979     if (LeftMS != RightMS &&
 980         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
 981          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
 982       switch (op) {
 983       default:
 984         return UnknownVal();
 985       case BO_EQ:
 986         return makeTruthVal(false, resultTy);
 987       case BO_NE:
 988         return makeTruthVal(true, resultTy);
 989       }
 990     }
 991
 992     // If both values wrap regions, see if they're from different base regions.
 993     // Note, heap base symbolic regions are assumed to not alias with
 994     // each other; for example, we assume that malloc returns different address
 995     // on each invocation.
 996     // FIXME: ObjC object pointers always reside on the heap, but currently
 997     // we treat their memory space as unknown, because symbolic pointers
 998     // to ObjC objects may alias. There should be a way to construct
 999     // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
1000     // guesses memory space for ObjC object pointers manually instead of
1001     // relying on us.
1002     if (LeftBase != RightBase &&
1003         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
1004          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
1005       switch (op) {
1006       default:
1007         return UnknownVal();
1008       case BO_EQ:
1009         return makeTruthVal(false, resultTy);
1010       case BO_NE:
1011         return makeTruthVal(true, resultTy);
1012       }
1013     }
1014
1015     // Handle special cases for when both regions are element regions.
1016     const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
1017     const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
1018     if (RightER && LeftER) {
1019       // Next, see if the two ERs have the same super-region and matching types.
1020       // FIXME: This should do something useful even if the types don't match,
1021       // though if both indexes are constant the RegionRawOffset path will
1022       // give the correct answer.
1023       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
1024           LeftER->getElementType() == RightER->getElementType()) {
1025         // Get the left index and cast it to the correct type.
1026         // If the index is unknown or undefined, bail out here.
1027         SVal LeftIndexVal = LeftER->getIndex();
1028         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
1029         if (!LeftIndex)
1030           return UnknownVal();
1031         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
1032         LeftIndex = LeftIndexVal.getAs<NonLoc>();
1033         if (!LeftIndex)
1034           return UnknownVal();
1035
1036         // Do the same for the right index.
1037         SVal RightIndexVal = RightER->getIndex();
1038         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
1039         if (!RightIndex)
1040           return UnknownVal();
1041         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
1042         RightIndex = RightIndexVal.getAs<NonLoc>();
1043         if (!RightIndex)
1044           return UnknownVal();
1045
1046         // Actually perform the operation.
1047         // evalBinOpNN expects the two indexes to already be the right type.
1048         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
1049       }
1050     }
1051
1052     // Special handling of the FieldRegions, even with symbolic offsets.
1053     const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
1054     const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
1055     if (RightFR && LeftFR) {
1056       SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
1057                                                *this);
1058       if (!R.isUnknown())
1059         return R;
1060     }
1061
1062     // Compare the regions using the raw offsets.
1063     RegionOffset LeftOffset = LeftMR->getAsOffset();
1064     RegionOffset RightOffset = RightMR->getAsOffset();
1065
1066     if (LeftOffset.getRegion() != nullptr &&
1067         LeftOffset.getRegion() == RightOffset.getRegion() &&
1068         !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
1069       int64_t left = LeftOffset.getOffset();
1070       int64_t right = RightOffset.getOffset();
1071
1072       switch (op) {
1073         default:
1074           return UnknownVal();
1075         case BO_LT:
1076           return makeTruthVal(left < right, resultTy);
1077         case BO_GT:
1078           return makeTruthVal(left > right, resultTy);
1079         case BO_LE:
1080           return makeTruthVal(left <= right, resultTy);
1081         case BO_GE:
1082           return makeTruthVal(left >= right, resultTy);
1083         case BO_EQ:
1084           return makeTruthVal(left == right, resultTy);
1085         case BO_NE:
1086           return makeTruthVal(left != right, resultTy);
1087       }
1088     }
1089
1090     // At this point we're not going to get a good answer, but we can try
1091     // conjuring an expression instead.
1092     SymbolRef LHSSym = lhs.getAsLocSymbol();
1093     SymbolRef RHSSym = rhs.getAsLocSymbol();
1094     if (LHSSym && RHSSym)
1095       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
1096
1097     // If we get here, we have no way of comparing the regions.
1098     return UnknownVal();
1099   }
1100   }
1101 }
1102
1103 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
1104                                   BinaryOperator::Opcode op,
1105                                   Loc lhs, NonLoc rhs, QualType resultTy) {
1106   if (op >= BO_PtrMemD && op <= BO_PtrMemI) {
1107     if (auto PTMSV = rhs.getAs<nonloc::PointerToMember>()) {
1108       if (PTMSV->isNullMemberPointer())
1109         return UndefinedVal();
1110       if (const FieldDecl *FD = PTMSV->getDeclAs<FieldDecl>()) {
1111         SVal Result = lhs;
1112
1113         for (const auto &I : *PTMSV)
1114           Result = StateMgr.getStoreManager().evalDerivedToBase(
1115               Result, I->getType(),I->isVirtual());
1116         return state->getLValue(FD, Result);
1117       }
1118     }
1119
1120     return rhs;
1121   }
1122
1123   assert(!BinaryOperator::isComparisonOp(op) &&
1124          "arguments to comparison ops must be of the same type");
1125
1126   // Special case: rhs is a zero constant.
1127   if (rhs.isZeroConstant())
1128     return lhs;
1129
1130   // Perserve the null pointer so that it can be found by the DerefChecker.
1131   if (lhs.isZeroConstant())
1132     return lhs;
1133
1134   // We are dealing with pointer arithmetic.
1135
1136   // Handle pointer arithmetic on constant values.
1137   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
1138     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
1139       const llvm::APSInt &leftI = lhsInt->getValue();
1140       assert(leftI.isUnsigned());
1141       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
1142
1143       // Convert the bitwidth of rightI.  This should deal with overflow
1144       // since we are dealing with concrete values.
1145       rightI = rightI.extOrTrunc(leftI.getBitWidth());
1146
1147       // Offset the increment by the pointer size.
1148       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
1149       QualType pointeeType = resultTy->getPointeeType();
1150       Multiplicand = getContext().getTypeSizeInChars(pointeeType).getQuantity();
1151       rightI *= Multiplicand;
1152
1153       // Compute the adjusted pointer.
1154       switch (op) {
1155         case BO_Add:
1156           rightI = leftI + rightI;
1157           break;
1158         case BO_Sub:
1159           rightI = leftI - rightI;
1160           break;
1161         default:
1162           llvm_unreachable("Invalid pointer arithmetic operation");
1163       }
1164       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
1165     }
1166   }
1167
1168   // Handle cases where 'lhs' is a region.
1169   if (const MemRegion *region = lhs.getAsRegion()) {
1170     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
1171     SVal index = UnknownVal();
1172     const SubRegion *superR = nullptr;
1173     // We need to know the type of the pointer in order to add an integer to it.
1174     // Depending on the type, different amount of bytes is added.
1175     QualType elementType;
1176
1177     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
1178       assert(op == BO_Add || op == BO_Sub);
1179       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
1180                           getArrayIndexType());
1181       superR = cast<SubRegion>(elemReg->getSuperRegion());
1182       elementType = elemReg->getElementType();
1183     }
1184     else if (isa<SubRegion>(region)) {
1185       assert(op == BO_Add || op == BO_Sub);
1186       index = (op == BO_Add) ? rhs : evalMinus(rhs);
1187       superR = cast<SubRegion>(region);
1188       // TODO: Is this actually reliable? Maybe improving our MemRegion
1189       // hierarchy to provide typed regions for all non-void pointers would be
1190       // better. For instance, we cannot extend this towards LocAsInteger
1191       // operations, where result type of the expression is integer.
1192       if (resultTy->isAnyPointerType())
1193         elementType = resultTy->getPointeeType();
1194     }
1195
1196     // Represent arithmetic on void pointers as arithmetic on char pointers.
1197     // It is fine when a TypedValueRegion of char value type represents
1198     // a void pointer. Note that arithmetic on void pointers is a GCC extension.
1199     if (elementType->isVoidType())
1200       elementType = getContext().CharTy;
1201
1202     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
1203       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
1204                                                        superR, getContext()));
1205     }
1206   }
1207   return UnknownVal();
1208 }
1209
1210 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
1211                                                    SVal V) {
1212   V = simplifySVal(state, V);
1213   if (V.isUnknownOrUndef())
1214     return nullptr;
1215
1216   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
1217     return &X->getValue();
1218
1219   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
1220     return &X->getValue();
1221
1222   if (SymbolRef Sym = V.getAsSymbol())
1223     return state->getConstraintManager().getSymVal(state, Sym);
1224
1225   // FIXME: Add support for SymExprs.
1226   return nullptr;
1227 }
1228
1229 SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
1230   // For now, this function tries to constant-fold symbols inside a
1231   // nonloc::SymbolVal, and does nothing else. More simplifications should
1232   // be possible, such as constant-folding an index in an ElementRegion.
1233
1234   class Simplifier : public FullSValVisitor<Simplifier, SVal> {
1235     ProgramStateRef State;
1236     SValBuilder &SVB;
1237
1238     // Cache results for the lifetime of the Simplifier. Results change every
1239     // time new constraints are added to the program state, which is the whole
1240     // point of simplifying, and for that very reason it's pointless to maintain
1241     // the same cache for the duration of the whole analysis.
1242     llvm::DenseMap<SymbolRef, SVal> Cached;
1243
1244     static bool isUnchanged(SymbolRef Sym, SVal Val) {
1245       return Sym == Val.getAsSymbol();
1246     }
1247
1248     SVal cache(SymbolRef Sym, SVal V) {
1249       Cached[Sym] = V;
1250       return V;
1251     }
1252
1253     SVal skip(SymbolRef Sym) {
1254       return cache(Sym, SVB.makeSymbolVal(Sym));
1255     }
1256
1257   public:
1258     Simplifier(ProgramStateRef State)
1259         : State(State), SVB(State->getStateManager().getSValBuilder()) {}
1260
1261     SVal VisitSymbolData(const SymbolData *S) {
1262       // No cache here.
1263       if (const llvm::APSInt *I =
1264               SVB.getKnownValue(State, SVB.makeSymbolVal(S)))
1265         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
1266                                             : (SVal)SVB.makeIntVal(*I);
1267       return SVB.makeSymbolVal(S);
1268     }
1269
1270     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
1271     // start producing them.
1272
1273     SVal VisitSymIntExpr(const SymIntExpr *S) {
1274       auto I = Cached.find(S);
1275       if (I != Cached.end())
1276         return I->second;
1277
1278       SVal LHS = Visit(S->getLHS());
1279       if (isUnchanged(S->getLHS(), LHS))
1280         return skip(S);
1281
1282       SVal RHS;
1283       // By looking at the APSInt in the right-hand side of S, we cannot
1284       // figure out if it should be treated as a Loc or as a NonLoc.
1285       // So make our guess by recalling that we cannot multiply pointers
1286       // or compare a pointer to an integer.
1287       if (Loc::isLocType(S->getLHS()->getType()) &&
1288           BinaryOperator::isComparisonOp(S->getOpcode())) {
1289         // The usual conversion of $sym to &SymRegion{$sym}, as they have
1290         // the same meaning for Loc-type symbols, but the latter form
1291         // is preferred in SVal computations for being Loc itself.
1292         if (SymbolRef Sym = LHS.getAsSymbol()) {
1293           assert(Loc::isLocType(Sym->getType()));
1294           LHS = SVB.makeLoc(Sym);
1295         }
1296         RHS = SVB.makeIntLocVal(S->getRHS());
1297       } else {
1298         RHS = SVB.makeIntVal(S->getRHS());
1299       }
1300
1301       return cache(
1302           S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
1303     }
1304
1305     SVal VisitSymSymExpr(const SymSymExpr *S) {
1306       auto I = Cached.find(S);
1307       if (I != Cached.end())
1308         return I->second;
1309
1310       // For now don't try to simplify mixed Loc/NonLoc expressions
1311       // because they often appear from LocAsInteger operations
1312       // and we don't know how to combine a LocAsInteger
1313       // with a concrete value.
1314       if (Loc::isLocType(S->getLHS()->getType()) !=
1315           Loc::isLocType(S->getRHS()->getType()))
1316         return skip(S);
1317
1318       SVal LHS = Visit(S->getLHS());
1319       SVal RHS = Visit(S->getRHS());
1320       if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))
1321         return skip(S);
1322
1323       return cache(
1324           S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
1325     }
1326
1327     SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
1328
1329     SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
1330
1331     SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
1332       // Simplification is much more costly than computing complexity.
1333       // For high complexity, it may be not worth it.
1334       return Visit(V.getSymbol());
1335     }
1336
1337     SVal VisitSVal(SVal V) { return V; }
1338   };
1339
1340   // A crude way of preventing this function from calling itself from evalBinOp.
1341   static bool isReentering = false;
1342   if (isReentering)
1343     return V;
1344
1345   isReentering = true;
1346   SVal SimplifiedV = Simplifier(State).Visit(V);
1347   isReentering = false;
1348
1349   return SimplifiedV;
1350 }