Line data    Source code

       1             : //===- lib/CodeGen/CalcSpillWeights.h ---------------------------*- 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             : #ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H
      11             : #define LLVM_CODEGEN_CALCSPILLWEIGHTS_H
      12             : 
      13             : #include "llvm/ADT/DenseMap.h"
      14             : #include "llvm/CodeGen/SlotIndexes.h"
      15             : 
      16             : namespace llvm {
      17             : 
      18             : class LiveInterval;
      19             : class LiveIntervals;
      20             : class MachineBlockFrequencyInfo;
      21             : class MachineFunction;
      22             : class MachineLoopInfo;
      23             : class VirtRegMap;
      24             : 
      25             :   /// Normalize the spill weight of a live interval
      26             :   ///
      27             :   /// The spill weight of a live interval is computed as:
      28             :   ///
      29             :   ///   (sum(use freq) + sum(def freq)) / (K + size)
      30             :   ///
      31             :   /// @param UseDefFreq Expected number of executed use and def instructions
      32             :   ///                   per function call. Derived from block frequencies.
      33             :   /// @param Size       Size of live interval as returnexd by getSize()
      34             :   /// @param NumInstr   Number of instructions using this live interval
      35      885610 :   static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size,
      36             :                                            unsigned NumInstr) {
      37             :     // The constant 25 instructions is added to avoid depending too much on
      38             :     // accidental SlotIndex gaps for small intervals. The effect is that small
      39             :     // intervals have a spill weight that is mostly proportional to the number
      40             :     // of uses, while large intervals get a spill weight that is closer to a use
      41             :     // density.
      42     1988569 :     return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
      43             :   }
      44             : 
      45             :   /// Calculate auxiliary information for a virtual register such as its
      46             :   /// spill weight and allocation hint.
      47             :   class VirtRegAuxInfo {
      48             :   public:
      49             :     using NormalizingFn = float (*)(float, unsigned, unsigned);
      50             : 
      51             :   private:
      52             :     MachineFunction &MF;
      53             :     LiveIntervals &LIS;
      54             :     VirtRegMap *VRM;
      55             :     const MachineLoopInfo &Loops;
      56             :     const MachineBlockFrequencyInfo &MBFI;
      57             :     DenseMap<unsigned, float> Hint;
      58             :     NormalizingFn normalize;
      59             : 
      60             :   public:
      61             :     VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis,
      62             :                    VirtRegMap *vrm, const MachineLoopInfo &loops,
      63             :                    const MachineBlockFrequencyInfo &mbfi,
      64             :                    NormalizingFn norm = normalizeSpillWeight)
      65      251316 :         : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {}
      66             : 
      67             :     /// (re)compute li's spill weight and allocation hint.
      68             :     void calculateSpillWeightAndHint(LiveInterval &li);
      69             : 
      70             :     /// Compute future expected spill weight of a split artifact of li
      71             :     /// that will span between start and end slot indexes.
      72             :     /// \param li     The live interval to be split.
      73             :     /// \param start  The expected begining of the split artifact. Instructions
      74             :     ///               before start will not affect the weight.
      75             :     /// \param end    The expected end of the split artifact. Instructions
      76             :     ///               after end will not affect the weight.
      77             :     /// \return The expected spill weight of the split artifact. Returns
      78             :     /// negative weight for unspillable li.
      79             :     float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end);
      80             : 
      81             :     /// Helper function for weight calculations.
      82             :     /// (Re)compute li's spill weight and allocation hint, or, for non null
      83             :     /// start and end - compute future expected spill weight of a split
      84             :     /// artifact of li that will span between start and end slot indexes.
      85             :     /// \param li     The live interval for which to compute the weight.
      86             :     /// \param start  The expected begining of the split artifact. Instructions
      87             :     ///               before start will not affect the weight. Relevant for
      88             :     ///               weight calculation of future split artifact.
      89             :     /// \param end    The expected end of the split artifact. Instructions
      90             :     ///               after end will not affect the weight. Relevant for
      91             :     ///               weight calculation of future split artifact.
      92             :     /// \return The spill weight. Returns negative weight for unspillable li.
      93             :     float weightCalcHelper(LiveInterval &li, SlotIndex *start = nullptr,
      94             :                            SlotIndex *end = nullptr);
      95             :   };
      96             : 
      97             :   /// Compute spill weights and allocation hints for all virtual register
      98             :   /// live intervals.
      99             :   void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF,
     100             :                                      VirtRegMap *VRM,
     101             :                                      const MachineLoopInfo &MLI,
     102             :                                      const MachineBlockFrequencyInfo &MBFI,
     103             :                                      VirtRegAuxInfo::NormalizingFn norm =
     104             :                                          normalizeSpillWeight);
     105             : 
     106             : } // end namespace llvm
     107             : 
     108             : #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H