Control Flow Graphs (CFGs)

Interprocedural control flow graph, with vertices of type Block. More...

Files
file	CFG.hpp
	Types and operations for interprocedural control flow graphs (CFGs).
file	CfgNode.hpp
	Base class for nodes of the CFG.
file	CodeBlock.hpp
	Class gtirb::CodeBlock.
file	ProxyBlock.hpp
	Class gtirb::ProxyBlock.

Typedefs
using	gtirb::block_iterator = cfg_node_cast_iter< CodeBlock >
	Iterator over blocks (Block). More...
using	gtirb::CFG = CfgBuilder< boost::listS, boost::listS, boost::bidirectionalS >::type
	Interprocedural control flow graph, with vertices of type Block. More...
using	gtirb::cfg_iterator = boost::indirect_iterator< cfg_node_iter_base >
	Iterator over CfgNodes (CfgNode). More...
using	gtirb::const_block_iterator = cfg_node_cast_iter< const CodeBlock >
	Constant iterator over blocks (Block). More...
using	gtirb::const_cfg_iterator = boost::indirect_iterator< cfg_node_iter_base, const CfgNode >
	Const iterator over CfgNodes (CfgNode). More...
using	gtirb::EdgeLabel = std::optional< std::tuple< ConditionalEdge, DirectEdge, EdgeType > >
	A label on a CFG edge. More...

Enumerations
enum	gtirb::ConditionalEdge : bool { gtirb::ConditionalEdge::OnFalse, gtirb::ConditionalEdge::OnTrue }
	Indicates whether an edge is conditional on true. More...
enum	gtirb::DirectEdge : bool { gtirb::DirectEdge::IsIndirect, gtirb::DirectEdge::IsDirect }
	Indicates whether an edge represents indirect control flow. More...
enum	gtirb::EdgeType {   gtirb::EdgeType::Branch, gtirb::EdgeType::Call, gtirb::EdgeType::Fallthrough, gtirb::EdgeType::Return,   gtirb::EdgeType::Syscall, gtirb::EdgeType::Sysret }
	Indicates the type of control flow transfer indicated by this edge. More...

Functions
GTIRB_EXPORT_API std::optional< CFG::edge_descriptor >	gtirb::addEdge (const CfgNode *From, const CfgNode *To, CFG &Cfg)
	Create a new edge between two CFG nodes if they exist in the graph. More...
GTIRB_EXPORT_API std::pair< CFG::vertex_descriptor, bool >	gtirb::addVertex (CfgNode *B, CFG &Cfg)
	Add a node to the CFG. More...
GTIRB_EXPORT_API boost::iterator_range< block_iterator >	gtirb::blocks (CFG &Cfg)
	Get a range of just the Block elements in the specified graph. More...
GTIRB_EXPORT_API boost::iterator_range< const_block_iterator >	gtirb::blocks (const CFG &Cfg)
	Get a constant range of just the Block elements in the specified graph. More...
cfg_predecessors_range	gtirb::cfgPredecessors (CFG &G, const CfgNode *N)
	Returns an iterator_range to iterate the predecessors of a CfgNode. More...
cfg_successors_range	gtirb::cfgSuccessors (CFG &G, const CfgNode *N)
	Returns an iterator_range to iterate the successors of a CfgNode. More...
GTIRB_EXPORT_API std::optional< CFG::vertex_descriptor >	gtirb::getVertex (const CfgNode *N, const CFG &Cfg)
	Get the boost::graph vertex descriptor for a CfgNode if it is in the graph. More...
GTIRB_EXPORT_API boost::iterator_range< cfg_iterator >	gtirb::nodes (CFG &Cfg)
	Get a range of the CfgNode elements in the specified graph. More...
GTIRB_EXPORT_API boost::iterator_range< const_cfg_iterator >	gtirb::nodes (const CFG &Cfg)
	Get a constant range of the CfgNode elements in the specified graph. More...
GTIRB_EXPORT_API bool	gtirb::removeEdge (const CfgNode *From, const CfgNode *To, CFG &Cfg)
	Remove all edges between the source and target nodes from the CFG. More...
