sammccall created this revision.
sammccall added reviewers: ymandel, xazax.hun.
Herald added a subscriber: martong.
Herald added a reviewer: NoQ.
Herald added a project: All.
sammccall requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
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).
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D153908
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -227,50 +227,39 @@
// 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())
+ // 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;
}
};
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ 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<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;
@@ -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});
}
}
Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ 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
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ 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.
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
+++ 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<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,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
