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