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
15namespace llvm {
16
17class LiveInterval;
18class LiveIntervals;
19class MachineBlockFrequencyInfo;
20class MachineFunction;
21class MachineLoopInfo;
22class 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
108