GPUOcelot
Public Types | Public Member Functions | Static Public Member Functions

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 ()
ControlFlowGraphoperator= (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 std::unordered_map<std::string, unsigned int> ir::ControlFlowGraph::BasicBlockColorMap

maps a basic block [by label] to a coloring

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.

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.

A const vector of block pointers.

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.

A list of edges.

Edge pair.

A vector of edge pointers.

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

An iterator over instructions.

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:
edgeedge 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:
blockblock 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:
edgeto 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:
blockThe block being split
theinstruction within the block to perform the split, it ends up in the newly split block
thelabel 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:
edgeexisting edge to split
newblocknew 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:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines