LLVM  10.0.0svn
CalcSpillWeights.h
Go to the documentation of this file.
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"
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.
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;
57  NormalizingFn normalize;
58 
59  public:
61  VirtRegMap *vrm, const MachineLoopInfo &loops,
62  const MachineBlockFrequencyInfo &mbfi,
64  : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {}
65 
66  /// (re)compute li's spill weight and allocation hint.
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.
99  VirtRegMap *VRM,
100  const MachineLoopInfo &MLI,
101  const MachineBlockFrequencyInfo &MBFI,
104 
105 } // end namespace llvm
106 
107 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:137
float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end)
Compute future expected spill weight of a split artifact of li that will span between start and end s...
VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, VirtRegMap *vrm, const MachineLoopInfo &loops, const MachineBlockFrequencyInfo &mbfi, NormalizingFn norm=normalizeSpillWeight)
float weightCalcHelper(LiveInterval &li, SlotIndex *start=nullptr, SlotIndex *end=nullptr)
Helper function for weight calculations.
void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, VirtRegMap *VRM, const MachineLoopInfo &MLI, const MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo::NormalizingFn norm=normalizeSpillWeight)
Compute spill weights and allocation hints for all virtual register live intervals.
void calculateSpillWeightAndHint(LiveInterval &li)
(re)compute li's spill weight and allocation hint.
uint32_t Size
Definition: Profile.cpp:46
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
float(*)(float, unsigned, unsigned) NormalizingFn
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
loops
Definition: LoopInfo.cpp:1054