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 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 only reads undefined lanes.
466/// The function only works for use operands with a subregister set.
467bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
468 // Shortcut if the operand is already marked undef.
469 if (MO.isUndef())
470 return true;
471
472 Register Reg = MO.getReg();
473 const LiveInterval &LI = LIS->getInterval(Reg);
474 const MachineInstr &MI = *MO.getParent();
475 SlotIndex BaseIndex = LIS->getInstructionIndex(Instr: MI);
476 // This code is only meant to handle reading undefined subregisters which
477 // we couldn't properly detect before.
478 assert(LI.liveAt(BaseIndex) &&
479 "Reads of completely dead register should be marked undef already");
480 unsigned SubRegIdx = MO.getSubReg();
481 assert(SubRegIdx != 0 && LI.hasSubRanges());
482 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubIdx: SubRegIdx);
483 // See if any of the relevant subregister liveranges is defined at this point.
484 for (const LiveInterval::SubRange &SR : LI.subranges()) {
485 if ((SR.LaneMask & UseMask).any() && SR.liveAt(index: BaseIndex))
486 return false;
487 }
488 return true;
489}
490
491void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) {
492 if (!MI.isIdentityCopy())
493 return;
494 LLVM_DEBUG(dbgs() << "Identity copy: " << MI);
495 ++NumIdCopies;
496
497 Register DstReg = MI.getOperand(i: 0).getReg();
498
499 // We may have deferred allocation of the virtual register, and the rewrite
500 // regs code doesn't handle the liveness update.
501 if (DstReg.isVirtual())
502 return;
503
504 RewriteRegs.insert(V: DstReg);
505
506 // Copies like:
507 // %r0 = COPY undef %r0
508 // %al = COPY %al, implicit-def %eax
509 // give us additional liveness information: The target (super-)register
510 // must not be valid before this point. Replace the COPY with a KILL
511 // instruction to maintain this information.
512 if (MI.getOperand(i: 1).isUndef() || MI.getNumOperands() > 2) {
513 MI.setDesc(TII->get(Opcode: TargetOpcode::KILL));
514 LLVM_DEBUG(dbgs() << " replace by: " << MI);
515 return;
516 }
517
518 if (Indexes)
519 Indexes->removeSingleMachineInstrFromMaps(MI);
520 MI.eraseFromBundle();
521 LLVM_DEBUG(dbgs() << " deleted.\n");
522}
523
524/// The liverange splitting logic sometimes produces bundles of copies when
525/// subregisters are involved. Expand these into a sequence of copy instructions
526/// after processing the last in the bundle. Does not update LiveIntervals
527/// which we shouldn't need for this instruction anymore.
528void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {
529 if (!MI.isCopy() && !MI.isKill())
530 return;
531
532 if (MI.isBundledWithPred() && !MI.isBundledWithSucc()) {
533 SmallVector<MachineInstr *, 2> MIs({&MI});
534
535 // Only do this when the complete bundle is made out of COPYs and KILLs.
536 MachineBasicBlock &MBB = *MI.getParent();
537 for (MachineBasicBlock::reverse_instr_iterator I =
538 std::next(x: MI.getReverseIterator()), E = MBB.instr_rend();
539 I != E && I->isBundledWithSucc(); ++I) {
540 if (!I->isCopy() && !I->isKill())
541 return;
542 MIs.push_back(Elt: &*I);
543 }
544 MachineInstr *FirstMI = MIs.back();
545
546 auto anyRegsAlias = [](const MachineInstr *Dst,
547 ArrayRef<MachineInstr *> Srcs,
548 const TargetRegisterInfo *TRI) {
549 for (const MachineInstr *Src : Srcs)
550 if (Src != Dst)
551 if (TRI->regsOverlap(RegA: Dst->getOperand(i: 0).getReg(),
552 RegB: Src->getOperand(i: 1).getReg()))
553 return true;
554 return false;
555 };
556
557 // If any of the destination registers in the bundle of copies alias any of
558 // the source registers, try to schedule the instructions to avoid any
559 // clobbering.
560 for (int E = MIs.size(), PrevE = E; E > 1; PrevE = E) {
561 for (int I = E; I--; )
562 if (!anyRegsAlias(MIs[I], ArrayRef(MIs).take_front(N: E), TRI)) {
563 if (I + 1 != E)
564 std::swap(a&: MIs[I], b&: MIs[E - 1]);
565 --E;
566 }
567 if (PrevE == E) {
568 MF->getFunction().getContext().emitError(
569 ErrorStr: "register rewriting failed: cycle in copy bundle");
570 break;
571 }
572 }
573
574 MachineInstr *BundleStart = FirstMI;
575 for (MachineInstr *BundledMI : llvm::reverse(C&: MIs)) {
576 // If instruction is in the middle of the bundle, move it before the
577 // bundle starts, otherwise, just unbundle it. When we get to the last
578 // instruction, the bundle will have been completely undone.
579 if (BundledMI != BundleStart) {
580 BundledMI->removeFromBundle();
581 MBB.insert(I: BundleStart, MI: BundledMI);
582 } else if (BundledMI->isBundledWithSucc()) {
583 BundledMI->unbundleFromSucc();
584 BundleStart = &*std::next(x: BundledMI->getIterator());
585 }
586
587 if (Indexes && BundledMI != FirstMI)
588 Indexes->insertMachineInstrInMaps(MI&: *BundledMI);
589 }
590 }
591}
592
593/// Check whether (part of) \p SuperPhysReg is live through \p MI.
594/// \pre \p MI defines a subregister of a virtual register that
595/// has been assigned to \p SuperPhysReg.
596bool VirtRegRewriter::subRegLiveThrough(const MachineInstr &MI,
597 MCRegister SuperPhysReg) const {
598 SlotIndex MIIndex = LIS->getInstructionIndex(Instr: MI);
599 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
600 SlotIndex AfterMIDefs = MIIndex.getBoundaryIndex();
601 for (MCRegUnit Unit : TRI->regunits(Reg: SuperPhysReg)) {
602 const LiveRange &UnitRange = LIS->getRegUnit(Unit);
603 // If the regunit is live both before and after MI,
604 // we assume it is live through.
605 // Generally speaking, this is not true, because something like
606 // "RU = op RU" would match that description.
607 // However, we know that we are trying to assess whether
608 // a def of a virtual reg, vreg, is live at the same time of RU.
609 // If we are in the "RU = op RU" situation, that means that vreg
610 // is defined at the same time as RU (i.e., "vreg, RU = op RU").
611 // Thus, vreg and RU interferes and vreg cannot be assigned to
612 // SuperPhysReg. Therefore, this situation cannot happen.
613 if (UnitRange.liveAt(index: AfterMIDefs) && UnitRange.liveAt(index: BeforeMIUses))
614 return true;
615 }
616 return false;
617}
618
619/// Compute a lanemask for undef lanes which need to be preserved out of the
620/// defining block for a register assignment for a subregister def. \p PhysReg
621/// is assigned to \p LI, which is the main range.
622LaneBitmask VirtRegRewriter::liveOutUndefPhiLanesForUndefSubregDef(
623 const LiveInterval &LI, const MachineBasicBlock &MBB, unsigned SubReg,
624 MCRegister PhysReg, const MachineInstr &MI) const {
625 LaneBitmask UndefMask = ~TRI->getSubRegIndexLaneMask(SubIdx: SubReg);
626 LaneBitmask LiveOutUndefLanes;
627
628 for (const LiveInterval::SubRange &SR : LI.subranges()) {
629 // Figure out which lanes are undef live into a successor.
630 LaneBitmask NeedImpDefLanes = UndefMask & SR.LaneMask;
631 if (NeedImpDefLanes.any() && !LIS->isLiveOutOfMBB(LR: SR, mbb: &MBB)) {
632 for (const MachineBasicBlock *Succ : MBB.successors()) {
633 if (LIS->isLiveInToMBB(LR: SR, mbb: Succ))
634 LiveOutUndefLanes |= NeedImpDefLanes;
635 }
636 }
637 }
638
639 SlotIndex MIIndex = LIS->getInstructionIndex(Instr: MI);
640 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
641 LaneBitmask InterferingLanes =
642 LRM->checkInterferenceLanes(Start: BeforeMIUses, End: MIIndex.getRegSlot(), PhysReg);
643 LiveOutUndefLanes &= ~InterferingLanes;
644
645 LLVM_DEBUG(if (LiveOutUndefLanes.any()) {
646 dbgs() << "Need live out undef defs for " << printReg(PhysReg)
647 << LiveOutUndefLanes << " from " << printMBBReference(MBB) << '\n';
648 });
649
650 return LiveOutUndefLanes;
651}
652
653void VirtRegRewriter::rewrite() {
654 bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
655 SmallVector<Register, 8> SuperDeads;
656 SmallVector<Register, 8> SuperDefs;
657 SmallVector<Register, 8> SuperKills;
658
659 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
660 MBBI != MBBE; ++MBBI) {
661 LLVM_DEBUG(MBBI->print(dbgs(), Indexes));
662 for (MachineInstr &MI : llvm::make_early_inc_range(Range: MBBI->instrs())) {
663 for (MachineOperand &MO : MI.operands()) {
664 // Make sure MRI knows about registers clobbered by regmasks.
665 if (MO.isRegMask())
666 MRI->addPhysRegsUsedFromRegMask(RegMask: MO.getRegMask());
667
668 if (!MO.isReg() || !MO.getReg().isVirtual())
669 continue;
670 Register VirtReg = MO.getReg();
671 MCRegister PhysReg = VRM->getPhys(virtReg: VirtReg);
672 if (!PhysReg)
673 continue;
674
675 assert(Register(PhysReg).isPhysical());
676
677 RewriteRegs.insert(V: PhysReg);
678 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
679
680 // Preserve semantics of sub-register operands.
681 unsigned SubReg = MO.getSubReg();
682 if (SubReg != 0) {
683 if (NoSubRegLiveness || !MRI->shouldTrackSubRegLiveness(VReg: VirtReg)) {
684 // A virtual register kill refers to the whole register, so we may
685 // have to add implicit killed operands for the super-register. A
686 // partial redef always kills and redefines the super-register.
687 if ((MO.readsReg() && (MO.isDef() || MO.isKill())) ||
688 (MO.isDef() && subRegLiveThrough(MI, SuperPhysReg: PhysReg)))
689 SuperKills.push_back(Elt: PhysReg);
690
691 if (MO.isDef()) {
692 // Also add implicit defs for the super-register.
693 if (MO.isDead())
694 SuperDeads.push_back(Elt: PhysReg);
695 else
696 SuperDefs.push_back(Elt: PhysReg);
697 }
698 } else {
699 if (MO.isUse()) {
700 if (readsUndefSubreg(MO))
701 // We need to add an <undef> flag if the subregister is
702 // completely undefined (and we are not adding super-register
703 // defs).
704 MO.setIsUndef(true);
705 } else if (!MO.isDead()) {
706 assert(MO.isDef());
707 if (MO.isUndef()) {
708 const LiveInterval &LI = LIS->getInterval(Reg: VirtReg);
709
710 LaneBitmask LiveOutUndefLanes =
711 liveOutUndefPhiLanesForUndefSubregDef(LI, MBB: *MBBI, SubReg,
712 PhysReg, MI);
713 if (LiveOutUndefLanes.any()) {
714 SmallVector<unsigned, 16> CoveringIndexes;
715
716 // TODO: Just use one super register def if none of the lanes
717 // are needed?
718 if (!TRI->getCoveringSubRegIndexes(RC: MRI->getRegClass(Reg: VirtReg),
719 LaneMask: LiveOutUndefLanes,
720 Indexes&: CoveringIndexes))
721 llvm_unreachable(
722 "cannot represent required subregister defs");
723
724 // Try to represent the minimum needed live out def as a
725 // sequence of subregister defs.
726 //
727 // FIXME: It would be better if we could directly represent
728 // liveness with a lanemask instead of spamming operands.
729 for (unsigned SubIdx : CoveringIndexes)
730 SuperDefs.push_back(Elt: TRI->getSubReg(Reg: PhysReg, Idx: SubIdx));
731 }
732 }
733 }
734 }
735
736 // The def undef and def internal flags only make sense for
737 // sub-register defs, and we are substituting a full physreg. An
738 // implicit killed operand from the SuperKills list will represent the
739 // partial read of the super-register.
740 if (MO.isDef()) {
741 MO.setIsUndef(false);
742 MO.setIsInternalRead(false);
743 }
744
745 // PhysReg operands cannot have subregister indexes.
746 PhysReg = TRI->getSubReg(Reg: PhysReg, Idx: SubReg);
747 assert(PhysReg.isValid() && "Invalid SubReg for physical register");
748 MO.setSubReg(0);
749 }
750 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
751 // we need the inlining here.
752 MO.setReg(PhysReg);
753 MO.setIsRenamable(true);
754 }
755
756 // Add any missing super-register kills after rewriting the whole
757 // instruction.
758 while (!SuperKills.empty())
759 MI.addRegisterKilled(IncomingReg: SuperKills.pop_back_val(), RegInfo: TRI, AddIfNotFound: true);
760
761 while (!SuperDeads.empty())
762 MI.addRegisterDead(Reg: SuperDeads.pop_back_val(), RegInfo: TRI, AddIfNotFound: true);
763
764 while (!SuperDefs.empty())
765 MI.addRegisterDefined(Reg: SuperDefs.pop_back_val(), RegInfo: TRI);
766
767 LLVM_DEBUG(dbgs() << "> " << MI);
768
769 expandCopyBundle(MI);
770
771 // We can remove identity copies right now.
772 handleIdentityCopy(MI);
773 }
774 }
775
776 if (LIS) {
777 // Don't bother maintaining accurate LiveIntervals for registers which were
778 // already allocated.
779 for (Register PhysReg : RewriteRegs) {
780 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
781 LIS->removeRegUnit(Unit);
782 }
783 }
784 }
785
786 RewriteRegs.clear();
787}
788
789void VirtRegRewriterPass::printPipeline(
790 raw_ostream &OS, function_ref<StringRef(StringRef)>) const {
791 OS << "virt-reg-rewriter";
792 if (!ClearVirtRegs)
793 OS << "<no-clear-vregs>";
794}
795
796FunctionPass *llvm::createVirtRegRewriter(bool ClearVirtRegs) {
797 return new VirtRegRewriterLegacy(ClearVirtRegs);
798}
799