=?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]>, =?utf-8?q?Donát?= Nagy <[email protected]> Message-ID: In-Reply-To: <llvm.org/llvm/llvm-project/pull/[email protected]>
llvmorg-github-actions[bot] wrote: <!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-static-analyzer-1 Author: Donát Nagy (NagyDonat) <details> <summary>Changes</summary> This change concludes the removal of the class `NodeBuilder` which previously added lots of unnecessary complications to the logic of the analyzer engine. The main "feature" of a `NodeBuilder` was that it tracked a "frontier" set of exploded nodes, which were freshly created and not yet superseded by the creation of another node. This was contraproductive in almost all code that used `NodeBuilder`s -- with the exception of `CheckerContext` where this was useful to support arbitrary chains of `addTransition` calls in checkers. As earlier commits removed the contraproductive use of `NodeBuilder`s, there was only one surviving `NodeBuilder`, a data member of `CheckerContext`, and its `generateNode` method was called only once, so this commit inlines still relevant fragments of `NodeBuilder` into `CheckerContext` and removes `NodeBuilder` as a separate class. This change also applies trivial code quality improvements (e.g. fixing typos) in the surrounding code. The class `NodeBuilderContext` will be removed soon by a follow-up commit. --- Patch is 21.35 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/217319.diff 5 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h (+19-19) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h (-92) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h (+1) - (modified) clang/lib/StaticAnalyzer/Core/CheckerManager.cpp (+58-51) - (modified) clang/lib/StaticAnalyzer/Core/CoreEngine.cpp (-11) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h index 18e55862bc855..38bcd55354a63 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h @@ -31,27 +31,26 @@ class CheckerContext { bool Changed; /// The tagged location, which is used to generate all new nodes. const ProgramPoint Location; - NodeBuilder &NB; + /// At the end of the checker evaluation, the analysis will continue from the + /// nodes in this set. When the checker adds a transition, freshly created + /// non-sink nodes are added to the `Frontier` and the node that was the + /// source of the transition is unconditionally removed from the `Frontier` + /// (it is superseded, even if the node creation fails or produces a sink). + /// At the beginning, the `Frontier` usually contains `Pred`. + ExplodedNodeSet &Frontier; public: /// If we are post visiting a call, this flag will be set if the /// call was inlined. In all other cases it will be false. const bool wasInlined; - CheckerContext(NodeBuilder &builder, - ExprEngine &eng, - ExplodedNode *pred, - const ProgramPoint &loc, - bool wasInlined = false) - : Eng(eng), - Pred(pred), - Changed(false), - Location(loc), - NB(builder), - wasInlined(wasInlined) { + CheckerContext(ExprEngine &Eng, ExplodedNode *Pred, ExplodedNodeSet &Dst, + const ProgramPoint &Loc, bool WasInlined = false) + : Eng(Eng), Pred(Pred), Changed(false), Location(Loc), Frontier(Dst), + wasInlined(WasInlined) { assert(Pred->getState() && "We should not call the checkers on an empty state."); - assert(loc.getTag() && "The ProgramPoint associated with CheckerContext " + assert(Loc.getTag() && "The ProgramPoint associated with CheckerContext " "must be tagged with the active checker."); } @@ -454,12 +453,13 @@ class CheckerContext { if (!P) P = Pred; - ExplodedNode *node; - if (MarkAsSink) - node = NB.generateSink(LocalLoc, State, P); - else - node = NB.generateNode(LocalLoc, State, P); - return node; + Frontier.erase(P); + ExplodedNode *N = + Eng.getCoreEngine().makeNode(LocalLoc, State, P, MarkAsSink); + + Frontier.insert(N); + + return N; } }; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 2a7264009b076..71443e4434462 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -49,7 +49,6 @@ class ExprEngine; /// It traverses the CFG and generates the ExplodedGraph. class CoreEngine { friend class ExprEngine; - friend class NodeBuilder; friend class NodeBuilderContext; public: @@ -242,97 +241,6 @@ class NodeBuilderContext { } }; -/// \class NodeBuilder -/// This is the simplest builder which generates nodes in the -/// ExplodedGraph. -/// -/// The main benefit of the builder is that it automatically tracks the -/// frontier nodes (or destination set). This is the set of nodes which should -/// be propagated to the next step / builder. They are the nodes which have been -/// added to the builder (either as the input node set or as the newly -/// constructed nodes) but did not have any outgoing transitions added. -/// -/// TODO: This "main benefit" is often useless, in fact the only significant -/// use is within `CheckerManager::ExpandGraphWithCheckers`. There this logic -/// ensures that if a checker performs multiple transitions on the same path, -/// then only the last of them is "built upon" by other checkers or the engine. -/// -/// However, there are also many short-lived temporary `NodeBuilder` instances -/// where the `generateNode` is called in a very predictable manner (once, or -/// once for each source node) and the frontier management is overkill. -/// These locations should be gradually simplified by using the method -/// `CoreEngine::makeNode()` instead of the temporary `NodeBuilder`s. -class NodeBuilder { -protected: - const NodeBuilderContext &C; - - /// The frontier set - a set of nodes which need to be propagated after - /// the builder dies. - ExplodedNodeSet &Frontier; - -public: - NodeBuilder(ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx) - : C(Ctx), Frontier(DstSet) {} - - NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, - const NodeBuilderContext &Ctx) - : NodeBuilder(DstSet, Ctx) { - Frontier.insert(SrcNode); - } - - NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, - const NodeBuilderContext &Ctx) - : NodeBuilder(DstSet, Ctx) { - Frontier.insert(SrcSet); - } - - /// Generates a node in the ExplodedGraph. - ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, - ExplodedNode *Pred, bool MarkAsSink = false); - - /// Generates a sink in the ExplodedGraph. - /// - /// When a node is marked as sink, the exploration from the node is stopped - - /// the node becomes the last node on the path and certain kinds of bugs are - /// suppressed. - ExplodedNode *generateSink(const ProgramPoint &PP, - ProgramStateRef State, - ExplodedNode *Pred) { - return generateNode(PP, State, Pred, true); - } - - ExplodedNode *generateNode(const Stmt *S, - ExplodedNode *Pred, - ProgramStateRef St, - const ProgramPointTag *tag = nullptr, - ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ - const ProgramPoint &L = - ProgramPoint::getProgramPoint(S, K, Pred->getStackFrame(), tag); - return generateNode(L, St, Pred); - } - - ExplodedNode *generateSink(const Stmt *S, - ExplodedNode *Pred, - ProgramStateRef St, - const ProgramPointTag *tag = nullptr, - ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ - const ProgramPoint &L = - ProgramPoint::getProgramPoint(S, K, Pred->getStackFrame(), tag); - return generateSink(L, St, Pred); - } - - const ExplodedNodeSet &getResults() const { return Frontier; } - - void takeNodes(const ExplodedNodeSet &S) { - for (const auto I : S) - Frontier.erase(I); - } - - void takeNodes(ExplodedNode *N) { Frontier.erase(N); } - void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } - void addNodes(ExplodedNode *N) { Frontier.insert(N); } -}; - } // namespace ento } // namespace clang diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 68d4362aca941..d0b667ccf9f99 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -505,6 +505,7 @@ class ExprEngine { bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); } bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); } + CoreEngine &getCoreEngine() { return Engine; } const CoreEngine &getCoreEngine() const { return Engine; } public: diff --git a/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp b/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp index 4db6b6ecaa9f7..67fa62709891c 100644 --- a/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp @@ -94,10 +94,8 @@ void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr, //===----------------------------------------------------------------------===// template <typename CHECK_CTX> -static void expandGraphWithCheckers(CHECK_CTX checkCtx, - ExplodedNodeSet &Dst, +static void expandGraphWithCheckers(CHECK_CTX checkCtx, ExplodedNodeSet &Dst, const ExplodedNodeSet &Src) { - const NodeBuilderContext &BldrCtx = checkCtx.Eng.getBuilderContext(); if (Src.empty()) return; @@ -120,9 +118,9 @@ static void expandGraphWithCheckers(CHECK_CTX checkCtx, CurrSet->clear(); } - NodeBuilder B(*PrevSet, *CurrSet, BldrCtx); + CurrSet->insert(*PrevSet); for (const auto &NI : *PrevSet) - checkCtx.runChecker(*I, B, NI); + checkCtx.runChecker(*I, NI, *CurrSet); // If all the produced transitions are sinks, stop. if (CurrSet->empty()) @@ -159,15 +157,15 @@ std::string checkerScopeName(StringRef Name, const CheckerBackend *Checker) { CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } CheckersTy::const_iterator checkers_end() { return Checkers.end(); } - void runChecker(CheckerManager::CheckStmtFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + void runChecker(CheckerManager::CheckStmtFunc checkFn, ExplodedNode *Pred, + ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope(checkerScopeName("Stmt", checkFn.Checker)); // FIXME: Remove respondsToCallback from CheckerContext; ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind : ProgramPoint::PostStmtKind; const ProgramPoint &L = ProgramPoint::getProgramPoint( S, K, Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L, WasInlined); + CheckerContext C(Eng, Pred, Dst, L, WasInlined); checkFn(S, C); } }; @@ -211,7 +209,7 @@ namespace { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckObjCMessageFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope( checkerScopeName("ObjCMsg", checkFn.Checker)); bool IsPreVisit; @@ -227,7 +225,7 @@ namespace { } const ProgramPoint &L = Msg.getProgramPoint(IsPreVisit,checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L, WasInlined); + CheckerContext C(Eng, Pred, Dst, L, WasInlined); checkFn(*Msg.cloneWithState<ObjCMethodCall>(Pred->getState()), C); } @@ -283,11 +281,11 @@ namespace { CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } CheckersTy::const_iterator checkers_end() { return Checkers.end(); } - void runChecker(CheckerManager::CheckCallFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + void runChecker(CheckerManager::CheckCallFunc checkFn, ExplodedNode *Pred, + ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope(checkerScopeName("Call", checkFn.Checker)); const ProgramPoint &L = Call.getProgramPoint(IsPreVisit,checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L, WasInlined); + CheckerContext C(Eng, Pred, Dst, L, WasInlined); checkFn(*Call.cloneWithState(Pred->getState()), C); } @@ -329,10 +327,10 @@ struct CheckLifetimeEndContext { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckLifetimeEndFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { assert(Pred->getLocation().getAs<LifetimeEnd>().has_value()); const ProgramPoint L = Pred->getLocation().withTag(checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); checkFn(Decl, C); } }; @@ -372,13 +370,13 @@ namespace { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckLocationFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope(checkerScopeName("Loc", checkFn.Checker)); ProgramPoint::Kind K = IsLoad ? ProgramPoint::PreLoadKind : ProgramPoint::PreStoreKind; const ProgramPoint &L = ProgramPoint::getProgramPoint( NodeEx, K, Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); checkFn(Loc, IsLoad, BoundEx, C); } }; @@ -423,11 +421,11 @@ namespace { CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } CheckersTy::const_iterator checkers_end() { return Checkers.end(); } - void runChecker(CheckerManager::CheckBindFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + void runChecker(CheckerManager::CheckBindFunc checkFn, ExplodedNode *Pred, + ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope(checkerScopeName("Bind", checkFn.Checker)); const ProgramPoint &L = PP.withTag(checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); checkFn(Loc, Val, S, AtDeclInit, C); } @@ -472,11 +470,11 @@ struct CheckBlockEntranceContext { auto checkers_begin() const { return Checkers.begin(); } auto checkers_end() const { return Checkers.end(); } - void runChecker(CheckBlockEntranceFunc CheckFn, NodeBuilder &Bldr, - ExplodedNode *Pred) { + void runChecker(CheckBlockEntranceFunc CheckFn, ExplodedNode *Pred, + ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope( checkerScopeName("BlockEntrance", CheckFn.Checker)); - CheckerContext C(Bldr, Eng, Pred, Entrance.withTag(CheckFn.Checker)); + CheckerContext C(Eng, Pred, Dst, Entrance.withTag(CheckFn.Checker)); CheckFn(Entrance, C); } }; @@ -516,10 +514,10 @@ struct CheckBeginFunctionContext { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckBeginFunctionFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope(checkerScopeName("Begin", checkFn.Checker)); const ProgramPoint &L = PP.withTag(checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); checkFn(C); } @@ -538,21 +536,35 @@ void CheckerManager::runCheckersForBeginFunction(ExplodedNodeSet &Dst, expandGraphWithCheckers(C, Dst, Src); } -/// Run checkers for end of path. -// Note, We do not chain the checker output (like in expandGraphWithCheckers) -// for this callback since end of path nodes are expected to be final. +/// Run checkers for end of a function (either the entrypoint or another +/// function that was inlined). Note that this function places the +/// checker activations on separate execution paths: +/// /-[checker1]-> N1 ... +/// Pred --[checker2]-> N2 ... +/// \-[checker3]-> N3 ... +/// (If none of the checkers produce a transition, we continue with 'Pred'.) +/// +/// This differs from the handling of all the other checker callbacks, where +/// the checker activations are chained sequentially on a single path: +/// Pred --[checker1]-> N1 --[checker2]-> N2 --[checker3]-> N3 ... +/// +/// This difference has historical reasons: originally this callback was called +/// 'EndPath' and only activated at the end of an execution paths, and +/// (according to an old comment) those 'EndPath' checkers expected that they +/// create an "end of path" node which will be final. +/// TODO: Check whether this exceptional behavior is still justified. void CheckerManager::runCheckersForEndFunction(ExplodedNodeSet &Dst, ExplodedNode *Pred, ExprEngine &Eng, const ReturnStmt *RS) { - // We define the builder outside of the loop because if at least one checker - // creates a successor for Pred, we do not need to generate an - // autotransition for it. - NodeBuilder Bldr(Pred, Dst, Eng.getBuilderContext()); + // By default, continue from 'Pred' -- this will be removed from 'Dst' if any + // checker generates a transition from it. + Dst.insert(Pred); + for (const auto &checkFn : EndFunctionCheckers) { const ProgramPoint &L = FunctionExitPoint(RS, Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); llvm::TimeTraceScope TimeScope(checkerScopeName("End", checkFn.Checker)); checkFn(RS, C); } @@ -575,12 +587,12 @@ namespace { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckBranchConditionFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope( checkerScopeName("BranchCond", checkFn.Checker)); ProgramPoint L = PostCondition(Condition, Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + CheckerContext C(Eng, Pred, Dst, L); checkFn(Condition, C); } }; @@ -619,12 +631,12 @@ namespace { CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckNewAllocatorFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope( checkerScopeName("Allocator", checkFn.Checker)); ProgramPoint L = PostAllocatorCall( Call.getOriginExpr(), Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L, WasInlined); + CheckerContext C(Eng, Pred, Dst, L, WasInlined); checkFn(cast<CXXAllocatorCall>(*Call.cloneWithState(Pred->getState())), C); } @@ -660,23 +672,23 @@ namespace { SymbolReaper &SR; const Stmt *S; ExprEngine &Eng; - ProgramPoint::Kind ProgarmPointKind; + ProgramPoint::Kind ProgramPointKind; CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr, const Stmt *s, ExprEngine &eng, ProgramPoint::Kind K) - : Checkers(checkers), SR(sr), S(s), Eng(eng), ProgarmPointKind(K) {} + : Checkers(checkers), SR(sr), S(s), Eng(eng), ProgramPointKind(K) {} CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } CheckersTy::const_iterator checkers_end() { return Checkers.end(); } void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn, - NodeBuilder &Bldr, ExplodedNode *Pred) { + ExplodedNode *Pred, ExplodedNodeSet &Dst) { llvm::TimeTraceScope TimeScope( checkerScopeName("DeadSymbols", checkFn.Checker)); const ProgramPoint &L = ProgramPoint::getProgramPoint( - S, ProgarmPointKind, Pred->getStackFrame(), checkFn.Checker); - CheckerContext C(Bldr, Eng, Pred, L); + S, ProgramPointKind, Pred->getStackFrame(), checkFn.Checker); + CheckerContext C(Eng, Pred, Dst, L); // Note, do not pass the statement to the checkers without letting them // differentiate if we ran remove dead bindings before or after the @@ -761,8 +773,7 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, for (auto *const Pred : Src) { std::optional<StringRef> evaluatorChecker; - ExplodedNodeSet checkDst; - NodeBuilder B(Pred, checkDst, Eng.getBuilderContext()); + ExplodedNodeSet checkDst{Pred}; ProgramStateRef State = Pred->getState(); CallEventRef<> UpdatedCall = Call.cloneWithState(State); @@ -774,13 +785,9 @@ void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, ProgramPoint L = ProgramPoint::getProgramPoint( UpdatedCall->getO... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/217319 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
