GPUOcelot
Classes | Public Types | Public Member Functions | Friends

analysis::DataflowGraph Class Reference

A class representing a graph of block of instructions, showing which registers are alive in each basic block. More...

#include <DataflowGraph.h>

Inheritance diagram for analysis::DataflowGraph:
Inheritance graph
[legend]
Collaboration diagram for analysis::DataflowGraph:
Collaboration graph
[legend]

List of all members.

Classes

class  Block
 A class for referring to a generic basic block of instructions. More...
struct  BlockVector_Hash
class  Instruction
 A class for referring to a generic instruction. More...
class  NoProducerException
 An exception for potentially uninitialized regs. More...
class  PhiInstruction
 A class for referring to a phi instruction. More...
class  Register
 A register with type info. More...
struct  Register_Hash
class  RegisterPointer
 A register with type info. More...

Public Types

typedef ir::PTXOperand::DataType Type
 Datatype, we use PTX.
typedef unsigned int RegisterId
 A unique ID for a logical register.
typedef
ir::ControlFlowGraph::InstructionList 
InstructionList
 A list of instructions.
typedef std::vector
< RegisterPointer
RegisterPointerVector
 A vector of register ID pointers.
typedef std::vector< RegisterRegisterVector
 A vector of register ID pointers.
typedef std::list< InstructionInstructionVector
 A vector of Instructions.
typedef std::list< PhiInstructionPhiInstructionVector
 A vector of PhiInstructions.
typedef std::list< BlockBlockVector
 A vector of blocks.
typedef std::list
< InstructionVector::iterator > 
InstructionIteratorList
typedef std::unordered_set
< BlockVector::iterator,
BlockVector_Hash
BlockPointerSet
 A vector of Block pointers.
typedef BlockVector::iterator iterator
 iterator
typedef BlockVector::const_iterator const_iterator
 const_iterator
typedef BlockVector::value_type value_type
 Value type.
typedef BlockVector::size_type size_type
 Size type.
typedef Block::RegisterSet RegisterSet
 Register set.
typedef RegisterSet::const_iterator register_iterator
 Register set iterator.
typedef std::vector< iteratorBlockPointerVector
 A vector of iterators.
typedef
BlockPointerVector::iterator 
pointer_iterator
 A pointer to an iterator.
typedef
BlockPointerVector::reverse_iterator 
reverse_pointer_iterator
 A reverse pointer to an iterator.
typedef std::unordered_map
< ir::ControlFlowGraph::iterator,
iterator
IteratorMap
 A map from cfg blocks to dfg equivalents.

Public Member Functions

Instruction convert (ir::PTXInstruction &i)
 Convert from a PTXInstruction to an Instruction.
void analyze (ir::IRKernel &kernel)
 Build from a kernel CFG.
 DataflowGraph ()
 The constructor.
 ~DataflowGraph ()
 The destructor.
 DataflowGraph (const DataflowGraph &)
DataflowGraphoperator= (const DataflowGraph &)
iterator begin ()
 Return an iterator to the program entry point.
const_iterator begin () const
 Return an iterator to the program entry point.
iterator end ()
 Return an iterator just beyond the program exit point.
const_iterator end () const
 Return an iterator just beyond the program exit point.
bool empty () const
 Is the graph empty?
size_type size () const
 Get the number of blocks.
size_type max_size () const
 Get the max number of blocks.
iterator insert (iterator predecessor, const std::string &label)
 Insert a Block between two existing blocks.
iterator insert (iterator predecessor, iterator successor, const std::string &label)
 Insert a Block between two existing blocks.
iterator split (iterator block, unsigned int instruction, bool isFallthrough)
 Split a block into two starting at a given instruction, the split instruction goes in the first block.
iterator split (iterator block, InstructionVector::iterator position, bool isFallthrough, const std::string &l)
 Split a block into two starting at a given instruction iterator, the split instruction goes in the first block.
void redirect (iterator source, iterator destination, iterator newTarget)
 Redirect an edge between two blocks to a third.
