10b57cec5SDimitry Andric //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file defines the template classes ExplodedNode and ExplodedGraph, 100b57cec5SDimitry Andric // which represent a path-sensitive, intra-procedural "exploded graph." 110b57cec5SDimitry Andric // See "Precise interprocedural dataflow analysis via graph reachability" 120b57cec5SDimitry Andric // by Reps, Horwitz, and Sagiv 130b57cec5SDimitry Andric // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 140b57cec5SDimitry Andric // exploded graph. 150b57cec5SDimitry Andric // 160b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 190b57cec5SDimitry Andric #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 200b57cec5SDimitry Andric 210b57cec5SDimitry Andric #include "clang/Analysis/AnalysisDeclContext.h" 220b57cec5SDimitry Andric #include "clang/Analysis/ProgramPoint.h" 230b57cec5SDimitry Andric #include "clang/Analysis/Support/BumpVector.h" 240b57cec5SDimitry Andric #include "clang/Basic/LLVM.h" 250b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 260b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 270b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 280b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h" 290b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 300b57cec5SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h" 310b57cec5SDimitry Andric #include "llvm/ADT/FoldingSet.h" 320b57cec5SDimitry Andric #include "llvm/ADT/GraphTraits.h" 330b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h" 340b57cec5SDimitry Andric #include "llvm/ADT/SetVector.h" 3506c3fb27SDimitry Andric #include "llvm/ADT/iterator_range.h" 360b57cec5SDimitry Andric #include "llvm/Support/Allocator.h" 370b57cec5SDimitry Andric #include "llvm/Support/Compiler.h" 380b57cec5SDimitry Andric #include <cassert> 390b57cec5SDimitry Andric #include <cstdint> 400b57cec5SDimitry Andric #include <memory> 41bdd1243dSDimitry Andric #include <optional> 420b57cec5SDimitry Andric #include <utility> 430b57cec5SDimitry Andric #include <vector> 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric namespace clang { 460b57cec5SDimitry Andric 470b57cec5SDimitry Andric class CFG; 480b57cec5SDimitry Andric class Decl; 490b57cec5SDimitry Andric class Expr; 500b57cec5SDimitry Andric class ParentMap; 510b57cec5SDimitry Andric class Stmt; 520b57cec5SDimitry Andric 530b57cec5SDimitry Andric namespace ento { 540b57cec5SDimitry Andric 550b57cec5SDimitry Andric class ExplodedGraph; 560b57cec5SDimitry Andric 570b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 580b57cec5SDimitry Andric // ExplodedGraph "implementation" classes. These classes are not typed to 590b57cec5SDimitry Andric // contain a specific kind of state. Typed-specialized versions are defined 600b57cec5SDimitry Andric // on top of these classes. 610b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 620b57cec5SDimitry Andric 630b57cec5SDimitry Andric // ExplodedNode is not constified all over the engine because we need to add 640b57cec5SDimitry Andric // successors to it at any time after creating it. 650b57cec5SDimitry Andric 660b57cec5SDimitry Andric class ExplodedNode : public llvm::FoldingSetNode { 670b57cec5SDimitry Andric friend class BranchNodeBuilder; 680b57cec5SDimitry Andric friend class CoreEngine; 690b57cec5SDimitry Andric friend class EndOfFunctionNodeBuilder; 700b57cec5SDimitry Andric friend class ExplodedGraph; 710b57cec5SDimitry Andric friend class IndirectGotoNodeBuilder; 720b57cec5SDimitry Andric friend class NodeBuilder; 730b57cec5SDimitry Andric friend class SwitchNodeBuilder; 740b57cec5SDimitry Andric 750b57cec5SDimitry Andric /// Efficiently stores a list of ExplodedNodes, or an optional flag. 760b57cec5SDimitry Andric /// 770b57cec5SDimitry Andric /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 780b57cec5SDimitry Andric /// for the case when there is only one node in the group. This is a fairly 790b57cec5SDimitry Andric /// common case in an ExplodedGraph, where most nodes have only one 800b57cec5SDimitry Andric /// predecessor and many have only one successor. It can also be used to 810b57cec5SDimitry Andric /// store a flag rather than a node list, which ExplodedNode uses to mark 820b57cec5SDimitry Andric /// whether a node is a sink. If the flag is set, the group is implicitly 830b57cec5SDimitry Andric /// empty and no nodes may be added. 840b57cec5SDimitry Andric class NodeGroup { 850b57cec5SDimitry Andric // Conceptually a discriminated union. If the low bit is set, the node is 860b57cec5SDimitry Andric // a sink. If the low bit is not set, the pointer refers to the storage 870b57cec5SDimitry Andric // for the nodes in the group. 880b57cec5SDimitry Andric // This is not a PointerIntPair in order to keep the storage type opaque. 890b57cec5SDimitry Andric uintptr_t P; 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric public: P(Flag)920b57cec5SDimitry Andric NodeGroup(bool Flag = false) : P(Flag) { 930b57cec5SDimitry Andric assert(getFlag() == Flag); 940b57cec5SDimitry Andric } 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric ExplodedNode * const *begin() const; 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric ExplodedNode * const *end() const; 990b57cec5SDimitry Andric 1000b57cec5SDimitry Andric unsigned size() const; 1010b57cec5SDimitry Andric empty()1020b57cec5SDimitry Andric bool empty() const { return P == 0 || getFlag() != 0; } 1030b57cec5SDimitry Andric 1040b57cec5SDimitry Andric /// Adds a node to the list. 1050b57cec5SDimitry Andric /// 1060b57cec5SDimitry Andric /// The group must not have been created with its flag set. 1070b57cec5SDimitry Andric void addNode(ExplodedNode *N, ExplodedGraph &G); 1080b57cec5SDimitry Andric 1090b57cec5SDimitry Andric /// Replaces the single node in this group with a new node. 1100b57cec5SDimitry Andric /// 1110b57cec5SDimitry Andric /// Note that this should only be used when you know the group was not 1120b57cec5SDimitry Andric /// created with its flag set, and that the group is empty or contains 1130b57cec5SDimitry Andric /// only a single node. 1140b57cec5SDimitry Andric void replaceNode(ExplodedNode *node); 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andric /// Returns whether this group was created with its flag set. getFlag()1170b57cec5SDimitry Andric bool getFlag() const { 1180b57cec5SDimitry Andric return (P & 1); 1190b57cec5SDimitry Andric } 1200b57cec5SDimitry Andric }; 1210b57cec5SDimitry Andric 1220b57cec5SDimitry Andric /// Location - The program location (within a function body) associated 1230b57cec5SDimitry Andric /// with this node. 1240b57cec5SDimitry Andric const ProgramPoint Location; 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric /// State - The state associated with this node. 1270b57cec5SDimitry Andric ProgramStateRef State; 1280b57cec5SDimitry Andric 1290b57cec5SDimitry Andric /// Preds - The predecessors of this node. 1300b57cec5SDimitry Andric NodeGroup Preds; 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric /// Succs - The successors of this node. 1330b57cec5SDimitry Andric NodeGroup Succs; 1340b57cec5SDimitry Andric 135a7dea167SDimitry Andric int64_t Id; 136a7dea167SDimitry Andric 1370b57cec5SDimitry Andric public: ExplodedNode(const ProgramPoint & loc,ProgramStateRef state,int64_t Id,bool IsSink)1380b57cec5SDimitry Andric explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 139a7dea167SDimitry Andric int64_t Id, bool IsSink) 140a7dea167SDimitry Andric : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) { 1410b57cec5SDimitry Andric assert(isSink() == IsSink); 1420b57cec5SDimitry Andric } 1430b57cec5SDimitry Andric 1440b57cec5SDimitry Andric /// getLocation - Returns the edge associated with the given node. getLocation()1450b57cec5SDimitry Andric ProgramPoint getLocation() const { return Location; } 1460b57cec5SDimitry Andric getLocationContext()1470b57cec5SDimitry Andric const LocationContext *getLocationContext() const { 1480b57cec5SDimitry Andric return getLocation().getLocationContext(); 1490b57cec5SDimitry Andric } 1500b57cec5SDimitry Andric getStackFrame()1510b57cec5SDimitry Andric const StackFrameContext *getStackFrame() const { 1520b57cec5SDimitry Andric return getLocation().getStackFrame(); 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric getCodeDecl()1550b57cec5SDimitry Andric const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 1560b57cec5SDimitry Andric getCFG()1570b57cec5SDimitry Andric CFG &getCFG() const { return *getLocationContext()->getCFG(); } 1580b57cec5SDimitry Andric 159a7dea167SDimitry Andric const CFGBlock *getCFGBlock() const; 160a7dea167SDimitry Andric getParentMap()161a7dea167SDimitry Andric const ParentMap &getParentMap() const { 162a7dea167SDimitry Andric return getLocationContext()->getParentMap(); 163a7dea167SDimitry Andric } 1640b57cec5SDimitry Andric getAnalysis()16581ad6265SDimitry Andric template <typename T> T &getAnalysis() const { 1660b57cec5SDimitry Andric return *getLocationContext()->getAnalysis<T>(); 1670b57cec5SDimitry Andric } 1680b57cec5SDimitry Andric getState()1690b57cec5SDimitry Andric const ProgramStateRef &getState() const { return State; } 1700b57cec5SDimitry Andric getLocationAs()171bdd1243dSDimitry Andric template <typename T> std::optional<T> getLocationAs() const & { 1720b57cec5SDimitry Andric return Location.getAs<T>(); 1730b57cec5SDimitry Andric } 1740b57cec5SDimitry Andric 1750b57cec5SDimitry Andric /// Get the value of an arbitrary expression at this node. getSVal(const Stmt * S)1760b57cec5SDimitry Andric SVal getSVal(const Stmt *S) const { 1770b57cec5SDimitry Andric return getState()->getSVal(S, getLocationContext()); 1780b57cec5SDimitry Andric } 1790b57cec5SDimitry Andric Profile(llvm::FoldingSetNodeID & ID,const ProgramPoint & Loc,const ProgramStateRef & state,bool IsSink)1800b57cec5SDimitry Andric static void Profile(llvm::FoldingSetNodeID &ID, 1810b57cec5SDimitry Andric const ProgramPoint &Loc, 1820b57cec5SDimitry Andric const ProgramStateRef &state, 1830b57cec5SDimitry Andric bool IsSink) { 1840b57cec5SDimitry Andric ID.Add(Loc); 1850b57cec5SDimitry Andric ID.AddPointer(state.get()); 1860b57cec5SDimitry Andric ID.AddBoolean(IsSink); 1870b57cec5SDimitry Andric } 1880b57cec5SDimitry Andric Profile(llvm::FoldingSetNodeID & ID)1890b57cec5SDimitry Andric void Profile(llvm::FoldingSetNodeID& ID) const { 1900b57cec5SDimitry Andric // We avoid copy constructors by not using accessors. 1910b57cec5SDimitry Andric Profile(ID, Location, State, isSink()); 1920b57cec5SDimitry Andric } 1930b57cec5SDimitry Andric 1940b57cec5SDimitry Andric /// addPredeccessor - Adds a predecessor to the current node, and 1950b57cec5SDimitry Andric /// in tandem add this node as a successor of the other node. 1960b57cec5SDimitry Andric void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 1970b57cec5SDimitry Andric succ_size()1980b57cec5SDimitry Andric unsigned succ_size() const { return Succs.size(); } pred_size()1990b57cec5SDimitry Andric unsigned pred_size() const { return Preds.size(); } succ_empty()2000b57cec5SDimitry Andric bool succ_empty() const { return Succs.empty(); } pred_empty()2010b57cec5SDimitry Andric bool pred_empty() const { return Preds.empty(); } 2020b57cec5SDimitry Andric isSink()2030b57cec5SDimitry Andric bool isSink() const { return Succs.getFlag(); } 2040b57cec5SDimitry Andric hasSinglePred()2050b57cec5SDimitry Andric bool hasSinglePred() const { 2060b57cec5SDimitry Andric return (pred_size() == 1); 2070b57cec5SDimitry Andric } 2080b57cec5SDimitry Andric getFirstPred()2090b57cec5SDimitry Andric ExplodedNode *getFirstPred() { 2100b57cec5SDimitry Andric return pred_empty() ? nullptr : *(pred_begin()); 2110b57cec5SDimitry Andric } 2120b57cec5SDimitry Andric getFirstPred()2130b57cec5SDimitry Andric const ExplodedNode *getFirstPred() const { 2140b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->getFirstPred(); 2150b57cec5SDimitry Andric } 2160b57cec5SDimitry Andric getFirstSucc()2170b57cec5SDimitry Andric ExplodedNode *getFirstSucc() { 2180b57cec5SDimitry Andric return succ_empty() ? nullptr : *(succ_begin()); 2190b57cec5SDimitry Andric } 2200b57cec5SDimitry Andric getFirstSucc()2210b57cec5SDimitry Andric const ExplodedNode *getFirstSucc() const { 2220b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->getFirstSucc(); 2230b57cec5SDimitry Andric } 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andric // Iterators over successor and predecessor vertices. 2260b57cec5SDimitry Andric using succ_iterator = ExplodedNode * const *; 227a7dea167SDimitry Andric using succ_range = llvm::iterator_range<succ_iterator>; 228a7dea167SDimitry Andric 2290b57cec5SDimitry Andric using const_succ_iterator = const ExplodedNode * const *; 230a7dea167SDimitry Andric using const_succ_range = llvm::iterator_range<const_succ_iterator>; 231a7dea167SDimitry Andric 2320b57cec5SDimitry Andric using pred_iterator = ExplodedNode * const *; 233a7dea167SDimitry Andric using pred_range = llvm::iterator_range<pred_iterator>; 234a7dea167SDimitry Andric 2350b57cec5SDimitry Andric using const_pred_iterator = const ExplodedNode * const *; 236a7dea167SDimitry Andric using const_pred_range = llvm::iterator_range<const_pred_iterator>; 2370b57cec5SDimitry Andric pred_begin()2380b57cec5SDimitry Andric pred_iterator pred_begin() { return Preds.begin(); } pred_end()2390b57cec5SDimitry Andric pred_iterator pred_end() { return Preds.end(); } preds()240a7dea167SDimitry Andric pred_range preds() { return {Preds.begin(), Preds.end()}; } 2410b57cec5SDimitry Andric pred_begin()2420b57cec5SDimitry Andric const_pred_iterator pred_begin() const { 2430b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->pred_begin(); 2440b57cec5SDimitry Andric } pred_end()2450b57cec5SDimitry Andric const_pred_iterator pred_end() const { 2460b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->pred_end(); 2470b57cec5SDimitry Andric } preds()248a7dea167SDimitry Andric const_pred_range preds() const { return {Preds.begin(), Preds.end()}; } 2490b57cec5SDimitry Andric succ_begin()2500b57cec5SDimitry Andric succ_iterator succ_begin() { return Succs.begin(); } succ_end()2510b57cec5SDimitry Andric succ_iterator succ_end() { return Succs.end(); } succs()252a7dea167SDimitry Andric succ_range succs() { return {Succs.begin(), Succs.end()}; } 2530b57cec5SDimitry Andric succ_begin()2540b57cec5SDimitry Andric const_succ_iterator succ_begin() const { 2550b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->succ_begin(); 2560b57cec5SDimitry Andric } succ_end()2570b57cec5SDimitry Andric const_succ_iterator succ_end() const { 2580b57cec5SDimitry Andric return const_cast<ExplodedNode*>(this)->succ_end(); 2590b57cec5SDimitry Andric } succs()260a7dea167SDimitry Andric const_succ_range succs() const { return {Succs.begin(), Succs.end()}; } 2610b57cec5SDimitry Andric getID()262a7dea167SDimitry Andric int64_t getID() const { return Id; } 2630b57cec5SDimitry Andric 2640b57cec5SDimitry Andric /// The node is trivial if it has only one successor, only one predecessor, 2650b57cec5SDimitry Andric /// it's predecessor has only one successor, 2660b57cec5SDimitry Andric /// and its program state is the same as the program state of the previous 2670b57cec5SDimitry Andric /// node. 2680b57cec5SDimitry Andric /// Trivial nodes may be skipped while printing exploded graph. 2690b57cec5SDimitry Andric bool isTrivial() const; 2700b57cec5SDimitry Andric 271a7dea167SDimitry Andric /// If the node's program point corresponds to a statement, retrieve that 272a7dea167SDimitry Andric /// statement. Useful for figuring out where to put a warning or a note. 273a7dea167SDimitry Andric /// If the statement belongs to a body-farmed definition, 274a7dea167SDimitry Andric /// retrieve the call site for that definition. 275a7dea167SDimitry Andric const Stmt *getStmtForDiagnostics() const; 276a7dea167SDimitry Andric 277a7dea167SDimitry Andric /// Find the next statement that was executed on this node's execution path. 278a7dea167SDimitry Andric /// Useful for explaining control flow that follows the current node. 279a7dea167SDimitry Andric /// If the statement belongs to a body-farmed definition, retrieve the 280a7dea167SDimitry Andric /// call site for that definition. 281a7dea167SDimitry Andric const Stmt *getNextStmtForDiagnostics() const; 282a7dea167SDimitry Andric 283a7dea167SDimitry Andric /// Find the statement that was executed immediately before this node. 284a7dea167SDimitry Andric /// Useful when the node corresponds to a CFG block entrance. 285a7dea167SDimitry Andric /// If the statement belongs to a body-farmed definition, retrieve the 286a7dea167SDimitry Andric /// call site for that definition. 287a7dea167SDimitry Andric const Stmt *getPreviousStmtForDiagnostics() const; 288a7dea167SDimitry Andric 289a7dea167SDimitry Andric /// Find the statement that was executed at or immediately before this node. 290a7dea167SDimitry Andric /// Useful when any nearby statement will do. 291a7dea167SDimitry Andric /// If the statement belongs to a body-farmed definition, retrieve the 292a7dea167SDimitry Andric /// call site for that definition. 293a7dea167SDimitry Andric const Stmt *getCurrentOrPreviousStmtForDiagnostics() const; 294a7dea167SDimitry Andric 2950b57cec5SDimitry Andric private: replaceSuccessor(ExplodedNode * node)2960b57cec5SDimitry Andric void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } replacePredecessor(ExplodedNode * node)2970b57cec5SDimitry Andric void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 2980b57cec5SDimitry Andric }; 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andric using InterExplodedGraphMap = 3010b57cec5SDimitry Andric llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>; 3020b57cec5SDimitry Andric 3030b57cec5SDimitry Andric class ExplodedGraph { 3040b57cec5SDimitry Andric protected: 3050b57cec5SDimitry Andric friend class CoreEngine; 3060b57cec5SDimitry Andric 3070b57cec5SDimitry Andric // Type definitions. 3080b57cec5SDimitry Andric using NodeVector = std::vector<ExplodedNode *>; 3090b57cec5SDimitry Andric 3100b57cec5SDimitry Andric /// The roots of the simulation graph. Usually there will be only 3110b57cec5SDimitry Andric /// one, but clients are free to establish multiple subgraphs within a single 3120b57cec5SDimitry Andric /// SimulGraph. Moreover, these subgraphs can often merge when paths from 3130b57cec5SDimitry Andric /// different roots reach the same state at the same program location. 3140b57cec5SDimitry Andric NodeVector Roots; 3150b57cec5SDimitry Andric 3160b57cec5SDimitry Andric /// The nodes in the simulation graph which have been 3170b57cec5SDimitry Andric /// specially marked as the endpoint of an abstract simulation path. 3180b57cec5SDimitry Andric NodeVector EndNodes; 3190b57cec5SDimitry Andric 3200b57cec5SDimitry Andric /// Nodes - The nodes in the graph. 3210b57cec5SDimitry Andric llvm::FoldingSet<ExplodedNode> Nodes; 3220b57cec5SDimitry Andric 3230b57cec5SDimitry Andric /// BVC - Allocator and context for allocating nodes and their predecessor 3240b57cec5SDimitry Andric /// and successor groups. 3250b57cec5SDimitry Andric BumpVectorContext BVC; 3260b57cec5SDimitry Andric 3270b57cec5SDimitry Andric /// NumNodes - The number of nodes in the graph. 328a7dea167SDimitry Andric int64_t NumNodes = 0; 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andric /// A list of recently allocated nodes that can potentially be recycled. 3310b57cec5SDimitry Andric NodeVector ChangedNodes; 3320b57cec5SDimitry Andric 3330b57cec5SDimitry Andric /// A list of nodes that can be reused. 3340b57cec5SDimitry Andric NodeVector FreeNodes; 3350b57cec5SDimitry Andric 3360b57cec5SDimitry Andric /// Determines how often nodes are reclaimed. 3370b57cec5SDimitry Andric /// 3380b57cec5SDimitry Andric /// If this is 0, nodes will never be reclaimed. 3390b57cec5SDimitry Andric unsigned ReclaimNodeInterval = 0; 3400b57cec5SDimitry Andric 3410b57cec5SDimitry Andric /// Counter to determine when to reclaim nodes. 3420b57cec5SDimitry Andric unsigned ReclaimCounter; 3430b57cec5SDimitry Andric 3440b57cec5SDimitry Andric public: 3450b57cec5SDimitry Andric ExplodedGraph(); 3460b57cec5SDimitry Andric ~ExplodedGraph(); 3470b57cec5SDimitry Andric 3480b57cec5SDimitry Andric /// Retrieve the node associated with a (Location,State) pair, 3490b57cec5SDimitry Andric /// where the 'Location' is a ProgramPoint in the CFG. If no node for 3500b57cec5SDimitry Andric /// this pair exists, it is created. IsNew is set to true if 3510b57cec5SDimitry Andric /// the node was freshly created. 3520b57cec5SDimitry Andric ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 3530b57cec5SDimitry Andric bool IsSink = false, 3540b57cec5SDimitry Andric bool* IsNew = nullptr); 3550b57cec5SDimitry Andric 3560b57cec5SDimitry Andric /// Create a node for a (Location, State) pair, 3570b57cec5SDimitry Andric /// but don't store it for deduplication later. This 3580b57cec5SDimitry Andric /// is useful when copying an already completed 3590b57cec5SDimitry Andric /// ExplodedGraph for further processing. 3600b57cec5SDimitry Andric ExplodedNode *createUncachedNode(const ProgramPoint &L, 3610b57cec5SDimitry Andric ProgramStateRef State, 362a7dea167SDimitry Andric int64_t Id, 3630b57cec5SDimitry Andric bool IsSink = false); 3640b57cec5SDimitry Andric MakeEmptyGraph()3650b57cec5SDimitry Andric std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const { 366a7dea167SDimitry Andric return std::make_unique<ExplodedGraph>(); 3670b57cec5SDimitry Andric } 3680b57cec5SDimitry Andric 3690b57cec5SDimitry Andric /// addRoot - Add an untyped node to the set of roots. addRoot(ExplodedNode * V)3700b57cec5SDimitry Andric ExplodedNode *addRoot(ExplodedNode *V) { 3710b57cec5SDimitry Andric Roots.push_back(V); 3720b57cec5SDimitry Andric return V; 3730b57cec5SDimitry Andric } 3740b57cec5SDimitry Andric 3750b57cec5SDimitry Andric /// addEndOfPath - Add an untyped node to the set of EOP nodes. addEndOfPath(ExplodedNode * V)3760b57cec5SDimitry Andric ExplodedNode *addEndOfPath(ExplodedNode *V) { 3770b57cec5SDimitry Andric EndNodes.push_back(V); 3780b57cec5SDimitry Andric return V; 3790b57cec5SDimitry Andric } 3800b57cec5SDimitry Andric num_roots()3810b57cec5SDimitry Andric unsigned num_roots() const { return Roots.size(); } num_eops()3820b57cec5SDimitry Andric unsigned num_eops() const { return EndNodes.size(); } 3830b57cec5SDimitry Andric empty()3840b57cec5SDimitry Andric bool empty() const { return NumNodes == 0; } size()3850b57cec5SDimitry Andric unsigned size() const { return NumNodes; } 3860b57cec5SDimitry Andric reserve(unsigned NodeCount)3870b57cec5SDimitry Andric void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); } 3880b57cec5SDimitry Andric 3890b57cec5SDimitry Andric // Iterators. 3900b57cec5SDimitry Andric using NodeTy = ExplodedNode; 3910b57cec5SDimitry Andric using AllNodesTy = llvm::FoldingSet<ExplodedNode>; 3920b57cec5SDimitry Andric using roots_iterator = NodeVector::iterator; 3930b57cec5SDimitry Andric using const_roots_iterator = NodeVector::const_iterator; 3940b57cec5SDimitry Andric using eop_iterator = NodeVector::iterator; 3950b57cec5SDimitry Andric using const_eop_iterator = NodeVector::const_iterator; 3960b57cec5SDimitry Andric using node_iterator = AllNodesTy::iterator; 3970b57cec5SDimitry Andric using const_node_iterator = AllNodesTy::const_iterator; 3980b57cec5SDimitry Andric nodes()39906c3fb27SDimitry Andric llvm::iterator_range<node_iterator> nodes() { return Nodes; } 4000b57cec5SDimitry Andric nodes()40106c3fb27SDimitry Andric llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; } 4020b57cec5SDimitry Andric roots_begin()4030b57cec5SDimitry Andric roots_iterator roots_begin() { return Roots.begin(); } 4040b57cec5SDimitry Andric roots_end()4050b57cec5SDimitry Andric roots_iterator roots_end() { return Roots.end(); } 4060b57cec5SDimitry Andric roots_begin()4070b57cec5SDimitry Andric const_roots_iterator roots_begin() const { return Roots.begin(); } 4080b57cec5SDimitry Andric roots_end()4090b57cec5SDimitry Andric const_roots_iterator roots_end() const { return Roots.end(); } 4100b57cec5SDimitry Andric eop_begin()4110b57cec5SDimitry Andric eop_iterator eop_begin() { return EndNodes.begin(); } 4120b57cec5SDimitry Andric eop_end()4130b57cec5SDimitry Andric eop_iterator eop_end() { return EndNodes.end(); } 4140b57cec5SDimitry Andric eop_begin()4150b57cec5SDimitry Andric const_eop_iterator eop_begin() const { return EndNodes.begin(); } 4160b57cec5SDimitry Andric eop_end()4170b57cec5SDimitry Andric const_eop_iterator eop_end() const { return EndNodes.end(); } 4180b57cec5SDimitry Andric getAllocator()4190b57cec5SDimitry Andric llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } getNodeAllocator()4200b57cec5SDimitry Andric BumpVectorContext &getNodeAllocator() { return BVC; } 4210b57cec5SDimitry Andric 4220b57cec5SDimitry Andric using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>; 4230b57cec5SDimitry Andric 4240b57cec5SDimitry Andric /// Creates a trimmed version of the graph that only contains paths leading 4250b57cec5SDimitry Andric /// to the given nodes. 4260b57cec5SDimitry Andric /// 4270b57cec5SDimitry Andric /// \param Nodes The nodes which must appear in the final graph. Presumably 4280b57cec5SDimitry Andric /// these are end-of-path nodes (i.e. they have no successors). 4290b57cec5SDimitry Andric /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 4300b57cec5SDimitry Andric /// the returned graph. 4310b57cec5SDimitry Andric /// \param[out] InverseMap An optional map from nodes in the returned graph to 4320b57cec5SDimitry Andric /// nodes in this graph. 4330b57cec5SDimitry Andric /// \returns The trimmed graph 4340b57cec5SDimitry Andric std::unique_ptr<ExplodedGraph> 4350b57cec5SDimitry Andric trim(ArrayRef<const NodeTy *> Nodes, 4360b57cec5SDimitry Andric InterExplodedGraphMap *ForwardMap = nullptr, 4370b57cec5SDimitry Andric InterExplodedGraphMap *InverseMap = nullptr) const; 4380b57cec5SDimitry Andric 4390b57cec5SDimitry Andric /// Enable tracking of recently allocated nodes for potential reclamation 4400b57cec5SDimitry Andric /// when calling reclaimRecentlyAllocatedNodes(). enableNodeReclamation(unsigned Interval)4410b57cec5SDimitry Andric void enableNodeReclamation(unsigned Interval) { 4420b57cec5SDimitry Andric ReclaimCounter = ReclaimNodeInterval = Interval; 4430b57cec5SDimitry Andric } 4440b57cec5SDimitry Andric 4450b57cec5SDimitry Andric /// Reclaim "uninteresting" nodes created since the last time this method 4460b57cec5SDimitry Andric /// was called. 4470b57cec5SDimitry Andric void reclaimRecentlyAllocatedNodes(); 4480b57cec5SDimitry Andric 4490b57cec5SDimitry Andric /// Returns true if nodes for the given expression kind are always 4500b57cec5SDimitry Andric /// kept around. 4510b57cec5SDimitry Andric static bool isInterestingLValueExpr(const Expr *Ex); 4520b57cec5SDimitry Andric 4530b57cec5SDimitry Andric private: 4540b57cec5SDimitry Andric bool shouldCollect(const ExplodedNode *node); 4550b57cec5SDimitry Andric void collectNode(ExplodedNode *node); 4560b57cec5SDimitry Andric }; 4570b57cec5SDimitry Andric 4580b57cec5SDimitry Andric class ExplodedNodeSet { 4590b57cec5SDimitry Andric using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>; 4600b57cec5SDimitry Andric ImplTy Impl; 4610b57cec5SDimitry Andric 4620b57cec5SDimitry Andric public: ExplodedNodeSet(ExplodedNode * N)4630b57cec5SDimitry Andric ExplodedNodeSet(ExplodedNode *N) { 4640b57cec5SDimitry Andric assert(N && !static_cast<ExplodedNode*>(N)->isSink()); 4650b57cec5SDimitry Andric Impl.insert(N); 4660b57cec5SDimitry Andric } 4670b57cec5SDimitry Andric 4680b57cec5SDimitry Andric ExplodedNodeSet() = default; 4690b57cec5SDimitry Andric Add(ExplodedNode * N)4700b57cec5SDimitry Andric void Add(ExplodedNode *N) { 4710b57cec5SDimitry Andric if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 4720b57cec5SDimitry Andric } 4730b57cec5SDimitry Andric 4740b57cec5SDimitry Andric using iterator = ImplTy::iterator; 4750b57cec5SDimitry Andric using const_iterator = ImplTy::const_iterator; 4760b57cec5SDimitry Andric size()4770b57cec5SDimitry Andric unsigned size() const { return Impl.size(); } empty()4780b57cec5SDimitry Andric bool empty() const { return Impl.empty(); } erase(ExplodedNode * N)4790b57cec5SDimitry Andric bool erase(ExplodedNode *N) { return Impl.remove(N); } 4800b57cec5SDimitry Andric clear()4810b57cec5SDimitry Andric void clear() { Impl.clear(); } 4820b57cec5SDimitry Andric insert(const ExplodedNodeSet & S)4830b57cec5SDimitry Andric void insert(const ExplodedNodeSet &S) { 4840b57cec5SDimitry Andric assert(&S != this); 4850b57cec5SDimitry Andric if (empty()) 4860b57cec5SDimitry Andric Impl = S.Impl; 4870b57cec5SDimitry Andric else 4880b57cec5SDimitry Andric Impl.insert(S.begin(), S.end()); 4890b57cec5SDimitry Andric } 4900b57cec5SDimitry Andric begin()4910b57cec5SDimitry Andric iterator begin() { return Impl.begin(); } end()4920b57cec5SDimitry Andric iterator end() { return Impl.end(); } 4930b57cec5SDimitry Andric begin()4940b57cec5SDimitry Andric const_iterator begin() const { return Impl.begin(); } end()4950b57cec5SDimitry Andric const_iterator end() const { return Impl.end(); } 4960b57cec5SDimitry Andric }; 4970b57cec5SDimitry Andric 4980b57cec5SDimitry Andric } // namespace ento 4990b57cec5SDimitry Andric 5000b57cec5SDimitry Andric } // namespace clang 5010b57cec5SDimitry Andric 5020b57cec5SDimitry Andric // GraphTraits 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric namespace llvm { 5050b57cec5SDimitry Andric template <> struct GraphTraits<clang::ento::ExplodedGraph *> { 5060b57cec5SDimitry Andric using GraphTy = clang::ento::ExplodedGraph *; 5070b57cec5SDimitry Andric using NodeRef = clang::ento::ExplodedNode *; 5080b57cec5SDimitry Andric using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; 5090b57cec5SDimitry Andric using nodes_iterator = llvm::df_iterator<GraphTy>; 5100b57cec5SDimitry Andric 5110b57cec5SDimitry Andric static NodeRef getEntryNode(const GraphTy G) { 5120b57cec5SDimitry Andric return *G->roots_begin(); 5130b57cec5SDimitry Andric } 5140b57cec5SDimitry Andric 5150b57cec5SDimitry Andric static bool predecessorOfTrivial(NodeRef N) { 5160b57cec5SDimitry Andric return N->succ_size() == 1 && N->getFirstSucc()->isTrivial(); 5170b57cec5SDimitry Andric } 5180b57cec5SDimitry Andric 5190b57cec5SDimitry Andric static ChildIteratorType child_begin(NodeRef N) { 5200b57cec5SDimitry Andric if (predecessorOfTrivial(N)) 5210b57cec5SDimitry Andric return child_begin(*N->succ_begin()); 5220b57cec5SDimitry Andric return N->succ_begin(); 5230b57cec5SDimitry Andric } 5240b57cec5SDimitry Andric 5250b57cec5SDimitry Andric static ChildIteratorType child_end(NodeRef N) { 5260b57cec5SDimitry Andric if (predecessorOfTrivial(N)) 5270b57cec5SDimitry Andric return child_end(N->getFirstSucc()); 5280b57cec5SDimitry Andric return N->succ_end(); 5290b57cec5SDimitry Andric } 5300b57cec5SDimitry Andric 5310b57cec5SDimitry Andric static nodes_iterator nodes_begin(const GraphTy G) { 5320b57cec5SDimitry Andric return df_begin(G); 5330b57cec5SDimitry Andric } 5340b57cec5SDimitry Andric 5350b57cec5SDimitry Andric static nodes_iterator nodes_end(const GraphTy G) { 5360b57cec5SDimitry Andric return df_end(G); 5370b57cec5SDimitry Andric } 5380b57cec5SDimitry Andric }; 5390b57cec5SDimitry Andric } // namespace llvm 5400b57cec5SDimitry Andric 5410b57cec5SDimitry Andric #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 542