12 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H 13 #define LLVM_ANALYSIS_REGIONINFOIMPL_H 25 #include "llvm/Config/llvm-config.h" 35 #include <type_traits> 38 #define DEBUG_TYPE "region" 46 typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
48 : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
59 this->
entry.setPointer(BB);
64 assert(exit &&
"No exit to replace!");
70 std::vector<RegionT *> RegionQueue;
71 BlockT *OldEntry = getEntry();
73 RegionQueue.push_back(static_cast<RegionT *>(
this));
74 while (!RegionQueue.empty()) {
75 RegionT *R = RegionQueue.back();
76 RegionQueue.pop_back();
78 R->replaceEntry(NewEntry);
79 for (std::unique_ptr<RegionT> &Child : *R) {
80 if (Child->getEntry() == OldEntry)
81 RegionQueue.push_back(Child.get());
88 std::vector<RegionT *> RegionQueue;
89 BlockT *OldExit = getExit();
91 RegionQueue.push_back(static_cast<RegionT *>(
this));
92 while (!RegionQueue.empty()) {
93 RegionT *R = RegionQueue.back();
94 RegionQueue.pop_back();
96 R->replaceExit(NewExit);
97 for (std::unique_ptr<RegionT> &Child : *R) {
98 if (Child->getExit() == OldExit)
99 RegionQueue.push_back(Child.get());
106 BlockT *BB =
const_cast<BlockT *
>(
B);
108 if (!DT->getNode(BB))
111 BlockT *
entry = getEntry(), *exit = getExit();
117 return (DT->dominates(entry, BB) &&
118 !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
127 return getExit() ==
nullptr;
133 L->getExitingBlocks(ExitingBlocks);
135 for (BlockT *BB : ExitingBlocks) {
148 while (L &&
contains(L->getParentLoop())) {
149 L = L->getParentLoop();
158 assert(LI && BB &&
"LI and BB cannot be null!");
159 LoopT *L = LI->getLoopFor(BB);
160 return outermostLoopInRegion(L);
165 BlockT *
entry = getEntry();
166 BlockT *enteringBlock =
nullptr;
168 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(entry),
169 InvBlockTraits::child_end(entry))) {
170 if (DT->getNode(Pred) && !
contains(Pred)) {
174 enteringBlock = Pred;
178 return enteringBlock;
184 bool CoverAll =
true;
189 for (PredIterTy PI = InvBlockTraits::child_begin(exit),
190 PE = InvBlockTraits::child_end(exit);
206 BlockT *exit = getExit();
207 BlockT *exitingBlock =
nullptr;
212 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(exit),
213 InvBlockTraits::child_end(exit))) {
227 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
232 std::string exitName;
233 std::string entryName;
238 getEntry()->printAsOperand(OS,
false);
240 entryName = getEntry()->getName();
246 getExit()->printAsOperand(OS,
false);
248 exitName = getExit()->getName();
250 exitName =
"<Function Return>";
252 return entryName +
" => " + exitName;
260 BlockT *
entry = getEntry(), *exit = getExit();
263 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
264 if (!
contains(Succ) && exit != Succ)
266 "to the exit node!");
270 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(BB),
271 InvBlockTraits::child_end(BB))) {
274 "go to the entry node!");
281 BlockT *exit = getExit();
285 verifyBBInRegion(BB);
288 make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
289 if (Succ != exit && visited->find(Succ) == visited->end())
290 verifyWalk(Succ, visited);
302 std::set<BlockT *> visited;
303 verifyWalk(getEntry(), &visited);
308 for (
const std::unique_ptr<RegionT> &R : *
this)
309 R->verifyRegionNest();
328 static_cast<const RegionT *>(
this));
335 static_cast<const RegionT *>(
this));
340 using RegionT =
typename Tr::RegionT;
342 RegionT *R = RI->getRegionFor(BB);
350 while (
contains(R->getParent()) && R->getParent() !=
this)
353 if (R->getEntry() != BB)
363 typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
365 if (at == BBNodeMap.end()) {
367 typename BBNodeMapT::value_type V = {
369 llvm::make_unique<RegionNodeT>(
static_cast<RegionT *
>(Deconst), BB)};
370 at = BBNodeMap.insert(std::move(V)).first;
372 return at->second.get();
378 if (RegionT *Child = getSubRegionNode(BB))
379 return Child->getNode();
381 return getBBNode(BB);
386 for (std::unique_ptr<RegionT> &R : *
this) {
388 To->children.push_back(std::move(R));
395 assert(!SubRegion->parent &&
"SubRegion already has a parent!");
397 [&](
const std::unique_ptr<RegionT> &R) {
398 return R.get() == SubRegion;
400 "Subregion already exists!");
402 SubRegion->parent =
static_cast<RegionT *
>(
this);
403 children.push_back(std::unique_ptr<RegionT>(SubRegion));
408 assert(SubRegion->children.empty() &&
409 "SubRegions that contain children are not supported");
411 for (RegionNodeT *Element : elements()) {
412 if (!Element->isSubRegion()) {
413 BlockT *BB = Element->template getNodeAs<BlockT>();
415 if (SubRegion->contains(BB))
416 RI->setRegionFor(BB, SubRegion);
420 std::vector<std::unique_ptr<RegionT>> Keep;
421 for (std::unique_ptr<RegionT> &R : *
this) {
422 if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
423 R->parent = SubRegion;
424 SubRegion->children.push_back(std::move(R));
426 Keep.push_back(std::move(R));
432 std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
433 std::move_iterator<typename RegionSet::iterator>(Keep.end()));
438 assert(Child->parent ==
this &&
"Child is not a child of this region!");
439 Child->parent =
nullptr;
440 typename RegionSet::iterator
I =
442 return R.get() == Child;
444 assert(I !=
children.end() &&
"Region does not exit. Unable to remove.");
453 for (RegionT *R =
getParent(); R !=
nullptr; R = R->getParent())
461 unsigned NumSuccessors = Tr::getNumSuccessors(exit);
463 if (NumSuccessors == 0)
466 RegionT *R = RI->getRegionFor(exit);
468 if (R->getEntry() != exit) {
469 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
470 InvBlockTraits::child_end(getExit())))
473 if (Tr::getNumSuccessors(exit) == 1)
474 return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
478 while (R->getParent() && R->getParent()->getEntry() == exit)
481 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
482 InvBlockTraits::child_end(getExit()))) {
483 if (!(
contains(Pred) || R->contains(Pred)))
487 return new RegionT(getEntry(), R->getExit(), RI, DT);
494 OS.
indent(level * 2) <<
'[' << level <<
"] " << getNameStr();
496 OS.
indent(level * 2) << getNameStr();
500 if (Style != PrintNone) {
501 OS.
indent(level * 2) <<
"{\n";
504 if (Style == PrintBB) {
505 for (
const auto *BB : blocks())
506 OS << BB->getName() <<
", ";
507 }
else if (Style == PrintRN) {
508 for (
const RegionNodeT *Element : elements()) {
509 OS << *Element <<
", ";
517 for (
const std::unique_ptr<RegionT> &R : *
this)
518 R->print(OS, print_tree, level + 1, Style);
521 if (Style != PrintNone)
522 OS.
indent(level * 2) <<
"} \n";
525 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 535 for (std::unique_ptr<RegionT> &R : *
this)
553 assert(R &&
"Re must be non-null");
554 for (
const typename Tr::RegionNodeT *Element : R->elements()) {
555 if (Element->isSubRegion()) {
556 const RegionT *SR = Element->template getNodeAs<RegionT>();
559 BlockT *BB = Element->template getNodeAs<BlockT>();
560 if (getRegionFor(BB) != R)
568 BlockT *exit)
const {
569 for (BlockT *
P :
make_range(InvBlockTraits::child_begin(BB),
570 InvBlockTraits::child_end(BB))) {
571 if (DT->dominates(entry,
P) && !DT->dominates(exit,
P))
580 assert(entry && exit &&
"entry and exit must not be null!");
582 using DST =
typename DomFrontierT::DomSetType;
584 DST *entrySuccs = &DF->find(entry)->second;
588 if (!DT->dominates(entry, exit)) {
589 for (
typename DST::iterator
SI = entrySuccs->begin(),
590 SE = entrySuccs->end();
592 if (*
SI != exit && *
SI != entry)
599 DST *exitSuccs = &DF->find(exit)->second;
602 for (BlockT *Succ : *entrySuccs) {
603 if (Succ == exit || Succ == entry)
605 if (exitSuccs->find(Succ) == exitSuccs->end())
607 if (!isCommonDomFrontier(Succ, entry, exit))
612 for (BlockT *Succ : *exitSuccs) {
613 if (DT->properlyDominates(entry, Succ) && Succ != exit)
622 BBtoBBMap *ShortCut)
const {
623 assert(entry && exit &&
"entry and exit must not be null!");
625 typename BBtoBBMap::iterator e = ShortCut->find(exit);
627 if (e == ShortCut->end())
629 (*ShortCut)[
entry] = exit;
634 BlockT *BB = e->second;
635 (*ShortCut)[
entry] = BB;
640 typename Tr::DomTreeNodeT *
642 typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
644 if (e == ShortCut->end())
647 return PDT->getNode(e->second)->getIDom();
652 assert(entry && exit &&
"entry and exit must not be null!");
654 unsigned num_successors =
655 BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
657 if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
666 assert(entry && exit &&
"entry and exit must not be null!");
668 if (isTrivialRegion(entry, exit))
672 new RegionT(entry, exit, static_cast<RegionInfoT *>(
this), DT);
673 BBtoRegion.insert({
entry, region});
675 #ifdef EXPENSIVE_CHECKS 676 region->verifyRegion();
681 updateStatistics(region);
687 BBtoBBMap *ShortCut) {
690 DomTreeNodeT *N = PDT->getNode(entry);
694 RegionT *lastRegion =
nullptr;
695 BlockT *lastExit =
entry;
699 while ((N = getNextPostDom(N, ShortCut))) {
700 BlockT *exit = N->getBlock();
705 if (isRegion(entry, exit)) {
706 RegionT *newRegion = createRegion(entry, exit);
709 newRegion->addSubRegion(lastRegion);
711 lastRegion = newRegion;
716 if (!DT->dominates(entry, exit))
722 if (lastExit != entry)
723 insertShortCut(entry, lastExit, ShortCut);
728 using FuncPtrT =
typename std::add_pointer<FuncT>::type;
731 DomTreeNodeT *N = DT->getNode(entry);
738 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
743 while (region->getParent())
744 region = region->getParent();
751 BlockT *BB = N->getBlock();
754 while (BB == region->getExit())
755 region = region->getParent();
757 typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
761 if (it != BBtoRegion.end()) {
762 RegionT *newRegion = it->second;
763 region->addSubRegion(getTopMostParent(newRegion));
766 BBtoRegion[BB] = region;
770 buildRegionsTree(
C, region);
774 #ifdef EXPENSIVE_CHECKS 779 bool RegionInfoBase<Tr>::VerifyRegionInfo =
false;
788 OS <<
"Region tree:\n";
789 TopLevelRegion->print(OS,
true, 0, printStyle);
790 OS <<
"End region tree\n";
793 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 802 delete TopLevelRegion;
803 TopLevelRegion =
nullptr;
810 if (!RegionInfoBase<Tr>::VerifyRegionInfo)
813 TopLevelRegion->verifyRegionNest();
815 verifyBBMap(TopLevelRegion);
822 return I != BBtoRegion.end() ? I->second :
nullptr;
832 return getRegionFor(BB);
836 typename RegionInfoBase<Tr>::BlockT *
838 BlockT *Exit =
nullptr;
842 RegionT *R = getRegionFor(BB);
843 while (R && R->getParent() && R->getParent()->getEntry() == BB)
847 if (R && R->getEntry() == BB)
849 else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
850 Exit = *BlockTraits::child_begin(BB);
855 RegionT *ExitR = getRegionFor(Exit);
856 while (ExitR && ExitR->getParent() &&
857 ExitR->getParent()->getEntry() == Exit)
858 ExitR = ExitR->getParent();
860 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(Exit),
861 InvBlockTraits::child_end(Exit))) {
862 if (!R->contains(Pred) && !ExitR->contains(Pred))
867 if (DT->dominates(Exit, BB))
879 assert(A && B &&
"One of the Regions is NULL");
884 while (!B->contains(A))
891 typename Tr::RegionT *
893 RegionT *ret = Regions.
back();
896 for (RegionT *R : Regions)
897 ret = getCommonRegion(ret, R);
903 typename Tr::RegionT *
905 RegionT *ret = getRegionFor(BBs.
back());
908 for (BlockT *BB : BBs)
909 ret = getCommonRegion(ret, getRegionFor(BB));
916 using FuncPtrT =
typename std::add_pointer<FuncT>::type;
923 scanForRegions(F, &ShortCut);
925 buildRegionsTree(DT->getNode(BB), TopLevelRegion);
932 #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
bool getExitingBlocks(SmallVectorImpl< BlockT *> &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
This class represents lattice values for constants.
void push_back(const T &Elt)
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void print(raw_ostream &OS) const
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
unsigned getDepth() const
Get the nesting level of this Region.
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
Analysis that detects all canonical Regions.
return AArch64::GPR64RegClass contains(Reg)
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
void clearNodeCache()
Clear the cache for BB RegionNodes.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
static StringRef getName(Value *V)
void verifyAnalysis() const
PrintStyle
PrintStyle - Print region in difference ways.
Base class for the actual dominator tree node.
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors...
bool isSimple() const
Is this a simple region?
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
void dump() const
Print the region to stderr.
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
element_iterator element_end()
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
iterator_range< po_iterator< T > > post_order(const T &G)
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
A single entry single exit Region.
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
element_iterator element_begin()
std::string getNameStr() const
Returns the name of the Region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
void verifyRegion() const
Verify if the region is a correct region.
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
~RegionBase()
Delete the Region and all its subregions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A raw_ostream that writes to an std::string.
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
print Instructions which execute on loop entry
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.