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