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 =
 343           cast_or_null<PointerValue>(Env.getValue(*SubExpr));
 344       if (SubExprVal == nullptr)
 345         break;
 346
 347       Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
 348       break;
 349     }
 350     case UO_AddrOf: {
 351       // FIXME: Model pointers to members.
 352       if (S->getType()->isMemberPointerType())
 353         break;
 354
 355       if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr))
 356         Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));
 357       break;
 358     }
 359     case UO_LNot: {
 360       auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr));
 361       if (SubExprVal == nullptr)
 362         break;
 363
 364       Env.setValue(*S, Env.makeNot(*SubExprVal));
 365       break;
 366     }
 367     default:
 368       break;
 369     }
 370   }
 371
 372   void VisitCXXThisExpr(const CXXThisExpr *S) {
 373     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
 374     if (ThisPointeeLoc == nullptr)
 375       // Unions are not supported yet, and will not have a location for the
 376       // `this` expression's pointee.
 377       return;
 378
 379     Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc));
 380   }
 381
 382   void VisitCXXNewExpr(const CXXNewExpr *S) {
 383     if (Value *Val = Env.createValue(S->getType()))
 384       Env.setValue(*S, *Val);
 385   }
 386
 387   void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
 388     // Empty method.
 389     // We consciously don't do anything on deletes.  Diagnosing double deletes
 390     // (for example) should be done by a specific analysis, not by the
 391     // framework.
 392   }
 393
 394   void VisitReturnStmt(const ReturnStmt *S) {
 395     if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
 396       return;
 397
 398     auto *Ret = S->getRetValue();
 399     if (Ret == nullptr)
 400       return;
 401
 402     if (Ret->isPRValue()) {
 403       auto *Val = Env.getValue(*Ret);
 404       if (Val == nullptr)
 405         return;
 406
 407       // FIXME: Model NRVO.
 408       Env.setReturnValue(Val);
 409     } else {
 410       auto *Loc = Env.getStorageLocation(*Ret);
 411       if (Loc == nullptr)
 412         return;
 413
 414       // FIXME: Model NRVO.
 415       Env.setReturnStorageLocation(Loc);
 416     }
 417   }
 418
 419   void VisitMemberExpr(const MemberExpr *S) {
 420     ValueDecl *Member = S->getMemberDecl();
 421     assert(Member != nullptr);
 422
 423     // FIXME: Consider assigning pointer values to function member expressions.
 424     if (Member->isFunctionOrFunctionTemplate())
 425       return;
 426
 427     // FIXME: if/when we add support for modeling enums, use that support here.
 428     if (isa<EnumConstantDecl>(Member))
 429       return;
 430
 431     if (auto *D = dyn_cast<VarDecl>(Member)) {
 432       if (D->hasGlobalStorage()) {
 433         auto *VarDeclLoc = Env.getStorageLocation(*D);
 434         if (VarDeclLoc == nullptr)
 435           return;
 436
 437         Env.setStorageLocation(*S, *VarDeclLoc);
 438         return;
 439       }
 440     }
 441
 442     RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);
 443     if (BaseLoc == nullptr)
 444       return;
 445
 446     auto *MemberLoc = BaseLoc->getChild(*Member);
 447     if (MemberLoc == nullptr)
 448       return;
 449     Env.setStorageLocation(*S, *MemberLoc);
 450   }
 451
 452   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
 453     const Expr *InitExpr = S->getExpr();
 454     assert(InitExpr != nullptr);
 455     propagateValueOrStorageLocation(*InitExpr, *S, Env);
 456   }
 457
 458   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
 459     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
 460     assert(ConstructorDecl != nullptr);
 461
 462     if (ConstructorDecl->isCopyOrMoveConstructor()) {
 463       // It is permissible for a copy/move constructor to have additional
 464       // parameters as long as they have default arguments defined for them.
 465       assert(S->getNumArgs() != 0);
 466
 467       const Expr *Arg = S->getArg(0);
 468       assert(Arg != nullptr);
 469
 470       auto *ArgLoc =
 471           cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg));
 472       if (ArgLoc == nullptr)
 473         return;
 474
 475       if (S->isElidable()) {
 476         if (Value *Val = Env.getValue(*ArgLoc))
 477           Env.setValue(*S, *Val);
 478       } else {
 479         auto &Val = *cast<RecordValue>(Env.createValue(S->getType()));
 480         Env.setValue(*S, Val);
 481         copyRecord(*ArgLoc, Val.getLoc(), Env);
 482       }
 483       return;
 484     }
 485
 486     // `CXXConstructExpr` can have array type if default-initializing an array
 487     // of records, and we currently can't create values for arrays. So check if
 488     // we've got a record type.
 489     if (S->getType()->isRecordType()) {
 490       auto &InitialVal = *cast<RecordValue>(Env.createValue(S->getType()));
 491       Env.setValue(*S, InitialVal);
 492       copyRecord(InitialVal.getLoc(), Env.getResultObjectLocation(*S), Env);
 493     }
 494
 495     transferInlineCall(S, ConstructorDecl);
 496   }
 497
 498   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
 499     if (S->getOperator() == OO_Equal) {
 500       assert(S->getNumArgs() == 2);
 501
 502       const Expr *Arg0 = S->getArg(0);
 503       assert(Arg0 != nullptr);
 504
 505       const Expr *Arg1 = S->getArg(1);
 506       assert(Arg1 != nullptr);
 507
 508       // Evaluate only copy and move assignment operators.
 509       const auto *Method =
 510           dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
 511       if (!Method)
 512         return;
 513       if (!Method->isCopyAssignmentOperator() &&
 514           !Method->isMoveAssignmentOperator())
 515         return;
 516
 517       auto *LocSrc =
 518           cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg1));
 519       auto *LocDst =
 520           cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg0));
 521
 522       if (LocSrc == nullptr || LocDst == nullptr)
 523         return;
 524
 525       // The assignment operators are different from the type of the destination
 526       // in this model (i.e. in one of their base classes). This must be very
 527       // rare and we just bail.
 528       if (Method->getFunctionObjectParameterType()
 529               .getCanonicalType()
 530               .getUnqualifiedType() !=
 531           LocDst->getType().getCanonicalType().getUnqualifiedType())
 532         return;
 533
 534       copyRecord(*LocSrc, *LocDst, Env);
 535       Env.setStorageLocation(*S, *LocDst);
 536     }
 537   }
 538
 539   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
 540     if (S->getCastKind() == CK_ConstructorConversion) {
 541       const Expr *SubExpr = S->getSubExpr();
 542       assert(SubExpr != nullptr);
 543
 544       propagateValue(*SubExpr, *S, Env);
 545     }
 546   }
 547
 548   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
 549     if (Value *Val = Env.createValue(S->getType()))
 550       Env.setValue(*S, *Val);
 551   }
 552
 553   void VisitCallExpr(const CallExpr *S) {
 554     // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
 555     // others (like trap, debugtrap, and unreachable) are handled by CFG
 556     // construction.
 557     if (S->isCallToStdMove()) {
 558       assert(S->getNumArgs() == 1);
 559
 560       const Expr *Arg = S->getArg(0);
 561       assert(Arg != nullptr);
 562
 563       auto *ArgLoc = Env.getStorageLocation(*Arg);
 564       if (ArgLoc == nullptr)
 565         return;
 566
 567       Env.setStorageLocation(*S, *ArgLoc);
 568     } else if (S->getDirectCallee() != nullptr &&
 569                S->getDirectCallee()->getBuiltinID() ==
 570                    Builtin::BI__builtin_expect) {
 571       assert(S->getNumArgs() > 0);
 572       assert(S->getArg(0) != nullptr);
 573       auto *ArgVal = Env.getValue(*S->getArg(0));
 574       if (ArgVal == nullptr)
 575         return;
 576       Env.setValue(*S, *ArgVal);
 577     } else if (const FunctionDecl *F = S->getDirectCallee()) {
 578       transferInlineCall(S, F);
 579     }
 580   }
 581
 582   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
 583     const Expr *SubExpr = S->getSubExpr();
 584     assert(SubExpr != nullptr);
 585
 586     Value *SubExprVal = Env.getValue(*SubExpr);
 587     if (SubExprVal == nullptr)
 588       return;
 589
 590     if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) {
 591       Env.setStorageLocation(*S, RecordVal->getLoc());
 592       return;
 593     }
 594
 595     StorageLocation &Loc = Env.createStorageLocation(*S);
 596     Env.setValue(Loc, *SubExprVal);
 597     Env.setStorageLocation(*S, Loc);
 598   }
 599
 600   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
 601     const Expr *SubExpr = S->getSubExpr();
 602     assert(SubExpr != nullptr);
 603
 604     propagateValue(*SubExpr, *S, Env);
 605   }
 606
 607   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
 608     if (S->getCastKind() == CK_NoOp) {
 609       const Expr *SubExpr = S->getSubExpr();
 610       assert(SubExpr != nullptr);
 611
 612       propagateValueOrStorageLocation(*SubExpr, *S, Env);
 613     }
 614   }
 615
 616   void VisitConditionalOperator(const ConditionalOperator *S) {
 617     // FIXME: Revisit this once flow conditions are added to the framework. For
 618     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
 619     // condition.
 620     if (S->isGLValue())
 621       Env.setStorageLocation(*S, Env.createObject(S->getType()));
 622     else if (Value *Val = Env.createValue(S->getType()))
 623       Env.setValue(*S, *Val);
 624   }
 625
 626   void VisitInitListExpr(const InitListExpr *S) {
 627     QualType Type = S->getType();
 628
 629     if (!Type->isStructureOrClassType()) {
 630       if (auto *Val = Env.createValue(Type))
 631         Env.setValue(*S, *Val);
 632
 633       return;
 634     }
 635
 636     // In case the initializer list is transparent, we just need to propagate
 637     // the value that it contains.
 638     if (S->isSemanticForm() && S->isTransparent()) {
 639       propagateValue(*S->getInit(0), *S, Env);
 640       return;
 641     }
 642
 643     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
 644
 645     // This only contains the direct fields for the given type.
 646     std::vector<FieldDecl *> FieldsForInit =
 647         getFieldsForInitListExpr(Type->getAsRecordDecl());
 648
 649     // `S->inits()` contains all the initializer epressions, including the
 650     // ones for direct base classes.
 651     auto Inits = S->inits();
 652     size_t InitIdx = 0;
 653
 654     // Initialize base classes.
 655     if (auto* R = S->getType()->getAsCXXRecordDecl()) {
 656       assert(FieldsForInit.size() + R->getNumBases() == Inits.size());
 657       for ([[maybe_unused]] const CXXBaseSpecifier &Base : R->bases()) {
 658         assert(InitIdx < Inits.size());
 659         auto Init = Inits[InitIdx++];
 660         assert(Base.getType().getCanonicalType() ==
 661                Init->getType().getCanonicalType());
 662         auto* BaseVal = cast_or_null<RecordValue>(Env.getValue(*Init));
 663         if (!BaseVal)
 664           BaseVal = cast<RecordValue>(Env.createValue(Init->getType()));
 665         // Take ownership of the fields of the `RecordValue` for the base class
 666         // and incorporate them into the "flattened" set of fields for the
 667         // derived class.
 668         auto Children = BaseVal->getLoc().children();
 669         FieldLocs.insert(Children.begin(), Children.end());
 670       }
 671     }
 672
 673     assert(FieldsForInit.size() == Inits.size() - InitIdx);
 674     for (auto Field : FieldsForInit) {
 675       assert(InitIdx < Inits.size());
 676       auto Init = Inits[InitIdx++];
 677       assert(
 678           // The types are same, or
 679           Field->getType().getCanonicalType().getUnqualifiedType() ==
 680               Init->getType().getCanonicalType() ||
 681           // The field's type is T&, and initializer is T
 682           (Field->getType()->isReferenceType() &&
 683               Field->getType().getCanonicalType()->getPointeeType() ==
 684               Init->getType().getCanonicalType()));
 685       auto& Loc = Env.createObject(Field->getType(), Init);
 686       FieldLocs.insert({Field, &Loc});
 687     }
 688
 689     // Check that we satisfy the invariant that a `RecordStorageLoation`
 690     // contains exactly the set of modeled fields for that type.
 691     // `ModeledFields` includes fields from all the bases, but only the
 692     // modeled ones. However, if a class type is initialized with an
 693     // `InitListExpr`, all fields in the class, including those from base
 694     // classes, are included in the set of modeled fields. The code above
 695     // should therefore populate exactly the modeled fields.
 696     assert([&]() {
 697       auto ModeledFields =
 698           Env.getDataflowAnalysisContext().getModeledFields(Type);
 699       if (ModeledFields.size() != FieldLocs.size())
 700         return false;
 701       for ([[maybe_unused]] auto [Field, Loc] : FieldLocs)
 702         if (!ModeledFields.contains(cast_or_null<FieldDecl>(Field)))
 703           return false;
 704       return true;
 705     }());
 706
 707     auto &Loc =
 708         Env.getDataflowAnalysisContext().arena().create<RecordStorageLocation>(
 709             Type, std::move(FieldLocs));
 710     RecordValue &RecordVal = Env.create<RecordValue>(Loc);
 711
 712     Env.setValue(Loc, RecordVal);
 713
 714     Env.setValue(*S, RecordVal);
 715
 716     // FIXME: Implement array initialization.
 717   }
 718
 719   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
 720     Env.setValue(*S, Env.getBoolLiteralValue(S->getValue()));
 721   }
 722
 723   void VisitIntegerLiteral(const IntegerLiteral *S) {
 724     Env.setValue(*S, Env.getIntLiteralValue(S->getValue()));
 725   }
 726
 727   void VisitParenExpr(const ParenExpr *S) {
 728     // The CFG does not contain `ParenExpr` as top-level statements in basic
 729     // blocks, however manual traversal to sub-expressions may encounter them.
 730     // Redirect to the sub-expression.
 731     auto *SubExpr = S->getSubExpr();
 732     assert(SubExpr != nullptr);
 733     Visit(SubExpr);
 734   }
 735
 736   void VisitExprWithCleanups(const ExprWithCleanups *S) {
 737     // The CFG does not contain `ExprWithCleanups` as top-level statements in
 738     // basic blocks, however manual traversal to sub-expressions may encounter
 739     // them. Redirect to the sub-expression.
 740     auto *SubExpr = S->getSubExpr();
 741     assert(SubExpr != nullptr);
 742     Visit(SubExpr);
 743   }
 744
 745 private:
 746   /// Returns the value for the sub-expression `SubExpr` of a logic operator.
 747   BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
 748     // `SubExpr` and its parent logic operator might be part of different basic
 749     // blocks. We try to access the value that is assigned to `SubExpr` in the
 750     // corresponding environment.
 751     if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
 752       if (auto *Val =
 753               dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
 754         return *Val;
 755
 756     // The sub-expression may lie within a basic block that isn't reachable,
 757     // even if we need it to evaluate the current (reachable) expression
 758     // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`
 759     // within the current environment and then try to get the value that gets
 760     // assigned to it.
 761     if (Env.getValue(SubExpr) == nullptr)
 762       Visit(&SubExpr);
 763     if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr)))
 764       return *Val;
 765
 766     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
 767     // boolean value for it.
 768     return Env.makeAtomicBoolValue();
 769   }
 770
 771   // If context sensitivity is enabled, try to analyze the body of the callee
 772   // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
 773   template <typename E>
 774   void transferInlineCall(const E *S, const FunctionDecl *F) {
 775     const auto &Options = Env.getDataflowAnalysisContext().getOptions();
 776     if (!(Options.ContextSensitiveOpts &&
 777           Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
 778       return;
 779
 780     const ControlFlowContext *CFCtx =
 781         Env.getDataflowAnalysisContext().getControlFlowContext(F);
 782     if (!CFCtx)
 783       return;
 784
 785     // FIXME: We don't support context-sensitive analysis of recursion, so
 786     // we should return early here if `F` is the same as the `FunctionDecl`
 787     // holding `S` itself.
 788
 789     auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
 790
 791     auto CalleeEnv = Env.pushCall(S);
 792
 793     // FIXME: Use the same analysis as the caller for the callee. Note,
 794     // though, that doing so would require support for changing the analysis's
 795     // ASTContext.
 796     auto Analysis = NoopAnalysis(CFCtx->getDecl().getASTContext(),
 797                                  DataflowAnalysisOptions{Options});
 798
 799     auto BlockToOutputState =
 800         dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
 801     assert(BlockToOutputState);
 802     assert(ExitBlock < BlockToOutputState->size());
 803
 804     auto &ExitState = (*BlockToOutputState)[ExitBlock];
 805     assert(ExitState);
 806
 807     Env.popCall(S, ExitState->Env);
 808   }
 809
 810   const StmtToEnvMap &StmtToEnv;
 811   Environment &Env;
 812 };
 813
 814 } // namespace
 815
 816 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
 817   TransferVisitor(StmtToEnv, Env).Visit(&S);
 818 }
 819
 820 } // namespace dataflow
 821 } // namespace clang