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:

Collaboration diagram for analysis::DataflowGraph:

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< Register >	RegisterVector
	A vector of register ID pointers.
typedef std::list< Instruction >	InstructionVector
	A vector of Instructions.
typedef std::list< PhiInstruction >	PhiInstructionVector
	A vector of PhiInstructions.
typedef std::list< Block >	BlockVector
	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< iterator >	BlockPointerVector
	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 &)
DataflowGraph &	operator= (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.

typedef std::vector< iterator > analysis::DataflowGraph::BlockPointerVector

A vector of iterators.

typedef std::list< Block > analysis::DataflowGraph::BlockVector

A vector of blocks.

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

const_iterator

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

typedef ir::ControlFlowGraph::InstructionList analysis::DataflowGraph::InstructionList

A list of instructions.

typedef std::list< Instruction > analysis::DataflowGraph::InstructionVector

A vector of Instructions.

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

iterator

typedef std::unordered_map< ir::ControlFlowGraph::iterator, iterator > analysis::DataflowGraph::IteratorMap

A map from cfg blocks to dfg equivalents.

typedef std::list< PhiInstruction > analysis::DataflowGraph::PhiInstructionVector

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.

typedef unsigned int analysis::DataflowGraph::RegisterId

A unique ID for a logical register.

typedef std::vector< RegisterPointer > analysis::DataflowGraph::RegisterPointerVector

A vector of register ID pointers.

typedef Block::RegisterSet analysis::DataflowGraph::RegisterSet

Register set.

typedef std::vector< Register > analysis::DataflowGraph::RegisterVector

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.

typedef ir::PTXOperand::DataType analysis::DataflowGraph::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:

predecessor An 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:

predecessor	An iterator to the previous block.
successor	An 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:

ocelot/analysis/interface/DataflowGraph.h
ocelot/analysis/implementation/DataflowGraph.cpp

analysis::DataflowGraph Class Reference

Classes

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation