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