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