RegsAvailable.reset(SubReg);
}
-/// setUnused - Set the register and its sub-registers as being unused.
-void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
- RegsAvailable.set(Reg);
-
- for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
- unsigned SubReg = *SubRegs; ++SubRegs)
- RegsAvailable.set(SubReg);
-}
-
bool RegScavenger::isAliasUsed(unsigned Reg) const {
if (isUsed(Reg))
return true;
// Reserved registers are always used.
RegsAvailable ^= ReservedRegs;
- // Live-in registers are in use.
- if (!MBB || MBB->livein_empty())
+ if (!MBB)
return;
- for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
+
+ // Live-in registers are in use.
+ for (MachineBasicBlock::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) {
CalleeSavedRegs.set(CSRegs[i]);
}
- // RS used within emit{Pro,Epi}logue()
- if (mbb != MBB) {
- MBB = mbb;
- initRegState();
- }
+ MBB = mbb;
+ initRegState();
Tracking = false;
}
-void RegScavenger::restoreScavengedReg() {
- TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
- ScavengingFrameIndex, ScavengedRC);
- MachineBasicBlock::iterator II = prior(MBBI);
- TRI->eliminateFrameIndex(II, 0, this);
- setUsed(ScavengedReg);
- ScavengedReg = 0;
- ScavengedRC = NULL;
-}
-
-#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;
- }
- if (!isLiveIn)
- return false;
-
- // Is there any use of it before the specified MI?
- SmallPtrSet<MachineInstr*, 4> 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())
- 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;
-}
-#endif
-
void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
BV.set(Reg);
for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
Tracking = true;
} else {
assert(MBBI != MBB->end() && "Already at the end of the basic block!");
- MBBI = next(MBBI);
+ MBBI = llvm::next(MBBI);
}
MachineInstr *MI = MBBI;
ScavengeRestore = NULL;
}
+ if (MI->isDebugValue())
+ return;
+
// Find out which registers are early clobbered, killed, defined, and marked
// def-dead in this instruction.
BitVector EarlyClobberRegs(NumPhysRegs);
if (!Reg || isReserved(Reg))
continue;
if (MO.isUse()) {
- assert(isUsed(Reg) && "Using an undefined register!");
- assert(!EarlyClobberRegs.test(Reg) &&
+ if (!isUsed(Reg)) {
+ // Check if it's partial live: e.g.
+ // D0 = insert_subreg D0<undef>, 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
}
}
Mask.set(*I);
}
-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 *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;
+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;
}
-/// DistanceMap - Keep track the distance of an MI from the current position.
-typedef DenseMap<MachineInstr*, unsigned> DistanceMap;
+/// 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;
-/// Build a distance map for instructions from I to E.
-static void buildDistanceMap(DistanceMap &DM,
- MachineBasicBlock::iterator I,
- MachineBasicBlock::iterator E) {
- DM.clear();
- for (unsigned d = 0; I != E; ++I, ++d)
- DM.insert(DistanceMap::value_type(I, d));
-}
+ // Update whether we're in the live range of a virtual register
+ if (isVirtKillInsn) inVirtLiveRange = false;
+ if (isVirtDefInsn) inVirtLiveRange = true;
-/// findFirstUse - Calculate the distance to the first use of the
-/// specified register in the range covered by DM.
-static MachineInstr *findFirstUse(const MachineBasicBlock *MBB,
- const DistanceMap &DM,
- unsigned Reg,
- unsigned &Dist) {
- const MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
- MachineInstr *UseMI = 0;
- Dist = ~0U;
- for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
- RE = MRI->reg_end(); RI != RE; ++RI) {
- MachineInstr *UDMI = &*RI;
- if (UDMI->getParent() != MBB)
- continue;
- DistanceMap::const_iterator DI = DM.find(UDMI);
- if (DI == DM.end())
+ // Was our survivor untouched by this instruction?
+ if (Candidates.test(Survivor))
continue;
- if (DI->second < Dist) {
- Dist = DI->second;
- UseMI = UDMI;
- }
+
+ // All candidates gone?
+ if (Candidates.none())
+ break;
+
+ Survivor = Candidates.find_first();
}
- return UseMI;
+ // 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) {
- 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);
// 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 &&
+ !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
Candidates.reset(MO.getReg());
}
- // Prepare to call findFirstUse() a number of times.
- DistanceMap DM;
- buildDistanceMap(DM, I, MBB->end());
-
// Find the register whose use is furthest away.
- unsigned SReg = 0;
- unsigned MaxDist = 0;
- MachineInstr *MaxUseMI = 0;
- int Reg = Candidates.find_first();
- while (Reg != -1) {
- unsigned Dist;
- MachineInstr *UseMI = findFirstUse(MBB, DM, Reg, Dist);
- for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
- unsigned AsDist;
- MachineInstr *AsUseMI = findFirstUse(MBB, DM, *AS, AsDist);
- if (AsDist < Dist) {
- Dist = AsDist;
- UseMI = AsUseMI;
- }
- }
+ MachineBasicBlock::iterator UseMI;
+ unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
- // If we found an unused register that is defined by a later instruction,
- // 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(Reg) && UseMI != NULL)
- return Reg;
-
- if (Dist >= MaxDist) {
- MaxDist = Dist;
- MaxUseMI = UseMI;
- SReg = Reg;
- }
- Reg = Candidates.find_next(Reg);
- }
+ // 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;
- // Make sure SReg is marked as used. It could be considered available
- // if it is one of the callee saved registers, but hasn't been spilled.
- if (!isUsed(SReg)) {
- MBB->addLiveIn(SReg);
- setUsed(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);
}
- // Spill the scavenged register before I.
- TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
- MachineBasicBlock::iterator II = prior(I);
- TRI->eliminateFrameIndex(II, SPAdj, this);
+ ScavengeRestore = prior(UseMI);
- // Restore the scavenged register before its use (or first terminator).
- II = MaxUseMI
- ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
- TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
- ScavengeRestore = prior(II);
// Doing this here leads to infinite regress.
// ScavengedReg = SReg;
ScavengedRC = RC;
projects / oota-llvm.git / blobdiff