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