clang 20.0.0git
Public Types | Public Member Functions | Static Public Member Functions | Protected Types | Protected Attributes | Friends | List of all members
clang::ento::ExplodedGraph Class Reference

#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"

Public Types

using NodeTy = ExplodedNode
 
using AllNodesTy = llvm::FoldingSet< ExplodedNode >
 
using roots_iterator = NodeVector::iterator
 
using const_roots_iterator = NodeVector::const_iterator
 
using eop_iterator = NodeVector::iterator
 
using const_eop_iterator = NodeVector::const_iterator
 
using node_iterator = AllNodesTy::iterator
 
using const_node_iterator = AllNodesTy::const_iterator
 
using NodeMap = llvm::DenseMap< const ExplodedNode *, ExplodedNode * >
 

Public Member Functions

 ExplodedGraph ()
 
 ~ExplodedGraph ()
 
ExplodedNodegetNode (const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
 Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in the CFG.
 
ExplodedNodecreateUncachedNode (const ProgramPoint &L, ProgramStateRef State, int64_t Id, bool IsSink=false)
 Create a node for a (Location, State) pair, but don't store it for deduplication later.
 
std::unique_ptr< ExplodedGraphMakeEmptyGraph () const
 
ExplodedNodeaddRoot (ExplodedNode *V)
 addRoot - Add an untyped node to the set of roots.
 
ExplodedNodeaddEndOfPath (ExplodedNode *V)
 addEndOfPath - Add an untyped node to the set of EOP nodes.
 
unsigned num_roots () const
 
unsigned num_eops () const
 
bool empty () const
 
unsigned size () const
 
void reserve (unsigned NodeCount)
 
llvm::iterator_range< node_iteratornodes ()
 
llvm::iterator_range< const_node_iteratornodes () const
 
roots_iterator roots_begin ()
 
roots_iterator roots_end ()
 
const_roots_iterator roots_begin () const
 
const_roots_iterator roots_end () const
 
eop_iterator eop_begin ()
 
eop_iterator eop_end ()
 
const_eop_iterator eop_begin () const
 
const_eop_iterator eop_end () const
 
llvm::BumpPtrAllocator & getAllocator ()
 
BumpVectorContextgetNodeAllocator ()
 
std::unique_ptr< ExplodedGraphtrim (ArrayRef< const NodeTy * > Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
 Creates a trimmed version of the graph that only contains paths leading to the given nodes.
 
void enableNodeReclamation (unsigned Interval)
 Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAllocatedNodes().
 
void reclaimRecentlyAllocatedNodes ()
 Reclaim "uninteresting" nodes created since the last time this method was called.
 

Static Public Member Functions

static bool isInterestingLValueExpr (const Expr *Ex)
 Returns true if nodes for the given expression kind are always kept around.
 

Protected Types

using NodeVector = std::vector< ExplodedNode * >
 

Protected Attributes

NodeVector Roots
 The roots of the simulation graph.
 
NodeVector EndNodes
 The nodes in the simulation graph which have been specially marked as the endpoint of an abstract simulation path.
 
llvm::FoldingSet< ExplodedNodeNodes
 Nodes - The nodes in the graph.
 
BumpVectorContext BVC
 BVC - Allocator and context for allocating nodes and their predecessor and successor groups.
 
int64_t NumNodes = 0
 NumNodes - The number of nodes in the graph.
 
NodeVector ChangedNodes
 A list of recently allocated nodes that can potentially be recycled.
 
NodeVector FreeNodes
 A list of nodes that can be reused.
 
unsigned ReclaimNodeInterval = 0
 Determines how often nodes are reclaimed.
 
unsigned ReclaimCounter
 Counter to determine when to reclaim nodes.
 

Friends

class CoreEngine
 

Detailed Description

Definition at line 303 of file ExplodedGraph.h.

Member Typedef Documentation

◆ AllNodesTy

Definition at line 391 of file ExplodedGraph.h.

◆ const_eop_iterator

using clang::ento::ExplodedGraph::const_eop_iterator = NodeVector::const_iterator

Definition at line 395 of file ExplodedGraph.h.

◆ const_node_iterator

using clang::ento::ExplodedGraph::const_node_iterator = AllNodesTy::const_iterator

Definition at line 397 of file ExplodedGraph.h.

◆ const_roots_iterator

using clang::ento::ExplodedGraph::const_roots_iterator = NodeVector::const_iterator

Definition at line 393 of file ExplodedGraph.h.

◆ eop_iterator

using clang::ento::ExplodedGraph::eop_iterator = NodeVector::iterator

Definition at line 394 of file ExplodedGraph.h.

◆ node_iterator

using clang::ento::ExplodedGraph::node_iterator = AllNodesTy::iterator

Definition at line 396 of file ExplodedGraph.h.

◆ NodeMap

Definition at line 422 of file ExplodedGraph.h.

◆ NodeTy

Definition at line 390 of file ExplodedGraph.h.

◆ NodeVector

using clang::ento::ExplodedGraph::NodeVector = std::vector<ExplodedNode *>
protected

Definition at line 308 of file ExplodedGraph.h.

◆ roots_iterator

using clang::ento::ExplodedGraph::roots_iterator = NodeVector::iterator

Definition at line 392 of file ExplodedGraph.h.

Constructor & Destructor Documentation

◆ ExplodedGraph()

ExplodedGraph::ExplodedGraph ( )
default

◆ ~ExplodedGraph()

ExplodedGraph::~ExplodedGraph ( )
default

Member Function Documentation

◆ addEndOfPath()

ExplodedNode * clang::ento::ExplodedGraph::addEndOfPath ( ExplodedNode V)
inline

addEndOfPath - Add an untyped node to the set of EOP nodes.

Definition at line 376 of file ExplodedGraph.h.

References EndNodes, and V.

Referenced by clang::ento::CoreEngine::enqueueEndOfFunction().

◆ addRoot()

ExplodedNode * clang::ento::ExplodedGraph::addRoot ( ExplodedNode V)
inline

addRoot - Add an untyped node to the set of roots.

Definition at line 370 of file ExplodedGraph.h.

References Roots, and V.

Referenced by clang::ento::CoreEngine::ExecuteWorkList().

◆ createUncachedNode()

ExplodedNode * ExplodedGraph::createUncachedNode ( const ProgramPoint L,
ProgramStateRef  State,
int64_t  Id,
bool  IsSink = false 
)

Create a node for a (Location, State) pair, but don't store it for deduplication later.

This is useful when copying an already completed ExplodedGraph for further processing.

Definition at line 430 of file ExplodedGraph.cpp.

References getAllocator(), Id, and V.

◆ empty()

bool clang::ento::ExplodedGraph::empty ( ) const
inline

Definition at line 384 of file ExplodedGraph.h.

References NumNodes.

◆ enableNodeReclamation()

void clang::ento::ExplodedGraph::enableNodeReclamation ( unsigned  Interval)
inline

Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAllocatedNodes().

Definition at line 441 of file ExplodedGraph.h.

References ReclaimCounter, and ReclaimNodeInterval.

Referenced by clang::ento::ExprEngine::ExprEngine().

◆ eop_begin() [1/2]

eop_iterator clang::ento::ExplodedGraph::eop_begin ( )
inline

Definition at line 411 of file ExplodedGraph.h.

References EndNodes.

◆ eop_begin() [2/2]

const_eop_iterator clang::ento::ExplodedGraph::eop_begin ( ) const
inline

Definition at line 415 of file ExplodedGraph.h.

References EndNodes.

◆ eop_end() [1/2]

eop_iterator clang::ento::ExplodedGraph::eop_end ( )
inline

Definition at line 413 of file ExplodedGraph.h.

References EndNodes.

◆ eop_end() [2/2]

const_eop_iterator clang::ento::ExplodedGraph::eop_end ( ) const
inline

Definition at line 417 of file ExplodedGraph.h.

References EndNodes.

◆ getAllocator()

llvm::BumpPtrAllocator & clang::ento::ExplodedGraph::getAllocator ( )
inline

Definition at line 419 of file ExplodedGraph.h.

References BVC, and clang::BumpVectorContext::getAllocator().

Referenced by createUncachedNode(), and getNode().

◆ getNode()

ExplodedNode * ExplodedGraph::getNode ( const ProgramPoint L,
ProgramStateRef  State,
bool  IsSink = false,
bool IsNew = nullptr 
)

◆ getNodeAllocator()

BumpVectorContext & clang::ento::ExplodedGraph::getNodeAllocator ( )
inline

Definition at line 420 of file ExplodedGraph.h.

References BVC.

◆ isInterestingLValueExpr()

bool ExplodedGraph::isInterestingLValueExpr ( const Expr Ex)
static

Returns true if nodes for the given expression kind are always kept around.

Definition at line 50 of file ExplodedGraph.cpp.

References clang::Expr::isLValue().

◆ MakeEmptyGraph()

std::unique_ptr< ExplodedGraph > clang::ento::ExplodedGraph::MakeEmptyGraph ( ) const
inline

Definition at line 365 of file ExplodedGraph.h.

Referenced by trim().

◆ nodes() [1/2]

llvm::iterator_range< node_iterator > clang::ento::ExplodedGraph::nodes ( )
inline

Definition at line 399 of file ExplodedGraph.h.

References Nodes.

◆ nodes() [2/2]

llvm::iterator_range< const_node_iterator > clang::ento::ExplodedGraph::nodes ( ) const
inline

Definition at line 401 of file ExplodedGraph.h.

References Nodes.

◆ num_eops()

unsigned clang::ento::ExplodedGraph::num_eops ( ) const
inline

Definition at line 382 of file ExplodedGraph.h.

References EndNodes.

◆ num_roots()

unsigned clang::ento::ExplodedGraph::num_roots ( ) const
inline

Definition at line 381 of file ExplodedGraph.h.

References Roots.

Referenced by clang::ento::CoreEngine::ExecuteWorkList().

◆ reclaimRecentlyAllocatedNodes()

void ExplodedGraph::reclaimRecentlyAllocatedNodes ( )

Reclaim "uninteresting" nodes created since the last time this method was called.

Definition at line 169 of file ExplodedGraph.cpp.

References ChangedNodes, ReclaimCounter, and ReclaimNodeInterval.

Referenced by clang::ento::ExprEngine::ProcessStmt().

◆ reserve()

void clang::ento::ExplodedGraph::reserve ( unsigned  NodeCount)
inline

Definition at line 387 of file ExplodedGraph.h.

References Nodes.

Referenced by clang::ento::CoreEngine::ExecuteWorkList().

◆ roots_begin() [1/2]

roots_iterator clang::ento::ExplodedGraph::roots_begin ( )
inline

◆ roots_begin() [2/2]

const_roots_iterator clang::ento::ExplodedGraph::roots_begin ( ) const
inline

Definition at line 407 of file ExplodedGraph.h.

References Roots.

◆ roots_end() [1/2]

roots_iterator clang::ento::ExplodedGraph::roots_end ( )
inline

Definition at line 405 of file ExplodedGraph.h.

References Roots.

Referenced by clang::ento::ExprEngine::getRootLocationContext().

◆ roots_end() [2/2]

const_roots_iterator clang::ento::ExplodedGraph::roots_end ( ) const
inline

Definition at line 409 of file ExplodedGraph.h.

References Roots.

◆ size()

unsigned clang::ento::ExplodedGraph::size ( ) const
inline

Definition at line 385 of file ExplodedGraph.h.

References NumNodes.

◆ trim()

std::unique_ptr< ExplodedGraph > ExplodedGraph::trim ( ArrayRef< const NodeTy * >  Nodes,
InterExplodedGraphMap ForwardMap = nullptr,
InterExplodedGraphMap InverseMap = nullptr 
) const

Creates a trimmed version of the graph that only contains paths leading to the given nodes.

Parameters
NodesThe nodes which must appear in the final graph. Presumably these are end-of-path nodes (i.e. they have no successors).
[out]ForwardMapA optional map from nodes in this graph to nodes in the returned graph.
[out]InverseMapAn optional map from nodes in the returned graph to nodes in this graph.
Returns
The trimmed graph

Definition at line 440 of file ExplodedGraph.cpp.

References clang::ento::ExplodedNode::addPredecessor(), clang::ento::ExplodedNode::getID(), clang::ento::ExplodedNode::getLocation(), clang::ento::ExplodedNode::isSink(), MakeEmptyGraph(), and Nodes.

Referenced by clang::ento::ExprEngine::DumpGraph().

Friends And Related Function Documentation

◆ CoreEngine

friend class CoreEngine
friend

Definition at line 305 of file ExplodedGraph.h.

Member Data Documentation

◆ BVC

BumpVectorContext clang::ento::ExplodedGraph::BVC
protected

BVC - Allocator and context for allocating nodes and their predecessor and successor groups.

Definition at line 325 of file ExplodedGraph.h.

Referenced by getAllocator(), and getNodeAllocator().

◆ ChangedNodes

NodeVector clang::ento::ExplodedGraph::ChangedNodes
protected

A list of recently allocated nodes that can potentially be recycled.

Definition at line 331 of file ExplodedGraph.h.

Referenced by getNode(), and reclaimRecentlyAllocatedNodes().

◆ EndNodes

NodeVector clang::ento::ExplodedGraph::EndNodes
protected

The nodes in the simulation graph which have been specially marked as the endpoint of an abstract simulation path.

Definition at line 318 of file ExplodedGraph.h.

Referenced by addEndOfPath(), eop_begin(), eop_end(), and num_eops().

◆ FreeNodes

NodeVector clang::ento::ExplodedGraph::FreeNodes
protected

A list of nodes that can be reused.

Definition at line 334 of file ExplodedGraph.h.

Referenced by getNode().

◆ Nodes

llvm::FoldingSet<ExplodedNode> clang::ento::ExplodedGraph::Nodes
protected

Nodes - The nodes in the graph.

Definition at line 321 of file ExplodedGraph.h.

Referenced by getNode(), nodes(), reserve(), and trim().

◆ NumNodes

int64_t clang::ento::ExplodedGraph::NumNodes = 0
protected

NumNodes - The number of nodes in the graph.

Definition at line 328 of file ExplodedGraph.h.

Referenced by empty(), getNode(), and size().

◆ ReclaimCounter

unsigned clang::ento::ExplodedGraph::ReclaimCounter
protected

Counter to determine when to reclaim nodes.

Definition at line 342 of file ExplodedGraph.h.

Referenced by enableNodeReclamation(), and reclaimRecentlyAllocatedNodes().

◆ ReclaimNodeInterval

unsigned clang::ento::ExplodedGraph::ReclaimNodeInterval = 0
protected

Determines how often nodes are reclaimed.

If this is 0, nodes will never be reclaimed.

Definition at line 339 of file ExplodedGraph.h.

Referenced by enableNodeReclamation(), getNode(), and reclaimRecentlyAllocatedNodes().

◆ Roots

NodeVector clang::ento::ExplodedGraph::Roots
protected

The roots of the simulation graph.

Usually there will be only one, but clients are free to establish multiple subgraphs within a single SimulGraph. Moreover, these subgraphs can often merge when paths from different roots reach the same state at the same program location.

Definition at line 314 of file ExplodedGraph.h.

Referenced by addRoot(), num_roots(), roots_begin(), and roots_end().


The documentation for this class was generated from the following files: