RegisterScavenging.cpp revision 60f90618203290f628f295510b8962c1bedd74da
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::const_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 = 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 // Find out which registers are early clobbered, killed, defined, and marked 140 // def-dead in this instruction. 141 BitVector EarlyClobberRegs(NumPhysRegs); 142 BitVector KillRegs(NumPhysRegs); 143 BitVector DefRegs(NumPhysRegs); 144 BitVector DeadRegs(NumPhysRegs); 145 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 146 const MachineOperand &MO = MI->getOperand(i); 147 if (!MO.isReg() || MO.isUndef()) 148 continue; 149 unsigned Reg = MO.getReg(); 150 if (!Reg || isReserved(Reg)) 151 continue; 152 153 if (MO.isUse()) { 154 // Two-address operands implicitly kill. 155 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) 156 addRegWithSubRegs(KillRegs, Reg); 157 } else { 158 assert(MO.isDef()); 159 if (MO.isDead()) 160 addRegWithSubRegs(DeadRegs, Reg); 161 else 162 addRegWithSubRegs(DefRegs, Reg); 163 if (MO.isEarlyClobber()) 164 addRegWithAliases(EarlyClobberRegs, Reg); 165 } 166 } 167 168 // Verify uses and defs. 169 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 170 const MachineOperand &MO = MI->getOperand(i); 171 if (!MO.isReg() || MO.isUndef()) 172 continue; 173 unsigned Reg = MO.getReg(); 174 if (!Reg || isReserved(Reg)) 175 continue; 176 if (MO.isUse()) { 177 if (!isUsed(Reg)) { 178 // Check if it's partial live: e.g. 179 // D0 = insert_subreg D0<undef>, S0 180 // ... D0 181 // The problem is the insert_subreg could be eliminated. The use of 182 // D0 is using a partially undef value. This is not *incorrect* since 183 // S1 is can be freely clobbered. 184 // Ideally we would like a way to model this, but leaving the 185 // insert_subreg around causes both correctness and performance issues. 186 bool SubUsed = false; 187 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 188 unsigned SubReg = *SubRegs; ++SubRegs) 189 if (isUsed(SubReg)) { 190 SubUsed = true; 191 break; 192 } 193 assert(SubUsed && "Using an undefined register!"); 194 } 195 assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 196 "Using an early clobbered register!"); 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 209 // Commit the changes. 210 setUnused(KillRegs); 211 setUnused(DeadRegs); 212 setUsed(DefRegs); 213} 214 215void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 216 if (includeReserved) 217 used = ~RegsAvailable; 218 else 219 used = ~RegsAvailable & ~ReservedRegs; 220} 221 222/// CreateRegClassMask - Set the bits that represent the registers in the 223/// TargetRegisterClass. 224static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 225 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 226 ++I) 227 Mask.set(*I); 228} 229 230unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 231 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 232 I != E; ++I) 233 if (!isAliasUsed(*I)) 234 return *I; 235 return 0; 236} 237 238/// findSurvivorReg - Return the candidate register that is unused for the 239/// longest after MBBI. UseMI is set to the instruction where the search 240/// stopped. 241/// 242/// No more than InstrLimit instructions are inspected. 243/// 244unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 245 BitVector &Candidates, 246 unsigned InstrLimit, 247 MachineBasicBlock::iterator &UseMI) { 248 int Survivor = Candidates.find_first(); 249 assert(Survivor > 0 && "No candidates for scavenging"); 250 251 MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 252 assert(StartMI != ME && "MI already at terminator"); 253 MachineBasicBlock::iterator RestorePointMI = StartMI; 254 MachineBasicBlock::iterator MI = StartMI; 255 256 bool inVirtLiveRange = false; 257 for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 258 bool isVirtKillInsn = false; 259 bool isVirtDefInsn = false; 260 // Remove any candidates touched by instruction. 261 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 262 const MachineOperand &MO = MI->getOperand(i); 263 if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 264 continue; 265 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 266 if (MO.isDef()) 267 isVirtDefInsn = true; 268 else if (MO.isKill()) 269 isVirtKillInsn = true; 270 continue; 271 } 272 Candidates.reset(MO.getReg()); 273 for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 274 Candidates.reset(*R); 275 } 276 // If we're not in a virtual reg's live range, this is a valid 277 // restore point. 278 if (!inVirtLiveRange) RestorePointMI = MI; 279 280 // Update whether we're in the live range of a virtual register 281 if (isVirtKillInsn) inVirtLiveRange = false; 282 if (isVirtDefInsn) inVirtLiveRange = true; 283 284 // Was our survivor untouched by this instruction? 285 if (Candidates.test(Survivor)) 286 continue; 287 288 // All candidates gone? 289 if (Candidates.none()) 290 break; 291 292 Survivor = Candidates.find_first(); 293 } 294 // If we ran off the end, that's where we want to restore. 295 if (MI == ME) RestorePointMI = ME; 296 assert (RestorePointMI != StartMI && 297 "No available scavenger restore location!"); 298 299 // We ran out of candidates, so stop the search. 300 UseMI = RestorePointMI; 301 return Survivor; 302} 303 304unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 305 MachineBasicBlock::iterator I, 306 int SPAdj) { 307 // Mask off the registers which are not in the TargetRegisterClass. 308 BitVector Candidates(NumPhysRegs, false); 309 CreateRegClassMask(RC, Candidates); 310 // Do not include reserved registers. 311 Candidates ^= ReservedRegs & Candidates; 312 313 // Exclude all the registers being used by the instruction. 314 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 315 MachineOperand &MO = I->getOperand(i); 316 if (MO.isReg() && MO.getReg() != 0 && 317 !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 318 Candidates.reset(MO.getReg()); 319 } 320 321 // Find the register whose use is furthest away. 322 MachineBasicBlock::iterator UseMI; 323 unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 324 325 // If we found an unused register there is no reason to spill it. We have 326 // probably found a callee-saved register that has been saved in the 327 // prologue, but happens to be unused at this point. 328 if (!isAliasUsed(SReg)) 329 return SReg; 330 331 assert(ScavengedReg == 0 && 332 "Scavenger slot is live, unable to scavenge another register!"); 333 334 // Avoid infinite regress 335 ScavengedReg = SReg; 336 337 // If the target knows how to save/restore the register, let it do so; 338 // otherwise, use the emergency stack spill slot. 339 if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 340 // Spill the scavenged register before I. 341 assert(ScavengingFrameIndex >= 0 && 342 "Cannot scavenge register without an emergency spill slot!"); 343 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 344 MachineBasicBlock::iterator II = prior(I); 345 TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 346 347 // Restore the scavenged register before its use (or first terminator). 348 TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); 349 II = prior(UseMI); 350 TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 351 } 352 353 ScavengeRestore = prior(UseMI); 354 355 // Doing this here leads to infinite regress. 356 // ScavengedReg = SReg; 357 ScavengedRC = RC; 358 359 return SReg; 360} 361