RegisterScavenging.cpp revision 207618
1193323Sed//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the machine register scavenger. It can provide 11193323Sed// information, such as unused registers, at any point in a machine basic block. 12193323Sed// It also provides a mechanism to make registers available by evicting them to 13193323Sed// spill slots. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17193323Sed#define DEBUG_TYPE "reg-scavenging" 18193323Sed#include "llvm/CodeGen/RegisterScavenging.h" 19198090Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 20193323Sed#include "llvm/CodeGen/MachineFunction.h" 21193323Sed#include "llvm/CodeGen/MachineBasicBlock.h" 22193323Sed#include "llvm/CodeGen/MachineInstr.h" 23193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 24198090Srdivacky#include "llvm/Support/ErrorHandling.h" 25193323Sed#include "llvm/Target/TargetRegisterInfo.h" 26193323Sed#include "llvm/Target/TargetInstrInfo.h" 27193323Sed#include "llvm/Target/TargetMachine.h" 28198090Srdivacky#include "llvm/ADT/DenseMap.h" 29193323Sed#include "llvm/ADT/SmallPtrSet.h" 30193323Sed#include "llvm/ADT/SmallVector.h" 31193323Sed#include "llvm/ADT/STLExtras.h" 32193323Sedusing namespace llvm; 33193323Sed 34193323Sed/// setUsed - Set the register and its sub-registers as being used. 35195340Sedvoid RegScavenger::setUsed(unsigned Reg) { 36193323Sed RegsAvailable.reset(Reg); 37193323Sed 38193323Sed for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 39195340Sed unsigned SubReg = *SubRegs; ++SubRegs) 40193323Sed RegsAvailable.reset(SubReg); 41193323Sed} 42193323Sed 43198090Srdivackybool RegScavenger::isAliasUsed(unsigned Reg) const { 44198090Srdivacky if (isUsed(Reg)) 45198090Srdivacky return true; 46198090Srdivacky for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 47198090Srdivacky if (isUsed(*R)) 48198090Srdivacky return true; 49198090Srdivacky return false; 50198090Srdivacky} 51193323Sed 52198090Srdivackyvoid RegScavenger::initRegState() { 53198090Srdivacky ScavengedReg = 0; 54198090Srdivacky ScavengedRC = NULL; 55198090Srdivacky ScavengeRestore = NULL; 56198090Srdivacky 57198090Srdivacky // All registers started out unused. 58198090Srdivacky RegsAvailable.set(); 59198090Srdivacky 60198090Srdivacky // Reserved registers are always used. 61198090Srdivacky RegsAvailable ^= ReservedRegs; 62198090Srdivacky 63198090Srdivacky if (!MBB) 64198090Srdivacky return; 65198090Srdivacky 66198090Srdivacky // Live-in registers are in use. 67207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 68198090Srdivacky E = MBB->livein_end(); I != E; ++I) 69198090Srdivacky setUsed(*I); 70198090Srdivacky 71198090Srdivacky // Pristine CSRs are also unavailable. 72198090Srdivacky BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 73198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 74198090Srdivacky setUsed(I); 75193323Sed} 76193323Sed 77193323Sedvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 78193323Sed MachineFunction &MF = *mbb->getParent(); 79193323Sed const TargetMachine &TM = MF.getTarget(); 80193323Sed TII = TM.getInstrInfo(); 81193323Sed TRI = TM.getRegisterInfo(); 82193323Sed MRI = &MF.getRegInfo(); 83193323Sed 84193323Sed assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 85193323Sed "Target changed?"); 86193323Sed 87198090Srdivacky // Self-initialize. 88193323Sed if (!MBB) { 89193323Sed NumPhysRegs = TRI->getNumRegs(); 90193323Sed RegsAvailable.resize(NumPhysRegs); 91193323Sed 92193323Sed // Create reserved registers bitvector. 93193323Sed ReservedRegs = TRI->getReservedRegs(MF); 94193323Sed 95193323Sed // Create callee-saved registers bitvector. 96193323Sed CalleeSavedRegs.resize(NumPhysRegs); 97193323Sed const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 98193323Sed if (CSRegs != NULL) 99193323Sed for (unsigned i = 0; CSRegs[i]; ++i) 100193323Sed CalleeSavedRegs.set(CSRegs[i]); 101193323Sed } 102193323Sed 103199481Srdivacky MBB = mbb; 104199481Srdivacky initRegState(); 105193323Sed 106193323Sed Tracking = false; 107193323Sed} 108193323Sed 109198090Srdivackyvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 110198090Srdivacky BV.set(Reg); 111198090Srdivacky for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 112198090Srdivacky BV.set(*R); 113193323Sed} 114193323Sed 115198090Srdivackyvoid RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 116198090Srdivacky BV.set(Reg); 117198090Srdivacky for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 118198090Srdivacky BV.set(*R); 119193323Sed} 120193323Sed 121193323Sedvoid RegScavenger::forward() { 122193323Sed // Move ptr forward. 123193323Sed if (!Tracking) { 124193323Sed MBBI = MBB->begin(); 125193323Sed Tracking = true; 126193323Sed } else { 127193323Sed assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 128200581Srdivacky MBBI = llvm::next(MBBI); 129193323Sed } 130193323Sed 131193323Sed MachineInstr *MI = MBBI; 132193323Sed 133193323Sed if (MI == ScavengeRestore) { 134193323Sed ScavengedReg = 0; 135193323Sed ScavengedRC = NULL; 136193323Sed ScavengeRestore = NULL; 137193323Sed } 138193323Sed 139207618Srdivacky if (MI->isDebugValue()) 140207618Srdivacky return; 141207618Srdivacky 142198090Srdivacky // Find out which registers are early clobbered, killed, defined, and marked 143198090Srdivacky // def-dead in this instruction. 144198090Srdivacky BitVector EarlyClobberRegs(NumPhysRegs); 145198090Srdivacky BitVector KillRegs(NumPhysRegs); 146198090Srdivacky BitVector DefRegs(NumPhysRegs); 147198090Srdivacky BitVector DeadRegs(NumPhysRegs); 148193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 149193323Sed const MachineOperand &MO = MI->getOperand(i); 150198090Srdivacky if (!MO.isReg() || MO.isUndef()) 151193323Sed continue; 152193323Sed unsigned Reg = MO.getReg(); 153198090Srdivacky if (!Reg || isReserved(Reg)) 154195340Sed continue; 155193323Sed 156198090Srdivacky if (MO.isUse()) { 157198090Srdivacky // Two-address operands implicitly kill. 158198090Srdivacky if (MO.isKill() || MI->isRegTiedToDefOperand(i)) 159198090Srdivacky addRegWithSubRegs(KillRegs, Reg); 160198090Srdivacky } else { 161198090Srdivacky assert(MO.isDef()); 162198090Srdivacky if (MO.isDead()) 163198090Srdivacky addRegWithSubRegs(DeadRegs, Reg); 164198090Srdivacky else 165198090Srdivacky addRegWithSubRegs(DefRegs, Reg); 166198090Srdivacky if (MO.isEarlyClobber()) 167198090Srdivacky addRegWithAliases(EarlyClobberRegs, Reg); 168193323Sed } 169193323Sed } 170193323Sed 171198090Srdivacky // Verify uses and defs. 172193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 173193323Sed const MachineOperand &MO = MI->getOperand(i); 174198090Srdivacky if (!MO.isReg() || MO.isUndef()) 175193323Sed continue; 176198090Srdivacky unsigned Reg = MO.getReg(); 177198090Srdivacky if (!Reg || isReserved(Reg)) 178195340Sed continue; 179198090Srdivacky if (MO.isUse()) { 180198892Srdivacky if (!isUsed(Reg)) { 181198892Srdivacky // Check if it's partial live: e.g. 182198892Srdivacky // D0 = insert_subreg D0<undef>, S0 183198892Srdivacky // ... D0 184198892Srdivacky // The problem is the insert_subreg could be eliminated. The use of 185198892Srdivacky // D0 is using a partially undef value. This is not *incorrect* since 186198892Srdivacky // S1 is can be freely clobbered. 187198892Srdivacky // Ideally we would like a way to model this, but leaving the 188198892Srdivacky // insert_subreg around causes both correctness and performance issues. 189198892Srdivacky bool SubUsed = false; 190198892Srdivacky for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 191198892Srdivacky unsigned SubReg = *SubRegs; ++SubRegs) 192198892Srdivacky if (isUsed(SubReg)) { 193198892Srdivacky SubUsed = true; 194198892Srdivacky break; 195198892Srdivacky } 196198892Srdivacky assert(SubUsed && "Using an undefined register!"); 197198892Srdivacky } 198198090Srdivacky assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 199198090Srdivacky "Using an early clobbered register!"); 200198090Srdivacky } else { 201198090Srdivacky assert(MO.isDef()); 202198090Srdivacky#if 0 203198090Srdivacky // FIXME: Enable this once we've figured out how to correctly transfer 204198090Srdivacky // implicit kills during codegen passes like the coalescer. 205198090Srdivacky assert((KillRegs.test(Reg) || isUnused(Reg) || 206198090Srdivacky isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 207198090Srdivacky "Re-defining a live register!"); 208198090Srdivacky#endif 209198090Srdivacky } 210193323Sed } 211193323Sed 212198090Srdivacky // Commit the changes. 213198090Srdivacky setUnused(KillRegs); 214198090Srdivacky setUnused(DeadRegs); 215198090Srdivacky setUsed(DefRegs); 216193323Sed} 217193323Sed 218193323Sedvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 219193323Sed if (includeReserved) 220193323Sed used = ~RegsAvailable; 221193323Sed else 222193323Sed used = ~RegsAvailable & ~ReservedRegs; 223193323Sed} 224193323Sed 225193323Sed/// CreateRegClassMask - Set the bits that represent the registers in the 226193323Sed/// TargetRegisterClass. 227193323Sedstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 228193323Sed for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 229193323Sed ++I) 230193323Sed Mask.set(*I); 231193323Sed} 232193323Sed 233198090Srdivackyunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 234198090Srdivacky for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 235198090Srdivacky I != E; ++I) 236198090Srdivacky if (!isAliasUsed(*I)) 237198090Srdivacky return *I; 238198090Srdivacky return 0; 239198090Srdivacky} 240193323Sed 241198090Srdivacky/// findSurvivorReg - Return the candidate register that is unused for the 242198090Srdivacky/// longest after MBBI. UseMI is set to the instruction where the search 243198090Srdivacky/// stopped. 244198090Srdivacky/// 245198090Srdivacky/// No more than InstrLimit instructions are inspected. 246198090Srdivacky/// 247198892Srdivackyunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 248198090Srdivacky BitVector &Candidates, 249198090Srdivacky unsigned InstrLimit, 250198090Srdivacky MachineBasicBlock::iterator &UseMI) { 251198090Srdivacky int Survivor = Candidates.find_first(); 252198090Srdivacky assert(Survivor > 0 && "No candidates for scavenging"); 253193323Sed 254198090Srdivacky MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 255198892Srdivacky assert(StartMI != ME && "MI already at terminator"); 256198892Srdivacky MachineBasicBlock::iterator RestorePointMI = StartMI; 257198892Srdivacky MachineBasicBlock::iterator MI = StartMI; 258193323Sed 259198892Srdivacky bool inVirtLiveRange = false; 260198090Srdivacky for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 261198892Srdivacky bool isVirtKillInsn = false; 262198892Srdivacky bool isVirtDefInsn = false; 263198090Srdivacky // Remove any candidates touched by instruction. 264198090Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 265198090Srdivacky const MachineOperand &MO = MI->getOperand(i); 266198892Srdivacky if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 267198090Srdivacky continue; 268198892Srdivacky if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 269198892Srdivacky if (MO.isDef()) 270198892Srdivacky isVirtDefInsn = true; 271198892Srdivacky else if (MO.isKill()) 272198892Srdivacky isVirtKillInsn = true; 273198892Srdivacky continue; 274198892Srdivacky } 275198090Srdivacky Candidates.reset(MO.getReg()); 276198090Srdivacky for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 277198090Srdivacky Candidates.reset(*R); 278198090Srdivacky } 279198892Srdivacky // If we're not in a virtual reg's live range, this is a valid 280198892Srdivacky // restore point. 281198892Srdivacky if (!inVirtLiveRange) RestorePointMI = MI; 282193323Sed 283198892Srdivacky // Update whether we're in the live range of a virtual register 284198892Srdivacky if (isVirtKillInsn) inVirtLiveRange = false; 285198892Srdivacky if (isVirtDefInsn) inVirtLiveRange = true; 286198892Srdivacky 287198090Srdivacky // Was our survivor untouched by this instruction? 288198090Srdivacky if (Candidates.test(Survivor)) 289198090Srdivacky continue; 290193323Sed 291198090Srdivacky // All candidates gone? 292198090Srdivacky if (Candidates.none()) 293198090Srdivacky break; 294193323Sed 295198090Srdivacky Survivor = Candidates.find_first(); 296193323Sed } 297198892Srdivacky // If we ran off the end, that's where we want to restore. 298198892Srdivacky if (MI == ME) RestorePointMI = ME; 299198892Srdivacky assert (RestorePointMI != StartMI && 300198892Srdivacky "No available scavenger restore location!"); 301198090Srdivacky 302198090Srdivacky // We ran out of candidates, so stop the search. 303198892Srdivacky UseMI = RestorePointMI; 304198090Srdivacky return Survivor; 305193323Sed} 306193323Sed 307193323Sedunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 308193323Sed MachineBasicBlock::iterator I, 309193323Sed int SPAdj) { 310193323Sed // Mask off the registers which are not in the TargetRegisterClass. 311193323Sed BitVector Candidates(NumPhysRegs, false); 312193323Sed CreateRegClassMask(RC, Candidates); 313198090Srdivacky // Do not include reserved registers. 314198090Srdivacky Candidates ^= ReservedRegs & Candidates; 315193323Sed 316193323Sed // Exclude all the registers being used by the instruction. 317193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 318193323Sed MachineOperand &MO = I->getOperand(i); 319198090Srdivacky if (MO.isReg() && MO.getReg() != 0 && 320198090Srdivacky !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 321193323Sed Candidates.reset(MO.getReg()); 322193323Sed } 323193323Sed 324193323Sed // Find the register whose use is furthest away. 325198090Srdivacky MachineBasicBlock::iterator UseMI; 326198090Srdivacky unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 327193323Sed 328198090Srdivacky // If we found an unused register there is no reason to spill it. We have 329198090Srdivacky // probably found a callee-saved register that has been saved in the 330198090Srdivacky // prologue, but happens to be unused at this point. 331198090Srdivacky if (!isAliasUsed(SReg)) 332198090Srdivacky return SReg; 333193323Sed 334198090Srdivacky assert(ScavengedReg == 0 && 335198090Srdivacky "Scavenger slot is live, unable to scavenge another register!"); 336193323Sed 337198090Srdivacky // Avoid infinite regress 338193323Sed ScavengedReg = SReg; 339198090Srdivacky 340198090Srdivacky // If the target knows how to save/restore the register, let it do so; 341198090Srdivacky // otherwise, use the emergency stack spill slot. 342198396Srdivacky if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 343198090Srdivacky // Spill the scavenged register before I. 344198090Srdivacky assert(ScavengingFrameIndex >= 0 && 345198090Srdivacky "Cannot scavenge register without an emergency spill slot!"); 346198090Srdivacky TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 347198090Srdivacky MachineBasicBlock::iterator II = prior(I); 348198090Srdivacky TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 349198090Srdivacky 350198090Srdivacky // Restore the scavenged register before its use (or first terminator). 351198090Srdivacky TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); 352198396Srdivacky II = prior(UseMI); 353198396Srdivacky TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 354198396Srdivacky } 355198090Srdivacky 356198090Srdivacky ScavengeRestore = prior(UseMI); 357198090Srdivacky 358198090Srdivacky // Doing this here leads to infinite regress. 359198090Srdivacky // ScavengedReg = SReg; 360193323Sed ScavengedRC = RC; 361193323Sed 362193323Sed return SReg; 363193323Sed} 364