clang/lib/Analysis/FlowSensitive/Transfer.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines transfer functions that evaluate program statements and
  10 //  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/Analysis/FlowSensitive/ControlFlowContext.h"
  24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
  25 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
  26 #include "clang/Analysis/FlowSensitive/RecordOps.h"
  27 #include "clang/Analysis/FlowSensitive/Value.h"
  28 #include "clang/Basic/Builtins.h"
  29 #include "clang/Basic/OperatorKinds.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/Debug.h"
  32 #include <assert.h>
  33 #include <cassert>
  34
  35 #define DEBUG_TYPE "dataflow"
  36
  37 namespace clang {
  38 namespace dataflow {
  39
  40 const Environment *StmtToEnvMap::getEnvironment(const Stmt &S) const {
  41   auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
  42   assert(BlockIt != CFCtx.getStmtToBlock().end());
  43   if (!CFCtx.isBlockReachable(*BlockIt->getSecond()))
  44     return nullptr;
  45   const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
  46   if (!(State))
  47     return nullptr;
  48   return &State->Env;
  49 }
  50
  51 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
  52                                           Environment &Env) {
  53   Value *LHSValue = Env.getValue(LHS);
  54   Value *RHSValue = Env.getValue(RHS);
  55
  56   if (LHSValue == RHSValue)
  57     return Env.getBoolLiteralValue(true);
  58
  59   if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
  60     if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
  61       return Env.makeIff(*LHSBool, *RHSBool);
  62
  63   return Env.makeAtomicBoolValue();
  64 }
  65
  66 static BoolValue &unpackValue(BoolValue &V, Environment &Env) {
  67   if (auto *Top = llvm::dyn_cast<TopBoolValue>(&V)) {
  68     auto &A = Env.getDataflowAnalysisContext().arena();
  69     return A.makeBoolValue(A.makeAtomRef(Top->getAtom()));
  70   }
  71   return V;
  72 }
  73
  74 // Unpacks the value (if any) associated with `E` and updates `E` to the new
  75 // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
  76 // by skipping past the reference.
  77 static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {
  78   auto *Loc = Env.getStorageLocation(E);
  79   if (Loc == nullptr)
  80     return nullptr;
  81   auto *Val = Env.getValue(*Loc);
  82
  83   auto *B = dyn_cast_or_null<BoolValue>(Val);
  84   if (B == nullptr)
  85     return Val;
  86
  87   auto &UnpackedVal = unpackValue(*B, Env);
  88   if (&UnpackedVal == Val)
  89     return Val;
  90   Env.setValue(*Loc, UnpackedVal);
  91   return &UnpackedVal;
  92 }
  93
  94 static void propagateValue(const Expr &From, const Expr &To, Environment &Env) {
  95   if (auto *Val = Env.getValue(From))
  96     Env.setValue(To, *Val);
  97 }
  98
  99 static void propagateStorageLocation(const Expr &From, const Expr &To,
 100                                      Environment &Env) {
 101   if (auto *Loc = Env.getStorageLocation(From))
 102     Env.setStorageLocation(To, *Loc);
 103 }
 104
 105 // Propagates the value or storage location of `From` to `To` in cases where
 106 // `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff
 107 // `From` is a glvalue.
 108 static void propagateValueOrStorageLocation(const Expr &From, const Expr &To,
 109                                             Environment &Env) {
 110   assert(From.isGLValue() == To.isGLValue());
 111   if (From.isGLValue())
 112     propagateStorageLocation(From, To, Env);
 113   else
 114     propagateValue(From, To, Env);
 115 }
 116
 117 namespace {
 118
 119 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
 120 public:
 121   TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
 122       : StmtToEnv(StmtToEnv), Env(Env) {}
 123
 124   void VisitBinaryOperator(const BinaryOperator *S) {
 125     const Expr *LHS = S->getLHS();
 126     assert(LHS != nullptr);
 127
 128     const Expr *RHS = S->getRHS();
 129     assert(RHS != nullptr);
 130
 131     switch (S->getOpcode()) {
 132     case BO_Assign: {
 133       auto *LHSLoc = Env.getStorageLocation(*LHS);
 134       if (LHSLoc == nullptr)
 135         break;
 136
 137       auto *RHSVal = Env.getValue(*RHS);
 138       if (RHSVal == nullptr)
 139         break;
 140
 141       // Assign a value to the storage location of the left-hand side.
 142       Env.setValue(*LHSLoc, *RHSVal);
 143
 144       // Assign a storage location for the whole expression.
 145       Env.setStorageLocation(*S, *LHSLoc);
 146       break;
 147     }
 148     case BO_LAnd:
 149     case BO_LOr: {
 150       BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
 151       BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
 152
 153       if (S->getOpcode() == BO_LAnd)
 154         Env.setValue(*S, Env.makeAnd(LHSVal, RHSVal));
 155       else
 156         Env.setValue(*S, Env.makeOr(LHSVal, RHSVal));
 157       break;
 158     }
 159     case BO_NE:
 160     case BO_EQ: {
 161       auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
 162       Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
 163                                                : Env.makeNot(LHSEqRHSValue));
 164       break;
 165     }
 166     case BO_Comma: {
 167       propagateValueOrStorageLocation(*RHS, *S, Env);
 168       break;
 169     }
 170     default:
 171       break;
 172     }
 173   }
 174
 175   void VisitDeclRefExpr(const DeclRefExpr *S) {
 176     const ValueDecl *VD = S->getDecl();
 177     assert(VD != nullptr);
 178
 179     // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a
 180     // `StorageLocation`, and there's also no sensible `Value` that we can
 181     // assign to them. Examples:
 182     // - Non-static member variables
 183     // - Non static member functions
 184     //   Note: Member operators are an exception to this, but apparently only
 185     //   if the `DeclRefExpr` is used within the callee of a
 186     //   `CXXOperatorCallExpr`. In other cases, for example when applying the
 187     //   address-of operator, the `DeclRefExpr` is a prvalue.
 188     if (!S->isGLValue())
 189       return;
 190
 191     auto *DeclLoc = Env.getStorageLocation(*VD);
 192     if (DeclLoc == nullptr)
 193       return;
 194
 195     Env.setStorageLocation(*S, *DeclLoc);
 196   }
 197
 198   void VisitDeclStmt(const DeclStmt *S) {
 199     // Group decls are converted into single decls in the CFG so the cast below
 200     // is safe.
 201     const auto &D = *cast<VarDecl>(S->getSingleDecl());
 202
 203     ProcessVarDecl(D);
 204   }
 205
 206   void ProcessVarDecl(const VarDecl &D) {
 207     // Static local vars are already initialized in `Environment`.
 208     if (D.hasGlobalStorage())
 209       return;
 210
 211     // If this is the holding variable for a `BindingDecl`, we may already
 212     // have a storage location set up -- so check. (See also explanation below
 213     // where we process the `BindingDecl`.)
 214     if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr)
 215       return;
 216
 217     assert(Env.getStorageLocation(D) == nullptr);
 218
 219     Env.setStorageLocation(D, Env.createObject(D));
 220
 221     // `DecompositionDecl` must be handled after we've interpreted the loc
 222     // itself, because the binding expression refers back to the
 223     // `DecompositionDecl` (even though it has no written name).
 224     if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
 225       // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
 226       // needs to be evaluated after initializing the values in the storage for
 227       // VarDecl, as the bindings refer to them.
 228       // FIXME: Add support for ArraySubscriptExpr.
 229       // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
 230       for (const auto *B : Decomp->bindings()) {
 231         if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
 232           auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
 233           if (DE == nullptr)
 234             continue;
 235
 236           // ME and its base haven't been visited because they aren't included
 237           // in the statements of the CFG basic block.
 238           VisitDeclRefExpr(DE);
 239           VisitMemberExpr(ME);
 240
 241           if (auto *Loc = Env.getStorageLocation(*ME))
 242             Env.setStorageLocation(*B, *Loc);
 243         } else if (auto *VD = B->getHoldingVar()) {
 244           // Holding vars are used to back the `BindingDecl`s of tuple-like
 245           // types. The holding var declarations appear after the
 246           // `DecompositionDecl`, so we have to explicitly process them here
 247           // to know their storage location. They will be processed a second
 248           // time when we visit their `VarDecl`s, so we have code that protects
 249           // against this above.
 250           ProcessVarDecl(*VD);
 251           auto *VDLoc = Env.getStorageLocation(*VD);
 252           assert(VDLoc != nullptr);
 253           Env.setStorageLocation(*B, *VDLoc);
 254         }
 255       }
 256     }
 257   }
 258
 259   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
 260     const Expr *SubExpr = S->getSubExpr();
 261     assert(SubExpr != nullptr);
 262
 263     switch (S->getCastKind()) {
 264     case CK_IntegralToBoolean: {
 265       // This cast creates a new, boolean value from the integral value. We
 266       // model that with a fresh value in the environment, unless it's already a
 267       // boolean.
 268       if (auto *SubExprVal =
 269               dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)))
 270         Env.setValue(*S, *SubExprVal);
 271       else
 272         // FIXME: If integer modeling is added, then update this code to create
 273         // the boolean based on the integer model.
 274         Env.setValue(*S, Env.makeAtomicBoolValue());
 275       break;
 276     }
 277
 278     case CK_LValueToRValue: {
 279       // When an L-value is used as an R-value, it may result in sharing, so we
 280       // need to unpack any nested `Top`s.
 281       auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);
 282       if (SubExprVal == nullptr)
 283         break;
 284
 285       Env.setValue(*S, *SubExprVal);
 286       break;
 287     }
 288
 289     case CK_IntegralCast:
 290       // FIXME: This cast creates a new integral value from the
 291       // subexpression. But, because we don't model integers, we don't
 292       // distinguish between this new value and the underlying one. If integer
 293       // modeling is added, then update this code to create a fresh location and
 294       // value.
 295     case CK_UncheckedDerivedToBase:
 296     case CK_ConstructorConversion:
 297     case CK_UserDefinedConversion:
 298       // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
 299       // CK_ConstructorConversion, and CK_UserDefinedConversion.
 300     case CK_NoOp: {
 301       // FIXME: Consider making `Environment::getStorageLocation` skip noop
 302       // expressions (this and other similar expressions in the file) instead
 303       // of assigning them storage locations.
 304       propagateValueOrStorageLocation(*SubExpr, *S, Env);
 305       break;
 306     }
 307     case CK_NullToPointer: {
 308       auto &NullPointerVal =
 309           Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
 310       Env.setValue(*S, NullPointerVal);
 311       break;
 312     }
 313     case CK_NullToMemberPointer:
 314       // FIXME: Implement pointers to members. For now, don't associate a value
 315       // with this expression.
 316       break;
 317     case CK_FunctionToPointerDecay: {
 318       StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr);
 319       if (PointeeLoc == nullptr)
 320         break;
 321
 322       Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));
 323       break;
 324     }
 325     case CK_BuiltinFnToFnPtr:
 326       // Despite its name, the result type of `BuiltinFnToFnPtr` is a function,
 327       // not a function pointer. In addition, builtin functions can only be
 328       // called directly; it is not legal to take their address. We therefore
 329       // don't need to create a value or storage location for them.
 330       break;
 331     default:
 332       break;
 333     }
 334   }
 335
 336   void VisitUnaryOperator(const UnaryOperator *S) {
 337     const Expr *SubExpr = S->getSubExpr();
 338     assert(SubExpr != nullptr);
 339
 340     switch (S->getOpcode()) {
 341     case UO_Deref: {
 342       const auto *SubExprVal = Env.get<PointerValue>(*SubExpr);
 343       if (SubExprVal == nullptr)
 344         break;
 345
 346       Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
 347       break;
 348     }
 349     case UO_AddrOf: {
 350       // FIXME: Model pointers to members.
 351       if (S->getType()->isMemberPointerType())
 352         break;
 353
 354       if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr))
 355         Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));
 356       break;
 357     }
 358     case UO_LNot: {
 359       auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr));
 360       if (SubExprVal == nullptr)
 361         break;
 362
 363       Env.setValue(*S, Env.makeNot(*SubExprVal));
 364       break;
 365     }
 366     default:
 367       break;
 368     }
 369   }
 370
 371   void VisitCXXThisExpr(const CXXThisExpr *S) {
 372     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
 373     if (ThisPointeeLoc == nullptr)
 374       // Unions are not supported yet, and will not have a location for the
 375       // `this` expression's pointee.
 376       return;
 377
 378     Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc));
 379   }
 380
 381   void VisitCXXNewExpr(const CXXNewExpr *S) {
 382     if (Value *Val = Env.createValue(S->getType()))
 383       Env.setValue(*S, *Val);
 384   }
 385
 386   void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
 387     // Empty method.
 388     // We consciously don't do anything on deletes.  Diagnosing double deletes
 389     // (for example) should be done by a specific analysis, not by the
 390     // framework.
 391   }
 392
 393   void VisitReturnStmt(const ReturnStmt *S) {
 394     if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
 395       return;
 396
 397     auto *Ret = S->getRetValue();
 398     if (Ret == nullptr)
 399       return;
 400
 401     if (Ret->isPRValue()) {
 402       auto *Val = Env.getValue(*Ret);
 403       if (Val == nullptr)
 404         return;
 405
 406       // FIXME: Model NRVO.
 407       Env.setReturnValue(Val);
 408     } else {
 409       auto *Loc = Env.getStorageLocation(*Ret);
 410       if (Loc == nullptr)
 411         return;
 412
 413       // FIXME: Model NRVO.
 414       Env.setReturnStorageLocation(Loc);
 415     }
 416   }
 417
 418   void VisitMemberExpr(const MemberExpr *S) {
 419     ValueDecl *Member = S->getMemberDecl();
 420     assert(Member != nullptr);
 421
 422     // FIXME: Consider assigning pointer values to function member expressions.
 423     if (Member->isFunctionOrFunctionTemplate())
 424       return;
 425
 426     // FIXME: if/when we add support for modeling enums, use that support here.
 427     if (isa<EnumConstantDecl>(Member))
 428       return;
 429
 430     if (auto *D = dyn_cast<VarDecl>(Member)) {
 431       if (D->hasGlobalStorage()) {
 432         auto *VarDeclLoc = Env.getStorageLocation(*D);
 433         if (VarDeclLoc == nullptr)
 434           return;
 435
 436         Env.setStorageLocation(*S, *VarDeclLoc);
 437         return;
 438       }
 439     }
 440
 441     RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);
 442     if (BaseLoc == nullptr)
 443       return;
 444
 445     auto *MemberLoc = BaseLoc->getChild(*Member);
 446     if (MemberLoc == nullptr)
 447       return;
 448     Env.setStorageLocation(*S, *MemberLoc);
 449   }
 450
 451   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
 452     const Expr *InitExpr = S->getExpr();
 453     assert(InitExpr != nullptr);
 454     propagateValueOrStorageLocation(*InitExpr, *S, Env);
 455   }
 456
 457   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
 458     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
 459     assert(ConstructorDecl != nullptr);
 460
 461     if (ConstructorDecl->isCopyOrMoveConstructor()) {
 462       // It is permissible for a copy/move constructor to have additional
 463       // parameters as long as they have default arguments defined for them.
 464       assert(S->getNumArgs() != 0);
 465
 466       const Expr *Arg = S->getArg(0);
 467       assert(Arg != nullptr);
 468
 469       auto *ArgLoc = Env.get<RecordStorageLocation>(*Arg);
 470       if (ArgLoc == nullptr)
 471         return;
 472
 473       if (S->isElidable()) {
 474         if (Value *Val = Env.getValue(*ArgLoc))
 475           Env.setValue(*S, *Val);
 476       } else {
 477         auto &Val = *cast<RecordValue>(Env.createValue(S->getType()));
 478         Env.setValue(*S, Val);
 479         copyRecord(*ArgLoc, Val.getLoc(), Env);
 480       }
 481       return;
 482     }
 483
 484     // `CXXConstructExpr` can have array type if default-initializing an array
 485     // of records, and we currently can't create values for arrays. So check if
 486     // we've got a record type.
 487     if (S->getType()->isRecordType()) {
 488       auto &InitialVal = *cast<RecordValue>(Env.createValue(S->getType()));
 489       Env.setValue(*S, InitialVal);
 490     }
 491
 492     transferInlineCall(S, ConstructorDecl);
 493   }
 494
 495   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
 496     if (S->getOperator() == OO_Equal) {
 497       assert(S->getNumArgs() == 2);
 498
 499       const Expr *Arg0 = S->getArg(0);
 500       assert(Arg0 != nullptr);
 501
 502       const Expr *Arg1 = S->getArg(1);
 503       assert(Arg1 != nullptr);
 504
 505       // Evaluate only copy and move assignment operators.
 506       const auto *Method =
 507           dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
 508       if (!Method)
 509         return;
 510       if (!Method->isCopyAssignmentOperator() &&
 511           !Method->isMoveAssignmentOperator())
 512         return;
 513
 514       RecordStorageLocation *LocSrc = nullptr;
 515       if (Arg1->isPRValue()) {
 516         if (auto *Val = Env.get<RecordValue>(*Arg1))
 517           LocSrc = &Val->getLoc();
 518       } else {
 519         LocSrc = Env.get<RecordStorageLocation>(*Arg1);
 520       }
 521       auto *LocDst = Env.get<RecordStorageLocation>(*Arg0);
 522
 523       if (LocSrc == nullptr || LocDst == nullptr)
 524         return;
 525
 526       // The assignment operators are different from the type of the destination
 527       // in this model (i.e. in one of their base classes). This must be very
 528       // rare and we just bail.
 529       if (Method->getFunctionObjectParameterType()
 530               .getCanonicalType()
 531               .getUnqualifiedType() !=
 532           LocDst->getType().getCanonicalType().getUnqualifiedType())
 533         return;
 534
 535       copyRecord(*LocSrc, *LocDst, Env);
 536       Env.setStorageLocation(*S, *LocDst);
 537     }
 538   }
 539
 540   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
 541     if (S->getCastKind() == CK_ConstructorConversion) {
 542       const Expr *SubExpr = S->getSubExpr();
 543       assert(SubExpr != nullptr);
 544
 545       propagateValue(*SubExpr, *S, Env);
 546     }
 547   }
 548
 549   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
 550     if (Value *Val = Env.createValue(S->getType()))
 551       Env.setValue(*S, *Val);
 552   }
 553
 554   void VisitCallExpr(const CallExpr *S) {
 555     // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
 556     // others (like trap, debugtrap, and unreachable) are handled by CFG
 557     // construction.
 558     if (S->isCallToStdMove()) {
 559       assert(S->getNumArgs() == 1);
 560
 561       const Expr *Arg = S->getArg(0);
 562       assert(Arg != nullptr);
 563
 564       auto *ArgLoc = Env.getStorageLocation(*Arg);
 565       if (ArgLoc == nullptr)
 566         return;
 567
 568       Env.setStorageLocation(*S, *ArgLoc);
 569     } else if (S->getDirectCallee() != nullptr &&
 570                S->getDirectCallee()->getBuiltinID() ==
 571                    Builtin::BI__builtin_expect) {
 572       assert(S->getNumArgs() > 0);
 573       assert(S->getArg(0) != nullptr);
 574       auto *ArgVal = Env.getValue(*S->getArg(0));
 575       if (ArgVal == nullptr)
 576         return;
 577       Env.setValue(*S, *ArgVal);
 578     } else if (const FunctionDecl *F = S->getDirectCallee()) {
 579       transferInlineCall(S, F);
 580
 581       // If this call produces a prvalue of record type, make sure that we have
 582       // a `RecordValue` for it. This is required so that
 583       // `Environment::getResultObjectLocation()` is able to return a location
 584       // for this `CallExpr`.
 585       if (S->getType()->isRecordType() && S->isPRValue())
 586         if (Env.getValue(*S) == nullptr)
 587           refreshRecordValue(*S, Env);
 588     }
 589   }
 590
 591   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
 592     const Expr *SubExpr = S->getSubExpr();
 593     assert(SubExpr != nullptr);
 594
 595     Value *SubExprVal = Env.getValue(*SubExpr);
 596     if (SubExprVal == nullptr)
 597       return;
 598
 599     if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) {
 600       Env.setStorageLocation(*S, RecordVal->getLoc());
 601       return;
 602     }
 603
 604     StorageLocation &Loc = Env.createStorageLocation(*S);
 605     Env.setValue(Loc, *SubExprVal);
 606     Env.setStorageLocation(*S, Loc);
 607   }
 608
 609   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
 610     const Expr *SubExpr = S->getSubExpr();
 611     assert(SubExpr != nullptr);
 612
 613     propagateValue(*SubExpr, *S, Env);
 614   }
 615
 616   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
 617     if (S->getCastKind() == CK_NoOp) {
 618       const Expr *SubExpr = S->getSubExpr();
 619       assert(SubExpr != nullptr);
 620
 621       propagateValueOrStorageLocation(*SubExpr, *S, Env);
 622     }
 623   }
 624
 625   void VisitConditionalOperator(const ConditionalOperator *S) {
 626     // FIXME: Revisit this once flow conditions are added to the framework. For
 627     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
 628     // condition.
 629     // When we do this, we will need to retrieve the values of the operands from
 630     // the environments for the basic blocks they are computed in, in a similar
 631     // way to how this is done for short-circuited logical operators in
 632     // `getLogicOperatorSubExprValue()`.
 633     if (S->isGLValue())
 634       Env.setStorageLocation(*S, Env.createObject(S->getType()));
 635     else if (Value *Val = Env.createValue(S->getType()))
 636       Env.setValue(*S, *Val);
 637   }
 638
 639   void VisitInitListExpr(const InitListExpr *S) {
 640     QualType Type = S->getType();
 641
 642     if (!Type->isStructureOrClassType()) {
 643       if (auto *Val = Env.createValue(Type))
 644         Env.setValue(*S, *Val);
 645
 646       return;
 647     }
 648
 649     // In case the initializer list is transparent, we just need to propagate
 650     // the value that it contains.
 651     if (S->isSemanticForm() && S->isTransparent()) {
 652       propagateValue(*S->getInit(0), *S, Env);
 653       return;
 654     }
 655
 656     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
 657
 658     // This only contains the direct fields for the given type.
 659     std::vector<FieldDecl *> FieldsForInit =
 660         getFieldsForInitListExpr(Type->getAsRecordDecl());
 661
 662     // `S->inits()` contains all the initializer epressions, including the
 663     // ones for direct base classes.
 664     auto Inits = S->inits();
 665     size_t InitIdx = 0;
 666
 667     // Initialize base classes.
 668     if (auto* R = S->getType()->getAsCXXRecordDecl()) {
 669       assert(FieldsForInit.size() + R->getNumBases() == Inits.size());
 670       for ([[maybe_unused]] const CXXBaseSpecifier &Base : R->bases()) {
 671         assert(InitIdx < Inits.size());
 672         auto Init = Inits[InitIdx++];
 673         assert(Base.getType().getCanonicalType() ==
 674                Init->getType().getCanonicalType());
 675         auto *BaseVal = Env.get<RecordValue>(*Init);
 676         if (!BaseVal)
 677           BaseVal = cast<RecordValue>(Env.createValue(Init->getType()));
 678         // Take ownership of the fields of the `RecordValue` for the base class
 679         // and incorporate them into the "flattened" set of fields for the
 680         // derived class.
 681         auto Children = BaseVal->getLoc().children();
 682         FieldLocs.insert(Children.begin(), Children.end());
 683       }
 684     }
 685
 686     assert(FieldsForInit.size() == Inits.size() - InitIdx);
 687     for (auto Field : FieldsForInit) {
 688       assert(InitIdx < Inits.size());
 689       auto Init = Inits[InitIdx++];
 690       assert(
 691           // The types are same, or
 692           Field->getType().getCanonicalType().getUnqualifiedType() ==
 693               Init->getType().getCanonicalType().getUnqualifiedType() ||
 694           // The field's type is T&, and initializer is T
 695           (Field->getType()->isReferenceType() &&
 696            Field->getType().getCanonicalType()->getPointeeType() ==
 697                Init->getType().getCanonicalType()));
 698       auto& Loc = Env.createObject(Field->getType(), Init);
 699       FieldLocs.insert({Field, &Loc});
 700     }
 701
 702     // Check that we satisfy the invariant that a `RecordStorageLoation`
 703     // contains exactly the set of modeled fields for that type.
 704     // `ModeledFields` includes fields from all the bases, but only the
 705     // modeled ones. However, if a class type is initialized with an
 706     // `InitListExpr`, all fields in the class, including those from base
 707     // classes, are included in the set of modeled fields. The code above
 708     // should therefore populate exactly the modeled fields.
 709     assert(containsSameFields(
 710         Env.getDataflowAnalysisContext().getModeledFields(Type), FieldLocs));
 711
 712     RecordStorageLocation::SyntheticFieldMap SyntheticFieldLocs;
 713     for (const auto &Entry :
 714          Env.getDataflowAnalysisContext().getSyntheticFields(Type)) {
 715       SyntheticFieldLocs.insert(
 716           {Entry.getKey(), &Env.createObject(Entry.getValue())});
 717     }
 718
 719     auto &Loc = Env.getDataflowAnalysisContext().createRecordStorageLocation(
 720         Type, std::move(FieldLocs), std::move(SyntheticFieldLocs));
 721     RecordValue &RecordVal = Env.create<RecordValue>(Loc);
 722
 723     Env.setValue(Loc, RecordVal);
 724
 725     Env.setValue(*S, RecordVal);
 726
 727     // FIXME: Implement array initialization.
 728   }
 729
 730   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
 731     Env.setValue(*S, Env.getBoolLiteralValue(S->getValue()));
 732   }
 733
 734   void VisitIntegerLiteral(const IntegerLiteral *S) {
 735     Env.setValue(*S, Env.getIntLiteralValue(S->getValue()));
 736   }
 737
 738   void VisitParenExpr(const ParenExpr *S) {
 739     // The CFG does not contain `ParenExpr` as top-level statements in basic
 740     // blocks, however manual traversal to sub-expressions may encounter them.
 741     // Redirect to the sub-expression.
 742     auto *SubExpr = S->getSubExpr();
 743     assert(SubExpr != nullptr);
 744     Visit(SubExpr);
 745   }
 746
 747   void VisitExprWithCleanups(const ExprWithCleanups *S) {
 748     // The CFG does not contain `ExprWithCleanups` as top-level statements in
 749     // basic blocks, however manual traversal to sub-expressions may encounter
 750     // them. Redirect to the sub-expression.
 751     auto *SubExpr = S->getSubExpr();
 752     assert(SubExpr != nullptr);
 753     Visit(SubExpr);
 754   }
 755
 756 private:
 757   /// Returns the value for the sub-expression `SubExpr` of a logic operator.
 758   BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
 759     // `SubExpr` and its parent logic operator might be part of different basic
 760     // blocks. We try to access the value that is assigned to `SubExpr` in the
 761     // corresponding environment.
 762     if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
 763       if (auto *Val =
 764               dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
 765         return *Val;
 766
 767     // The sub-expression may lie within a basic block that isn't reachable,
 768     // even if we need it to evaluate the current (reachable) expression
 769     // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`
 770     // within the current environment and then try to get the value that gets
 771     // assigned to it.
 772     if (Env.getValue(SubExpr) == nullptr)
 773       Visit(&SubExpr);
 774     if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr)))
 775       return *Val;
 776
 777     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
 778     // boolean value for it.
 779     return Env.makeAtomicBoolValue();
 780   }
 781
 782   // If context sensitivity is enabled, try to analyze the body of the callee
 783   // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
 784   template <typename E>
 785   void transferInlineCall(const E *S, const FunctionDecl *F) {
 786     const auto &Options = Env.getDataflowAnalysisContext().getOptions();
 787     if (!(Options.ContextSensitiveOpts &&
 788           Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
 789       return;
 790
 791     const ControlFlowContext *CFCtx =
 792         Env.getDataflowAnalysisContext().getControlFlowContext(F);
 793     if (!CFCtx)
 794       return;
 795
 796     // FIXME: We don't support context-sensitive analysis of recursion, so
 797     // we should return early here if `F` is the same as the `FunctionDecl`
 798     // holding `S` itself.
 799
 800     auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
 801
 802     auto CalleeEnv = Env.pushCall(S);
 803
 804     // FIXME: Use the same analysis as the caller for the callee. Note,
 805     // though, that doing so would require support for changing the analysis's
 806     // ASTContext.
 807     auto Analysis = NoopAnalysis(CFCtx->getDecl().getASTContext(),
 808                                  DataflowAnalysisOptions{Options});
 809
 810     auto BlockToOutputState =
 811         dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
 812     assert(BlockToOutputState);
 813     assert(ExitBlock < BlockToOutputState->size());
 814
 815     auto &ExitState = (*BlockToOutputState)[ExitBlock];
 816     assert(ExitState);
 817
 818     Env.popCall(S, ExitState->Env);
 819   }
 820
 821   const StmtToEnvMap &StmtToEnv;
 822   Environment &Env;
 823 };
 824
 825 } // namespace
 826
 827 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
 828   TransferVisitor(StmtToEnv, Env).Visit(&S);
 829 }
 830
 831 } // namespace dataflow
 832 } // namespace clang