Home | History | Annotate | Download | only in CodeGen
      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 
     11 #ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H
     12 #define LLVM_CODEGEN_CALCSPILLWEIGHTS_H
     13 
     14 #include "llvm/ADT/DenseMap.h"
     15 #include "llvm/CodeGen/SlotIndexes.h"
     16 
     17 namespace llvm {
     18 
     19   class LiveInterval;
     20   class LiveIntervals;
     21   class MachineBlockFrequencyInfo;
     22   class MachineLoopInfo;
     23 
     24   /// \brief 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   ///
     34   static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size) {
     35     // The constant 25 instructions is added to avoid depending too much on
     36     // accidental SlotIndex gaps for small intervals. The effect is that small
     37     // intervals have a spill weight that is mostly proportional to the number
     38     // of uses, while large intervals get a spill weight that is closer to a use
     39     // density.
     40     return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
     41   }
     42 
     43   /// \brief Calculate auxiliary information for a virtual register such as its
     44   /// spill weight and allocation hint.
     45   class VirtRegAuxInfo {
     46   public:
     47     typedef float (*NormalizingFn)(float, unsigned);
     48 
     49   private:
     50     MachineFunction &MF;
     51     LiveIntervals &LIS;
     52     const MachineLoopInfo &Loops;
     53     const MachineBlockFrequencyInfo &MBFI;
     54     DenseMap<unsigned, float> Hint;
     55     NormalizingFn normalize;
     56 
     57   public:
     58     VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis,
     59                    const MachineLoopInfo &loops,
     60                    const MachineBlockFrequencyInfo &mbfi,
     61                    NormalizingFn norm = normalizeSpillWeight)
     62         : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi), normalize(norm) {}
     63 
     64     /// \brief (re)compute li's spill weight and allocation hint.
     65     void calculateSpillWeightAndHint(LiveInterval &li);
     66   };
     67 
     68   /// \brief Compute spill weights and allocation hints for all virtual register
     69   /// live intervals.
     70   void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF,
     71                                      const MachineLoopInfo &MLI,
     72                                      const MachineBlockFrequencyInfo &MBFI,
     73                                      VirtRegAuxInfo::NormalizingFn norm =
     74                                          normalizeSpillWeight);
     75 }
     76 
     77 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H
     78