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