diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -61,6 +61,7 @@ /// 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. /// @@ -98,11 +99,13 @@ return {static_cast(this)->initialElement()}; } - LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, + TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final { - Lattice &L1 = llvm::any_cast(E1.Value); + // FIXME: change the signature of join() to avoid copying here. + Lattice L1 = llvm::any_cast(E1.Value); const Lattice &L2 = llvm::any_cast(E2.Value); - return L1.join(L2); + L1.join(L2); + return {std::move(L1)}; } LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -218,16 +218,15 @@ 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. diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -72,7 +72,7 @@ /// 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 diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -526,18 +526,18 @@ 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()`. @@ -546,22 +546,22 @@ // 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(CallStack.back()); + auto *Func = dyn_cast(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; @@ -569,27 +569,27 @@ // 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); @@ -598,9 +598,8 @@ 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}); } } diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -227,50 +227,39 @@ // Avoids unneccesary copies of the environment. class JoinedStateBuilder { AnalysisContext &AC; - std::optional OwnedState; - // Points either to OwnedState, an external Environment, or nothing. - const TypeErasedDataflowAnalysisState *CurrentState = nullptr; + std::vector All; + std::deque 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()) + // FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement + // to enable building analyses like computation of dominators that + // initialize the state of each basic block differently. + 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; } };