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