1 //===-- LiveRangeEdit.cpp - Basic tools for editing a register live range -===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // The LiveRangeEdit class represents changes done to a virtual register when it
11 // is spilled or split.
12 //===----------------------------------------------------------------------===//
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"
26 #define DEBUG_TYPE "regalloc"
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");
32 void LiveRangeEdit::Delegate::anchor() { }
34 LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(unsigned OldReg) {
35 unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
37 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
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);
50 unsigned LiveRangeEdit::createFrom(unsigned OldReg) {
51 unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
53 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
58 bool LiveRangeEdit::checkRematerializable(VNInfo *VNI,
59 const MachineInstr *DefMI,
61 assert(DefMI && "Missing instruction");
62 ScannedRemattable = true;
63 if (!TII.isTriviallyReMaterializable(*DefMI, aa))
65 Remattable.insert(VNI);
69 void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
70 for (VNInfo *VNI : getParent().valnos) {
73 unsigned Original = VRM->getOriginal(getReg());
74 LiveInterval &OrigLI = LIS.getInterval(Original);
75 VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
78 MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
81 checkRematerializable(OrigVNI, DefMI, aa);
83 ScannedRemattable = true;
86 bool LiveRangeEdit::anyRematerializable(AliasAnalysis *aa) {
87 if (!ScannedRemattable)
89 return !Remattable.empty();
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,
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())
104 // We can't remat physreg uses, unless it is a constant.
105 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
106 if (MRI.isConstantPhysReg(MO.getReg()))
111 LiveInterval &li = LIS.getInterval(MO.getReg());
112 const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
116 // Don't allow rematerialization immediately after the original def.
117 // It would be incorrect if OrigMI redefines the register.
119 if (SlotIndex::isSameInstr(OrigIdx, UseIdx))
122 if (OVNI != li.getVNInfoAt(UseIdx))
128 bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI,
129 SlotIndex UseIdx, bool cheapAsAMove) {
130 assert(ScannedRemattable && "Call anyRematerializable first");
132 // Use scanRemattable info.
133 if (!Remattable.count(OrigVNI))
136 // No defining instruction provided.
138 assert(RM.OrigMI && "No defining instruction for remattable value");
139 DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
141 // If only cheap remats were requested, bail out early.
142 if (cheapAsAMove && !TII.isAsCheapAsAMove(*RM.OrigMI))
145 // Verify that all used registers are available with the same values.
146 if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx))
152 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
153 MachineBasicBlock::iterator MI,
156 const TargetRegisterInfo &tri,
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
163 (*--MI).getOperand(0).setIsDead(false);
164 Rematted.insert(RM.ParentVNI);
165 return LIS.getSlotIndexes()->insertMachineInstrInMaps(*MI, Late).getRegSlot();
168 void LiveRangeEdit::eraseVirtReg(unsigned Reg) {
169 if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))
170 LIS.removeInterval(Reg);
173 bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
174 SmallVectorImpl<MachineInstr*> &Dead) {
175 MachineInstr *DefMI = nullptr, *UseMI = nullptr;
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();
181 if (DefMI && DefMI != MI)
183 if (!MI->canFoldAsLoad())
186 } else if (!MO.isUndef()) {
187 if (UseMI && UseMI != MI)
189 // FIXME: Targets don't know how to fold subreg uses.
195 if (!DefMI || !UseMI)
198 // Since we're moving the DefMI load, make sure we're not extending any live
200 if (!allUsesAvailableAt(DefMI, LIS.getInstructionIndex(*DefMI),
201 LIS.getInstructionIndex(*UseMI)))
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))
210 DEBUG(dbgs() << "Try to fold single def: " << *DefMI
211 << " into single use: " << *UseMI);
213 SmallVector<unsigned, 8> Ops;
214 if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second)
217 MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);
220 DEBUG(dbgs() << " folded: " << *FoldMI);
221 LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);
222 UseMI->eraseFromParent();
223 DefMI->addRegisterDead(LI->reg, nullptr);
224 Dead.push_back(DefMI);
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())
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).any() && S.Query(Idx).isKill())
245 /// Find all live intervals that need to shrink, then remove the instruction.
246 void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
248 assert(MI->allDefsAreDead() && "Def isn't really dead");
249 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
251 // Never delete a bundled instruction.
252 if (MI->isBundled()) {
255 // Never delete inline asm.
256 if (MI->isInlineAsm()) {
257 DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
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);
268 DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
270 // Collect virtual registers to be erased after MI is gone.
271 SmallVector<unsigned, 8> RegsToErase;
272 bool ReadsPhysRegs = false;
273 bool isOrigDef = false;
275 // Only optimize rematerialize case when the instruction has one def, since
276 // otherwise we could leave some dead defs in the code. This case is
278 if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
279 MI->getDesc().getNumDefs() == 1) {
280 Dest = MI->getOperand(0).getReg();
281 unsigned Original = VRM->getOriginal(Dest);
282 LiveInterval &OrigLI = LIS.getInterval(Original);
283 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
284 // The original live-range may have been shrunk to
285 // an empty live-range. It happens when it is dead, but
286 // we still keep it around to be able to rematerialize
287 // other values that depend on it.
289 isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
292 // Check for live intervals that may shrink
293 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
294 MOE = MI->operands_end(); MOI != MOE; ++MOI) {
297 unsigned Reg = MOI->getReg();
298 if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
299 // Check if MI reads any unreserved physregs.
300 if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
301 ReadsPhysRegs = true;
302 else if (MOI->isDef())
303 LIS.removePhysRegDefAt(Reg, Idx);
306 LiveInterval &LI = LIS.getInterval(Reg);
308 // Shrink read registers, unless it is likely to be expensive and
309 // unlikely to change anything. We typically don't want to shrink the
310 // PIC base register that has lots of uses everywhere.
311 // Always shrink COPY uses that probably come from live range splitting.
312 if ((MI->readsVirtualRegister(Reg) && (MI->isCopy() || MOI->isDef())) ||
313 (MOI->readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, *MOI))))
314 ToShrink.insert(&LI);
316 // Remove defined value.
318 if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)
319 TheDelegate->LRE_WillShrinkVirtReg(LI.reg);
320 LIS.removeVRegDefAt(LI, Idx);
322 RegsToErase.push_back(Reg);
326 // Currently, we don't support DCE of physreg live ranges. If MI reads
327 // any unreserved physregs, don't erase the instruction, but turn it into
328 // a KILL instead. This way, the physreg live ranges don't end up
330 // FIXME: It would be better to have something like shrinkToUses() for
331 // physregs. That could potentially enable more DCE and it would free up
332 // the physreg. It would not happen often, though.
334 MI->setDesc(TII.get(TargetOpcode::KILL));
335 // Remove all operands that aren't physregs.
336 for (unsigned i = MI->getNumOperands(); i; --i) {
337 const MachineOperand &MO = MI->getOperand(i-1);
338 if (MO.isReg() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
340 MI->RemoveOperand(i-1);
342 DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
344 // If the dest of MI is an original reg and MI is reMaterializable,
345 // don't delete the inst. Replace the dest with a new reg, and keep
346 // the inst for remat of other siblings. The inst is saved in
347 // LiveRangeEdit::DeadRemats and will be deleted after all the
348 // allocations of the func are done.
349 if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
350 LiveInterval &NewLI = createEmptyIntervalFrom(Dest);
351 NewLI.removeEmptySubRanges();
352 VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
353 NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
356 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
357 MI->substituteRegister(Dest, NewLI.reg, 0, TRI);
358 MI->getOperand(0).setIsDead(true);
361 TheDelegate->LRE_WillEraseInstruction(MI);
362 LIS.RemoveMachineInstrFromMaps(*MI);
363 MI->eraseFromParent();
368 // Erase any virtregs that are now empty and unused. There may be <undef>
369 // uses around. Keep the empty live range in that case.
370 for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
371 unsigned Reg = RegsToErase[i];
372 if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
373 ToShrink.remove(&LIS.getInterval(Reg));
379 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
380 ArrayRef<unsigned> RegsBeingSpilled,
382 ToShrinkSet ToShrink;
385 // Erase all dead defs.
386 while (!Dead.empty())
387 eliminateDeadDef(Dead.pop_back_val(), ToShrink, AA);
389 if (ToShrink.empty())
392 // Shrink just one live interval. Then delete new dead defs.
393 LiveInterval *LI = ToShrink.back();
395 if (foldAsLoad(LI, Dead))
397 unsigned VReg = LI->reg;
399 TheDelegate->LRE_WillShrinkVirtReg(VReg);
400 if (!LIS.shrinkToUses(LI, &Dead))
403 // Don't create new intervals for a register being spilled.
404 // The new intervals would have to be spilled anyway so its not worth it.
405 // Also they currently aren't spilled so creating them and not spilling
406 // them results in incorrect code.
407 bool BeingSpilled = false;
408 for (unsigned i = 0, e = RegsBeingSpilled.size(); i != e; ++i) {
409 if (VReg == RegsBeingSpilled[i]) {
415 if (BeingSpilled) continue;
417 // LI may have been separated, create new intervals.
418 LI->RenumberValues();
419 SmallVector<LiveInterval*, 8> SplitLIs;
420 LIS.splitSeparateComponents(*LI, SplitLIs);
421 if (!SplitLIs.empty())
424 unsigned Original = VRM ? VRM->getOriginal(VReg) : 0;
425 for (const LiveInterval *SplitLI : SplitLIs) {
426 // If LI is an original interval that hasn't been split yet, make the new
427 // intervals their own originals instead of referring to LI. The original
428 // interval must contain all the split products, and LI doesn't.
429 if (Original != VReg && Original != 0)
430 VRM->setIsSplitFromReg(SplitLI->reg, Original);
432 TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg, VReg);
437 // Keep track of new virtual registers created via
438 // MachineRegisterInfo::createVirtualRegister.
440 LiveRangeEdit::MRI_NoteNewVirtualRegister(unsigned VReg)
445 if (Parent && !Parent->isSpillable())
446 LIS.getInterval(VReg).markNotSpillable();
448 NewRegs.push_back(VReg);
452 LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
453 const MachineLoopInfo &Loops,
454 const MachineBlockFrequencyInfo &MBFI) {
455 VirtRegAuxInfo VRAI(MF, LIS, VRM, Loops, MBFI);
456 for (unsigned I = 0, Size = size(); I < Size; ++I) {
457 LiveInterval &LI = LIS.getInterval(get(I));
458 if (MRI.recomputeRegClass(LI.reg))
460 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
461 dbgs() << "Inflated " << PrintReg(LI.reg) << " to "
462 << TRI->getRegClassName(MRI.getRegClass(LI.reg)) << '\n';
464 VRAI.calculateSpillWeightAndHint(LI);