A single entry single exit Region. More...

#include <RegionInfo.h>

Inheritance diagram for llvm::RegionBase< Tr >:

Collaboration diagram for llvm::RegionBase< Tr >:

Classes
class	block_iterator_wrapper
Public Types
enum	PrintStyle { PrintNone, PrintBB, PrintRN }
	PrintStyle - Print region in difference ways. More...
Public Member Functions
	RegionBase (BlockT Entry, BlockT Exit, RegionInfoT RI, DomTreeT DT, RegionT *Parent=nullptr)
	Create a new region.
	~RegionBase ()
	Delete the Region and all its subregions.
BlockT *	getEntry () const
	Get the entry BasicBlock of the Region.
void	replaceEntry (BlockT *BB)
	Replace the entry basic block of the region with the new basic block.
void	replaceExit (BlockT *BB)
	Replace the exit basic block of the region with the new basic block.
void	replaceEntryRecursive (BlockT *NewEntry)
	Recursively replace the entry basic block of the region.
void	replaceExitRecursive (BlockT *NewExit)
	Recursively replace the exit basic block of the region.
BlockT *	getExit () const
	Get the exit BasicBlock of the Region.
RegionT *	getParent () const
	Get the parent of the Region.
RegionNodeT *	getNode () const
	Get the RegionNode representing the current Region.
unsigned	getDepth () const
	Get the nesting level of this Region.
bool	isTopLevelRegion () const
	Check if a Region is the TopLevel region.
RegionT *	getExpandedRegion () const
	Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
BlockT *	getEnteringBlock () const
	Return the first block of this region's single entry edge, if existing.
BlockT *	getExitingBlock () const
	Return the first block of this region's single exit edge, if existing.
bool	isSimple () const
	Is this a simple region?
std::string	getNameStr () const
	Returns the name of the Region.
RegionInfoT *	getRegionInfo () const
	Return the RegionInfo object, that belongs to this Region.
