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