[clang][dataflow] Eliminate intermediate `ReferenceValue`s from `Environment::DeclToLoc`.

[mboehme]

Summary

For the wider context of this change, see the RFC at
https://discourse.llvm.org/t/70086.

After this change, global and local variables of reference type are associated
directly with the StorageLocation of the referenced object instead of the
StorageLocation of a ReferenceValue.

Some tests that explicitly check for an existence of ReferenceValue for a
variable of reference type have been modified accordingly.

As discussed in the RFC, I have added an assertion to Environment::join() to
check that if both environments contain an entry for the same declaration in
DeclToLoc, they both map to the same StorageLocation. As discussed in
https://discourse.llvm.org/t/70086/5, this also necessitates removing
declarations from DeclToLoc when they go out of scope.

In the RFC, I proposed a gradual migration for this change, but it appears
that all of the callers of `Environment::setStorageLocation(const ValueDecl &,
SkipPast` are in the dataflow framework itself, and that there are only a few of
them.

As this is the function whose semantics are changing in a way that callers
potentially need to adapt to, I've decided to change the semantics of the
function directly.

The semantics of getStorageLocation(const ValueDecl &, SkipPast SP now no
longer depend on the behavior of the SP parameter. (There don't appear to be
any callers that use SkipPast::ReferenceThenPointer, so I've added an
assertion that forbids this usage.)

This patch adds a default argument for the SP parameter and removes the
explicit SP argument at the callsites that are touched by this change. A
followup patch will remove the argument from the remaining callsites,
allowing the SkipPast parameter to be removed entirely. (I don't want to do
that in this patch so that semantics-changing changes can be reviewed separately
from semantics-neutral changes.)

[mboehme]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

43

There were a number of pre-existing declarations that were ODR violation risks. I'm adding a new file-local function below, so instead of making it static, I decided to put everything that's supposed to be file-local in an anonymous namespace.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

505

We're creating a slightly deeper object hierarchy here because we now call createValue() with the non-reference type in a number of places. I believe this slightly deeper hierarchy shouldn't be a problem in practice.

2662

The changes in this test are a result of the fact that we now remove declarations from Environment::DeclToLoc when they go out of scope.

[mboehme]

Add two assertions that I forgot to add in the first upload.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

43

https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

"Avoid putting declarations other than classes into anonymous namespaces"

[mboehme]

Use anonymous namespace only for classes, static for functions.

[mboehme]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

43

Thanks for the pointer -- done!

[ymandel]

Really nice patch. Thanks for this improvement!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

307–311

Maybe comment as to why we're not use the VarDecl overloads of createStorageLocation and why we're specifically using getNonReferenceType for createValue.

610

631

would isa_and_nonnull work?

clang/lib/Analysis/FlowSensitive/Transfer.cpp

279–281

329

why the recursive call rather than relying on what we know about their structure?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

616

Would we dump this in release builds? Do we want to limit this to debug/assert builds?

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

I think one question is whether we are interested in ScopeEnd or LifetimeEnd, see the discussions in https://reviews.llvm.org/D15031 and https://reviews.llvm.org/D16403, specifically Devin's comment:

In D16403#799926, @dcoughlin wrote:

@dcoughlin As a reviewer of both patches - could you tell us what's the difference between them? And how are we going to resolve this issue?

These two patches are emitting markers in the CFG for different things.

Here is how I would characterize the difference between the two patches.

• Despite its name, https://reviews.llvm.org/D15031, is really emitting markers for when the lifetime of a C++ object in an automatic variable ends. For C++ objects with non-trivial destructors, this point is when the destructor is called. At this point the storage for the variable still exists, but what you can do with that storage is very restricted by the language because its contents have been destroyed. Note that even with the contents of the object have been destroyed, it is still meaningful to, say, take the address of the variable and construct a new object into it with a placement new. In other words, the same variable can have different objects, with different lifetimes, in it at different program points.

• In contrast, the purpose of this patch (https://reviews.llvm.org/D16403) is to add markers for when the storage duration for the variable begins and ends (this is, when the storage exists). Once the storage duration has ended, you can't placement new into the variables address, because another variable may already be at that address.

I don't think there is an "issue" to resolve here. We should make sure the two patches play nicely with each other, though. In particular, we should make sure that the markers for when lifetime ends and when storage duration ends are ordered correctly.

What I wanted to add, I wonder if we might not get ScopeEnd event for temporaries and there might be other differences. The Clang implementation of P1179 used LifetimeEnd instead of ScopeEnd, and I believe probably most clients are more interested in LifetimeEnd events rather than ScopeEnd.

I think I understand why you went with ScopeEnd for this specific problem, but to avoid the confusion from having both in the Cfg (because I anticipate someone will need LifetimeEnd at some point), I wonder if we can make this work with LifetimeEnd.

[mboehme]

Changes in response to review comments

[mboehme]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

307–311

Added comment on the getNonReferenceType().

As to why we're not using the VarDecl overload -- it's really just because we don't need the "stable" location behavior here. Wasn't sure if this rises to the level of needing to be addressed in a comment, so I've left it out for now. WDYT?

616

True, we'd want to do this only in debug builds. For simplicity, I've taken out the dump entirely -- it's easy enough to add back if we do actually encounter assertion failures here.

631

Good point, done!

clang/lib/Analysis/FlowSensitive/Transfer.cpp

329

Not sure exactly what you're asking?

If we don't want to make a recursive call here, we'd need to duplicate behavior that ProcessVarDecl() already contains and inline that code here. It seems preferable to just call ProcessVarDecl() instead? (Or to put it differently, what is a reason against making this call?)

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

Hm, thanks for bringing it up.

Conincidentally, I realized while chasing another issue that CFGScopeEnd isn't the right construct here. I assumed that we would get a CFGScopeEnd for every variable, but I now realize that we only get a CFGScopeEnd for the first variable in the scope.

So CFGLifetimeEnds definitely looks like the right construct to use here, and indeed it's what I originally tried to use. Unfortuately, CFG::BuildOptions::AddLifetime cannot be used at the same time as AddImplicitDtors, which we already use. We don't actually need the CFGElements added by AddImplicitDtors, but we do need AddTemporaryDtors, and that in turn can only be turned on if AddImplicitDtors is turned on.

It looks as if I will need to break one of these constraints. It looks as if the constraint that is easiest to break is that AddLifetime currently cannot be used at the same time as AddImplicitDtors. I'm not sure why this constraint currently exists (I'd appreciate any insights you or others may have), but I suspect it's because it's hard to ensure that the CFGElements added by AddImplicitDtors are ordered correctly with respect to the CFGLifetimeEnds elements.

Anyway, this requires a change to CFG one way or another. I'll work on that next. I'll then make the required changes to this patch and will ask for another look before submitting.

[ymandel]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

329

At least previously, given what we know of their structure, the inlining was trivial. But, I think your second point is key -- why not recursively call -- it's a clean solution. I'm fine with that, thx.

[mboehme]

• Removed usage of CFGScopeEnd
• Removed the assertion that two DeclToLoc to be joined don't contain conflicting entries

[mboehme]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

I've taken a look at what it would take to make AddLifetime coexist with AddImplicitDtors, and it's hard (because we need to get the ordering right, and that's non-trivial).

So I've instead decided to remove the behavior from this patch that removes declarations from Environment::DeclToLoc when they go out of scope and have instead added FIXMEs in various places.

It would be nice to add this behavior, but all that it was used for in this patch was the assertion I added that the two DeclToLocs to be joined don't have entries for the same declaration but with different storage locations. Instead, if we now encounter a scenario where we have such conflicting entries for a declaration (as discussed in https://discourse.llvm.org/t//70086/5), we use the existing behavior of intersectDenseMaps that removes the corresponding declaration from the joined map.

It would be nice to be able to retain the assertion, but I don't really see any plausible failure modes that it would guard against. Also, when I tested various existing clients of the dataflow framework with this assertion in place, I didn't see any assertion failures.

WDYT?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

Why do you need AddImplicitDtors? I have the impression if we have the LifetimeEnd markers, we can sort of simulate implicit dtors. This is more like a note for the future if we cannot make both work at the same time.

For this patch, I am OK with the current solution.

[mboehme]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

We don't need AddImplicitDtors per se, but we do need AddTemporaryDtors, and to get that we have to set AddImplicitDtors as well. (And it's hard to disentangle both of those too.)

We need AddTemporaryDtors so that we get a CFGTerminator::TemporaryDtorsBranch, which is used here. I'm not sure that we can get something similar with CFGLifetimeEnds -- this would at the least require some more research.

[gribozavr2]

LGTM still.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

Oh, I see! Sorry, somehow my mind skipped over AddTemporaryDtors. Indeed, I don't think this is a simple problem to solve. I'd love to see AddScopes to be removed from the CFG, it does not look useful in its current form. And hopefully AddLifetime, AddImplicitDtors, and AddTemporaryDtors could all be unified as they have some overlapping.

[mboehme]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

329

Yes, I would love that too -- it would simplify life for clients as well as make the code cleaner I think.

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

public:
   /// location to `E` in the environment. Does not assign a value to the
   /// returned storage location in the environment.
   StorageLocation &createStorageLocation(const Expr &E);
 
   /// Assigns `Loc` as the storage location of `D` in the environment.
   ///
   /// Requirements:
   ///
-  ///  `D` must not be assigned a storage location in the environment.
+  ///  `D` must not already have a storage location in the environment.
+  ///
+  ///  If `D` has reference type, `Loc` must refer directly to the referenced
+  ///  object (if any), not to a `ReferenceValue`, and it is not permitted to
+  ///  later change `Loc` to refer to a `ReferenceValue.`
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
 
-  /// Returns the storage location assigned to `D` in the environment, applying
-  /// the `SP` policy for skipping past indirections, or null if `D` isn't
-  /// assigned a storage location in the environment.
-  StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
+  /// Removes the storage location assigned to `D`.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must have a storage location in the environment.
+  void unsetStorageLocation(const ValueDecl &D);
+
+  /// Returns the storage location assigned to `D` in the environment, or null
+  /// if `D` isn't assigned a storage location in the environment.
+  ///
+  /// Note that if `D` has reference type, the storage location that is returned
+  /// refers directly to the referenced object, not a `ReferenceValue`.
+  ///
+  /// The `SP` parameter is deprecated and has no effect. In addition, it is
+  /// not permitted to pass `SkipPast::ReferenceThenPointer` for this parameter.
+  /// New uses of this function should use the default argument for `SP`.
+  StorageLocation *getStorageLocation(const ValueDecl &D,
+                                      SkipPast SP = SkipPast::None) const;
 
   /// Assigns `Loc` as the storage location of `E` in the environment.
   ///
   /// Requirements:
   ///
   ///  `E` must not be assigned a storage location in the environment.
   void setStorageLocation(const Expr &E, StorageLocation &Loc);
 
public:
   void setValue(const StorageLocation &Loc, Value &Val);
 
   /// Returns the value assigned to `Loc` in the environment or null if `Loc`
   /// isn't assigned a value in the environment.
   Value *getValue(const StorageLocation &Loc) const;
 
   /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
   /// is assigned a storage location in the environment, otherwise returns null.
-  Value *getValue(const ValueDecl &D, SkipPast SP) const;
+  ///
+  /// The `SP` parameter is deprecated and has no effect. In addition, it is
+  /// not permitted to pass `SkipPast::ReferenceThenPointer` for this parameter.
+  /// New uses of this function should use the default argument for `SP`.
+  Value *getValue(const ValueDecl &D, SkipPast SP = SkipPast::None) const;
 
   /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
   /// is assigned a storage location in the environment, otherwise returns null.
   Value *getValue(const Expr &E, SkipPast SP) const;
 
   // FIXME: should we deprecate the following & call arena().create() directly?
 
   /// Creates a `T` (some subclass of `Value`), forwarding `args` to the

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

 llvm::Expected<ControlFlowContext>
 ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) {
   CFG::BuildOptions Options;
   Options.PruneTriviallyFalseEdges = false;
   Options.AddImplicitDtors = true;
   Options.AddTemporaryDtors = true;
   Options.AddInitializers = true;
   Options.AddCXXDefaultInitExprInCtors = true;
+  Options.AddScopes = true;
 
   // Ensure that all sub-expressions in basic blocks are evaluated.
   Options.setAllAlwaysAdd();
 
   auto Cfg = CFG::buildCFG(D, &S, &C, Options);
   if (Cfg == nullptr)
     return llvm::createStringError(
         std::make_error_code(std::errc::invalid_argument),

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
   for (auto &Entry : Map1) {
     auto It = Map2.find(Entry.first);
     if (It != Map2.end() && Entry.second == It->second)
       Result.insert({Entry.first, Entry.second});
   }
   return Result;
 }
 
+/// Returns whether there is a key that is present in both maps and maps to
+/// different values.
+template <typename K, typename V>
+bool conflictingValues(const llvm::DenseMap<K, V> &Map1,
+                       const llvm::DenseMap<K, V> &Map2) {
+  for (auto &Entry : Map1) {
+    auto It = Map2.find(Entry.first);
+    if (It != Map2.end() && Entry.second != It->second)
+      return true;
+  }
+  return false;
+}
+
 static bool compareDistinctValues(QualType Type, Value &Val1,
                                   const Environment &Env1, Value &Val2,
                                   const Environment &Env2,
                                   Environment::ValueModel &Model) {
   // Note: Potentially costly, but, for booleans, we could check whether both
   // can be proven equivalent in their respective environments.
 
   // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
 
   // These have to be added before the lines that follow to ensure that
   // `create*` work correctly for structs.
   DACtx->addModeledFields(Fields);
 
   for (const VarDecl *D : Vars) {
     if (getStorageLocation(*D, SkipPast::None) != nullptr)
       continue;
-    auto &Loc = createStorageLocation(*D);
+    auto &Loc = createStorageLocation(D->getType().getNonReferenceType());
     setStorageLocation(*D, Loc);
-    if (auto *Val = createValue(D->getType()))
+    if (auto *Val = createValue(D->getType().getNonReferenceType()))
       setValue(Loc, *Val);
   }
 
   for (const FunctionDecl *FD : Funcs) {
     if (getStorageLocation(*FD, SkipPast::None) != nullptr)
       continue;
     auto &Loc = createStorageLocation(FD->getType());
     setStorageLocation(*FD, Loc);
Environment::Environment(DataflowAnalysisContext &DACtx,
 
   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
     assert(FuncDecl->getBody() != nullptr);
 
     initFieldsGlobalsAndFuncs(FuncDecl);
 
     for (const auto *ParamDecl : FuncDecl->parameters()) {
       assert(ParamDecl != nullptr);
-      auto &ParamLoc = createStorageLocation(*ParamDecl);
+      auto &ParamLoc =
+          createStorageLocation(ParamDecl->getType().getNonReferenceType());
       setStorageLocation(*ParamDecl, ParamLoc);
-      if (Value *ParamVal = createValue(ParamDecl->getType()))
+      if (Value *ParamVal =
+              createValue(ParamDecl->getType().getNonReferenceType()))
           setValue(ParamLoc, *ParamVal);
     }
 
     QualType ReturnType = FuncDecl->getReturnType();
     ReturnLoc = &createStorageLocation(ReturnType);
   }
 
   if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
     auto *Parent = MethodDecl->getParent();
for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
     assert(ParamIt != FuncDecl->param_end());
 
     const Expr *Arg = Args[ArgIndex];
     auto *ArgLoc = getStorageLocation(*Arg, SkipPast::Reference);
     if (ArgLoc == nullptr)
       continue;
 
     const VarDecl *Param = *ParamIt;
-    auto &Loc = createStorageLocation(*Param);
-    setStorageLocation(*Param, Loc);
 
     QualType ParamType = Param->getType();
     if (ParamType->isReferenceType()) {
-      auto &Val = arena().create<ReferenceValue>(*ArgLoc);
-      setValue(Loc, Val);
-    } else if (auto *ArgVal = getValue(*ArgLoc)) {
+      setStorageLocation(*Param, *ArgLoc);
+    } else {
+      auto &Loc = createStorageLocation(*Param);
+      setStorageLocation(*Param, Loc);
+
+      if (auto *ArgVal = getValue(*ArgLoc)) {
         setValue(Loc, *ArgVal);
       } else if (Value *Val = createValue(ParamType)) {
         setValue(Loc, *Val);
       }
     }
   }
+}
 
 void Environment::popCall(const Environment &CalleeEnv) {
   // We ignore `DACtx` because it's already the same in both. We don't want the
   // callee's `DeclCtx`, `ReturnLoc` or `ThisPointeeLoc`. We don't bring back
   // `DeclToLoc` and `ExprToLoc` because we want to be able to later analyze the
   // same callee in a different context, and `setStorageLocation` requires there
   // to not already be a storage location assigned. Conceptually, these maps
   // capture information from the local scope, so when popping that scope, we do
LatticeJoinEffect Environment::join(const Environment &Other,
   auto Effect = LatticeJoinEffect::Unchanged;
 
   Environment JoinedEnv(*DACtx);
 
   JoinedEnv.CallStack = CallStack;
   JoinedEnv.ReturnLoc = ReturnLoc;
   JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
 
+  assert(!conflictingValues(DeclToLoc, Other.DeclToLoc));
   JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
   if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
   JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
   if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
StorageLocation &Environment::createStorageLocation(const Expr &E) {
   // Evaluated expressions are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated expressions are stored in the analysis context.
   return DACtx->getStableStorageLocation(E);
 }
 
 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
   assert(!DeclToLoc.contains(&D));
+  assert(dyn_cast_or_null<ReferenceValue>(getValue(Loc)) == nullptr);
   DeclToLoc[&D] = &Loc;
 }
 
+void Environment::unsetStorageLocation(const ValueDecl &D) {
+  bool erased = DeclToLoc.erase(&D);
+  if (!erased)
+    D.dump();
+  assert(erased);
+}
+
 StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
                                                  SkipPast SP) const {
+  assert(SP != SkipPast::ReferenceThenPointer);
+
   auto It = DeclToLoc.find(&D);
-  return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
+  if (It == DeclToLoc.end())
+    return nullptr;
+
+  StorageLocation *Loc = It->second;
+
+  assert(dyn_cast_or_null<ReferenceValue>(getValue(*Loc)) == nullptr);
+
+  return Loc;
 }
 
 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
   const Expr &CanonE = ignoreCFGOmittedNodes(E);
   assert(!ExprToLoc.contains(&CanonE));
   ExprToLoc[&CanonE] = &Loc;
 }
 

 }
 
 Value *Environment::getValue(const StorageLocation &Loc) const {
   auto It = LocToVal.find(&Loc);
   return It == LocToVal.end() ? nullptr : It->second;
 }
 
 Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
