Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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"
  15. #include "llvm/ADT/PostOrderIterator.h"
  16. #include "llvm/ADT/STLExtras.h"
  17. #include "llvm/ADT/SmallVector.h"
  18. #include "llvm/Analysis/LoopInfo.h"
  19. #include "llvm/Analysis/PostDominators.h"
  20. #include "llvm/Analysis/RegionInfo.h"
  21. #include "llvm/Analysis/RegionIterator.h"
  22. #include "llvm/Config/llvm-config.h"
  23. #include "llvm/Support/Debug.h"
  24. #include "llvm/Support/ErrorHandling.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>
  48. RegionBase<Tr>::~RegionBase() {
  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>
  55. void RegionBase<Tr>::replaceEntry(BlockT *BB) {
  56.   this->entry.setPointer(BB);
  57. }
  58.  
  59. template <class Tr>
  60. void RegionBase<Tr>::replaceExit(BlockT *BB) {
  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>
  173. bool RegionBase<Tr>::getExitingBlocks(
  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>
  211. bool RegionBase<Tr>::isSimple() const {
  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>
  280. void RegionBase<Tr>::verifyRegion() const {
  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.
  284.   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
  285.     return;
  286.  
  287.   std::set<BlockT *> visited;
  288.   verifyWalk(getEntry(), &visited);
  289. }
  290.  
  291. template <class Tr>
  292. void RegionBase<Tr>::verifyRegionNest() const {
  293.   for (const std::unique_ptr<RegionT> &R : *this)
  294.     R->verifyRegionNest();
  295.  
  296.   verifyRegion();
  297. }
  298.  
  299. template <class Tr>
  300. typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
  301.   return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
  302. }
  303.  
  304. template <class Tr>
  305. typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
  306.   return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
  307. }
  308.  
  309. template <class Tr>
  310. typename RegionBase<Tr>::const_element_iterator
  311. RegionBase<Tr>::element_begin() const {
  312.   return GraphTraits<const RegionT *>::nodes_begin(
  313.       static_cast<const RegionT *>(this));
  314. }
  315.  
  316. template <class Tr>
  317. typename RegionBase<Tr>::const_element_iterator
  318. RegionBase<Tr>::element_end() const {
  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>
  370. void RegionBase<Tr>::transferChildrenTo(RegionT *To) {
  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>
  518. void RegionBase<Tr>::clearNodeCache() {
  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>
  529. RegionInfoBase<Tr>::RegionInfoBase() = default;
  530.  
  531. template <class Tr>
  532. RegionInfoBase<Tr>::~RegionInfoBase() {
  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>
  759. bool RegionInfoBase<Tr>::VerifyRegionInfo = true;
  760. #else
  761. template <class Tr>
  762. bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
  763. #endif
  764.  
  765. template <class Tr>
  766. typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
  767.     RegionBase<Tr>::PrintNone;
  768.  
  769. template <class Tr>
  770. void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
  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> void RegionInfoBase<Tr>::releaseMemory() {
  782.   BBtoRegion.clear();
  783.   if (TopLevelRegion) {
  784.     delete TopLevelRegion;
  785.     TopLevelRegion = nullptr;
  786.   }
  787. }
  788.  
  789. template <class Tr>
  790. void RegionInfoBase<Tr>::verifyAnalysis() const {
  791.   // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
  792.   // -verify-region-info
  793.   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
  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 *
  819. RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const {
  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 *
  874. RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const {
  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 *
  885. RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const {
  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);
  905.   BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
  906.   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
  907. }
  908.  
  909. } // end namespace llvm
  910.  
  911. #undef DEBUG_TYPE
  912.  
  913. #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H
  914.