Representation of a parametric execution graph (Parametric Execution Graph). More...

#include <otawa/parexegraph/ParExeGraph.h>

Inheritance diagram for otawa::ParExeGraph:

Classes
class	InstIterator

class	InstNodeIterator

class	Predecessor

class	PreorderIterator

struct	rename_table_t

class	StageIterator

class	StageNodeIterator

class	Successor

Public Types
typedef ParExeNode *	Vertex

typedef ParExeEdge *	Edge

Public Member Functions
	ParExeGraph (WorkSpace ws, ParExeProc proc, elm::genstruct::Vector< Resource * > hw_resources, ParExeSequence seq, const PropList &props=PropList::EMPTY)
	Build a parametric execution graph. More...

virtual	~ParExeGraph (void)

ParExeSequence *	getSequence (void) const

ParExeNode *	firstNode ()

virtual ParExePipeline *	pipeline (ParExeStage stage, ParExeInst inst)

int	numResources ()

Resource *	resource (int index)

int	numInstructions ()

virtual void	build ()

virtual void	createNodes (void)
	Creates nodes in the graph: one node for each (instruction/pipeline_stage) pair. More...

virtual void	findDataDependencies (void)
	Compute for each first FU node which is the FU node producing the required data (and fill the producer list of a FU node). More...

virtual void	addEdgesForPipelineOrder (void)
	Adds edges that represent the order of stages in the pipeline. More...

virtual void	addEdgesForFetch (void)
	Add edges for fetch timing, that is edges ensuring that instruction in the same block are fetched in the same cycle and that instructions in sequence belonging to different memory blocks require are fetched in two cycles. More...

virtual void	addEdgesForProgramOrder (elm::genstruct::SLList< ParExeStage * > *list_of_stages=NULL)
	Adds edges to reflect processing of instruction in the order of the program. More...

virtual void	addEdgesForMemoryOrder (void)
	Adds edges to represent contention to access memory, basically, between FUs of instructions performing memory access. More...

virtual void	addEdgesForDataDependencies (void)
	Adds edges for data dependencies, that is, if an instruction (a) produces content of a register and instruction (b) uses this register value create a solid edge between their execute stages. More...

virtual void	addEdgesForQueues (void)
	Called to add edges representing contention on the different queues of the microprocessor. More...

void	findContendingNodes ()

void	createSequenceResources ()

int	analyze ()
	Computes the cost, in cycles, of the current graph. More...

void	initDelays ()

void	clearDelays ()

void	restoreDefaultLatencies ()

void	setDefaultLatencies (TimingContext *tctxt)

void	setLatencies (TimingContext *tctxt)

void	propagate ()

void	analyzeContentions ()

int	cost ()

