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