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