RegisterScavenging.cpp revision 198396
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. 67198090Srdivacky for (MachineBasicBlock::const_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 103198090Srdivacky // RS used within emit{Pro,Epi}logue() 104198090Srdivacky if (mbb != MBB) { 105198090Srdivacky MBB = mbb; 106198090Srdivacky initRegState(); 107198090Srdivacky } 108193323Sed 109193323Sed Tracking = false; 110193323Sed} 111193323Sed 112198090Srdivackyvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 113198090Srdivacky BV.set(Reg); 114198090Srdivacky for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 115198090Srdivacky BV.set(*R); 116193323Sed} 117193323Sed 118198090Srdivackyvoid RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 119198090Srdivacky BV.set(Reg); 120198090Srdivacky for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 121198090Srdivacky BV.set(*R); 122193323Sed} 123193323Sed 124193323Sedvoid RegScavenger::forward() { 125193323Sed // Move ptr forward. 126193323Sed if (!Tracking) { 127193323Sed MBBI = MBB->begin(); 128193323Sed Tracking = true; 129193323Sed } else { 130193323Sed assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 131193323Sed MBBI = next(MBBI); 132193323Sed } 133193323Sed 134193323Sed MachineInstr *MI = MBBI; 135193323Sed 136193323Sed if (MI == ScavengeRestore) { 137193323Sed ScavengedReg = 0; 138193323Sed ScavengedRC = NULL; 139193323Sed ScavengeRestore = NULL; 140193323Sed } 141193323Sed 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()) { 180198090Srdivacky assert(isUsed(Reg) && "Using an undefined register!"); 181198090Srdivacky assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 182198090Srdivacky "Using an early clobbered register!"); 183198090Srdivacky } else { 184198090Srdivacky assert(MO.isDef()); 185198090Srdivacky#if 0 186198090Srdivacky // FIXME: Enable this once we've figured out how to correctly transfer 187198090Srdivacky // implicit kills during codegen passes like the coalescer. 188198090Srdivacky assert((KillRegs.test(Reg) || isUnused(Reg) || 189198090Srdivacky isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 190198090Srdivacky "Re-defining a live register!"); 191198090Srdivacky#endif 192198090Srdivacky } 193193323Sed } 194193323Sed 195198090Srdivacky // Commit the changes. 196198090Srdivacky setUnused(KillRegs); 197198090Srdivacky setUnused(DeadRegs); 198198090Srdivacky setUsed(DefRegs); 199193323Sed} 200193323Sed 201193323Sedvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 202193323Sed if (includeReserved) 203193323Sed used = ~RegsAvailable; 204193323Sed else 205193323Sed used = ~RegsAvailable & ~ReservedRegs; 206193323Sed} 207193323Sed 208193323Sed/// CreateRegClassMask - Set the bits that represent the registers in the 209193323Sed/// TargetRegisterClass. 210193323Sedstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 211193323Sed for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 212193323Sed ++I) 213193323Sed Mask.set(*I); 214193323Sed} 215193323Sed 216198090Srdivackyunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 217198090Srdivacky for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 218198090Srdivacky I != E; ++I) 219198090Srdivacky if (!isAliasUsed(*I)) 220198090Srdivacky return *I; 221198090Srdivacky return 0; 222198090Srdivacky} 223193323Sed 224198090Srdivacky/// findSurvivorReg - Return the candidate register that is unused for the 225198090Srdivacky/// longest after MBBI. UseMI is set to the instruction where the search 226198090Srdivacky/// stopped. 227198090Srdivacky/// 228198090Srdivacky/// No more than InstrLimit instructions are inspected. 229198090Srdivacky/// 230198090Srdivackyunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI, 231198090Srdivacky BitVector &Candidates, 232198090Srdivacky unsigned InstrLimit, 233198090Srdivacky MachineBasicBlock::iterator &UseMI) { 234198090Srdivacky int Survivor = Candidates.find_first(); 235198090Srdivacky assert(Survivor > 0 && "No candidates for scavenging"); 236193323Sed 237198090Srdivacky MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 238198090Srdivacky assert(MI != ME && "MI already at terminator"); 239193323Sed 240198090Srdivacky for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 241198090Srdivacky // Remove any candidates touched by instruction. 242198090Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 243198090Srdivacky const MachineOperand &MO = MI->getOperand(i); 244198090Srdivacky if (!MO.isReg() || MO.isUndef() || !MO.getReg() || 245198090Srdivacky TargetRegisterInfo::isVirtualRegister(MO.getReg())) 246198090Srdivacky continue; 247198090Srdivacky Candidates.reset(MO.getReg()); 248198090Srdivacky for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 249198090Srdivacky Candidates.reset(*R); 250198090Srdivacky } 251193323Sed 252198090Srdivacky // Was our survivor untouched by this instruction? 253198090Srdivacky if (Candidates.test(Survivor)) 254198090Srdivacky continue; 255193323Sed 256198090Srdivacky // All candidates gone? 257198090Srdivacky if (Candidates.none()) 258198090Srdivacky break; 259193323Sed 260198090Srdivacky Survivor = Candidates.find_first(); 261193323Sed } 262198090Srdivacky 263198090Srdivacky // We ran out of candidates, so stop the search. 264198090Srdivacky UseMI = MI; 265198090Srdivacky return Survivor; 266193323Sed} 267193323Sed 268193323Sedunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 269193323Sed MachineBasicBlock::iterator I, 270193323Sed int SPAdj) { 271193323Sed // Mask off the registers which are not in the TargetRegisterClass. 272193323Sed BitVector Candidates(NumPhysRegs, false); 273193323Sed CreateRegClassMask(RC, Candidates); 274198090Srdivacky // Do not include reserved registers. 275198090Srdivacky Candidates ^= ReservedRegs & Candidates; 276193323Sed 277193323Sed // Exclude all the registers being used by the instruction. 278193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 279193323Sed MachineOperand &MO = I->getOperand(i); 280198090Srdivacky if (MO.isReg() && MO.getReg() != 0 && 281198090Srdivacky !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 282193323Sed Candidates.reset(MO.getReg()); 283193323Sed } 284193323Sed 285193323Sed // Find the register whose use is furthest away. 286198090Srdivacky MachineBasicBlock::iterator UseMI; 287198090Srdivacky unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 288193323Sed 289198090Srdivacky // If we found an unused register there is no reason to spill it. We have 290198090Srdivacky // probably found a callee-saved register that has been saved in the 291198090Srdivacky // prologue, but happens to be unused at this point. 292198090Srdivacky if (!isAliasUsed(SReg)) 293198090Srdivacky return SReg; 294193323Sed 295198090Srdivacky assert(ScavengedReg == 0 && 296198090Srdivacky "Scavenger slot is live, unable to scavenge another register!"); 297193323Sed 298198090Srdivacky // Avoid infinite regress 299193323Sed ScavengedReg = SReg; 300198090Srdivacky 301198090Srdivacky // If the target knows how to save/restore the register, let it do so; 302198090Srdivacky // otherwise, use the emergency stack spill slot. 303198396Srdivacky if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 304198090Srdivacky // Spill the scavenged register before I. 305198090Srdivacky assert(ScavengingFrameIndex >= 0 && 306198090Srdivacky "Cannot scavenge register without an emergency spill slot!"); 307198090Srdivacky TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 308198090Srdivacky MachineBasicBlock::iterator II = prior(I); 309198090Srdivacky TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 310198090Srdivacky 311198090Srdivacky // Restore the scavenged register before its use (or first terminator). 312198090Srdivacky TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); 313198396Srdivacky II = prior(UseMI); 314198396Srdivacky TRI->eliminateFrameIndex(II, SPAdj, NULL, this); 315198396Srdivacky } 316198090Srdivacky 317198090Srdivacky ScavengeRestore = prior(UseMI); 318198090Srdivacky 319198090Srdivacky // Doing this here leads to infinite regress. 320198090Srdivacky // ScavengedReg = SReg; 321193323Sed ScavengedRC = RC; 322193323Sed 323193323Sed return SReg; 324193323Sed} 325