Control Flow Graph representation. More...

#include <otawa/cfg/CFG.h>

Inheritance diagram for otawa::CFG:

Classes
class	BBIterator

Public Member Functions
	CFG (Segment seg, BasicBlock entry)
	Constructor. More...

virtual	~CFG (void)

Segment *	segment (void) const

string	label (void)
	Get some label to identify the CFG. More...

string	name (void)
	Build a name that identifies this CFG and is valid C name. More...

string	format (const Address &addr)
	Format the display of the given address relativelt to the given CFG. More...

int	number (void)

address_t	address (void)
	Get the address of the first instruction of the CFG. More...

BasicBlock *	entry (void)
	Get the entry basic block of the CFG. More...

BasicBlock *	exit (void)
	Get the exit basic block of the CFG. More...

int	countBB (void)

bool	isVirtual (void) const

bool	isInlined (void) const

void	numberBB (void)
	Number the basic block of the CFG, that is, hook a property with ID_Index identifier and the integer value of the number to each basic block. More...

BasicBlock *	firstBB (void)
	Get the first basic block of the CFG. More...

Inst *	firstInst (void)
	Get the first instruction of the CFG. More...

void	print (io::Output &out)
	Print a reference for the CFG. More...

Property *	getProp (const AbstractIdentifier *id) const
	Find a property by its identifier. More...

void	setProp (Property *prop)
	Set the property in the property list removing any double. More...

void	setProp (const AbstractIdentifier *id)

void	removeProp (const AbstractIdentifier *id)
	Remove a property matching the given identifier. More...

void	removeProp (const AbstractIdentifier &id)

Property *	extractProp (const AbstractIdentifier *id)
	Remove a property matching the given identifier and return it. More...

Property *	extractProp (const AbstractIdentifier &id)
	Remove a property matching the given identifier and return it. More...

void	addProp (Property *prop)
	Add property to the list without checking of duplication. More...

void	removeAllProp (const AbstractIdentifier *id)
	Remove all the properties matching the given identifier. More...

bool	hasProp (const AbstractIdentifier &id) const
	Test if the property list contains a property matching the given identifier. More...

void	clearProps (void)
	Remove all properties from the list. More...

void	addProps (const PropList &props)
	Add all properties from the given property list, in a reverse order. More...

void	print (elm::io::Output &out) const
	Display the current property list. More...

Static Public Attributes
static const PropList	EMPTY
	This is an empty proplist for convenience. More...

Protected Member Functions
	CFG (void)
	Build an empty CFG. More...

virtual void	scan (void)
	Scan the CFG for finding exit and builds virtual edges with entry and exit. More...

Protected Attributes
unsigned long	flags

EndBasicBlock	_entry

EndBasicBlock	_exit

bbs_t	_bbs

Static Protected Attributes
static const unsigned long	FLAG_Scanned = 0x01

static const unsigned long	FLAG_Virtual = 0x02

static const unsigned long	FLAG_Inlined = 0x04

Private Types
typedef genstruct::FragTable < BasicBlock * >	bbs_t

Private Member Functions
const bbs_t &	getBBS (void)

Private Attributes
Segment *	_seg

BasicBlock *	ent

Friends
class	CFGInfo

Detailed Description

Control Flow Graph representation.

Its entry basic block is given and the graph is built using following taken and not-taken properties of the block.

Member Typedef Documentation

typedef genstruct::FragTable<BasicBlock *> otawa::CFG::bbs_t

private

Constructor & Destructor Documentation

otawa::CFG::CFG	(	Segment *	seg,
		BasicBlock *	entry
	)

Constructor.

Add a property to the basic block for quick retrieval of the matching CFG.

References otawa::FUNCTION_LABEL, label(), and otawa::LABEL.

otawa::CFG::~CFG ( void )

virtual

References _bbs, otawa::cfgio::bb(), otawa::cfgio::edge(), and elm::genstruct::FragTable< T >::length().

otawa::CFG::CFG ( void )

protected

Build an empty CFG.

Member Function Documentation

void otawa::PropList::addProp ( Property * prop )

inherited

Add property to the list without checking of duplication.

Parameters

prop	Property to add.

References otawa::Property::_next.

Referenced by otawa::Identifier< T >::add(), otawa::ast::ASTInfo::ASTInfo(), otawa::Identifier< otawa::arm::Info * >::copy(), otawa::AbstractIdentifier::initProps(), otawa::ContextualProperty::make(), otawa::script::Script::makeConfig(), otawa::ccg::Builder::processLBlockSet(), otawa::ipet::ILPSystemGetter::processWorkSpace(), otawa::Identifier< T >::ref(), otawa::ContextualProperty::ref(), and otawa::ContextualProperty::refProps().

