LLVM  14.0.0git
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  MachineFunction &MF;
48  LiveIntervals &LIS;
49  const VirtRegMap &VRM;
50  const MachineLoopInfo &Loops;
51  const MachineBlockFrequencyInfo &MBFI;
52 
53  /// Returns true if Reg of live interval LI is used in instruction with many
54  /// operands like STATEPOINT.
55  bool isLiveAtStatepointVarArg(LiveInterval &LI);
56 
57  public:
59  const VirtRegMap &VRM, const MachineLoopInfo &Loops,
60  const MachineBlockFrequencyInfo &MBFI)
61  : MF(MF), LIS(LIS), VRM(VRM), Loops(Loops), MBFI(MBFI) {}
62 
63  virtual ~VirtRegAuxInfo() = default;
64 
65  /// (re)compute li's spill weight and allocation hint.
67 
68  /// Compute future expected spill weight of a split artifact of LI
69  /// that will span between start and end slot indexes.
70  /// \param LI The live interval to be split.
71  /// \param Start The expected beginning of the split artifact. Instructions
72  /// before start will not affect the weight.
73  /// \param End The expected end of the split artifact. Instructions
74  /// after end will not affect the weight.
75  /// \return The expected spill weight of the split artifact. Returns
76  /// negative weight for unspillable LI.
77  float futureWeight(LiveInterval &LI, SlotIndex Start, SlotIndex End);
78 
79  /// Compute spill weights and allocation hints for all virtual register
80  /// live intervals.
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
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::normalizeSpillWeight
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
Definition: CalcSpillWeights.h:34
llvm::VirtRegAuxInfo::futureWeight
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...
Definition: CalcSpillWeights.cpp:147
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::VirtRegAuxInfo::~VirtRegAuxInfo
virtual ~VirtRegAuxInfo()=default
llvm::SlotIndex::InstrDist
@ InstrDist
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:137
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::VirtRegAuxInfo
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
Definition: CalcSpillWeights.h:46
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::VirtRegAuxInfo::normalize
virtual float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr)
Weight normalization function.
Definition: CalcSpillWeights.h:100
llvm::VirtRegAuxInfo::calculateSpillWeightsAndHints
void calculateSpillWeightsAndHints()
Compute spill weights and allocation hints for all virtual register live intervals.
Definition: CalcSpillWeights.cpp:32
DenseMap.h
llvm::VirtRegAuxInfo::calculateSpillWeightAndHint
void calculateSpillWeightAndHint(LiveInterval &LI)
(re)compute li's spill weight and allocation hint.
Definition: CalcSpillWeights.cpp:139
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::VirtRegAuxInfo::weightCalcHelper
float weightCalcHelper(LiveInterval &LI, SlotIndex *Start=nullptr, SlotIndex *End=nullptr)
Helper function for weight calculations.
Definition: CalcSpillWeights.cpp:152
llvm::VirtRegAuxInfo::VirtRegAuxInfo
VirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS, const VirtRegMap &VRM, const MachineLoopInfo &Loops, const MachineBlockFrequencyInfo &MBFI)
Definition: CalcSpillWeights.h:58
llvm::LiveIntervals
Definition: LiveIntervals.h:54
SlotIndexes.h