[dataflow] avoid more accidental copies of Environment

[sammccall]

Summary

This is clunky but greatly improves debugging of flow conditions - each
copy adds more indirections in the form of flow condition tokens.

(LatticeEffect presumably once did something here, but it's now both
unused and untested.)

For the exit flow condition of:

void target(base::Optional<int*> opt) {
  if (opt.value_or(nullptr) != nullptr) {
    opt.value();
  } else {
    opt.value(); // unsafe
  }
}

Before:

(B0:1 = V15)
(B1:1 = V8)
(B2:1 = V10)
(B3:1 = (V4 & (!V7 => V6)))
(V10 = (B3:1 & !V7))
(V12 = B1:1)
(V13 = B2:1)
(V15 = (V12 | V13))
(V3 = V2)
(V4 = V3)
(V8 = (B3:1 & !!V7))
B0:1
V2

After D153491:

(B0:1 = (V9 | V10))
(B1:1 = (B3:1 & !!V6))
(B2:1 = (B3:1 & !V6))
(B3:1 = (V3 & (!V6 => V5)))
(V10 = B2:1)
(V3 = V2)
(V9 = B1:1)
B0:1
V2

After this patch, we can finally see the relations between the flow
conditions directly:

(B0:1 = (B2:1 | B1:1))
(B1:1 = (B3:1 & !!V6))
(B2:1 = (B3:1 & !V6))
(B3:1 = (V3 & (!V6 => V5)))
(V3 = V2)
B0:1
V2

(I believe V2 is the FC for the InitEnv, and V3 is introduced when
computing the input state for B3 - not sure how to eliminate it)

[sammccall]

refactor, restore comment

[sammccall]

The idea with the change to Environment::join() is that the current signature forces the base environment to be mutable, but this sometimes forces the caller to make a copy, and the implementation actually copies everything anyway...

[sammccall]

BTW i thought this was just nice for debugging and saving copying a few maps, but Dmitri says that the way even trivial indirections like (FC1 = FC2), (FC2 = ...) are expressed in the SAT solver means they can add significant cost there too...

[cor3ntin]

This seem to produce build failures when building clang-test

/home/cor3ntin/dev/compilers/LLVM/llvm-project/clang/unittests/Analysis/FlowSensitive/RecordOpsTest.cpp:50:27: error: calling a private constructor of class 'clang::dataflow::Environment'
        Environment Env = getEnvironmentAtAnnotation(Results, "p");
                          ^
/home/cor3ntin/dev/compilers/LLVM/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h:556:3: note: declared private here
  Environment(const Environment &) = default;
  ^
/home/cor3ntin/dev/compilers/LLVM/llvm-project/clang/unittests/Analysis/FlowSensitive/RecordOpsTest.cpp:112:27: error: calling a private constructor of class 'clang::dataflow::Environment'
        Environment Env = getEnvironmentAtAnnotation(Results, "p");
                          ^
/home/cor3ntin/dev/compilers/LLVM/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h:556:3: note: declared private here
  Environment(const Environment &) = default;
  ^

[sammccall]

Sorry, this was a mid-air collision with f2123af1e7d75, fixed
in 1adc5a781faa

[cor3ntin]

In D153493#4448851, @sammccall wrote:

Sorry, this was a mid-air collision with f2123af1e7d75, fixed
in 1adc5a781faa

Thanks :)

[sammccall]

Sorry, I got confused between branches and landed this one without approval

Going to review, review would still be appreciated

[sammccall]

Sorry, going to revert, review would still be appreciated

[ymandel]

Just FYI (since you mentioned it in your description): LatticeEffect is vestigial and should be removed. It's now only used (properly) for widening.

Regarding the design. This looks like an optimal solution in terms of copying but introduces lifetime risks and complexity that I'm uncomfortable with. There's a lot of flexibility here and I wonder if we can reduce that without (substantially?) impacting the amount of copying. Specifically, I wonder if we can have the builder *always* own an environment, which simplifies the handling of CurrentState and, generally, the number of cases to consider. It costs more in principle, but maybe negligible in practice?

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

603

nit: i think you can now drop the braces.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

209

Is there some invariant that guarantees the safety here? Because const & can bind to a temporary, so this feels like a risky API.

[sammccall]

Regarding the design. This looks like an optimal solution in terms of copying but introduces lifetime risks and complexity that I'm uncomfortable with.

