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