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 167 void rewrite(); 168 void addMBBLiveIns(); 169 bool readsUndefSubreg(const MachineOperand &MO) const; 170 void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const; 171 172 public: 173 static char ID; 174 VirtRegRewriter() : MachineFunctionPass(ID) {} 175 176 void getAnalysisUsage(AnalysisUsage &AU) const override; 177 178 bool runOnMachineFunction(MachineFunction&) override; 179 }; 180 } // end anonymous namespace 181 182 char &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 183 184 INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 185 "Virtual Register Rewriter", false, false) 186 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 187 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 188 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 189 INITIALIZE_PASS_DEPENDENCY(LiveStacks) 190 INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 191 INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 192 "Virtual Register Rewriter", false, false) 193 194 char VirtRegRewriter::ID = 0; 195 196 void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 197 AU.setPreservesCFG(); 198 AU.addRequired<LiveIntervals>(); 199 AU.addRequired<SlotIndexes>(); 200 AU.addPreserved<SlotIndexes>(); 201 AU.addRequired<LiveDebugVariables>(); 202 AU.addRequired<LiveStacks>(); 203 AU.addPreserved<LiveStacks>(); 204 AU.addRequired<VirtRegMap>(); 205 MachineFunctionPass::getAnalysisUsage(AU); 206 } 207 208 bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 209 MF = &fn; 210 TM = &MF->getTarget(); 211 TRI = MF->getSubtarget().getRegisterInfo(); 212 TII = MF->getSubtarget().getInstrInfo(); 213 MRI = &MF->getRegInfo(); 214 Indexes = &getAnalysis<SlotIndexes>(); 215 LIS = &getAnalysis<LiveIntervals>(); 216 VRM = &getAnalysis<VirtRegMap>(); 217 DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 218 << "********** Function: " 219 << MF->getName() << '\n'); 220 DEBUG(VRM->dump()); 221 222 // Add kill flags while we still have virtual registers. 223 LIS->addKillFlags(VRM); 224 225 // Live-in lists on basic blocks are required for physregs. 226 addMBBLiveIns(); 227 228 // Rewrite virtual registers. 229 rewrite(); 230 231 // Write out new DBG_VALUE instructions. 232 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 233 234 // All machine operands and other references to virtual registers have been 235 // replaced. Remove the virtual registers and release all the transient data. 236 VRM->clearAllVirt(); 237 MRI->clearVirtRegs(); 238 return true; 239 } 240 241 void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI, 242 unsigned PhysReg) const { 243 assert(!LI.empty()); 244 assert(LI.hasSubRanges()); 245 246 typedef std::pair<const LiveInterval::SubRange *, 247 LiveInterval::const_iterator> SubRangeIteratorPair; 248 SmallVector<SubRangeIteratorPair, 4> SubRanges; 249 SlotIndex First; 250 SlotIndex Last; 251 for (const LiveInterval::SubRange &SR : LI.subranges()) { 252 SubRanges.push_back(std::make_pair(&SR, SR.begin())); 253 if (!First.isValid() || SR.segments.front().start < First) 254 First = SR.segments.front().start; 255 if (!Last.isValid() || SR.segments.back().end > Last) 256 Last = SR.segments.back().end; 257 } 258 259 // Check all mbb start positions between First and Last while 260 // simulatenously advancing an iterator for each subrange. 261 for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First); 262 MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) { 263 SlotIndex MBBBegin = MBBI->first; 264 // Advance all subrange iterators so that their end position is just 265 // behind MBBBegin (or the iterator is at the end). 266 LaneBitmask LaneMask = 0; 267 for (auto &RangeIterPair : SubRanges) { 268 const LiveInterval::SubRange *SR = RangeIterPair.first; 269 LiveInterval::const_iterator &SRI = RangeIterPair.second; 270 while (SRI != SR->end() && SRI->end <= MBBBegin) 271 ++SRI; 272 if (SRI == SR->end()) 273 continue; 274 if (SRI->start <= MBBBegin) 275 LaneMask |= SR->LaneMask; 276 } 277 if (LaneMask == 0) 278 continue; 279 MachineBasicBlock *MBB = MBBI->second; 280 MBB->addLiveIn(PhysReg, LaneMask); 281 } 282 } 283 284 // Compute MBB live-in lists from virtual register live ranges and their 285 // assignments. 286 void VirtRegRewriter::addMBBLiveIns() { 287 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 288 unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 289 if (MRI->reg_nodbg_empty(VirtReg)) 290 continue; 291 LiveInterval &LI = LIS->getInterval(VirtReg); 292 if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 293 continue; 294 // This is a virtual register that is live across basic blocks. Its 295 // assigned PhysReg must be marked as live-in to those blocks. 296 unsigned PhysReg = VRM->getPhys(VirtReg); 297 assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 298 299 if (LI.hasSubRanges()) { 300 addLiveInsForSubRanges(LI, PhysReg); 301 } else { 302 // Go over MBB begin positions and see if we have segments covering them. 303 // The following works because segments and the MBBIndex list are both 304 // sorted by slot indexes. 305 SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(); 306 for (const auto &Seg : LI) { 307 I = Indexes->advanceMBBIndex(I, Seg.start); 308 for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) { 309 MachineBasicBlock *MBB = I->second; 310 MBB->addLiveIn(PhysReg); 311 } 312 } 313 } 314 } 315 316 // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in 317 // each MBB's LiveIns set before calling addLiveIn on them. 318 for (MachineBasicBlock &MBB : *MF) 319 MBB.sortUniqueLiveIns(); 320 } 321 322 /// Returns true if the given machine operand \p MO only reads undefined lanes. 323 /// The function only works for use operands with a subregister set. 324 bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const { 325 // Shortcut if the operand is already marked undef. 326 if (MO.isUndef()) 327 return true; 328 329 unsigned Reg = MO.getReg(); 330 const LiveInterval &LI = LIS->getInterval(Reg); 331 const MachineInstr &MI = *MO.getParent(); 332 SlotIndex BaseIndex = LIS->getInstructionIndex(&MI); 333 // This code is only meant to handle reading undefined subregisters which 334 // we couldn't properly detect before. 335 assert(LI.liveAt(BaseIndex) && 336 "Reads of completely dead register should be marked undef already"); 337 unsigned SubRegIdx = MO.getSubReg(); 338 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx); 339 // See if any of the relevant subregister liveranges is defined at this point. 340 for (const LiveInterval::SubRange &SR : LI.subranges()) { 341 if ((SR.LaneMask & UseMask) != 0 && SR.liveAt(BaseIndex)) 342 return false; 343 } 344 return true; 345 } 346 347 void VirtRegRewriter::rewrite() { 348 bool NoSubRegLiveness = !MRI->subRegLivenessEnabled(); 349 SmallVector<unsigned, 8> SuperDeads; 350 SmallVector<unsigned, 8> SuperDefs; 351 SmallVector<unsigned, 8> SuperKills; 352 353 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 354 MBBI != MBBE; ++MBBI) { 355 DEBUG(MBBI->print(dbgs(), Indexes)); 356 for (MachineBasicBlock::instr_iterator 357 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 358 MachineInstr *MI = &*MII; 359 ++MII; 360 361 for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 362 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 363 MachineOperand &MO = *MOI; 364 365 // Make sure MRI knows about registers clobbered by regmasks. 366 if (MO.isRegMask()) 367 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 368 369 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 370 continue; 371 unsigned VirtReg = MO.getReg(); 372 unsigned PhysReg = VRM->getPhys(VirtReg); 373 assert(PhysReg != VirtRegMap::NO_PHYS_REG && 374 "Instruction uses unmapped VirtReg"); 375 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 376 377 // Preserve semantics of sub-register operands. 378 unsigned SubReg = MO.getSubReg(); 379 if (SubReg != 0) { 380 if (NoSubRegLiveness) { 381 // A virtual register kill refers to the whole register, so we may 382 // have to add <imp-use,kill> operands for the super-register. A 383 // partial redef always kills and redefines the super-register. 384 if (MO.readsReg() && (MO.isDef() || MO.isKill())) 385 SuperKills.push_back(PhysReg); 386 387 if (MO.isDef()) { 388 // Also add implicit defs for the super-register. 389 if (MO.isDead()) 390 SuperDeads.push_back(PhysReg); 391 else 392 SuperDefs.push_back(PhysReg); 393 } 394 } else { 395 if (MO.isUse()) { 396 if (readsUndefSubreg(MO)) 397 // We need to add an <undef> flag if the subregister is 398 // completely undefined (and we are not adding super-register 399 // defs). 400 MO.setIsUndef(true); 401 } else if (!MO.isDead()) { 402 assert(MO.isDef()); 403 } 404 } 405 406 // The <def,undef> flag only makes sense for sub-register defs, and 407 // we are substituting a full physreg. An <imp-use,kill> operand 408 // from the SuperKills list will represent the partial read of the 409 // super-register. 410 if (MO.isDef()) 411 MO.setIsUndef(false); 412 413 // PhysReg operands cannot have subregister indexes. 414 PhysReg = TRI->getSubReg(PhysReg, SubReg); 415 assert(PhysReg && "Invalid SubReg for physical register"); 416 MO.setSubReg(0); 417 } 418 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 419 // we need the inlining here. 420 MO.setReg(PhysReg); 421 } 422 423 // Add any missing super-register kills after rewriting the whole 424 // instruction. 425 while (!SuperKills.empty()) 426 MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 427 428 while (!SuperDeads.empty()) 429 MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 430 431 while (!SuperDefs.empty()) 432 MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 433 434 DEBUG(dbgs() << "> " << *MI); 435 436 // Finally, remove any identity copies. 437 if (MI->isIdentityCopy()) { 438 ++NumIdCopies; 439 DEBUG(dbgs() << "Deleting identity copy.\n"); 440 if (Indexes) 441 Indexes->removeMachineInstrFromMaps(MI); 442 // It's safe to erase MI because MII has already been incremented. 443 MI->eraseFromParent(); 444 } 445 } 446 } 447 } 448 449