include/llvm/CodeGen/CalcSpillWeights.h

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