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