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

          Line data    Source code
       1             : //===-- SpillPlacement.h - Optimal Spill Code Placement --------*- 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             : // This analysis computes the optimal spill code placement between basic blocks.
      11             : //
      12             : // The runOnMachineFunction() method only precomputes some profiling information
      13             : // about the CFG. The real work is done by prepare(), addConstraints(), and
      14             : // finish() which are called by the register allocator.
      15             : //
      16             : // Given a variable that is live across multiple basic blocks, and given
      17             : // constraints on the basic blocks where the variable is live, determine which
      18             : // edge bundles should have the variable in a register and which edge bundles
      19             : // should have the variable in a stack slot.
      20             : //
      21             : // The returned bit vector can be used to place optimal spill code at basic
      22             : // block entries and exits. Spill code placement inside a basic block is not
      23             : // considered.
      24             : //
      25             : //===----------------------------------------------------------------------===//
      26             : 
      27             : #ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
      28             : #define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
      29             : 
      30             : #include "llvm/ADT/ArrayRef.h"
      31             : #include "llvm/ADT/SmallVector.h"
      32             : #include "llvm/ADT/SparseSet.h"
      33             : #include "llvm/CodeGen/MachineFunctionPass.h"
      34             : #include "llvm/Support/BlockFrequency.h"
      35             : 
      36             : namespace llvm {
      37             : 
      38             : class BitVector;
      39             : class EdgeBundles;
      40             : class MachineBasicBlock;
      41             : class MachineLoopInfo;
      42             : class MachineBlockFrequencyInfo;
      43             : 
      44             : class SpillPlacement : public MachineFunctionPass {
      45             :   struct Node;
      46             :   const MachineFunction *MF;
      47             :   const EdgeBundles *bundles;
      48             :   const MachineLoopInfo *loops;
      49             :   const MachineBlockFrequencyInfo *MBFI;
      50             :   Node *nodes;
      51             : 
      52             :   // Nodes that are active in the current computation. Owned by the prepare()
      53             :   // caller.
      54             :   BitVector *ActiveNodes;
      55             : 
      56             :   // Nodes with active links. Populated by scanActiveBundles.
      57             :   SmallVector<unsigned, 8> Linked;
      58             : 
      59             :   // Nodes that went positive during the last call to scanActiveBundles or
      60             :   // iterate.
      61             :   SmallVector<unsigned, 8> RecentPositive;
      62             : 
      63             :   // Block frequencies are computed once. Indexed by block number.
      64             :   SmallVector<BlockFrequency, 8> BlockFrequencies;
      65             : 
      66             :   /// Decision threshold. A node gets the output value 0 if the weighted sum of
      67             :   /// its inputs falls in the open interval (-Threshold;Threshold).
      68             :   BlockFrequency Threshold;
      69             : 
      70             :   /// List of nodes that need to be updated in ::iterate.
      71             :   SparseSet<unsigned> TodoList;
      72             : 
      73             : public:
      74             :   static char ID; // Pass identification, replacement for typeid.
      75             : 
      76       91830 :   SpillPlacement() : MachineFunctionPass(ID), nodes(nullptr) {}
      77       76070 :   ~SpillPlacement() override { releaseMemory(); }
      78             : 
      79             :   /// BorderConstraint - A basic block has separate constraints for entry and
      80             :   /// exit.
      81             :   enum BorderConstraint {
      82             :     DontCare,  ///< Block doesn't care / variable not live.
      83             :     PrefReg,   ///< Block entry/exit prefers a register.
      84             :     PrefSpill, ///< Block entry/exit prefers a stack slot.
      85             :     PrefBoth,  ///< Block entry prefers both register and stack.
      86             :     MustSpill  ///< A register is impossible, variable must be spilled.
      87             :   };
      88             : 
      89             :   /// BlockConstraint - Entry and exit constraints for a basic block.
      90             :   struct BlockConstraint {
      91             :     unsigned Number;            ///< Basic block number (from MBB::getNumber()).
      92             :     BorderConstraint Entry : 8; ///< Constraint on block entry.
      93             :     BorderConstraint Exit : 8;  ///< Constraint on block exit.
      94             : 
      95             :     /// True when this block changes the value of the live range. This means
      96             :     /// the block has a non-PHI def.  When this is false, a live-in value on
      97             :     /// the stack can be live-out on the stack without inserting a spill.
      98             :     bool ChangesValue;
      99             :   };
     100             : 
     101             :   /// prepare - Reset state and prepare for a new spill placement computation.
     102             :   /// @param RegBundles Bit vector to receive the edge bundles where the
     103             :   ///                   variable should be kept in a register. Each bit
     104             :   ///                   corresponds to an edge bundle, a set bit means the
     105             :   ///                   variable should be kept in a register through the
     106             :   ///                   bundle. A clear bit means the variable should be
     107             :   ///                   spilled. This vector is retained.
     108             :   void prepare(BitVector &RegBundles);
     109             : 
     110             :   /// addConstraints - Add constraints and biases. This method may be called
     111             :   /// more than once to accumulate constraints.
     112             :   /// @param LiveBlocks Constraints for blocks that have the variable live in or
     113             :   ///                   live out.
     114             :   void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
     115             : 
     116             :   /// addPrefSpill - Add PrefSpill constraints to all blocks listed.  This is
     117             :   /// equivalent to calling addConstraint with identical BlockConstraints with
     118             :   /// Entry = Exit = PrefSpill, and ChangesValue = false.
     119             :   ///
     120             :   /// @param Blocks Array of block numbers that prefer to spill in and out.
     121             :   /// @param Strong When true, double the negative bias for these blocks.
     122             :   void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong);
     123             : 
     124             :   /// addLinks - Add transparent blocks with the given numbers.
     125             :   void addLinks(ArrayRef<unsigned> Links);
     126             : 
     127             :   /// scanActiveBundles - Perform an initial scan of all bundles activated by
     128             :   /// addConstraints and addLinks, updating their state. Add all the bundles
     129             :   /// that now prefer a register to RecentPositive.
     130             :   /// Prepare internal data structures for iterate.
     131             :   /// Return true is there are any positive nodes.
     132             :   bool scanActiveBundles();
     133             : 
     134             :   /// iterate - Update the network iteratively until convergence, or new bundles
     135             :   /// are found.
     136             :   void iterate();
     137             : 
     138             :   /// getRecentPositive - Return an array of bundles that became positive during
     139             :   /// the previous call to scanActiveBundles or iterate.
     140      841848 :   ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
     141             : 
     142             :   /// finish - Compute the optimal spill code placement given the
     143             :   /// constraints. No MustSpill constraints will be violated, and the smallest
     144             :   /// possible number of PrefX constraints will be violated, weighted by
     145             :   /// expected execution frequencies.
     146             :   /// The selected bundles are returned in the bitvector passed to prepare().
     147             :   /// @return True if a perfect solution was found, allowing the variable to be
     148             :   ///         in a register through all relevant bundles.
     149             :   bool finish();
     150             : 
     151             :   /// getBlockFrequency - Return the estimated block execution frequency per
     152             :   /// function invocation.
     153             :   BlockFrequency getBlockFrequency(unsigned Number) const {
     154     3024570 :     return BlockFrequencies[Number];
     155             :   }
     156             : 
     157             : private:
     158             :   bool runOnMachineFunction(MachineFunction&) override;
     159             :   void getAnalysisUsage(AnalysisUsage&) const override;
     160             :   void releaseMemory() override;
     161             : 
     162             :   void activate(unsigned);
     163             :   void setThreshold(const BlockFrequency &Entry);
     164             : 
     165             :   bool update(unsigned);
     166             : };
     167             : 
     168             : } // end namespace llvm
     169             : 
     170             : #endif

Generated by: LCOV version 1.13