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