sammccall created this revision.
Herald added subscribers: martong, xazax.hun.
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.
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 <https://reviews.llvm.org/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 <https://reviews.llvm.org/B3> - not sure how
to eliminate it)
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D153493
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.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
@@ -225,9 +225,45 @@
}
}
- std::optional<TypeErasedDataflowAnalysisState> MaybeState;
+ std::optional<TypeErasedDataflowAnalysisState> OwnedState;
+ const TypeErasedDataflowAnalysisState *CurrentState = nullptr;
auto &Analysis = AC.Analysis;
+ auto 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, Analysis));
+ Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
+ } else {
+ OwnedState->Env = CurrentState->Env.join(State.Env, Analysis);
+ Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
+ }
+ };
+ auto AddUnowned = [&](const TypeErasedDataflowAnalysisState &State) {
+ if (!CurrentState) {
+ CurrentState = &State;
+ } else if (!OwnedState) {
+ OwnedState.emplace(CurrentState->Lattice,
+ CurrentState->Env.join(State.Env, Analysis));
+ Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
+ } else {
+ OwnedState->Env = CurrentState->Env.join(State.Env, Analysis);
+ Analysis.joinTypeErased(OwnedState->Lattice, State.Lattice);
+ }
+ };
+ auto Finish = [&] {
+ if (!OwnedState) {
+ if (CurrentState)
+ OwnedState = *CurrentState;
+ else
+ OwnedState.emplace(Analysis.typeErasedInitialElement(), AC.InitEnv);
+ }
+ return std::move(*OwnedState);
+ };
+
for (const CFGBlock *Pred : Preds) {
// Skip if the `Block` is unreachable or control flow cannot get past it.
if (!Pred || Pred->hasNoReturnElement())
@@ -240,36 +276,30 @@
if (!MaybePredState)
continue;
- TypeErasedDataflowAnalysisState PredState = *MaybePredState;
if (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;
+
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);
+ Analysis.transferBranchTypeErased(CondValue, Cond, Copy.Lattice,
+ Copy.Env);
+ AddOwned(std::move(Copy));
+ continue;
}
}
-
- if (MaybeState) {
- Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
- MaybeState->Env.join(PredState.Env, Analysis);
- } else {
- MaybeState = std::move(PredState);
- }
- }
- 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);
+ AddUnowned(*MaybePredState);
+ continue;
}
- return std::move(*MaybeState);
+ return Finish();
}
/// Built-in transfer function for `CFGStmt`.
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -535,14 +535,12 @@
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;
@@ -569,7 +567,6 @@
mergeDistinctValues(Func->getReturnType(), *ReturnVal, *this,
*Other.ReturnVal, Other, JoinedEnv, Model)) {
JoinedEnv.ReturnVal = MergedVal;
- Effect = LatticeJoinEffect::Changed;
}
}
@@ -583,19 +580,12 @@
// `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(
@@ -622,15 +612,10 @@
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) {
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -216,9 +216,8 @@
/// 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.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
