RegisterScavenging.cpp revision d9642faf7c66273eb3a8d99e5fa6b542da5374dd
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/MachineFrameInfo.h" 20#include "llvm/CodeGen/MachineFunction.h" 21#include "llvm/CodeGen/MachineBasicBlock.h" 22#include "llvm/CodeGen/MachineInstr.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/Support/ErrorHandling.h" 25#include "llvm/Target/TargetRegisterInfo.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/ADT/DenseMap.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/STLExtras.h" 32using namespace llvm; 33 34/// setUsed - Set the register and its sub-registers as being used. 35void RegScavenger::setUsed(unsigned Reg) { 36 RegsAvailable.reset(Reg); 37 38 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 39 unsigned SubReg = *SubRegs; ++SubRegs) 40 RegsAvailable.reset(SubReg); 41} 42 43bool RegScavenger::isAliasUsed(unsigned Reg) const { 44 if (isUsed(Reg)) 45 return true; 46 for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 47 if (isUsed(*R)) 48 return true; 49 return false; 50} 51 52void RegScavenger::initRegState() { 53 ScavengedReg = 0; 54 ScavengedRC = NULL; 55 ScavengeRestore = NULL; 56 57 // All registers started out unused. 58 RegsAvailable.set(); 59 60 // Reserved registers are always used. 61 RegsAvailable ^= ReservedRegs; 62 63 if (!MBB) 64 return; 65 66 // Live-in registers are in use. 67 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 68 E = MBB->livein_end(); I != E; ++I) 69 setUsed(*I); 70 71 // Pristine CSRs are also unavailable. 72 BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 73 for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 74 setUsed(I); 75} 76 77void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 78 MachineFunction &MF = *mbb->getParent(); 79 const TargetMachine &TM = MF.getTarget(); 80 TII = TM.getInstrInfo(); 81 TRI = TM.getRegisterInfo(); 82 MRI = &MF.getRegInfo(); 83 84 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 85 "Target changed?"); 86 87 // Self-initialize. 88 if (!MBB) { 89 NumPhysRegs = TRI->getNumRegs(); 90 RegsAvailable.resize(NumPhysRegs); 91 92 // Create reserved registers bitvector. 93 ReservedRegs = TRI->getReservedRegs(MF); 94 95 // Create callee-saved registers bitvector. 96 CalleeSavedRegs.resize(NumPhysRegs); 97 const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 98 if (CSRegs != NULL) 99 for (unsigned i = 0; CSRegs[i]; ++i) 100 CalleeSavedRegs.set(CSRegs[i]); 101 } 102 103 MBB = mbb; 104 initRegState(); 105 106 Tracking = false; 107} 108 109void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 110 BV.set(Reg); 111 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 112 BV.set(*R); 113} 114 115void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 116 BV.set(Reg); 117 for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 118 BV.set(*R); 119} 120 121void RegScavenger::forward() { 122 // Move ptr forward. 123 if (!Tracking) { 124 MBBI = MBB->begin(); 125 Tracking = true; 126 } else { 127 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 128 MBBI = llvm::next(MBBI); 129 } 130 131 MachineInstr *MI = MBBI; 132 133 if (MI == ScavengeRestore) { 134 ScavengedReg = 0; 135 ScavengedRC = NULL; 136 ScavengeRestore = NULL; 137 } 138 139 if (MI->isDebugValue()) 140 return; 141 142 // Find out which registers are early clobbered, killed, defined, and marked 143 // def-dead in this instruction. 144 // FIXME: The scavenger is not predication aware. If the instruction is 145 // predicated, conservatively assume "kill" markers do not actually kill the 146 // register. Similarly ignores "dead" markers. 147 bool isPred = TII->isPredicated(MI); 148 BitVector EarlyClobberRegs(NumPhysRegs); 149 BitVector KillRegs(NumPhysRegs); 150 BitVector DefRegs(NumPhysRegs); 151 BitVector DeadRegs(NumPhysRegs); 152 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 153 const MachineOperand &MO = MI->getOperand(i); 154 if (!MO.isReg() || MO.isUndef()) 155 continue; 156 unsigned Reg = MO.getReg(); 157 if (!Reg || isReserved(Reg)) 158 continue; 159 160 if (MO.isUse()) { 161 // Two-address operands implicitly kill. 162 if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i))) 163 addRegWithSubRegs(KillRegs, Reg); 164 } else { 165 assert(MO.isDef()); 166 if (!isPred && MO.isDead()) 167 addRegWithSubRegs(DeadRegs, Reg); 168 else 169 addRegWithSubRegs(DefRegs, Reg); 170 if (MO.isEarlyClobber()) 171 addRegWithAliases(EarlyClobberRegs, Reg); 172 } 173 } 174 175 // Verify uses and defs. 176 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 177 const MachineOperand &MO = MI->getOperand(i); 178 if (!MO.isReg() || MO.isUndef()) 179 continue; 180 unsigned Reg = MO.getReg(); 181 if (!Reg || isReserved(Reg)) 182 continue; 183 if (MO.isUse()) { 184 if (!isUsed(Reg)) { 185 // Check if it's partial live: e.g. 186 // D0 = insert_subreg D0<undef>, S0 187 // ... D0 188 // The problem is the insert_subreg could be eliminated. The use of 189 // D0 is using a partially undef value. This is not *incorrect* since 190 // S1 is can be freely clobbered. 191 // Ideally we would like a way to model this, but leaving the 192 // insert_subreg around causes both correctness and performance issues. 193 bool SubUsed = false; 194 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 195 unsigned SubReg = *SubRegs; ++SubRegs) 196 if (isUsed(SubReg)) { 197 SubUsed = true; 198 break; 199 } 200 assert(SubUsed && "Using an undefined register!"); 201 } 202 assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 203 "Using an early clobbered register!"); 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 216 // Commit the changes. 217 setUnused(KillRegs); 218 setUnused(DeadRegs); 219 setUsed(DefRegs); 220} 221 222void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 223 if (includeReserved) 224 used = ~RegsAvailable; 225 else 226 used = ~RegsAvailable & ~ReservedRegs; 227} 228 229/// CreateRegClassMask - Set the bits that represent the registers in the 230/// TargetRegisterClass. 231static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 232 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 233 ++I) 234 Mask.set(*I); 235} 236 237unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 238 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 239 I != E; ++I) 240 if (!isAliasUsed(*I)) 241 return *I; 242 return 0; 243} 244 245/// getRegsAvailable - Return all available registers in the register class 246/// in Mask. 247void RegScavenger::getRegsAvailable(const TargetRegisterClass *RC, 248 BitVector &Mask) { 249 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 250 I != E; ++I) 251 if (!isAliasUsed(*I)) 252 Mask.set(*I); 253} 254 255/// findSurvivorReg - Return the candidate register that is unused for the 256/// longest after StargMII. UseMI is set to the instruction where the search 257/// stopped. 258/// 259/// No more than InstrLimit instructions are inspected. 260/// 261unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 262 BitVector &Candidates, 263 unsigned InstrLimit, 264 MachineBasicBlock::iterator &UseMI) { 265 int Survivor = Candidates.find_first(); 266 assert(Survivor > 0 && "No candidates for scavenging"); 267 268 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 269 assert(StartMI != ME && "MI already at terminator"); 270 MachineBasicBlock::iterator RestorePointMI = StartMI; 271 MachineBasicBlock::iterator MI = StartMI; 272 273 bool inVirtLiveRange = false; 274 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 275 if (MI->isDebugValue()) { 276 ++InstrLimit; // Don't count debug instructions 277 continue; 278 } 279 bool isVirtKillInsn = false; 280 bool isVirtDefInsn = false; 281 // Remove any candidates touched by instruction. 282 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 283 const MachineOperand &MO = MI->getOperand(i); 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 Candidates.reset(MO.getReg()); 294 for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 295 Candidates.reset(*R); 296 } 297 // If we're not in a virtual reg's live range, this is a valid 298 // restore point. 299 if (!inVirtLiveRange) RestorePointMI = MI; 300 301 // Update whether we're in the live range of a virtual register 302 if (isVirtKillInsn) inVirtLiveRange = false; 303 if (isVirtDefInsn) inVirtLiveRange = true; 304 305 // Was our survivor untouched by this instruction? 306 if (Candidates.test(Survivor)) 307 continue; 308 309 // All candidates gone? 310 if (Candidates.none()) 311 break; 312 313 Survivor = Candidates.find_first(); 314 } 315 // If we ran off the end, that's where we want to restore. 316 if (MI == ME) RestorePointMI = ME; 317 assert (RestorePointMI != StartMI && 318 "No available scavenger restore location!"); 319 320 // We ran out of candidates, so stop the search. 321 UseMI = RestorePointMI; 322 return Survivor; 323} 324 325unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 326 MachineBasicBlock::iterator I, 327 int SPAdj) { 328 // Mask off the registers which are not in the TargetRegisterClass. 329 BitVector Candidates(NumPhysRegs, false); 330 CreateRegClassMask(RC, Candidates); 331 // Do not include reserved registers. 332 Candidates ^= ReservedRegs & Candidates; 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 // Find the register whose use is furthest away. 343 MachineBasicBlock::iterator UseMI; 344 unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 345 346 // If we found an unused register there is no reason to spill it. We have 347 // probably found a callee-saved register that has been saved in the 348 // prologue, but happens to be unused at this point. 349 if (!isAliasUsed(SReg)) 350 return SReg; 351 352 assert(ScavengedReg == 0 && 353 "Scavenger slot is live, unable to scavenge another register!"); 354 355 // Avoid infinite regress 356 ScavengedReg = SReg; 357 358 // If the target knows how to save/restore the register, let it do so; 359 // otherwise, use the emergency stack spill slot. 360 if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 361 // Spill the scavenged register before I. 362 assert(ScavengingFrameIndex >= 0 && 363 "Cannot scavenge register without an emergency spill slot!"); 364 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 365 MachineBasicBlock::iterator II = prior(I); 366 TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 367 368 // Restore the scavenged register before its use (or first terminator). 369 TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 370 II = prior(UseMI); 371 TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 372 } 373 374 ScavengeRestore = prior(UseMI); 375 376 // Doing this here leads to infinite regress. 377 // ScavengedReg = SReg; 378 ScavengedRC = RC; 379 380 return SReg; 381} 382