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