[dataflow] Use consistent, symmetrical, non-mutating erased signature for join()

[sammccall]

Summary

Mutating join() isn't used and so appears to be an anti-optimization.
Having Lattice vs Environment inconsistent is awkward, particularly when trying
to minimize copies while joining.

This patch eliminates the difference, but doesn't actually change the signature
of join on concrete lattice types (as that's a breaking change).

[ymandel]

LGTM, thanks Sam!

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

 ///     lattice join or a more general widening operation.
 ///
 ///  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
 ///  provide the following public members:
 ///   * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
 ///     argument by computing their least upper bound, modifies the object if
 ///     necessary, and returns an effect indicating whether any changes were
 ///     made to it;
+///     FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)`
 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
 ///     the object is equal to the argument.
 ///
 /// `LatticeT` can optionally provide the following members:
 ///  * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
 ///    lattice element with an  approximation that can reach a fixed point more
 ///    quickly than iterated application of the transfer function alone. The
 ///    previous value is provided to inform the choice of widened value. The
explicit DataflowAnalysis(ASTContext &Context,
       : TypeErasedDataflowAnalysis(Options), Context(Context) {}
 
   ASTContext &getASTContext() final { return Context; }
 
   TypeErasedLattice typeErasedInitialElement() final {
     return {static_cast<Derived *>(this)->initialElement()};
   }
 
-  LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
+  TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1,
                                    const TypeErasedLattice &E2) final {
-    Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
+    // FIXME: change the signature of join() to avoid copying here.
+    Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value);
     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
-    return L1.join(L2);
+    L1.join(L2);
+    return {std::move(L1)};
   }
 
   LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current,
                                     const TypeErasedLattice &Previous) final {
     Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
     const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
     return widenInternal(Rank0{}, C, P);
   }

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

public:
   ///    the same storage locations.
   ///
   /// Requirements:
   ///
   ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
   bool equivalentTo(const Environment &Other,
                     Environment::ValueModel &Model) const;
 
-  /// Joins the environment with `Other` by taking the intersection of storage
-  /// locations and values that are stored in them. Distinct values that are
-  /// assigned to the same storage locations in the environment and `Other` are
-  /// merged using `Model`.
+  /// Joins two environments by taking the intersection of storage locations and
+  /// values that are stored in them. Distinct values that are assigned to the
+  /// same storage locations in `EnvA` and `EnvB` are merged using `Model`.
   ///
   /// Requirements:
   ///
-  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
-  Environment join(const Environment &Other,
-                   Environment::ValueModel &Model) const;
+  ///  `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`.
+  static Environment join(const Environment &EnvA, const Environment &EnvB,
+                          Environment::ValueModel &Model);
 
   /// Widens the environment point-wise, using `PrevEnv` as needed to inform the
   /// approximation.
   ///
   /// Requirements:
   ///
   ///  `PrevEnv` must be the immediate previous version of the environment.
   ///  `PrevEnv` and `this` must use the same `DataflowAnalysisContext`.

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

public:
 
   /// Returns a type-erased lattice element that models the initial state of a
   /// basic block.
   virtual TypeErasedLattice typeErasedInitialElement() = 0;
 
   /// Joins two type-erased lattice elements by computing their least upper
   /// bound. Places the join result in the left element and returns an effect
   /// indicating whether any changes were made to it.
-  virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
+  virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &,
                                            const TypeErasedLattice &) = 0;
 
   /// Chooses a lattice element that approximates the current element at a
   /// program point, given the previous element at that point. Places the
   /// widened result in the current element (`Current`). Widening is optional --
   /// it is only needed to either accelerate convergence (for lattices with
   /// non-trivial height) or guarantee convergence (for lattices with infinite
   /// height).

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
       ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
       LocToVal.size() != PrevEnv.LocToVal.size() ||
       MemberLocToStruct.size() != PrevEnv.MemberLocToStruct.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;
 }
 
-Environment Environment::join(const Environment &Other,
-                              Environment::ValueModel &Model) const {
-  assert(DACtx == Other.DACtx);
-  assert(ThisPointeeLoc == Other.ThisPointeeLoc);
-  assert(CallStack == Other.CallStack);
+Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
+                              Environment::ValueModel &Model) {
+  assert(EnvA.DACtx == EnvB.DACtx);
+  assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
+  assert(EnvA.CallStack == EnvB.CallStack);
 
-  Environment JoinedEnv(*DACtx);
+  Environment JoinedEnv(*EnvA.DACtx);
 
-  JoinedEnv.CallStack = CallStack;
-  JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
+  JoinedEnv.CallStack = EnvA.CallStack;
+  JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
 
-  if (ReturnVal == nullptr || Other.ReturnVal == nullptr) {
+  if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) {
     // `ReturnVal` might not always get set -- for example if we have a return
     // statement of the form `return some_other_func()` and we decide not to
     // analyze `some_other_func()`.
     // In this case, we can't say anything about the joined return value -- we
     // don't simply want to propagate the return value that we do have, because
     // it might not be the correct one.
     // This occurs for example in the test `ContextSensitiveMutualRecursion`.
     JoinedEnv.ReturnVal = nullptr;
-  } else if (areEquivalentValues(*ReturnVal, *Other.ReturnVal)) {
-    JoinedEnv.ReturnVal = ReturnVal;
+  } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) {
+    JoinedEnv.ReturnVal = EnvA.ReturnVal;
   } else {
-    assert(!CallStack.empty());
+    assert(!EnvA.CallStack.empty());
     // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
     // cast.
-    auto *Func = dyn_cast<FunctionDecl>(CallStack.back());
+    auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
     assert(Func != nullptr);
     if (Value *MergedVal =
-            mergeDistinctValues(Func->getReturnType(), *ReturnVal, *this,
-                                *Other.ReturnVal, Other, JoinedEnv, Model))
+            mergeDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA,
+                                *EnvB.ReturnVal, EnvB, JoinedEnv, Model))
       JoinedEnv.ReturnVal = MergedVal;
   }
 
