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