785 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the VirtRegMap class.10//11// It also contains implementations of the Spiller interface, which, given a12// virtual register map and a machine function, eliminates all virtual13// references by replacing them with physical register references - adding spill14// 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 implementation58//===----------------------------------------------------------------------===//59 60char VirtRegMapWrapperLegacy::ID = 0;61 62INITIALIZE_PASS(VirtRegMapWrapperLegacy, "virtregmap", "Virtual Register Map",63 false, true)64 65void VirtRegMap::init(MachineFunction &mf) {66 MRI = &mf.getRegInfo();67 TII = mf.getSubtarget().getInstrInfo();68 TRI = mf.getSubtarget().getRegisterInfo();69 MF = &mf;70 71 Virt2PhysMap.clear();72 Virt2StackSlotMap.clear();73 Virt2SplitMap.clear();74 Virt2ShapeMap.clear();75 76 grow();77}78 79void VirtRegMap::grow() {80 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();81 Virt2PhysMap.resize(NumRegs);82 Virt2StackSlotMap.resize(NumRegs);83 Virt2SplitMap.resize(NumRegs);84}85 86void VirtRegMap::assignVirt2Phys(Register virtReg, MCRegister physReg) {87 assert(virtReg.isVirtual() && physReg.isPhysical());88 assert(!Virt2PhysMap[virtReg] &&89 "attempt to assign physical register to already mapped "90 "virtual register");91 assert(!getRegInfo().isReserved(physReg) &&92 "Attempt to map virtReg to a reserved physReg");93 Virt2PhysMap[virtReg] = physReg;94}95 96unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {97 unsigned Size = TRI->getSpillSize(*RC);98 Align Alignment = TRI->getSpillAlign(*RC);99 // Set preferred alignment if we are still able to realign the stack100 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 110bool VirtRegMap::hasPreferredPhys(Register VirtReg) const {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 119bool VirtRegMap::hasKnownPreference(Register VirtReg) const {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 128int VirtRegMap::assignVirt2StackSlot(Register virtReg) {129 assert(virtReg.isVirtual());130 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&131 "attempt to assign stack slot to already spilled register");132 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);133 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);134}135 136void VirtRegMap::assignVirt2StackSlot(Register virtReg, int SS) {137 assert(virtReg.isVirtual());138 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&139 "attempt to assign stack slot to already spilled register");140 assert((SS >= 0 ||141 (SS >= MF->getFrameInfo().getObjectIndexBegin())) &&142 "illegal fixed frame index");143 Virt2StackSlotMap[virtReg] = SS;144}145 146void VirtRegMap::print(raw_ostream &OS, const Module*) const {147 OS << "********** REGISTER MAP **********\n";148 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {149 Register Reg = Register::index2VirtReg(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) {158 Register Reg = Register::index2VirtReg(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)168LLVM_DUMP_METHOD void VirtRegMap::dump() const {169 print(dbgs());170}171#endif172 173AnalysisKey VirtRegMapAnalysis::Key;174 175PreservedAnalyses176VirtRegMapPrinterPass::run(MachineFunction &MF,177 MachineFunctionAnalysisManager &MFAM) {178 OS << MFAM.getResult<VirtRegMapAnalysis>(MF);179 return PreservedAnalyses::all();180}181 182VirtRegMap VirtRegMapAnalysis::run(MachineFunction &MF,183 MachineFunctionAnalysisManager &MAM) {184 VirtRegMap VRM;185 VRM.init(MF);186 return VRM;187}188 189//===----------------------------------------------------------------------===//190// VirtRegRewriter191//===----------------------------------------------------------------------===//192//193// The VirtRegRewriter is the last of the register allocator passes.194// It rewrites virtual registers to physical registers as specified in the195// VirtRegMap analysis. It also updates live-in information on basic blocks196// 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 namespace255 256char VirtRegRewriterLegacy::ID = 0;257 258char &llvm::VirtRegRewriterID = VirtRegRewriterLegacy::ID;259 260INITIALIZE_PASS_BEGIN(VirtRegRewriterLegacy, "virtregrewriter",261 "Virtual Register Rewriter", false, false)262INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)263INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)264INITIALIZE_PASS_DEPENDENCY(LiveDebugVariablesWrapperLegacy)265INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)266INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)267INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)268INITIALIZE_PASS_END(VirtRegRewriterLegacy, "virtregrewriter",269 "Virtual Register Rewriter", false, false)270 271void VirtRegRewriterLegacy::getAnalysisUsage(AnalysisUsage &AU) const {272 AU.setPreservesCFG();273 AU.addRequired<LiveIntervalsWrapperPass>();274 AU.addPreserved<LiveIntervalsWrapperPass>();275 AU.addRequired<SlotIndexesWrapperPass>();276 AU.addPreserved<SlotIndexesWrapperPass>();277 AU.addRequired<LiveDebugVariablesWrapperLegacy>();278 AU.addRequired<LiveStacksWrapperLegacy>();279 AU.addPreserved<LiveStacksWrapperLegacy>();280 AU.addRequired<VirtRegMapWrapperLegacy>();281 AU.addRequired<LiveRegMatrixWrapperLegacy>();282 283 if (!ClearVirtRegs)284 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();285 286 MachineFunctionPass::getAnalysisUsage(AU);287}288 289bool VirtRegRewriterLegacy::runOnMachineFunction(MachineFunction &MF) {290 VirtRegMap &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM();291 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();292 LiveRegMatrix &LRM = getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM();293 SlotIndexes &Indexes = getAnalysis<SlotIndexesWrapperPass>().getSI();294 LiveDebugVariables &DebugVars =295 getAnalysis<LiveDebugVariablesWrapperLegacy>().getLDV();296 297 VirtRegRewriter R(ClearVirtRegs, &Indexes, &LIS, &LRM, &VRM, &DebugVars);298 return R.run(MF);299}300 301PreservedAnalyses302VirtRegRewriterPass::run(MachineFunction &MF,303 MachineFunctionAnalysisManager &MFAM) {304 MFPropsModifier _(*this, MF);305 306 VirtRegMap &VRM = MFAM.getResult<VirtRegMapAnalysis>(MF);307 LiveIntervals &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF);308 LiveRegMatrix &LRM = MFAM.getResult<LiveRegMatrixAnalysis>(MF);309 SlotIndexes &Indexes = MFAM.getResult<SlotIndexesAnalysis>(MF);310 LiveDebugVariables &DebugVars =311 MFAM.getResult<LiveDebugVariablesAnalysis>(MF);312 313 VirtRegRewriter R(ClearVirtRegs, &Indexes, &LIS, &LRM, &VRM, &DebugVars);314 if (!R.run(MF))315 return PreservedAnalyses::all();316 317 auto PA = getMachineFunctionPassPreservedAnalyses();318 PA.preserveSet<CFGAnalyses>();319 PA.preserve<LiveIntervalsAnalysis>();320 PA.preserve<SlotIndexesAnalysis>();321 PA.preserve<LiveStacksAnalysis>();322 // LiveDebugVariables is preserved by default, so clear it323 // if this VRegRewriter is the last one in the pipeline.324 if (ClearVirtRegs)325 PA.abandon<LiveDebugVariablesAnalysis>();326 return PA;327}328 329bool VirtRegRewriter::run(MachineFunction &fn) {330 MF = &fn;331 TRI = MF->getSubtarget().getRegisterInfo();332 TII = MF->getSubtarget().getInstrInfo();333 MRI = &MF->getRegInfo();334 335 LLVM_DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"336 << "********** Function: " << MF->getName() << '\n');337 LLVM_DEBUG(VRM->dump());338 339 // Add kill flags while we still have virtual registers.340 LIS->addKillFlags(VRM);341 342 // Live-in lists on basic blocks are required for physregs.343 addMBBLiveIns();344 345 // Rewrite virtual registers.346 rewrite();347 348 if (ClearVirtRegs) {349 // Write out new DBG_VALUE instructions.350 351 // We only do this if ClearVirtRegs is specified since this should be the352 // 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 been356 // replaced. Remove the virtual registers and release all the transient data.357 VRM->clearAllVirt();358 MRI->clearVirtRegs();359 }360 361 return true;362}363 364void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,365 MCRegister PhysReg) const {366 assert(!LI.empty());367 assert(LI.hasSubRanges());368 369 using SubRangeIteratorPair =370 std::pair<const LiveInterval::SubRange *, LiveInterval::const_iterator>;371 372 SmallVector<SubRangeIteratorPair, 4> SubRanges;373 SlotIndex First;374 SlotIndex Last;375 for (const LiveInterval::SubRange &SR : LI.subranges()) {376 SubRanges.push_back(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 while384 // simultaneously advancing an iterator for each subrange.385 for (SlotIndexes::MBBIndexIterator MBBI = Indexes->getMBBLowerBound(First);386 MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) {387 SlotIndex MBBBegin = MBBI->first;388 // Advance all subrange iterators so that their end position is just389 // 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 their409// 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. Its419 // 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 register423 // 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 both433 // sorted by slot indexes.434 SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin();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 in446 // each MBB's LiveIns set before calling addLiveIn on them.447 for (MachineBasicBlock &MBB : *MF)448 MBB.sortUniqueLiveIns();449}450 451/// Returns true if the given machine operand \p MO only reads undefined lanes.452/// The function only works for use operands with a subregister set.453bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {454 // Shortcut if the operand is already marked undef.455 if (MO.isUndef())456 return true;457 458 Register Reg = MO.getReg();459 const LiveInterval &LI = LIS->getInterval(Reg);460 const MachineInstr &MI = *MO.getParent();461 SlotIndex BaseIndex = LIS->getInstructionIndex(MI);462 // This code is only meant to handle reading undefined subregisters which463 // 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 rewrite486 // 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 %r0494 // %al = COPY %al, implicit-def %eax495 // give us additional liveness information: The target (super-)register496 // must not be valid before this point. Replace the COPY with a KILL497 // 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)505 Indexes->removeSingleMachineInstrFromMaps(MI);506 MI.eraseFromBundle();507 LLVM_DEBUG(dbgs() << " deleted.\n");508}509 510/// The liverange splitting logic sometimes produces bundles of copies when511/// subregisters are involved. Expand these into a sequence of copy instructions512/// after processing the last in the bundle. Does not update LiveIntervals513/// which we shouldn't need for this instruction anymore.514void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {515 if (!MI.isCopy() && !MI.isKill())516 return;517 518 if (MI.isBundledWithPred() && !MI.isBundledWithSucc()) {519 SmallVector<MachineInstr *, 2> MIs({&MI});520 521 // Only do this when the complete bundle is made out of COPYs and KILLs.522 MachineBasicBlock &MBB = *MI.getParent();523 for (MachineBasicBlock::reverse_instr_iterator I =524 std::next(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,533 ArrayRef<MachineInstr *> Srcs,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 of544 // the source registers, try to schedule the instructions to avoid any545 // 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 the563 // bundle starts, otherwise, just unbundle it. When we get to the last564 // 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 that581/// 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 like592 // "RU = op RU" would match that description.593 // However, we know that we are trying to assess whether594 // 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 vreg596 // 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 to598 // 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 the606/// defining block for a register assignment for a subregister def. \p PhysReg607/// 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));648 for (MachineInstr &MI : llvm::make_early_inc_range(MBBI->instrs())) {649 for (MachineOperand &MO : MI.operands()) {650 // Make sure MRI knows about registers clobbered by regmasks.651 if (MO.isRegMask())652 MRI->addPhysRegsUsedFromRegMask(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 may671 // have to add implicit killed operands for the super-register. A672 // 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 else682 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 is688 // completely undefined (and we are not adding super-register689 // 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 lanes703 // are needed?704 if (!TRI->getCoveringSubRegIndexes(MRI->getRegClass(VirtReg),705 LiveOutUndefLanes,706 CoveringIndexes))707 llvm_unreachable(708 "cannot represent required subregister defs");709 710 // Try to represent the minimum needed live out def as a711 // sequence of subregister defs.712 //713 // FIXME: It would be better if we could directly represent714 // 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 for723 // sub-register defs, and we are substituting a full physreg. An724 // implicit killed operand from the SuperKills list will represent the725 // 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(), but737 // 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 whole743 // 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 were764 // 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 775void VirtRegRewriterPass::printPipeline(776 raw_ostream &OS, function_ref<StringRef(StringRef)>) const {777 OS << "virt-reg-rewriter";778 if (!ClearVirtRegs)779 OS << "<no-clear-vregs>";780}781 782FunctionPass *llvm::createVirtRegRewriter(bool ClearVirtRegs) {783 return new VirtRegRewriterLegacy(ClearVirtRegs);784}785