lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

   1 // SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- 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 SimpleSValBuilder, a basic implementation of SValBuilder.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
  18
  19 using namespace clang;
  20 using namespace ento;
  21
  22 namespace {
  23 class SimpleSValBuilder : public SValBuilder {
  24 protected:
  25   SVal dispatchCast(SVal val, QualType castTy) override;
  26   SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override;
  27   SVal evalCastFromLoc(Loc val, QualType castTy) override;
  28
  29 public:
  30   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
  31                     ProgramStateManager &stateMgr)
  32                     : SValBuilder(alloc, context, stateMgr) {}
  33   ~SimpleSValBuilder() override {}
  34
  35   SVal evalMinus(NonLoc val) override;
  36   SVal evalComplement(NonLoc val) override;
  37   SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
  38                    NonLoc lhs, NonLoc rhs, QualType resultTy) override;
  39   SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
  40                    Loc lhs, Loc rhs, QualType resultTy) override;
  41   SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
  42                    Loc lhs, NonLoc rhs, QualType resultTy) override;
  43
  44   /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
  45   ///  (integer) value, that value is returned. Otherwise, returns NULL.
  46   const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
  47
  48   /// Recursively descends into symbolic expressions and replaces symbols
  49   /// with their known values (in the sense of the getKnownValue() method).
  50   SVal simplifySVal(ProgramStateRef State, SVal V) override;
  51
  52   SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
  53                      const llvm::APSInt &RHS, QualType resultTy);
  54 };
  55 } // end anonymous namespace
  56
  57 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
  58                                            ASTContext &context,
  59                                            ProgramStateManager &stateMgr) {
  60   return new SimpleSValBuilder(alloc, context, stateMgr);
  61 }
  62
  63 //===----------------------------------------------------------------------===//
  64 // Transfer function for Casts.
  65 //===----------------------------------------------------------------------===//
  66
  67 SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
  68   assert(Val.getAs<Loc>() || Val.getAs<NonLoc>());
  69   return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy)
  70                            : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy);
  71 }
  72
  73 SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
  74
  75   bool isLocType = Loc::isLocType(castTy);
  76
  77   if (val.getAs<nonloc::PointerToMember>())
  78     return val;
  79
  80   if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) {
  81     if (isLocType)
  82       return LI->getLoc();
  83
  84     // FIXME: Correctly support promotions/truncations.
  85     unsigned castSize = Context.getTypeSize(castTy);
  86     if (castSize == LI->getNumBits())
  87       return val;
  88     return makeLocAsInteger(LI->getLoc(), castSize);
  89   }
  90
  91   if (const SymExpr *se = val.getAsSymbolicExpression()) {
  92     QualType T = Context.getCanonicalType(se->getType());
  93     // If types are the same or both are integers, ignore the cast.
  94     // FIXME: Remove this hack when we support symbolic truncation/extension.
  95     // HACK: If both castTy and T are integers, ignore the cast.  This is
  96     // not a permanent solution.  Eventually we want to precisely handle
  97     // extension/truncation of symbolic integers.  This prevents us from losing
  98     // precision when we assign 'x = y' and 'y' is symbolic and x and y are
  99     // different integer types.
 100    if (haveSameType(T, castTy))
 101       return val;
 102
 103     if (!isLocType)
 104       return makeNonLoc(se, T, castTy);
 105     return UnknownVal();
 106   }
 107
 108   // If value is a non-integer constant, produce unknown.
 109   if (!val.getAs<nonloc::ConcreteInt>())
 110     return UnknownVal();
 111
 112   // Handle casts to a boolean type.
 113   if (castTy->isBooleanType()) {
 114     bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue();
 115     return makeTruthVal(b, castTy);
 116   }
 117
 118   // Only handle casts from integers to integers - if val is an integer constant
 119   // being cast to a non-integer type, produce unknown.
 120   if (!isLocType && !castTy->isIntegralOrEnumerationType())
 121     return UnknownVal();
 122
 123   llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue();
 124   BasicVals.getAPSIntType(castTy).apply(i);
 125
 126   if (isLocType)
 127     return makeIntLocVal(i);
 128   else
 129     return makeIntVal(i);
 130 }
 131
 132 SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
 133
 134   // Casts from pointers -> pointers, just return the lval.
 135   //
 136   // Casts from pointers -> references, just return the lval.  These
 137   //   can be introduced by the frontend for corner cases, e.g
 138   //   casting from va_list* to __builtin_va_list&.
 139   //
 140   if (Loc::isLocType(castTy) || castTy->isReferenceType())
 141     return val;
 142
 143   // FIXME: Handle transparent unions where a value can be "transparently"
 144   //  lifted into a union type.
 145   if (castTy->isUnionType())
 146     return UnknownVal();
 147
 148   // Casting a Loc to a bool will almost always be true,
 149   // unless this is a weak function or a symbolic region.
 150   if (castTy->isBooleanType()) {
 151     switch (val.getSubKind()) {
 152       case loc::MemRegionValKind: {
 153         const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion();
 154         if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
 155           if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
 156             if (FD->isWeak())
 157               // FIXME: Currently we are using an extent symbol here,
 158               // because there are no generic region address metadata
 159               // symbols to use, only content metadata.
 160               return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
 161
 162         if (const SymbolicRegion *SymR = R->getSymbolicBase())
 163           return nonloc::SymbolVal(SymR->getSymbol());
 164
 165         // FALL-THROUGH
 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.getTypeSize(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 SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
 313                                   BinaryOperator::Opcode op,
 314                                   NonLoc lhs, NonLoc rhs,
 315                                   QualType resultTy)  {
 316   NonLoc InputLHS = lhs;
 317   NonLoc InputRHS = rhs;
 318
 319   // Handle trivial case where left-side and right-side are the same.
 320   if (lhs == rhs)
 321     switch (op) {
 322       default:
 323         break;
 324       case BO_EQ:
 325       case BO_LE:
 326       case BO_GE:
 327         return makeTruthVal(true, resultTy);
 328       case BO_LT:
 329       case BO_GT:
 330       case BO_NE:
 331         return makeTruthVal(false, resultTy);
 332       case BO_Xor:
 333       case BO_Sub:
 334         if (resultTy->isIntegralOrEnumerationType())
 335           return makeIntVal(0, resultTy);
 336         return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy);
 337       case BO_Or:
 338       case BO_And:
 339         return evalCastFromNonLoc(lhs, resultTy);
 340     }
 341
 342   while (1) {
 343     switch (lhs.getSubKind()) {
 344     default:
 345       return makeSymExprValNN(state, op, lhs, rhs, resultTy);
 346     case nonloc::PointerToMemberKind: {
 347       assert(rhs.getSubKind() == nonloc::PointerToMemberKind &&
 348              "Both SVals should have pointer-to-member-type");
 349       auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
 350            RPTM = rhs.castAs<nonloc::PointerToMember>();
 351       auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
 352       switch (op) {
 353         case BO_EQ:
 354           return makeTruthVal(LPTMD == RPTMD, resultTy);
 355         case BO_NE:
 356           return makeTruthVal(LPTMD != RPTMD, resultTy);
 357         default:
 358           return UnknownVal();
 359       }
 360     }
 361     case nonloc::LocAsIntegerKind: {
 362       Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
 363       switch (rhs.getSubKind()) {
 364         case nonloc::LocAsIntegerKind:
 365           return evalBinOpLL(state, op, lhsL,
 366                              rhs.castAs<nonloc::LocAsInteger>().getLoc(),
 367                              resultTy);
 368         case nonloc::ConcreteIntKind: {
 369           // Transform the integer into a location and compare.
 370           // FIXME: This only makes sense for comparisons. If we want to, say,
 371           // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
 372           // then pack it back into a LocAsInteger.
 373           llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
 374           BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
 375           return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
 376         }
 377         default:
 378           switch (op) {
 379             case BO_EQ:
 380               return makeTruthVal(false, resultTy);
 381             case BO_NE:
 382               return makeTruthVal(true, resultTy);
 383             default:
 384               // This case also handles pointer arithmetic.
 385               return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
 386           }
 387       }
 388     }
 389     case nonloc::ConcreteIntKind: {
 390       llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
 391
 392       // If we're dealing with two known constants, just perform the operation.
 393       if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
 394         llvm::APSInt RHSValue = *KnownRHSValue;
 395         if (BinaryOperator::isComparisonOp(op)) {
 396           // We're looking for a type big enough to compare the two values.
 397           // FIXME: This is not correct. char + short will result in a promotion
 398           // to int. Unfortunately we have lost types by this point.
 399           APSIntType CompareType = std::max(APSIntType(LHSValue),
 400                                             APSIntType(RHSValue));
 401           CompareType.apply(LHSValue);
 402           CompareType.apply(RHSValue);
 403         } else if (!BinaryOperator::isShiftOp(op)) {
 404           APSIntType IntType = BasicVals.getAPSIntType(resultTy);
 405           IntType.apply(LHSValue);
 406           IntType.apply(RHSValue);
 407         }
 408
 409         const llvm::APSInt *Result =
 410           BasicVals.evalAPSInt(op, LHSValue, RHSValue);
 411         if (!Result)
 412           return UndefinedVal();
 413
 414         return nonloc::ConcreteInt(*Result);
 415       }
 416
 417       // Swap the left and right sides and flip the operator if doing so
 418       // allows us to better reason about the expression (this is a form
 419       // of expression canonicalization).
 420       // While we're at it, catch some special cases for non-commutative ops.
 421       switch (op) {
 422       case BO_LT:
 423       case BO_GT:
 424       case BO_LE:
 425       case BO_GE:
 426         op = BinaryOperator::reverseComparisonOp(op);
 427         // FALL-THROUGH
 428       case BO_EQ:
 429       case BO_NE:
 430       case BO_Add:
 431       case BO_Mul:
 432       case BO_And:
 433       case BO_Xor:
 434       case BO_Or:
 435         std::swap(lhs, rhs);
 436         continue;
 437       case BO_Shr:
 438         // (~0)>>a
 439         if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
 440           return evalCastFromNonLoc(lhs, resultTy);
 441         // FALL-THROUGH
 442       case BO_Shl:
 443         // 0<<a and 0>>a
 444         if (LHSValue == 0)
 445           return evalCastFromNonLoc(lhs, resultTy);
 446         return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
 447       default:
 448         return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
 449       }
 450     }
 451     case nonloc::SymbolValKind: {
 452       // We only handle LHS as simple symbols or SymIntExprs.
 453       SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
 454
 455       // LHS is a symbolic expression.
 456       if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
 457
 458         // Is this a logical not? (!x is represented as x == 0.)
 459         if (op == BO_EQ && rhs.isZeroConstant()) {
 460           // We know how to negate certain expressions. Simplify them here.
 461
 462           BinaryOperator::Opcode opc = symIntExpr->getOpcode();
 463           switch (opc) {
 464           default:
 465             // We don't know how to negate this operation.
 466             // Just handle it as if it were a normal comparison to 0.
 467             break;
 468           case BO_LAnd:
 469           case BO_LOr:
 470             llvm_unreachable("Logical operators handled by branching logic.");
 471           case BO_Assign:
 472           case BO_MulAssign:
 473           case BO_DivAssign:
 474           case BO_RemAssign:
 475           case BO_AddAssign:
 476           case BO_SubAssign:
 477           case BO_ShlAssign:
 478           case BO_ShrAssign:
 479           case BO_AndAssign:
 480           case BO_XorAssign:
 481           case BO_OrAssign:
 482           case BO_Comma:
 483             llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
 484           case BO_PtrMemD:
 485           case BO_PtrMemI:
 486             llvm_unreachable("Pointer arithmetic not handled here.");
 487           case BO_LT:
 488           case BO_GT:
 489           case BO_LE:
 490           case BO_GE:
 491           case BO_EQ:
 492           case BO_NE:
 493             assert(resultTy->isBooleanType() ||
 494                    resultTy == getConditionType());
 495             assert(symIntExpr->getType()->isBooleanType() ||
 496                    getContext().hasSameUnqualifiedType(symIntExpr->getType(),
 497                                                        getConditionType()));
 498             // Negate the comparison and make a value.
 499             opc = BinaryOperator::negateComparisonOp(opc);
 500             return makeNonLoc(symIntExpr->getLHS(), opc,
 501                 symIntExpr->getRHS(), resultTy);
 502           }
 503         }
 504
 505         // For now, only handle expressions whose RHS is a constant.
 506         if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
 507           // If both the LHS and the current expression are additive,
 508           // fold their constants and try again.
 509           if (BinaryOperator::isAdditiveOp(op)) {
 510             BinaryOperator::Opcode lop = symIntExpr->getOpcode();
 511             if (BinaryOperator::isAdditiveOp(lop)) {
 512               // Convert the two constants to a common type, then combine them.
 513
 514               // resultTy may not be the best type to convert to, but it's
 515               // probably the best choice in expressions with mixed type
 516               // (such as x+1U+2LL). The rules for implicit conversions should
 517               // choose a reasonable type to preserve the expression, and will
 518               // at least match how the value is going to be used.
 519               APSIntType IntType = BasicVals.getAPSIntType(resultTy);
 520               const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
 521               const llvm::APSInt &second = IntType.convert(*RHSValue);
 522
 523               const llvm::APSInt *newRHS;
 524               if (lop == op)
 525                 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
 526               else
 527                 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
 528
 529               assert(newRHS && "Invalid operation despite common type!");
 530               rhs = nonloc::ConcreteInt(*newRHS);
 531               lhs = nonloc::SymbolVal(symIntExpr->getLHS());
 532               op = lop;
 533               continue;
 534             }
 535           }
 536
 537           // Otherwise, make a SymIntExpr out of the expression.
 538           return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
 539         }
 540       }
 541
 542       // Does the symbolic expression simplify to a constant?
 543       // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
 544       // and try again.
 545       SVal simplifiedLhs = simplifySVal(state, lhs);
 546       if (simplifiedLhs != lhs)
 547         if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>()) {
 548           lhs = *simplifiedLhsAsNonLoc;
 549           continue;
 550         }
 551
 552       // Is the RHS a constant?
 553       if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
 554         return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
 555
 556       // Give up -- this is not a symbolic expression we can handle.
 557       return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
 558     }
 559     }
 560   }
 561 }
 562
 563 static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
 564                                             const FieldRegion *RightFR,
 565                                             BinaryOperator::Opcode op,
 566                                             QualType resultTy,
 567                                             SimpleSValBuilder &SVB) {
 568   // Only comparisons are meaningful here!
 569   if (!BinaryOperator::isComparisonOp(op))
 570     return UnknownVal();
 571
 572   // Next, see if the two FRs have the same super-region.
 573   // FIXME: This doesn't handle casts yet, and simply stripping the casts
 574   // doesn't help.
 575   if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
 576     return UnknownVal();
 577
 578   const FieldDecl *LeftFD = LeftFR->getDecl();
 579   const FieldDecl *RightFD = RightFR->getDecl();
 580   const RecordDecl *RD = LeftFD->getParent();
 581
 582   // Make sure the two FRs are from the same kind of record. Just in case!
 583   // FIXME: This is probably where inheritance would be a problem.
 584   if (RD != RightFD->getParent())
 585     return UnknownVal();
 586
 587   // We know for sure that the two fields are not the same, since that
 588   // would have given us the same SVal.
 589   if (op == BO_EQ)
 590     return SVB.makeTruthVal(false, resultTy);
 591   if (op == BO_NE)
 592     return SVB.makeTruthVal(true, resultTy);
 593
 594   // Iterate through the fields and see which one comes first.
 595   // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
 596   // members and the units in which bit-fields reside have addresses that
 597   // increase in the order in which they are declared."
 598   bool leftFirst = (op == BO_LT || op == BO_LE);
 599   for (const auto *I : RD->fields()) {
 600     if (I == LeftFD)
 601       return SVB.makeTruthVal(leftFirst, resultTy);
 602     if (I == RightFD)
 603       return SVB.makeTruthVal(!leftFirst, resultTy);
 604   }
 605
 606   llvm_unreachable("Fields not found in parent record's definition");
 607 }
 608
 609 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 610 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
 611                                   BinaryOperator::Opcode op,
 612                                   Loc lhs, Loc rhs,
 613                                   QualType resultTy) {
 614   // Only comparisons and subtractions are valid operations on two pointers.
 615   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
 616   // However, if a pointer is casted to an integer, evalBinOpNN may end up
 617   // calling this function with another operation (PR7527). We don't attempt to
 618   // model this for now, but it could be useful, particularly when the
 619   // "location" is actually an integer value that's been passed through a void*.
 620   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
 621     return UnknownVal();
 622
 623   // Special cases for when both sides are identical.
 624   if (lhs == rhs) {
 625     switch (op) {
 626     default:
 627       llvm_unreachable("Unimplemented operation for two identical values");
 628     case BO_Sub:
 629       return makeZeroVal(resultTy);
 630     case BO_EQ:
 631     case BO_LE:
 632     case BO_GE:
 633       return makeTruthVal(true, resultTy);
 634     case BO_NE:
 635     case BO_LT:
 636     case BO_GT:
 637       return makeTruthVal(false, resultTy);
 638     }
 639   }
 640
 641   switch (lhs.getSubKind()) {
 642   default:
 643     llvm_unreachable("Ordering not implemented for this Loc.");
 644
 645   case loc::GotoLabelKind:
 646     // The only thing we know about labels is that they're non-null.
 647     if (rhs.isZeroConstant()) {
 648       switch (op) {
 649       default:
 650         break;
 651       case BO_Sub:
 652         return evalCastFromLoc(lhs, resultTy);
 653       case BO_EQ:
 654       case BO_LE:
 655       case BO_LT:
 656         return makeTruthVal(false, resultTy);
 657       case BO_NE:
 658       case BO_GT:
 659       case BO_GE:
 660         return makeTruthVal(true, resultTy);
 661       }
 662     }
 663     // There may be two labels for the same location, and a function region may
 664     // have the same address as a label at the start of the function (depending
 665     // on the ABI).
 666     // FIXME: we can probably do a comparison against other MemRegions, though.
 667     // FIXME: is there a way to tell if two labels refer to the same location?
 668     return UnknownVal();
 669
 670   case loc::ConcreteIntKind: {
 671     // If one of the operands is a symbol and the other is a constant,
 672     // build an expression for use by the constraint manager.
 673     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
 674       // We can only build expressions with symbols on the left,
 675       // so we need a reversible operator.
 676       if (!BinaryOperator::isComparisonOp(op))
 677         return UnknownVal();
 678
 679       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
 680       op = BinaryOperator::reverseComparisonOp(op);
 681       return makeNonLoc(rSym, op, lVal, resultTy);
 682     }
 683
 684     // If both operands are constants, just perform the operation.
 685     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 686       SVal ResultVal =
 687           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
 688       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
 689         return evalCastFromNonLoc(*Result, resultTy);
 690
 691       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
 692       return UnknownVal();
 693     }
 694
 695     // Special case comparisons against NULL.
 696     // This must come after the test if the RHS is a symbol, which is used to
 697     // build constraints. The address of any non-symbolic region is guaranteed
 698     // to be non-NULL, as is any label.
 699     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
 700     if (lhs.isZeroConstant()) {
 701       switch (op) {
 702       default:
 703         break;
 704       case BO_EQ:
 705       case BO_GT:
 706       case BO_GE:
 707         return makeTruthVal(false, resultTy);
 708       case BO_NE:
 709       case BO_LT:
 710       case BO_LE:
 711         return makeTruthVal(true, resultTy);
 712       }
 713     }
 714
 715     // Comparing an arbitrary integer to a region or label address is
 716     // completely unknowable.
 717     return UnknownVal();
 718   }
 719   case loc::MemRegionValKind: {
 720     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 721       // If one of the operands is a symbol and the other is a constant,
 722       // build an expression for use by the constraint manager.
 723       if (SymbolRef lSym = lhs.getAsLocSymbol(true))
 724         return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
 725
 726       // Special case comparisons to NULL.
 727       // This must come after the test if the LHS is a symbol, which is used to
 728       // build constraints. The address of any non-symbolic region is guaranteed
 729       // to be non-NULL.
 730       if (rInt->isZeroConstant()) {
 731         if (op == BO_Sub)
 732           return evalCastFromLoc(lhs, resultTy);
 733
 734         if (BinaryOperator::isComparisonOp(op)) {
 735           QualType boolType = getContext().BoolTy;
 736           NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
 737           NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
 738           return evalBinOpNN(state, op, l, r, resultTy);
 739         }
 740       }
 741
 742       // Comparing a region to an arbitrary integer is completely unknowable.
 743       return UnknownVal();
 744     }
 745
 746     // Get both values as regions, if possible.
 747     const MemRegion *LeftMR = lhs.getAsRegion();
 748     assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
 749
 750     const MemRegion *RightMR = rhs.getAsRegion();
 751     if (!RightMR)
 752       // The RHS is probably a label, which in theory could address a region.
 753       // FIXME: we can probably make a more useful statement about non-code
 754       // regions, though.
 755       return UnknownVal();
 756
 757     const MemRegion *LeftBase = LeftMR->getBaseRegion();
 758     const MemRegion *RightBase = RightMR->getBaseRegion();
 759     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
 760     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
 761     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
 762
 763     // If the two regions are from different known memory spaces they cannot be
 764     // equal. Also, assume that no symbolic region (whose memory space is
 765     // unknown) is on the stack.
 766     if (LeftMS != RightMS &&
 767         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
 768          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
 769       switch (op) {
 770       default:
 771         return UnknownVal();
 772       case BO_EQ:
 773         return makeTruthVal(false, resultTy);
 774       case BO_NE:
 775         return makeTruthVal(true, resultTy);
 776       }
 777     }
 778
 779     // If both values wrap regions, see if they're from different base regions.
 780     // Note, heap base symbolic regions are assumed to not alias with
 781     // each other; for example, we assume that malloc returns different address
 782     // on each invocation.
 783     // FIXME: ObjC object pointers always reside on the heap, but currently
 784     // we treat their memory space as unknown, because symbolic pointers
 785     // to ObjC objects may alias. There should be a way to construct
 786     // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
 787     // guesses memory space for ObjC object pointers manually instead of
 788     // relying on us.
 789     if (LeftBase != RightBase &&
 790         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
 791          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
 792       switch (op) {
 793       default:
 794         return UnknownVal();
 795       case BO_EQ:
 796         return makeTruthVal(false, resultTy);
 797       case BO_NE:
 798         return makeTruthVal(true, resultTy);
 799       }
 800     }
 801
 802     // Handle special cases for when both regions are element regions.
 803     const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
 804     const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
 805     if (RightER && LeftER) {
 806       // Next, see if the two ERs have the same super-region and matching types.
 807       // FIXME: This should do something useful even if the types don't match,
 808       // though if both indexes are constant the RegionRawOffset path will
 809       // give the correct answer.
 810       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
 811           LeftER->getElementType() == RightER->getElementType()) {
 812         // Get the left index and cast it to the correct type.
 813         // If the index is unknown or undefined, bail out here.
 814         SVal LeftIndexVal = LeftER->getIndex();
 815         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
 816         if (!LeftIndex)
 817           return UnknownVal();
 818         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
 819         LeftIndex = LeftIndexVal.getAs<NonLoc>();
 820         if (!LeftIndex)
 821           return UnknownVal();
 822
 823         // Do the same for the right index.
 824         SVal RightIndexVal = RightER->getIndex();
 825         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
 826         if (!RightIndex)
 827           return UnknownVal();
 828         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
 829         RightIndex = RightIndexVal.getAs<NonLoc>();
 830         if (!RightIndex)
 831           return UnknownVal();
 832
 833         // Actually perform the operation.
 834         // evalBinOpNN expects the two indexes to already be the right type.
 835         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
 836       }
 837     }
 838
 839     // Special handling of the FieldRegions, even with symbolic offsets.
 840     const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
 841     const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
 842     if (RightFR && LeftFR) {
 843       SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
 844                                                *this);
 845       if (!R.isUnknown())
 846         return R;
 847     }
 848
 849     // Compare the regions using the raw offsets.
 850     RegionOffset LeftOffset = LeftMR->getAsOffset();
 851     RegionOffset RightOffset = RightMR->getAsOffset();
 852
 853     if (LeftOffset.getRegion() != nullptr &&
 854         LeftOffset.getRegion() == RightOffset.getRegion() &&
 855         !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
 856       int64_t left = LeftOffset.getOffset();
 857       int64_t right = RightOffset.getOffset();
 858
 859       switch (op) {
 860         default:
 861           return UnknownVal();
 862         case BO_LT:
 863           return makeTruthVal(left < right, resultTy);
 864         case BO_GT:
 865           return makeTruthVal(left > right, resultTy);
 866         case BO_LE:
 867           return makeTruthVal(left <= right, resultTy);
 868         case BO_GE:
 869           return makeTruthVal(left >= right, resultTy);
 870         case BO_EQ:
 871           return makeTruthVal(left == right, resultTy);
 872         case BO_NE:
 873           return makeTruthVal(left != right, resultTy);
 874       }
 875     }
 876
 877     // At this point we're not going to get a good answer, but we can try
 878     // conjuring an expression instead.
 879     SymbolRef LHSSym = lhs.getAsLocSymbol();
 880     SymbolRef RHSSym = rhs.getAsLocSymbol();
 881     if (LHSSym && RHSSym)
 882       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
 883
 884     // If we get here, we have no way of comparing the regions.
 885     return UnknownVal();
 886   }
 887   }
 888 }
 889
 890 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
 891                                   BinaryOperator::Opcode op,
 892                                   Loc lhs, NonLoc rhs, QualType resultTy) {
 893   if (op >= BO_PtrMemD && op <= BO_PtrMemI) {
 894     if (auto PTMSV = rhs.getAs<nonloc::PointerToMember>()) {
 895       if (PTMSV->isNullMemberPointer())
 896         return UndefinedVal();
 897       if (const FieldDecl *FD = PTMSV->getDeclAs<FieldDecl>()) {
 898         SVal Result = lhs;
 899
 900         for (const auto &I : *PTMSV)
 901           Result = StateMgr.getStoreManager().evalDerivedToBase(
 902               Result, I->getType(),I->isVirtual());
 903         return state->getLValue(FD, Result);
 904       }
 905     }
 906
 907     return rhs;
 908   }
 909
 910   assert(!BinaryOperator::isComparisonOp(op) &&
 911          "arguments to comparison ops must be of the same type");
 912
 913   // Special case: rhs is a zero constant.
 914   if (rhs.isZeroConstant())
 915     return lhs;
 916
 917   // We are dealing with pointer arithmetic.
 918
 919   // Handle pointer arithmetic on constant values.
 920   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
 921     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
 922       const llvm::APSInt &leftI = lhsInt->getValue();
 923       assert(leftI.isUnsigned());
 924       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
 925
 926       // Convert the bitwidth of rightI.  This should deal with overflow
 927       // since we are dealing with concrete values.
 928       rightI = rightI.extOrTrunc(leftI.getBitWidth());
 929
 930       // Offset the increment by the pointer size.
 931       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
 932       rightI *= Multiplicand;
 933
 934       // Compute the adjusted pointer.
 935       switch (op) {
 936         case BO_Add:
 937           rightI = leftI + rightI;
 938           break;
 939         case BO_Sub:
 940           rightI = leftI - rightI;
 941           break;
 942         default:
 943           llvm_unreachable("Invalid pointer arithmetic operation");
 944       }
 945       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
 946     }
 947   }
 948
 949   // Handle cases where 'lhs' is a region.
 950   if (const MemRegion *region = lhs.getAsRegion()) {
 951     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
 952     SVal index = UnknownVal();
 953     const SubRegion *superR = nullptr;
 954     // We need to know the type of the pointer in order to add an integer to it.
 955     // Depending on the type, different amount of bytes is added.
 956     QualType elementType;
 957
 958     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
 959       assert(op == BO_Add || op == BO_Sub);
 960       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
 961                           getArrayIndexType());
 962       superR = cast<SubRegion>(elemReg->getSuperRegion());
 963       elementType = elemReg->getElementType();
 964     }
 965     else if (isa<SubRegion>(region)) {
 966       assert(op == BO_Add || op == BO_Sub);
 967       index = (op == BO_Add) ? rhs : evalMinus(rhs);
 968       superR = cast<SubRegion>(region);
 969       // TODO: Is this actually reliable? Maybe improving our MemRegion
 970       // hierarchy to provide typed regions for all non-void pointers would be
 971       // better. For instance, we cannot extend this towards LocAsInteger
 972       // operations, where result type of the expression is integer.
 973       if (resultTy->isAnyPointerType())
 974         elementType = resultTy->getPointeeType();
 975     }
 976
 977     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
 978       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
 979                                                        superR, getContext()));
 980     }
 981   }
 982   return UnknownVal();
 983 }
 984
 985 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
 986                                                    SVal V) {
 987   if (V.isUnknownOrUndef())
 988     return nullptr;
 989
 990   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
 991     return &X->getValue();
 992
 993   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
 994     return &X->getValue();
 995
 996   if (SymbolRef Sym = V.getAsSymbol())
 997     return state->getConstraintManager().getSymVal(state, Sym);
 998
 999   // FIXME: Add support for SymExprs.
1000   return nullptr;
1001 }
1002
1003 SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
1004   // For now, this function tries to constant-fold symbols inside a
1005   // nonloc::SymbolVal, and does nothing else. More simplifications should
1006   // be possible, such as constant-folding an index in an ElementRegion.
1007
1008   class Simplifier : public FullSValVisitor<Simplifier, SVal> {
1009     ProgramStateRef State;
1010     SValBuilder &SVB;
1011
1012   public:
1013     Simplifier(ProgramStateRef State)
1014         : State(State), SVB(State->getStateManager().getSValBuilder()) {}
1015
1016     SVal VisitSymbolData(const SymbolData *S) {
1017       if (const llvm::APSInt *I =
1018               SVB.getKnownValue(State, nonloc::SymbolVal(S)))
1019         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
1020                                             : (SVal)SVB.makeIntVal(*I);
1021       return nonloc::SymbolVal(S);
1022     }
1023
1024     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
1025     // start producing them.
1026
1027     SVal VisitSymIntExpr(const SymIntExpr *S) {
1028       SVal LHS = Visit(S->getLHS());
1029       SVal RHS;
1030       // By looking at the APSInt in the right-hand side of S, we cannot
1031       // figure out if it should be treated as a Loc or as a NonLoc.
1032       // So make our guess by recalling that we cannot multiply pointers
1033       // or compare a pointer to an integer.
1034       if (Loc::isLocType(S->getLHS()->getType()) &&
1035           BinaryOperator::isComparisonOp(S->getOpcode())) {
1036         // The usual conversion of $sym to &SymRegion{$sym}, as they have
1037         // the same meaning for Loc-type symbols, but the latter form
1038         // is preferred in SVal computations for being Loc itself.
1039         if (SymbolRef Sym = LHS.getAsSymbol()) {
1040           assert(Loc::isLocType(Sym->getType()));
1041           LHS = SVB.makeLoc(Sym);
1042         }
1043         RHS = SVB.makeIntLocVal(S->getRHS());
1044       } else {
1045         RHS = SVB.makeIntVal(S->getRHS());
1046       }
1047       return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
1048     }
1049
1050     SVal VisitSymSymExpr(const SymSymExpr *S) {
1051       SVal LHS = Visit(S->getLHS());
1052       SVal RHS = Visit(S->getRHS());
1053       return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
1054     }
1055
1056     SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
1057
1058     SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
1059
1060     SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
1061       // Simplification is much more costly than computing complexity.
1062       // For high complexity, it may be not worth it.
1063       if (V.getSymbol()->computeComplexity() > 100)
1064         return V;
1065       return Visit(V.getSymbol());
1066     }
1067
1068     SVal VisitSVal(SVal V) { return V; }
1069   };
1070
1071   return Simplifier(State).Visit(V);
1072 }