Line data Source code
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/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 :
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 0 : void LiveRangeEdit::Delegate::anchor() { }
33 :
34 69607 : LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(unsigned OldReg,
35 : bool createSubRanges) {
36 139214 : unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
37 69607 : if (VRM)
38 : VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
39 :
40 69607 : LiveInterval &LI = LIS.createEmptyInterval(VReg);
41 69607 : if (Parent && !Parent->isSpillable())
42 : LI.markNotSpillable();
43 69607 : 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 61443 : LiveInterval &OldLI = LIS.getInterval(OldReg);
48 61443 : VNInfo::Allocator &Alloc = LIS.getVNInfoAllocator();
49 61871 : for (LiveInterval::SubRange &S : OldLI.subranges())
50 428 : LI.createSubRange(Alloc, S.LaneMask);
51 : }
52 69607 : return LI;
53 : }
54 :
55 38599 : unsigned LiveRangeEdit::createFrom(unsigned OldReg) {
56 77198 : unsigned VReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
57 38599 : 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 38599 : if (Parent && !Parent->isSpillable())
67 0 : LIS.getInterval(VReg).markNotSpillable();
68 38599 : return VReg;
69 : }
70 :
71 95685 : bool LiveRangeEdit::checkRematerializable(VNInfo *VNI,
72 : const MachineInstr *DefMI,
73 : AliasAnalysis *aa) {
74 : assert(DefMI && "Missing instruction");
75 95685 : ScannedRemattable = true;
76 95685 : if (!TII.isTriviallyReMaterializable(*DefMI, aa))
77 : return false;
78 41706 : Remattable.insert(VNI);
79 41706 : return true;
80 : }
81 :
82 74544 : void LiveRangeEdit::scanRemattable(AliasAnalysis *aa) {
83 179889 : for (VNInfo *VNI : getParent().valnos) {
84 105345 : if (VNI->isUnused())
85 : continue;
86 105291 : unsigned Original = VRM->getOriginal(getReg());
87 105291 : LiveInterval &OrigLI = LIS.getInterval(Original);
88 105291 : VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
89 105291 : if (!OrigVNI)
90 0 : continue;
91 : MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
92 105291 : if (!DefMI)
93 : continue;
94 95685 : checkRematerializable(OrigVNI, DefMI, aa);
95 : }
96 74544 : ScannedRemattable = true;
97 74544 : }
98 :
99 74544 : bool LiveRangeEdit::anyRematerializable(AliasAnalysis *aa) {
100 74544 : if (!ScannedRemattable)
101 74544 : scanRemattable(aa);
102 74544 : 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.
107 57145 : bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
108 : SlotIndex OrigIdx,
109 : SlotIndex UseIdx) const {
110 : OrigIdx = OrigIdx.getRegSlot(true);
111 : UseIdx = UseIdx.getRegSlot(true);
112 237519 : for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
113 180384 : const MachineOperand &MO = OrigMI->getOperand(i);
114 180384 : if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
115 : continue;
116 :
117 : // We can't remat physreg uses, unless it is a constant.
118 7706 : if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
119 7670 : if (MRI.isConstantPhysReg(MO.getReg()))
120 : continue;
121 : return false;
122 : }
123 :
124 36 : LiveInterval &li = LIS.getInterval(MO.getReg());
125 36 : const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
126 36 : if (!OVNI)
127 0 : 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 36 : if (SlotIndex::isSameInstr(OrigIdx, UseIdx))
133 : return false;
134 :
135 35 : if (OVNI != li.getVNInfoAt(UseIdx))
136 : return false;
137 : }
138 : return true;
139 : }
140 :
141 93748 : bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI,
142 : SlotIndex UseIdx, bool cheapAsAMove) {
143 : assert(ScannedRemattable && "Call anyRematerializable first");
144 :
145 : // Use scanRemattable info.
146 93748 : 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 70746 : DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
153 :
154 : // If only cheap remats were requested, bail out early.
155 70746 : if (cheapAsAMove && !TII.isAsCheapAsAMove(*RM.OrigMI))
156 : return false;
157 :
158 : // Verify that all used registers are available with the same values.
159 56731 : if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx))
160 6 : return false;
161 :
162 : return true;
163 : }
164 :
165 54094 : SlotIndex 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 54094 : 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 54094 : (*--MI).getOperand(0).setIsDead(false);
177 54094 : Rematted.insert(RM.ParentVNI);
178 108188 : return LIS.getSlotIndexes()->insertMachineInstrInMaps(*MI, Late).getRegSlot();
179 : }
180 :
181 85386 : void LiveRangeEdit::eraseVirtReg(unsigned Reg) {
182 85386 : if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))
183 30981 : LIS.removeInterval(Reg);
184 85386 : }
185 :
186 8660 : bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
187 : SmallVectorImpl<MachineInstr*> &Dead) {
188 8660 : MachineInstr *DefMI = nullptr, *UseMI = nullptr;
189 :
190 : // Check that there is a single def and a single use.
191 21063 : for (MachineOperand &MO : MRI.reg_nodbg_operands(LI->reg)) {
192 11794 : MachineInstr *MI = MO.getParent();
193 11794 : if (MO.isDef()) {
194 9267 : if (DefMI && DefMI != MI)
195 : return false;
196 8522 : if (!MI->canFoldAsLoad())
197 : return false;
198 2272 : DefMI = MI;
199 2527 : } else if (!MO.isUndef()) {
200 2527 : if (UseMI && UseMI != MI)
201 : return false;
202 : // FIXME: Targets don't know how to fold subreg uses.
203 1488 : if (MO.getSubReg())
204 : return false;
205 : UseMI = MI;
206 : }
207 : }
208 609 : 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 414 : if (!allUsesAvailableAt(DefMI, LIS.getInstructionIndex(*DefMI),
214 414 : 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 410 : bool SawStore = true;
220 410 : 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 365 : if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second)
228 : return false;
229 :
230 730 : MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);
231 365 : if (!FoldMI)
232 : return false;
233 : LLVM_DEBUG(dbgs() << " folded: " << *FoldMI);
234 111 : LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);
235 111 : UseMI->eraseFromParent();
236 111 : DefMI->addRegisterDead(LI->reg, nullptr);
237 111 : Dead.push_back(DefMI);
238 : ++NumDCEFoldedLoads;
239 111 : return true;
240 : }
241 :
242 1980 : bool LiveRangeEdit::useIsKill(const LiveInterval &LI,
243 : const MachineOperand &MO) const {
244 1980 : const MachineInstr &MI = *MO.getParent();
245 1980 : SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
246 1980 : if (LI.Query(Idx).isKill())
247 : return true;
248 1159 : const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
249 : unsigned SubReg = MO.getSubReg();
250 1159 : LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
251 1159 : for (const LiveInterval::SubRange &S : LI.subranges()) {
252 0 : if ((S.LaneMask & LaneMask).any() && S.Query(Idx).isKill())
253 : return true;
254 : }
255 : return false;
256 : }
257 :
258 : /// Find all live intervals that need to shrink, then remove the instruction.
259 62761 : void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink,
260 : AliasAnalysis *AA) {
261 : assert(MI->allDefsAreDead() && "Def isn't really dead");
262 62761 : SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
263 :
264 : // Never delete a bundled instruction.
265 : if (MI->isBundled()) {
266 2 : return;
267 : }
268 : // Never delete inline asm.
269 62759 : if (MI->isInlineAsm()) {
270 : LLVM_DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
271 : return;
272 : }
273 :
274 : // Use the same criteria as DeadMachineInstructionElim.
275 62759 : bool SawStore = false;
276 62759 : if (!MI->isSafeToMove(nullptr, SawStore)) {
277 : LLVM_DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
278 : return;
279 : }
280 :
281 : LLVM_DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
282 :
283 : // Collect virtual registers to be erased after MI is gone.
284 : SmallVector<unsigned, 8> RegsToErase;
285 : bool ReadsPhysRegs = false;
286 : bool isOrigDef = false;
287 : unsigned Dest;
288 : // Only optimize rematerialize case when the instruction has one def, since
289 : // otherwise we could leave some dead defs in the code. This case is
290 : // extremely rare.
291 62759 : if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
292 30347 : MI->getDesc().getNumDefs() == 1) {
293 30347 : Dest = MI->getOperand(0).getReg();
294 : unsigned Original = VRM->getOriginal(Dest);
295 30347 : LiveInterval &OrigLI = LIS.getInterval(Original);
296 30347 : VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
297 : // The original live-range may have been shrunk to
298 : // an empty live-range. It happens when it is dead, but
299 : // we still keep it around to be able to rematerialize
300 : // other values that depend on it.
301 30347 : if (OrigVNI)
302 : isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
303 : }
304 :
305 : // Check for live intervals that may shrink
306 156806 : for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
307 219565 : MOE = MI->operands_end(); MOI != MOE; ++MOI) {
308 156806 : if (!MOI->isReg())
309 85232 : continue;
310 108987 : unsigned Reg = MOI->getReg();
311 108987 : if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
312 : // Check if MI reads any unreserved physregs.
313 49853 : if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
314 : ReadsPhysRegs = true;
315 37411 : else if (MOI->isDef())
316 8734 : LIS.removePhysRegDefAt(Reg, Idx);
317 37413 : continue;
318 : }
319 71574 : LiveInterval &LI = LIS.getInterval(Reg);
320 :
321 : // Shrink read registers, unless it is likely to be expensive and
322 : // unlikely to change anything. We typically don't want to shrink the
323 : // PIC base register that has lots of uses everywhere.
324 : // Always shrink COPY uses that probably come from live range splitting.
325 71574 : if ((MI->readsVirtualRegister(Reg) && (MI->isCopy() || MOI->isDef())) ||
326 2094 : (MOI->readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, *MOI))))
327 9728 : ToShrink.insert(&LI);
328 :
329 : // Remove defined value.
330 71574 : if (MOI->isDef()) {
331 121340 : if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)
332 60670 : TheDelegate->LRE_WillShrinkVirtReg(LI.reg);
333 60670 : LIS.removeVRegDefAt(LI, Idx);
334 60670 : if (LI.empty())
335 54837 : RegsToErase.push_back(Reg);
336 : }
337 : }
338 :
339 : // Currently, we don't support DCE of physreg live ranges. If MI reads
340 : // any unreserved physregs, don't erase the instruction, but turn it into
341 : // a KILL instead. This way, the physreg live ranges don't end up
342 : // dangling.
343 : // FIXME: It would be better to have something like shrinkToUses() for
344 : // physregs. That could potentially enable more DCE and it would free up
345 : // the physreg. It would not happen often, though.
346 62759 : if (ReadsPhysRegs) {
347 2 : MI->setDesc(TII.get(TargetOpcode::KILL));
348 : // Remove all operands that aren't physregs.
349 6 : for (unsigned i = MI->getNumOperands(); i; --i) {
350 4 : const MachineOperand &MO = MI->getOperand(i-1);
351 4 : if (MO.isReg() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
352 : continue;
353 2 : MI->RemoveOperand(i-1);
354 : }
355 : LLVM_DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
356 : } else {
357 : // If the dest of MI is an original reg and MI is reMaterializable,
358 : // don't delete the inst. Replace the dest with a new reg, and keep
359 : // the inst for remat of other siblings. The inst is saved in
360 : // LiveRangeEdit::DeadRemats and will be deleted after all the
361 : // allocations of the func are done.
362 62757 : if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
363 8164 : LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);
364 16328 : VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
365 8164 : NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
366 8164 : pop_back();
367 8164 : DeadRemats->insert(MI);
368 8164 : const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
369 8164 : MI->substituteRegister(Dest, NewLI.reg, 0, TRI);
370 8164 : MI->getOperand(0).setIsDead(true);
371 : } else {
372 54593 : if (TheDelegate)
373 54593 : TheDelegate->LRE_WillEraseInstruction(MI);
374 54593 : LIS.RemoveMachineInstrFromMaps(*MI);
375 54593 : MI->eraseFromParent();
376 : ++NumDCEDeleted;
377 : }
378 : }
379 :
380 : // Erase any virtregs that are now empty and unused. There may be <undef>
381 : // uses around. Keep the empty live range in that case.
382 117596 : for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
383 54837 : unsigned Reg = RegsToErase[i];
384 109674 : if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
385 54322 : ToShrink.remove(&LIS.getInterval(Reg));
386 54322 : eraseVirtReg(Reg);
387 : }
388 : }
389 : }
390 :
391 72188 : void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
392 : ArrayRef<unsigned> RegsBeingSpilled,
393 : AliasAnalysis *AA) {
394 72188 : ToShrinkSet ToShrink;
395 :
396 : for (;;) {
397 : // Erase all dead defs.
398 206370 : while (!Dead.empty())
399 62761 : eliminateDeadDef(Dead.pop_back_val(), ToShrink, AA);
400 :
401 80848 : if (ToShrink.empty())
402 : break;
403 :
404 : // Shrink just one live interval. Then delete new dead defs.
405 8660 : LiveInterval *LI = ToShrink.back();
406 8660 : ToShrink.pop_back();
407 8660 : if (foldAsLoad(LI, Dead))
408 8472 : continue;
409 8549 : unsigned VReg = LI->reg;
410 8549 : if (TheDelegate)
411 8549 : TheDelegate->LRE_WillShrinkVirtReg(VReg);
412 8549 : if (!LIS.shrinkToUses(LI, &Dead))
413 : continue;
414 :
415 : // Don't create new intervals for a register being spilled.
416 : // The new intervals would have to be spilled anyway so its not worth it.
417 : // Also they currently aren't spilled so creating them and not spilling
418 : // them results in incorrect code.
419 : bool BeingSpilled = false;
420 336 : for (unsigned i = 0, e = RegsBeingSpilled.size(); i != e; ++i) {
421 296 : if (VReg == RegsBeingSpilled[i]) {
422 : BeingSpilled = true;
423 : break;
424 : }
425 : }
426 :
427 189 : if (BeingSpilled) continue;
428 :
429 : // LI may have been separated, create new intervals.
430 188 : LI->RenumberValues();
431 : SmallVector<LiveInterval*, 8> SplitLIs;
432 188 : LIS.splitSeparateComponents(*LI, SplitLIs);
433 188 : if (!SplitLIs.empty())
434 : ++NumFracRanges;
435 :
436 188 : unsigned Original = VRM ? VRM->getOriginal(VReg) : 0;
437 411 : for (const LiveInterval *SplitLI : SplitLIs) {
438 : // If LI is an original interval that hasn't been split yet, make the new
439 : // intervals their own originals instead of referring to LI. The original
440 : // interval must contain all the split products, and LI doesn't.
441 223 : if (Original != VReg && Original != 0)
442 222 : VRM->setIsSplitFromReg(SplitLI->reg, Original);
443 223 : if (TheDelegate)
444 223 : TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg, VReg);
445 : }
446 : }
447 72188 : }
448 :
449 : // Keep track of new virtual registers created via
450 : // MachineRegisterInfo::createVirtualRegister.
451 : void
452 114650 : LiveRangeEdit::MRI_NoteNewVirtualRegister(unsigned VReg)
453 : {
454 114650 : if (VRM)
455 114649 : VRM->grow();
456 :
457 114650 : NewRegs.push_back(VReg);
458 114650 : }
459 :
460 : void
461 56424 : LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
462 : const MachineLoopInfo &Loops,
463 : const MachineBlockFrequencyInfo &MBFI) {
464 56424 : VirtRegAuxInfo VRAI(MF, LIS, VRM, Loops, MBFI);
465 162877 : for (unsigned I = 0, Size = size(); I < Size; ++I) {
466 212906 : LiveInterval &LI = LIS.getInterval(get(I));
467 106453 : if (MRI.recomputeRegClass(LI.reg))
468 : LLVM_DEBUG({
469 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
470 : dbgs() << "Inflated " << printReg(LI.reg) << " to "
471 : << TRI->getRegClassName(MRI.getRegClass(LI.reg)) << '\n';
472 : });
473 106453 : VRAI.calculateSpillWeightAndHint(LI);
474 : }
475 56424 : }
|
