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