LLVM  14.0.0git
RegionInfoImpl.h
Go to the documentation of this file.
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"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Config/llvm-config.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>
58  this->entry.setPointer(BB);
59 }
60 
61 template <class Tr>
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 = 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 
254 template <class Tr>
255 void 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 
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>
333  return GraphTraits<const RegionT *>::nodes_end(
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  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 
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  report_fatal_error("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 (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 
617 template <class Tr>
618 void 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 
636 template <class Tr>
637 typename Tr::DomTreeNodeT *
638 RegionInfoBase<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 
647 template <class Tr>
648 bool 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 
660 template <class Tr>
661 typename 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 
682 template <class Tr>
683 void 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 
723 template <class Tr>
724 void 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 
738 template <class Tr>
739 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
740  while (region->getParent())
741  region = region->getParent();
742 
743  return region;
744 }
745 
746 template <class Tr>
747 void 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
772 template <class Tr>
774 #else
775 template <class Tr>
777 #endif
778 
779 template <class Tr>
780 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
782 
783 template <class Tr>
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)
791 template <class Tr>
792 void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
793 #endif
794 
795 template <class Tr>
797  BBtoRegion.clear();
798  if (TopLevelRegion)
799  delete TopLevelRegion;
800  TopLevelRegion = nullptr;
801 }
802 
803 template <class Tr>
805  // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
806  // -verify-region-info
808  return;
809 
810  TopLevelRegion->verifyRegionNest();
811 
812  verifyBBMap(TopLevelRegion);
813 }
814 
815 // Region pass manager support.
816 template <class Tr>
817 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
818  return BBtoRegion.lookup(BB);
819 }
820 
821 template <class Tr>
822 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
823  BBtoRegion[BB] = R;
824 }
825 
826 template <class Tr>
827 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
828  return getRegionFor(BB);
829 }
830 
831 template <class Tr>
832 typename RegionInfoBase<Tr>::BlockT *
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 
872 template <class Tr>
873 typename 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 
886 template <class Tr>
887 typename Tr::RegionT *
889  RegionT *ret = Regions.pop_back_val();
890 
891  for (RegionT *R : Regions)
892  ret = getCommonRegion(ret, R);
893 
894  return ret;
895 }
896 
897 template <class Tr>
898 typename Tr::RegionT *
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 
909 template <class Tr>
910 void 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);
920  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
921 }
922 
923 } // end namespace llvm
924 
925 #undef DEBUG_TYPE
926 
927 #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H
RegionInfo.h
llvm::RegionBase::getBBNode
RegionNodeT * getBBNode(BlockT *BB) const
Get the BasicBlock RegionNode for a BasicBlock.
Definition: RegionInfoImpl.h:359
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
DominanceFrontier.h
llvm::RegionBase::addSubRegion
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
Definition: RegionInfoImpl.h:393
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
verifyRegion
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
Definition: VPlanVerifier.cpp:95
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::RegionBase
A single entry single exit Region.
Definition: RegionInfo.h:66
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:623
llvm::RegionBase::~RegionBase
~RegionBase()
Delete the Region and all its subregions.
Definition: RegionInfoImpl.h:50
contains
return AArch64::GPR64RegClass contains(Reg)
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
ErrorHandling.h
llvm::RegionInfoBase::operator[]
RegionT * operator[](BlockT *BB) const
A shortcut for getRegionFor().
Definition: RegionInfoImpl.h:827
llvm::RegionBase::transferChildrenTo
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
Definition: RegionInfoImpl.h:384
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::RegionBase::replaceExitRecursive
void replaceExitRecursive(BlockT *NewExit)
Recursively replace the exit basic block of the region.
Definition: RegionInfoImpl.h:86
ret
to esp esp setne al movzbw ax esp setg cl movzbw cx cmove cx cl jne LBB1_2 esp ret(also really horrible code on ppc). This is due to the expand code for 64-bit compares. GCC produces multiple branches
at
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional ldr LCPI1_0 ldr ldr tst movne lsr ldr LCPI1_1 and r0 bx lr it saves an instruction and a register It might be profitable to cse MOVi16 if there are lots of bit immediates with the same bottom half Robert Muth started working on an alternate jump table implementation that does not put the tables in line in the text This is more like the llvm default jump table implementation This might be useful sometime Several revisions of patches are on the mailing beginning at
Definition: README.txt:582
llvm::RegionBase::removeSubRegion
RegionT * removeSubRegion(RegionT *SubRegion)
Remove a subregion from this Region.
Definition: RegionInfoImpl.h:436
STLExtras.h
llvm::RegionBase::outermostLoopInRegion
LoopT * outermostLoopInRegion(LoopT *L) const
Get the outermost loop in the region that contains a loop.
Definition: RegionInfoImpl.h:143
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::RegionBase::replaceEntry
void replaceEntry(BlockT *BB)
Replace the entry basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:57
GraphTraits.h
PostDominators.h
llvm::RegionBase::RegionBase
RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT, RegionT *Parent=nullptr)
Create a new region.
llvm::RegionInfoBase::VerifyRegionInfo
static bool VerifyRegionInfo
Definition: RegionInfo.h:802
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::RegionInfoBase::dump
void dump() const
Definition: RegionInfoImpl.h:792
llvm::RegionBase< RegionTraits< Function > >::PrintStyle
PrintStyle
PrintStyle - Print region in difference ways.
Definition: RegionInfo.h:429
llvm::RegionBase::element_end
element_iterator element_end()
Definition: RegionInfoImpl.h:319
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::RegionBase::verifyRegion
void verifyRegion() const
Verify if the region is a correct region.
Definition: RegionInfoImpl.h:294
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::RegionInfoBase
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:68
llvm::RegionBase::PrintNone
@ PrintNone
Definition: RegionInfo.h:429
DF
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
LoopInfo.h
llvm::RegionInfoBase::printStyle
static RegionT::PrintStyle printStyle
Definition: RegionInfo.h:803
llvm::RegionInfoBase::getRegionFor
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
Definition: RegionInfoImpl.h:817
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::RegionBase::clearNodeCache
void clearNodeCache()
Clear the cache for BB RegionNodes.
Definition: RegionInfoImpl.h:532
llvm::RegionInfoBase::setRegionFor
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
Definition: RegionInfoImpl.h:822
llvm::RegionBase::element_begin
element_iterator element_begin()
Definition: RegionInfoImpl.h:314
llvm::HexStyle::Style
Style
Definition: MCInstPrinter.h:32
llvm::RegionBase::getSubRegionNode
RegionT * getSubRegionNode(BlockT *BB) const
Get the subregion that starts at a BasicBlock.
Definition: RegionInfoImpl.h:338
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegionIterator.h
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
iterator_range.h
llvm::RegionInfoBase::print
void print(raw_ostream &OS) const
Definition: RegionInfoImpl.h:784
llvm::df_iterator
Definition: DepthFirstIterator.h:85
elements
This compiles xmm1 mulss xmm1 xorps xmm0 movss xmm0 ret Because mulss doesn t modify the top elements
Definition: README-SSE.txt:221
llvm::RegionInfoBase::getCommonRegion
RegionT * getCommonRegion(RegionT *A, RegionT *B) const
Find the smallest region that contains two regions.
Definition: RegionInfoImpl.h:873
llvm::RegionBase::print
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
Definition: RegionInfoImpl.h:490
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
llvm::RegionBase::getExpandedRegion
RegionT * getExpandedRegion() const
Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.
Definition: RegionInfoImpl.h:459
llvm::RegionBase::const_element_iterator
df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > const_element_iterator
Definition: RegionInfo.h:647
llvm::RegionBase::getEnteringBlock
BlockT * getEnteringBlock() const
Return the first block of this region's single entry edge, if existing.
Definition: RegionInfoImpl.h:163
llvm::RegionBase::dump
void dump() const
Print the region to stderr.
Definition: RegionInfoImpl.h:526
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1574
llvm::RegionBase::getDepth
unsigned getDepth() const
Get the nesting level of this Region.
Definition: RegionInfoImpl.h:449
llvm::RegionBase::getNode
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:370
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:254
llvm::RegionInfoBase::verifyAnalysis
void verifyAnalysis() const
Definition: RegionInfoImpl.h:804
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:188
llvm::RegionBase::getExitingBlocks
bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const
Collect all blocks of this region's single exit edge, if existing.
Definition: RegionInfoImpl.h:181
llvm::RegionBase::getNameStr
std::string getNameStr() const
Returns the name of the Region.
Definition: RegionInfoImpl.h:230
llvm::RegionBase::replaceEntryRecursive
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
Definition: RegionInfoImpl.h:68
llvm::RegionBase::contains
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Definition: RegionInfoImpl.h:104
llvm::RegionBase::isSimple
bool isSimple() const
Is this a simple region?
Definition: RegionInfoImpl.h:225
llvm::RegionInfoBase::getMaxRegionExit
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
Definition: RegionInfoImpl.h:833
PostOrderIterator.h
SmallVector.h
llvm::RegionInfoBase::releaseMemory
void releaseMemory()
Definition: RegionInfoImpl.h:796
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:497
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
N
#define N
llvm::SmallVectorImpl< BlockT * >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::RegionBase::getExitingBlock
BlockT * getExitingBlock() const
Return the first block of this region's single exit edge, if existing.
Definition: RegionInfoImpl.h:204
raw_ostream.h
Debug.h
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339
llvm::RegionBase::replaceExit
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:62