LLVM  8.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  LLVM_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  unsigned 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.
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  unsigned 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;
256  CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint)));
257  }
258 
259  Hint.clear();
260 
261  // Pass all the sorted copy hints to mri.
262  if (updateLI && CopyHints.size()) {
263  // Remove a generic hint if previously added by target.
264  if (TargetHint.first == 0 && TargetHint.second)
265  mri.clearSimpleHint(li.reg);
266 
267  std::set<unsigned> HintedRegs;
268  for (auto &Hint : CopyHints) {
269  if (!HintedRegs.insert(Hint.Reg).second ||
270  (TargetHint.first != 0 && Hint.Reg == TargetHint.second))
271  // Don't add the same reg twice or the target-type hint again.
272  continue;
273  mri.addRegAllocationHint(li.reg, Hint.Reg);
274  }
275 
276  // Weakly boost the spill weight of hinted registers.
277  totalWeight *= 1.01F;
278  }
279 
280  // If the live interval was already unspillable, leave it that way.
281  if (!Spillable)
282  return -1.0;
283 
284  // Mark li as unspillable if all live ranges are tiny and the interval
285  // is not live at any reg mask. If the interval is live at a reg mask
286  // spilling may be required.
287  if (updateLI && li.isZeroLength(LIS.getSlotIndexes()) &&
288  !li.isLiveAtIndexes(LIS.getRegMaskSlots())) {
289  li.markNotSpillable();
290  return -1.0;
291  }
292 
293  // If all of the definitions of the interval are re-materializable,
294  // it is a preferred candidate for spilling.
295  // FIXME: this gets much more complicated once we support non-trivial
296  // re-materialization.
297  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
298  totalWeight *= 0.5F;
299 
300  if (localSplitArtifact)
301  return normalize(totalWeight, start->distance(*end), numInstr);
302  return normalize(totalWeight, li.getSize(), numInstr);
303 }
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:259
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
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...
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 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:53
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
Hexagon Hardware Loops
const HexagonInstrInfo * TII
Result of a LiveRange query.
Definition: LiveInterval.h:90
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: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: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: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
bool isImplicitDef() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool isDebugInstr() const
Definition: MachineInstr.h:999
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.
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)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange&#39;s.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
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:64
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
IRTranslator LLVM IR MI
float(*)(float, unsigned, unsigned) NormalizingFn
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
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