LLVM  16.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  auto isEnteringBlock = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
163  assert(!AllowRepeats && "Unexpected parameter value.");
164  return DT->getNode(Pred) && !contains(Pred) ? Pred : nullptr;
165  };
166  BlockT *entry = getEntry();
167  return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(entry),
168  InvBlockTraits::child_end(entry)),
169  isEnteringBlock);
170 }
171 
172 template <class Tr>
174  SmallVectorImpl<BlockT *> &Exitings) const {
175  bool CoverAll = true;
176 
177  if (!exit)
178  return CoverAll;
179 
180  for (PredIterTy PI = InvBlockTraits::child_begin(exit),
181  PE = InvBlockTraits::child_end(exit);
182  PI != PE; ++PI) {
183  BlockT *Pred = *PI;
184  if (contains(Pred)) {
185  Exitings.push_back(Pred);
186  continue;
187  }
188 
189  CoverAll = false;
190  }
191 
192  return CoverAll;
193 }
194 
195 template <class Tr>
196 typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
197  BlockT *exit = getExit();
198  if (!exit)
199  return nullptr;
200 
201  auto isContained = [&](BlockT *Pred, bool AllowRepeats) -> BlockT * {
202  assert(!AllowRepeats && "Unexpected parameter value.");
203  return contains(Pred) ? Pred : nullptr;
204  };
205  return find_singleton<BlockT>(make_range(InvBlockTraits::child_begin(exit),
206  InvBlockTraits::child_end(exit)),
207  isContained);
208 }
209 
210 template <class Tr>
212  return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
213 }
214 
215 template <class Tr>
216 std::string RegionBase<Tr>::getNameStr() const {
217  std::string exitName;
218  std::string entryName;
219 
220  if (getEntry()->getName().empty()) {
221  raw_string_ostream OS(entryName);
222 
223  getEntry()->printAsOperand(OS, false);
224  } else
225  entryName = std::string(getEntry()->getName());
226 
227  if (getExit()) {
228  if (getExit()->getName().empty()) {
229  raw_string_ostream OS(exitName);
230 
231  getExit()->printAsOperand(OS, false);
232  } else
233  exitName = std::string(getExit()->getName());
234  } else
235  exitName = "<Function Return>";
236 
237  return entryName + " => " + exitName;
238 }
239 
240 template <class Tr>
241 void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
242  if (!contains(BB))
243  report_fatal_error("Broken region found: enumerated BB not in region!");
244 
245  BlockT *entry = getEntry(), *exit = getExit();
246 
247  for (BlockT *Succ :
248  make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
249  if (!contains(Succ) && exit != Succ)
250  report_fatal_error("Broken region found: edges leaving the region must go "
251  "to the exit node!");
252  }
253 
254  if (entry != BB) {
255  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
256  InvBlockTraits::child_end(BB))) {
257  if (!contains(Pred))
258  report_fatal_error("Broken region found: edges entering the region must "
259  "go to the entry node!");
260  }
261  }
262 }
263 
264 template <class Tr>
265 void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
266  BlockT *exit = getExit();
267 
268  visited->insert(BB);
269 
270  verifyBBInRegion(BB);
271 
272  for (BlockT *Succ :
273  make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
274  if (Succ != exit && visited->find(Succ) == visited->end())
275  verifyWalk(Succ, visited);
276  }
277 }
278 
279 template <class Tr>
281  // Only do verification when user wants to, otherwise this expensive check
282  // will be invoked by PMDataManager::verifyPreservedAnalysis when
283  // a regionpass (marked PreservedAll) finish.
285  return;
286 
287  std::set<BlockT *> visited;
288  verifyWalk(getEntry(), &visited);
289 }
290 
291 template <class Tr>
293  for (const std::unique_ptr<RegionT> &R : *this)
294  R->verifyRegionNest();
295 
296  verifyRegion();
297 }
298 
299 template <class Tr>
301  return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
302 }
303 
304 template <class Tr>
306  return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
307 }
308 
309 template <class Tr>
313  static_cast<const RegionT *>(this));
314 }
315 
316 template <class Tr>
319  return GraphTraits<const RegionT *>::nodes_end(
320  static_cast<const RegionT *>(this));
321 }
322 
323 template <class Tr>
324 typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
325  using RegionT = typename Tr::RegionT;
326 
327  RegionT *R = RI->getRegionFor(BB);
328 
329  if (!R || R == this)
330  return nullptr;
331 
332  // If we pass the BB out of this region, that means our code is broken.
333  assert(contains(R) && "BB not in current region!");
334 
335  while (contains(R->getParent()) && R->getParent() != this)
336  R = R->getParent();
337 
338  if (R->getEntry() != BB)
339  return nullptr;
340 
341  return R;
342 }
343 
344 template <class Tr>
345 typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
346  assert(contains(BB) && "Can get BB node out of this region!");
347 
348  typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
349 
350  if (at == BBNodeMap.end()) {
351  auto Deconst = const_cast<RegionBase<Tr> *>(this);
352  typename BBNodeMapT::value_type V = {
353  BB,
354  std::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
355  at = BBNodeMap.insert(std::move(V)).first;
356  }
357  return at->second.get();
358 }
359 
360 template <class Tr>
361 typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
362  assert(contains(BB) && "Can get BB node out of this region!");
363  if (RegionT *Child = getSubRegionNode(BB))
364  return Child->getNode();
365 
366  return getBBNode(BB);
367 }
368 
369 template <class Tr>
371  for (std::unique_ptr<RegionT> &R : *this) {
372  R->parent = To;
373  To->children.push_back(std::move(R));
374  }
375  children.clear();
376 }
377 
378 template <class Tr>
379 void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
380  assert(!SubRegion->parent && "SubRegion already has a parent!");
381  assert(llvm::none_of(*this,
382  [&](const std::unique_ptr<RegionT> &R) {
383  return R.get() == SubRegion;
384  }) &&
385  "Subregion already exists!");
386 
387  SubRegion->parent = static_cast<RegionT *>(this);
388  children.push_back(std::unique_ptr<RegionT>(SubRegion));
389 
390  if (!moveChildren)
391  return;
392 
393  assert(SubRegion->children.empty() &&
394  "SubRegions that contain children are not supported");
395 
396  for (RegionNodeT *Element : elements()) {
397  if (!Element->isSubRegion()) {
398  BlockT *BB = Element->template getNodeAs<BlockT>();
399 
400  if (SubRegion->contains(BB))
401  RI->setRegionFor(BB, SubRegion);
402  }
403  }
404 
405  std::vector<std::unique_ptr<RegionT>> Keep;
406  for (std::unique_ptr<RegionT> &R : *this) {
407  if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
408  R->parent = SubRegion;
409  SubRegion->children.push_back(std::move(R));
410  } else
411  Keep.push_back(std::move(R));
412  }
413 
414  children.clear();
415  children.insert(
416  children.begin(),
417  std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
418  std::move_iterator<typename RegionSet::iterator>(Keep.end()));
419 }
420 
421 template <class Tr>
422 typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
423  assert(Child->parent == this && "Child is not a child of this region!");
424  Child->parent = nullptr;
425  typename RegionSet::iterator I =
426  llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) {
427  return R.get() == Child;
428  });
429  assert(I != children.end() && "Region does not exit. Unable to remove.");
430  children.erase(children.begin() + (I - begin()));
431  return Child;
432 }
433 
434 template <class Tr>
435 unsigned RegionBase<Tr>::getDepth() const {
436  unsigned Depth = 0;
437 
438  for (RegionT *R = getParent(); R != nullptr; R = R->getParent())
439  ++Depth;
440 
441  return Depth;
442 }
443 
444 template <class Tr>
445 typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
446  unsigned NumSuccessors = Tr::getNumSuccessors(exit);
447 
448  if (NumSuccessors == 0)
449  return nullptr;
450 
451  RegionT *R = RI->getRegionFor(exit);
452 
453  if (R->getEntry() != exit) {
454  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
455  InvBlockTraits::child_end(getExit())))
456  if (!contains(Pred))
457  return nullptr;
458  if (Tr::getNumSuccessors(exit) == 1)
459  return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
460  return nullptr;
461  }
462 
463  while (R->getParent() && R->getParent()->getEntry() == exit)
464  R = R->getParent();
465 
466  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
467  InvBlockTraits::child_end(getExit()))) {
468  if (!(contains(Pred) || R->contains(Pred)))
469  return nullptr;
470  }
471 
472  return new RegionT(getEntry(), R->getExit(), RI, DT);
473 }
474 
475 template <class Tr>
476 void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
477  PrintStyle Style) const {
478  if (print_tree)
479  OS.indent(level * 2) << '[' << level << "] " << getNameStr();
480  else
481  OS.indent(level * 2) << getNameStr();
482 
483  OS << '\n';
484 
485  if (Style != PrintNone) {
486  OS.indent(level * 2) << "{\n";
487  OS.indent(level * 2 + 2);
488 
489  if (Style == PrintBB) {
490  for (const auto *BB : blocks())
491  OS << BB->getName() << ", "; // TODO: remove the last ","
492  } else if (Style == PrintRN) {
493  for (const RegionNodeT *Element : elements()) {
494  OS << *Element << ", "; // TODO: remove the last ",
495  }
496  }
497 
498  OS << '\n';
499  }
500 
501  if (print_tree) {
502  for (const std::unique_ptr<RegionT> &R : *this)
503  R->print(OS, print_tree, level + 1, Style);
504  }
505 
506  if (Style != PrintNone)
507  OS.indent(level * 2) << "} \n";
508 }
509 
510 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
511 template <class Tr>
512 void RegionBase<Tr>::dump() const {
513  print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
514 }
515 #endif
516 
517 template <class Tr>
519  BBNodeMap.clear();
520  for (std::unique_ptr<RegionT> &R : *this)
521  R->clearNodeCache();
522 }
523 
524 //===----------------------------------------------------------------------===//
525 // RegionInfoBase implementation
526 //
527 
528 template <class Tr>
530 
531 template <class Tr>
533  releaseMemory();
534 }
535 
536 template <class Tr>
537 void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
538  assert(R && "Re must be non-null");
539  for (const typename Tr::RegionNodeT *Element : R->elements()) {
540  if (Element->isSubRegion()) {
541  const RegionT *SR = Element->template getNodeAs<RegionT>();
542  verifyBBMap(SR);
543  } else {
544  BlockT *BB = Element->template getNodeAs<BlockT>();
545  if (getRegionFor(BB) != R)
546  report_fatal_error("BB map does not match region nesting");
547  }
548  }
549 }
550 
551 template <class Tr>
552 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
553  BlockT *exit) const {
554  for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
555  InvBlockTraits::child_end(BB))) {
556  if (DT->dominates(entry, P) && !DT->dominates(exit, P))
557  return false;
558  }
559 
560  return true;
561 }
562 
563 template <class Tr>
564 bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
565  assert(entry && exit && "entry and exit must not be null!");
566 
567  using DST = typename DomFrontierT::DomSetType;
568 
569  DST *entrySuccs = &DF->find(entry)->second;
570 
571  // Exit is the header of a loop that contains the entry. In this case,
572  // the dominance frontier must only contain the exit.
573  if (!DT->dominates(entry, exit)) {
574  for (BlockT *successor : *entrySuccs) {
575  if (successor != exit && successor != entry)
576  return false;
577  }
578 
579  return true;
580  }
581 
582  DST *exitSuccs = &DF->find(exit)->second;
583 
584  // Do not allow edges leaving the region.
585  for (BlockT *Succ : *entrySuccs) {
586  if (Succ == exit || Succ == entry)
587  continue;
588  if (exitSuccs->find(Succ) == exitSuccs->end())
589  return false;
590  if (!isCommonDomFrontier(Succ, entry, exit))
591  return false;
592  }
593 
594  // Do not allow edges pointing into the region.
595  for (BlockT *Succ : *exitSuccs) {
596  if (DT->properlyDominates(entry, Succ) && Succ != exit)
597  return false;
598  }
599 
600  return true;
601 }
602 
603 template <class Tr>
604 void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
605  BBtoBBMap *ShortCut) const {
606  assert(entry && exit && "entry and exit must not be null!");
607 
608  typename BBtoBBMap::iterator e = ShortCut->find(exit);
609 
610  if (e == ShortCut->end())
611  // No further region at exit available.
612  (*ShortCut)[entry] = exit;
613  else {
614  // We found a region e that starts at exit. Therefore (entry, e->second)
615  // is also a region, that is larger than (entry, exit). Insert the
616  // larger one.
617  BlockT *BB = e->second;
618  (*ShortCut)[entry] = BB;
619  }
620 }
621 
622 template <class Tr>
623 typename Tr::DomTreeNodeT *
624 RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
625  typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
626 
627  if (e == ShortCut->end())
628  return N->getIDom();
629 
630  return PDT->getNode(e->second)->getIDom();
631 }
632 
633 template <class Tr>
634 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
635  assert(entry && exit && "entry and exit must not be null!");
636 
637  unsigned num_successors =
638  BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
639 
640  if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
641  return true;
642 
643  return false;
644 }
645 
646 template <class Tr>
647 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
648  BlockT *exit) {
649  assert(entry && exit && "entry and exit must not be null!");
650 
651  if (isTrivialRegion(entry, exit))
652  return nullptr;
653 
654  RegionT *region =
655  new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
656  BBtoRegion.insert({entry, region});
657 
658 #ifdef EXPENSIVE_CHECKS
659  region->verifyRegion();
660 #else
661  LLVM_DEBUG(region->verifyRegion());
662 #endif
663 
664  updateStatistics(region);
665  return region;
666 }
667 
668 template <class Tr>
669 void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
670  BBtoBBMap *ShortCut) {
671  assert(entry);
672 
673  DomTreeNodeT *N = PDT->getNode(entry);
674  if (!N)
675  return;
676 
677  RegionT *lastRegion = nullptr;
678  BlockT *lastExit = entry;
679 
680  // As only a BasicBlock that postdominates entry can finish a region, walk the
681  // post dominance tree upwards.
682  while ((N = getNextPostDom(N, ShortCut))) {
683  BlockT *exit = N->getBlock();
684 
685  if (!exit)
686  break;
687 
688  if (isRegion(entry, exit)) {
689  RegionT *newRegion = createRegion(entry, exit);
690 
691  if (lastRegion)
692  newRegion->addSubRegion(lastRegion);
693 
694  lastRegion = newRegion;
695  lastExit = exit;
696  }
697 
698  // This can never be a region, so stop the search.
699  if (!DT->dominates(entry, exit))
700  break;
701  }
702 
703  // Tried to create regions from entry to lastExit. Next time take a
704  // shortcut from entry to lastExit.
705  if (lastExit != entry)
706  insertShortCut(entry, lastExit, ShortCut);
707 }
708 
709 template <class Tr>
710 void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
711  using FuncPtrT = std::add_pointer_t<FuncT>;
712 
713  BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
714  DomTreeNodeT *N = DT->getNode(entry);
715 
716  // Iterate over the dominance tree in post order to start with the small
717  // regions from the bottom of the dominance tree. If the small regions are
718  // detected first, detection of bigger regions is faster, as we can jump
719  // over the small regions.
720  for (auto DomNode : post_order(N))
721  findRegionsWithEntry(DomNode->getBlock(), ShortCut);
722 }
723 
724 template <class Tr>
725 typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
726  while (region->getParent())
727  region = region->getParent();
728 
729  return region;
730 }
731 
732 template <class Tr>
733 void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
734  BlockT *BB = N->getBlock();
735 
736  // Passed region exit
737  while (BB == region->getExit())
738  region = region->getParent();
739 
740  typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
741 
742  // This basic block is a start block of a region. It is already in the
743  // BBtoRegion relation. Only the child basic blocks have to be updated.
744  if (it != BBtoRegion.end()) {
745  RegionT *newRegion = it->second;
746  region->addSubRegion(getTopMostParent(newRegion));
747  region = newRegion;
748  } else {
749  BBtoRegion[BB] = region;
750  }
751 
752  for (DomTreeNodeBase<BlockT> *C : *N) {
753  buildRegionsTree(C, region);
754  }
755 }
756 
757 #ifdef EXPENSIVE_CHECKS
758 template <class Tr>
760 #else
761 template <class Tr>
763 #endif
764 
765 template <class Tr>
766 typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
768 
769 template <class Tr>
771  OS << "Region tree:\n";
772  TopLevelRegion->print(OS, true, 0, printStyle);
773  OS << "End region tree\n";
774 }
775 
776 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
777 template <class Tr>
778 void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
779 #endif
780 
781 template <class Tr>
783  BBtoRegion.clear();
784  if (TopLevelRegion)
785  delete TopLevelRegion;
786  TopLevelRegion = nullptr;
787 }
788 
789 template <class Tr>
791  // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
792  // -verify-region-info
794  return;
795 
796  TopLevelRegion->verifyRegionNest();
797 
798  verifyBBMap(TopLevelRegion);
799 }
800 
801 // Region pass manager support.
802 template <class Tr>
803 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
804  return BBtoRegion.lookup(BB);
805 }
806 
807 template <class Tr>
808 void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
809  BBtoRegion[BB] = R;
810 }
811 
812 template <class Tr>
813 typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
814  return getRegionFor(BB);
815 }
816 
817 template <class Tr>
818 typename RegionInfoBase<Tr>::BlockT *
820  BlockT *Exit = nullptr;
821 
822  while (true) {
823  // Get largest region that starts at BB.
824  RegionT *R = getRegionFor(BB);
825  while (R && R->getParent() && R->getParent()->getEntry() == BB)
826  R = R->getParent();
827 
828  // Get the single exit of BB.
829  if (R && R->getEntry() == BB)
830  Exit = R->getExit();
831  else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
832  Exit = *BlockTraits::child_begin(BB);
833  else // No single exit exists.
834  return Exit;
835 
836  // Get largest region that starts at Exit.
837  RegionT *ExitR = getRegionFor(Exit);
838  while (ExitR && ExitR->getParent() &&
839  ExitR->getParent()->getEntry() == Exit)
840  ExitR = ExitR->getParent();
841 
842  for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
843  InvBlockTraits::child_end(Exit))) {
844  if (!R->contains(Pred) && !ExitR->contains(Pred))
845  break;
846  }
847 
848  // This stops infinite cycles.
849  if (DT->dominates(Exit, BB))
850  break;
851 
852  BB = Exit;
853  }
854 
855  return Exit;
856 }
857 
858 template <class Tr>
859 typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
860  RegionT *B) const {
861  assert(A && B && "One of the Regions is NULL");
862 
863  if (A->contains(B))
864  return A;
865 
866  while (!B->contains(A))
867  B = B->getParent();
868 
869  return B;
870 }
871 
872 template <class Tr>
873 typename Tr::RegionT *
875  RegionT *ret = Regions.pop_back_val();
876 
877  for (RegionT *R : Regions)
878  ret = getCommonRegion(ret, R);
879 
880  return ret;
881 }
882 
883 template <class Tr>
884 typename Tr::RegionT *
886  RegionT *ret = getRegionFor(BBs.back());
887  BBs.pop_back();
888 
889  for (BlockT *BB : BBs)
890  ret = getCommonRegion(ret, getRegionFor(BB));
891 
892  return ret;
893 }
894 
895 template <class Tr>
896 void RegionInfoBase<Tr>::calculate(FuncT &F) {
897  using FuncPtrT = std::add_pointer_t<FuncT>;
898 
899  // ShortCut a function where for every BB the exit of the largest region
900  // starting with BB is stored. These regions can be threated as single BBS.
901  // This improves performance on linear CFGs.
902  BBtoBBMap ShortCut;
903 
904  scanForRegions(F, &ShortCut);
906  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
907 }
908 
909 } // end namespace llvm
910 
911 #undef DEBUG_TYPE
912 
913 #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:345
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:20
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RegionBase::addSubRegion
void addSubRegion(RegionT *SubRegion, bool moveChildren=false)
Add a new subregion to this Region.
Definition: RegionInfoImpl.h:379
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::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1748
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
verifyRegion
static void verifyRegion(const VPRegionBlock *Region)
Verify the CFG invariants of VPRegionBlock Region and its nested VPBlockBases.
Definition: VPlanVerifier.cpp:98
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:629
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:813
llvm::RegionBase::transferChildrenTo
void transferChildrenTo(RegionT *To)
Move all direct child nodes of this Region to another Region.
Definition: RegionInfoImpl.h:370
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:422
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_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:265
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:778
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:305
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:280
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:145
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: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:803
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:53
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::RegionBase::clearNodeCache
void clearNodeCache()
Clear the cache for BB RegionNodes.
Definition: RegionInfoImpl.h:518
llvm::RegionInfoBase::setRegionFor
void setRegionFor(BlockT *BB, RegionT *R)
Set the smallest region that surrounds a basic block.
Definition: RegionInfoImpl.h:808
llvm::RegionBase::element_begin
element_iterator element_begin()
Definition: RegionInfoImpl.h:300
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:324
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:770
llvm::df_iterator
Definition: DepthFirstIterator.h:86
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
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:859
llvm::RegionBase::print
void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const
Print the region.
Definition: RegionInfoImpl.h:476
A
* A
Definition: README_ALTIVEC.txt:89
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
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:445
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:512
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:1761
llvm::RegionBase::getDepth
unsigned getDepth() const
Get the nesting level of this Region.
Definition: RegionInfoImpl.h:435
llvm::RegionBase::getNode
RegionNodeT * getNode() const
Get the RegionNode representing the current Region.
Definition: RegionInfo.h:370
llvm::RegionInfoBase::verifyAnalysis
void verifyAnalysis() const
Definition: RegionInfoImpl.h:790
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:173
llvm::RegionBase::getNameStr
std::string getNameStr() const
Returns the name of the Region.
Definition: RegionInfoImpl.h:216
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::AMDGPU::VOPD::DST
@ DST
Definition: AMDGPUBaseInfo.h:523
llvm::FunctionReturnThunksKind::Keep
@ Keep
No function return thunk.
llvm::RegionBase::isSimple
bool isSimple() const
Is this a simple region?
Definition: RegionInfoImpl.h:211
llvm::RegionInfoBase::getMaxRegionExit
BlockT * getMaxRegionExit(BlockT *BB) const
Return the exit of the maximal refined region, that starts at a BasicBlock.
Definition: RegionInfoImpl.h:819
PostOrderIterator.h
SmallVector.h
llvm::RegionInfoBase::releaseMemory
void releaseMemory()
Definition: RegionInfoImpl.h:782
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:494
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
N
#define N
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
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:196
Debug.h
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:346
llvm::RegionBase::replaceExit
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:60