LCOV - code coverage report
Current view: top level - include/llvm/Analysis - RegionInfo.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 58 90 64.4 %
Date: 2017-09-14 15:23:50 Functions: 14 72 19.4 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- RegionInfo.h - SESE region 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             : //
      10             : // Calculate a program structure tree built out of single entry single exit
      11             : // regions.
      12             : // The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
      13             : // David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
      14             : // Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
      15             : // Koehler - 2009".
      16             : // The algorithm to calculate these data structures however is completely
      17             : // different, as it takes advantage of existing information already available
      18             : // in (Post)dominace tree and dominance frontier passes. This leads to a simpler
      19             : // and in practice hopefully better performing algorithm. The runtime of the
      20             : // algorithms described in the papers above are both linear in graph size,
      21             : // O(V+E), whereas this algorithm is not, as the dominance frontier information
      22             : // itself is not, but in practice runtime seems to be in the order of magnitude
      23             : // of dominance tree calculation.
      24             : //
      25             : // WARNING: LLVM is generally very concerned about compile time such that
      26             : //          the use of additional analysis passes in the default
      27             : //          optimization sequence is avoided as much as possible.
      28             : //          Specifically, if you do not need the RegionInfo, but dominance
      29             : //          information could be sufficient please base your work only on
      30             : //          the dominator tree. Most passes maintain it, such that using
      31             : //          it has often near zero cost. In contrast RegionInfo is by
      32             : //          default not available, is not maintained by existing
      33             : //          transformations and there is no intention to do so.
      34             : //
      35             : //===----------------------------------------------------------------------===//
      36             : 
      37             : #ifndef LLVM_ANALYSIS_REGIONINFO_H
      38             : #define LLVM_ANALYSIS_REGIONINFO_H
      39             : 
      40             : #include "llvm/ADT/DenseMap.h"
      41             : #include "llvm/ADT/DepthFirstIterator.h"
      42             : #include "llvm/ADT/GraphTraits.h"
      43             : #include "llvm/ADT/PointerIntPair.h"
      44             : #include "llvm/ADT/iterator_range.h"
      45             : #include "llvm/IR/BasicBlock.h"
      46             : #include "llvm/IR/Dominators.h"
      47             : #include "llvm/IR/PassManager.h"
      48             : #include "llvm/Pass.h"
      49             : #include "llvm/Support/raw_ostream.h"
      50             : #include <algorithm>
      51             : #include <cassert>
      52             : #include <map>
      53             : #include <memory>
      54             : #include <set>
      55             : #include <string>
      56             : #include <type_traits>
      57             : #include <vector>
      58             : 
      59             : namespace llvm {
      60             : 
      61             : class DominanceFrontier;
      62             : class DominatorTree;
      63             : class Loop;
      64             : class LoopInfo;
      65             : struct PostDominatorTree;
      66             : class Region;
      67             : template <class RegionTr> class RegionBase;
      68             : class RegionInfo;
      69             : template <class RegionTr> class RegionInfoBase;
      70             : class RegionNode;
      71             : 
      72             : // Class to be specialized for different users of RegionInfo
      73             : // (i.e. BasicBlocks or MachineBasicBlocks). This is only to avoid needing to
      74             : // pass around an unreasonable number of template parameters.
      75             : template <class FuncT_>
      76             : struct RegionTraits {
      77             :   // FuncT
      78             :   // BlockT
      79             :   // RegionT
      80             :   // RegionNodeT
      81             :   // RegionInfoT
      82             :   using BrokenT = typename FuncT_::UnknownRegionTypeError;
      83             : };
      84             : 
      85             : template <>
      86             : struct RegionTraits<Function> {
      87             :   using FuncT = Function;
      88             :   using BlockT = BasicBlock;
      89             :   using RegionT = Region;
      90             :   using RegionNodeT = RegionNode;
      91             :   using RegionInfoT = RegionInfo;
      92             :   using DomTreeT = DominatorTree;
      93             :   using DomTreeNodeT = DomTreeNode;
      94             :   using DomFrontierT = DominanceFrontier;
      95             :   using PostDomTreeT = PostDominatorTree;
      96             :   using InstT = Instruction;
      97             :   using LoopT = Loop;
      98             :   using LoopInfoT = LoopInfo;
      99             : 
     100             :   static unsigned getNumSuccessors(BasicBlock *BB) {
     101        4426 :     return BB->getTerminator()->getNumSuccessors();
     102             :   }
     103             : };
     104             : 
     105             : /// @brief Marker class to iterate over the elements of a Region in flat mode.
     106             : ///
     107             : /// The class is used to either iterate in Flat mode or by not using it to not
     108             : /// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
     109             : /// and the iteration returns every BasicBlock.  If the Flat mode is not
     110             : /// selected for SubRegions just one RegionNode containing the subregion is
     111             : /// returned.
     112             : template <class GraphType>
     113             : class FlatIt {};
     114             : 
     115             : /// @brief A RegionNode represents a subregion or a BasicBlock that is part of a
     116             : /// Region.
     117             : template <class Tr>
     118             : class RegionNodeBase {
     119             :   friend class RegionBase<Tr>;
     120             : 
     121             : public:
     122             :   using BlockT = typename Tr::BlockT;
     123             :   using RegionT = typename Tr::RegionT;
     124             : 
     125             : private:
     126             :   /// This is the entry basic block that starts this region node.  If this is a
     127             :   /// BasicBlock RegionNode, then entry is just the basic block, that this
     128             :   /// RegionNode represents.  Otherwise it is the entry of this (Sub)RegionNode.
     129             :   ///
     130             :   /// In the BBtoRegionNode map of the parent of this node, BB will always map
     131             :   /// to this node no matter which kind of node this one is.
     132             :   ///
     133             :   /// The node can hold either a Region or a BasicBlock.
     134             :   /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
     135             :   /// RegionNode.
     136             :   PointerIntPair<BlockT *, 1, bool> entry;
     137             : 
     138             :   /// @brief The parent Region of this RegionNode.
     139             :   /// @see getParent()
     140             :   RegionT *parent;
     141             : 
     142             : protected:
     143             :   /// @brief Create a RegionNode.
     144             :   ///
     145             :   /// @param Parent      The parent of this RegionNode.
     146             :   /// @param Entry       The entry BasicBlock of the RegionNode.  If this
     147             :   ///                    RegionNode represents a BasicBlock, this is the
     148             :   ///                    BasicBlock itself.  If it represents a subregion, this
     149             :   ///                    is the entry BasicBlock of the subregion.
     150             :   /// @param isSubRegion If this RegionNode represents a SubRegion.
     151       42169 :   inline RegionNodeBase(RegionT *Parent, BlockT *Entry,
     152             :                         bool isSubRegion = false)
     153       84338 :       : entry(Entry, isSubRegion), parent(Parent) {}
     154             : 
     155             : public:
     156             :   RegionNodeBase(const RegionNodeBase &) = delete;
     157             :   RegionNodeBase &operator=(const RegionNodeBase &) = delete;
     158             : 
     159             :   /// @brief Get the parent Region of this RegionNode.
     160             :   ///
     161             :   /// The parent Region is the Region this RegionNode belongs to. If for
     162             :   /// example a BasicBlock is element of two Regions, there exist two
     163             :   /// RegionNodes for this BasicBlock. Each with the getParent() function
     164             :   /// pointing to the Region this RegionNode belongs to.
     165             :   ///
     166             :   /// @return Get the parent Region of this RegionNode.
     167       50230 :   inline RegionT *getParent() const { return parent; }
     168             : 
     169             :   /// @brief Get the entry BasicBlock of this RegionNode.
     170             :   ///
     171             :   /// If this RegionNode represents a BasicBlock this is just the BasicBlock
     172             :   /// itself, otherwise we return the entry BasicBlock of the Subregion
     173             :   ///
     174             :   /// @return The entry BasicBlock of this RegionNode.
     175     3640046 :   inline BlockT *getEntry() const { return entry.getPointer(); }
     176             : 
     177             :   /// @brief Get the content of this RegionNode.
     178             :   ///
     179             :   /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
     180             :   /// check the type of the content with the isSubRegion() function call.
     181             :   ///
     182             :   /// @return The content of this RegionNode.
     183             :   template <class T> inline T *getNodeAs() const;
     184             : 
     185             :   /// @brief Is this RegionNode a subregion?
     186             :   ///
     187             :   /// @return True if it contains a subregion. False if it contains a
     188             :   ///         BasicBlock.
     189      839430 :   inline bool isSubRegion() const { return entry.getInt(); }
     190             : };
     191             : 
     192             : //===----------------------------------------------------------------------===//
     193             : /// @brief A single entry single exit Region.
     194             : ///
     195             : /// A Region is a connected subgraph of a control flow graph that has exactly
     196             : /// two connections to the remaining graph. It can be used to analyze or
     197             : /// optimize parts of the control flow graph.
     198             : ///
     199             : /// A <em> simple Region </em> is connected to the remaining graph by just two
     200             : /// edges. One edge entering the Region and another one leaving the Region.
     201             : ///
     202             : /// An <em> extended Region </em> (or just Region) is a subgraph that can be
     203             : /// transform into a simple Region. The transformation is done by adding
     204             : /// BasicBlocks that merge several entry or exit edges so that after the merge
     205             : /// just one entry and one exit edge exists.
     206             : ///
     207             : /// The \e Entry of a Region is the first BasicBlock that is passed after
     208             : /// entering the Region. It is an element of the Region. The entry BasicBlock
     209             : /// dominates all BasicBlocks in the Region.
     210             : ///
     211             : /// The \e Exit of a Region is the first BasicBlock that is passed after
     212             : /// leaving the Region. It is not an element of the Region. The exit BasicBlock,
     213             : /// postdominates all BasicBlocks in the Region.
     214             : ///
     215             : /// A <em> canonical Region </em> cannot be constructed by combining smaller
     216             : /// Regions.
     217             : ///
     218             : /// Region A is the \e parent of Region B, if B is completely contained in A.
     219             : ///
     220             : /// Two canonical Regions either do not intersect at all or one is
     221             : /// the parent of the other.
     222             : ///
     223             : /// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
     224             : /// Regions in the control flow graph and E is the \e parent relation of these
     225             : /// Regions.
     226             : ///
     227             : /// Example:
     228             : ///
     229             : /// \verbatim
     230             : /// A simple control flow graph, that contains two regions.
     231             : ///
     232             : ///        1
     233             : ///       / |
     234             : ///      2   |
     235             : ///     / \   3
     236             : ///    4   5  |
     237             : ///    |   |  |
     238             : ///    6   7  8
     239             : ///     \  | /
     240             : ///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
     241             : ///        9        Region B: 2 -> 9 {2,4,5,6,7}
     242             : /// \endverbatim
     243             : ///
     244             : /// You can obtain more examples by either calling
     245             : ///
     246             : /// <tt> "opt -regions -analyze anyprogram.ll" </tt>
     247             : /// or
     248             : /// <tt> "opt -view-regions-only anyprogram.ll" </tt>
     249             : ///
     250             : /// on any LLVM file you are interested in.
     251             : ///
     252             : /// The first call returns a textual representation of the program structure
     253             : /// tree, the second one creates a graphical representation using graphviz.
     254             : template <class Tr>
     255             : class RegionBase : public RegionNodeBase<Tr> {
     256             :   friend class RegionInfoBase<Tr>;
     257             : 
     258             :   using FuncT = typename Tr::FuncT;
     259             :   using BlockT = typename Tr::BlockT;
     260             :   using RegionInfoT = typename Tr::RegionInfoT;
     261             :   using RegionT = typename Tr::RegionT;
     262             :   using RegionNodeT = typename Tr::RegionNodeT;
     263             :   using DomTreeT = typename Tr::DomTreeT;
     264             :   using LoopT = typename Tr::LoopT;
     265             :   using LoopInfoT = typename Tr::LoopInfoT;
     266             :   using InstT = typename Tr::InstT;
     267             : 
     268             :   using BlockTraits = GraphTraits<BlockT *>;
     269             :   using InvBlockTraits = GraphTraits<Inverse<BlockT *>>;
     270             :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
     271             :   using PredIterTy = typename InvBlockTraits::ChildIteratorType;
     272             : 
     273             :   // Information necessary to manage this Region.
     274             :   RegionInfoT *RI;
     275             :   DomTreeT *DT;
     276             : 
     277             :   // The exit BasicBlock of this region.
     278             :   // (The entry BasicBlock is part of RegionNode)
     279             :   BlockT *exit;
     280             : 
     281             :   using RegionSet = std::vector<std::unique_ptr<RegionT>>;
     282             : 
     283             :   // The subregions of this region.
     284             :   RegionSet children;
     285             : 
     286             :   using BBNodeMapT = std::map<BlockT *, std::unique_ptr<RegionNodeT>>;
     287             : 
     288             :   // Save the BasicBlock RegionNodes that are element of this Region.
     289             :   mutable BBNodeMapT BBNodeMap;
     290             : 
     291             :   /// Check if a BB is in this Region. This check also works
     292             :   /// if the region is incorrectly built. (EXPENSIVE!)
     293             :   void verifyBBInRegion(BlockT *BB) const;
     294             : 
     295             :   /// Walk over all the BBs of the region starting from BB and
     296             :   /// verify that all reachable basic blocks are elements of the region.
     297             :   /// (EXPENSIVE!)
     298             :   void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const;
     299             : 
     300             :   /// Verify if the region and its children are valid regions (EXPENSIVE!)
     301             :   void verifyRegionNest() const;
     302             : 
     303             : public:
     304             :   /// @brief Create a new region.
     305             :   ///
     306             :   /// @param Entry  The entry basic block of the region.
     307             :   /// @param Exit   The exit basic block of the region.
     308             :   /// @param RI     The region info object that is managing this region.
     309             :   /// @param DT     The dominator tree of the current function.
     310             :   /// @param Parent The surrounding region or NULL if this is a top level
     311             :   ///               region.
     312             :   RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT,
     313             :              RegionT *Parent = nullptr);
     314             : 
     315             :   RegionBase(const RegionBase &) = delete;
     316             :   RegionBase &operator=(const RegionBase &) = delete;
     317             : 
     318             :   /// Delete the Region and all its subregions.
     319             :   ~RegionBase();
     320             : 
     321             :   /// @brief Get the entry BasicBlock of the Region.
     322             :   /// @return The entry BasicBlock of the region.
     323           0 :   BlockT *getEntry() const {
     324     2674412 :     return RegionNodeBase<Tr>::getEntry();
     325             :   }
     326             : 
     327             :   /// @brief Replace the entry basic block of the region with the new basic
     328             :   ///        block.
     329             :   ///
     330             :   /// @param BB  The new entry basic block of the region.
     331             :   void replaceEntry(BlockT *BB);
     332             : 
     333             :   /// @brief Replace the exit basic block of the region with the new basic
     334             :   ///        block.
     335             :   ///
     336             :   /// @param BB  The new exit basic block of the region.
     337             :   void replaceExit(BlockT *BB);
     338             : 
     339             :   /// @brief Recursively replace the entry basic block of the region.
     340             :   ///
     341             :   /// This function replaces the entry basic block with a new basic block. It
     342             :   /// also updates all child regions that have the same entry basic block as
     343             :   /// this region.
     344             :   ///
     345             :   /// @param NewEntry The new entry basic block.
     346             :   void replaceEntryRecursive(BlockT *NewEntry);
     347             : 
     348             :   /// @brief Recursively replace the exit basic block of the region.
     349             :   ///
     350             :   /// This function replaces the exit basic block with a new basic block. It
     351             :   /// also updates all child regions that have the same exit basic block as
     352             :   /// this region.
     353             :   ///
     354             :   /// @param NewExit The new exit basic block.
     355             :   void replaceExitRecursive(BlockT *NewExit);
     356             : 
     357             :   /// @brief Get the exit BasicBlock of the Region.
     358             :   /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
     359             :   ///         Region.
     360     1138880 :   BlockT *getExit() const { return exit; }
     361             : 
     362             :   /// @brief Get the parent of the Region.
     363             :   /// @return The parent of the Region or NULL if this is a top level
     364             :   ///         Region.
     365           0 :   RegionT *getParent() const {
     366       91441 :     return RegionNodeBase<Tr>::getParent();
     367             :   }
     368             : 
     369             :   /// @brief Get the RegionNode representing the current Region.
     370             :   /// @return The RegionNode representing the current Region.
     371           0 :   RegionNodeT *getNode() const {
     372             :     return const_cast<RegionNodeT *>(
     373           0 :         reinterpret_cast<const RegionNodeT *>(this));
     374             :   }
     375             : 
     376             :   /// @brief Get the nesting level of this Region.
     377             :   ///
     378             :   /// An toplevel Region has depth 0.
     379             :   ///
     380             :   /// @return The depth of the region.
     381             :   unsigned getDepth() const;
     382             : 
     383             :   /// @brief Check if a Region is the TopLevel region.
     384             :   ///
     385             :   /// The toplevel region represents the whole function.
     386       26015 :   bool isTopLevelRegion() const { return exit == nullptr; }
     387             : 
     388             :   /// @brief Return a new (non-canonical) region, that is obtained by joining
     389             :   ///        this region with its predecessors.
     390             :   ///
     391             :   /// @return A region also starting at getEntry(), but reaching to the next
     392             :   ///         basic block that forms with getEntry() a (non-canonical) region.
     393             :   ///         NULL if such a basic block does not exist.
     394             :   RegionT *getExpandedRegion() const;
     395             : 
     396             :   /// @brief Return the first block of this region's single entry edge,
     397             :   ///        if existing.
     398             :   ///
     399             :   /// @return The BasicBlock starting this region's single entry edge,
     400             :   ///         else NULL.
     401             :   BlockT *getEnteringBlock() const;
     402             : 
     403             :   /// @brief Return the first block of this region's single exit edge,
     404             :   ///        if existing.
     405             :   ///
     406             :   /// @return The BasicBlock starting this region's single exit edge,
     407             :   ///         else NULL.
     408             :   BlockT *getExitingBlock() const;
     409             : 
     410             :   /// @brief Is this a simple region?
     411             :   ///
     412             :   /// A region is simple if it has exactly one exit and one entry edge.
     413             :   ///
     414             :   /// @return True if the Region is simple.
     415             :   bool isSimple() const;
     416             : 
     417             :   /// @brief Returns the name of the Region.
     418             :   /// @return The Name of the Region.
     419             :   std::string getNameStr() const;
     420             : 
     421             :   /// @brief Return the RegionInfo object, that belongs to this Region.
     422           0 :   RegionInfoT *getRegionInfo() const { return RI; }
     423             : 
     424             :   /// PrintStyle - Print region in difference ways.
     425             :   enum PrintStyle { PrintNone, PrintBB, PrintRN };
     426             : 
     427             :   /// @brief Print the region.
     428             :   ///
     429             :   /// @param OS The output stream the Region is printed to.
     430             :   /// @param printTree Print also the tree of subregions.
     431             :   /// @param level The indentation level used for printing.
     432             :   void print(raw_ostream &OS, bool printTree = true, unsigned level = 0,
     433             :              PrintStyle Style = PrintNone) const;
     434             : 
     435             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     436             :   /// @brief Print the region to stderr.
     437             :   void dump() const;
     438             : #endif
     439             : 
     440             :   /// @brief Check if the region contains a BasicBlock.
     441             :   ///
     442             :   /// @param BB The BasicBlock that might be contained in this Region.
     443             :   /// @return True if the block is contained in the region otherwise false.
     444             :   bool contains(const BlockT *BB) const;
     445             : 
     446             :   /// @brief Check if the region contains another region.
     447             :   ///
     448             :   /// @param SubRegion The region that might be contained in this Region.
     449             :   /// @return True if SubRegion is contained in the region otherwise false.
     450       17576 :   bool contains(const RegionT *SubRegion) const {
     451             :     // Toplevel Region.
     452       17576 :     if (!getExit())
     453             :       return true;
     454             : 
     455       49600 :     return contains(SubRegion->getEntry()) &&
     456       48291 :            (contains(SubRegion->getExit()) ||
     457       45897 :             SubRegion->getExit() == getExit());
     458             :   }
     459             : 
     460             :   /// @brief Check if the region contains an Instruction.
     461             :   ///
     462             :   /// @param Inst The Instruction that might be contained in this region.
     463             :   /// @return True if the Instruction is contained in the region otherwise
     464             :   /// false.
     465      114462 :   bool contains(const InstT *Inst) const { return contains(Inst->getParent()); }
     466             : 
     467             :   /// @brief Check if the region contains a loop.
     468             :   ///
     469             :   /// @param L The loop that might be contained in this region.
     470             :   /// @return True if the loop is contained in the region otherwise false.
     471             :   ///         In case a NULL pointer is passed to this function the result
     472             :   ///         is false, except for the region that describes the whole function.
     473             :   ///         In that case true is returned.
     474             :   bool contains(const LoopT *L) const;
     475             : 
     476             :   /// @brief Get the outermost loop in the region that contains a loop.
     477             :   ///
     478             :   /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
     479             :   /// and is itself contained in the region.
     480             :   ///
     481             :   /// @param L The loop the lookup is started.
     482             :   /// @return The outermost loop in the region, NULL if such a loop does not
     483             :   ///         exist or if the region describes the whole function.
     484             :   LoopT *outermostLoopInRegion(LoopT *L) const;
     485             : 
     486             :   /// @brief Get the outermost loop in the region that contains a basic block.
     487             :   ///
     488             :   /// Find for a basic block BB the outermost loop L that contains BB and is
     489             :   /// itself contained in the region.
     490             :   ///
     491             :   /// @param LI A pointer to a LoopInfo analysis.
     492             :   /// @param BB The basic block surrounded by the loop.
     493             :   /// @return The outermost loop in the region, NULL if such a loop does not
     494             :   ///         exist or if the region describes the whole function.
     495             :   LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const;
     496             : 
     497             :   /// @brief Get the subregion that starts at a BasicBlock
     498             :   ///
     499             :   /// @param BB The BasicBlock the subregion should start.
     500             :   /// @return The Subregion if available, otherwise NULL.
     501             :   RegionT *getSubRegionNode(BlockT *BB) const;
     502             : 
     503             :   /// @brief Get the RegionNode for a BasicBlock
     504             :   ///
     505             :   /// @param BB The BasicBlock at which the RegionNode should start.
     506             :   /// @return If available, the RegionNode that represents the subregion
     507             :   ///         starting at BB. If no subregion starts at BB, the RegionNode
     508             :   ///         representing BB.
     509             :   RegionNodeT *getNode(BlockT *BB) const;
     510             : 
     511             :   /// @brief Get the BasicBlock RegionNode for a BasicBlock
     512             :   ///
     513             :   /// @param BB The BasicBlock for which the RegionNode is requested.
     514             :   /// @return The RegionNode representing the BB.
     515             :   RegionNodeT *getBBNode(BlockT *BB) const;
     516             : 
     517             :   /// @brief Add a new subregion to this Region.
     518             :   ///
     519             :   /// @param SubRegion The new subregion that will be added.
     520             :   /// @param moveChildren Move the children of this region, that are also
     521             :   ///                     contained in SubRegion into SubRegion.
     522             :   void addSubRegion(RegionT *SubRegion, bool moveChildren = false);
     523             : 
     524             :   /// @brief Remove a subregion from this Region.
     525             :   ///
     526             :   /// The subregion is not deleted, as it will probably be inserted into another
     527             :   /// region.
     528             :   /// @param SubRegion The SubRegion that will be removed.
     529             :   RegionT *removeSubRegion(RegionT *SubRegion);
     530             : 
     531             :   /// @brief Move all direct child nodes of this Region to another Region.
     532             :   ///
     533             :   /// @param To The Region the child nodes will be transferred to.
     534             :   void transferChildrenTo(RegionT *To);
     535             : 
     536             :   /// @brief Verify if the region is a correct region.
     537             :   ///
     538             :   /// Check if this is a correctly build Region. This is an expensive check, as
     539             :   /// the complete CFG of the Region will be walked.
     540             :   void verifyRegion() const;
     541             : 
     542             :   /// @brief Clear the cache for BB RegionNodes.
     543             :   ///
     544             :   /// After calling this function the BasicBlock RegionNodes will be stored at
     545             :   /// different memory locations. RegionNodes obtained before this function is
     546             :   /// called are therefore not comparable to RegionNodes abtained afterwords.
     547             :   void clearNodeCache();
     548             : 
     549             :   /// @name Subregion Iterators
     550             :   ///
     551             :   /// These iterators iterator over all subregions of this Region.
     552             :   //@{
     553             :   using iterator = typename RegionSet::iterator;
     554             :   using const_iterator = typename RegionSet::const_iterator;
     555             : 
     556      184520 :   iterator begin() { return children.begin(); }
     557      184520 :   iterator end() { return children.end(); }
     558             : 
     559        1541 :   const_iterator begin() const { return children.begin(); }
     560        1541 :   const_iterator end() const { return children.end(); }
     561             :   //@}
     562             : 
     563             :   /// @name BasicBlock Iterators
     564             :   ///
     565             :   /// These iterators iterate over all BasicBlocks that are contained in this
     566             :   /// Region. The iterator also iterates over BasicBlocks that are elements of
     567             :   /// a subregion of this Region. It is therefore called a flat iterator.
     568             :   //@{
     569             :   template <bool IsConst>
     570      260260 :   class block_iterator_wrapper
     571             :       : public df_iterator<
     572             :             typename std::conditional<IsConst, const BlockT, BlockT>::type *> {
     573             :     using super =
     574             :         df_iterator<
     575             :             typename std::conditional<IsConst, const BlockT, BlockT>::type *>;
     576             : 
     577             :   public:
     578             :     using Self = block_iterator_wrapper<IsConst>;
     579             :     using value_type = typename super::value_type;
     580             : 
     581             :     // Construct the begin iterator.
     582             :     block_iterator_wrapper(value_type Entry, value_type Exit)
     583        6920 :         : super(df_begin(Entry)) {
     584             :       // Mark the exit of the region as visited, so that the children of the
     585             :       // exit and the exit itself, i.e. the block outside the region will never
     586             :       // be visited.
     587       13840 :       super::Visited.insert(Exit);
     588             :     }
     589             : 
     590             :     // Construct the end iterator.
     591             :     block_iterator_wrapper() : super(df_end<value_type>((BlockT *)nullptr)) {}
     592             : 
     593             :     /*implicit*/ block_iterator_wrapper(super I) : super(I) {}
     594             : 
     595             :     // FIXME: Even a const_iterator returns a non-const BasicBlock pointer.
     596             :     //        This was introduced for backwards compatibility, but should
     597             :     //        be removed as soon as all users are fixed.
     598             :     BlockT *operator*() const {
     599      313448 :       return const_cast<BlockT *>(super::operator*());
     600             :     }
     601             :   };
     602             : 
     603             :   using block_iterator = block_iterator_wrapper<false>;
     604             :   using const_block_iterator = block_iterator_wrapper<true>;
     605             : 
     606       20748 :   block_iterator block_begin() { return block_iterator(getEntry(), getExit()); }
     607             : 
     608        6916 :   block_iterator block_end() { return block_iterator(); }
     609             : 
     610           0 :   const_block_iterator block_begin() const {
     611          12 :     return const_block_iterator(getEntry(), getExit());
     612             :   }
     613           4 :   const_block_iterator block_end() const { return const_block_iterator(); }
     614             : 
     615             :   using block_range = iterator_range<block_iterator>;
     616             :   using const_block_range = iterator_range<const_block_iterator>;
     617             : 
     618             :   /// @brief Returns a range view of the basic blocks in the region.
     619        6710 :   inline block_range blocks() {
     620       33550 :     return block_range(block_begin(), block_end());
     621             :   }
     622             : 
     623             :   /// @brief Returns a range view of the basic blocks in the region.
     624             :   ///
     625             :   /// This is the 'const' version of the range view.
     626           4 :   inline const_block_range blocks() const {
     627          20 :     return const_block_range(block_begin(), block_end());
     628             :   }
     629             :   //@}
     630             : 
     631             :   /// @name Element Iterators
     632             :   ///
     633             :   /// These iterators iterate over all BasicBlock and subregion RegionNodes that
     634             :   /// are direct children of this Region. It does not iterate over any
     635             :   /// RegionNodes that are also element of a subregion of this Region.
     636             :   //@{
     637             :   using element_iterator =
     638             :       df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false,
     639             :                   GraphTraits<RegionNodeT *>>;
     640             : 
     641             :   using const_element_iterator =
     642             :       df_iterator<const RegionNodeT *,
     643             :                   df_iterator_default_set<const RegionNodeT *>, false,
     644             :                   GraphTraits<const RegionNodeT *>>;
     645             : 
     646             :   element_iterator element_begin();
     647             :   element_iterator element_end();
     648         622 :   iterator_range<element_iterator> elements() {
     649         622 :     return make_range(element_begin(), element_end());
     650             :   }
     651             : 
     652             :   const_element_iterator element_begin() const;
     653             :   const_element_iterator element_end() const;
     654           4 :   iterator_range<const_element_iterator> elements() const {
     655           4 :     return make_range(element_begin(), element_end());
     656             :   }
     657             :   //@}
     658             : };
     659             : 
     660             : /// Print a RegionNode.
     661             : template <class Tr>
     662             : inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node);
     663             : 
     664             : //===----------------------------------------------------------------------===//
     665             : /// @brief Analysis that detects all canonical Regions.
     666             : ///
     667             : /// The RegionInfo pass detects all canonical regions in a function. The Regions
     668             : /// are connected using the parent relation. This builds a Program Structure
     669             : /// Tree.
     670             : template <class Tr>
     671        8362 : class RegionInfoBase {
     672             :   friend class RegionInfo;
     673             :   friend class MachineRegionInfo;
     674             : 
     675             :   using BlockT = typename Tr::BlockT;
     676             :   using FuncT = typename Tr::FuncT;
     677             :   using RegionT = typename Tr::RegionT;
     678             :   using RegionInfoT = typename Tr::RegionInfoT;
     679             :   using DomTreeT = typename Tr::DomTreeT;
     680             :   using DomTreeNodeT = typename Tr::DomTreeNodeT;
     681             :   using PostDomTreeT = typename Tr::PostDomTreeT;
     682             :   using DomFrontierT = typename Tr::DomFrontierT;
     683             :   using BlockTraits = GraphTraits<BlockT *>;
     684             :   using InvBlockTraits = GraphTraits<Inverse<BlockT *>>;
     685             :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
     686             :   using PredIterTy = typename InvBlockTraits::ChildIteratorType;
     687             : 
     688             :   using BBtoBBMap = DenseMap<BlockT *, BlockT *>;
     689             :   using BBtoRegionMap = DenseMap<BlockT *, RegionT *>;
     690             : 
     691             :   RegionInfoBase();
     692             : 
     693           0 :   RegionInfoBase(RegionInfoBase &&Arg)
     694           0 :     : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)),
     695           0 :       TopLevelRegion(std::move(Arg.TopLevelRegion)),
     696           0 :       BBtoRegion(std::move(Arg.BBtoRegion)) {
     697           0 :     Arg.wipe();
     698           0 :   }
     699             : 
     700           0 :   RegionInfoBase &operator=(RegionInfoBase &&RHS) {
     701           0 :     DT = std::move(RHS.DT);
     702           0 :     PDT = std::move(RHS.PDT);
     703           0 :     DF = std::move(RHS.DF);
     704           0 :     TopLevelRegion = std::move(RHS.TopLevelRegion);
     705           0 :     BBtoRegion = std::move(RHS.BBtoRegion);
     706           0 :     RHS.wipe();
     707           0 :     return *this;
     708             :   }
     709             : 
     710             :   virtual ~RegionInfoBase();
     711             : 
     712             :   DomTreeT *DT;
     713             :   PostDomTreeT *PDT;
     714             :   DomFrontierT *DF;
     715             : 
     716             :   /// The top level region.
     717             :   RegionT *TopLevelRegion = nullptr;
     718             : 
     719             :   /// Map every BB to the smallest region, that contains BB.
     720             :   BBtoRegionMap BBtoRegion;
     721             : 
     722             : protected:
     723             :   /// \brief Update refences to a RegionInfoT held by the RegionT managed here
     724             :   ///
     725             :   /// This is a post-move helper. Regions hold references to the owning
     726             :   /// RegionInfo object. After a move these need to be fixed.
     727             :   template<typename TheRegionT>
     728          28 :   void updateRegionTree(RegionInfoT &RI, TheRegionT *R) {
     729          28 :     if (!R)
     730             :       return;
     731          28 :     R->RI = &RI;
     732         128 :     for (auto &SubR : *R)
     733          16 :       updateRegionTree(RI, SubR.get());
     734             :   }
     735             : 
     736             : private:
     737             :   /// \brief Wipe this region tree's state without releasing any resources.
     738             :   ///
     739             :   /// This is essentially a post-move helper only. It leaves the object in an
     740             :   /// assignable and destroyable state, but otherwise invalid.
     741           0 :   void wipe() {
     742           0 :     DT = nullptr;
     743           0 :     PDT = nullptr;
     744           0 :     DF = nullptr;
     745           0 :     TopLevelRegion = nullptr;
     746           0 :     BBtoRegion.clear();
     747           0 :   }
     748             : 
     749             :   // Check whether the entries of BBtoRegion for the BBs of region
     750             :   // SR are correct. Triggers an assertion if not. Calls itself recursively for
     751             :   // subregions.
     752             :   void verifyBBMap(const RegionT *SR) const;
     753             : 
     754             :   // Returns true if BB is in the dominance frontier of
     755             :   // entry, because it was inherited from exit. In the other case there is an
     756             :   // edge going from entry to BB without passing exit.
     757             :   bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;
     758             : 
     759             :   // Check if entry and exit surround a valid region, based on
     760             :   // dominance tree and dominance frontier.
     761             :   bool isRegion(BlockT *entry, BlockT *exit) const;
     762             : 
     763             :   // Saves a shortcut pointing from entry to exit.
     764             :   // This function may extend this shortcut if possible.
     765             :   void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const;
     766             : 
     767             :   // Returns the next BB that postdominates N, while skipping
     768             :   // all post dominators that cannot finish a canonical region.
     769             :   DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const;
     770             : 
     771             :   // A region is trivial, if it contains only one BB.
     772             :   bool isTrivialRegion(BlockT *entry, BlockT *exit) const;
     773             : 
     774             :   // Creates a single entry single exit region.
     775             :   RegionT *createRegion(BlockT *entry, BlockT *exit);
     776             : 
     777             :   // Detect all regions starting with bb 'entry'.
     778             :   void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut);
     779             : 
     780             :   // Detects regions in F.
     781             :   void scanForRegions(FuncT &F, BBtoBBMap *ShortCut);
     782             : 
     783             :   // Get the top most parent with the same entry block.
     784             :   RegionT *getTopMostParent(RegionT *region);
     785             : 
     786             :   // Build the region hierarchy after all region detected.
     787             :   void buildRegionsTree(DomTreeNodeT *N, RegionT *region);
     788             : 
     789             :   // Update statistic about created regions.
     790             :   virtual void updateStatistics(RegionT *R) = 0;
     791             : 
     792             :   // Detect all regions in function and build the region tree.
     793             :   void calculate(FuncT &F);
     794             : 
     795             : public:
     796             :   RegionInfoBase(const RegionInfoBase &) = delete;
     797             :   RegionInfoBase &operator=(const RegionInfoBase &) = delete;
     798             : 
     799             :   static bool VerifyRegionInfo;
     800             :   static typename RegionT::PrintStyle printStyle;
     801             : 
     802             :   void print(raw_ostream &OS) const;
     803             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     804             :   void dump() const;
     805             : #endif
     806             : 
     807             :   void releaseMemory();
     808             : 
     809             :   /// @brief Get the smallest region that contains a BasicBlock.
     810             :   ///
     811             :   /// @param BB The basic block.
     812             :   /// @return The smallest region, that contains BB or NULL, if there is no
     813             :   /// region containing BB.
     814             :   RegionT *getRegionFor(BlockT *BB) const;
     815             : 
     816             :   /// @brief  Set the smallest region that surrounds a basic block.
     817             :   ///
     818             :   /// @param BB The basic block surrounded by a region.
     819             :   /// @param R The smallest region that surrounds BB.
     820             :   void setRegionFor(BlockT *BB, RegionT *R);
     821             : 
     822             :   /// @brief A shortcut for getRegionFor().
     823             :   ///
     824             :   /// @param BB The basic block.
     825             :   /// @return The smallest region, that contains BB or NULL, if there is no
     826             :   /// region containing BB.
     827             :   RegionT *operator[](BlockT *BB) const;
     828             : 
     829             :   /// @brief Return the exit of the maximal refined region, that starts at a
     830             :   /// BasicBlock.
     831             :   ///
     832             :   /// @param BB The BasicBlock the refined region starts.
     833             :   BlockT *getMaxRegionExit(BlockT *BB) const;
     834             : 
     835             :   /// @brief Find the smallest region that contains two regions.
     836             :   ///
     837             :   /// @param A The first region.
     838             :   /// @param B The second region.
     839             :   /// @return The smallest region containing A and B.
     840             :   RegionT *getCommonRegion(RegionT *A, RegionT *B) const;
     841             : 
     842             :   /// @brief Find the smallest region that contains two basic blocks.
     843             :   ///
     844             :   /// @param A The first basic block.
     845             :   /// @param B The second basic block.
     846             :   /// @return The smallest region that contains A and B.
     847           0 :   RegionT *getCommonRegion(BlockT *A, BlockT *B) const {
     848           0 :     return getCommonRegion(getRegionFor(A), getRegionFor(B));
     849             :   }
     850             : 
     851             :   /// @brief Find the smallest region that contains a set of regions.
     852             :   ///
     853             :   /// @param Regions A vector of regions.
     854             :   /// @return The smallest region that contains all regions in Regions.
     855             :   RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const;
     856             : 
     857             :   /// @brief Find the smallest region that contains a set of basic blocks.
     858             :   ///
     859             :   /// @param BBs A vector of basic blocks.
     860             :   /// @return The smallest region that contains all basic blocks in BBS.
     861             :   RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const;
     862             : 
     863           0 :   RegionT *getTopLevelRegion() const { return TopLevelRegion; }
     864             : 
     865             :   /// @brief Clear the Node Cache for all Regions.
     866             :   ///
     867             :   /// @see Region::clearNodeCache()
     868           0 :   void clearNodeCache() {
     869       25428 :     if (TopLevelRegion)
     870       25428 :       TopLevelRegion->clearNodeCache();
     871           0 :   }
     872             : 
     873             :   void verifyAnalysis() const;
     874             : };
     875             : 
     876             : class Region;
     877             : 
     878             : class RegionNode : public RegionNodeBase<RegionTraits<Function>> {
     879             : public:
     880             :   inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false)
     881       29848 :       : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {}
     882             : 
     883             :   bool operator==(const Region &RN) const {
     884             :     return this == reinterpret_cast<const RegionNode *>(&RN);
     885             :   }
     886             : };
     887             : 
     888       27073 : class Region : public RegionBase<RegionTraits<Function>> {
     889             : public:
     890             :   Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT,
     891             :          Region *Parent = nullptr);
     892             :   ~Region();
     893             : 
     894             :   bool operator==(const RegionNode &RN) const {
     895             :     return &RN == reinterpret_cast<const RegionNode *>(this);
     896             :   }
     897             : };
     898             : 
     899        8321 : class RegionInfo : public RegionInfoBase<RegionTraits<Function>> {
     900             : public:
     901             :   using Base = RegionInfoBase<RegionTraits<Function>>;
     902             : 
     903             :   explicit RegionInfo();
     904             : 
     905          12 :   RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) {
     906          12 :     updateRegionTree(*this, TopLevelRegion);
     907          12 :   }
     908             : 
     909             :   RegionInfo &operator=(RegionInfo &&RHS) {
     910             :     Base::operator=(std::move(static_cast<Base &>(RHS)));
     911             :     updateRegionTree(*this, TopLevelRegion);
     912             :     return *this;
     913             :   }
     914             : 
     915             :   ~RegionInfo() override;
     916             : 
     917             :   /// Handle invalidation explicitly.
     918             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     919             :                   FunctionAnalysisManager::Invalidator &);
     920             : 
     921             :   // updateStatistics - Update statistic about created regions.
     922             :   void updateStatistics(Region *R) final;
     923             : 
     924             :   void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT,
     925             :                    DominanceFrontier *DF);
     926             : 
     927             : #ifndef NDEBUG
     928             :   /// @brief Opens a viewer to show the GraphViz visualization of the regions.
     929             :   ///
     930             :   /// Useful during debugging as an alternative to dump().
     931             :   void view();
     932             : 
     933             :   /// @brief Opens a viewer to show the GraphViz visualization of this region
     934             :   /// without instructions in the BasicBlocks.
     935             :   ///
     936             :   /// Useful during debugging as an alternative to dump().
     937             :   void viewOnly();
     938             : #endif
     939             : };
     940             : 
     941       12366 : class RegionInfoPass : public FunctionPass {
     942             :   RegionInfo RI;
     943             : 
     944             : public:
     945             :   static char ID;
     946             : 
     947             :   explicit RegionInfoPass();
     948             :   ~RegionInfoPass() override;
     949             : 
     950       22420 :   RegionInfo &getRegionInfo() { return RI; }
     951             : 
     952             :   const RegionInfo &getRegionInfo() const { return RI; }
     953             : 
     954             :   /// @name FunctionPass interface
     955             :   //@{
     956             :   bool runOnFunction(Function &F) override;
     957             :   void releaseMemory() override;
     958             :   void verifyAnalysis() const override;
     959             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     960             :   void print(raw_ostream &OS, const Module *) const override;
     961             :   void dump() const;
     962             :   //@}
     963             : };
     964             : 
     965             : /// \brief Analysis pass that exposes the \c RegionInfo for a function.
     966             : class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> {
     967             :   friend AnalysisInfoMixin<RegionInfoAnalysis>;
     968             : 
     969             :   static AnalysisKey Key;
     970             : 
     971             : public:
     972             :   using Result = RegionInfo;
     973             : 
     974             :   RegionInfo run(Function &F, FunctionAnalysisManager &AM);
     975             : };
     976             : 
     977             : /// \brief Printer pass for the \c RegionInfo.
     978             : class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
     979             :   raw_ostream &OS;
     980             : 
     981             : public:
     982             :   explicit RegionInfoPrinterPass(raw_ostream &OS);
     983             : 
     984             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     985             : };
     986             : 
     987             : /// \brief Verifier pass for the \c RegionInfo.
     988             : struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
     989             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     990             : };
     991             : 
     992             : template <>
     993             : template <>
     994             : inline BasicBlock *
     995             : RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const {
     996             :   assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
     997      132755 :   return getEntry();
     998             : }
     999             : 
    1000             : template <>
    1001             : template <>
    1002             : inline Region *
    1003             : RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const {
    1004             :   assert(isSubRegion() && "This is not a subregion RegionNode!");
    1005       45549 :   auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this);
    1006             :   return reinterpret_cast<Region *>(Unconst);
    1007             : }
    1008             : 
    1009             : template <class Tr>
    1010           8 : inline raw_ostream &operator<<(raw_ostream &OS,
    1011             :                                const RegionNodeBase<Tr> &Node) {
    1012             :   using BlockT = typename Tr::BlockT;
    1013             :   using RegionT = typename Tr::RegionT;
    1014             : 
    1015           8 :   if (Node.isSubRegion())
    1016           6 :     return OS << Node.template getNodeAs<RegionT>()->getNameStr();
    1017             :   else
    1018           6 :     return OS << Node.template getNodeAs<BlockT>()->getName();
    1019             : }
    1020             : 
    1021             : extern template class RegionBase<RegionTraits<Function>>;
    1022             : extern template class RegionNodeBase<RegionTraits<Function>>;
    1023             : extern template class RegionInfoBase<RegionTraits<Function>>;
    1024             : 
    1025             : } // end namespace llvm
    1026             : 
    1027             : #endif // LLVM_ANALYSIS_REGIONINFO_H

Generated by: LCOV version 1.13