GPUOcelot
|
A class representing a graph of block of instructions, showing which registers are alive in each basic block. More...
#include <DataflowGraph.h>
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 |
A class representing a graph of block of instructions, showing which registers are alive in each basic block.
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 |
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 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.
Datatype, we use PTX.
Reimplemented from analysis::Analysis.
typedef BlockVector::value_type analysis::DataflowGraph::value_type |
Value type.
analysis::DataflowGraph::DataflowGraph | ( | ) |
The constructor.
analysis::DataflowGraph::~DataflowGraph | ( | ) |
The destructor.
analysis::DataflowGraph::DataflowGraph | ( | const DataflowGraph & | ) |
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.
predecessor | An iterator to the previous 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.
predecessor | An iterator to the previous block. |
successor | An iterator to the next 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?
Set the target of a block.
void analysis::DataflowGraph::toSsa | ( | ) |
Convert into ssa form.
friend class SSAGraph [friend] |