A single entry single exit Region. More...

#include <RegionInfo.h>

Inheritance diagram for llvm::Region:

Collaboration diagram for llvm::Region:

Classes
class	block_iterator_wrapper

Public Types
enum	PrintStyle { PrintNone, PrintBB, PrintRN }
	PrintStyle - Print region in difference ways. More...

Public Member Functions
	Region (BasicBlock Entry, BasicBlock Exit, RegionInfo RI, DominatorTree DT, Region *Parent=0)
	Create a new region. More...

	~Region ()
	Delete the Region and all its subregions. More...

BasicBlock *	getEntry () const
	Get the entry BasicBlock of the Region. More...

void	replaceEntry (BasicBlock *BB)
	Replace the entry basic block of the region with the new basic block. More...

void	replaceExit (BasicBlock *BB)
	Replace the exit basic block of the region with the new basic block. More...

void	replaceEntryRecursive (BasicBlock *NewEntry)
	Recursively replace the entry basic block of the region. More...

void	replaceExitRecursive (BasicBlock *NewExit)
	Recursively replace the exit basic block of the region. More...

BasicBlock *	getExit () const
	Get the exit BasicBlock of the Region. More...

Region *	getParent () const
	Get the parent of the Region. More...

RegionNode *	getNode () const
	Get the RegionNode representing the current Region. More...

unsigned	getDepth () const
	Get the nesting level of this Region. More...

bool	isTopLevelRegion () const
	Check if a Region is the TopLevel region. More...

Region *	getExpandedRegion () const
	Return a new (non canonical) region, that is obtained by joining this region with its predecessors. More...

BasicBlock *	getEnteringBlock () const
	Return the first block of this region's single entry edge, if existing. More...

BasicBlock *	getExitingBlock () const
	Return the first block of this region's single exit edge, if existing. More...

bool	isSimple () const
	Is this a simple region? More...

std::string	getNameStr () const
	Returns the name of the Region. More...

RegionInfo *	getRegionInfo () const
	Return the RegionInfo object, that belongs to this Region. More...

void	print (raw_ostream &OS, bool printTree=true, unsigned level=0, enum PrintStyle Style=PrintNone) const
	Print the region. More...

void	dump () const
	Print the region to stderr. More...

bool	contains (const BasicBlock *BB) const
	Check if the region contains a BasicBlock. More...

bool	contains (const Region *SubRegion) const
	Check if the region contains another region. More...

bool	contains (const Instruction *Inst) const
	Check if the region contains an Instruction. More...

bool	contains (const Loop *L) const
	Check if the region contains a loop. More...

Loop *	outermostLoopInRegion (Loop *L) const
	Get the outermost loop in the region that contains a loop. More...

Loop *	outermostLoopInRegion (LoopInfo LI, BasicBlock BB) const
	Get the outermost loop in the region that contains a basic block. More...

Region *	getSubRegionNode (BasicBlock *BB) const
	Get the subregion that starts at a BasicBlock. More...

RegionNode *	getNode (BasicBlock *BB) const
	Get the RegionNode for a BasicBlock. More...

RegionNode *	getBBNode (BasicBlock *BB) const
	Get the BasicBlock RegionNode for a BasicBlock. More...

void	addSubRegion (Region *SubRegion, bool moveChildren=false)
	Add a new subregion to this Region. More...

Region *	removeSubRegion (Region *SubRegion)
	Remove a subregion from this Region. More...

void	transferChildrenTo (Region *To)
	Move all direct child nodes of this Region to another Region. More...

void	verifyRegion () const
	Verify if the region is a correct region. More...

void	clearNodeCache ()
	Clear the cache for BB RegionNodes. More...

Public Member Functions inherited from llvm::RegionNode
	RegionNode (Region Parent, BasicBlock Entry, bool isSubRegion=0)
	Create a RegionNode. More...

Region *	getParent () const
	Get the parent Region of this RegionNode. More...

BasicBlock *	getEntry () const
	Get the entry BasicBlock of this RegionNode. More...

template<class T >
T *	getNodeAs () const
	Get the content of this RegionNode. More...

