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

Collaboration diagram for clang::ento::ExplodedGraph:

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 ()

ExplodedNode *	getNode (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. More...

ExplodedNode *	createUncachedNode (const ProgramPoint &L, ProgramStateRef State, bool IsSink=false)
	Create a node for a (Location, State) pair, but don't store it for deduplication later. More...

std::unique_ptr< ExplodedGraph >	MakeEmptyGraph () const

ExplodedNode *	addRoot (ExplodedNode *V)
	addRoot - Add an untyped node to the set of roots. More...

ExplodedNode *	addEndOfPath (ExplodedNode *V)
	addEndOfPath - Add an untyped node to the set of EOP nodes. More...

unsigned	num_roots () const

unsigned	num_eops () const

bool	empty () const

unsigned	size () const

void	reserve (unsigned NodeCount)

node_iterator	nodes_begin ()

node_iterator	nodes_end ()

const_node_iterator	nodes_begin () const

const_node_iterator	nodes_end () 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 ()

BumpVectorContext &	getNodeAllocator ()

std::unique_ptr< 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. More...

void	enableNodeReclamation (unsigned Interval)
	Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAllocatedNodes(). More...

void	reclaimRecentlyAllocatedNodes ()
	Reclaim "uninteresting" nodes created since the last time this method was called. More...

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

Protected Types
using	NodeVector = std::vector< ExplodedNode * >

Protected Attributes
NodeVector	Roots
	The roots of the simulation graph. More...

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

llvm::FoldingSet< ExplodedNode >	Nodes
	Nodes - The nodes in the graph. More...

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

unsigned	NumNodes = 0
	NumNodes - The number of nodes in the graph. More...

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

NodeVector	FreeNodes
	A list of nodes that can be reused. More...

unsigned	ReclaimNodeInterval = 0
	Determines how often nodes are reclaimed. More...

unsigned	ReclaimCounter
	Counter to determine when to reclaim nodes. More...

Friends
class	CoreEngine

Detailed Description

Definition at line 258 of file ExplodedGraph.h.

Member Typedef Documentation

◆ AllNodesTy

using clang::ento::ExplodedGraph::AllNodesTy = llvm::FoldingSet<ExplodedNode>

Definition at line 345 of file ExplodedGraph.h.

◆ const_eop_iterator

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

Definition at line 349 of file ExplodedGraph.h.

◆ const_node_iterator

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

Definition at line 351 of file ExplodedGraph.h.

◆ const_roots_iterator

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

Definition at line 347 of file ExplodedGraph.h.

◆ eop_iterator

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

Definition at line 348 of file ExplodedGraph.h.

◆ node_iterator

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

Definition at line 350 of file ExplodedGraph.h.

◆ NodeMap

using clang::ento::ExplodedGraph::NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>

Definition at line 380 of file ExplodedGraph.h.

◆ NodeTy

using clang::ento::ExplodedGraph::NodeTy = ExplodedNode

Definition at line 344 of file ExplodedGraph.h.

◆ NodeVector

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

protected

Definition at line 263 of file ExplodedGraph.h.

◆ roots_iterator

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

Definition at line 346 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 330 of file ExplodedGraph.h.

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 324 of file ExplodedGraph.h.

Referenced by clang::ento::CoreEngine::ExecuteWorkList(), and clang::ento::CoreEngine::ExecuteWorkListWithInitialState().

◆ createUncachedNode()

ExplodedNode * ExplodedGraph::createUncachedNode	(	const ProgramPoint &	L,
		ProgramStateRef	State,
		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 336 of file ExplodedGraph.cpp.

References getAllocator().

◆ empty()

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

inline

Definition at line 338 of file ExplodedGraph.h.

◆ enableNodeReclamation()

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

inline

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

Definition at line 399 of file ExplodedGraph.h.

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

◆ eop_begin() [1/2]

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

inline

Definition at line 369 of file ExplodedGraph.h.

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

◆ eop_begin() [2/2]

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

inline

Definition at line 373 of file ExplodedGraph.h.

◆ eop_end() [1/2]

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

inline

Definition at line 371 of file ExplodedGraph.h.

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

◆ eop_end() [2/2]

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

inline

Definition at line 375 of file ExplodedGraph.h.

◆ getAllocator()

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

inline

Definition at line 377 of file ExplodedGraph.h.

References clang::BumpVectorContext::getAllocator().

Referenced by clang::ento::ExplodedNode::addPredecessor(), createUncachedNode(), clang::ento::ExplodedNode::getID(), and getNode().

◆ getNode()

ExplodedNode * ExplodedGraph::getNode	(	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.

If no node for this pair exists, it is created. IsNew is set to true if the node was freshly created.

Definition at line 298 of file ExplodedGraph.cpp.

References ChangedNodes, FreeNodes, getAllocator(), Nodes, NumNodes, clang::ento::ExplodedNode::Profile(), and ReclaimNodeInterval.

Referenced by clang::ento::CoreEngine::enqueueStmtNode(), clang::ento::CoreEngine::ExecuteWorkList(), clang::ento::CoreEngine::ExecuteWorkListWithInitialState(), clang::ento::ExprEngine::processCallEnter(), and clang::ento::ExprEngine::processCallExit().

◆ getNodeAllocator()

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

inline

Definition at line 378 of file ExplodedGraph.h.

Referenced by clang::ento::ExplodedNode::addPredecessor().

◆ 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::ProgramPoint::castAs(), FreeNodes, clang::ProgramPoint::getAs(), clang::ento::ExplodedNode::getLocation(), clang::ento::ExplodedNode::getLocationContext(), clang::ProgramPoint::getLocationContext(), clang::LocationContext::getParentMap(), clang::ento::ExplodedNode::getState(), clang::ProgramPoint::getTag(), clang::ento::CallEvent::isCallStmt(), clang::ParentMap::isConsumedExpr(), clang::Expr::isLValue(), Nodes, NumNodes, clang::ento::ExplodedNode::pred_begin(), clang::ento::ExplodedNode::pred_size(), clang::CodeGen::state, clang::ento::ExplodedNode::succ_begin(), and clang::ento::ExplodedNode::succ_size().

◆ MakeEmptyGraph()

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

inline

Definition at line 319 of file ExplodedGraph.h.

Referenced by trim().

◆ nodes_begin() [1/2]

node_iterator clang::ento::ExplodedGraph::nodes_begin ( )

inline

Definition at line 353 of file ExplodedGraph.h.

◆ nodes_begin() [2/2]

const_node_iterator clang::ento::ExplodedGraph::nodes_begin ( ) const

inline

Definition at line 357 of file ExplodedGraph.h.

◆ nodes_end() [1/2]

node_iterator clang::ento::ExplodedGraph::nodes_end ( )

inline

Definition at line 355 of file ExplodedGraph.h.

◆ nodes_end() [2/2]

const_node_iterator clang::ento::ExplodedGraph::nodes_end ( ) const

inline

Definition at line 359 of file ExplodedGraph.h.

◆ num_eops()

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

inline

Definition at line 336 of file ExplodedGraph.h.

◆ num_roots()

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

inline

Definition at line 335 of file ExplodedGraph.h.

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 171 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 341 of file ExplodedGraph.h.

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

◆ roots_begin() [1/2]

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

inline

Definition at line 361 of file ExplodedGraph.h.

Referenced by llvm::GraphTraits< clang::ento::ExplodedGraph * >::getEntryNode().

◆ roots_begin() [2/2]

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

inline

Definition at line 365 of file ExplodedGraph.h.

◆ roots_end() [1/2]

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

inline

Definition at line 363 of file ExplodedGraph.h.

◆ roots_end() [2/2]

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

inline

Definition at line 367 of file ExplodedGraph.h.

◆ size()

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

inline

Definition at line 339 of file ExplodedGraph.h.

◆ 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

	Nodes	The nodes which must appear in the final graph. Presumably these are end-of-path nodes (i.e. they have no successors).
[out]	ForwardMap	A optional map from nodes in this graph to nodes in the returned graph.
[out]	InverseMap	An optional map from nodes in the returned graph to nodes in this graph.

Returns: The trimmed graph

Definition at line 345 of file ExplodedGraph.cpp.

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

Friends And Related Function Documentation

◆ CoreEngine

friend class CoreEngine

friend

Definition at line 260 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 280 of file ExplodedGraph.h.

◆ ChangedNodes

NodeVector clang::ento::ExplodedGraph::ChangedNodes

protected

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

Definition at line 286 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 273 of file ExplodedGraph.h.

◆ FreeNodes

NodeVector clang::ento::ExplodedGraph::FreeNodes

protected

A list of nodes that can be reused.

Definition at line 289 of file ExplodedGraph.h.

Referenced by getNode(), and isInterestingLValueExpr().

◆ Nodes

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

protected

Nodes - The nodes in the graph.

Definition at line 276 of file ExplodedGraph.h.

Referenced by getNode(), isInterestingLValueExpr(), and trim().

◆ NumNodes

unsigned clang::ento::ExplodedGraph::NumNodes = 0

protected

NumNodes - The number of nodes in the graph.

Definition at line 283 of file ExplodedGraph.h.

Referenced by getNode(), and isInterestingLValueExpr().

◆ ReclaimCounter

unsigned clang::ento::ExplodedGraph::ReclaimCounter

protected

Counter to determine when to reclaim nodes.

Definition at line 297 of file ExplodedGraph.h.

Referenced by 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 294 of file ExplodedGraph.h.

Referenced by 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 269 of file ExplodedGraph.h.

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

include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
lib/StaticAnalyzer/Core/ExplodedGraph.cpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ AllNodesTy

◆ const_eop_iterator

◆ const_node_iterator

◆ const_roots_iterator

◆ eop_iterator

◆ node_iterator

◆ NodeMap

◆ NodeTy

◆ NodeVector

◆ roots_iterator

Constructor & Destructor Documentation

◆ ExplodedGraph()

◆ ~ExplodedGraph()

Member Function Documentation

◆ addEndOfPath()

◆ addRoot()

◆ createUncachedNode()

◆ empty()

◆ enableNodeReclamation()

◆ eop_begin() [1/2]

◆ eop_begin() [2/2]

◆ eop_end() [1/2]

◆ eop_end() [2/2]

◆ getAllocator()

◆ getNode()

◆ getNodeAllocator()

◆ isInterestingLValueExpr()

◆ MakeEmptyGraph()

◆ nodes_begin() [1/2]

◆ nodes_begin() [2/2]

◆ nodes_end() [1/2]

◆ nodes_end() [2/2]

◆ num_eops()

◆ num_roots()

◆ reclaimRecentlyAllocatedNodes()

◆ reserve()

◆ roots_begin() [1/2]

◆ roots_begin() [2/2]

◆ roots_end() [1/2]

◆ roots_end() [2/2]

◆ size()

◆ trim()

Friends And Related Function Documentation

◆ CoreEngine

Member Data Documentation

◆ BVC

◆ ChangedNodes

◆ EndNodes

◆ FreeNodes

◆ Nodes

◆ NumNodes

◆ ReclaimCounter

◆ ReclaimNodeInterval

◆ Roots