1//===-- LiveRangeEdit.cpp - Basic tools for editing a register live range -===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The LiveRangeEdit class represents changes done to a virtual register when it
10// is spilled or split.
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/LiveRangeEdit.h"
14#include "llvm/ADT/Statistic.h"
15#include "llvm/Analysis/AliasAnalysis.h"
16#include "llvm/CodeGen/CalcSpillWeights.h"
17#include "llvm/CodeGen/LiveIntervals.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/TargetInstrInfo.h"
20#include "llvm/CodeGen/VirtRegMap.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "regalloc"
27
28STATISTIC(NumDCEDeleted,     "Number of instructions deleted by DCE");
29STATISTIC(NumDCEFoldedLoads, "Number of single use loads folded after DCE");
30STATISTIC(NumFracRanges,     "Number of live ranges fractured by DCE");
31
32void LiveRangeEdit::Delegate::anchor() { }
33
34LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(Register OldReg,
35                                                     bool createSubRanges) {
36  Register VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
37  if (VRM)
38    VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
39
40  LiveInterval &LI = LIS.createEmptyInterval(VReg);
41  if (Parent && !Parent->isSpillable())
42    LI.markNotSpillable();
43  if (createSubRanges) {
44    // Create empty subranges if the OldReg's interval has them. Do not create
45    // the main range here---it will be constructed later after the subranges
46    // have been finalized.
47    LiveInterval &OldLI = LIS.getInterval(OldReg);
48    VNInfo::Allocator &Alloc = LIS.getVNInfoAllocator();
49    for (LiveInterval::SubRange &S : OldLI.subranges())
50      LI.createSubRange(Alloc, S.LaneMask);
51  }
52  return LI;
53}
54
55Register LiveRangeEdit::createFrom(Register OldReg) {
56  Register VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
57  if (VRM) {
58    VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
59  }
60  // FIXME: Getting the interval here actually computes it.
61  // In theory, this may not be what we want, but in practice
62  // the createEmptyIntervalFrom API is used when this is not
63  // the case. Generally speaking we just want to annotate the
64  // LiveInterval when it gets created but we cannot do that at
65  // the moment.
66  if (Parent && !Parent->isSpillable())
67    LIS.getInterval(VReg).markNotSpillable();
68  return VReg;
69}
70
71bool LiveRangeEdit::checkRematerializable(VNInfo *VNI,
72                                          const MachineInstr *DefMI,
73                                          AAResults *aa) {
74  assert(DefMI && "Missing instruction");
75  ScannedRemattable = true;
76  if (!TII.isTriviallyReMaterializable(*DefMI, aa))
77    return false;
78  Remattable.insert(VNI);
79  return true;
80}
81
82void LiveRangeEdit::scanRemattable(AAResults *aa) {
83  for (VNInfo *VNI : getParent().valnos) {
84    if (VNI->isUnused())
85      continue;
86    unsigned Original = VRM->getOriginal(getReg());
87    LiveInterval &OrigLI = LIS.getInterval(Original);
88    VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
89    if (!OrigVNI)
90      continue;
91    MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
92    if (!DefMI)
93      continue;
94    checkRematerializable(OrigVNI, DefMI, aa);
95  }
96  ScannedRemattable = true;
97}
98
99bool LiveRangeEdit::anyRematerializable(AAResults *aa) {
100  if (!ScannedRemattable)
101    scanRemattable(aa);
102  return !Remattable.empty();
103}
104
105/// allUsesAvailableAt - Return true if all registers used by OrigMI at
106/// OrigIdx are also available with the same value at UseIdx.
107bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
108                                       SlotIndex OrigIdx,
109                                       SlotIndex UseIdx) const {
110  OrigIdx = OrigIdx.getRegSlot(true);
111  UseIdx = UseIdx.getRegSlot(true);
112  for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
113    const MachineOperand &MO = OrigMI->getOperand(i);
114    if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
115      continue;
116
117    // We can't remat physreg uses, unless it is a constant.
118    if (Register::isPhysicalRegister(MO.getReg())) {
119      if (MRI.isConstantPhysReg(MO.getReg()))
120        continue;
121      return false;
122    }
123
124    LiveInterval &li = LIS.getInterval(MO.getReg());
125    const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
126    if (!OVNI)
127      continue;
128
129    // Don't allow rematerialization immediately after the original def.
130    // It would be incorrect if OrigMI redefines the register.
131    // See PR14098.
132    if (SlotIndex::isSameInstr(OrigIdx, UseIdx))
133      return false;
134
135    if (OVNI != li.getVNInfoAt(UseIdx))
136      return false;
137  }
138  return true;
139}
140
141bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI,
142                                       SlotIndex UseIdx, bool cheapAsAMove) {
143  assert(ScannedRemattable && "Call anyRematerializable first");
144
145  // Use scanRemattable info.
146  if (!Remattable.count(OrigVNI))
147    return false;
148
149  // No defining instruction provided.
150  SlotIndex DefIdx;
151  assert(RM.OrigMI && "No defining instruction for remattable value");
152  DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
153
154  // If only cheap remats were requested, bail out early.
155  if (cheapAsAMove && !TII.isAsCheapAsAMove(*RM.OrigMI))
156    return false;
157
158  // Verify that all used registers are available with the same values.
159  if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx))
160    return false;
161
162  return true;
163}
164
165SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
166                                         MachineBasicBlock::iterator MI,
167                                         unsigned DestReg,
168                                         const Remat &RM,
169                                         const TargetRegisterInfo &tri,
170                                         bool Late) {
171  assert(RM.OrigMI && "Invalid remat");
172  TII.reMaterialize(MBB, MI, DestReg, 0, *RM.OrigMI, tri);
173  // DestReg of the cloned instruction cannot be Dead. Set isDead of DestReg
174  // to false anyway in case the isDead flag of RM.OrigMI's dest register
175  // is true.
176  (*--MI).getOperand(0).setIsDead(false);
177  Rematted.insert(RM.ParentVNI);
178  return LIS.getSlotIndexes()->insertMachineInstrInMaps(*MI, Late).getRegSlot();
179}
180
181void LiveRangeEdit::eraseVirtReg(Register Reg) {
182  if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))
183    LIS.removeInterval(Reg);
184}
185
186bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
187                               SmallVectorImpl<MachineInstr*> &Dead) {
188  MachineInstr *DefMI = nullptr, *UseMI = nullptr;
189
190  // Check that there is a single def and a single use.
191  for (MachineOperand &MO : MRI.reg_nodbg_operands(LI->reg)) {
192    MachineInstr *MI = MO.getParent();
193    if (MO.isDef()) {
194      if (DefMI && DefMI != MI)
195        return false;
196      if (!MI->canFoldAsLoad())
197        return false;
198      DefMI = MI;
199    } else if (!MO.isUndef()) {
200      if (UseMI && UseMI != MI)
201        return false;
202      // FIXME: Targets don't know how to fold subreg uses.
203      if (MO.getSubReg())
204        return false;
205      UseMI = MI;
206    }
207  }
208  if (!DefMI || !UseMI)
209    return false;
210
211  // Since we're moving the DefMI load, make sure we're not extending any live
212  // ranges.
213  if (!allUsesAvailableAt(DefMI, LIS.getInstructionIndex(*DefMI),
214                          LIS.getInstructionIndex(*UseMI)))
215    return false;
216
217  // We also need to make sure it is safe to move the load.
218  // Assume there are stores between DefMI and UseMI.
219  bool SawStore = true;
220  if (!DefMI->isSafeToMove(nullptr, SawStore))
221    return false;
222
223  LLVM_DEBUG(dbgs() << "Try to fold single def: " << *DefMI
224                    << "       into single use: " << *UseMI);
225
226  SmallVector<unsigned, 8> Ops;
227  if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second)
228    return false;
229
230  MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);
231  if (!FoldMI)
232    return false;
233  LLVM_DEBUG(dbgs() << "                folded: " << *FoldMI);
234  LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);
235  // Update the call site info.
236  if (UseMI->shouldUpdateCallSiteInfo())
237    UseMI->getMF()->moveCallSiteInfo(UseMI, FoldMI);
238  UseMI->eraseFromParent();
239  DefMI->addRegisterDead(LI->reg, nullptr);
240  Dead.push_back(DefMI);
241  ++NumDCEFoldedLoads;
242  return true;
243}
244
245bool LiveRangeEdit::useIsKill(const LiveInterval &LI,
246                              const MachineOperand &MO) const {
247  const MachineInstr &MI = *MO.getParent();
248  SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
249  if (LI.Query(Idx).isKill())
250    return true;
251  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
252  unsigned SubReg = MO.getSubReg();
253  LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
254  for (const LiveInterval::SubRange &S : LI.subranges()) {
255    if ((S.LaneMask & LaneMask).any() && S.Query(Idx).isKill())
256      return true;
257  }
258  return false;
259}
260
261/// Find all live intervals that need to shrink, then remove the instruction.
262void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
263                                     AAResults *AA) {
264  assert(MI->allDefsAreDead() && "Def isn't really dead");
265  SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
266
267  // Never delete a bundled instruction.
268  if (MI->isBundled()) {
269    return;
270  }
271  // Never delete inline asm.
272  if (MI->isInlineAsm()) {
273    LLVM_DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
274    return;
275  }
276
277  // Use the same criteria as DeadMachineInstructionElim.
278  bool SawStore = false;
279  if (!MI->isSafeToMove(nullptr, SawStore)) {
280    LLVM_DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
281    return;
282  }
283
284  LLVM_DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
285
286  // Collect virtual registers to be erased after MI is gone.
287  SmallVector<unsigned, 8> RegsToErase;
288  bool ReadsPhysRegs = false;
289  bool isOrigDef = false;
290  unsigned Dest;
291  // Only optimize rematerialize case when the instruction has one def, since
292  // otherwise we could leave some dead defs in the code.  This case is
293  // extremely rare.
294  if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
295      MI->getDesc().getNumDefs() == 1) {
296    Dest = MI->getOperand(0).getReg();
297    unsigned Original = VRM->getOriginal(Dest);
298    LiveInterval &OrigLI = LIS.getInterval(Original);
299    VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
300    // The original live-range may have been shrunk to
301    // an empty live-range. It happens when it is dead, but
302    // we still keep it around to be able to rematerialize
303    // other values that depend on it.
304    if (OrigVNI)
305      isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
306  }
307
308  // Check for live intervals that may shrink
309  for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
310         MOE = MI->operands_end(); MOI != MOE; ++MOI) {
311    if (!MOI->isReg())
312      continue;
313    Register Reg = MOI->getReg();
314    if (!Register::isVirtualRegister(Reg)) {
315      // Check if MI reads any unreserved physregs.
316      if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
317        ReadsPhysRegs = true;
318      else if (MOI->isDef())
319        LIS.removePhysRegDefAt(Reg, Idx);
320      continue;
321    }
322    LiveInterval &LI = LIS.getInterval(Reg);
323
324    // Shrink read registers, unless it is likely to be expensive and
325    // unlikely to change anything. We typically don't want to shrink the
326    // PIC base register that has lots of uses everywhere.
327    // Always shrink COPY uses that probably come from live range splitting.
328    if ((MI->readsVirtualRegister(Reg) && (MI->isCopy() || MOI->isDef())) ||
329        (MOI->readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, *MOI))))
330      ToShrink.insert(&LI);
331
332    // Remove defined value.
333    if (MOI->isDef()) {
334      if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)
335        TheDelegate->LRE_WillShrinkVirtReg(LI.reg);
336      LIS.removeVRegDefAt(LI, Idx);
337      if (LI.empty())
338        RegsToErase.push_back(Reg);
339    }
340  }
341
342  // Currently, we don't support DCE of physreg live ranges. If MI reads
343  // any unreserved physregs, don't erase the instruction, but turn it into
344  // a KILL instead. This way, the physreg live ranges don't end up
345  // dangling.
346  // FIXME: It would be better to have something like shrinkToUses() for
347  // physregs. That could potentially enable more DCE and it would free up
348  // the physreg. It would not happen often, though.
349  if (ReadsPhysRegs) {
350    MI->setDesc(TII.get(TargetOpcode::KILL));
351    // Remove all operands that aren't physregs.
352    for (unsigned i = MI->getNumOperands(); i; --i) {
353      const MachineOperand &MO = MI->getOperand(i-1);
354      if (MO.isReg() && Register::isPhysicalRegister(MO.getReg()))
355        continue;
356      MI->RemoveOperand(i-1);
357    }
358    LLVM_DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
359  } else {
360    // If the dest of MI is an original reg and MI is reMaterializable,
361    // don't delete the inst. Replace the dest with a new reg, and keep
362    // the inst for remat of other siblings. The inst is saved in
363    // LiveRangeEdit::DeadRemats and will be deleted after all the
364    // allocations of the func are done.
365    if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
366      LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);
367      VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
368      NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
369      pop_back();
370      DeadRemats->insert(MI);
371      const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
372      MI->substituteRegister(Dest, NewLI.reg, 0, TRI);
373      MI->getOperand(0).setIsDead(true);
374    } else {
375      if (TheDelegate)
376        TheDelegate->LRE_WillEraseInstruction(MI);
377      LIS.RemoveMachineInstrFromMaps(*MI);
378      MI->eraseFromParent();
379      ++NumDCEDeleted;
380    }
381  }
382
383  // Erase any virtregs that are now empty and unused. There may be <undef>
384  // uses around. Keep the empty live range in that case.
385  for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
386    Register Reg = RegsToErase[i];
387    if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
388      ToShrink.remove(&LIS.getInterval(Reg));
389      eraseVirtReg(Reg);
390    }
391  }
392}
393
394void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
395                                      ArrayRef<Register> RegsBeingSpilled,
396                                      AAResults *AA) {
397  ToShrinkSet ToShrink;
398
399  for (;;) {
400    // Erase all dead defs.
401    while (!Dead.empty())
402      eliminateDeadDef(Dead.pop_back_val(), ToShrink, AA);
403
404    if (ToShrink.empty())
405      break;
406
407    // Shrink just one live interval. Then delete new dead defs.
408    LiveInterval *LI = ToShrink.back();
409    ToShrink.pop_back();
410    if (foldAsLoad(LI, Dead))
411      continue;
412    unsigned VReg = LI->reg;
413    if (TheDelegate)
414      TheDelegate->LRE_WillShrinkVirtReg(VReg);
415    if (!LIS.shrinkToUses(LI, &Dead))
416      continue;
417
418    // Don't create new intervals for a register being spilled.
419    // The new intervals would have to be spilled anyway so its not worth it.
420    // Also they currently aren't spilled so creating them and not spilling
421    // them results in incorrect code.
422    bool BeingSpilled = false;
423    for (unsigned i = 0, e = RegsBeingSpilled.size(); i != e; ++i) {
424      if (VReg == RegsBeingSpilled[i]) {
425        BeingSpilled = true;
426        break;
427      }
428    }
429
430    if (BeingSpilled) continue;
431
432    // LI may have been separated, create new intervals.
433    LI->RenumberValues();
434    SmallVector<LiveInterval*, 8> SplitLIs;
435    LIS.splitSeparateComponents(*LI, SplitLIs);
436    if (!SplitLIs.empty())
437      ++NumFracRanges;
438
439    unsigned Original = VRM ? VRM->getOriginal(VReg) : 0;
440    for (const LiveInterval *SplitLI : SplitLIs) {
441      // If LI is an original interval that hasn't been split yet, make the new
442      // intervals their own originals instead of referring to LI. The original
443      // interval must contain all the split products, and LI doesn't.
444      if (Original != VReg && Original != 0)
445        VRM->setIsSplitFromReg(SplitLI->reg, Original);
446      if (TheDelegate)
447        TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg, VReg);
448    }
449  }
450}
451
452// Keep track of new virtual registers created via
453// MachineRegisterInfo::createVirtualRegister.
454void
455LiveRangeEdit::MRI_NoteNewVirtualRegister(Register VReg) {
456  if (VRM)
457    VRM->grow();
458
459  NewRegs.push_back(VReg);
460}
461
462void
463LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
464                                        const MachineLoopInfo &Loops,
465                                        const MachineBlockFrequencyInfo &MBFI) {
466  VirtRegAuxInfo VRAI(MF, LIS, VRM, Loops, MBFI);
467  for (unsigned I = 0, Size = size(); I < Size; ++I) {
468    LiveInterval &LI = LIS.getInterval(get(I));
469    if (MRI.recomputeRegClass(LI.reg))
470      LLVM_DEBUG({
471        const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
472        dbgs() << "Inflated " << printReg(LI.reg) << " to "
473               << TRI->getRegClassName(MRI.getRegClass(LI.reg)) << '\n';
474      });
475    VRAI.calculateSpillWeightAndHint(LI);
476  }
477}
478