LLVM  10.0.0svn
CalcSpillWeights.cpp
Go to the documentation of this file.
1 //===- CalcSpillWeights.cpp -----------------------------------------------===//
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 
10 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Support/Debug.h"
24 #include <cassert>
25 #include <tuple>
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "calcspillweights"
30 
32  MachineFunction &MF,
33  VirtRegMap *VRM,
34  const MachineLoopInfo &MLI,
35  const MachineBlockFrequencyInfo &MBFI,
37  LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
38  << "********** Function: " << MF.getName() << '\n');
39 
41  VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
42  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
43  unsigned Reg = Register::index2VirtReg(i);
44  if (MRI.reg_nodbg_empty(Reg))
45  continue;
47  }
48 }
49 
50 // Return the preferred allocation register for reg, given a COPY instruction.
51 static Register copyHint(const MachineInstr *mi, unsigned reg,
52  const TargetRegisterInfo &tri,
53  const MachineRegisterInfo &mri) {
54  unsigned sub, hsub;
55  Register hreg;
56  if (mi->getOperand(0).getReg() == reg) {
57  sub = mi->getOperand(0).getSubReg();
58  hreg = mi->getOperand(1).getReg();
59  hsub = mi->getOperand(1).getSubReg();
60  } else {
61  sub = mi->getOperand(1).getSubReg();
62  hreg = mi->getOperand(0).getReg();
63  hsub = mi->getOperand(0).getSubReg();
64  }
65 
66  if (!hreg)
67  return 0;
68 
70  return sub == hsub ? hreg : Register();
71 
72  const TargetRegisterClass *rc = mri.getRegClass(reg);
73  Register CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
74  if (rc->contains(CopiedPReg))
75  return CopiedPReg;
76 
77  // Check if reg:sub matches so that a super register could be hinted.
78  if (sub)
79  return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
80 
81  return 0;
82 }
83 
84 // Check if all values in LI are rematerializable
85 static bool isRematerializable(const LiveInterval &LI,
86  const LiveIntervals &LIS,
87  VirtRegMap *VRM,
88  const TargetInstrInfo &TII) {
89  unsigned Reg = LI.reg;
90  unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
92  I != E; ++I) {
93  const VNInfo *VNI = *I;
94  if (VNI->isUnused())
95  continue;
96  if (VNI->isPHIDef())
97  return false;
98 
100  assert(MI && "Dead valno in interval");
101 
102  // Trace copies introduced by live range splitting. The inline
103  // spiller can rematerialize through these copies, so the spill
104  // weight must reflect this.
105  if (VRM) {
106  while (MI->isFullCopy()) {
107  // The copy destination must match the interval register.
108  if (MI->getOperand(0).getReg() != Reg)
109  return false;
110 
111  // Get the source register.
112  Reg = MI->getOperand(1).getReg();
113 
114  // If the original (pre-splitting) registers match this
115  // copy came from a split.
116  if (!Register::isVirtualRegister(Reg) ||
117  VRM->getOriginal(Reg) != Original)
118  return false;
119 
120  // Follow the copy live-in value.
121  const LiveInterval &SrcLI = LIS.getInterval(Reg);
122  LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
123  VNI = SrcQ.valueIn();
124  assert(VNI && "Copy from non-existing value");
125  if (VNI->isPHIDef())
126  return false;
127  MI = LIS.getInstructionFromIndex(VNI->def);
128  assert(MI && "Dead valno in interval");
129  }
130  }
131 
132  if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis()))
133  return false;
134  }
135  return true;
136 }
137 
139  float weight = weightCalcHelper(li);
140  // Check if unspillable.
141  if (weight < 0)
142  return;
143  li.weight = weight;
144 }
145 
147  SlotIndex end) {
148  return weightCalcHelper(li, &start, &end);
149 }
150 
152  SlotIndex *end) {
153  MachineRegisterInfo &mri = MF.getRegInfo();
154  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
155  MachineBasicBlock *mbb = nullptr;
156  MachineLoop *loop = nullptr;
157  bool isExiting = false;
158  float totalWeight = 0;
159  unsigned numInstr = 0; // Number of instructions using li
161 
162  std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
163 
164  // Don't recompute spill weight for an unspillable register.
165  bool Spillable = li.isSpillable();
166 
167  bool localSplitArtifact = start && end;
168 
169  // Do not update future local split artifacts.
170  bool updateLI = !localSplitArtifact;
171 
172  if (localSplitArtifact) {
173  MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
174  assert(localMBB == LIS.getMBBFromIndex(*start) &&
175  "start and end are expected to be in the same basic block");
176 
177  // Local split artifact will have 2 additional copy instructions and they
178  // will be in the same BB.
179  // localLI = COPY other
180  // ...
181  // other = COPY localLI
182  totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
183  totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
184 
185  numInstr += 2;
186  }
187 
188  // CopyHint is a sortable hint derived from a COPY instruction.
189  struct CopyHint {
190  unsigned Reg;
191  float Weight;
192  bool IsPhys;
193  CopyHint(unsigned R, float W, bool P) :
194  Reg(R), Weight(W), IsPhys(P) {}
195  bool operator<(const CopyHint &rhs) const {
196  // Always prefer any physreg hint.
197  if (IsPhys != rhs.IsPhys)
198  return (IsPhys && !rhs.IsPhys);
199  if (Weight != rhs.Weight)
200  return (Weight > rhs.Weight);
201  return Reg < rhs.Reg; // Tie-breaker.
202  }
203  };
204  std::set<CopyHint> CopyHints;
205 
207  I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
208  I != E; ) {
209  MachineInstr *mi = &*(I++);
210 
211  // For local split artifacts, we are interested only in instructions between
212  // the expected start and end of the range.
213  SlotIndex si = LIS.getInstructionIndex(*mi);
214  if (localSplitArtifact && ((si < *start) || (si > *end)))
215  continue;
216 
217  numInstr++;
218  if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugInstr())
219  continue;
220  if (!visited.insert(mi).second)
221  continue;
222 
223  float weight = 1.0f;
224  if (Spillable) {
225  // Get loop info for mi.
226  if (mi->getParent() != mbb) {
227  mbb = mi->getParent();
228  loop = Loops.getLoopFor(mbb);
229  isExiting = loop ? loop->isLoopExiting(mbb) : false;
230  }
231 
232  // Calculate instr weight.
233  bool reads, writes;
234  std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
235  weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
236 
237  // Give extra weight to what looks like a loop induction variable update.
238  if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
239  weight *= 3;
240 
241  totalWeight += weight;
242  }
243 
244  // Get allocation hints from copies.
245  if (!mi->isCopy())
246  continue;
247  Register hint = copyHint(mi, li.reg, tri, mri);
248  if (!hint)
249  continue;
250  // Force hweight onto the stack so that x86 doesn't add hidden precision,
251  // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
252  //
253  // FIXME: we probably shouldn't use floats at all.
254  volatile float hweight = Hint[hint] += weight;
255  if (Register::isVirtualRegister(hint) || mri.isAllocatable(hint))
256  CopyHints.insert(
257  CopyHint(hint, hweight, Register::isPhysicalRegister(hint)));
258  }
259 
260  Hint.clear();
261 
262  // Pass all the sorted copy hints to mri.
263  if (updateLI && CopyHints.size()) {
264  // Remove a generic hint if previously added by target.
265  if (TargetHint.first == 0 && TargetHint.second)
266  mri.clearSimpleHint(li.reg);
267 
268  std::set<unsigned> HintedRegs;
269  for (auto &Hint : CopyHints) {
270  if (!HintedRegs.insert(Hint.Reg).second ||
271  (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
272  // Don't add the same reg twice or the target-type hint again.
273  continue;
274  mri.addRegAllocationHint(li.reg, Hint.Reg);
275  }
276 
277  // Weakly boost the spill weight of hinted registers.
278  totalWeight *= 1.01F;
279  }
280 
281  // If the live interval was already unspillable, leave it that way.
282  if (!Spillable)
283  return -1.0;
284 
285  // Mark li as unspillable if all live ranges are tiny and the interval
286  // is not live at any reg mask. If the interval is live at a reg mask
287  // spilling may be required.
288  if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
289  !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
290  li.markNotSpillable();
291  return -1.0;
292  }
293 
294  // If all of the definitions of the interval are re-materializable,
295  // it is a preferred candidate for spilling.
296  // FIXME: this gets much more complicated once we support non-trivial
297  // re-materialization.
298  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
299  totalWeight *= 0.5F;
300 
301  if (localSplitArtifact)
302  return normalize(totalWeight, start->distance(*end), numInstr);
303  return normalize(totalWeight, li.getSize(), numInstr);
304 }
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:77
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...
const unsigned reg
Definition: LiveInterval.h:708
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:60
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn&#39;t been...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
vni_iterator vni_begin()
Definition: LiveInterval.h:223
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
unsigned Reg
unsigned getSubReg() const
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:80
Hexagon Hardware Loops
const HexagonInstrInfo * TII
std::pair< bool, bool > readsWritesVirtualRegister(Register Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const
Return a pair of bools (reads, writes) indicating if this instruction reads or writes Reg...
Result of a LiveRange query.
Definition: LiveInterval.h:89
static reg_instr_iterator reg_instr_end()
defusechain_iterator - This class provides iterator support for machine operands in the function that...
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS, VirtRegMap *VRM, const TargetInstrInfo &TII)
bool isFullCopy() const
bool isIdentityCopy() const
Return true is the instruction is an identity copy.
Register getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
AliasAnalysis * getAliasAnalysis() const
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:577
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
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...
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:104
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:532
TargetInstrInfo - Interface to description of machine instruction set.
#define rc(i)
#define P(N)
unsigned const MachineRegisterInfo * MRI
VNInfoList::const_iterator const_vni_iterator
Definition: LiveInterval.h:221
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
Definition: LoopInfo.h:208
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
static Register copyHint(const MachineInstr *mi, unsigned reg, const TargetRegisterInfo &tri, const MachineRegisterInfo &mri)
constexpr double e
Definition: MathExtras.h:57
LiveInterval & getInterval(Register Reg)
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
bool isCopy() const
bool isImplicitDef() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool isDebugInstr() const
float weightCalcHelper(LiveInterval &li, SlotIndex *start=nullptr, SlotIndex *end=nullptr)
Helper function for weight calculations.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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.
std::pair< unsigned, unsigned > getRegAllocationHint(Register VReg) const
getRegAllocationHint - Return the register allocation hint for the specified virtual register...
void calculateSpillWeightAndHint(LiveInterval &li)
(re)compute li&#39;s spill weight and allocation hint.
Promote Memory to Register
Definition: Mem2Reg.cpp:109
void clearSimpleHint(unsigned VReg)
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:813
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange&#39;s.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, const TargetRegisterClass *RC) const
Return a super-register of the specified register Reg so its sub-register of index SubIdx is Reg...
int distance(SlotIndex other) const
Return the distance from this index to the given one.
Definition: SlotIndexes.h:214
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:343
void addRegAllocationHint(unsigned VReg, unsigned PrefReg)
addRegAllocationHint - Add a register allocation hint to the hints vector for VReg.
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:808
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
static uint64_t sub(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:219
bool isTriviallyReMaterializable(const MachineInstr &MI, AAResults *AA=nullptr) const
Return true if the instruction is trivially rematerializable, meaning it has no side effects and requ...
IRTranslator LLVM IR MI
float(*)(float, unsigned, unsigned) NormalizingFn
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
unsigned getOriginal(unsigned VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting...
Definition: VirtRegMap.h:148
vni_iterator vni_end()
Definition: LiveInterval.h:224
reg_instr_iterator reg_instr_begin(unsigned RegNo) const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19