FWIW I agree with the complexity (not the lifetime risks).
I think it ultimately stems from having too many interacting types & functions with complicated and inconsistent signatures & constraints (TypeErasedDataflowAnalysisState, Environment, TypeErasedLattice, Lattice, the various join functions, etc) so we resort to case-bashing.
However this system is difficult to make changes to, and getting consensus as to what changes are good also doesn't seem easy. So I think we need to be able to fix bugs within the existing design (where copies need to be avoided ad-hoc).

There's a lot of flexibility here and I wonder if we can reduce that without (substantially?) impacting the amount of copying. Specifically, I wonder if we can have the builder *always* own an environment, which simplifies the handling of CurrentState and, generally, the number of cases to consider. It costs more in principle, but maybe negligible in practice?

I don't understand the specific suggestion:

• if we create the builder lazily, we're just moving handling this extra state into the callsites
• if the builder owns a copy of initenv, its FC token will end up in the result FC
• if the builder owns a copy of initenv and detects when it should discard it, that just sounds like nullptr with extra steps

can you clarify?

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

209

The invariant is that an external/unowned environment will outlive the joiner, which is just a temporary helper object.

Added comments to the class & CurrentState.

const & can bind to a temporary

given that the method name is addUnowned I think "i shouldn't pass null" is more important to communicate than "I shouldn't pass a temporary", though.

[sammccall]

address comments

[ymandel]

I don't want to block the progress you're making elsewhere and I think the concerns here are sufficiently localized to revisit another time. So, feel free to reify any suggestions/disagreements in FIXMEs and submit.

In D153493#4449993, @sammccall wrote:

Regarding the design. This looks like an optimal solution in terms of copying but introduces lifetime risks and complexity that I'm uncomfortable with.

FWIW I agree with the complexity (not the lifetime risks).
I think it ultimately stems from having too many interacting types & functions with complicated and inconsistent signatures & constraints (TypeErasedDataflowAnalysisState, Environment, TypeErasedLattice, Lattice, the various join functions, etc) so we resort to case-bashing.
However this system is difficult to make changes to, and getting consensus as to what changes are good also doesn't seem easy. So I think we need to be able to fix bugs within the existing design (where copies need to be avoided ad-hoc).

I realize the complexity is frustrating, but I don't see how that's related to the issue here. The complexity of the JoinedStateBuilder is caused by the desire to minimize copies. The multiple cases come directly from the algorithm itself, most particularly that we may or may not be in an initial state, and the previous block may or may not have an environment we care about. At least, that is the specific issue I'm concerned with.

There's a lot of flexibility here and I wonder if we can reduce that without (substantially?) impacting the amount of copying. Specifically, I wonder if we can have the builder *always* own an environment, which simplifies the handling of CurrentState and, generally, the number of cases to consider. It costs more in principle, but maybe negligible in practice?

I don't understand the specific suggestion:

• if we create the builder lazily, we're just moving handling this extra state into the callsites
• if the builder owns a copy of initenv, its FC token will end up in the result FC
• if the builder owns a copy of initenv and detects when it should discard it, that just sounds like nullptr with extra steps

can you clarify?

I suppose I'm thinking along the lines of:

• if the builder owns a copy of initenv, its FC token will end up in the result FC

Can you expand on why this is a problem? That would help motivate the complexity. "join with InitEnv" should reduce to the identity function, so if its not, that feels like a problem we're sweeping under the rug.

[sammccall]

In D153493#4450191, @ymandel wrote:

I don't want to block the progress you're making elsewhere and I think the concerns here are sufficiently localized to revisit another time. So, feel free to reify any suggestions/disagreements in FIXMEs and submit.

In D153493#4449993, @sammccall wrote:

Regarding the design. This looks like an optimal solution in terms of copying but introduces lifetime risks and complexity that I'm uncomfortable with.

FWIW I agree with the complexity (not the lifetime risks).
I think it ultimately stems from having too many interacting types & functions with complicated and inconsistent signatures & constraints (TypeErasedDataflowAnalysisState, Environment, TypeErasedLattice, Lattice, the various join functions, etc) so we resort to case-bashing.
However this system is difficult to make changes to, and getting consensus as to what changes are good also doesn't seem easy. So I think we need to be able to fix bugs within the existing design (where copies need to be avoided ad-hoc).