void target (iterator block, iterator target, bool fallthrough=false)
 Set the target of a block.
iterator erase (iterator block)
 Delete a block, joining predecessors and successors.
void clear ()
 Revert back to a single entry and exit block.
void insert (iterator block, const ir::Instruction &instruction, unsigned int index)
 Insert an instruction into a block immediately before the specified index.
InstructionVector::iterator insert (iterator block, const ir::Instruction &instruction, InstructionVector::iterator position)
 Insert an instruction into a block immediately before the element at specified position.
void insert (iterator block, const ir::Instruction &instruction)
 Insert an instruction at the end of a block.
void erase (iterator block, InstructionVector::iterator position)
 Erase an instruction from a block at the specified position.
void erase (iterator block, unsigned int index)
 Erase an instruction from a block at the specified index.
void compute ()
 Compute live ranges.
void constructDUChains ()
 Construct DU/UD chains.
void constructBlockDUChains (iterator blockIter)
RegisterId maxRegister () const
 Determine the max register used in the graph.
RegisterId newRegister ()
 Allocate a new register that is not used elswhere in the graph.
void toSsa ()
 Convert into ssa form.
void fromSsa ()
 Convert out of ssa form.
bool ssa () const
 Is the graph in ssa form?
BlockPointerVector executableSequence ()
 Get an executable sequence of blocks.
IteratorMap getCFGtoDFGMap ()
 Get a map from CFG to DFG iterators.

Friends

class SSAGraph

Detailed Description

A class representing a graph of block of instructions, showing which registers are alive in each basic block.


Member Typedef Documentation

typedef std::unordered_set< BlockVector::iterator, BlockVector_Hash > analysis::DataflowGraph::BlockPointerSet

A vector of Block pointers.

A vector of iterators.

A vector of blocks.

typedef BlockVector::const_iterator analysis::DataflowGraph::const_iterator

const_iterator

typedef std::list<InstructionVector::iterator> analysis::DataflowGraph::InstructionIteratorList

A list of instructions.

A vector of Instructions.

typedef BlockVector::iterator analysis::DataflowGraph::iterator

iterator

A map from cfg blocks to dfg equivalents.

A vector of PhiInstructions.

typedef BlockPointerVector::iterator analysis::DataflowGraph::pointer_iterator

A pointer to an iterator.

typedef RegisterSet::const_iterator analysis::DataflowGraph::register_iterator

Register set iterator.

A unique ID for a logical register.

A vector of register ID pointers.

Register set.

A vector of register ID pointers.

typedef BlockPointerVector::reverse_iterator analysis::DataflowGraph::reverse_pointer_iterator

A reverse pointer to an iterator.

typedef BlockVector::size_type analysis::DataflowGraph::size_type

Size type.

Datatype, we use PTX.

Reimplemented from analysis::Analysis.

typedef BlockVector::value_type analysis::DataflowGraph::value_type

Value type.


Constructor & Destructor Documentation

analysis::DataflowGraph::DataflowGraph ( )

The constructor.

analysis::DataflowGraph::~DataflowGraph ( )

The destructor.

analysis::DataflowGraph::DataflowGraph ( const DataflowGraph )

Member Function Documentation

void analysis::DataflowGraph::analyze ( ir::IRKernel kernel) [virtual]

Build from a kernel CFG.

Implements analysis::KernelAnalysis.

DataflowGraph::iterator analysis::DataflowGraph::begin ( )

Return an iterator to the program entry point.

DataflowGraph::const_iterator analysis::DataflowGraph::begin ( ) const

Return an iterator to the program entry point.

void analysis::DataflowGraph::clear ( )

Revert back to a single entry and exit block.

void analysis::DataflowGraph::compute ( )

Compute live ranges.

void analysis::DataflowGraph::constructBlockDUChains ( iterator  blockIter)
void analysis::DataflowGraph::constructDUChains ( )

Construct DU/UD chains.

