X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterScavenging.cpp;h=ca02aa1b81436721f72eec90325ecdf7451f432e;hb=340d596509129de8c3fa9dbe4184a2b148b78757;hp=9fc3da3b170fbbca8d598d83ec04fea8b0d1c455;hpb=366e021fb2cb0efb8e727ef5e40bd55cef974c7a;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp index 9fc3da3b170..ca02aa1b814 100644 --- a/lib/CodeGen/RegisterScavenging.cpp +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -21,7 +21,9 @@ #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/Support/raw_ostream.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -64,7 +66,7 @@ void RegScavenger::initRegState() { 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); @@ -100,11 +102,8 @@ void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { CalleeSavedRegs.set(CSRegs[i]); } - // RS used within emit{Pro,Epi}logue() - if (mbb != MBB) { - MBB = mbb; - initRegState(); - } + MBB = mbb; + initRegState(); Tracking = false; } @@ -127,9 +126,10 @@ 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 = llvm::next(MBBI); } + assert(MBBI != MBB->end() && "Already at the end of the basic block!"); MachineInstr *MI = MBBI; @@ -139,27 +139,37 @@ void RegScavenger::forward() { ScavengeRestore = NULL; } + if (MI->isDebugValue()) + return; + // 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); 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()) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (!Reg || isReserved(Reg)) continue; if (MO.isUse()) { + // Ignore undef uses. + if (MO.isUndef()) + continue; // Two-address operands implicitly kill. - if (MO.isKill() || MI->isRegTiedToDefOperand(i)) + if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i))) addRegWithSubRegs(KillRegs, Reg); } else { assert(MO.isDef()); - if (MO.isDead()) + if (!isPred && MO.isDead()) addRegWithSubRegs(DeadRegs, Reg); else addRegWithSubRegs(DefRegs, Reg); @@ -171,13 +181,33 @@ void RegScavenger::forward() { // Verify uses and defs. 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)) continue; if (MO.isUse()) { - assert(isUsed(Reg) && "Using an undefined register!"); + if (MO.isUndef()) + continue; + 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!"); + (void)SubUsed; + } assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && "Using an early clobbered register!"); } else { @@ -205,29 +235,35 @@ void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 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); -} - unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; ++I) - if (!isAliasUsed(*I)) + if (!isAliasUsed(*I)) { + DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << + "\n"); return *I; + } return 0; } +/// 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 (!isAliasUsed(*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 StargMII. 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) { @@ -235,19 +271,41 @@ 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.isReg() || MO.isUndef() || !MO.getReg() || - TargetRegisterInfo::isVirtualRegister(MO.getReg())) + 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)) @@ -259,23 +317,22 @@ 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; } 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) { @@ -285,15 +342,24 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 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. + BitVector Available = getRegsAvailable(RC); + + if ((Candidates & 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 (!isAliasUsed(SReg)) { + DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); return SReg; + } assert(ScavengedReg == 0 && "Scavenger slot is live, unable to scavenge another register!"); @@ -301,17 +367,30 @@ unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, // Avoid infinite regress ScavengedReg = SReg; - // Spill the scavenged register before I. - TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); - MachineBasicBlock::iterator II = prior(I); - TRI->eliminateFrameIndex(II, SPAdj, this); + // 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,TRI); + MachineBasicBlock::iterator II = prior(I); + TRI->eliminateFrameIndex(II, SPAdj, this); + + // Restore the scavenged register before its use (or first terminator). + TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); + II = prior(UseMI); + TRI->eliminateFrameIndex(II, SPAdj, this); + } - // 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; + DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << + "\n"); + return SReg; }