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