bool	isSubRegion () const
	Is this RegionNode a subregion? More...

template<>
BasicBlock *	getNodeAs () const

template<>
Region *	getNodeAs () const

Friends
class	RegionInfo

Subregion Iterators
These iterators iterator over all subregions of this Region.
typedef RegionSet::iterator	iterator

typedef RegionSet::const_iterator	const_iterator

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

BasicBlock Iterators
These iterators iterate over all BasicBlocks that are contained in this Region. The iterator also iterates over BasicBlocks that are elements of a subregion of this Region. It is therefore called a flat iterator.
typedef block_iterator_wrapper < false >	block_iterator

typedef block_iterator_wrapper < true >	const_block_iterator

block_iterator	block_begin ()

block_iterator	block_end ()

const_block_iterator	block_begin () const

const_block_iterator	block_end () const

Element Iterators
These iterators iterate over all BasicBlock and subregion RegionNodes that are direct children of this Region. It does not iterate over any RegionNodes that are also element of a subregion of this Region.
typedef df_iterator < RegionNode , SmallPtrSet < RegionNode , 8 >, false, GraphTraits< RegionNode * > >	element_iterator

typedef df_iterator< const RegionNode , SmallPtrSet < const RegionNode , 8 > , false, GraphTraits< const RegionNode * > >	const_element_iterator

element_iterator	element_begin ()

element_iterator	element_end ()

const_element_iterator	element_begin () const

const_element_iterator	element_end () const

Additional Inherited Members
Protected Attributes inherited from llvm::RegionNode
PointerIntPair< BasicBlock *, 1, bool >	entry

Region *	parent
	The parent Region of this RegionNode. More...

Detailed Description

A single entry single exit Region.

A Region is a connected subgraph of a control flow graph that has exactly two connections to the remaining graph. It can be used to analyze or optimize parts of the control flow graph.

A simple Region is connected to the remaining graph by just two edges. One edge entering the Region and another one leaving the Region.

An extended Region (or just Region) is a subgraph that can be transform into a simple Region. The transformation is done by adding BasicBlocks that merge several entry or exit edges so that after the merge just one entry and one exit edge exists.

The Entry of a Region is the first BasicBlock that is passed after entering the Region. It is an element of the Region. The entry BasicBlock dominates all BasicBlocks in the Region.

The Exit of a Region is the first BasicBlock that is passed after leaving the Region. It is not an element of the Region. The exit BasicBlock, postdominates all BasicBlocks in the Region.

A canonical Region cannot be constructed by combining smaller Regions.

Region A is the parent of Region B, if B is completely contained in A.

Two canonical Regions either do not intersect at all or one is the parent of the other.

The Program Structure Tree is a graph (V, E) where V is the set of Regions in the control flow graph and E is the parent relation of these Regions.

Example:

/// A simple control flow graph, that contains two regions.
///
///        1
///       / |
///      2   |
///     / \   3
///    4   5  |
///    |   |  |
///    6   7  8
///     \  | /
///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
///        9        Region B: 2 -> 9 {2,4,5,6,7}
///

You can obtain more examples by either calling

<tt> "opt -regions -analyze anyprogram.ll" </tt>
or
<tt> "opt -view-regions-only anyprogram.ll" </tt>

on any LLVM file you are interested in.

The first call returns a textual representation of the program structure
tree, the second one creates a graphical representation using graphviz.

Definition at line 202 of file RegionInfo.h.

Member Typedef Documentation

typedef block_iterator_wrapper<false> llvm::Region::block_iterator

Definition at line 531 of file RegionInfo.h.

typedef block_iterator_wrapper<true> llvm::Region::const_block_iterator

Definition at line 532 of file RegionInfo.h.

typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>, false, GraphTraits<const RegionNode*> > llvm::Region::const_element_iterator

Definition at line 561 of file RegionInfo.h.

typedef RegionSet::const_iterator llvm::Region::const_iterator

Definition at line 481 of file RegionInfo.h.

typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false, GraphTraits<RegionNode*> > llvm::Region::element_iterator

Definition at line 557 of file RegionInfo.h.

