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