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