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) { 34263508Sdim for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 35263508Sdim SubRegs.isValid(); ++SubRegs) 36239462Sdim RegsAvailable.reset(*SubRegs); 37193323Sed} 38193323Sed 39198090Srdivackybool RegScavenger::isAliasUsed(unsigned Reg) const { 40239462Sdim for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 41249423Sdim if (isUsed(*AI, *AI == Reg)) 42198090Srdivacky return true; 43198090Srdivacky return false; 44198090Srdivacky} 45193323Sed 46198090Srdivackyvoid RegScavenger::initRegState() { 47263508Sdim for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(), 48263508Sdim IE = Scavenged.end(); I != IE; ++I) { 49249423Sdim I->Reg = 0; 50249423Sdim I->Restore = NULL; 51249423Sdim } 52198090Srdivacky 53198090Srdivacky // All registers started out unused. 54198090Srdivacky RegsAvailable.set(); 55198090Srdivacky 56198090Srdivacky if (!MBB) 57198090Srdivacky return; 58198090Srdivacky 59198090Srdivacky // Live-in registers are in use. 60207618Srdivacky for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 61198090Srdivacky E = MBB->livein_end(); I != E; ++I) 62198090Srdivacky setUsed(*I); 63198090Srdivacky 64198090Srdivacky // Pristine CSRs are also unavailable. 65198090Srdivacky BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 66198090Srdivacky for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 67198090Srdivacky setUsed(I); 68193323Sed} 69193323Sed 70193323Sedvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 71193323Sed MachineFunction &MF = *mbb->getParent(); 72193323Sed const TargetMachine &TM = MF.getTarget(); 73193323Sed TII = TM.getInstrInfo(); 74193323Sed TRI = TM.getRegisterInfo(); 75193323Sed MRI = &MF.getRegInfo(); 76193323Sed 77193323Sed assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 78193323Sed "Target changed?"); 79193323Sed 80234353Sdim // It is not possible to use the register scavenger after late optimization 81234353Sdim // passes that don't preserve accurate liveness information. 82234353Sdim assert(MRI->tracksLiveness() && 83234353Sdim "Cannot use register scavenger with inaccurate liveness"); 84234353Sdim 85198090Srdivacky // Self-initialize. 86193323Sed if (!MBB) { 87193323Sed NumPhysRegs = TRI->getNumRegs(); 88193323Sed RegsAvailable.resize(NumPhysRegs); 89234353Sdim KillRegs.resize(NumPhysRegs); 90234353Sdim DefRegs.resize(NumPhysRegs); 91193323Sed 92193323Sed // Create callee-saved registers bitvector. 93193323Sed CalleeSavedRegs.resize(NumPhysRegs); 94234353Sdim const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF); 95193323Sed if (CSRegs != NULL) 96193323Sed for (unsigned i = 0; CSRegs[i]; ++i) 97193323Sed CalleeSavedRegs.set(CSRegs[i]); 98193323Sed } 99193323Sed 100199481Srdivacky MBB = mbb; 101199481Srdivacky initRegState(); 102193323Sed 103193323Sed Tracking = false; 104193323Sed} 105193323Sed 106198090Srdivackyvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 107263508Sdim for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 108263508Sdim SubRegs.isValid(); ++SubRegs) 109239462Sdim BV.set(*SubRegs); 110193323Sed} 111193323Sed 112249423Sdimvoid RegScavenger::determineKillsAndDefs() { 113249423Sdim assert(Tracking && "Must be tracking to determine kills and defs"); 114193323Sed 115193323Sed MachineInstr *MI = MBBI; 116249423Sdim assert(!MI->isDebugValue() && "Debug values have no kills or defs"); 117193323Sed 118198090Srdivacky // Find out which registers are early clobbered, killed, defined, and marked 119198090Srdivacky // def-dead in this instruction. 120210299Sed // FIXME: The scavenger is not predication aware. If the instruction is 121210299Sed // predicated, conservatively assume "kill" markers do not actually kill the 122210299Sed // register. Similarly ignores "dead" markers. 123210299Sed bool isPred = TII->isPredicated(MI); 124234353Sdim KillRegs.reset(); 125234353Sdim DefRegs.reset(); 126193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 127193323Sed const MachineOperand &MO = MI->getOperand(i); 128234353Sdim if (MO.isRegMask()) 129234353Sdim (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); 130223017Sdim if (!MO.isReg()) 131193323Sed continue; 132193323Sed unsigned Reg = MO.getReg(); 133249423Sdim if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 134195340Sed continue; 135193323Sed 136198090Srdivacky if (MO.isUse()) { 137223017Sdim // Ignore undef uses. 138223017Sdim if (MO.isUndef()) 139223017Sdim continue; 140234353Sdim if (!isPred && MO.isKill()) 141198090Srdivacky addRegWithSubRegs(KillRegs, Reg); 142198090Srdivacky } else { 143198090Srdivacky assert(MO.isDef()); 144210299Sed if (!isPred && MO.isDead()) 145234353Sdim addRegWithSubRegs(KillRegs, Reg); 146198090Srdivacky else 147198090Srdivacky addRegWithSubRegs(DefRegs, Reg); 148193323Sed } 149193323Sed } 150249423Sdim} 151193323Sed 152249423Sdimvoid RegScavenger::unprocess() { 153249423Sdim assert(Tracking && "Cannot unprocess because we're not tracking"); 154249423Sdim 155249423Sdim MachineInstr *MI = MBBI; 156251662Sdim if (!MI->isDebugValue()) { 157251662Sdim determineKillsAndDefs(); 158249423Sdim 159251662Sdim // Commit the changes. 160251662Sdim setUsed(KillRegs); 161251662Sdim setUnused(DefRegs); 162251662Sdim } 163249423Sdim 164249423Sdim if (MBBI == MBB->begin()) { 165249423Sdim MBBI = MachineBasicBlock::iterator(NULL); 166249423Sdim Tracking = false; 167249423Sdim } else 168249423Sdim --MBBI; 169249423Sdim} 170249423Sdim 171249423Sdimvoid RegScavenger::forward() { 172249423Sdim // Move ptr forward. 173249423Sdim if (!Tracking) { 174249423Sdim MBBI = MBB->begin(); 175249423Sdim Tracking = true; 176249423Sdim } else { 177249423Sdim assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 178249423Sdim MBBI = llvm::next(MBBI); 179249423Sdim } 180249423Sdim assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 181249423Sdim 182249423Sdim MachineInstr *MI = MBBI; 183249423Sdim 184263508Sdim for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(), 185263508Sdim IE = Scavenged.end(); I != IE; ++I) { 186249423Sdim if (I->Restore != MI) 187249423Sdim continue; 188249423Sdim 189249423Sdim I->Reg = 0; 190249423Sdim I->Restore = NULL; 191249423Sdim } 192249423Sdim 193249423Sdim if (MI->isDebugValue()) 194249423Sdim return; 195249423Sdim 196249423Sdim determineKillsAndDefs(); 197249423Sdim 198198090Srdivacky // Verify uses and defs. 199234353Sdim#ifndef NDEBUG 200193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 201193323Sed const MachineOperand &MO = MI->getOperand(i); 202223017Sdim if (!MO.isReg()) 203193323Sed continue; 204198090Srdivacky unsigned Reg = MO.getReg(); 205249423Sdim if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) 206195340Sed continue; 207198090Srdivacky if (MO.isUse()) { 208223017Sdim if (MO.isUndef()) 209223017Sdim continue; 210198892Srdivacky if (!isUsed(Reg)) { 211198892Srdivacky // Check if it's partial live: e.g. 212198892Srdivacky // D0 = insert_subreg D0<undef>, S0 213198892Srdivacky // ... D0 214198892Srdivacky // The problem is the insert_subreg could be eliminated. The use of 215198892Srdivacky // D0 is using a partially undef value. This is not *incorrect* since 216198892Srdivacky // S1 is can be freely clobbered. 217198892Srdivacky // Ideally we would like a way to model this, but leaving the 218198892Srdivacky // insert_subreg around causes both correctness and performance issues. 219198892Srdivacky bool SubUsed = false; 220239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 221239462Sdim if (isUsed(*SubRegs)) { 222198892Srdivacky SubUsed = true; 223198892Srdivacky break; 224198892Srdivacky } 225234353Sdim if (!SubUsed) { 226234353Sdim MBB->getParent()->verify(NULL, "In Register Scavenger"); 227234353Sdim llvm_unreachable("Using an undefined register!"); 228234353Sdim } 229226633Sdim (void)SubUsed; 230198892Srdivacky } 231198090Srdivacky } else { 232198090Srdivacky assert(MO.isDef()); 233198090Srdivacky#if 0 234198090Srdivacky // FIXME: Enable this once we've figured out how to correctly transfer 235198090Srdivacky // implicit kills during codegen passes like the coalescer. 236198090Srdivacky assert((KillRegs.test(Reg) || isUnused(Reg) || 237198090Srdivacky isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 238198090Srdivacky "Re-defining a live register!"); 239198090Srdivacky#endif 240198090Srdivacky } 241193323Sed } 242234353Sdim#endif // NDEBUG 243193323Sed 244198090Srdivacky // Commit the changes. 245198090Srdivacky setUnused(KillRegs); 246198090Srdivacky setUsed(DefRegs); 247193323Sed} 248193323Sed 249193323Sedvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 250234353Sdim used = RegsAvailable; 251234353Sdim used.flip(); 252193323Sed if (includeReserved) 253243830Sdim used |= MRI->getReservedRegs(); 254193323Sed else 255243830Sdim used.reset(MRI->getReservedRegs()); 256193323Sed} 257193323Sed 258198090Srdivackyunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 259198090Srdivacky for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 260198090Srdivacky I != E; ++I) 261212904Sdim if (!isAliasUsed(*I)) { 262212904Sdim DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 263212904Sdim "\n"); 264198090Srdivacky return *I; 265212904Sdim } 266198090Srdivacky return 0; 267198090Srdivacky} 268193323Sed 269210299Sed/// getRegsAvailable - Return all available registers in the register class 270210299Sed/// in Mask. 271221345SdimBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 272221345Sdim BitVector Mask(TRI->getNumRegs()); 273210299Sed for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 274210299Sed I != E; ++I) 275210299Sed if (!isAliasUsed(*I)) 276210299Sed Mask.set(*I); 277221345Sdim return Mask; 278210299Sed} 279210299Sed 280198090Srdivacky/// findSurvivorReg - Return the candidate register that is unused for the 281210299Sed/// longest after StargMII. UseMI is set to the instruction where the search 282198090Srdivacky/// stopped. 283198090Srdivacky/// 284198090Srdivacky/// No more than InstrLimit instructions are inspected. 285198090Srdivacky/// 286198892Srdivackyunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 287198090Srdivacky BitVector &Candidates, 288198090Srdivacky unsigned InstrLimit, 289198090Srdivacky MachineBasicBlock::iterator &UseMI) { 290198090Srdivacky int Survivor = Candidates.find_first(); 291198090Srdivacky assert(Survivor > 0 && "No candidates for scavenging"); 292193323Sed 293198090Srdivacky MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 294198892Srdivacky assert(StartMI != ME && "MI already at terminator"); 295198892Srdivacky MachineBasicBlock::iterator RestorePointMI = StartMI; 296198892Srdivacky MachineBasicBlock::iterator MI = StartMI; 297193323Sed 298198892Srdivacky bool inVirtLiveRange = false; 299198090Srdivacky for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 300210299Sed if (MI->isDebugValue()) { 301210299Sed ++InstrLimit; // Don't count debug instructions 302210299Sed continue; 303210299Sed } 304198892Srdivacky bool isVirtKillInsn = false; 305198892Srdivacky bool isVirtDefInsn = false; 306198090Srdivacky // Remove any candidates touched by instruction. 307198090Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 308198090Srdivacky const MachineOperand &MO = MI->getOperand(i); 309234353Sdim if (MO.isRegMask()) 310234353Sdim Candidates.clearBitsNotInMask(MO.getRegMask()); 311198892Srdivacky if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 312198090Srdivacky continue; 313198892Srdivacky if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 314198892Srdivacky if (MO.isDef()) 315198892Srdivacky isVirtDefInsn = true; 316198892Srdivacky else if (MO.isKill()) 317198892Srdivacky isVirtKillInsn = true; 318198892Srdivacky continue; 319198892Srdivacky } 320239462Sdim for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 321239462Sdim Candidates.reset(*AI); 322198090Srdivacky } 323198892Srdivacky // If we're not in a virtual reg's live range, this is a valid 324198892Srdivacky // restore point. 325198892Srdivacky if (!inVirtLiveRange) RestorePointMI = MI; 326193323Sed 327198892Srdivacky // Update whether we're in the live range of a virtual register 328198892Srdivacky if (isVirtKillInsn) inVirtLiveRange = false; 329198892Srdivacky if (isVirtDefInsn) inVirtLiveRange = true; 330198892Srdivacky 331198090Srdivacky // Was our survivor untouched by this instruction? 332198090Srdivacky if (Candidates.test(Survivor)) 333198090Srdivacky continue; 334193323Sed 335198090Srdivacky // All candidates gone? 336198090Srdivacky if (Candidates.none()) 337198090Srdivacky break; 338193323Sed 339198090Srdivacky Survivor = Candidates.find_first(); 340193323Sed } 341198892Srdivacky // If we ran off the end, that's where we want to restore. 342198892Srdivacky if (MI == ME) RestorePointMI = ME; 343198892Srdivacky assert (RestorePointMI != StartMI && 344198892Srdivacky "No available scavenger restore location!"); 345198090Srdivacky 346198090Srdivacky // We ran out of candidates, so stop the search. 347198892Srdivacky UseMI = RestorePointMI; 348198090Srdivacky return Survivor; 349193323Sed} 350193323Sed 351249423Sdimstatic unsigned getFrameIndexOperandNum(MachineInstr *MI) { 352249423Sdim unsigned i = 0; 353249423Sdim while (!MI->getOperand(i).isFI()) { 354249423Sdim ++i; 355249423Sdim assert(i < MI->getNumOperands() && 356249423Sdim "Instr doesn't have FrameIndex operand!"); 357249423Sdim } 358249423Sdim return i; 359249423Sdim} 360249423Sdim 361193323Sedunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 362193323Sed MachineBasicBlock::iterator I, 363193323Sed int SPAdj) { 364212904Sdim // Consider all allocatable registers in the register class initially 365212904Sdim BitVector Candidates = 366212904Sdim TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 367193323Sed 368193323Sed // Exclude all the registers being used by the instruction. 369193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 370193323Sed MachineOperand &MO = I->getOperand(i); 371263508Sdim if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) && 372198090Srdivacky !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 373193323Sed Candidates.reset(MO.getReg()); 374193323Sed } 375193323Sed 376210299Sed // Try to find a register that's unused if there is one, as then we won't 377221345Sdim // have to spill. Search explicitly rather than masking out based on 378221345Sdim // RegsAvailable, as RegsAvailable does not take aliases into account. 379221345Sdim // That's what getRegsAvailable() is for. 380221345Sdim BitVector Available = getRegsAvailable(RC); 381234353Sdim Available &= Candidates; 382234353Sdim if (Available.any()) 383234353Sdim Candidates = Available; 384210299Sed 385193323Sed // Find the register whose use is furthest away. 386198090Srdivacky MachineBasicBlock::iterator UseMI; 387198090Srdivacky unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 388193323Sed 389210299Sed // If we found an unused register there is no reason to spill it. 390212904Sdim if (!isAliasUsed(SReg)) { 391212904Sdim DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 392198090Srdivacky return SReg; 393212904Sdim } 394193323Sed 395249423Sdim // Find an available scavenging slot. 396249423Sdim unsigned SI; 397249423Sdim for (SI = 0; SI < Scavenged.size(); ++SI) 398249423Sdim if (Scavenged[SI].Reg == 0) 399249423Sdim break; 400193323Sed 401249423Sdim if (SI == Scavenged.size()) { 402249423Sdim // We need to scavenge a register but have no spill slot, the target 403249423Sdim // must know how to do it (if not, we'll assert below). 404249423Sdim Scavenged.push_back(ScavengedInfo()); 405249423Sdim } 406249423Sdim 407198090Srdivacky // Avoid infinite regress 408249423Sdim Scavenged[SI].Reg = SReg; 409198090Srdivacky 410198090Srdivacky // If the target knows how to save/restore the register, let it do so; 411198090Srdivacky // otherwise, use the emergency stack spill slot. 412198396Srdivacky if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 413198090Srdivacky // Spill the scavenged register before I. 414249423Sdim assert(Scavenged[SI].FrameIndex >= 0 && 415198090Srdivacky "Cannot scavenge register without an emergency spill slot!"); 416249423Sdim TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex, 417249423Sdim RC, TRI); 418198090Srdivacky MachineBasicBlock::iterator II = prior(I); 419198090Srdivacky 420249423Sdim unsigned FIOperandNum = getFrameIndexOperandNum(II); 421249423Sdim TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 422249423Sdim 423198090Srdivacky // Restore the scavenged register before its use (or first terminator). 424249423Sdim TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, 425249423Sdim RC, TRI); 426198396Srdivacky II = prior(UseMI); 427249423Sdim 428249423Sdim FIOperandNum = getFrameIndexOperandNum(II); 429249423Sdim TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); 430198396Srdivacky } 431198090Srdivacky 432249423Sdim Scavenged[SI].Restore = prior(UseMI); 433198090Srdivacky 434198090Srdivacky // Doing this here leads to infinite regress. 435249423Sdim // Scavenged[SI].Reg = SReg; 436193323Sed 437212904Sdim DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 438212904Sdim "\n"); 439212904Sdim 440193323Sed return SReg; 441193323Sed} 442