GTIRB_EXPORT_API bool	gtirb::removeEdge (const CfgNode *From, const CfgNode *To, EdgeLabel Label, CFG &Cfg)
	Remove all edges with given label between the source and target nodes from the CFG. More...
GTIRB_EXPORT_API bool	gtirb::removeVertex (CfgNode *N, CFG &Cfg)
	Remove a node from the CFG. More...

Detailed Description

Interprocedural control flow graph, with vertices of type Block.

See also md_CFG-Edges.

Typedef Documentation

block_iterator

using gtirb::block_iterator = typedef cfg_node_cast_iter<CodeBlock>

#include <CFG.hpp>

Iterator over blocks (Block).

CFG

using gtirb::CFG = typedef CfgBuilder<boost::listS, boost::listS, boost::bidirectionalS >::type

#include <CFG.hpp>

Interprocedural control flow graph, with vertices of type Block.

cfg_iterator

using gtirb::cfg_iterator = typedef boost::indirect_iterator<cfg_node_iter_base>

#include <CFG.hpp>

Iterator over CfgNodes (CfgNode).

const_block_iterator

using gtirb::const_block_iterator = typedef cfg_node_cast_iter<const CodeBlock>

#include <CFG.hpp>

Constant iterator over blocks (Block).

const_cfg_iterator

using gtirb::const_cfg_iterator = typedef boost::indirect_iterator<cfg_node_iter_base, const CfgNode>

#include <CFG.hpp>

Const iterator over CfgNodes (CfgNode).

EdgeLabel

using gtirb::EdgeLabel = typedef std::optional<std::tuple<ConditionalEdge, DirectEdge, EdgeType> >

#include <CFG.hpp>

A label on a CFG edge.

Enumeration Type Documentation

ConditionalEdge

enum gtirb::ConditionalEdge : bool

strong

#include <CFG.hpp>

Indicates whether an edge is conditional on true.

Enumerator
OnFalse	Indicates an unconditional edge or a conditional edge that fires when the condition is false.
OnTrue	Indicates a conditional edge that fires when the condition is true.

DirectEdge

enum gtirb::DirectEdge : bool

strong

#include <CFG.hpp>

Indicates whether an edge represents indirect control flow.

Enumerator
IsIndirect
IsDirect

EdgeType

enum gtirb::EdgeType

strong

#include <CFG.hpp>

Indicates the type of control flow transfer indicated by this edge.

Enumerator
Branch
Call
Fallthrough
Return
Syscall
Sysret

Function Documentation

addEdge()

GTIRB_EXPORT_API std::optional<CFG::edge_descriptor> gtirb::addEdge	(	const CfgNode *	From,
		const CfgNode *	To,
		CFG &	Cfg
	)

#include <CFG.hpp>

Create a new edge between two CFG nodes if they exist in the graph.

Parameters

Cfg	The graph to modify.
From	The source node.
To	The target node.

Returns

A descriptor which can be used to retrieve the edge from the graph or assign a label. If either CFG node is not present in the graph, returns std::nullopt instead.

addVertex()

GTIRB_EXPORT_API std::pair<CFG::vertex_descriptor, bool> gtirb::addVertex	(	CfgNode *	B,
		CFG &	Cfg
	)

#include <CFG.hpp>

Add a node to the CFG.

If the graph already contains the node, it is not modified.

Parameters

N	The CFG node to add.
Cfg	The graph to modify.

Returns

A pair consisting of a descriptor to the vertex for that node and a bool indicating whether the graph was modified.

blocks() [1/2]

GTIRB_EXPORT_API boost::iterator_range<block_iterator> gtirb::blocks

(

CFG &

Cfg

)

#include <CFG.hpp>

Get a range of just the Block elements in the specified graph.

The returned range will not include any ProxyBlocks. To retrieve those as well, use nodes(CFG&).

Parameters

Cfg	The graph to be iterated over.

Returns