void otawa::PropList::addProps ( const PropList & props )

inherited

Add all properties from the given property list, in a reverse order.

Parameters

props Property list to clone.

References copy(), otawa::PropList::head, and otawa::Property::next().

Referenced by otawa::display::CFGDrawer::CFGDrawer(), otawa::display::GraphVizGraph::GraphVizGraph(), otawa::ParamFeature::instantiate(), otawa::Manager::loadXML(), otawa::display::GraphVizGraph::newEdge(), otawa::display::GraphVizGraph::newNode(), otawa::PropList::operator=(), otawa::Process::Process(), otawa::PropList::PropList(), otawa::display::GraphVizItem::setProps(), otawa::VirtualBasicBlock::VirtualBasicBlock(), and otawa::VirtualCFG::VirtualCFG().

Address otawa::CFG::address ( void )

Get the address of the first instruction of the CFG.

Returns: Return address of the first instruction.

References otawa::BasicBlock::address(), otawa::cfgio::edge(), ent, entry(), and otawa::Address::null.

Referenced by otawa::PCGBlock::getAddress(), makeAddress(), and nameOf().

void otawa::PropList::clearProps ( void )

inherited

Remove all properties from the list.

References otawa::Property::next().

Referenced by otawa::PSTBuilder::getVCFG(), otawa::PropList::operator=(), otawa::display::GraphVizItem::setProps(), otawa::PropList::~PropList(), and otawa::WorkSpace::~WorkSpace().

int otawa::CFG::countBB ( void )

inline

BasicBlock * otawa::CFG::entry ( void )

inline

Get the entry basic block of the CFG.

Returns: Entry basic block.

References _entry, FLAG_Scanned, flags, and scan().

Referenced by otawa::ipet::BasicConstraintsBuilder::addEntryConstraint(), address(), otawa::DelayedBuilder::buildBB(), otawa::Dominance::ensure(), otawa::PostDominance::ensure(), otawa::ForwardCFGAdapter::entry(), otawa::dfa::Predecessor::entry(), otawa::PSTBuilder::getVCFG(), label(), otawa::cfgio::Output::processCFG(), otawa::BBStatCollector::processCFG(), otawa::CFGSaver::processCFG(), otawa::BBRatioDisplayer::processCFG(), otawa::ContextualProcessor::processCFG(), otawa::PSTBuilder::processCFG(), otawa::LoopReductor::processWorkSpace(), otawa::LoopUnroller::processWorkSpace(), otawa::SubCFGBuilder::processWorkSpace(), otawa::DelayedBuilder::processWorkSpace(), otawa::ipet::BasicConstraintsBuilder::processWorkSpace(), otawa::LoopReductor::reduce(), otawa::SESERegion::SESERegion(), otawa::dfa::hai::HalfAbsInt< FixPoint >::solve(), otawa::LoopUnroller::unroll(), otawa::VirtualCFG::virtualize(), otawa::Virtualizer::virtualize(), and otawa::Virtualizer::virtualizeCFG().

BasicBlock * otawa::CFG::exit ( void )

inline

Property * otawa::PropList::extractProp ( const AbstractIdentifier * id )

inherited

Remove a property matching the given identifier and return it.

Caller is responsible of the management of the obtained property.

Parameters

id	Identifier of the property to extract.

References otawa::Property::_next, and otawa::Property::next().

Referenced by otawa::script::Script::makeConfig().

Property * otawa::PropList::extractProp ( const AbstractIdentifier & id )

inlineinherited

Remove a property matching the given identifier and return it.

Caller is responsible of the management of the obtained property.

Parameters

id	Identifier of the property to extract.

References otawa::PropList::extractProp().

Referenced by otawa::PropList::extractProp().

BasicBlock * otawa::CFG::firstBB ( void )

Get the first basic block of the CFG.

Returns: First basic block.

References _bbs, FLAG_Scanned, flags, and scan().

Referenced by otawa::DelayedBuilder::buildEdges(), firstInst(), and otawa::etime::EdgeTimeBuilder::processEdge().

Inst * otawa::CFG::firstInst ( void )

Get the first instruction of the CFG.

Returns: First instruction of the CFG.

References otawa::cfgio::bb(), firstBB(), FLAG_Scanned, flags, and scan().

Referenced by otawa::Virtualizer::isInlined(), otawa::CFGProcessor::str(), otawa::VirtualCFG::virtualize(), and otawa::Virtualizer::virtualize().

string otawa::CFG::format ( const Address & addr )

Format the display of the given address relativelt to the given CFG.

Parameters

addr	Address to format.

Returns: Formatted address.

References elm::_, otawa::ot::address(), elm::io::hex(), and otawa::display::LABEL.

const bbs_t& otawa::CFG::getBBS ( void )