I realize the complexity is frustrating, but I don't see how that's related to the issue here. The complexity of the JoinedStateBuilder is caused by the desire to minimize copies. The multiple cases come directly from the algorithm itself, most particularly that we may or may not be in an initial state, and the previous block may or may not have an environment we care about. At least, that is the specific issue I'm concerned with.

We have 9 state transitions (3 states x 3 operations). Each would be less than half as complicated if it didn't have to deal with Lattice's join being mutating and Environment's being non-mutating.

I believe further simplifications are possible (essentially: back at the callsite track vector<const Env*> All plus deque<Environment> Owned for owned copies, special case All.size() == 0 and All.size() == 1 and otherwise joinVec(All).
However with Lattice's mutating join involved this no longer works, and after addressing that it's no longer simpler.

There's a lot of flexibility here and I wonder if we can reduce that without (substantially?) impacting the amount of copying. Specifically, I wonder if we can have the builder *always* own an environment, which simplifies the handling of CurrentState and, generally, the number of cases to consider. It costs more in principle, but maybe negligible in practice?

I don't understand the specific suggestion:

• if we create the builder lazily, we're just moving handling this extra state into the callsites
• if the builder owns a copy of initenv, its FC token will end up in the result FC
• if the builder owns a copy of initenv and detects when it should discard it, that just sounds like nullptr with extra steps

can you clarify?

I suppose I'm thinking along the lines of:

• if the builder owns a copy of initenv, its FC token will end up in the result FC

Can you expand on why this is a problem? That would help motivate the complexity.

The purpose of this change is to stop introducing meaningless variables into the FC, because they impede debugging and slow down the SAT solver.
An extra join with a copy of InitEnv introduces up to 3 extra variables: one for InitEnv, one for the copy, one for the join.

"join with InitEnv" should reduce to the identity function, so if its not, that feels like a problem we're sweeping under the rug.

Only in a mathematical sense - in reality humans need to read these SAT systems, and we're using a solver that can't perform that reduction.

[ymandel]

In D153493#4450358, @sammccall wrote:

I realize the complexity is frustrating, but I don't see how that's related to the issue here. The complexity of the JoinedStateBuilder is caused by the desire to minimize copies. The multiple cases come directly from the algorithm itself, most particularly that we may or may not be in an initial state, and the previous block may or may not have an environment we care about. At least, that is the specific issue I'm concerned with.

We have 9 state transitions (3 states x 3 operations). Each would be less than half as complicated if it didn't have to deal with Lattice's join being mutating and Environment's being non-mutating.

I believe further simplifications are possible (essentially: back at the callsite track vector<const Env*> All plus deque<Environment> Owned for owned copies, special case All.size() == 0 and All.size() == 1 and otherwise joinVec(All).
However with Lattice's mutating join involved this no longer works, and after addressing that it's no longer simpler.

I'm pretty sure I agree on all of this, please document it somewhere (file an Issue in the github tracker?). FWIW, I think mutating join was a case of premature optimization gone bad, and ultimately the builtin lattice should not be built in at all -- it should exist outside the core and be just another client.

"join with InitEnv" should reduce to the identity function, so if its not, that feels like a problem we're sweeping under the rug.

Only in a mathematical sense - in reality humans need to read these SAT systems, and we're using a solver that can't perform that reduction.

I think we're talking past each other (and actually agreeing), sorry. To be clear, I don't mean that as a criticism of this change -- I think you've hit an important point and fixing it might make this simpler. I totally agree about SAT systems, and the solver, etc. But, I'm saying that it shouldn't come to that. I think the Environment join operation is broken if join(InitEnv, E) != E. I'm asking whether we can reduce (some) complexity by fixing that. From your earlier point, there are more problems, but I want to focus on this particular one in case solving it makes other things easier.

[sammccall]

Thanks! I'll land this to eliminate the variables, and follow up with trying to simplify join().

In D153493#4450440, @ymandel wrote:

In D153493#4450358, @sammccall wrote:

I realize the complexity is frustrating, but I don't see how that's related to the issue here. The complexity of the JoinedStateBuilder is caused by the desire to minimize copies. The multiple cases come directly from the algorithm itself, most particularly that we may or may not be in an initial state, and the previous block may or may not have an environment we care about. At least, that is the specific issue I'm concerned with.

We have 9 state transitions (3 states x 3 operations). Each would be less than half as complicated if it didn't have to deal with Lattice's join being mutating and Environment's being non-mutating.

I believe further simplifications are possible (essentially: back at the callsite track vector<const Env*> All plus deque<Environment> Owned for owned copies, special case All.size() == 0 and All.size() == 1 and otherwise joinVec(All).
However with Lattice's mutating join involved this no longer works, and after addressing that it's no longer simpler.

I'm pretty sure I agree on all of this, please document it somewhere (file an Issue in the github tracker?). FWIW, I think mutating join was a case of premature optimization gone bad

Thanks - I will file a bug if it turns out not to be trivial, but I think it probably is trivial to fix so I'll give that a shot first.

and ultimately the builtin lattice should not be built in at all -- it should exist outside the core and be just another client.

Yeah, this looks like a bigger change :-)

"join with InitEnv" should reduce to the identity function, so if its not, that feels like a problem we're sweeping under the rug.

Only in a mathematical sense - in reality humans need to read these SAT systems, and we're using a solver that can't perform that reduction.

I think we're talking past each other (and actually agreeing), sorry. To be clear, I don't mean that as a criticism of this change -- I think you've hit an important point and fixing it might make this simpler. I totally agree about SAT systems, and the solver, etc. But, I'm saying that it shouldn't come to that. I think the Environment join operation is broken if join(InitEnv, E) != E. I'm asking whether we can reduce (some) complexity by fixing that. From your earlier point, there are more problems, but I want to focus on this particular one in case solving it makes other things easier.

Ah, got it, thanks!
I think if we can change Environment (e.g. dropping FC tokens) so this just falls out, and it makes sense for other reasons, that'd be great.
I'm not a big fan of special-casing InitEnv somehow though.

[sammccall]

This relanded as 1e010c5c4fae43c52d6f5f1c8e8920c26bcc6cc7

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

public:
   /// 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`.
   ///
   /// Requirements:
   ///
   ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
-  LatticeJoinEffect join(const Environment &Other,
-                         Environment::ValueModel &Model);
-
+  Environment join(const Environment &Other,
+                   Environment::ValueModel &Model) const;
 
   /// 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/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;
 }
 
-LatticeJoinEffect Environment::join(const Environment &Other,
-                                    Environment::ValueModel &Model) {
+Environment Environment::join(const Environment &Other,
+                              Environment::ValueModel &Model) const {
   assert(DACtx == Other.DACtx);
   assert(ThisPointeeLoc == Other.ThisPointeeLoc);
   assert(CallStack == Other.CallStack);
 
-  auto Effect = LatticeJoinEffect::Unchanged;
-
   Environment JoinedEnv(*DACtx);
 
   JoinedEnv.CallStack = CallStack;
   JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
 
   if (ReturnVal == nullptr || Other.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 {
     assert(!CallStack.empty());
     // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
     // cast.
     auto *Func = dyn_cast<FunctionDecl>(CallStack.back());
     assert(Func != nullptr);
     if (Value *MergedVal =
             mergeDistinctValues(Func->getReturnType(), *ReturnVal, *this,
-                                *Other.ReturnVal, Other, JoinedEnv, Model)) {
+                                *Other.ReturnVal, Other, JoinedEnv, Model))
       JoinedEnv.ReturnVal = MergedVal;
-      Effect = LatticeJoinEffect::Changed;
-    }
   }
 
   if (ReturnLoc == Other.ReturnLoc)
     JoinedEnv.ReturnLoc = 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);
-  if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
-    Effect = LatticeJoinEffect::Changed;
 
   JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
-  if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
-    Effect = LatticeJoinEffect::Changed;
 
   JoinedEnv.MemberLocToStruct =
       intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
-  if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
-    Effect = LatticeJoinEffect::Changed;
 
-  // FIXME: set `Effect` as needed.
   // FIXME: update join to detect backedges and simplify the flow condition
   // accordingly.
   JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
       *FlowConditionToken, *Other.FlowConditionToken);
 
   for (auto &Entry : 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())
       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)) {
       JoinedEnv.LocToVal.insert({Loc, MergedVal});
-      Effect = LatticeJoinEffect::Changed;
     }
   }
