ir::ControlFlowGraph Class Reference

#include <ControlFlowGraph.h>

List of all members.

Public Types
typedef ir::BasicBlock	BasicBlock
typedef BasicBlock::BlockList	BlockList
	A list of basic blocks.
typedef BasicBlock::EdgeList	EdgeList
	A list of edges.
typedef BasicBlock::EdgePointerVector	EdgePointerVector
	A vector of edge pointers.
typedef BasicBlock::BlockPointerVector	BlockPointerVector
	A vector of block pointers.
typedef BasicBlock::ConstBlockPointerVector	ConstBlockPointerVector
	A const vector of block pointers.
typedef BlockList::iterator	iterator
	An iterator over basic blocks.
typedef BlockList::const_iterator	const_iterator
	A const iterator over basic blocks.
typedef BlockPointerVector::iterator	pointer_iterator
	A pointer to an iterator.
typedef BlockPointerVector::const_iterator	const_pointer_iterator
	A pointer to an iterator.
typedef BlockPointerVector::reverse_iterator	reverse_pointer_iterator
	A pointer to an iterator.
typedef EdgeList::iterator	edge_iterator
	An iterator over edges.
typedef EdgeList::const_iterator	const_edge_iterator
	A const iterator over edges.
typedef std::pair < edge_iterator, edge_iterator >	EdgePair
	Edge pair.
typedef EdgePointerVector::iterator	edge_pointer_iterator
	A pointer to an edge iterator.
typedef EdgePointerVector::const_iterator	const_edge_pointer_iterator
	A const pointer to an edge iterator.
typedef std::unordered_map < const_iterator, unsigned int >	BlockMap
	A map from a block pointer to an int.
typedef BasicBlock::Edge	Edge
	The edge.
typedef BasicBlock::InstructionList	InstructionList
	An instruction list.
typedef InstructionList::iterator	instruction_iterator
	An iterator over instructions.
typedef std::unordered_map < std::string, unsigned int >	BasicBlockColorMap
	maps a basic block [by label] to a coloring
Public Member Functions
	ControlFlowGraph ()
	~ControlFlowGraph ()
void	computeNewBlockId ()
BasicBlock::Id	newId ()
size_t	size () const
bool	empty () const
iterator	insert_block (const BasicBlock &b)
iterator	clone_block (iterator block, std::string suffix)
void	remove_block (iterator block)
edge_iterator	insert_edge (const Edge &e)
void	remove_edge (edge_iterator edge)
EdgePair	split_edge (edge_iterator edge, const BasicBlock &newBlock)
iterator	split_block (iterator block, unsigned int instruction, Edge::Type type, const std::string &label="")
	Splits a basic block into two such that there is a fallthrough edge from the original block to the newly split block.
iterator	get_entry_block ()
iterator	get_exit_block ()
const_iterator	get_entry_block () const
const_iterator	get_exit_block () const
std::ostream &	write (std::ostream &out) const
std::ostream &	write (std::ostream &out, BasicBlock::DotFormatter &blockFormatter) const
	write a graphviz-compatible file for visualizing the CFG
void	clear ()
	Clears all basic blocks and edges in the CFG.
BlockPointerVector	pre_order_sequence ()
BlockPointerVector	post_order_sequence ()
BlockPointerVector	topological_sequence ()
BlockPointerVector	reverse_topological_sequence ()
BlockPointerVector	executable_sequence ()
ControlFlowGraph &	operator= (const ControlFlowGraph &)
iterator	begin ()
	Get an iterator to the first block.
iterator	end ()
	Get an iterator to the last block.
const_iterator	begin () const
	Get a const iterator to the first block.
const_iterator	end () const
	Get a const iterator the last block.
edge_iterator	edges_begin ()
	Get an iterator to the first edge.
edge_iterator	edges_end ()
	Get an iterator to the last edge.
const_edge_iterator	edges_begin () const
	Get a const iterator to the first edge.
const_edge_iterator	edges_end () const
	Get a const iterator to the last edge.
Static Public Member Functions
static std::string	toString (Edge::Type t)
	Get the name of an edge type.

---

Detailed Description

Control flow graph

---

Member Typedef Documentation

typedef ir::BasicBlock ir::ControlFlowGraph::BasicBlock

