1//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the VirtRegMap class. 11// 12// It also contains implementations of the Spiller interface, which, given a 13// virtual register map and a machine function, eliminates all virtual 14// references by replacing them with physical register references - adding spill 15// code as necessary. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "regalloc" 20#include "VirtRegMap.h" 21#include "LiveDebugVariables.h" 22#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23#include "llvm/CodeGen/LiveStackAnalysis.h" 24#include "llvm/CodeGen/MachineFrameInfo.h" 25#include "llvm/CodeGen/MachineFunction.h" 26#include "llvm/CodeGen/MachineInstrBuilder.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/CodeGen/Passes.h" 29#include "llvm/Target/TargetMachine.h" 30#include "llvm/Target/TargetInstrInfo.h" 31#include "llvm/Target/TargetRegisterInfo.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Compiler.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/Support/raw_ostream.h" 36#include "llvm/ADT/Statistic.h" 37#include "llvm/ADT/STLExtras.h" 38#include <algorithm> 39using namespace llvm; 40 41STATISTIC(NumSpillSlots, "Number of spill slots allocated"); 42STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 43 44//===----------------------------------------------------------------------===// 45// VirtRegMap implementation 46//===----------------------------------------------------------------------===// 47 48char VirtRegMap::ID = 0; 49 50INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 51 52bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 53 MRI = &mf.getRegInfo(); 54 TII = mf.getTarget().getInstrInfo(); 55 TRI = mf.getTarget().getRegisterInfo(); 56 MF = &mf; 57 58 Virt2PhysMap.clear(); 59 Virt2StackSlotMap.clear(); 60 Virt2SplitMap.clear(); 61 62 grow(); 63 return false; 64} 65 66void VirtRegMap::grow() { 67 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 68 Virt2PhysMap.resize(NumRegs); 69 Virt2StackSlotMap.resize(NumRegs); 70 Virt2SplitMap.resize(NumRegs); 71} 72 73unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 74 int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 75 RC->getAlignment()); 76 ++NumSpillSlots; 77 return SS; 78} 79 80unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { 81 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg); 82 unsigned physReg = Hint.second; 83 if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) 84 physReg = getPhys(physReg); 85 if (Hint.first == 0) 86 return (TargetRegisterInfo::isPhysicalRegister(physReg)) 87 ? physReg : 0; 88 return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); 89} 90 91int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 92 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 93 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 94 "attempt to assign stack slot to already spilled register"); 95 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 96 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 97} 98 99void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 100 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 101 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 102 "attempt to assign stack slot to already spilled register"); 103 assert((SS >= 0 || 104 (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 105 "illegal fixed frame index"); 106 Virt2StackSlotMap[virtReg] = SS; 107} 108 109void VirtRegMap::print(raw_ostream &OS, const Module*) const { 110 OS << "********** REGISTER MAP **********\n"; 111 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 112 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 113 if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 114 OS << '[' << PrintReg(Reg, TRI) << " -> " 115 << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 116 << MRI->getRegClass(Reg)->getName() << "\n"; 117 } 118 } 119 120 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 121 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 122 if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 123 OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 124 << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 125 } 126 } 127 OS << '\n'; 128} 129 130#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 131void VirtRegMap::dump() const { 132 print(dbgs()); 133} 134#endif 135 136//===----------------------------------------------------------------------===// 137// VirtRegRewriter 138//===----------------------------------------------------------------------===// 139// 140// The VirtRegRewriter is the last of the register allocator passes. 141// It rewrites virtual registers to physical registers as specified in the 142// VirtRegMap analysis. It also updates live-in information on basic blocks 143// according to LiveIntervals. 144// 145namespace { 146class VirtRegRewriter : public MachineFunctionPass { 147 MachineFunction *MF; 148 const TargetMachine *TM; 149 const TargetRegisterInfo *TRI; 150 const TargetInstrInfo *TII; 151 MachineRegisterInfo *MRI; 152 SlotIndexes *Indexes; 153 LiveIntervals *LIS; 154 VirtRegMap *VRM; 155 156 void rewrite(); 157 void addMBBLiveIns(); 158public: 159 static char ID; 160 VirtRegRewriter() : MachineFunctionPass(ID) {} 161 162 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 163 164 virtual bool runOnMachineFunction(MachineFunction&); 165}; 166} // end anonymous namespace 167 168char &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 169 170INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 171 "Virtual Register Rewriter", false, false) 172INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 173INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 174INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 175INITIALIZE_PASS_DEPENDENCY(LiveStacks) 176INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 177INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 178 "Virtual Register Rewriter", false, false) 179 180char VirtRegRewriter::ID = 0; 181 182void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 183 AU.setPreservesCFG(); 184 AU.addRequired<LiveIntervals>(); 185 AU.addRequired<SlotIndexes>(); 186 AU.addPreserved<SlotIndexes>(); 187 AU.addRequired<LiveDebugVariables>(); 188 AU.addRequired<LiveStacks>(); 189 AU.addPreserved<LiveStacks>(); 190 AU.addRequired<VirtRegMap>(); 191 MachineFunctionPass::getAnalysisUsage(AU); 192} 193 194bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 195 MF = &fn; 196 TM = &MF->getTarget(); 197 TRI = TM->getRegisterInfo(); 198 TII = TM->getInstrInfo(); 199 MRI = &MF->getRegInfo(); 200 Indexes = &getAnalysis<SlotIndexes>(); 201 LIS = &getAnalysis<LiveIntervals>(); 202 VRM = &getAnalysis<VirtRegMap>(); 203 DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 204 << "********** Function: " 205 << MF->getName() << '\n'); 206 DEBUG(VRM->dump()); 207 208 // Add kill flags while we still have virtual registers. 209 LIS->addKillFlags(VRM); 210 211 // Live-in lists on basic blocks are required for physregs. 212 addMBBLiveIns(); 213 214 // Rewrite virtual registers. 215 rewrite(); 216 217 // Write out new DBG_VALUE instructions. 218 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 219 220 // All machine operands and other references to virtual registers have been 221 // replaced. Remove the virtual registers and release all the transient data. 222 VRM->clearAllVirt(); 223 MRI->clearVirtRegs(); 224 return true; 225} 226 227// Compute MBB live-in lists from virtual register live ranges and their 228// assignments. 229void VirtRegRewriter::addMBBLiveIns() { 230 SmallVector<MachineBasicBlock*, 16> LiveIn; 231 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 232 unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 233 if (MRI->reg_nodbg_empty(VirtReg)) 234 continue; 235 LiveInterval &LI = LIS->getInterval(VirtReg); 236 if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 237 continue; 238 // This is a virtual register that is live across basic blocks. Its 239 // assigned PhysReg must be marked as live-in to those blocks. 240 unsigned PhysReg = VRM->getPhys(VirtReg); 241 assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 242 243 // Scan the segments of LI. 244 for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 245 ++I) { 246 if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 247 continue; 248 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 249 if (!LiveIn[i]->isLiveIn(PhysReg)) 250 LiveIn[i]->addLiveIn(PhysReg); 251 LiveIn.clear(); 252 } 253 } 254} 255 256void VirtRegRewriter::rewrite() { 257 SmallVector<unsigned, 8> SuperDeads; 258 SmallVector<unsigned, 8> SuperDefs; 259 SmallVector<unsigned, 8> SuperKills; 260 261 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 262 MBBI != MBBE; ++MBBI) { 263 DEBUG(MBBI->print(dbgs(), Indexes)); 264 for (MachineBasicBlock::instr_iterator 265 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 266 MachineInstr *MI = MII; 267 ++MII; 268 269 for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 270 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 271 MachineOperand &MO = *MOI; 272 273 // Make sure MRI knows about registers clobbered by regmasks. 274 if (MO.isRegMask()) 275 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 276 277 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 278 continue; 279 unsigned VirtReg = MO.getReg(); 280 unsigned PhysReg = VRM->getPhys(VirtReg); 281 assert(PhysReg != VirtRegMap::NO_PHYS_REG && 282 "Instruction uses unmapped VirtReg"); 283 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 284 285 // Preserve semantics of sub-register operands. 286 if (MO.getSubReg()) { 287 // A virtual register kill refers to the whole register, so we may 288 // have to add <imp-use,kill> operands for the super-register. A 289 // partial redef always kills and redefines the super-register. 290 if (MO.readsReg() && (MO.isDef() || MO.isKill())) 291 SuperKills.push_back(PhysReg); 292 293 if (MO.isDef()) { 294 // The <def,undef> flag only makes sense for sub-register defs, and 295 // we are substituting a full physreg. An <imp-use,kill> operand 296 // from the SuperKills list will represent the partial read of the 297 // super-register. 298 MO.setIsUndef(false); 299 300 // Also add implicit defs for the super-register. 301 if (MO.isDead()) 302 SuperDeads.push_back(PhysReg); 303 else 304 SuperDefs.push_back(PhysReg); 305 } 306 307 // PhysReg operands cannot have subregister indexes. 308 PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 309 assert(PhysReg && "Invalid SubReg for physical register"); 310 MO.setSubReg(0); 311 } 312 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 313 // we need the inlining here. 314 MO.setReg(PhysReg); 315 } 316 317 // Add any missing super-register kills after rewriting the whole 318 // instruction. 319 while (!SuperKills.empty()) 320 MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 321 322 while (!SuperDeads.empty()) 323 MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 324 325 while (!SuperDefs.empty()) 326 MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 327 328 DEBUG(dbgs() << "> " << *MI); 329 330 // Finally, remove any identity copies. 331 if (MI->isIdentityCopy()) { 332 ++NumIdCopies; 333 if (MI->getNumOperands() == 2) { 334 DEBUG(dbgs() << "Deleting identity copy.\n"); 335 if (Indexes) 336 Indexes->removeMachineInstrFromMaps(MI); 337 // It's safe to erase MI because MII has already been incremented. 338 MI->eraseFromParent(); 339 } else { 340 // Transform identity copy to a KILL to deal with subregisters. 341 MI->setDesc(TII->get(TargetOpcode::KILL)); 342 DEBUG(dbgs() << "Identity copy: " << *MI); 343 } 344 } 345 } 346 } 347 348 // Tell MRI about physical registers in use. 349 for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 350 if (!MRI->reg_nodbg_empty(Reg)) 351 MRI->setPhysRegUsed(Reg); 352} 353