using namespace llvm;
STATISTIC(NumSpills, "Number of register spills");
+STATISTIC(NumReMats, "Number of re-materialization");
STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads , "Number of loads added");
STATISTIC(NumReused, "Number of values reused");
VirtRegMap::VirtRegMap(MachineFunction &mf)
: TII(*mf.getTarget().getInstrInfo()), MF(mf),
- Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT) {
+ Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT),
+ ReMatId(MAX_STACK_SLOT+1) {
grow();
}
assert(MRegisterInfo::isVirtualRegister(virtReg));
assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
"attempt to assign stack slot to already spilled register");
+ assert((frameIndex >= 0 ||
+ (frameIndex >= MF.getFrameInfo()->getObjectIndexBegin())) &&
+ "illegal fixed frame index");
Virt2StackSlotMap[virtReg] = frameIndex;
}
+int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
+ assert(MRegisterInfo::isVirtualRegister(virtReg));
+ assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
+ "attempt to assign re-mat id to already spilled register");
+ const MachineInstr *DefMI = getReMaterializedMI(virtReg);
+ int FrameIdx;
+ if (TII.isLoadFromStackSlot((MachineInstr*)DefMI, FrameIdx)) {
+ // Load from stack slot is re-materialize as reload from the stack slot!
+ Virt2StackSlotMap[virtReg] = FrameIdx;
+ return FrameIdx;
+ }
+ Virt2StackSlotMap[virtReg] = ReMatId;
+ return ReMatId++;
+}
+
void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
unsigned OpNo, MachineInstr *NewMI) {
// Move previous memory references folded to new instruction.
DOUT << "\n**** Local spiller rewriting function '"
<< MF.getFunction()->getName() << "':\n";
+ std::vector<MachineInstr *> ReMatedMIs;
for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
MBB != E; ++MBB)
- RewriteMBB(*MBB, VRM);
+ RewriteMBB(*MBB, VRM, ReMatedMIs);
+ for (unsigned i = 0, e = ReMatedMIs.size(); i != e; ++i)
+ delete ReMatedMIs[i];
return true;
}
private:
- void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM);
+ void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
+ std::vector<MachineInstr*> &ReMatedMIs);
};
}
// SpillSlotsAvailable - This map keeps track of all of the spilled virtual
// register values that are still available, due to being loaded or stored to,
- // but not invalidated yet.
- std::map<int, unsigned> SpillSlotsAvailable;
+ // but not invalidated yet. It also tracks the instructions that defined
+ // or used the register.
+ typedef std::pair<unsigned, std::vector<MachineInstr*> > SSInfo;
+ std::map<int, SSInfo> SpillSlotsAvailable;
// PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating
// which stack slot values are currently held by a physreg. This is used to
: MRI(mri), TII(tii) {
}
+ const MRegisterInfo *getRegInfo() const { return MRI; }
+
/// getSpillSlotPhysReg - If the specified stack slot is available in a
- /// physical register, return that PhysReg, otherwise return 0.
- unsigned getSpillSlotPhysReg(int Slot) const {
- std::map<int, unsigned>::const_iterator I = SpillSlotsAvailable.find(Slot);
- if (I != SpillSlotsAvailable.end())
- return I->second >> 1; // Remove the CanClobber bit.
+ /// physical register, return that PhysReg, otherwise return 0. It also
+ /// returns by reference the instruction that either defines or last uses
+ /// the register.
+ unsigned getSpillSlotPhysReg(int Slot, MachineInstr *&SSMI) const {
+ std::map<int, SSInfo>::const_iterator I = SpillSlotsAvailable.find(Slot);
+ if (I != SpillSlotsAvailable.end()) {
+ if (!I->second.second.empty())
+ SSMI = I->second.second.back();
+ return I->second.first >> 1; // Remove the CanClobber bit.
+ }
return 0;
}
-
- const MRegisterInfo *getRegInfo() const { return MRI; }
+ /// addLastUse - Add the last use information of all stack slots whose
+ /// values are available in the specific register.
+ void addLastUse(unsigned PhysReg, MachineInstr *Use) {
+ std::multimap<unsigned, int>::iterator I =
+ PhysRegsAvailable.lower_bound(PhysReg);
+ while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
+ int Slot = I->second;
+ I++;
+
+ std::map<int, SSInfo>::iterator II = SpillSlotsAvailable.find(Slot);
+ assert(II != SpillSlotsAvailable.end() && "Slot not available!");
+ unsigned Val = II->second.first;
+ assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!");
+ // This can be true if there are multiple uses of the same register.
+ if (II->second.second.back() != Use)
+ II->second.second.push_back(Use);
+ }
+ }
+
+ /// removeLastUse - Remove the last use information of all stack slots whose
+ /// values are available in the specific register.
+ void removeLastUse(unsigned PhysReg, MachineInstr *Use) {
+ std::multimap<unsigned, int>::iterator I =
+ PhysRegsAvailable.lower_bound(PhysReg);
+ while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
+ int Slot = I->second;
+ I++;
+
+ std::map<int, SSInfo>::iterator II = SpillSlotsAvailable.find(Slot);
+ assert(II != SpillSlotsAvailable.end() && "Slot not available!");
+ unsigned Val = II->second.first;
+ assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!");
+ if (II->second.second.back() == Use)
+ II->second.second.pop_back();
+ }
+ }
+
/// addAvailable - Mark that the specified stack slot is available in the
/// specified physreg. If CanClobber is true, the physreg can be modified at
/// any time without changing the semantics of the program.
- void addAvailable(int Slot, unsigned Reg, bool CanClobber = true) {
+ void addAvailable(int Slot, MachineInstr *MI, unsigned Reg,
+ bool CanClobber = true) {
// If this stack slot is thought to be available in some other physreg,
// remove its record.
ModifyStackSlot(Slot);
PhysRegsAvailable.insert(std::make_pair(Reg, Slot));
- SpillSlotsAvailable[Slot] = (Reg << 1) | (unsigned)CanClobber;
+ std::vector<MachineInstr*> DefUses;
+ DefUses.push_back(MI);
+ SpillSlotsAvailable[Slot] =
+ std::make_pair((Reg << 1) | (unsigned)CanClobber, DefUses);
- DOUT << "Remembering SS#" << Slot << " in physreg "
- << MRI->getName(Reg) << "\n";
+ if (Slot > VirtRegMap::MAX_STACK_SLOT)
+ DOUT << "Remembering RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1;
+ else
+ DOUT << "Remembering SS#" << Slot;
+ DOUT << " in physreg " << MRI->getName(Reg) << "\n";
}
/// canClobberPhysReg - Return true if the spiller is allowed to change the
/// stack slot must be available in a physreg for this query to make sense.
bool canClobberPhysReg(int Slot) const {
assert(SpillSlotsAvailable.count(Slot) && "Slot not available!");
- return SpillSlotsAvailable.find(Slot)->second & 1;
+ return SpillSlotsAvailable.find(Slot)->second.first & 1;
}
/// disallowClobberPhysReg - Unset the CanClobber bit of the specified
while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
int Slot = I->second;
I++;
- assert((SpillSlotsAvailable[Slot] >> 1) == PhysReg &&
+ assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg &&
"Bidirectional map mismatch!");
- SpillSlotsAvailable[Slot] &= ~1;
+ SpillSlotsAvailable[Slot].first &= ~1;
DOUT << "PhysReg " << MRI->getName(PhysReg)
<< " copied, it is available for use but can no longer be modified\n";
}
while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
int Slot = I->second;
PhysRegsAvailable.erase(I++);
- assert((SpillSlotsAvailable[Slot] >> 1) == PhysReg &&
+ assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg &&
"Bidirectional map mismatch!");
SpillSlotsAvailable.erase(Slot);
DOUT << "PhysReg " << MRI->getName(PhysReg)
- << " clobbered, invalidating SS#" << Slot << "\n";
+ << " clobbered, invalidating ";
+ if (Slot > VirtRegMap::MAX_STACK_SLOT)
+ DOUT << "RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
+ else
+ DOUT << "SS#" << Slot << "\n";
}
}
/// changes. This removes information about which register the previous value
/// for this slot lives in (as the previous value is dead now).
void AvailableSpills::ModifyStackSlot(int Slot) {
- std::map<int, unsigned>::iterator It = SpillSlotsAvailable.find(Slot);
+ std::map<int, SSInfo>::iterator It = SpillSlotsAvailable.find(Slot);
if (It == SpillSlotsAvailable.end()) return;
- unsigned Reg = It->second >> 1;
+ unsigned Reg = It->second.first >> 1;
SpillSlotsAvailable.erase(It);
// This register may hold the value of multiple stack slots, only remove this
MI->getOperand(NewOp.Operand).setReg(NewPhysReg);
- Spills.addAvailable(NewOp.StackSlot, NewPhysReg);
+ Spills.addAvailable(NewOp.StackSlot, MI, NewPhysReg);
++NumLoads;
DEBUG(MachineBasicBlock::iterator MII = MI;
DOUT << '\t' << *prior(MII));
/// rewriteMBB - Keep track of which spills are available even after the
/// register allocator is done with them. If possible, avoid reloading vregs.
-void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
-
+void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
+ std::vector<MachineInstr*> &ReMatedMIs) {
DOUT << MBB.getBasicBlock()->getName() << ":\n";
// Spills - Keep track of which spilled values are available in physregs so
// Loop over all of the implicit defs, clearing them from our available
// sets.
const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
+
+ // If this instruction is being rematerialized, just remove it!
+ int FrameIdx;
+ if ((TID->Flags & M_REMATERIALIZIBLE) ||
+ TII->isLoadFromStackSlot(&MI, FrameIdx)) {
+ bool Remove = true;
+ for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI.getOperand(i);
+ if (!MO.isRegister() || MO.getReg() == 0)
+ continue; // Ignore non-register operands.
+ if (MO.isDef() && !VRM.isReMaterialized(MO.getReg())) {
+ Remove = false;
+ break;
+ }
+ }
+ if (Remove) {
+ VRM.RemoveFromFoldedVirtMap(&MI);
+ ReMatedMIs.push_back(MI.removeFromParent());
+ MII = NextMII;
+ continue;
+ }
+ }
+
const unsigned *ImpDef = TID->ImplicitDefs;
if (ImpDef) {
for ( ; *ImpDef; ++ImpDef) {
if (!MO.isUse())
continue; // Handle defs in the loop below (handle use&def here though)
+ bool doReMat = VRM.isReMaterialized(VirtReg);
int StackSlot = VRM.getStackSlot(VirtReg);
unsigned PhysReg;
// Check to see if this stack slot is available.
- if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot))) {
-
+ MachineInstr *SSMI = NULL;
+ if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot, SSMI))) {
// This spilled operand might be part of a two-address operand. If this
// is the case, then changing it will necessarily require changing the
// def part of the instruction as well. However, in some cases, we
if (CanReuse) {
// If this stack slot value is already available, reuse it!
- DOUT << "Reusing SS#" << StackSlot << " from physreg "
+ if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
+ DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
+ else
+ DOUT << "Reusing SS#" << StackSlot;
+ DOUT << " from physreg "
<< MRI->getName(PhysReg) << " for vreg"
<< VirtReg <<" instead of reloading into physreg "
<< MRI->getName(VRM.getPhys(VirtReg)) << "\n";
MI.getOperand(i).setReg(PhysReg);
+ // Extend the live range of the MI that last kill the register if
+ // necessary.
+ bool WasKill = false;
+ if (SSMI) {
+ int UIdx = SSMI->findRegisterUseOperand(PhysReg, true);
+ if (UIdx != -1) {
+ MachineOperand &MOK = SSMI->getOperand(UIdx);
+ WasKill = MOK.isKill();
+ MOK.unsetIsKill();
+ }
+ }
+ if (ti == -1) {
+ // Unless it's the use of a two-address code, transfer the kill
+ // of the reused register to this use.
+ if (WasKill)
+ MI.getOperand(i).setIsKill();
+ Spills.addLastUse(PhysReg, &MI);
+ }
+
// The only technical detail we have is that we don't know that
// PhysReg won't be clobbered by a reloaded stack slot that occurs
// later in the instruction. In particular, consider 'op V1, V2'.
// incoming, we don't need to inserted a dead copy.
if (DesignatedReg == PhysReg) {
// If this stack slot value is already available, reuse it!
- DOUT << "Reusing SS#" << StackSlot << " from physreg "
- << MRI->getName(PhysReg) << " for vreg"
+ if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
+ DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
+ else
+ DOUT << "Reusing SS#" << StackSlot;
+ DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg"
<< VirtReg
<< " instead of reloading into same physreg.\n";
MI.getOperand(i).setReg(PhysReg);
PhysRegsUsed[DesignatedReg] = true;
ReusedOperands.markClobbered(DesignatedReg);
MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC);
-
+
+ // Extend the live range of the MI that last kill the register if
+ // necessary.
+ bool WasKill = false;
+ if (SSMI) {
+ int UIdx = SSMI->findRegisterUseOperand(PhysReg, true);
+ if (UIdx != -1) {
+ MachineOperand &MOK = SSMI->getOperand(UIdx);
+ WasKill = MOK.isKill();
+ MOK.unsetIsKill();
+ }
+ }
+ MachineInstr *CopyMI = prior(MII);
+ if (WasKill) {
+ // Transfer kill to the next use.
+ int UIdx = CopyMI->findRegisterUseOperand(PhysReg);
+ assert(UIdx != -1);
+ MachineOperand &MOU = CopyMI->getOperand(UIdx);
+ MOU.setIsKill();
+ }
+ Spills.addLastUse(PhysReg, CopyMI);
+
// This invalidates DesignatedReg.
Spills.ClobberPhysReg(DesignatedReg);
- Spills.addAvailable(StackSlot, DesignatedReg);
+ Spills.addAvailable(StackSlot, &MI, DesignatedReg);
MI.getOperand(i).setReg(DesignatedReg);
DOUT << '\t' << *prior(MII);
++NumReused;
PhysRegsUsed[PhysReg] = true;
ReusedOperands.markClobbered(PhysReg);
- MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
+ if (doReMat) {
+ MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg));
+ ++NumReMats;
+ } else {
+ MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
+ ++NumLoads;
+ }
// This invalidates PhysReg.
Spills.ClobberPhysReg(PhysReg);
// Any stores to this stack slot are not dead anymore.
- MaybeDeadStores.erase(StackSlot);
- Spills.addAvailable(StackSlot, PhysReg);
- ++NumLoads;
+ if (!doReMat)
+ MaybeDeadStores.erase(StackSlot);
+ Spills.addAvailable(StackSlot, &MI, PhysReg);
+ // Assumes this is the last use. IsKill will be unset if reg is reused
+ // unless it's a two-address operand.
+ if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1)
+ MI.getOperand(i).setIsKill();
MI.getOperand(i).setReg(PhysReg);
DOUT << '\t' << *prior(MII);
}
if (FrameIdx == SS) {
// If this spill slot is available, turn it into a copy (or nothing)
// instead of leaving it as a load!
- if (unsigned InReg = Spills.getSpillSlotPhysReg(SS)) {
+ MachineInstr *SSMI = NULL;
+ if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, SSMI)) {
DOUT << "Promoted Load To Copy: " << MI;
MachineFunction &MF = *MBB.getParent();
if (DestReg != InReg) {
// virtual or needing to clobber any values if it's physical).
NextMII = &MI;
--NextMII; // backtrack to the copy.
+ } else
+ DOUT << "Removing now-noop copy: " << MI;
+
+ // Either way, the live range of the last kill of InReg has been
+ // extended. Remove its kill.
+ bool WasKill = false;
+ if (SSMI) {
+ int UIdx = SSMI->findRegisterUseOperand(InReg, true);
+ if (UIdx != -1) {
+ MachineOperand &MOK = SSMI->getOperand(UIdx);
+ WasKill = MOK.isKill();
+ MOK.unsetIsKill();
+ }
}
+ if (NextMII != MBB.end()) {
+ // If NextMII uses InReg and the use is not a two address
+ // operand, mark it killed.
+ int UIdx = NextMII->findRegisterUseOperand(InReg);
+ if (UIdx != -1) {
+ MachineOperand &MOU = NextMII->getOperand(UIdx);
+ if (WasKill) {
+ const TargetInstrDescriptor *NTID =
+ NextMII->getInstrDescriptor();
+ if (UIdx >= NTID->numOperands ||
+ NTID->getOperandConstraint(UIdx, TOI::TIED_TO) == -1)
+ MOU.setIsKill();
+ }
+ Spills.addLastUse(InReg, &(*NextMII));
+ }
+ }
+
VRM.RemoveFromFoldedVirtMap(&MI);
MBB.erase(&MI);
goto ProcessNextInst;
// If the stack slot value was previously available in some other
// register, change it now. Otherwise, make the register available,
// in PhysReg.
- Spills.addAvailable(StackSlot, SrcReg, false /*don't clobber*/);
+ Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/);
}
}
}
if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
++NumDCE;
DOUT << "Removing now-noop copy: " << MI;
+ Spills.removeLastUse(Src, &MI);
MBB.erase(&MI);
VRM.RemoveFromFoldedVirtMap(&MI);
Spills.disallowClobberPhysReg(VirtReg);
assert(DestReg == VirtReg && "Unknown load situation!");
// Otherwise, if it wasn't available, remember that it is now!
- Spills.addAvailable(FrameIdx, DestReg);
+ Spills.addAvailable(FrameIdx, &MI, DestReg);
goto ProcessNextInst;
}
// in PhysReg.
Spills.ModifyStackSlot(StackSlot);
Spills.ClobberPhysReg(PhysReg);
- Spills.addAvailable(StackSlot, PhysReg);
+ Spills.addAvailable(StackSlot, LastStore, PhysReg);
++NumStores;
// Check to see if this is a noop copy. If so, eliminate the
if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
++NumDCE;
DOUT << "Removing now-noop copy: " << MI;
+ Spills.removeLastUse(Src, &MI);
MBB.erase(&MI);
VRM.RemoveFromFoldedVirtMap(&MI);
goto ProcessNextInst;
projects / oota-llvm.git / blobdiff