Go to the documentation of this file.
36 #ifndef LLVM_ANALYSIS_REGIONINFO_H
37 #define LLVM_ANALYSIS_REGIONINFO_H
44 #include "llvm/Config/llvm-config.h"
54 #include <type_traits>
60 class DominanceFrontier;
63 class PostDominatorTree;
74 template <
class FuncT_>
81 using BrokenT =
typename FuncT_::UnknownRegionTypeError;
100 return BB->getTerminator()->getNumSuccessors();
111 template <
class GraphType>
182 template <
class T>
inline T *
getNodeAs()
const;
254 class RegionBase :
public RegionNodeBase<Tr> {
257 using FuncT =
typename Tr::FuncT;
258 using BlockT =
typename Tr::BlockT;
259 using RegionInfoT =
typename Tr::RegionInfoT;
260 using RegionT =
typename Tr::RegionT;
261 using RegionNodeT =
typename Tr::RegionNodeT;
262 using DomTreeT =
typename Tr::DomTreeT;
263 using LoopT =
typename Tr::LoopT;
264 using LoopInfoT =
typename Tr::LoopInfoT;
265 using InstT =
typename Tr::InstT;
269 using SuccIterTy =
typename BlockTraits::ChildIteratorType;
270 using PredIterTy =
typename InvBlockTraits::ChildIteratorType;
280 using RegionSet = std::vector<std::unique_ptr<RegionT>>;
285 using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>;
288 mutable BBNodeMapT BBNodeMap;
292 void verifyBBInRegion(BlockT *
BB)
const;
297 void verifyWalk(BlockT *
BB, std::set<BlockT *> *visitedBB)
const;
300 void verifyRegionNest()
const;
311 RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT,
312 RegionT *Parent =
nullptr);
371 return const_cast<RegionNodeT *
>(
372 reinterpret_cast<const RegionNodeT *
>(
this));
439 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
459 return contains(SubRegion->getEntry()) &&
461 SubRegion->getExit() ==
getExit());
478 bool contains(
const LoopT *L)
const;
526 void addSubRegion(RegionT *SubRegion,
bool moveChildren =
false);
573 template <
bool IsConst>
576 std::conditional_t<IsConst, const BlockT, BlockT> *> {
665 inline raw_ostream &
operator<<(raw_ostream &OS,
const RegionNodeBase<Tr> &
Node);
674 class RegionInfoBase {
678 using BlockT =
typename Tr::BlockT;
679 using FuncT =
typename Tr::FuncT;
680 using RegionT =
typename Tr::RegionT;
681 using RegionInfoT =
typename Tr::RegionInfoT;
682 using DomTreeT =
typename Tr::DomTreeT;
683 using DomTreeNodeT =
typename Tr::DomTreeNodeT;
684 using PostDomTreeT =
typename Tr::PostDomTreeT;
685 using DomFrontierT =
typename Tr::DomFrontierT;
688 using SuccIterTy =
typename BlockTraits::ChildIteratorType;
689 using PredIterTy =
typename InvBlockTraits::ChildIteratorType;
698 TopLevelRegion(
std::
move(
Arg.TopLevelRegion)),
713 virtual ~RegionInfoBase();
720 RegionT *TopLevelRegion =
nullptr;
723 BBtoRegionMap BBtoRegion;
730 template<
typename TheRegionT>
735 for (
auto &SubR : *
R)
748 TopLevelRegion =
nullptr;
755 void verifyBBMap(
const RegionT *SR)
const;
760 bool isCommonDomFrontier(BlockT *
BB, BlockT *
entry, BlockT *
exit)
const;
764 bool isRegion(BlockT *
entry, BlockT *
exit)
const;
768 void insertShortCut(BlockT *
entry, BlockT *
exit, BBtoBBMap *ShortCut)
const;
772 DomTreeNodeT *getNextPostDom(DomTreeNodeT *
N, BBtoBBMap *ShortCut)
const;
775 bool isTrivialRegion(BlockT *
entry, BlockT *
exit)
const;
778 RegionT *createRegion(BlockT *
entry, BlockT *
exit);
781 void findRegionsWithEntry(BlockT *
entry, BBtoBBMap *ShortCut);
784 void scanForRegions(FuncT &
F, BBtoBBMap *ShortCut);
787 RegionT *getTopMostParent(RegionT *region);
790 void buildRegionsTree(DomTreeNodeT *
N, RegionT *region);
793 virtual void updateStatistics(RegionT *
R) = 0;
796 void calculate(FuncT &
F);
799 RegionInfoBase(
const RegionInfoBase &) =
delete;
800 RegionInfoBase &operator=(
const RegionInfoBase &) =
delete;
806 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
873 TopLevelRegion->clearNodeCache();
885 return this ==
reinterpret_cast<const RegionNode *
>(&
RN);
892 Region *Parent =
nullptr);
896 return &
RN ==
reinterpret_cast<const RegionNode *
>(
this);
997 assert(!isSubRegion() &&
"This is not a BasicBlock RegionNode!");
1005 assert(isSubRegion() &&
"This is not a subregion RegionNode!");
1007 return reinterpret_cast<Region *
>(Unconst);
1013 using BlockT =
typename Tr::BlockT;
1014 using RegionT =
typename Tr::RegionT;
1016 if (
Node.isSubRegion())
1017 return OS <<
Node.template getNodeAs<RegionT>()->getNameStr();
1019 return OS <<
Node.template getNodeAs<BlockT>()->getName();
1022 extern template class RegionBase<RegionTraits<Function>>;
1023 extern template class RegionNodeBase<RegionTraits<Function>>;
1024 extern template class RegionInfoBase<RegionTraits<Function>>;
1028 #endif // LLVM_ANALYSIS_REGIONINFO_H
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
A set of analyses that are preserved following a run of a transformation pass.
const_iterator begin() const
void updateStatistics(Region *R) final
RegionInfoT * getRegionInfo() const
Return the RegionInfo object, that belongs to this Region.
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
BlockT * operator*() const
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const_iterator end() const
RegionT * getTopLevelRegion() const
Verifier pass for the RegionInfo.
RegionInfoPrinterPass(raw_ostream &OS)
A CRTP mix-in to automatically provide informational APIs needed for passes.
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Represents a single loop in the control flow graph.
block_iterator block_end()
A single entry single exit Region.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
DomTreeNodeBase< BasicBlock > DomTreeNode
~RegionBase()
Delete the Region and all its subregions.
Marker class to iterate over the elements of a Region in flat mode.
df_iterator< T > df_end(const T &G)
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
iterator_range< const_element_iterator > elements() const
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
Printer pass for the RegionInfo.
const_block_iterator block_begin() const
const RegionInfo & getRegionInfo() const
RegionInfo & getRegionInfo()
block_iterator_wrapper< true > const_block_iterator
typename RegionSet::iterator iterator
LLVM Basic Block Representation.
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
static unsigned getNumSuccessors(BasicBlock *BB)
typename super::value_type value_type
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
block_iterator_wrapper(value_type Entry, value_type Exit)
df_iterator< RegionNodeT *, df_iterator_default_set< RegionNodeT * >, false, GraphTraits< RegionNodeT * > > element_iterator
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.
Analysis pass that exposes the RegionInfo for a function.
static bool VerifyRegionInfo
RegionBase & operator=(const RegionBase &)=delete
bool isTopLevelRegion() const
Check if a Region is the TopLevel region.
PrintStyle
PrintStyle - Print region in difference ways.
Represent the analysis usage information of a pass.
RegionInfo & operator=(RegionInfo &&RHS)
element_iterator element_end()
const_block_range blocks() const
Returns a range view of the basic blocks in the region.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void verifyRegion() const
Verify if the region is a correct region.
RegionNodeBase & operator=(const RegionNodeBase &)=delete
iterator_range< const_block_iterator > const_block_range
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
void clearNodeCache()
Clear the Node Cache for all Regions.
const NodeRef & operator*() const
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
API to communicate dependencies between analyses during invalidation.
Analysis that detects all canonical Regions.
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
block_range blocks()
Returns a range view of the basic blocks in the region.
static RegionT::PrintStyle printStyle
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
RegionInfo(RegionInfo &&Arg)
df_iterator_default_set< typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * >::NodeRef > Visited
T * getNodeAs() const
Get the content of this RegionNode.
bool operator==(const Region &RN) const
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
A special type used by analysis passes to provide an address that identifies that particular analysis...
typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * > ::NodeRef value_type
void clearNodeCache()
Clear the cache for BB RegionNodes.
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
element_iterator element_begin()
bool contains(const RegionT *SubRegion) const
Check if the region contains another region.
df_iterator< T > df_begin(const T &G)
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
typename RegionTraits< Function > ::RegionT RegionT
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
@ BasicBlock
Various leaf nodes.
void print(raw_ostream &OS) const
bool contains(const InstT *Inst) const
Check if the region contains an Instruction.
std::pair< iterator, bool > insert(NodeRef N)
A Module instance is used to store all the information related to an LLVM module.
A CRTP mix-in that provides informational APIs needed for analysis passes.
RegionNodeBase(RegionT *Parent, BlockT *Entry, bool isSubRegion=false)
Create a RegionNode.
bool isSubRegion() const
Is this RegionNode a subregion?
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
const_block_iterator block_end() const
typename RegionSet::const_iterator const_iterator
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > const_element_iterator
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
void dump() const
Print the region to stderr.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
void view()
Opens a viewer to show the GraphViz visualization of the regions.
block_iterator_wrapper< false > block_iterator
unsigned getDepth() const
Get the nesting level of this Region.
RegionT * getCommonRegion(BlockT *A, BlockT *B) const
Find the smallest region that contains two basic blocks.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
void verifyAnalysis() const
RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion=false)
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
std::string getNameStr() const
Returns the name of the Region.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
block_iterator_wrapper(super I)
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
iterator_range< block_iterator > block_range
bool isSimple() const
Is this a simple region?
~RegionInfoPass() override
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
BlockT * getEntry() const
Get the entry BasicBlock of this RegionNode.
declare void exit(i32) noreturn nounwind This compiles into
block_iterator block_begin()
A range adaptor for a pair of iterators.
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
RegionT * getParent() const
Get the parent Region of this RegionNode.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
typename RegionTraits< Function > ::BlockT BlockT
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
typename FuncT_::UnknownRegionTypeError BrokenT
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
bool operator==(const RegionNode &RN) const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
BlockT * getExit() const
Get the exit BasicBlock of the Region.
print Instructions which execute on loop entry
iterator_range< element_iterator > elements()
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
void updateRegionTree(RegionInfoT &RI, TheRegionT *R)
Update refences to a RegionInfoT held by the RegionT managed here.
RegionT * getParent() const
Get the parent of the Region.