Home | History | Annotate | Download | only in Analysis
      1 //===- RegionInfoImpl.h - SESE region detection analysis --------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 // Detects single entry single exit regions in the control flow graph.
     10 //===----------------------------------------------------------------------===//
     11 
     12 #ifndef LLVM_ANALYSIS_REGIONINFOIMPL_H
     13 #define LLVM_ANALYSIS_REGIONINFOIMPL_H
     14 
     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"
     24 #include <algorithm>
     25 #include <iterator>
     26 #include <set>
     27 
     28 namespace llvm {
     29 
     30 #define DEBUG_TYPE "region"
     31 
     32 //===----------------------------------------------------------------------===//
     33 /// RegionBase Implementation
     34 template <class Tr>
     35 RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit,
     36                            typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
     37                            RegionT *Parent)
     38     : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
     39 
     40 template <class Tr>
     41 RegionBase<Tr>::~RegionBase() {
     42   // Free the cached nodes.
     43   for (typename BBNodeMapT::iterator it = BBNodeMap.begin(),
     44                                      ie = BBNodeMap.end();
     45        it != ie; ++it)
     46     delete it->second;
     47 
     48   // Only clean the cache for this Region. Caches of child Regions will be
     49   // cleaned when the child Regions are deleted.
     50   BBNodeMap.clear();
     51 }
     52 
     53 template <class Tr>
     54 void RegionBase<Tr>::replaceEntry(BlockT *BB) {
     55   this->entry.setPointer(BB);
     56 }
     57 
     58 template <class Tr>
     59 void RegionBase<Tr>::replaceExit(BlockT *BB) {
     60   assert(exit && "No exit to replace!");
     61   exit = BB;
     62 }
     63 
     64 template <class Tr>
     65 void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) {
     66   std::vector<RegionT *> RegionQueue;
     67   BlockT *OldEntry = getEntry();
     68 
     69   RegionQueue.push_back(static_cast<RegionT *>(this));
     70   while (!RegionQueue.empty()) {
     71     RegionT *R = RegionQueue.back();
     72     RegionQueue.pop_back();
     73 
     74     R->replaceEntry(NewEntry);
     75     for (typename RegionT::const_iterator RI = R->begin(), RE = R->end();
     76          RI != RE; ++RI) {
     77       if ((*RI)->getEntry() == OldEntry)
     78         RegionQueue.push_back(RI->get());
     79     }
     80   }
     81 }
     82 
     83 template <class Tr>
     84 void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
     85   std::vector<RegionT *> RegionQueue;
     86   BlockT *OldExit = getExit();
     87 
     88   RegionQueue.push_back(static_cast<RegionT *>(this));
     89   while (!RegionQueue.empty()) {
     90     RegionT *R = RegionQueue.back();
     91     RegionQueue.pop_back();
     92 
     93     R->replaceExit(NewExit);
     94     for (typename RegionT::const_iterator RI = R->begin(), RE = R->end();
     95          RI != RE; ++RI) {
     96       if ((*RI)->getExit() == OldExit)
     97         RegionQueue.push_back(RI->get());
     98     }
     99   }
    100 }
    101 
    102 template <class Tr>
    103 bool RegionBase<Tr>::contains(const BlockT *B) const {
    104   BlockT *BB = const_cast<BlockT *>(B);
    105 
    106   if (!DT->getNode(BB))
    107     return false;
    108 
    109   BlockT *entry = getEntry(), *exit = getExit();
    110 
    111   // Toplevel region.
    112   if (!exit)
    113     return true;
    114 
    115   return (DT->dominates(entry, BB) &&
    116           !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
    117 }
    118 
    119 template <class Tr>
    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.
    124   if (!L)
    125     return getExit() == nullptr;
    126 
    127   if (!contains(L->getHeader()))
    128     return false;
    129 
    130   SmallVector<BlockT *, 8> ExitingBlocks;
    131   L->getExitingBlocks(ExitingBlocks);
    132 
    133   for (BlockT *BB : ExitingBlocks) {
    134     if (!contains(BB))
    135       return false;
    136   }
    137 
    138   return true;
    139 }
    140 
    141 template <class Tr>
    142 typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
    143   if (!contains(L))
    144     return nullptr;
    145 
    146   while (L && contains(L->getParentLoop())) {
    147     L = L->getParentLoop();
    148   }
    149 
    150   return L;
    151 }
    152 
    153 template <class Tr>
    154 typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopInfoT *LI,
    155                                                           BlockT *BB) const {
    156   assert(LI && BB && "LI and BB cannot be null!");
    157   LoopT *L = LI->getLoopFor(BB);
    158   return outermostLoopInRegion(L);
    159 }
    160 
    161 template <class Tr>
    162 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
    163   BlockT *entry = getEntry();
    164   BlockT *Pred;
    165   BlockT *enteringBlock = nullptr;
    166 
    167   for (PredIterTy PI = InvBlockTraits::child_begin(entry),
    168                   PE = InvBlockTraits::child_end(entry);
    169        PI != PE; ++PI) {
    170     Pred = *PI;
    171     if (DT->getNode(Pred) && !contains(Pred)) {
    172       if (enteringBlock)
    173         return nullptr;
    174 
    175       enteringBlock = Pred;
    176     }
    177   }
    178 
    179   return enteringBlock;
    180 }
    181 
    182 template <class Tr>
    183 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
    184   BlockT *exit = getExit();
    185   BlockT *Pred;
    186   BlockT *exitingBlock = nullptr;
    187 
    188   if (!exit)
    189     return nullptr;
    190 
    191   for (PredIterTy PI = InvBlockTraits::child_begin(exit),
    192                   PE = InvBlockTraits::child_end(exit);
    193        PI != PE; ++PI) {
    194     Pred = *PI;
    195     if (contains(Pred)) {
    196       if (exitingBlock)
    197         return nullptr;
    198 
    199       exitingBlock = Pred;
    200     }
    201   }
    202 
    203   return exitingBlock;
    204 }
    205 
    206 template <class Tr>
    207 bool RegionBase<Tr>::isSimple() const {
    208   return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
    209 }
    210 
    211 template <class Tr>
    212 std::string RegionBase<Tr>::getNameStr() const {
    213   std::string exitName;
    214   std::string entryName;
    215 
    216   if (getEntry()->getName().empty()) {
    217     raw_string_ostream OS(entryName);
    218 
    219     getEntry()->printAsOperand(OS, false);
    220   } else
    221     entryName = getEntry()->getName();
    222 
    223   if (getExit()) {
    224     if (getExit()->getName().empty()) {
    225       raw_string_ostream OS(exitName);
    226 
    227       getExit()->printAsOperand(OS, false);
    228     } else
    229       exitName = getExit()->getName();
    230   } else
    231     exitName = "<Function Return>";
    232 
    233   return entryName + " => " + exitName;
    234 }
    235 
    236 template <class Tr>
    237 void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
    238   if (!contains(BB))
    239     llvm_unreachable("Broken region found: enumerated BB not in region!");
    240 
    241   BlockT *entry = getEntry(), *exit = getExit();
    242 
    243   for (SuccIterTy SI = BlockTraits::child_begin(BB),
    244                   SE = BlockTraits::child_end(BB);
    245        SI != SE; ++SI) {
    246     if (!contains(*SI) && exit != *SI)
    247       llvm_unreachable("Broken region found: edges leaving the region must go "
    248                        "to the exit node!");
    249   }
    250 
    251   if (entry != BB) {
    252     for (PredIterTy SI = InvBlockTraits::child_begin(BB),
    253                     SE = InvBlockTraits::child_end(BB);
    254          SI != SE; ++SI) {
    255       if (!contains(*SI))
    256         llvm_unreachable("Broken region found: edges entering the region must "
    257                          "go to the entry node!");
    258     }
    259   }
    260 }
    261 
    262 template <class Tr>
    263 void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
    264   BlockT *exit = getExit();
    265 
    266   visited->insert(BB);
    267 
    268   verifyBBInRegion(BB);
    269 
    270   for (SuccIterTy SI = BlockTraits::child_begin(BB),
    271                   SE = BlockTraits::child_end(BB);
    272        SI != SE; ++SI) {
    273     if (*SI != exit && visited->find(*SI) == visited->end())
    274       verifyWalk(*SI, visited);
    275   }
    276 }
    277 
    278 template <class Tr>
    279 void RegionBase<Tr>::verifyRegion() const {
    280   // Only do verification when user wants to, otherwise this expensive check
    281   // will be invoked by PMDataManager::verifyPreservedAnalysis when
    282   // a regionpass (marked PreservedAll) finish.
    283   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
    284     return;
    285 
    286   std::set<BlockT *> visited;
    287   verifyWalk(getEntry(), &visited);
    288 }
    289 
    290 template <class Tr>
    291 void RegionBase<Tr>::verifyRegionNest() const {
    292   for (typename RegionT::const_iterator RI = begin(), RE = end(); RI != RE;
    293        ++RI)
    294     (*RI)->verifyRegionNest();
    295 
    296   verifyRegion();
    297 }
    298 
    299 template <class Tr>
    300 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
    301   return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
    302 }
    303 
    304 template <class Tr>
    305 typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
    306   return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
    307 }
    308 
    309 template <class Tr>
    310 typename RegionBase<Tr>::const_element_iterator
    311 RegionBase<Tr>::element_begin() const {
    312   return GraphTraits<const RegionT *>::nodes_begin(
    313       static_cast<const RegionT *>(this));
    314 }
    315 
    316 template <class Tr>
    317 typename RegionBase<Tr>::const_element_iterator
    318 RegionBase<Tr>::element_end() const {
    319   return GraphTraits<const RegionT *>::nodes_end(
    320       static_cast<const RegionT *>(this));
    321 }
    322 
    323 template <class Tr>
    324 typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
    325   typedef typename Tr::RegionT RegionT;
    326   RegionT *R = RI->getRegionFor(BB);
    327 
    328   if (!R || R == this)
    329     return nullptr;
    330 
    331   // If we pass the BB out of this region, that means our code is broken.
    332   assert(contains(R) && "BB not in current region!");
    333 
    334   while (contains(R->getParent()) && R->getParent() != this)
    335     R = R->getParent();
    336 
    337   if (R->getEntry() != BB)
    338     return nullptr;
    339 
    340   return R;
    341 }
    342 
    343 template <class Tr>
    344 typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
    345   assert(contains(BB) && "Can get BB node out of this region!");
    346 
    347   typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
    348 
    349   if (at != BBNodeMap.end())
    350     return at->second;
    351 
    352   auto Deconst = const_cast<RegionBase<Tr> *>(this);
    353   RegionNodeT *NewNode = new RegionNodeT(static_cast<RegionT *>(Deconst), BB);
    354   BBNodeMap.insert(std::make_pair(BB, NewNode));
    355   return NewNode;
    356 }
    357 
    358 template <class Tr>
    359 typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
    360   assert(contains(BB) && "Can get BB node out of this region!");
    361   if (RegionT *Child = getSubRegionNode(BB))
    362     return Child->getNode();
    363 
    364   return getBBNode(BB);
    365 }
    366 
    367 template <class Tr>
    368 void RegionBase<Tr>::transferChildrenTo(RegionT *To) {
    369   for (iterator I = begin(), E = end(); I != E; ++I) {
    370     (*I)->parent = To;
    371     To->children.push_back(std::move(*I));
    372   }
    373   children.clear();
    374 }
    375 
    376 template <class Tr>
    377 void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
    378   assert(!SubRegion->parent && "SubRegion already has a parent!");
    379   assert(std::find_if(begin(), end(), [&](const std::unique_ptr<RegionT> &R) {
    380            return R.get() == SubRegion;
    381          }) == children.end() &&
    382          "Subregion already exists!");
    383 
    384   SubRegion->parent = static_cast<RegionT *>(this);
    385   children.push_back(std::unique_ptr<RegionT>(SubRegion));
    386 
    387   if (!moveChildren)
    388     return;
    389 
    390   assert(SubRegion->children.empty() &&
    391          "SubRegions that contain children are not supported");
    392 
    393   for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) {
    394     if (!(*I)->isSubRegion()) {
    395       BlockT *BB = (*I)->template getNodeAs<BlockT>();
    396 
    397       if (SubRegion->contains(BB))
    398         RI->setRegionFor(BB, SubRegion);
    399     }
    400   }
    401 
    402   std::vector<std::unique_ptr<RegionT>> Keep;
    403   for (iterator I = begin(), E = end(); I != E; ++I) {
    404     if (SubRegion->contains(I->get()) && I->get() != SubRegion) {
    405       (*I)->parent = SubRegion;
    406       SubRegion->children.push_back(std::move(*I));
    407     } else
    408       Keep.push_back(std::move(*I));
    409   }
    410 
    411   children.clear();
    412   children.insert(
    413       children.begin(),
    414       std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
    415       std::move_iterator<typename RegionSet::iterator>(Keep.end()));
    416 }
    417 
    418 template <class Tr>
    419 typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
    420   assert(Child->parent == this && "Child is not a child of this region!");
    421   Child->parent = nullptr;
    422   typename RegionSet::iterator I = std::find_if(
    423       children.begin(), children.end(),
    424       [&](const std::unique_ptr<RegionT> &R) { return R.get() == Child; });
    425   assert(I != children.end() && "Region does not exit. Unable to remove.");
    426   children.erase(children.begin() + (I - begin()));
    427   return Child;
    428 }
    429 
    430 template <class Tr>
    431 unsigned RegionBase<Tr>::getDepth() const {
    432   unsigned Depth = 0;
    433 
    434   for (RegionT *R = getParent(); R != nullptr; R = R->getParent())
    435     ++Depth;
    436 
    437   return Depth;
    438 }
    439 
    440 template <class Tr>
    441 typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
    442   unsigned NumSuccessors = Tr::getNumSuccessors(exit);
    443 
    444   if (NumSuccessors == 0)
    445     return nullptr;
    446 
    447   RegionT *R = RI->getRegionFor(exit);
    448 
    449   if (R->getEntry() != exit) {
    450     for (PredIterTy PI = InvBlockTraits::child_begin(getExit()),
    451                     PE = InvBlockTraits::child_end(getExit());
    452          PI != PE; ++PI)
    453       if (!contains(*PI))
    454         return nullptr;
    455     if (Tr::getNumSuccessors(exit) == 1)
    456       return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
    457     return nullptr;
    458   }
    459 
    460   while (R->getParent() && R->getParent()->getEntry() == exit)
    461     R = R->getParent();
    462 
    463   for (PredIterTy PI = InvBlockTraits::child_begin(getExit()),
    464                   PE = InvBlockTraits::child_end(getExit());
    465        PI != PE; ++PI) {
    466     if (!(contains(*PI) || R->contains(*PI)))
    467       return nullptr;
    468   }
    469 
    470   return new RegionT(getEntry(), R->getExit(), RI, DT);
    471 }
    472 
    473 template <class Tr>
    474 void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
    475                            PrintStyle Style) const {
    476   if (print_tree)
    477     OS.indent(level * 2) << '[' << level << "] " << getNameStr();
    478   else
    479     OS.indent(level * 2) << getNameStr();
    480 
    481   OS << '\n';
    482 
    483   if (Style != PrintNone) {
    484     OS.indent(level * 2) << "{\n";
    485     OS.indent(level * 2 + 2);
    486 
    487     if (Style == PrintBB) {
    488       for (const auto *BB : blocks())
    489         OS << BB->getName() << ", "; // TODO: remove the last ","
    490     } else if (Style == PrintRN) {
    491       for (const_element_iterator I = element_begin(), E = element_end();
    492            I != E; ++I) {
    493         OS << **I << ", "; // TODO: remove the last ",
    494       }
    495     }
    496 
    497     OS << '\n';
    498   }
    499 
    500   if (print_tree) {
    501     for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
    502       (*RI)->print(OS, print_tree, level + 1, Style);
    503   }
    504 
    505   if (Style != PrintNone)
    506     OS.indent(level * 2) << "} \n";
    507 }
    508 
    509 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    510 template <class Tr>
    511 void RegionBase<Tr>::dump() const {
    512   print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
    513 }
    514 #endif
    515 
    516 template <class Tr>
    517 void RegionBase<Tr>::clearNodeCache() {
    518   // Free the cached nodes.
    519   for (typename BBNodeMapT::iterator I = BBNodeMap.begin(),
    520                                      IE = BBNodeMap.end();
    521        I != IE; ++I)
    522     delete I->second;
    523 
    524   BBNodeMap.clear();
    525   for (typename RegionT::iterator RI = begin(), RE = end(); RI != RE; ++RI)
    526     (*RI)->clearNodeCache();
    527 }
    528 
    529 //===----------------------------------------------------------------------===//
    530 // RegionInfoBase implementation
    531 //
    532 
    533 template <class Tr>
    534 RegionInfoBase<Tr>::RegionInfoBase()
    535     : TopLevelRegion(nullptr) {}
    536 
    537 template <class Tr>
    538 RegionInfoBase<Tr>::~RegionInfoBase() {
    539   releaseMemory();
    540 }
    541 
    542 template <class Tr>
    543 void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
    544   assert(R && "Re must be non-null");
    545   for (auto I = R->element_begin(), E = R->element_end(); I != E; ++I) {
    546     if (I->isSubRegion()) {
    547       const RegionT *SR = I->template getNodeAs<RegionT>();
    548       verifyBBMap(SR);
    549     } else {
    550       BlockT *BB = I->template getNodeAs<BlockT>();
    551       if (getRegionFor(BB) != R)
    552         llvm_unreachable("BB map does not match region nesting");
    553     }
    554   }
    555 }
    556 
    557 template <class Tr>
    558 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
    559                                              BlockT *exit) const {
    560   for (PredIterTy PI = InvBlockTraits::child_begin(BB),
    561                   PE = InvBlockTraits::child_end(BB);
    562        PI != PE; ++PI) {
    563     BlockT *P = *PI;
    564     if (DT->dominates(entry, P) && !DT->dominates(exit, P))
    565       return false;
    566   }
    567 
    568   return true;
    569 }
    570 
    571 template <class Tr>
    572 bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
    573   assert(entry && exit && "entry and exit must not be null!");
    574   typedef typename DomFrontierT::DomSetType DST;
    575 
    576   DST *entrySuccs = &DF->find(entry)->second;
    577 
    578   // Exit is the header of a loop that contains the entry. In this case,
    579   // the dominance frontier must only contain the exit.
    580   if (!DT->dominates(entry, exit)) {
    581     for (typename DST::iterator SI = entrySuccs->begin(),
    582                                 SE = entrySuccs->end();
    583          SI != SE; ++SI) {
    584       if (*SI != exit && *SI != entry)
    585         return false;
    586     }
    587 
    588     return true;
    589   }
    590 
    591   DST *exitSuccs = &DF->find(exit)->second;
    592 
    593   // Do not allow edges leaving the region.
    594   for (typename DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
    595        SI != SE; ++SI) {
    596     if (*SI == exit || *SI == entry)
    597       continue;
    598     if (exitSuccs->find(*SI) == exitSuccs->end())
    599       return false;
    600     if (!isCommonDomFrontier(*SI, entry, exit))
    601       return false;
    602   }
    603 
    604   // Do not allow edges pointing into the region.
    605   for (typename DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end();
    606        SI != SE; ++SI) {
    607     if (DT->properlyDominates(entry, *SI) && *SI != exit)
    608       return false;
    609   }
    610 
    611   return true;
    612 }
    613 
    614 template <class Tr>
    615 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
    616                                         BBtoBBMap *ShortCut) const {
    617   assert(entry && exit && "entry and exit must not be null!");
    618 
    619   typename BBtoBBMap::iterator e = ShortCut->find(exit);
    620 
    621   if (e == ShortCut->end())
    622     // No further region at exit available.
    623     (*ShortCut)[entry] = exit;
    624   else {
    625     // We found a region e that starts at exit. Therefore (entry, e->second)
    626     // is also a region, that is larger than (entry, exit). Insert the
    627     // larger one.
    628     BlockT *BB = e->second;
    629     (*ShortCut)[entry] = BB;
    630   }
    631 }
    632 
    633 template <class Tr>
    634 typename Tr::DomTreeNodeT *
    635 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
    636   typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
    637 
    638   if (e == ShortCut->end())
    639     return N->getIDom();
    640 
    641   return PDT->getNode(e->second)->getIDom();
    642 }
    643 
    644 template <class Tr>
    645 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
    646   assert(entry && exit && "entry and exit must not be null!");
    647 
    648   unsigned num_successors =
    649       BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
    650 
    651   if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
    652     return true;
    653 
    654   return false;
    655 }
    656 
    657 template <class Tr>
    658 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
    659                                                        BlockT *exit) {
    660   assert(entry && exit && "entry and exit must not be null!");
    661 
    662   if (isTrivialRegion(entry, exit))
    663     return nullptr;
    664 
    665   RegionT *region =
    666       new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
    667   BBtoRegion.insert(std::make_pair(entry, region));
    668 
    669 #ifdef XDEBUG
    670   region->verifyRegion();
    671 #else
    672   DEBUG(region->verifyRegion());
    673 #endif
    674 
    675   updateStatistics(region);
    676   return region;
    677 }
    678 
    679 template <class Tr>
    680 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
    681                                               BBtoBBMap *ShortCut) {
    682   assert(entry);
    683 
    684   DomTreeNodeT *N = PDT->getNode(entry);
    685   if (!N)
    686     return;
    687 
    688   RegionT *lastRegion = nullptr;
    689   BlockT *lastExit = entry;
    690 
    691   // As only a BasicBlock that postdominates entry can finish a region, walk the
    692   // post dominance tree upwards.
    693   while ((N = getNextPostDom(N, ShortCut))) {
    694     BlockT *exit = N->getBlock();
    695 
    696     if (!exit)
    697       break;
    698 
    699     if (isRegion(entry, exit)) {
    700       RegionT *newRegion = createRegion(entry, exit);
    701 
    702       if (lastRegion)
    703         newRegion->addSubRegion(lastRegion);
    704 
    705       lastRegion = newRegion;
    706       lastExit = exit;
    707     }
    708 
    709     // This can never be a region, so stop the search.
    710     if (!DT->dominates(entry, exit))
    711       break;
    712   }
    713 
    714   // Tried to create regions from entry to lastExit.  Next time take a
    715   // shortcut from entry to lastExit.
    716   if (lastExit != entry)
    717     insertShortCut(entry, lastExit, ShortCut);
    718 }
    719 
    720 template <class Tr>
    721 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
    722   typedef typename std::add_pointer<FuncT>::type FuncPtrT;
    723   BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
    724   DomTreeNodeT *N = DT->getNode(entry);
    725 
    726   // Iterate over the dominance tree in post order to start with the small
    727   // regions from the bottom of the dominance tree.  If the small regions are
    728   // detected first, detection of bigger regions is faster, as we can jump
    729   // over the small regions.
    730   for (auto DomNode : post_order(N))
    731     findRegionsWithEntry(DomNode->getBlock(), ShortCut);
    732 }
    733 
    734 template <class Tr>
    735 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
    736   while (region->getParent())
    737     region = region->getParent();
    738 
    739   return region;
    740 }
    741 
    742 template <class Tr>
    743 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
    744   BlockT *BB = N->getBlock();
    745 
    746   // Passed region exit
    747   while (BB == region->getExit())
    748     region = region->getParent();
    749 
    750   typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
    751 
    752   // This basic block is a start block of a region. It is already in the
    753   // BBtoRegion relation. Only the child basic blocks have to be updated.
    754   if (it != BBtoRegion.end()) {
    755     RegionT *newRegion = it->second;
    756     region->addSubRegion(getTopMostParent(newRegion));
    757     region = newRegion;
    758   } else {
    759     BBtoRegion[BB] = region;
    760   }
    761 
    762   for (typename DomTreeNodeT::iterator CI = N->begin(), CE = N->end(); CI != CE;
    763        ++CI) {
    764     buildRegionsTree(*CI, region);
    765   }
    766 }
    767 
    768 #ifdef XDEBUG
    769 template <class Tr>
    770 bool RegionInfoBase<Tr>::VerifyRegionInfo = true;
    771 #else
    772 template <class Tr>
    773 bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
    774 #endif
    775 
    776 template <class Tr>
    777 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
    778     RegionBase<Tr>::PrintNone;
    779 
    780 template <class Tr>
    781 void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
    782   OS << "Region tree:\n";
    783   TopLevelRegion->print(OS, true, 0, printStyle);
    784   OS << "End region tree\n";
    785 }
    786 
    787 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    788 template <class Tr>
    789 void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
    790 #endif
    791 
    792 template <class Tr>
    793 void RegionInfoBase<Tr>::releaseMemory() {
    794   BBtoRegion.clear();
    795   if (TopLevelRegion)
    796     delete TopLevelRegion;
    797   TopLevelRegion = nullptr;
    798 }
    799 
    800 template <class Tr>
    801 void RegionInfoBase<Tr>::verifyAnalysis() const {
    802   // Do only verify regions if explicitely activated using XDEBUG or
    803   // -verify-region-info
    804   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
    805     return;
    806 
    807   TopLevelRegion->verifyRegionNest();
    808 
    809   verifyBBMap(TopLevelRegion);
    810 }
    811 
    812 // Region pass manager support.
    813 template <class Tr>
    814 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
    815   typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
    816   return I != BBtoRegion.end() ? I->second : nullptr;
    817 }
    818 
    819 template <class Tr>
    820 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
    821   BBtoRegion[BB] = R;
    822 }
    823 
    824 template <class Tr>
    825 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
    826   return getRegionFor(BB);
    827 }
    828 
    829 template <class Tr>
    830 typename RegionInfoBase<Tr>::BlockT *
    831 RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const {
    832   BlockT *Exit = nullptr;
    833 
    834   while (true) {
    835     // Get largest region that starts at BB.
    836     RegionT *R = getRegionFor(BB);
    837     while (R && R->getParent() && R->getParent()->getEntry() == BB)
    838       R = R->getParent();
    839 
    840     // Get the single exit of BB.
    841     if (R && R->getEntry() == BB)
    842       Exit = R->getExit();
    843     else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
    844       Exit = *BlockTraits::child_begin(BB);
    845     else // No single exit exists.
    846       return Exit;
    847 
    848     // Get largest region that starts at Exit.
    849     RegionT *ExitR = getRegionFor(Exit);
    850     while (ExitR && ExitR->getParent() &&
    851            ExitR->getParent()->getEntry() == Exit)
    852       ExitR = ExitR->getParent();
    853 
    854     for (PredIterTy PI = InvBlockTraits::child_begin(Exit),
    855                     PE = InvBlockTraits::child_end(Exit);
    856          PI != PE; ++PI) {
    857       if (!R->contains(*PI) && !ExitR->contains(*PI))
    858         break;
    859     }
    860 
    861     // This stops infinite cycles.
    862     if (DT->dominates(Exit, BB))
    863       break;
    864 
    865     BB = Exit;
    866   }
    867 
    868   return Exit;
    869 }
    870 
    871 template <class Tr>
    872 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
    873                                                           RegionT *B) const {
    874   assert(A && B && "One of the Regions is NULL");
    875 
    876   if (A->contains(B))
    877     return A;
    878 
    879   while (!B->contains(A))
    880     B = B->getParent();
    881 
    882   return B;
    883 }
    884 
    885 template <class Tr>
    886 typename Tr::RegionT *
    887 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const {
    888   RegionT *ret = Regions.back();
    889   Regions.pop_back();
    890 
    891   for (RegionT *R : Regions)
    892     ret = getCommonRegion(ret, R);
    893 
    894   return ret;
    895 }
    896 
    897 template <class Tr>
    898 typename Tr::RegionT *
    899 RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const {
    900   RegionT *ret = getRegionFor(BBs.back());
    901   BBs.pop_back();
    902 
    903   for (BlockT *BB : BBs)
    904     ret = getCommonRegion(ret, getRegionFor(BB));
    905 
    906   return ret;
    907 }
    908 
    909 template <class Tr>
    910 void RegionInfoBase<Tr>::calculate(FuncT &F) {
    911   typedef typename std::add_pointer<FuncT>::type FuncPtrT;
    912 
    913   // ShortCut a function where for every BB the exit of the largest region
    914   // starting with BB is stored. These regions can be threated as single BBS.
    915   // This improves performance on linear CFGs.
    916   BBtoBBMap ShortCut;
    917 
    918   scanForRegions(F, &ShortCut);
    919   BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
    920   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
    921 }
    922 
    923 #undef DEBUG_TYPE
    924 
    925 } // end namespace llvm
    926 
    927 #endif
    928