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 } 974