LLVM  9.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) {
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 unsigned copyHint(const MachineInstr *mi, unsigned reg,
52  const TargetRegisterInfo &tri,
53  const MachineRegisterInfo &mri) {
54  unsigned sub, hreg, hsub;
55  if (mi->getOperand(0).getReg() == reg) {
56  sub = mi->getOperand(0).getSubReg();
57  hreg = mi->getOperand(1).getReg();
58  hsub = mi->getOperand(1).getSubReg();
59  } else {
60  sub = mi->getOperand(1).getSubReg();
61  hreg = mi->getOperand(0).getReg();
62  hsub = mi->getOperand(0).getSubReg();
63  }
64 
65  if (!hreg)
66  return 0;
67 
69  return sub == hsub ? hreg : 0;
70 
71  const TargetRegisterClass *rc = mri.getRegClass(reg);
72  unsigned CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
73  if (rc->contains(CopiedPReg))
74  return CopiedPReg;
75 
76  // Check if reg:sub matches so that a super register could be hinted.
77  if (sub)
78  return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
79 
80  return 0;
81 }
82 
83 // Check if all values in LI are rematerializable
84 static bool isRematerializable(const LiveInterval &LI,
85  const LiveIntervals &LIS,
86  VirtRegMap *VRM,
87  const TargetInstrInfo &TII) {
88  unsigned Reg = LI.reg;
89  unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
91  I != E; ++I) {
92  const VNInfo *VNI = *I;
93  if (VNI->isUnused())
94  continue;
95  if (VNI->isPHIDef())
96  return false;
97 
99  assert(MI && "Dead valno in interval");
100 
101  // Trace copies introduced by live range splitting. The inline
102  // spiller can rematerialize through these copies, so the spill
103  // weight must reflect this.
104  if (VRM) {
105  while (MI->isFullCopy()) {
106  // The copy destination must match the interval register.
107  if (MI->getOperand(0).getReg() != Reg)
108  return false;
109 
110  // Get the source register.
111  Reg = MI->getOperand(1).getReg();
112 
113  // If the original (pre-splitting) registers match this
114  // copy came from a split.
116  VRM->getOriginal(Reg) != Original)
117  return false;
118 
119  // Follow the copy live-in value.
120  const LiveInterval &SrcLI = LIS.getInterval(Reg);
121  LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
122  VNI = SrcQ.valueIn();
123  assert(VNI && "Copy from non-existing value");
124  if (VNI->isPHIDef())
125  return false;
126  MI = LIS.getInstructionFromIndex(VNI->def);
127  assert(MI && "Dead valno in interval");
128  }
129  }
130 
131  if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis()))
132  return false;
133  }
134  return true;
135 }
136 
138  float weight = weightCalcHelper(li);
139  // Check if unspillable.
140  if (weight < 0)
141  return;
142  li.weight = weight;
143 }
144 
146  SlotIndex end) {
147  return weightCalcHelper(li, &start, &end);
148 }
149 
151  SlotIndex *end) {
152  MachineRegisterInfo &mri = MF.getRegInfo();
153  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
154  MachineBasicBlock *mbb = nullptr;
155  MachineLoop *loop = nullptr;
156  bool isExiting = false;
157  float totalWeight = 0;
158  unsigned numInstr = 0; // Number of instructions using li
160 
161  std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
162 
163  // Don't recompute spill weight for an unspillable register.
164  bool Spillable = li.isSpillable();
165 
166  bool localSplitArtifact = start && end;
167 
168  // Do not update future local split artifacts.
169  bool updateLI = !localSplitArtifact;
170 
171  if (localSplitArtifact) {
172  MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
173  assert(localMBB == LIS.getMBBFromIndex(*start) &&
174  "start and end are expected to be in the same basic block");
175 
176  // Local split artifact will have 2 additional copy instructions and they
177  // will be in the same BB.
178  // localLI = COPY other
179  // ...
180  // other = COPY localLI
181  totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
182  totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
183 
184  numInstr += 2;
185  }
186 
187  // CopyHint is a sortable hint derived from a COPY instruction.
188  struct CopyHint {
189  unsigned Reg;
190  float Weight;
191  bool IsPhys;
192  CopyHint(unsigned R, float W, bool P) :
193  Reg(R), Weight(W), IsPhys(P) {}
194  bool operator<(const CopyHint &rhs) const {
195  // Always prefer any physreg hint.
196  if (IsPhys != rhs.IsPhys)
197  return (IsPhys && !rhs.IsPhys);
198  if (Weight != rhs.Weight)
199  return (Weight > rhs.Weight);
200  return Reg < rhs.Reg; // Tie-breaker.
201  }
202  };
203  std::set<CopyHint> CopyHints;
204 
206  I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
207  I != E; ) {
208  MachineInstr *mi = &*(I++);
209 
210  // For local split artifacts, we are interested only in instructions between
211  // the expected start and end of the range.
212  SlotIndex si = LIS.getInstructionIndex(*mi);
213  if (localSplitArtifact && ((si < *start) || (si > *end)))
214  continue;
215 
216  numInstr++;
217  if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugInstr())
218  continue;
219  if (!visited.insert(mi).second)
220  continue;
221 
222  float weight = 1.0f;
223  if (Spillable) {
224  // Get loop info for mi.
225  if (mi->getParent() != mbb) {
226  mbb = mi->getParent();
227  loop = Loops.getLoopFor(mbb);
228  isExiting = loop ? loop->isLoopExiting(mbb) : false;
229  }
230 
231  // Calculate instr weight.
232  bool reads, writes;
233  std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
234  weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
235 
236  // Give extra weight to what looks like a loop induction variable update.
237  if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
238  weight *= 3;
239 
240  totalWeight += weight;
241  }
242 
243  // Get allocation hints from copies.
244  if (!mi->isCopy())
245  continue;
246  unsigned hint = copyHint(mi, li.reg, tri, mri);
247  if (!hint)
248  continue;
249  // Force hweight onto the stack so that x86 doesn't add hidden precision,
250  // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
251  //
252  // FIXME: we probably shouldn't use floats at all.
253  volatile float hweight = Hint[hint] += weight;
255  CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint)));
256  }
257 
258  Hint.clear();
259 
260  // Pass all the sorted copy hints to mri.
261  if (updateLI && CopyHints.size()) {
262  // Remove a generic hint if previously added by target.
263  if (TargetHint.first == 0 && TargetHint.second)
264  mri.clearSimpleHint(li.reg);
265 
266  std::set<unsigned> HintedRegs;
267  for (auto &Hint : CopyHints) {
268  if (!HintedRegs.insert(Hint.Reg).second ||
269  (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
270  // Don't add the same reg twice or the target-type hint again.
271  continue;
272  mri.addRegAllocationHint(li.reg, Hint.Reg);
273  }
274 
275  // Weakly boost the spill weight of hinted registers.
276  totalWeight *= 1.01F;
277  }
278 
279  // If the live interval was already unspillable, leave it that way.
280  if (!Spillable)
281  return -1.0;
282 
283  // Mark li as unspillable if all live ranges are tiny and the interval
284  // is not live at any reg mask. If the interval is live at a reg mask
285  // spilling may be required.
286  if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
287  !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
288  li.markNotSpillable();
289  return -1.0;
290  }
291 
292  // If all of the definitions of the interval are re-materializable,
293  // it is a preferred candidate for spilling.
294  // FIXME: this gets much more complicated once we support non-trivial
295  // re-materialization.
296  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
297  totalWeight *= 0.5F;
298 
299  if (localSplitArtifact)
300  return normalize(totalWeight, start->distance(*end), numInstr);
301  return normalize(totalWeight, li.getSize(), numInstr);
302 }
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:666
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
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
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
vni_iterator vni_begin()
Definition: LiveInterval.h:219
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:637
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
unsigned getSubReg() const
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:80
Hexagon Hardware Loops
const HexagonInstrInfo * TII
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.
AliasAnalysis * getAliasAnalysis() const
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:573
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:528
static unsigned copyHint(const MachineInstr *mi, unsigned reg, const TargetRegisterInfo &tri, const MachineRegisterInfo &mri)
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:217
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:203
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
unsigned getSubReg(unsigned Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
std::pair< bool, bool > readsWritesVirtualRegister(unsigned Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const
Return a pair of bools (reads, writes) indicating if this instruction reads or writes 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
Definition: MachineInstr.h:998
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.
void calculateSpillWeightAndHint(LiveInterval &li)
(re)compute li&#39;s spill weight and allocation hint.
void clearSimpleHint(unsigned VReg)
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:771
LiveInterval & getInterval(unsigned Reg)
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:253
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
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
std::pair< unsigned, unsigned > getRegAllocationHint(unsigned VReg) const
getRegAllocationHint - Return the register allocation hint for the specified virtual register...
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:766
static uint64_t sub(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:128
IRTranslator LLVM IR MI
float(*)(float, unsigned, unsigned) NormalizingFn
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
bool isTriviallyReMaterializable(const MachineInstr &MI, AliasAnalysis *AA=nullptr) const
Return true if the instruction is trivially rematerializable, meaning it has no side effects and requ...
unsigned getOriginal(unsigned VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting...
Definition: VirtRegMap.h:146
vni_iterator vni_end()
Definition: LiveInterval.h:220
reg_instr_iterator reg_instr_begin(unsigned RegNo) const