LLVM  6.0.0svn
RegionInfoImpl.h
Go to the documentation of this file.
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/GraphTraits.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Analysis/LoopInfo.h"
25 #include "llvm/Support/Debug.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 
39 namespace llvm {
40 
41 //===----------------------------------------------------------------------===//
42 /// RegionBase Implementation
43 template <class Tr>
44 RegionBase<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 
49 template <class Tr>
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 
56 template <class Tr>
57 void RegionBase<Tr>::replaceEntry(BlockT *BB) {
58  this->entry.setPointer(BB);
59 }
60 
61 template <class Tr>
62 void RegionBase<Tr>::replaceExit(BlockT *BB) {
63  assert(exit && "No exit to replace!");
64  exit = BB;
65 }
66 
67 template <class Tr>
68 void 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 
85 template <class Tr>
86 void 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 
103 template <class Tr>
104 bool 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 
120 template <class Tr>
121 bool 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 
142 template <class Tr>
143 typename 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 
154 template <class Tr>
155 typename 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 
162 template <class Tr>
163 typename 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 
180 template <class Tr>
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 
203 template <class Tr>
204 typename 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 
224 template <class Tr>
226  return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
227 }
228 
229 template <class Tr>
230 std::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 = 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 = getExit()->getName();
248  } else
249  exitName = "<Function Return>";
250 
251  return entryName + " => " + exitName;
252 }
253 
254 template <class Tr>
255 void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
256  if (!contains(BB))
257  llvm_unreachable("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  llvm_unreachable("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  llvm_unreachable("Broken region found: edges entering the region must "
273  "go to the entry node!");
274  }
275  }
276 }
277 
278 template <class Tr>
279 void 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 
293 template <class Tr>
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.
299  return;
300 
301  std::set<BlockT *> visited;
302  verifyWalk(getEntry(), &visited);
303 }
304 
305 template <class Tr>
307  for (const std::unique_ptr<RegionT> &R : *this)
308  R->verifyRegionNest();
309 
310  verifyRegion();
311 }
312 
313 template <class Tr>
315  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
316 }
317 
318 template <class Tr>
320  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
321 }
322 
323 template <class Tr>
327  static_cast<const RegionT *>(this));
328 }
329 
330 template <class Tr>
334  static_cast<const RegionT *>(this));
335 }
336 
337 template <class Tr>
338 typename 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 
358 template <class Tr>
359 typename 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  llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
369  at = BBNodeMap.insert(std::move(V)).first;
370  }
371  return at->second.get();
372 }
373 
374 template <class Tr>
375 typename 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 
383 template <class Tr>
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 
392 template <class Tr>
393 void 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 
435 template <class Tr>
436 typename 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 
448 template <class Tr>
449 unsigned 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 
458 template <class Tr>
459 typename 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 
489 template <class Tr>
490 void 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)
525 template <class Tr>
526 void RegionBase<Tr>::dump() const {
527  print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
528 }
529 #endif
530 
531 template <class Tr>
533  BBNodeMap.clear();
534  for (std::unique_ptr<RegionT> &R : *this)
535  R->clearNodeCache();
536 }
537 
538 //===----------------------------------------------------------------------===//
539 // RegionInfoBase implementation
540 //
541 
542 template <class Tr>
544 
545 template <class Tr>
547  releaseMemory();
548 }
549 
550 template <class Tr>
551 void 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  llvm_unreachable("BB map does not match region nesting");
561  }
562  }
563 }
564 
565 template <class Tr>
566 bool 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 
577 template <class Tr>
578 bool 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 (typename DST::iterator SI = entrySuccs->begin(),
589  SE = entrySuccs->end();
590  SI != SE; ++SI) {
591  if (*SI != exit && *SI != entry)
592  return false;
593  }
594 
595  return true;
596  }
597 
598  DST *exitSuccs = &DF->find(exit)->second;
599 
600  // Do not allow edges leaving the region.
601  for (BlockT *Succ : *entrySuccs) {
602  if (Succ == exit || Succ == entry)
603  continue;
604  if (exitSuccs->find(Succ) == exitSuccs->end())
605  return false;
606  if (!isCommonDomFrontier(Succ, entry, exit))
607  return false;
608  }
609 
610  // Do not allow edges pointing into the region.
611  for (BlockT *Succ : *exitSuccs) {
612  if (DT->properlyDominates(entry, Succ) && Succ != exit)
613  return false;
614  }
615 
616  return true;
617 }
618 
619 template <class Tr>
620 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
621  BBtoBBMap *ShortCut) const {
622  assert(entry && exit && "entry and exit must not be null!");
623 
624  typename BBtoBBMap::iterator e = ShortCut->find(exit);
625 
626  if (e == ShortCut->end())
627  // No further region at exit available.
628  (*ShortCut)[entry] = exit;
629  else {
630  // We found a region e that starts at exit. Therefore (entry, e->second)
631  // is also a region, that is larger than (entry, exit). Insert the
632  // larger one.
633  BlockT *BB = e->second;
634  (*ShortCut)[entry] = BB;
635  }
636 }
637 
638 template <class Tr>
639 typename Tr::DomTreeNodeT *
640 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
641  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
642 
643  if (e == ShortCut->end())
644  return N->getIDom();
645 
646  return PDT->getNode(e->second)->getIDom();
647 }
648 
649 template <class Tr>
650 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
651  assert(entry && exit && "entry and exit must not be null!");
652 
653  unsigned num_successors =
654  BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
655 
656  if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
657  return true;
658 
659  return false;
660 }
661 
662 template <class Tr>
663 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
664  BlockT *exit) {
665  assert(entry && exit && "entry and exit must not be null!");
666 
667  if (isTrivialRegion(entry, exit))
668  return nullptr;
669 
670  RegionT *region =
671  new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
672  BBtoRegion.insert({entry, region});
673 
674 #ifdef EXPENSIVE_CHECKS
675  region->verifyRegion();
676 #else
677  DEBUG(region->verifyRegion());
678 #endif
679 
680  updateStatistics(region);
681  return region;
682 }
683 
684 template <class Tr>
686  BBtoBBMap *ShortCut) {
687  assert(entry);
688 
689  DomTreeNodeT *N = PDT->getNode(entry);
690  if (!N)
691  return;
692 
693  RegionT *lastRegion = nullptr;
694  BlockT *lastExit = entry;
695 
696  // As only a BasicBlock that postdominates entry can finish a region, walk the
697  // post dominance tree upwards.
698  while ((N = getNextPostDom(N, ShortCut))) {
699  BlockT *exit = N->getBlock();
700 
701  if (!exit)
702  break;
703 
704  if (isRegion(entry, exit)) {
705  RegionT *newRegion = createRegion(entry, exit);
706 
707  if (lastRegion)
708  newRegion->addSubRegion(lastRegion);
709 
710  lastRegion = newRegion;
711  lastExit = exit;
712  }
713 
714  // This can never be a region, so stop the search.
715  if (!DT->dominates(entry, exit))
716  break;
717  }
718 
719  // Tried to create regions from entry to lastExit. Next time take a
720  // shortcut from entry to lastExit.
721  if (lastExit != entry)
722  insertShortCut(entry, lastExit, ShortCut);
723 }
724 
725 template <class Tr>
726 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
727  using FuncPtrT = typename std::add_pointer<FuncT>::type;
728 
729  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
730  DomTreeNodeT *N = DT->getNode(entry);
731 
732  // Iterate over the dominance tree in post order to start with the small
733  // regions from the bottom of the dominance tree. If the small regions are
734  // detected first, detection of bigger regions is faster, as we can jump
735  // over the small regions.
736  for (auto DomNode : post_order(N))
737  findRegionsWithEntry(DomNode->getBlock(), ShortCut);
738 }
739 
740 template <class Tr>
741 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
742  while (region->getParent())
743  region = region->getParent();
744 
745  return region;
746 }
747 
748 template <class Tr>
749 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
750  BlockT *BB = N->getBlock();
751 
752  // Passed region exit
753  while (BB == region->getExit())
754  region = region->getParent();
755 
756  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
757 
758  // This basic block is a start block of a region. It is already in the
759  // BBtoRegion relation. Only the child basic blocks have to be updated.
760  if (it != BBtoRegion.end()) {
761  RegionT *newRegion = it->second;
762  region->addSubRegion(getTopMostParent(newRegion));
763  region = newRegion;
764  } else {
765  BBtoRegion[BB] = region;
766  }
767 
768  for (DomTreeNodeBase<BlockT> *C : *N) {
769  buildRegionsTree(C, region);
770  }
771 }
772 
773 #ifdef EXPENSIVE_CHECKS
774 template <class Tr>
776 #else
777 template <class Tr>
778 bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
779 #endif
780 
781 template <class Tr>
782 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
784 
785 template <class Tr>
787  OS << "Region tree:\n";
788  TopLevelRegion->print(OS, true, 0, printStyle);
789  OS << "End region tree\n";
790 }
791 
792 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
793 template <class Tr>
794 void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
795 #endif
796 
797 template <class Tr>
799  BBtoRegion.clear();
800  if (TopLevelRegion)
801  delete TopLevelRegion;
802  TopLevelRegion = nullptr;
803 }
804 
805 template <class Tr>
807  // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
808  // -verify-region-info
809  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
810  return;
811 
812  TopLevelRegion->verifyRegionNest();
813 
814  verifyBBMap(TopLevelRegion);
815 }
816 
817 // Region pass manager support.
818 template <class Tr>
819 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
820  typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
821  return I != BBtoRegion.end() ? I->second : nullptr;
822 }
823 
824 template <class Tr>
825 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
826  BBtoRegion[BB] = R;
827 }
828 
829 template <class Tr>
830 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
831  return getRegionFor(BB);
832 }
833 
834 template <class Tr>
835 typename RegionInfoBase<Tr>::BlockT *
837  BlockT *Exit = nullptr;
838 
839  while (true) {
840  // Get largest region that starts at BB.
841  RegionT *R = getRegionFor(BB);
842  while (R && R->getParent() && R->getParent()->getEntry() == BB)
843  R = R->getParent();
844 
845  // Get the single exit of BB.
846  if (R && R->getEntry() == BB)
847  Exit = R->getExit();
848  else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
849  Exit = *BlockTraits::child_begin(BB);
850  else // No single exit exists.
851  return Exit;
852 
853  // Get largest region that starts at Exit.
854  RegionT *ExitR = getRegionFor(Exit);
855  while (ExitR && ExitR->getParent() &&
856  ExitR->getParent()->getEntry() == Exit)
857  ExitR = ExitR->getParent();
858 
859  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
860  InvBlockTraits::child_end(Exit))) {
861  if (!R->contains(Pred) && !ExitR->contains(Pred))
862  break;
863  }
864 
865  // This stops infinite cycles.
866  if (DT->dominates(Exit, BB))
867  break;
868 
869  BB = Exit;
870  }
871 
872  return Exit;
873 }
874 
875 template <class Tr>
876 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
877  RegionT *B) const {
878  assert(A && B && "One of the Regions is NULL");
879 
880  if (A->contains(B))
881  return A;
882 
883  while (!B->contains(A))
884  B = B->getParent();
885 
886  return B;
887 }
888 
889 template <class Tr>
890 typename Tr::RegionT *
892  RegionT *ret = Regions.back();
893  Regions.pop_back();
894 
895  for (RegionT *R : Regions)
896  ret = getCommonRegion(ret, R);
897 
898  return ret;
899 }
900 
901 template <class Tr>
902 typename Tr::RegionT *
904  RegionT *ret = getRegionFor(BBs.back());
905  BBs.pop_back();
906 
907  for (BlockT *BB : BBs)
908  ret = getCommonRegion(ret, getRegionFor(BB));
909 
910  return ret;
911 }
912 
913 template <class Tr>
914 void RegionInfoBase<Tr>::calculate(FuncT &F) {
915  using FuncPtrT = typename std::add_pointer<FuncT>::type;
916 
917  // ShortCut a function where for every BB the exit of the largest region
918  // starting with BB is stored. These regions can be threated as single BBS.
919  // This improves performance on linear CFGs.
920  BBtoBBMap ShortCut;
921 
922  scanForRegions(F, &ShortCut);
923  BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
924  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
925 }
926 
927 } // end namespace llvm
928 
929 #undef DEBUG_TYPE
930 
931 #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
uint64_t CallInst * C
void push_back(const T &Elt)
Definition: SmallVector.h:212
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:102
bool getExitingBlocks(SmallVectorImpl< BlockT *> &Exitings) const
Collect all blocks of this region&#39;s single exit edge, if existing.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:235
BlockT * getEnteringBlock() const
Return the first block of this region&#39;s single entry edge, if existing.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void print(raw_ostream &OS) const
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
unsigned getDepth() const
Get the nesting level of this Region.
F(f)
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:69
return AArch64::GPR64RegClass contains(Reg)
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
void clearNodeCache()
Clear the cache for BB RegionNodes.
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:371
static StringRef getName(Value *V)
void verifyAnalysis() const
PrintStyle
PrintStyle - Print region in difference ways.
Definition: RegionInfo.h:430
Base class for the actual dominator tree node.
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors...
bool isSimple() const
Is this a simple region?
#define P(N)
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
void dump() const
Print the region to stderr.
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
element_iterator element_end()
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
iterator_range< po_iterator< T > > post_order(const T &G)
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:841
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
A single entry single exit Region.
Definition: RegionInfo.h:67
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
element_iterator element_begin()
std::string getNameStr() const
Returns the name of the Region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
void verifyRegion() const
Verify if the region is a correct region.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
~RegionBase()
Delete the Region and all its subregions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:462
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
BlockT * getExitingBlock() const
Return the first block of this region&#39;s single exit edge, if existing.
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.