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   if (castTy->isIntegralOrEnumerationType()) {
 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             assert(resultTy->isBooleanType() ||
 442                    resultTy == getConditionType());
 443             assert(symIntExpr->getType()->isBooleanType() ||
 444                    getContext().hasSameUnqualifiedType(symIntExpr->getType(),
 445                                                        getConditionType()));
 446             // Negate the comparison and make a value.
 447             opc = BinaryOperator::negateComparisonOp(opc);
 448             return makeNonLoc(symIntExpr->getLHS(), opc,
 449                 symIntExpr->getRHS(), resultTy);
 450           }
 451         }
 452
 453         // For now, only handle expressions whose RHS is a constant.
 454         if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
 455           // If both the LHS and the current expression are additive,
 456           // fold their constants and try again.
 457           if (BinaryOperator::isAdditiveOp(op)) {
 458             BinaryOperator::Opcode lop = symIntExpr->getOpcode();
 459             if (BinaryOperator::isAdditiveOp(lop)) {
 460               // Convert the two constants to a common type, then combine them.
 461
 462               // resultTy may not be the best type to convert to, but it's
 463               // probably the best choice in expressions with mixed type
 464               // (such as x+1U+2LL). The rules for implicit conversions should
 465               // choose a reasonable type to preserve the expression, and will
 466               // at least match how the value is going to be used.
 467               APSIntType IntType = BasicVals.getAPSIntType(resultTy);
 468               const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
 469               const llvm::APSInt &second = IntType.convert(*RHSValue);
 470
 471               const llvm::APSInt *newRHS;
 472               if (lop == op)
 473                 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
 474               else
 475                 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
 476
 477               assert(newRHS && "Invalid operation despite common type!");
 478               rhs = nonloc::ConcreteInt(*newRHS);
 479               lhs = nonloc::SymbolVal(symIntExpr->getLHS());
 480               op = lop;
 481               continue;
 482             }
 483           }
 484
 485           // Otherwise, make a SymIntExpr out of the expression.
 486           return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
 487         }
 488       }
 489
 490       // Does the symbolic expression simplify to a constant?
 491       // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
 492       // and try again.
 493       ConstraintManager &CMgr = state->getConstraintManager();
 494       if (const llvm::APSInt *Constant = CMgr.getSymVal(state, Sym)) {
 495         lhs = nonloc::ConcreteInt(*Constant);
 496         continue;
 497       }
 498
 499       // Is the RHS a constant?
 500       if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
 501         return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
 502
 503       // Give up -- this is not a symbolic expression we can handle.
 504       return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
 505     }
 506     }
 507   }
 508 }
 509
 510 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 511 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
 512                                   BinaryOperator::Opcode op,
 513                                   Loc lhs, Loc rhs,
 514                                   QualType resultTy) {
 515   // Only comparisons and subtractions are valid operations on two pointers.
 516   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
 517   // However, if a pointer is casted to an integer, evalBinOpNN may end up
 518   // calling this function with another operation (PR7527). We don't attempt to
 519   // model this for now, but it could be useful, particularly when the
 520   // "location" is actually an integer value that's been passed through a void*.
 521   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
 522     return UnknownVal();
 523
 524   // Special cases for when both sides are identical.
 525   if (lhs == rhs) {
 526     switch (op) {
 527     default:
 528       llvm_unreachable("Unimplemented operation for two identical values");
 529     case BO_Sub:
 530       return makeZeroVal(resultTy);
 531     case BO_EQ:
 532     case BO_LE:
 533     case BO_GE:
 534       return makeTruthVal(true, resultTy);
 535     case BO_NE:
 536     case BO_LT:
 537     case BO_GT:
 538       return makeTruthVal(false, resultTy);
 539     }
 540   }
 541
 542   switch (lhs.getSubKind()) {
 543   default:
 544     llvm_unreachable("Ordering not implemented for this Loc.");
 545
 546   case loc::GotoLabelKind:
 547     // The only thing we know about labels is that they're non-null.
 548     if (rhs.isZeroConstant()) {
 549       switch (op) {
 550       default:
 551         break;
 552       case BO_Sub:
 553         return evalCastFromLoc(lhs, resultTy);
 554       case BO_EQ:
 555       case BO_LE:
 556       case BO_LT:
 557         return makeTruthVal(false, resultTy);
 558       case BO_NE:
 559       case BO_GT:
 560       case BO_GE:
 561         return makeTruthVal(true, resultTy);
 562       }
 563     }
 564     // There may be two labels for the same location, and a function region may
 565     // have the same address as a label at the start of the function (depending
 566     // on the ABI).
 567     // FIXME: we can probably do a comparison against other MemRegions, though.
 568     // FIXME: is there a way to tell if two labels refer to the same location?
 569     return UnknownVal();
 570
 571   case loc::ConcreteIntKind: {
 572     // If one of the operands is a symbol and the other is a constant,
 573     // build an expression for use by the constraint manager.
 574     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
 575       // We can only build expressions with symbols on the left,
 576       // so we need a reversible operator.
 577       if (!BinaryOperator::isComparisonOp(op))
 578         return UnknownVal();
 579
 580       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
 581       op = BinaryOperator::reverseComparisonOp(op);
 582       return makeNonLoc(rSym, op, lVal, resultTy);
 583     }
 584
 585     // If both operands are constants, just perform the operation.
 586     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 587       SVal ResultVal =
 588           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
 589       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
 590         return evalCastFromNonLoc(*Result, resultTy);
 591
 592       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
 593       return UnknownVal();
 594     }
 595
 596     // Special case comparisons against NULL.
 597     // This must come after the test if the RHS is a symbol, which is used to
 598     // build constraints. The address of any non-symbolic region is guaranteed
 599     // to be non-NULL, as is any label.
 600     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
 601     if (lhs.isZeroConstant()) {
 602       switch (op) {
 603       default:
 604         break;
 605       case BO_EQ:
 606       case BO_GT:
 607       case BO_GE:
 608         return makeTruthVal(false, resultTy);
 609       case BO_NE:
 610       case BO_LT:
 611       case BO_LE:
 612         return makeTruthVal(true, resultTy);
 613       }
 614     }
 615
 616     // Comparing an arbitrary integer to a region or label address is
 617     // completely unknowable.
 618     return UnknownVal();
 619   }
 620   case loc::MemRegionKind: {
 621     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
 622       // If one of the operands is a symbol and the other is a constant,
 623       // build an expression for use by the constraint manager.
 624       if (SymbolRef lSym = lhs.getAsLocSymbol())
 625         return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
 626
 627       // Special case comparisons to NULL.
 628       // This must come after the test if the LHS is a symbol, which is used to
 629       // build constraints. The address of any non-symbolic region is guaranteed
 630       // to be non-NULL.
 631       if (rInt->isZeroConstant()) {
 632         switch (op) {
 633         default:
 634           break;
 635         case BO_Sub:
 636           return evalCastFromLoc(lhs, resultTy);
 637         case BO_EQ:
 638         case BO_LT:
 639         case BO_LE:
 640           return makeTruthVal(false, resultTy);
 641         case BO_NE:
 642         case BO_GT:
 643         case BO_GE:
 644           return makeTruthVal(true, resultTy);
 645         }
 646       }
 647
 648       // Comparing a region to an arbitrary integer is completely unknowable.
 649       return UnknownVal();
 650     }
 651
 652     // Get both values as regions, if possible.
 653     const MemRegion *LeftMR = lhs.getAsRegion();
 654     assert(LeftMR && "MemRegionKind SVal doesn't have a region!");
 655
 656     const MemRegion *RightMR = rhs.getAsRegion();
 657     if (!RightMR)
 658       // The RHS is probably a label, which in theory could address a region.
 659       // FIXME: we can probably make a more useful statement about non-code
 660       // regions, though.
 661       return UnknownVal();
 662
 663     const MemRegion *LeftBase = LeftMR->getBaseRegion();
 664     const MemRegion *RightBase = RightMR->getBaseRegion();
 665     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
 666     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
 667     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
 668
 669     // If the two regions are from different known memory spaces they cannot be
 670     // equal. Also, assume that no symbolic region (whose memory space is
 671     // unknown) is on the stack.
 672     if (LeftMS != RightMS &&
 673         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
 674          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
 675       switch (op) {
 676       default:
 677         return UnknownVal();
 678       case BO_EQ:
 679         return makeTruthVal(false, resultTy);
 680       case BO_NE:
 681         return makeTruthVal(true, resultTy);
 682       }
 683     }
 684
 685     // If both values wrap regions, see if they're from different base regions.
 686     // Note, heap base symbolic regions are assumed to not alias with
 687     // each other; for example, we assume that malloc returns different address
 688     // on each invocation.
 689     if (LeftBase != RightBase &&
 690         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
 691          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
 692       switch (op) {
 693       default:
 694         return UnknownVal();
 695       case BO_EQ:
 696         return makeTruthVal(false, resultTy);
 697       case BO_NE:
 698         return makeTruthVal(true, resultTy);
 699       }
 700     }
 701
 702     // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this
 703     // ElementRegion path and the FieldRegion path below should be unified.
 704     if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) {
 705       // First see if the right region is also an ElementRegion.
 706       const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
 707       if (!RightER)
 708         return UnknownVal();
 709
 710       // Next, see if the two ERs have the same super-region and matching types.
 711       // FIXME: This should do something useful even if the types don't match,
 712       // though if both indexes are constant the RegionRawOffset path will
 713       // give the correct answer.
 714       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
 715           LeftER->getElementType() == RightER->getElementType()) {
 716         // Get the left index and cast it to the correct type.
 717         // If the index is unknown or undefined, bail out here.
 718         SVal LeftIndexVal = LeftER->getIndex();
 719         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
 720         if (!LeftIndex)
 721           return UnknownVal();
 722         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
 723         LeftIndex = LeftIndexVal.getAs<NonLoc>();
 724         if (!LeftIndex)
 725           return UnknownVal();
 726
 727         // Do the same for the right index.
 728         SVal RightIndexVal = RightER->getIndex();
 729         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
 730         if (!RightIndex)
 731           return UnknownVal();
 732         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
 733         RightIndex = RightIndexVal.getAs<NonLoc>();
 734         if (!RightIndex)
 735           return UnknownVal();
 736
 737         // Actually perform the operation.
 738         // evalBinOpNN expects the two indexes to already be the right type.
 739         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
 740       }
 741
 742       // If the element indexes aren't comparable, see if the raw offsets are.
 743       RegionRawOffset LeftOffset = LeftER->getAsArrayOffset();
 744       RegionRawOffset RightOffset = RightER->getAsArrayOffset();
 745
 746       if (LeftOffset.getRegion() != NULL &&
 747           LeftOffset.getRegion() == RightOffset.getRegion()) {
 748         CharUnits left = LeftOffset.getOffset();
 749         CharUnits right = RightOffset.getOffset();
 750
 751         switch (op) {
 752         default:
 753           return UnknownVal();
 754         case BO_LT:
 755           return makeTruthVal(left < right, resultTy);
 756         case BO_GT:
 757           return makeTruthVal(left > right, resultTy);
 758         case BO_LE:
 759           return makeTruthVal(left <= right, resultTy);
 760         case BO_GE:
 761           return makeTruthVal(left >= right, resultTy);
 762         case BO_EQ:
 763           return makeTruthVal(left == right, resultTy);
 764         case BO_NE:
 765           return makeTruthVal(left != right, resultTy);
 766         }
 767       }
 768
 769       // If we get here, we have no way of comparing the ElementRegions.
 770     }
 771
 772     // See if both regions are fields of the same structure.
 773     // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars.
 774     if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) {
 775       // Only comparisons are meaningful here!
 776       if (!BinaryOperator::isComparisonOp(op))
 777         return UnknownVal();
 778
 779       // First see if the right region is also a FieldRegion.
 780       const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
 781       if (!RightFR)
 782         return UnknownVal();
 783
 784       // Next, see if the two FRs have the same super-region.
 785       // FIXME: This doesn't handle casts yet, and simply stripping the casts
 786       // doesn't help.
 787       if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
 788         return UnknownVal();
 789
 790       const FieldDecl *LeftFD = LeftFR->getDecl();
 791       const FieldDecl *RightFD = RightFR->getDecl();
 792       const RecordDecl *RD = LeftFD->getParent();
 793
 794       // Make sure the two FRs are from the same kind of record. Just in case!
 795       // FIXME: This is probably where inheritance would be a problem.
 796       if (RD != RightFD->getParent())
 797         return UnknownVal();
 798
 799       // We know for sure that the two fields are not the same, since that
 800       // would have given us the same SVal.
 801       if (op == BO_EQ)
 802         return makeTruthVal(false, resultTy);
 803       if (op == BO_NE)
 804         return makeTruthVal(true, resultTy);
 805
 806       // Iterate through the fields and see which one comes first.
 807       // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
 808       // members and the units in which bit-fields reside have addresses that
 809       // increase in the order in which they are declared."
 810       bool leftFirst = (op == BO_LT || op == BO_LE);
 811       for (RecordDecl::field_iterator I = RD->field_begin(),
 812            E = RD->field_end(); I!=E; ++I) {
 813         if (*I == LeftFD)
 814           return makeTruthVal(leftFirst, resultTy);
 815         if (*I == RightFD)
 816           return makeTruthVal(!leftFirst, resultTy);
 817       }
 818
 819       llvm_unreachable("Fields not found in parent record's definition");
 820     }
 821
 822     // At this point we're not going to get a good answer, but we can try
 823     // conjuring an expression instead.
 824     SymbolRef LHSSym = lhs.getAsLocSymbol();
 825     SymbolRef RHSSym = rhs.getAsLocSymbol();
 826     if (LHSSym && RHSSym)
 827       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
 828
 829     // If we get here, we have no way of comparing the regions.
 830     return UnknownVal();
 831   }
 832   }
 833 }
 834
 835 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
 836                                   BinaryOperator::Opcode op,
 837                                   Loc lhs, NonLoc rhs, QualType resultTy) {
 838
 839   // Special case: rhs is a zero constant.
 840   if (rhs.isZeroConstant())
 841     return lhs;
 842
 843   // Special case: 'rhs' is an integer that has the same width as a pointer and
 844   // we are using the integer location in a comparison.  Normally this cannot be
 845   // triggered, but transfer functions like those for OSCompareAndSwapBarrier32
 846   // can generate comparisons that trigger this code.
 847   // FIXME: Are all locations guaranteed to have pointer width?
 848   if (BinaryOperator::isComparisonOp(op)) {
 849     if (Optional<nonloc::ConcreteInt> rhsInt =
 850             rhs.getAs<nonloc::ConcreteInt>()) {
 851       const llvm::APSInt *x = &rhsInt->getValue();
 852       ASTContext &ctx = Context;
 853       if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) {
 854         // Convert the signedness of the integer (if necessary).
 855         if (x->isSigned())
 856           x = &getBasicValueFactory().getValue(*x, true);
 857
 858         return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy);
 859       }
 860     }
 861     return UnknownVal();
 862   }
 863
 864   // We are dealing with pointer arithmetic.
 865
 866   // Handle pointer arithmetic on constant values.
 867   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
 868     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
 869       const llvm::APSInt &leftI = lhsInt->getValue();
 870       assert(leftI.isUnsigned());
 871       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
 872
 873       // Convert the bitwidth of rightI.  This should deal with overflow
 874       // since we are dealing with concrete values.
 875       rightI = rightI.extOrTrunc(leftI.getBitWidth());
 876
 877       // Offset the increment by the pointer size.
 878       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
 879       rightI *= Multiplicand;
 880
 881       // Compute the adjusted pointer.
 882       switch (op) {
 883         case BO_Add:
 884           rightI = leftI + rightI;
 885           break;
 886         case BO_Sub:
 887           rightI = leftI - rightI;
 888           break;
 889         default:
 890           llvm_unreachable("Invalid pointer arithmetic operation");
 891       }
 892       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
 893     }
 894   }
 895
 896   // Handle cases where 'lhs' is a region.
 897   if (const MemRegion *region = lhs.getAsRegion()) {
 898     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
 899     SVal index = UnknownVal();
 900     const MemRegion *superR = 0;
 901     QualType elementType;
 902
 903     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
 904       assert(op == BO_Add || op == BO_Sub);
 905       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
 906                           getArrayIndexType());
 907       superR = elemReg->getSuperRegion();
 908       elementType = elemReg->getElementType();
 909     }
 910     else if (isa<SubRegion>(region)) {
 911       superR = region;
 912       index = rhs;
 913       if (resultTy->isAnyPointerType())
 914         elementType = resultTy->getPointeeType();
 915     }
 916
 917     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
 918       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
 919                                                        superR, getContext()));
 920     }
 921   }
 922   return UnknownVal();
 923 }
 924
 925 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
 926                                                    SVal V) {
 927   if (V.isUnknownOrUndef())
 928     return NULL;
 929
 930   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
 931     return &X->getValue();
 932
 933   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
 934     return &X->getValue();
 935
 936   if (SymbolRef Sym = V.getAsSymbol())
 937     return state->getConstraintManager().getSymVal(state, Sym);
 938
 939   // FIXME: Add support for SymExprs.
 940   return NULL;
 941 }