X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterScavenging.cpp;h=7626dd29c00a33e53ae2a01eafadf06e2e9ae53d;hb=24dbb798ff3003c52974cfa2e4275dfd2d35b512;hp=9faf597c4283f8ae32e49dfdc74045795b1aa990;hpb=66a39699fb6b862e674415b32d307263812e996e;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp index 9faf597c428..7626dd29c00 100644 --- a/lib/CodeGen/RegisterScavenging.cpp +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -14,150 +14,156 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "reg-scavenging" #include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; -/// setUsed - Set the register and its sub-registers as being used. -void RegScavenger::setUsed(unsigned Reg) { - RegsAvailable.reset(Reg); - - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) - RegsAvailable.reset(SubReg); -} +#define DEBUG_TYPE "reg-scavenging" -bool RegScavenger::isAliasUsed(unsigned Reg) const { - if (isUsed(Reg)) - return true; - for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) - if (isUsed(*R)) - return true; - return false; +/// setUsed - Set the register units of this register as used. +void RegScavenger::setRegUsed(unsigned Reg) { + for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) + RegUnitsAvailable.reset(*RUI); } void RegScavenger::initRegState() { - ScavengedReg = 0; - ScavengedRC = NULL; - ScavengeRestore = NULL; - - // All registers started out unused. - RegsAvailable.set(); + for (SmallVectorImpl::iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) { + I->Reg = 0; + I->Restore = nullptr; + } - // Reserved registers are always used. - RegsAvailable ^= ReservedRegs; + // All register units start out unused. + RegUnitsAvailable.set(); if (!MBB) return; // Live-in registers are in use. - for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), + for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), E = MBB->livein_end(); I != E; ++I) - setUsed(*I); + setRegUsed(*I); // Pristine CSRs are also unavailable. BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); for (int I = PR.find_first(); I>0; I = PR.find_next(I)) - setUsed(I); + setRegUsed(I); } void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { MachineFunction &MF = *mbb->getParent(); - const TargetMachine &TM = MF.getTarget(); - TII = TM.getInstrInfo(); - TRI = TM.getRegisterInfo(); + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); - assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && + assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) && "Target changed?"); + // It is not possible to use the register scavenger after late optimization + // passes that don't preserve accurate liveness information. + assert(MRI->tracksLiveness() && + "Cannot use register scavenger with inaccurate liveness"); + // Self-initialize. if (!MBB) { - NumPhysRegs = TRI->getNumRegs(); - RegsAvailable.resize(NumPhysRegs); - - // Create reserved registers bitvector. - ReservedRegs = TRI->getReservedRegs(MF); - - // Create callee-saved registers bitvector. - CalleeSavedRegs.resize(NumPhysRegs); - const unsigned *CSRegs = TRI->getCalleeSavedRegs(); - if (CSRegs != NULL) - for (unsigned i = 0; CSRegs[i]; ++i) - CalleeSavedRegs.set(CSRegs[i]); + NumRegUnits = TRI->getNumRegUnits(); + RegUnitsAvailable.resize(NumRegUnits); + KillRegUnits.resize(NumRegUnits); + DefRegUnits.resize(NumRegUnits); + TmpRegUnits.resize(NumRegUnits); } - // RS used within emit{Pro,Epi}logue() - if (mbb != MBB) { - MBB = mbb; - initRegState(); - } + MBB = mbb; + initRegState(); Tracking = false; } -#ifndef NDEBUG -/// isLiveInButUnusedBefore - Return true if register is livein the MBB not -/// not used before it reaches the MI that defines register. -static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, - MachineBasicBlock *MBB, - const TargetRegisterInfo *TRI, - MachineRegisterInfo* MRI) { - // First check if register is livein. - bool isLiveIn = false; - for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), - E = MBB->livein_end(); I != E; ++I) - if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { - isLiveIn = true; - break; +void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) { + for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) + BV.set(*RUI); +} + +void RegScavenger::determineKillsAndDefs() { + assert(Tracking && "Must be tracking to determine kills and defs"); + + MachineInstr *MI = MBBI; + assert(!MI->isDebugValue() && "Debug values have no kills or defs"); + + // Find out which registers are early clobbered, killed, defined, and marked + // def-dead in this instruction. + // FIXME: The scavenger is not predication aware. If the instruction is + // predicated, conservatively assume "kill" markers do not actually kill the + // register. Similarly ignores "dead" markers. + bool isPred = TII->isPredicated(MI); + KillRegUnits.reset(); + DefRegUnits.reset(); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isRegMask()) { + + TmpRegUnits.clear(); + for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) { + for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) { + if (MO.clobbersPhysReg(*RURI)) { + TmpRegUnits.set(RU); + break; + } + } + } + + // Apply the mask. + (isPred ? DefRegUnits : KillRegUnits) |= TmpRegUnits; } - if (!isLiveIn) - return false; - - // Is there any use of it before the specified MI? - SmallPtrSet UsesInMBB; - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), - UE = MRI->use_end(); UI != UE; ++UI) { - MachineOperand &UseMO = UI.getOperand(); - if (UseMO.isReg() && UseMO.isUndef()) + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; - MachineInstr *UseMI = &*UI; - if (UseMI->getParent() == MBB) - UsesInMBB.insert(UseMI); - } - if (UsesInMBB.empty()) - return true; - for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) - if (UsesInMBB.count(&*I)) - return false; - return true; + if (MO.isUse()) { + // Ignore undef uses. + if (MO.isUndef()) + continue; + if (!isPred && MO.isKill()) + addRegUnits(KillRegUnits, Reg); + } else { + assert(MO.isDef()); + if (!isPred && MO.isDead()) + addRegUnits(KillRegUnits, Reg); + else + addRegUnits(DefRegUnits, Reg); + } + } } -#endif -void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { - BV.set(Reg); - for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) - BV.set(*R); -} +void RegScavenger::unprocess() { + assert(Tracking && "Cannot unprocess because we're not tracking"); + + MachineInstr *MI = MBBI; + if (!MI->isDebugValue()) { + determineKillsAndDefs(); + + // Commit the changes. + setUsed(KillRegUnits); + setUnused(DefRegUnits); + } -void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { - BV.set(Reg); - for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) - BV.set(*R); + if (MBBI == MBB->begin()) { + MBBI = MachineBasicBlock::iterator(nullptr); + Tracking = false; + } else + --MBBI; } void RegScavenger::forward() { @@ -166,127 +172,124 @@ void RegScavenger::forward() { MBBI = MBB->begin(); Tracking = true; } else { - assert(MBBI != MBB->end() && "Already at the end of the basic block!"); - MBBI = next(MBBI); + assert(MBBI != MBB->end() && "Already past the end of the basic block!"); + MBBI = std::next(MBBI); } + assert(MBBI != MBB->end() && "Already at the end of the basic block!"); MachineInstr *MI = MBBI; - if (MI == ScavengeRestore) { - ScavengedReg = 0; - ScavengedRC = NULL; - ScavengeRestore = NULL; - } - - // Find out which registers are early clobbered, killed, defined, and marked - // def-dead in this instruction. - BitVector EarlyClobberRegs(NumPhysRegs); - BitVector KillRegs(NumPhysRegs); - BitVector DefRegs(NumPhysRegs); - BitVector DeadRegs(NumPhysRegs); - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || MO.isUndef()) - continue; - unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + for (SmallVectorImpl::iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) { + if (I->Restore != MI) continue; - if (MO.isUse()) { - // Two-address operands implicitly kill. - if (MO.isKill() || MI->isRegTiedToDefOperand(i)) - addRegWithSubRegs(KillRegs, Reg); - } else { - assert(MO.isDef()); - if (MO.isDead()) - addRegWithSubRegs(DeadRegs, Reg); - else - addRegWithSubRegs(DefRegs, Reg); - if (MO.isEarlyClobber()) - addRegWithAliases(EarlyClobberRegs, Reg); - } + I->Reg = 0; + I->Restore = nullptr; } + if (MI->isDebugValue()) + return; + + determineKillsAndDefs(); + // Verify uses and defs. +#ifndef NDEBUG for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || MO.isUndef()) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; if (MO.isUse()) { - assert(isUsed(Reg) && "Using an undefined register!"); - assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && - "Using an early clobbered register!"); + if (MO.isUndef()) + continue; + if (!isRegUsed(Reg)) { + // Check if it's partial live: e.g. + // D0 = insert_subreg D0, S0 + // ... D0 + // The problem is the insert_subreg could be eliminated. The use of + // D0 is using a partially undef value. This is not *incorrect* since + // S1 is can be freely clobbered. + // Ideally we would like a way to model this, but leaving the + // insert_subreg around causes both correctness and performance issues. + bool SubUsed = false; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) + if (isRegUsed(*SubRegs)) { + SubUsed = true; + break; + } + bool SuperUsed = false; + for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) { + if (isRegUsed(*SR)) { + SuperUsed = true; + break; + } + } + if (!SubUsed && !SuperUsed) { + MBB->getParent()->verify(nullptr, "In Register Scavenger"); + llvm_unreachable("Using an undefined register!"); + } + (void)SubUsed; + (void)SuperUsed; + } } else { assert(MO.isDef()); +#if 0 + // FIXME: Enable this once we've figured out how to correctly transfer + // implicit kills during codegen passes like the coalescer. assert((KillRegs.test(Reg) || isUnused(Reg) || isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && "Re-defining a live register!"); +#endif } } +#endif // NDEBUG // Commit the changes. - setUnused(KillRegs); - setUnused(DeadRegs); - setUsed(DefRegs); + setUnused(KillRegUnits); + setUsed(DefRegUnits); } -void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { - if (includeReserved) - used = ~RegsAvailable; - else - used = ~RegsAvailable & ~ReservedRegs; -} - -/// CreateRegClassMask - Set the bits that represent the registers in the -/// TargetRegisterClass. -static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { - for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; - ++I) - Mask.set(*I); +bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const { + if (includeReserved && isReserved(Reg)) + return true; + for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) + if (!RegUnitsAvailable.test(*RUI)) + return true; + return false; } -unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, - const BitVector &Candidates) const { - // Mask off the registers which are not in the TargetRegisterClass. - BitVector RegsAvailableCopy(NumPhysRegs, false); - CreateRegClassMask(RegClass, RegsAvailableCopy); - RegsAvailableCopy &= RegsAvailable; - - // Restrict the search to candidates. - RegsAvailableCopy &= Candidates; - - // Returns the first unused (bit is set) register, or 0 is none is found. - int Reg = RegsAvailableCopy.find_first(); - return (Reg == -1) ? 0 : Reg; +unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { + for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); + I != E; ++I) + if (!isRegUsed(*I)) { + DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << + "\n"); + return *I; + } + return 0; } -unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, - bool ExCalleeSaved) const { - // Mask off the registers which are not in the TargetRegisterClass. - BitVector RegsAvailableCopy(NumPhysRegs, false); - CreateRegClassMask(RegClass, RegsAvailableCopy); - RegsAvailableCopy &= RegsAvailable; - - // If looking for a non-callee-saved register, mask off all the callee-saved - // registers. - if (ExCalleeSaved) - RegsAvailableCopy &= ~CalleeSavedRegs; - - // Returns the first unused (bit is set) register, or 0 is none is found. - int Reg = RegsAvailableCopy.find_first(); - return (Reg == -1) ? 0 : Reg; +/// getRegsAvailable - Return all available registers in the register class +/// in Mask. +BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { + BitVector Mask(TRI->getNumRegs()); + for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); + I != E; ++I) + if (!isRegUsed(*I)) + Mask.set(*I); + return Mask; } /// findSurvivorReg - Return the candidate register that is unused for the -/// longest after MBBI. UseMI is set to the instruction where the search +/// longest after StartMII. UseMI is set to the instruction where the search /// stopped. /// /// No more than InstrLimit instructions are inspected. /// -unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI, +unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, BitVector &Candidates, unsigned InstrLimit, MachineBasicBlock::iterator &UseMI) { @@ -294,18 +297,42 @@ unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI, assert(Survivor > 0 && "No candidates for scavenging"); MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); - assert(MI != ME && "MI already at terminator"); + assert(StartMI != ME && "MI already at terminator"); + MachineBasicBlock::iterator RestorePointMI = StartMI; + MachineBasicBlock::iterator MI = StartMI; + bool inVirtLiveRange = false; for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { + if (MI->isDebugValue()) { + ++InstrLimit; // Don't count debug instructions + continue; + } + bool isVirtKillInsn = false; + bool isVirtDefInsn = false; // Remove any candidates touched by instruction. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); + if (MO.isRegMask()) + Candidates.clearBitsNotInMask(MO.getRegMask()); if (!MO.isReg() || MO.isUndef() || !MO.getReg()) continue; - Candidates.reset(MO.getReg()); - for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) - Candidates.reset(*R); + if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + if (MO.isDef()) + isVirtDefInsn = true; + else if (MO.isKill()) + isVirtKillInsn = true; + continue; + } + for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) + Candidates.reset(*AI); } + // If we're not in a virtual reg's live range, this is a valid + // restore point. + if (!inVirtLiveRange) RestorePointMI = MI; + + // Update whether we're in the live range of a virtual register + if (isVirtKillInsn) inVirtLiveRange = false; + if (isVirtDefInsn) inVirtLiveRange = true; // Was our survivor untouched by this instruction? if (Candidates.test(Survivor)) @@ -317,58 +344,102 @@ unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI, Survivor = Candidates.find_first(); } + // If we ran off the end, that's where we want to restore. + if (MI == ME) RestorePointMI = ME; + assert (RestorePointMI != StartMI && + "No available scavenger restore location!"); // We ran out of candidates, so stop the search. - UseMI = MI; + UseMI = RestorePointMI; return Survivor; } +static unsigned getFrameIndexOperandNum(MachineInstr *MI) { + unsigned i = 0; + while (!MI->getOperand(i).isFI()) { + ++i; + assert(i < MI->getNumOperands() && + "Instr doesn't have FrameIndex operand!"); + } + return i; +} + unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, MachineBasicBlock::iterator I, int SPAdj) { - assert(ScavengingFrameIndex >= 0 && - "Cannot scavenge a register without an emergency spill slot!"); - - // Mask off the registers which are not in the TargetRegisterClass. - BitVector Candidates(NumPhysRegs, false); - CreateRegClassMask(RC, Candidates); - // Do not include reserved registers. - Candidates ^= ReservedRegs & Candidates; + // Consider all allocatable registers in the register class initially + BitVector Candidates = + TRI->getAllocatableSet(*I->getParent()->getParent(), RC); // Exclude all the registers being used by the instruction. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { MachineOperand &MO = I->getOperand(i); - if (MO.isReg()) + if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) && + !TargetRegisterInfo::isVirtualRegister(MO.getReg())) Candidates.reset(MO.getReg()); } + // Try to find a register that's unused if there is one, as then we won't + // have to spill. + BitVector Available = getRegsAvailable(RC); + Available &= Candidates; + if (Available.any()) + Candidates = Available; + // Find the register whose use is furthest away. MachineBasicBlock::iterator UseMI; unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); - // If we found an unused register there is no reason to spill it. We have - // probably found a callee-saved register that has been saved in the - // prologue, but happens to be unused at this point. - if (!isAliasUsed(SReg)) + // If we found an unused register there is no reason to spill it. + if (!isRegUsed(SReg)) { + DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); return SReg; + } - assert(ScavengedReg == 0 && - "Scavenger slot is live, unable to scavenge another register!"); + // Find an available scavenging slot. + unsigned SI; + for (SI = 0; SI < Scavenged.size(); ++SI) + if (Scavenged[SI].Reg == 0) + break; + + if (SI == Scavenged.size()) { + // We need to scavenge a register but have no spill slot, the target + // must know how to do it (if not, we'll assert below). + Scavenged.push_back(ScavengedInfo()); + } // Avoid infinite regress - ScavengedReg = SReg; + Scavenged[SI].Reg = SReg; + + // If the target knows how to save/restore the register, let it do so; + // otherwise, use the emergency stack spill slot. + if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { + // Spill the scavenged register before I. + assert(Scavenged[SI].FrameIndex >= 0 && + "Cannot scavenge register without an emergency spill slot!"); + TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex, + RC, TRI); + MachineBasicBlock::iterator II = std::prev(I); + + unsigned FIOperandNum = getFrameIndexOperandNum(II); + TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); + + // Restore the scavenged register before its use (or first terminator). + TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, + RC, TRI); + II = std::prev(UseMI); + + FIOperandNum = getFrameIndexOperandNum(II); + TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); + } - // Spill the scavenged register before I. - TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); - MachineBasicBlock::iterator II = prior(I); - TRI->eliminateFrameIndex(II, SPAdj, this); + Scavenged[SI].Restore = std::prev(UseMI); - // Restore the scavenged register before its use (or first terminator). - TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); - ScavengeRestore = prior(UseMI); // Doing this here leads to infinite regress. - // ScavengedReg = SReg; - ScavengedRC = RC; + // Scavenged[SI].Reg = SReg; + + DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << + "\n"); return SReg; }