Home | History | Annotate | Line # | Download | only in CodeGen 
      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     MachineFunction &MF;
     48     LiveIntervals &LIS;
     49     const VirtRegMap &VRM;
     50     const MachineLoopInfo &Loops;
     51     const MachineBlockFrequencyInfo &MBFI;
     52 
     53     /// Returns true if Reg of live interval LI is used in instruction with many
     54     /// operands like STATEPOINT.
     55     bool isLiveAtStatepointVarArg(LiveInterval &LI);
     56 
     57   public:
     58     VirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS,
     59                    const VirtRegMap &VRM, const MachineLoopInfo &Loops,
     60                    const MachineBlockFrequencyInfo &MBFI)
     61         : MF(MF), LIS(LIS), VRM(VRM), Loops(Loops), MBFI(MBFI) {}
     62 
     63     virtual ~VirtRegAuxInfo() = default;
     64 
     65     /// (re)compute li's spill weight and allocation hint.
     66     void calculateSpillWeightAndHint(LiveInterval &LI);
     67 
     68     /// Compute future expected spill weight of a split artifact of LI
     69     /// that will span between start and end slot indexes.
     70     /// \param LI     The live interval to be split.
     71     /// \param Start  The expected beginning of the split artifact. Instructions
     72     ///               before start will not affect the weight.
     73     /// \param End    The expected end of the split artifact. Instructions
     74     ///               after end will not affect the weight.
     75     /// \return The expected spill weight of the split artifact. Returns
     76     /// negative weight for unspillable LI.
     77     float futureWeight(LiveInterval &LI, SlotIndex Start, SlotIndex End);
     78 
     79     /// Compute spill weights and allocation hints for all virtual register
     80     /// live intervals.
     81     void calculateSpillWeightsAndHints();
     82 
     83   protected:
     84     /// Helper function for weight calculations.
     85     /// (Re)compute LI's spill weight and allocation hint, or, for non null
     86     /// start and end - compute future expected spill weight of a split
     87     /// artifact of LI that will span between start and end slot indexes.
     88     /// \param LI     The live interval for which to compute the weight.
     89     /// \param Start  The expected beginning of the split artifact. Instructions
     90     ///               before start will not affect the weight. Relevant for
     91     ///               weight calculation of future split artifact.
     92     /// \param End    The expected end of the split artifact. Instructions
     93     ///               after end will not affect the weight. Relevant for
     94     ///               weight calculation of future split artifact.
     95     /// \return The spill weight. Returns negative weight for unspillable LI.
     96     float weightCalcHelper(LiveInterval &LI, SlotIndex *Start = nullptr,
     97                            SlotIndex *End = nullptr);
     98 
     99     /// Weight normalization function.
    100     virtual float normalize(float UseDefFreq, unsigned Size,
    101                             unsigned NumInstr) {
    102       return normalizeSpillWeight(UseDefFreq, Size, NumInstr);
    103     }
    104   };
    105 } // end namespace llvm
    106 
    107 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H
    108