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