lib/Analysis/RegionInfo.cpp

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