LLVM 22.0.0git
VirtRegMap.cpp
Go to the documentation of this file.
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
20#include "llvm/ADT/Statistic.h"
39#include "llvm/Config/llvm-config.h"
40#include "llvm/MC/LaneBitmask.h"
41#include "llvm/Pass.h"
43#include "llvm/Support/Debug.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
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
80 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
81 Virt2PhysMap.resize(NumRegs);
82 Virt2StackSlotMap.resize(NumRegs);
83 Virt2SplitMap.resize(NumRegs);
84}
85
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);
98 Align Alignment = TRI->getSpillAlign(*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)) {
103 Alignment = CurrentAlign;
104 }
105 int SS = MF->getFrameInfo().CreateSpillStackObject(Size, Alignment);
106 ++NumSpillSlots;
107 return SS;
108}
109
111 Register Hint = MRI->getSimpleHint(VirtReg);
112 if (!Hint.isValid())
113 return false;
114 if (Hint.isVirtual())
115 Hint = getPhys(Hint);
116 return Register(getPhys(VirtReg)) == Hint;
117}
118
120 std::pair<unsigned, Register> Hint = MRI->getRegAllocationHint(VirtReg);
121 if (Hint.second.isPhysical())
122 return true;
123 if (Hint.second.isVirtual())
124 return hasPhys(Hint.second);
125 return false;
126}
127
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(virtReg);
133 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
134}
135
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) {
150 if (Virt2PhysMap[Reg]) {
151 OS << '[' << printReg(Reg, TRI) << " -> "
152 << printReg(Virt2PhysMap[Reg], TRI) << "] "
153 << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
154 }
155 }
156
157 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
159 if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
160 OS << '[' << printReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
161 << "] " << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
162 }
163 }
164 OS << '\n';
165}
166
167#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
169 print(dbgs());
170}
171#endif
172
173AnalysisKey VirtRegMapAnalysis::Key;
174
181
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)
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
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
304 MFPropsModifier _(*this, MF);
305
306 VirtRegMap &VRM = MFAM.getResult<VirtRegMapAnalysis>(MF);
309 SlotIndexes &Indexes = MFAM.getResult<SlotIndexesAnalysis>(MF);
310 LiveDebugVariables &DebugVars =
312
313 VirtRegRewriter R(ClearVirtRegs, &Indexes, &LIS, &LRM, &VRM, &DebugVars);
314 if (!R.run(MF))
315 return PreservedAnalyses::all();
316
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;
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
375 for (const LiveInterval::SubRange &SR : LI.subranges()) {
376 SubRanges.push_back(std::make_pair(&SR, 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.
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(Idx);
413 if (MRI->reg_nodbg_empty(VirtReg))
414 continue;
415 LiveInterval &LI = LIS->getInterval(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);
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.
435 for (const auto &Seg : LI) {
436 I = Indexes->getMBBLowerBound(I, 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)
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(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(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(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(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(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(1).isUndef() || MI.getNumOperands() > 2) {
499 MI.setDesc(TII->get(TargetOpcode::KILL));
500 LLVM_DEBUG(dbgs() << " replace by: " << MI);
501 return;
502 }
503
504 if (Indexes)
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()) {
520
521 // Only do this when the complete bundle is made out of COPYs and KILLs.
522 MachineBasicBlock &MBB = *MI.getParent();
524 std::next(MI.getReverseIterator()), E = MBB.instr_rend();
525 I != E && I->isBundledWithSucc(); ++I) {
526 if (!I->isCopy() && !I->isKill())
527 return;
528 MIs.push_back(&*I);
529 }
530 MachineInstr *FirstMI = MIs.back();
531
532 auto anyRegsAlias = [](const MachineInstr *Dst,
534 const TargetRegisterInfo *TRI) {
535 for (const MachineInstr *Src : Srcs)
536 if (Src != Dst)
537 if (TRI->regsOverlap(Dst->getOperand(0).getReg(),
538 Src->getOperand(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(E), TRI)) {
549 if (I + 1 != E)
550 std::swap(MIs[I], MIs[E - 1]);
551 --E;
552 }
553 if (PrevE == E) {
554 MF->getFunction().getContext().emitError(
555 "register rewriting failed: cycle in copy bundle");
556 break;
557 }
558 }
559
560 MachineInstr *BundleStart = FirstMI;
561 for (MachineInstr *BundledMI : llvm::reverse(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(BundleStart, BundledMI);
568 } else if (BundledMI->isBundledWithSucc()) {
569 BundledMI->unbundleFromSucc();
570 BundleStart = &*std::next(BundledMI->getIterator());
571 }
572
573 if (Indexes && BundledMI != FirstMI)
574 Indexes->insertMachineInstrInMaps(*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(MI);
585 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
586 SlotIndex AfterMIDefs = MIIndex.getBoundaryIndex();
587 for (MCRegUnit Unit : TRI->regunits(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(AfterMIDefs) && UnitRange.liveAt(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(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(SR, &MBB)) {
618 for (const MachineBasicBlock *Succ : MBB.successors()) {
619 if (LIS->isLiveInToMBB(SR, Succ))
620 LiveOutUndefLanes |= NeedImpDefLanes;
621 }
622 }
623 }
624
625 SlotIndex MIIndex = LIS->getInstructionIndex(MI);
626 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
627 LaneBitmask InterferingLanes =
628 LRM->checkInterferenceLanes(BeforeMIUses, 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));
649 for (MachineOperand &MO : MI.operands()) {
650 // Make sure MRI knows about registers clobbered by regmasks.
651 if (MO.isRegMask())
652 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
653
654 if (!MO.isReg() || !MO.getReg().isVirtual())
655 continue;
656 Register VirtReg = MO.getReg();
657 MCRegister PhysReg = VRM->getPhys(VirtReg);
658 if (!PhysReg)
659 continue;
660
661 assert(Register(PhysReg).isPhysical());
662
663 RewriteRegs.insert(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(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, PhysReg)))
675 SuperKills.push_back(PhysReg);
676
677 if (MO.isDef()) {
678 // Also add implicit defs for the super-register.
679 if (MO.isDead())
680 SuperDeads.push_back(PhysReg);
681 else
682 SuperDefs.push_back(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(VirtReg);
695
696 LaneBitmask LiveOutUndefLanes =
697 liveOutUndefPhiLanesForUndefSubregDef(LI, *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(MRI->getRegClass(VirtReg),
705 LiveOutUndefLanes,
706 CoveringIndexes))
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(TRI->getSubReg(PhysReg, 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(PhysReg, 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(SuperKills.pop_back_val(), TRI, true);
746
747 while (!SuperDeads.empty())
748 MI.addRegisterDead(SuperDeads.pop_back_val(), TRI, true);
749
750 while (!SuperDefs.empty())
751 MI.addRegisterDefined(SuperDefs.pop_back_val(), 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(PhysReg)) {
767 LIS->removeRegUnit(Unit);
768 }
769 }
770 }
771
772 RewriteRegs.clear();
773}
774
777 OS << "virt-reg-rewriter";
778 if (!ClearVirtRegs)
779 OS << "<no-clear-vregs>";
780}
781
783 return new VirtRegRewriterLegacy(ClearVirtRegs);
784}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator MBBI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define I(x, y, z)
Definition MD5.cpp:58
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
ModuleAnalysisManager MAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition PassSupport.h:56
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:167
#define LLVM_DEBUG(...)
Definition Debug.h:119
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
Implements a dense probed hash-table based set.
Definition DenseSet.h:261
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:314
void emitDebugValues(VirtRegMap *VRM)
emitDebugValues - Emit new DBG_VALUE instructions reflecting the changes that happened during registe...
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
iterator_range< subrange_iterator > subranges()
LLVM_ABI void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
LiveInterval & getInterval(Register Reg)
LLVM_ABI MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
void removeRegUnit(unsigned Unit)
Remove computed live range for register unit Unit.
bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
This class represents the liveness of a register, stack slot, etc.
Segments::const_iterator const_iterator
bool liveAt(SlotIndex index) const
bool empty() const
LaneBitmask checkInterferenceLanes(SlotIndex Start, SlotIndex End, MCRegister PhysReg)
Check for interference in the segment [Start, End) that may prevent assignment to PhysReg,...
Wrapper class representing physical registers. Should be passed by value.
Definition MCRegister.h:33
constexpr bool isValid() const
Definition MCRegister.h:76
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition MCRegister.h:64
An RAII based helper class to modify MachineFunctionProperties when running pass.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
LLVM_ABI void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
LLVM_ABI void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
reverse_instr_iterator instr_rend()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
iterator_range< succ_iterator > successors()
Instructions::reverse_iterator reverse_instr_iterator
LLVM_ABI int CreateSpillStackObject(uint64_t Size, Align Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
BasicBlockListType::iterator iterator
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
void setIsInternalRead(bool Val=true)
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
LLVM_ABI void setIsRenamable(bool Val=true)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:67
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Wrapper class representing virtual and physical registers.
Definition Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition Register.h:67
constexpr bool isValid() const
Definition Register.h:107
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:74
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:66
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
SlotIndexes pass.
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
MBBIndexIterator getMBBLowerBound(MBBIndexIterator Start, SlotIndex Idx) const
Get an iterator pointing to the first IdxMBBPair with SlotIndex greater than or equal to Idx.
LLVM_ABI void removeSingleMachineInstrFromMaps(MachineInstr &MI)
Removes a single machine instruction MI from the mapping.
MBBIndexIterator MBBIndexBegin() const
Returns an iterator for the begin of the idx2MBBMap.
MBBIndexIterator MBBIndexEnd() const
Return an iterator for the end of the idx2MBBMap.
SmallVectorImpl< IdxMBBPair >::const_iterator MBBIndexIterator
Iterator over the idx2MBBMap (sorted pairs of slot index of basic block begin and basic block)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Definition StringRef.h:55
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
LLVM_ABI VirtRegMap run(MachineFunction &MF, MachineFunctionAnalysisManager &MAM)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
static LLVM_ABI char ID
Definition VirtRegMap.h:198
LLVM_ABI bool hasKnownPreference(Register VirtReg) const
returns true if VirtReg has a known preferred register.
LLVM_ABI int assignVirt2StackSlot(Register virtReg)
create a mapping for the specifed virtual register to the next available stack slot
void clearAllVirt()
clears all virtual to physical register mappings
Definition VirtRegMap.h:125
LLVM_ABI void init(MachineFunction &MF)
LLVM_ABI bool hasPreferredPhys(Register VirtReg) const
returns true if VirtReg is assigned to its preferred physreg.
LLVM_ABI void dump() const
MachineRegisterInfo & getRegInfo() const
Definition VirtRegMap.h:80
LLVM_ABI void assignVirt2Phys(Register virtReg, MCRegister physReg)
creates a mapping for the specified virtual register to the specified physical register
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition VirtRegMap.h:91
LLVM_ABI void print(raw_ostream &OS, const Module *M=nullptr) const
LLVM_ABI void grow()
bool hasPhys(Register virtReg) const
returns true if the specified virtual register is mapped to a physical register
Definition VirtRegMap.h:87
static constexpr int NO_STACK_SLOT
Definition VirtRegMap.h:66
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)>) const
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:646
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
auto reverse(ContainerTy &&C)
Definition STLExtras.h:420
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
unsigned MCRegUnit
Register units are used to compute register aliasing.
Definition MCRegister.h:30
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
Definition ModRef.h:71
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI char & VirtRegRewriterID
VirtRegRewriter pass.
LLVM_ABI FunctionPass * createVirtRegRewriter(bool ClearVirtRegs=true)
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:853
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
constexpr bool none() const
Definition LaneBitmask.h:52
constexpr bool any() const
Definition LaneBitmask.h:53