LCOV - code coverage report
Current view: top level - include/llvm/Analysis - RegionInfo.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 45 81 55.6 %
Date: 2018-02-23 15:42:53 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             : class 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        4648 :     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       45219 :   inline RegionNodeBase(RegionT *Parent, BlockT *Entry,
     152             :                         bool isSubRegion = false)
     153       45219 :       : 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       52707 :   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           0 :   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           0 :   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           0 :     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     1141906 :   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        1444 :     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       28197 :   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 Collect all blocks of this region's single exit edge, if existing.
     411             :   ///
     412             :   /// @return True if this region contains all the predecessors of the exit.
     413             :   bool getExitingBlocks(SmallVectorImpl<BlockT *> &Exitings) const;
     414             : 
     415             :   /// @brief Is this a simple region?
     416             :   ///
     417             :   /// A region is simple if it has exactly one exit and one entry edge.
     418             :   ///
     419             :   /// @return True if the Region is simple.
     420             :   bool isSimple() const;
     421             : 
     422             :   /// @brief Returns the name of the Region.
     423             :   /// @return The Name of the Region.
     424             :   std::string getNameStr() const;
     425             : 
     426             :   /// @brief Return the RegionInfo object, that belongs to this Region.
     427           0 :   RegionInfoT *getRegionInfo() const { return RI; }
     428             : 
     429             :   /// PrintStyle - Print region in difference ways.
     430             :   enum PrintStyle { PrintNone, PrintBB, PrintRN };
     431             : 
     432             :   /// @brief Print the region.
     433             :   ///
     434             :   /// @param OS The output stream the Region is printed to.
     435             :   /// @param printTree Print also the tree of subregions.
     436             :   /// @param level The indentation level used for printing.
     437             :   void print(raw_ostream &OS, bool printTree = true, unsigned level = 0,
     438             :              PrintStyle Style = PrintNone) const;
     439             : 
     440             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     441             :   /// @brief Print the region to stderr.
     442             :   void dump() const;
     443             : #endif
     444             : 
     445             :   /// @brief Check if the region contains a BasicBlock.
     446             :   ///
     447             :   /// @param BB The BasicBlock that might be contained in this Region.
     448             :   /// @return True if the block is contained in the region otherwise false.
     449             :   bool contains(const BlockT *BB) const;
     450             : 
     451             :   /// @brief Check if the region contains another region.
     452             :   ///
     453             :   /// @param SubRegion The region that might be contained in this Region.
     454             :   /// @return True if SubRegion is contained in the region otherwise false.
     455       18524 :   bool contains(const RegionT *SubRegion) const {
     456             :     // Toplevel Region.
     457       18524 :     if (!getExit())
     458             :       return true;
     459             : 
     460       34816 :     return contains(SubRegion->getEntry()) &&
     461       33499 :            (contains(SubRegion->getExit()) ||
     462             :             SubRegion->getExit() == getExit());
     463             :   }
     464             : 
     465             :   /// @brief Check if the region contains an Instruction.
     466             :   ///
     467             :   /// @param Inst The Instruction that might be contained in this region.
     468             :   /// @return True if the Instruction is contained in the region otherwise
     469             :   /// false.
     470      112028 :   bool contains(const InstT *Inst) const { return contains(Inst->getParent()); }
     471             : 
     472             :   /// @brief Check if the region contains a loop.
     473             :   ///
     474             :   /// @param L The loop that might be contained in this region.
     475             :   /// @return True if the loop is contained in the region otherwise false.
     476             :   ///         In case a NULL pointer is passed to this function the result
     477             :   ///         is false, except for the region that describes the whole function.
     478             :   ///         In that case true is returned.
     479             :   bool contains(const LoopT *L) const;
     480             : 
     481             :   /// @brief Get the outermost loop in the region that contains a loop.
     482             :   ///
     483             :   /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
     484             :   /// and is itself contained in the region.
     485             :   ///
     486             :   /// @param L The loop the lookup is started.
     487             :   /// @return The outermost loop in the region, NULL if such a loop does not
     488             :   ///         exist or if the region describes the whole function.
     489             :   LoopT *outermostLoopInRegion(LoopT *L) const;
     490             : 
     491             :   /// @brief Get the outermost loop in the region that contains a basic block.
     492             :   ///
     493             :   /// Find for a basic block BB the outermost loop L that contains BB and is
     494             :   /// itself contained in the region.
     495             :   ///
     496             :   /// @param LI A pointer to a LoopInfo analysis.
     497             :   /// @param BB The basic block surrounded by the loop.
     498             :   /// @return The outermost loop in the region, NULL if such a loop does not
     499             :   ///         exist or if the region describes the whole function.
     500             :   LoopT *outermostLoopInRegion(LoopInfoT *LI, BlockT *BB) const;
     501             : 
     502             :   /// @brief Get the subregion that starts at a BasicBlock
     503             :   ///
     504             :   /// @param BB The BasicBlock the subregion should start.
     505             :   /// @return The Subregion if available, otherwise NULL.
     506             :   RegionT *getSubRegionNode(BlockT *BB) const;
     507             : 
     508             :   /// @brief Get the RegionNode for a BasicBlock
     509             :   ///
     510             :   /// @param BB The BasicBlock at which the RegionNode should start.
     511             :   /// @return If available, the RegionNode that represents the subregion
     512             :   ///         starting at BB. If no subregion starts at BB, the RegionNode
     513             :   ///         representing BB.
     514             :   RegionNodeT *getNode(BlockT *BB) const;
     515             : 
     516             :   /// @brief Get the BasicBlock RegionNode for a BasicBlock
     517             :   ///
     518             :   /// @param BB The BasicBlock for which the RegionNode is requested.
     519             :   /// @return The RegionNode representing the BB.
     520             :   RegionNodeT *getBBNode(BlockT *BB) const;
     521             : 
     522             :   /// @brief Add a new subregion to this Region.
     523             :   ///
     524             :   /// @param SubRegion The new subregion that will be added.
     525             :   /// @param moveChildren Move the children of this region, that are also
     526             :   ///                     contained in SubRegion into SubRegion.
     527             :   void addSubRegion(RegionT *SubRegion, bool moveChildren = false);
     528             : 
     529             :   /// @brief Remove a subregion from this Region.
     530             :   ///
     531             :   /// The subregion is not deleted, as it will probably be inserted into another
     532             :   /// region.
     533             :   /// @param SubRegion The SubRegion that will be removed.
     534             :   RegionT *removeSubRegion(RegionT *SubRegion);
     535             : 
     536             :   /// @brief Move all direct child nodes of this Region to another Region.
     537             :   ///
     538             :   /// @param To The Region the child nodes will be transferred to.
     539             :   void transferChildrenTo(RegionT *To);
     540             : 
     541             :   /// @brief Verify if the region is a correct region.
     542             :   ///
     543             :   /// Check if this is a correctly build Region. This is an expensive check, as
     544             :   /// the complete CFG of the Region will be walked.
     545             :   void verifyRegion() const;
     546             : 
     547             :   /// @brief Clear the cache for BB RegionNodes.
     548             :   ///
     549             :   /// After calling this function the BasicBlock RegionNodes will be stored at
     550             :   /// different memory locations. RegionNodes obtained before this function is
     551             :   /// called are therefore not comparable to RegionNodes abtained afterwords.
     552             :   void clearNodeCache();
     553             : 
     554             :   /// @name Subregion Iterators
     555             :   ///
     556             :   /// These iterators iterator over all subregions of this Region.
     557             :   //@{
     558             :   using iterator = typename RegionSet::iterator;
     559             :   using const_iterator = typename RegionSet::const_iterator;
     560             : 
     561           0 :   iterator begin() { return children.begin(); }
     562           0 :   iterator end() { return children.end(); }
     563             : 
     564        1719 :   const_iterator begin() const { return children.begin(); }
     565        1719 :   const_iterator end() const { return children.end(); }
     566             :   //@}
     567             : 
     568             :   /// @name BasicBlock Iterators
     569             :   ///
     570             :   /// These iterators iterate over all BasicBlocks that are contained in this
     571             :   /// Region. The iterator also iterates over BasicBlocks that are elements of
     572             :   /// a subregion of this Region. It is therefore called a flat iterator.
     573             :   //@{
     574             :   template <bool IsConst>
     575       42637 :   class block_iterator_wrapper
     576             :       : public df_iterator<
     577             :             typename std::conditional<IsConst, const BlockT, BlockT>::type *> {
     578             :     using super =
     579             :         df_iterator<
     580             :             typename std::conditional<IsConst, const BlockT, BlockT>::type *>;
     581             : 
     582             :   public:
     583             :     using Self = block_iterator_wrapper<IsConst>;
     584             :     using value_type = typename super::value_type;
     585             : 
     586             :     // Construct the begin iterator.
     587             :     block_iterator_wrapper(value_type Entry, value_type Exit)
     588             :         : super(df_begin(Entry)) {
     589             :       // Mark the exit of the region as visited, so that the children of the
     590             :       // exit and the exit itself, i.e. the block outside the region will never
     591             :       // be visited.
     592        7180 :       super::Visited.insert(Exit);
     593             :     }
     594             : 
     595             :     // Construct the end iterator.
     596             :     block_iterator_wrapper() : super(df_end<value_type>((BlockT *)nullptr)) {}
     597             : 
     598             :     /*implicit*/ block_iterator_wrapper(super I) : super(I) {}
     599             : 
     600             :     // FIXME: Even a const_iterator returns a non-const BasicBlock pointer.
     601             :     //        This was introduced for backwards compatibility, but should
     602             :     //        be removed as soon as all users are fixed.
     603             :     BlockT *operator*() const {
     604      185890 :       return const_cast<BlockT *>(super::operator*());
     605             :     }
     606             :   };
     607             : 
     608             :   using block_iterator = block_iterator_wrapper<false>;
     609             :   using const_block_iterator = block_iterator_wrapper<true>;
     610             : 
     611         212 :   block_iterator block_begin() { return block_iterator(getEntry(), getExit()); }
     612             : 
     613           0 :   block_iterator block_end() { return block_iterator(); }
     614             : 
     615           0 :   const_block_iterator block_begin() const {
     616           0 :     return const_block_iterator(getEntry(), getExit());
     617             :   }
     618           0 :   const_block_iterator block_end() const { return const_block_iterator(); }
     619             : 
     620             :   using block_range = iterator_range<block_iterator>;
     621             :   using const_block_range = iterator_range<const_block_iterator>;
     622             : 
     623             :   /// @brief Returns a range view of the basic blocks in the region.
     624        6964 :   inline block_range blocks() {
     625       13928 :     return block_range(block_begin(), block_end());
     626             :   }
     627             : 
     628             :   /// @brief Returns a range view of the basic blocks in the region.
     629             :   ///
     630             :   /// This is the 'const' version of the range view.
     631           4 :   inline const_block_range blocks() const {
     632           8 :     return const_block_range(block_begin(), block_end());
     633             :   }
     634             :   //@}
     635             : 
     636             :   /// @name Element Iterators
     637             :   ///
     638             :   /// These iterators iterate over all BasicBlock and subregion RegionNodes that
     639             :   /// are direct children of this Region. It does not iterate over any
     640             :   /// RegionNodes that are also element of a subregion of this Region.
     641             :   //@{
     642             :   using element_iterator =
     643             :       df_iterator<RegionNodeT *, df_iterator_default_set<RegionNodeT *>, false,
     644             :                   GraphTraits<RegionNodeT *>>;
     645             : 
     646             :   using const_element_iterator =
     647             :       df_iterator<const RegionNodeT *,
     648             :                   df_iterator_default_set<const RegionNodeT *>, false,
     649             :                   GraphTraits<const RegionNodeT *>>;
     650             : 
     651             :   element_iterator element_begin();
     652             :   element_iterator element_end();
     653         686 :   iterator_range<element_iterator> elements() {
     654         686 :     return make_range(element_begin(), element_end());
     655             :   }
     656             : 
     657             :   const_element_iterator element_begin() const;
     658             :   const_element_iterator element_end() const;
     659           4 :   iterator_range<const_element_iterator> elements() const {
     660           4 :     return make_range(element_begin(), element_end());
     661             :   }
     662             :   //@}
     663             : };
     664             : 
     665             : /// Print a RegionNode.
     666             : template <class Tr>
     667             : inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase<Tr> &Node);
     668             : 
     669             : //===----------------------------------------------------------------------===//
     670             : /// @brief Analysis that detects all canonical Regions.
     671             : ///
     672             : /// The RegionInfo pass detects all canonical regions in a function. The Regions
     673             : /// are connected using the parent relation. This builds a Program Structure
     674             : /// Tree.
     675             : template <class Tr>
     676        9036 : class RegionInfoBase {
     677             :   friend class RegionInfo;
     678             :   friend class MachineRegionInfo;
     679             : 
     680             :   using BlockT = typename Tr::BlockT;
     681             :   using FuncT = typename Tr::FuncT;
     682             :   using RegionT = typename Tr::RegionT;
     683             :   using RegionInfoT = typename Tr::RegionInfoT;
     684             :   using DomTreeT = typename Tr::DomTreeT;
     685             :   using DomTreeNodeT = typename Tr::DomTreeNodeT;
     686             :   using PostDomTreeT = typename Tr::PostDomTreeT;
     687             :   using DomFrontierT = typename Tr::DomFrontierT;
     688             :   using BlockTraits = GraphTraits<BlockT *>;
     689             :   using InvBlockTraits = GraphTraits<Inverse<BlockT *>>;
     690             :   using SuccIterTy = typename BlockTraits::ChildIteratorType;
     691             :   using PredIterTy = typename InvBlockTraits::ChildIteratorType;
     692             : 
     693             :   using BBtoBBMap = DenseMap<BlockT *, BlockT *>;
     694             :   using BBtoRegionMap = DenseMap<BlockT *, RegionT *>;
     695             : 
     696             :   RegionInfoBase();
     697             : 
     698           0 :   RegionInfoBase(RegionInfoBase &&Arg)
     699             :     : DT(std::move(Arg.DT)), PDT(std::move(Arg.PDT)), DF(std::move(Arg.DF)),
     700             :       TopLevelRegion(std::move(Arg.TopLevelRegion)),
     701           0 :       BBtoRegion(std::move(Arg.BBtoRegion)) {
     702             :     Arg.wipe();
     703           0 :   }
     704             : 
     705           0 :   RegionInfoBase &operator=(RegionInfoBase &&RHS) {
     706           0 :     DT = std::move(RHS.DT);
     707           0 :     PDT = std::move(RHS.PDT);
     708           0 :     DF = std::move(RHS.DF);
     709           0 :     TopLevelRegion = std::move(RHS.TopLevelRegion);
     710           0 :     BBtoRegion = std::move(RHS.BBtoRegion);
     711             :     RHS.wipe();
     712           0 :     return *this;
     713             :   }
     714             : 
     715             :   virtual ~RegionInfoBase();
     716             : 
     717             :   DomTreeT *DT;
     718             :   PostDomTreeT *PDT;
     719             :   DomFrontierT *DF;
     720             : 
     721             :   /// The top level region.
     722             :   RegionT *TopLevelRegion = nullptr;
     723             : 
     724             :   /// Map every BB to the smallest region, that contains BB.
     725             :   BBtoRegionMap BBtoRegion;
     726             : 
     727             : protected:
     728             :   /// \brief Update refences to a RegionInfoT held by the RegionT managed here
     729             :   ///
     730             :   /// This is a post-move helper. Regions hold references to the owning
     731             :   /// RegionInfo object. After a move these need to be fixed.
     732             :   template<typename TheRegionT>
     733          28 :   void updateRegionTree(RegionInfoT &RI, TheRegionT *R) {
     734          28 :     if (!R)
     735             :       return;
     736          28 :     R->RI = &RI;
     737          44 :     for (auto &SubR : *R)
     738          16 :       updateRegionTree(RI, SubR.get());
     739             :   }
     740             : 
     741             : private:
     742             :   /// \brief Wipe this region tree's state without releasing any resources.
     743             :   ///
     744             :   /// This is essentially a post-move helper only. It leaves the object in an
     745             :   /// assignable and destroyable state, but otherwise invalid.
     746           0 :   void wipe() {
     747           0 :     DT = nullptr;
     748           0 :     PDT = nullptr;
     749           0 :     DF = nullptr;
     750           0 :     TopLevelRegion = nullptr;
     751           0 :     BBtoRegion.clear();
     752           0 :   }
     753             : 
     754             :   // Check whether the entries of BBtoRegion for the BBs of region
     755             :   // SR are correct. Triggers an assertion if not. Calls itself recursively for
     756             :   // subregions.
     757             :   void verifyBBMap(const RegionT *SR) const;
     758             : 
     759             :   // Returns true if BB is in the dominance frontier of
     760             :   // entry, because it was inherited from exit. In the other case there is an
     761             :   // edge going from entry to BB without passing exit.
     762             :   bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;
     763             : 
     764             :   // Check if entry and exit surround a valid region, based on
     765             :   // dominance tree and dominance frontier.
     766             :   bool isRegion(BlockT *entry, BlockT *exit) const;
     767             : 
     768             :   // Saves a shortcut pointing from entry to exit.
     769             :   // This function may extend this shortcut if possible.
     770             :   void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const;
     771             : 
     772             :   // Returns the next BB that postdominates N, while skipping
     773             :   // all post dominators that cannot finish a canonical region.
     774             :   DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const;
     775             : 
     776             :   // A region is trivial, if it contains only one BB.
     777             :   bool isTrivialRegion(BlockT *entry, BlockT *exit) const;
     778             : 
     779             :   // Creates a single entry single exit region.
     780             :   RegionT *createRegion(BlockT *entry, BlockT *exit);
     781             : 
     782             :   // Detect all regions starting with bb 'entry'.
     783             :   void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut);
     784             : 
     785             :   // Detects regions in F.
     786             :   void scanForRegions(FuncT &F, BBtoBBMap *ShortCut);
     787             : 
     788             :   // Get the top most parent with the same entry block.
     789             :   RegionT *getTopMostParent(RegionT *region);
     790             : 
     791             :   // Build the region hierarchy after all region detected.
     792             :   void buildRegionsTree(DomTreeNodeT *N, RegionT *region);
     793             : 
     794             :   // Update statistic about created regions.
     795             :   virtual void updateStatistics(RegionT *R) = 0;
     796             : 
     797             :   // Detect all regions in function and build the region tree.
     798             :   void calculate(FuncT &F);
     799             : 
     800             : public:
     801             :   RegionInfoBase(const RegionInfoBase &) = delete;
     802             :   RegionInfoBase &operator=(const RegionInfoBase &) = delete;
     803             : 
     804             :   static bool VerifyRegionInfo;
     805             :   static typename RegionT::PrintStyle printStyle;
     806             : 
     807             :   void print(raw_ostream &OS) const;
     808             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     809             :   void dump() const;
     810             : #endif
     811             : 
     812             :   void releaseMemory();
     813             : 
     814             :   /// @brief Get the smallest region that contains a BasicBlock.
     815             :   ///
     816             :   /// @param BB The basic block.
     817             :   /// @return The smallest region, that contains BB or NULL, if there is no
     818             :   /// region containing BB.
     819             :   RegionT *getRegionFor(BlockT *BB) const;
     820             : 
     821             :   /// @brief  Set the smallest region that surrounds a basic block.
     822             :   ///
     823             :   /// @param BB The basic block surrounded by a region.
     824             :   /// @param R The smallest region that surrounds BB.
     825             :   void setRegionFor(BlockT *BB, RegionT *R);
     826             : 
     827             :   /// @brief A shortcut for getRegionFor().
     828             :   ///
     829             :   /// @param BB The basic block.
     830             :   /// @return The smallest region, that contains BB or NULL, if there is no
     831             :   /// region containing BB.
     832             :   RegionT *operator[](BlockT *BB) const;
     833             : 
     834             :   /// @brief Return the exit of the maximal refined region, that starts at a
     835             :   /// BasicBlock.
     836             :   ///
     837             :   /// @param BB The BasicBlock the refined region starts.
     838             :   BlockT *getMaxRegionExit(BlockT *BB) const;
     839             : 
     840             :   /// @brief Find the smallest region that contains two regions.
     841             :   ///
     842             :   /// @param A The first region.
     843             :   /// @param B The second region.
     844             :   /// @return The smallest region containing A and B.
     845             :   RegionT *getCommonRegion(RegionT *A, RegionT *B) const;
     846             : 
     847             :   /// @brief Find the smallest region that contains two basic blocks.
     848             :   ///
     849             :   /// @param A The first basic block.
     850             :   /// @param B The second basic block.
     851             :   /// @return The smallest region that contains A and B.
     852           0 :   RegionT *getCommonRegion(BlockT *A, BlockT *B) const {
     853           0 :     return getCommonRegion(getRegionFor(A), getRegionFor(B));
     854             :   }
     855             : 
     856             :   /// @brief Find the smallest region that contains a set of regions.
     857             :   ///
     858             :   /// @param Regions A vector of regions.
     859             :   /// @return The smallest region that contains all regions in Regions.
     860             :   RegionT *getCommonRegion(SmallVectorImpl<RegionT *> &Regions) const;
     861             : 
     862             :   /// @brief Find the smallest region that contains a set of basic blocks.
     863             :   ///
     864             :   /// @param BBs A vector of basic blocks.
     865             :   /// @return The smallest region that contains all basic blocks in BBS.
     866             :   RegionT *getCommonRegion(SmallVectorImpl<BlockT *> &BBs) const;
     867             : 
     868           0 :   RegionT *getTopLevelRegion() const { return TopLevelRegion; }
     869             : 
     870             :   /// @brief Clear the Node Cache for all Regions.
     871             :   ///
     872             :   /// @see Region::clearNodeCache()
     873           0 :   void clearNodeCache() {
     874       27673 :     if (TopLevelRegion)
     875       27673 :       TopLevelRegion->clearNodeCache();
     876           0 :   }
     877             : 
     878             :   void verifyAnalysis() const;
     879             : };
     880             : 
     881             : class Region;
     882             : 
     883             : class RegionNode : public RegionNodeBase<RegionTraits<Function>> {
     884             : public:
     885             :   inline RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion = false)
     886             :       : RegionNodeBase<RegionTraits<Function>>(Parent, Entry, isSubRegion) {}
     887             : 
     888             :   bool operator==(const Region &RN) const {
     889             :     return this == reinterpret_cast<const RegionNode *>(&RN);
     890             :   }
     891             : };
     892             : 
     893       29318 : class Region : public RegionBase<RegionTraits<Function>> {
     894             : public:
     895             :   Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT,
     896             :          Region *Parent = nullptr);
     897             :   ~Region();
     898             : 
     899             :   bool operator==(const RegionNode &RN) const {
     900             :     return &RN == reinterpret_cast<const RegionNode *>(this);
     901             :   }
     902             : };
     903             : 
     904        8994 : class RegionInfo : public RegionInfoBase<RegionTraits<Function>> {
     905             : public:
     906             :   using Base = RegionInfoBase<RegionTraits<Function>>;
     907             : 
     908             :   explicit RegionInfo();
     909             : 
     910          12 :   RegionInfo(RegionInfo &&Arg) : Base(std::move(static_cast<Base &>(Arg))) {
     911          12 :     updateRegionTree(*this, TopLevelRegion);
     912          12 :   }
     913             : 
     914             :   RegionInfo &operator=(RegionInfo &&RHS) {
     915             :     Base::operator=(std::move(static_cast<Base &>(RHS)));
     916             :     updateRegionTree(*this, TopLevelRegion);
     917             :     return *this;
     918             :   }
     919             : 
     920             :   ~RegionInfo() override;
     921             : 
     922             :   /// Handle invalidation explicitly.
     923             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     924             :                   FunctionAnalysisManager::Invalidator &);
     925             : 
     926             :   // updateStatistics - Update statistic about created regions.
     927             :   void updateStatistics(Region *R) final;
     928             : 
     929             :   void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT,
     930             :                    DominanceFrontier *DF);
     931             : 
     932             : #ifndef NDEBUG
     933             :   /// @brief Opens a viewer to show the GraphViz visualization of the regions.
     934             :   ///
     935             :   /// Useful during debugging as an alternative to dump().
     936             :   void view();
     937             : 
     938             :   /// @brief Opens a viewer to show the GraphViz visualization of this region
     939             :   /// without instructions in the BasicBlocks.
     940             :   ///
     941             :   /// Useful during debugging as an alternative to dump().
     942             :   void viewOnly();
     943             : #endif
     944             : };
     945             : 
     946       13374 : class RegionInfoPass : public FunctionPass {
     947             :   RegionInfo RI;
     948             : 
     949             : public:
     950             :   static char ID;
     951             : 
     952             :   explicit RegionInfoPass();
     953             :   ~RegionInfoPass() override;
     954             : 
     955       24490 :   RegionInfo &getRegionInfo() { return RI; }
     956             : 
     957             :   const RegionInfo &getRegionInfo() const { return RI; }
     958             : 
     959             :   /// @name FunctionPass interface
     960             :   //@{
     961             :   bool runOnFunction(Function &F) override;
     962             :   void releaseMemory() override;
     963             :   void verifyAnalysis() const override;
     964             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     965             :   void print(raw_ostream &OS, const Module *) const override;
     966             :   void dump() const;
     967             :   //@}
     968             : };
     969             : 
     970             : /// \brief Analysis pass that exposes the \c RegionInfo for a function.
     971             : class RegionInfoAnalysis : public AnalysisInfoMixin<RegionInfoAnalysis> {
     972             :   friend AnalysisInfoMixin<RegionInfoAnalysis>;
     973             : 
     974             :   static AnalysisKey Key;
     975             : 
     976             : public:
     977             :   using Result = RegionInfo;
     978             : 
     979             :   RegionInfo run(Function &F, FunctionAnalysisManager &AM);
     980             : };
     981             : 
     982             : /// \brief Printer pass for the \c RegionInfo.
     983             : class RegionInfoPrinterPass : public PassInfoMixin<RegionInfoPrinterPass> {
     984             :   raw_ostream &OS;
     985             : 
     986             : public:
     987             :   explicit RegionInfoPrinterPass(raw_ostream &OS);
     988             : 
     989             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     990             : };
     991             : 
     992             : /// \brief Verifier pass for the \c RegionInfo.
     993             : struct RegionInfoVerifierPass : PassInfoMixin<RegionInfoVerifierPass> {
     994             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     995             : };
     996             : 
     997             : template <>
     998             : template <>
     999             : inline BasicBlock *
    1000             : RegionNodeBase<RegionTraits<Function>>::getNodeAs<BasicBlock>() const {
    1001             :   assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
    1002             :   return getEntry();
    1003             : }
    1004             : 
    1005             : template <>
    1006             : template <>
    1007             : inline Region *
    1008             : RegionNodeBase<RegionTraits<Function>>::getNodeAs<Region>() const {
    1009             :   assert(isSubRegion() && "This is not a subregion RegionNode!");
    1010             :   auto Unconst = const_cast<RegionNodeBase<RegionTraits<Function>> *>(this);
    1011             :   return reinterpret_cast<Region *>(Unconst);
    1012             : }
    1013             : 
    1014             : template <class Tr>
    1015           8 : inline raw_ostream &operator<<(raw_ostream &OS,
    1016             :                                const RegionNodeBase<Tr> &Node) {
    1017             :   using BlockT = typename Tr::BlockT;
    1018             :   using RegionT = typename Tr::RegionT;
    1019             : 
    1020           8 :   if (Node.isSubRegion())
    1021           4 :     return OS << Node.template getNodeAs<RegionT>()->getNameStr();
    1022             :   else
    1023           6 :     return OS << Node.template getNodeAs<BlockT>()->getName();
    1024             : }
    1025             : 
    1026             : extern template class RegionBase<RegionTraits<Function>>;
    1027             : extern template class RegionNodeBase<RegionTraits<Function>>;
    1028             : extern template class RegionInfoBase<RegionTraits<Function>>;
    1029             : 
    1030             : } // end namespace llvm
    1031             : 
    1032             : #endif // LLVM_ANALYSIS_REGIONINFO_H

Generated by: LCOV version 1.13