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