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  /// Return the preferred allocation register for reg, given a COPY
84  /// instruction.
85  static Register copyHint(const MachineInstr *MI, unsigned Reg,
86  const TargetRegisterInfo &TRI,
87  const MachineRegisterInfo &MRI);
88 
89  /// Determine if all values in LI are rematerializable.
90  static bool isRematerializable(const LiveInterval &LI,
91  const LiveIntervals &LIS,
92  const VirtRegMap &VRM,
93  const TargetInstrInfo &TII);
94 
95  protected:
96  /// Helper function for weight calculations.
97  /// (Re)compute LI's spill weight and allocation hint, or, for non null
98  /// start and end - compute future expected spill weight of a split
99  /// artifact of LI that will span between start and end slot indexes.
100  /// \param LI The live interval for which to compute the weight.
101  /// \param Start The expected beginning of the split artifact. Instructions
102  /// before start will not affect the weight. Relevant for
103  /// weight calculation of future split artifact.
104  /// \param End The expected end of the split artifact. Instructions
105  /// after end will not affect the weight. Relevant for
106  /// weight calculation of future split artifact.
107  /// \return The spill weight. Returns negative weight for unspillable LI.
108  float weightCalcHelper(LiveInterval &LI, SlotIndex *Start = nullptr,
109  SlotIndex *End = nullptr);
110 
111  /// Weight normalization function.
112  virtual float normalize(float UseDefFreq, unsigned Size,
113  unsigned NumInstr) {
114  return normalizeSpillWeight(UseDefFreq, Size, NumInstr);
115  }
116  };
117 } // end namespace llvm
118 
119 #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:148
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
llvm::VirtRegAuxInfo::~VirtRegAuxInfo
virtual ~VirtRegAuxInfo()=default
llvm::VirtRegAuxInfo::isRematerializable
static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS, const VirtRegMap &VRM, const TargetInstrInfo &TII)
Determine if all values in LI are rematerializable.
Definition: CalcSpillWeights.cpp:80
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::VirtRegAuxInfo::copyHint
static Register copyHint(const MachineInstr *MI, unsigned Reg, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI)
Return the preferred allocation register for reg, given a COPY instruction.
Definition: CalcSpillWeights.cpp:46
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:112
llvm::VirtRegAuxInfo::calculateSpillWeightsAndHints
void calculateSpillWeightsAndHints()
Compute spill weights and allocation hints for all virtual register live intervals.
Definition: CalcSpillWeights.cpp:32
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
llvm::VirtRegAuxInfo::calculateSpillWeightAndHint
void calculateSpillWeightAndHint(LiveInterval &LI)
(re)compute li's spill weight and allocation hint.
Definition: CalcSpillWeights.cpp:140
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1559
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
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::SlotIndex::InstrDist
@ InstrDist
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:137
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineFunction
Definition: MachineFunction.h:241
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::VirtRegAuxInfo::weightCalcHelper
float weightCalcHelper(LiveInterval &LI, SlotIndex *Start=nullptr, SlotIndex *End=nullptr)
Helper function for weight calculations.
Definition: CalcSpillWeights.cpp:153
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