-  if (LocToVal.size() != JoinedEnv.LocToVal.size())
-    Effect = LatticeJoinEffect::Changed;
-
-  *this = std::move(JoinedEnv);
 
-  return Effect;
+  return JoinedEnv;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
   return DACtx->createStorageLocation(Type);
 }
 
 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
   // Evaluated declarations are always assigned the same storage locations to

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry {
 public:
   PrettyStackTraceCFGElement(const CFGElement &Element, int BlockIdx,
                              int ElementIdx, const char *Message)
       : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
         Message(Message) {}
 
   void print(raw_ostream &OS) const override {
     OS << Message << ": Element [B" << BlockIdx << "." << ElementIdx << "]\n";
     if (auto Stmt = Element.getAs<CFGStmt>()) {
       OS << "Stmt:\n";
       ASTDumper Dumper(OS, false);
       Dumper.Visit(Stmt->getStmt());
     }
   }
 
 private:
   const CFGElement &Element;
   int BlockIdx;
   int ElementIdx;
   const char *Message;
 };
 
+// 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 &AC;
+  std::optional<TypeErasedDataflowAnalysisState> OwnedState;
+  // Points either to OwnedState, an external Environment, or nothing.
+  const TypeErasedDataflowAnalysisState *CurrentState = nullptr;
+
+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);
+    }
+  }
+  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);
+    }
+  }
+  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);
+  }
+};
+
 } // 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
