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