typedef RegionSet::iterator llvm::Region::iterator

Definition at line 480 of file RegionInfo.h.

Member Enumeration Documentation

enum llvm::Region::PrintStyle

PrintStyle - Print region in difference ways.

Enumerator
PrintNone
PrintBB
PrintRN

Definition at line 354 of file RegionInfo.h.

Constructor & Destructor Documentation

Region::Region	(	BasicBlock *	Entry,
		BasicBlock *	Exit,
		RegionInfo *	RI,
		DominatorTree *	DT,
		Region *	Parent = `0`
	)

Create a new region.

Region Implementation.

Parameters

Entry	The entry basic block of the region.
Exit	The exit basic block of the region.
RI	The region info object that is managing this region.
DT	The dominator tree of the current function.
Parent	The surrounding region or NULL if this is a top level region.

Definition at line 53 of file RegionInfo.cpp.

Region::~Region ( )

Delete the Region and all its subregions.

Definition at line 57 of file RegionInfo.cpp.

References begin(), end(), and I.

Member Function Documentation

void Region::addSubRegion	(	Region *	SubRegion,
		bool	moveChildren = `false`
	)

Add a new subregion to this Region.

Parameters

SubRegion	The new subregion that will be added.
moveChildren	Move the children of this region, that are also contained in SubRegion into SubRegion.

Definition at line 342 of file RegionInfo.cpp.

References begin(), contains(), element_begin(), element_end(), end(), I, llvm::RegionNode::parent, and llvm::RegionInfo::setRegionFor().

iterator llvm::Region::begin ( )

inline

Definition at line 483 of file RegionInfo.h.

Referenced by addRegionIntoQueue(), addSubRegion(), clearNodeCache(), print(), llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster(), removeSubRegion(), replaceEntryRecursive(), replaceExitRecursive(), transferChildrenTo(), and ~Region().

const_iterator llvm::Region::begin ( ) const

inline

Definition at line 486 of file RegionInfo.h.

block_iterator llvm::Region::block_begin ( )

inline

Definition at line 534 of file RegionInfo.h.

References getEntry(), and getExit().

Referenced by buildExtractionBlockSet(), print(), and llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

const_block_iterator llvm::Region::block_begin ( ) const

inline

Definition at line 542 of file RegionInfo.h.

References getEntry(), and getExit().

block_iterator llvm::Region::block_end ( )

inline

Definition at line 538 of file RegionInfo.h.

Referenced by buildExtractionBlockSet(), print(), and llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

const_block_iterator llvm::Region::block_end ( ) const

inline

Definition at line 545 of file RegionInfo.h.

void Region::clearNodeCache ( )

Clear the cache for BB RegionNodes.

After calling this function the BasicBlock RegionNodes will be stored at different memory locations. RegionNodes obtained before this function is called are therefore not comparable to RegionNodes abtained afterwords.

Definition at line 466 of file RegionInfo.cpp.

References begin(), end(), I, and llvm::ARM_PROC::IE.

Referenced by llvm::RegionInfo::clearNodeCache().

bool Region::contains ( const BasicBlock * BB ) const

Check if the region contains a BasicBlock.

Parameters

BB	The BasicBlock that might be contained in this Region.

Returns: True if the block is contained in the region otherwise false.

Definition at line 112 of file RegionInfo.cpp.

References llvm::DominatorTree::dominates(), llvm::RegionNode::entry, getEntry(), getExit(), and llvm::DominatorTree::getNode().

Referenced by addSubRegion(), contains(), getBBNode(), llvm::RegionInfo::getCommonRegion(), getEnteringBlock(), getExitingBlock(), llvm::RegionInfo::getMaxRegionExit(), getNode(), getSubRegionNode(), and outermostLoopInRegion().

bool llvm::Region::contains ( const Region * SubRegion ) const

inline

Check if the region contains another region.

Parameters

SubRegion The region that might be contained in this Region.

Returns: True if SubRegion is contained in the region otherwise false.

Definition at line 377 of file RegionInfo.h.

References contains(), getEntry(), and getExit().

