1//===- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map -----------------===//
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// This file implements the VirtRegMap class.
10//
11// It also contains implementations of the Spiller interface, which, given a
12// virtual register map and a machine function, eliminates all virtual
13// references by replacing them with physical register references - adding spill
14// code as necessary.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/VirtRegMap.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/CodeGen/LiveDebugVariables.h"
22#include "llvm/CodeGen/LiveInterval.h"
23#include "llvm/CodeGen/LiveIntervals.h"
24#include "llvm/CodeGen/LiveRegMatrix.h"
25#include "llvm/CodeGen/LiveStacks.h"
26#include "llvm/CodeGen/MachineBasicBlock.h"
27#include "llvm/CodeGen/MachineFrameInfo.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/MachineInstr.h"
31#include "llvm/CodeGen/MachineOperand.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/SlotIndexes.h"
34#include "llvm/CodeGen/TargetFrameLowering.h"
35#include "llvm/CodeGen/TargetInstrInfo.h"
36#include "llvm/CodeGen/TargetOpcodes.h"
37#include "llvm/CodeGen/TargetRegisterInfo.h"
38#include "llvm/CodeGen/TargetSubtargetInfo.h"
39#include "llvm/Config/llvm-config.h"
40#include "llvm/MC/LaneBitmask.h"
41#include "llvm/Pass.h"
42#include "llvm/Support/Compiler.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/raw_ostream.h"
45#include <cassert>
46#include <iterator>
47#include <utility>
48
49using namespace llvm;
50
51#define DEBUG_TYPE "regalloc"
52
53STATISTIC(NumSpillSlots, "Number of spill slots allocated");
54STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting");
55
56//===----------------------------------------------------------------------===//
57// VirtRegMap implementation
58//===----------------------------------------------------------------------===//
59
60char VirtRegMapWrapperLegacy::ID = 0;
61
62INITIALIZE_PASS(VirtRegMapWrapperLegacy, "virtregmap", "Virtual Register Map",
63 false, true)
64
65void VirtRegMap::init(MachineFunction &mf) {
66 MRI = &mf.getRegInfo();
67 TII = mf.getSubtarget().getInstrInfo();
68 TRI = mf.getSubtarget().getRegisterInfo();
69 MF = &mf;
70
71 Virt2PhysMap.clear();
72 Virt2StackSlotMap.clear();
73 Virt2SplitMap.clear();
74 Virt2ShapeMap.clear();
75
76 grow();
77}
78
79void VirtRegMap::grow() {
80 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
81 Virt2PhysMap.resize(S: NumRegs);
82 Virt2StackSlotMap.resize(S: NumRegs);
83 Virt2SplitMap.resize(S: NumRegs);
84}
85
86void VirtRegMap::assignVirt2Phys(Register virtReg, MCRegister physReg) {
87 assert(virtReg.isVirtual() && physReg.isPhysical());
88 assert(!Virt2PhysMap[virtReg] &&
89 "attempt to assign physical register to already mapped "
90 "virtual register");
91 assert(!getRegInfo().isReserved(physReg) &&
92 "Attempt to map virtReg to a reserved physReg");
93 Virt2PhysMap[virtReg] = physReg;
94}
95
96unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
97 unsigned Size = TRI->getSpillSize(RC: *RC);
98 Align Alignment = TRI->getSpillAlign(RC: *RC);
99 // Set preferred alignment if we are still able to realign the stack
100 auto &ST = MF->getSubtarget();
101 Align CurrentAlign = ST.getFrameLowering()->getStackAlign();
102 if (Alignment > CurrentAlign && !TRI->canRealignStack(MF: *MF)) {
103 Alignment = CurrentAlign;
104 }
105 int SS = MF->getFrameInfo().CreateSpillStackObject(Size, Alignment);
106 ++NumSpillSlots;
107 return SS;
108}
109
110bool VirtRegMap::hasPreferredPhys(Register VirtReg) const {
111 Register Hint = MRI->getSimpleHint(VReg: VirtReg);
112 if (!Hint.isValid())
113 return false;
114 if (Hint.isVirtual())
115 Hint = getPhys(virtReg: Hint);
116 return Register(getPhys(virtReg: VirtReg)) == Hint;
117}
118
119bool VirtRegMap::hasKnownPreference(Register VirtReg) const {
120 std::pair<unsigned, Register> Hint = MRI->getRegAllocationHint(VReg: VirtReg);
121 if (Hint.second.isPhysical())
122 return true;
123 if (Hint.second.isVirtual())
124 return hasPhys(virtReg: Hint.second);
125 return false;
126}
127
128int VirtRegMap::assignVirt2StackSlot(Register virtReg) {
129 assert(virtReg.isVirtual());
130 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
131 "attempt to assign stack slot to already spilled register");
132 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(Reg: virtReg);
133 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
134}
135
136void VirtRegMap::assignVirt2StackSlot(Register virtReg, int SS) {
137 assert(virtReg.isVirtual());
138 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
139 "attempt to assign stack slot to already spilled register");
140 assert((SS >= 0 ||
141 (SS >= MF->getFrameInfo().getObjectIndexBegin())) &&
142 "illegal fixed frame index");
143 Virt2StackSlotMap[virtReg] = SS;
144}
145
146void VirtRegMap::print(raw_ostream &OS, const Module*) const {
147 OS << "********** REGISTER MAP **********\n";
148 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
149 Register Reg = Register::index2VirtReg(Index: i);
150 if (Virt2PhysMap[Reg]) {
151 OS << '[' << printReg(Reg, TRI) << " -> "
152 << printReg(Reg: Virt2PhysMap[Reg], TRI) << "] "
153 << TRI->getRegClassName(Class: MRI->getRegClass(Reg)) << "\n";
154 }
155 }
156
157 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
158 Register Reg = Register::index2VirtReg(Index: i);
159 if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
160 OS << '[' << printReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
161 << "] " << TRI->getRegClassName(Class: MRI->getRegClass(Reg)) << "\n";
162 }
163 }
164 OS << '\n';
165}
166
167#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
168LLVM_DUMP_METHOD void VirtRegMap::dump() const {
169 print(dbgs());
170}
171#endif
172
173AnalysisKey VirtRegMapAnalysis::Key;
174
175PreservedAnalyses
176VirtRegMapPrinterPass::run(MachineFunction &MF,
177 MachineFunctionAnalysisManager &MFAM) {
178 OS << MFAM.getResult<VirtRegMapAnalysis>(IR&: MF);
179 return PreservedAnalyses::all();
180}
181
182VirtRegMap VirtRegMapAnalysis::run(MachineFunction &MF,
183 MachineFunctionAnalysisManager &MAM) {
184 VirtRegMap VRM;
185 VRM.init(mf&: MF);
186 return VRM;
187}
188
189//===----------------------------------------------------------------------===//
190// VirtRegRewriter
191//===----------------------------------------------------------------------===//
192//
193// The VirtRegRewriter is the last of the register allocator passes.
194// It rewrites virtual registers to physical registers as specified in the
195// VirtRegMap analysis. It also updates live-in information on basic blocks
196// according to LiveIntervals.
197//
198namespace {
199
200class VirtRegRewriter {
201 MachineFunction *MF = nullptr;
202 const TargetRegisterInfo *TRI = nullptr;
203 const TargetInstrInfo *TII = nullptr;
204 MachineRegisterInfo *MRI = nullptr;
205 SlotIndexes *Indexes = nullptr;
206 LiveIntervals *LIS = nullptr;
207 LiveRegMatrix *LRM = nullptr;
208 VirtRegMap *VRM = nullptr;
209 LiveDebugVariables *DebugVars = nullptr;
210 DenseSet<Register> RewriteRegs;
211 bool ClearVirtRegs;
212
213 void rewrite();
214 void addMBBLiveIns();
215 bool readsUndefSubreg(const MachineOperand &MO) const;
216 void addLiveInsForSubRanges(const LiveInterval &LI, MCRegister PhysReg) const;
217 void handleIdentityCopy(MachineInstr &MI);
218 void expandCopyBundle(MachineInstr &MI) const;
219 bool subRegLiveThrough(const MachineInstr &MI, MCRegister SuperPhysReg) const;
220 LaneBitmask liveOutUndefPhiLanesForUndefSubregDef(
221 const LiveInterval &LI, const MachineBasicBlock &MBB, unsigned SubReg,
222 MCRegister PhysReg, const MachineInstr &MI) const;
223
224public:
225 VirtRegRewriter(bool ClearVirtRegs, SlotIndexes *Indexes, LiveIntervals *LIS,
226 LiveRegMatrix *LRM, VirtRegMap *VRM,
227 LiveDebugVariables *DebugVars)
228 : Indexes(Indexes), LIS(LIS), LRM(LRM), VRM(VRM), DebugVars(DebugVars),
229 ClearVirtRegs(ClearVirtRegs) {}
230
231 bool run(MachineFunction &);
232};
233
234class VirtRegRewriterLegacy : public MachineFunctionPass {
235public:
236 static char ID;
237 bool ClearVirtRegs;
238 VirtRegRewriterLegacy(bool ClearVirtRegs = true)
239 : MachineFunctionPass(ID), ClearVirtRegs(ClearVirtRegs) {}
240
241 void getAnalysisUsage(AnalysisUsage &AU) const override;
242
243 bool runOnMachineFunction(MachineFunction&) override;
244
245 MachineFunctionProperties getSetProperties() const override {
246 if (ClearVirtRegs) {
247 return MachineFunctionProperties().setNoVRegs();
248 }
249
250 return MachineFunctionProperties();
251 }
252};
253
254} // end anonymous namespace
255
256char VirtRegRewriterLegacy::ID = 0;
257
258char &llvm::VirtRegRewriterID = VirtRegRewriterLegacy::ID;
259
260INITIALIZE_PASS_BEGIN(VirtRegRewriterLegacy, "virtregrewriter",
261 "Virtual Register Rewriter", false, false)
262INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
263INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
264INITIALIZE_PASS_DEPENDENCY(LiveDebugVariablesWrapperLegacy)
265INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)
266INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)
267INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
268INITIALIZE_PASS_END(VirtRegRewriterLegacy, "virtregrewriter",
269 "Virtual Register Rewriter", false, false)
270
271void VirtRegRewriterLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
272 AU.setPreservesCFG();
273 AU.addRequired<LiveIntervalsWrapperPass>();
274 AU.addPreserved<LiveIntervalsWrapperPass>();
275 AU.addRequired<SlotIndexesWrapperPass>();
276 AU.addPreserved<SlotIndexesWrapperPass>();
277 AU.addRequired<LiveDebugVariablesWrapperLegacy>();
278 AU.addRequired<LiveStacksWrapperLegacy>();
279 AU.addPreserved<LiveStacksWrapperLegacy>();
280 AU.addRequired<VirtRegMapWrapperLegacy>();
281 AU.addRequired<LiveRegMatrixWrapperLegacy>();
282
283 if (!ClearVirtRegs)
284 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();
285
286 MachineFunctionPass::getAnalysisUsage(AU);
287}
288
289bool VirtRegRewriterLegacy::runOnMachineFunction(MachineFunction &MF) {
290 VirtRegMap &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM();
291 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
292 LiveRegMatrix &LRM = getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM();
293 SlotIndexes &Indexes = getAnalysis<SlotIndexesWrapperPass>().getSI();
294 LiveDebugVariables &DebugVars =
295 getAnalysis<LiveDebugVariablesWrapperLegacy>().getLDV();
296
297 VirtRegRewriter R(ClearVirtRegs, &Indexes, &LIS, &LRM, &VRM, &DebugVars);
298 return R.run(MF);
299}
300
301PreservedAnalyses
302VirtRegRewriterPass::run(MachineFunction &MF,
303 MachineFunctionAnalysisManager &MFAM) {
304 MFPropsModifier _(*this, MF);
305
306 VirtRegMap &VRM = MFAM.getResult<VirtRegMapAnalysis>(IR&: MF);
307 LiveIntervals &LIS = MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
308 LiveRegMatrix &LRM = MFAM.getResult<LiveRegMatrixAnalysis>(IR&: MF);
309 SlotIndexes &Indexes = MFAM.getResult<SlotIndexesAnalysis>(IR&: MF);
310 LiveDebugVariables &DebugVars =
311 MFAM.getResult<LiveDebugVariablesAnalysis>(IR&: MF);
312
313 VirtRegRewriter R(ClearVirtRegs, &Indexes, &LIS, &LRM, &VRM, &DebugVars);
314 if (!R.run(MF))
315 return PreservedAnalyses::all();
316
317 auto PA = getMachineFunctionPassPreservedAnalyses();
318 PA.preserveSet<CFGAnalyses>();
319 PA.preserve<LiveIntervalsAnalysis>();
320 PA.preserve<SlotIndexesAnalysis>();
321 PA.preserve<LiveStacksAnalysis>();
322 // LiveDebugVariables is preserved by default, so clear it
323 // if this VRegRewriter is the last one in the pipeline.
324 if (ClearVirtRegs)
325 PA.abandon<LiveDebugVariablesAnalysis>();
326 return PA;
327}
328
329bool VirtRegRewriter::run(MachineFunction &fn) {
330 MF = &fn;
331 TRI = MF->getSubtarget().getRegisterInfo();
332 TII = MF->getSubtarget().getInstrInfo();
333 MRI = &MF->getRegInfo();
334
335 LLVM_DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
336 << "********** Function: " << MF->getName() << '\n');
337 LLVM_DEBUG(VRM->dump());
338
339 // Add kill flags while we still have virtual registers.
340 LIS->addKillFlags(VRM);
341
342 // Live-in lists on basic blocks are required for physregs.
343 addMBBLiveIns();
344
345 // Rewrite virtual registers.
346 rewrite();
347
348 if (ClearVirtRegs) {
349 // Write out new DBG_VALUE instructions.
350
351 // We only do this if ClearVirtRegs is specified since this should be the
352 // final run of the pass and we don't want to emit them multiple times.
353 DebugVars->emitDebugValues(VRM);
354
355 // All machine operands and other references to virtual registers have been
356 // replaced. Remove the virtual registers and release all the transient data.
357 VRM->clearAllVirt();
358 MRI->clearVirtRegs();
359 }
360
361 return true;
362}
363
364void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,
365 MCRegister PhysReg) const {
366 assert(!LI.empty());
367 assert(LI.hasSubRanges());
368
369 using SubRangeIteratorPair =
370 std::pair<const LiveInterval::SubRange *, LiveInterval::const_iterator>;
371
372 SmallVector<SubRangeIteratorPair, 4> SubRanges;
373 SlotIndex First;
374 SlotIndex Last;
375 for (const LiveInterval::SubRange &SR : LI.subranges()) {
376 SubRanges.push_back(Elt: std::make_pair(x: &SR, y: SR.begin()));
377 if (!First.isValid() || SR.segments.front().start < First)
378 First = SR.segments.front().start;
379 if (!Last.isValid() || SR.segments.back().end > Last)
380 Last = SR.segments.back().end;
381 }
382
383 // Check all mbb start positions between First and Last while
384 // simultaneously advancing an iterator for each subrange.
385 for (SlotIndexes::MBBIndexIterator MBBI = Indexes->getMBBLowerBound(Idx: First);
386 MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) {
387 SlotIndex MBBBegin = MBBI->first;
388 // Advance all subrange iterators so that their end position is just
389 // behind MBBBegin (or the iterator is at the end).
390 LaneBitmask LaneMask;
391 for (auto &RangeIterPair : SubRanges) {
392 const LiveInterval::SubRange *SR = RangeIterPair.first;
393 LiveInterval::const_iterator &SRI = RangeIterPair.second;
394 while (SRI != SR->end() && SRI->end <= MBBBegin)
395 ++SRI;
396 if (SRI == SR->end())
397 continue;
398 if (SRI->start <= MBBBegin)
399 LaneMask |= SR->LaneMask;
400 }
401 if (LaneMask.none())
402 continue;
403 MachineBasicBlock *MBB = MBBI->second;
404 MBB->addLiveIn(PhysReg, LaneMask);
405 }
406}
407
408// Compute MBB live-in lists from virtual register live ranges and their
409// assignments.
410void VirtRegRewriter::addMBBLiveIns() {
411 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) {
412 Register VirtReg = Register::index2VirtReg(Index: Idx);
413 if (MRI->reg_nodbg_empty(RegNo: VirtReg))
414 continue;
415 LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
416 if (LI.empty() || LIS->intervalIsInOneMBB(LI))
417 continue;
418 // This is a virtual register that is live across basic blocks. Its
419 // assigned PhysReg must be marked as live-in to those blocks.
420 MCRegister PhysReg = VRM->getPhys(virtReg: VirtReg);
421 if (!PhysReg) {
422 // There may be no physical register assigned if only some register
423 // classes were already allocated.
424 assert(!ClearVirtRegs && "Unmapped virtual register");
425 continue;
426 }
427
428 if (LI.hasSubRanges()) {
429 addLiveInsForSubRanges(LI, PhysReg);
430 } else {
431 // Go over MBB begin positions and see if we have segments covering them.
432 // The following works because segments and the MBBIndex list are both
433 // sorted by slot indexes.
434 SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin();
435 for (const auto &Seg : LI) {
436 I = Indexes->getMBBLowerBound(Start: I, Idx: Seg.start);
437 for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) {
438 MachineBasicBlock *MBB = I->second;
439 MBB->addLiveIn(PhysReg);
440 }
441 }
442 }
443 }
444
445 // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in
446 // each MBB's LiveIns set before calling addLiveIn on them.
447 for (MachineBasicBlock &MBB : *MF)
448 MBB.sortUniqueLiveIns();
449}
450
451/// Returns true if the given machine operand \p MO only reads undefined lanes.
452/// The function only works for use operands with a subregister set.
453bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
454 // Shortcut if the operand is already marked undef.
455 if (MO.isUndef())
456 return true;
457
458 Register Reg = MO.getReg();
459 const LiveInterval &LI = LIS->getInterval(Reg);
460 const MachineInstr &MI = *MO.getParent();
461 SlotIndex BaseIndex = LIS->getInstructionIndex(Instr: MI);
462 // This code is only meant to handle reading undefined subregisters which
463 // we couldn't properly detect before.
464 assert(LI.liveAt(BaseIndex) &&
465 "Reads of completely dead register should be marked undef already");
466 unsigned SubRegIdx = MO.getSubReg();
467 assert(SubRegIdx != 0 && LI.hasSubRanges());
468 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubIdx: SubRegIdx);
469 // See if any of the relevant subregister liveranges is defined at this point.
470 for (const LiveInterval::SubRange &SR : LI.subranges()) {
471 if ((SR.LaneMask & UseMask).any() && SR.liveAt(index: BaseIndex))
472 return false;
473 }
474 return true;
475}
476
477void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) {
478 if (!MI.isIdentityCopy())
479 return;
480 LLVM_DEBUG(dbgs() << "Identity copy: " << MI);
481 ++NumIdCopies;
482
483 Register DstReg = MI.getOperand(i: 0).getReg();
484
485 // We may have deferred allocation of the virtual register, and the rewrite
486 // regs code doesn't handle the liveness update.
487 if (DstReg.isVirtual())
488 return;
489
490 RewriteRegs.insert(V: DstReg);
491
492 // Copies like:
493 // %r0 = COPY undef %r0
494 // %al = COPY %al, implicit-def %eax
495 // give us additional liveness information: The target (super-)register
496 // must not be valid before this point. Replace the COPY with a KILL
497 // instruction to maintain this information.
498 if (MI.getOperand(i: 1).isUndef() || MI.getNumOperands() > 2) {
499 MI.setDesc(TII->get(Opcode: TargetOpcode::KILL));
500 LLVM_DEBUG(dbgs() << " replace by: " << MI);
501 return;
502 }
503
504 if (Indexes)
505 Indexes->removeSingleMachineInstrFromMaps(MI);
506 MI.eraseFromBundle();
507 LLVM_DEBUG(dbgs() << " deleted.\n");
508}
509
510/// The liverange splitting logic sometimes produces bundles of copies when
511/// subregisters are involved. Expand these into a sequence of copy instructions
512/// after processing the last in the bundle. Does not update LiveIntervals
513/// which we shouldn't need for this instruction anymore.
514void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {
515 if (!MI.isCopy() && !MI.isKill())
516 return;
517
518 if (MI.isBundledWithPred() && !MI.isBundledWithSucc()) {
519 SmallVector<MachineInstr *, 2> MIs({&MI});
520
521 // Only do this when the complete bundle is made out of COPYs and KILLs.
522 MachineBasicBlock &MBB = *MI.getParent();
523 for (MachineBasicBlock::reverse_instr_iterator I =
524 std::next(x: MI.getReverseIterator()), E = MBB.instr_rend();
525 I != E && I->isBundledWithSucc(); ++I) {
526 if (!I->isCopy() && !I->isKill())
527 return;
528 MIs.push_back(Elt: &*I);
529 }
530 MachineInstr *FirstMI = MIs.back();
531
532 auto anyRegsAlias = [](const MachineInstr *Dst,
533 ArrayRef<MachineInstr *> Srcs,
534 const TargetRegisterInfo *TRI) {
535 for (const MachineInstr *Src : Srcs)
536 if (Src != Dst)
537 if (TRI->regsOverlap(RegA: Dst->getOperand(i: 0).getReg(),
538 RegB: Src->getOperand(i: 1).getReg()))
539 return true;
540 return false;
541 };
542
543 // If any of the destination registers in the bundle of copies alias any of
544 // the source registers, try to schedule the instructions to avoid any
545 // clobbering.
546 for (int E = MIs.size(), PrevE = E; E > 1; PrevE = E) {
547 for (int I = E; I--; )
548 if (!anyRegsAlias(MIs[I], ArrayRef(MIs).take_front(N: E), TRI)) {
549 if (I + 1 != E)
550 std::swap(a&: MIs[I], b&: MIs[E - 1]);
551 --E;
552 }
553 if (PrevE == E) {
554 MF->getFunction().getContext().emitError(
555 ErrorStr: "register rewriting failed: cycle in copy bundle");
556 break;
557 }
558 }
559
560 MachineInstr *BundleStart = FirstMI;
561 for (MachineInstr *BundledMI : llvm::reverse(C&: MIs)) {
562 // If instruction is in the middle of the bundle, move it before the
563 // bundle starts, otherwise, just unbundle it. When we get to the last
564 // instruction, the bundle will have been completely undone.
565 if (BundledMI != BundleStart) {
566 BundledMI->removeFromBundle();
567 MBB.insert(I: BundleStart, MI: BundledMI);
568 } else if (BundledMI->isBundledWithSucc()) {
569 BundledMI->unbundleFromSucc();
570 BundleStart = &*std::next(x: BundledMI->getIterator());
571 }
572
573 if (Indexes && BundledMI != FirstMI)
574 Indexes->insertMachineInstrInMaps(MI&: *BundledMI);
575 }
576 }
577}
578
579/// Check whether (part of) \p SuperPhysReg is live through \p MI.
580/// \pre \p MI defines a subregister of a virtual register that
581/// has been assigned to \p SuperPhysReg.
582bool VirtRegRewriter::subRegLiveThrough(const MachineInstr &MI,
583 MCRegister SuperPhysReg) const {
584 SlotIndex MIIndex = LIS->getInstructionIndex(Instr: MI);
585 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
586 SlotIndex AfterMIDefs = MIIndex.getBoundaryIndex();
587 for (MCRegUnit Unit : TRI->regunits(Reg: SuperPhysReg)) {
588 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
589 // If the regunit is live both before and after MI,
590 // we assume it is live through.
591 // Generally speaking, this is not true, because something like
592 // "RU = op RU" would match that description.
593 // However, we know that we are trying to assess whether
594 // a def of a virtual reg, vreg, is live at the same time of RU.
595 // If we are in the "RU = op RU" situation, that means that vreg
596 // is defined at the same time as RU (i.e., "vreg, RU = op RU").
597 // Thus, vreg and RU interferes and vreg cannot be assigned to
598 // SuperPhysReg. Therefore, this situation cannot happen.
599 if (UnitRange.liveAt(index: AfterMIDefs) && UnitRange.liveAt(index: BeforeMIUses))
600 return true;
601 }
602 return false;
603}
604
605/// Compute a lanemask for undef lanes which need to be preserved out of the
606/// defining block for a register assignment for a subregister def. \p PhysReg
607/// is assigned to \p LI, which is the main range.
608LaneBitmask VirtRegRewriter::liveOutUndefPhiLanesForUndefSubregDef(
609 const LiveInterval &LI, const MachineBasicBlock &MBB, unsigned SubReg,
610 MCRegister PhysReg, const MachineInstr &MI) const {
611 LaneBitmask UndefMask = ~TRI->getSubRegIndexLaneMask(SubIdx: SubReg);
612 LaneBitmask LiveOutUndefLanes;
613
614 for (const LiveInterval::SubRange &SR : LI.subranges()) {
615 // Figure out which lanes are undef live into a successor.
616 LaneBitmask NeedImpDefLanes = UndefMask & SR.LaneMask;
617 if (NeedImpDefLanes.any() && !LIS->isLiveOutOfMBB(LR: SR, mbb: &MBB)) {
618 for (const MachineBasicBlock *Succ : MBB.successors()) {
619 if (LIS->isLiveInToMBB(LR: SR, mbb: Succ))
620 LiveOutUndefLanes |= NeedImpDefLanes;
621 }
622 }
623 }
624
625 SlotIndex MIIndex = LIS->getInstructionIndex(Instr: MI);
626 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
627 LaneBitmask InterferingLanes =
628 LRM->checkInterferenceLanes(Start: BeforeMIUses, End: MIIndex.getRegSlot(), PhysReg);
629 LiveOutUndefLanes &= ~InterferingLanes;
630
631 LLVM_DEBUG(if (LiveOutUndefLanes.any()) {
632 dbgs() << "Need live out undef defs for " << printReg(PhysReg)
633 << LiveOutUndefLanes << " from " << printMBBReference(MBB) << '\n';
634 });
635
636 return LiveOutUndefLanes;
637}
638
639void VirtRegRewriter::rewrite() {
640 bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
641 SmallVector<Register, 8> SuperDeads;
642 SmallVector<Register, 8> SuperDefs;
643 SmallVector<Register, 8> SuperKills;
644
645 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
646 MBBI != MBBE; ++MBBI) {
647 LLVM_DEBUG(MBBI->print(dbgs(), Indexes));
648 for (MachineInstr &MI : llvm::make_early_inc_range(Range: MBBI->instrs())) {
649 for (MachineOperand &MO : MI.operands()) {
650 // Make sure MRI knows about registers clobbered by regmasks.
651 if (MO.isRegMask())
652 MRI->addPhysRegsUsedFromRegMask(RegMask: MO.getRegMask());
653
654 if (!MO.isReg() || !MO.getReg().isVirtual())
655 continue;
656 Register VirtReg = MO.getReg();
657 MCRegister PhysReg = VRM->getPhys(virtReg: VirtReg);
658 if (!PhysReg)
659 continue;
660
661 assert(Register(PhysReg).isPhysical());
662
663 RewriteRegs.insert(V: PhysReg);
664 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
665
666 // Preserve semantics of sub-register operands.
667 unsigned SubReg = MO.getSubReg();
668 if (SubReg != 0) {
669 if (NoSubRegLiveness || !MRI->shouldTrackSubRegLiveness(VReg: VirtReg)) {
670 // A virtual register kill refers to the whole register, so we may
671 // have to add implicit killed operands for the super-register. A
672 // partial redef always kills and redefines the super-register.
673 if ((MO.readsReg() && (MO.isDef() || MO.isKill())) ||
674 (MO.isDef() && subRegLiveThrough(MI, SuperPhysReg: PhysReg)))
675 SuperKills.push_back(Elt: PhysReg);
676
677 if (MO.isDef()) {
678 // Also add implicit defs for the super-register.
679 if (MO.isDead())
680 SuperDeads.push_back(Elt: PhysReg);
681 else
682 SuperDefs.push_back(Elt: PhysReg);
683 }
684 } else {
685 if (MO.isUse()) {
686 if (readsUndefSubreg(MO))
687 // We need to add an <undef> flag if the subregister is
688 // completely undefined (and we are not adding super-register
689 // defs).
690 MO.setIsUndef(true);
691 } else if (!MO.isDead()) {
692 assert(MO.isDef());
693 if (MO.isUndef()) {
694 const LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
695
696 LaneBitmask LiveOutUndefLanes =
697 liveOutUndefPhiLanesForUndefSubregDef(LI, MBB: *MBBI, SubReg,
698 PhysReg, MI);
699 if (LiveOutUndefLanes.any()) {
700 SmallVector<unsigned, 16> CoveringIndexes;
701
702 // TODO: Just use one super register def if none of the lanes
703 // are needed?
704 if (!TRI->getCoveringSubRegIndexes(RC: MRI->getRegClass(Reg: VirtReg),
705 LaneMask: LiveOutUndefLanes,
706 Indexes&: CoveringIndexes))
707 llvm_unreachable(
708 "cannot represent required subregister defs");
709
710 // Try to represent the minimum needed live out def as a
711 // sequence of subregister defs.
712 //
713 // FIXME: It would be better if we could directly represent
714 // liveness with a lanemask instead of spamming operands.
715 for (unsigned SubIdx : CoveringIndexes)
716 SuperDefs.push_back(Elt: TRI->getSubReg(Reg: PhysReg, Idx: SubIdx));
717 }
718 }
719 }
720 }
721
722 // The def undef and def internal flags only make sense for
723 // sub-register defs, and we are substituting a full physreg. An
724 // implicit killed operand from the SuperKills list will represent the
725 // partial read of the super-register.
726 if (MO.isDef()) {
727 MO.setIsUndef(false);
728 MO.setIsInternalRead(false);
729 }
730
731 // PhysReg operands cannot have subregister indexes.
732 PhysReg = TRI->getSubReg(Reg: PhysReg, Idx: SubReg);
733 assert(PhysReg.isValid() && "Invalid SubReg for physical register");
734 MO.setSubReg(0);
735 }
736 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
737 // we need the inlining here.
738 MO.setReg(PhysReg);
739 MO.setIsRenamable(true);
740 }
741
742 // Add any missing super-register kills after rewriting the whole
743 // instruction.
744 while (!SuperKills.empty())
745 MI.addRegisterKilled(IncomingReg: SuperKills.pop_back_val(), RegInfo: TRI, AddIfNotFound: true);
746
747 while (!SuperDeads.empty())
748 MI.addRegisterDead(Reg: SuperDeads.pop_back_val(), RegInfo: TRI, AddIfNotFound: true);
749
750 while (!SuperDefs.empty())
751 MI.addRegisterDefined(Reg: SuperDefs.pop_back_val(), RegInfo: TRI);
752
753 LLVM_DEBUG(dbgs() << "> " << MI);
754
755 expandCopyBundle(MI);
756
757 // We can remove identity copies right now.
758 handleIdentityCopy(MI);
759 }
760 }
761
762 if (LIS) {
763 // Don't bother maintaining accurate LiveIntervals for registers which were
764 // already allocated.
765 for (Register PhysReg : RewriteRegs) {
766 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
767 LIS->removeRegUnit(Unit);
768 }
769 }
770 }
771
772 RewriteRegs.clear();
773}
774
775void VirtRegRewriterPass::printPipeline(
776 raw_ostream &OS, function_ref<StringRef(StringRef)>) const {
777 OS << "virt-reg-rewriter";
778 if (!ClearVirtRegs)
779 OS << "<no-clear-vregs>";
780}
781
782FunctionPass *llvm::createVirtRegRewriter(bool ClearVirtRegs) {
783 return new VirtRegRewriterLegacy(ClearVirtRegs);
784}
785