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