llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: Donát Nagy (NagyDonat) <details> <summary>Changes</summary> Previously the class `ExplodedGraph` had a data member called `Roots` which could (in theory) store multiple root nodes -- but in practice exploded graphs always had at most one root node (zero was possible for empty and partially copied graphs) and introducing a graph with multiple roots would've caused severe malfuncitons (e.g. in code that used the pattern `*roots_begin()` to refer to _the_ root node. I don't see any practical usecase for adding multiple root nodes in a single graph (this seems to be yet another of the "generalize for the sake of generalization" decisions which were common in the early history of the analyzer), so this commit replaces the vector `Roots` with `ExplodedNode *Root` (which may be null when the graph is empty or construction). Note that the overcomplicated logic of `ExplodedGraph::trim` deserves a through cleanup, but I left that for a follow-up commit. --- Full diff: https://github.com/llvm/llvm-project/pull/139903.diff 7 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h (+20-35) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h (+2-2) - (modified) clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp (+3-2) - (modified) clang/lib/StaticAnalyzer/Core/BugReporter.cpp (+4-3) - (modified) clang/lib/StaticAnalyzer/Core/CoreEngine.cpp (+6-9) - (modified) clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp (+15-6) - (modified) clang/lib/StaticAnalyzer/Core/ExprEngine.cpp (+1-1) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 3754e25501635..e995151927c96 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -307,11 +307,9 @@ class ExplodedGraph { // Type definitions. using NodeVector = std::vector<ExplodedNode *>; - /// The roots of the simulation graph. Usually there will be only - /// one, but clients are free to establish multiple subgraphs within a single - /// SimulGraph. Moreover, these subgraphs can often merge when paths from - /// different roots reach the same state at the same program location. - NodeVector Roots; + /// The root of the simulation graph. Can be nullptr if the graph is empty or + /// if it was populated by `createUncachedNode()`. + ExplodedNode *Root = nullptr; /// The nodes in the simulation graph which have been /// specially marked as the endpoint of an abstract simulation path. @@ -345,31 +343,31 @@ class ExplodedGraph { ExplodedGraph(); ~ExplodedGraph(); - /// Retrieve the node associated with a (Location,State) pair, - /// where the 'Location' is a ProgramPoint in the CFG. If no node for - /// this pair exists, it is created. IsNew is set to true if - /// the node was freshly created. + /// Get the root node of the graph. This may return nullptr if the graph is + /// empty or under construction. + ExplodedNode *getRoot() const { return Root; } + + /// Retrieve the node associated with a (Location, State) pair, where the + /// 'Location' is a ProgramPoint in the CFG. If no node for this pair exists, + /// it is created. IsNew is set to true if the node was freshly created. ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink = false, bool* IsNew = nullptr); - /// Create a node for a (Location, State) pair, - /// but don't store it for deduplication later. This - /// is useful when copying an already completed - /// ExplodedGraph for further processing. + /// Create a node for a (Location, State) pair, but don't store it for + /// deduplication later. This is useful when copying some nodes from an + /// already completed ExplodedGraph for further processing. ExplodedNode *createUncachedNode(const ProgramPoint &L, ProgramStateRef State, int64_t Id, bool IsSink = false); - std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const { - return std::make_unique<ExplodedGraph>(); - } - - /// addRoot - Add an untyped node to the set of roots. - ExplodedNode *addRoot(ExplodedNode *V) { - Roots.push_back(V); - return V; + /// Mark a node as the root of the graph. Calling this is an error if the + /// graph already has a root node. + void designateAsRoot(ExplodedNode *V) { + assert(V && "Cannot designate nullptr as root!"); + assert(!Root && "The graph already has a root, cannot designate another!"); + Root = V; } /// addEndOfPath - Add an untyped node to the set of EOP nodes. @@ -378,7 +376,6 @@ class ExplodedGraph { return V; } - unsigned num_roots() const { return Roots.size(); } unsigned num_eops() const { return EndNodes.size(); } bool empty() const { return NumNodes == 0; } @@ -389,8 +386,6 @@ class ExplodedGraph { // Iterators. using NodeTy = ExplodedNode; using AllNodesTy = llvm::FoldingSet<ExplodedNode>; - using roots_iterator = NodeVector::iterator; - using const_roots_iterator = NodeVector::const_iterator; using eop_iterator = NodeVector::iterator; using const_eop_iterator = NodeVector::const_iterator; using node_iterator = AllNodesTy::iterator; @@ -400,14 +395,6 @@ class ExplodedGraph { llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; } - roots_iterator roots_begin() { return Roots.begin(); } - - roots_iterator roots_end() { return Roots.end(); } - - const_roots_iterator roots_begin() const { return Roots.begin(); } - - const_roots_iterator roots_end() const { return Roots.end(); } - eop_iterator eop_begin() { return EndNodes.begin(); } eop_iterator eop_end() { return EndNodes.end(); } @@ -508,9 +495,7 @@ namespace llvm { using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; using nodes_iterator = llvm::df_iterator<GraphTy>; - static NodeRef getEntryNode(const GraphTy G) { - return *G->roots_begin(); - } + static NodeRef getEntryNode(const GraphTy G) { return G->getRoot(); } static bool predecessorOfTrivial(NodeRef N) { return N->succ_size() == 1 && N->getFirstSucc()->isTrivial(); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 285194148d3d3..b8a4dcbc727a6 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -222,8 +222,8 @@ class ExprEngine { const Stmt *getStmt() const; const LocationContext *getRootLocationContext() const { - assert(G.roots_begin() != G.roots_end()); - return (*G.roots_begin())->getLocation().getLocationContext(); + assert(G.getRoot()); + return G.getRoot()->getLocation().getLocationContext(); } ConstCFGElementRef getCFGElementRef() const { diff --git a/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp index d030e69a2a6e0..23fad31b29a80 100644 --- a/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/AnalyzerStatsChecker.cpp @@ -46,8 +46,9 @@ void AnalyzerStatsChecker::checkEndAnalysis(ExplodedGraph &G, llvm::SmallPtrSet<const CFGBlock*, 32> reachable; // Root node should have the location context of the top most function. - const ExplodedNode *GraphRoot = *G.roots_begin(); - const LocationContext *LC = GraphRoot->getLocation().getLocationContext(); + // FIXME: Use `Eng.getRootLocationContext()` unless `G` can be different from + // the `ExplodedGraph` owned by Eng. + const LocationContext *LC = G.getRoot()->getLocation().getLocationContext(); const Decl *D = LC->getDecl(); diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp index 28b96f2717210..d5bc3ac2962d5 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -2660,8 +2660,7 @@ BugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph, // Perform a forward BFS to find all the shortest paths. std::queue<const ExplodedNode *> WS; - assert(TrimmedGraph->num_roots() == 1); - WS.push(*TrimmedGraph->roots_begin()); + WS.push(TrimmedGraph->getRoot()); unsigned Priority = 0; while (!WS.empty()) { @@ -2722,7 +2721,9 @@ BugPathInfo *BugPathGetter::getNextBugPath() { // Are we at the final node? if (OrigN->pred_empty()) { - GNew->addRoot(NewN); + assert(OrigN == TrimmedGraph->getRoot() && + "There should be only one root!"); + GNew->designateAsRoot(NewN); break; } diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 8ba304b3af0ca..2e6631f2f620c 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -87,8 +87,9 @@ void CoreEngine::setBlockCounter(BlockCounter C) { /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps, ProgramStateRef InitState) { - if (G.num_roots() == 0) { // Initialize the analysis by constructing - // the root if none exists. + if (G.empty()) { + assert(!G.getRoot() && "empty graph must not have a root node"); + // Initialize the analysis by constructing the root if there are no nodes. const CFGBlock *Entry = &(L->getCFG()->getEntry()); @@ -117,7 +118,7 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps, bool IsNew; ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew); assert(IsNew); - G.addRoot(Node); + G.designateAsRoot(Node); NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node); ExplodedNodeSet DstBegin; @@ -548,15 +549,11 @@ void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, void CoreEngine::generateNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *Pred) { + assert(Pred); bool IsNew; ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew); - if (Pred) - Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. - else { - assert(IsNew); - G.addRoot(Node); // 'Node' has no predecessor. Make it a root. - } + Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor. // Only add 'Node' to the worklist if it was freshly generated. if (IsNew) WList->enqueue(Node); diff --git a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index 7b2cccce93cfe..098922d94061f 100644 --- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -442,6 +442,10 @@ std::unique_ptr<ExplodedGraph> ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, InterExplodedGraphMap *ForwardMap, InterExplodedGraphMap *InverseMap) const { + // FIXME: The two-pass algorithm of this function (which was introduced in + // 2008) is terribly overcomplicated and should be replaced by a single + // (backward) pass. + if (Nodes.empty()) return nullptr; @@ -467,8 +471,9 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, if (!Pass1.insert(N).second) continue; - // If this is a root enqueue it to the second worklist. + // If this is the root enqueue it to the second worklist. if (N->Preds.empty()) { + assert(N == getRoot() && "Found non-root node with no predecessors!"); WL2.push_back(N); continue; } @@ -477,12 +482,14 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, WL1.append(N->Preds.begin(), N->Preds.end()); } - // We didn't hit a root? Return with a null pointer for the new graph. + // We didn't hit the root? Return with a null pointer for the new graph. if (WL2.empty()) return nullptr; + assert(WL2.size() == 1 && "There must be only one root!"); + // Create an empty graph. - std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph(); + std::unique_ptr<ExplodedGraph> G = std::make_unique<ExplodedGraph>(); // ===- Pass 2 (forward DFS to construct the new graph) -=== while (!WL2.empty()) { @@ -503,9 +510,11 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, // Also record the reverse mapping from the new node to the old node. if (InverseMap) (*InverseMap)[NewN] = N; - // If this node is a root, designate it as such in the graph. - if (N->Preds.empty()) - G->addRoot(NewN); + // If this node is the root, designate it as such in the graph. + if (N->Preds.empty()) { + assert(N == getRoot()); + G->designateAsRoot(NewN); + } // In the case that some of the intended predecessors of NewN have already // been created, we should hook them up as predecessors. diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index f71441a3bb49b..ebad83dad0c8f 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2529,7 +2529,7 @@ static const LocationContext *getInlinedLocationContext(ExplodedNode *Node, ExplodedGraph &G) { const LocationContext *CalleeLC = Node->getLocation().getLocationContext(); const LocationContext *RootLC = - (*G.roots_begin())->getLocation().getLocationContext(); + G.getRoot()->getLocation().getLocationContext(); if (CalleeLC->getStackFrame() == RootLC->getStackFrame()) return nullptr; `````````` </details> https://github.com/llvm/llvm-project/pull/139903 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
