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