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.
- typedef std::pair<unsigned, MachineInstr*> SSInfo;
+ // 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
unsigned getSpillSlotPhysReg(int Slot, MachineInstr *&SSMI) const {
std::map<int, SSInfo>::const_iterator I = SpillSlotsAvailable.find(Slot);
if (I != SpillSlotsAvailable.end()) {
- SSMI = I->second.second;
+ if (!I->second.second.empty())
+ SSMI = I->second.second.back();
return I->second.first >> 1; // Remove the CanClobber bit.
}
return 0;
}
+
+ /// 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
ModifyStackSlot(Slot);
PhysRegsAvailable.insert(std::make_pair(Reg, Slot));
+ std::vector<MachineInstr*> DefUses;
+ DefUses.push_back(MI);
SpillSlotsAvailable[Slot] =
- std::make_pair((Reg << 1) | (unsigned)CanClobber, MI);
+ 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
"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";
}
}
/// 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;
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";
// Extend the live range of the MI that last kill the register if
// necessary.
- MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true);
- if (MOK) {
- 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.
+ 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
// 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);
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);
+ if (!doReMat)
+ MaybeDeadStores.erase(StackSlot);
Spills.addAvailable(StackSlot, &MI, PhysReg);
- ++NumLoads;
+ // 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!
- MachineInstr *Dummy = NULL;
- if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, Dummy)) {
+ 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 (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);
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