1 //===- SValBuilder.cpp - Basic class for all SValBuilder implementations --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines SValBuilder, the base class for all (complete) SValBuilder 10 // implementations. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 15 #include "clang/AST/ASTContext.h" 16 #include "clang/AST/Decl.h" 17 #include "clang/AST/DeclCXX.h" 18 #include "clang/AST/ExprCXX.h" 19 #include "clang/AST/ExprObjC.h" 20 #include "clang/AST/Stmt.h" 21 #include "clang/AST/Type.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/Analysis/AnalysisDeclContext.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 30 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 31 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 32 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 33 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 34 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 35 #include "llvm/ADT/APSInt.h" 36 #include "llvm/ADT/None.h" 37 #include "llvm/ADT/Optional.h" 38 #include "llvm/Support/Casting.h" 39 #include "llvm/Support/Compiler.h" 40 #include <cassert> 41 #include <tuple> 42 43 using namespace clang; 44 using namespace ento; 45 46 //===----------------------------------------------------------------------===// 47 // Basic SVal creation. 48 //===----------------------------------------------------------------------===// 49 50 void SValBuilder::anchor() {} 51 52 SValBuilder::SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, 53 ProgramStateManager &stateMgr) 54 : Context(context), BasicVals(context, alloc), 55 SymMgr(context, BasicVals, alloc), MemMgr(context, alloc), 56 StateMgr(stateMgr), 57 AnOpts( 58 stateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions()), 59 ArrayIndexTy(context.LongLongTy), 60 ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {} 61 62 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { 63 if (Loc::isLocType(type)) 64 return makeNullWithType(type); 65 66 if (type->isIntegralOrEnumerationType()) 67 return makeIntVal(0, type); 68 69 if (type->isArrayType() || type->isRecordType() || type->isVectorType() || 70 type->isAnyComplexType()) 71 return makeCompoundVal(type, BasicVals.getEmptySValList()); 72 73 // FIXME: Handle floats. 74 return UnknownVal(); 75 } 76 77 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, 78 BinaryOperator::Opcode op, 79 const llvm::APSInt &rhs, 80 QualType type) { 81 // The Environment ensures we always get a persistent APSInt in 82 // BasicValueFactory, so we don't need to get the APSInt from 83 // BasicValueFactory again. 84 assert(lhs); 85 assert(!Loc::isLocType(type)); 86 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); 87 } 88 89 nonloc::SymbolVal SValBuilder::makeNonLoc(const llvm::APSInt &lhs, 90 BinaryOperator::Opcode op, 91 const SymExpr *rhs, QualType type) { 92 assert(rhs); 93 assert(!Loc::isLocType(type)); 94 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); 95 } 96 97 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, 98 BinaryOperator::Opcode op, 99 const SymExpr *rhs, QualType type) { 100 assert(lhs && rhs); 101 assert(!Loc::isLocType(type)); 102 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); 103 } 104 105 NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, 106 QualType type) { 107 assert(operand); 108 assert(!Loc::isLocType(type)); 109 return nonloc::SymbolVal(SymMgr.getUnarySymExpr(operand, op, type)); 110 } 111 112 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *operand, 113 QualType fromTy, QualType toTy) { 114 assert(operand); 115 assert(!Loc::isLocType(toTy)); 116 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); 117 } 118 119 SVal SValBuilder::convertToArrayIndex(SVal val) { 120 if (val.isUnknownOrUndef()) 121 return val; 122 123 // Common case: we have an appropriately sized integer. 124 if (Optional<nonloc::ConcreteInt> CI = val.getAs<nonloc::ConcreteInt>()) { 125 const llvm::APSInt& I = CI->getValue(); 126 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned()) 127 return val; 128 } 129 130 return evalCast(val, ArrayIndexTy, QualType{}); 131 } 132 133 nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){ 134 return makeTruthVal(boolean->getValue()); 135 } 136 137 DefinedOrUnknownSVal 138 SValBuilder::getRegionValueSymbolVal(const TypedValueRegion *region) { 139 QualType T = region->getValueType(); 140 141 if (T->isNullPtrType()) 142 return makeZeroVal(T); 143 144 if (!SymbolManager::canSymbolicate(T)) 145 return UnknownVal(); 146 147 SymbolRef sym = SymMgr.getRegionValueSymbol(region); 148 149 if (Loc::isLocType(T)) 150 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 151 152 return nonloc::SymbolVal(sym); 153 } 154 155 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *SymbolTag, 156 const Expr *Ex, 157 const LocationContext *LCtx, 158 unsigned Count) { 159 QualType T = Ex->getType(); 160 161 if (T->isNullPtrType()) 162 return makeZeroVal(T); 163 164 // Compute the type of the result. If the expression is not an R-value, the 165 // result should be a location. 166 QualType ExType = Ex->getType(); 167 if (Ex->isGLValue()) 168 T = LCtx->getAnalysisDeclContext()->getASTContext().getPointerType(ExType); 169 170 return conjureSymbolVal(SymbolTag, Ex, LCtx, T, Count); 171 } 172 173 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, 174 const Expr *expr, 175 const LocationContext *LCtx, 176 QualType type, 177 unsigned count) { 178 if (type->isNullPtrType()) 179 return makeZeroVal(type); 180 181 if (!SymbolManager::canSymbolicate(type)) 182 return UnknownVal(); 183 184 SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag); 185 186 if (Loc::isLocType(type)) 187 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 188 189 return nonloc::SymbolVal(sym); 190 } 191 192 DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt, 193 const LocationContext *LCtx, 194 QualType type, 195 unsigned visitCount) { 196 if (type->isNullPtrType()) 197 return makeZeroVal(type); 198 199 if (!SymbolManager::canSymbolicate(type)) 200 return UnknownVal(); 201 202 SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount); 203 204 if (Loc::isLocType(type)) 205 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 206 207 return nonloc::SymbolVal(sym); 208 } 209 210 DefinedOrUnknownSVal 211 SValBuilder::getConjuredHeapSymbolVal(const Expr *E, 212 const LocationContext *LCtx, 213 unsigned VisitCount) { 214 QualType T = E->getType(); 215 return getConjuredHeapSymbolVal(E, LCtx, T, VisitCount); 216 } 217 218 DefinedOrUnknownSVal 219 SValBuilder::getConjuredHeapSymbolVal(const Expr *E, 220 const LocationContext *LCtx, 221 QualType type, unsigned VisitCount) { 222 assert(Loc::isLocType(type)); 223 assert(SymbolManager::canSymbolicate(type)); 224 if (type->isNullPtrType()) 225 return makeZeroVal(type); 226 227 SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, type, VisitCount); 228 return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym)); 229 } 230 231 DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag, 232 const MemRegion *region, 233 const Expr *expr, QualType type, 234 const LocationContext *LCtx, 235 unsigned count) { 236 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type"); 237 238 SymbolRef sym = 239 SymMgr.getMetadataSymbol(region, expr, type, LCtx, count, symbolTag); 240 241 if (Loc::isLocType(type)) 242 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 243 244 return nonloc::SymbolVal(sym); 245 } 246 247 DefinedOrUnknownSVal 248 SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, 249 const TypedValueRegion *region) { 250 QualType T = region->getValueType(); 251 252 if (T->isNullPtrType()) 253 return makeZeroVal(T); 254 255 if (!SymbolManager::canSymbolicate(T)) 256 return UnknownVal(); 257 258 SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region); 259 260 if (Loc::isLocType(T)) 261 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 262 263 return nonloc::SymbolVal(sym); 264 } 265 266 DefinedSVal SValBuilder::getMemberPointer(const NamedDecl *ND) { 267 assert(!ND || (isa<CXXMethodDecl, FieldDecl, IndirectFieldDecl>(ND))); 268 269 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(ND)) { 270 // Sema treats pointers to static member functions as have function pointer 271 // type, so return a function pointer for the method. 272 // We don't need to play a similar trick for static member fields 273 // because these are represented as plain VarDecls and not FieldDecls 274 // in the AST. 275 if (MD->isStatic()) 276 return getFunctionPointer(MD); 277 } 278 279 return nonloc::PointerToMember(ND); 280 } 281 282 DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { 283 return loc::MemRegionVal(MemMgr.getFunctionCodeRegion(func)); 284 } 285 286 DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, 287 CanQualType locTy, 288 const LocationContext *locContext, 289 unsigned blockCount) { 290 const BlockCodeRegion *BC = 291 MemMgr.getBlockCodeRegion(block, locTy, locContext->getAnalysisDeclContext()); 292 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext, 293 blockCount); 294 return loc::MemRegionVal(BD); 295 } 296 297 Optional<loc::MemRegionVal> 298 SValBuilder::getCastedMemRegionVal(const MemRegion *R, QualType Ty) { 299 if (auto OptR = StateMgr.getStoreManager().castRegion(R, Ty)) 300 return loc::MemRegionVal(*OptR); 301 return None; 302 } 303 304 /// Return a memory region for the 'this' object reference. 305 loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D, 306 const StackFrameContext *SFC) { 307 return loc::MemRegionVal( 308 getRegionManager().getCXXThisRegion(D->getThisType(), SFC)); 309 } 310 311 /// Return a memory region for the 'this' object reference. 312 loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D, 313 const StackFrameContext *SFC) { 314 const Type *T = D->getTypeForDecl(); 315 QualType PT = getContext().getPointerType(QualType(T, 0)); 316 return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC)); 317 } 318 319 Optional<SVal> SValBuilder::getConstantVal(const Expr *E) { 320 E = E->IgnoreParens(); 321 322 switch (E->getStmtClass()) { 323 // Handle expressions that we treat differently from the AST's constant 324 // evaluator. 325 case Stmt::AddrLabelExprClass: 326 return makeLoc(cast<AddrLabelExpr>(E)); 327 328 case Stmt::CXXScalarValueInitExprClass: 329 case Stmt::ImplicitValueInitExprClass: 330 return makeZeroVal(E->getType()); 331 332 case Stmt::ObjCStringLiteralClass: { 333 const auto *SL = cast<ObjCStringLiteral>(E); 334 return makeLoc(getRegionManager().getObjCStringRegion(SL)); 335 } 336 337 case Stmt::StringLiteralClass: { 338 const auto *SL = cast<StringLiteral>(E); 339 return makeLoc(getRegionManager().getStringRegion(SL)); 340 } 341 342 case Stmt::PredefinedExprClass: { 343 const auto *PE = cast<PredefinedExpr>(E); 344 assert(PE->getFunctionName() && 345 "Since we analyze only instantiated functions, PredefinedExpr " 346 "should have a function name."); 347 return makeLoc(getRegionManager().getStringRegion(PE->getFunctionName())); 348 } 349 350 // Fast-path some expressions to avoid the overhead of going through the AST's 351 // constant evaluator 352 case Stmt::CharacterLiteralClass: { 353 const auto *C = cast<CharacterLiteral>(E); 354 return makeIntVal(C->getValue(), C->getType()); 355 } 356 357 case Stmt::CXXBoolLiteralExprClass: 358 return makeBoolVal(cast<CXXBoolLiteralExpr>(E)); 359 360 case Stmt::TypeTraitExprClass: { 361 const auto *TE = cast<TypeTraitExpr>(E); 362 return makeTruthVal(TE->getValue(), TE->getType()); 363 } 364 365 case Stmt::IntegerLiteralClass: 366 return makeIntVal(cast<IntegerLiteral>(E)); 367 368 case Stmt::ObjCBoolLiteralExprClass: 369 return makeBoolVal(cast<ObjCBoolLiteralExpr>(E)); 370 371 case Stmt::CXXNullPtrLiteralExprClass: 372 return makeNullWithType(E->getType()); 373 374 case Stmt::CStyleCastExprClass: 375 case Stmt::CXXFunctionalCastExprClass: 376 case Stmt::CXXConstCastExprClass: 377 case Stmt::CXXReinterpretCastExprClass: 378 case Stmt::CXXStaticCastExprClass: 379 case Stmt::ImplicitCastExprClass: { 380 const auto *CE = cast<CastExpr>(E); 381 switch (CE->getCastKind()) { 382 default: 383 break; 384 case CK_ArrayToPointerDecay: 385 case CK_IntegralToPointer: 386 case CK_NoOp: 387 case CK_BitCast: { 388 const Expr *SE = CE->getSubExpr(); 389 Optional<SVal> Val = getConstantVal(SE); 390 if (!Val) 391 return None; 392 return evalCast(*Val, CE->getType(), SE->getType()); 393 } 394 } 395 // FALLTHROUGH 396 LLVM_FALLTHROUGH; 397 } 398 399 // If we don't have a special case, fall back to the AST's constant evaluator. 400 default: { 401 // Don't try to come up with a value for materialized temporaries. 402 if (E->isGLValue()) 403 return None; 404 405 ASTContext &Ctx = getContext(); 406 Expr::EvalResult Result; 407 if (E->EvaluateAsInt(Result, Ctx)) 408 return makeIntVal(Result.Val.getInt()); 409 410 if (Loc::isLocType(E->getType())) 411 if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) 412 return makeNullWithType(E->getType()); 413 414 return None; 415 } 416 } 417 } 418 419 SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op, 420 NonLoc LHS, NonLoc RHS, 421 QualType ResultTy) { 422 SymbolRef symLHS = LHS.getAsSymbol(); 423 SymbolRef symRHS = RHS.getAsSymbol(); 424 425 // TODO: When the Max Complexity is reached, we should conjure a symbol 426 // instead of generating an Unknown value and propagate the taint info to it. 427 const unsigned MaxComp = AnOpts.MaxSymbolComplexity; 428 429 if (symLHS && symRHS && 430 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp) 431 return makeNonLoc(symLHS, Op, symRHS, ResultTy); 432 433 if (symLHS && symLHS->computeComplexity() < MaxComp) 434 if (Optional<nonloc::ConcreteInt> rInt = RHS.getAs<nonloc::ConcreteInt>()) 435 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); 436 437 if (symRHS && symRHS->computeComplexity() < MaxComp) 438 if (Optional<nonloc::ConcreteInt> lInt = LHS.getAs<nonloc::ConcreteInt>()) 439 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); 440 441 return UnknownVal(); 442 } 443 444 SVal SValBuilder::evalMinus(NonLoc X) { 445 switch (X.getSubKind()) { 446 case nonloc::ConcreteIntKind: 447 return makeIntVal(-X.castAs<nonloc::ConcreteInt>().getValue()); 448 case nonloc::SymbolValKind: 449 return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Minus, 450 X.getType(Context)); 451 default: 452 return UnknownVal(); 453 } 454 } 455 456 SVal SValBuilder::evalComplement(NonLoc X) { 457 switch (X.getSubKind()) { 458 case nonloc::ConcreteIntKind: 459 return makeIntVal(~X.castAs<nonloc::ConcreteInt>().getValue()); 460 case nonloc::SymbolValKind: 461 return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Not, 462 X.getType(Context)); 463 default: 464 return UnknownVal(); 465 } 466 } 467 468 SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, 469 SVal operand, QualType type) { 470 auto OpN = operand.getAs<NonLoc>(); 471 if (!OpN) 472 return UnknownVal(); 473 474 if (opc == UO_Minus) 475 return evalMinus(*OpN); 476 if (opc == UO_Not) 477 return evalComplement(*OpN); 478 llvm_unreachable("Unexpected unary operator"); 479 } 480 481 SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, 482 SVal lhs, SVal rhs, QualType type) { 483 if (lhs.isUndef() || rhs.isUndef()) 484 return UndefinedVal(); 485 486 if (lhs.isUnknown() || rhs.isUnknown()) 487 return UnknownVal(); 488 489 if (isa<nonloc::LazyCompoundVal>(lhs) || isa<nonloc::LazyCompoundVal>(rhs)) { 490 return UnknownVal(); 491 } 492 493 if (op == BinaryOperatorKind::BO_Cmp) { 494 // We can't reason about C++20 spaceship operator yet. 495 // 496 // FIXME: Support C++20 spaceship operator. 497 // The main problem here is that the result is not integer. 498 return UnknownVal(); 499 } 500 501 if (Optional<Loc> LV = lhs.getAs<Loc>()) { 502 if (Optional<Loc> RV = rhs.getAs<Loc>()) 503 return evalBinOpLL(state, op, *LV, *RV, type); 504 505 return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type); 506 } 507 508 if (const Optional<Loc> RV = rhs.getAs<Loc>()) { 509 const auto IsCommutative = [](BinaryOperatorKind Op) { 510 return Op == BO_Mul || Op == BO_Add || Op == BO_And || Op == BO_Xor || 511 Op == BO_Or; 512 }; 513 514 if (IsCommutative(op)) { 515 // Swap operands. 516 return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type); 517 } 518 519 // If the right operand is a concrete int location then we have nothing 520 // better but to treat it as a simple nonloc. 521 if (auto RV = rhs.getAs<loc::ConcreteInt>()) { 522 const nonloc::ConcreteInt RhsAsLoc = makeIntVal(RV->getValue()); 523 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), RhsAsLoc, type); 524 } 525 } 526 527 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(), 528 type); 529 } 530 531 ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs, 532 SVal rhs) { 533 return state->isNonNull(evalEQ(state, lhs, rhs)); 534 } 535 536 SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) { 537 return evalBinOp(state, BO_EQ, lhs, rhs, getConditionType()); 538 } 539 540 DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state, 541 DefinedOrUnknownSVal lhs, 542 DefinedOrUnknownSVal rhs) { 543 return evalEQ(state, static_cast<SVal>(lhs), static_cast<SVal>(rhs)) 544 .castAs<DefinedOrUnknownSVal>(); 545 } 546 547 /// Recursively check if the pointer types are equal modulo const, volatile, 548 /// and restrict qualifiers. Also, assume that all types are similar to 'void'. 549 /// Assumes the input types are canonical. 550 static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy, 551 QualType FromTy) { 552 while (Context.UnwrapSimilarTypes(ToTy, FromTy)) { 553 Qualifiers Quals1, Quals2; 554 ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1); 555 FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2); 556 557 // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address 558 // spaces) are identical. 559 Quals1.removeCVRQualifiers(); 560 Quals2.removeCVRQualifiers(); 561 if (Quals1 != Quals2) 562 return false; 563 } 564 565 // If we are casting to void, the 'From' value can be used to represent the 566 // 'To' value. 567 // 568 // FIXME: Doing this after unwrapping the types doesn't make any sense. A 569 // cast from 'int**' to 'void**' is not special in the way that a cast from 570 // 'int*' to 'void*' is. 571 if (ToTy->isVoidType()) 572 return true; 573 574 if (ToTy != FromTy) 575 return false; 576 577 return true; 578 } 579 580 // Handles casts of type CK_IntegralCast. 581 // At the moment, this function will redirect to evalCast, except when the range 582 // of the original value is known to be greater than the max of the target type. 583 SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val, 584 QualType castTy, QualType originalTy) { 585 // No truncations if target type is big enough. 586 if (getContext().getTypeSize(castTy) >= getContext().getTypeSize(originalTy)) 587 return evalCast(val, castTy, originalTy); 588 589 SymbolRef se = val.getAsSymbol(); 590 if (!se) // Let evalCast handle non symbolic expressions. 591 return evalCast(val, castTy, originalTy); 592 593 // Find the maximum value of the target type. 594 APSIntType ToType(getContext().getTypeSize(castTy), 595 castTy->isUnsignedIntegerType()); 596 llvm::APSInt ToTypeMax = ToType.getMaxValue(); 597 NonLoc ToTypeMaxVal = 598 makeIntVal(ToTypeMax.isUnsigned() ? ToTypeMax.getZExtValue() 599 : ToTypeMax.getSExtValue(), 600 castTy) 601 .castAs<NonLoc>(); 602 // Check the range of the symbol being casted against the maximum value of the 603 // target type. 604 NonLoc FromVal = val.castAs<NonLoc>(); 605 QualType CmpTy = getConditionType(); 606 NonLoc CompVal = 607 evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>(); 608 ProgramStateRef IsNotTruncated, IsTruncated; 609 std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal); 610 if (!IsNotTruncated && IsTruncated) { 611 // Symbol is truncated so we evaluate it as a cast. 612 return makeNonLoc(se, originalTy, castTy); 613 } 614 return evalCast(val, castTy, originalTy); 615 } 616 617 //===----------------------------------------------------------------------===// 618 // Cast methods. 619 // `evalCast` is the main method 620 // `evalCastKind` and `evalCastSubKind` are helpers 621 //===----------------------------------------------------------------------===// 622 623 /// Cast a given SVal to another SVal using given QualType's. 624 /// \param V -- SVal that should be casted. 625 /// \param CastTy -- QualType that V should be casted according to. 626 /// \param OriginalTy -- QualType which is associated to V. It provides 627 /// additional information about what type the cast performs from. 628 /// \returns the most appropriate casted SVal. 629 /// Note: Many cases don't use an exact OriginalTy. It can be extracted 630 /// from SVal or the cast can performs unconditionaly. Always pass OriginalTy! 631 /// It can be crucial in certain cases and generates different results. 632 /// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy 633 /// only. This behavior is uncertain and should be improved. 634 SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) { 635 if (CastTy.isNull()) 636 return V; 637 638 CastTy = Context.getCanonicalType(CastTy); 639 640 const bool IsUnknownOriginalType = OriginalTy.isNull(); 641 if (!IsUnknownOriginalType) { 642 OriginalTy = Context.getCanonicalType(OriginalTy); 643 644 if (CastTy == OriginalTy) 645 return V; 646 647 // FIXME: Move this check to the most appropriate 648 // evalCastKind/evalCastSubKind function. For const casts, casts to void, 649 // just propagate the value. 650 if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType()) 651 if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy), 652 Context.getPointerType(OriginalTy))) 653 return V; 654 } 655 656 // Cast SVal according to kinds. 657 switch (V.getBaseKind()) { 658 case SVal::UndefinedValKind: 659 return evalCastKind(V.castAs<UndefinedVal>(), CastTy, OriginalTy); 660 case SVal::UnknownValKind: 661 return evalCastKind(V.castAs<UnknownVal>(), CastTy, OriginalTy); 662 case SVal::LocKind: 663 return evalCastKind(V.castAs<Loc>(), CastTy, OriginalTy); 664 case SVal::NonLocKind: 665 return evalCastKind(V.castAs<NonLoc>(), CastTy, OriginalTy); 666 } 667 668 llvm_unreachable("Unknown SVal kind"); 669 } 670 671 SVal SValBuilder::evalCastKind(UndefinedVal V, QualType CastTy, 672 QualType OriginalTy) { 673 return V; 674 } 675 676 SVal SValBuilder::evalCastKind(UnknownVal V, QualType CastTy, 677 QualType OriginalTy) { 678 return V; 679 } 680 681 SVal SValBuilder::evalCastKind(Loc V, QualType CastTy, QualType OriginalTy) { 682 switch (V.getSubKind()) { 683 case loc::ConcreteIntKind: 684 return evalCastSubKind(V.castAs<loc::ConcreteInt>(), CastTy, OriginalTy); 685 case loc::GotoLabelKind: 686 return evalCastSubKind(V.castAs<loc::GotoLabel>(), CastTy, OriginalTy); 687 case loc::MemRegionValKind: 688 return evalCastSubKind(V.castAs<loc::MemRegionVal>(), CastTy, OriginalTy); 689 } 690 691 llvm_unreachable("Unknown SVal kind"); 692 } 693 694 SVal SValBuilder::evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy) { 695 switch (V.getSubKind()) { 696 case nonloc::CompoundValKind: 697 return evalCastSubKind(V.castAs<nonloc::CompoundVal>(), CastTy, OriginalTy); 698 case nonloc::ConcreteIntKind: 699 return evalCastSubKind(V.castAs<nonloc::ConcreteInt>(), CastTy, OriginalTy); 700 case nonloc::LazyCompoundValKind: 701 return evalCastSubKind(V.castAs<nonloc::LazyCompoundVal>(), CastTy, 702 OriginalTy); 703 case nonloc::LocAsIntegerKind: 704 return evalCastSubKind(V.castAs<nonloc::LocAsInteger>(), CastTy, 705 OriginalTy); 706 case nonloc::SymbolValKind: 707 return evalCastSubKind(V.castAs<nonloc::SymbolVal>(), CastTy, OriginalTy); 708 case nonloc::PointerToMemberKind: 709 return evalCastSubKind(V.castAs<nonloc::PointerToMember>(), CastTy, 710 OriginalTy); 711 } 712 713 llvm_unreachable("Unknown SVal kind"); 714 } 715 716 SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy, 717 QualType OriginalTy) { 718 // Pointer to bool. 719 if (CastTy->isBooleanType()) 720 return makeTruthVal(V.getValue().getBoolValue(), CastTy); 721 722 // Pointer to integer. 723 if (CastTy->isIntegralOrEnumerationType()) { 724 llvm::APSInt Value = V.getValue(); 725 BasicVals.getAPSIntType(CastTy).apply(Value); 726 return makeIntVal(Value); 727 } 728 729 // Pointer to any pointer. 730 if (Loc::isLocType(CastTy)) { 731 llvm::APSInt Value = V.getValue(); 732 BasicVals.getAPSIntType(CastTy).apply(Value); 733 return loc::ConcreteInt(BasicVals.getValue(Value)); 734 } 735 736 // Pointer to whatever else. 737 return UnknownVal(); 738 } 739 740 SVal SValBuilder::evalCastSubKind(loc::GotoLabel V, QualType CastTy, 741 QualType OriginalTy) { 742 // Pointer to bool. 743 if (CastTy->isBooleanType()) 744 // Labels are always true. 745 return makeTruthVal(true, CastTy); 746 747 // Pointer to integer. 748 if (CastTy->isIntegralOrEnumerationType()) { 749 const unsigned BitWidth = Context.getIntWidth(CastTy); 750 return makeLocAsInteger(V, BitWidth); 751 } 752 753 const bool IsUnknownOriginalType = OriginalTy.isNull(); 754 if (!IsUnknownOriginalType) { 755 // Array to pointer. 756 if (isa<ArrayType>(OriginalTy)) 757 if (CastTy->isPointerType() || CastTy->isReferenceType()) 758 return UnknownVal(); 759 } 760 761 // Pointer to any pointer. 762 if (Loc::isLocType(CastTy)) 763 return V; 764 765 // Pointer to whatever else. 766 return UnknownVal(); 767 } 768 769 static bool hasSameUnqualifiedPointeeType(QualType ty1, QualType ty2) { 770 return ty1->getPointeeType().getCanonicalType().getTypePtr() == 771 ty2->getPointeeType().getCanonicalType().getTypePtr(); 772 } 773 774 SVal SValBuilder::evalCastSubKind(loc::MemRegionVal V, QualType CastTy, 775 QualType OriginalTy) { 776 // Pointer to bool. 777 if (CastTy->isBooleanType()) { 778 const MemRegion *R = V.getRegion(); 779 if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R)) 780 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) 781 if (FD->isWeak()) 782 // FIXME: Currently we are using an extent symbol here, 783 // because there are no generic region address metadata 784 // symbols to use, only content metadata. 785 return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR)); 786 787 if (const SymbolicRegion *SymR = R->getSymbolicBase()) { 788 SymbolRef Sym = SymR->getSymbol(); 789 QualType Ty = Sym->getType(); 790 // This change is needed for architectures with varying 791 // pointer widths. See the amdgcn opencl reproducer with 792 // this change as an example: solver-sym-simplification-ptr-bool.cl 793 if (!Ty->isReferenceType()) 794 return makeNonLoc(Sym, BO_NE, BasicVals.getZeroWithTypeSize(Ty), 795 CastTy); 796 } 797 // Non-symbolic memory regions are always true. 798 return makeTruthVal(true, CastTy); 799 } 800 801 const bool IsUnknownOriginalType = OriginalTy.isNull(); 802 // Try to cast to array 803 const auto *ArrayTy = 804 IsUnknownOriginalType 805 ? nullptr 806 : dyn_cast<ArrayType>(OriginalTy.getCanonicalType()); 807 808 // Pointer to integer. 809 if (CastTy->isIntegralOrEnumerationType()) { 810 SVal Val = V; 811 // Array to integer. 812 if (ArrayTy) { 813 // We will always decay to a pointer. 814 QualType ElemTy = ArrayTy->getElementType(); 815 Val = StateMgr.ArrayToPointer(V, ElemTy); 816 // FIXME: Keep these here for now in case we decide soon that we 817 // need the original decayed type. 818 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); 819 // QualType pointerTy = C.getPointerType(elemTy); 820 } 821 const unsigned BitWidth = Context.getIntWidth(CastTy); 822 return makeLocAsInteger(Val.castAs<Loc>(), BitWidth); 823 } 824 825 // Pointer to pointer. 826 if (Loc::isLocType(CastTy)) { 827 828 if (IsUnknownOriginalType) { 829 // When retrieving symbolic pointer and expecting a non-void pointer, 830 // wrap them into element regions of the expected type if necessary. 831 // It is necessary to make sure that the retrieved value makes sense, 832 // because there's no other cast in the AST that would tell us to cast 833 // it to the correct pointer type. We might need to do that for non-void 834 // pointers as well. 835 // FIXME: We really need a single good function to perform casts for us 836 // correctly every time we need it. 837 const MemRegion *R = V.getRegion(); 838 if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) { 839 if (const auto *SR = dyn_cast<SymbolicRegion>(R)) { 840 QualType SRTy = SR->getSymbol()->getType(); 841 if (!hasSameUnqualifiedPointeeType(SRTy, CastTy)) { 842 if (auto OptMemRegV = getCastedMemRegionVal(SR, CastTy)) 843 return *OptMemRegV; 844 } 845 } 846 } 847 // Next fixes pointer dereference using type different from its initial 848 // one. See PR37503 and PR49007 for details. 849 if (const auto *ER = dyn_cast<ElementRegion>(R)) { 850 if (auto OptMemRegV = getCastedMemRegionVal(ER, CastTy)) 851 return *OptMemRegV; 852 } 853 854 return V; 855 } 856 857 if (OriginalTy->isIntegralOrEnumerationType() || 858 OriginalTy->isBlockPointerType() || OriginalTy->isFunctionPointerType()) 859 return V; 860 861 // Array to pointer. 862 if (ArrayTy) { 863 // Are we casting from an array to a pointer? If so just pass on 864 // the decayed value. 865 if (CastTy->isPointerType() || CastTy->isReferenceType()) { 866 // We will always decay to a pointer. 867 QualType ElemTy = ArrayTy->getElementType(); 868 return StateMgr.ArrayToPointer(V, ElemTy); 869 } 870 // Are we casting from an array to an integer? If so, cast the decayed 871 // pointer value to an integer. 872 assert(CastTy->isIntegralOrEnumerationType()); 873 } 874 875 // Other pointer to pointer. 876 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || 877 CastTy->isReferenceType()); 878 879 // We get a symbolic function pointer for a dereference of a function 880 // pointer, but it is of function type. Example: 881 882 // struct FPRec { 883 // void (*my_func)(int * x); 884 // }; 885 // 886 // int bar(int x); 887 // 888 // int f1_a(struct FPRec* foo) { 889 // int x; 890 // (*foo->my_func)(&x); 891 // return bar(x)+1; // no-warning 892 // } 893 894 // Get the result of casting a region to a different type. 895 const MemRegion *R = V.getRegion(); 896 if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) 897 return *OptMemRegV; 898 } 899 900 // Pointer to whatever else. 901 // FIXME: There can be gross cases where one casts the result of a 902 // function (that returns a pointer) to some other value that happens to 903 // fit within that pointer value. We currently have no good way to model 904 // such operations. When this happens, the underlying operation is that 905 // the caller is reasoning about bits. Conceptually we are layering a 906 // "view" of a location on top of those bits. Perhaps we need to be more 907 // lazy about mutual possible views, even on an SVal? This may be 908 // necessary for bit-level reasoning as well. 909 return UnknownVal(); 910 } 911 912 SVal SValBuilder::evalCastSubKind(nonloc::CompoundVal V, QualType CastTy, 913 QualType OriginalTy) { 914 // Compound to whatever. 915 return UnknownVal(); 916 } 917 918 SVal SValBuilder::evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy, 919 QualType OriginalTy) { 920 auto CastedValue = [V, CastTy, this]() { 921 llvm::APSInt Value = V.getValue(); 922 BasicVals.getAPSIntType(CastTy).apply(Value); 923 return Value; 924 }; 925 926 // Integer to bool. 927 if (CastTy->isBooleanType()) 928 return makeTruthVal(V.getValue().getBoolValue(), CastTy); 929 930 // Integer to pointer. 931 if (CastTy->isIntegralOrEnumerationType()) 932 return makeIntVal(CastedValue()); 933 934 // Integer to pointer. 935 if (Loc::isLocType(CastTy)) 936 return makeIntLocVal(CastedValue()); 937 938 // Pointer to whatever else. 939 return UnknownVal(); 940 } 941 942 SVal SValBuilder::evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy, 943 QualType OriginalTy) { 944 // Compound to whatever. 945 return UnknownVal(); 946 } 947 948 SVal SValBuilder::evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy, 949 QualType OriginalTy) { 950 Loc L = V.getLoc(); 951 952 // Pointer as integer to bool. 953 if (CastTy->isBooleanType()) 954 // Pass to Loc function. 955 return evalCastKind(L, CastTy, OriginalTy); 956 957 const bool IsUnknownOriginalType = OriginalTy.isNull(); 958 // Pointer as integer to pointer. 959 if (!IsUnknownOriginalType && Loc::isLocType(CastTy) && 960 OriginalTy->isIntegralOrEnumerationType()) { 961 if (const MemRegion *R = L.getAsRegion()) 962 if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) 963 return *OptMemRegV; 964 return L; 965 } 966 967 // Pointer as integer with region to integer/pointer. 968 const MemRegion *R = L.getAsRegion(); 969 if (!IsUnknownOriginalType && R) { 970 if (CastTy->isIntegralOrEnumerationType()) 971 return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy); 972 973 if (Loc::isLocType(CastTy)) { 974 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || 975 CastTy->isReferenceType()); 976 // Delegate to store manager to get the result of casting a region to a 977 // different type. If the MemRegion* returned is NULL, this expression 978 // Evaluates to UnknownVal. 979 if (auto OptMemRegV = getCastedMemRegionVal(R, CastTy)) 980 return *OptMemRegV; 981 } 982 } else { 983 if (Loc::isLocType(CastTy)) { 984 if (IsUnknownOriginalType) 985 return evalCastSubKind(loc::MemRegionVal(R), CastTy, OriginalTy); 986 return L; 987 } 988 989 SymbolRef SE = nullptr; 990 if (R) { 991 if (const SymbolicRegion *SR = 992 dyn_cast<SymbolicRegion>(R->StripCasts())) { 993 SE = SR->getSymbol(); 994 } 995 } 996 997 if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) { 998 // FIXME: Correctly support promotions/truncations. 999 const unsigned CastSize = Context.getIntWidth(CastTy); 1000 if (CastSize == V.getNumBits()) 1001 return V; 1002 1003 return makeLocAsInteger(L, CastSize); 1004 } 1005 } 1006 1007 // Pointer as integer to whatever else. 1008 return UnknownVal(); 1009 } 1010 1011 SVal SValBuilder::evalCastSubKind(nonloc::SymbolVal V, QualType CastTy, 1012 QualType OriginalTy) { 1013 SymbolRef SE = V.getSymbol(); 1014 1015 const bool IsUnknownOriginalType = OriginalTy.isNull(); 1016 // Symbol to bool. 1017 if (!IsUnknownOriginalType && CastTy->isBooleanType()) { 1018 // Non-float to bool. 1019 if (Loc::isLocType(OriginalTy) || 1020 OriginalTy->isIntegralOrEnumerationType() || 1021 OriginalTy->isMemberPointerType()) { 1022 BasicValueFactory &BVF = getBasicValueFactory(); 1023 return makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy); 1024 } 1025 } else { 1026 // Symbol to integer, float. 1027 QualType T = Context.getCanonicalType(SE->getType()); 1028 1029 // Produce SymbolCast if CastTy and T are different integers. 1030 // NOTE: In the end the type of SymbolCast shall be equal to CastTy. 1031 if (T->isIntegralOrUnscopedEnumerationType() && 1032 CastTy->isIntegralOrUnscopedEnumerationType()) { 1033 AnalyzerOptions &Opts = 1034 StateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions(); 1035 // If appropriate option is disabled, ignore the cast. 1036 // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default. 1037 if (!Opts.ShouldSupportSymbolicIntegerCasts) 1038 return V; 1039 return simplifySymbolCast(V, CastTy); 1040 } 1041 if (!Loc::isLocType(CastTy)) 1042 if (!IsUnknownOriginalType || !CastTy->isFloatingType() || 1043 T->isFloatingType()) 1044 return makeNonLoc(SE, T, CastTy); 1045 } 1046 1047 // Symbol to pointer and whatever else. 1048 return UnknownVal(); 1049 } 1050 1051 SVal SValBuilder::evalCastSubKind(nonloc::PointerToMember V, QualType CastTy, 1052 QualType OriginalTy) { 1053 // Member pointer to whatever. 1054 return V; 1055 } 1056 1057 nonloc::SymbolVal SValBuilder::simplifySymbolCast(nonloc::SymbolVal V, 1058 QualType CastTy) { 1059 // We use seven conditions to recognize a simplification case. 1060 // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type - `R`, 1061 // prefix `u` for unsigned, `s` for signed, no prefix - any sign: 1062 // E.g. (char)(short)(uint x) 1063 // ( sC )( sT )( uR x) 1064 // 1065 // C === R (the same type) 1066 // (char)(char x) -> (char x) 1067 // (long)(long x) -> (long x) 1068 // Note: Comparisons operators below are for bit width. 1069 // C == T 1070 // (short)(short)(int x) -> (short)(int x) 1071 // (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int)) 1072 // (long)(ullong)(char x) -> (long)(char x) (sizeof(long) == sizeof(ullong)) 1073 // C < T 1074 // (short)(int)(char x) -> (short)(char x) 1075 // (char)(int)(short x) -> (char)(short x) 1076 // (short)(int)(short x) -> (short x) 1077 // C > T > uR 1078 // (int)(short)(uchar x) -> (int)(uchar x) 1079 // (uint)(short)(uchar x) -> (uint)(uchar x) 1080 // (int)(ushort)(uchar x) -> (int)(uchar x) 1081 // C > sT > sR 1082 // (int)(short)(char x) -> (int)(char x) 1083 // (uint)(short)(char x) -> (uint)(char x) 1084 // C > sT == sR 1085 // (int)(char)(char x) -> (int)(char x) 1086 // (uint)(short)(short x) -> (uint)(short x) 1087 // C > uT == uR 1088 // (int)(uchar)(uchar x) -> (int)(uchar x) 1089 // (uint)(ushort)(ushort x) -> (uint)(ushort x) 1090 // (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) == sizeof(uint)) 1091 1092 SymbolRef SE = V.getSymbol(); 1093 QualType T = Context.getCanonicalType(SE->getType()); 1094 1095 if (T == CastTy) 1096 return V; 1097 1098 if (!isa<SymbolCast>(SE)) 1099 return makeNonLoc(SE, T, CastTy); 1100 1101 SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand(); 1102 QualType RT = RootSym->getType().getCanonicalType(); 1103 1104 BasicValueFactory &BVF = getBasicValueFactory(); 1105 APSIntType CTy = BVF.getAPSIntType(CastTy); 1106 APSIntType TTy = BVF.getAPSIntType(T); 1107 1108 const auto WC = CTy.getBitWidth(); 1109 const auto WT = TTy.getBitWidth(); 1110 1111 if (WC <= WT) { 1112 const bool isSameType = (RT == CastTy); 1113 if (isSameType) 1114 return nonloc::SymbolVal(RootSym); 1115 return makeNonLoc(RootSym, RT, CastTy); 1116 } 1117 1118 APSIntType RTy = BVF.getAPSIntType(RT); 1119 const auto WR = RTy.getBitWidth(); 1120 const bool UT = TTy.isUnsigned(); 1121 const bool UR = RTy.isUnsigned(); 1122 1123 if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR))) 1124 return makeNonLoc(RootSym, RT, CastTy); 1125 1126 return makeNonLoc(SE, T, CastTy); 1127 } 1128