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