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-02-22 16:16:46 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/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       29493 : RegionBase<Tr>::RegionBase(BlockT *Entry, BlockT *Exit,
      45             :                            typename Tr::RegionInfoT *RInfo, DomTreeT *dt,
      46             :                            RegionT *Parent)
      47       58986 :     : RegionNodeBase<Tr>(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
      48             : 
      49             : template <class Tr>
      50       29318 : 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             :   BBNodeMap.clear();
      54       29318 : }
      55             : 
      56             : template <class Tr>
      57          10 : void RegionBase<Tr>::replaceEntry(BlockT *BB) {
      58             :   this->entry.setPointer(BB);
      59          10 : }
      60             : 
      61             : template <class Tr>
      62         976 : void RegionBase<Tr>::replaceExit(BlockT *BB) {
      63             :   assert(exit && "No exit to replace!");
      64         976 :   exit = BB;
      65         976 : }
      66             : 
      67             : template <class Tr>
      68           0 : void RegionBase<Tr>::replaceEntryRecursive(BlockT *NewEntry) {
      69             :   std::vector<RegionT *> RegionQueue;
      70             :   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             :     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         702 : void RegionBase<Tr>::replaceExitRecursive(BlockT *NewExit) {
      87             :   std::vector<RegionT *> RegionQueue;
      88             :   BlockT *OldExit = getExit();
      89             : 
      90        1404 :   RegionQueue.push_back(static_cast<RegionT *>(this));
      91        1470 :   while (!RegionQueue.empty()) {
      92         768 :     RegionT *R = RegionQueue.back();
      93             :     RegionQueue.pop_back();
      94             : 
      95         768 :     R->replaceExit(NewExit);
      96        1184 :     for (std::unique_ptr<RegionT> &Child : *R) {
      97         416 :       if (Child->getExit() == OldExit)
      98         132 :         RegionQueue.push_back(Child.get());
      99             :     }
     100             :   }
     101         702 : }
     102             : 
     103             : template <class Tr>
     104      969177 : bool RegionBase<Tr>::contains(const BlockT *B) const {
     105             :   BlockT *BB = const_cast<BlockT *>(B);
     106             : 
     107     1938344 :   if (!DT->getNode(BB))
     108             :     return false;
     109             : 
     110             :   BlockT *entry = getEntry(), *exit = getExit();
     111             : 
     112             :   // Toplevel region.
     113      969167 :   if (!exit)
     114             :     return true;
     115             : 
     116     1864831 :   return (DT->dominates(entry, BB) &&
     117      950362 :           !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
     118             : }
     119             : 
     120             : template <class Tr>
     121      291486 : 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      291486 :   if (!L)
     126       31290 :     return getExit() == nullptr;
     127             : 
     128      260196 :   if (!contains(L->getHeader()))
     129             :     return false;
     130             : 
     131             :   SmallVector<BlockT *, 8> ExitingBlocks;
     132      251882 :   L->getExitingBlocks(ExitingBlocks);
     133             : 
     134      758710 :   for (BlockT *BB : ExitingBlocks) {
     135      254742 :     if (!contains(BB))
     136             :       return false;
     137             :   }
     138             : 
     139             :   return true;
     140             : }
     141             : 
     142             : template <class Tr>
     143       27288 : typename Tr::LoopT *RegionBase<Tr>::outermostLoopInRegion(LoopT *L) const {
     144       27288 :   if (!contains(L))
     145             :     return nullptr;
     146             : 
     147       46636 :   while (L && contains(L->getParentLoop())) {
     148        9674 :     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             :   LoopT *L = LI->getLoopFor(BB);
     159           0 :   return outermostLoopInRegion(L);
     160             : }
     161             : 
     162             : template <class Tr>
     163        9060 : typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getEnteringBlock() const {
     164             :   BlockT *entry = getEntry();
     165             :   BlockT *enteringBlock = nullptr;
     166             : 
     167       32590 :   for (BlockT *Pred : make_range(InvBlockTraits::child_begin(entry),
     168             :                                  InvBlockTraits::child_end(entry))) {
     169       29980 :     if (DT->getNode(Pred) && !contains(Pred)) {
     170        8822 :       if (enteringBlock)
     171         521 :         return nullptr;
     172             : 
     173             :       enteringBlock = Pred;
     174             :     }
     175             :   }
     176             : 
     177        8539 :   return enteringBlock;
     178             : }
     179             : 
     180             : template <class Tr>
     181           0 : bool RegionBase<Tr>::getExitingBlocks(
     182             :     SmallVectorImpl<BlockT *> &Exitings) const {
     183             :   bool CoverAll = true;
     184             : 
     185           0 :   if (!exit)
     186             :     return CoverAll;
     187             : 
     188           0 :   for (PredIterTy PI = InvBlockTraits::child_begin(exit),
     189             :                   PE = InvBlockTraits::child_end(exit);
     190           0 :        PI != PE; ++PI) {
     191           0 :     BlockT *Pred = *PI;
     192           0 :     if (contains(Pred)) {
     193           0 :       Exitings.push_back(Pred);
     194           0 :       continue;
     195             :     }
     196             : 
     197             :     CoverAll = false;
     198             :   }
     199             : 
     200           0 :   return CoverAll;
     201             : }
     202             : 
     203             : template <class Tr>
     204        9718 : typename RegionBase<Tr>::BlockT *RegionBase<Tr>::getExitingBlock() const {
     205             :   BlockT *exit = getExit();
     206             :   BlockT *exitingBlock = nullptr;
     207             : 
     208        9718 :   if (!exit)
     209             :     return nullptr;
     210             : 
     211       30683 :   for (BlockT *Pred : make_range(InvBlockTraits::child_begin(exit),
     212             :                                  InvBlockTraits::child_end(exit))) {
     213       12941 :     if (contains(Pred)) {
     214       11388 :       if (exitingBlock)
     215        1678 :         return nullptr;
     216             : 
     217             :       exitingBlock = Pred;
     218             :     }
     219             :   }
     220             : 
     221        8032 :   return exitingBlock;
     222             : }
     223             : 
     224             : template <class Tr>
     225       28197 : bool RegionBase<Tr>::isSimple() const {
     226       28197 :   return !isTopLevelRegion() && getEnteringBlock() && getExitingBlock();
     227             : }
     228             : 
     229             : template <class Tr>
     230        9205 : std::string RegionBase<Tr>::getNameStr() const {
     231             :   std::string exitName;
     232             :   std::string entryName;
     233             : 
     234       18410 :   if (getEntry()->getName().empty()) {
     235          52 :     raw_string_ostream OS(entryName);
     236             : 
     237          52 :     getEntry()->printAsOperand(OS, false);
     238             :   } else
     239       27459 :     entryName = getEntry()->getName();
     240             : 
     241        9205 :   if (getExit()) {
     242       14666 :     if (getExit()->getName().empty()) {
     243          38 :       raw_string_ostream OS(exitName);
     244             : 
     245          38 :       getExit()->printAsOperand(OS, false);
     246             :     } else
     247       21885 :       exitName = getExit()->getName();
     248             :   } else
     249             :     exitName = "<Function Return>";
     250             : 
     251       27615 :   return entryName + " => " + exitName;
     252             : }
     253             : 
     254             : template <class Tr>
     255         513 : void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
     256         513 :   if (!contains(BB))
     257           0 :     report_fatal_error("Broken region found: enumerated BB not in region!");
     258             : 
     259             :   BlockT *entry = getEntry(), *exit = getExit();
     260             : 
     261        1226 :   for (BlockT *Succ :
     262             :        make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
     263         713 :     if (!contains(Succ) && exit != Succ)
     264           0 :       report_fatal_error("Broken region found: edges leaving the region must go "
     265             :                          "to the exit node!");
     266             :   }
     267             : 
     268         513 :   if (entry != BB) {
     269        1413 :     for (BlockT *Pred : make_range(InvBlockTraits::child_begin(BB),
     270             :                                    InvBlockTraits::child_end(BB))) {
     271         582 :       if (!contains(Pred))
     272           1 :         report_fatal_error("Broken region found: edges entering the region must "
     273             :                            "go to the entry node!");
     274             :     }
     275             :   }
     276         512 : }
     277             : 
     278             : template <class Tr>
     279         513 : void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
     280             :   BlockT *exit = getExit();
     281             : 
     282             :   visited->insert(BB);
     283             : 
     284         513 :   verifyBBInRegion(BB);
     285             : 
     286        1207 :   for (BlockT *Succ :
     287        1024 :        make_range(BlockTraits::child_begin(BB), BlockTraits::child_end(BB))) {
     288        1336 :     if (Succ != exit && visited->find(Succ) == visited->end())
     289         416 :       verifyWalk(Succ, visited);
     290             :   }
     291         500 : }
     292             : 
     293             : template <class Tr>
     294       46598 : void RegionBase<Tr>::verifyRegion() const {
     295             :   // Only do verification when user wants to, otherwise this expensive check
     296             :   // will be invoked by PMDataManager::verifyPreservedAnalysis when
     297             :   // a regionpass (marked PreservedAll) finish.
     298       46598 :   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
     299       46501 :     return;
     300             : 
     301             :   std::set<BlockT *> visited;
     302          97 :   verifyWalk(getEntry(), &visited);
     303             : }
     304             : 
     305             : template <class Tr>
     306           0 : void RegionBase<Tr>::verifyRegionNest() const {
     307           0 :   for (const std::unique_ptr<RegionT> &R : *this)
     308           0 :     R->verifyRegionNest();
     309             : 
     310           0 :   verifyRegion();
     311           0 : }
     312             : 
     313             : template <class Tr>
     314        5980 : typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_begin() {
     315        5980 :   return GraphTraits<RegionT *>::nodes_begin(static_cast<RegionT *>(this));
     316             : }
     317             : 
     318             : template <class Tr>
     319        5980 : typename RegionBase<Tr>::element_iterator RegionBase<Tr>::element_end() {
     320        5980 :   return GraphTraits<RegionT *>::nodes_end(static_cast<RegionT *>(this));
     321             : }
     322             : 
     323             : template <class Tr>
     324             : typename RegionBase<Tr>::const_element_iterator
     325           4 : RegionBase<Tr>::element_begin() const {
     326             :   return GraphTraits<const RegionT *>::nodes_begin(
     327           4 :       static_cast<const RegionT *>(this));
     328             : }
     329             : 
     330             : template <class Tr>
     331             : typename RegionBase<Tr>::const_element_iterator
     332           4 : RegionBase<Tr>::element_end() const {
     333             :   return GraphTraits<const RegionT *>::nodes_end(
     334           4 :       static_cast<const RegionT *>(this));
     335             : }
     336             : 
     337             : template <class Tr>
     338       97407 : typename Tr::RegionT *RegionBase<Tr>::getSubRegionNode(BlockT *BB) const {
     339             :   using RegionT = typename Tr::RegionT;
     340             : 
     341       97407 :   RegionT *R = RI->getRegionFor(BB);
     342             : 
     343       97407 :   if (!R || R == this)
     344             :     return nullptr;
     345             : 
     346             :   // If we pass the BB out of this region, that means our code is broken.
     347             :   assert(contains(R) && "BB not in current region!");
     348             : 
     349       33356 :   while (contains(R->getParent()) && R->getParent() != this)
     350             :     R = R->getParent();
     351             : 
     352       16248 :   if (R->getEntry() != BB)
     353             :     return nullptr;
     354             : 
     355       16248 :   return R;
     356             : }
     357             : 
     358             : template <class Tr>
     359       81539 : typename Tr::RegionNodeT *RegionBase<Tr>::getBBNode(BlockT *BB) const {
     360             :   assert(contains(BB) && "Can get BB node out of this region!");
     361             : 
     362             :   typename BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
     363             : 
     364       81539 :   if (at == BBNodeMap.end()) {
     365             :     auto Deconst = const_cast<RegionBase<Tr> *>(this);
     366             :     typename BBNodeMapT::value_type V = {
     367             :         BB,
     368             :         llvm::make_unique<RegionNodeT>(static_cast<RegionT *>(Deconst), BB)};
     369             :     at = BBNodeMap.insert(std::move(V)).first;
     370             :   }
     371       81539 :   return at->second.get();
     372             : }
     373             : 
     374             : template <class Tr>
     375       97407 : typename Tr::RegionNodeT *RegionBase<Tr>::getNode(BlockT *BB) const {
     376             :   assert(contains(BB) && "Can get BB node out of this region!");
     377       97407 :   if (RegionT *Child = getSubRegionNode(BB))
     378       16248 :     return Child->getNode();
     379             : 
     380       81159 :   return getBBNode(BB);
     381             : }
     382             : 
     383             : template <class Tr>
     384           0 : void RegionBase<Tr>::transferChildrenTo(RegionT *To) {
     385           0 :   for (std::unique_ptr<RegionT> &R : *this) {
     386           0 :     R->parent = To;
     387           0 :     To->children.push_back(std::move(R));
     388             :   }
     389             :   children.clear();
     390           0 : }
     391             : 
     392             : template <class Tr>
     393        7426 : void RegionBase<Tr>::addSubRegion(RegionT *SubRegion, bool moveChildren) {
     394             :   assert(!SubRegion->parent && "SubRegion already has a parent!");
     395             :   assert(llvm::find_if(*this,
     396             :                        [&](const std::unique_ptr<RegionT> &R) {
     397             :                          return R.get() == SubRegion;
     398             :                        }) == children.end() &&
     399             :          "Subregion already exists!");
     400             : 
     401        7426 :   SubRegion->parent = static_cast<RegionT *>(this);
     402       14852 :   children.push_back(std::unique_ptr<RegionT>(SubRegion));
     403             : 
     404        7426 :   if (!moveChildren)
     405        6740 :     return;
     406             : 
     407             :   assert(SubRegion->children.empty() &&
     408             :          "SubRegions that contain children are not supported");
     409             : 
     410        9026 :   for (RegionNodeT *Element : elements()) {
     411        3484 :     if (!Element->isSubRegion()) {
     412             :       BlockT *BB = Element->template getNodeAs<BlockT>();
     413             : 
     414        2324 :       if (SubRegion->contains(BB))
     415         784 :         RI->setRegionFor(BB, SubRegion);
     416             :     }
     417             :   }
     418             : 
     419         686 :   std::vector<std::unique_ptr<RegionT>> Keep;
     420        2532 :   for (std::unique_ptr<RegionT> &R : *this) {
     421        5482 :     if (SubRegion->contains(R.get()) && R.get() != SubRegion) {
     422        1104 :       R->parent = SubRegion;
     423        1104 :       SubRegion->children.push_back(std::move(R));
     424             :     } else
     425             :       Keep.push_back(std::move(R));
     426             :   }
     427             : 
     428             :   children.clear();
     429         686 :   children.insert(
     430             :       children.begin(),
     431             :       std::move_iterator<typename RegionSet::iterator>(Keep.begin()),
     432             :       std::move_iterator<typename RegionSet::iterator>(Keep.end()));
     433             : }
     434             : 
     435             : template <class Tr>
     436           0 : typename Tr::RegionT *RegionBase<Tr>::removeSubRegion(RegionT *Child) {
     437             :   assert(Child->parent == this && "Child is not a child of this region!");
     438           0 :   Child->parent = nullptr;
     439             :   typename RegionSet::iterator I =
     440             :       llvm::find_if(children, [&](const std::unique_ptr<RegionT> &R) {
     441           0 :         return R.get() == Child;
     442             :       });
     443             :   assert(I != children.end() && "Region does not exit. Unable to remove.");
     444           0 :   children.erase(children.begin() + (I - begin()));
     445           0 :   return Child;
     446             : }
     447             : 
     448             : template <class Tr>
     449           6 : unsigned RegionBase<Tr>::getDepth() const {
     450             :   unsigned Depth = 0;
     451             : 
     452          26 :   for (RegionT *R = getParent(); R != nullptr; R = R->getParent())
     453          10 :     ++Depth;
     454             : 
     455           6 :   return Depth;
     456             : }
     457             : 
     458             : template <class Tr>
     459        3752 : typename Tr::RegionT *RegionBase<Tr>::getExpandedRegion() const {
     460        3752 :   unsigned NumSuccessors = Tr::getNumSuccessors(exit);
     461             : 
     462        3752 :   if (NumSuccessors == 0)
     463             :     return nullptr;
     464             : 
     465        1472 :   RegionT *R = RI->getRegionFor(exit);
     466             : 
     467        1472 :   if (R->getEntry() != exit) {
     468        2956 :     for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
     469             :                                    InvBlockTraits::child_end(getExit())))
     470        1130 :       if (!contains(Pred))
     471          34 :         return nullptr;
     472        1792 :     if (Tr::getNumSuccessors(exit) == 1)
     473        1632 :       return new RegionT(getEntry(), *BlockTraits::child_begin(exit), RI, DT);
     474             :     return nullptr;
     475             :   }
     476             : 
     477        1104 :   while (R->getParent() && R->getParent()->getEntry() == exit)
     478             :     R = R->getParent();
     479             : 
     480        2084 :   for (BlockT *Pred : make_range(InvBlockTraits::child_begin(getExit()),
     481             :                                  InvBlockTraits::child_end(getExit()))) {
     482        1062 :     if (!(contains(Pred) || R->contains(Pred)))
     483          62 :       return nullptr;
     484             :   }
     485             : 
     486         480 :   return new RegionT(getEntry(), R->getExit(), RI, DT);
     487             : }
     488             : 
     489             : template <class Tr>
     490          19 : void RegionBase<Tr>::print(raw_ostream &OS, bool print_tree, unsigned level,
     491             :                            PrintStyle Style) const {
     492          19 :   if (print_tree)
     493          57 :     OS.indent(level * 2) << '[' << level << "] " << getNameStr();
     494             :   else
     495           0 :     OS.indent(level * 2) << getNameStr();
     496             : 
     497             :   OS << '\n';
     498             : 
     499          19 :   if (Style != PrintNone) {
     500           8 :     OS.indent(level * 2) << "{\n";
     501           8 :     OS.indent(level * 2 + 2);
     502             : 
     503           8 :     if (Style == PrintBB) {
     504          18 :       for (const auto *BB : blocks())
     505          10 :         OS << BB->getName() << ", "; // TODO: remove the last ","
     506           4 :     } else if (Style == PrintRN) {
     507          28 :       for (const RegionNodeT *Element : elements()) {
     508           8 :         OS << *Element << ", "; // TODO: remove the last ",
     509             :       }
     510             :     }
     511             : 
     512             :     OS << '\n';
     513             :   }
     514             : 
     515          19 :   if (print_tree) {
     516          28 :     for (const std::unique_ptr<RegionT> &R : *this)
     517           9 :       R->print(OS, print_tree, level + 1, Style);
     518             :   }
     519             : 
     520          19 :   if (Style != PrintNone)
     521           8 :     OS.indent(level * 2) << "} \n";
     522          19 : }
     523             : 
     524             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     525             : template <class Tr>
     526             : void RegionBase<Tr>::dump() const {
     527             :   print(dbgs(), true, getDepth(), RegionInfoBase<Tr>::printStyle);
     528             : }
     529             : #endif
     530             : 
     531             : template <class Tr>
     532       61687 : void RegionBase<Tr>::clearNodeCache() {
     533             :   BBNodeMap.clear();
     534       95701 :   for (std::unique_ptr<RegionT> &R : *this)
     535       34014 :     R->clearNodeCache();
     536       61687 : }
     537             : 
     538             : //===----------------------------------------------------------------------===//
     539             : // RegionInfoBase implementation
     540             : //
     541             : 
     542             : template <class Tr>
     543             : RegionInfoBase<Tr>::RegionInfoBase() = default;
     544             : 
     545             : template <class Tr>
     546        4476 : RegionInfoBase<Tr>::~RegionInfoBase() {
     547        4476 :   releaseMemory();
     548        8952 : }
     549             : 
     550             : template <class Tr>
     551           0 : void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
     552             :   assert(R && "Re must be non-null");
     553           0 :   for (const typename Tr::RegionNodeT *Element : R->elements()) {
     554           0 :     if (Element->isSubRegion()) {
     555           0 :       const RegionT *SR = Element->template getNodeAs<RegionT>();
     556           0 :       verifyBBMap(SR);
     557             :     } else {
     558             :       BlockT *BB = Element->template getNodeAs<BlockT>();
     559           0 :       if (getRegionFor(BB) != R)
     560           0 :         report_fatal_error("BB map does not match region nesting");
     561             :     }
     562             :   }
     563           0 : }
     564             : 
     565             : template <class Tr>
     566        6754 : bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
     567             :                                              BlockT *exit) const {
     568       27260 :   for (BlockT *P : make_range(InvBlockTraits::child_begin(BB),
     569             :                               InvBlockTraits::child_end(BB))) {
     570       13756 :     if (DT->dominates(entry, P) && !DT->dominates(exit, P))
     571           4 :       return false;
     572             :   }
     573             : 
     574        6750 :   return true;
     575             : }
     576             : 
     577             : template <class Tr>
     578       26545 : bool RegionInfoBase<Tr>::isRegion(BlockT *entry, BlockT *exit) const {
     579             :   assert(entry && exit && "entry and exit must not be null!");
     580             : 
     581             :   using DST = typename DomFrontierT::DomSetType;
     582             : 
     583       26545 :   DST *entrySuccs = &DF->find(entry)->second;
     584             : 
     585             :   // Exit is the header of a loop that contains the entry. In this case,
     586             :   // the dominance frontier must only contain the exit.
     587       26545 :   if (!DT->dominates(entry, exit)) {
     588             :     for (typename DST::iterator SI = entrySuccs->begin(),
     589             :                                 SE = entrySuccs->end();
     590       16439 :          SI != SE; ++SI) {
     591       11001 :       if (*SI != exit && *SI != entry)
     592             :         return false;
     593             :     }
     594             : 
     595             :     return true;
     596             :   }
     597             : 
     598       16058 :   DST *exitSuccs = &DF->find(exit)->second;
     599             : 
     600             :   // Do not allow edges leaving the region.
     601       27749 :   for (BlockT *Succ : *entrySuccs) {
     602       13381 :     if (Succ == exit || Succ == entry)
     603        4941 :       continue;
     604        8440 :     if (exitSuccs->find(Succ) == exitSuccs->end())
     605             :       return false;
     606        6754 :     if (!isCommonDomFrontier(Succ, entry, exit))
     607             :       return false;
     608             :   }
     609             : 
     610             :   // Do not allow edges pointing into the region.
     611       25605 :   for (BlockT *Succ : *exitSuccs) {
     612       11260 :     if (DT->properlyDominates(entry, Succ) && Succ != exit)
     613             :       return false;
     614             :   }
     615             : 
     616             :   return true;
     617             : }
     618             : 
     619             : template <class Tr>
     620       18920 : void RegionInfoBase<Tr>::insertShortCut(BlockT *entry, BlockT *exit,
     621             :                                         BBtoBBMap *ShortCut) const {
     622             :   assert(entry && exit && "entry and exit must not be null!");
     623             : 
     624       18920 :   typename BBtoBBMap::iterator e = ShortCut->find(exit);
     625             : 
     626       18920 :   if (e == ShortCut->end())
     627             :     // No further region at exit available.
     628        8972 :     (*ShortCut)[entry] = exit;
     629             :   else {
     630             :     // We found a region e that starts at exit. Therefore (entry, e->second)
     631             :     // is also a region, that is larger than (entry, exit). Insert the
     632             :     // larger one.
     633        9948 :     BlockT *BB = e->second;
     634        9948 :     (*ShortCut)[entry] = BB;
     635             :   }
     636       18920 : }
     637             : 
     638             : template <class Tr>
     639             : typename Tr::DomTreeNodeT *
     640       58135 : RegionInfoBase<Tr>::getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const {
     641       58135 :   typename BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
     642             : 
     643       58135 :   if (e == ShortCut->end())
     644       47831 :     return N->getIDom();
     645             : 
     646       20608 :   return PDT->getNode(e->second)->getIDom();
     647             : }
     648             : 
     649             : template <class Tr>
     650       19783 : bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
     651             :   assert(entry && exit && "entry and exit must not be null!");
     652             : 
     653           0 :   unsigned num_successors =
     654             :       BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
     655             : 
     656       33444 :   if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
     657             :     return true;
     658             : 
     659             :   return false;
     660             : }
     661             : 
     662             : template <class Tr>
     663       19783 : typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,
     664             :                                                        BlockT *exit) {
     665             :   assert(entry && exit && "entry and exit must not be null!");
     666             : 
     667       19783 :   if (isTrivialRegion(entry, exit))
     668             :     return nullptr;
     669             : 
     670             :   RegionT *region =
     671        6740 :       new RegionT(entry, exit, static_cast<RegionInfoT *>(this), DT);
     672       13480 :   BBtoRegion.insert({entry, region});
     673             : 
     674             : #ifdef EXPENSIVE_CHECKS
     675             :   region->verifyRegion();
     676             : #else
     677             :   DEBUG(region->verifyRegion());
     678             : #endif
     679             : 
     680        6740 :   updateStatistics(region);
     681        6740 :   return region;
     682             : }
     683             : 
     684             : template <class Tr>
     685       42077 : void RegionInfoBase<Tr>::findRegionsWithEntry(BlockT *entry,
     686             :                                               BBtoBBMap *ShortCut) {
     687             :   assert(entry);
     688             : 
     689       42077 :   DomTreeNodeT *N = PDT->getNode(entry);
     690       42077 :   if (!N)
     691             :     return;
     692             : 
     693             :   RegionT *lastRegion = nullptr;
     694             :   BlockT *lastExit = entry;
     695             : 
     696             :   // As only a BasicBlock that postdominates entry can finish a region, walk the
     697             :   // post dominance tree upwards.
     698       58135 :   while ((N = getNextPostDom(N, ShortCut))) {
     699       58135 :     BlockT *exit = N->getBlock();
     700             : 
     701       58135 :     if (!exit)
     702             :       break;
     703             : 
     704       26545 :     if (isRegion(entry, exit)) {
     705       19783 :       RegionT *newRegion = createRegion(entry, exit);
     706             : 
     707       19783 :       if (lastRegion)
     708         245 :         newRegion->addSubRegion(lastRegion);
     709             : 
     710             :       lastRegion = newRegion;
     711             :       lastExit = exit;
     712             :     }
     713             : 
     714             :     // This can never be a region, so stop the search.
     715       26545 :     if (!DT->dominates(entry, exit))
     716             :       break;
     717             :   }
     718             : 
     719             :   // Tried to create regions from entry to lastExit.  Next time take a
     720             :   // shortcut from entry to lastExit.
     721       42077 :   if (lastExit != entry)
     722       18920 :     insertShortCut(entry, lastExit, ShortCut);
     723             : }
     724             : 
     725             : template <class Tr>
     726       21457 : void RegionInfoBase<Tr>::scanForRegions(FuncT &F, BBtoBBMap *ShortCut) {
     727             :   using FuncPtrT = typename std::add_pointer<FuncT>::type;
     728             : 
     729             :   BlockT *entry = GraphTraits<FuncPtrT>::getEntryNode(&F);
     730       21457 :   DomTreeNodeT *N = DT->getNode(entry);
     731             : 
     732             :   // Iterate over the dominance tree in post order to start with the small
     733             :   // regions from the bottom of the dominance tree.  If the small regions are
     734             :   // detected first, detection of bigger regions is faster, as we can jump
     735             :   // over the small regions.
     736      148525 :   for (auto DomNode : post_order(N))
     737       42077 :     findRegionsWithEntry(DomNode->getBlock(), ShortCut);
     738       21457 : }
     739             : 
     740             : template <class Tr>
     741        6495 : typename Tr::RegionT *RegionInfoBase<Tr>::getTopMostParent(RegionT *region) {
     742        6740 :   while (region->getParent())
     743             :     region = region->getParent();
     744             : 
     745        6495 :   return region;
     746             : }
     747             : 
     748             : template <class Tr>
     749       42077 : void RegionInfoBase<Tr>::buildRegionsTree(DomTreeNodeT *N, RegionT *region) {
     750       42077 :   BlockT *BB = N->getBlock();
     751             : 
     752             :   // Passed region exit
     753       54291 :   while (BB == region->getExit())
     754             :     region = region->getParent();
     755             : 
     756       42077 :   typename BBtoRegionMap::iterator it = BBtoRegion.find(BB);
     757             : 
     758             :   // This basic block is a start block of a region. It is already in the
     759             :   // BBtoRegion relation. Only the child basic blocks have to be updated.
     760       42077 :   if (it != BBtoRegion.end()) {
     761        6495 :     RegionT *newRegion = it->second;
     762        6495 :     region->addSubRegion(getTopMostParent(newRegion));
     763             :     region = newRegion;
     764             :   } else {
     765       35582 :     BBtoRegion[BB] = region;
     766             :   }
     767             : 
     768       62697 :   for (DomTreeNodeBase<BlockT> *C : *N) {
     769       20620 :     buildRegionsTree(C, region);
     770             :   }
     771       42077 : }
     772             : 
     773             : #ifdef EXPENSIVE_CHECKS
     774             : template <class Tr>
     775             : bool RegionInfoBase<Tr>::VerifyRegionInfo = true;
     776             : #else
     777             : template <class Tr>
     778             : bool RegionInfoBase<Tr>::VerifyRegionInfo = false;
     779             : #endif
     780             : 
     781             : template <class Tr>
     782             : typename Tr::RegionT::PrintStyle RegionInfoBase<Tr>::printStyle =
     783             :     RegionBase<Tr>::PrintNone;
     784             : 
     785             : template <class Tr>
     786          10 : void RegionInfoBase<Tr>::print(raw_ostream &OS) const {
     787          10 :   OS << "Region tree:\n";
     788          10 :   TopLevelRegion->print(OS, true, 0, printStyle);
     789          10 :   OS << "End region tree\n";
     790          10 : }
     791             : 
     792             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     793             : template <class Tr>
     794             : void RegionInfoBase<Tr>::dump() const { print(dbgs()); }
     795             : #endif
     796             : 
     797             : template <class Tr>
     798       47333 : void RegionInfoBase<Tr>::releaseMemory() {
     799       47333 :   BBtoRegion.clear();
     800       47333 :   if (TopLevelRegion)
     801       21412 :     delete TopLevelRegion;
     802       47333 :   TopLevelRegion = nullptr;
     803       47333 : }
     804             : 
     805             : template <class Tr>
     806           0 : void RegionInfoBase<Tr>::verifyAnalysis() const {
     807             :   // Do only verify regions if explicitely activated using EXPENSIVE_CHECKS or
     808             :   // -verify-region-info
     809           0 :   if (!RegionInfoBase<Tr>::VerifyRegionInfo)
     810             :     return;
     811             : 
     812           0 :   TopLevelRegion->verifyRegionNest();
     813             : 
     814           0 :   verifyBBMap(TopLevelRegion);
     815             : }
     816             : 
     817             : // Region pass manager support.
     818             : template <class Tr>
     819      137511 : typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
     820      137511 :   typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
     821      137511 :   return I != BBtoRegion.end() ? I->second : nullptr;
     822             : }
     823             : 
     824             : template <class Tr>
     825        8982 : void RegionInfoBase<Tr>::setRegionFor(BlockT *BB, RegionT *R) {
     826       17964 :   BBtoRegion[BB] = R;
     827        8982 : }
     828             : 
     829             : template <class Tr>
     830           0 : typename Tr::RegionT *RegionInfoBase<Tr>::operator[](BlockT *BB) const {
     831           0 :   return getRegionFor(BB);
     832             : }
     833             : 
     834             : template <class Tr>
     835             : typename RegionInfoBase<Tr>::BlockT *
     836           0 : RegionInfoBase<Tr>::getMaxRegionExit(BlockT *BB) const {
     837             :   BlockT *Exit = nullptr;
     838             : 
     839             :   while (true) {
     840             :     // Get largest region that starts at BB.
     841           0 :     RegionT *R = getRegionFor(BB);
     842           0 :     while (R && R->getParent() && R->getParent()->getEntry() == BB)
     843             :       R = R->getParent();
     844             : 
     845             :     // Get the single exit of BB.
     846           0 :     if (R && R->getEntry() == BB)
     847             :       Exit = R->getExit();
     848           0 :     else if (++BlockTraits::child_begin(BB) == BlockTraits::child_end(BB))
     849           0 :       Exit = *BlockTraits::child_begin(BB);
     850             :     else // No single exit exists.
     851             :       return Exit;
     852             : 
     853             :     // Get largest region that starts at Exit.
     854           0 :     RegionT *ExitR = getRegionFor(Exit);
     855           0 :     while (ExitR && ExitR->getParent() &&
     856             :            ExitR->getParent()->getEntry() == Exit)
     857             :       ExitR = ExitR->getParent();
     858             : 
     859           0 :     for (BlockT *Pred : make_range(InvBlockTraits::child_begin(Exit),
     860             :                                    InvBlockTraits::child_end(Exit))) {
     861           0 :       if (!R->contains(Pred) && !ExitR->contains(Pred))
     862             :         break;
     863             :     }
     864             : 
     865             :     // This stops infinite cycles.
     866           0 :     if (DT->dominates(Exit, BB))
     867             :       break;
     868             : 
     869             :     BB = Exit;
     870             :   }
     871             : 
     872             :   return Exit;
     873             : }
     874             : 
     875             : template <class Tr>
     876           0 : typename Tr::RegionT *RegionInfoBase<Tr>::getCommonRegion(RegionT *A,
     877             :                                                           RegionT *B) const {
     878             :   assert(A && B && "One of the Regions is NULL");
     879             : 
     880           0 :   if (A->contains(B))
     881             :     return A;
     882             : 
     883           0 :   while (!B->contains(A))
     884             :     B = B->getParent();
     885             : 
     886             :   return B;
     887             : }
     888             : 
     889             : template <class Tr>
     890             : typename Tr::RegionT *
     891           0 : RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const {
     892           0 :   RegionT *ret = Regions.back();
     893             :   Regions.pop_back();
     894             : 
     895           0 :   for (RegionT *R : Regions)
     896           0 :     ret = getCommonRegion(ret, R);
     897             : 
     898           0 :   return ret;
     899             : }
     900             : 
     901             : template <class Tr>
     902             : typename Tr::RegionT *
     903           0 : RegionInfoBase<Tr>::getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const {
     904           0 :   RegionT *ret = getRegionFor(BBs.back());
     905             :   BBs.pop_back();
     906             : 
     907           0 :   for (BlockT *BB : BBs)
     908           0 :     ret = getCommonRegion(ret, getRegionFor(BB));
     909             : 
     910           0 :   return ret;
     911             : }
     912             : 
     913             : template <class Tr>
     914       21457 : void RegionInfoBase<Tr>::calculate(FuncT &F) {
     915             :   using FuncPtrT = typename std::add_pointer<FuncT>::type;
     916             : 
     917             :   // ShortCut a function where for every BB the exit of the largest region
     918             :   // starting with BB is stored. These regions can be threated as single BBS.
     919             :   // This improves performance on linear CFGs.
     920             :   BBtoBBMap ShortCut;
     921             : 
     922       21457 :   scanForRegions(F, &ShortCut);
     923             :   BlockT *BB = GraphTraits<FuncPtrT>::getEntryNode(&F);
     924       42914 :   buildRegionsTree(DT->getNode(BB), TopLevelRegion);
     925       21457 : }
     926             : 
     927             : } // end namespace llvm
     928             : 
     929             : #undef DEBUG_TYPE
     930             : 
     931             : #endif // LLVM_ANALYSIS_REGIONINFOIMPL_H

Generated by: LCOV version 1.13