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 "go to the entry node!");
265void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited)
const {
266 BlockT *exit = getExit();
270 verifyBBInRegion(BB);
273 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
274 if (Succ != exit && visited->find(Succ) == visited->end())
275 verifyWalk(Succ, visited);
287 std::set<BlockT *> visited;
288 verifyWalk(getEntry(), &visited);
293 for (
const std::unique_ptr<RegionT> &R : *
this)
294 R->verifyRegionNest();
313 static_cast<const RegionT *
>(
this));
320 static_cast<const RegionT *
>(
this));
325 using RegionT =
typename Tr::RegionT;
327 RegionT *R = RI->getRegionFor(BB);
335 while (
contains(R->getParent()) && R->getParent() !=
this)
338 if (R->getEntry() != BB)
348 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
350 if (at == BBNodeMap.end()) {
352 typename BBNodeMapT::value_type V = {
354 std::make_unique<RegionNodeT>(
static_cast<RegionT *
>(Deconst), BB)};
355 at = BBNodeMap.insert(std::move(V)).first;
357 return at->second.get();
363 if (RegionT *Child = getSubRegionNode(BB))
364 return Child->getNode();
366 return getBBNode(BB);
371 for (std::unique_ptr<RegionT> &R : *
this) {
373 To->children.push_back(std::move(R));
380 assert(!SubRegion->parent &&
"SubRegion already has a parent!");
382 [&](
const std::unique_ptr<RegionT> &R) {
383 return R.get() == SubRegion;
385 "Subregion already exists!");
387 SubRegion->parent =
static_cast<RegionT *
>(
this);
388 children.push_back(std::unique_ptr<RegionT>(SubRegion));
394 "SubRegions that contain children are not supported");
396 for (RegionNodeT *Element : elements()) {
397 if (!Element->isSubRegion()) {
398 BlockT *BB = Element->template getNodeAs<BlockT>();
400 if (SubRegion->contains(BB))
401 RI->setRegionFor(BB, SubRegion);
405 std::vector<std::unique_ptr<RegionT>>
Keep;
406 for (std::unique_ptr<RegionT> &R : *
this) {
407 if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
408 R->parent = SubRegion;
409 SubRegion->children.push_back(std::move(R));
411 Keep.push_back(std::move(R));
417 std::move_iterator<typename RegionSet::iterator>(
Keep.begin()),
418 std::move_iterator<typename RegionSet::iterator>(
Keep.end()));
423 assert(Child->parent ==
this &&
"Child is not a child of this region!");
424 Child->parent =
nullptr;
425 typename RegionSet::iterator
I =
427 return R.get() == Child;
429 assert(
I !=
children.end() &&
"Region does not exit. Unable to remove.");
438 for (RegionT *R =
getParent(); R !=
nullptr; R = R->getParent())
446 unsigned NumSuccessors = Tr::getNumSuccessors(exit);
448 if (NumSuccessors == 0)
451 RegionT *R = RI->getRegionFor(exit);
453 if (R->getEntry() != exit) {
454 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
455 InvBlockTraits::child_end(getExit())))
458 if (Tr::getNumSuccessors(exit) == 1)
459 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
463 while (R->getParent() && R->getParent()->getEntry() == exit)
466 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
467 InvBlockTraits::child_end(getExit()))) {
468 if (!(
contains(Pred) || R->contains(Pred)))
472 return new RegionT(getEntry(), R->getExit(), RI, DT);
479 OS.
indent(level * 2) <<
'[' << level <<
"] " << getNameStr();
481 OS.
indent(level * 2) << getNameStr();
485 if (Style != PrintNone) {
489 if (Style == PrintBB) {
490 for (
const auto *BB : blocks())
491 OS << BB->getName() <<
", ";
492 }
else if (Style == PrintRN) {
493 for (
const RegionNodeT *Element : elements()) {
494 OS << *Element <<
", ";
502 for (
const std::unique_ptr<RegionT> &R : *
this)
503 R->print(
OS, print_tree, level + 1, Style);
506 if (Style != PrintNone)
510#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
520 for (std::unique_ptr<RegionT> &R : *
this)
539 for (
const typename Tr::RegionNodeT *Element : R->elements()) {
540 if (Element->isSubRegion()) {
541 const RegionT *SR = Element->template getNodeAs<RegionT>();
544 BlockT *BB = Element->template getNodeAs<BlockT>();
545 if (getRegionFor(BB) != R)
553 BlockT *exit)
const {
554 for (BlockT *
P :
make_range(InvBlockTraits::child_begin(BB),
555 InvBlockTraits::child_end(BB))) {
556 if (DT->dominates(
entry,
P) && !DT->dominates(exit,
P))
565 assert(
entry && exit &&
"entry and exit must not be null!");
567 using DST =
typename DomFrontierT::DomSetType;
569 DST *entrySuccs = &
DF->find(
entry)->second;
573 if (!DT->dominates(
entry, exit)) {
574 for (BlockT *successor : *entrySuccs) {
575 if (successor != exit && successor !=
entry)
582 DST *exitSuccs = &
DF->find(exit)->second;
585 for (BlockT *Succ : *entrySuccs) {
586 if (Succ == exit || Succ ==
entry)
588 if (exitSuccs->find(Succ) == exitSuccs->end())
590 if (!isCommonDomFrontier(Succ,
entry, exit))
595 for (BlockT *Succ : *exitSuccs) {
596 if (DT->properlyDominates(
entry, Succ) && Succ != exit)
604void RegionInfoBase<Tr>::insertShortCut(BlockT *
entry, BlockT *exit,
605 BBtoBBMap *ShortCut)
const {
606 assert(
entry && exit &&
"entry and exit must not be null!");
608 typename BBtoBBMap::iterator
e = ShortCut->find(exit);
610 if (e == ShortCut->end())
612 (*ShortCut)[
entry] = exit;
617 BlockT *BB =
e->second;
618 (*ShortCut)[
entry] = BB;
623typename Tr::DomTreeNodeT *
624RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *
N, BBtoBBMap *ShortCut)
const {
625 typename BBtoBBMap::iterator
e = ShortCut->find(
N->getBlock());
627 if (e == ShortCut->end())
630 return PDT->getNode(
e->second)->getIDom();
634bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *
entry, BlockT *exit)
const {
635 assert(
entry && exit &&
"entry and exit must not be null!");
637 unsigned num_successors =
638 BlockTraits::child_end(
entry) - BlockTraits::child_begin(
entry);
640 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(
entry)))
647typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *
entry,
651 if (isTrivialRegion(
entry, exit))
655 new RegionT(
entry, exit,
static_cast<RegionInfoT *
>(
this), DT);
658#ifdef EXPENSIVE_CHECKS
659 region->verifyRegion();
664 updateStatistics(region);
669void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *
entry,
670 BBtoBBMap *ShortCut) {
673 DomTreeNodeT *
N = PDT->getNode(
entry);
677 RegionT *lastRegion =
nullptr;
678 BlockT *lastExit =
entry;
682 while ((
N = getNextPostDom(
N, ShortCut))) {
683 BlockT *exit =
N->getBlock();
688 if (isRegion(
entry, exit)) {
689 RegionT *newRegion = createRegion(
entry, exit);
692 newRegion->addSubRegion(lastRegion);
694 lastRegion = newRegion;
699 if (!DT->dominates(
entry, exit))
705 if (lastExit !=
entry)
706 insertShortCut(
entry, lastExit, ShortCut);
710void RegionInfoBase<Tr>::scanForRegions(FuncT &
F, BBtoBBMap *ShortCut) {
711 using FuncPtrT = std::add_pointer_t<FuncT>;
713 BlockT *
entry = GraphTraits<FuncPtrT>::getEntryNode(&
F);
714 DomTreeNodeT *
N = DT->getNode(
entry);
721 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
725typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
726 while (region->getParent())
727 region = region->getParent();
733void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *
N, RegionT *region) {
734 BlockT *BB =
N->getBlock();
737 while (BB == region->getExit())
738 region = region->getParent();
740 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
744 if (it != BBtoRegion.end()) {
745 RegionT *newRegion = it->second;
746 region->addSubRegion(getTopMostParent(newRegion));
749 BBtoRegion[BB] = region;
752 for (DomTreeNodeBase<BlockT> *
C : *
N) {
753 buildRegionsTree(
C, region);
757#ifdef EXPENSIVE_CHECKS
771 OS <<
"Region tree:\n";
772 TopLevelRegion->print(
OS,
true, 0, printStyle);
773 OS <<
"End region tree\n";
776#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
783 if (TopLevelRegion) {
784 delete TopLevelRegion;
785 TopLevelRegion =
nullptr;
796 TopLevelRegion->verifyRegionNest();
798 verifyBBMap(TopLevelRegion);
804 return BBtoRegion.lookup(BB);
814 return getRegionFor(BB);
818typename RegionInfoBase<Tr>::BlockT *
820 BlockT *Exit =
nullptr;
824 RegionT *R = getRegionFor(BB);
825 while (R && R->getParent() && R->getParent()->getEntry() == BB)
829 if (R && R->getEntry() == BB)
831 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
832 Exit = *BlockTraits::child_begin(BB);
837 RegionT *ExitR = getRegionFor(Exit);
838 while (ExitR && ExitR->getParent() &&
839 ExitR->getParent()->getEntry() == Exit)
840 ExitR = ExitR->getParent();
842 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(Exit),
843 InvBlockTraits::child_end(Exit))) {
844 if (!R->contains(Pred) && !ExitR->contains(Pred))
849 if (DT->dominates(Exit, BB))
861 assert(
A &&
B &&
"One of the Regions is NULL");
866 while (!
B->contains(
A))
873typename Tr::RegionT *
877 for (RegionT *R : Regions)
878 ret = getCommonRegion(ret, R);
884typename Tr::RegionT *
886 RegionT *ret = getRegionFor(BBs.
back());
889 for (BlockT *BB : BBs)
890 ret = getCommonRegion(ret, getRegionFor(BB));
897 using FuncPtrT = std::add_pointer_t<FuncT>;
904 scanForRegions(
F, &ShortCut);
906 buildRegionsTree(DT->getNode(BB), TopLevelRegion);
static const Function * getParent(const Value *V)
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...
print Instructions which execute on loop entry
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.