+  assert(SP != SkipPast::ReferenceThenPointer);
+
   auto *Loc = getStorageLocation(D, SP);
   if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);
 }
 
 Value *Environment::getValue(const Expr &E, SkipPast SP) const {
   auto *Loc = getStorageLocation(E, SP);

clang/lib/Analysis/FlowSensitive/Transfer.cpp

public:
 
   void VisitDeclRefExpr(const DeclRefExpr *S) {
     const ValueDecl *VD = S->getDecl();
     assert(VD != nullptr);
     auto *DeclLoc = Env.getStorageLocation(*VD, SkipPast::None);
     if (DeclLoc == nullptr)
       return;
 
-    // If the value is already an lvalue, don't double-wrap it.
-    if (isa_and_nonnull<ReferenceValue>(Env.getValue(*DeclLoc))) {
-      // We only expect to encounter a `ReferenceValue` for a reference type
-      // (always) or for `BindingDecl` (sometimes). For the latter, we can't
-      // rely on type, because their type does not indicate whether they are a
-      // reference type. The assert is not strictly necessary, since we don't
-      // depend on its truth to proceed. But, it verifies our assumptions,
-      // which, if violated, probably indicate a problem elsewhere.
-      assert((VD->getType()->isReferenceType() || isa<BindingDecl>(VD)) &&
-             "Only reference-typed declarations or `BindingDecl`s should map "
-             "to `ReferenceValue`s");
-      Env.setStorageLocation(*S, *DeclLoc);
-    } else {
-      auto &Loc = Env.createStorageLocation(*S);
-      auto &Val = Env.create<ReferenceValue>(*DeclLoc);
-      Env.setStorageLocation(*S, Loc);
-      Env.setValue(Loc, Val);
-    }
   }
 
   void VisitDeclStmt(const DeclStmt *S) {
     // Group decls are converted into single decls in the CFG so the cast below
     // is safe.
     const auto &D = *cast<VarDecl>(S->getSingleDecl());
 
+    ProcessVarDecl(D);
+  }
+
+  void ProcessVarDecl(const VarDecl &D) {
     // Static local vars are already initialized in `Environment`.
     if (D.hasGlobalStorage())
       return;
 
-    // The storage location for `D` could have been created earlier, before the
-    // variable's declaration statement (for example, in the case of
-    // BindingDecls).
-    auto *MaybeLoc = Env.getStorageLocation(D, SkipPast::None);
-    if (MaybeLoc == nullptr) {
-      MaybeLoc = &Env.createStorageLocation(D);
-      Env.setStorageLocation(D, *MaybeLoc);
+    if (D.getType()->isReferenceType()) {
+      // If this is the holding variable for a `BindingDecl`, we may already
+      // have a storage location set up -- so check. (See also explanation below
+      // where we process the `BindingDecl`.)
+      if (Env.getStorageLocation(D) == nullptr) {
+        const Expr *InitExpr = D.getInit();
+        assert(InitExpr != nullptr);
+        if (auto *InitExprLoc =
+                Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
+          Env.setStorageLocation(D, *InitExprLoc);
+        } else {
+          // Even though we have an initializer, we might not get an
+          // InitExprLoc, for example if the InitExpr is a CallExpr for which we
+          // don't have a function body. In this case, we just invent a storage
+          // location and value -- it's the best we can do.
+          StorageLocation &Loc =
+              Env.createStorageLocation(D.getType().getNonReferenceType());
+          Env.setStorageLocation(D, Loc);
+          if (Value *Val = Env.createValue(D.getType().getNonReferenceType()))
+            Env.setValue(Loc, *Val);
         }
-    auto &Loc = *MaybeLoc;
+      }
+    } else {
+      // Not a reference type.
+
+      assert(Env.getStorageLocation(D) == nullptr);
+      StorageLocation &Loc = Env.createStorageLocation(D);
+      Env.setStorageLocation(D, Loc);
 
       const Expr *InitExpr = D.getInit();
       if (InitExpr == nullptr) {
         // No initializer expression - associate `Loc` with a new value.
         if (Value *Val = Env.createValue(D.getType()))
           Env.setValue(Loc, *Val);
         return;
       }
 
-    if (D.getType()->isReferenceType()) {
-      // Initializing a reference variable - do not create a reference to
-      // reference.
-      // FIXME: reuse the ReferenceValue instead of creating a new one.
-      if (auto *InitExprLoc =
-              Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
-        auto &Val = Env.create<ReferenceValue>(*InitExprLoc);
-        Env.setValue(Loc, Val);
-      }
-    } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
+      if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
         Env.setValue(Loc, *InitExprVal);
       }
 
       if (Env.getValue(Loc) == nullptr) {
-      // We arrive here in (the few) cases where an expression is intentionally
-      // "uninterpreted". There are two ways to handle this situation: propagate
-      // the status, so that uninterpreted initializers result in uninterpreted
-      // variables, or provide a default value. We choose the latter so that
-      // later refinements of the variable can be used for reasoning about the
-      // surrounding code.
+        // We arrive here in (the few) cases where an expression is
+        // intentionally "uninterpreted". There are two ways to handle this
+        // situation: propagate the status, so that uninterpreted initializers
+        // result in uninterpreted variables, or provide a default value. We
+        // choose the latter so that later refinements of the variable can be
+        // used for reasoning about the surrounding code.
         //
         // FIXME. If and when we interpret all language cases, change this to
-      // assert that `InitExpr` is interpreted, rather than supplying a default
-      // value (assuming we don't update the environment API to return
+        // assert that `InitExpr` is interpreted, rather than supplying a
+        // default value (assuming we don't update the environment API to return
         // references).
         if (Value *Val = Env.createValue(D.getType()))
           Env.setValue(Loc, *Val);
       }
+    }
 
     // `DecompositionDecl` must be handled after we've interpreted the loc
     // itself, because the binding expression refers back to the
     // `DecompositionDecl` (even though it has no written name).
     if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
       // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
       // needs to be evaluated after initializing the values in the storage for
       // VarDecl, as the bindings refer to them.
       // FIXME: Add support for ArraySubscriptExpr.
       // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
       for (const auto *B : Decomp->bindings()) {
         if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
           auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
           if (DE == nullptr)
             continue;
 
           // ME and its base haven't been visited because they aren't included
           // in the statements of the CFG basic block.
           VisitDeclRefExpr(DE);
           VisitMemberExpr(ME);
 
           if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference))
             Env.setStorageLocation(*B, *Loc);
         } else if (auto *VD = B->getHoldingVar()) {
-          // Holding vars are used to back the BindingDecls of tuple-like
-          // types. The holding var declarations appear *after* this statement,
-          // so we have to create a location for them here to share with `B`. We
-          // don't visit the binding, because we know it will be a DeclRefExpr
-          // to `VD`. Note that, by construction of the AST, `VD` will always be
-          // a reference -- either lvalue or rvalue.
-          auto &VDLoc = Env.createStorageLocation(*VD);
-          Env.setStorageLocation(*VD, VDLoc);
-          Env.setStorageLocation(*B, VDLoc);
+          // Holding vars are used to back the `BindingDecl`s of tuple-like
+          // types. The holding var declarations appear after the
+          // `DecompositionDecl`, so we have to explicitly process them here
+          // to know their storage location. They will be processed a second
+          // time when we visit their `VarDecl`s, so we have code that protects
+          // against this above.
+          ProcessVarDecl(*VD);
+          auto *VDLoc = Env.getStorageLocation(*VD);
+          assert(VDLoc != nullptr);
+          Env.setStorageLocation(*B, *VDLoc);
         }
       }
     }
   }
 
   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