inlineprivate

References _bbs, FLAG_Scanned, flags, and scan().

Property * otawa::PropList::getProp ( const AbstractIdentifier * id ) const

inherited

Find a property by its identifier.

Parameters

id	Identifier of the property to find.

Returns: Found property or null.

References otawa::Property::_next, and otawa::Property::next().

Referenced by otawa::Identifier< otawa::arm::Info * >::exists(), otawa::ContextualProperty::exists(), otawa::ContextualProperty::find(), otawa::Identifier< T >::get(), otawa::PropList::hasProp(), otawa::ContextualProperty::make(), otawa::ParamFeature::matches(), otawa::ImmutableRef< T, I >::print(), otawa::ContextualProperty::print(), otawa::Identifier< T >::ref(), otawa::ContextualProperty::ref(), otawa::ContextualProperty::refProps(), otawa::Identifier< T >::set(), otawa::Identifier< T >::use(), and otawa::Identifier< T >::value().

bool otawa::PropList::hasProp ( const AbstractIdentifier & id ) const

inlineinherited

Test if the property list contains a property matching the given identifier.

Parameters

id	Property identifier to look for.

Returns: True if the list contains the matching property, false else.

References otawa::PropList::getProp().

Referenced by otawa::ipet::BasicConstraintsBuilder::addEntryConstraint(), otawa::Monitor::configure(), otawa::ImmutableRef< T, I >::exists(), and otawa::Manager::setVerbosity().

bool otawa::CFG::isInlined ( void ) const

inline

References FLAG_Inlined, and flags.

Referenced by otawa::VirtualCFG::virtualize().

bool otawa::CFG::isVirtual ( void ) const

inline

References FLAG_Virtual, and flags.

Referenced by otawa::SubCFGBuilder::processWorkSpace().

String otawa::CFG::label ( void )

Get some label to identify the CFG.

Returns: CFG label (if any) or empty string.

References ent, entry(), otawa::BasicBlock::firstInst(), otawa::FUNCTION_LABEL, otawa::LABEL, and out.

Referenced by otawa::CFGBuilder::addCFG(), otawa::ContextTree::addChild(), otawa::PCGBuilder::addPCGBlock(), otawa::dfa::hai::UnrollingListener< P >::blockInterpreted(), CFG(), otawa::ContextTree::ContextTree(), otawa::etime::EdgeTimeBuilder::contributeSplit(), otawa::display::CFGOutput::genGraphLabel(), otawa::PCGBlock::getName(), makeAddress(), otawa::ipet::VarAssignment::makeEdgeVar(), otawa::ipet::VarAssignment::makeNodeVar(), name(), nameOf(), otawa::display::CFGDrawer::onCall(), print(), otawa::ipet::BasicObjectFunctionBuilder::processBB(), otawa::ipet::FlowFactConstraintBuilder::processBB(), otawa::BBRatioDisplayer::processBB(), otawa::cfgio::Output::processCFG(), otawa::CFGChecker::processCFG(), otawa::BBRatioDisplayer::processCFG(), otawa::display::CFGOutput::processCFG(), otawa::ContextualProcessor::processCFG(), otawa::ccg::ConstraintBuilder::processLBlockSet(), otawa::dcache::CatConstraintBuilder::processWorkSpace(), otawa::StackAnalysis::processWorkSpace(), otawa::CFGCollector::processWorkSpace(), otawa::CFGProcessor::processWorkSpace(), otawa::clp::Analysis::processWorkSpace(), and otawa::Virtualizer::virtualize().

string otawa::CFG::name ( void )

Build a name that identifies this CFG and is valid C name.

Returns: Name of the CFG.

References _, otawa::BasicBlock::address(), ent, and label().

int otawa::CFG::number ( void )

inline

References otawa::INDEX.

Referenced by otawa::dfa::hai::UnrollingListener< P >::blockInterpreted(), otawa::dfa::hai::DefaultListener< P >::blockInterpreted(), otawa::dfa::hai::WideningListener< P >::blockInterpreted(), otawa::cfgio::Output::id(), and otawa::cfgio::Output::processCFG().

void otawa::CFG::numberBB ( void )

Number the basic block of the CFG, that is, hook a property with ID_Index identifier and the integer value of the number to each basic block.

The entry get the number 0 et the exit the last number.

References _bbs, otawa::INDEX, and elm::genstruct::FragTable< T >::length().

Referenced by otawa::PSTBuilder::getVCFG(), and otawa::Virtualizer::virtualizeCFG().

void otawa::CFG::print ( io::Output & out )

Print a reference for the CFG.

Parameters

out	Output stream.

References label().

Referenced by otawa::operator<<().

void otawa::PropList::print ( elm::io::Output & out ) const

inherited

