11#ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
12#define LLVM_ANALYSIS_REGIONINFOIMPL_H
22#include "llvm/Config/llvm-config.h"
34#define DEBUG_TYPE "region"
43 typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
45 :
RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
56 this->entry.setPointer(BB);
61 assert(exit &&
"No exit to replace!");
67 std::vector<RegionT *> RegionQueue;
68 BlockT *OldEntry = getEntry();
70 RegionQueue.push_back(
static_cast<RegionT *
>(
this));
71 while (!RegionQueue.empty()) {
72 RegionT *R = RegionQueue.back();
73 RegionQueue.pop_back();
75 R->replaceEntry(NewEntry);
76 for (std::unique_ptr<RegionT> &Child : *R) {
77 if (Child->getEntry() == OldEntry)
78 RegionQueue.push_back(Child.get());
85 std::vector<RegionT *> RegionQueue;
86 BlockT *OldExit = getExit();
88 RegionQueue.push_back(
static_cast<RegionT *
>(
this));
89 while (!RegionQueue.empty()) {
90 RegionT *R = RegionQueue.back();
91 RegionQueue.pop_back();
93 R->replaceExit(NewExit);
94 for (std::unique_ptr<RegionT> &Child : *R) {
95 if (Child->getExit() == OldExit)
96 RegionQueue.push_back(Child.get());
103 BlockT *BB =
const_cast<BlockT *
>(
B);
105 if (!DT->getNode(BB))
108 BlockT *entry = getEntry(), *exit = getExit();
114 return (DT->dominates(entry, BB) &&
115 !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
124 return getExit() ==
nullptr;
130 L->getExitingBlocks(ExitingBlocks);
132 for (BlockT *BB : ExitingBlocks) {
145 while (L &&
contains(L->getParentLoop())) {
146 L = L->getParentLoop();
155 assert(LI && BB &&
"LI and BB cannot be null!");
156 LoopT *L = LI->getLoopFor(BB);
157 return outermostLoopInRegion(L);
162 auto isEnteringBlock = [&](BlockT *Pred,
bool AllowRepeats) -> BlockT * {
163 assert(!AllowRepeats &&
"Unexpected parameter value.");
164 return DT->getNode(Pred) && !
contains(Pred) ? Pred :
nullptr;
166 BlockT *entry = getEntry();
167 return find_singleton<BlockT>(
make_range(InvBlockTraits::child_begin(entry),
168 InvBlockTraits::child_end(entry)),
175 bool CoverAll =
true;
180 for (PredIterTy PI = InvBlockTraits::child_begin(exit),
181 PE = InvBlockTraits::child_end(exit);
197 BlockT *exit = getExit();
201 auto isContained = [&](BlockT *Pred,
bool AllowRepeats) -> BlockT * {
202 assert(!AllowRepeats &&
"Unexpected parameter value.");
203 return contains(Pred) ? Pred :
nullptr;
205 return find_singleton<BlockT>(
make_range(InvBlockTraits::child_begin(exit),
206 InvBlockTraits::child_end(exit)),
212 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
217 std::string exitName;
218 std::string entryName;
220 if (getEntry()->
getName().empty()) {
223 getEntry()->printAsOperand(
OS,
false);
225 entryName = std::string(getEntry()->
getName());
228 if (getExit()->
getName().empty()) {
231 getExit()->printAsOperand(
OS,
false);
233 exitName = std::string(getExit()->
getName());
235 exitName =
"<Function Return>";
237 return entryName +
" => " + exitName;
245 BlockT *entry = getEntry(), *exit = getExit();
248 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
249 if (!
contains(Succ) && exit != Succ)
251 "to the exit node!");
255 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(BB),
256 InvBlockTraits::child_end(BB))) {
259 if (!
contains(Pred) && DT->isReachableFromEntry(Pred))
261 "go to the entry node!");
267void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited)
const {
268 BlockT *exit = getExit();
272 verifyBBInRegion(BB);
275 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
276 if (Succ != exit && visited->find(Succ) == visited->end())
277 verifyWalk(Succ, visited);
289 std::set<BlockT *> visited;
290 verifyWalk(getEntry(), &visited);
295 for (
const std::unique_ptr<RegionT> &R : *
this)
296 R->verifyRegionNest();
315 static_cast<const RegionT *
>(
this));
322 static_cast<const RegionT *
>(
this));
327 using RegionT =
typename Tr::RegionT;
329 RegionT *R = RI->getRegionFor(BB);
337 while (
contains(R->getParent()) && R->getParent() !=
this)
340 if (R->getEntry() != BB)
350 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
352 if (at == BBNodeMap.end()) {
354 typename BBNodeMapT::value_type V = {
356 std::make_unique<RegionNodeT>(
static_cast<RegionT *
>(Deconst), BB)};
357 at = BBNodeMap.insert(std::move(V)).first;
359 return at->second.get();
365 if (RegionT *Child = getSubRegionNode(BB))
366 return Child->getNode();
368 return getBBNode(BB);
373 for (std::unique_ptr<RegionT> &R : *
this) {
375 To->children.push_back(std::move(R));
382 assert(!SubRegion->parent &&
"SubRegion already has a parent!");
384 [&](
const std::unique_ptr<RegionT> &R) {
385 return R.get() == SubRegion;
387 "Subregion already exists!");
389 SubRegion->parent =
static_cast<RegionT *
>(
this);
390 children.push_back(std::unique_ptr<RegionT>(SubRegion));
395 assert(SubRegion->children.empty() &&
396 "SubRegions that contain children are not supported");
398 for (RegionNodeT *Element : elements()) {
399 if (!Element->isSubRegion()) {
400 BlockT *BB = Element->template getNodeAs<BlockT>();
402 if (SubRegion->contains(BB))
403 RI->setRegionFor(BB, SubRegion);
407 std::vector<std::unique_ptr<RegionT>>
Keep;
408 for (std::unique_ptr<RegionT> &R : *
this) {
409 if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
410 R->parent = SubRegion;
411 SubRegion->children.push_back(std::move(R));
413 Keep.push_back(std::move(R));
419 std::move_iterator<typename RegionSet::iterator>(
Keep.begin()),
420 std::move_iterator<typename RegionSet::iterator>(
Keep.end()));
425 assert(Child->parent ==
this &&
"Child is not a child of this region!");
426 Child->parent =
nullptr;
427 typename RegionSet::iterator
I =
429 return R.get() == Child;
431 assert(
I !=
children.end() &&
"Region does not exit. Unable to remove.");
440 for (RegionT *R =
getParent(); R !=
nullptr; R = R->getParent())
448 unsigned NumSuccessors = Tr::getNumSuccessors(exit);
450 if (NumSuccessors == 0)
453 RegionT *R = RI->getRegionFor(exit);
455 if (R->getEntry() != exit) {
456 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
457 InvBlockTraits::child_end(getExit())))
460 if (Tr::getNumSuccessors(exit) == 1)
461 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
465 while (R->getParent() && R->getParent()->getEntry() == exit)
468 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
469 InvBlockTraits::child_end(getExit()))) {
470 if (!(
contains(Pred) || R->contains(Pred)))
474 return new RegionT(getEntry(), R->getExit(), RI, DT);
481 OS.
indent(level * 2) <<
'[' << level <<
"] " << getNameStr();
483 OS.
indent(level * 2) << getNameStr();
487 if (Style != PrintNone) {
491 if (Style == PrintBB) {
492 for (
const auto *BB :
blocks())
493 OS << BB->getName() <<
", ";
494 }
else if (Style == PrintRN) {
495 for (
const RegionNodeT *Element : elements()) {
496 OS << *Element <<
", ";
504 for (
const std::unique_ptr<RegionT> &R : *
this)
505 R->print(
OS, print_tree, level + 1, Style);
508 if (Style != PrintNone)
512#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
522 for (std::unique_ptr<RegionT> &R : *
this)
540 assert(R &&
"Re must be non-null");
541 for (
const typename Tr::RegionNodeT *Element : R->elements()) {
542 if (Element->isSubRegion()) {
543 const RegionT *SR = Element->template getNodeAs<RegionT>();
546 BlockT *BB = Element->template getNodeAs<BlockT>();
547 if (getRegionFor(BB) != R)
555 BlockT *exit)
const {
556 for (BlockT *
P :
make_range(InvBlockTraits::child_begin(BB),
557 InvBlockTraits::child_end(BB))) {
558 if (DT->dominates(entry,
P) && !DT->dominates(exit,
P))
566bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit)
const {
567 assert(entry && exit &&
"entry and exit must not be null!");
569 using DST =
typename DomFrontierT::DomSetType;
571 DST *entrySuccs = &
DF->find(entry)->second;
575 if (!DT->dominates(entry, exit)) {
576 for (BlockT *successor : *entrySuccs) {
577 if (successor != exit && successor != entry)
584 DST *exitSuccs = &
DF->find(exit)->second;
587 for (BlockT *Succ : *entrySuccs) {
588 if (Succ == exit || Succ == entry)
590 if (!exitSuccs->contains(Succ))
592 if (!isCommonDomFrontier(Succ, entry, exit))
597 for (BlockT *Succ : *exitSuccs) {
598 if (DT->properlyDominates(entry, Succ) && Succ != exit)
606void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
607 BBtoBBMap *ShortCut)
const {
608 assert(entry && exit &&
"entry and exit must not be null!");
610 typename BBtoBBMap::iterator
e = ShortCut->find(exit);
612 if (e == ShortCut->end())
614 (*ShortCut)[entry] = exit;
619 BlockT *BB =
e->second;
620 (*ShortCut)[entry] = BB;
625typename Tr::DomTreeNodeT *
626RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *
N, BBtoBBMap *ShortCut)
const {
627 typename BBtoBBMap::iterator
e = ShortCut->find(
N->getBlock());
629 if (e == ShortCut->end())
632 return PDT->getNode(
e->second)->getIDom();
636bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit)
const {
637 assert(entry && exit &&
"entry and exit must not be null!");
639 unsigned num_successors =
640 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
642 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
651 assert(entry && exit &&
"entry and exit must not be null!");
653 if (isTrivialRegion(entry, exit))
657 new RegionT(entry, exit,
static_cast<RegionInfoT *
>(
this), DT);
658 BBtoRegion.insert({entry, region});
660 region->verifyRegion();
662 updateStatistics(region);
667void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
668 BBtoBBMap *ShortCut) {
671 DomTreeNodeT *
N = PDT->getNode(entry);
675 RegionT *lastRegion =
nullptr;
676 BlockT *lastExit = entry;
680 while ((
N = getNextPostDom(
N, ShortCut))) {
681 BlockT *exit =
N->getBlock();
686 if (isRegion(entry, exit)) {
687 RegionT *newRegion = createRegion(entry, exit);
690 newRegion->addSubRegion(lastRegion);
692 lastRegion = newRegion;
697 if (!DT->dominates(entry, exit))
703 if (lastExit != entry)
704 insertShortCut(entry, lastExit, ShortCut);
708void RegionInfoBase<Tr>::scanForRegions(FuncT &
F, BBtoBBMap *ShortCut) {
709 using FuncPtrT = std::add_pointer_t<FuncT>;
711 BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&
F);
712 DomTreeNodeT *
N = DT->getNode(entry);
719 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
723typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
724 while (region->getParent())
725 region = region->getParent();
731void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *
N, RegionT *region) {
732 BlockT *BB =
N->getBlock();
735 while (BB == region->getExit())
736 region = region->getParent();
738 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
742 if (it != BBtoRegion.end()) {
743 RegionT *newRegion = it->second;
744 region->addSubRegion(getTopMostParent(newRegion));
747 BBtoRegion[BB] = region;
750 for (DomTreeNodeBase<BlockT> *
C : *
N) {
751 buildRegionsTree(
C, region);
755#ifdef EXPENSIVE_CHECKS
769 OS <<
"Region tree:\n";
770 TopLevelRegion->print(
OS,
true, 0, printStyle);
771 OS <<
"End region tree\n";
774#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
781 if (TopLevelRegion) {
782 delete TopLevelRegion;
783 TopLevelRegion =
nullptr;
794 TopLevelRegion->verifyRegionNest();
796 verifyBBMap(TopLevelRegion);
802 return BBtoRegion.lookup(BB);
812 return getRegionFor(BB);
816typename RegionInfoBase<Tr>::BlockT *
818 BlockT *Exit =
nullptr;
822 RegionT *R = getRegionFor(BB);
823 while (R && R->getParent() && R->getParent()->getEntry() == BB)
827 if (R && R->getEntry() == BB)
829 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
830 Exit = *BlockTraits::child_begin(BB);
835 RegionT *ExitR = getRegionFor(Exit);
836 while (ExitR && ExitR->getParent() &&
837 ExitR->getParent()->getEntry() == Exit)
838 ExitR = ExitR->getParent();
840 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(Exit),
841 InvBlockTraits::child_end(Exit))) {
842 if (!R->contains(Pred) && !ExitR->contains(Pred))
847 if (DT->dominates(Exit, BB))
859 assert(
A &&
B &&
"One of the Regions is NULL");
864 while (!
B->contains(
A))
871typename Tr::RegionT *
875 for (RegionT *R : Regions)
876 ret = getCommonRegion(ret, R);
882typename Tr::RegionT *
884 RegionT *ret = getRegionFor(BBs.
back());
887 for (BlockT *BB : BBs)
888 ret = getCommonRegion(ret, getRegionFor(BB));
895 using FuncPtrT = std::add_pointer_t<FuncT>;
902 scanForRegions(
F, &ShortCut);
904 buildRegionsTree(DT->getNode(BB), TopLevelRegion);
static const Function * getParent(const Value *V)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
A single entry single exit Region.
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
void clearNodeCache()
Clear the cache for BB RegionNodes.
std::string getNameStr() const
Returns the name of the Region.
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
unsigned getDepth() const
Get the nesting level of this Region.
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
void dump() const
Print the region to stderr.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
element_iterator element_begin()
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
void verifyRegion() const
Verify if the region is a correct region.
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
element_iterator element_end()
bool isSimple() const
Is this a simple region?
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
~RegionBase()
Delete the Region and all its subregions.
PrintStyle
PrintStyle - Print region in difference ways.
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
Analysis that detects all canonical Regions.
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
static bool VerifyRegionInfo
void print(raw_ostream &OS) const
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
static RegionT::PrintStyle printStyle
void verifyAnalysis() const
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
A raw_ostream that writes to an std::string.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< po_iterator< T > > post_order(const T &G)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
@ Keep
No function return thunk.