1193323Sed//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the VirtRegMap class. 11193323Sed// 12203954Srdivacky// It also contains implementations of the Spiller interface, which, given a 13193323Sed// virtual register map and a machine function, eliminates all virtual 14193323Sed// references by replacing them with physical register references - adding spill 15193323Sed// code as necessary. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19235633Sdim#define DEBUG_TYPE "regalloc" 20252723Sdim#include "llvm/CodeGen/VirtRegMap.h" 21245431Sdim#include "LiveDebugVariables.h" 22252723Sdim#include "llvm/ADT/STLExtras.h" 23252723Sdim#include "llvm/ADT/Statistic.h" 24245431Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 25245431Sdim#include "llvm/CodeGen/LiveStackAnalysis.h" 26193323Sed#include "llvm/CodeGen/MachineFrameInfo.h" 27193323Sed#include "llvm/CodeGen/MachineFunction.h" 28193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 29193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 30245431Sdim#include "llvm/CodeGen/Passes.h" 31263509Sdim#include "llvm/IR/Function.h" 32193323Sed#include "llvm/Support/CommandLine.h" 33193323Sed#include "llvm/Support/Compiler.h" 34193323Sed#include "llvm/Support/Debug.h" 35198090Srdivacky#include "llvm/Support/raw_ostream.h" 36252723Sdim#include "llvm/Target/TargetInstrInfo.h" 37252723Sdim#include "llvm/Target/TargetMachine.h" 38252723Sdim#include "llvm/Target/TargetRegisterInfo.h" 39193323Sed#include <algorithm> 40193323Sedusing namespace llvm; 41193323Sed 42226890SdimSTATISTIC(NumSpillSlots, "Number of spill slots allocated"); 43226890SdimSTATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 44193323Sed 45193323Sed//===----------------------------------------------------------------------===// 46193323Sed// VirtRegMap implementation 47193323Sed//===----------------------------------------------------------------------===// 48193323Sed 49193323Sedchar VirtRegMap::ID = 0; 50193323Sed 51218893SdimINITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 52193323Sed 53193323Sedbool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 54194612Sed MRI = &mf.getRegInfo(); 55193323Sed TII = mf.getTarget().getInstrInfo(); 56193323Sed TRI = mf.getTarget().getRegisterInfo(); 57193323Sed MF = &mf; 58198892Srdivacky 59193323Sed Virt2PhysMap.clear(); 60193323Sed Virt2StackSlotMap.clear(); 61193323Sed Virt2SplitMap.clear(); 62193323Sed 63193323Sed grow(); 64193323Sed return false; 65193323Sed} 66193323Sed 67193323Sedvoid VirtRegMap::grow() { 68218893Sdim unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 69218893Sdim Virt2PhysMap.resize(NumRegs); 70218893Sdim Virt2StackSlotMap.resize(NumRegs); 71218893Sdim Virt2SplitMap.resize(NumRegs); 72193323Sed} 73193323Sed 74218893Sdimunsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 75218893Sdim int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 76218893Sdim RC->getAlignment()); 77226890Sdim ++NumSpillSlots; 78218893Sdim return SS; 79218893Sdim} 80218893Sdim 81252723Sdimbool VirtRegMap::hasPreferredPhys(unsigned VirtReg) { 82252723Sdim unsigned Hint = MRI->getSimpleHint(VirtReg); 83252723Sdim if (!Hint) 84252723Sdim return 0; 85252723Sdim if (TargetRegisterInfo::isVirtualRegister(Hint)) 86252723Sdim Hint = getPhys(Hint); 87252723Sdim return getPhys(VirtReg) == Hint; 88194612Sed} 89194612Sed 90252723Sdimbool VirtRegMap::hasKnownPreference(unsigned VirtReg) { 91252723Sdim std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg); 92252723Sdim if (TargetRegisterInfo::isPhysicalRegister(Hint.second)) 93252723Sdim return true; 94252723Sdim if (TargetRegisterInfo::isVirtualRegister(Hint.second)) 95252723Sdim return hasPhys(Hint.second); 96252723Sdim return false; 97252723Sdim} 98252723Sdim 99193323Sedint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 100193323Sed assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 101193323Sed assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 102193323Sed "attempt to assign stack slot to already spilled register"); 103193323Sed const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 104218893Sdim return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 105193323Sed} 106193323Sed 107193323Sedvoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 108193323Sed assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 109193323Sed assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 110193323Sed "attempt to assign stack slot to already spilled register"); 111193323Sed assert((SS >= 0 || 112193323Sed (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 113193323Sed "illegal fixed frame index"); 114193323Sed Virt2StackSlotMap[virtReg] = SS; 115193323Sed} 116193323Sed 117245431Sdimvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 118245431Sdim OS << "********** REGISTER MAP **********\n"; 119245431Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 120245431Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 121245431Sdim if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 122245431Sdim OS << '[' << PrintReg(Reg, TRI) << " -> " 123245431Sdim << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 124245431Sdim << MRI->getRegClass(Reg)->getName() << "\n"; 125245431Sdim } 126245431Sdim } 127245431Sdim 128245431Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 129245431Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 130245431Sdim if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 131245431Sdim OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 132245431Sdim << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 133245431Sdim } 134245431Sdim } 135245431Sdim OS << '\n'; 136245431Sdim} 137245431Sdim 138245431Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 139245431Sdimvoid VirtRegMap::dump() const { 140245431Sdim print(dbgs()); 141245431Sdim} 142245431Sdim#endif 143245431Sdim 144245431Sdim//===----------------------------------------------------------------------===// 145245431Sdim// VirtRegRewriter 146245431Sdim//===----------------------------------------------------------------------===// 147245431Sdim// 148245431Sdim// The VirtRegRewriter is the last of the register allocator passes. 149245431Sdim// It rewrites virtual registers to physical registers as specified in the 150245431Sdim// VirtRegMap analysis. It also updates live-in information on basic blocks 151245431Sdim// according to LiveIntervals. 152245431Sdim// 153245431Sdimnamespace { 154245431Sdimclass VirtRegRewriter : public MachineFunctionPass { 155245431Sdim MachineFunction *MF; 156245431Sdim const TargetMachine *TM; 157245431Sdim const TargetRegisterInfo *TRI; 158245431Sdim const TargetInstrInfo *TII; 159245431Sdim MachineRegisterInfo *MRI; 160245431Sdim SlotIndexes *Indexes; 161245431Sdim LiveIntervals *LIS; 162245431Sdim VirtRegMap *VRM; 163245431Sdim 164245431Sdim void rewrite(); 165245431Sdim void addMBBLiveIns(); 166245431Sdimpublic: 167245431Sdim static char ID; 168245431Sdim VirtRegRewriter() : MachineFunctionPass(ID) {} 169245431Sdim 170245431Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 171245431Sdim 172245431Sdim virtual bool runOnMachineFunction(MachineFunction&); 173245431Sdim}; 174245431Sdim} // end anonymous namespace 175245431Sdim 176245431Sdimchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 177245431Sdim 178245431SdimINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 179245431Sdim "Virtual Register Rewriter", false, false) 180245431SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 181245431SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 182245431SdimINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 183245431SdimINITIALIZE_PASS_DEPENDENCY(LiveStacks) 184245431SdimINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 185245431SdimINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 186245431Sdim "Virtual Register Rewriter", false, false) 187245431Sdim 188245431Sdimchar VirtRegRewriter::ID = 0; 189245431Sdim 190245431Sdimvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 191245431Sdim AU.setPreservesCFG(); 192245431Sdim AU.addRequired<LiveIntervals>(); 193245431Sdim AU.addRequired<SlotIndexes>(); 194245431Sdim AU.addPreserved<SlotIndexes>(); 195245431Sdim AU.addRequired<LiveDebugVariables>(); 196245431Sdim AU.addRequired<LiveStacks>(); 197245431Sdim AU.addPreserved<LiveStacks>(); 198245431Sdim AU.addRequired<VirtRegMap>(); 199245431Sdim MachineFunctionPass::getAnalysisUsage(AU); 200245431Sdim} 201245431Sdim 202245431Sdimbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 203245431Sdim MF = &fn; 204245431Sdim TM = &MF->getTarget(); 205245431Sdim TRI = TM->getRegisterInfo(); 206245431Sdim TII = TM->getInstrInfo(); 207245431Sdim MRI = &MF->getRegInfo(); 208245431Sdim Indexes = &getAnalysis<SlotIndexes>(); 209245431Sdim LIS = &getAnalysis<LiveIntervals>(); 210245431Sdim VRM = &getAnalysis<VirtRegMap>(); 211218893Sdim DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 212218893Sdim << "********** Function: " 213245431Sdim << MF->getName() << '\n'); 214245431Sdim DEBUG(VRM->dump()); 215245431Sdim 216245431Sdim // Add kill flags while we still have virtual registers. 217245431Sdim LIS->addKillFlags(VRM); 218245431Sdim 219245431Sdim // Live-in lists on basic blocks are required for physregs. 220245431Sdim addMBBLiveIns(); 221245431Sdim 222245431Sdim // Rewrite virtual registers. 223245431Sdim rewrite(); 224245431Sdim 225245431Sdim // Write out new DBG_VALUE instructions. 226245431Sdim getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 227245431Sdim 228245431Sdim // All machine operands and other references to virtual registers have been 229245431Sdim // replaced. Remove the virtual registers and release all the transient data. 230245431Sdim VRM->clearAllVirt(); 231245431Sdim MRI->clearVirtRegs(); 232245431Sdim return true; 233245431Sdim} 234245431Sdim 235245431Sdim// Compute MBB live-in lists from virtual register live ranges and their 236245431Sdim// assignments. 237245431Sdimvoid VirtRegRewriter::addMBBLiveIns() { 238245431Sdim SmallVector<MachineBasicBlock*, 16> LiveIn; 239245431Sdim for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 240245431Sdim unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 241245431Sdim if (MRI->reg_nodbg_empty(VirtReg)) 242245431Sdim continue; 243245431Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 244245431Sdim if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 245245431Sdim continue; 246245431Sdim // This is a virtual register that is live across basic blocks. Its 247245431Sdim // assigned PhysReg must be marked as live-in to those blocks. 248245431Sdim unsigned PhysReg = VRM->getPhys(VirtReg); 249245431Sdim assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 250245431Sdim 251245431Sdim // Scan the segments of LI. 252245431Sdim for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 253245431Sdim ++I) { 254245431Sdim if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 255245431Sdim continue; 256245431Sdim for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 257245431Sdim if (!LiveIn[i]->isLiveIn(PhysReg)) 258245431Sdim LiveIn[i]->addLiveIn(PhysReg); 259245431Sdim LiveIn.clear(); 260245431Sdim } 261245431Sdim } 262245431Sdim} 263245431Sdim 264245431Sdimvoid VirtRegRewriter::rewrite() { 265221345Sdim SmallVector<unsigned, 8> SuperDeads; 266221345Sdim SmallVector<unsigned, 8> SuperDefs; 267218893Sdim SmallVector<unsigned, 8> SuperKills; 268263509Sdim SmallPtrSet<const MachineInstr *, 4> NoReturnInsts; 269218893Sdim 270218893Sdim for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 271218893Sdim MBBI != MBBE; ++MBBI) { 272218893Sdim DEBUG(MBBI->print(dbgs(), Indexes)); 273263509Sdim bool IsExitBB = MBBI->succ_empty(); 274235633Sdim for (MachineBasicBlock::instr_iterator 275235633Sdim MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 276218893Sdim MachineInstr *MI = MII; 277218893Sdim ++MII; 278218893Sdim 279263509Sdim // Check if this instruction is a call to a noreturn function. 280263509Sdim // If so, all the definitions set by this instruction can be ignored. 281263509Sdim if (IsExitBB && MI->isCall()) 282263509Sdim for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 283263509Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 284263509Sdim MachineOperand &MO = *MOI; 285263509Sdim if (!MO.isGlobal()) 286263509Sdim continue; 287263509Sdim const Function *Func = dyn_cast<Function>(MO.getGlobal()); 288263509Sdim if (!Func || !Func->hasFnAttribute(Attribute::NoReturn) || 289263509Sdim // We need to keep correct unwind information 290263509Sdim // even if the function will not return, since the 291263509Sdim // runtime may need it. 292263509Sdim !Func->hasFnAttribute(Attribute::NoUnwind)) 293263509Sdim continue; 294263509Sdim NoReturnInsts.insert(MI); 295263509Sdim break; 296263509Sdim } 297263509Sdim 298218893Sdim for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 299218893Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 300218893Sdim MachineOperand &MO = *MOI; 301235633Sdim 302235633Sdim // Make sure MRI knows about registers clobbered by regmasks. 303235633Sdim if (MO.isRegMask()) 304235633Sdim MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 305235633Sdim 306218893Sdim if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 307218893Sdim continue; 308218893Sdim unsigned VirtReg = MO.getReg(); 309245431Sdim unsigned PhysReg = VRM->getPhys(VirtReg); 310245431Sdim assert(PhysReg != VirtRegMap::NO_PHYS_REG && 311245431Sdim "Instruction uses unmapped VirtReg"); 312245431Sdim assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 313218893Sdim 314218893Sdim // Preserve semantics of sub-register operands. 315218893Sdim if (MO.getSubReg()) { 316218893Sdim // A virtual register kill refers to the whole register, so we may 317226890Sdim // have to add <imp-use,kill> operands for the super-register. A 318226890Sdim // partial redef always kills and redefines the super-register. 319226890Sdim if (MO.readsReg() && (MO.isDef() || MO.isKill())) 320226890Sdim SuperKills.push_back(PhysReg); 321218893Sdim 322226890Sdim if (MO.isDef()) { 323226890Sdim // The <def,undef> flag only makes sense for sub-register defs, and 324226890Sdim // we are substituting a full physreg. An <imp-use,kill> operand 325226890Sdim // from the SuperKills list will represent the partial read of the 326226890Sdim // super-register. 327226890Sdim MO.setIsUndef(false); 328226890Sdim 329226890Sdim // Also add implicit defs for the super-register. 330226890Sdim if (MO.isDead()) 331226890Sdim SuperDeads.push_back(PhysReg); 332226890Sdim else 333226890Sdim SuperDefs.push_back(PhysReg); 334226890Sdim } 335226890Sdim 336218893Sdim // PhysReg operands cannot have subregister indexes. 337218893Sdim PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 338218893Sdim assert(PhysReg && "Invalid SubReg for physical register"); 339218893Sdim MO.setSubReg(0); 340218893Sdim } 341218893Sdim // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 342218893Sdim // we need the inlining here. 343218893Sdim MO.setReg(PhysReg); 344218893Sdim } 345218893Sdim 346218893Sdim // Add any missing super-register kills after rewriting the whole 347218893Sdim // instruction. 348218893Sdim while (!SuperKills.empty()) 349218893Sdim MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 350218893Sdim 351221345Sdim while (!SuperDeads.empty()) 352221345Sdim MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 353221345Sdim 354221345Sdim while (!SuperDefs.empty()) 355221345Sdim MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 356221345Sdim 357218893Sdim DEBUG(dbgs() << "> " << *MI); 358218893Sdim 359218893Sdim // Finally, remove any identity copies. 360218893Sdim if (MI->isIdentityCopy()) { 361223017Sdim ++NumIdCopies; 362221345Sdim if (MI->getNumOperands() == 2) { 363221345Sdim DEBUG(dbgs() << "Deleting identity copy.\n"); 364221345Sdim if (Indexes) 365221345Sdim Indexes->removeMachineInstrFromMaps(MI); 366221345Sdim // It's safe to erase MI because MII has already been incremented. 367221345Sdim MI->eraseFromParent(); 368221345Sdim } else { 369221345Sdim // Transform identity copy to a KILL to deal with subregisters. 370221345Sdim MI->setDesc(TII->get(TargetOpcode::KILL)); 371221345Sdim DEBUG(dbgs() << "Identity copy: " << *MI); 372221345Sdim } 373218893Sdim } 374218893Sdim } 375218893Sdim } 376218893Sdim 377218893Sdim // Tell MRI about physical registers in use. 378263509Sdim if (NoReturnInsts.empty()) { 379263509Sdim for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 380263509Sdim if (!MRI->reg_nodbg_empty(Reg)) 381263509Sdim MRI->setPhysRegUsed(Reg); 382263509Sdim } else { 383263509Sdim for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) { 384263509Sdim if (MRI->reg_nodbg_empty(Reg)) 385263509Sdim continue; 386263509Sdim // Check if this register has a use that will impact the rest of the 387263509Sdim // code. Uses in debug and noreturn instructions do not impact the 388263509Sdim // generated code. 389263509Sdim for (MachineRegisterInfo::reg_nodbg_iterator It = 390263509Sdim MRI->reg_nodbg_begin(Reg), 391263509Sdim EndIt = MRI->reg_nodbg_end(); It != EndIt; ++It) { 392263509Sdim if (!NoReturnInsts.count(&(*It))) { 393263509Sdim MRI->setPhysRegUsed(Reg); 394263509Sdim break; 395263509Sdim } 396263509Sdim } 397263509Sdim } 398263509Sdim } 399218893Sdim} 400