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

Generated by: LCOV version 1.13