| //===-- Transfer.cpp --------------------------------------------*- C++ -*-===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| // | |
| // This file defines transfer functions that evaluate program statements and | |
| // update an environment accordingly. | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #include "clang/Analysis/FlowSensitive/Transfer.h" | |
| #include "clang/AST/Decl.h" | |
| #include "clang/AST/DeclBase.h" | |
| #include "clang/AST/DeclCXX.h" | |
| #include "clang/AST/Expr.h" | |
| #include "clang/AST/ExprCXX.h" | |
| #include "clang/AST/OperationKinds.h" | |
| #include "clang/AST/Stmt.h" | |
| #include "clang/AST/StmtVisitor.h" | |
| #include "clang/AST/Type.h" | |
| #include "clang/Analysis/FlowSensitive/ASTOps.h" | |
| #include "clang/Analysis/FlowSensitive/AdornedCFG.h" | |
| #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" | |
| #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" | |
| #include "clang/Analysis/FlowSensitive/NoopAnalysis.h" | |
| #include "clang/Analysis/FlowSensitive/RecordOps.h" | |
| #include "clang/Analysis/FlowSensitive/StorageLocation.h" | |
| #include "clang/Analysis/FlowSensitive/Value.h" | |
| #include "clang/Basic/Builtins.h" | |
| #include "clang/Basic/LLVM.h" | |
| #include "clang/Basic/OperatorKinds.h" | |
| #include "llvm/Support/Casting.h" | |
| #include <assert.h> | |
| #include <cassert> | |
| #define DEBUG_TYPE "dataflow" | |
| namespace clang { | |
| namespace dataflow { | |
| const Environment *StmtToEnvMap::getEnvironment(const Stmt &S) const { | |
| const CFGBlock *Block = ACFG.blockForStmt(S); | |
| if (Block == nullptr) { | |
| assert(false); | |
| return nullptr; | |
| } | |
| if (!ACFG.isBlockReachable(*Block)) | |
| return nullptr; | |
| if (Block->getBlockID() == CurBlockID) | |
| return &CurState.Env; | |
| const auto &State = BlockToState[Block->getBlockID()]; | |
| if (!(State)) | |
| return nullptr; | |
| return &State->Env; | |
| } | |
| static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, | |
| Environment &Env) { | |
| Value *LHSValue = Env.getValue(LHS); | |
| Value *RHSValue = Env.getValue(RHS); | |
| // When two unsupported values are compared, both are nullptr. Only supported | |
| // values should evaluate to equal. | |
| if (LHSValue == RHSValue && LHSValue) | |
| return Env.getBoolLiteralValue(true); | |
| // Special case: `NullPtrLiteralExpr == itself`. When both sides are untyped | |
| // nullptr, they do not have an assigned Value, but they compare equal. | |
| if (LHS.getType()->isNullPtrType() && RHS.getType()->isNullPtrType()) | |
| return Env.getBoolLiteralValue(true); | |
| if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue)) | |
| if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue)) | |
| return Env.makeIff(*LHSBool, *RHSBool); | |
| if (auto *LHSPtr = dyn_cast_or_null<PointerValue>(LHSValue)) | |
| if (auto *RHSPtr = dyn_cast_or_null<PointerValue>(RHSValue)) | |
| // If the storage locations are the same, the pointers definitely compare | |
| // the same. If the storage locations are different, they may still alias, | |
| // so we fall through to the case below that returns an atom. | |
| if (&LHSPtr->getPointeeLoc() == &RHSPtr->getPointeeLoc()) | |
| return Env.getBoolLiteralValue(true); | |
| return Env.makeAtomicBoolValue(); | |
| } | |
| static BoolValue &unpackValue(BoolValue &V, Environment &Env) { | |
| if (auto *Top = llvm::dyn_cast<TopBoolValue>(&V)) { | |
| auto &A = Env.getDataflowAnalysisContext().arena(); | |
| return A.makeBoolValue(A.makeAtomRef(Top->getAtom())); | |
| } | |
| return V; | |
| } | |
| // Unpacks the value (if any) associated with `E` and updates `E` to the new | |
| // value, if any unpacking occurred. Also, does the lvalue-to-rvalue conversion, | |
| // by skipping past the reference. | |
| static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) { | |
| auto *Loc = Env.getStorageLocation(E); | |
| if (Loc == nullptr) | |
| return nullptr; | |
| auto *Val = Env.getValue(*Loc); | |
| auto *B = dyn_cast_or_null<BoolValue>(Val); | |
| if (B == nullptr) | |
| return Val; | |
| auto &UnpackedVal = unpackValue(*B, Env); | |
| if (&UnpackedVal == Val) | |
| return Val; | |
| Env.setValue(*Loc, UnpackedVal); | |
| return &UnpackedVal; | |
| } | |
| static void propagateValue(const Expr &From, const Expr &To, Environment &Env) { | |
| if (From.getType()->isRecordType()) | |
| return; | |
| if (auto *Val = Env.getValue(From)) | |
| Env.setValue(To, *Val); | |
| } | |
| static void propagateStorageLocation(const Expr &From, const Expr &To, | |
| Environment &Env) { | |
| if (auto *Loc = Env.getStorageLocation(From)) | |
| Env.setStorageLocation(To, *Loc); | |
| } | |
| // Propagates the value or storage location of `From` to `To` in cases where | |
| // `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff | |
| // `From` is a glvalue. | |
| static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, | |
| Environment &Env) { | |
| assert(From.isGLValue() == To.isGLValue()); | |
| if (From.isGLValue()) | |
| propagateStorageLocation(From, To, Env); | |
| else | |
| propagateValue(From, To, Env); | |
| } | |
| namespace { | |
| class TransferVisitor : public ConstStmtVisitor<TransferVisitor> { | |
| public: | |
| TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, | |
| Environment::ValueModel &Model) | |
| : StmtToEnv(StmtToEnv), Env(Env), Model(Model) {} | |
| void VisitBinaryOperator(const BinaryOperator *S) { | |
| const Expr *LHS = S->getLHS(); | |
| assert(LHS != nullptr); | |
| const Expr *RHS = S->getRHS(); | |
| assert(RHS != nullptr); | |
| // Do assignments and compound assignments up-front, as there are | |
| // so many of them and we don't want to list all of them in | |
| // the switch statement below. | |
| if (S->isAssignmentOp()) { | |
| auto *LHSLoc = Env.getStorageLocation(*LHS); | |
| if (LHSLoc == nullptr) | |
| return; | |
| // Assign a storage location for the whole expression. | |
| Env.setStorageLocation(*S, *LHSLoc); | |
| // Compound assignments involve arithmetic we don't model yet. | |
| // Regular assignments preserve the value so they're easy. | |
| Value *RHSVal = | |
| S->isCompoundAssignmentOp() ? nullptr : Env.getValue(*RHS); | |
| if (RHSVal == nullptr) { | |
| // Either way, we need to conjure a value if we don't have any so that | |
| // future lookups into that location produce consistent results. | |
| RHSVal = Env.createValue(LHS->getType()); | |
| if (RHSVal == nullptr) { | |
| // At least make sure the old value is gone. It's unlikely to be there | |
| // in the first place given that we don't even know how to create | |
| // a basic unknown value of that type. | |
| Env.clearValue(*LHSLoc); | |
| return; | |
| } | |
| } | |
| // Assign a value to the storage location of the left-hand side. | |
| Env.setValue(*LHSLoc, *RHSVal); | |
| return; | |
| } | |
| switch (S->getOpcode()) { | |
| case BO_LAnd: | |
| case BO_LOr: { | |
| BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS); | |
| BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS); | |
| if (S->getOpcode() == BO_LAnd) | |
| Env.setValue(*S, Env.makeAnd(LHSVal, RHSVal)); | |
| else | |
| Env.setValue(*S, Env.makeOr(LHSVal, RHSVal)); | |
| break; | |
| } | |
| case BO_NE: | |
| case BO_EQ: { | |
| auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env); | |
| Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue | |
| : Env.makeNot(LHSEqRHSValue)); | |
| break; | |
| } | |
| case BO_Comma: { | |
| propagateValueOrStorageLocation(*RHS, *S, Env); | |
| break; | |
| } | |
| default: | |
| break; | |
| } | |
| } | |
| void VisitDeclRefExpr(const DeclRefExpr *S) { | |
| const ValueDecl *VD = S->getDecl(); | |
| assert(VD != nullptr); | |
| // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a | |
| // `StorageLocation`, and there's also no sensible `Value` that we can | |
| // assign to them. Examples: | |
| // - Non-static member variables | |
| // - Non static member functions | |
| // Note: Member operators are an exception to this, but apparently only | |
| // if the `DeclRefExpr` is used within the callee of a | |
| // `CXXOperatorCallExpr`. In other cases, for example when applying the | |
| // address-of operator, the `DeclRefExpr` is a prvalue. | |
| if (!S->isGLValue()) | |
| return; | |
| auto *DeclLoc = Env.getStorageLocation(*VD); | |
| if (DeclLoc == nullptr) | |
| return; | |
| Env.setStorageLocation(*S, *DeclLoc); | |
| } | |
| void VisitDeclStmt(const DeclStmt *S) { | |
| // Group decls are converted into single decls in the CFG so the cast below | |
| // is safe. | |
| const auto &D = *cast<VarDecl>(S->getSingleDecl()); | |
| ProcessVarDecl(D); | |
| } | |
| void ProcessVarDecl(const VarDecl &D) { | |
| // Static local vars are already initialized in `Environment`. | |
| if (D.hasGlobalStorage()) | |
| return; | |
| // If this is the holding variable for a `BindingDecl`, we may already | |
| // have a storage location set up -- so check. (See also explanation below | |
| // where we process the `BindingDecl`.) | |
| if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr) | |
| return; | |
| assert(Env.getStorageLocation(D) == nullptr); | |
| Env.setStorageLocation(D, Env.createObject(D)); | |
| // `DecompositionDecl` must be handled after we've interpreted the loc | |
| // itself, because the binding expression refers back to the | |
| // `DecompositionDecl` (even though it has no written name). | |
| if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) { | |
| // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This | |
| // needs to be evaluated after initializing the values in the storage for | |
| // VarDecl, as the bindings refer to them. | |
| // FIXME: Add support for ArraySubscriptExpr. | |
| // FIXME: Consider adding AST nodes used in BindingDecls to the CFG. | |
| for (const auto *B : Decomp->bindings()) { | |
| if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) { | |
| auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase()); | |
| if (DE == nullptr) | |
| continue; | |
| // ME and its base haven't been visited because they aren't included | |
| // in the statements of the CFG basic block. | |
| VisitDeclRefExpr(DE); | |
| VisitMemberExpr(ME); | |
| if (auto *Loc = Env.getStorageLocation(*ME)) | |
| Env.setStorageLocation(*B, *Loc); | |
| } else if (auto *VD = B->getHoldingVar()) { | |
| // Holding vars are used to back the `BindingDecl`s of tuple-like | |
| // types. The holding var declarations appear after the | |
| // `DecompositionDecl`, so we have to explicitly process them here | |
| // to know their storage location. They will be processed a second | |
| // time when we visit their `VarDecl`s, so we have code that protects | |
| // against this above. | |
| ProcessVarDecl(*VD); | |
| auto *VDLoc = Env.getStorageLocation(*VD); | |
| assert(VDLoc != nullptr); | |
| Env.setStorageLocation(*B, *VDLoc); | |
| } | |
| } | |
| } | |
| } | |
| void VisitCastExpr(const CastExpr *S) { | |
| const Expr *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| switch (S->getCastKind()) { | |
| case CK_IntegralToBoolean: { | |
| // This cast creates a new, boolean value from the integral value. We | |
| // model that with a fresh value in the environment, unless it's already a | |
| // boolean. | |
| if (auto *SubExprVal = | |
| dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr))) | |
| Env.setValue(*S, *SubExprVal); | |
| else | |
| // FIXME: If integer modeling is added, then update this code to create | |
| // the boolean based on the integer model. | |
| Env.setValue(*S, Env.makeAtomicBoolValue()); | |
| break; | |
| } | |
| case CK_LValueToRValue: { | |
| // When an L-value is used as an R-value, it may result in sharing, so we | |
| // need to unpack any nested `Top`s. | |
| auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env); | |
| if (SubExprVal == nullptr) | |
| break; | |
| Env.setValue(*S, *SubExprVal); | |
| break; | |
| } | |
| case CK_BaseToDerived: { | |
| // This is a cast of (single-layer) pointer or reference to a record type. | |
| // We should now model the fields for the derived type. | |
| // Get the RecordStorageLocation for the record object underneath. | |
| RecordStorageLocation *Loc = nullptr; | |
| if (S->getType()->isPointerType()) { | |
| auto *PV = Env.get<PointerValue>(*SubExpr); | |
| if (PV == nullptr) | |
| break; | |
| Loc = cast<RecordStorageLocation>(&PV->getPointeeLoc()); | |
| } else { | |
| assert(S->getType()->isRecordType()); | |
| if (SubExpr->isGLValue()) { | |
| Loc = Env.get<RecordStorageLocation>(*SubExpr); | |
| } else { | |
| Loc = &Env.getResultObjectLocation(*SubExpr); | |
| } | |
| } | |
| if (!Loc) { | |
| // Nowhere to add children or propagate from, so we're done. | |
| break; | |
| } | |
| // Get the derived record type underneath the reference or pointer. | |
| QualType Derived = S->getType().getNonReferenceType(); | |
| if (Derived->isPointerType()) { | |
| Derived = Derived->getPointeeType(); | |
| } | |
| // Add children to the storage location for fields (including synthetic | |
| // fields) of the derived type and initialize their values. | |
| for (const FieldDecl *Field : | |
| Env.getDataflowAnalysisContext().getModeledFields(Derived)) { | |
| assert(Field != nullptr); | |
| QualType FieldType = Field->getType(); | |
| if (FieldType->isReferenceType()) { | |
| Loc->addChild(*Field, nullptr); | |
| } else { | |
| Loc->addChild(*Field, &Env.createStorageLocation(FieldType)); | |
| } | |
| for (const auto &Entry : | |
| Env.getDataflowAnalysisContext().getSyntheticFields(Derived)) { | |
| Loc->addSyntheticField(Entry.getKey(), | |
| Env.createStorageLocation(Entry.getValue())); | |
| } | |
| } | |
| Env.initializeFieldsWithValues(*Loc, Derived); | |
| // Fall through to propagate SubExpr's StorageLocation to the CastExpr. | |
| [[fallthrough]]; | |
| } | |
| case CK_IntegralCast: | |
| // FIXME: This cast creates a new integral value from the | |
| // subexpression. But, because we don't model integers, we don't | |
| // distinguish between this new value and the underlying one. If integer | |
| // modeling is added, then update this code to create a fresh location and | |
| // value. | |
| case CK_UncheckedDerivedToBase: | |
| case CK_DerivedToBase: | |
| case CK_ConstructorConversion: | |
| case CK_UserDefinedConversion: | |
| case CK_NoOp: { | |
| // FIXME: Consider making `Environment::getStorageLocation` skip noop | |
| // expressions (this and other similar expressions in the file) instead | |
| // of assigning them storage locations. | |
| propagateValueOrStorageLocation(*SubExpr, *S, Env); | |
| break; | |
| } | |
| case CK_NullToPointer: { | |
| auto &NullPointerVal = | |
| Env.getOrCreateNullPointerValue(S->getType()->getPointeeType()); | |
| Env.setValue(*S, NullPointerVal); | |
| break; | |
| } | |
| case CK_NullToMemberPointer: | |
| // FIXME: Implement pointers to members. For now, don't associate a value | |
| // with this expression. | |
| break; | |
| case CK_FunctionToPointerDecay: { | |
| StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr); | |
| if (PointeeLoc == nullptr) | |
| break; | |
| Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc)); | |
| break; | |
| } | |
| case CK_BuiltinFnToFnPtr: | |
| // Despite its name, the result type of `BuiltinFnToFnPtr` is a function, | |
| // not a function pointer. In addition, builtin functions can only be | |
| // called directly; it is not legal to take their address. We therefore | |
| // don't need to create a value or storage location for them. | |
| break; | |
| default: | |
| break; | |
| } | |
| } | |
| void VisitUnaryOperator(const UnaryOperator *S) { | |
| const Expr *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| switch (S->getOpcode()) { | |
| case UO_Deref: { | |
| const auto *SubExprVal = Env.get<PointerValue>(*SubExpr); | |
| if (SubExprVal == nullptr) | |
| break; | |
| Env.setStorageLocation(*S, SubExprVal->getPointeeLoc()); | |
| break; | |
| } | |
| case UO_AddrOf: { | |
| // FIXME: Model pointers to members. | |
| if (S->getType()->isMemberPointerType()) | |
| break; | |
| if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr)) | |
| Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc)); | |
| break; | |
| } | |
| case UO_LNot: { | |
| auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)); | |
| if (SubExprVal == nullptr) | |
| break; | |
| Env.setValue(*S, Env.makeNot(*SubExprVal)); | |
| break; | |
| } | |
| case UO_PreInc: | |
| case UO_PreDec: | |
| // Propagate the storage location and clear out any value associated with | |
| // it (to represent the fact that the value has definitely changed). | |
| // To avoid generating unnecessary values, we leave it to the specific | |
| // analysis to create a new value if desired. | |
| propagateStorageLocation(*S->getSubExpr(), *S, Env); | |
| if (StorageLocation *Loc = Env.getStorageLocation(*S->getSubExpr())) | |
| Env.clearValue(*Loc); | |
| break; | |
| case UO_PostInc: | |
| case UO_PostDec: | |
| // Propagate the old value, then clear out any value associated with the | |
| // storage location (to represent the fact that the value has definitely | |
| // changed). See above for rationale. | |
| propagateValue(*S->getSubExpr(), *S, Env); | |
| if (StorageLocation *Loc = Env.getStorageLocation(*S->getSubExpr())) | |
| Env.clearValue(*Loc); | |
| break; | |
| default: | |
| break; | |
| } | |
| } | |
| void VisitCXXThisExpr(const CXXThisExpr *S) { | |
| auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation(); | |
| if (ThisPointeeLoc == nullptr) | |
| // Unions are not supported yet, and will not have a location for the | |
| // `this` expression's pointee. | |
| return; | |
| Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc)); | |
| } | |
| void VisitCXXNewExpr(const CXXNewExpr *S) { | |
| if (Value *Val = Env.createValue(S->getType())) | |
| Env.setValue(*S, *Val); | |
| } | |
| void VisitCXXDeleteExpr(const CXXDeleteExpr *S) { | |
| // Empty method. | |
| // We consciously don't do anything on deletes. Diagnosing double deletes | |
| // (for example) should be done by a specific analysis, not by the | |
| // framework. | |
| } | |
| void VisitReturnStmt(const ReturnStmt *S) { | |
| if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts) | |
| return; | |
| auto *Ret = S->getRetValue(); | |
| if (Ret == nullptr) | |
| return; | |
| if (Ret->isPRValue()) { | |
| if (Ret->getType()->isRecordType()) | |
| return; | |
| auto *Val = Env.getValue(*Ret); | |
| if (Val == nullptr) | |
| return; | |
| // FIXME: Model NRVO. | |
| Env.setReturnValue(Val); | |
| } else { | |
| auto *Loc = Env.getStorageLocation(*Ret); | |
| if (Loc == nullptr) | |
| return; | |
| // FIXME: Model NRVO. | |
| Env.setReturnStorageLocation(Loc); | |
| } | |
| } | |
| void VisitMemberExpr(const MemberExpr *S) { | |
| ValueDecl *Member = S->getMemberDecl(); | |
| assert(Member != nullptr); | |
| // FIXME: Consider assigning pointer values to function member expressions. | |
| if (Member->isFunctionOrFunctionTemplate()) | |
| return; | |
| // FIXME: if/when we add support for modeling enums, use that support here. | |
| if (isa<EnumConstantDecl>(Member)) | |
| return; | |
| if (auto *D = dyn_cast<VarDecl>(Member)) { | |
| if (D->hasGlobalStorage()) { | |
| auto *VarDeclLoc = Env.getStorageLocation(*D); | |
| if (VarDeclLoc == nullptr) | |
| return; | |
| Env.setStorageLocation(*S, *VarDeclLoc); | |
| return; | |
| } | |
| } | |
| RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env); | |
| if (BaseLoc == nullptr) | |
| return; | |
| auto *MemberLoc = BaseLoc->getChild(*Member); | |
| if (MemberLoc == nullptr) | |
| return; | |
| Env.setStorageLocation(*S, *MemberLoc); | |
| } | |
| void VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *S) { | |
| const Expr *ArgExpr = S->getExpr(); | |
| assert(ArgExpr != nullptr); | |
| propagateValueOrStorageLocation(*ArgExpr, *S, Env); | |
| if (S->isPRValue() && S->getType()->isRecordType()) { | |
| auto &Loc = Env.getResultObjectLocation(*S); | |
| Env.initializeFieldsWithValues(Loc); | |
| } | |
| } | |
| void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) { | |
| const Expr *InitExpr = S->getExpr(); | |
| assert(InitExpr != nullptr); | |
| // If this is a prvalue of record type, the handler for `*InitExpr` (if one | |
| // exists) will initialize the result object; there is no value to propgate | |
| // here. | |
| if (S->getType()->isRecordType() && S->isPRValue()) | |
| return; | |
| propagateValueOrStorageLocation(*InitExpr, *S, Env); | |
| } | |
| void VisitCXXConstructExpr(const CXXConstructExpr *S) { | |
| const CXXConstructorDecl *ConstructorDecl = S->getConstructor(); | |
| assert(ConstructorDecl != nullptr); | |
| // `CXXConstructExpr` can have array type if default-initializing an array | |
| // of records. We don't handle this specifically beyond potentially inlining | |
| // the call. | |
| if (!S->getType()->isRecordType()) { | |
| transferInlineCall(S, ConstructorDecl); | |
| return; | |
| } | |
| RecordStorageLocation &Loc = Env.getResultObjectLocation(*S); | |
| if (ConstructorDecl->isCopyOrMoveConstructor()) { | |
| // It is permissible for a copy/move constructor to have additional | |
| // parameters as long as they have default arguments defined for them. | |
| assert(S->getNumArgs() != 0); | |
| const Expr *Arg = S->getArg(0); | |
| assert(Arg != nullptr); | |
| auto *ArgLoc = Env.get<RecordStorageLocation>(*Arg); | |
| if (ArgLoc == nullptr) | |
| return; | |
| // Even if the copy/move constructor call is elidable, we choose to copy | |
| // the record in all cases (which isn't wrong, just potentially not | |
| // optimal). | |
| // | |
| // To handle cases of base class initializers in constructors, where a | |
| // sibling derived class can be used to initialize a shared-base-class | |
| // subobject through a DerivedToBase cast, intentionally copy only the | |
| // parts of `ArgLoc` that are part of the base class being initialized. | |
| // This is necessary because the type of `Loc` in these cases is the | |
| // derived type ultimately being constructed, not the type of the base | |
| // class subobject. | |
| copyRecord(*ArgLoc, Loc, Env, S->getType()); | |
| return; | |
| } | |
| Env.initializeFieldsWithValues(Loc, S->getType()); | |
| transferInlineCall(S, ConstructorDecl); | |
| } | |
| void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) { | |
| if (S->getOperator() == OO_Equal) { | |
| assert(S->getNumArgs() == 2); | |
| const Expr *Arg0 = S->getArg(0); | |
| assert(Arg0 != nullptr); | |
| const Expr *Arg1 = S->getArg(1); | |
| assert(Arg1 != nullptr); | |
| // Evaluate only copy and move assignment operators. | |
| const auto *Method = | |
| dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee()); | |
| if (!Method) | |
| return; | |
| if (!Method->isCopyAssignmentOperator() && | |
| !Method->isMoveAssignmentOperator()) | |
| return; | |
| RecordStorageLocation *LocSrc = nullptr; | |
| if (Arg1->isPRValue()) { | |
| LocSrc = &Env.getResultObjectLocation(*Arg1); | |
| } else { | |
| LocSrc = Env.get<RecordStorageLocation>(*Arg1); | |
| } | |
| auto *LocDst = Env.get<RecordStorageLocation>(*Arg0); | |
| if (LocSrc == nullptr || LocDst == nullptr) | |
| return; | |
| // If the destination object here is of a derived class, `Arg0` may be a | |
| // cast of that object to a base class, and the source object may be of a | |
| // sibling derived class. To handle these cases, ensure we are copying | |
| // only the fields for `Arg0`'s type, not the type of the underlying | |
| // `RecordStorageLocation`. | |
| copyRecord(*LocSrc, *LocDst, Env, Arg0->getType()); | |
| // The assignment operator can have an arbitrary return type. We model the | |
| // return value only if the return type is the same as or a base class of | |
| // the destination type. | |
| if (S->getType().getCanonicalType().getUnqualifiedType() != | |
| LocDst->getType().getCanonicalType().getUnqualifiedType()) { | |
| auto ReturnDecl = S->getType()->getAsCXXRecordDecl(); | |
| auto DstDecl = LocDst->getType()->getAsCXXRecordDecl(); | |
| if (ReturnDecl == nullptr || DstDecl == nullptr) | |
| return; | |
| if (!DstDecl->isDerivedFrom(ReturnDecl)) | |
| return; | |
| } | |
| if (S->isGLValue()) | |
| Env.setStorageLocation(*S, *LocDst); | |
| else | |
| copyRecord(*LocDst, Env.getResultObjectLocation(*S), Env); | |
| return; | |
| } | |
| // `CXXOperatorCallExpr` can be a prvalue. Call `VisitCallExpr`() to | |
| // initialize the prvalue's fields with values. | |
| VisitCallExpr(S); | |
| } | |
| void VisitCXXRewrittenBinaryOperator(const CXXRewrittenBinaryOperator *RBO) { | |
| propagateValue(*RBO->getSemanticForm(), *RBO, Env); | |
| } | |
| void VisitCallExpr(const CallExpr *S) { | |
| // Of clang's builtins, only `__builtin_expect` is handled explicitly, since | |
| // others (like trap, debugtrap, and unreachable) are handled by CFG | |
| // construction. | |
| if (S->isCallToStdMove()) { | |
| assert(S->getNumArgs() == 1); | |
| const Expr *Arg = S->getArg(0); | |
| assert(Arg != nullptr); | |
| auto *ArgLoc = Env.getStorageLocation(*Arg); | |
| if (ArgLoc == nullptr) | |
| return; | |
| Env.setStorageLocation(*S, *ArgLoc); | |
| } else if (S->getDirectCallee() != nullptr && | |
| S->getDirectCallee()->getBuiltinID() == | |
| Builtin::BI__builtin_expect) { | |
| assert(S->getNumArgs() > 0); | |
| assert(S->getArg(0) != nullptr); | |
| auto *ArgVal = Env.getValue(*S->getArg(0)); | |
| if (ArgVal == nullptr) | |
| return; | |
| Env.setValue(*S, *ArgVal); | |
| } else if (const FunctionDecl *F = S->getDirectCallee()) { | |
| transferInlineCall(S, F); | |
| // If this call produces a prvalue of record type, initialize its fields | |
| // with values. | |
| if (S->getType()->isRecordType() && S->isPRValue()) { | |
| RecordStorageLocation &Loc = Env.getResultObjectLocation(*S); | |
| Env.initializeFieldsWithValues(Loc); | |
| } | |
| } | |
| } | |
| void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) { | |
| const Expr *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| StorageLocation &Loc = Env.createStorageLocation(*S); | |
| Env.setStorageLocation(*S, Loc); | |
| if (SubExpr->getType()->isRecordType()) | |
| // Nothing else left to do -- we initialized the record when transferring | |
| // `SubExpr`. | |
| return; | |
| if (Value *SubExprVal = Env.getValue(*SubExpr)) | |
| Env.setValue(Loc, *SubExprVal); | |
| } | |
| void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) { | |
| const Expr *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| propagateValue(*SubExpr, *S, Env); | |
| } | |
| void VisitConditionalOperator(const ConditionalOperator *S) { | |
| const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr()); | |
| const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr()); | |
| if (TrueEnv == nullptr || FalseEnv == nullptr) { | |
| // If the true or false branch is dead, we may not have an environment for | |
| // it. We could handle this specifically by forwarding the value or | |
| // location of the live branch, but this case is rare enough that this | |
| // probably isn't worth the additional complexity. | |
| return; | |
| } | |
| if (S->isGLValue()) { | |
| StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr()); | |
| StorageLocation *FalseLoc = | |
| FalseEnv->getStorageLocation(*S->getFalseExpr()); | |
| if (TrueLoc == FalseLoc && TrueLoc != nullptr) { | |
| Env.setStorageLocation(*S, *TrueLoc); | |
| } else if (!S->getType()->isRecordType()) { | |
| // Ideally, we would have something like an "alias set" to say that the | |
| // result StorageLocation can be either of the locations from the | |
| // TrueEnv or FalseEnv. Then, when this ConditionalOperator is | |
| // (a) used in an LValueToRValue cast, the value is the join of all of | |
| // the values in the alias set. | |
| // (b) or, used in an assignment to the resulting LValue, the assignment | |
| // *may* update all of the locations in the alias set. | |
| // For now, we do the simpler thing of creating a new StorageLocation | |
| // and joining the values right away, handling only case (a). | |
| // Otherwise, the dataflow framework needs to be updated be able to | |
| // represent alias sets and weak updates (for the "may"). | |
| if (Value *Val = Environment::joinValues( | |
| S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv, | |
| FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, | |
| Model)) { | |
| StorageLocation &Loc = Env.createStorageLocation(*S); | |
| Env.setStorageLocation(*S, Loc); | |
| Env.setValue(Loc, *Val); | |
| } | |
| } | |
| } else if (!S->getType()->isRecordType()) { | |
| // The conditional operator can evaluate to either of the values of the | |
| // two branches. To model this, join these two values together to yield | |
| // the result of the conditional operator. | |
| // Note: Most joins happen in `computeBlockInputState()`, but this case is | |
| // different: | |
| // - `computeBlockInputState()` (which in turn calls `Environment::join()` | |
| // joins values associated with the _same_ expression or storage | |
| // location, then associates the joined value with that expression or | |
| // storage location. This join has nothing to do with transfer -- | |
| // instead, it joins together the results of performing transfer on two | |
| // different blocks. | |
| // - Here, we join values associated with _different_ expressions (the | |
| // true and false branch), then associate the joined value with a third | |
| // expression (the conditional operator itself). This join is what it | |
| // means to perform transfer on the conditional operator. | |
| if (Value *Val = Environment::joinValues( | |
| S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv, | |
| FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, Model)) | |
| Env.setValue(*S, *Val); | |
| } | |
| } | |
| void VisitInitListExpr(const InitListExpr *S) { | |
| QualType Type = S->getType(); | |
| if (!Type->isRecordType()) { | |
| // Until array initialization is implemented, we skip arrays and don't | |
| // need to care about cases where `getNumInits() > 1`. | |
| if (!Type->isArrayType() && S->getNumInits() == 1) | |
| propagateValueOrStorageLocation(*S->getInit(0), *S, Env); | |
| return; | |
| } | |
| // If the initializer list is transparent, there's nothing to do. | |
| if (S->isSemanticForm() && S->isTransparent()) | |
| return; | |
| RecordStorageLocation &Loc = Env.getResultObjectLocation(*S); | |
| // Initialization of base classes and fields of record type happens when we | |
| // visit the nested `CXXConstructExpr` or `InitListExpr` for that base class | |
| // or field. We therefore only need to deal with fields of non-record type | |
| // here. | |
| RecordInitListHelper InitListHelper(S); | |
| for (auto [Field, Init] : InitListHelper.field_inits()) { | |
| if (Field->getType()->isRecordType()) | |
| continue; | |
| if (Field->getType()->isReferenceType()) { | |
| assert(Field->getType().getCanonicalType()->getPointeeType() == | |
| Init->getType().getCanonicalType()); | |
| Loc.setChild(*Field, &Env.createObject(Field->getType(), Init)); | |
| continue; | |
| } | |
| assert(Field->getType().getCanonicalType().getUnqualifiedType() == | |
| Init->getType().getCanonicalType().getUnqualifiedType()); | |
| StorageLocation *FieldLoc = Loc.getChild(*Field); | |
| // Locations for non-reference fields must always be non-null. | |
| assert(FieldLoc != nullptr); | |
| Value *Val = Env.getValue(*Init); | |
| if (Val == nullptr && isa<ImplicitValueInitExpr>(Init) && | |
| Init->getType()->isPointerType()) | |
| Val = | |
| &Env.getOrCreateNullPointerValue(Init->getType()->getPointeeType()); | |
| if (Val == nullptr) | |
| Val = Env.createValue(Field->getType()); | |
| if (Val != nullptr) | |
| Env.setValue(*FieldLoc, *Val); | |
| } | |
| for (const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) { | |
| QualType FieldType = FieldLoc->getType(); | |
| if (FieldType->isRecordType()) { | |
| Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc)); | |
| } else { | |
| if (Value *Val = Env.createValue(FieldType)) | |
| Env.setValue(*FieldLoc, *Val); | |
| } | |
| } | |
| // FIXME: Implement array initialization. | |
| } | |
| void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) { | |
| Env.setValue(*S, Env.getBoolLiteralValue(S->getValue())); | |
| } | |
| void VisitIntegerLiteral(const IntegerLiteral *S) { | |
| Env.setValue(*S, Env.getIntLiteralValue(S->getValue())); | |
| } | |
| void VisitParenExpr(const ParenExpr *S) { | |
| // The CFG does not contain `ParenExpr` as top-level statements in basic | |
| // blocks, however manual traversal to sub-expressions may encounter them. | |
| // Redirect to the sub-expression. | |
| auto *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| Visit(SubExpr); | |
| } | |
| void VisitExprWithCleanups(const ExprWithCleanups *S) { | |
| // The CFG does not contain `ExprWithCleanups` as top-level statements in | |
| // basic blocks, however manual traversal to sub-expressions may encounter | |
| // them. Redirect to the sub-expression. | |
| auto *SubExpr = S->getSubExpr(); | |
| assert(SubExpr != nullptr); | |
| Visit(SubExpr); | |
| } | |
| private: | |
| /// Returns the value for the sub-expression `SubExpr` of a logic operator. | |
| BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) { | |
| // `SubExpr` and its parent logic operator might be part of different basic | |
| // blocks. We try to access the value that is assigned to `SubExpr` in the | |
| // corresponding environment. | |
| if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) | |
| if (auto *Val = | |
| dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr))) | |
| return *Val; | |
| // The sub-expression may lie within a basic block that isn't reachable, | |
| // even if we need it to evaluate the current (reachable) expression | |
| // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr` | |
| // within the current environment and then try to get the value that gets | |
| // assigned to it. | |
| if (Env.getValue(SubExpr) == nullptr) | |
| Visit(&SubExpr); | |
| if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr))) | |
| return *Val; | |
| // If the value of `SubExpr` is still unknown, we create a fresh symbolic | |
| // boolean value for it. | |
| return Env.makeAtomicBoolValue(); | |
| } | |
| // If context sensitivity is enabled, try to analyze the body of the callee | |
| // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`. | |
| template <typename E> | |
| void transferInlineCall(const E *S, const FunctionDecl *F) { | |
| const auto &Options = Env.getDataflowAnalysisContext().getOptions(); | |
| if (!(Options.ContextSensitiveOpts && | |
| Env.canDescend(Options.ContextSensitiveOpts->Depth, F))) | |
| return; | |
| const AdornedCFG *ACFG = Env.getDataflowAnalysisContext().getAdornedCFG(F); | |
| if (!ACFG) | |
| return; | |
| // FIXME: We don't support context-sensitive analysis of recursion, so | |
| // we should return early here if `F` is the same as the `FunctionDecl` | |
| // holding `S` itself. | |
| auto ExitBlock = ACFG->getCFG().getExit().getBlockID(); | |
| auto CalleeEnv = Env.pushCall(S); | |
| // FIXME: Use the same analysis as the caller for the callee. Note, | |
| // though, that doing so would require support for changing the analysis's | |
| // ASTContext. | |
| auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(), | |
| DataflowAnalysisOptions{Options}); | |
| auto BlockToOutputState = | |
| dataflow::runDataflowAnalysis(*ACFG, Analysis, CalleeEnv); | |
| assert(BlockToOutputState); | |
| assert(ExitBlock < BlockToOutputState->size()); | |
| auto &ExitState = (*BlockToOutputState)[ExitBlock]; | |
| assert(ExitState); | |
| Env.popCall(S, ExitState->Env); | |
| } | |
| const StmtToEnvMap &StmtToEnv; | |
| Environment &Env; | |
| Environment::ValueModel &Model; | |
| }; | |
| } // namespace | |
| void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, | |
| Environment::ValueModel &Model) { | |
| TransferVisitor(StmtToEnv, Env, Model).Visit(&S); | |
| } | |
| } // namespace dataflow | |
| } // namespace clang |