LLVM  6.0.0svn
InlineSpiller.cpp
Go to the documentation of this file.
1 //===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
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 //
10 // The inline spiller modifies the machine function directly instead of
11 // inserting spills and restores in VirtRegMap.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "LiveRangeCalc.h"
16 #include "Spiller.h"
17 #include "SplitKit.h"
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
52 #include "llvm/Support/Compiler.h"
53 #include "llvm/Support/Debug.h"
56 #include <cassert>
57 #include <iterator>
58 #include <tuple>
59 #include <utility>
60 #include <vector>
61 
62 using namespace llvm;
63 
64 #define DEBUG_TYPE "regalloc"
65 
66 STATISTIC(NumSpilledRanges, "Number of spilled live ranges");
67 STATISTIC(NumSnippets, "Number of spilled snippets");
68 STATISTIC(NumSpills, "Number of spills inserted");
69 STATISTIC(NumSpillsRemoved, "Number of spills removed");
70 STATISTIC(NumReloads, "Number of reloads inserted");
71 STATISTIC(NumReloadsRemoved, "Number of reloads removed");
72 STATISTIC(NumFolded, "Number of folded stack accesses");
73 STATISTIC(NumFoldedLoads, "Number of folded loads");
74 STATISTIC(NumRemats, "Number of rematerialized defs for spilling");
75 
76 static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
77  cl::desc("Disable inline spill hoisting"));
78 
79 namespace {
80 
81 class HoistSpillHelper : private LiveRangeEdit::Delegate {
82  MachineFunction &MF;
83  LiveIntervals &LIS;
84  LiveStacks &LSS;
85  AliasAnalysis *AA;
88  VirtRegMap &VRM;
90  const TargetInstrInfo &TII;
91  const TargetRegisterInfo &TRI;
92  const MachineBlockFrequencyInfo &MBFI;
93 
95 
96  // Map from StackSlot to the LiveInterval of the original register.
97  // Note the LiveInterval of the original register may have been deleted
98  // after it is spilled. We keep a copy here to track the range where
99  // spills can be moved.
101 
102  // Map from pair of (StackSlot and Original VNI) to a set of spills which
103  // have the same stackslot and have equal values defined by Original VNI.
104  // These spills are mergeable and are hoist candiates.
105  using MergeableSpillsMap =
107  MergeableSpillsMap MergeableSpills;
108 
109  /// This is the map from original register to a set containing all its
110  /// siblings. To hoist a spill to another BB, we need to find out a live
111  /// sibling there and use it as the source of the new spill.
113 
114  bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
115  MachineBasicBlock &BB, unsigned &LiveReg);
116 
117  void rmRedundantSpills(
118  SmallPtrSet<MachineInstr *, 16> &Spills,
121 
122  void getVisitOrders(
123  MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
128 
129  void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
130  SmallPtrSet<MachineInstr *, 16> &Spills,
133 
134 public:
135  HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
136  VirtRegMap &vrm)
137  : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
138  LSS(pass.getAnalysis<LiveStacks>()),
139  AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
140  MDT(pass.getAnalysis<MachineDominatorTree>()),
141  Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
142  MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
143  TRI(*mf.getSubtarget().getRegisterInfo()),
144  MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
145  IPA(LIS, mf.getNumBlockIDs()) {}
146 
147  void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
148  unsigned Original);
149  bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
150  void hoistAllSpills();
151  void LRE_DidCloneVirtReg(unsigned, unsigned) override;
152 };
153 
154 class InlineSpiller : public Spiller {
155  MachineFunction &MF;
156  LiveIntervals &LIS;
157  LiveStacks &LSS;
158  AliasAnalysis *AA;
161  VirtRegMap &VRM;
163  const TargetInstrInfo &TII;
164  const TargetRegisterInfo &TRI;
165  const MachineBlockFrequencyInfo &MBFI;
166 
167  // Variables that are valid during spill(), but used by multiple methods.
168  LiveRangeEdit *Edit;
169  LiveInterval *StackInt;
170  int StackSlot;
171  unsigned Original;
172 
173  // All registers to spill to StackSlot, including the main register.
174  SmallVector<unsigned, 8> RegsToSpill;
175 
176  // All COPY instructions to/from snippets.
177  // They are ignored since both operands refer to the same stack slot.
178  SmallPtrSet<MachineInstr*, 8> SnippetCopies;
179 
180  // Values that failed to remat at some point.
181  SmallPtrSet<VNInfo*, 8> UsedValues;
182 
183  // Dead defs generated during spilling.
185 
186  // Object records spills information and does the hoisting.
187  HoistSpillHelper HSpiller;
188 
189  ~InlineSpiller() override = default;
190 
191 public:
192  InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
193  : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
194  LSS(pass.getAnalysis<LiveStacks>()),
195  AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
196  MDT(pass.getAnalysis<MachineDominatorTree>()),
197  Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
198  MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
199  TRI(*mf.getSubtarget().getRegisterInfo()),
200  MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
201  HSpiller(pass, mf, vrm) {}
202 
203  void spill(LiveRangeEdit &) override;
204  void postOptimization() override;
205 
206 private:
207  bool isSnippet(const LiveInterval &SnipLI);
208  void collectRegsToSpill();
209 
210  bool isRegToSpill(unsigned Reg) { return is_contained(RegsToSpill, Reg); }
211 
212  bool isSibling(unsigned Reg);
213  bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
214  void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
215 
216  void markValueUsed(LiveInterval*, VNInfo*);
217  bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
218  void reMaterializeAll();
219 
220  bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
221  bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
222  MachineInstr *LoadMI = nullptr);
223  void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI);
224  void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI);
225 
226  void spillAroundUses(unsigned Reg);
227  void spillAll();
228 };
229 
230 } // end anonymous namespace
231 
232 Spiller::~Spiller() = default;
233 
234 void Spiller::anchor() {}
235 
237  MachineFunction &mf,
238  VirtRegMap &vrm) {
239  return new InlineSpiller(pass, mf, vrm);
240 }
241 
242 //===----------------------------------------------------------------------===//
243 // Snippets
244 //===----------------------------------------------------------------------===//
245 
246 // When spilling a virtual register, we also spill any snippets it is connected
247 // to. The snippets are small live ranges that only have a single real use,
248 // leftovers from live range splitting. Spilling them enables memory operand
249 // folding or tightens the live range around the single use.
250 //
251 // This minimizes register pressure and maximizes the store-to-load distance for
252 // spill slots which can be important in tight loops.
253 
254 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
255 /// otherwise return 0.
256 static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg) {
257  if (!MI.isFullCopy())
258  return 0;
259  if (MI.getOperand(0).getReg() == Reg)
260  return MI.getOperand(1).getReg();
261  if (MI.getOperand(1).getReg() == Reg)
262  return MI.getOperand(0).getReg();
263  return 0;
264 }
265 
266 /// isSnippet - Identify if a live interval is a snippet that should be spilled.
267 /// It is assumed that SnipLI is a virtual register with the same original as
268 /// Edit->getReg().
269 bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
270  unsigned Reg = Edit->getReg();
271 
272  // A snippet is a tiny live range with only a single instruction using it
273  // besides copies to/from Reg or spills/fills. We accept:
274  //
275  // %snip = COPY %Reg / FILL fi#
276  // %snip = USE %snip
277  // %Reg = COPY %snip / SPILL %snip, fi#
278  //
279  if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
280  return false;
281 
282  MachineInstr *UseMI = nullptr;
283 
284  // Check that all uses satisfy our criteria.
286  RI = MRI.reg_instr_nodbg_begin(SnipLI.reg),
287  E = MRI.reg_instr_nodbg_end(); RI != E; ) {
288  MachineInstr &MI = *RI++;
289 
290  // Allow copies to/from Reg.
291  if (isFullCopyOf(MI, Reg))
292  continue;
293 
294  // Allow stack slot loads.
295  int FI;
296  if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
297  continue;
298 
299  // Allow stack slot stores.
300  if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
301  continue;
302 
303  // Allow a single additional instruction.
304  if (UseMI && &MI != UseMI)
305  return false;
306  UseMI = &MI;
307  }
308  return true;
309 }
310 
311 /// collectRegsToSpill - Collect live range snippets that only have a single
312 /// real use.
313 void InlineSpiller::collectRegsToSpill() {
314  unsigned Reg = Edit->getReg();
315 
316  // Main register always spills.
317  RegsToSpill.assign(1, Reg);
318  SnippetCopies.clear();
319 
320  // Snippets all have the same original, so there can't be any for an original
321  // register.
322  if (Original == Reg)
323  return;
324 
326  RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
327  MachineInstr &MI = *RI++;
328  unsigned SnipReg = isFullCopyOf(MI, Reg);
329  if (!isSibling(SnipReg))
330  continue;
331  LiveInterval &SnipLI = LIS.getInterval(SnipReg);
332  if (!isSnippet(SnipLI))
333  continue;
334  SnippetCopies.insert(&MI);
335  if (isRegToSpill(SnipReg))
336  continue;
337  RegsToSpill.push_back(SnipReg);
338  DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
339  ++NumSnippets;
340  }
341 }
342 
343 bool InlineSpiller::isSibling(unsigned Reg) {
345  VRM.getOriginal(Reg) == Original;
346 }
347 
348 /// It is beneficial to spill to earlier place in the same BB in case
349 /// as follows:
350 /// There is an alternative def earlier in the same MBB.
351 /// Hoist the spill as far as possible in SpillMBB. This can ease
352 /// register pressure:
353 ///
354 /// x = def
355 /// y = use x
356 /// s = copy x
357 ///
358 /// Hoisting the spill of s to immediately after the def removes the
359 /// interference between x and y:
360 ///
361 /// x = def
362 /// spill x
363 /// y = use x<kill>
364 ///
365 /// This hoist only helps when the copy kills its source.
366 ///
367 bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
368  MachineInstr &CopyMI) {
369  SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
370 #ifndef NDEBUG
371  VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
372  assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");
373 #endif
374 
375  unsigned SrcReg = CopyMI.getOperand(1).getReg();
376  LiveInterval &SrcLI = LIS.getInterval(SrcReg);
377  VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
378  LiveQueryResult SrcQ = SrcLI.Query(Idx);
379  MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
380  if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
381  return false;
382 
383  // Conservatively extend the stack slot range to the range of the original
384  // value. We may be able to do better with stack slot coloring by being more
385  // careful here.
386  assert(StackInt && "No stack slot assigned yet.");
387  LiveInterval &OrigLI = LIS.getInterval(Original);
388  VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
389  StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
390  DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
391  << *StackInt << '\n');
392 
393  // We are going to spill SrcVNI immediately after its def, so clear out
394  // any later spills of the same value.
395  eliminateRedundantSpills(SrcLI, SrcVNI);
396 
397  MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
399  if (SrcVNI->isPHIDef())
400  MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
401  else {
402  MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
403  assert(DefMI && "Defining instruction disappeared");
404  MII = DefMI;
405  ++MII;
406  }
407  // Insert spill without kill flag immediately after def.
408  TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
409  MRI.getRegClass(SrcReg), &TRI);
410  --MII; // Point to store instruction.
411  LIS.InsertMachineInstrInMaps(*MII);
412  DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);
413 
414  HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
415  ++NumSpills;
416  return true;
417 }
418 
419 /// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
420 /// redundant spills of this value in SLI.reg and sibling copies.
421 void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
422  assert(VNI && "Missing value");
424  WorkList.push_back(std::make_pair(&SLI, VNI));
425  assert(StackInt && "No stack slot assigned yet.");
426 
427  do {
428  LiveInterval *LI;
429  std::tie(LI, VNI) = WorkList.pop_back_val();
430  unsigned Reg = LI->reg;
431  DEBUG(dbgs() << "Checking redundant spills for "
432  << VNI->id << '@' << VNI->def << " in " << *LI << '\n');
433 
434  // Regs to spill are taken care of.
435  if (isRegToSpill(Reg))
436  continue;
437 
438  // Add all of VNI's live range to StackInt.
439  StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
440  DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
441 
442  // Find all spills and copies of VNI.
444  UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
445  UI != E; ) {
446  MachineInstr &MI = *UI++;
447  if (!MI.isCopy() && !MI.mayStore())
448  continue;
449  SlotIndex Idx = LIS.getInstructionIndex(MI);
450  if (LI->getVNInfoAt(Idx) != VNI)
451  continue;
452 
453  // Follow sibling copies down the dominator tree.
454  if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
455  if (isSibling(DstReg)) {
456  LiveInterval &DstLI = LIS.getInterval(DstReg);
457  VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
458  assert(DstVNI && "Missing defined value");
459  assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");
460  WorkList.push_back(std::make_pair(&DstLI, DstVNI));
461  }
462  continue;
463  }
464 
465  // Erase spills.
466  int FI;
467  if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
468  DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI);
469  // eliminateDeadDefs won't normally remove stores, so switch opcode.
470  MI.setDesc(TII.get(TargetOpcode::KILL));
471  DeadDefs.push_back(&MI);
472  ++NumSpillsRemoved;
473  if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
474  --NumSpills;
475  }
476  }
477  } while (!WorkList.empty());
478 }
479 
480 //===----------------------------------------------------------------------===//
481 // Rematerialization
482 //===----------------------------------------------------------------------===//
483 
484 /// markValueUsed - Remember that VNI failed to rematerialize, so its defining
485 /// instruction cannot be eliminated. See through snippet copies
486 void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
488  WorkList.push_back(std::make_pair(LI, VNI));
489  do {
490  std::tie(LI, VNI) = WorkList.pop_back_val();
491  if (!UsedValues.insert(VNI).second)
492  continue;
493 
494  if (VNI->isPHIDef()) {
495  MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
496  for (MachineBasicBlock *P : MBB->predecessors()) {
497  VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
498  if (PVNI)
499  WorkList.push_back(std::make_pair(LI, PVNI));
500  }
501  continue;
502  }
503 
504  // Follow snippet copies.
505  MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
506  if (!SnippetCopies.count(MI))
507  continue;
508  LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
509  assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
510  VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
511  assert(SnipVNI && "Snippet undefined before copy");
512  WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
513  } while (!WorkList.empty());
514 }
515 
516 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
517 bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
518  // Analyze instruction
520  MIBundleOperands::VirtRegInfo RI =
521  MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops);
522 
523  if (!RI.Reads)
524  return false;
525 
526  SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
527  VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
528 
529  if (!ParentVNI) {
530  DEBUG(dbgs() << "\tadding <undef> flags: ");
531  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
532  MachineOperand &MO = MI.getOperand(i);
533  if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg)
534  MO.setIsUndef();
535  }
536  DEBUG(dbgs() << UseIdx << '\t' << MI);
537  return true;
538  }
539 
540  if (SnippetCopies.count(&MI))
541  return false;
542 
543  LiveInterval &OrigLI = LIS.getInterval(Original);
544  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
545  LiveRangeEdit::Remat RM(ParentVNI);
546  RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
547 
548  if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
549  markValueUsed(&VirtReg, ParentVNI);
550  DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
551  return false;
552  }
553 
554  // If the instruction also writes VirtReg.reg, it had better not require the
555  // same register for uses and defs.
556  if (RI.Tied) {
557  markValueUsed(&VirtReg, ParentVNI);
558  DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI);
559  return false;
560  }
561 
562  // Before rematerializing into a register for a single instruction, try to
563  // fold a load into the instruction. That avoids allocating a new register.
564  if (RM.OrigMI->canFoldAsLoad() &&
565  foldMemoryOperand(Ops, RM.OrigMI)) {
566  Edit->markRematerialized(RM.ParentVNI);
567  ++NumFoldedLoads;
568  return true;
569  }
570 
571  // Allocate a new register for the remat.
572  unsigned NewVReg = Edit->createFrom(Original);
573 
574  // Finally we can rematerialize OrigMI before MI.
575  SlotIndex DefIdx =
576  Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);
577 
578  // We take the DebugLoc from MI, since OrigMI may be attributed to a
579  // different source location.
580  auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
581  NewMI->setDebugLoc(MI.getDebugLoc());
582 
583  (void)DefIdx;
584  DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
585  << *LIS.getInstructionFromIndex(DefIdx));
586 
587  // Replace operands
588  for (const auto &OpPair : Ops) {
589  MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
590  if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) {
591  MO.setReg(NewVReg);
592  MO.setIsKill();
593  }
594  }
595  DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n');
596 
597  ++NumRemats;
598  return true;
599 }
600 
601 /// reMaterializeAll - Try to rematerialize as many uses as possible,
602 /// and trim the live ranges after.
603 void InlineSpiller::reMaterializeAll() {
604  if (!Edit->anyRematerializable(AA))
605  return;
606 
607  UsedValues.clear();
608 
609  // Try to remat before all uses of snippets.
610  bool anyRemat = false;
611  for (unsigned Reg : RegsToSpill) {
612  LiveInterval &LI = LIS.getInterval(Reg);
614  RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
615  RegI != E; ) {
616  MachineInstr &MI = *RegI++;
617 
618  // Debug values are not allowed to affect codegen.
619  if (MI.isDebugValue())
620  continue;
621 
622  anyRemat |= reMaterializeFor(LI, MI);
623  }
624  }
625  if (!anyRemat)
626  return;
627 
628  // Remove any values that were completely rematted.
629  for (unsigned Reg : RegsToSpill) {
630  LiveInterval &LI = LIS.getInterval(Reg);
631  for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
632  I != E; ++I) {
633  VNInfo *VNI = *I;
634  if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
635  continue;
636  MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
637  MI->addRegisterDead(Reg, &TRI);
638  if (!MI->allDefsAreDead())
639  continue;
640  DEBUG(dbgs() << "All defs dead: " << *MI);
641  DeadDefs.push_back(MI);
642  }
643  }
644 
645  // Eliminate dead code after remat. Note that some snippet copies may be
646  // deleted here.
647  if (DeadDefs.empty())
648  return;
649  DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
650  Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
651 
652  // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
653  // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
654  // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
655  // removed, PHI VNI are still left in the LiveInterval.
656  // So to get rid of unused reg, we need to check whether it has non-dbg
657  // reference instead of whether it has non-empty interval.
658  unsigned ResultPos = 0;
659  for (unsigned Reg : RegsToSpill) {
660  if (MRI.reg_nodbg_empty(Reg)) {
661  Edit->eraseVirtReg(Reg);
662  continue;
663  }
664 
665  assert(LIS.hasInterval(Reg) &&
666  (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
667  "Empty and not used live-range?!");
668 
669  RegsToSpill[ResultPos++] = Reg;
670  }
671  RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
672  DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n");
673 }
674 
675 //===----------------------------------------------------------------------===//
676 // Spilling
677 //===----------------------------------------------------------------------===//
678 
679 /// If MI is a load or store of StackSlot, it can be removed.
680 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
681  int FI = 0;
682  unsigned InstrReg = TII.isLoadFromStackSlot(*MI, FI);
683  bool IsLoad = InstrReg;
684  if (!IsLoad)
685  InstrReg = TII.isStoreToStackSlot(*MI, FI);
686 
687  // We have a stack access. Is it the right register and slot?
688  if (InstrReg != Reg || FI != StackSlot)
689  return false;
690 
691  if (!IsLoad)
692  HSpiller.rmFromMergeableSpills(*MI, StackSlot);
693 
694  DEBUG(dbgs() << "Coalescing stack access: " << *MI);
695  LIS.RemoveMachineInstrFromMaps(*MI);
696  MI->eraseFromParent();
697 
698  if (IsLoad) {
699  ++NumReloadsRemoved;
700  --NumReloads;
701  } else {
702  ++NumSpillsRemoved;
703  --NumSpills;
704  }
705 
706  return true;
707 }
708 
709 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
711 // Dump the range of instructions from B to E with their slot indexes.
714  LiveIntervals const &LIS,
715  const char *const header,
716  unsigned VReg =0) {
717  char NextLine = '\n';
718  char SlotIndent = '\t';
719 
720  if (std::next(B) == E) {
721  NextLine = ' ';
722  SlotIndent = ' ';
723  }
724 
725  dbgs() << '\t' << header << ": " << NextLine;
726 
727  for (MachineBasicBlock::iterator I = B; I != E; ++I) {
728  SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();
729 
730  // If a register was passed in and this instruction has it as a
731  // destination that is marked as an early clobber, print the
732  // early-clobber slot index.
733  if (VReg) {
734  MachineOperand *MO = I->findRegisterDefOperand(VReg);
735  if (MO && MO->isEarlyClobber())
736  Idx = Idx.getRegSlot(true);
737  }
738 
739  dbgs() << SlotIndent << Idx << '\t' << *I;
740  }
741 }
742 #endif
743 
744 /// foldMemoryOperand - Try folding stack slot references in Ops into their
745 /// instructions.
746 ///
747 /// @param Ops Operand indices from analyzeVirtReg().
748 /// @param LoadMI Load instruction to use instead of stack slot when non-null.
749 /// @return True on success.
750 bool InlineSpiller::
751 foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
752  MachineInstr *LoadMI) {
753  if (Ops.empty())
754  return false;
755  // Don't attempt folding in bundles.
756  MachineInstr *MI = Ops.front().first;
757  if (Ops.back().first != MI || MI->isBundled())
758  return false;
759 
760  bool WasCopy = MI->isCopy();
761  unsigned ImpReg = 0;
762 
763  // Spill subregs if the target allows it.
764  // We always want to spill subregs for stackmap/patchpoint pseudos.
765  bool SpillSubRegs = TII.isSubregFoldable() ||
766  MI->getOpcode() == TargetOpcode::STATEPOINT ||
767  MI->getOpcode() == TargetOpcode::PATCHPOINT ||
768  MI->getOpcode() == TargetOpcode::STACKMAP;
769 
770  // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
771  // operands.
772  SmallVector<unsigned, 8> FoldOps;
773  for (const auto &OpPair : Ops) {
774  unsigned Idx = OpPair.second;
775  assert(MI == OpPair.first && "Instruction conflict during operand folding");
776  MachineOperand &MO = MI->getOperand(Idx);
777  if (MO.isImplicit()) {
778  ImpReg = MO.getReg();
779  continue;
780  }
781 
782  if (!SpillSubRegs && MO.getSubReg())
783  return false;
784  // We cannot fold a load instruction into a def.
785  if (LoadMI && MO.isDef())
786  return false;
787  // Tied use operands should not be passed to foldMemoryOperand.
788  if (!MI->isRegTiedToDefOperand(Idx))
789  FoldOps.push_back(Idx);
790  }
791 
792  // If we only have implicit uses, we won't be able to fold that.
793  // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
794  if (FoldOps.empty())
795  return false;
796 
797  MachineInstrSpan MIS(MI);
798 
799  MachineInstr *FoldMI =
800  LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
801  : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS);
802  if (!FoldMI)
803  return false;
804 
805  // Remove LIS for any dead defs in the original MI not in FoldMI.
806  for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
807  if (!MO->isReg())
808  continue;
809  unsigned Reg = MO->getReg();
810  if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
811  MRI.isReserved(Reg)) {
812  continue;
813  }
814  // Skip non-Defs, including undef uses and internal reads.
815  if (MO->isUse())
816  continue;
817  MIBundleOperands::PhysRegInfo RI =
818  MIBundleOperands(*FoldMI).analyzePhysReg(Reg, &TRI);
819  if (RI.FullyDefined)
820  continue;
821  // FoldMI does not define this physreg. Remove the LI segment.
822  assert(MO->isDead() && "Cannot fold physreg def");
823  SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
824  LIS.removePhysRegDefAt(Reg, Idx);
825  }
826 
827  int FI;
828  if (TII.isStoreToStackSlot(*MI, FI) &&
829  HSpiller.rmFromMergeableSpills(*MI, FI))
830  --NumSpills;
831  LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
832  MI->eraseFromParent();
833 
834  // Insert any new instructions other than FoldMI into the LIS maps.
835  assert(!MIS.empty() && "Unexpected empty span of instructions!");
836  for (MachineInstr &MI : MIS)
837  if (&MI != FoldMI)
838  LIS.InsertMachineInstrInMaps(MI);
839 
840  // TII.foldMemoryOperand may have left some implicit operands on the
841  // instruction. Strip them.
842  if (ImpReg)
843  for (unsigned i = FoldMI->getNumOperands(); i; --i) {
844  MachineOperand &MO = FoldMI->getOperand(i - 1);
845  if (!MO.isReg() || !MO.isImplicit())
846  break;
847  if (MO.getReg() == ImpReg)
848  FoldMI->RemoveOperand(i - 1);
849  }
850 
851  DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,
852  "folded"));
853 
854  if (!WasCopy)
855  ++NumFolded;
856  else if (Ops.front().second == 0) {
857  ++NumSpills;
858  HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
859  } else
860  ++NumReloads;
861  return true;
862 }
863 
864 void InlineSpiller::insertReload(unsigned NewVReg,
865  SlotIndex Idx,
867  MachineBasicBlock &MBB = *MI->getParent();
868 
869  MachineInstrSpan MIS(MI);
870  TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
871  MRI.getRegClass(NewVReg), &TRI);
872 
873  LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
874 
875  DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",
876  NewVReg));
877  ++NumReloads;
878 }
879 
880 /// Check if \p Def fully defines a VReg with an undefined value.
881 /// If that's the case, that means the value of VReg is actually
882 /// not relevant.
883 static bool isFullUndefDef(const MachineInstr &Def) {
884  if (!Def.isImplicitDef())
885  return false;
886  assert(Def.getNumOperands() == 1 &&
887  "Implicit def with more than one definition");
888  // We can say that the VReg defined by Def is undef, only if it is
889  // fully defined by Def. Otherwise, some of the lanes may not be
890  // undef and the value of the VReg matters.
891  return !Def.getOperand(0).getSubReg();
892 }
893 
894 /// insertSpill - Insert a spill of NewVReg after MI.
895 void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill,
897  MachineBasicBlock &MBB = *MI->getParent();
898 
899  MachineInstrSpan MIS(MI);
900  bool IsRealSpill = true;
901  if (isFullUndefDef(*MI)) {
902  // Don't spill undef value.
903  // Anything works for undef, in particular keeping the memory
904  // uninitialized is a viable option and it saves code size and
905  // run time.
906  BuildMI(MBB, std::next(MI), MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
907  .addReg(NewVReg, getKillRegState(isKill));
908  IsRealSpill = false;
909  } else
910  TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot,
911  MRI.getRegClass(NewVReg), &TRI);
912 
913  LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end());
914 
915  DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS,
916  "spill"));
917  ++NumSpills;
918  if (IsRealSpill)
919  HSpiller.addToMergeableSpills(*std::next(MI), StackSlot, Original);
920 }
921 
922 /// spillAroundUses - insert spill code around each use of Reg.
923 void InlineSpiller::spillAroundUses(unsigned Reg) {
924  DEBUG(dbgs() << "spillAroundUses " << PrintReg(Reg) << '\n');
925  LiveInterval &OldLI = LIS.getInterval(Reg);
926 
927  // Iterate over instructions using Reg.
929  RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
930  RegI != E; ) {
931  MachineInstr *MI = &*(RegI++);
932 
933  // Debug values are not allowed to affect codegen.
934  if (MI->isDebugValue()) {
935  // Modify DBG_VALUE now that the value is in a spill slot.
936  MachineBasicBlock *MBB = MI->getParent();
937  DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI);
938  buildDbgValueForSpill(*MBB, MI, *MI, StackSlot);
939  MBB->erase(MI);
940  continue;
941  }
942 
943  // Ignore copies to/from snippets. We'll delete them.
944  if (SnippetCopies.count(MI))
945  continue;
946 
947  // Stack slot accesses may coalesce away.
948  if (coalesceStackAccess(MI, Reg))
949  continue;
950 
951  // Analyze instruction.
953  MIBundleOperands::VirtRegInfo RI =
954  MIBundleOperands(*MI).analyzeVirtReg(Reg, &Ops);
955 
956  // Find the slot index where this instruction reads and writes OldLI.
957  // This is usually the def slot, except for tied early clobbers.
958  SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
959  if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
960  if (SlotIndex::isSameInstr(Idx, VNI->def))
961  Idx = VNI->def;
962 
963  // Check for a sibling copy.
964  unsigned SibReg = isFullCopyOf(*MI, Reg);
965  if (SibReg && isSibling(SibReg)) {
966  // This may actually be a copy between snippets.
967  if (isRegToSpill(SibReg)) {
968  DEBUG(dbgs() << "Found new snippet copy: " << *MI);
969  SnippetCopies.insert(MI);
970  continue;
971  }
972  if (RI.Writes) {
973  if (hoistSpillInsideBB(OldLI, *MI)) {
974  // This COPY is now dead, the value is already in the stack slot.
975  MI->getOperand(0).setIsDead();
976  DeadDefs.push_back(MI);
977  continue;
978  }
979  } else {
980  // This is a reload for a sib-reg copy. Drop spills downstream.
981  LiveInterval &SibLI = LIS.getInterval(SibReg);
982  eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
983  // The COPY will fold to a reload below.
984  }
985  }
986 
987  // Attempt to fold memory ops.
988  if (foldMemoryOperand(Ops))
989  continue;
990 
991  // Create a new virtual register for spill/fill.
992  // FIXME: Infer regclass from instruction alone.
993  unsigned NewVReg = Edit->createFrom(Reg);
994 
995  if (RI.Reads)
996  insertReload(NewVReg, Idx, MI);
997 
998  // Rewrite instruction operands.
999  bool hasLiveDef = false;
1000  for (const auto &OpPair : Ops) {
1001  MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
1002  MO.setReg(NewVReg);
1003  if (MO.isUse()) {
1004  if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1005  MO.setIsKill();
1006  } else {
1007  if (!MO.isDead())
1008  hasLiveDef = true;
1009  }
1010  }
1011  DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n');
1012 
1013  // FIXME: Use a second vreg if instruction has no tied ops.
1014  if (RI.Writes)
1015  if (hasLiveDef)
1016  insertSpill(NewVReg, true, MI);
1017  }
1018 }
1019 
1020 /// spillAll - Spill all registers remaining after rematerialization.
1021 void InlineSpiller::spillAll() {
1022  // Update LiveStacks now that we are committed to spilling.
1023  if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
1024  StackSlot = VRM.assignVirt2StackSlot(Original);
1025  StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
1026  StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
1027  } else
1028  StackInt = &LSS.getInterval(StackSlot);
1029 
1030  if (Original != Edit->getReg())
1031  VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1032 
1033  assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
1034  for (unsigned Reg : RegsToSpill)
1035  StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
1036  StackInt->getValNumInfo(0));
1037  DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
1038 
1039  // Spill around uses of all RegsToSpill.
1040  for (unsigned Reg : RegsToSpill)
1041  spillAroundUses(Reg);
1042 
1043  // Hoisted spills may cause dead code.
1044  if (!DeadDefs.empty()) {
1045  DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
1046  Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
1047  }
1048 
1049  // Finally delete the SnippetCopies.
1050  for (unsigned Reg : RegsToSpill) {
1052  RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
1053  RI != E; ) {
1054  MachineInstr &MI = *(RI++);
1055  assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy");
1056  // FIXME: Do this with a LiveRangeEdit callback.
1057  LIS.RemoveMachineInstrFromMaps(MI);
1058  MI.eraseFromParent();
1059  }
1060  }
1061 
1062  // Delete all spilled registers.
1063  for (unsigned Reg : RegsToSpill)
1064  Edit->eraseVirtReg(Reg);
1065 }
1066 
1067 void InlineSpiller::spill(LiveRangeEdit &edit) {
1068  ++NumSpilledRanges;
1069  Edit = &edit;
1071  && "Trying to spill a stack slot.");
1072  // Share a stack slot among all descendants of Original.
1073  Original = VRM.getOriginal(edit.getReg());
1074  StackSlot = VRM.getStackSlot(Original);
1075  StackInt = nullptr;
1076 
1077  DEBUG(dbgs() << "Inline spilling "
1078  << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))
1079  << ':' << edit.getParent()
1080  << "\nFrom original " << PrintReg(Original) << '\n');
1081  assert(edit.getParent().isSpillable() &&
1082  "Attempting to spill already spilled value.");
1083  assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
1084 
1085  collectRegsToSpill();
1086  reMaterializeAll();
1087 
1088  // Remat may handle everything.
1089  if (!RegsToSpill.empty())
1090  spillAll();
1091 
1092  Edit->calculateRegClassAndHint(MF, Loops, MBFI);
1093 }
1094 
1095 /// Optimizations after all the reg selections and spills are done.
1096 void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1097 
1098 /// When a spill is inserted, add the spill to MergeableSpills map.
1099 void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
1100  unsigned Original) {
1101  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1102  LiveInterval &OrigLI = LIS.getInterval(Original);
1103  // save a copy of LiveInterval in StackSlotToOrigLI because the original
1104  // LiveInterval may be cleared after all its references are spilled.
1105  if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
1106  auto LI = llvm::make_unique<LiveInterval>(OrigLI.reg, OrigLI.weight);
1107  LI->assign(OrigLI, Allocator);
1108  StackSlotToOrigLI[StackSlot] = std::move(LI);
1109  }
1110  SlotIndex Idx = LIS.getInstructionIndex(Spill);
1111  VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot());
1112  std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1113  MergeableSpills[MIdx].insert(&Spill);
1114 }
1115 
1116 /// When a spill is removed, remove the spill from MergeableSpills map.
1117 /// Return true if the spill is removed successfully.
1118 bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
1119  int StackSlot) {
1120  auto It = StackSlotToOrigLI.find(StackSlot);
1121  if (It == StackSlotToOrigLI.end())
1122  return false;
1123  SlotIndex Idx = LIS.getInstructionIndex(Spill);
1124  VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
1125  std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1126  return MergeableSpills[MIdx].erase(&Spill);
1127 }
1128 
1129 /// Check BB to see if it is a possible target BB to place a hoisted spill,
1130 /// i.e., there should be a living sibling of OrigReg at the insert point.
1131 bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
1132  MachineBasicBlock &BB, unsigned &LiveReg) {
1133  SlotIndex Idx;
1134  unsigned OrigReg = OrigLI.reg;
1135  MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, BB);
1136  if (MI != BB.end())
1137  Idx = LIS.getInstructionIndex(*MI);
1138  else
1139  Idx = LIS.getMBBEndIdx(&BB).getPrevSlot();
1140  SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg];
1141  assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI");
1142 
1143  for (auto const SibReg : Siblings) {
1144  LiveInterval &LI = LIS.getInterval(SibReg);
1145  VNInfo *VNI = LI.getVNInfoAt(Idx);
1146  if (VNI) {
1147  LiveReg = SibReg;
1148  return true;
1149  }
1150  }
1151  return false;
1152 }
1153 
1154 /// Remove redundant spills in the same BB. Save those redundant spills in
1155 /// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1156 void HoistSpillHelper::rmRedundantSpills(
1158  SmallVectorImpl<MachineInstr *> &SpillsToRm,
1160  // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1161  // another spill inside. If a BB contains more than one spill, only keep the
1162  // earlier spill with smaller SlotIndex.
1163  for (const auto CurrentSpill : Spills) {
1164  MachineBasicBlock *Block = CurrentSpill->getParent();
1165  MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
1166  MachineInstr *PrevSpill = SpillBBToSpill[Node];
1167  if (PrevSpill) {
1168  SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
1169  SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
1170  MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1171  MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1172  SpillsToRm.push_back(SpillToRm);
1173  SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
1174  } else {
1175  SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
1176  }
1177  }
1178  for (const auto SpillToRm : SpillsToRm)
1179  Spills.erase(SpillToRm);
1180 }
1181 
1182 /// Starting from \p Root find a top-down traversal order of the dominator
1183 /// tree to visit all basic blocks containing the elements of \p Spills.
1184 /// Redundant spills will be found and put into \p SpillsToRm at the same
1185 /// time. \p SpillBBToSpill will be populated as part of the process and
1186 /// maps a basic block to the first store occurring in the basic block.
1187 /// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1188 void HoistSpillHelper::getVisitOrders(
1191  SmallVectorImpl<MachineInstr *> &SpillsToRm,
1194  // The set contains all the possible BB nodes to which we may hoist
1195  // original spills.
1197  // Save the BB nodes on the path from the first BB node containing
1198  // non-redundant spill to the Root node.
1200  // All the spills to be hoisted must originate from a single def instruction
1201  // to the OrigReg. It means the def instruction should dominate all the spills
1202  // to be hoisted. We choose the BB where the def instruction is located as
1203  // the Root.
1204  MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
1205  // For every node on the dominator tree with spill, walk up on the dominator
1206  // tree towards the Root node until it is reached. If there is other node
1207  // containing spill in the middle of the path, the previous spill saw will
1208  // be redundant and the node containing it will be removed. All the nodes on
1209  // the path starting from the first node with non-redundant spill to the Root
1210  // node will be added to the WorkSet, which will contain all the possible
1211  // locations where spills may be hoisted to after the loop below is done.
1212  for (const auto Spill : Spills) {
1213  MachineBasicBlock *Block = Spill->getParent();
1214  MachineDomTreeNode *Node = MDT[Block];
1215  MachineInstr *SpillToRm = nullptr;
1216  while (Node != RootIDomNode) {
1217  // If Node dominates Block, and it already contains a spill, the spill in
1218  // Block will be redundant.
1219  if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1220  SpillToRm = SpillBBToSpill[MDT[Block]];
1221  break;
1222  /// If we see the Node already in WorkSet, the path from the Node to
1223  /// the Root node must already be traversed by another spill.
1224  /// Then no need to repeat.
1225  } else if (WorkSet.count(Node)) {
1226  break;
1227  } else {
1228  NodesOnPath.insert(Node);
1229  }
1230  Node = Node->getIDom();
1231  }
1232  if (SpillToRm) {
1233  SpillsToRm.push_back(SpillToRm);
1234  } else {
1235  // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1236  // set the initial status before hoisting start. The value of BBs
1237  // containing original spills is set to 0, in order to descriminate
1238  // with BBs containing hoisted spills which will be inserted to
1239  // SpillsToKeep later during hoisting.
1240  SpillsToKeep[MDT[Block]] = 0;
1241  WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
1242  }
1243  NodesOnPath.clear();
1244  }
1245 
1246  // Sort the nodes in WorkSet in top-down order and save the nodes
1247  // in Orders. Orders will be used for hoisting in runHoistSpills.
1248  unsigned idx = 0;
1249  Orders.push_back(MDT.getBase().getNode(Root));
1250  do {
1251  MachineDomTreeNode *Node = Orders[idx++];
1252  const std::vector<MachineDomTreeNode *> &Children = Node->getChildren();
1253  unsigned NumChildren = Children.size();
1254  for (unsigned i = 0; i != NumChildren; ++i) {
1255  MachineDomTreeNode *Child = Children[i];
1256  if (WorkSet.count(Child))
1257  Orders.push_back(Child);
1258  }
1259  } while (idx != Orders.size());
1260  assert(Orders.size() == WorkSet.size() &&
1261  "Orders have different size with WorkSet");
1262 
1263 #ifndef NDEBUG
1264  DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");
1266  for (; RIt != Orders.rend(); RIt++)
1267  DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");
1268  DEBUG(dbgs() << "\n");
1269 #endif
1270 }
1271 
1272 /// Try to hoist spills according to BB hotness. The spills to removed will
1273 /// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1274 /// \p SpillsToIns.
1275 void HoistSpillHelper::runHoistSpills(
1276  LiveInterval &OrigLI, VNInfo &OrigVNI,
1278  SmallVectorImpl<MachineInstr *> &SpillsToRm,
1280  // Visit order of dominator tree nodes.
1282  // SpillsToKeep contains all the nodes where spills are to be inserted
1283  // during hoisting. If the spill to be inserted is an original spill
1284  // (not a hoisted one), the value of the map entry is 0. If the spill
1285  // is a hoisted spill, the value of the map entry is the VReg to be used
1286  // as the source of the spill.
1288  // Map from BB to the first spill inside of it.
1290 
1291  rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1292 
1293  MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
1294  getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1295  SpillBBToSpill);
1296 
1297  // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1298  // nodes set and the cost of all the spills inside those nodes.
1299  // The nodes set are the locations where spills are to be inserted
1300  // in the subtree of current node.
1301  using NodesCostPair =
1302  std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
1304 
1305  // Iterate Orders set in reverse order, which will be a bottom-up order
1306  // in the dominator tree. Once we visit a dom tree node, we know its
1307  // children have already been visited and the spill locations in the
1308  // subtrees of all the children have been determined.
1310  for (; RIt != Orders.rend(); RIt++) {
1311  MachineBasicBlock *Block = (*RIt)->getBlock();
1312 
1313  // If Block contains an original spill, simply continue.
1314  if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
1315  SpillsInSubTreeMap[*RIt].first.insert(*RIt);
1316  // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
1317  SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1318  continue;
1319  }
1320 
1321  // Collect spills in subtree of current node (*RIt) to
1322  // SpillsInSubTreeMap[*RIt].first.
1323  const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren();
1324  unsigned NumChildren = Children.size();
1325  for (unsigned i = 0; i != NumChildren; ++i) {
1326  MachineDomTreeNode *Child = Children[i];
1327  if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
1328  continue;
1329  // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
1330  // should be placed before getting the begin and end iterators of
1331  // SpillsInSubTreeMap[Child].first, or else the iterators may be
1332  // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1333  // and the map grows and then the original buckets in the map are moved.
1334  SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1335  SpillsInSubTreeMap[*RIt].first;
1336  BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1337  SubTreeCost += SpillsInSubTreeMap[Child].second;
1338  auto BI = SpillsInSubTreeMap[Child].first.begin();
1339  auto EI = SpillsInSubTreeMap[Child].first.end();
1340  SpillsInSubTree.insert(BI, EI);
1341  SpillsInSubTreeMap.erase(Child);
1342  }
1343 
1344  SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1345  SpillsInSubTreeMap[*RIt].first;
1346  BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1347  // No spills in subtree, simply continue.
1348  if (SpillsInSubTree.empty())
1349  continue;
1350 
1351  // Check whether Block is a possible candidate to insert spill.
1352  unsigned LiveReg = 0;
1353  if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1354  continue;
1355 
1356  // If there are multiple spills that could be merged, bias a little
1357  // to hoist the spill.
1358  BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
1359  ? BranchProbability(9, 10)
1360  : BranchProbability(1, 1);
1361  if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1362  // Hoist: Move spills to current Block.
1363  for (const auto SpillBB : SpillsInSubTree) {
1364  // When SpillBB is a BB contains original spill, insert the spill
1365  // to SpillsToRm.
1366  if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
1367  !SpillsToKeep[SpillBB]) {
1368  MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1369  SpillsToRm.push_back(SpillToRm);
1370  }
1371  // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1372  SpillsToKeep.erase(SpillBB);
1373  }
1374  // Current Block is the BB containing the new hoisted spill. Add it to
1375  // SpillsToKeep. LiveReg is the source of the new spill.
1376  SpillsToKeep[*RIt] = LiveReg;
1377  DEBUG({
1378  dbgs() << "spills in BB: ";
1379  for (const auto Rspill : SpillsInSubTree)
1380  dbgs() << Rspill->getBlock()->getNumber() << " ";
1381  dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()
1382  << "\n";
1383  });
1384  SpillsInSubTree.clear();
1385  SpillsInSubTree.insert(*RIt);
1386  SubTreeCost = MBFI.getBlockFreq(Block);
1387  }
1388  }
1389  // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1390  // save them to SpillsToIns.
1391  for (const auto Ent : SpillsToKeep) {
1392  if (Ent.second)
1393  SpillsToIns[Ent.first->getBlock()] = Ent.second;
1394  }
1395 }
1396 
1397 /// For spills with equal values, remove redundant spills and hoist those left
1398 /// to less hot spots.
1399 ///
1400 /// Spills with equal values will be collected into the same set in
1401 /// MergeableSpills when spill is inserted. These equal spills are originated
1402 /// from the same defining instruction and are dominated by the instruction.
1403 /// Before hoisting all the equal spills, redundant spills inside in the same
1404 /// BB are first marked to be deleted. Then starting from the spills left, walk
1405 /// up on the dominator tree towards the Root node where the define instruction
1406 /// is located, mark the dominated spills to be deleted along the way and
1407 /// collect the BB nodes on the path from non-dominated spills to the define
1408 /// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1409 /// where we are considering to hoist the spills. We iterate the WorkSet in
1410 /// bottom-up order, and for each node, we will decide whether to hoist spills
1411 /// inside its subtree to that node. In this way, we can get benefit locally
1412 /// even if hoisting all the equal spills to one cold place is impossible.
1413 void HoistSpillHelper::hoistAllSpills() {
1414  SmallVector<unsigned, 4> NewVRegs;
1415  LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1416 
1417  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
1418  unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
1419  unsigned Original = VRM.getPreSplitReg(Reg);
1420  if (!MRI.def_empty(Reg))
1421  Virt2SiblingsMap[Original].insert(Reg);
1422  }
1423 
1424  // Each entry in MergeableSpills contains a spill set with equal values.
1425  for (auto &Ent : MergeableSpills) {
1426  int Slot = Ent.first.first;
1427  LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
1428  VNInfo *OrigVNI = Ent.first.second;
1429  SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1430  if (Ent.second.empty())
1431  continue;
1432 
1433  DEBUG({
1434  dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
1435  << "Equal spills in BB: ";
1436  for (const auto spill : EqValSpills)
1437  dbgs() << spill->getParent()->getNumber() << " ";
1438  dbgs() << "\n";
1439  });
1440 
1441  // SpillsToRm is the spill set to be removed from EqValSpills.
1443  // SpillsToIns is the spill set to be newly inserted after hoisting.
1445 
1446  runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1447 
1448  DEBUG({
1449  dbgs() << "Finally inserted spills in BB: ";
1450  for (const auto Ispill : SpillsToIns)
1451  dbgs() << Ispill.first->getNumber() << " ";
1452  dbgs() << "\nFinally removed spills in BB: ";
1453  for (const auto Rspill : SpillsToRm)
1454  dbgs() << Rspill->getParent()->getNumber() << " ";
1455  dbgs() << "\n";
1456  });
1457 
1458  // Stack live range update.
1459  LiveInterval &StackIntvl = LSS.getInterval(Slot);
1460  if (!SpillsToIns.empty() || !SpillsToRm.empty())
1461  StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1462  StackIntvl.getValNumInfo(0));
1463 
1464  // Insert hoisted spills.
1465  for (auto const Insert : SpillsToIns) {
1466  MachineBasicBlock *BB = Insert.first;
1467  unsigned LiveReg = Insert.second;
1468  MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, *BB);
1469  TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot,
1470  MRI.getRegClass(LiveReg), &TRI);
1471  LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI);
1472  ++NumSpills;
1473  }
1474 
1475  // Remove redundant spills or change them to dead instructions.
1476  NumSpills -= SpillsToRm.size();
1477  for (auto const RMEnt : SpillsToRm) {
1478  RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1479  for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1480  MachineOperand &MO = RMEnt->getOperand(i - 1);
1481  if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1482  RMEnt->RemoveOperand(i - 1);
1483  }
1484  }
1485  Edit.eliminateDeadDefs(SpillsToRm, None, AA);
1486  }
1487 }
1488 
1489 /// For VirtReg clone, the \p New register should have the same physreg or
1490 /// stackslot as the \p old register.
1491 void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
1492  if (VRM.hasPhys(Old))
1493  VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1494  else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1495  VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1496  else
1497  llvm_unreachable("VReg should be assigned either physreg or stackslot");
1498 }
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
Safe Stack instrumentation pass
Definition: SafeStack.cpp:846
const unsigned reg
Definition: LiveInterval.h:667
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:242
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo)
MergeValueInAsValue - Merge all of the segments of a specific val# in RHS into this live range as the...
bool addRegisterDead(unsigned Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Store the specified register of the given register class to the specified stack frame index...
VNInfoList::iterator vni_iterator
Definition: LiveInterval.h:217
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:268
vni_iterator vni_begin()
Definition: LiveInterval.h:220
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
MIBundleOperands - Iterate over all operands in a bundle of machine instructions. ...
unsigned getReg() const
getReg - Returns the register number.
void setIsUndef(bool Val=true)
void eliminateDeadDefs(SmallVectorImpl< MachineInstr *> &Dead, ArrayRef< unsigned > RegsBeingSpilled=None, AliasAnalysis *AA=nullptr)
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned getSubReg() const
Spiller interface.
Definition: Spiller.h:24
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
STATISTIC(NumFunctions, "Total number of functions")
void setIsDead(bool Val=true)
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
Determines the latest safe point in a block in which we can insert a split, spill or other instructio...
Definition: SplitKit.h:49
Callback methods for LiveRangeEdit owners.
Definition: LiveRangeEdit.h:49
VirtRegInfo analyzeVirtReg(unsigned Reg, SmallVectorImpl< std::pair< MachineInstr *, unsigned > > *Ops=nullptr)
analyzeVirtReg - Analyze how the current instruction or bundle uses a virtual register.
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
MachineInstrSpan provides an interface to get an iteration range containing the instruction it was in...
bool isEarlyClobber() const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
Hexagon Hardware Loops
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI) const override
Load the specified register of the given register class from the specified stack frame index...
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
Result of a LiveRange query.
Definition: LiveInterval.h:90
Reg
All possible values of the reg field in the ModR/M byte.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
PhysRegInfo analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI)
analyzePhysReg - Analyze how the current instruction or bundle uses a physical register.
MachineBasicBlock::iterator end()
defusechain_iterator - This class provides iterator support for machine operands in the function that...
void RemoveOperand(unsigned i)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
bool isValid() const
isValid - Returns true until all the operands have been visited.
bool isFullCopy() const
Definition: MachineInstr.h:861
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:255
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const std::vector< DomTreeNodeBase * > & getChildren() const
unsigned getReg() const
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
bool isKill() const
Return true if the live-in value is killed by this instruction.
Definition: LiveInterval.h:112
bool allDefsAreDead() const
Return true if all the defs of this instruction are dead.
unsigned getKillRegState(bool B)
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:529
TargetInstrInfo - Interface to description of machine instruction set.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:639
#define P(N)
static LLVM_DUMP_METHOD void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E, LiveIntervals const &LIS, const char *const header, unsigned VReg=0)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
bool isBundled() const
Return true if this instruction part of a bundle.
Definition: MachineInstr.h:241
MachineInstrBuilder & UseMI
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
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
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
iterator_range< pred_iterator > predecessors()
bool isCopy() const
Definition: MachineInstr.h:857
bool isImplicitDef() const
Definition: MachineInstr.h:831
Information about a live register.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setIsKill(bool Val=true)
virtual ~Spiller()=0
static bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful the be able to store a non-negative frame index in a variable th...
size_type size() const
Definition: SmallPtrSet.h:93
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
Basic Register Allocator
LiveInterval & getParent() const
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
static bool isFullUndefDef(const MachineInstr &Def)
Check if Def fully defines a VReg with an undefined value.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
MachineInstrBuilder MachineInstrBuilder & DefMI
static cl::opt< bool > DisableHoisting("disable-spill-hoist", cl::Hidden, cl::desc("Disable inline spill hoisting"))
unsigned isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx...
Definition: LiveInterval.h:417
unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
TargetInstrInfo overrides.
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.
Spiller * createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
unsigned getNumValNums() const
Definition: LiveInterval.h:301
Representation of each machine instruction.
Definition: MachineInstr.h:59
iterator begin() const
Definition: SmallPtrSet.h:397
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
Definition: LiveInterval.h:240
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
bool canFoldAsLoad(QueryType Type=IgnoreBundle) const
Return true for instructions that can be folded as memory operands in other instructions.
Definition: MachineInstr.h:572
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg)
isFullCopyOf - If MI is a COPY to or from Reg, return the other register, otherwise return 0...
iterator end() const
Definition: SmallPtrSet.h:402
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Remat - Information needed to rematerialize at a specific location.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:767
#define DEBUG(X)
Definition: Debug.h:118
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
IRTranslator LLVM IR MI
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
vni_iterator vni_end()
Definition: LiveInterval.h:221
bool isImplicit() const
MachineBasicBlock::iterator begin()
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:821