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