A range over the Blocks in the Cfg

blocks() [2/2]

GTIRB_EXPORT_API boost::iterator_range<const_block_iterator> gtirb::blocks

(

const CFG &

Cfg

)

#include <CFG.hpp>

Get a constant range of just the Block elements in the specified graph.

The returned range will not include any ProxyBlocks. To retrieve those as well, use nodes(CFG&).

Parameters

Cfg	The graph to be iterated over.

Returns

A range over the Blocks in the Cfg

cfgPredecessors()

cfg_predecessors_range gtirb::cfgPredecessors ( CFG &  G, const CfgNode *  N  )

inline

#include <CFG.hpp>

Returns an iterator_range to iterate the predecessors of a CfgNode.

To iterate the predecessors of node N in graph G:

for (auto [PredNode, EdgeLabel] : gtirb::cfgPredecessors(G, N)) { ... }

Parameters

G	The CFG containing N.
N	The CfgNode whose predecessors will be iterated.

Returns

A range over N's predecessors.

cfgSuccessors()

cfg_successors_range gtirb::cfgSuccessors ( CFG &  G, const CfgNode *  N  )

inline

#include <CFG.hpp>

Returns an iterator_range to iterate the successors of a CfgNode.

To iterate the successors of node N in graph G:

for (auto [SuccNode, EdgeLabel] : gtirb::cfgSuccessors(G, N)) { ... }

Parameters

G	The CFG containing N.
N	The CfgNode whose successors will be iterated.

Returns

A range over N's successors.

getVertex()

GTIRB_EXPORT_API std::optional<CFG::vertex_descriptor> gtirb::getVertex	(	const CfgNode *	N,
		const CFG &	Cfg
	)

#include <CFG.hpp>

Get the boost::graph vertex descriptor for a CfgNode if it is in the graph.

Parameters

N	The node to query.
Cfg	The graph to query.

Returns

A descriptor which can be used to retrieve the node from the graph.

nodes() [1/2]

GTIRB_EXPORT_API boost::iterator_range<cfg_iterator> gtirb::nodes

(

CFG &

Cfg

)

#include <CFG.hpp>

Get a range of the CfgNode elements in the specified graph.

Parameters

Cfg	The graph to be iterated over.

Returns

a range over the Cfg.

nodes() [2/2]

GTIRB_EXPORT_API boost::iterator_range<const_cfg_iterator> gtirb::nodes

(

const CFG &

Cfg

)

#include <CFG.hpp>

Get a constant range of the CfgNode elements in the specified graph.

Parameters

Cfg	The graph to be iterated over.

Returns

A range over teh Cfg.

removeEdge() [1/2]

GTIRB_EXPORT_API bool gtirb::removeEdge	(	const CfgNode *	From,
		const CfgNode *	To,
		CFG &	Cfg
	)

#include <CFG.hpp>

Remove all edges between the source and target nodes from the CFG.

If the graph does not contain any of these nodes, it is not modified.

Parameters

Cfg	The graph to modify.
From	The source node.
To	The target node.

Returns

A bool indicating whether the graph was modified.

removeEdge() [2/2]

GTIRB_EXPORT_API bool gtirb::removeEdge	(	const CfgNode *	From,
		const CfgNode *	To,
		EdgeLabel	Label,
		CFG &	Cfg
	)

#include <CFG.hpp>

Remove all edges with given label between the source and target nodes from the CFG.

If the graph does not contain any of these nodes, it is not modified.

Parameters

Cfg	The graph to modify.
From	The source node.
To	The target node.
Label	The Edge label. Only edges with this label will be removed.

Returns

A bool indicating whether the graph was modified.

removeVertex()

GTIRB_EXPORT_API bool gtirb::removeVertex	(	CfgNode *	N,
		CFG &	Cfg
	)

#include <CFG.hpp>

Remove a node from the CFG.

If the graph does not contain the node, it is not modified.

Parameters

N	The CFG node to remove.
Cfg	The graph to modify.

Returns

A bool indicating whether the graph was modified.