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/ADT/None.h" 38 #include "llvm/ADT/Optional.h" 39 #include "llvm/Support/Casting.h" 40 #include "llvm/Support/Compiler.h" 41 #include <cassert> 42 #include <tuple> 43 44 using namespace clang; 45 using namespace ento; 46 47 //===----------------------------------------------------------------------===// 48 // Basic SVal creation. 49 //===----------------------------------------------------------------------===// 50 51 void SValBuilder::anchor() {} 52 53 SValBuilder::SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, 54 ProgramStateManager &stateMgr) 55 : Context(context), BasicVals(context, alloc), 56 SymMgr(context, BasicVals, alloc), MemMgr(context, alloc), 57 StateMgr(stateMgr), 58 AnOpts( 59 stateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions()), 60 ArrayIndexTy(context.LongLongTy), 61 ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {} 62 63 DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { 64 if (Loc::isLocType(type)) 65 return makeNullWithType(type); 66 67 if (type->isIntegralOrEnumerationType()) 68 return makeIntVal(0, type); 69 70 if (type->isArrayType() || type->isRecordType() || type->isVectorType() || 71 type->isAnyComplexType()) 72 return makeCompoundVal(type, BasicVals.getEmptySValList()); 73 74 // FIXME: Handle floats. 75 return UnknownVal(); 76 } 77 78 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, 79 BinaryOperator::Opcode op, 80 const llvm::APSInt &rhs, 81 QualType type) { 82 // The Environment ensures we always get a persistent APSInt in 83 // BasicValueFactory, so we don't need to get the APSInt from 84 // BasicValueFactory again. 85 assert(lhs); 86 assert(!Loc::isLocType(type)); 87 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); 88 } 89 90 nonloc::SymbolVal SValBuilder::makeNonLoc(const llvm::APSInt &lhs, 91 BinaryOperator::Opcode op, 92 const SymExpr *rhs, QualType type) { 93 assert(rhs); 94 assert(!Loc::isLocType(type)); 95 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); 96 } 97 98 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, 99 BinaryOperator::Opcode op, 100 const SymExpr *rhs, QualType type) { 101 assert(lhs && rhs); 102 assert(!Loc::isLocType(type)); 103 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); 104 } 105 106 NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, 107 QualType type) { 108 assert(operand); 109 assert(!Loc::isLocType(type)); 110 return nonloc::SymbolVal(SymMgr.getUnarySymExpr(operand, op, type)); 111 } 112 113 nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *operand, 114 QualType fromTy, QualType toTy) { 115 assert(operand); 116 assert(!Loc::isLocType(toTy)); 117 if (fromTy == toTy) 118 return operand; 119 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); 120 } 121 122 SVal SValBuilder::convertToArrayIndex(SVal val) { 123 if (val.isUnknownOrUndef()) 124 return val; 125 126 // Common case: we have an appropriately sized integer. 127 if (Optional<nonloc::ConcreteInt> CI = 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 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 None; 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 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 Optional<SVal> Val = getConstantVal(SE); 393 if (!Val) 394 return None; 395 return evalCast(*Val, CE->getType(), SE->getType()); 396 } 397 } 398 // FALLTHROUGH 399 LLVM_FALLTHROUGH; 400 } 401 402 // If we don't have a special case, fall back to the AST's constant evaluator. 403 default: { 404 // Don't try to come up with a value for materialized temporaries. 405 if (E->isGLValue()) 406 return None; 407 408 ASTContext &Ctx = getContext(); 409 Expr::EvalResult Result; 410 if (E->EvaluateAsInt(Result, Ctx)) 411 return makeIntVal(Result.Val.getInt()); 412 413 if (Loc::isLocType(E->getType())) 414 if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) 415 return makeNullWithType(E->getType()); 416 417 return None; 418 } 419 } 420 } 421 422 SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op, 423 NonLoc LHS, NonLoc RHS, 424 QualType ResultTy) { 425 SymbolRef symLHS = LHS.getAsSymbol(); 426 SymbolRef symRHS = RHS.getAsSymbol(); 427 428 // TODO: When the Max Complexity is reached, we should conjure a symbol 429 // instead of generating an Unknown value and propagate the taint info to it. 430 const unsigned MaxComp = AnOpts.MaxSymbolComplexity; 431 432 if (symLHS && symRHS && 433 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp) 434 return makeNonLoc(symLHS, Op, symRHS, ResultTy); 435 436 if (symLHS && symLHS->computeComplexity() < MaxComp) 437 if (Optional<nonloc::ConcreteInt> rInt = RHS.getAs<nonloc::ConcreteInt>()) 438 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); 439 440 if (symRHS && symRHS->computeComplexity() < MaxComp) 441 if (Optional<nonloc::ConcreteInt> lInt = LHS.getAs<nonloc::ConcreteInt>()) 442 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); 443 444 return UnknownVal(); 445 } 446 447 SVal SValBuilder::evalMinus(NonLoc X) { 448 switch (X.getSubKind()) { 449 case nonloc::ConcreteIntKind: 450 return makeIntVal(-X.castAs<nonloc::ConcreteInt>().getValue()); 451 case nonloc::SymbolValKind: 452 return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Minus, 453 X.getType(Context)); 454 default: 455 return UnknownVal(); 456 } 457 } 458 459 SVal SValBuilder::evalComplement(NonLoc X) { 460 switch (X.getSubKind()) { 461 case nonloc::ConcreteIntKind: 462 return makeIntVal(~X.castAs<nonloc::ConcreteInt>().getValue()); 463 case nonloc::SymbolValKind: 464 return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Not, 465 X.getType(Context)); 466 default: 467 return UnknownVal(); 468 } 469 } 470 471 SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, 472 SVal operand, QualType type) { 473 auto OpN = operand.getAs<NonLoc>(); 474 if (!OpN) 475 return UnknownVal(); 476 477 if (opc == UO_Minus) 478 return evalMinus(*OpN); 479 if (opc == UO_Not) 480 return evalComplement(*OpN); 481 llvm_unreachable("Unexpected unary operator"); 482 } 483 484 SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, 485 SVal lhs, SVal rhs, QualType type) { 486 if (lhs.isUndef() || rhs.isUndef()) 487 return UndefinedVal(); 488 489 if (lhs.isUnknown() || rhs.isUnknown()) 490 return UnknownVal(); 491 492 if (isa<nonloc::LazyCompoundVal>(lhs) || isa<nonloc::LazyCompoundVal>(rhs)) { 493 return UnknownVal(); 494 } 495 496 if (op == BinaryOperatorKind::BO_Cmp) { 497 // We can't reason about C++20 spaceship operator yet. 498 // 499 // FIXME: Support C++20 spaceship operator. 500 // The main problem here is that the result is not integer. 501 return UnknownVal(); 502 } 503 504 if (Optional<Loc> LV = lhs.getAs<Loc>()) { 505 if (Optional<Loc> RV = rhs.getAs<Loc>()) 506 return evalBinOpLL(state, op, *LV, *RV, type); 507 508 return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type); 509 } 510 511 if (const Optional<Loc> RV = rhs.getAs<Loc>()) { 512 const auto IsCommutative = [](BinaryOperatorKind Op) { 513 return Op == BO_Mul || Op == BO_Add || Op == BO_And || Op == BO_Xor || 514 Op == BO_Or; 515 }; 516 517 if (IsCommutative(op)) { 518 // Swap operands. 519 return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type); 520 } 521 522 // If the right operand is a concrete int location then we have nothing 523 // better but to treat it as a simple nonloc. 524 if (auto RV = rhs.getAs<loc::ConcreteInt>()) { 525 const nonloc::ConcreteInt RhsAsLoc = makeIntVal(RV->getValue()); 526 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), RhsAsLoc, type); 527 } 528 } 529 530 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(), 531 type); 532 } 533 534 ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs, 535 SVal rhs) { 536 return state->isNonNull(evalEQ(state, lhs, rhs)); 537 } 538 539 SVal SValBuilder::evalEQ(ProgramStateRef state, SVal lhs, SVal rhs) { 540 return evalBinOp(state, BO_EQ, lhs, rhs, getConditionType()); 541 } 542 543 DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state, 544 DefinedOrUnknownSVal lhs, 545 DefinedOrUnknownSVal rhs) { 546 return evalEQ(state, static_cast<SVal>(lhs), static_cast<SVal>(rhs)) 547 .castAs<DefinedOrUnknownSVal>(); 548 } 549 550 /// Recursively check if the pointer types are equal modulo const, volatile, 551 /// and restrict qualifiers. Also, assume that all types are similar to 'void'. 552 /// Assumes the input types are canonical. 553 static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy, 554 QualType FromTy) { 555 while (Context.UnwrapSimilarTypes(ToTy, FromTy)) { 556 Qualifiers Quals1, Quals2; 557 ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1); 558 FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2); 559 560 // Make sure that non-cvr-qualifiers the other qualifiers (e.g., address 561 // spaces) are identical. 562 Quals1.removeCVRQualifiers(); 563 Quals2.removeCVRQualifiers(); 564 if (Quals1 != Quals2) 565 return false; 566 } 567 568 // If we are casting to void, the 'From' value can be used to represent the 569 // 'To' value. 570 // 571 // FIXME: Doing this after unwrapping the types doesn't make any sense. A 572 // cast from 'int**' to 'void**' is not special in the way that a cast from 573 // 'int*' to 'void*' is. 574 if (ToTy->isVoidType()) 575 return true; 576 577 if (ToTy != FromTy) 578 return false; 579 580 return true; 581 } 582 583 // Handles casts of type CK_IntegralCast. 584 // At the moment, this function will redirect to evalCast, except when the range 585 // of the original value is known to be greater than the max of the target type. 586 SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val, 587 QualType castTy, QualType originalTy) { 588 // No truncations if target type is big enough. 589 if (getContext().getTypeSize(castTy) >= getContext().getTypeSize(originalTy)) 590 return evalCast(val, castTy, originalTy); 591 592 SymbolRef se = val.getAsSymbol(); 593 if (!se) // Let evalCast handle non symbolic expressions. 594 return evalCast(val, castTy, originalTy); 595 596 // Find the maximum value of the target type. 597 APSIntType ToType(getContext().getTypeSize(castTy), 598 castTy->isUnsignedIntegerType()); 599 llvm::APSInt ToTypeMax = ToType.getMaxValue(); 600 NonLoc ToTypeMaxVal = 601 makeIntVal(ToTypeMax.isUnsigned() ? ToTypeMax.getZExtValue() 602 : ToTypeMax.getSExtValue(), 603 castTy) 604 .castAs<NonLoc>(); 605 // Check the range of the symbol being casted against the maximum value of the 606 // target type. 607 NonLoc FromVal = val.castAs<NonLoc>(); 608 QualType CmpTy = getConditionType(); 609 NonLoc CompVal = 610 evalBinOpNN(state, BO_LE, FromVal, ToTypeMaxVal, CmpTy).castAs<NonLoc>(); 611 ProgramStateRef IsNotTruncated, IsTruncated; 612 std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal); 613 if (!IsNotTruncated && IsTruncated) { 614 // Symbol is truncated so we evaluate it as a cast. 615 return makeNonLoc(se, originalTy, castTy); 616 } 617 return evalCast(val, castTy, originalTy); 618 } 619 620 //===----------------------------------------------------------------------===// 621 // Cast method. 622 // `evalCast` and its helper `EvalCastVisitor` 623 //===----------------------------------------------------------------------===// 624 625 namespace { 626 class EvalCastVisitor : public SValVisitor<EvalCastVisitor, SVal> { 627 private: 628 SValBuilder &VB; 629 ASTContext &Context; 630 QualType CastTy, OriginalTy; 631 632 public: 633 EvalCastVisitor(SValBuilder &VB, QualType CastTy, QualType OriginalTy) 634 : VB(VB), Context(VB.getContext()), CastTy(CastTy), 635 OriginalTy(OriginalTy) {} 636 637 SVal Visit(SVal V) { 638 if (CastTy.isNull()) 639 return V; 640 641 CastTy = Context.getCanonicalType(CastTy); 642 643 const bool IsUnknownOriginalType = OriginalTy.isNull(); 644 if (!IsUnknownOriginalType) { 645 OriginalTy = Context.getCanonicalType(OriginalTy); 646 647 if (CastTy == OriginalTy) 648 return V; 649 650 // FIXME: Move this check to the most appropriate 651 // evalCastKind/evalCastSubKind function. For const casts, casts to void, 652 // just propagate the value. 653 if (!CastTy->isVariableArrayType() && !OriginalTy->isVariableArrayType()) 654 if (shouldBeModeledWithNoOp(Context, Context.getPointerType(CastTy), 655 Context.getPointerType(OriginalTy))) 656 return V; 657 } 658 return SValVisitor::Visit(V); 659 } 660 SVal VisitUndefinedVal(UndefinedVal V) { return V; } 661 SVal VisitUnknownVal(UnknownVal V) { return V; } 662 SVal VisitLocConcreteInt(loc::ConcreteInt V) { 663 // Pointer to bool. 664 if (CastTy->isBooleanType()) 665 return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy); 666 667 // Pointer to integer. 668 if (CastTy->isIntegralOrEnumerationType()) { 669 llvm::APSInt Value = V.getValue(); 670 VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); 671 return VB.makeIntVal(Value); 672 } 673 674 // Pointer to any pointer. 675 if (Loc::isLocType(CastTy)) { 676 llvm::APSInt Value = V.getValue(); 677 VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); 678 return loc::ConcreteInt(VB.getBasicValueFactory().getValue(Value)); 679 } 680 681 // Pointer to whatever else. 682 return UnknownVal(); 683 } 684 SVal VisitLocGotoLabel(loc::GotoLabel V) { 685 // Pointer to bool. 686 if (CastTy->isBooleanType()) 687 // Labels are always true. 688 return VB.makeTruthVal(true, CastTy); 689 690 // Pointer to integer. 691 if (CastTy->isIntegralOrEnumerationType()) { 692 const unsigned BitWidth = Context.getIntWidth(CastTy); 693 return VB.makeLocAsInteger(V, BitWidth); 694 } 695 696 const bool IsUnknownOriginalType = OriginalTy.isNull(); 697 if (!IsUnknownOriginalType) { 698 // Array to pointer. 699 if (isa<ArrayType>(OriginalTy)) 700 if (CastTy->isPointerType() || CastTy->isReferenceType()) 701 return UnknownVal(); 702 } 703 704 // Pointer to any pointer. 705 if (Loc::isLocType(CastTy)) 706 return V; 707 708 // Pointer to whatever else. 709 return UnknownVal(); 710 } 711 SVal VisitLocMemRegionVal(loc::MemRegionVal V) { 712 // Pointer to bool. 713 if (CastTy->isBooleanType()) { 714 const MemRegion *R = V.getRegion(); 715 if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R)) 716 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl())) 717 if (FD->isWeak()) 718 // FIXME: Currently we are using an extent symbol here, 719 // because there are no generic region address metadata 720 // symbols to use, only content metadata. 721 return nonloc::SymbolVal( 722 VB.getSymbolManager().getExtentSymbol(FTR)); 723 724 if (const SymbolicRegion *SymR = R->getSymbolicBase()) { 725 SymbolRef Sym = SymR->getSymbol(); 726 QualType Ty = Sym->getType(); 727 // This change is needed for architectures with varying 728 // pointer widths. See the amdgcn opencl reproducer with 729 // this change as an example: solver-sym-simplification-ptr-bool.cl 730 if (!Ty->isReferenceType()) 731 return VB.makeNonLoc( 732 Sym, BO_NE, VB.getBasicValueFactory().getZeroWithTypeSize(Ty), 733 CastTy); 734 } 735 // Non-symbolic memory regions are always true. 736 return VB.makeTruthVal(true, CastTy); 737 } 738 739 const bool IsUnknownOriginalType = OriginalTy.isNull(); 740 // Try to cast to array 741 const auto *ArrayTy = 742 IsUnknownOriginalType 743 ? nullptr 744 : dyn_cast<ArrayType>(OriginalTy.getCanonicalType()); 745 746 // Pointer to integer. 747 if (CastTy->isIntegralOrEnumerationType()) { 748 SVal Val = V; 749 // Array to integer. 750 if (ArrayTy) { 751 // We will always decay to a pointer. 752 QualType ElemTy = ArrayTy->getElementType(); 753 Val = VB.getStateManager().ArrayToPointer(V, ElemTy); 754 // FIXME: Keep these here for now in case we decide soon that we 755 // need the original decayed type. 756 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); 757 // QualType pointerTy = C.getPointerType(elemTy); 758 } 759 const unsigned BitWidth = Context.getIntWidth(CastTy); 760 return VB.makeLocAsInteger(Val.castAs<Loc>(), BitWidth); 761 } 762 763 // Pointer to pointer. 764 if (Loc::isLocType(CastTy)) { 765 766 if (IsUnknownOriginalType) { 767 // When retrieving symbolic pointer and expecting a non-void pointer, 768 // wrap them into element regions of the expected type if necessary. 769 // It is necessary to make sure that the retrieved value makes sense, 770 // because there's no other cast in the AST that would tell us to cast 771 // it to the correct pointer type. We might need to do that for non-void 772 // pointers as well. 773 // FIXME: We really need a single good function to perform casts for us 774 // correctly every time we need it. 775 const MemRegion *R = V.getRegion(); 776 if (CastTy->isPointerType() && !CastTy->isVoidPointerType()) { 777 if (const auto *SR = dyn_cast<SymbolicRegion>(R)) { 778 QualType SRTy = SR->getSymbol()->getType(); 779 780 auto HasSameUnqualifiedPointeeType = [](QualType ty1, 781 QualType ty2) { 782 return ty1->getPointeeType().getCanonicalType().getTypePtr() == 783 ty2->getPointeeType().getCanonicalType().getTypePtr(); 784 }; 785 if (!HasSameUnqualifiedPointeeType(SRTy, CastTy)) { 786 if (auto OptMemRegV = VB.getCastedMemRegionVal(SR, CastTy)) 787 return *OptMemRegV; 788 } 789 } 790 } 791 // Next fixes pointer dereference using type different from its initial 792 // one. See PR37503 and PR49007 for details. 793 if (const auto *ER = dyn_cast<ElementRegion>(R)) { 794 if (auto OptMemRegV = VB.getCastedMemRegionVal(ER, CastTy)) 795 return *OptMemRegV; 796 } 797 798 return V; 799 } 800 801 if (OriginalTy->isIntegralOrEnumerationType() || 802 OriginalTy->isBlockPointerType() || 803 OriginalTy->isFunctionPointerType()) 804 return V; 805 806 // Array to pointer. 807 if (ArrayTy) { 808 // Are we casting from an array to a pointer? If so just pass on 809 // the decayed value. 810 if (CastTy->isPointerType() || CastTy->isReferenceType()) { 811 // We will always decay to a pointer. 812 QualType ElemTy = ArrayTy->getElementType(); 813 return VB.getStateManager().ArrayToPointer(V, ElemTy); 814 } 815 // Are we casting from an array to an integer? If so, cast the decayed 816 // pointer value to an integer. 817 assert(CastTy->isIntegralOrEnumerationType()); 818 } 819 820 // Other pointer to pointer. 821 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || 822 CastTy->isReferenceType()); 823 824 // We get a symbolic function pointer for a dereference of a function 825 // pointer, but it is of function type. Example: 826 827 // struct FPRec { 828 // void (*my_func)(int * x); 829 // }; 830 // 831 // int bar(int x); 832 // 833 // int f1_a(struct FPRec* foo) { 834 // int x; 835 // (*foo->my_func)(&x); 836 // return bar(x)+1; // no-warning 837 // } 838 839 // Get the result of casting a region to a different type. 840 const MemRegion *R = V.getRegion(); 841 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) 842 return *OptMemRegV; 843 } 844 845 // Pointer to whatever else. 846 // FIXME: There can be gross cases where one casts the result of a 847 // function (that returns a pointer) to some other value that happens to 848 // fit within that pointer value. We currently have no good way to model 849 // such operations. When this happens, the underlying operation is that 850 // the caller is reasoning about bits. Conceptually we are layering a 851 // "view" of a location on top of those bits. Perhaps we need to be more 852 // lazy about mutual possible views, even on an SVal? This may be 853 // necessary for bit-level reasoning as well. 854 return UnknownVal(); 855 } 856 SVal VisitNonLocCompoundVal(nonloc::CompoundVal V) { 857 // Compound to whatever. 858 return UnknownVal(); 859 } 860 SVal VisitNonLocConcreteInt(nonloc::ConcreteInt V) { 861 auto CastedValue = [V, this]() { 862 llvm::APSInt Value = V.getValue(); 863 VB.getBasicValueFactory().getAPSIntType(CastTy).apply(Value); 864 return Value; 865 }; 866 867 // Integer to bool. 868 if (CastTy->isBooleanType()) 869 return VB.makeTruthVal(V.getValue().getBoolValue(), CastTy); 870 871 // Integer to pointer. 872 if (CastTy->isIntegralOrEnumerationType()) 873 return VB.makeIntVal(CastedValue()); 874 875 // Integer to pointer. 876 if (Loc::isLocType(CastTy)) 877 return VB.makeIntLocVal(CastedValue()); 878 879 // Pointer to whatever else. 880 return UnknownVal(); 881 } 882 SVal VisitNonLocLazyCompoundVal(nonloc::LazyCompoundVal V) { 883 // LazyCompound to whatever. 884 return UnknownVal(); 885 } 886 SVal VisitNonLocLocAsInteger(nonloc::LocAsInteger V) { 887 Loc L = V.getLoc(); 888 889 // Pointer as integer to bool. 890 if (CastTy->isBooleanType()) 891 // Pass to Loc function. 892 return Visit(L); 893 894 const bool IsUnknownOriginalType = OriginalTy.isNull(); 895 // Pointer as integer to pointer. 896 if (!IsUnknownOriginalType && Loc::isLocType(CastTy) && 897 OriginalTy->isIntegralOrEnumerationType()) { 898 if (const MemRegion *R = L.getAsRegion()) 899 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) 900 return *OptMemRegV; 901 return L; 902 } 903 904 // Pointer as integer with region to integer/pointer. 905 const MemRegion *R = L.getAsRegion(); 906 if (!IsUnknownOriginalType && R) { 907 if (CastTy->isIntegralOrEnumerationType()) 908 return VisitLocMemRegionVal(loc::MemRegionVal(R)); 909 910 if (Loc::isLocType(CastTy)) { 911 assert(Loc::isLocType(OriginalTy) || OriginalTy->isFunctionType() || 912 CastTy->isReferenceType()); 913 // Delegate to store manager to get the result of casting a region to a 914 // different type. If the MemRegion* returned is NULL, this expression 915 // Evaluates to UnknownVal. 916 if (auto OptMemRegV = VB.getCastedMemRegionVal(R, CastTy)) 917 return *OptMemRegV; 918 } 919 } else { 920 if (Loc::isLocType(CastTy)) { 921 if (IsUnknownOriginalType) 922 return VisitLocMemRegionVal(loc::MemRegionVal(R)); 923 return L; 924 } 925 926 SymbolRef SE = nullptr; 927 if (R) { 928 if (const SymbolicRegion *SR = 929 dyn_cast<SymbolicRegion>(R->StripCasts())) { 930 SE = SR->getSymbol(); 931 } 932 } 933 934 if (!CastTy->isFloatingType() || !SE || SE->getType()->isFloatingType()) { 935 // FIXME: Correctly support promotions/truncations. 936 const unsigned CastSize = Context.getIntWidth(CastTy); 937 if (CastSize == V.getNumBits()) 938 return V; 939 940 return VB.makeLocAsInteger(L, CastSize); 941 } 942 } 943 944 // Pointer as integer to whatever else. 945 return UnknownVal(); 946 } 947 SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) { 948 SymbolRef SE = V.getSymbol(); 949 950 const bool IsUnknownOriginalType = OriginalTy.isNull(); 951 // Symbol to bool. 952 if (!IsUnknownOriginalType && CastTy->isBooleanType()) { 953 // Non-float to bool. 954 if (Loc::isLocType(OriginalTy) || 955 OriginalTy->isIntegralOrEnumerationType() || 956 OriginalTy->isMemberPointerType()) { 957 BasicValueFactory &BVF = VB.getBasicValueFactory(); 958 return VB.makeNonLoc(SE, BO_NE, BVF.getValue(0, SE->getType()), CastTy); 959 } 960 } else { 961 // Symbol to integer, float. 962 QualType T = Context.getCanonicalType(SE->getType()); 963 964 // Produce SymbolCast if CastTy and T are different integers. 965 // NOTE: In the end the type of SymbolCast shall be equal to CastTy. 966 if (T->isIntegralOrUnscopedEnumerationType() && 967 CastTy->isIntegralOrUnscopedEnumerationType()) { 968 AnalyzerOptions &Opts = VB.getStateManager() 969 .getOwningEngine() 970 .getAnalysisManager() 971 .getAnalyzerOptions(); 972 // If appropriate option is disabled, ignore the cast. 973 // NOTE: ShouldSupportSymbolicIntegerCasts is `false` by default. 974 if (!Opts.ShouldSupportSymbolicIntegerCasts) 975 return V; 976 return simplifySymbolCast(V, CastTy); 977 } 978 if (!Loc::isLocType(CastTy)) 979 if (!IsUnknownOriginalType || !CastTy->isFloatingType() || 980 T->isFloatingType()) 981 return VB.makeNonLoc(SE, T, CastTy); 982 } 983 984 // Symbol to pointer and whatever else. 985 return UnknownVal(); 986 } 987 SVal VisitNonLocPointerToMember(nonloc::PointerToMember V) { 988 // Member pointer to whatever. 989 return V; 990 } 991 992 /// Reduce cast expression by removing redundant intermediate casts. 993 /// E.g. 994 /// - (char)(short)(int x) -> (char)(int x) 995 /// - (int)(int x) -> int x 996 /// 997 /// \param V -- SymbolVal, which pressumably contains SymbolCast or any symbol 998 /// that is applicable for cast operation. 999 /// \param CastTy -- QualType, which `V` shall be cast to. 1000 /// \return SVal with simplified cast expression. 1001 /// \note: Currently only support integral casts. 1002 nonloc::SymbolVal simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) { 1003 // We use seven conditions to recognize a simplification case. 1004 // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type - 1005 // `R`, prefix `u` for unsigned, `s` for signed, no prefix - any sign: E.g. 1006 // (char)(short)(uint x) 1007 // ( sC )( sT )( uR x) 1008 // 1009 // C === R (the same type) 1010 // (char)(char x) -> (char x) 1011 // (long)(long x) -> (long x) 1012 // Note: Comparisons operators below are for bit width. 1013 // C == T 1014 // (short)(short)(int x) -> (short)(int x) 1015 // (int)(long)(char x) -> (int)(char x) (sizeof(long) == sizeof(int)) 1016 // (long)(ullong)(char x) -> (long)(char x) (sizeof(long) == 1017 // sizeof(ullong)) 1018 // C < T 1019 // (short)(int)(char x) -> (short)(char x) 1020 // (char)(int)(short x) -> (char)(short x) 1021 // (short)(int)(short x) -> (short x) 1022 // C > T > uR 1023 // (int)(short)(uchar x) -> (int)(uchar x) 1024 // (uint)(short)(uchar x) -> (uint)(uchar x) 1025 // (int)(ushort)(uchar x) -> (int)(uchar x) 1026 // C > sT > sR 1027 // (int)(short)(char x) -> (int)(char x) 1028 // (uint)(short)(char x) -> (uint)(char x) 1029 // C > sT == sR 1030 // (int)(char)(char x) -> (int)(char x) 1031 // (uint)(short)(short x) -> (uint)(short x) 1032 // C > uT == uR 1033 // (int)(uchar)(uchar x) -> (int)(uchar x) 1034 // (uint)(ushort)(ushort x) -> (uint)(ushort x) 1035 // (llong)(ulong)(uint x) -> (llong)(uint x) (sizeof(ulong) == 1036 // sizeof(uint)) 1037 1038 SymbolRef SE = V.getSymbol(); 1039 QualType T = Context.getCanonicalType(SE->getType()); 1040 1041 if (T == CastTy) 1042 return V; 1043 1044 if (!isa<SymbolCast>(SE)) 1045 return VB.makeNonLoc(SE, T, CastTy); 1046 1047 SymbolRef RootSym = cast<SymbolCast>(SE)->getOperand(); 1048 QualType RT = RootSym->getType().getCanonicalType(); 1049 1050 // FIXME support simplification from non-integers. 1051 if (!RT->isIntegralOrEnumerationType()) 1052 return VB.makeNonLoc(SE, T, CastTy); 1053 1054 BasicValueFactory &BVF = VB.getBasicValueFactory(); 1055 APSIntType CTy = BVF.getAPSIntType(CastTy); 1056 APSIntType TTy = BVF.getAPSIntType(T); 1057 1058 const auto WC = CTy.getBitWidth(); 1059 const auto WT = TTy.getBitWidth(); 1060 1061 if (WC <= WT) { 1062 const bool isSameType = (RT == CastTy); 1063 if (isSameType) 1064 return nonloc::SymbolVal(RootSym); 1065 return VB.makeNonLoc(RootSym, RT, CastTy); 1066 } 1067 1068 APSIntType RTy = BVF.getAPSIntType(RT); 1069 const auto WR = RTy.getBitWidth(); 1070 const bool UT = TTy.isUnsigned(); 1071 const bool UR = RTy.isUnsigned(); 1072 1073 if (((WT > WR) && (UR || !UT)) || ((WT == WR) && (UT == UR))) 1074 return VB.makeNonLoc(RootSym, RT, CastTy); 1075 1076 return VB.makeNonLoc(SE, T, CastTy); 1077 } 1078 }; 1079 } // end anonymous namespace 1080 1081 /// Cast a given SVal to another SVal using given QualType's. 1082 /// \param V -- SVal that should be casted. 1083 /// \param CastTy -- QualType that V should be casted according to. 1084 /// \param OriginalTy -- QualType which is associated to V. It provides 1085 /// additional information about what type the cast performs from. 1086 /// \returns the most appropriate casted SVal. 1087 /// Note: Many cases don't use an exact OriginalTy. It can be extracted 1088 /// from SVal or the cast can performs unconditionaly. Always pass OriginalTy! 1089 /// It can be crucial in certain cases and generates different results. 1090 /// FIXME: If `OriginalTy.isNull()` is true, then cast performs based on CastTy 1091 /// only. This behavior is uncertain and should be improved. 1092 SVal SValBuilder::evalCast(SVal V, QualType CastTy, QualType OriginalTy) { 1093 EvalCastVisitor TRV{*this, CastTy, OriginalTy}; 1094 return TRV.Visit(V); 1095 } 1096