LLVM 20.0.0git
|
A single entry single exit Region. More...
#include "llvm/Analysis/RegionInfo.h"
Classes | |
class | block_iterator_wrapper |
Public Types | |
enum | PrintStyle { PrintNone , PrintBB , PrintRN } |
PrintStyle - Print region in difference ways. More... | |
Public Types inherited from llvm::RegionNodeBase< Tr > | |
using | BlockT = typename Tr::BlockT |
using | RegionT = typename Tr::RegionT |
Public Member Functions | |
RegionBase (BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr) | |
Create a new region. | |
RegionBase (const RegionBase &)=delete | |
RegionBase & | operator= (const RegionBase &)=delete |
~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 | getExitingBlocks (SmallVectorImpl< BlockT * > &Exitings) const |
Collect all blocks 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. | |
Public Member Functions inherited from llvm::RegionNodeBase< Tr > | |
RegionNodeBase (const RegionNodeBase &)=delete | |
RegionNodeBase & | operator= (const RegionNodeBase &)=delete |
RegionT * | getParent () const |
Get the parent Region of this RegionNode. | |
BlockT * | getEntry () const |
Get the entry BasicBlock of this RegionNode. | |
template<class T > | |
T * | getNodeAs () const |
Get the content of this RegionNode. | |
bool | isSubRegion () const |
Is this RegionNode a subregion? | |
BasicBlock * | getNodeAs () const |
Region * | getNodeAs () const |
MachineBasicBlock * | getNodeAs () const |
MachineRegion * | getNodeAs () const |
Friends | |
class | RegionInfoBase< Tr > |
Subregion Iterators | |
These iterators iterator over all subregions of this Region. | |
using | iterator = typename RegionSet::iterator |
using | const_iterator = typename RegionSet::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. | |
using | block_iterator = block_iterator_wrapper< false > |
using | const_block_iterator = block_iterator_wrapper< true > |
using | block_range = iterator_range< block_iterator > |
using | const_block_range = iterator_range< const_block_iterator > |
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. | |
using | element_iterator = df_iterator< RegionNodeT *, df_iterator_default_set< RegionNodeT * >, false, GraphTraits< RegionNodeT * > > |
using | const_element_iterator = df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > |
element_iterator | element_begin () |
element_iterator | element_end () |
iterator_range< element_iterator > | elements () |
const_element_iterator | element_begin () const |
const_element_iterator | element_end () const |
iterator_range< const_element_iterator > | elements () const |
Additional Inherited Members | |
Protected Member Functions inherited from llvm::RegionNodeBase< Tr > | |
RegionNodeBase (RegionT *Parent, BlockT *Entry, bool isSubRegion=false) | |
Create a RegionNode. | |
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 -passes='print<regions>' 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 252 of file RegionInfo.h.
using llvm::RegionBase< Tr >::block_iterator = block_iterator_wrapper<false> |
Definition at line 604 of file RegionInfo.h.
using llvm::RegionBase< Tr >::block_range = iterator_range<block_iterator> |
Definition at line 616 of file RegionInfo.h.
using llvm::RegionBase< Tr >::const_block_iterator = block_iterator_wrapper<true> |
Definition at line 605 of file RegionInfo.h.
using llvm::RegionBase< Tr >::const_block_range = iterator_range<const_block_iterator> |
Definition at line 617 of file RegionInfo.h.
using llvm::RegionBase< Tr >::const_element_iterator = df_iterator<const RegionNodeT *, df_iterator_default_set<const RegionNodeT *>, false, GraphTraits<const RegionNodeT *> > |
Definition at line 642 of file RegionInfo.h.
using llvm::RegionBase< Tr >::const_iterator = typename RegionSet::const_iterator |
Definition at line 556 of file RegionInfo.h.
using llvm::RegionBase< Tr >::element_iterator = df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false, GraphTraits<RegionNodeT *> > |
Definition at line 638 of file RegionInfo.h.
using llvm::RegionBase< Tr >::iterator = typename RegionSet::iterator |
Definition at line 555 of file RegionInfo.h.
enum llvm::RegionBase::PrintStyle |
PrintStyle - Print region in difference ways.
Enumerator | |
---|---|
PrintNone | |
PrintBB | |
PrintRN |
Definition at line 427 of file RegionInfo.h.
llvm::RegionBase< Tr >::RegionBase | ( | BlockT * | Entry, |
BlockT * | Exit, | ||
typename Tr::RegionInfoT * | RInfo, | ||
DomTreeT * | DT, | ||
RegionT * | Parent = nullptr |
||
) |
Create a new region.
RegionBase Implementation.
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 42 of file RegionInfoImpl.h.
|
delete |
llvm::RegionBase< Tr >::~RegionBase |
Delete the Region and all its subregions.
Definition at line 48 of file RegionInfoImpl.h.
void llvm::RegionBase< Tr >::addSubRegion | ( | RegionT * | SubRegion, |
bool | moveChildren = false |
||
) |
Add a new subregion to this Region.
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 372 of file RegionInfoImpl.h.
References assert(), and llvm::none_of().
|
inline |
Definition at line 558 of file RegionInfo.h.
References llvm::children().
|
inline |
Definition at line 561 of file RegionInfo.h.
References llvm::children().
|
inline |
Definition at line 607 of file RegionInfo.h.
References llvm::RegionBase< Tr >::getEntry(), and llvm::RegionBase< Tr >::getExit().
Referenced by llvm::RegionBase< Tr >::blocks().
|
inline |
Definition at line 611 of file RegionInfo.h.
References llvm::RegionBase< Tr >::getEntry(), and llvm::RegionBase< Tr >::getExit().
|
inline |
Definition at line 609 of file RegionInfo.h.
Referenced by llvm::RegionBase< Tr >::blocks().
|
inline |
Definition at line 614 of file RegionInfo.h.
|
inline |
Returns a range view of the basic blocks in the region.
Definition at line 620 of file RegionInfo.h.
References llvm::RegionBase< Tr >::block_begin(), and llvm::RegionBase< Tr >::block_end().
Referenced by hasOnlyUniformBranches().
|
inline |
Returns a range view of the basic blocks in the region.
This is the 'const' version of the range view.
Definition at line 627 of file RegionInfo.h.
References llvm::RegionBase< Tr >::block_begin(), and llvm::RegionBase< Tr >::block_end().
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 509 of file RegionInfoImpl.h.
bool llvm::RegionBase< Tr >::contains | ( | const BlockT * | BB | ) | const |
Check if the region contains a BasicBlock.
BB | The BasicBlock that might be contained in this Region. |
Definition at line 102 of file RegionInfoImpl.h.
References B.
Referenced by llvm::RegionBase< Tr >::contains(), removeOldExitPreds(), replaceArgumentUses(), replaceCalledFunction(), and sortBlocks().
|
inline |
Check if the region contains an Instruction.
Inst | The Instruction that might be contained in this region. |
Definition at line 467 of file RegionInfo.h.
References llvm::RegionBase< Tr >::contains().
Referenced by llvm::RegionBase< Tr >::contains().
bool llvm::RegionBase< Tr >::contains | ( | const LoopT * | L | ) | const |
Check if the region contains a loop.
L | The loop that might be contained in this region. |
Definition at line 119 of file RegionInfoImpl.h.
References contains().
|
inline |
Check if the region contains another region.
SubRegion | The region that might be contained in this Region. |
Definition at line 452 of file RegionInfo.h.
References llvm::RegionBase< Tr >::contains(), and llvm::RegionBase< Tr >::getExit().
void llvm::RegionBase< Tr >::dump |
Print the region to stderr.
Definition at line 503 of file RegionInfoImpl.h.
References llvm::dbgs(), and llvm::print().
RegionBase< Tr >::element_iterator llvm::RegionBase< Tr >::element_begin |
Definition at line 293 of file RegionInfoImpl.h.
Referenced by llvm::RegionBase< Tr >::elements().
RegionBase< Tr >::const_element_iterator llvm::RegionBase< Tr >::element_begin |
Definition at line 304 of file RegionInfoImpl.h.
RegionBase< Tr >::element_iterator llvm::RegionBase< Tr >::element_end |
Definition at line 298 of file RegionInfoImpl.h.
Referenced by llvm::RegionBase< Tr >::elements().
RegionBase< Tr >::const_element_iterator llvm::RegionBase< Tr >::element_end |
Definition at line 311 of file RegionInfoImpl.h.
|
inline |
Definition at line 649 of file RegionInfo.h.
References llvm::RegionBase< Tr >::element_begin(), llvm::RegionBase< Tr >::element_end(), and llvm::make_range().
|
inline |
Definition at line 655 of file RegionInfo.h.
References llvm::RegionBase< Tr >::element_begin(), llvm::RegionBase< Tr >::element_end(), and llvm::make_range().
|
inline |
Definition at line 559 of file RegionInfo.h.
References llvm::children().
Referenced by replaceCalledFunction().
|
inline |
Definition at line 562 of file RegionInfo.h.
References llvm::children().
Tr::RegionNodeT * llvm::RegionBase< Tr >::getBBNode | ( | BlockT * | BB | ) | const |
Get the BasicBlock RegionNode for a BasicBlock.
BB | The BasicBlock for which the RegionNode is requested. |
Definition at line 338 of file RegionInfoImpl.h.
References assert(), and contains().
unsigned llvm::RegionBase< Tr >::getDepth |
Get the nesting level of this Region.
An toplevel Region has depth 0.
Definition at line 428 of file RegionInfoImpl.h.
References llvm::Depth, and getParent().
RegionBase< Tr >::BlockT * llvm::RegionBase< Tr >::getEnteringBlock |
Return the first block of this region's single entry edge, if existing.
Definition at line 161 of file RegionInfoImpl.h.
References assert(), and contains().
|
inline |
Get the entry BasicBlock of the Region.
Definition at line 320 of file RegionInfo.h.
References llvm::RegionNodeBase< Tr >::getEntry().
Referenced by llvm::RegionBase< Tr >::block_begin(), llvm::VPBlockBase::getEntryBasicBlock(), and llvm::RGPassManager::runOnFunction().
|
inline |
Get the exit BasicBlock of the Region.
Definition at line 357 of file RegionInfo.h.
Referenced by llvm::RegionBase< Tr >::block_begin(), and llvm::RegionBase< Tr >::contains().
RegionBase< Tr >::BlockT * llvm::RegionBase< Tr >::getExitingBlock |
Return the first block of this region's single exit edge, if existing.
Definition at line 191 of file RegionInfoImpl.h.
References assert(), and contains().
bool llvm::RegionBase< Tr >::getExitingBlocks | ( | SmallVectorImpl< BlockT * > & | Exitings | ) | const |
Collect all blocks of this region's single exit edge, if existing.
Definition at line 171 of file RegionInfoImpl.h.
References contains(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Tr::RegionT * llvm::RegionBase< Tr >::getExpandedRegion |
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
Definition at line 438 of file RegionInfoImpl.h.
std::string llvm::RegionBase< Tr >::getNameStr |
Returns the name of the Region.
Definition at line 210 of file RegionInfoImpl.h.
Referenced by llvm::RGPassManager::runOnFunction().
|
inline |
Get the RegionNode representing the current Region.
Definition at line 368 of file RegionInfo.h.
Tr::RegionNodeT * llvm::RegionBase< Tr >::getNode | ( | BlockT * | BB | ) | const |
Get the RegionNode for a BasicBlock.
BB | The BasicBlock at which the RegionNode should start. |
Definition at line 354 of file RegionInfoImpl.h.
References assert(), and contains().
|
inline |
Get the parent of the Region.
Definition at line 362 of file RegionInfo.h.
References llvm::RegionNodeBase< Tr >::getParent().
Referenced by getCodeExtractorArguments().
|
inline |
Return the RegionInfo object, that belongs to this Region.
Definition at line 424 of file RegionInfo.h.
Tr::RegionT * llvm::RegionBase< Tr >::getSubRegionNode | ( | BlockT * | BB | ) | const |
Get the subregion that starts at a BasicBlock.
BB | The BasicBlock the subregion should start. |
Definition at line 317 of file RegionInfoImpl.h.
References assert(), and contains().
bool llvm::RegionBase< Tr >::isSimple |
Is this a simple region?
A region is simple if it has exactly one exit and one entry edge.
Definition at line 205 of file RegionInfoImpl.h.
|
inline |
Check if a Region is the TopLevel region.
The toplevel region represents the whole function.
Definition at line 383 of file RegionInfo.h.
|
delete |
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.
LI | A pointer to a LoopInfo analysis. |
BB | The basic block surrounded by the loop. |
Definition at line 153 of file RegionInfoImpl.h.
References assert().
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.
L | The loop the lookup is started. |
Definition at line 141 of file RegionInfoImpl.h.
References contains().
void llvm::RegionBase< Tr >::print | ( | raw_ostream & | OS, |
bool | printTree = true , |
||
unsigned | level = 0 , |
||
PrintStyle | Style = PrintNone |
||
) | const |
Print the region.
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 467 of file RegionInfoImpl.h.
References llvm::raw_ostream::indent(), and OS.
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.
SubRegion | The SubRegion that will be removed. |
Definition at line 415 of file RegionInfoImpl.h.
References assert().
void llvm::RegionBase< Tr >::replaceEntry | ( | BlockT * | BB | ) |
Replace the entry basic block of the region with the new basic block.
BB | The new entry basic block of the region. |
Definition at line 55 of file RegionInfoImpl.h.
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.
NewEntry | The new entry basic block. |
Definition at line 66 of file RegionInfoImpl.h.
void llvm::RegionBase< Tr >::replaceExit | ( | BlockT * | BB | ) |
Replace the exit basic block of the region with the new basic block.
BB | The new exit basic block of the region. |
Definition at line 60 of file RegionInfoImpl.h.
References assert().
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.
NewExit | The new exit basic block. |
Definition at line 84 of file RegionInfoImpl.h.
void llvm::RegionBase< Tr >::transferChildrenTo | ( | RegionT * | To | ) |
Move all direct child nodes of this Region to another Region.
To | The Region the child nodes will be transferred to. |
Definition at line 363 of file RegionInfoImpl.h.
References llvm::children().
void llvm::RegionBase< Tr >::verifyRegion |
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 273 of file RegionInfoImpl.h.
Referenced by llvm::RGPassManager::runOnFunction().
|
friend |
Definition at line 186 of file RegionInfo.h.