if (isa<EnumConstantDecl>(Member))
       return;
 
     if (auto *D = dyn_cast<VarDecl>(Member)) {
       if (D->hasGlobalStorage()) {
         auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
         if (VarDeclLoc == nullptr)
           return;
 
-        if (VarDeclLoc->getType()->isReferenceType()) {
-          assert(isa_and_nonnull<ReferenceValue>(Env.getValue((*VarDeclLoc))) &&
-                 "reference-typed declarations map to `ReferenceValue`s");
-          Env.setStorageLocation(*S, *VarDeclLoc);
-        } else {
-          auto &Loc = Env.createStorageLocation(*S);
-          Env.setStorageLocation(*S, Loc);
-          Env.setValue(Loc, Env.create<ReferenceValue>(*VarDeclLoc));
-        }
         return;
       }
     }
 
     // The receiver can be either a value or a pointer to a value. Skip past the
     // indirection to handle both cases.
     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
 #define DEBUG_TYPE "clang-dataflow"
 
 namespace clang {
 namespace dataflow {
 
 /// Returns the index of `Block` in the successors of `Pred`.
 static int blockIndexInPredecessor(const CFGBlock &Pred,
                                    const CFGBlock &Block) {
   auto BlockPos = llvm::find_if(
       Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
         return Succ && Succ->getBlockID() == Block.getBlockID();
       });
   return BlockPos - Pred.succ_begin();
 }
 
 static bool isLoopHead(const CFGBlock &B) {
   if (const auto *T = B.getTerminatorStmt())
     switch (T->getStmtClass()) {
       case Stmt::WhileStmtClass:
       case Stmt::DoStmtClass:
       case Stmt::ForStmtClass:
         return true;
       default:
         return false;
     }
 
   return false;
 }
 
+namespace {
+
 // The return type of the visit functions in TerminatorVisitor. The first
 // element represents the terminator expression (that is the conditional
 // expression in case of a path split in the CFG). The second element
 // represents whether the condition was true or false.
 using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
 
 /// Extends the flow condition of an environment based on a terminator
 /// statement.
struct AnalysisContext {
   /// Initial state to start the analysis.
   const Environment &InitEnv;
   Logger &Log;
   /// Stores the state of a CFG block if it has been evaluated by the analysis.
   /// The indices correspond to the block IDs.
   llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
 };
 
+} // namespace
+
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `AC.BlockStates` that are set to
 ///   `std::nullopt` represent basic blocks that are not evaluated yet.
if (!MaybeState) {
     // to enable building analyses like computation of dominators that
     // initialize the state of each basic block differently.
     MaybeState.emplace(Analysis.typeErasedInitialElement(), AC.InitEnv);
   }
   return *MaybeState;
 }
 
 /// Built-in transfer function for `CFGStmt`.
