1 //===- lib/CodeGen/CalcSpillWeights.h ---------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H
11 #define LLVM_CODEGEN_CALCSPILLWEIGHTS_H
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/CodeGen/SlotIndexes.h"
20 class MachineBlockFrequencyInfo;
21 class MachineFunction;
22 class MachineLoopInfo;
25 /// \brief Normalize the spill weight of a live interval
27 /// The spill weight of a live interval is computed as:
29 /// (sum(use freq) + sum(def freq)) / (K + size)
31 /// @param UseDefFreq Expected number of executed use and def instructions
32 /// per function call. Derived from block frequencies.
33 /// @param Size Size of live interval as returnexd by getSize()
34 /// @param NumInstr Number of instructions using this live interval
35 static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size,
37 // The constant 25 instructions is added to avoid depending too much on
38 // accidental SlotIndex gaps for small intervals. The effect is that small
39 // intervals have a spill weight that is mostly proportional to the number
40 // of uses, while large intervals get a spill weight that is closer to a use
42 return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
45 /// \brief Calculate auxiliary information for a virtual register such as its
46 /// spill weight and allocation hint.
47 class VirtRegAuxInfo {
49 using NormalizingFn = float (*)(float, unsigned, unsigned);
55 const MachineLoopInfo &Loops;
56 const MachineBlockFrequencyInfo &MBFI;
57 DenseMap<unsigned, float> Hint;
58 NormalizingFn normalize;
61 VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis,
62 VirtRegMap *vrm, const MachineLoopInfo &loops,
63 const MachineBlockFrequencyInfo &mbfi,
64 NormalizingFn norm = normalizeSpillWeight)
65 : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {}
67 /// \brief (re)compute li's spill weight and allocation hint.
68 void calculateSpillWeightAndHint(LiveInterval &li);
70 /// \brief Compute future expected spill weight of a split artifact of li
71 /// that will span between start and end slot indexes.
72 /// \param li The live interval to be split.
73 /// \param start The expected begining of the split artifact. Instructions
74 /// before start will not affect the weight.
75 /// \param end The expected end of the split artifact. Instructions
76 /// after end will not affect the weight.
77 /// \return The expected spill weight of the split artifact. Returns
78 /// negative weight for unspillable li.
79 float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end);
81 /// \brief Helper function for weight calculations.
82 /// (Re)compute li's spill weight and allocation hint, or, for non null
83 /// start and end - compute future expected spill weight of a split
84 /// artifact of li that will span between start and end slot indexes.
85 /// \param li The live interval for which to compute the weight.
86 /// \param start The expected begining of the split artifact. Instructions
87 /// before start will not affect the weight. Relevant for
88 /// weight calculation of future split artifact.
89 /// \param end The expected end of the split artifact. Instructions
90 /// after end will not affect the weight. Relevant for
91 /// weight calculation of future split artifact.
92 /// \return The spill weight. Returns negative weight for unspillable li.
93 float weightCalcHelper(LiveInterval &li, SlotIndex *start = nullptr,
94 SlotIndex *end = nullptr);
97 /// \brief Compute spill weights and allocation hints for all virtual register
99 void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF,
101 const MachineLoopInfo &MLI,
102 const MachineBlockFrequencyInfo &MBFI,
103 VirtRegAuxInfo::NormalizingFn norm =
104 normalizeSpillWeight);
106 } // end namespace llvm
108 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H