typedef std::unordered_map<std::string, unsigned int> ir::ControlFlowGraph::BasicBlockColorMap

maps a basic block [by label] to a coloring

typedef BasicBlock::BlockList ir::ControlFlowGraph::BlockList

A list of basic blocks.

typedef std::unordered_map<const_iterator, unsigned int> ir::ControlFlowGraph::BlockMap

A map from a block pointer to an int.

typedef BasicBlock::BlockPointerVector ir::ControlFlowGraph::BlockPointerVector

A vector of block pointers.

typedef EdgeList::const_iterator ir::ControlFlowGraph::const_edge_iterator

A const iterator over edges.

typedef EdgePointerVector::const_iterator ir::ControlFlowGraph::const_edge_pointer_iterator

A const pointer to an edge iterator.

typedef BlockList::const_iterator ir::ControlFlowGraph::const_iterator

A const iterator over basic blocks.

typedef BlockPointerVector::const_iterator ir::ControlFlowGraph::const_pointer_iterator

A pointer to an iterator.

typedef BasicBlock::ConstBlockPointerVector ir::ControlFlowGraph::ConstBlockPointerVector

A const vector of block pointers.

typedef BasicBlock::Edge ir::ControlFlowGraph::Edge

The edge.

typedef EdgeList::iterator ir::ControlFlowGraph::edge_iterator

An iterator over edges.

typedef EdgePointerVector::iterator ir::ControlFlowGraph::edge_pointer_iterator

A pointer to an edge iterator.

typedef BasicBlock::EdgeList ir::ControlFlowGraph::EdgeList

A list of edges.

typedef std::pair<edge_iterator, edge_iterator> ir::ControlFlowGraph::EdgePair

Edge pair.

typedef BasicBlock::EdgePointerVector ir::ControlFlowGraph::EdgePointerVector

A vector of edge pointers.

typedef InstructionList::iterator ir::ControlFlowGraph::instruction_iterator

An iterator over instructions.

typedef BasicBlock::InstructionList ir::ControlFlowGraph::InstructionList

An instruction list.

typedef BlockList::iterator ir::ControlFlowGraph::iterator

An iterator over basic blocks.

typedef BlockPointerVector::iterator ir::ControlFlowGraph::pointer_iterator

A pointer to an iterator.

typedef BlockPointerVector::reverse_iterator ir::ControlFlowGraph::reverse_pointer_iterator

A pointer to an iterator.

---

Constructor & Destructor Documentation

ir::ControlFlowGraph::ControlFlowGraph

(

)

ir::ControlFlowGraph::~ControlFlowGraph

(

)

---

Member Function Documentation

ControlFlowGraph::iterator ir::ControlFlowGraph::begin

(

)

Get an iterator to the first block.

ControlFlowGraph::const_iterator ir::ControlFlowGraph::begin

(

)

const

Get a const iterator to the first block.

void ir::ControlFlowGraph::clear

(

)

Clears all basic blocks and edges in the CFG.

ControlFlowGraph::iterator ir::ControlFlowGraph::clone_block	(	iterator	block,
		std::string	suffix
	)

Duplicates the selected block, inserts it in an unconnected state, returns an iterator to the newly created block

void ir::ControlFlowGraph::computeNewBlockId

(

)

Make sure that the next call to newId will return a unique id

ControlFlowGraph::const_edge_iterator ir::ControlFlowGraph::edges_begin

(

)

const

Get a const iterator to the first edge.

ControlFlowGraph::edge_iterator ir::ControlFlowGraph::edges_begin

(

)

Get an iterator to the first edge.

ControlFlowGraph::const_edge_iterator ir::ControlFlowGraph::edges_end

(

)

const

Get a const iterator to the last edge.

ControlFlowGraph::edge_iterator ir::ControlFlowGraph::edges_end

(

)

Get an iterator to the last edge.

bool ir::ControlFlowGraph::empty

(

)

const

Is the graph empty?

ControlFlowGraph::iterator ir::ControlFlowGraph::end

(

)

Get an iterator to the last block.

ControlFlowGraph::const_iterator ir::ControlFlowGraph::end

(

)

const

Get a const iterator the last block.

ControlFlowGraph::BlockPointerVector ir::ControlFlowGraph::executable_sequence

(

)

