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