Author: Sam McCall Date: 2023-06-26T15:58:23+02:00 New Revision: ae54f01dd8c53d18c276420b23f0d0ab7afefff1
URL: https://github.com/llvm/llvm-project/commit/ae54f01dd8c53d18c276420b23f0d0ab7afefff1 DIFF: https://github.com/llvm/llvm-project/commit/ae54f01dd8c53d18c276420b23f0d0ab7afefff1.diff LOG: [dataflow] avoid more accidental copies of Environment 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) Differential Revision: https://reviews.llvm.org/D153493 Added: Modified: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index 15e63c3d91a32..8494bc197cb25 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -226,9 +226,8 @@ class Environment { /// 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. diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index b2e67651626d5..70dbe6dbb7a24 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -526,14 +526,12 @@ LatticeJoinEffect Environment::widen(const Environment &PrevEnv, 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; @@ -560,7 +558,6 @@ LatticeJoinEffect Environment::join(const Environment &Other, mergeDistinctValues(Func->getReturnType(), *ReturnVal, *this, *Other.ReturnVal, Other, JoinedEnv, Model)) { JoinedEnv.ReturnVal = MergedVal; - Effect = LatticeJoinEffect::Changed; } } @@ -574,19 +571,12 @@ LatticeJoinEffect Environment::join(const Environment &Other, // `DeclToLoc` and `Other.DeclToLoc` that map the same declaration to // diff erent 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( @@ -613,15 +603,10 @@ LatticeJoinEffect Environment::join(const Environment &Other, 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) { diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 1f23b6cf238f7..2d49dc6f44fd4 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -221,6 +221,57 @@ class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry { const char *Message; }; +// Builds a joined TypeErasedDataflowAnalysisState from 0 or more sources, +// each of which may be an owned copy or an immutable reference. +// Avoids unneccesary copies of the environment. +class JoinedStateBuilder { + AnalysisContext &AC; + std::optional<TypeErasedDataflowAnalysisState> OwnedState; + 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 diff erently. + 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 @@ -267,9 +318,7 @@ computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) { } } - 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()) @@ -282,36 +331,30 @@ computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) { 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); + AC.Analysis.transferBranchTypeErased(CondValue, Cond, Copy.Lattice, + Copy.Env); + Builder.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 diff erently. - 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`. _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
