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