bool llvm::Region::contains ( const Instruction * Inst ) const

inline

Check if the region contains an Instruction.

Parameters

Inst	The Instruction that might be contained in this region.

Returns: True if the Instruction is contained in the region otherwise false.

Definition at line 390 of file RegionInfo.h.

References contains(), and llvm::Instruction::getParent().

bool Region::contains ( const Loop * L ) const

Check if the region contains a loop.

Parameters

L	The loop that might be contained in this region.

Returns: True if the loop is contained in the region otherwise false. In case a NULL pointer is passed to this function the result is false, except for the region that describes the whole function. In that case true is returned.

Definition at line 128 of file RegionInfo.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), contains(), llvm::SmallVectorTemplateCommon< T >::end(), getExit(), llvm::LoopBase< N, M >::getExitingBlocks(), and llvm::LoopBase< N, M >::getHeader().

void Region::dump ( ) const

Print the region to stderr.

Definition at line 461 of file RegionInfo.cpp.

References llvm::dbgs(), getDepth(), print(), and printStyle.

Region::element_iterator Region::element_begin ( )

Definition at line 279 of file RegionInfo.cpp.

Referenced by addSubRegion(), and print().

Region::const_element_iterator Region::element_begin ( ) const

Definition at line 287 of file RegionInfo.cpp.

Region::element_iterator Region::element_end ( )

Definition at line 283 of file RegionInfo.cpp.

Referenced by addSubRegion(), and print().

Region::const_element_iterator Region::element_end ( ) const

Definition at line 291 of file RegionInfo.cpp.

iterator llvm::Region::end ( )

inline

Definition at line 484 of file RegionInfo.h.

Referenced by addRegionIntoQueue(), addSubRegion(), clearNodeCache(), print(), llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster(), replaceEntryRecursive(), replaceExitRecursive(), transferChildrenTo(), and ~Region().

const_iterator llvm::Region::end ( ) const

inline

Definition at line 487 of file RegionInfo.h.

RegionNode * Region::getBBNode ( BasicBlock * BB ) const

Get the BasicBlock RegionNode for a BasicBlock.

Parameters

BB	The BasicBlock for which the RegionNode is requested.

Returns: The RegionNode representing the BB.

Definition at line 313 of file RegionInfo.cpp.

References contains().

Referenced by getNode(), llvm::RNSuccIterator< FlatIt< NodeType > >::operator*(), and llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

unsigned Region::getDepth ( ) const

Get the nesting level of this Region.

An toplevel Region has depth 0.

Returns: The depth of the region.

Definition at line 386 of file RegionInfo.cpp.

References llvm::RegionNode::parent.

Referenced by dump(), and llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

BasicBlock * Region::getEnteringBlock ( ) const

Return the first block of this region's single entry edge, if existing.

Returns: The BasicBlock starting this region's single entry edge, else NULL.

Definition at line 166 of file RegionInfo.cpp.

References contains(), llvm::RegionNode::entry, getEntry(), llvm::DominatorTree::getNode(), llvm::pred_begin(), and llvm::pred_end().

Referenced by isSimple().

BasicBlock* llvm::Region::getEntry ( ) const

inline

Get the entry BasicBlock of the Region.

Returns: The entry BasicBlock of the region.

Definition at line 255 of file RegionInfo.h.

References llvm::RegionNode::getEntry().

Referenced by block_begin(), contains(), getEnteringBlock(), getExpandedRegion(), llvm::RegionInfo::getMaxRegionExit(), getNameStr(), getSubRegionNode(), replaceEntryRecursive(), llvm::RGPassManager::runOnFunction(), llvm::RegionInfo::splitBlock(), and verifyRegion().

BasicBlock* llvm::Region::getExit ( ) const

inline

Get the exit BasicBlock of the Region.

Returns: The exit BasicBlock of the Region, NULL if this is the TopLevel Region.

Definition at line 290 of file RegionInfo.h.

Referenced by block_begin(), contains(), getExitingBlock(), getExpandedRegion(), llvm::RegionInfo::getMaxRegionExit(), getNameStr(), llvm::RNSuccIterator< FlatIt< NodeType > >::operator*(), and replaceExitRecursive().