if (Block.succ_begin()->getReachableBlock() != nullptr &&
         Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
       auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
       auto StmtBlock = StmtToBlock.find(Block.getTerminatorStmt());
       assert(StmtBlock != StmtToBlock.end());
       Preds.erase(StmtBlock->getSecond());
     }
   }
 
-  std::optional<TypeErasedDataflowAnalysisState> MaybeState;
-
-  auto &Analysis = AC.Analysis;
+  JoinedStateBuilder Builder(AC);
   for (const CFGBlock *Pred : Preds) {
     // Skip if the `Block` is unreachable or control flow cannot get past it.
     if (!Pred || Pred->hasNoReturnElement())
       continue;
 
     // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
     // loop back edge to `Block`.
     const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         AC.BlockStates[Pred->getBlockID()];
     if (!MaybePredState)
       continue;
 
-    TypeErasedDataflowAnalysisState PredState = MaybePredState->fork();
-    if (Analysis.builtinOptions()) {
+    if (AC.Analysis.builtinOptions()) {
       if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
+        // We have a terminator: we need to mutate an environment to describe
+        // when the terminator is taken. Copy now.
+        TypeErasedDataflowAnalysisState Copy = MaybePredState->fork();
+
         const StmtToEnvMap StmtToEnv(AC.CFCtx, AC.BlockStates);
         auto [Cond, CondValue] =
-            TerminatorVisitor(StmtToEnv, PredState.Env,
+            TerminatorVisitor(StmtToEnv, Copy.Env,
                               blockIndexInPredecessor(*Pred, Block))
                 .Visit(PredTerminatorStmt);
         if (Cond != nullptr)
           // FIXME: Call transferBranchTypeErased even if BuiltinTransferOpts
           // are not set.
-          Analysis.transferBranchTypeErased(CondValue, Cond, PredState.Lattice,
-                                            PredState.Env);
-      }
-    }
-
-    if (MaybeState) {
-      Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
-      MaybeState->Env.join(PredState.Env, Analysis);
-    } else {
-      MaybeState = std::move(PredState);
+          AC.Analysis.transferBranchTypeErased(CondValue, Cond, Copy.Lattice,
+                                               Copy.Env);
+        Builder.addOwned(std::move(Copy));
+        continue;
       }
     }
-  if (!MaybeState) {
-    // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
-    // to enable building analyses like computation of dominators that
-    // initialize the state of each basic block differently.
-    MaybeState.emplace(Analysis.typeErasedInitialElement(), AC.InitEnv.fork());
+    Builder.addUnowned(*MaybePredState);
+    continue;
   }
-  return std::move(*MaybeState);
+  return std::move(Builder).take();
 }
 
 /// Built-in transfer function for `CFGStmt`.
 static void
 builtinTransferStatement(const CFGStmt &Elt,
                          TypeErasedDataflowAnalysisState &InputState,
                          AnalysisContext &AC) {
   const Stmt *S = Elt.getStmt();