-  if (ReturnLoc == Other.ReturnLoc)
-    JoinedEnv.ReturnLoc = ReturnLoc;
+  if (EnvA.ReturnLoc == EnvB.ReturnLoc)
+    JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
   else
     JoinedEnv.ReturnLoc = nullptr;
 
   // FIXME: Once we're able to remove declarations from `DeclToLoc` when their
   // lifetime ends, add an assertion that there aren't any entries in
   // `DeclToLoc` and `Other.DeclToLoc` that map the same declaration to
   // different storage locations.
-  JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
+  JoinedEnv.DeclToLoc = intersectDenseMaps(EnvA.DeclToLoc, EnvB.DeclToLoc);
 
-  JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
+  JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
 
   JoinedEnv.MemberLocToStruct =
-      intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
+      intersectDenseMaps(EnvA.MemberLocToStruct, EnvB.MemberLocToStruct);
 
   // FIXME: update join to detect backedges and simplify the flow condition
   // accordingly.
-  JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
-      *FlowConditionToken, *Other.FlowConditionToken);
+  JoinedEnv.FlowConditionToken = &EnvA.DACtx->joinFlowConditions(
+      *EnvA.FlowConditionToken, *EnvB.FlowConditionToken);
 
-  for (auto &Entry : LocToVal) {
+  for (auto &Entry : EnvA.LocToVal) {
     const StorageLocation *Loc = Entry.first;
     assert(Loc != nullptr);
 
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
-    auto It = Other.LocToVal.find(Loc);
-    if (It == Other.LocToVal.end())
+    auto It = EnvB.LocToVal.find(Loc);
+    if (It == EnvB.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
     if (areEquivalentValues(*Val, *It->second)) {
       JoinedEnv.LocToVal.insert({Loc, Val});
       continue;
     }
 
-    if (Value *MergedVal =
-            mergeDistinctValues(Loc->getType(), *Val, *this, *It->second, Other,
-                                JoinedEnv, Model)) {
+    if (Value *MergedVal = mergeDistinctValues(
+            Loc->getType(), *Val, EnvA, *It->second, EnvB, JoinedEnv, Model)) {
       JoinedEnv.LocToVal.insert({Loc, MergedVal});
     }
   }
 
   return JoinedEnv;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 };
 
 // Builds a joined TypeErasedDataflowAnalysisState from 0 or more sources,
 // each of which may be owned (built as part of the join) or external (a
 // reference to an Environment that will outlive the builder).
 // Avoids unneccesary copies of the environment.
 class JoinedStateBuilder {
   AnalysisContext ∾
-  std::optional<TypeErasedDataflowAnalysisState> OwnedState;
-  // Points either to OwnedState, an external Environment, or nothing.
-  const TypeErasedDataflowAnalysisState *CurrentState = nullptr;
+  std::vector<const TypeErasedDataflowAnalysisState *> All;
+  std::deque<TypeErasedDataflowAnalysisState> Owned;
+
+  TypeErasedDataflowAnalysisState
+  join(const TypeErasedDataflowAnalysisState &L,
+       const TypeErasedDataflowAnalysisState &R) {
+    return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
+            Environment::join(L.Env, R.Env, AC.Analysis)};
+  }
 
 public:
   JoinedStateBuilder(AnalysisContext &AC) : AC(AC) {}
 
   void addOwned(TypeErasedDataflowAnalysisState State) {
-    if (!CurrentState) {
-      OwnedState = std::move(State);
-      CurrentState = &*OwnedState;
-    } else if (!OwnedState) {
-      OwnedState.emplace(std::move(CurrentState->Lattice),
-                         CurrentState->Env.join(State.Env, AC.Analysis));
-      AC.Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
-    } else {
-      OwnedState->Env = CurrentState->Env.join(State.Env, AC.Analysis);
-      AC.Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
-    }
+    Owned.push_back(std::move(State));
+    All.push_back(&Owned.back());
   }
   void addUnowned(const TypeErasedDataflowAnalysisState &State) {
-    if (!CurrentState) {
-      CurrentState = &State;
-    } else if (!OwnedState) {
-      OwnedState.emplace(CurrentState->Lattice,
-                         CurrentState->Env.join(State.Env, AC.Analysis));
-      AC.Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
-    } else {
-      OwnedState->Env = CurrentState->Env.join(State.Env, AC.Analysis);
-      AC.Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
-    }
+    All.push_back(&State);
   }
   TypeErasedDataflowAnalysisState take() && {
-    if (!OwnedState) {
-      if (CurrentState)
-        OwnedState.emplace(CurrentState->Lattice, CurrentState->Env.fork());
-      else
-        // FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement
-        // to enable building analyses like computation of dominators that
-        // initialize the state of each basic block differently.
-        OwnedState.emplace(AC.Analysis.typeErasedInitialElement(),
-                           AC.InitEnv.fork());
-    }
-    return std::move(*OwnedState);
+    if (All.empty())
+      return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
+    if (All.size() == 1)
+      return Owned.empty() ? All.front()->fork() : std::move(Owned.front());
+
+    auto Result = join(*All[0], *All[1]);
+    for (unsigned I = 2; I < All.size(); ++I)
+      Result = join(Result, *All[I]);
+    return Result;
   }
 };
 
 } // namespace
 
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///