BasicBlock * Region::getExitingBlock ( ) const

Return the first block of this region's single exit edge, if existing.

Returns: The BasicBlock starting this region's single exit edge, else NULL.

Definition at line 185 of file RegionInfo.cpp.

References contains(), getExit(), llvm::pred_begin(), and llvm::pred_end().

Referenced by isSimple().

Region * Region::getExpandedRegion ( ) const

Return a new (non canonical) region, that is obtained by joining this region with its predecessors.

Returns: A region also starting at getEntry(), but reaching to the next basic block that forms with getEntry() a (non canonical) region. NULL if such a basic block does not exist.

Definition at line 395 of file RegionInfo.cpp.

References llvm::DominatorTree::dominates(), getEntry(), getExit(), llvm::TerminatorInst::getNumSuccessors(), getParent(), llvm::RegionInfo::getRegionFor(), llvm::BasicBlock::getTerminator(), llvm::pred_begin(), llvm::pred_end(), and llvm::succ_begin().

std::string Region::getNameStr ( ) const

Returns the name of the Region.

Returns: The Name of the Region.

Definition at line 211 of file RegionInfo.cpp.

References getEntry(), getExit(), llvm::Intrinsic::getName(), llvm::Value::getName(), and llvm::WriteAsOperand().

Referenced by llvm::operator<<(), print(), and llvm::RGPassManager::runOnFunction().

RegionNode* llvm::Region::getNode ( ) const

inline

Get the RegionNode representing the current Region.

Returns: The RegionNode representing the current Region.

Definition at line 299 of file RegionInfo.h.

RegionNode * Region::getNode ( BasicBlock * BB ) const

Get the RegionNode for a BasicBlock.

Parameters

BB	The BasicBlock at which the RegionNode should start.

Returns: If available, the RegionNode that represents the subregion starting at BB. If no subregion starts at BB, the RegionNode representing BB.

Definition at line 326 of file RegionInfo.cpp.

References contains(), getBBNode(), and getSubRegionNode().

Region* llvm::Region::getParent ( ) const

inline

Get the parent of the Region.

Returns: The parent of the Region or NULL if this is a top level Region.

Definition at line 295 of file RegionInfo.h.

References llvm::RegionNode::getParent().

Referenced by llvm::RegionInfo::getCommonRegion(), llvm::DOTGraphTraits< RegionInfo * >::getEdgeAttributes(), getExpandedRegion(), llvm::RegionInfo::getMaxRegionExit(), getSubRegionNode(), and llvm::RegionInfo::splitBlock().

RegionInfo* llvm::Region::getRegionInfo ( ) const

inline

Return the RegionInfo object, that belongs to this Region.

Definition at line 349 of file RegionInfo.h.

Referenced by llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

Region * Region::getSubRegionNode ( BasicBlock * BB ) const

Get the subregion that starts at a BasicBlock.

Parameters

BB	The BasicBlock the subregion should start.

Returns: The Subregion if available, otherwise NULL.

Definition at line 295 of file RegionInfo.cpp.

References contains(), getEntry(), getParent(), and llvm::RegionInfo::getRegionFor().

Referenced by getNode().

bool Region::isSimple ( ) const

Is this a simple region?

A region is simple if it has exactly one exit and one entry edge.

Returns: True if the Region is simple.

Definition at line 207 of file RegionInfo.cpp.

References getEnteringBlock(), getExitingBlock(), and isTopLevelRegion().

Referenced by llvm::DOTGraphTraits< RegionInfo * >::printRegionCluster().

bool llvm::Region::isTopLevelRegion ( ) const

inline

Check if a Region is the TopLevel region.

The toplevel region represents the whole function.

Definition at line 313 of file RegionInfo.h.

Referenced by isSimple(), and llvm::RegionInfo::splitBlock().

Loop * Region::outermostLoopInRegion ( Loop * L ) const

Get the outermost loop in the region that contains a loop.

Find for a Loop L the outermost loop OuterL that is a parent loop of L and is itself contained in the region.