-void builtinTransferStatement(const CFGStmt &Elt,
-                              TypeErasedDataflowAnalysisState &InputState,
-                              AnalysisContext &AC) {
+static void
+builtinTransferStatement(const CFGStmt &Elt,
   const Stmt *S = Elt.getStmt();
   assert(S != nullptr);
   transfer(StmtToEnvMap(AC.CFCtx, AC.BlockStates), *S, InputState.Env);
 }
 
 /// Built-in transfer function for `CFGInitializer`.
-void builtinTransferInitializer(const CFGInitializer &Elt,
-                                TypeErasedDataflowAnalysisState &InputState) {
+static void
+builtinTransferInitializer(const CFGInitializer &Elt,
   const CXXCtorInitializer *Init = Elt.getInitializer();
   assert(Init != nullptr);
 
   auto &Env = InputState.Env;
   const auto &ThisLoc =
       *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
 
   const FieldDecl *Member = Init->getMember();
if (Member->getType()->isReferenceType()) {
     auto &MemberLoc = ThisLoc.getChild(*Member);
     Env.setValue(MemberLoc, Env.create<ReferenceValue>(*InitStmtLoc));
   } else {
     auto &MemberLoc = ThisLoc.getChild(*Member);
     Env.setValue(MemberLoc, *InitStmtVal);
   }
 }
 
-void builtinTransfer(const CFGElement &Elt,
+static void
+builtinTransferScopeEnd(const CFGScopeEnd &Elt,
+                        TypeErasedDataflowAnalysisState &InputState) {
+  if (const VarDecl *VD = Elt.getVarDecl()) {
+    InputState.Env.unsetStorageLocation(*VD);
+  }
+}
+
+static void builtinTransfer(const CFGElement &Elt,
                             TypeErasedDataflowAnalysisState &State,
                             AnalysisContext &AC) {
   switch (Elt.getKind()) {
   case CFGElement::Statement:
     builtinTransferStatement(Elt.castAs<CFGStmt>(), State, AC);
     break;
   case CFGElement::Initializer:
     builtinTransferInitializer(Elt.castAs<CFGInitializer>(), State);
     break;
+  case CFGElement::ScopeEnd:
+    builtinTransferScopeEnd(Elt.castAs<CFGScopeEnd>(), State);
+    break;
   default:
     // FIXME: Evaluate other kinds of `CFGElement`.
     break;
   }
 }
 
 /// Transfers `State` by evaluating each element in the `Block` based on the
 /// `AC.Analysis` specified.
 ///
 /// Built-in transfer functions (if the option for `ApplyBuiltinTransfer` is set
 /// by the analysis) will be applied to the element before evaluation by the
 /// user-specified analysis.
 /// `PostVisitCFG` (if provided) will be applied to the element after evaluation
 /// by the user-specified analysis.
-TypeErasedDataflowAnalysisState
+static TypeErasedDataflowAnalysisState
 transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
                  std::function<void(const CFGElement &,
                                     const TypeErasedDataflowAnalysisState &)>
                      PostVisitCFG = nullptr) {
   AC.Log.enterBlock(Block);
   auto State = computeBlockInputState(Block, AC);
   AC.Log.recordState(State);
   for (const auto &Element : Block) {

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
         const StorageLocation *FooLoc =
             Env.getStorageLocation(*FooDecl, SkipPast::None);
-        ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
-
-        const ReferenceValue *FooVal =
-            cast<ReferenceValue>(Env.getValue(*FooLoc));
-        const StorageLocation &FooReferentLoc = FooVal->getReferentLoc();
-        EXPECT_TRUE(isa<AggregateStorageLocation>(&FooReferentLoc));
+        ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooLoc));
 
-        const Value *FooReferentVal = Env.getValue(FooReferentLoc);
+        const Value *FooReferentVal = Env.getValue(*FooLoc);
         EXPECT_TRUE(isa_and_nonnull<StructValue>(FooReferentVal));
       });
 }
 
 TEST(TransferTest, SelfReferentialReferenceVarDecl) {
   std::string Code = R"(
     struct A;
 
for (FieldDecl *Field : BarFields) {
         FAIL() << "Unexpected field: " << Field->getNameAsString();
       }
     }
     ASSERT_THAT(FooRefDecl, NotNull());
     ASSERT_THAT(FooPtrDecl, NotNull());
     ASSERT_THAT(BazRefDecl, NotNull());
     ASSERT_THAT(BazPtrDecl, NotNull());
 
