LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRangeCalc.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 7 7 100.0 %
Date: 2017-09-14 15:23:50 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LiveRangeCalc.h - Calculate live ranges ------------------*- 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             : // The LiveRangeCalc class can be used to compute live ranges from scratch.  It
      11             : // caches information about values in the CFG to speed up repeated operations
      12             : // on the same live range.  The cache can be shared by non-overlapping live
      13             : // ranges.  SplitKit uses that when computing the live range of split products.
      14             : //
      15             : // A low-level interface is available to clients that know where a variable is
      16             : // live, but don't know which value it has as every point.  LiveRangeCalc will
      17             : // propagate values down the dominator tree, and even insert PHI-defs where
      18             : // needed.  SplitKit uses this faster interface when possible.
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H
      23             : #define LLVM_LIB_CODEGEN_LIVERANGECALC_H
      24             : 
      25             : #include "llvm/ADT/ArrayRef.h"
      26             : #include "llvm/ADT/BitVector.h"
      27             : #include "llvm/ADT/DenseMap.h"
      28             : #include "llvm/ADT/IndexedMap.h"
      29             : #include "llvm/ADT/SmallVector.h"
      30             : #include "llvm/CodeGen/LiveInterval.h"
      31             : #include "llvm/CodeGen/MachineBasicBlock.h"
      32             : #include "llvm/CodeGen/SlotIndexes.h"
      33             : #include "llvm/MC/LaneBitmask.h"
      34             : #include <utility>
      35             : 
      36             : namespace llvm {
      37             : 
      38             : template <class NodeT> class DomTreeNodeBase;
      39             : class MachineDominatorTree;
      40             : class MachineFunction;
      41             : class MachineRegisterInfo;
      42             : 
      43             : using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
      44             : 
      45     2767372 : class LiveRangeCalc {
      46             :   const MachineFunction *MF = nullptr;
      47             :   const MachineRegisterInfo *MRI = nullptr;
      48             :   SlotIndexes *Indexes = nullptr;
      49             :   MachineDominatorTree *DomTree = nullptr;
      50             :   VNInfo::Allocator *Alloc = nullptr;
      51             : 
      52             :   /// LiveOutPair - A value and the block that defined it.  The domtree node is
      53             :   /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)].
      54             :   using LiveOutPair = std::pair<VNInfo *, MachineDomTreeNode *>;
      55             : 
      56             :   /// LiveOutMap - Map basic blocks to the value leaving the block.
      57             :   using LiveOutMap = IndexedMap<LiveOutPair, MBB2NumberFunctor>;
      58             : 
      59             :   /// Bit vector of active entries in LiveOut, also used as a visited set by
      60             :   /// findReachingDefs.  One entry per basic block, indexed by block number.
      61             :   /// This is kept as a separate bit vector because it can be cleared quickly
      62             :   /// when switching live ranges.
      63             :   BitVector Seen;
      64             : 
      65             :   /// Map LiveRange to sets of blocks (represented by bit vectors) that
      66             :   /// in the live range are defined on entry and undefined on entry.
      67             :   /// A block is defined on entry if there is a path from at least one of
      68             :   /// the defs in the live range to the entry of the block, and conversely,
      69             :   /// a block is undefined on entry, if there is no such path (i.e. no
      70             :   /// definition reaches the entry of the block). A single LiveRangeCalc
      71             :   /// object is used to track live-out information for multiple registers
      72             :   /// in live range splitting (which is ok, since the live ranges of these
      73             :   /// registers do not overlap), but the defined/undefined information must
      74             :   /// be kept separate for each individual range.
      75             :   /// By convention, EntryInfoMap[&LR] = { Defined, Undefined }.
      76             :   using EntryInfoMap = DenseMap<LiveRange *, std::pair<BitVector, BitVector>>;
      77             :   EntryInfoMap EntryInfos;
      78             : 
      79             :   /// Map each basic block where a live range is live out to the live-out value
      80             :   /// and its defining block.
      81             :   ///
      82             :   /// For every basic block, MBB, one of these conditions shall be true:
      83             :   ///
      84             :   ///  1. !Seen.count(MBB->getNumber())
      85             :   ///     Blocks without a Seen bit are ignored.
      86             :   ///  2. LiveOut[MBB].second.getNode() == MBB
      87             :   ///     The live-out value is defined in MBB.
      88             :   ///  3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
      89             :   ///     The live-out value passses through MBB. All predecessors must carry
      90             :   ///     the same value.
      91             :   ///
      92             :   /// The domtree node may be null, it can be computed.
      93             :   ///
      94             :   /// The map can be shared by multiple live ranges as long as no two are
      95             :   /// live-out of the same block.
      96             :   LiveOutMap Map;
      97             : 
      98             :   /// LiveInBlock - Information about a basic block where a live range is known
      99             :   /// to be live-in, but the value has not yet been determined.
     100             :   struct LiveInBlock {
     101             :     // The live range set that is live-in to this block.  The algorithms can
     102             :     // handle multiple non-overlapping live ranges simultaneously.
     103             :     LiveRange &LR;
     104             : 
     105             :     // DomNode - Dominator tree node for the block.
     106             :     // Cleared when the final value has been determined and LI has been updated.
     107             :     MachineDomTreeNode *DomNode;
     108             : 
     109             :     // Position in block where the live-in range ends, or SlotIndex() if the
     110             :     // range passes through the block.  When the final value has been
     111             :     // determined, the range from the block start to Kill will be added to LI.
     112             :     SlotIndex Kill;
     113             : 
     114             :     // Live-in value filled in by updateSSA once it is known.
     115             :     VNInfo *Value = nullptr;
     116             : 
     117             :     LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill)
     118      129369 :       : LR(LR), DomNode(node), Kill(kill) {}
     119             :   };
     120             : 
     121             :   /// LiveIn - Work list of blocks where the live-in value has yet to be
     122             :   /// determined.  This list is typically computed by findReachingDefs() and
     123             :   /// used as a work list by updateSSA().  The low-level interface may also be
     124             :   /// used to add entries directly.
     125             :   SmallVector<LiveInBlock, 16> LiveIn;
     126             : 
     127             :   /// Check if the entry to block @p MBB can be reached by any of the defs
     128             :   /// in @p LR. Return true if none of the defs reach the entry to @p MBB.
     129             :   bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
     130             :                     MachineBasicBlock &MBB, BitVector &DefOnEntry,
     131             :                     BitVector &UndefOnEntry);
     132             : 
     133             :   /// Find the set of defs that can reach @p Kill. @p Kill must belong to
     134             :   /// @p UseMBB.
     135             :   ///
     136             :   /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill,
     137             :   /// all paths from the def to @p UseMBB are added to @p LR, and the function
     138             :   /// returns true.
     139             :   ///
     140             :   /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be
     141             :   /// live in are added to the LiveIn array, and the function returns false.
     142             :   ///
     143             :   /// The array @p Undef provides the locations where the range @p LR becomes
     144             :   /// undefined by <def,read-undef> operands on other subranges. If @p Undef
     145             :   /// is non-empty and @p Kill is jointly dominated only by the entries of
     146             :   /// @p Undef, the function returns false.
     147             :   ///
     148             :   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
     149             :   bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
     150             :                         SlotIndex Kill, unsigned PhysReg,
     151             :                         ArrayRef<SlotIndex> Undefs);
     152             : 
     153             :   /// updateSSA - Compute the values that will be live in to all requested
     154             :   /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
     155             :   ///
     156             :   /// Every live-in block must be jointly dominated by the added live-out
     157             :   /// blocks.  No values are read from the live ranges.
     158             :   void updateSSA();
     159             : 
     160             :   /// Transfer information from the LiveIn vector to the live ranges and update
     161             :   /// the given @p LiveOuts.
     162             :   void updateFromLiveIns();
     163             : 
     164             :   /// Extend the live range of @p LR to reach all uses of Reg.
     165             :   ///
     166             :   /// If @p LR is a main range, or if @p LI is null, then all uses must be
     167             :   /// jointly dominated by the definitions from @p LR. If @p LR is a subrange
     168             :   /// of the live interval @p LI, corresponding to lane mask @p LaneMask,
     169             :   /// all uses must be jointly dominated by the definitions from @p LR
     170             :   /// together with definitions of other lanes where @p LR becomes undefined
     171             :   /// (via <def,read-undef> operands).
     172             :   /// If @p LR is a main range, the @p LaneMask should be set to ~0, i.e.
     173             :   /// LaneBitmask::getAll().
     174             :   void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask,
     175             :                     LiveInterval *LI = nullptr);
     176             : 
     177             :   /// Reset Map and Seen fields.
     178             :   void resetLiveOutMap();
     179             : 
     180             : public:
     181     2767610 :   LiveRangeCalc() = default;
     182             : 
     183             :   //===--------------------------------------------------------------------===//
     184             :   // High-level interface.
     185             :   //===--------------------------------------------------------------------===//
     186             :   //
     187             :   // Calculate live ranges from scratch.
     188             :   //
     189             : 
     190             :   /// reset - Prepare caches for a new set of non-overlapping live ranges.  The
     191             :   /// caches must be reset before attempting calculations with a live range
     192             :   /// that may overlap a previously computed live range, and before the first
     193             :   /// live range in a function.  If live ranges are not known to be
     194             :   /// non-overlapping, call reset before each.
     195             :   void reset(const MachineFunction *mf, SlotIndexes *SI,
     196             :              MachineDominatorTree *MDT, VNInfo::Allocator *VNIA);
     197             : 
     198             :   //===--------------------------------------------------------------------===//
     199             :   // Mid-level interface.
     200             :   //===--------------------------------------------------------------------===//
     201             :   //
     202             :   // Modify existing live ranges.
     203             :   //
     204             : 
     205             :   /// Extend the live range of @p LR to reach @p Use.
     206             :   ///
     207             :   /// The existing values in @p LR must be live so they jointly dominate @p Use.
     208             :   /// If @p Use is not dominated by a single existing value, PHI-defs are
     209             :   /// inserted as required to preserve SSA form.
     210             :   ///
     211             :   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
     212             :   void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
     213             :               ArrayRef<SlotIndex> Undefs);
     214             : 
     215             :   /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
     216             :   /// Each instruction defining Reg gets a new VNInfo with a corresponding
     217             :   /// minimal live range.
     218             :   void createDeadDefs(LiveRange &LR, unsigned Reg);
     219             : 
     220             :   /// Extend the live range of @p LR to reach all uses of Reg.
     221             :   ///
     222             :   /// All uses must be jointly dominated by existing liveness.  PHI-defs are
     223             :   /// inserted as needed to preserve SSA form.
     224             :   void extendToUses(LiveRange &LR, unsigned PhysReg) {
     225      419873 :     extendToUses(LR, PhysReg, LaneBitmask::getAll());
     226             :   }
     227             : 
     228             :   /// Calculates liveness for the register specified in live interval @p LI.
     229             :   /// Creates subregister live ranges as needed if subreg liveness tracking is
     230             :   /// enabled.
     231             :   void calculate(LiveInterval &LI, bool TrackSubRegs);
     232             : 
     233             :   /// For live interval \p LI with correct SubRanges construct matching
     234             :   /// information for the main live range. Expects the main live range to not
     235             :   /// have any segments or value numbers.
     236             :   void constructMainRangeFromSubranges(LiveInterval &LI);
     237             : 
     238             :   //===--------------------------------------------------------------------===//
     239             :   // Low-level interface.
     240             :   //===--------------------------------------------------------------------===//
     241             :   //
     242             :   // These functions can be used to compute live ranges where the live-in and
     243             :   // live-out blocks are already known, but the SSA value in each block is
     244             :   // unknown.
     245             :   //
     246             :   // After calling reset(), add known live-out values and known live-in blocks.
     247             :   // Then call calculateValues() to compute the actual value that is
     248             :   // live-in to each block, and add liveness to the live ranges.
     249             :   //
     250             : 
     251             :   /// setLiveOutValue - Indicate that VNI is live out from MBB.  The
     252             :   /// calculateValues() function will not add liveness for MBB, the caller
     253             :   /// should take care of that.
     254             :   ///
     255             :   /// VNI may be null only if MBB is a live-through block also passed to
     256             :   /// addLiveInBlock().
     257             :   void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) {
     258     2830896 :     Seen.set(MBB->getNumber());
     259     5661792 :     Map[MBB] = LiveOutPair(VNI, nullptr);
     260             :   }
     261             : 
     262             :   /// addLiveInBlock - Add a block with an unknown live-in value.  This
     263             :   /// function can only be called once per basic block.  Once the live-in value
     264             :   /// has been determined, calculateValues() will add liveness to LI.
     265             :   ///
     266             :   /// @param LR      The live range that is live-in to the block.
     267             :   /// @param DomNode The domtree node for the block.
     268             :   /// @param Kill    Index in block where LI is killed.  If the value is
     269             :   ///                live-through, set Kill = SLotIndex() and also call
     270             :   ///                setLiveOutValue(MBB, 0).
     271             :   void addLiveInBlock(LiveRange &LR,
     272             :                       MachineDomTreeNode *DomNode,
     273             :                       SlotIndex Kill = SlotIndex()) {
     274      258738 :     LiveIn.push_back(LiveInBlock(LR, DomNode, Kill));
     275             :   }
     276             : 
     277             :   /// calculateValues - Calculate the value that will be live-in to each block
     278             :   /// added with addLiveInBlock.  Add PHI-def values as needed to preserve SSA
     279             :   /// form.  Add liveness to all live-in blocks up to the Kill point, or the
     280             :   /// whole block for live-through blocks.
     281             :   ///
     282             :   /// Every predecessor of a live-in block must have been given a value with
     283             :   /// setLiveOutValue, the value may be null for live-trough blocks.
     284             :   void calculateValues();
     285             : };
     286             : 
     287             : } // end namespace llvm
     288             : 
     289             : #endif // LLVM_LIB_CODEGEN_LIVERANGECALC_H

Generated by: LCOV version 1.13