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 evalCastFromNonLoc(NonLoc val, QualType castTy);
  24   virtual SVal evalCastFromLoc(Loc val, QualType castTy);
  25
  26 public:
  27   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
  28                     ProgramStateManager &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 ProgramState *state, BinaryOperator::Opcode op,
  35                            NonLoc lhs, NonLoc rhs, QualType resultTy);
  36   virtual SVal evalBinOpLL(const ProgramState *state, BinaryOperator::Opcode op,
  37                            Loc lhs, Loc rhs, QualType resultTy);
  38   virtual SVal evalBinOpLN(const ProgramState *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 ProgramState *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                                            ProgramStateManager &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     llvm_unreachable("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     llvm_unreachable("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 ProgramState *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           llvm_unreachable("Logical operators handled by branching logic.");
 351         case BO_Assign:
 352         case BO_MulAssign:
 353         case BO_DivAssign:
 354         case BO_RemAssign:
 355         case BO_AddAssign:
 356         case BO_SubAssign:
 357         case BO_ShlAssign:
 358         case BO_ShrAssign:
 359         case BO_AndAssign:
 360         case BO_XorAssign:
 361         case BO_OrAssign:
 362         case BO_Comma:
 363           llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
 364         case BO_PtrMemD:
 365         case BO_PtrMemI:
 366           llvm_unreachable("Pointer arithmetic not handled here.");
 367         case BO_LT:
 368         case BO_GT:
 369         case BO_LE:
 370         case BO_GE:
 371         case BO_EQ:
 372         case BO_NE:
 373           // Negate the comparison and make a value.
 374           opc = NegateComparison(opc);
 375           assert(symIntExpr->getType(Context) == resultTy);
 376           return makeNonLoc(symIntExpr->getLHS(), opc,
 377                                    symIntExpr->getRHS(), resultTy);
 378         }
 379       }
 380
 381       // For now, only handle expressions whose RHS is a constant.
 382       const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs);
 383       if (!rhsInt)
 384         return UnknownVal();
 385
 386       // If both the LHS and the current expression are additive,
 387       // fold their constants.
 388       if (BinaryOperator::isAdditiveOp(op)) {
 389         BinaryOperator::Opcode lop = symIntExpr->getOpcode();
 390         if (BinaryOperator::isAdditiveOp(lop)) {
 391           // resultTy may not be the best type to convert to, but it's
 392           // probably the best choice in expressions with mixed type
 393           // (such as x+1U+2LL). The rules for implicit conversions should
 394           // choose a reasonable type to preserve the expression, and will
 395           // at least match how the value is going to be used.
 396           const llvm::APSInt &first =
 397             BasicVals.Convert(resultTy, symIntExpr->getRHS());
 398           const llvm::APSInt &second =
 399             BasicVals.Convert(resultTy, rhsInt->getValue());
 400           const llvm::APSInt *newRHS;
 401           if (lop == op)
 402             newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
 403           else
 404             newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
 405           return MakeSymIntVal(symIntExpr->getLHS(), lop, *newRHS, resultTy);
 406         }
 407       }
 408
 409       // Otherwise, make a SymExprVal out of the expression.
 410       return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy);
 411     }
 412     case nonloc::ConcreteIntKind: {
 413       const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs);
 414
 415       // Is the RHS a symbol we can simplify?
 416       // FIXME: This was mostly copy/pasted from the LHS-is-a-symbol case.
 417       if (const nonloc::SymbolVal *srhs = dyn_cast<nonloc::SymbolVal>(&rhs)) {
 418         SymbolRef RSym = srhs->getSymbol();
 419         if (RSym->getType(Context)->isIntegerType()) {
 420           if (const llvm::APSInt *Constant = state->getSymVal(RSym)) {
 421             // The symbol evaluates to a constant.
 422             const llvm::APSInt *rhs_I;
 423             if (BinaryOperator::isRelationalOp(op))
 424               rhs_I = &BasicVals.Convert(lhsInt.getValue(), *Constant);
 425             else
 426               rhs_I = &BasicVals.Convert(resultTy, *Constant);
 427
 428             rhs = nonloc::ConcreteInt(*rhs_I);
 429           }
 430         }
 431       }
 432
 433       if (isa<nonloc::ConcreteInt>(rhs)) {
 434         return lhsInt.evalBinOp(*this, op, cast<nonloc::ConcreteInt>(rhs));
 435       } else {
 436         const llvm::APSInt& lhsValue = lhsInt.getValue();
 437
 438         // Swap the left and right sides and flip the operator if doing so
 439         // allows us to better reason about the expression (this is a form
 440         // of expression canonicalization).
 441         // While we're at it, catch some special cases for non-commutative ops.
 442         NonLoc tmp = rhs;
 443         rhs = lhs;
 444         lhs = tmp;
 445
 446         switch (op) {
 447           case BO_LT:
 448           case BO_GT:
 449           case BO_LE:
 450           case BO_GE:
 451             op = ReverseComparison(op);
 452             continue;
 453           case BO_EQ:
 454           case BO_NE:
 455           case BO_Add:
 456           case BO_Mul:
 457           case BO_And:
 458           case BO_Xor:
 459           case BO_Or:
 460             continue;
 461           case BO_Shr:
 462             if (lhsValue.isAllOnesValue() && lhsValue.isSigned())
 463               // At this point lhs and rhs have been swapped.
 464               return rhs;
 465             // FALL-THROUGH
 466           case BO_Shl:
 467             if (lhsValue == 0)
 468               // At this point lhs and rhs have been swapped.
 469               return rhs;
 470             return UnknownVal();
 471           default:
 472             return UnknownVal();
 473         }
 474       }
 475     }
 476     case nonloc::SymbolValKind: {
 477       nonloc::SymbolVal *slhs = cast<nonloc::SymbolVal>(&lhs);
 478       SymbolRef Sym = slhs->getSymbol();
 479       QualType lhsType = Sym->getType(Context);
 480
 481       // The conversion type is usually the result type, but not in the case
 482       // of relational expressions.
 483       QualType conversionType = resultTy;
 484       if (BinaryOperator::isRelationalOp(op))
 485         conversionType = lhsType;
 486
 487       // Does the symbol simplify to a constant?  If so, "fold" the constant
 488       // by setting 'lhs' to a ConcreteInt and try again.
 489       if (lhsType->isIntegerType())
 490         if (const llvm::APSInt *Constant = state->getSymVal(Sym)) {
 491           // The symbol evaluates to a constant. If necessary, promote the
 492           // folded constant (LHS) to the result type.
 493           const llvm::APSInt &lhs_I = BasicVals.Convert(conversionType,
 494                                                         *Constant);
 495           lhs = nonloc::ConcreteInt(lhs_I);
 496
 497           // Also promote the RHS (if necessary).
 498
 499           // For shifts, it is not necessary to promote the RHS.
 500           if (BinaryOperator::isShiftOp(op))
 501             continue;
 502
 503           // Other operators: do an implicit conversion.  This shouldn't be
 504           // necessary once we support truncation/extension of symbolic values.
 505           if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)){
 506             rhs = nonloc::ConcreteInt(BasicVals.Convert(conversionType,
 507                                                         rhs_I->getValue()));
 508           }
 509
 510           continue;
 511         }
 512
 513       // Is the RHS a symbol we can simplify?
 514       if (const nonloc::SymbolVal *srhs = dyn_cast<nonloc::SymbolVal>(&rhs)) {
 515         SymbolRef RSym = srhs->getSymbol();
 516         if (RSym->getType(Context)->isIntegerType()) {
 517           if (const llvm::APSInt *Constant = state->getSymVal(RSym)) {
 518             // The symbol evaluates to a constant.
 519             const llvm::APSInt &rhs_I = BasicVals.Convert(conversionType,
 520                                                           *Constant);
 521             rhs = nonloc::ConcreteInt(rhs_I);
 522           }
 523         }
 524       }
 525
 526       if (isa<nonloc::ConcreteInt>(rhs)) {
 527         return MakeSymIntVal(slhs->getSymbol(), op,
 528                              cast<nonloc::ConcreteInt>(rhs).getValue(),
 529                              resultTy);
 530       }
 531
 532       return UnknownVal();
 533     }
 534     }
 535   }
 536 }
 537
 538 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
 539 SVal SimpleSValBuilder::evalBinOpLL(const ProgramState *state,
 540                                   BinaryOperator::Opcode op,
 541                                   Loc lhs, Loc rhs,
 542                                   QualType resultTy) {
 543   // Only comparisons and subtractions are valid operations on two pointers.
 544   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
 545   // However, if a pointer is casted to an integer, evalBinOpNN may end up
 546   // calling this function with another operation (PR7527). We don't attempt to
 547   // model this for now, but it could be useful, particularly when the
 548   // "location" is actually an integer value that's been passed through a void*.
 549   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
 550     return UnknownVal();
 551
 552   // Special cases for when both sides are identical.
 553   if (lhs == rhs) {
 554     switch (op) {
 555     default:
 556       llvm_unreachable("Unimplemented operation for two identical values");
 557     case BO_Sub:
 558       return makeZeroVal(resultTy);
 559     case BO_EQ:
 560     case BO_LE:
 561     case BO_GE:
 562       return makeTruthVal(true, resultTy);
 563     case BO_NE:
 564     case BO_LT:
 565     case BO_GT:
 566       return makeTruthVal(false, resultTy);
 567     }
 568   }
 569
 570   switch (lhs.getSubKind()) {
 571   default:
 572     llvm_unreachable("Ordering not implemented for this Loc.");
 573
 574   case loc::GotoLabelKind:
 575     // The only thing we know about labels is that they're non-null.
 576     if (rhs.isZeroConstant()) {
 577       switch (op) {
 578       default:
 579         break;
 580       case BO_Sub:
 581         return evalCastFromLoc(lhs, resultTy);
 582       case BO_EQ:
 583       case BO_LE:
 584       case BO_LT:
 585         return makeTruthVal(false, resultTy);
 586       case BO_NE:
 587       case BO_GT:
 588       case BO_GE:
 589         return makeTruthVal(true, resultTy);
 590       }
 591     }
 592     // There may be two labels for the same location, and a function region may
 593     // have the same address as a label at the start of the function (depending
 594     // on the ABI).
 595     // FIXME: we can probably do a comparison against other MemRegions, though.
 596     // FIXME: is there a way to tell if two labels refer to the same location?
 597     return UnknownVal();
 598
 599   case loc::ConcreteIntKind: {
 600     // If one of the operands is a symbol and the other is a constant,
 601     // build an expression for use by the constraint manager.
 602     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
 603       // We can only build expressions with symbols on the left,
 604       // so we need a reversible operator.
 605       if (!BinaryOperator::isComparisonOp(op))
 606         return UnknownVal();
 607
 608       const llvm::APSInt &lVal = cast<loc::ConcreteInt>(lhs).getValue();
 609       return makeNonLoc(rSym, ReverseComparison(op), lVal, resultTy);
 610     }
 611
 612     // If both operands are constants, just perform the operation.
 613     if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
 614       SVal ResultVal = cast<loc::ConcreteInt>(lhs).evalBinOp(BasicVals, op,
 615                                                              *rInt);
 616       if (Loc *Result = dyn_cast<Loc>(&ResultVal))
 617         return evalCastFromLoc(*Result, resultTy);
 618       else
 619         return UnknownVal();
 620     }
 621
 622     // Special case comparisons against NULL.
 623     // This must come after the test if the RHS is a symbol, which is used to
 624     // build constraints. The address of any non-symbolic region is guaranteed
 625     // to be non-NULL, as is any label.
 626     assert(isa<loc::MemRegionVal>(rhs) || isa<loc::GotoLabel>(rhs));
 627     if (lhs.isZeroConstant()) {
 628       switch (op) {
 629       default:
 630         break;
 631       case BO_EQ:
 632       case BO_GT:
 633       case BO_GE:
 634         return makeTruthVal(false, resultTy);
 635       case BO_NE:
 636       case BO_LT:
 637       case BO_LE:
 638         return makeTruthVal(true, resultTy);
 639       }
 640     }
 641
 642     // Comparing an arbitrary integer to a region or label address is
 643     // completely unknowable.
 644     return UnknownVal();
 645   }
 646   case loc::MemRegionKind: {
 647     if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
 648       // If one of the operands is a symbol and the other is a constant,
 649       // build an expression for use by the constraint manager.
 650       if (SymbolRef lSym = lhs.getAsLocSymbol())
 651         return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
 652
 653       // Special case comparisons to NULL.
 654       // This must come after the test if the LHS is a symbol, which is used to
 655       // build constraints. The address of any non-symbolic region is guaranteed
 656       // to be non-NULL.
 657       if (rInt->isZeroConstant()) {
 658         switch (op) {
 659         default:
 660           break;
 661         case BO_Sub:
 662           return evalCastFromLoc(lhs, resultTy);
 663         case BO_EQ:
 664         case BO_LT:
 665         case BO_LE:
 666           return makeTruthVal(false, resultTy);
 667         case BO_NE:
 668         case BO_GT:
 669         case BO_GE:
 670           return makeTruthVal(true, resultTy);
 671         }
 672       }
 673
 674       // Comparing a region to an arbitrary integer is completely unknowable.
 675       return UnknownVal();
 676     }
 677
 678     // Get both values as regions, if possible.
 679     const MemRegion *LeftMR = lhs.getAsRegion();
 680     assert(LeftMR && "MemRegionKind SVal doesn't have a region!");
 681
 682     const MemRegion *RightMR = rhs.getAsRegion();
 683     if (!RightMR)
 684       // The RHS is probably a label, which in theory could address a region.
 685       // FIXME: we can probably make a more useful statement about non-code
 686       // regions, though.
 687       return UnknownVal();
 688
 689     // If both values wrap regions, see if they're from different base regions.
 690     const MemRegion *LeftBase = LeftMR->getBaseRegion();
 691     const MemRegion *RightBase = RightMR->getBaseRegion();
 692     if (LeftBase != RightBase &&
 693         !isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) {
 694       switch (op) {
 695       default:
 696         return UnknownVal();
 697       case BO_EQ:
 698         return makeTruthVal(false, resultTy);
 699       case BO_NE:
 700         return makeTruthVal(true, resultTy);
 701       }
 702     }
 703
 704     // The two regions are from the same base region. See if they're both a
 705     // type of region we know how to compare.
 706
 707     // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this
 708     // ElementRegion path and the FieldRegion path below should be unified.
 709     if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) {
 710       // First see if the right region is also an ElementRegion.
 711       const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
 712       if (!RightER)
 713         return UnknownVal();
 714
 715       // Next, see if the two ERs have the same super-region and matching types.
 716       // FIXME: This should do something useful even if the types don't match,
 717       // though if both indexes are constant the RegionRawOffset path will
 718       // give the correct answer.
 719       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
 720           LeftER->getElementType() == RightER->getElementType()) {
 721         // Get the left index and cast it to the correct type.
 722         // If the index is unknown or undefined, bail out here.
 723         SVal LeftIndexVal = LeftER->getIndex();
 724         NonLoc *LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
 725         if (!LeftIndex)
 726           return UnknownVal();
 727         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, resultTy);
 728         LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
 729         if (!LeftIndex)
 730           return UnknownVal();
 731
 732         // Do the same for the right index.
 733         SVal RightIndexVal = RightER->getIndex();
 734         NonLoc *RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
 735         if (!RightIndex)
 736           return UnknownVal();
 737         RightIndexVal = evalCastFromNonLoc(*RightIndex, resultTy);
 738         RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
 739         if (!RightIndex)
 740           return UnknownVal();
 741
 742         // Actually perform the operation.
 743         // evalBinOpNN expects the two indexes to already be the right type.
 744         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
 745       }
 746
 747       // If the element indexes aren't comparable, see if the raw offsets are.
 748       RegionRawOffset LeftOffset = LeftER->getAsArrayOffset();
 749       RegionRawOffset RightOffset = RightER->getAsArrayOffset();
 750
 751       if (LeftOffset.getRegion() != NULL &&
 752           LeftOffset.getRegion() == RightOffset.getRegion()) {
 753         CharUnits left = LeftOffset.getOffset();
 754         CharUnits right = RightOffset.getOffset();
 755
 756         switch (op) {
 757         default:
 758           return UnknownVal();
 759         case BO_LT:
 760           return makeTruthVal(left < right, resultTy);
 761         case BO_GT:
 762           return makeTruthVal(left > right, resultTy);
 763         case BO_LE:
 764           return makeTruthVal(left <= right, resultTy);
 765         case BO_GE:
 766           return makeTruthVal(left >= right, resultTy);
 767         case BO_EQ:
 768           return makeTruthVal(left == right, resultTy);
 769         case BO_NE:
 770           return makeTruthVal(left != right, resultTy);
 771         }
 772       }
 773
 774       // If we get here, we have no way of comparing the ElementRegions.
 775       return UnknownVal();
 776     }
 777
 778     // See if both regions are fields of the same structure.
 779     // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars.
 780     if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) {
 781       // Only comparisons are meaningful here!
 782       if (!BinaryOperator::isComparisonOp(op))
 783         return UnknownVal();
 784
 785       // First see if the right region is also a FieldRegion.
 786       const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
 787       if (!RightFR)
 788         return UnknownVal();
 789
 790       // Next, see if the two FRs have the same super-region.
 791       // FIXME: This doesn't handle casts yet, and simply stripping the casts
 792       // doesn't help.
 793       if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
 794         return UnknownVal();
 795
 796       const FieldDecl *LeftFD = LeftFR->getDecl();
 797       const FieldDecl *RightFD = RightFR->getDecl();
 798       const RecordDecl *RD = LeftFD->getParent();
 799
 800       // Make sure the two FRs are from the same kind of record. Just in case!
 801       // FIXME: This is probably where inheritance would be a problem.
 802       if (RD != RightFD->getParent())
 803         return UnknownVal();
 804
 805       // We know for sure that the two fields are not the same, since that
 806       // would have given us the same SVal.
 807       if (op == BO_EQ)
 808         return makeTruthVal(false, resultTy);
 809       if (op == BO_NE)
 810         return makeTruthVal(true, resultTy);
 811
 812       // Iterate through the fields and see which one comes first.
 813       // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
 814       // members and the units in which bit-fields reside have addresses that
 815       // increase in the order in which they are declared."
 816       bool leftFirst = (op == BO_LT || op == BO_LE);
 817       for (RecordDecl::field_iterator I = RD->field_begin(),
 818            E = RD->field_end(); I!=E; ++I) {
 819         if (*I == LeftFD)
 820           return makeTruthVal(leftFirst, resultTy);
 821         if (*I == RightFD)
 822           return makeTruthVal(!leftFirst, resultTy);
 823       }
 824
 825       llvm_unreachable("Fields not found in parent record's definition");
 826     }
 827
 828     // If we get here, we have no way of comparing the regions.
 829     return UnknownVal();
 830   }
 831   }
 832 }
 833
 834 SVal SimpleSValBuilder::evalBinOpLN(const ProgramState *state,
 835                                   BinaryOperator::Opcode op,
 836                                   Loc lhs, NonLoc rhs, QualType resultTy) {
 837
 838   // Special case: rhs is a zero constant.
 839   if (rhs.isZeroConstant())
 840     return lhs;
 841
 842   // Special case: 'rhs' is an integer that has the same width as a pointer and
 843   // we are using the integer location in a comparison.  Normally this cannot be
 844   // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32
 845   // can generate comparisons that trigger this code.
 846   // FIXME: Are all locations guaranteed to have pointer width?
 847   if (BinaryOperator::isComparisonOp(op)) {
 848     if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
 849       const llvm::APSInt *x = &rhsInt->getValue();
 850       ASTContext &ctx = Context;
 851       if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) {
 852         // Convert the signedness of the integer (if necessary).
 853         if (x->isSigned())
 854           x = &getBasicValueFactory().getValue(*x, true);
 855
 856         return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy);
 857       }
 858     }
 859   }
 860
 861   // We are dealing with pointer arithmetic.
 862
 863   // Handle pointer arithmetic on constant values.
 864   if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
 865     if (loc::ConcreteInt *lhsInt = dyn_cast<loc::ConcreteInt>(&lhs)) {
 866       const llvm::APSInt &leftI = lhsInt->getValue();
 867       assert(leftI.isUnsigned());
 868       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
 869
 870       // Convert the bitwidth of rightI.  This should deal with overflow
 871       // since we are dealing with concrete values.
 872       rightI = rightI.extOrTrunc(leftI.getBitWidth());
 873
 874       // Offset the increment by the pointer size.
 875       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
 876       rightI *= Multiplicand;
 877
 878       // Compute the adjusted pointer.
 879       switch (op) {
 880         case BO_Add:
 881           rightI = leftI + rightI;
 882           break;
 883         case BO_Sub:
 884           rightI = leftI - rightI;
 885           break;
 886         default:
 887           llvm_unreachable("Invalid pointer arithmetic operation");
 888       }
 889       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
 890     }
 891   }
 892
 893   // Handle cases where 'lhs' is a region.
 894   if (const MemRegion *region = lhs.getAsRegion()) {
 895     rhs = cast<NonLoc>(convertToArrayIndex(rhs));
 896     SVal index = UnknownVal();
 897     const MemRegion *superR = 0;
 898     QualType elementType;
 899
 900     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
 901       assert(op == BO_Add || op == BO_Sub);
 902       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
 903                           getArrayIndexType());
 904       superR = elemReg->getSuperRegion();
 905       elementType = elemReg->getElementType();
 906     }
 907     else if (isa<SubRegion>(region)) {
 908       superR = region;
 909       index = rhs;
 910       if (const PointerType *PT = resultTy->getAs<PointerType>()) {
 911         elementType = PT->getPointeeType();
 912       }
 913       else {
 914         const ObjCObjectPointerType *OT =
 915           resultTy->getAs<ObjCObjectPointerType>();
 916         elementType = OT->getPointeeType();
 917       }
 918     }
 919
 920     if (NonLoc *indexV = dyn_cast<NonLoc>(&index)) {
 921       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
 922                                                        superR, getContext()));
 923     }
 924   }
 925   return UnknownVal();
 926 }
 927
 928 const llvm::APSInt *SimpleSValBuilder::getKnownValue(const ProgramState *state,
 929                                                    SVal V) {
 930   if (V.isUnknownOrUndef())
 931     return NULL;
 932
 933   if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V))
 934     return &X->getValue();
 935
 936   if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V))
 937     return &X->getValue();
 938
 939   if (SymbolRef Sym = V.getAsSymbol())
 940     return state->getSymVal(Sym);
 941
 942   // FIXME: Add support for SymExprs.
 943   return NULL;
 944 }