Returns an ordered sequence of basic blocks such that the entry node is first and all fall-through edges produce adjacencies

ControlFlowGraph::const_iterator ir::ControlFlowGraph::get_entry_block

(

)

const

Returns the entry block of a control flow graph

ControlFlowGraph::iterator ir::ControlFlowGraph::get_entry_block

(

)

Returns the entry block of a control flow graph

ControlFlowGraph::const_iterator ir::ControlFlowGraph::get_exit_block

(

)

const

Returns the exit block of a control flow graph

ControlFlowGraph::iterator ir::ControlFlowGraph::get_exit_block

(

)

Returns the exit block of a control flow graph

ControlFlowGraph::iterator ir::ControlFlowGraph::insert_block

(

const BasicBlock &

b

)

Inserts a basic block into the CFG

ControlFlowGraph::edge_iterator ir::ControlFlowGraph::insert_edge

(

const Edge &

e

)

Creates an edge between given basic blocks

Parameters:

edge	edge to create

BasicBlock::Id ir::ControlFlowGraph::newId

(

)

Get a unique identifier for a new block

ControlFlowGraph & ir::ControlFlowGraph::operator=

(

const ControlFlowGraph &

cfg

)

deep copy of ControlFlowGraph

ControlFlowGraph::BlockPointerVector ir::ControlFlowGraph::post_order_sequence

(

)

returns an ordered sequence of the nodes of the CFG including entry and exit that would be encountered by a post order traversal

ControlFlowGraph::BlockPointerVector ir::ControlFlowGraph::pre_order_sequence

(

)

returns an ordered sequence of the nodes of the CFG including entry and exit that would be encountered by a pre order traversal

void ir::ControlFlowGraph::remove_block

(

iterator

block

)

Removes a basic block and associated edges. Any blocks dominated by block are now unreachable but still part of the graph.

Parameters:

block

block to remove from graph

void ir::ControlFlowGraph::remove_edge

(

edge_iterator

edge

)

Removes the edge which may exist from head->tail. This may render tail unreachable.

Parameters:

edge

to remove

ControlFlowGraph::BlockPointerVector ir::ControlFlowGraph::reverse_topological_sequence

(

)

returns an ordered sequence of the nodes of the CFG including entry and exit that would be encountered by a reverse post order traversal This is equivalent to a topological order

size_t ir::ControlFlowGraph::size

(

)

const

Gets the number of blocks within the graph

ControlFlowGraph::iterator ir::ControlFlowGraph::split_block	(	iterator	block,
		unsigned int	instruction,
		Edge::Type	type,
		const std::string &	label = ""
	)

Splits a basic block into two such that there is a fallthrough edge from the original block to the newly split block.

This function will map all out_edges of the first block to the second block.

Parameters:

block	The block being split
the	instruction within the block to perform the split, it ends up in the newly split block
the	label of the new block

Returns:

A pointer to the newly allocated second block

ControlFlowGraph::EdgePair ir::ControlFlowGraph::split_edge	(	edge_iterator	edge,
		const BasicBlock &	newBlock
	)

Given an edge head->tail, retargets edge and creates new edge such that the path head->newblock->tail exists. Inserts newblock into CFG and returns newly created edge

Parameters:

edge	existing edge to split
newblock	new BasicBlock to insert into CFG and create an edge from

Returns:

implicily created edges (head->newblock, newblock->tail) with same type as edge [may need modifying]

ControlFlowGraph::BlockPointerVector ir::ControlFlowGraph::topological_sequence

(

)

returns an ordered sequence of the nodes of the CFG including entry and exit that would be encountered by a reverse post order traversal This is equivalent to a topological order

std::string ir::ControlFlowGraph::toString

(

Edge::Type

t

)

[static]

Get the name of an edge type.

std::ostream & ir::ControlFlowGraph::write

(

std::ostream &

out

)

const

write a graphviz-compatible file for visualizing the CFG

std::ostream & ir::ControlFlowGraph::write	(	std::ostream &	out,
		BasicBlock::DotFormatter &	blockFormatter
	)		const

write a graphviz-compatible file for visualizing the CFG

---

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

• ocelot/ir/interface/ControlFlowGraph.h
• ocelot/ir/implementation/ControlFlowGraph.cpp