X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterScavenging.cpp;h=67bf209c73250ab44ef32f98d0682d95f9379304;hb=030c4bfbc9885444b8a5ad0b5f1e50045a351d17;hp=9135edcfb9e23727287433c79002e495710d802b;hpb=0badfea274f9612780caccbad6e1870f39ed9f40;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp index 9135edcfb9e..67bf209c732 100644 --- a/lib/CodeGen/RegisterScavenging.cpp +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -2,124 +2,221 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the Evan Cheng and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements the machine register scavenger. It can provide -// information such as unused register at any point in a machine basic block. -// It also provides a mechanism to make registers availbale by evicting them -// to spill slots. +// information, such as unused registers, at any point in a machine basic block. +// It also provides a mechanism to make registers available by evicting them to +// spill slots. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "reg-scavenging" #include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Target/MRegisterInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Target/TargetRegisterInfo.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" using namespace llvm; -RegScavenger::RegScavenger(MachineBasicBlock *mbb) - : MBB(mbb), MBBI(mbb->begin()) { - const MachineFunction &MF = *MBB->getParent(); - const TargetMachine &TM = MF.getTarget(); - const MRegisterInfo *RegInfo = TM.getRegisterInfo(); +/// 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); +} + +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; +} - NumPhysRegs = RegInfo->getNumRegs(); - RegStates.resize(NumPhysRegs, true); +void RegScavenger::initRegState() { + ScavengedReg = 0; + ScavengedRC = NULL; + ScavengeRestore = NULL; - // Create reserved registers bitvector. - ReservedRegs = RegInfo->getReservedRegs(MF); - RegStates ^= ReservedRegs; + // All registers started out unused. + RegsAvailable.set(); - // Create callee-saved registers bitvector. - CalleeSavedRegs.resize(NumPhysRegs); - const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); - if (CSRegs != NULL) - for (unsigned i = 0; CSRegs[i]; ++i) - CalleeSavedRegs.set(CSRegs[i]); + // Reserved registers are always used. + RegsAvailable ^= ReservedRegs; + + if (!MBB) + return; // Live-in registers are in use. - if (!MBB->livein_empty()) - for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), - E = MBB->livein_end(); I != E; ++I) - setUsed(*I); + for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), + E = MBB->livein_end(); I != E; ++I) + setUsed(*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); +} + +void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { + MachineFunction &MF = *mbb->getParent(); + const TargetMachine &TM = MF.getTarget(); + TII = TM.getInstrInfo(); + TRI = TM.getRegisterInfo(); + MRI = &MF.getRegInfo(); + + assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && + "Target changed?"); + + // 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]); + } + + MBB = mbb; + initRegState(); + + Tracking = false; +} + +void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { + BV.set(Reg); + for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) + BV.set(*R); +} + +void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { + BV.set(Reg); + for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) + BV.set(*R); } void RegScavenger::forward() { + // Move ptr forward. + if (!Tracking) { + MBBI = MBB->begin(); + Tracking = true; + } else { + assert(MBBI != MBB->end() && "Already at the end of the basic block!"); + MBBI = llvm::next(MBBI); + } + MachineInstr *MI = MBBI; - // Process uses first. - BitVector ChangedRegs(NumPhysRegs); + + 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.isUse()) + if (!MO.isReg() || MO.isUndef()) continue; unsigned Reg = MO.getReg(); - if (Reg == 0) + if (!Reg || isReserved(Reg)) continue; - assert(isUsed(Reg)); - if (MO.isKill() && !isReserved(Reg)) - ChangedRegs.set(Reg); + + 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); + } } - // Change states of all registers after all the uses are processed to guard - // against multiple uses. - setUnused(ChangedRegs); - // Process defs. - const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); + // Verify uses and defs. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef()) + if (!MO.isReg() || MO.isUndef()) continue; unsigned Reg = MO.getReg(); - // Skip two-address destination operand. - if (TID->findTiedToSrcOperand(i) != -1) { - assert(isUsed(Reg)); + if (!Reg || isReserved(Reg)) continue; + if (MO.isUse()) { + if (!isUsed(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 (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + unsigned SubReg = *SubRegs; ++SubRegs) + if (isUsed(SubReg)) { + SubUsed = true; + break; + } + assert(SubUsed && "Using an undefined register!"); + } + assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && + "Using an early clobbered register!"); + } 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 } - assert(isUnused(Reg) || isReserved(Reg)); - if (!MO.isDead()) - setUsed(Reg); } - ++MBBI; + // Commit the changes. + setUnused(KillRegs); + setUnused(DeadRegs); + setUsed(DefRegs); } -void RegScavenger::backward() { - MachineInstr *MI = --MBBI; - // Process defs first. - const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef()) - continue; - // Skip two-address destination operand. - if (TID->findTiedToSrcOperand(i) != -1) - continue; - unsigned Reg = MO.getReg(); - assert(isUsed(Reg)); - if (!isReserved(Reg)) - setUnused(Reg); - } - - // Process uses. - BitVector ChangedRegs(NumPhysRegs); - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse()) - continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) - continue; - assert(isUnused(Reg) || isReserved(Reg)); - ChangedRegs.set(Reg); - } - setUsed(ChangedRegs); +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 @@ -130,19 +227,134 @@ static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { Mask.set(*I); } -unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, - bool ExCalleeSaved) const { +unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { + for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); + I != E; ++I) + if (!isAliasUsed(*I)) + return *I; + return 0; +} + +/// findSurvivorReg - Return the candidate register that is unused for the +/// longest after MBBI. UseMI is set to the instruction where the search +/// stopped. +/// +/// No more than InstrLimit instructions are inspected. +/// +unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, + BitVector &Candidates, + unsigned InstrLimit, + MachineBasicBlock::iterator &UseMI) { + int Survivor = Candidates.find_first(); + assert(Survivor > 0 && "No candidates for scavenging"); + + MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); + 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) { + 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.isReg() || MO.isUndef() || !MO.getReg()) + continue; + if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + if (MO.isDef()) + isVirtDefInsn = true; + else if (MO.isKill()) + isVirtKillInsn = true; + continue; + } + Candidates.reset(MO.getReg()); + for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) + Candidates.reset(*R); + } + // 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)) + continue; + + // All candidates gone? + if (Candidates.none()) + break; + + 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 = RestorePointMI; + return Survivor; +} + +unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, + MachineBasicBlock::iterator I, + int SPAdj) { // Mask off the registers which are not in the TargetRegisterClass. - BitVector RegStatesCopy(NumPhysRegs, false); - CreateRegClassMask(RegClass, RegStatesCopy); - RegStatesCopy &= RegStates; - - // If looking for a non-callee-saved register, mask off all the callee-saved - // registers. - if (ExCalleeSaved) - RegStatesCopy &= ~CalleeSavedRegs; - - // Returns the first unused (bit is set) register, or 0 is none is found. - int Reg = RegStatesCopy.find_first(); - return (Reg == -1) ? 0 : Reg; + BitVector Candidates(NumPhysRegs, false); + CreateRegClassMask(RC, Candidates); + // Do not include reserved registers. + Candidates ^= ReservedRegs & Candidates; + + // 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 && + !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + Candidates.reset(MO.getReg()); + } + + // 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)) + return SReg; + + assert(ScavengedReg == 0 && + "Scavenger slot is live, unable to scavenge another register!"); + + // Avoid infinite regress + ScavengedReg = 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 && + "Cannot scavenge register without an emergency spill slot!"); + TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); + MachineBasicBlock::iterator II = prior(I); + TRI->eliminateFrameIndex(II, SPAdj, NULL, this); + + // Restore the scavenged register before its use (or first terminator). + TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC); + II = prior(UseMI); + TRI->eliminateFrameIndex(II, SPAdj, NULL, this); + } + + ScavengeRestore = prior(UseMI); + + // Doing this here leads to infinite regress. + // ScavengedReg = SReg; + ScavengedRC = RC; + + return SReg; }