-    const auto *FooLoc = cast<ScalarStorageLocation>(
+    const auto *FooLoc = cast<AggregateStorageLocation>(
         Env.getStorageLocation(*FooDecl, SkipPast::None));
-    const auto *FooVal = cast<ReferenceValue>(Env.getValue(*FooLoc));
-    const auto *FooReferentVal =
-        cast<StructValue>(Env.getValue(FooVal->getReferentLoc()));
+    const auto *FooReferentVal = cast<StructValue>(Env.getValue(*FooLoc));
 
     const auto *BarVal =
         cast<ReferenceValue>(FooReferentVal->getChild(*BarDecl));
     const auto *BarReferentVal =
         cast<StructValue>(Env.getValue(BarVal->getReferentLoc()));
 
     const auto *FooRefVal =
         cast<ReferenceValue>(BarReferentVal->getChild(*FooRefDecl));
-    const StorageLocation &FooReferentLoc = FooRefVal->getReferentLoc();
-    EXPECT_THAT(Env.getValue(FooReferentLoc), IsNull());
+    const auto &FooReferentLoc =
+        cast<AggregateStorageLocation>(FooRefVal->getReferentLoc());
+    EXPECT_THAT(Env.getValue(FooReferentLoc), NotNull());
+    EXPECT_THAT(Env.getValue(FooReferentLoc.getChild(*BarDecl)), IsNull());
 
     const auto *FooPtrVal =
         cast<PointerValue>(BarReferentVal->getChild(*FooPtrDecl));
-    const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc();
-    EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
+    const auto &FooPtrPointeeLoc =
+        cast<AggregateStorageLocation>(FooPtrVal->getPointeeLoc());
+    EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), NotNull());
+    EXPECT_THAT(Env.getValue(FooPtrPointeeLoc.getChild(*BarDecl)), IsNull());
 
     const auto *BazRefVal =
         cast<ReferenceValue>(BarReferentVal->getChild(*BazRefDecl));
     const StorageLocation &BazReferentLoc = BazRefVal->getReferentLoc();
     EXPECT_THAT(Env.getValue(BazReferentLoc), NotNull());
 
     const auto *BazPtrVal =
         cast<PointerValue>(BarReferentVal->getChild(*BazPtrDecl));
