1*06f32e7eSjoerg //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===// 2*06f32e7eSjoerg // 3*06f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*06f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 5*06f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*06f32e7eSjoerg // 7*06f32e7eSjoerg //===----------------------------------------------------------------------===// 8*06f32e7eSjoerg // 9*06f32e7eSjoerg // This file defines the template classes ExplodedNode and ExplodedGraph, 10*06f32e7eSjoerg // which represent a path-sensitive, intra-procedural "exploded graph." 11*06f32e7eSjoerg // See "Precise interprocedural dataflow analysis via graph reachability" 12*06f32e7eSjoerg // by Reps, Horwitz, and Sagiv 13*06f32e7eSjoerg // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 14*06f32e7eSjoerg // exploded graph. 15*06f32e7eSjoerg // 16*06f32e7eSjoerg //===----------------------------------------------------------------------===// 17*06f32e7eSjoerg 18*06f32e7eSjoerg #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 19*06f32e7eSjoerg #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 20*06f32e7eSjoerg 21*06f32e7eSjoerg #include "clang/Analysis/AnalysisDeclContext.h" 22*06f32e7eSjoerg #include "clang/Analysis/ProgramPoint.h" 23*06f32e7eSjoerg #include "clang/Analysis/Support/BumpVector.h" 24*06f32e7eSjoerg #include "clang/Basic/LLVM.h" 25*06f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 26*06f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 27*06f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 28*06f32e7eSjoerg #include "llvm/ADT/ArrayRef.h" 29*06f32e7eSjoerg #include "llvm/ADT/DenseMap.h" 30*06f32e7eSjoerg #include "llvm/ADT/DepthFirstIterator.h" 31*06f32e7eSjoerg #include "llvm/ADT/FoldingSet.h" 32*06f32e7eSjoerg #include "llvm/ADT/GraphTraits.h" 33*06f32e7eSjoerg #include "llvm/ADT/Optional.h" 34*06f32e7eSjoerg #include "llvm/ADT/STLExtras.h" 35*06f32e7eSjoerg #include "llvm/ADT/SetVector.h" 36*06f32e7eSjoerg #include "llvm/Support/Allocator.h" 37*06f32e7eSjoerg #include "llvm/Support/Compiler.h" 38*06f32e7eSjoerg #include <cassert> 39*06f32e7eSjoerg #include <cstdint> 40*06f32e7eSjoerg #include <memory> 41*06f32e7eSjoerg #include <utility> 42*06f32e7eSjoerg #include <vector> 43*06f32e7eSjoerg 44*06f32e7eSjoerg namespace clang { 45*06f32e7eSjoerg 46*06f32e7eSjoerg class CFG; 47*06f32e7eSjoerg class Decl; 48*06f32e7eSjoerg class Expr; 49*06f32e7eSjoerg class ParentMap; 50*06f32e7eSjoerg class Stmt; 51*06f32e7eSjoerg 52*06f32e7eSjoerg namespace ento { 53*06f32e7eSjoerg 54*06f32e7eSjoerg class ExplodedGraph; 55*06f32e7eSjoerg 56*06f32e7eSjoerg //===----------------------------------------------------------------------===// 57*06f32e7eSjoerg // ExplodedGraph "implementation" classes. These classes are not typed to 58*06f32e7eSjoerg // contain a specific kind of state. Typed-specialized versions are defined 59*06f32e7eSjoerg // on top of these classes. 60*06f32e7eSjoerg //===----------------------------------------------------------------------===// 61*06f32e7eSjoerg 62*06f32e7eSjoerg // ExplodedNode is not constified all over the engine because we need to add 63*06f32e7eSjoerg // successors to it at any time after creating it. 64*06f32e7eSjoerg 65*06f32e7eSjoerg class ExplodedNode : public llvm::FoldingSetNode { 66*06f32e7eSjoerg friend class BranchNodeBuilder; 67*06f32e7eSjoerg friend class CoreEngine; 68*06f32e7eSjoerg friend class EndOfFunctionNodeBuilder; 69*06f32e7eSjoerg friend class ExplodedGraph; 70*06f32e7eSjoerg friend class IndirectGotoNodeBuilder; 71*06f32e7eSjoerg friend class NodeBuilder; 72*06f32e7eSjoerg friend class SwitchNodeBuilder; 73*06f32e7eSjoerg 74*06f32e7eSjoerg /// Efficiently stores a list of ExplodedNodes, or an optional flag. 75*06f32e7eSjoerg /// 76*06f32e7eSjoerg /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 77*06f32e7eSjoerg /// for the case when there is only one node in the group. This is a fairly 78*06f32e7eSjoerg /// common case in an ExplodedGraph, where most nodes have only one 79*06f32e7eSjoerg /// predecessor and many have only one successor. It can also be used to 80*06f32e7eSjoerg /// store a flag rather than a node list, which ExplodedNode uses to mark 81*06f32e7eSjoerg /// whether a node is a sink. If the flag is set, the group is implicitly 82*06f32e7eSjoerg /// empty and no nodes may be added. 83*06f32e7eSjoerg class NodeGroup { 84*06f32e7eSjoerg // Conceptually a discriminated union. If the low bit is set, the node is 85*06f32e7eSjoerg // a sink. If the low bit is not set, the pointer refers to the storage 86*06f32e7eSjoerg // for the nodes in the group. 87*06f32e7eSjoerg // This is not a PointerIntPair in order to keep the storage type opaque. 88*06f32e7eSjoerg uintptr_t P; 89*06f32e7eSjoerg 90*06f32e7eSjoerg public: P(Flag)91*06f32e7eSjoerg NodeGroup(bool Flag = false) : P(Flag) { 92*06f32e7eSjoerg assert(getFlag() == Flag); 93*06f32e7eSjoerg } 94*06f32e7eSjoerg 95*06f32e7eSjoerg ExplodedNode * const *begin() const; 96*06f32e7eSjoerg 97*06f32e7eSjoerg ExplodedNode * const *end() const; 98*06f32e7eSjoerg 99*06f32e7eSjoerg unsigned size() const; 100*06f32e7eSjoerg empty()101*06f32e7eSjoerg bool empty() const { return P == 0 || getFlag() != 0; } 102*06f32e7eSjoerg 103*06f32e7eSjoerg /// Adds a node to the list. 104*06f32e7eSjoerg /// 105*06f32e7eSjoerg /// The group must not have been created with its flag set. 106*06f32e7eSjoerg void addNode(ExplodedNode *N, ExplodedGraph &G); 107*06f32e7eSjoerg 108*06f32e7eSjoerg /// Replaces the single node in this group with a new node. 109*06f32e7eSjoerg /// 110*06f32e7eSjoerg /// Note that this should only be used when you know the group was not 111*06f32e7eSjoerg /// created with its flag set, and that the group is empty or contains 112*06f32e7eSjoerg /// only a single node. 113*06f32e7eSjoerg void replaceNode(ExplodedNode *node); 114*06f32e7eSjoerg 115*06f32e7eSjoerg /// Returns whether this group was created with its flag set. getFlag()116*06f32e7eSjoerg bool getFlag() const { 117*06f32e7eSjoerg return (P & 1); 118*06f32e7eSjoerg } 119*06f32e7eSjoerg }; 120*06f32e7eSjoerg 121*06f32e7eSjoerg /// Location - The program location (within a function body) associated 122*06f32e7eSjoerg /// with this node. 123*06f32e7eSjoerg const ProgramPoint Location; 124*06f32e7eSjoerg 125*06f32e7eSjoerg /// State - The state associated with this node. 126*06f32e7eSjoerg ProgramStateRef State; 127*06f32e7eSjoerg 128*06f32e7eSjoerg /// Preds - The predecessors of this node. 129*06f32e7eSjoerg NodeGroup Preds; 130*06f32e7eSjoerg 131*06f32e7eSjoerg /// Succs - The successors of this node. 132*06f32e7eSjoerg NodeGroup Succs; 133*06f32e7eSjoerg 134*06f32e7eSjoerg int64_t Id; 135*06f32e7eSjoerg 136*06f32e7eSjoerg public: ExplodedNode(const ProgramPoint & loc,ProgramStateRef state,int64_t Id,bool IsSink)137*06f32e7eSjoerg explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 138*06f32e7eSjoerg int64_t Id, bool IsSink) 139*06f32e7eSjoerg : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) { 140*06f32e7eSjoerg assert(isSink() == IsSink); 141*06f32e7eSjoerg } 142*06f32e7eSjoerg 143*06f32e7eSjoerg /// getLocation - Returns the edge associated with the given node. getLocation()144*06f32e7eSjoerg ProgramPoint getLocation() const { return Location; } 145*06f32e7eSjoerg getLocationContext()146*06f32e7eSjoerg const LocationContext *getLocationContext() const { 147*06f32e7eSjoerg return getLocation().getLocationContext(); 148*06f32e7eSjoerg } 149*06f32e7eSjoerg getStackFrame()150*06f32e7eSjoerg const StackFrameContext *getStackFrame() const { 151*06f32e7eSjoerg return getLocation().getStackFrame(); 152*06f32e7eSjoerg } 153*06f32e7eSjoerg getCodeDecl()154*06f32e7eSjoerg const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 155*06f32e7eSjoerg getCFG()156*06f32e7eSjoerg CFG &getCFG() const { return *getLocationContext()->getCFG(); } 157*06f32e7eSjoerg 158*06f32e7eSjoerg const CFGBlock *getCFGBlock() const; 159*06f32e7eSjoerg getParentMap()160*06f32e7eSjoerg const ParentMap &getParentMap() const { 161*06f32e7eSjoerg return getLocationContext()->getParentMap(); 162*06f32e7eSjoerg } 163*06f32e7eSjoerg 164*06f32e7eSjoerg template <typename T> getAnalysis()165*06f32e7eSjoerg T &getAnalysis() const { 166*06f32e7eSjoerg return *getLocationContext()->getAnalysis<T>(); 167*06f32e7eSjoerg } 168*06f32e7eSjoerg getState()169*06f32e7eSjoerg const ProgramStateRef &getState() const { return State; } 170*06f32e7eSjoerg 171*06f32e7eSjoerg template <typename T> getLocationAs()172*06f32e7eSjoerg Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 173*06f32e7eSjoerg return Location.getAs<T>(); 174*06f32e7eSjoerg } 175*06f32e7eSjoerg 176*06f32e7eSjoerg /// Get the value of an arbitrary expression at this node. getSVal(const Stmt * S)177*06f32e7eSjoerg SVal getSVal(const Stmt *S) const { 178*06f32e7eSjoerg return getState()->getSVal(S, getLocationContext()); 179*06f32e7eSjoerg } 180*06f32e7eSjoerg Profile(llvm::FoldingSetNodeID & ID,const ProgramPoint & Loc,const ProgramStateRef & state,bool IsSink)181*06f32e7eSjoerg static void Profile(llvm::FoldingSetNodeID &ID, 182*06f32e7eSjoerg const ProgramPoint &Loc, 183*06f32e7eSjoerg const ProgramStateRef &state, 184*06f32e7eSjoerg bool IsSink) { 185*06f32e7eSjoerg ID.Add(Loc); 186*06f32e7eSjoerg ID.AddPointer(state.get()); 187*06f32e7eSjoerg ID.AddBoolean(IsSink); 188*06f32e7eSjoerg } 189*06f32e7eSjoerg Profile(llvm::FoldingSetNodeID & ID)190*06f32e7eSjoerg void Profile(llvm::FoldingSetNodeID& ID) const { 191*06f32e7eSjoerg // We avoid copy constructors by not using accessors. 192*06f32e7eSjoerg Profile(ID, Location, State, isSink()); 193*06f32e7eSjoerg } 194*06f32e7eSjoerg 195*06f32e7eSjoerg /// addPredeccessor - Adds a predecessor to the current node, and 196*06f32e7eSjoerg /// in tandem add this node as a successor of the other node. 197*06f32e7eSjoerg void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 198*06f32e7eSjoerg succ_size()199*06f32e7eSjoerg unsigned succ_size() const { return Succs.size(); } pred_size()200*06f32e7eSjoerg unsigned pred_size() const { return Preds.size(); } succ_empty()201*06f32e7eSjoerg bool succ_empty() const { return Succs.empty(); } pred_empty()202*06f32e7eSjoerg bool pred_empty() const { return Preds.empty(); } 203*06f32e7eSjoerg isSink()204*06f32e7eSjoerg bool isSink() const { return Succs.getFlag(); } 205*06f32e7eSjoerg hasSinglePred()206*06f32e7eSjoerg bool hasSinglePred() const { 207*06f32e7eSjoerg return (pred_size() == 1); 208*06f32e7eSjoerg } 209*06f32e7eSjoerg getFirstPred()210*06f32e7eSjoerg ExplodedNode *getFirstPred() { 211*06f32e7eSjoerg return pred_empty() ? nullptr : *(pred_begin()); 212*06f32e7eSjoerg } 213*06f32e7eSjoerg getFirstPred()214*06f32e7eSjoerg const ExplodedNode *getFirstPred() const { 215*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->getFirstPred(); 216*06f32e7eSjoerg } 217*06f32e7eSjoerg getFirstSucc()218*06f32e7eSjoerg ExplodedNode *getFirstSucc() { 219*06f32e7eSjoerg return succ_empty() ? nullptr : *(succ_begin()); 220*06f32e7eSjoerg } 221*06f32e7eSjoerg getFirstSucc()222*06f32e7eSjoerg const ExplodedNode *getFirstSucc() const { 223*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->getFirstSucc(); 224*06f32e7eSjoerg } 225*06f32e7eSjoerg 226*06f32e7eSjoerg // Iterators over successor and predecessor vertices. 227*06f32e7eSjoerg using succ_iterator = ExplodedNode * const *; 228*06f32e7eSjoerg using succ_range = llvm::iterator_range<succ_iterator>; 229*06f32e7eSjoerg 230*06f32e7eSjoerg using const_succ_iterator = const ExplodedNode * const *; 231*06f32e7eSjoerg using const_succ_range = llvm::iterator_range<const_succ_iterator>; 232*06f32e7eSjoerg 233*06f32e7eSjoerg using pred_iterator = ExplodedNode * const *; 234*06f32e7eSjoerg using pred_range = llvm::iterator_range<pred_iterator>; 235*06f32e7eSjoerg 236*06f32e7eSjoerg using const_pred_iterator = const ExplodedNode * const *; 237*06f32e7eSjoerg using const_pred_range = llvm::iterator_range<const_pred_iterator>; 238*06f32e7eSjoerg pred_begin()239*06f32e7eSjoerg pred_iterator pred_begin() { return Preds.begin(); } pred_end()240*06f32e7eSjoerg pred_iterator pred_end() { return Preds.end(); } preds()241*06f32e7eSjoerg pred_range preds() { return {Preds.begin(), Preds.end()}; } 242*06f32e7eSjoerg pred_begin()243*06f32e7eSjoerg const_pred_iterator pred_begin() const { 244*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->pred_begin(); 245*06f32e7eSjoerg } pred_end()246*06f32e7eSjoerg const_pred_iterator pred_end() const { 247*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->pred_end(); 248*06f32e7eSjoerg } preds()249*06f32e7eSjoerg const_pred_range preds() const { return {Preds.begin(), Preds.end()}; } 250*06f32e7eSjoerg succ_begin()251*06f32e7eSjoerg succ_iterator succ_begin() { return Succs.begin(); } succ_end()252*06f32e7eSjoerg succ_iterator succ_end() { return Succs.end(); } succs()253*06f32e7eSjoerg succ_range succs() { return {Succs.begin(), Succs.end()}; } 254*06f32e7eSjoerg succ_begin()255*06f32e7eSjoerg const_succ_iterator succ_begin() const { 256*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->succ_begin(); 257*06f32e7eSjoerg } succ_end()258*06f32e7eSjoerg const_succ_iterator succ_end() const { 259*06f32e7eSjoerg return const_cast<ExplodedNode*>(this)->succ_end(); 260*06f32e7eSjoerg } succs()261*06f32e7eSjoerg const_succ_range succs() const { return {Succs.begin(), Succs.end()}; } 262*06f32e7eSjoerg getID()263*06f32e7eSjoerg int64_t getID() const { return Id; } 264*06f32e7eSjoerg 265*06f32e7eSjoerg /// The node is trivial if it has only one successor, only one predecessor, 266*06f32e7eSjoerg /// it's predecessor has only one successor, 267*06f32e7eSjoerg /// and its program state is the same as the program state of the previous 268*06f32e7eSjoerg /// node. 269*06f32e7eSjoerg /// Trivial nodes may be skipped while printing exploded graph. 270*06f32e7eSjoerg bool isTrivial() const; 271*06f32e7eSjoerg 272*06f32e7eSjoerg /// If the node's program point corresponds to a statement, retrieve that 273*06f32e7eSjoerg /// statement. Useful for figuring out where to put a warning or a note. 274*06f32e7eSjoerg /// If the statement belongs to a body-farmed definition, 275*06f32e7eSjoerg /// retrieve the call site for that definition. 276*06f32e7eSjoerg const Stmt *getStmtForDiagnostics() const; 277*06f32e7eSjoerg 278*06f32e7eSjoerg /// Find the next statement that was executed on this node's execution path. 279*06f32e7eSjoerg /// Useful for explaining control flow that follows the current node. 280*06f32e7eSjoerg /// If the statement belongs to a body-farmed definition, retrieve the 281*06f32e7eSjoerg /// call site for that definition. 282*06f32e7eSjoerg const Stmt *getNextStmtForDiagnostics() const; 283*06f32e7eSjoerg 284*06f32e7eSjoerg /// Find the statement that was executed immediately before this node. 285*06f32e7eSjoerg /// Useful when the node corresponds to a CFG block entrance. 286*06f32e7eSjoerg /// If the statement belongs to a body-farmed definition, retrieve the 287*06f32e7eSjoerg /// call site for that definition. 288*06f32e7eSjoerg const Stmt *getPreviousStmtForDiagnostics() const; 289*06f32e7eSjoerg 290*06f32e7eSjoerg /// Find the statement that was executed at or immediately before this node. 291*06f32e7eSjoerg /// Useful when any nearby statement will do. 292*06f32e7eSjoerg /// If the statement belongs to a body-farmed definition, retrieve the 293*06f32e7eSjoerg /// call site for that definition. 294*06f32e7eSjoerg const Stmt *getCurrentOrPreviousStmtForDiagnostics() const; 295*06f32e7eSjoerg 296*06f32e7eSjoerg private: replaceSuccessor(ExplodedNode * node)297*06f32e7eSjoerg void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } replacePredecessor(ExplodedNode * node)298*06f32e7eSjoerg void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 299*06f32e7eSjoerg }; 300*06f32e7eSjoerg 301*06f32e7eSjoerg using InterExplodedGraphMap = 302*06f32e7eSjoerg llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>; 303*06f32e7eSjoerg 304*06f32e7eSjoerg class ExplodedGraph { 305*06f32e7eSjoerg protected: 306*06f32e7eSjoerg friend class CoreEngine; 307*06f32e7eSjoerg 308*06f32e7eSjoerg // Type definitions. 309*06f32e7eSjoerg using NodeVector = std::vector<ExplodedNode *>; 310*06f32e7eSjoerg 311*06f32e7eSjoerg /// The roots of the simulation graph. Usually there will be only 312*06f32e7eSjoerg /// one, but clients are free to establish multiple subgraphs within a single 313*06f32e7eSjoerg /// SimulGraph. Moreover, these subgraphs can often merge when paths from 314*06f32e7eSjoerg /// different roots reach the same state at the same program location. 315*06f32e7eSjoerg NodeVector Roots; 316*06f32e7eSjoerg 317*06f32e7eSjoerg /// The nodes in the simulation graph which have been 318*06f32e7eSjoerg /// specially marked as the endpoint of an abstract simulation path. 319*06f32e7eSjoerg NodeVector EndNodes; 320*06f32e7eSjoerg 321*06f32e7eSjoerg /// Nodes - The nodes in the graph. 322*06f32e7eSjoerg llvm::FoldingSet<ExplodedNode> Nodes; 323*06f32e7eSjoerg 324*06f32e7eSjoerg /// BVC - Allocator and context for allocating nodes and their predecessor 325*06f32e7eSjoerg /// and successor groups. 326*06f32e7eSjoerg BumpVectorContext BVC; 327*06f32e7eSjoerg 328*06f32e7eSjoerg /// NumNodes - The number of nodes in the graph. 329*06f32e7eSjoerg int64_t NumNodes = 0; 330*06f32e7eSjoerg 331*06f32e7eSjoerg /// A list of recently allocated nodes that can potentially be recycled. 332*06f32e7eSjoerg NodeVector ChangedNodes; 333*06f32e7eSjoerg 334*06f32e7eSjoerg /// A list of nodes that can be reused. 335*06f32e7eSjoerg NodeVector FreeNodes; 336*06f32e7eSjoerg 337*06f32e7eSjoerg /// Determines how often nodes are reclaimed. 338*06f32e7eSjoerg /// 339*06f32e7eSjoerg /// If this is 0, nodes will never be reclaimed. 340*06f32e7eSjoerg unsigned ReclaimNodeInterval = 0; 341*06f32e7eSjoerg 342*06f32e7eSjoerg /// Counter to determine when to reclaim nodes. 343*06f32e7eSjoerg unsigned ReclaimCounter; 344*06f32e7eSjoerg 345*06f32e7eSjoerg public: 346*06f32e7eSjoerg ExplodedGraph(); 347*06f32e7eSjoerg ~ExplodedGraph(); 348*06f32e7eSjoerg 349*06f32e7eSjoerg /// Retrieve the node associated with a (Location,State) pair, 350*06f32e7eSjoerg /// where the 'Location' is a ProgramPoint in the CFG. If no node for 351*06f32e7eSjoerg /// this pair exists, it is created. IsNew is set to true if 352*06f32e7eSjoerg /// the node was freshly created. 353*06f32e7eSjoerg ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, 354*06f32e7eSjoerg bool IsSink = false, 355*06f32e7eSjoerg bool* IsNew = nullptr); 356*06f32e7eSjoerg 357*06f32e7eSjoerg /// Create a node for a (Location, State) pair, 358*06f32e7eSjoerg /// but don't store it for deduplication later. This 359*06f32e7eSjoerg /// is useful when copying an already completed 360*06f32e7eSjoerg /// ExplodedGraph for further processing. 361*06f32e7eSjoerg ExplodedNode *createUncachedNode(const ProgramPoint &L, 362*06f32e7eSjoerg ProgramStateRef State, 363*06f32e7eSjoerg int64_t Id, 364*06f32e7eSjoerg bool IsSink = false); 365*06f32e7eSjoerg MakeEmptyGraph()366*06f32e7eSjoerg std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const { 367*06f32e7eSjoerg return std::make_unique<ExplodedGraph>(); 368*06f32e7eSjoerg } 369*06f32e7eSjoerg 370*06f32e7eSjoerg /// addRoot - Add an untyped node to the set of roots. addRoot(ExplodedNode * V)371*06f32e7eSjoerg ExplodedNode *addRoot(ExplodedNode *V) { 372*06f32e7eSjoerg Roots.push_back(V); 373*06f32e7eSjoerg return V; 374*06f32e7eSjoerg } 375*06f32e7eSjoerg 376*06f32e7eSjoerg /// addEndOfPath - Add an untyped node to the set of EOP nodes. addEndOfPath(ExplodedNode * V)377*06f32e7eSjoerg ExplodedNode *addEndOfPath(ExplodedNode *V) { 378*06f32e7eSjoerg EndNodes.push_back(V); 379*06f32e7eSjoerg return V; 380*06f32e7eSjoerg } 381*06f32e7eSjoerg num_roots()382*06f32e7eSjoerg unsigned num_roots() const { return Roots.size(); } num_eops()383*06f32e7eSjoerg unsigned num_eops() const { return EndNodes.size(); } 384*06f32e7eSjoerg empty()385*06f32e7eSjoerg bool empty() const { return NumNodes == 0; } size()386*06f32e7eSjoerg unsigned size() const { return NumNodes; } 387*06f32e7eSjoerg reserve(unsigned NodeCount)388*06f32e7eSjoerg void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); } 389*06f32e7eSjoerg 390*06f32e7eSjoerg // Iterators. 391*06f32e7eSjoerg using NodeTy = ExplodedNode; 392*06f32e7eSjoerg using AllNodesTy = llvm::FoldingSet<ExplodedNode>; 393*06f32e7eSjoerg using roots_iterator = NodeVector::iterator; 394*06f32e7eSjoerg using const_roots_iterator = NodeVector::const_iterator; 395*06f32e7eSjoerg using eop_iterator = NodeVector::iterator; 396*06f32e7eSjoerg using const_eop_iterator = NodeVector::const_iterator; 397*06f32e7eSjoerg using node_iterator = AllNodesTy::iterator; 398*06f32e7eSjoerg using const_node_iterator = AllNodesTy::const_iterator; 399*06f32e7eSjoerg nodes_begin()400*06f32e7eSjoerg node_iterator nodes_begin() { return Nodes.begin(); } 401*06f32e7eSjoerg nodes_end()402*06f32e7eSjoerg node_iterator nodes_end() { return Nodes.end(); } 403*06f32e7eSjoerg nodes_begin()404*06f32e7eSjoerg const_node_iterator nodes_begin() const { return Nodes.begin(); } 405*06f32e7eSjoerg nodes_end()406*06f32e7eSjoerg const_node_iterator nodes_end() const { return Nodes.end(); } 407*06f32e7eSjoerg roots_begin()408*06f32e7eSjoerg roots_iterator roots_begin() { return Roots.begin(); } 409*06f32e7eSjoerg roots_end()410*06f32e7eSjoerg roots_iterator roots_end() { return Roots.end(); } 411*06f32e7eSjoerg roots_begin()412*06f32e7eSjoerg const_roots_iterator roots_begin() const { return Roots.begin(); } 413*06f32e7eSjoerg roots_end()414*06f32e7eSjoerg const_roots_iterator roots_end() const { return Roots.end(); } 415*06f32e7eSjoerg eop_begin()416*06f32e7eSjoerg eop_iterator eop_begin() { return EndNodes.begin(); } 417*06f32e7eSjoerg eop_end()418*06f32e7eSjoerg eop_iterator eop_end() { return EndNodes.end(); } 419*06f32e7eSjoerg eop_begin()420*06f32e7eSjoerg const_eop_iterator eop_begin() const { return EndNodes.begin(); } 421*06f32e7eSjoerg eop_end()422*06f32e7eSjoerg const_eop_iterator eop_end() const { return EndNodes.end(); } 423*06f32e7eSjoerg getAllocator()424*06f32e7eSjoerg llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } getNodeAllocator()425*06f32e7eSjoerg BumpVectorContext &getNodeAllocator() { return BVC; } 426*06f32e7eSjoerg 427*06f32e7eSjoerg using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>; 428*06f32e7eSjoerg 429*06f32e7eSjoerg /// Creates a trimmed version of the graph that only contains paths leading 430*06f32e7eSjoerg /// to the given nodes. 431*06f32e7eSjoerg /// 432*06f32e7eSjoerg /// \param Nodes The nodes which must appear in the final graph. Presumably 433*06f32e7eSjoerg /// these are end-of-path nodes (i.e. they have no successors). 434*06f32e7eSjoerg /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in 435*06f32e7eSjoerg /// the returned graph. 436*06f32e7eSjoerg /// \param[out] InverseMap An optional map from nodes in the returned graph to 437*06f32e7eSjoerg /// nodes in this graph. 438*06f32e7eSjoerg /// \returns The trimmed graph 439*06f32e7eSjoerg std::unique_ptr<ExplodedGraph> 440*06f32e7eSjoerg trim(ArrayRef<const NodeTy *> Nodes, 441*06f32e7eSjoerg InterExplodedGraphMap *ForwardMap = nullptr, 442*06f32e7eSjoerg InterExplodedGraphMap *InverseMap = nullptr) const; 443*06f32e7eSjoerg 444*06f32e7eSjoerg /// Enable tracking of recently allocated nodes for potential reclamation 445*06f32e7eSjoerg /// when calling reclaimRecentlyAllocatedNodes(). enableNodeReclamation(unsigned Interval)446*06f32e7eSjoerg void enableNodeReclamation(unsigned Interval) { 447*06f32e7eSjoerg ReclaimCounter = ReclaimNodeInterval = Interval; 448*06f32e7eSjoerg } 449*06f32e7eSjoerg 450*06f32e7eSjoerg /// Reclaim "uninteresting" nodes created since the last time this method 451*06f32e7eSjoerg /// was called. 452*06f32e7eSjoerg void reclaimRecentlyAllocatedNodes(); 453*06f32e7eSjoerg 454*06f32e7eSjoerg /// Returns true if nodes for the given expression kind are always 455*06f32e7eSjoerg /// kept around. 456*06f32e7eSjoerg static bool isInterestingLValueExpr(const Expr *Ex); 457*06f32e7eSjoerg 458*06f32e7eSjoerg private: 459*06f32e7eSjoerg bool shouldCollect(const ExplodedNode *node); 460*06f32e7eSjoerg void collectNode(ExplodedNode *node); 461*06f32e7eSjoerg }; 462*06f32e7eSjoerg 463*06f32e7eSjoerg class ExplodedNodeSet { 464*06f32e7eSjoerg using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>; 465*06f32e7eSjoerg ImplTy Impl; 466*06f32e7eSjoerg 467*06f32e7eSjoerg public: ExplodedNodeSet(ExplodedNode * N)468*06f32e7eSjoerg ExplodedNodeSet(ExplodedNode *N) { 469*06f32e7eSjoerg assert(N && !static_cast<ExplodedNode*>(N)->isSink()); 470*06f32e7eSjoerg Impl.insert(N); 471*06f32e7eSjoerg } 472*06f32e7eSjoerg 473*06f32e7eSjoerg ExplodedNodeSet() = default; 474*06f32e7eSjoerg Add(ExplodedNode * N)475*06f32e7eSjoerg void Add(ExplodedNode *N) { 476*06f32e7eSjoerg if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); 477*06f32e7eSjoerg } 478*06f32e7eSjoerg 479*06f32e7eSjoerg using iterator = ImplTy::iterator; 480*06f32e7eSjoerg using const_iterator = ImplTy::const_iterator; 481*06f32e7eSjoerg size()482*06f32e7eSjoerg unsigned size() const { return Impl.size(); } empty()483*06f32e7eSjoerg bool empty() const { return Impl.empty(); } erase(ExplodedNode * N)484*06f32e7eSjoerg bool erase(ExplodedNode *N) { return Impl.remove(N); } 485*06f32e7eSjoerg clear()486*06f32e7eSjoerg void clear() { Impl.clear(); } 487*06f32e7eSjoerg insert(const ExplodedNodeSet & S)488*06f32e7eSjoerg void insert(const ExplodedNodeSet &S) { 489*06f32e7eSjoerg assert(&S != this); 490*06f32e7eSjoerg if (empty()) 491*06f32e7eSjoerg Impl = S.Impl; 492*06f32e7eSjoerg else 493*06f32e7eSjoerg Impl.insert(S.begin(), S.end()); 494*06f32e7eSjoerg } 495*06f32e7eSjoerg begin()496*06f32e7eSjoerg iterator begin() { return Impl.begin(); } end()497*06f32e7eSjoerg iterator end() { return Impl.end(); } 498*06f32e7eSjoerg begin()499*06f32e7eSjoerg const_iterator begin() const { return Impl.begin(); } end()500*06f32e7eSjoerg const_iterator end() const { return Impl.end(); } 501*06f32e7eSjoerg }; 502*06f32e7eSjoerg 503*06f32e7eSjoerg } // namespace ento 504*06f32e7eSjoerg 505*06f32e7eSjoerg } // namespace clang 506*06f32e7eSjoerg 507*06f32e7eSjoerg // GraphTraits 508*06f32e7eSjoerg 509*06f32e7eSjoerg namespace llvm { 510*06f32e7eSjoerg template <> struct GraphTraits<clang::ento::ExplodedGraph *> { 511*06f32e7eSjoerg using GraphTy = clang::ento::ExplodedGraph *; 512*06f32e7eSjoerg using NodeRef = clang::ento::ExplodedNode *; 513*06f32e7eSjoerg using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; 514*06f32e7eSjoerg using nodes_iterator = llvm::df_iterator<GraphTy>; 515*06f32e7eSjoerg 516*06f32e7eSjoerg static NodeRef getEntryNode(const GraphTy G) { 517*06f32e7eSjoerg return *G->roots_begin(); 518*06f32e7eSjoerg } 519*06f32e7eSjoerg 520*06f32e7eSjoerg static bool predecessorOfTrivial(NodeRef N) { 521*06f32e7eSjoerg return N->succ_size() == 1 && N->getFirstSucc()->isTrivial(); 522*06f32e7eSjoerg } 523*06f32e7eSjoerg 524*06f32e7eSjoerg static ChildIteratorType child_begin(NodeRef N) { 525*06f32e7eSjoerg if (predecessorOfTrivial(N)) 526*06f32e7eSjoerg return child_begin(*N->succ_begin()); 527*06f32e7eSjoerg return N->succ_begin(); 528*06f32e7eSjoerg } 529*06f32e7eSjoerg 530*06f32e7eSjoerg static ChildIteratorType child_end(NodeRef N) { 531*06f32e7eSjoerg if (predecessorOfTrivial(N)) 532*06f32e7eSjoerg return child_end(N->getFirstSucc()); 533*06f32e7eSjoerg return N->succ_end(); 534*06f32e7eSjoerg } 535*06f32e7eSjoerg 536*06f32e7eSjoerg static nodes_iterator nodes_begin(const GraphTy G) { 537*06f32e7eSjoerg return df_begin(G); 538*06f32e7eSjoerg } 539*06f32e7eSjoerg 540*06f32e7eSjoerg static nodes_iterator nodes_end(const GraphTy G) { 541*06f32e7eSjoerg return df_end(G); 542*06f32e7eSjoerg } 543*06f32e7eSjoerg }; 544*06f32e7eSjoerg } // namespace llvm 545*06f32e7eSjoerg 546*06f32e7eSjoerg #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 547