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