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   public:
54     VirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS,
55                    const VirtRegMap &VRM, const MachineLoopInfo &Loops,
56                    const MachineBlockFrequencyInfo &MBFI)
57         : MF(MF), LIS(LIS), VRM(VRM), Loops(Loops), MBFI(MBFI) {}
58 
59     virtual ~VirtRegAuxInfo() = default;
60 
61     /// (re)compute li's spill weight and allocation hint.
62     void calculateSpillWeightAndHint(LiveInterval &LI);
63 
64     /// Compute future expected spill weight of a split artifact of LI
65     /// that will span between start and end slot indexes.
66     /// \param LI     The live interval to be split.
67     /// \param Start  The expected beginning of the split artifact. Instructions
68     ///               before start will not affect the weight.
69     /// \param End    The expected end of the split artifact. Instructions
70     ///               after end will not affect the weight.
71     /// \return The expected spill weight of the split artifact. Returns
72     /// negative weight for unspillable LI.
73     float futureWeight(LiveInterval &LI, SlotIndex Start, SlotIndex End);
74 
75     /// Compute spill weights and allocation hints for all virtual register
76     /// live intervals.
77     void calculateSpillWeightsAndHints();
78 
79   protected:
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 beginning 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     /// Weight normalization function.
96     virtual float normalize(float UseDefFreq, unsigned Size,
97                             unsigned NumInstr) {
98       return normalizeSpillWeight(UseDefFreq, Size, NumInstr);
99     }
100   };
101 } // end namespace llvm
102 
103 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H
104