int	delta (ParExeNode a, Resource res)
	This method is called to compute the delay of a given node compared to the last node of the prologue (i.e. More...

void	dump (elm::io::Output &dotFile, const string &info="")

void	display (elm::io::Output &output)

int	count (void) const

bool	contains (ParExeNode *item) const

bool	isEmpty (void) const

	operator bool (void) const

void	clear (void)

void	add (GenNode *node)

void	addAll (const C< ParExeNode * > &items)

void	remove (GenNode *node)

void	remove (GenEdge *edge)

void	removeAll (const C< ParExeNode * > &items)

ParExeNode *	sinkOf (ParExeEdge *edge) const

int	outDegree (ParExeNode *vertex) const

bool	isSuccessorOf (ParExeNode succ, ParExeNode ref) const

ParExeNode *	sourceOf (ParExeEdge *edge) const

int	inDegree (ParExeNode *vertex) const

bool	isPredecessorOf (ParExeNode succ, ParExeNode ref) const

int	indexOf (ParExeNode *vertex) const

const graph::Graph *	_ (void) const

graph::Graph *	_ (void)

Static Public Member Functions
static const graph::Node *	_ (const GenNode *node)

static const graph::Edge *	_ (const GenEdge *edge)

static graph::Node *	_ (GenNode *node)

static graph::Edge *	_ (Edge *edge)

Protected Types
typedef struct otawa::ParExeGraph::rename_table_t	rename_table_t

Protected Attributes
WorkSpace *	_ws

PropList	_props

ParExeProc *	_microprocessor

elm::genstruct::Vector < Resource * >	_resources

ParExeNode *	_first_node

ParExeNode *	_last_prologue_node

ParExeNode *	_last_node

Private Attributes
ParExeSequence *	_sequence

int	_cache_line_size

int	_capacity

int	_branch_penalty

Friends
class	InstIterator

class	ParExeNode

Detailed Description

Representation of a parametric execution graph (Parametric Execution Graph).

Member Typedef Documentation

typedef ParExeEdge * otawa::GenGraph< ParExeNode , ParExeEdge >::Edge

inherited

typedef struct otawa::ParExeGraph::rename_table_t otawa::ParExeGraph::rename_table_t

protected

typedef ParExeNode * otawa::GenGraph< ParExeNode , ParExeEdge >::Vertex

inherited

Constructor & Destructor Documentation

otawa::ParExeGraph::ParExeGraph	(	WorkSpace *	ws,
		ParExeProc *	proc,
		elm::genstruct::Vector< Resource * > *	hw_resources,
		ParExeSequence *	seq,
		const PropList &	props = `PropList::EMPTY`
	)

Build a parametric execution graph.

Parameters

ws	Current workspace.
proc	Processor description.
seq	Instruction sequence to compute.
props	Other parameters.

References _cache_line_size, _props, _resources, otawa::hard::Cache::blockSize(), cache, otawa::hard::CACHE_CONFIGURATION, otawa::hard::CacheConfiguration::instCache(), otawa::Process::instSize(), elm::genstruct::Vector< T >::isEmpty(), and otawa::WorkSpace::process().

otawa::ParExeGraph::~ParExeGraph ( void )

virtual

References _microprocessor, _sequence, otawa::ParExeStage::EXECUTE, and otawa::ParExeProc::pipeline().

Member Function Documentation

static const graph::Node* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( const GenNode * node )

inlinestaticinherited

static const graph::Edge* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( const GenEdge * edge )

inlinestaticinherited

const graph::Graph* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( void ) const

inlineinherited

static graph::Node* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( GenNode * node )

inlinestaticinherited

static graph::Edge* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( Edge * edge )

inlinestaticinherited

graph::Graph* otawa::GenGraph< ParExeNode , ParExeEdge >::_ ( void )

inlineinherited

void otawa::GenGraph< ParExeNode , ParExeEdge >::add ( GenNode * node )

inlineinherited

void otawa::GenGraph< ParExeNode , ParExeEdge >::addAll ( const C< ParExeNode * > & items )

inlineinherited

void otawa::ParExeGraph::addEdgesForDataDependencies ( void )

virtual

Adds edges for data dependencies, that is, if an instruction (a) produces content of a register and instruction (b) uses this register value create a solid edge between their execute stages.

References _microprocessor, otawa::ParExeProc::execStage(), otawa::ParExePipeline::firstStage(), otawa::ParExeStage::fu(), otawa::ParExeNode::inst(), otawa::ParExeStage::node(), otawa::ParExeStage::numFus(), otawa::ParExeStage::numNodes(), and otawa::ParExeEdge::SOLID.

Referenced by build().

void otawa::ParExeGraph::addEdgesForFetch ( void )

virtual

Add edges for fetch timing, that is edges ensuring that instruction in the same block are fetched in the same cycle and that instructions in sequence belonging to different memory blocks require are fetched in two cycles.

For example, for a block size of 16 with fixed-size instructions of 4 bytes, the instruction sequence is marked with fetches bounds:

start of basic block
0x100C fetch
0x1010 fetch
0x1014
0x1018
0x101C
0x1010 fetch
0x1014

References _branch_penalty, _cache_line_size, _microprocessor, otawa::ProgItem::address(), otawa::cfgio::edge(), otawa::ParExeProc::fetchStage(), otawa::ParExeStage::firstNode(), otawa::ParExeInst::inst(), otawa::ParExeNode::inst(), otawa::Address::offset(), otawa::ParExeEdge::SLASHED, otawa::ParExeEdge::SOLID, and otawa::ProgItem::topAddress().

Referenced by build().

void otawa::ParExeGraph::addEdgesForMemoryOrder ( void )

virtual

Adds edges to represent contention to access memory, basically, between FUs of instructions performing memory access.

References _microprocessor, otawa::ParExeProc::execStage(), otawa::ParExePipeline::firstStage(), otawa::ParExeStage::FU, otawa::ParExeStage::fu(), otawa::ParExeInst::inst(), otawa::ParExeNode::inst(), otawa::Inst::isLoad(), otawa::Inst::isStore(), otawa::ParExeStage::node(), otawa::ParExeStage::numFus(), otawa::ParExeStage::numNodes(), and otawa::ParExeEdge::SOLID.

Referenced by build().

void otawa::ParExeGraph::addEdgesForPipelineOrder ( void )

virtual

Adds edges that represent the order of stages in the pipeline.

References _sequence, and otawa::ParExeEdge::SOLID.

Referenced by build().

void otawa::ParExeGraph::addEdgesForProgramOrder ( elm::genstruct::SLList< ParExeStage * > * list_of_stages = NULL )

virtual

Adds edges to reflect processing of instruction in the order of the program.

Parameters

list_of_stages List of stages that process nodes in order (if an empty pointer is passed, one is created containing the in-order-scheduled stages).

References _microprocessor, otawa::GenGraph< ParExeNode, ParExeEdge >::count(), otawa::ParExeProc::listOfInorderStages(), otawa::ParExeEdge::SLASHED, and otawa::ParExeEdge::SOLID.

Referenced by build().

void otawa::ParExeGraph::addEdgesForQueues ( void )

virtual

Called to add edges representing contention on the different queues of the microprocessor.

References _microprocessor, otawa::ParExeQueue::fillingStage(), otawa::ParExeQueue::name(), otawa::ParExeStage::node(), otawa::ParExeProc::pipeline(), otawa::ParExeQueue::size(), and otawa::ParExeEdge::SLASHED.

Referenced by build().

int otawa::ParExeGraph::analyze ( )

Computes the cost, in cycles, of the current graph.

The cost is the difference between the execution date in the commit stage of the last instruction of the considered instruction and of the last prefix instruction.

Returns: Cost for the current graph.

References _last_node, _last_prologue_node, clearDelays(), cost(), otawa::ParExeNode::delay(), initDelays(), and propagate().

Referenced by otawa::etime::EdgeTimeBuilder::processSequence().

void otawa::ParExeGraph::analyzeContentions ( )

void otawa::ParExeGraph::build ( )

virtual

References addEdgesForDataDependencies(), addEdgesForFetch(), addEdgesForMemoryOrder(), addEdgesForPipelineOrder(), addEdgesForProgramOrder(), addEdgesForQueues(), createNodes(), and createSequenceResources().

Referenced by otawa::etime::EdgeTimeBuilder::make().

void otawa::GenGraph< ParExeNode , ParExeEdge >::clear ( void )

inlineinherited

void otawa::ParExeGraph::clearDelays ( )

References _resources, otawa::Resource::index(), and resource().

Referenced by analyze().

bool otawa::GenGraph< ParExeNode , ParExeEdge >::contains ( ParExeNode * item ) const

inlineinherited

int otawa::ParExeGraph::cost ( void )

References _last_node, _resources, otawa::Resource::BLOCK_START, otawa::ParExeNode::delay(), delta(), and otawa::Resource::QUEUE.

Referenced by analyze().

int otawa::GenGraph< ParExeNode , ParExeEdge >::count ( void ) const

inlineinherited

Referenced by addEdgesForProgramOrder().

void otawa::ParExeGraph::createNodes ( void )

virtual

Creates nodes in the graph: one node for each (instruction/pipeline_stage) pair.

For the execution stage, creates as many nodes as stages in the pipeline of the required functional unit.

References _last_node, _microprocessor, _sequence, otawa::ParExeStage::EXECUTE, ParExeNode, otawa::ParExeProc::pipeline(), and pipeline().

Referenced by build().

void otawa::ParExeGraph::createSequenceResources ( )

References _resources, _sequence, _ws, otawa::RegResource::addUsingInst(), otawa::sem::inst::inst(), otawa::WorkSpace::platform(), otawa::hard::Platform::regCount(), and elm::StringBuffer::toString().

Referenced by build().

int otawa::ParExeGraph::delta	(	ParExeNode *	node,
		Resource *	res
	)

This method is called to compute the delay of a given node compared to the last node of the prologue (i.e.

the last node of the preceding block) with respect to a given resource.

Parameters

node	The node for which the delay is computed (e.g., the last node of the basic block under analysis)
res	The resource for which the delay is computed.

Returns: Delay (number of cycles).

References _last_prologue_node, _microprocessor, otawa::ParExeNode::delay(), otawa::Resource::index(), numResources(), otawa::ParExePipeline::numStages(), otawa::ParExeProc::pipeline(), otawa::Resource::QUEUE, otawa::Resource::STAGE, and otawa::Resource::type().

Referenced by cost().

void otawa::ParExeGraph::display ( elm::io::Output & output )

void otawa::ParExeGraph::dump	(	elm::io::Output &	dotFile,
		const string &	info = `""`
	)

References elm::_, _resources, _sequence, otawa::ot::address(), otawa::cfgio::bb(), otawa::BLOCK, otawa::ParExeStage::EXECUTE, otawa::sem::inst::inst(), otawa::ParExeEdge::SLASHED, otawa::ParExeEdge::SOLID, and width().

void otawa::ParExeGraph::findContendingNodes ( )

References _microprocessor, otawa::ParExeNode::addContender(), otawa::ParExeStage::EXECUTE, otawa::ParExePipeline::firstStage(), otawa::ParExeStage::fu(), otawa::ParExeStage::node(), otawa::ParExeStage::numNodes(), otawa::ParExeStage::OUT_OF_ORDER, and otawa::ParExeProc::pipeline().

void otawa::ParExeGraph::findDataDependencies ( void )

virtual

Compute for each first FU node which is the FU node producing the required data (and fill the producer list of a FU node).

ParExeNode* otawa::ParExeGraph::firstNode ( void )

inline

References _first_node.

Referenced by otawa::ParExeNode::ParExeNode(), and otawa::etime::EdgeTimeBuilder::processSequence().

ParExeSequence* otawa::ParExeGraph::getSequence ( void ) const

inline

References _sequence.

int otawa::GenGraph< ParExeNode , ParExeEdge >::inDegree ( ParExeNode * vertex ) const

inlineinherited

int otawa::GenGraph< ParExeNode , ParExeEdge >::indexOf ( ParExeNode * vertex ) const

inlineinherited

void otawa::ParExeGraph::initDelays ( )

References _first_node, _resources, otawa::Resource::BLOCK_START, otawa::ParExeStage::EXECUTE, otawa::ParExeQueue::fillingStage(), otawa::ParExeStage::node(), otawa::Resource::QUEUE, otawa::Resource::REG, otawa::Resource::RES_TYPE_NUM, otawa::ParExeNode::setDelay(), and otawa::Resource::STAGE.

Referenced by analyze().

bool otawa::GenGraph< ParExeNode , ParExeEdge >::isEmpty ( void ) const

inlineinherited

bool otawa::GenGraph< ParExeNode , ParExeEdge >::isPredecessorOf	(	ParExeNode *	succ,
		ParExeNode *	ref
	)		const

inlineinherited

bool otawa::GenGraph< ParExeNode , ParExeEdge >::isSuccessorOf	(	ParExeNode *	succ,
		ParExeNode *	ref
	)		const

inlineinherited

int otawa::ParExeGraph::numInstructions ( )

inline

References _sequence, and otawa::ParExeSequence::length().

Referenced by otawa::ParExeNode::ParExeNode().

int otawa::ParExeGraph::numResources ( )

inline

References _resources.

Referenced by delta(), and otawa::ParExeNode::ParExeNode().

otawa::GenGraph< ParExeNode , ParExeEdge >::operator bool ( void ) const

inlineinherited

int otawa::GenGraph< ParExeNode , ParExeEdge >::outDegree ( ParExeNode * vertex ) const

inlineinherited

ParExePipeline * otawa::ParExeGraph::pipeline	(	ParExeStage *	stage,
		ParExeInst *	inst
	)

virtual

References otawa::ParExeStage::findFU(), otawa::ParExeInst::inst(), and otawa::Inst::kind().

Referenced by createNodes().

void otawa::ParExeGraph::propagate ( )

References _resources, otawa::Resource::index(), resource(), and otawa::ParExeEdge::SOLID.

Referenced by analyze().

void otawa::GenGraph< ParExeNode , ParExeEdge >::remove ( GenNode * node )

inlineinherited

void otawa::GenGraph< ParExeNode , ParExeEdge >::remove ( GenEdge * edge )

inlineinherited

void otawa::GenGraph< ParExeNode , ParExeEdge >::removeAll ( const C< ParExeNode * > & items )

inlineinherited

Resource* otawa::ParExeGraph::resource ( int index )

inline

References _resources.

Referenced by clearDelays(), and propagate().

void otawa::ParExeGraph::restoreDefaultLatencies ( )

void otawa::ParExeGraph::setDefaultLatencies ( TimingContext * tctxt )

void otawa::ParExeGraph::setLatencies ( TimingContext * tctxt )

ParExeNode * otawa::GenGraph< ParExeNode , ParExeEdge >::sinkOf ( ParExeEdge * edge ) const

inlineinherited

ParExeNode * otawa::GenGraph< ParExeNode , ParExeEdge >::sourceOf ( ParExeEdge * edge ) const

inlineinherited

Friends And Related Function Documentation

friend class InstIterator

friend

friend class ParExeNode

friend

Referenced by createNodes().

Member Data Documentation

int otawa::ParExeGraph::_branch_penalty

private

Referenced by addEdgesForFetch().

int otawa::ParExeGraph::_cache_line_size

private

Referenced by addEdgesForFetch(), and ParExeGraph().

int otawa::ParExeGraph::_capacity

private

ParExeNode* otawa::ParExeGraph::_first_node

protected

Referenced by firstNode(), initDelays(), and otawa::ParExeNode::ParExeNode().

ParExeNode* otawa::ParExeGraph::_last_node

protected

Referenced by analyze(), cost(), and createNodes().

ParExeNode* otawa::ParExeGraph::_last_prologue_node

protected

Referenced by analyze(), delta(), and otawa::ParExeNode::ParExeNode().

ParExeProc* otawa::ParExeGraph::_microprocessor

protected

Referenced by addEdgesForDataDependencies(), addEdgesForFetch(), addEdgesForMemoryOrder(), addEdgesForProgramOrder(), addEdgesForQueues(), createNodes(), delta(), findContendingNodes(), and ~ParExeGraph().

PropList otawa::ParExeGraph::_props

protected

Referenced by ParExeGraph().

elm::genstruct::Vector<Resource *> otawa::ParExeGraph::_resources

protected

Referenced by clearDelays(), cost(), createSequenceResources(), dump(), initDelays(), numResources(), ParExeGraph(), propagate(), and resource().

ParExeSequence* otawa::ParExeGraph::_sequence

private

Referenced by addEdgesForPipelineOrder(), createNodes(), createSequenceResources(), dump(), getSequence(), numInstructions(), and ~ParExeGraph().

WorkSpace* otawa::ParExeGraph::_ws

protected

Referenced by createSequenceResources().

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

include/otawa/parexegraph/ParExeGraph.h
src/prog/parexegraph_ParExeGraph.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Attributes

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation