LLVM API Documentation

RegionInfo.cpp
Go to the documentation of this file.
00001 //===- RegionInfo.cpp - SESE region detection analysis --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 // Detects single entry single exit regions in the control flow graph.
00010 //===----------------------------------------------------------------------===//
00011 
00012 #include "llvm/Analysis/RegionInfo.h"
00013 #include "llvm/ADT/PostOrderIterator.h"
00014 #include "llvm/ADT/Statistic.h"
00015 #include "llvm/Analysis/LoopInfo.h"
00016 #include "llvm/Analysis/RegionIterator.h"
00017 #include "llvm/Support/CommandLine.h"
00018 #include "llvm/Support/Debug.h"
00019 #include "llvm/Support/ErrorHandling.h"
00020 #include <algorithm>
00021 #include <iterator>
00022 #include <set>
00023 
00024 using namespace llvm;
00025 
00026 #define DEBUG_TYPE "region"
00027 
00028 // Always verify if expensive checking is enabled.
00029 #ifdef XDEBUG
00030 static bool VerifyRegionInfo = true;
00031 #else
00032 static bool VerifyRegionInfo = false;
00033 #endif
00034 
00035 static cl::opt<bool,true>
00036 VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo),
00037                 cl::desc("Verify region info (time consuming)"));
00038 
00039 STATISTIC(numRegions,       "The # of regions");
00040 STATISTIC(numSimpleRegions, "The # of simple regions");
00041 
00042 static cl::opt<enum Region::PrintStyle> printStyle("print-region-style",
00043   cl::Hidden,
00044   cl::desc("style of printing regions"),
00045   cl::values(
00046     clEnumValN(Region::PrintNone, "none",  "print no details"),
00047     clEnumValN(Region::PrintBB, "bb",
00048                "print regions in detail with block_iterator"),
00049     clEnumValN(Region::PrintRN, "rn",
00050                "print regions in detail with element_iterator"),
00051     clEnumValEnd));
00052 //===----------------------------------------------------------------------===//
00053 /// Region Implementation
00054 Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo,
00055                DominatorTree *dt, Region *Parent)
00056                : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
00057 
00058 Region::~Region() {
00059   // Free the cached nodes.
00060   for (BBNodeMapT::iterator it = BBNodeMap.begin(),
00061          ie = BBNodeMap.end(); it != ie; ++it)
00062     delete it->second;
00063 
00064   // Only clean the cache for this Region. Caches of child Regions will be
00065   // cleaned when the child Regions are deleted.
00066   BBNodeMap.clear();
00067 }
00068 
00069 void Region::replaceEntry(BasicBlock *BB) {
00070   entry.setPointer(BB);
00071 }
00072 
00073 void Region::replaceExit(BasicBlock *BB) {
00074   assert(exit && "No exit to replace!");
00075   exit = BB;
00076 }
00077 
00078 void Region::replaceEntryRecursive(BasicBlock *NewEntry) {
00079   std::vector<Region *> RegionQueue;
00080   BasicBlock *OldEntry = getEntry();
00081 
00082   RegionQueue.push_back(this);
00083   while (!RegionQueue.empty()) {
00084     Region *R = RegionQueue.back();
00085     RegionQueue.pop_back();
00086 
00087     R->replaceEntry(NewEntry);
00088     for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI)
00089       if ((*RI)->getEntry() == OldEntry)
00090         RegionQueue.push_back(RI->get());
00091   }
00092 }
00093 
00094 void Region::replaceExitRecursive(BasicBlock *NewExit) {
00095   std::vector<Region *> RegionQueue;
00096   BasicBlock *OldExit = getExit();
00097 
00098   RegionQueue.push_back(this);
00099   while (!RegionQueue.empty()) {
00100     Region *R = RegionQueue.back();
00101     RegionQueue.pop_back();
00102 
00103     R->replaceExit(NewExit);
00104     for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI)
00105       if ((*RI)->getExit() == OldExit)
00106         RegionQueue.push_back(RI->get());
00107   }
00108 }
00109 
00110 bool Region::contains(const BasicBlock *B) const {
00111   BasicBlock *BB = const_cast<BasicBlock*>(B);
00112 
00113   if (!DT->getNode(BB))
00114     return false;
00115 
00116   BasicBlock *entry = getEntry(), *exit = getExit();
00117 
00118   // Toplevel region.
00119   if (!exit)
00120     return true;
00121 
00122   return (DT->dominates(entry, BB)
00123     && !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
00124 }
00125 
00126 bool Region::contains(const Loop *L) const {
00127   // BBs that are not part of any loop are element of the Loop
00128   // described by the NULL pointer. This loop is not part of any region,
00129   // except if the region describes the whole function.
00130   if (!L)
00131     return getExit() == nullptr;
00132 
00133   if (!contains(L->getHeader()))
00134     return false;
00135 
00136   SmallVector<BasicBlock *, 8> ExitingBlocks;
00137   L->getExitingBlocks(ExitingBlocks);
00138 
00139   for (SmallVectorImpl<BasicBlock*>::iterator BI = ExitingBlocks.begin(),
00140        BE = ExitingBlocks.end(); BI != BE; ++BI)
00141     if (!contains(*BI))
00142       return false;
00143 
00144   return true;
00145 }
00146 
00147 Loop *Region::outermostLoopInRegion(Loop *L) const {
00148   if (!contains(L))
00149     return nullptr;
00150 
00151   while (L && contains(L->getParentLoop())) {
00152     L = L->getParentLoop();
00153   }
00154 
00155   return L;
00156 }
00157 
00158 Loop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const {
00159   assert(LI && BB && "LI and BB cannot be null!");
00160   Loop *L = LI->getLoopFor(BB);
00161   return outermostLoopInRegion(L);
00162 }
00163 
00164 BasicBlock *Region::getEnteringBlock() const {
00165   BasicBlock *entry = getEntry();
00166   BasicBlock *Pred;
00167   BasicBlock *enteringBlock = nullptr;
00168 
00169   for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
00170        ++PI) {
00171     Pred = *PI;
00172     if (DT->getNode(Pred) && !contains(Pred)) {
00173       if (enteringBlock)
00174         return nullptr;
00175 
00176       enteringBlock = Pred;
00177     }
00178   }
00179 
00180   return enteringBlock;
00181 }
00182 
00183 BasicBlock *Region::getExitingBlock() const {
00184   BasicBlock *exit = getExit();
00185   BasicBlock *Pred;
00186   BasicBlock *exitingBlock = nullptr;
00187 
00188   if (!exit)
00189     return nullptr;
00190 
00191   for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE;
00192        ++PI) {
00193     Pred = *PI;
00194     if (contains(Pred)) {
00195       if (exitingBlock)
00196         return nullptr;
00197 
00198       exitingBlock = Pred;
00199     }
00200   }
00201 
00202   return exitingBlock;
00203 }
00204 
00205 bool Region::isSimple() const {
00206   return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
00207 }
00208 
00209 std::string Region::getNameStr() const {
00210   std::string exitName;
00211   std::string entryName;
00212 
00213   if (getEntry()->getName().empty()) {
00214     raw_string_ostream OS(entryName);
00215 
00216     getEntry()->printAsOperand(OS, false);
00217   } else
00218     entryName = getEntry()->getName();
00219 
00220   if (getExit()) {
00221     if (getExit()->getName().empty()) {
00222       raw_string_ostream OS(exitName);
00223 
00224       getExit()->printAsOperand(OS, false);
00225     } else
00226       exitName = getExit()->getName();
00227   } else
00228     exitName = "<Function Return>";
00229 
00230   return entryName + " => " + exitName;
00231 }
00232 
00233 void Region::verifyBBInRegion(BasicBlock *BB) const {
00234   if (!contains(BB))
00235     llvm_unreachable("Broken region found!");
00236 
00237   BasicBlock *entry = getEntry(), *exit = getExit();
00238 
00239   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00240     if (!contains(*SI) && exit != *SI)
00241       llvm_unreachable("Broken region found!");
00242 
00243   if (entry != BB)
00244     for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI)
00245       if (!contains(*SI))
00246         llvm_unreachable("Broken region found!");
00247 }
00248 
00249 void Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const {
00250   BasicBlock *exit = getExit();
00251 
00252   visited->insert(BB);
00253 
00254   verifyBBInRegion(BB);
00255 
00256   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
00257     if (*SI != exit && visited->find(*SI) == visited->end())
00258         verifyWalk(*SI, visited);
00259 }
00260 
00261 void Region::verifyRegion() const {
00262   // Only do verification when user wants to, otherwise this expensive
00263   // check will be invoked by PassManager.
00264   if (!VerifyRegionInfo) return;
00265 
00266   std::set<BasicBlock*> visited;
00267   verifyWalk(getEntry(), &visited);
00268 }
00269 
00270 void Region::verifyRegionNest() const {
00271   for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
00272     (*RI)->verifyRegionNest();
00273 
00274   verifyRegion();
00275 }
00276 
00277 Region::element_iterator Region::element_begin() {
00278   return GraphTraits<Region*>::nodes_begin(this);
00279 }
00280 
00281 Region::element_iterator Region::element_end() {
00282   return GraphTraits<Region*>::nodes_end(this);
00283 }
00284 
00285 Region::const_element_iterator Region::element_begin() const {
00286   return GraphTraits<const Region*>::nodes_begin(this);
00287 }
00288 
00289 Region::const_element_iterator Region::element_end() const {
00290   return GraphTraits<const Region*>::nodes_end(this);
00291 }
00292 
00293 Region* Region::getSubRegionNode(BasicBlock *BB) const {
00294   Region *R = RI->getRegionFor(BB);
00295 
00296   if (!R || R == this)
00297     return nullptr;
00298 
00299   // If we pass the BB out of this region, that means our code is broken.
00300   assert(contains(R) && "BB not in current region!");
00301 
00302   while (contains(R->getParent()) && R->getParent() != this)
00303     R = R->getParent();
00304 
00305   if (R->getEntry() != BB)
00306     return nullptr;
00307 
00308   return R;
00309 }
00310 
00311 RegionNode* Region::getBBNode(BasicBlock *BB) const {
00312   assert(contains(BB) && "Can get BB node out of this region!");
00313 
00314   BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
00315 
00316   if (at != BBNodeMap.end())
00317     return at->second;
00318 
00319   RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB);
00320   BBNodeMap.insert(std::make_pair(BB, NewNode));
00321   return NewNode;
00322 }
00323 
00324 RegionNode* Region::getNode(BasicBlock *BB) const {
00325   assert(contains(BB) && "Can get BB node out of this region!");
00326   if (Region* Child = getSubRegionNode(BB))
00327     return Child->getNode();
00328 
00329   return getBBNode(BB);
00330 }
00331 
00332 void Region::transferChildrenTo(Region *To) {
00333   for (iterator I = begin(), E = end(); I != E; ++I) {
00334     (*I)->parent = To;
00335     To->children.push_back(std::move(*I));
00336   }
00337   children.clear();
00338 }
00339 
00340 void Region::addSubRegion(Region *SubRegion, bool moveChildren) {
00341   assert(!SubRegion->parent && "SubRegion already has a parent!");
00342   assert(std::find_if(begin(), end(), [&](const std::unique_ptr<Region> &R) {
00343            return R.get() == SubRegion;
00344          }) == children.end() &&
00345          "Subregion already exists!");
00346 
00347   SubRegion->parent = this;
00348   children.push_back(std::unique_ptr<Region>(SubRegion));
00349 
00350   if (!moveChildren)
00351     return;
00352 
00353   assert(SubRegion->children.size() == 0
00354          && "SubRegions that contain children are not supported");
00355 
00356   for (element_iterator I = element_begin(), E = element_end(); I != E; ++I)
00357     if (!(*I)->isSubRegion()) {
00358       BasicBlock *BB = (*I)->getNodeAs<BasicBlock>();
00359 
00360       if (SubRegion->contains(BB))
00361         RI->setRegionFor(BB, SubRegion);
00362     }
00363 
00364   std::vector<std::unique_ptr<Region>> Keep;
00365   for (iterator I = begin(), E = end(); I != E; ++I)
00366     if (SubRegion->contains(I->get()) && I->get() != SubRegion) {
00367       (*I)->parent = SubRegion;
00368       SubRegion->children.push_back(std::move(*I));
00369     } else
00370       Keep.push_back(std::move(*I));
00371 
00372   children.clear();
00373   children.insert(children.begin(),
00374                   std::move_iterator<RegionSet::iterator>(Keep.begin()),
00375                   std::move_iterator<RegionSet::iterator>(Keep.end()));
00376 }
00377 
00378 
00379 Region *Region::removeSubRegion(Region *Child) {
00380   assert(Child->parent == this && "Child is not a child of this region!");
00381   Child->parent = nullptr;
00382   RegionSet::iterator I = std::find_if(
00383       children.begin(), children.end(),
00384       [&](const std::unique_ptr<Region> &R) { return R.get() == Child; });
00385   assert(I != children.end() && "Region does not exit. Unable to remove.");
00386   children.erase(children.begin()+(I-begin()));
00387   return Child;
00388 }
00389 
00390 unsigned Region::getDepth() const {
00391   unsigned Depth = 0;
00392 
00393   for (Region *R = parent; R != nullptr; R = R->parent)
00394     ++Depth;
00395 
00396   return Depth;
00397 }
00398 
00399 Region *Region::getExpandedRegion() const {
00400   unsigned NumSuccessors = exit->getTerminator()->getNumSuccessors();
00401 
00402   if (NumSuccessors == 0)
00403     return nullptr;
00404 
00405   for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit());
00406        PI != PE; ++PI)
00407     if (!DT->dominates(getEntry(), *PI))
00408       return nullptr;
00409 
00410   Region *R = RI->getRegionFor(exit);
00411 
00412   if (R->getEntry() != exit) {
00413     if (exit->getTerminator()->getNumSuccessors() == 1)
00414       return new Region(getEntry(), *succ_begin(exit), RI, DT);
00415     else
00416       return nullptr;
00417   }
00418 
00419   while (R->getParent() && R->getParent()->getEntry() == exit)
00420     R = R->getParent();
00421 
00422   if (!DT->dominates(getEntry(), R->getExit()))
00423     for (pred_iterator PI = pred_begin(getExit()), PE = pred_end(getExit());
00424          PI != PE; ++PI)
00425     if (!DT->dominates(R->getExit(), *PI))
00426       return nullptr;
00427 
00428   return new Region(getEntry(), R->getExit(), RI, DT);
00429 }
00430 
00431 void Region::print(raw_ostream &OS, bool print_tree, unsigned level,
00432                    enum PrintStyle Style) const {
00433   if (print_tree)
00434     OS.indent(level*2) << "[" << level << "] " << getNameStr();
00435   else
00436     OS.indent(level*2) << getNameStr();
00437 
00438   OS << "\n";
00439 
00440 
00441   if (Style != PrintNone) {
00442     OS.indent(level*2) << "{\n";
00443     OS.indent(level*2 + 2);
00444 
00445     if (Style == PrintBB) {
00446       for (const auto &BB : blocks())
00447         OS << BB->getName() << ", "; // TODO: remove the last ","
00448     } else if (Style == PrintRN) {
00449       for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I)
00450         OS << **I << ", "; // TODO: remove the last ",
00451     }
00452 
00453     OS << "\n";
00454   }
00455 
00456   if (print_tree)
00457     for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
00458       (*RI)->print(OS, print_tree, level+1, Style);
00459 
00460   if (Style != PrintNone)
00461     OS.indent(level*2) << "} \n";
00462 }
00463 
00464 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00465 void Region::dump() const {
00466   print(dbgs(), true, getDepth(), printStyle.getValue());
00467 }
00468 #endif
00469 
00470 void Region::clearNodeCache() {
00471   // Free the cached nodes.
00472   for (BBNodeMapT::iterator I = BBNodeMap.begin(),
00473        IE = BBNodeMap.end(); I != IE; ++I)
00474     delete I->second;
00475 
00476   BBNodeMap.clear();
00477   for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI)
00478     (*RI)->clearNodeCache();
00479 }
00480 
00481 //===----------------------------------------------------------------------===//
00482 // RegionInfo implementation
00483 //
00484 
00485 bool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry,
00486                                      BasicBlock *exit) const {
00487   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
00488     BasicBlock *P = *PI;
00489     if (DT->dominates(entry, P) && !DT->dominates(exit, P))
00490       return false;
00491   }
00492   return true;
00493 }
00494 
00495 bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const {
00496   assert(entry && exit && "entry and exit must not be null!");
00497   typedef DominanceFrontier::DomSetType DST;
00498 
00499   DST *entrySuccs = &DF->find(entry)->second;
00500 
00501   // Exit is the header of a loop that contains the entry. In this case,
00502   // the dominance frontier must only contain the exit.
00503   if (!DT->dominates(entry, exit)) {
00504     for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
00505          SI != SE; ++SI)
00506       if (*SI != exit && *SI != entry)
00507         return false;
00508 
00509     return true;
00510   }
00511 
00512   DST *exitSuccs = &DF->find(exit)->second;
00513 
00514   // Do not allow edges leaving the region.
00515   for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
00516        SI != SE; ++SI) {
00517     if (*SI == exit || *SI == entry)
00518       continue;
00519     if (exitSuccs->find(*SI) == exitSuccs->end())
00520       return false;
00521     if (!isCommonDomFrontier(*SI, entry, exit))
00522       return false;
00523   }
00524 
00525   // Do not allow edges pointing into the region.
00526   for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end();
00527        SI != SE; ++SI)
00528     if (DT->properlyDominates(entry, *SI) && *SI != exit)
00529       return false;
00530 
00531 
00532   return true;
00533 }
00534 
00535 void RegionInfo::insertShortCut(BasicBlock *entry, BasicBlock *exit,
00536                              BBtoBBMap *ShortCut) const {
00537   assert(entry && exit && "entry and exit must not be null!");
00538 
00539   BBtoBBMap::iterator e = ShortCut->find(exit);
00540 
00541   if (e == ShortCut->end())
00542     // No further region at exit available.
00543     (*ShortCut)[entry] = exit;
00544   else {
00545     // We found a region e that starts at exit. Therefore (entry, e->second)
00546     // is also a region, that is larger than (entry, exit). Insert the
00547     // larger one.
00548     BasicBlock *BB = e->second;
00549     (*ShortCut)[entry] = BB;
00550   }
00551 }
00552 
00553 DomTreeNode* RegionInfo::getNextPostDom(DomTreeNode* N,
00554                                         BBtoBBMap *ShortCut) const {
00555   BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
00556 
00557   if (e == ShortCut->end())
00558     return N->getIDom();
00559 
00560   return PDT->getNode(e->second)->getIDom();
00561 }
00562 
00563 bool RegionInfo::isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const {
00564   assert(entry && exit && "entry and exit must not be null!");
00565 
00566   unsigned num_successors = succ_end(entry) - succ_begin(entry);
00567 
00568   if (num_successors <= 1 && exit == *(succ_begin(entry)))
00569     return true;
00570 
00571   return false;
00572 }
00573 
00574 void RegionInfo::updateStatistics(Region *R) {
00575   ++numRegions;
00576 
00577   // TODO: Slow. Should only be enabled if -stats is used.
00578   if (R->isSimple()) ++numSimpleRegions;
00579 }
00580 
00581 Region *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) {
00582   assert(entry && exit && "entry and exit must not be null!");
00583 
00584   if (isTrivialRegion(entry, exit))
00585     return nullptr;
00586 
00587   Region *region = new Region(entry, exit, this, DT);
00588   BBtoRegion.insert(std::make_pair(entry, region));
00589 
00590  #ifdef XDEBUG
00591     region->verifyRegion();
00592  #else
00593     DEBUG(region->verifyRegion());
00594  #endif
00595 
00596   updateStatistics(region);
00597   return region;
00598 }
00599 
00600 void RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) {
00601   assert(entry);
00602 
00603   DomTreeNode *N = PDT->getNode(entry);
00604 
00605   if (!N)
00606     return;
00607 
00608   Region *lastRegion= nullptr;
00609   BasicBlock *lastExit = entry;
00610 
00611   // As only a BasicBlock that postdominates entry can finish a region, walk the
00612   // post dominance tree upwards.
00613   while ((N = getNextPostDom(N, ShortCut))) {
00614     BasicBlock *exit = N->getBlock();
00615 
00616     if (!exit)
00617       break;
00618 
00619     if (isRegion(entry, exit)) {
00620       Region *newRegion = createRegion(entry, exit);
00621 
00622       if (lastRegion)
00623         newRegion->addSubRegion(lastRegion);
00624 
00625       lastRegion = newRegion;
00626       lastExit = exit;
00627     }
00628 
00629     // This can never be a region, so stop the search.
00630     if (!DT->dominates(entry, exit))
00631       break;
00632   }
00633 
00634   // Tried to create regions from entry to lastExit.  Next time take a
00635   // shortcut from entry to lastExit.
00636   if (lastExit != entry)
00637     insertShortCut(entry, lastExit, ShortCut);
00638 }
00639 
00640 void RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) {
00641   BasicBlock *entry = &(F.getEntryBlock());
00642   DomTreeNode *N = DT->getNode(entry);
00643 
00644   // Iterate over the dominance tree in post order to start with the small
00645   // regions from the bottom of the dominance tree.  If the small regions are
00646   // detected first, detection of bigger regions is faster, as we can jump
00647   // over the small regions.
00648   for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE;
00649     ++FI) {
00650     findRegionsWithEntry(FI->getBlock(), ShortCut);
00651   }
00652 }
00653 
00654 Region *RegionInfo::getTopMostParent(Region *region) {
00655   while (region->parent)
00656     region = region->getParent();
00657 
00658   return region;
00659 }
00660 
00661 void RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) {
00662   BasicBlock *BB = N->getBlock();
00663 
00664   // Passed region exit
00665   while (BB == region->getExit())
00666     region = region->getParent();
00667 
00668   BBtoRegionMap::iterator it = BBtoRegion.find(BB);
00669 
00670   // This basic block is a start block of a region. It is already in the
00671   // BBtoRegion relation. Only the child basic blocks have to be updated.
00672   if (it != BBtoRegion.end()) {
00673     Region *newRegion = it->second;
00674     region->addSubRegion(getTopMostParent(newRegion));
00675     region = newRegion;
00676   } else {
00677     BBtoRegion[BB] = region;
00678   }
00679 
00680   for (DomTreeNode::iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI)
00681     buildRegionsTree(*CI, region);
00682 }
00683 
00684 void RegionInfo::releaseMemory() {
00685   BBtoRegion.clear();
00686   if (TopLevelRegion)
00687     delete TopLevelRegion;
00688   TopLevelRegion = nullptr;
00689 }
00690 
00691 RegionInfo::RegionInfo() : FunctionPass(ID) {
00692   initializeRegionInfoPass(*PassRegistry::getPassRegistry());
00693   TopLevelRegion = nullptr;
00694 }
00695 
00696 RegionInfo::~RegionInfo() {
00697   releaseMemory();
00698 }
00699 
00700 void RegionInfo::Calculate(Function &F) {
00701   // ShortCut a function where for every BB the exit of the largest region
00702   // starting with BB is stored. These regions can be threated as single BBS.
00703   // This improves performance on linear CFGs.
00704   BBtoBBMap ShortCut;
00705 
00706   scanForRegions(F, &ShortCut);
00707   BasicBlock *BB = &F.getEntryBlock();
00708   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
00709 }
00710 
00711 bool RegionInfo::runOnFunction(Function &F) {
00712   releaseMemory();
00713 
00714   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00715   PDT = &getAnalysis<PostDominatorTree>();
00716   DF = &getAnalysis<DominanceFrontier>();
00717 
00718   TopLevelRegion = new Region(&F.getEntryBlock(), nullptr, this, DT, nullptr);
00719   updateStatistics(TopLevelRegion);
00720 
00721   Calculate(F);
00722 
00723   return false;
00724 }
00725 
00726 void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
00727   AU.setPreservesAll();
00728   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
00729   AU.addRequired<PostDominatorTree>();
00730   AU.addRequired<DominanceFrontier>();
00731 }
00732 
00733 void RegionInfo::print(raw_ostream &OS, const Module *) const {
00734   OS << "Region tree:\n";
00735   TopLevelRegion->print(OS, true, 0, printStyle.getValue());
00736   OS << "End region tree\n";
00737 }
00738 
00739 void RegionInfo::verifyAnalysis() const {
00740   // Only do verification when user wants to, otherwise this expensive check
00741   // will be invoked by PMDataManager::verifyPreservedAnalysis when
00742   // a regionpass (marked PreservedAll) finish.
00743   if (!VerifyRegionInfo) return;
00744 
00745   TopLevelRegion->verifyRegionNest();
00746 }
00747 
00748 // Region pass manager support.
00749 Region *RegionInfo::getRegionFor(BasicBlock *BB) const {
00750   BBtoRegionMap::const_iterator I=
00751     BBtoRegion.find(BB);
00752   return I != BBtoRegion.end() ? I->second : nullptr;
00753 }
00754 
00755 void RegionInfo::setRegionFor(BasicBlock *BB, Region *R) {
00756   BBtoRegion[BB] = R;
00757 }
00758 
00759 Region *RegionInfo::operator[](BasicBlock *BB) const {
00760   return getRegionFor(BB);
00761 }
00762 
00763 BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const {
00764   BasicBlock *Exit = nullptr;
00765 
00766   while (true) {
00767     // Get largest region that starts at BB.
00768     Region *R = getRegionFor(BB);
00769     while (R && R->getParent() && R->getParent()->getEntry() == BB)
00770       R = R->getParent();
00771 
00772     // Get the single exit of BB.
00773     if (R && R->getEntry() == BB)
00774       Exit = R->getExit();
00775     else if (++succ_begin(BB) == succ_end(BB))
00776       Exit = *succ_begin(BB);
00777     else // No single exit exists.
00778       return Exit;
00779 
00780     // Get largest region that starts at Exit.
00781     Region *ExitR = getRegionFor(Exit);
00782     while (ExitR && ExitR->getParent()
00783            && ExitR->getParent()->getEntry() == Exit)
00784       ExitR = ExitR->getParent();
00785 
00786     for (pred_iterator PI = pred_begin(Exit), PE = pred_end(Exit); PI != PE;
00787          ++PI)
00788       if (!R->contains(*PI) && !ExitR->contains(*PI))
00789         break;
00790 
00791     // This stops infinite cycles.
00792     if (DT->dominates(Exit, BB))
00793       break;
00794 
00795     BB = Exit;
00796   }
00797 
00798   return Exit;
00799 }
00800 
00801 Region*
00802 RegionInfo::getCommonRegion(Region *A, Region *B) const {
00803   assert (A && B && "One of the Regions is NULL");
00804 
00805   if (A->contains(B)) return A;
00806 
00807   while (!B->contains(A))
00808     B = B->getParent();
00809 
00810   return B;
00811 }
00812 
00813 Region*
00814 RegionInfo::getCommonRegion(SmallVectorImpl<Region*> &Regions) const {
00815   Region* ret = Regions.back();
00816   Regions.pop_back();
00817 
00818   for (SmallVectorImpl<Region*>::const_iterator I = Regions.begin(),
00819        E = Regions.end(); I != E; ++I)
00820       ret = getCommonRegion(ret, *I);
00821 
00822   return ret;
00823 }
00824 
00825 Region*
00826 RegionInfo::getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const {
00827   Region* ret = getRegionFor(BBs.back());
00828   BBs.pop_back();
00829 
00830   for (SmallVectorImpl<BasicBlock*>::const_iterator I = BBs.begin(),
00831        E = BBs.end(); I != E; ++I)
00832       ret = getCommonRegion(ret, getRegionFor(*I));
00833 
00834   return ret;
00835 }
00836 
00837 void RegionInfo::splitBlock(BasicBlock* NewBB, BasicBlock *OldBB)
00838 {
00839   Region *R = getRegionFor(OldBB);
00840 
00841   setRegionFor(NewBB, R);
00842 
00843   while (R->getEntry() == OldBB && !R->isTopLevelRegion()) {
00844     R->replaceEntry(NewBB);
00845     R = R->getParent();
00846   }
00847 
00848   setRegionFor(OldBB, R);
00849 }
00850 
00851 char RegionInfo::ID = 0;
00852 INITIALIZE_PASS_BEGIN(RegionInfo, "regions",
00853                 "Detect single entry single exit regions", true, true)
00854 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00855 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
00856 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
00857 INITIALIZE_PASS_END(RegionInfo, "regions",
00858                 "Detect single entry single exit regions", true, true)
00859 
00860 // Create methods available outside of this file, to use them
00861 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
00862 // the link time optimization.
00863 
00864 namespace llvm {
00865   FunctionPass *createRegionInfoPass() {
00866     return new RegionInfo();
00867   }
00868 }
00869