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