LLVM  7.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  if (!tri.enableMultipleCopyHints()) {
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  unsigned CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
83  if (rc->contains(CopiedPReg))
84  return CopiedPReg;
85 
86  // Check if reg:sub matches so that a super register could be hinted.
87  if (sub)
88  return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
89 
90  return 0;
91 }
92 
93 // Check if all values in LI are rematerializable
94 static bool isRematerializable(const LiveInterval &LI,
95  const LiveIntervals &LIS,
96  VirtRegMap *VRM,
97  const TargetInstrInfo &TII) {
98  unsigned Reg = LI.reg;
99  unsigned Original = VRM ? VRM->getOriginal(Reg) : 0;
101  I != E; ++I) {
102  const VNInfo *VNI = *I;
103  if (VNI->isUnused())
104  continue;
105  if (VNI->isPHIDef())
106  return false;
107 
109  assert(MI && "Dead valno in interval");
110 
111  // Trace copies introduced by live range splitting. The inline
112  // spiller can rematerialize through these copies, so the spill
113  // weight must reflect this.
114  if (VRM) {
115  while (MI->isFullCopy()) {
116  // The copy destination must match the interval register.
117  if (MI->getOperand(0).getReg() != Reg)
118  return false;
119 
120  // Get the source register.
121  Reg = MI->getOperand(1).getReg();
122 
123  // If the original (pre-splitting) registers match this
124  // copy came from a split.
126  VRM->getOriginal(Reg) != Original)
127  return false;
128 
129  // Follow the copy live-in value.
130  const LiveInterval &SrcLI = LIS.getInterval(Reg);
131  LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
132  VNI = SrcQ.valueIn();
133  assert(VNI && "Copy from non-existing value");
134  if (VNI->isPHIDef())
135  return false;
136  MI = LIS.getInstructionFromIndex(VNI->def);
137  assert(MI && "Dead valno in interval");
138  }
139  }
140 
141  if (!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis()))
142  return false;
143  }
144  return true;
145 }
146 
148  float weight = weightCalcHelper(li);
149  // Check if unspillable.
150  if (weight < 0)
151  return;
152  li.weight = weight;
153 }
154 
156  SlotIndex end) {
157  return weightCalcHelper(li, &start, &end);
158 }
159 
161  SlotIndex *end) {
162  MachineRegisterInfo &mri = MF.getRegInfo();
163  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
164  MachineBasicBlock *mbb = nullptr;
165  MachineLoop *loop = nullptr;
166  bool isExiting = false;
167  float totalWeight = 0;
168  unsigned numInstr = 0; // Number of instructions using li
170 
171  std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
172 
173  // Don't recompute spill weight for an unspillable register.
174  bool Spillable = li.isSpillable();
175 
176  bool localSplitArtifact = start && end;
177 
178  // Do not update future local split artifacts.
179  bool updateLI = !localSplitArtifact;
180 
181  if (localSplitArtifact) {
182  MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
183  assert(localMBB == LIS.getMBBFromIndex(*start) &&
184  "start and end are expected to be in the same basic block");
185 
186  // Local split artifact will have 2 additional copy instructions and they
187  // will be in the same BB.
188  // localLI = COPY other
189  // ...
190  // other = COPY localLI
191  totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
192  totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
193 
194  numInstr += 2;
195  }
196 
197  // CopyHint is a sortable hint derived from a COPY instruction.
198  struct CopyHint {
199  unsigned Reg;
200  float Weight;
201  bool IsPhys;
202  unsigned HintOrder;
203  CopyHint(unsigned R, float W, bool P, unsigned HR) :
204  Reg(R), Weight(W), IsPhys(P), HintOrder(HR) {}
205  bool operator<(const CopyHint &rhs) const {
206  // Always prefer any physreg hint.
207  if (IsPhys != rhs.IsPhys)
208  return (IsPhys && !rhs.IsPhys);
209  if (Weight != rhs.Weight)
210  return (Weight > rhs.Weight);
211 
212  // This is just a temporary way to achive NFC for targets that don't
213  // enable multiple copy hints. HintOrder should be removed when all
214  // targets return true in enableMultipleCopyHints().
215  return (HintOrder < rhs.HintOrder);
216 
217 #if 0 // Should replace the HintOrder check, see above.
218  // (just for the purpose of maintaining the set)
219  return Reg < rhs.Reg;
220 #endif
221  }
222  };
223  std::set<CopyHint> CopyHints;
224 
225  // Temporary: see comment for HintOrder above.
226  unsigned CopyHintOrder = 0;
228  I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
229  I != E; ) {
230  MachineInstr *mi = &*(I++);
231 
232  // For local split artifacts, we are interested only in instructions between
233  // the expected start and end of the range.
234  SlotIndex si = LIS.getInstructionIndex(*mi);
235  if (localSplitArtifact && ((si < *start) || (si > *end)))
236  continue;
237 
238  numInstr++;
239  if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue())
240  continue;
241  if (!visited.insert(mi).second)
242  continue;
243 
244  float weight = 1.0f;
245  if (Spillable) {
246  // Get loop info for mi.
247  if (mi->getParent() != mbb) {
248  mbb = mi->getParent();
249  loop = Loops.getLoopFor(mbb);
250  isExiting = loop ? loop->isLoopExiting(mbb) : false;
251  }
252 
253  // Calculate instr weight.
254  bool reads, writes;
255  std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
256  weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
257 
258  // Give extra weight to what looks like a loop induction variable update.
259  if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
260  weight *= 3;
261 
262  totalWeight += weight;
263  }
264 
265  // Get allocation hints from copies.
266  if (!mi->isCopy() ||
267  (TargetHint.first != 0 && !tri.enableMultipleCopyHints()))
268  continue;
269  unsigned hint = copyHint(mi, li.reg, tri, mri);
270  if (!hint)
271  continue;
272  // Force hweight onto the stack so that x86 doesn't add hidden precision,
273  // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
274  //
275  // FIXME: we probably shouldn't use floats at all.
276  volatile float hweight = Hint[hint] += weight;
278  CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint),
279  (tri.enableMultipleCopyHints() ? hint : CopyHintOrder++)));
280  }
281 
282  Hint.clear();
283 
284  // Pass all the sorted copy hints to mri.
285  if (updateLI && CopyHints.size()) {
286  // Remove a generic hint if previously added by target.
287  if (TargetHint.first == 0 && TargetHint.second)
288  mri.clearSimpleHint(li.reg);
289 
290  for (auto &Hint : CopyHints) {
291  if (TargetHint.first != 0 && Hint.Reg == TargetHint.second)
292  // Don't add again the target-type hint.
293  continue;
294  mri.addRegAllocationHint(li.reg, Hint.Reg);
295  if (!tri.enableMultipleCopyHints())
296  break;
297  }
298 
299  // Weakly boost the spill weight of hinted registers.
300  totalWeight *= 1.01F;
301  }
302 
303  // If the live interval was already unspillable, leave it that way.
304  if (!Spillable)
305  return -1.0;
306 
307  // Mark li as unspillable if all live ranges are tiny and the interval
308  // is not live at any reg mask. If the interval is live at a reg mask
309  // spilling may be required.
310  if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
311  !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
312  li.markNotSpillable();
313  return -1.0;
314  }
315 
316  // If all of the definitions of the interval are re-materializable,
317  // it is a preferred candidate for spilling.
318  // FIXME: this gets much more complicated once we support non-trivial
319  // re-materialization.
320  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
321  totalWeight *= 0.5F;
322 
323  if (localSplitArtifact)
324  return normalize(totalWeight, start->distance(*end), numInstr);
325  return normalize(totalWeight, li.getSize(), numInstr);
326 }
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:245
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...
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
virtual bool enableMultipleCopyHints() const
The creation of multiple copy hints have been implemented in weightCalcHelper(), but since this affec...
Hexagon Hardware Loops
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:864
bool isIdentityCopy() const
Return true is the instruction is an identity copy.
Definition: MachineInstr.h:879
AliasAnalysis * getAliasAnalysis() 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)
#define P(N)
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:197
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
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
Definition: MachineInstr.h:860
bool isImplicitDef() const
Definition: MachineInstr.h:834
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:819
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: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.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:142
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:60
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
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:767
#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:298
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