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 19234353Sdim#define DEBUG_TYPE "regalloc" 20249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 21239462Sdim#include "LiveDebugVariables.h" 22249423Sdim#include "llvm/ADT/STLExtras.h" 23249423Sdim#include "llvm/ADT/Statistic.h" 24239462Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 25243830Sdim#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" 30239462Sdim#include "llvm/CodeGen/Passes.h" 31263508Sdim#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" 36249423Sdim#include "llvm/Target/TargetInstrInfo.h" 37249423Sdim#include "llvm/Target/TargetMachine.h" 38249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 39193323Sed#include <algorithm> 40193323Sedusing namespace llvm; 41193323Sed 42226633SdimSTATISTIC(NumSpillSlots, "Number of spill slots allocated"); 43226633SdimSTATISTIC(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()); 77226633Sdim ++NumSpillSlots; 78218893Sdim return SS; 79218893Sdim} 80218893Sdim 81249423Sdimbool VirtRegMap::hasPreferredPhys(unsigned VirtReg) { 82249423Sdim unsigned Hint = MRI->getSimpleHint(VirtReg); 83249423Sdim if (!Hint) 84249423Sdim return 0; 85249423Sdim if (TargetRegisterInfo::isVirtualRegister(Hint)) 86249423Sdim Hint = getPhys(Hint); 87249423Sdim return getPhys(VirtReg) == Hint; 88194612Sed} 89194612Sed 90249423Sdimbool VirtRegMap::hasKnownPreference(unsigned VirtReg) { 91249423Sdim std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg); 92249423Sdim if (TargetRegisterInfo::isPhysicalRegister(Hint.second)) 93249423Sdim return true; 94249423Sdim if (TargetRegisterInfo::isVirtualRegister(Hint.second)) 95249423Sdim return hasPhys(Hint.second); 96249423Sdim return false; 97249423Sdim} 98249423Sdim 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 117239462Sdimvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 118239462Sdim OS << "********** REGISTER MAP **********\n"; 119239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 120239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 121239462Sdim if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 122239462Sdim OS << '[' << PrintReg(Reg, TRI) << " -> " 123239462Sdim << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 124239462Sdim << MRI->getRegClass(Reg)->getName() << "\n"; 125239462Sdim } 126239462Sdim } 127239462Sdim 128239462Sdim for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 129239462Sdim unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 130239462Sdim if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 131239462Sdim OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 132239462Sdim << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 133239462Sdim } 134239462Sdim } 135239462Sdim OS << '\n'; 136239462Sdim} 137239462Sdim 138243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 139239462Sdimvoid VirtRegMap::dump() const { 140239462Sdim print(dbgs()); 141239462Sdim} 142243830Sdim#endif 143239462Sdim 144239462Sdim//===----------------------------------------------------------------------===// 145239462Sdim// VirtRegRewriter 146239462Sdim//===----------------------------------------------------------------------===// 147239462Sdim// 148239462Sdim// The VirtRegRewriter is the last of the register allocator passes. 149239462Sdim// It rewrites virtual registers to physical registers as specified in the 150239462Sdim// VirtRegMap analysis. It also updates live-in information on basic blocks 151239462Sdim// according to LiveIntervals. 152239462Sdim// 153239462Sdimnamespace { 154239462Sdimclass VirtRegRewriter : public MachineFunctionPass { 155239462Sdim MachineFunction *MF; 156239462Sdim const TargetMachine *TM; 157239462Sdim const TargetRegisterInfo *TRI; 158239462Sdim const TargetInstrInfo *TII; 159239462Sdim MachineRegisterInfo *MRI; 160239462Sdim SlotIndexes *Indexes; 161239462Sdim LiveIntervals *LIS; 162239462Sdim VirtRegMap *VRM; 163239462Sdim 164239462Sdim void rewrite(); 165239462Sdim void addMBBLiveIns(); 166239462Sdimpublic: 167239462Sdim static char ID; 168239462Sdim VirtRegRewriter() : MachineFunctionPass(ID) {} 169239462Sdim 170239462Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 171239462Sdim 172239462Sdim virtual bool runOnMachineFunction(MachineFunction&); 173239462Sdim}; 174239462Sdim} // end anonymous namespace 175239462Sdim 176239462Sdimchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 177239462Sdim 178239462SdimINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 179239462Sdim "Virtual Register Rewriter", false, false) 180239462SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 181239462SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 182239462SdimINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 183243830SdimINITIALIZE_PASS_DEPENDENCY(LiveStacks) 184239462SdimINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 185239462SdimINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 186239462Sdim "Virtual Register Rewriter", false, false) 187239462Sdim 188239462Sdimchar VirtRegRewriter::ID = 0; 189239462Sdim 190239462Sdimvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 191239462Sdim AU.setPreservesCFG(); 192239462Sdim AU.addRequired<LiveIntervals>(); 193239462Sdim AU.addRequired<SlotIndexes>(); 194239462Sdim AU.addPreserved<SlotIndexes>(); 195239462Sdim AU.addRequired<LiveDebugVariables>(); 196243830Sdim AU.addRequired<LiveStacks>(); 197243830Sdim AU.addPreserved<LiveStacks>(); 198239462Sdim AU.addRequired<VirtRegMap>(); 199239462Sdim MachineFunctionPass::getAnalysisUsage(AU); 200239462Sdim} 201239462Sdim 202239462Sdimbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 203239462Sdim MF = &fn; 204239462Sdim TM = &MF->getTarget(); 205239462Sdim TRI = TM->getRegisterInfo(); 206239462Sdim TII = TM->getInstrInfo(); 207239462Sdim MRI = &MF->getRegInfo(); 208239462Sdim Indexes = &getAnalysis<SlotIndexes>(); 209239462Sdim LIS = &getAnalysis<LiveIntervals>(); 210239462Sdim VRM = &getAnalysis<VirtRegMap>(); 211218893Sdim DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 212218893Sdim << "********** Function: " 213243830Sdim << MF->getName() << '\n'); 214239462Sdim DEBUG(VRM->dump()); 215239462Sdim 216239462Sdim // Add kill flags while we still have virtual registers. 217243830Sdim LIS->addKillFlags(VRM); 218239462Sdim 219239462Sdim // Live-in lists on basic blocks are required for physregs. 220239462Sdim addMBBLiveIns(); 221239462Sdim 222239462Sdim // Rewrite virtual registers. 223239462Sdim rewrite(); 224239462Sdim 225239462Sdim // Write out new DBG_VALUE instructions. 226239462Sdim getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 227239462Sdim 228239462Sdim // All machine operands and other references to virtual registers have been 229239462Sdim // replaced. Remove the virtual registers and release all the transient data. 230239462Sdim VRM->clearAllVirt(); 231239462Sdim MRI->clearVirtRegs(); 232239462Sdim return true; 233239462Sdim} 234239462Sdim 235239462Sdim// Compute MBB live-in lists from virtual register live ranges and their 236239462Sdim// assignments. 237239462Sdimvoid VirtRegRewriter::addMBBLiveIns() { 238239462Sdim SmallVector<MachineBasicBlock*, 16> LiveIn; 239239462Sdim for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 240239462Sdim unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 241239462Sdim if (MRI->reg_nodbg_empty(VirtReg)) 242239462Sdim continue; 243239462Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 244239462Sdim if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 245239462Sdim continue; 246239462Sdim // This is a virtual register that is live across basic blocks. Its 247239462Sdim // assigned PhysReg must be marked as live-in to those blocks. 248239462Sdim unsigned PhysReg = VRM->getPhys(VirtReg); 249239462Sdim assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 250239462Sdim 251239462Sdim // Scan the segments of LI. 252239462Sdim for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 253239462Sdim ++I) { 254239462Sdim if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 255239462Sdim continue; 256239462Sdim for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 257239462Sdim if (!LiveIn[i]->isLiveIn(PhysReg)) 258239462Sdim LiveIn[i]->addLiveIn(PhysReg); 259239462Sdim LiveIn.clear(); 260239462Sdim } 261239462Sdim } 262239462Sdim} 263239462Sdim 264239462Sdimvoid VirtRegRewriter::rewrite() { 265221345Sdim SmallVector<unsigned, 8> SuperDeads; 266221345Sdim SmallVector<unsigned, 8> SuperDefs; 267218893Sdim SmallVector<unsigned, 8> SuperKills; 268263508Sdim 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)); 273263508Sdim bool IsExitBB = MBBI->succ_empty(); 274234353Sdim for (MachineBasicBlock::instr_iterator 275234353Sdim MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 276218893Sdim MachineInstr *MI = MII; 277218893Sdim ++MII; 278218893Sdim 279263508Sdim // Check if this instruction is a call to a noreturn function. 280263508Sdim // If so, all the definitions set by this instruction can be ignored. 281263508Sdim if (IsExitBB && MI->isCall()) 282263508Sdim for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 283263508Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 284263508Sdim MachineOperand &MO = *MOI; 285263508Sdim if (!MO.isGlobal()) 286263508Sdim continue; 287263508Sdim const Function *Func = dyn_cast<Function>(MO.getGlobal()); 288263508Sdim if (!Func || !Func->hasFnAttribute(Attribute::NoReturn) || 289263508Sdim // We need to keep correct unwind information 290263508Sdim // even if the function will not return, since the 291263508Sdim // runtime may need it. 292263508Sdim !Func->hasFnAttribute(Attribute::NoUnwind)) 293263508Sdim continue; 294263508Sdim NoReturnInsts.insert(MI); 295263508Sdim break; 296263508Sdim } 297263508Sdim 298218893Sdim for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 299218893Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 300218893Sdim MachineOperand &MO = *MOI; 301234353Sdim 302234353Sdim // Make sure MRI knows about registers clobbered by regmasks. 303234353Sdim if (MO.isRegMask()) 304234353Sdim MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 305234353Sdim 306218893Sdim if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 307218893Sdim continue; 308218893Sdim unsigned VirtReg = MO.getReg(); 309239462Sdim unsigned PhysReg = VRM->getPhys(VirtReg); 310239462Sdim assert(PhysReg != VirtRegMap::NO_PHYS_REG && 311239462Sdim "Instruction uses unmapped VirtReg"); 312243830Sdim 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 317226633Sdim // have to add <imp-use,kill> operands for the super-register. A 318226633Sdim // partial redef always kills and redefines the super-register. 319226633Sdim if (MO.readsReg() && (MO.isDef() || MO.isKill())) 320226633Sdim SuperKills.push_back(PhysReg); 321218893Sdim 322226633Sdim if (MO.isDef()) { 323226633Sdim // The <def,undef> flag only makes sense for sub-register defs, and 324226633Sdim // we are substituting a full physreg. An <imp-use,kill> operand 325226633Sdim // from the SuperKills list will represent the partial read of the 326226633Sdim // super-register. 327226633Sdim MO.setIsUndef(false); 328226633Sdim 329226633Sdim // Also add implicit defs for the super-register. 330226633Sdim if (MO.isDead()) 331226633Sdim SuperDeads.push_back(PhysReg); 332226633Sdim else 333226633Sdim SuperDefs.push_back(PhysReg); 334226633Sdim } 335226633Sdim 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. 378263508Sdim if (NoReturnInsts.empty()) { 379263508Sdim for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 380263508Sdim if (!MRI->reg_nodbg_empty(Reg)) 381263508Sdim MRI->setPhysRegUsed(Reg); 382263508Sdim } else { 383263508Sdim for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) { 384263508Sdim if (MRI->reg_nodbg_empty(Reg)) 385263508Sdim continue; 386263508Sdim // Check if this register has a use that will impact the rest of the 387263508Sdim // code. Uses in debug and noreturn instructions do not impact the 388263508Sdim // generated code. 389263508Sdim for (MachineRegisterInfo::reg_nodbg_iterator It = 390263508Sdim MRI->reg_nodbg_begin(Reg), 391263508Sdim EndIt = MRI->reg_nodbg_end(); It != EndIt; ++It) { 392263508Sdim if (!NoReturnInsts.count(&(*It))) { 393263508Sdim MRI->setPhysRegUsed(Reg); 394263508Sdim break; 395263508Sdim } 396263508Sdim } 397263508Sdim } 398263508Sdim } 399218893Sdim} 400