Parameters

L	The loop the lookup is started.

Returns: The outermost loop in the region, NULL if such a loop does not exist or if the region describes the whole function.

Definition at line 149 of file RegionInfo.cpp.

References contains(), and llvm::LoopBase< N, M >::getParentLoop().

Referenced by outermostLoopInRegion().

Loop * Region::outermostLoopInRegion	(	LoopInfo *	LI,
		BasicBlock *	BB
	)		const

Get the outermost loop in the region that contains a basic block.

Find for a basic block BB the outermost loop L that contains BB and is itself contained in the region.

Parameters

LI	A pointer to a LoopInfo analysis.
BB	The basic block surrounded by the loop.

Returns: The outermost loop in the region, NULL if such a loop does not exist or if the region describes the whole function.

Definition at line 160 of file RegionInfo.cpp.

References llvm::LoopInfo::getLoopFor(), and outermostLoopInRegion().

void Region::print	(	raw_ostream &	OS,
		bool	printTree = `true`,
		unsigned	level = `0`,
		enum PrintStyle	Style = `PrintNone`
	)		const

Print the region.

Parameters

OS	The output stream the Region is printed to.
printTree	Print also the tree of subregions.
level	The indentation level used for printing.

Definition at line 427 of file RegionInfo.cpp.

References begin(), block_begin(), block_end(), element_begin(), element_end(), end(), getNameStr(), I, llvm::raw_ostream::indent(), PrintBB, PrintNone, and PrintRN.

Referenced by dump(), and llvm::RegionInfo::print().

Region * Region::removeSubRegion ( Region * SubRegion )

Remove a subregion from this Region.

The subregion is not deleted, as it will probably be inserted into another region.

Parameters

SubRegion The SubRegion that will be removed.

Definition at line 377 of file RegionInfo.cpp.

References begin(), I, and llvm::RegionNode::parent.

void Region::replaceEntry ( BasicBlock * BB )

Replace the entry basic block of the region with the new basic block.

Parameters

BB	The new entry basic block of the region.

Definition at line 71 of file RegionInfo.cpp.

References llvm::RegionNode::entry, and llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits >::setPointer().

Referenced by replaceEntryRecursive(), and llvm::RegionInfo::splitBlock().

void Region::replaceEntryRecursive ( BasicBlock * NewEntry )

Recursively replace the entry basic block of the region.

This function replaces the entry basic block with a new basic block. It also updates all child regions that have the same entry basic block as this region.

Parameters

NewEntry The new entry basic block.

Definition at line 80 of file RegionInfo.cpp.

References begin(), end(), getEntry(), and replaceEntry().

void Region::replaceExit ( BasicBlock * BB )

Replace the exit basic block of the region with the new basic block.

Parameters

BB	The new exit basic block of the region.

Definition at line 75 of file RegionInfo.cpp.

Referenced by replaceExitRecursive().

void Region::replaceExitRecursive ( BasicBlock * NewExit )

Recursively replace the exit basic block of the region.

This function replaces the exit basic block with a new basic block. It also updates all child regions that have the same exit basic block as this region.

Parameters

NewExit The new exit basic block.

Definition at line 96 of file RegionInfo.cpp.

References begin(), end(), getExit(), and replaceExit().

void Region::transferChildrenTo ( Region * To )

Move all direct child nodes of this Region to another Region.

Parameters

To	The Region the child nodes will be transferred to.

Definition at line 334 of file RegionInfo.cpp.

References begin(), end(), and I.

void Region::verifyRegion ( ) const

Verify if the region is a correct region.

Check if this is a correctly build Region. This is an expensive check, as the complete CFG of the Region will be walked.

Definition at line 263 of file RegionInfo.cpp.

References getEntry(), and VerifyRegionInfo.

Referenced by llvm::RGPassManager::runOnFunction().

Friends And Related Function Documentation

friend class RegionInfo

friend

Definition at line 203 of file RegionInfo.h.

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

Classes

Public Types

Public Member Functions

Friends

Subregion Iterators

BasicBlock Iterators

Element Iterators

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation