LLVM  6.0.0svn
CalcSpillWeights.cpp
Go to the documentation of this file.
1 //===- CalcSpillWeights.cpp -----------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/Support/Debug.h"
25 #include <cassert>
26 #include <tuple>
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "calcspillweights"
31 
33  MachineFunction &MF,
34  VirtRegMap *VRM,
35  const MachineLoopInfo &MLI,
36  const MachineBlockFrequencyInfo &MBFI,
38  DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
39  << "********** Function: " << MF.getName() << '\n');
40 
42  VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
43  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
45  if (MRI.reg_nodbg_empty(Reg))
46  continue;
48  }
49 }
50 
51 // Return the preferred allocation register for reg, given a COPY instruction.
52 static unsigned copyHint(const MachineInstr *mi, unsigned reg,
53  const TargetRegisterInfo &tri,
54  const MachineRegisterInfo &mri) {
55  unsigned sub, hreg, hsub;
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 : 0;
71 
72  const TargetRegisterClass *rc = mri.getRegClass(reg);
73 
74  // Only allow physreg hints in rc.
75  if (sub == 0)
76  return rc->contains(hreg) ? hreg : 0;
77 
78  // reg:sub should match the physreg hreg.
79  return tri.getMatchingSuperReg(hreg, sub, rc);
80 }
81 
82 // Check if all values in LI are rematerializable
83 static bool isRematerializable(const LiveInterval &LI,
84  const LiveIntervals &LIS,
85  VirtRegMap *VRM,
86  const TargetInstrInfo &TII) {
87  unsigned Reg = LI.reg;
88  unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
90  I != E; ++I) {
91  const VNInfo *VNI = *I;
92  if (VNI->isUnused())
93  continue;
94  if (VNI->isPHIDef())
95  return false;
96 
98  assert(MI && "Dead valno in interval");
99 
100  // Trace copies introduced by live range splitting. The inline
101  // spiller can rematerialize through these copies, so the spill
102  // weight must reflect this.
103  if (VRM) {
104  while (MI->isFullCopy()) {
105  // The copy destination must match the interval register.
106  if (MI->getOperand(0).getReg() != Reg)
107  return false;
108 
109  // Get the source register.
110  Reg = MI->getOperand(1).getReg();
111 
112  // If the original (pre-splitting) registers match this
113  // copy came from a split.
115  VRM->getOriginal(Reg) != Original)
116  return false;
117 
118  // Follow the copy live-in value.
119  const LiveInterval &SrcLI = LIS.getInterval(Reg);
120  LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
121  VNI = SrcQ.valueIn();
122  assert(VNI && "Copy from non-existing value");
123  if (VNI->isPHIDef())
124  return false;
125  MI = LIS.getInstructionFromIndex(VNI->def);
126  assert(MI && "Dead valno in interval");
127  }
128  }
129 
130  if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis()))
131  return false;
132  }
133  return true;
134 }
135 
137  float weight = weightCalcHelper(li);
138  // Check if unspillable.
139  if (weight < 0)
140  return;
141  li.weight = weight;
142 }
143 
145  SlotIndex end) {
146  return weightCalcHelper(li, &start, &end);
147 }
148 
150  SlotIndex *end) {
151  MachineRegisterInfo &mri = MF.getRegInfo();
152  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
153  MachineBasicBlock *mbb = nullptr;
154  MachineLoop *loop = nullptr;
155  bool isExiting = false;
156  float totalWeight = 0;
157  unsigned numInstr = 0; // Number of instructions using li
159 
160  // Find the best physreg hint and the best virtreg hint.
161  float bestPhys = 0, bestVirt = 0;
162  unsigned hintPhys = 0, hintVirt = 0;
163 
164  // Don't recompute a target specific hint.
165  bool noHint = mri.getRegAllocationHint(li.reg).first != 0;
166 
167  // Don't recompute spill weight for an unspillable register.
168  bool Spillable = li.isSpillable();
169 
170  bool localSplitArtifact = start && end;
171 
172  // Do not update future local split artifacts.
173  bool updateLI = !localSplitArtifact;
174 
175  if (localSplitArtifact) {
176  MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
177  assert(localMBB == LIS.getMBBFromIndex(*start) &&
178  "start and end are expected to be in the same basic block");
179 
180  // Local split artifact will have 2 additional copy instructions and they
181  // will be in the same BB.
182  // localLI = COPY other
183  // ...
184  // other = COPY localLI
185  totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
186  totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
187 
188  numInstr += 2;
189  }
190 
192  I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
193  I != E; ) {
194  MachineInstr *mi = &*(I++);
195 
196  // For local split artifacts, we are interested only in instructions between
197  // the expected start and end of the range.
198  SlotIndex si = LIS.getInstructionIndex(*mi);
199  if (localSplitArtifact && ((si < *start) || (si > *end)))
200  continue;
201 
202  numInstr++;
203  if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue())
204  continue;
205  if (!visited.insert(mi).second)
206  continue;
207 
208  float weight = 1.0f;
209  if (Spillable) {
210  // Get loop info for mi.
211  if (mi->getParent() != mbb) {
212  mbb = mi->getParent();
213  loop = Loops.getLoopFor(mbb);
214  isExiting = loop ? loop->isLoopExiting(mbb) : false;
215  }
216 
217  // Calculate instr weight.
218  bool reads, writes;
219  std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
220  weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
221 
222  // Give extra weight to what looks like a loop induction variable update.
223  if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
224  weight *= 3;
225 
226  totalWeight += weight;
227  }
228 
229  // Get allocation hints from copies.
230  if (noHint || !mi->isCopy())
231  continue;
232  unsigned hint = copyHint(mi, li.reg, tri, mri);
233  if (!hint)
234  continue;
235  // Force hweight onto the stack so that x86 doesn't add hidden precision,
236  // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
237  //
238  // FIXME: we probably shouldn't use floats at all.
239  volatile float hweight = Hint[hint] += weight;
241  if (hweight > bestPhys && mri.isAllocatable(hint)) {
242  bestPhys = hweight;
243  hintPhys = hint;
244  }
245  } else {
246  if (hweight > bestVirt) {
247  bestVirt = hweight;
248  hintVirt = hint;
249  }
250  }
251  }
252 
253  Hint.clear();
254 
255  // Always prefer the physreg hint.
256  if (updateLI) {
257  if (unsigned hint = hintPhys ? hintPhys : hintVirt) {
258  mri.setRegAllocationHint(li.reg, 0, hint);
259  // Weakly boost the spill weight of hinted registers.
260  totalWeight *= 1.01F;
261  }
262  }
263 
264  // If the live interval was already unspillable, leave it that way.
265  if (!Spillable)
266  return -1.0;
267 
268  // Mark li as unspillable if all live ranges are tiny and the interval
269  // is not live at any reg mask. If the interval is live at a reg mask
270  // spilling may be required.
271  if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
272  !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
273  li.markNotSpillable();
274  return -1.0;
275  }
276 
277  // If all of the definitions of the interval are re-materializable,
278  // it is a preferred candidate for spilling.
279  // FIXME: this gets much more complicated once we support non-trivial
280  // re-materialization.
281  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
282  totalWeight *= 0.5F;
283 
284  if (localSplitArtifact)
285  return normalize(totalWeight, start->distance(*end), numInstr);
286  return normalize(totalWeight, li.getSize(), numInstr);
287 }
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:78
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint...
const unsigned reg
Definition: LiveInterval.h:667
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:61
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn&#39;t been...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:220
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
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 getSubReg() const
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
const HexagonInstrInfo * TII
Result of a LiveRange query.
Definition: LiveInterval.h:90
Reg
All possible values of the reg field in the ModR/M byte.
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
Definition: MachineInstr.h:861
bool isIdentityCopy() const
Return true is the instruction is an identity copy.
Definition: MachineInstr.h:876
AliasAnalysis * getAliasAnalysis() const
virtual const TargetInstrInfo * getInstrInfo() const
bool isZeroLength(SlotIndexes *Indexes) const
Returns true if the live range is zero length, i.e.
Definition: LiveInterval.h:574
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:105
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:529
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)
unsigned const MachineRegisterInfo * MRI
VNInfoList::const_iterator const_vni_iterator
Definition: LiveInterval.h:218
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:184
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:371
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
Definition: MachineInstr.h:857
bool isImplicitDef() const
Definition: MachineInstr.h:831
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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:418
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.
bool isDebugValue() const
Definition: MachineInstr.h:816
void setRegAllocationHint(unsigned VReg, unsigned Type, unsigned PrefReg)
setRegAllocationHint - Specify a register allocation hint for the specified virtual register...
void calculateSpillWeightAndHint(LiveInterval &li)
(re)compute li&#39;s spill weight and allocation hint.
void markNotSpillable()
markNotSpillable - Mark interval as not spillable
Definition: LiveInterval.h:772
LiveInterval & getInterval(unsigned Reg)
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &Instr)
Calculate the spill weight to assign to a single instruction.
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.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
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:59
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:215
#define I(x, y, z)
Definition: MD5.cpp:58
SlotIndexes * getSlotIndexes() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:767
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
float(*)(float, unsigned, unsigned) NormalizingFn
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
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:147
vni_iterator vni_end()
Definition: LiveInterval.h:221
reg_instr_iterator reg_instr_begin(unsigned RegNo) const