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/CodeGen/SlotIndexes.h"
13 
14 namespace llvm {
15 
16 class LiveInterval;
17 class LiveIntervals;
18 class MachineBlockFrequencyInfo;
19 class MachineFunction;
20 class MachineLoopInfo;
21 class VirtRegMap;
22 
23   /// Normalize the spill weight of a live interval
24   ///
25   /// The spill weight of a live interval is computed as:
26   ///
27   ///   (sum(use freq) + sum(def freq)) / (K + size)
28   ///
29   /// @param UseDefFreq Expected number of executed use and def instructions
30   ///                   per function call. Derived from block frequencies.
31   /// @param Size       Size of live interval as returnexd by getSize()
32   /// @param NumInstr   Number of instructions using this live interval
33   static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size,
34                                            unsigned NumInstr) {
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   /// Calculate auxiliary information for a virtual register such as its
44   /// spill weight and allocation hint.
45   class VirtRegAuxInfo {
46     MachineFunction &MF;
47     LiveIntervals &LIS;
48     const VirtRegMap &VRM;
49     const MachineLoopInfo &Loops;
50     const MachineBlockFrequencyInfo &MBFI;
51 
52     /// Returns true if Reg of live interval LI is used in instruction with many
53     /// operands like STATEPOINT.
54     bool isLiveAtStatepointVarArg(LiveInterval &LI);
55 
56   public:
57     VirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS,
58                    const VirtRegMap &VRM, const MachineLoopInfo &Loops,
59                    const MachineBlockFrequencyInfo &MBFI)
60         : MF(MF), LIS(LIS), VRM(VRM), Loops(Loops), MBFI(MBFI) {}
61 
62     virtual ~VirtRegAuxInfo() = default;
63 
64     /// (re)compute li's spill weight and allocation hint.
65     void calculateSpillWeightAndHint(LiveInterval &LI);
66 
67     /// Compute spill weights and allocation hints for all virtual register
68     /// live intervals.
69     void calculateSpillWeightsAndHints();
70 
71     /// Return the preferred allocation register for reg, given a COPY
72     /// instruction.
73     static Register copyHint(const MachineInstr *MI, unsigned Reg,
74                              const TargetRegisterInfo &TRI,
75                              const MachineRegisterInfo &MRI);
76 
77     /// Determine if all values in LI are rematerializable.
78     static bool isRematerializable(const LiveInterval &LI,
79                                    const LiveIntervals &LIS,
80                                    const VirtRegMap &VRM,
81                                    const TargetInstrInfo &TII);
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