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