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   virtual SVal dispatchCast(SVal val, QualType castTy);
  25   virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy);
  26   virtual SVal evalCastFromLoc(Loc val, QualType castTy);
  27
  28 public:
  29   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
  30                     ProgramStateManager &stateMgr)
  31                     : SValBuilder(alloc, context, stateMgr) {}
  32   virtual ~SimpleSValBuilder() {}
  33
  34   virtual SVal evalMinus(NonLoc val);
  35   virtual SVal evalComplement(NonLoc val);
  36   virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
  37                            NonLoc lhs, NonLoc rhs, QualType resultTy);
  38   virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
  39                            Loc lhs, Loc rhs, QualType resultTy);
  40   virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
  41                            Loc lhs, NonLoc rhs, QualType resultTy);
  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   virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V);
  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 (RecordDecl::field_iterator I = RD->field_begin(),
 573        E = RD->field_end(); I!=E; ++I) {
 574     if (*I == LeftFD)
 575       return SVB.makeTruthVal(leftFirst, resultTy);
 576     if (*I == RightFD)
 577       return SVB.makeTruthVal(!leftFirst, resultTy);
 578   }
 579
 580   llvm_unreachable("Fields not found in parent record's definition");
 581 }
 582
 583 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 584 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
 585                                   BinaryOperator::Opcode op,
 586                                   Loc lhs, Loc rhs,
 587                                   QualType resultTy) {
 588   // Only comparisons and subtractions are valid operations on two pointers.
 589   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
 590   // However, if a pointer is casted to an integer, evalBinOpNN may end up
 591   // calling this function with another operation (PR7527). We don't attempt to
 592   // model this for now, but it could be useful, particularly when the
 593   // "location" is actually an integer value that's been passed through a void*.
 594   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
 595     return UnknownVal();
 596
 597   // Special cases for when both sides are identical.
 598   if (lhs == rhs) {
 599     switch (op) {
 600     default:
 601       llvm_unreachable("Unimplemented operation for two identical values");
 602     case BO_Sub:
 603       return makeZeroVal(resultTy);
 604     case BO_EQ:
 605     case BO_LE:
 606     case BO_GE:
 607       return makeTruthVal(true, resultTy);
 608     case BO_NE:
 609     case BO_LT:
 610     case BO_GT:
 611       return makeTruthVal(false, resultTy);
 612     }
 613   }
 614
 615   switch (lhs.getSubKind()) {
 616   default:
 617     llvm_unreachable("Ordering not implemented for this Loc.");
 618
 619   case loc::GotoLabelKind:
 620     // The only thing we know about labels is that they're non-null.
 621     if (rhs.isZeroConstant()) {
 622       switch (op) {
 623       default:
 624         break;
 625       case BO_Sub:
 626         return evalCastFromLoc(lhs, resultTy);
 627       case BO_EQ:
 628       case BO_LE:
 629       case BO_LT:
 630         return makeTruthVal(false, resultTy);
 631       case BO_NE:
 632       case BO_GT:
 633       case BO_GE:
 634         return makeTruthVal(true, resultTy);
 635       }
 636     }
 637     // There may be two labels for the same location, and a function region may
 638     // have the same address as a label at the start of the function (depending
 639     // on the ABI).
 640     // FIXME: we can probably do a comparison against other MemRegions, though.
 641     // FIXME: is there a way to tell if two labels refer to the same location?
 642     return UnknownVal();
 643
 644   case loc::ConcreteIntKind: {
 645     // If one of the operands is a symbol and the other is a constant,
 646     // build an expression for use by the constraint manager.
 647     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
 648       // We can only build expressions with symbols on the left,
 649       // so we need a reversible operator.
 650       if (!BinaryOperator::isComparisonOp(op))
 651         return UnknownVal();
 652
 653       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
 654       op = BinaryOperator::reverseComparisonOp(op);
 655       return makeNonLoc(rSym, op, lVal, resultTy);
 656     }
 657
 658     // If both operands are constants, just perform the operation.
 659     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 660       SVal ResultVal =
 661           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
 662       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
 663         return evalCastFromNonLoc(*Result, resultTy);
 664
 665       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
 666       return UnknownVal();
 667     }
 668
 669     // Special case comparisons against NULL.
 670     // This must come after the test if the RHS is a symbol, which is used to
 671     // build constraints. The address of any non-symbolic region is guaranteed
 672     // to be non-NULL, as is any label.
 673     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
 674     if (lhs.isZeroConstant()) {
 675       switch (op) {
 676       default:
 677         break;
 678       case BO_EQ:
 679       case BO_GT:
 680       case BO_GE:
 681         return makeTruthVal(false, resultTy);
 682       case BO_NE:
 683       case BO_LT:
 684       case BO_LE:
 685         return makeTruthVal(true, resultTy);
 686       }
 687     }
 688
 689     // Comparing an arbitrary integer to a region or label address is
 690     // completely unknowable.
 691     return UnknownVal();
 692   }
 693   case loc::MemRegionKind: {
 694     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 695       // If one of the operands is a symbol and the other is a constant,
 696       // build an expression for use by the constraint manager.
 697       if (SymbolRef lSym = lhs.getAsLocSymbol(true))
 698         return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
 699
 700       // Special case comparisons to NULL.
 701       // This must come after the test if the LHS is a symbol, which is used to
 702       // build constraints. The address of any non-symbolic region is guaranteed
 703       // to be non-NULL.
 704       if (rInt->isZeroConstant()) {
 705         if (op == BO_Sub)
 706           return evalCastFromLoc(lhs, resultTy);
 707
 708         if (BinaryOperator::isComparisonOp(op)) {
 709           QualType boolType = getContext().BoolTy;
 710           NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
 711           NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
 712           return evalBinOpNN(state, op, l, r, resultTy);
 713         }
 714       }
 715
 716       // Comparing a region to an arbitrary integer is completely unknowable.
 717       return UnknownVal();
 718     }
 719
 720     // Get both values as regions, if possible.
 721     const MemRegion *LeftMR = lhs.getAsRegion();
 722     assert(LeftMR && "MemRegionKind SVal doesn't have a region!");
 723
 724     const MemRegion *RightMR = rhs.getAsRegion();
 725     if (!RightMR)
 726       // The RHS is probably a label, which in theory could address a region.
 727       // FIXME: we can probably make a more useful statement about non-code
 728       // regions, though.
 729       return UnknownVal();
 730
 731     const MemRegion *LeftBase = LeftMR->getBaseRegion();
 732     const MemRegion *RightBase = RightMR->getBaseRegion();
 733     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
 734     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
 735     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
 736
 737     // If the two regions are from different known memory spaces they cannot be
 738     // equal. Also, assume that no symbolic region (whose memory space is
 739     // unknown) is on the stack.
 740     if (LeftMS != RightMS &&
 741         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
 742          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
 743       switch (op) {
 744       default:
 745         return UnknownVal();
 746       case BO_EQ:
 747         return makeTruthVal(false, resultTy);
 748       case BO_NE:
 749         return makeTruthVal(true, resultTy);
 750       }
 751     }
 752
 753     // If both values wrap regions, see if they're from different base regions.
 754     // Note, heap base symbolic regions are assumed to not alias with
 755     // each other; for example, we assume that malloc returns different address
 756     // on each invocation.
 757     if (LeftBase != RightBase &&
 758         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
 759          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
 760       switch (op) {
 761       default:
 762         return UnknownVal();
 763       case BO_EQ:
 764         return makeTruthVal(false, resultTy);
 765       case BO_NE:
 766         return makeTruthVal(true, resultTy);
 767       }
 768     }
 769
 770     // Handle special cases for when both regions are element regions.
 771     const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
 772     const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
 773     if (RightER && LeftER) {
 774       // Next, see if the two ERs have the same super-region and matching types.
 775       // FIXME: This should do something useful even if the types don't match,
 776       // though if both indexes are constant the RegionRawOffset path will
 777       // give the correct answer.
 778       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
 779           LeftER->getElementType() == RightER->getElementType()) {
 780         // Get the left index and cast it to the correct type.
 781         // If the index is unknown or undefined, bail out here.
 782         SVal LeftIndexVal = LeftER->getIndex();
 783         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
 784         if (!LeftIndex)
 785           return UnknownVal();
 786         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
 787         LeftIndex = LeftIndexVal.getAs<NonLoc>();
 788         if (!LeftIndex)
 789           return UnknownVal();
 790
 791         // Do the same for the right index.
 792         SVal RightIndexVal = RightER->getIndex();
 793         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
 794         if (!RightIndex)
 795           return UnknownVal();
 796         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
 797         RightIndex = RightIndexVal.getAs<NonLoc>();
 798         if (!RightIndex)
 799           return UnknownVal();
 800
 801         // Actually perform the operation.
 802         // evalBinOpNN expects the two indexes to already be the right type.
 803         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
 804       }
 805     }
 806
 807     // Special handling of the FieldRegions, even with symbolic offsets.
 808     const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
 809     const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
 810     if (RightFR && LeftFR) {
 811       SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
 812                                                *this);
 813       if (!R.isUnknown())
 814         return R;
 815     }
 816
 817     // Compare the regions using the raw offsets.
 818     RegionOffset LeftOffset = LeftMR->getAsOffset();
 819     RegionOffset RightOffset = RightMR->getAsOffset();
 820
 821     if (LeftOffset.getRegion() != NULL &&
 822         LeftOffset.getRegion() == RightOffset.getRegion() &&
 823         !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
 824       int64_t left = LeftOffset.getOffset();
 825       int64_t right = RightOffset.getOffset();
 826
 827       switch (op) {
 828         default:
 829           return UnknownVal();
 830         case BO_LT:
 831           return makeTruthVal(left < right, resultTy);
 832         case BO_GT:
 833           return makeTruthVal(left > right, resultTy);
 834         case BO_LE:
 835           return makeTruthVal(left <= right, resultTy);
 836         case BO_GE:
 837           return makeTruthVal(left >= right, resultTy);
 838         case BO_EQ:
 839           return makeTruthVal(left == right, resultTy);
 840         case BO_NE:
 841           return makeTruthVal(left != right, resultTy);
 842       }
 843     }
 844
 845     // At this point we're not going to get a good answer, but we can try
 846     // conjuring an expression instead.
 847     SymbolRef LHSSym = lhs.getAsLocSymbol();
 848     SymbolRef RHSSym = rhs.getAsLocSymbol();
 849     if (LHSSym && RHSSym)
 850       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
 851
 852     // If we get here, we have no way of comparing the regions.
 853     return UnknownVal();
 854   }
 855   }
 856 }
 857
 858 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
 859                                   BinaryOperator::Opcode op,
 860                                   Loc lhs, NonLoc rhs, QualType resultTy) {
 861   assert(!BinaryOperator::isComparisonOp(op) &&
 862          "arguments to comparison ops must be of the same type");
 863
 864   // Special case: rhs is a zero constant.
 865   if (rhs.isZeroConstant())
 866     return lhs;
 867
 868   // We are dealing with pointer arithmetic.
 869
 870   // Handle pointer arithmetic on constant values.
 871   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
 872     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
 873       const llvm::APSInt &leftI = lhsInt->getValue();
 874       assert(leftI.isUnsigned());
 875       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
 876
 877       // Convert the bitwidth of rightI.  This should deal with overflow
 878       // since we are dealing with concrete values.
 879       rightI = rightI.extOrTrunc(leftI.getBitWidth());
 880
 881       // Offset the increment by the pointer size.
 882       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
 883       rightI *= Multiplicand;
 884
 885       // Compute the adjusted pointer.
 886       switch (op) {
 887         case BO_Add:
 888           rightI = leftI + rightI;
 889           break;
 890         case BO_Sub:
 891           rightI = leftI - rightI;
 892           break;
 893         default:
 894           llvm_unreachable("Invalid pointer arithmetic operation");
 895       }
 896       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
 897     }
 898   }
 899
 900   // Handle cases where 'lhs' is a region.
 901   if (const MemRegion *region = lhs.getAsRegion()) {
 902     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
 903     SVal index = UnknownVal();
 904     const MemRegion *superR = 0;
 905     QualType elementType;
 906
 907     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
 908       assert(op == BO_Add || op == BO_Sub);
 909       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
 910                           getArrayIndexType());
 911       superR = elemReg->getSuperRegion();
 912       elementType = elemReg->getElementType();
 913     }
 914     else if (isa<SubRegion>(region)) {
 915       superR = region;
 916       index = rhs;
 917       if (resultTy->isAnyPointerType())
 918         elementType = resultTy->getPointeeType();
 919     }
 920
 921     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
 922       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
 923                                                        superR, getContext()));
 924     }
 925   }
 926   return UnknownVal();
 927 }
 928
 929 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
 930                                                    SVal V) {
 931   if (V.isUnknownOrUndef())
 932     return NULL;
 933
 934   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
 935     return &X->getValue();
 936
 937   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
 938     return &X->getValue();
 939
 940   if (SymbolRef Sym = V.getAsSymbol())
 941     return state->getConstraintManager().getSymVal(state, Sym);
 942
 943   // FIXME: Add support for SymExprs.
 944   return NULL;
 945 }