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