DataflowGraph::Instruction analysis::DataflowGraph::convert ( ir::PTXInstruction i)

Convert from a PTXInstruction to an Instruction.

bool analysis::DataflowGraph::empty ( ) const

Is the graph empty?

DataflowGraph::iterator analysis::DataflowGraph::end ( )

Return an iterator just beyond the program exit point.

DataflowGraph::const_iterator analysis::DataflowGraph::end ( ) const

Return an iterator just beyond the program exit point.

DataflowGraph::iterator analysis::DataflowGraph::erase ( iterator  block)

Delete a block, joining predecessors and successors.

void analysis::DataflowGraph::erase ( iterator  block,
InstructionVector::iterator  position 
)

Erase an instruction from a block at the specified position.

void analysis::DataflowGraph::erase ( iterator  block,
unsigned int  index 
)

Erase an instruction from a block at the specified index.

DataflowGraph::BlockPointerVector analysis::DataflowGraph::executableSequence ( )

Get an executable sequence of blocks.

void analysis::DataflowGraph::fromSsa ( )

Convert out of ssa form.

DataflowGraph::IteratorMap analysis::DataflowGraph::getCFGtoDFGMap ( )

Get a map from CFG to DFG iterators.

void analysis::DataflowGraph::insert ( iterator  block,
const ir::Instruction instruction 
)

Insert an instruction at the end of a block.

void analysis::DataflowGraph::insert ( iterator  block,
const ir::Instruction instruction,
unsigned int  index 
)

Insert an instruction into a block immediately before the specified index.

DataflowGraph::InstructionVector::iterator analysis::DataflowGraph::insert ( iterator  block,
const ir::Instruction instruction,
InstructionVector::iterator  position 
)

Insert an instruction into a block immediately before the element at specified position.

DataflowGraph::iterator analysis::DataflowGraph::insert ( iterator  predecessor,
const std::string &  label 
)

Insert a Block between two existing blocks.

Parameters:
predecessorAn iterator to the previous block.
Returns:
An iterator to the inserted block.

Note that this insert splits the fallthrough edge

DataflowGraph::iterator analysis::DataflowGraph::insert ( iterator  predecessor,
iterator  successor,
const std::string &  label 
)

Insert a Block between two existing blocks.

Parameters:
predecessorAn iterator to the previous block.
successorAn iterator to the next block.
Returns:
An iterator to the inserted block

Note that this insert splits the edge between predecessor and successor.

DataflowGraph::size_type analysis::DataflowGraph::max_size ( ) const

Get the max number of blocks.

DataflowGraph::RegisterId analysis::DataflowGraph::maxRegister ( ) const

Determine the max register used in the graph.

DataflowGraph::RegisterId analysis::DataflowGraph::newRegister ( )

Allocate a new register that is not used elswhere in the graph.

DataflowGraph& analysis::DataflowGraph::operator= ( const DataflowGraph )
void analysis::DataflowGraph::redirect ( iterator  source,
iterator  destination,
iterator  newTarget 
)

Redirect an edge between two blocks to a third.

DataflowGraph::size_type analysis::DataflowGraph::size ( ) const

Get the number of blocks.

DataflowGraph::iterator analysis::DataflowGraph::split ( iterator  block,
unsigned int  instruction,
bool  isFallthrough 
)

Split a block into two starting at a given instruction, the split instruction goes in the first block.

DataflowGraph::iterator analysis::DataflowGraph::split ( iterator  block,
InstructionVector::iterator  position,
bool  isFallthrough,
const std::string &  l 
)

Split a block into two starting at a given instruction iterator, the split instruction goes in the first block.

bool analysis::DataflowGraph::ssa ( ) const

Is the graph in ssa form?

void analysis::DataflowGraph::target ( iterator  block,
iterator  target,
bool  fallthrough = false 
)

Set the target of a block.

void analysis::DataflowGraph::toSsa ( )

Convert into ssa form.


Friends And Related Function Documentation

friend class SSAGraph [friend]

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines