1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 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 machine register scavenger. It can provide 11 // information, such as unused registers, at any point in a machine basic block. 12 // It also provides a mechanism to make registers available by evicting them to 13 // spill slots. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/CodeGen/RegisterScavenging.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/MachineFrameInfo.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineInstr.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include "llvm/Target/TargetInstrInfo.h" 27 #include "llvm/Target/TargetRegisterInfo.h" 28 #include "llvm/Target/TargetSubtargetInfo.h" 29 using namespace llvm; 30 31 #define DEBUG_TYPE "reg-scavenging" 32 33 /// setUsed - Set the register units of this register as used. 34 void RegScavenger::setRegUsed(unsigned Reg) { 35 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) 36 RegUnitsAvailable.reset(*RUI); 37 } 38 39 void RegScavenger::initRegState() { 40 for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(), 41 IE = Scavenged.end(); I != IE; ++I) { 42 I->Reg = 0; 43 I->Restore = nullptr; 44 } 45 46 // All register units start out unused. 47 RegUnitsAvailable.set(); 48 49 if (!MBB) 50 return; 51 52 // Live-in registers are in use. 53 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 54 E = MBB->livein_end(); I != E; ++I) 55 setRegUsed(*I); 56 57 // Pristine CSRs are also unavailable. 58 BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 59 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 60 setRegUsed(I); 61 } 62 63 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 64 MachineFunction &MF = *mbb->getParent(); 65 TII = MF.getSubtarget().getInstrInfo(); 66 TRI = MF.getSubtarget().getRegisterInfo(); 67 MRI = &MF.getRegInfo(); 68 69 assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) && 70 "Target changed?"); 71 72 // It is not possible to use the register scavenger after late optimization 73 // passes that don't preserve accurate liveness information. 74 assert(MRI->tracksLiveness() && 75 "Cannot use register scavenger with inaccurate liveness"); 76 77 // Self-initialize. 78 if (!MBB) { 79 NumRegUnits = TRI->getNumRegUnits(); 80 RegUnitsAvailable.resize(NumRegUnits); 81 KillRegUnits.resize(NumRegUnits); 82 DefRegUnits.resize(NumRegUnits); 83 TmpRegUnits.resize(NumRegUnits); 84 } 85 86 MBB = mbb; 87 initRegState(); 88 89 Tracking = false; 90 } 91 92 void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) { 93 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) 94 BV.set(*RUI); 95 } 96 97 void RegScavenger::determineKillsAndDefs() { 98 assert(Tracking && "Must be tracking to determine kills and defs"); 99 100 MachineInstr *MI = MBBI; 101 assert(!MI->isDebugValue() && "Debug values have no kills or defs"); 102 103 // Find out which registers are early clobbered, killed, defined, and marked 104 // def-dead in this instruction. 105 // FIXME: The scavenger is not predication aware. If the instruction is 106 // predicated, conservatively assume "kill" markers do not actually kill the 107 // register. Similarly ignores "dead" markers. 108 bool isPred = TII->isPredicated(MI); 109 KillRegUnits.reset(); 110 DefRegUnits.reset(); 111 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 112 const MachineOperand &MO = MI->getOperand(i); 113 if (MO.isRegMask()) { 114 115 TmpRegUnits.clear(); 116 for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) { 117 for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) { 118 if (MO.clobbersPhysReg(*RURI)) { 119 TmpRegUnits.set(RU); 120 break; 121 } 122 } 123 } 124 125 // Apply the mask. 126 (isPred ? DefRegUnits : KillRegUnits) |= TmpRegUnits; 127 } 128 if (!MO.isReg()) 129 continue; 130 unsigned Reg = MO.getReg(); 131 if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 132 continue; 133 134 if (MO.isUse()) { 135 // Ignore undef uses. 136 if (MO.isUndef()) 137 continue; 138 if (!isPred && MO.isKill()) 139 addRegUnits(KillRegUnits, Reg); 140 } else { 141 assert(MO.isDef()); 142 if (!isPred && MO.isDead()) 143 addRegUnits(KillRegUnits, Reg); 144 else 145 addRegUnits(DefRegUnits, Reg); 146 } 147 } 148 } 149 150 void RegScavenger::unprocess() { 151 assert(Tracking && "Cannot unprocess because we're not tracking"); 152 153 MachineInstr *MI = MBBI; 154 if (!MI->isDebugValue()) { 155 determineKillsAndDefs(); 156 157 // Commit the changes. 158 setUsed(KillRegUnits); 159 setUnused(DefRegUnits); 160 } 161 162 if (MBBI == MBB->begin()) { 163 MBBI = MachineBasicBlock::iterator(nullptr); 164 Tracking = false; 165 } else 166 --MBBI; 167 } 168 169 void RegScavenger::forward() { 170 // Move ptr forward. 171 if (!Tracking) { 172 MBBI = MBB->begin(); 173 Tracking = true; 174 } else { 175 assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 176 MBBI = std::next(MBBI); 177 } 178 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 179 180 MachineInstr *MI = MBBI; 181 182 for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(), 183 IE = Scavenged.end(); I != IE; ++I) { 184 if (I->Restore != MI) 185 continue; 186 187 I->Reg = 0; 188 I->Restore = nullptr; 189 } 190 191 if (MI->isDebugValue()) 192 return; 193 194 determineKillsAndDefs(); 195 196 // Verify uses and defs. 197 #ifndef NDEBUG 198 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 199 const MachineOperand &MO = MI->getOperand(i); 200 if (!MO.isReg()) 201 continue; 202 unsigned Reg = MO.getReg(); 203 if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 204 continue; 205 if (MO.isUse()) { 206 if (MO.isUndef()) 207 continue; 208 if (!isRegUsed(Reg)) { 209 // Check if it's partial live: e.g. 210 // D0 = insert_subreg D0<undef>, S0 211 // ... D0 212 // The problem is the insert_subreg could be eliminated. The use of 213 // D0 is using a partially undef value. This is not *incorrect* since 214 // S1 is can be freely clobbered. 215 // Ideally we would like a way to model this, but leaving the 216 // insert_subreg around causes both correctness and performance issues. 217 bool SubUsed = false; 218 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 219 if (isRegUsed(*SubRegs)) { 220 SubUsed = true; 221 break; 222 } 223 bool SuperUsed = false; 224 for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) { 225 if (isRegUsed(*SR)) { 226 SuperUsed = true; 227 break; 228 } 229 } 230 if (!SubUsed && !SuperUsed) { 231 MBB->getParent()->verify(nullptr, "In Register Scavenger"); 232 llvm_unreachable("Using an undefined register!"); 233 } 234 (void)SubUsed; 235 (void)SuperUsed; 236 } 237 } else { 238 assert(MO.isDef()); 239 #if 0 240 // FIXME: Enable this once we've figured out how to correctly transfer 241 // implicit kills during codegen passes like the coalescer. 242 assert((KillRegs.test(Reg) || isUnused(Reg) || 243 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 244 "Re-defining a live register!"); 245 #endif 246 } 247 } 248 #endif // NDEBUG 249 250 // Commit the changes. 251 setUnused(KillRegUnits); 252 setUsed(DefRegUnits); 253 } 254 255 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const { 256 if (includeReserved && isReserved(Reg)) 257 return true; 258 for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) 259 if (!RegUnitsAvailable.test(*RUI)) 260 return true; 261 return false; 262 } 263 264 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 265 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 266 I != E; ++I) 267 if (!isRegUsed(*I)) { 268 DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 269 "\n"); 270 return *I; 271 } 272 return 0; 273 } 274 275 /// getRegsAvailable - Return all available registers in the register class 276 /// in Mask. 277 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 278 BitVector Mask(TRI->getNumRegs()); 279 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 280 I != E; ++I) 281 if (!isRegUsed(*I)) 282 Mask.set(*I); 283 return Mask; 284 } 285 286 /// findSurvivorReg - Return the candidate register that is unused for the 287 /// longest after StartMII. UseMI is set to the instruction where the search 288 /// stopped. 289 /// 290 /// No more than InstrLimit instructions are inspected. 291 /// 292 unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 293 BitVector &Candidates, 294 unsigned InstrLimit, 295 MachineBasicBlock::iterator &UseMI) { 296 int Survivor = Candidates.find_first(); 297 assert(Survivor > 0 && "No candidates for scavenging"); 298 299 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 300 assert(StartMI != ME && "MI already at terminator"); 301 MachineBasicBlock::iterator RestorePointMI = StartMI; 302 MachineBasicBlock::iterator MI = StartMI; 303 304 bool inVirtLiveRange = false; 305 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 306 if (MI->isDebugValue()) { 307 ++InstrLimit; // Don't count debug instructions 308 continue; 309 } 310 bool isVirtKillInsn = false; 311 bool isVirtDefInsn = false; 312 // Remove any candidates touched by instruction. 313 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 314 const MachineOperand &MO = MI->getOperand(i); 315 if (MO.isRegMask()) 316 Candidates.clearBitsNotInMask(MO.getRegMask()); 317 if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 318 continue; 319 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 320 if (MO.isDef()) 321 isVirtDefInsn = true; 322 else if (MO.isKill()) 323 isVirtKillInsn = true; 324 continue; 325 } 326 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 327 Candidates.reset(*AI); 328 } 329 // If we're not in a virtual reg's live range, this is a valid 330 // restore point. 331 if (!inVirtLiveRange) RestorePointMI = MI; 332 333 // Update whether we're in the live range of a virtual register 334 if (isVirtKillInsn) inVirtLiveRange = false; 335 if (isVirtDefInsn) inVirtLiveRange = true; 336 337 // Was our survivor untouched by this instruction? 338 if (Candidates.test(Survivor)) 339 continue; 340 341 // All candidates gone? 342 if (Candidates.none()) 343 break; 344 345 Survivor = Candidates.find_first(); 346 } 347 // If we ran off the end, that's where we want to restore. 348 if (MI == ME) RestorePointMI = ME; 349 assert (RestorePointMI != StartMI && 350 "No available scavenger restore location!"); 351 352 // We ran out of candidates, so stop the search. 353 UseMI = RestorePointMI; 354 return Survivor; 355 } 356 357 static unsigned getFrameIndexOperandNum(MachineInstr *MI) { 358 unsigned i = 0; 359 while (!MI->getOperand(i).isFI()) { 360 ++i; 361 assert(i < MI->getNumOperands() && 362 "Instr doesn't have FrameIndex operand!"); 363 } 364 return i; 365 } 366 367 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 368 MachineBasicBlock::iterator I, 369 int SPAdj) { 370 // Consider all allocatable registers in the register class initially 371 BitVector Candidates = 372 TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 373 374 // Exclude all the registers being used by the instruction. 375 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 376 MachineOperand &MO = I->getOperand(i); 377 if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) && 378 !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 379 Candidates.reset(MO.getReg()); 380 } 381 382 // Try to find a register that's unused if there is one, as then we won't 383 // have to spill. 384 BitVector Available = getRegsAvailable(RC); 385 Available &= Candidates; 386 if (Available.any()) 387 Candidates = Available; 388 389 // Find the register whose use is furthest away. 390 MachineBasicBlock::iterator UseMI; 391 unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 392 393 // If we found an unused register there is no reason to spill it. 394 if (!isRegUsed(SReg)) { 395 DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 396 return SReg; 397 } 398 399 // Find an available scavenging slot. 400 unsigned SI; 401 for (SI = 0; SI < Scavenged.size(); ++SI) 402 if (Scavenged[SI].Reg == 0) 403 break; 404 405 if (SI == Scavenged.size()) { 406 // We need to scavenge a register but have no spill slot, the target 407 // must know how to do it (if not, we'll assert below). 408 Scavenged.push_back(ScavengedInfo()); 409 } 410 411 // Avoid infinite regress 412 Scavenged[SI].Reg = SReg; 413 414 // If the target knows how to save/restore the register, let it do so; 415 // otherwise, use the emergency stack spill slot. 416 if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 417 // Spill the scavenged register before I. 418 assert(Scavenged[SI].FrameIndex >= 0 && 419 "Cannot scavenge register without an emergency spill slot!"); 420 TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex, 421 RC, TRI); 422 MachineBasicBlock::iterator II = std::prev(I); 423 424 unsigned FIOperandNum = getFrameIndexOperandNum(II); 425 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 426 427 // Restore the scavenged register before its use (or first terminator). 428 TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, 429 RC, TRI); 430 II = std::prev(UseMI); 431 432 FIOperandNum = getFrameIndexOperandNum(II); 433 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 434 } 435 436 Scavenged[SI].Restore = std::prev(UseMI); 437 438 // Doing this here leads to infinite regress. 439 // Scavenged[SI].Reg = SReg; 440 441 DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 442 "\n"); 443 444 return SReg; 445 } 446