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