RegisterScavenging.cpp revision 251662
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" 19249423Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 20198090Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 21193323Sed#include "llvm/CodeGen/MachineFunction.h" 22193323Sed#include "llvm/CodeGen/MachineInstr.h" 23193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 24212904Sdim#include "llvm/Support/Debug.h" 25198090Srdivacky#include "llvm/Support/ErrorHandling.h" 26212904Sdim#include "llvm/Support/raw_ostream.h" 27193323Sed#include "llvm/Target/TargetInstrInfo.h" 28193323Sed#include "llvm/Target/TargetMachine.h" 29249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 30193323Sedusing namespace llvm; 31193323Sed 32193323Sed/// setUsed - Set the register and its sub-registers as being used. 33195340Sedvoid RegScavenger::setUsed(unsigned Reg) { 34193323Sed RegsAvailable.reset(Reg); 35193323Sed 36239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 37239462Sdim RegsAvailable.reset(*SubRegs); 38193323Sed} 39193323Sed 40198090Srdivackybool RegScavenger::isAliasUsed(unsigned Reg) const { 41239462Sdim for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 42249423Sdim if (isUsed(*AI, *AI == Reg)) 43198090Srdivacky return true; 44198090Srdivacky return false; 45198090Srdivacky} 46193323Sed 47198090Srdivackyvoid RegScavenger::initRegState() { 48249423Sdim for (SmallVector<ScavengedInfo, 2>::iterator I = Scavenged.begin(), 49249423Sdim IE = Scavenged.end(); I != IE; ++I) { 50249423Sdim I->Reg = 0; 51249423Sdim I->Restore = NULL; 52249423Sdim } 53198090Srdivacky 54198090Srdivacky // All registers started out unused. 55198090Srdivacky RegsAvailable.set(); 56198090Srdivacky 57198090Srdivacky if (!MBB) 58198090Srdivacky return; 59198090Srdivacky 60198090Srdivacky // Live-in registers are in use. 61207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 62198090Srdivacky E = MBB->livein_end(); I != E; ++I) 63198090Srdivacky setUsed(*I); 64198090Srdivacky 65198090Srdivacky // Pristine CSRs are also unavailable. 66198090Srdivacky BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 67198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 68198090Srdivacky setUsed(I); 69193323Sed} 70193323Sed 71193323Sedvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 72193323Sed MachineFunction &MF = *mbb->getParent(); 73193323Sed const TargetMachine &TM = MF.getTarget(); 74193323Sed TII = TM.getInstrInfo(); 75193323Sed TRI = TM.getRegisterInfo(); 76193323Sed MRI = &MF.getRegInfo(); 77193323Sed 78193323Sed assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 79193323Sed "Target changed?"); 80193323Sed 81234353Sdim // It is not possible to use the register scavenger after late optimization 82234353Sdim // passes that don't preserve accurate liveness information. 83234353Sdim assert(MRI->tracksLiveness() && 84234353Sdim "Cannot use register scavenger with inaccurate liveness"); 85234353Sdim 86198090Srdivacky // Self-initialize. 87193323Sed if (!MBB) { 88193323Sed NumPhysRegs = TRI->getNumRegs(); 89193323Sed RegsAvailable.resize(NumPhysRegs); 90234353Sdim KillRegs.resize(NumPhysRegs); 91234353Sdim DefRegs.resize(NumPhysRegs); 92193323Sed 93193323Sed // Create callee-saved registers bitvector. 94193323Sed CalleeSavedRegs.resize(NumPhysRegs); 95234353Sdim const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF); 96193323Sed if (CSRegs != NULL) 97193323Sed for (unsigned i = 0; CSRegs[i]; ++i) 98193323Sed CalleeSavedRegs.set(CSRegs[i]); 99193323Sed } 100193323Sed 101199481Srdivacky MBB = mbb; 102199481Srdivacky initRegState(); 103193323Sed 104193323Sed Tracking = false; 105193323Sed} 106193323Sed 107198090Srdivackyvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 108198090Srdivacky BV.set(Reg); 109239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 110239462Sdim BV.set(*SubRegs); 111193323Sed} 112193323Sed 113249423Sdimvoid RegScavenger::determineKillsAndDefs() { 114249423Sdim assert(Tracking && "Must be tracking to determine kills and defs"); 115193323Sed 116193323Sed MachineInstr *MI = MBBI; 117249423Sdim assert(!MI->isDebugValue() && "Debug values have no kills or defs"); 118193323Sed 119198090Srdivacky // Find out which registers are early clobbered, killed, defined, and marked 120198090Srdivacky // def-dead in this instruction. 121210299Sed // FIXME: The scavenger is not predication aware. If the instruction is 122210299Sed // predicated, conservatively assume "kill" markers do not actually kill the 123210299Sed // register. Similarly ignores "dead" markers. 124210299Sed bool isPred = TII->isPredicated(MI); 125234353Sdim KillRegs.reset(); 126234353Sdim DefRegs.reset(); 127193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 128193323Sed const MachineOperand &MO = MI->getOperand(i); 129234353Sdim if (MO.isRegMask()) 130234353Sdim (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); 131223017Sdim if (!MO.isReg()) 132193323Sed continue; 133193323Sed unsigned Reg = MO.getReg(); 134249423Sdim if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 135195340Sed continue; 136193323Sed 137198090Srdivacky if (MO.isUse()) { 138223017Sdim // Ignore undef uses. 139223017Sdim if (MO.isUndef()) 140223017Sdim continue; 141234353Sdim if (!isPred && MO.isKill()) 142198090Srdivacky addRegWithSubRegs(KillRegs, Reg); 143198090Srdivacky } else { 144198090Srdivacky assert(MO.isDef()); 145210299Sed if (!isPred && MO.isDead()) 146234353Sdim addRegWithSubRegs(KillRegs, Reg); 147198090Srdivacky else 148198090Srdivacky addRegWithSubRegs(DefRegs, Reg); 149193323Sed } 150193323Sed } 151249423Sdim} 152193323Sed 153249423Sdimvoid RegScavenger::unprocess() { 154249423Sdim assert(Tracking && "Cannot unprocess because we're not tracking"); 155249423Sdim 156249423Sdim MachineInstr *MI = MBBI; 157251662Sdim if (!MI->isDebugValue()) { 158251662Sdim determineKillsAndDefs(); 159249423Sdim 160251662Sdim // Commit the changes. 161251662Sdim setUsed(KillRegs); 162251662Sdim setUnused(DefRegs); 163251662Sdim } 164249423Sdim 165249423Sdim if (MBBI == MBB->begin()) { 166249423Sdim MBBI = MachineBasicBlock::iterator(NULL); 167249423Sdim Tracking = false; 168249423Sdim } else 169249423Sdim --MBBI; 170249423Sdim} 171249423Sdim 172249423Sdimvoid RegScavenger::forward() { 173249423Sdim // Move ptr forward. 174249423Sdim if (!Tracking) { 175249423Sdim MBBI = MBB->begin(); 176249423Sdim Tracking = true; 177249423Sdim } else { 178249423Sdim assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 179249423Sdim MBBI = llvm::next(MBBI); 180249423Sdim } 181249423Sdim assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 182249423Sdim 183249423Sdim MachineInstr *MI = MBBI; 184249423Sdim 185249423Sdim for (SmallVector<ScavengedInfo, 2>::iterator I = Scavenged.begin(), 186249423Sdim IE = Scavenged.end(); I != IE; ++I) { 187249423Sdim if (I->Restore != MI) 188249423Sdim continue; 189249423Sdim 190249423Sdim I->Reg = 0; 191249423Sdim I->Restore = NULL; 192249423Sdim } 193249423Sdim 194249423Sdim if (MI->isDebugValue()) 195249423Sdim return; 196249423Sdim 197249423Sdim determineKillsAndDefs(); 198249423Sdim 199198090Srdivacky // Verify uses and defs. 200234353Sdim#ifndef NDEBUG 201193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 202193323Sed const MachineOperand &MO = MI->getOperand(i); 203223017Sdim if (!MO.isReg()) 204193323Sed continue; 205198090Srdivacky unsigned Reg = MO.getReg(); 206249423Sdim if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 207195340Sed continue; 208198090Srdivacky if (MO.isUse()) { 209223017Sdim if (MO.isUndef()) 210223017Sdim continue; 211198892Srdivacky if (!isUsed(Reg)) { 212198892Srdivacky // Check if it's partial live: e.g. 213198892Srdivacky // D0 = insert_subreg D0<undef>, S0 214198892Srdivacky // ... D0 215198892Srdivacky // The problem is the insert_subreg could be eliminated. The use of 216198892Srdivacky // D0 is using a partially undef value. This is not *incorrect* since 217198892Srdivacky // S1 is can be freely clobbered. 218198892Srdivacky // Ideally we would like a way to model this, but leaving the 219198892Srdivacky // insert_subreg around causes both correctness and performance issues. 220198892Srdivacky bool SubUsed = false; 221239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 222239462Sdim if (isUsed(*SubRegs)) { 223198892Srdivacky SubUsed = true; 224198892Srdivacky break; 225198892Srdivacky } 226234353Sdim if (!SubUsed) { 227234353Sdim MBB->getParent()->verify(NULL, "In Register Scavenger"); 228234353Sdim llvm_unreachable("Using an undefined register!"); 229234353Sdim } 230226633Sdim (void)SubUsed; 231198892Srdivacky } 232198090Srdivacky } else { 233198090Srdivacky assert(MO.isDef()); 234198090Srdivacky#if 0 235198090Srdivacky // FIXME: Enable this once we've figured out how to correctly transfer 236198090Srdivacky // implicit kills during codegen passes like the coalescer. 237198090Srdivacky assert((KillRegs.test(Reg) || isUnused(Reg) || 238198090Srdivacky isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 239198090Srdivacky "Re-defining a live register!"); 240198090Srdivacky#endif 241198090Srdivacky } 242193323Sed } 243234353Sdim#endif // NDEBUG 244193323Sed 245198090Srdivacky // Commit the changes. 246198090Srdivacky setUnused(KillRegs); 247198090Srdivacky setUsed(DefRegs); 248193323Sed} 249193323Sed 250193323Sedvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 251234353Sdim used = RegsAvailable; 252234353Sdim used.flip(); 253193323Sed if (includeReserved) 254243830Sdim used |= MRI->getReservedRegs(); 255193323Sed else 256243830Sdim used.reset(MRI->getReservedRegs()); 257193323Sed} 258193323Sed 259198090Srdivackyunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 260198090Srdivacky for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 261198090Srdivacky I != E; ++I) 262212904Sdim if (!isAliasUsed(*I)) { 263212904Sdim DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 264212904Sdim "\n"); 265198090Srdivacky return *I; 266212904Sdim } 267198090Srdivacky return 0; 268198090Srdivacky} 269193323Sed 270210299Sed/// getRegsAvailable - Return all available registers in the register class 271210299Sed/// in Mask. 272221345SdimBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 273221345Sdim BitVector Mask(TRI->getNumRegs()); 274210299Sed for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 275210299Sed I != E; ++I) 276210299Sed if (!isAliasUsed(*I)) 277210299Sed Mask.set(*I); 278221345Sdim return Mask; 279210299Sed} 280210299Sed 281198090Srdivacky/// findSurvivorReg - Return the candidate register that is unused for the 282210299Sed/// longest after StargMII. UseMI is set to the instruction where the search 283198090Srdivacky/// stopped. 284198090Srdivacky/// 285198090Srdivacky/// No more than InstrLimit instructions are inspected. 286198090Srdivacky/// 287198892Srdivackyunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 288198090Srdivacky BitVector &Candidates, 289198090Srdivacky unsigned InstrLimit, 290198090Srdivacky MachineBasicBlock::iterator &UseMI) { 291198090Srdivacky int Survivor = Candidates.find_first(); 292198090Srdivacky assert(Survivor > 0 && "No candidates for scavenging"); 293193323Sed 294198090Srdivacky MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 295198892Srdivacky assert(StartMI != ME && "MI already at terminator"); 296198892Srdivacky MachineBasicBlock::iterator RestorePointMI = StartMI; 297198892Srdivacky MachineBasicBlock::iterator MI = StartMI; 298193323Sed 299198892Srdivacky bool inVirtLiveRange = false; 300198090Srdivacky for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 301210299Sed if (MI->isDebugValue()) { 302210299Sed ++InstrLimit; // Don't count debug instructions 303210299Sed continue; 304210299Sed } 305198892Srdivacky bool isVirtKillInsn = false; 306198892Srdivacky bool isVirtDefInsn = false; 307198090Srdivacky // Remove any candidates touched by instruction. 308198090Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 309198090Srdivacky const MachineOperand &MO = MI->getOperand(i); 310234353Sdim if (MO.isRegMask()) 311234353Sdim Candidates.clearBitsNotInMask(MO.getRegMask()); 312198892Srdivacky if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 313198090Srdivacky continue; 314198892Srdivacky if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 315198892Srdivacky if (MO.isDef()) 316198892Srdivacky isVirtDefInsn = true; 317198892Srdivacky else if (MO.isKill()) 318198892Srdivacky isVirtKillInsn = true; 319198892Srdivacky continue; 320198892Srdivacky } 321239462Sdim for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 322239462Sdim Candidates.reset(*AI); 323198090Srdivacky } 324198892Srdivacky // If we're not in a virtual reg's live range, this is a valid 325198892Srdivacky // restore point. 326198892Srdivacky if (!inVirtLiveRange) RestorePointMI = MI; 327193323Sed 328198892Srdivacky // Update whether we're in the live range of a virtual register 329198892Srdivacky if (isVirtKillInsn) inVirtLiveRange = false; 330198892Srdivacky if (isVirtDefInsn) inVirtLiveRange = true; 331198892Srdivacky 332198090Srdivacky // Was our survivor untouched by this instruction? 333198090Srdivacky if (Candidates.test(Survivor)) 334198090Srdivacky continue; 335193323Sed 336198090Srdivacky // All candidates gone? 337198090Srdivacky if (Candidates.none()) 338198090Srdivacky break; 339193323Sed 340198090Srdivacky Survivor = Candidates.find_first(); 341193323Sed } 342198892Srdivacky // If we ran off the end, that's where we want to restore. 343198892Srdivacky if (MI == ME) RestorePointMI = ME; 344198892Srdivacky assert (RestorePointMI != StartMI && 345198892Srdivacky "No available scavenger restore location!"); 346198090Srdivacky 347198090Srdivacky // We ran out of candidates, so stop the search. 348198892Srdivacky UseMI = RestorePointMI; 349198090Srdivacky return Survivor; 350193323Sed} 351193323Sed 352249423Sdimstatic unsigned getFrameIndexOperandNum(MachineInstr *MI) { 353249423Sdim unsigned i = 0; 354249423Sdim while (!MI->getOperand(i).isFI()) { 355249423Sdim ++i; 356249423Sdim assert(i < MI->getNumOperands() && 357249423Sdim "Instr doesn't have FrameIndex operand!"); 358249423Sdim } 359249423Sdim return i; 360249423Sdim} 361249423Sdim 362193323Sedunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 363193323Sed MachineBasicBlock::iterator I, 364193323Sed int SPAdj) { 365212904Sdim // Consider all allocatable registers in the register class initially 366212904Sdim BitVector Candidates = 367212904Sdim TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 368193323Sed 369193323Sed // Exclude all the registers being used by the instruction. 370193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 371193323Sed MachineOperand &MO = I->getOperand(i); 372198090Srdivacky if (MO.isReg() && MO.getReg() != 0 && 373198090Srdivacky !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 374193323Sed Candidates.reset(MO.getReg()); 375193323Sed } 376193323Sed 377210299Sed // Try to find a register that's unused if there is one, as then we won't 378221345Sdim // have to spill. Search explicitly rather than masking out based on 379221345Sdim // RegsAvailable, as RegsAvailable does not take aliases into account. 380221345Sdim // That's what getRegsAvailable() is for. 381221345Sdim BitVector Available = getRegsAvailable(RC); 382234353Sdim Available &= Candidates; 383234353Sdim if (Available.any()) 384234353Sdim Candidates = Available; 385210299Sed 386193323Sed // Find the register whose use is furthest away. 387198090Srdivacky MachineBasicBlock::iterator UseMI; 388198090Srdivacky unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 389193323Sed 390210299Sed // If we found an unused register there is no reason to spill it. 391212904Sdim if (!isAliasUsed(SReg)) { 392212904Sdim DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 393198090Srdivacky return SReg; 394212904Sdim } 395193323Sed 396249423Sdim // Find an available scavenging slot. 397249423Sdim unsigned SI; 398249423Sdim for (SI = 0; SI < Scavenged.size(); ++SI) 399249423Sdim if (Scavenged[SI].Reg == 0) 400249423Sdim break; 401193323Sed 402249423Sdim if (SI == Scavenged.size()) { 403249423Sdim // We need to scavenge a register but have no spill slot, the target 404249423Sdim // must know how to do it (if not, we'll assert below). 405249423Sdim Scavenged.push_back(ScavengedInfo()); 406249423Sdim } 407249423Sdim 408198090Srdivacky // Avoid infinite regress 409249423Sdim Scavenged[SI].Reg = SReg; 410198090Srdivacky 411198090Srdivacky // If the target knows how to save/restore the register, let it do so; 412198090Srdivacky // otherwise, use the emergency stack spill slot. 413198396Srdivacky if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 414198090Srdivacky // Spill the scavenged register before I. 415249423Sdim assert(Scavenged[SI].FrameIndex >= 0 && 416198090Srdivacky "Cannot scavenge register without an emergency spill slot!"); 417249423Sdim TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex, 418249423Sdim RC, TRI); 419198090Srdivacky MachineBasicBlock::iterator II = prior(I); 420198090Srdivacky 421249423Sdim unsigned FIOperandNum = getFrameIndexOperandNum(II); 422249423Sdim TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 423249423Sdim 424198090Srdivacky // Restore the scavenged register before its use (or first terminator). 425249423Sdim TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, 426249423Sdim RC, TRI); 427198396Srdivacky II = prior(UseMI); 428249423Sdim 429249423Sdim FIOperandNum = getFrameIndexOperandNum(II); 430249423Sdim TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 431198396Srdivacky } 432198090Srdivacky 433249423Sdim Scavenged[SI].Restore = prior(UseMI); 434198090Srdivacky 435198090Srdivacky // Doing this here leads to infinite regress. 436249423Sdim // Scavenged[SI].Reg = SReg; 437193323Sed 438212904Sdim DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 439212904Sdim "\n"); 440212904Sdim 441193323Sed return SReg; 442193323Sed} 443