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