runDataflow(
         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
         const StorageLocation *FooLoc =
             Env.getStorageLocation(*FooDecl, SkipPast::None);
-        ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
-
-        const ReferenceValue *FooVal =
-            dyn_cast<ReferenceValue>(Env.getValue(*FooLoc));
-        ASSERT_THAT(FooVal, NotNull());
-
-        const StorageLocation &FooReferentLoc = FooVal->getReferentLoc();
-        EXPECT_TRUE(isa<AggregateStorageLocation>(&FooReferentLoc));
+        ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooLoc));
 
-        const Value *FooReferentVal = Env.getValue(FooReferentLoc);
+        const Value *FooReferentVal = Env.getValue(*FooLoc);
         EXPECT_TRUE(isa_and_nonnull<StructValue>(FooReferentVal));
       });
 }
 
 TEST(TransferTest, PointerParamDecl) {
   std::string Code = R"(
     struct A {};
 
runDataflow(
 
         const auto *ThisLoc = dyn_cast<AggregateStorageLocation>(
             Env.getThisPointeeStorageLocation());
         ASSERT_THAT(ThisLoc, NotNull());
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const auto *FooVal =
-            cast<ReferenceValue>(Env.getValue(*FooDecl, SkipPast::None));
+        const auto *FooLoc = Env.getStorageLocation(*FooDecl);
 
         const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux");
         ASSERT_THAT(QuxDecl, NotNull());
 
-        const auto *QuxVal =
-            cast<ReferenceValue>(Env.getValue(*QuxDecl, SkipPast::None));
-        EXPECT_EQ(&QuxVal->getReferentLoc(), &FooVal->getReferentLoc());
+        const auto *QuxLoc = Env.getStorageLocation(*QuxDecl);
+        EXPECT_EQ(QuxLoc, FooLoc);
       });
 }
 
 TEST(TransferTest, TemporaryObject) {
   std::string Code = R"(
     struct A {
       int Bar;
     };
runDataflow(
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooVal =
             cast<PointerValue>(Env.getValue(*FooDecl, SkipPast::None));
-        const auto *BarVal =
-            cast<ReferenceValue>(Env.getValue(*BarDecl, SkipPast::None));
-        EXPECT_EQ(&BarVal->getReferentLoc(), &FooVal->getPointeeLoc());
+        const auto *BarLoc = Env.getStorageLocation(*BarDecl);
+        EXPECT_EQ(BarLoc, &FooVal->getPointeeLoc());
       });
 }
 
 TEST(TransferTest, VarDeclInitAssignConditionalOperator) {
   std::string Code = R"(
     struct A {};
 
     void target(A Foo, A Bar, bool Cond) {
runDataflow(
       });
 }
 
 TEST(TransferTest, VarDeclInDoWhile) {
   std::string Code = R"(
     void target(int *Foo) {
       do {
         int Bar = *Foo;
+        // [[in_loop]]
       } while (true);
       (void)0;
-      /*[[p]]*/
+      // [[after_loop]]
     }
   )";
   runDataflow(
       Code,
       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
          ASTContext &ASTCtx) {
-        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
-        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+        const Environment &EnvInLoop =
+            getEnvironmentAtAnnotation(Results, "in_loop");
+        const Environment &EnvAfterLoop =
+            getEnvironmentAtAnnotation(Results, "after_loop");
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
 
         const auto *FooVal =
-            cast<PointerValue>(Env.getValue(*FooDecl, SkipPast::None));
+            cast<PointerValue>(EnvAfterLoop.getValue(*FooDecl));
         const auto *FooPointeeVal =
-            cast<IntegerValue>(Env.getValue(FooVal->getPointeeLoc()));
-
-        const auto *BarVal = dyn_cast_or_null<IntegerValue>(
-            Env.getValue(*BarDecl, SkipPast::None));
-        ASSERT_THAT(BarVal, NotNull());
+            cast<IntegerValue>(EnvAfterLoop.getValue(FooVal->getPointeeLoc()));
 
+        const auto *BarVal = cast<IntegerValue>(EnvInLoop.getValue(*BarDecl));
         EXPECT_EQ(BarVal, FooPointeeVal);
+
+        ASSERT_THAT(EnvAfterLoop.getValue(*BarDecl), IsNull());
       });
 }
 
 TEST(TransferTest, AggregateInitialization) {
   std::string BracesCode = R"(
     struct A {
       int Foo;
     };