1 //===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // Detects single entry single exit regions in the control flow graph.
10 //===----------------------------------------------------------------------===//
12 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
13 #define LLVM_ANALYSIS_REGIONINFOIMPL_H
15 #include "llvm/ADT/PostOrderIterator.h"
16 #include "llvm/Analysis/DominanceFrontier.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/PostDominators.h"
19 #include "llvm/Analysis/RegionInfo.h"
20 #include "llvm/Analysis/RegionIterator.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/ErrorHandling.h"
30 #define DEBUG_TYPE "region"
32 //===----------------------------------------------------------------------===//
33 /// RegionBase Implementation
35 RegionBase
<Tr
>::RegionBase(BlockT
*Entry
, BlockT
*Exit
,
36 typename
Tr::RegionInfoT
*RInfo
, DomTreeT
*dt
,
38 : RegionNodeBase
<Tr
>(Parent
, Entry
, 1), RI(RInfo
), DT(dt
), exit(Exit
) {}
41 RegionBase
<Tr
>::~RegionBase() {
42 // Free the cached nodes.
43 for (typename
BBNodeMapT::iterator it
= BBNodeMap
.begin(),
48 // Only clean the cache for this Region. Caches of child Regions will be
49 // cleaned when the child Regions are deleted.
54 void RegionBase
<Tr
>::replaceEntry(BlockT
*BB
) {
55 this->entry
.setPointer(BB
);
59 void RegionBase
<Tr
>::replaceExit(BlockT
*BB
) {
60 assert(exit
&& "No exit to replace!");
65 void RegionBase
<Tr
>::replaceEntryRecursive(BlockT
*NewEntry
) {
66 std::vector
<RegionT
*> RegionQueue
;
67 BlockT
*OldEntry
= getEntry();
69 RegionQueue
.push_back(static_cast<RegionT
*>(this));
70 while (!RegionQueue
.empty()) {
71 RegionT
*R
= RegionQueue
.back();
72 RegionQueue
.pop_back();
74 R
->replaceEntry(NewEntry
);
75 for (typename
RegionT::const_iterator RI
= R
->begin(), RE
= R
->end();
77 if ((*RI
)->getEntry() == OldEntry
)
78 RegionQueue
.push_back(RI
->get());
84 void RegionBase
<Tr
>::replaceExitRecursive(BlockT
*NewExit
) {
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 (typename
RegionT::const_iterator RI
= R
->begin(), RE
= R
->end();
96 if ((*RI
)->getExit() == OldExit
)
97 RegionQueue
.push_back(RI
->get());
103 bool RegionBase
<Tr
>::contains(const BlockT
*B
) const {
104 BlockT
*BB
= const_cast<BlockT
*>(B
);
106 if (!DT
->getNode(BB
))
109 BlockT
*entry
= getEntry(), *exit
= getExit();
115 return (DT
->dominates(entry
, BB
) &&
116 !(DT
->dominates(exit
, BB
) && DT
->dominates(entry
, exit
)));
120 bool RegionBase
<Tr
>::contains(const LoopT
*L
) const {
121 // BBs that are not part of any loop are element of the Loop
122 // described by the NULL pointer. This loop is not part of any region,
123 // except if the region describes the whole function.
125 return getExit() == nullptr;
127 if (!contains(L
->getHeader()))
130 SmallVector
<BlockT
*, 8> ExitingBlocks
;
131 L
->getExitingBlocks(ExitingBlocks
);
133 for (BlockT
*BB
: ExitingBlocks
) {
142 typename
Tr::LoopT
*RegionBase
<Tr
>::outermostLoopInRegion(LoopT
*L
) const {
146 while (L
&& contains(L
->getParentLoop())) {
147 L
= L
->getParentLoop();
154 typename
Tr::LoopT
*RegionBase
<Tr
>::outermostLoopInRegion(LoopInfoT
*LI
,
156 assert(LI
&& BB
&& "LI and BB cannot be null!");
157 LoopT
*L
= LI
->getLoopFor(BB
);
158 return outermostLoopInRegion(L
);
162 typename RegionBase
<Tr
>::BlockT
*RegionBase
<Tr
>::getEnteringBlock() const {
163 BlockT
*entry
= getEntry();
165 BlockT
*enteringBlock
= nullptr;
167 for (PredIterTy PI
= InvBlockTraits::child_begin(entry
),
168 PE
= InvBlockTraits::child_end(entry
);
171 if (DT
->getNode(Pred
) && !contains(Pred
)) {
175 enteringBlock
= Pred
;
179 return enteringBlock
;
183 typename RegionBase
<Tr
>::BlockT
*RegionBase
<Tr
>::getExitingBlock() const {
184 BlockT
*exit
= getExit();
186 BlockT
*exitingBlock
= nullptr;
191 for (PredIterTy PI
= InvBlockTraits::child_begin(exit
),
192 PE
= InvBlockTraits::child_end(exit
);
195 if (contains(Pred
)) {
207 bool RegionBase
<Tr
>::isSimple() const {
208 return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
212 std::string RegionBase
<Tr
>::getNameStr() const {
213 std::string exitName
;
214 std::string entryName
;
216 if (getEntry()->getName().empty()) {
217 raw_string_ostream
OS(entryName
);
219 getEntry()->printAsOperand(OS
, false);
221 entryName
= getEntry()->getName();
224 if (getExit()->getName().empty()) {
225 raw_string_ostream
OS(exitName
);
227 getExit()->printAsOperand(OS
, false);
229 exitName
= getExit()->getName();
231 exitName
= "<Function Return>";
233 return entryName
+ " => " + exitName
;
237 void RegionBase
<Tr
>::verifyBBInRegion(BlockT
*BB
) const {
239 llvm_unreachable("Broken region found!");
241 BlockT
*entry
= getEntry(), *exit
= getExit();
243 for (SuccIterTy SI
= BlockTraits::child_begin(BB
),
244 SE
= BlockTraits::child_end(BB
);
246 if (!contains(*SI
) && exit
!= *SI
)
247 llvm_unreachable("Broken region found!");
251 for (PredIterTy SI
= InvBlockTraits::child_begin(BB
),
252 SE
= InvBlockTraits::child_end(BB
);
255 llvm_unreachable("Broken region found!");
261 void RegionBase
<Tr
>::verifyWalk(BlockT
*BB
, std::set
<BlockT
*> *visited
) const {
262 BlockT
*exit
= getExit();
266 verifyBBInRegion(BB
);
268 for (SuccIterTy SI
= BlockTraits::child_begin(BB
),
269 SE
= BlockTraits::child_end(BB
);
271 if (*SI
!= exit
&& visited
->find(*SI
) == visited
->end())
272 verifyWalk(*SI
, visited
);
277 void RegionBase
<Tr
>::verifyRegion() const {
278 // Only do verification when user wants to, otherwise this expensive check
279 // will be invoked by PMDataManager::verifyPreservedAnalysis when
280 // a regionpass (marked PreservedAll) finish.
281 if (!RegionInfoBase
<Tr
>::VerifyRegionInfo
)
284 std::set
<BlockT
*> visited
;
285 verifyWalk(getEntry(), &visited
);
289 void RegionBase
<Tr
>::verifyRegionNest() const {
290 for (typename
RegionT::const_iterator RI
= begin(), RE
= end(); RI
!= RE
;
292 (*RI
)->verifyRegionNest();
298 typename RegionBase
<Tr
>::element_iterator RegionBase
<Tr
>::element_begin() {
299 return GraphTraits
<RegionT
*>::nodes_begin(static_cast<RegionT
*>(this));
303 typename RegionBase
<Tr
>::element_iterator RegionBase
<Tr
>::element_end() {
304 return GraphTraits
<RegionT
*>::nodes_end(static_cast<RegionT
*>(this));
308 typename RegionBase
<Tr
>::const_element_iterator
309 RegionBase
<Tr
>::element_begin() const {
310 return GraphTraits
<const RegionT
*>::nodes_begin(
311 static_cast<const RegionT
*>(this));
315 typename RegionBase
<Tr
>::const_element_iterator
316 RegionBase
<Tr
>::element_end() const {
317 return GraphTraits
<const RegionT
*>::nodes_end(
318 static_cast<const RegionT
*>(this));
322 typename
Tr::RegionT
*RegionBase
<Tr
>::getSubRegionNode(BlockT
*BB
) const {
323 typedef typename
Tr::RegionT RegionT
;
324 RegionT
*R
= RI
->getRegionFor(BB
);
329 // If we pass the BB out of this region, that means our code is broken.
330 assert(contains(R
) && "BB not in current region!");
332 while (contains(R
->getParent()) && R
->getParent() != this)
335 if (R
->getEntry() != BB
)
342 typename
Tr::RegionNodeT
*RegionBase
<Tr
>::getBBNode(BlockT
*BB
) const {
343 assert(contains(BB
) && "Can get BB node out of this region!");
345 typename
BBNodeMapT::const_iterator at
= BBNodeMap
.find(BB
);
347 if (at
!= BBNodeMap
.end())
350 auto Deconst
= const_cast<RegionBase
<Tr
> *>(this);
351 RegionNodeT
*NewNode
= new RegionNodeT(static_cast<RegionT
*>(Deconst
), BB
);
352 BBNodeMap
.insert(std::make_pair(BB
, NewNode
));
357 typename
Tr::RegionNodeT
*RegionBase
<Tr
>::getNode(BlockT
*BB
) const {
358 assert(contains(BB
) && "Can get BB node out of this region!");
359 if (RegionT
*Child
= getSubRegionNode(BB
))
360 return Child
->getNode();
362 return getBBNode(BB
);
366 void RegionBase
<Tr
>::transferChildrenTo(RegionT
*To
) {
367 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
369 To
->children
.push_back(std::move(*I
));
375 void RegionBase
<Tr
>::addSubRegion(RegionT
*SubRegion
, bool moveChildren
) {
376 assert(!SubRegion
->parent
&& "SubRegion already has a parent!");
377 assert(std::find_if(begin(), end(), [&](const std::unique_ptr
<RegionT
> &R
) {
378 return R
.get() == SubRegion
;
379 }) == children
.end() &&
380 "Subregion already exists!");
382 SubRegion
->parent
= static_cast<RegionT
*>(this);
383 children
.push_back(std::unique_ptr
<RegionT
>(SubRegion
));
388 assert(SubRegion
->children
.empty() &&
389 "SubRegions that contain children are not supported");
391 for (element_iterator I
= element_begin(), E
= element_end(); I
!= E
; ++I
) {
392 if (!(*I
)->isSubRegion()) {
393 BlockT
*BB
= (*I
)->template getNodeAs
<BlockT
>();
395 if (SubRegion
->contains(BB
))
396 RI
->setRegionFor(BB
, SubRegion
);
400 std::vector
<std::unique_ptr
<RegionT
>> Keep
;
401 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
402 if (SubRegion
->contains(I
->get()) && I
->get() != SubRegion
) {
403 (*I
)->parent
= SubRegion
;
404 SubRegion
->children
.push_back(std::move(*I
));
406 Keep
.push_back(std::move(*I
));
412 std::move_iterator
<typename
RegionSet::iterator
>(Keep
.begin()),
413 std::move_iterator
<typename
RegionSet::iterator
>(Keep
.end()));
417 typename
Tr::RegionT
*RegionBase
<Tr
>::removeSubRegion(RegionT
*Child
) {
418 assert(Child
->parent
== this && "Child is not a child of this region!");
419 Child
->parent
= nullptr;
420 typename
RegionSet::iterator I
= std::find_if(
421 children
.begin(), children
.end(),
422 [&](const std::unique_ptr
<RegionT
> &R
) { return R
.get() == Child
; });
423 assert(I
!= children
.end() && "Region does not exit. Unable to remove.");
424 children
.erase(children
.begin() + (I
- begin()));
429 unsigned RegionBase
<Tr
>::getDepth() const {
432 for (RegionT
*R
= getParent(); R
!= nullptr; R
= R
->getParent())
439 typename
Tr::RegionT
*RegionBase
<Tr
>::getExpandedRegion() const {
440 unsigned NumSuccessors
= Tr::getNumSuccessors(exit
);
442 if (NumSuccessors
== 0)
445 for (PredIterTy PI
= InvBlockTraits::child_begin(getExit()),
446 PE
= InvBlockTraits::child_end(getExit());
448 if (!DT
->dominates(getEntry(), *PI
))
452 RegionT
*R
= RI
->getRegionFor(exit
);
454 if (R
->getEntry() != exit
) {
455 if (Tr::getNumSuccessors(exit
) == 1)
456 return new RegionT(getEntry(), *BlockTraits::child_begin(exit
), RI
, DT
);
460 while (R
->getParent() && R
->getParent()->getEntry() == exit
)
463 if (!DT
->dominates(getEntry(), R
->getExit())) {
464 for (PredIterTy PI
= InvBlockTraits::child_begin(getExit()),
465 PE
= InvBlockTraits::child_end(getExit());
467 if (!DT
->dominates(R
->getExit(), *PI
))
472 return new RegionT(getEntry(), R
->getExit(), RI
, DT
);
476 void RegionBase
<Tr
>::print(raw_ostream
&OS
, bool print_tree
, unsigned level
,
477 PrintStyle Style
) const {
479 OS
.indent(level
* 2) << '[' << level
<< "] " << getNameStr();
481 OS
.indent(level
* 2) << getNameStr();
485 if (Style
!= PrintNone
) {
486 OS
.indent(level
* 2) << "{\n";
487 OS
.indent(level
* 2 + 2);
489 if (Style
== PrintBB
) {
490 for (const auto &BB
: blocks())
491 OS
<< BB
->getName() << ", "; // TODO: remove the last ","
492 } else if (Style
== PrintRN
) {
493 for (const_element_iterator I
= element_begin(), E
= element_end();
495 OS
<< **I
<< ", "; // TODO: remove the last ",
503 for (const_iterator RI
= begin(), RE
= end(); RI
!= RE
; ++RI
)
504 (*RI
)->print(OS
, print_tree
, level
+ 1, Style
);
507 if (Style
!= PrintNone
)
508 OS
.indent(level
* 2) << "} \n";
511 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
513 void RegionBase
<Tr
>::dump() const {
514 print(dbgs(), true, getDepth(), RegionInfoBase
<Tr
>::printStyle
);
519 void RegionBase
<Tr
>::clearNodeCache() {
520 // Free the cached nodes.
521 for (typename
BBNodeMapT::iterator I
= BBNodeMap
.begin(),
522 IE
= BBNodeMap
.end();
527 for (typename
RegionT::iterator RI
= begin(), RE
= end(); RI
!= RE
; ++RI
)
528 (*RI
)->clearNodeCache();
531 //===----------------------------------------------------------------------===//
532 // RegionInfoBase implementation
536 RegionInfoBase
<Tr
>::RegionInfoBase()
537 : TopLevelRegion(nullptr) {}
540 RegionInfoBase
<Tr
>::~RegionInfoBase() {
545 bool RegionInfoBase
<Tr
>::isCommonDomFrontier(BlockT
*BB
, BlockT
*entry
,
546 BlockT
*exit
) const {
547 for (PredIterTy PI
= InvBlockTraits::child_begin(BB
),
548 PE
= InvBlockTraits::child_end(BB
);
551 if (DT
->dominates(entry
, P
) && !DT
->dominates(exit
, P
))
559 bool RegionInfoBase
<Tr
>::isRegion(BlockT
*entry
, BlockT
*exit
) const {
560 assert(entry
&& exit
&& "entry and exit must not be null!");
561 typedef typename
DomFrontierT::DomSetType DST
;
563 DST
*entrySuccs
= &DF
->find(entry
)->second
;
565 // Exit is the header of a loop that contains the entry. In this case,
566 // the dominance frontier must only contain the exit.
567 if (!DT
->dominates(entry
, exit
)) {
568 for (typename
DST::iterator SI
= entrySuccs
->begin(),
569 SE
= entrySuccs
->end();
571 if (*SI
!= exit
&& *SI
!= entry
)
578 DST
*exitSuccs
= &DF
->find(exit
)->second
;
580 // Do not allow edges leaving the region.
581 for (typename
DST::iterator SI
= entrySuccs
->begin(), SE
= entrySuccs
->end();
583 if (*SI
== exit
|| *SI
== entry
)
585 if (exitSuccs
->find(*SI
) == exitSuccs
->end())
587 if (!isCommonDomFrontier(*SI
, entry
, exit
))
591 // Do not allow edges pointing into the region.
592 for (typename
DST::iterator SI
= exitSuccs
->begin(), SE
= exitSuccs
->end();
594 if (DT
->properlyDominates(entry
, *SI
) && *SI
!= exit
)
602 void RegionInfoBase
<Tr
>::insertShortCut(BlockT
*entry
, BlockT
*exit
,
603 BBtoBBMap
*ShortCut
) const {
604 assert(entry
&& exit
&& "entry and exit must not be null!");
606 typename
BBtoBBMap::iterator e
= ShortCut
->find(exit
);
608 if (e
== ShortCut
->end())
609 // No further region at exit available.
610 (*ShortCut
)[entry
] = exit
;
612 // We found a region e that starts at exit. Therefore (entry, e->second)
613 // is also a region, that is larger than (entry, exit). Insert the
615 BlockT
*BB
= e
->second
;
616 (*ShortCut
)[entry
] = BB
;
621 typename
Tr::DomTreeNodeT
*
622 RegionInfoBase
<Tr
>::getNextPostDom(DomTreeNodeT
*N
, BBtoBBMap
*ShortCut
) const {
623 typename
BBtoBBMap::iterator e
= ShortCut
->find(N
->getBlock());
625 if (e
== ShortCut
->end())
628 return PDT
->getNode(e
->second
)->getIDom();
632 bool RegionInfoBase
<Tr
>::isTrivialRegion(BlockT
*entry
, BlockT
*exit
) const {
633 assert(entry
&& exit
&& "entry and exit must not be null!");
635 unsigned num_successors
=
636 BlockTraits::child_end(entry
) - BlockTraits::child_begin(entry
);
638 if (num_successors
<= 1 && exit
== *(BlockTraits::child_begin(entry
)))
645 typename
Tr::RegionT
*RegionInfoBase
<Tr
>::createRegion(BlockT
*entry
,
647 assert(entry
&& exit
&& "entry and exit must not be null!");
649 if (isTrivialRegion(entry
, exit
))
653 new RegionT(entry
, exit
, static_cast<RegionInfoT
*>(this), DT
);
654 BBtoRegion
.insert(std::make_pair(entry
, region
));
657 region
->verifyRegion();
659 DEBUG(region
->verifyRegion());
662 updateStatistics(region
);
667 void RegionInfoBase
<Tr
>::findRegionsWithEntry(BlockT
*entry
,
668 BBtoBBMap
*ShortCut
) {
671 DomTreeNodeT
*N
= PDT
->getNode(entry
);
675 RegionT
*lastRegion
= nullptr;
676 BlockT
*lastExit
= entry
;
678 // As only a BasicBlock that postdominates entry can finish a region, walk the
679 // post dominance tree upwards.
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
;
696 // This can never be a region, so stop the search.
697 if (!DT
->dominates(entry
, exit
))
701 // Tried to create regions from entry to lastExit. Next time take a
702 // shortcut from entry to lastExit.
703 if (lastExit
!= entry
)
704 insertShortCut(entry
, lastExit
, ShortCut
);
708 void RegionInfoBase
<Tr
>::scanForRegions(FuncT
&F
, BBtoBBMap
*ShortCut
) {
709 typedef typename
std::add_pointer
<FuncT
>::type FuncPtrT
;
710 BlockT
*entry
= GraphTraits
<FuncPtrT
>::getEntryNode(&F
);
711 DomTreeNodeT
*N
= DT
->getNode(entry
);
713 // Iterate over the dominance tree in post order to start with the small
714 // regions from the bottom of the dominance tree. If the small regions are
715 // detected first, detection of bigger regions is faster, as we can jump
716 // over the small regions.
717 for (po_iterator
<DomTreeNodeT
*> FI
= po_begin(N
), FE
= po_end(N
); FI
!= FE
;
719 findRegionsWithEntry(FI
->getBlock(), ShortCut
);
724 typename
Tr::RegionT
*RegionInfoBase
<Tr
>::getTopMostParent(RegionT
*region
) {
725 while (region
->getParent())
726 region
= region
->getParent();
732 void RegionInfoBase
<Tr
>::buildRegionsTree(DomTreeNodeT
*N
, RegionT
*region
) {
733 BlockT
*BB
= N
->getBlock();
735 // Passed region exit
736 while (BB
== region
->getExit())
737 region
= region
->getParent();
739 typename
BBtoRegionMap::iterator it
= BBtoRegion
.find(BB
);
741 // This basic block is a start block of a region. It is already in the
742 // BBtoRegion relation. Only the child basic blocks have to be updated.
743 if (it
!= BBtoRegion
.end()) {
744 RegionT
*newRegion
= it
->second
;
745 region
->addSubRegion(getTopMostParent(newRegion
));
748 BBtoRegion
[BB
] = region
;
751 for (typename
DomTreeNodeT::iterator CI
= N
->begin(), CE
= N
->end(); CI
!= CE
;
753 buildRegionsTree(*CI
, region
);
759 bool RegionInfoBase
<Tr
>::VerifyRegionInfo
= true;
762 bool RegionInfoBase
<Tr
>::VerifyRegionInfo
= false;
766 typename
Tr::RegionT::PrintStyle RegionInfoBase
<Tr
>::printStyle
=
767 RegionBase
<Tr
>::PrintNone
;
770 void RegionInfoBase
<Tr
>::print(raw_ostream
&OS
) const {
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)
778 void RegionInfoBase
<Tr
>::dump() const { print(dbgs()); }
782 void RegionInfoBase
<Tr
>::releaseMemory() {
785 delete TopLevelRegion
;
786 TopLevelRegion
= nullptr;
790 void RegionInfoBase
<Tr
>::verifyAnalysis() const {
791 TopLevelRegion
->verifyRegionNest();
794 // Region pass manager support.
796 typename
Tr::RegionT
*RegionInfoBase
<Tr
>::getRegionFor(BlockT
*BB
) const {
797 typename
BBtoRegionMap::const_iterator I
= BBtoRegion
.find(BB
);
798 return I
!= BBtoRegion
.end() ? I
->second
: nullptr;
802 void RegionInfoBase
<Tr
>::setRegionFor(BlockT
*BB
, RegionT
*R
) {
807 typename
Tr::RegionT
*RegionInfoBase
<Tr
>::operator[](BlockT
*BB
) const {
808 return getRegionFor(BB
);
812 typename RegionInfoBase
<Tr
>::BlockT
*
813 RegionInfoBase
<Tr
>::getMaxRegionExit(BlockT
*BB
) const {
814 BlockT
*Exit
= nullptr;
817 // Get largest region that starts at BB.
818 RegionT
*R
= getRegionFor(BB
);
819 while (R
&& R
->getParent() && R
->getParent()->getEntry() == BB
)
822 // Get the single exit of BB.
823 if (R
&& R
->getEntry() == BB
)
825 else if (++BlockTraits::child_begin(BB
) == BlockTraits::child_end(BB
))
826 Exit
= *BlockTraits::child_begin(BB
);
827 else // No single exit exists.
830 // Get largest region that starts at Exit.
831 RegionT
*ExitR
= getRegionFor(Exit
);
832 while (ExitR
&& ExitR
->getParent() &&
833 ExitR
->getParent()->getEntry() == Exit
)
834 ExitR
= ExitR
->getParent();
836 for (PredIterTy PI
= InvBlockTraits::child_begin(Exit
),
837 PE
= InvBlockTraits::child_end(Exit
);
839 if (!R
->contains(*PI
) && !ExitR
->contains(*PI
))
843 // This stops infinite cycles.
844 if (DT
->dominates(Exit
, BB
))
854 typename
Tr::RegionT
*RegionInfoBase
<Tr
>::getCommonRegion(RegionT
*A
,
856 assert(A
&& B
&& "One of the Regions is NULL");
861 while (!B
->contains(A
))
868 typename
Tr::RegionT
*
869 RegionInfoBase
<Tr
>::getCommonRegion(SmallVectorImpl
<RegionT
*> &Regions
) const {
870 RegionT
*ret
= Regions
.back();
873 for (RegionT
*R
: Regions
)
874 ret
= getCommonRegion(ret
, R
);
880 typename
Tr::RegionT
*
881 RegionInfoBase
<Tr
>::getCommonRegion(SmallVectorImpl
<BlockT
*> &BBs
) const {
882 RegionT
*ret
= getRegionFor(BBs
.back());
885 for (BlockT
*BB
: BBs
)
886 ret
= getCommonRegion(ret
, getRegionFor(BB
));
892 void RegionInfoBase
<Tr
>::splitBlock(BlockT
*NewBB
, BlockT
*OldBB
) {
893 RegionT
*R
= getRegionFor(OldBB
);
895 setRegionFor(NewBB
, R
);
897 while (R
->getEntry() == OldBB
&& !R
->isTopLevelRegion()) {
898 R
->replaceEntry(NewBB
);
902 setRegionFor(OldBB
, R
);
906 void RegionInfoBase
<Tr
>::calculate(FuncT
&F
) {
907 typedef typename
std::add_pointer
<FuncT
>::type FuncPtrT
;
909 // ShortCut a function where for every BB the exit of the largest region
910 // starting with BB is stored. These regions can be threated as single BBS.
911 // This improves performance on linear CFGs.
914 scanForRegions(F
, &ShortCut
);
915 BlockT
*BB
= GraphTraits
<FuncPtrT
>::getEntryNode(&F
);
916 buildRegionsTree(DT
->getNode(BB
), TopLevelRegion
);
921 } // end namespace llvm