LCOV - code coverage report
Current view: top level - include/llvm/Analysis - RegionInfoImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 251 328 76.5 %
Date: 2018-07-13 00:08:38 Functions: 43 114 37.7 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13