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