Display the current property list.

Parameters

out	Output to use.

Referenced by otawa::operator<<(), and otawa::ContextualProperty::print().

void otawa::PropList::removeAllProp ( const AbstractIdentifier * id )

inherited

Remove all the properties matching the given identifier.

Parameters

id	Identifier of properties to remove.

References otawa::Property::_next, and otawa::Property::next().

Referenced by otawa::LoopUnroller::unroll().

void otawa::PropList::removeProp ( const AbstractIdentifier * id )

inherited

Remove a property matching the given identifier.

Parameters

id	Identifier of the property to remove.

References otawa::Property::_next, and otawa::Property::next().

Referenced by otawa::PSTBuilder::buildTree(), otawa::BBRemover< T >::clean(), otawa::display::CFGOutput::processCFG(), otawa::SubCFGBuilder::processWorkSpace(), otawa::Ref< T, I >::remove(), and otawa::ContextualPath::Ref< T >::remove().

void otawa::PropList::removeProp ( const AbstractIdentifier & id )

inlineinherited

References otawa::PropList::removeProp().

Referenced by otawa::PropList::removeProp().

void otawa::CFG::scan ( void )

protectedvirtual

Scan the CFG for finding exit and builds virtual edges with entry and exit.

For memory-place and time purposes, this method is only called when the CFG is used (call to an accessors method).

Reimplemented in otawa::VirtualCFG.

References _bbs, _entry, _exit, elm::genstruct::FragTable< T >::add(), otawa::BasicBlock::address(), otawa::cfgio::bb(), otawa::Edge::CALL, otawa::cfgio::edge(), ent, otawa::ENTRY, otawa::BasicBlock::FLAG_Call, FLAG_Scanned, flags, elm::genstruct::VectorQueue< T, class >::get(), otawa::INDEX, otawa::BasicBlock::isReturn(), elm::genstruct::FragTable< T >::length(), elm::genstruct::VectorQueue< T, class >::put(), otawa::Edge::toCall(), and otawa::Edge::VIRTUAL.

Referenced by countBB(), entry(), exit(), firstBB(), firstInst(), and getBBS().

Segment * otawa::CFG::segment ( void ) const

inline

References _seg.

void otawa::PropList::setProp ( Property * prop )

inherited

Set the property in the property list removing any double.

Parameters

prop	Property to set.

References otawa::Property::_next, otawa::Property::id(), and otawa::Property::next().

void otawa::PropList::setProp ( const AbstractIdentifier * id )

inlineinherited

References otawa::PropList::setProp().

Referenced by otawa::PropList::setProp().

Friends And Related Function Documentation

friend class CFGInfo

friend

Member Data Documentation

bbs_t otawa::CFG::_bbs

protected

Referenced by otawa::VirtualCFG::addBB(), countBB(), firstBB(), getBBS(), numberBB(), otawa::VirtualCFG::numberBBs(), otawa::VirtualCFG::removeBB(), otawa::VirtualCFG::scan(), scan(), otawa::VirtualCFG::VirtualCFG(), otawa::VirtualCFG::virtualize(), and ~CFG().

EndBasicBlock otawa::CFG::_entry

protected

Referenced by entry(), otawa::VirtualCFG::scan(), scan(), and otawa::VirtualCFG::VirtualCFG().

EndBasicBlock otawa::CFG::_exit

protected

Referenced by exit(), otawa::VirtualCFG::scan(), scan(), and otawa::VirtualCFG::VirtualCFG().

Segment* otawa::CFG::_seg

private

Referenced by segment().

const PropList otawa::PropList::EMPTY

staticinherited

This is an empty proplist for convenience.

BasicBlock* otawa::CFG::ent

mutableprivate

Referenced by address(), label(), name(), and scan().

const unsigned long otawa::CFG::FLAG_Inlined = 0x04

staticprotected

Referenced by isInlined(), and otawa::VirtualCFG::VirtualCFG().

const unsigned long otawa::CFG::FLAG_Scanned = 0x01

staticprotected

Referenced by countBB(), entry(), exit(), firstBB(), firstInst(), getBBS(), otawa::VirtualCFG::scan(), scan(), and otawa::VirtualCFG::VirtualCFG().

const unsigned long otawa::CFG::FLAG_Virtual = 0x02

staticprotected

Referenced by isVirtual(), and otawa::VirtualCFG::VirtualCFG().

unsigned long otawa::CFG::flags

protected

Referenced by countBB(), entry(), exit(), firstBB(), firstInst(), getBBS(), isInlined(), isVirtual(), otawa::VirtualCFG::scan(), scan(), and otawa::VirtualCFG::VirtualCFG().

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

include/otawa/cfg/CFG.h
src/prog/CFG.cpp

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation