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

Generated by: LCOV version 1.13