984 lines · cpp
1//===-- Transfer.cpp --------------------------------------------*- C++ -*-===//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 transfer functions that evaluate program statements and10// update an environment accordingly.11//12//===----------------------------------------------------------------------===//13 14#include "clang/Analysis/FlowSensitive/Transfer.h"15#include "clang/AST/Decl.h"16#include "clang/AST/DeclBase.h"17#include "clang/AST/DeclCXX.h"18#include "clang/AST/Expr.h"19#include "clang/AST/ExprCXX.h"20#include "clang/AST/OperationKinds.h"21#include "clang/AST/Stmt.h"22#include "clang/AST/StmtVisitor.h"23#include "clang/AST/Type.h"24#include "clang/Analysis/FlowSensitive/ASTOps.h"25#include "clang/Analysis/FlowSensitive/AdornedCFG.h"26#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"27#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"28#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"29#include "clang/Analysis/FlowSensitive/RecordOps.h"30#include "clang/Analysis/FlowSensitive/StorageLocation.h"31#include "clang/Analysis/FlowSensitive/Value.h"32#include "clang/Basic/Builtins.h"33#include "clang/Basic/LLVM.h"34#include "clang/Basic/OperatorKinds.h"35#include "llvm/Support/Casting.h"36#include <assert.h>37#include <cassert>38 39#define DEBUG_TYPE "dataflow"40 41namespace clang {42namespace dataflow {43 44const Environment *StmtToEnvMap::getEnvironment(const Stmt &S) const {45 const CFGBlock *Block = ACFG.blockForStmt(S);46 if (Block == nullptr) {47 assert(false);48 return nullptr;49 }50 if (!ACFG.isBlockReachable(*Block))51 return nullptr;52 if (Block->getBlockID() == CurBlockID)53 return &CurState.Env;54 const auto &State = BlockToState[Block->getBlockID()];55 if (!(State))56 return nullptr;57 return &State->Env;58}59 60static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,61 Environment &Env) {62 Value *LHSValue = Env.getValue(LHS);63 Value *RHSValue = Env.getValue(RHS);64 65 // When two unsupported values are compared, both are nullptr. Only supported66 // values should evaluate to equal.67 if (LHSValue == RHSValue && LHSValue)68 return Env.getBoolLiteralValue(true);69 70 // Special case: `NullPtrLiteralExpr == itself`. When both sides are untyped71 // nullptr, they do not have an assigned Value, but they compare equal.72 if (LHS.getType()->isNullPtrType() && RHS.getType()->isNullPtrType())73 return Env.getBoolLiteralValue(true);74 75 if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))76 if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))77 return Env.makeIff(*LHSBool, *RHSBool);78 79 if (auto *LHSPtr = dyn_cast_or_null<PointerValue>(LHSValue))80 if (auto *RHSPtr = dyn_cast_or_null<PointerValue>(RHSValue))81 // If the storage locations are the same, the pointers definitely compare82 // the same. If the storage locations are different, they may still alias,83 // so we fall through to the case below that returns an atom.84 if (&LHSPtr->getPointeeLoc() == &RHSPtr->getPointeeLoc())85 return Env.getBoolLiteralValue(true);86 87 return Env.makeAtomicBoolValue();88}89 90static BoolValue &unpackValue(BoolValue &V, Environment &Env) {91 if (auto *Top = llvm::dyn_cast<TopBoolValue>(&V)) {92 auto &A = Env.getDataflowAnalysisContext().arena();93 return A.makeBoolValue(A.makeAtomRef(Top->getAtom()));94 }95 return V;96}97 98// Unpacks the value (if any) associated with `E` and updates `E` to the new99// value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,100// by skipping past the reference.101static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {102 auto *Loc = Env.getStorageLocation(E);103 if (Loc == nullptr)104 return nullptr;105 auto *Val = Env.getValue(*Loc);106 107 auto *B = dyn_cast_or_null<BoolValue>(Val);108 if (B == nullptr)109 return Val;110 111 auto &UnpackedVal = unpackValue(*B, Env);112 if (&UnpackedVal == Val)113 return Val;114 Env.setValue(*Loc, UnpackedVal);115 return &UnpackedVal;116}117 118static void propagateValue(const Expr &From, const Expr &To, Environment &Env) {119 if (From.getType()->isRecordType())120 return;121 if (auto *Val = Env.getValue(From))122 Env.setValue(To, *Val);123}124 125static void propagateStorageLocation(const Expr &From, const Expr &To,126 Environment &Env) {127 if (auto *Loc = Env.getStorageLocation(From))128 Env.setStorageLocation(To, *Loc);129}130 131// Propagates the value or storage location of `From` to `To` in cases where132// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff133// `From` is a glvalue.134static void propagateValueOrStorageLocation(const Expr &From, const Expr &To,135 Environment &Env) {136 assert(From.isGLValue() == To.isGLValue());137 if (From.isGLValue())138 propagateStorageLocation(From, To, Env);139 else140 propagateValue(From, To, Env);141}142 143namespace {144 145class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {146public:147 TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,148 Environment::ValueModel &Model)149 : StmtToEnv(StmtToEnv), Env(Env), Model(Model) {}150 151 void VisitBinaryOperator(const BinaryOperator *S) {152 const Expr *LHS = S->getLHS();153 assert(LHS != nullptr);154 155 const Expr *RHS = S->getRHS();156 assert(RHS != nullptr);157 158 // Do compound assignments up-front, as there are so many of them and we159 // don't want to list all of them in the switch statement below.160 // To avoid generating unnecessary values, we don't create a new value but161 // instead leave it to the specific analysis to do this if desired.162 if (S->isCompoundAssignmentOp())163 propagateStorageLocation(*S->getLHS(), *S, Env);164 165 switch (S->getOpcode()) {166 case BO_Assign: {167 auto *LHSLoc = Env.getStorageLocation(*LHS);168 if (LHSLoc == nullptr)169 break;170 171 auto *RHSVal = Env.getValue(*RHS);172 if (RHSVal == nullptr)173 break;174 175 // Assign a value to the storage location of the left-hand side.176 Env.setValue(*LHSLoc, *RHSVal);177 178 // Assign a storage location for the whole expression.179 Env.setStorageLocation(*S, *LHSLoc);180 break;181 }182 case BO_LAnd:183 case BO_LOr: {184 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);185 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);186 187 if (S->getOpcode() == BO_LAnd)188 Env.setValue(*S, Env.makeAnd(LHSVal, RHSVal));189 else190 Env.setValue(*S, Env.makeOr(LHSVal, RHSVal));191 break;192 }193 case BO_NE:194 case BO_EQ: {195 auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);196 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue197 : Env.makeNot(LHSEqRHSValue));198 break;199 }200 case BO_Comma: {201 propagateValueOrStorageLocation(*RHS, *S, Env);202 break;203 }204 default:205 break;206 }207 }208 209 void VisitDeclRefExpr(const DeclRefExpr *S) {210 const ValueDecl *VD = S->getDecl();211 assert(VD != nullptr);212 213 // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a214 // `StorageLocation`, and there's also no sensible `Value` that we can215 // assign to them. Examples:216 // - Non-static member variables217 // - Non static member functions218 // Note: Member operators are an exception to this, but apparently only219 // if the `DeclRefExpr` is used within the callee of a220 // `CXXOperatorCallExpr`. In other cases, for example when applying the221 // address-of operator, the `DeclRefExpr` is a prvalue.222 if (!S->isGLValue())223 return;224 225 auto *DeclLoc = Env.getStorageLocation(*VD);226 if (DeclLoc == nullptr)227 return;228 229 Env.setStorageLocation(*S, *DeclLoc);230 }231 232 void VisitDeclStmt(const DeclStmt *S) {233 // Group decls are converted into single decls in the CFG so the cast below234 // is safe.235 const auto &D = *cast<VarDecl>(S->getSingleDecl());236 237 ProcessVarDecl(D);238 }239 240 void ProcessVarDecl(const VarDecl &D) {241 // Static local vars are already initialized in `Environment`.242 if (D.hasGlobalStorage())243 return;244 245 // If this is the holding variable for a `BindingDecl`, we may already246 // have a storage location set up -- so check. (See also explanation below247 // where we process the `BindingDecl`.)248 if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr)249 return;250 251 assert(Env.getStorageLocation(D) == nullptr);252 253 Env.setStorageLocation(D, Env.createObject(D));254 255 // `DecompositionDecl` must be handled after we've interpreted the loc256 // itself, because the binding expression refers back to the257 // `DecompositionDecl` (even though it has no written name).258 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {259 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This260 // needs to be evaluated after initializing the values in the storage for261 // VarDecl, as the bindings refer to them.262 // FIXME: Add support for ArraySubscriptExpr.263 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.264 for (const auto *B : Decomp->bindings()) {265 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {266 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());267 if (DE == nullptr)268 continue;269 270 // ME and its base haven't been visited because they aren't included271 // in the statements of the CFG basic block.272 VisitDeclRefExpr(DE);273 VisitMemberExpr(ME);274 275 if (auto *Loc = Env.getStorageLocation(*ME))276 Env.setStorageLocation(*B, *Loc);277 } else if (auto *VD = B->getHoldingVar()) {278 // Holding vars are used to back the `BindingDecl`s of tuple-like279 // types. The holding var declarations appear after the280 // `DecompositionDecl`, so we have to explicitly process them here281 // to know their storage location. They will be processed a second282 // time when we visit their `VarDecl`s, so we have code that protects283 // against this above.284 ProcessVarDecl(*VD);285 auto *VDLoc = Env.getStorageLocation(*VD);286 assert(VDLoc != nullptr);287 Env.setStorageLocation(*B, *VDLoc);288 }289 }290 }291 }292 293 void VisitCastExpr(const CastExpr *S) {294 const Expr *SubExpr = S->getSubExpr();295 assert(SubExpr != nullptr);296 297 switch (S->getCastKind()) {298 case CK_IntegralToBoolean: {299 // This cast creates a new, boolean value from the integral value. We300 // model that with a fresh value in the environment, unless it's already a301 // boolean.302 if (auto *SubExprVal =303 dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)))304 Env.setValue(*S, *SubExprVal);305 else306 // FIXME: If integer modeling is added, then update this code to create307 // the boolean based on the integer model.308 Env.setValue(*S, Env.makeAtomicBoolValue());309 break;310 }311 312 case CK_LValueToRValue: {313 // When an L-value is used as an R-value, it may result in sharing, so we314 // need to unpack any nested `Top`s.315 auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);316 if (SubExprVal == nullptr)317 break;318 319 Env.setValue(*S, *SubExprVal);320 break;321 }322 323 case CK_BaseToDerived: {324 // This is a cast of (single-layer) pointer or reference to a record type.325 // We should now model the fields for the derived type.326 327 // Get the RecordStorageLocation for the record object underneath.328 RecordStorageLocation *Loc = nullptr;329 if (S->getType()->isPointerType()) {330 auto *PV = Env.get<PointerValue>(*SubExpr);331 assert(PV != nullptr);332 if (PV == nullptr)333 break;334 Loc = cast<RecordStorageLocation>(&PV->getPointeeLoc());335 } else {336 assert(S->getType()->isRecordType());337 if (SubExpr->isGLValue()) {338 Loc = Env.get<RecordStorageLocation>(*SubExpr);339 } else {340 Loc = &Env.getResultObjectLocation(*SubExpr);341 }342 }343 if (!Loc) {344 // Nowhere to add children or propagate from, so we're done.345 break;346 }347 348 // Get the derived record type underneath the reference or pointer.349 QualType Derived = S->getType().getNonReferenceType();350 if (Derived->isPointerType()) {351 Derived = Derived->getPointeeType();352 }353 354 // Add children to the storage location for fields (including synthetic355 // fields) of the derived type and initialize their values.356 for (const FieldDecl *Field :357 Env.getDataflowAnalysisContext().getModeledFields(Derived)) {358 assert(Field != nullptr);359 QualType FieldType = Field->getType();360 if (FieldType->isReferenceType()) {361 Loc->addChild(*Field, nullptr);362 } else {363 Loc->addChild(*Field, &Env.createStorageLocation(FieldType));364 }365 366 for (const auto &Entry :367 Env.getDataflowAnalysisContext().getSyntheticFields(Derived)) {368 Loc->addSyntheticField(Entry.getKey(),369 Env.createStorageLocation(Entry.getValue()));370 }371 }372 Env.initializeFieldsWithValues(*Loc, Derived);373 374 // Fall through to propagate SubExpr's StorageLocation to the CastExpr.375 [[fallthrough]];376 }377 case CK_IntegralCast:378 // FIXME: This cast creates a new integral value from the379 // subexpression. But, because we don't model integers, we don't380 // distinguish between this new value and the underlying one. If integer381 // modeling is added, then update this code to create a fresh location and382 // value.383 case CK_UncheckedDerivedToBase:384 case CK_DerivedToBase:385 case CK_ConstructorConversion:386 case CK_UserDefinedConversion:387 case CK_NoOp: {388 // FIXME: Consider making `Environment::getStorageLocation` skip noop389 // expressions (this and other similar expressions in the file) instead390 // of assigning them storage locations.391 propagateValueOrStorageLocation(*SubExpr, *S, Env);392 break;393 }394 case CK_NullToPointer: {395 auto &NullPointerVal =396 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());397 Env.setValue(*S, NullPointerVal);398 break;399 }400 case CK_NullToMemberPointer:401 // FIXME: Implement pointers to members. For now, don't associate a value402 // with this expression.403 break;404 case CK_FunctionToPointerDecay: {405 StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr);406 if (PointeeLoc == nullptr)407 break;408 409 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));410 break;411 }412 case CK_BuiltinFnToFnPtr:413 // Despite its name, the result type of `BuiltinFnToFnPtr` is a function,414 // not a function pointer. In addition, builtin functions can only be415 // called directly; it is not legal to take their address. We therefore416 // don't need to create a value or storage location for them.417 break;418 default:419 break;420 }421 }422 423 void VisitUnaryOperator(const UnaryOperator *S) {424 const Expr *SubExpr = S->getSubExpr();425 assert(SubExpr != nullptr);426 427 switch (S->getOpcode()) {428 case UO_Deref: {429 const auto *SubExprVal = Env.get<PointerValue>(*SubExpr);430 if (SubExprVal == nullptr)431 break;432 433 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());434 break;435 }436 case UO_AddrOf: {437 // FIXME: Model pointers to members.438 if (S->getType()->isMemberPointerType())439 break;440 441 if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr))442 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));443 break;444 }445 case UO_LNot: {446 auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr));447 if (SubExprVal == nullptr)448 break;449 450 Env.setValue(*S, Env.makeNot(*SubExprVal));451 break;452 }453 case UO_PreInc:454 case UO_PreDec:455 // Propagate the storage location and clear out any value associated with456 // it (to represent the fact that the value has definitely changed).457 // To avoid generating unnecessary values, we leave it to the specific458 // analysis to create a new value if desired.459 propagateStorageLocation(*S->getSubExpr(), *S, Env);460 if (StorageLocation *Loc = Env.getStorageLocation(*S->getSubExpr()))461 Env.clearValue(*Loc);462 break;463 case UO_PostInc:464 case UO_PostDec:465 // Propagate the old value, then clear out any value associated with the466 // storage location (to represent the fact that the value has definitely467 // changed). See above for rationale.468 propagateValue(*S->getSubExpr(), *S, Env);469 if (StorageLocation *Loc = Env.getStorageLocation(*S->getSubExpr()))470 Env.clearValue(*Loc);471 break;472 default:473 break;474 }475 }476 477 void VisitCXXThisExpr(const CXXThisExpr *S) {478 auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();479 if (ThisPointeeLoc == nullptr)480 // Unions are not supported yet, and will not have a location for the481 // `this` expression's pointee.482 return;483 484 Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc));485 }486 487 void VisitCXXNewExpr(const CXXNewExpr *S) {488 if (Value *Val = Env.createValue(S->getType()))489 Env.setValue(*S, *Val);490 }491 492 void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {493 // Empty method.494 // We consciously don't do anything on deletes. Diagnosing double deletes495 // (for example) should be done by a specific analysis, not by the496 // framework.497 }498 499 void VisitReturnStmt(const ReturnStmt *S) {500 if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)501 return;502 503 auto *Ret = S->getRetValue();504 if (Ret == nullptr)505 return;506 507 if (Ret->isPRValue()) {508 if (Ret->getType()->isRecordType())509 return;510 511 auto *Val = Env.getValue(*Ret);512 if (Val == nullptr)513 return;514 515 // FIXME: Model NRVO.516 Env.setReturnValue(Val);517 } else {518 auto *Loc = Env.getStorageLocation(*Ret);519 if (Loc == nullptr)520 return;521 522 // FIXME: Model NRVO.523 Env.setReturnStorageLocation(Loc);524 }525 }526 527 void VisitMemberExpr(const MemberExpr *S) {528 ValueDecl *Member = S->getMemberDecl();529 assert(Member != nullptr);530 531 // FIXME: Consider assigning pointer values to function member expressions.532 if (Member->isFunctionOrFunctionTemplate())533 return;534 535 // FIXME: if/when we add support for modeling enums, use that support here.536 if (isa<EnumConstantDecl>(Member))537 return;538 539 if (auto *D = dyn_cast<VarDecl>(Member)) {540 if (D->hasGlobalStorage()) {541 auto *VarDeclLoc = Env.getStorageLocation(*D);542 if (VarDeclLoc == nullptr)543 return;544 545 Env.setStorageLocation(*S, *VarDeclLoc);546 return;547 }548 }549 550 RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);551 if (BaseLoc == nullptr)552 return;553 554 auto *MemberLoc = BaseLoc->getChild(*Member);555 if (MemberLoc == nullptr)556 return;557 Env.setStorageLocation(*S, *MemberLoc);558 }559 560 void VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *S) {561 const Expr *ArgExpr = S->getExpr();562 assert(ArgExpr != nullptr);563 propagateValueOrStorageLocation(*ArgExpr, *S, Env);564 565 if (S->isPRValue() && S->getType()->isRecordType()) {566 auto &Loc = Env.getResultObjectLocation(*S);567 Env.initializeFieldsWithValues(Loc);568 }569 }570 571 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {572 const Expr *InitExpr = S->getExpr();573 assert(InitExpr != nullptr);574 575 // If this is a prvalue of record type, the handler for `*InitExpr` (if one576 // exists) will initialize the result object; there is no value to propgate577 // here.578 if (S->getType()->isRecordType() && S->isPRValue())579 return;580 581 propagateValueOrStorageLocation(*InitExpr, *S, Env);582 }583 584 void VisitCXXConstructExpr(const CXXConstructExpr *S) {585 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();586 assert(ConstructorDecl != nullptr);587 588 // `CXXConstructExpr` can have array type if default-initializing an array589 // of records. We don't handle this specifically beyond potentially inlining590 // the call.591 if (!S->getType()->isRecordType()) {592 transferInlineCall(S, ConstructorDecl);593 return;594 }595 596 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);597 598 if (ConstructorDecl->isCopyOrMoveConstructor()) {599 // It is permissible for a copy/move constructor to have additional600 // parameters as long as they have default arguments defined for them.601 assert(S->getNumArgs() != 0);602 603 const Expr *Arg = S->getArg(0);604 assert(Arg != nullptr);605 606 auto *ArgLoc = Env.get<RecordStorageLocation>(*Arg);607 if (ArgLoc == nullptr)608 return;609 610 // Even if the copy/move constructor call is elidable, we choose to copy611 // the record in all cases (which isn't wrong, just potentially not612 // optimal).613 //614 // To handle cases of base class initializers in constructors, where a615 // sibling derived class can be used to initialize a shared-base-class616 // subobject through a DerivedToBase cast, intentionally copy only the617 // parts of `ArgLoc` that are part of the base class being initialized.618 // This is necessary because the type of `Loc` in these cases is the619 // derived type ultimately being constructed, not the type of the base620 // class subobject.621 copyRecord(*ArgLoc, Loc, Env, S->getType());622 return;623 }624 625 Env.initializeFieldsWithValues(Loc, S->getType());626 627 transferInlineCall(S, ConstructorDecl);628 }629 630 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {631 if (S->getOperator() == OO_Equal) {632 assert(S->getNumArgs() == 2);633 634 const Expr *Arg0 = S->getArg(0);635 assert(Arg0 != nullptr);636 637 const Expr *Arg1 = S->getArg(1);638 assert(Arg1 != nullptr);639 640 // Evaluate only copy and move assignment operators.641 const auto *Method =642 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());643 if (!Method)644 return;645 if (!Method->isCopyAssignmentOperator() &&646 !Method->isMoveAssignmentOperator())647 return;648 649 RecordStorageLocation *LocSrc = nullptr;650 if (Arg1->isPRValue()) {651 LocSrc = &Env.getResultObjectLocation(*Arg1);652 } else {653 LocSrc = Env.get<RecordStorageLocation>(*Arg1);654 }655 auto *LocDst = Env.get<RecordStorageLocation>(*Arg0);656 657 if (LocSrc == nullptr || LocDst == nullptr)658 return;659 660 // If the destination object here is of a derived class, `Arg0` may be a661 // cast of that object to a base class, and the source object may be of a662 // sibling derived class. To handle these cases, ensure we are copying663 // only the fields for `Arg0`'s type, not the type of the underlying664 // `RecordStorageLocation`.665 copyRecord(*LocSrc, *LocDst, Env, Arg0->getType());666 667 // The assignment operator can have an arbitrary return type. We model the668 // return value only if the return type is the same as or a base class of669 // the destination type.670 if (S->getType().getCanonicalType().getUnqualifiedType() !=671 LocDst->getType().getCanonicalType().getUnqualifiedType()) {672 auto ReturnDecl = S->getType()->getAsCXXRecordDecl();673 auto DstDecl = LocDst->getType()->getAsCXXRecordDecl();674 if (ReturnDecl == nullptr || DstDecl == nullptr)675 return;676 if (!DstDecl->isDerivedFrom(ReturnDecl))677 return;678 }679 680 if (S->isGLValue())681 Env.setStorageLocation(*S, *LocDst);682 else683 copyRecord(*LocDst, Env.getResultObjectLocation(*S), Env);684 685 return;686 }687 688 // `CXXOperatorCallExpr` can be a prvalue. Call `VisitCallExpr`() to689 // initialize the prvalue's fields with values.690 VisitCallExpr(S);691 }692 693 void VisitCXXRewrittenBinaryOperator(const CXXRewrittenBinaryOperator *RBO) {694 propagateValue(*RBO->getSemanticForm(), *RBO, Env);695 }696 697 void VisitCallExpr(const CallExpr *S) {698 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since699 // others (like trap, debugtrap, and unreachable) are handled by CFG700 // construction.701 if (S->isCallToStdMove()) {702 assert(S->getNumArgs() == 1);703 704 const Expr *Arg = S->getArg(0);705 assert(Arg != nullptr);706 707 auto *ArgLoc = Env.getStorageLocation(*Arg);708 if (ArgLoc == nullptr)709 return;710 711 Env.setStorageLocation(*S, *ArgLoc);712 } else if (S->getDirectCallee() != nullptr &&713 S->getDirectCallee()->getBuiltinID() ==714 Builtin::BI__builtin_expect) {715 assert(S->getNumArgs() > 0);716 assert(S->getArg(0) != nullptr);717 auto *ArgVal = Env.getValue(*S->getArg(0));718 if (ArgVal == nullptr)719 return;720 Env.setValue(*S, *ArgVal);721 } else if (const FunctionDecl *F = S->getDirectCallee()) {722 transferInlineCall(S, F);723 724 // If this call produces a prvalue of record type, initialize its fields725 // with values.726 if (S->getType()->isRecordType() && S->isPRValue()) {727 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);728 Env.initializeFieldsWithValues(Loc);729 }730 }731 }732 733 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {734 const Expr *SubExpr = S->getSubExpr();735 assert(SubExpr != nullptr);736 737 StorageLocation &Loc = Env.createStorageLocation(*S);738 Env.setStorageLocation(*S, Loc);739 740 if (SubExpr->getType()->isRecordType())741 // Nothing else left to do -- we initialized the record when transferring742 // `SubExpr`.743 return;744 745 if (Value *SubExprVal = Env.getValue(*SubExpr))746 Env.setValue(Loc, *SubExprVal);747 }748 749 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {750 const Expr *SubExpr = S->getSubExpr();751 assert(SubExpr != nullptr);752 753 propagateValue(*SubExpr, *S, Env);754 }755 756 void VisitConditionalOperator(const ConditionalOperator *S) {757 const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr());758 const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr());759 760 if (TrueEnv == nullptr || FalseEnv == nullptr) {761 // If the true or false branch is dead, we may not have an environment for762 // it. We could handle this specifically by forwarding the value or763 // location of the live branch, but this case is rare enough that this764 // probably isn't worth the additional complexity.765 return;766 }767 768 if (S->isGLValue()) {769 StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr());770 StorageLocation *FalseLoc =771 FalseEnv->getStorageLocation(*S->getFalseExpr());772 if (TrueLoc == FalseLoc && TrueLoc != nullptr) {773 Env.setStorageLocation(*S, *TrueLoc);774 } else if (!S->getType()->isRecordType()) {775 // Ideally, we would have something like an "alias set" to say that the776 // result StorageLocation can be either of the locations from the777 // TrueEnv or FalseEnv. Then, when this ConditionalOperator is778 // (a) used in an LValueToRValue cast, the value is the join of all of779 // the values in the alias set.780 // (b) or, used in an assignment to the resulting LValue, the assignment781 // *may* update all of the locations in the alias set.782 // For now, we do the simpler thing of creating a new StorageLocation783 // and joining the values right away, handling only case (a).784 // Otherwise, the dataflow framework needs to be updated be able to785 // represent alias sets and weak updates (for the "may").786 if (Value *Val = Environment::joinValues(787 S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv,788 FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env,789 Model)) {790 StorageLocation &Loc = Env.createStorageLocation(*S);791 Env.setStorageLocation(*S, Loc);792 Env.setValue(Loc, *Val);793 }794 }795 } else if (!S->getType()->isRecordType()) {796 // The conditional operator can evaluate to either of the values of the797 // two branches. To model this, join these two values together to yield798 // the result of the conditional operator.799 // Note: Most joins happen in `computeBlockInputState()`, but this case is800 // different:801 // - `computeBlockInputState()` (which in turn calls `Environment::join()`802 // joins values associated with the _same_ expression or storage803 // location, then associates the joined value with that expression or804 // storage location. This join has nothing to do with transfer --805 // instead, it joins together the results of performing transfer on two806 // different blocks.807 // - Here, we join values associated with _different_ expressions (the808 // true and false branch), then associate the joined value with a third809 // expression (the conditional operator itself). This join is what it810 // means to perform transfer on the conditional operator.811 if (Value *Val = Environment::joinValues(812 S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv,813 FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, Model))814 Env.setValue(*S, *Val);815 }816 }817 818 void VisitInitListExpr(const InitListExpr *S) {819 QualType Type = S->getType();820 821 if (!Type->isRecordType()) {822 // Until array initialization is implemented, we skip arrays and don't823 // need to care about cases where `getNumInits() > 1`.824 if (!Type->isArrayType() && S->getNumInits() == 1)825 propagateValueOrStorageLocation(*S->getInit(0), *S, Env);826 return;827 }828 829 // If the initializer list is transparent, there's nothing to do.830 if (S->isSemanticForm() && S->isTransparent())831 return;832 833 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);834 835 // Initialization of base classes and fields of record type happens when we836 // visit the nested `CXXConstructExpr` or `InitListExpr` for that base class837 // or field. We therefore only need to deal with fields of non-record type838 // here.839 840 RecordInitListHelper InitListHelper(S);841 842 for (auto [Field, Init] : InitListHelper.field_inits()) {843 if (Field->getType()->isRecordType())844 continue;845 if (Field->getType()->isReferenceType()) {846 assert(Field->getType().getCanonicalType()->getPointeeType() ==847 Init->getType().getCanonicalType());848 Loc.setChild(*Field, &Env.createObject(Field->getType(), Init));849 continue;850 }851 assert(Field->getType().getCanonicalType().getUnqualifiedType() ==852 Init->getType().getCanonicalType().getUnqualifiedType());853 StorageLocation *FieldLoc = Loc.getChild(*Field);854 // Locations for non-reference fields must always be non-null.855 assert(FieldLoc != nullptr);856 Value *Val = Env.getValue(*Init);857 if (Val == nullptr && isa<ImplicitValueInitExpr>(Init) &&858 Init->getType()->isPointerType())859 Val =860 &Env.getOrCreateNullPointerValue(Init->getType()->getPointeeType());861 if (Val == nullptr)862 Val = Env.createValue(Field->getType());863 if (Val != nullptr)864 Env.setValue(*FieldLoc, *Val);865 }866 867 for (const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) {868 QualType FieldType = FieldLoc->getType();869 if (FieldType->isRecordType()) {870 Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc));871 } else {872 if (Value *Val = Env.createValue(FieldType))873 Env.setValue(*FieldLoc, *Val);874 }875 }876 877 // FIXME: Implement array initialization.878 }879 880 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {881 Env.setValue(*S, Env.getBoolLiteralValue(S->getValue()));882 }883 884 void VisitIntegerLiteral(const IntegerLiteral *S) {885 Env.setValue(*S, Env.getIntLiteralValue(S->getValue()));886 }887 888 void VisitParenExpr(const ParenExpr *S) {889 // The CFG does not contain `ParenExpr` as top-level statements in basic890 // blocks, however manual traversal to sub-expressions may encounter them.891 // Redirect to the sub-expression.892 auto *SubExpr = S->getSubExpr();893 assert(SubExpr != nullptr);894 Visit(SubExpr);895 }896 897 void VisitExprWithCleanups(const ExprWithCleanups *S) {898 // The CFG does not contain `ExprWithCleanups` as top-level statements in899 // basic blocks, however manual traversal to sub-expressions may encounter900 // them. Redirect to the sub-expression.901 auto *SubExpr = S->getSubExpr();902 assert(SubExpr != nullptr);903 Visit(SubExpr);904 }905 906private:907 /// Returns the value for the sub-expression `SubExpr` of a logic operator.908 BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {909 // `SubExpr` and its parent logic operator might be part of different basic910 // blocks. We try to access the value that is assigned to `SubExpr` in the911 // corresponding environment.912 if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))913 if (auto *Val =914 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))915 return *Val;916 917 // The sub-expression may lie within a basic block that isn't reachable,918 // even if we need it to evaluate the current (reachable) expression919 // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`920 // within the current environment and then try to get the value that gets921 // assigned to it.922 if (Env.getValue(SubExpr) == nullptr)923 Visit(&SubExpr);924 if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr)))925 return *Val;926 927 // If the value of `SubExpr` is still unknown, we create a fresh symbolic928 // boolean value for it.929 return Env.makeAtomicBoolValue();930 }931 932 // If context sensitivity is enabled, try to analyze the body of the callee933 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.934 template <typename E>935 void transferInlineCall(const E *S, const FunctionDecl *F) {936 const auto &Options = Env.getDataflowAnalysisContext().getOptions();937 if (!(Options.ContextSensitiveOpts &&938 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))939 return;940 941 const AdornedCFG *ACFG = Env.getDataflowAnalysisContext().getAdornedCFG(F);942 if (!ACFG)943 return;944 945 // FIXME: We don't support context-sensitive analysis of recursion, so946 // we should return early here if `F` is the same as the `FunctionDecl`947 // holding `S` itself.948 949 auto ExitBlock = ACFG->getCFG().getExit().getBlockID();950 951 auto CalleeEnv = Env.pushCall(S);952 953 // FIXME: Use the same analysis as the caller for the callee. Note,954 // though, that doing so would require support for changing the analysis's955 // ASTContext.956 auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(),957 DataflowAnalysisOptions{Options});958 959 auto BlockToOutputState =960 dataflow::runDataflowAnalysis(*ACFG, Analysis, CalleeEnv);961 assert(BlockToOutputState);962 assert(ExitBlock < BlockToOutputState->size());963 964 auto &ExitState = (*BlockToOutputState)[ExitBlock];965 assert(ExitState);966 967 Env.popCall(S, ExitState->Env);968 }969 970 const StmtToEnvMap &StmtToEnv;971 Environment &Env;972 Environment::ValueModel &Model;973};974 975} // namespace976 977void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,978 Environment::ValueModel &Model) {979 TransferVisitor(StmtToEnv, Env, Model).Visit(&S);980}981 982} // namespace dataflow983} // namespace clang984