This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG6f22de67c585: [dataflow] Use consistent, symmetrical,
non-mutating erased signature for join() (authored by sammccall).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153908/new/
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
