RegisterScavenging.cpp revision 8846129f6eb58982a2cac22306c8c9b586084475
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::forward() { 114 // Move ptr forward. 115 if (!Tracking) { 116 MBBI = MBB->begin(); 117 Tracking = true; 118 } else { 119 assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 120 MBBI = llvm::next(MBBI); 121 } 122 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 123 124 MachineInstr *MI = MBBI; 125 126 for (SmallVector<ScavengedInfo, 2>::iterator I = Scavenged.begin(), 127 IE = Scavenged.end(); I != IE; ++I) { 128 if (I->Restore != MI) 129 continue; 130 131 I->Reg = 0; 132 I->Restore = NULL; 133 } 134 135 if (MI->isDebugValue()) 136 return; 137 138 // Find out which registers are early clobbered, killed, defined, and marked 139 // def-dead in this instruction. 140 // FIXME: The scavenger is not predication aware. If the instruction is 141 // predicated, conservatively assume "kill" markers do not actually kill the 142 // register. Similarly ignores "dead" markers. 143 bool isPred = TII->isPredicated(MI); 144 KillRegs.reset(); 145 DefRegs.reset(); 146 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 147 const MachineOperand &MO = MI->getOperand(i); 148 if (MO.isRegMask()) 149 (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); 150 if (!MO.isReg()) 151 continue; 152 unsigned Reg = MO.getReg(); 153 if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 154 continue; 155 156 if (MO.isUse()) { 157 // Ignore undef uses. 158 if (MO.isUndef()) 159 continue; 160 if (!isPred && MO.isKill()) 161 addRegWithSubRegs(KillRegs, Reg); 162 } else { 163 assert(MO.isDef()); 164 if (!isPred && MO.isDead()) 165 addRegWithSubRegs(KillRegs, Reg); 166 else 167 addRegWithSubRegs(DefRegs, Reg); 168 } 169 } 170 171 // Verify uses and defs. 172#ifndef NDEBUG 173 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 174 const MachineOperand &MO = MI->getOperand(i); 175 if (!MO.isReg()) 176 continue; 177 unsigned Reg = MO.getReg(); 178 if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 179 continue; 180 if (MO.isUse()) { 181 if (MO.isUndef()) 182 continue; 183 if (!isUsed(Reg)) { 184 // Check if it's partial live: e.g. 185 // D0 = insert_subreg D0<undef>, S0 186 // ... D0 187 // The problem is the insert_subreg could be eliminated. The use of 188 // D0 is using a partially undef value. This is not *incorrect* since 189 // S1 is can be freely clobbered. 190 // Ideally we would like a way to model this, but leaving the 191 // insert_subreg around causes both correctness and performance issues. 192 bool SubUsed = false; 193 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 194 if (isUsed(*SubRegs)) { 195 SubUsed = true; 196 break; 197 } 198 if (!SubUsed) { 199 MBB->getParent()->verify(NULL, "In Register Scavenger"); 200 llvm_unreachable("Using an undefined register!"); 201 } 202 (void)SubUsed; 203 } 204 } else { 205 assert(MO.isDef()); 206#if 0 207 // FIXME: Enable this once we've figured out how to correctly transfer 208 // implicit kills during codegen passes like the coalescer. 209 assert((KillRegs.test(Reg) || isUnused(Reg) || 210 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 211 "Re-defining a live register!"); 212#endif 213 } 214 } 215#endif // NDEBUG 216 217 // Commit the changes. 218 setUnused(KillRegs); 219 setUsed(DefRegs); 220} 221 222void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 223 used = RegsAvailable; 224 used.flip(); 225 if (includeReserved) 226 used |= MRI->getReservedRegs(); 227 else 228 used.reset(MRI->getReservedRegs()); 229} 230 231unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 232 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 233 I != E; ++I) 234 if (!isAliasUsed(*I)) { 235 DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 236 "\n"); 237 return *I; 238 } 239 return 0; 240} 241 242/// getRegsAvailable - Return all available registers in the register class 243/// in Mask. 244BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 245 BitVector Mask(TRI->getNumRegs()); 246 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 247 I != E; ++I) 248 if (!isAliasUsed(*I)) 249 Mask.set(*I); 250 return Mask; 251} 252 253/// findSurvivorReg - Return the candidate register that is unused for the 254/// longest after StargMII. UseMI is set to the instruction where the search 255/// stopped. 256/// 257/// No more than InstrLimit instructions are inspected. 258/// 259unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 260 BitVector &Candidates, 261 unsigned InstrLimit, 262 MachineBasicBlock::iterator &UseMI) { 263 int Survivor = Candidates.find_first(); 264 assert(Survivor > 0 && "No candidates for scavenging"); 265 266 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 267 assert(StartMI != ME && "MI already at terminator"); 268 MachineBasicBlock::iterator RestorePointMI = StartMI; 269 MachineBasicBlock::iterator MI = StartMI; 270 271 bool inVirtLiveRange = false; 272 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 273 if (MI->isDebugValue()) { 274 ++InstrLimit; // Don't count debug instructions 275 continue; 276 } 277 bool isVirtKillInsn = false; 278 bool isVirtDefInsn = false; 279 // Remove any candidates touched by instruction. 280 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 281 const MachineOperand &MO = MI->getOperand(i); 282 if (MO.isRegMask()) 283 Candidates.clearBitsNotInMask(MO.getRegMask()); 284 if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 285 continue; 286 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 287 if (MO.isDef()) 288 isVirtDefInsn = true; 289 else if (MO.isKill()) 290 isVirtKillInsn = true; 291 continue; 292 } 293 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 294 Candidates.reset(*AI); 295 } 296 // If we're not in a virtual reg's live range, this is a valid 297 // restore point. 298 if (!inVirtLiveRange) RestorePointMI = MI; 299 300 // Update whether we're in the live range of a virtual register 301 if (isVirtKillInsn) inVirtLiveRange = false; 302 if (isVirtDefInsn) inVirtLiveRange = true; 303 304 // Was our survivor untouched by this instruction? 305 if (Candidates.test(Survivor)) 306 continue; 307 308 // All candidates gone? 309 if (Candidates.none()) 310 break; 311 312 Survivor = Candidates.find_first(); 313 } 314 // If we ran off the end, that's where we want to restore. 315 if (MI == ME) RestorePointMI = ME; 316 assert (RestorePointMI != StartMI && 317 "No available scavenger restore location!"); 318 319 // We ran out of candidates, so stop the search. 320 UseMI = RestorePointMI; 321 return Survivor; 322} 323 324static unsigned getFrameIndexOperandNum(MachineInstr *MI) { 325 unsigned i = 0; 326 while (!MI->getOperand(i).isFI()) { 327 ++i; 328 assert(i < MI->getNumOperands() && 329 "Instr doesn't have FrameIndex operand!"); 330 } 331 return i; 332} 333 334unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 335 MachineBasicBlock::iterator I, 336 int SPAdj) { 337 // Consider all allocatable registers in the register class initially 338 BitVector Candidates = 339 TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 340 341 // Exclude all the registers being used by the instruction. 342 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 343 MachineOperand &MO = I->getOperand(i); 344 if (MO.isReg() && MO.getReg() != 0 && 345 !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 346 Candidates.reset(MO.getReg()); 347 } 348 349 // Try to find a register that's unused if there is one, as then we won't 350 // have to spill. Search explicitly rather than masking out based on 351 // RegsAvailable, as RegsAvailable does not take aliases into account. 352 // That's what getRegsAvailable() is for. 353 BitVector Available = getRegsAvailable(RC); 354 Available &= Candidates; 355 if (Available.any()) 356 Candidates = Available; 357 358 // Find the register whose use is furthest away. 359 MachineBasicBlock::iterator UseMI; 360 unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 361 362 // If we found an unused register there is no reason to spill it. 363 if (!isAliasUsed(SReg)) { 364 DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 365 return SReg; 366 } 367 368 // Find an available scavenging slot. 369 unsigned SI; 370 for (SI = 0; SI < Scavenged.size(); ++SI) 371 if (Scavenged[SI].Reg == 0) 372 break; 373 374 assert(SI < Scavenged.size() && 375 "Scavenger slots are live, unable to scavenge another register!"); 376 377 // Avoid infinite regress 378 Scavenged[SI].Reg = SReg; 379 380 // If the target knows how to save/restore the register, let it do so; 381 // otherwise, use the emergency stack spill slot. 382 if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 383 // Spill the scavenged register before I. 384 assert(Scavenged[SI].FrameIndex >= 0 && 385 "Cannot scavenge register without an emergency spill slot!"); 386 TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex, 387 RC, TRI); 388 MachineBasicBlock::iterator II = prior(I); 389 390 unsigned FIOperandNum = getFrameIndexOperandNum(II); 391 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 392 393 // Restore the scavenged register before its use (or first terminator). 394 TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, 395 RC, TRI); 396 II = prior(UseMI); 397 398 FIOperandNum = getFrameIndexOperandNum(II); 399 TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 400 } 401 402 Scavenged[SI].Restore = prior(UseMI); 403 404 // Doing this here leads to infinite regress. 405 // Scavenged[SI].Reg = SReg; 406 407 DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 408 "\n"); 409 410 return SReg; 411} 412