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