void	print (raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
	Print the region.
void	dump () const
	Print the region to stderr.
bool	contains (const BlockT *BB) const
	Check if the region contains a BasicBlock.
bool	contains (const RegionT *SubRegion) const
	Check if the region contains another region.
bool	contains (const InstT *Inst) const
	Check if the region contains an Instruction.
bool	contains (const LoopT *L) const
	Check if the region contains a loop.
LoopT *	outermostLoopInRegion (LoopT *L) const
	Get the outermost loop in the region that contains a loop.
LoopT *	outermostLoopInRegion (LoopInfoT LI, BlockT BB) const
	Get the outermost loop in the region that contains a basic block.
RegionT *	getSubRegionNode (BlockT *BB) const
	Get the subregion that starts at a BasicBlock.
RegionNodeT *	getNode (BlockT *BB) const
	Get the RegionNode for a BasicBlock.
RegionNodeT *	getBBNode (BlockT *BB) const
	Get the BasicBlock RegionNode for a BasicBlock.
void	addSubRegion (RegionT *SubRegion, bool moveChildren=false)
	Add a new subregion to this Region.
RegionT *	removeSubRegion (RegionT *SubRegion)
	Remove a subregion from this Region.
void	transferChildrenTo (RegionT *To)
	Move all direct child nodes of this Region to another Region.
void	verifyRegion () const
	Verify if the region is a correct region.
void	clearNodeCache ()
	Clear the cache for BB RegionNodes.
Friends
class	RegionInfoBase< Tr >
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
typedef iterator_range < block_iterator >	block_range
typedef iterator_range < const_block_iterator >	const_block_range
block_iterator	block_begin ()
block_iterator	block_end ()
const_block_iterator	block_begin () const
const_block_iterator	block_end () const
block_range	blocks ()
	Returns a range view of the basic blocks in the region.
const_block_range	blocks () const
	Returns a range view of the basic blocks in the region.
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 < RegionNodeT , SmallPtrSet < RegionNodeT , 8 >, false, GraphTraits< RegionNodeT * > >	element_iterator
typedef df_iterator< const RegionNodeT , SmallPtrSet < const RegionNodeT , 8 > , false, GraphTraits< const RegionNodeT * > >	const_element_iterator
element_iterator	element_begin ()
element_iterator	element_end ()
const_element_iterator	element_begin () const
const_element_iterator	element_end () const

Detailed Description

template<class Tr>
class llvm::RegionBase< Tr >

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

"opt -regions -analyze anyprogram.ll" or "opt -view-regions-only anyprogram.ll"

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 247 of file RegionInfo.h.

Member Typedef Documentation

template<class Tr>

typedef block_iterator_wrapper<false> llvm::RegionBase< Tr >::block_iterator

Definition at line 592 of file RegionInfo.h.

template<class Tr>

typedef iterator_range<block_iterator> llvm::RegionBase< Tr >::block_range

Definition at line 604 of file RegionInfo.h.

template<class Tr>

typedef block_iterator_wrapper<true> llvm::RegionBase< Tr >::const_block_iterator

Definition at line 593 of file RegionInfo.h.

template<class Tr>

typedef iterator_range<const_block_iterator> llvm::RegionBase< Tr >::const_block_range

Definition at line 605 of file RegionInfo.h.

template<class Tr>

typedef df_iterator<const RegionNodeT *, SmallPtrSet<const RegionNodeT *, 8>, false, GraphTraits<const RegionNodeT *> > llvm::RegionBase< Tr >::const_element_iterator

Definition at line 631 of file RegionInfo.h.

template<class Tr>

typedef RegionSet::const_iterator llvm::RegionBase< Tr >::const_iterator

Definition at line 544 of file RegionInfo.h.

template<class Tr>

typedef df_iterator<RegionNodeT *, SmallPtrSet<RegionNodeT *, 8>, false, GraphTraits<RegionNodeT *> > llvm::RegionBase< Tr >::element_iterator

Definition at line 627 of file RegionInfo.h.

template<class Tr>

typedef RegionSet::iterator llvm::RegionBase< Tr >::iterator

Definition at line 543 of file RegionInfo.h.

Member Enumeration Documentation

template<class Tr>

enum llvm::RegionBase::PrintStyle

PrintStyle - Print region in difference ways.

Enumerator:

PrintNone
PrintBB
PrintRN

Definition at line 417 of file RegionInfo.h.

Constructor & Destructor Documentation

template<class Tr >

llvm::RegionBase< Tr >::RegionBase	(	BlockT *	Entry,
		BlockT *	Exit,
		typename Tr::RegionInfoT *	RInfo,
		DomTreeT *	DT,
		RegionT *	Parent = `nullptr`
	)

Create a new region.

RegionBase 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 35 of file RegionInfoImpl.h.

template<class Tr >

llvm::RegionBase< Tr >::~RegionBase ( )

Delete the Region and all its subregions.

Definition at line 41 of file RegionInfoImpl.h.

Member Function Documentation

template<class Tr >

void llvm::RegionBase< Tr >::addSubRegion	(	RegionT *	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 375 of file RegionInfoImpl.h.

References llvm::sys::path::begin(), llvm::sys::path::end(), and I.

template<class Tr>

iterator llvm::RegionBase< Tr >::begin ( ) [inline]

Definition at line 546 of file RegionInfo.h.

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

template<class Tr>

const_iterator llvm::RegionBase< Tr >::begin ( ) const [inline]

Definition at line 549 of file RegionInfo.h.

template<class Tr>

block_iterator llvm::RegionBase< Tr >::block_begin ( ) [inline]

Definition at line 595 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::blocks(), and buildExtractionBlockSet().

template<class Tr>

const_block_iterator llvm::RegionBase< Tr >::block_begin ( ) const [inline]

Definition at line 599 of file RegionInfo.h.

template<class Tr>

block_iterator llvm::RegionBase< Tr >::block_end ( ) [inline]

Definition at line 597 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::blocks(), and buildExtractionBlockSet().

template<class Tr>

const_block_iterator llvm::RegionBase< Tr >::block_end ( ) const [inline]

Definition at line 602 of file RegionInfo.h.

template<class Tr>

block_range llvm::RegionBase< Tr >::blocks ( ) [inline]

Returns a range view of the basic blocks in the region.

Definition at line 608 of file RegionInfo.h.

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

template<class Tr>

const_block_range llvm::RegionBase< Tr >::blocks ( ) const [inline]

Returns a range view of the basic blocks in the region.

This is the 'const' version of the range view.

Definition at line 615 of file RegionInfo.h.

template<class Tr >

void llvm::RegionBase< Tr >::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 519 of file RegionInfoImpl.h.

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

template<class Tr >

bool llvm::RegionBase< Tr >::contains ( const BlockT * 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 103 of file RegionInfoImpl.h.

References getEntry().

Referenced by llvm::RegionBase< RegionTraits< Function > >::contains().

template<class Tr>

bool llvm::RegionBase< Tr >::contains ( const RegionT * 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 440 of file RegionInfo.h.

template<class Tr>

bool llvm::RegionBase< Tr >::contains ( const InstT * 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 455 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::contains().

template<class Tr >

bool llvm::RegionBase< Tr >::contains ( const LoopT * 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 120 of file RegionInfoImpl.h.

References contains().

template<class Tr >

void llvm::RegionBase< Tr >::dump ( ) const

Print the region to stderr.

Definition at line 513 of file RegionInfoImpl.h.

References llvm::dbgs().

template<class Tr >

RegionBase< Tr >::element_iterator llvm::RegionBase< Tr >::element_begin ( )

Definition at line 298 of file RegionInfoImpl.h.

template<class Tr >

RegionBase< Tr >::const_element_iterator llvm::RegionBase< Tr >::element_begin ( ) const

Definition at line 309 of file RegionInfoImpl.h.

template<class Tr >

RegionBase< Tr >::element_iterator llvm::RegionBase< Tr >::element_end ( )

Definition at line 303 of file RegionInfoImpl.h.

template<class Tr >

RegionBase< Tr >::const_element_iterator llvm::RegionBase< Tr >::element_end ( ) const

Definition at line 316 of file RegionInfoImpl.h.

template<class Tr>

iterator llvm::RegionBase< Tr >::end ( ) [inline]

Definition at line 547 of file RegionInfo.h.

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

template<class Tr>

const_iterator llvm::RegionBase< Tr >::end ( ) const [inline]

Definition at line 550 of file RegionInfo.h.

template<class Tr >

Tr::RegionNodeT * llvm::RegionBase< Tr >::getBBNode ( BlockT * 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 342 of file RegionInfoImpl.h.

References contains().

template<class Tr >

unsigned llvm::RegionBase< Tr >::getDepth ( ) const

Get the nesting level of this Region.

An toplevel Region has depth 0.

Returns:: The depth of the region.

Definition at line 429 of file RegionInfoImpl.h.

References llvm::GlobalValue::getParent(), and getParent().

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

template<class Tr >

RegionBase< Tr >::BlockT * llvm::RegionBase< Tr >::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 162 of file RegionInfoImpl.h.

References contains(), and getEntry().

template<class Tr>

BlockT* llvm::RegionBase< Tr >::getEntry ( ) const [inline]

Get the entry BasicBlock of the Region.

Returns:: The entry BasicBlock of the region.

Reimplemented from llvm::RegionNodeBase< Tr >.

Definition at line 315 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::block_begin(), llvm::RegionBase< RegionTraits< Function > >::getEntry(), and llvm::RGPassManager::runOnFunction().

template<class Tr>

BlockT* llvm::RegionBase< Tr >::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 352 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::block_begin(), and llvm::RegionBase< RegionTraits< Function > >::contains().

template<class Tr >

RegionBase< Tr >::BlockT * llvm::RegionBase< Tr >::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 183 of file RegionInfoImpl.h.

References contains().

template<class Tr >

Tr::RegionT * llvm::RegionBase< Tr >::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 439 of file RegionInfoImpl.h.

References getEntry().

template<class Tr >

std::string llvm::RegionBase< Tr >::getNameStr ( ) const

Returns the name of the Region.

Returns:: The Name of the Region.

Definition at line 212 of file RegionInfoImpl.h.

References getEntry(), and llvm::Intrinsic::getName().

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

template<class Tr>

RegionNodeT* llvm::RegionBase< Tr >::getNode ( ) const [inline]

Get the RegionNode representing the current Region.

Returns:: The RegionNode representing the current Region.

Definition at line 363 of file RegionInfo.h.

template<class Tr >

Tr::RegionNodeT * llvm::RegionBase< Tr >::getNode ( BlockT * 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 357 of file RegionInfoImpl.h.

References contains().

template<class Tr>

RegionT* llvm::RegionBase< Tr >::getParent ( ) const [inline]

Get the parent of the Region.

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

Reimplemented from llvm::RegionNodeBase< Tr >.

Definition at line 357 of file RegionInfo.h.

Referenced by llvm::RegionBase< RegionTraits< Function > >::getParent().

template<class Tr>

RegionInfoT* llvm::RegionBase< Tr >::getRegionInfo ( ) const [inline]

Return the RegionInfo object, that belongs to this Region.

Definition at line 414 of file RegionInfo.h.

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

template<class Tr >

Tr::RegionT * llvm::RegionBase< Tr >::getSubRegionNode ( BlockT * 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 322 of file RegionInfoImpl.h.

References contains().

template<class Tr >

bool llvm::RegionBase< Tr >::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 RegionInfoImpl.h.

Referenced by llvm::DOTGraphTraits< RegionInfoPass * >::printRegionCluster(), llvm::MachineRegionInfo::updateStatistics(), and llvm::RegionInfo::updateStatistics().

template<class Tr>

bool llvm::RegionBase< Tr >::isTopLevelRegion ( ) const [inline]

Check if a Region is the TopLevel region.

The toplevel region represents the whole function.

Definition at line 378 of file RegionInfo.h.

template<class Tr >

Tr::LoopT * llvm::RegionBase< Tr >::outermostLoopInRegion ( LoopT * 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 142 of file RegionInfoImpl.h.

References contains().

template<class Tr >

Tr::LoopT * llvm::RegionBase< Tr >::outermostLoopInRegion	(	LoopInfoT *	LI,
		BlockT *	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 154 of file RegionInfoImpl.h.

template<class Tr >

void llvm::RegionBase< Tr >::print	(	raw_ostream &	OS,
		bool	printTree = `true`,
		unsigned	level = `0`,
		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 476 of file RegionInfoImpl.h.

References llvm::sys::path::begin(), llvm::sys::path::end(), I, and llvm::raw_ostream::indent().

template<class Tr >

Tr::RegionT * llvm::RegionBase< Tr >::removeSubRegion ( RegionT * 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 417 of file RegionInfoImpl.h.

References llvm::sys::path::begin(), and I.

template<class Tr >

void llvm::RegionBase< Tr >::replaceEntry ( BlockT * 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 54 of file RegionInfoImpl.h.

template<class Tr >

void llvm::RegionBase< Tr >::replaceEntryRecursive ( BlockT * 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 65 of file RegionInfoImpl.h.

References getEntry().

template<class Tr >

void llvm::RegionBase< Tr >::replaceExit ( BlockT * 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 59 of file RegionInfoImpl.h.

template<class Tr >

void llvm::RegionBase< Tr >::replaceExitRecursive ( BlockT * 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 84 of file RegionInfoImpl.h.

template<class Tr >

void llvm::RegionBase< Tr >::transferChildrenTo ( RegionT * 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 366 of file RegionInfoImpl.h.

References llvm::sys::path::begin(), llvm::sys::path::end(), and I.

template<class Tr >

void llvm::RegionBase< Tr >::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 277 of file RegionInfoImpl.h.

References getEntry().

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

Friends And Related Function Documentation

template<class Tr>

friend class RegionInfoBase< Tr > [friend]

Definition at line 263 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

Detailed Description

template<class Tr> class llvm::RegionBase< Tr >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<class Tr>
class llvm::RegionBase< Tr >