X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterScavenging.cpp;h=471cdcd832d4e41024c40d534458e485dcf2e38e;hb=49d0fee4f60bdecd7dba946aa64f405c9864bd8f;hp=d0d30e8f946d49b5d8659d46ee0985802d424ea2;hpb=9b294d4056f47bac5985de89c847aa1a04d38bf0;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp index d0d30e8f946..471cdcd832d 100644 --- a/lib/CodeGen/RegisterScavenging.cpp +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -14,7 +14,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "reg-scavenging" #include "llvm/CodeGen/RegisterScavenging.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" @@ -25,54 +24,49 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.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 (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) - RegsAvailable.reset(*SubRegs); -} +#define DEBUG_TYPE "reg-scavenging" -bool RegScavenger::isAliasUsed(unsigned Reg) const { - for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) - if (isUsed(*AI, *AI == Reg)) - 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; - ScavengeRestore = NULL; + for (SmallVectorImpl::iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) { + I->Reg = 0; + I->Restore = nullptr; + } - // All registers started out unused. - RegsAvailable.set(); + // All register units start out unused. + RegUnitsAvailable.set(); if (!MBB) return; // Live-in registers are in use. - for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), - E = MBB->livein_end(); I != E; ++I) - setUsed(*I); + for (unsigned LI : MBB->liveins()) + setRegUsed(LI); // Pristine CSRs are also unavailable. - BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); + const MachineFunction &MF = *MBB->getParent(); + BitVector PR = MF.getFrameInfo()->getPristineRegs(MF); 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 @@ -82,17 +76,11 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { // Self-initialize. if (!MBB) { - NumPhysRegs = TRI->getNumRegs(); - RegsAvailable.resize(NumPhysRegs); - KillRegs.resize(NumPhysRegs); - DefRegs.resize(NumPhysRegs); - - // Create callee-saved registers bitvector. - CalleeSavedRegs.resize(NumPhysRegs); - const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF); - 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); } MBB = mbb; @@ -101,65 +89,105 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { Tracking = false; } -void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { - BV.set(Reg); - for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) - BV.set(*SubRegs); +void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) { + for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) + BV.set(*RUI); } -void RegScavenger::forward() { - // Move ptr forward. - if (!Tracking) { - MBBI = MBB->begin(); - Tracking = true; - } else { - assert(MBBI != MBB->end() && "Already past the end of the basic block!"); - MBBI = llvm::next(MBBI); - } - assert(MBBI != MBB->end() && "Already at the end of the basic block!"); +void RegScavenger::determineKillsAndDefs() { + assert(Tracking && "Must be tracking to determine kills and defs"); MachineInstr *MI = MBBI; - - if (MI == ScavengeRestore) { - ScavengedReg = 0; - ScavengeRestore = NULL; - } - - if (MI->isDebugValue()) - return; + 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); - KillRegs.reset(); - DefRegs.reset(); + KillRegUnits.reset(); + DefRegUnits.reset(); for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegMask()) - (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); + 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. + KillRegUnits |= TmpRegUnits; + } if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; if (MO.isUse()) { // Ignore undef uses. if (MO.isUndef()) continue; - if (!isPred && MO.isKill()) - addRegWithSubRegs(KillRegs, Reg); + if (MO.isKill()) + addRegUnits(KillRegUnits, Reg); } else { assert(MO.isDef()); - if (!isPred && MO.isDead()) - addRegWithSubRegs(KillRegs, Reg); + if (MO.isDead()) + addRegUnits(KillRegUnits, Reg); else - addRegWithSubRegs(DefRegs, Reg); + addRegUnits(DefRegUnits, Reg); } } +} + +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); + } + + if (MBBI == MBB->begin()) { + MBBI = MachineBasicBlock::iterator(nullptr); + Tracking = false; + } else + --MBBI; +} + +void RegScavenger::forward() { + // Move ptr forward. + if (!Tracking) { + MBBI = MBB->begin(); + Tracking = true; + } else { + 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; + + for (SmallVectorImpl::iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) { + if (I->Restore != MI) + continue; + + I->Reg = 0; + I->Restore = nullptr; + } + + if (MI->isDebugValue()) + return; + + determineKillsAndDefs(); // Verify uses and defs. #ifndef NDEBUG @@ -168,12 +196,12 @@ void RegScavenger::forward() { if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; if (MO.isUse()) { if (MO.isUndef()) continue; - if (!isUsed(Reg)) { + if (!isRegUsed(Reg)) { // Check if it's partial live: e.g. // D0 = insert_subreg D0, S0 // ... D0 @@ -184,15 +212,23 @@ void RegScavenger::forward() { // insert_subreg around causes both correctness and performance issues. bool SubUsed = false; for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) - if (isUsed(*SubRegs)) { + if (isRegUsed(*SubRegs)) { SubUsed = true; break; } - if (!SubUsed) { - MBB->getParent()->verify(NULL, "In Register Scavenger"); + 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()); @@ -208,23 +244,23 @@ void RegScavenger::forward() { #endif // NDEBUG // Commit the changes. - setUnused(KillRegs); - setUsed(DefRegs); + setUnused(KillRegUnits); + setUsed(DefRegUnits); } -void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { - used = RegsAvailable; - used.flip(); - if (includeReserved) - used |= MRI->getReservedRegs(); - else - used.reset(MRI->getReservedRegs()); +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 *RC) const { for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; ++I) - if (!isAliasUsed(*I)) { + if (!isRegUsed(*I)) { DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << "\n"); return *I; @@ -238,13 +274,13 @@ BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { BitVector Mask(TRI->getNumRegs()); for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; ++I) - if (!isAliasUsed(*I)) + if (!isRegUsed(*I)) Mask.set(*I); return Mask; } /// findSurvivorReg - Return the candidate register that is unused for the -/// longest after StargMII. 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. @@ -334,15 +370,13 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *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() && MO.getReg() != 0 && + 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. Search explicitly rather than masking out based on - // RegsAvailable, as RegsAvailable does not take aliases into account. - // That's what getRegsAvailable() is for. + // have to spill. BitVector Available = getRegsAvailable(RC); Available &= Candidates; if (Available.any()) @@ -353,41 +387,52 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); // If we found an unused register there is no reason to spill it. - if (!isAliasUsed(SReg)) { + 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(ScavengingFrameIndex >= 0 && + assert(Scavenged[SI].FrameIndex >= 0 && "Cannot scavenge register without an emergency spill slot!"); - TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); - MachineBasicBlock::iterator II = prior(I); + 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, ScavengingFrameIndex, RC, TRI); - II = prior(UseMI); + TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex, + RC, TRI); + II = std::prev(UseMI); FIOperandNum = getFrameIndexOperandNum(II); TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this); } - ScavengeRestore = prior(UseMI); + Scavenged[SI].Restore = std::prev(UseMI); // Doing this here leads to infinite regress. - // ScavengedReg = SReg; + // Scavenged[SI].Reg = SReg; DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << "\n");