11 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
12 #define LLVM_ANALYSIS_REGIONINFOIMPL_H
22 #include "llvm/Config/llvm-config.h"
31 #include <type_traits>
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);
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) &&
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 BlockT *
entry = getEntry();
163 BlockT *enteringBlock =
nullptr;
166 InvBlockTraits::child_end(
entry))) {
167 if (DT->getNode(Pred) && !
contains(Pred)) {
171 enteringBlock = Pred;
175 return enteringBlock;
181 bool CoverAll =
true;
186 for (PredIterTy PI = InvBlockTraits::child_begin(
exit),
187 PE = InvBlockTraits::child_end(
exit);
191 Exitings.push_back(Pred);
203 BlockT *
exit = getExit();
204 BlockT *exitingBlock =
nullptr;
210 InvBlockTraits::child_end(
exit))) {
224 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
229 std::string exitName;
230 std::string entryName;
235 getEntry()->printAsOperand(OS,
false);
237 entryName = std::string(getEntry()->
getName());
243 getExit()->printAsOperand(OS,
false);
245 exitName = std::string(getExit()->
getName());
247 exitName =
"<Function Return>";
249 return entryName +
" => " + exitName;
257 BlockT *
entry = getEntry(), *
exit = getExit();
260 make_range(BlockTraits::child_begin(
BB), BlockTraits::child_end(
BB))) {
263 "to the exit node!");
267 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(
BB),
268 InvBlockTraits::child_end(
BB))) {
271 "go to the entry node!");
277 void RegionBase<Tr>::verifyWalk(BlockT *
BB, std::set<BlockT *> *visited)
const {
278 BlockT *
exit = getExit();
282 verifyBBInRegion(
BB);
285 make_range(BlockTraits::child_begin(
BB), BlockTraits::child_end(
BB))) {
286 if (Succ !=
exit && visited->find(Succ) == visited->end())
287 verifyWalk(Succ, visited);
299 std::set<BlockT *> visited;
300 verifyWalk(getEntry(), &visited);
305 for (
const std::unique_ptr<RegionT> &
R : *
this)
306 R->verifyRegionNest();
325 static_cast<const RegionT *
>(
this));
331 return GraphTraits<const RegionT *>::nodes_end(
332 static_cast<const RegionT *
>(
this));
337 using RegionT =
typename Tr::RegionT;
339 RegionT *
R = RI->getRegionFor(
BB);
347 while (
contains(
R->getParent()) &&
R->getParent() !=
this)
350 if (
R->getEntry() !=
BB)
360 typename BBNodeMapT::const_iterator
at = BBNodeMap.find(
BB);
362 if (
at == BBNodeMap.end()) {
364 typename BBNodeMapT::value_type V = {
366 std::make_unique<RegionNodeT>(
static_cast<RegionT *
>(Deconst),
BB)};
369 return at->second.get();
375 if (RegionT *Child = getSubRegionNode(
BB))
376 return Child->getNode();
378 return getBBNode(
BB);
383 for (std::unique_ptr<RegionT> &
R : *
this) {
392 assert(!SubRegion->parent &&
"SubRegion already has a parent!");
394 [&](
const std::unique_ptr<RegionT> &
R) {
395 return R.get() == SubRegion;
397 "Subregion already exists!");
399 SubRegion->parent =
static_cast<RegionT *
>(
this);
400 children.push_back(std::unique_ptr<RegionT>(SubRegion));
405 assert(SubRegion->children.empty() &&
406 "SubRegions that contain children are not supported");
408 for (RegionNodeT *Element :
elements()) {
409 if (!Element->isSubRegion()) {
410 BlockT *
BB = Element->template getNodeAs<BlockT>();
412 if (SubRegion->contains(
BB))
413 RI->setRegionFor(
BB, SubRegion);
417 std::vector<std::unique_ptr<RegionT>> Keep;
418 for (std::unique_ptr<RegionT> &
R : *
this) {
419 if (SubRegion->contains(
R.get()) &&
R.get() != SubRegion) {
420 R->parent = SubRegion;
429 std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
430 std::move_iterator<typename RegionSet::iterator>(Keep.end()));
435 assert(Child->parent ==
this &&
"Child is not a child of this region!");
436 Child->parent =
nullptr;
437 typename RegionSet::iterator
I =
439 return R.get() == Child;
441 assert(
I !=
children.end() &&
"Region does not exit. Unable to remove.");
450 for (RegionT *
R =
getParent();
R !=
nullptr;
R =
R->getParent())
458 unsigned NumSuccessors = Tr::getNumSuccessors(
exit);
460 if (NumSuccessors == 0)
463 RegionT *
R = RI->getRegionFor(
exit);
465 if (
R->getEntry() !=
exit) {
466 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
467 InvBlockTraits::child_end(getExit())))
470 if (Tr::getNumSuccessors(
exit) == 1)
471 return new RegionT(getEntry(), *BlockTraits::child_begin(
exit), RI, DT);
475 while (
R->getParent() &&
R->getParent()->getEntry() ==
exit)
478 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(getExit()),
479 InvBlockTraits::child_end(getExit()))) {
480 if (!(
contains(Pred) ||
R->contains(Pred)))
484 return new RegionT(getEntry(),
R->getExit(), RI, DT);
491 OS.
indent(level * 2) <<
'[' << level <<
"] " << getNameStr();
493 OS.
indent(level * 2) << getNameStr();
497 if (
Style != PrintNone) {
498 OS.
indent(level * 2) <<
"{\n";
501 if (
Style == PrintBB) {
502 for (
const auto *
BB : blocks())
503 OS <<
BB->getName() <<
", ";
504 }
else if (
Style == PrintRN) {
505 for (
const RegionNodeT *Element :
elements()) {
506 OS << *Element <<
", ";
514 for (
const std::unique_ptr<RegionT> &
R : *
this)
515 R->print(OS, print_tree, level + 1,
Style);
518 if (
Style != PrintNone)
519 OS.
indent(level * 2) <<
"} \n";
522 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
532 for (std::unique_ptr<RegionT> &
R : *
this)
549 void RegionInfoBase<Tr>::verifyBBMap(
const RegionT *
R)
const {
550 assert(
R &&
"Re must be non-null");
551 for (
const typename Tr::RegionNodeT *Element :
R->elements()) {
552 if (Element->isSubRegion()) {
553 const RegionT *SR = Element->template getNodeAs<RegionT>();
556 BlockT *
BB = Element->template getNodeAs<BlockT>();
557 if (getRegionFor(
BB) !=
R)
564 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *
BB, BlockT *
entry,
565 BlockT *
exit)
const {
567 InvBlockTraits::child_end(
BB))) {
568 if (DT->dominates(
entry,
P) && !DT->dominates(
exit,
P))
576 bool RegionInfoBase<Tr>::isRegion(BlockT *
entry, BlockT *
exit)
const {
579 using DST =
typename DomFrontierT::DomSetType;
581 DST *entrySuccs = &
DF->find(
entry)->second;
586 for (BlockT *successor : *entrySuccs) {
587 if (successor !=
exit && successor !=
entry)
594 DST *exitSuccs = &
DF->find(
exit)->second;
597 for (BlockT *Succ : *entrySuccs) {
600 if (exitSuccs->find(Succ) == exitSuccs->end())
602 if (!isCommonDomFrontier(Succ,
entry,
exit))
607 for (BlockT *Succ : *exitSuccs) {
608 if (DT->properlyDominates(
entry, Succ) && Succ !=
exit)
616 void RegionInfoBase<Tr>::insertShortCut(BlockT *
entry, BlockT *
exit,
617 BBtoBBMap *ShortCut)
const {
620 typename BBtoBBMap::iterator
e = ShortCut->find(
exit);
622 if (
e == ShortCut->end())
629 BlockT *
BB =
e->second;
635 typename Tr::DomTreeNodeT *
636 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *
N, BBtoBBMap *ShortCut)
const {
637 typename BBtoBBMap::iterator
e = ShortCut->find(
N->getBlock());
639 if (
e == ShortCut->end())
642 return PDT->getNode(
e->second)->getIDom();
646 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *
entry, BlockT *
exit)
const {
649 unsigned num_successors =
650 BlockTraits::child_end(
entry) - BlockTraits::child_begin(
entry);
652 if (num_successors <= 1 &&
exit == *(BlockTraits::child_begin(
entry)))
659 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *
entry,
667 new RegionT(
entry,
exit,
static_cast<RegionInfoT *
>(
this), DT);
668 BBtoRegion.insert({
entry, region});
670 #ifdef EXPENSIVE_CHECKS
671 region->verifyRegion();
676 updateStatistics(region);
681 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *
entry,
682 BBtoBBMap *ShortCut) {
685 DomTreeNodeT *
N = PDT->getNode(
entry);
689 RegionT *lastRegion =
nullptr;
690 BlockT *lastExit =
entry;
694 while ((
N = getNextPostDom(
N, ShortCut))) {
695 BlockT *
exit =
N->getBlock();
701 RegionT *newRegion = createRegion(
entry,
exit);
704 newRegion->addSubRegion(lastRegion);
706 lastRegion = newRegion;
717 if (lastExit !=
entry)
718 insertShortCut(
entry, lastExit, ShortCut);
722 void RegionInfoBase<Tr>::scanForRegions(FuncT &
F, BBtoBBMap *ShortCut) {
723 using FuncPtrT = std::add_pointer_t<FuncT>;
725 BlockT *
entry = GraphTraits<FuncPtrT>::getEntryNode(&
F);
726 DomTreeNodeT *
N = DT->getNode(
entry);
733 findRegionsWithEntry(DomNode->getBlock(), ShortCut);
737 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
738 while (region->getParent())
739 region = region->getParent();
745 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *
N, RegionT *region) {
746 BlockT *
BB =
N->getBlock();
749 while (
BB == region->getExit())
750 region = region->getParent();
752 typename BBtoRegionMap::iterator
it = BBtoRegion.find(
BB);
756 if (
it != BBtoRegion.end()) {
757 RegionT *newRegion =
it->second;
758 region->addSubRegion(getTopMostParent(newRegion));
761 BBtoRegion[
BB] = region;
764 for (DomTreeNodeBase<BlockT> *
C : *
N) {
765 buildRegionsTree(
C, region);
769 #ifdef EXPENSIVE_CHECKS
783 OS <<
"Region tree:\n";
784 TopLevelRegion->print(OS,
true, 0, printStyle);
785 OS <<
"End region tree\n";
788 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
797 delete TopLevelRegion;
798 TopLevelRegion =
nullptr;
808 TopLevelRegion->verifyRegionNest();
810 verifyBBMap(TopLevelRegion);
816 return BBtoRegion.lookup(
BB);
826 return getRegionFor(
BB);
830 typename RegionInfoBase<Tr>::BlockT *
832 BlockT *Exit =
nullptr;
836 RegionT *
R = getRegionFor(
BB);
837 while (
R &&
R->getParent() &&
R->getParent()->getEntry() ==
BB)
841 if (
R &&
R->getEntry() ==
BB)
843 else if (++BlockTraits::child_begin(
BB) == BlockTraits::child_end(
BB))
844 Exit = *BlockTraits::child_begin(
BB);
849 RegionT *ExitR = getRegionFor(Exit);
850 while (ExitR && ExitR->getParent() &&
851 ExitR->getParent()->getEntry() == Exit)
852 ExitR = ExitR->getParent();
854 for (BlockT *Pred :
make_range(InvBlockTraits::child_begin(Exit),
855 InvBlockTraits::child_end(Exit))) {
856 if (!
R->contains(Pred) && !ExitR->contains(Pred))
861 if (DT->dominates(Exit,
BB))
873 assert(
A &&
B &&
"One of the Regions is NULL");
878 while (!
B->contains(
A))
885 typename Tr::RegionT *
889 for (RegionT *
R : Regions)
896 typename Tr::RegionT *
898 RegionT *
ret = getRegionFor(BBs.back());
901 for (BlockT *
BB : BBs)
902 ret = getCommonRegion(
ret, getRegionFor(
BB));
909 using FuncPtrT = std::add_pointer_t<FuncT>;
916 scanForRegions(
F, &ShortCut);
918 buildRegionsTree(DT->getNode(
BB), TopLevelRegion);
925 #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H