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 << "********** Function: " << MF.getFunction()->getName() << '\n';
const TargetMachine &TM = MF.getTarget();
const MRegisterInfo &MRI = *TM.getRegisterInfo();
- bool *PhysRegsUsed = MF.getUsedPhysregs();
// LoadedRegs - Keep track of which vregs are loaded, so that we only load
// each vreg once (in the case where a spilled vreg is used by multiple
++NumStores;
}
}
- PhysRegsUsed[PhysReg] = true;
+ MF.setPhysRegUsed(PhysReg);
MI.getOperand(i).setReg(PhysReg);
} else {
- PhysRegsUsed[MO.getReg()] = true;
+ MF.setPhysRegUsed(MO.getReg());
}
}
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. It also tracks the instruction that last defined
+ // but not invalidated yet. It also tracks the instructions that defined
// or used the register.
- typedef std::pair<unsigned, MachineInstr*> SSInfo;
+ 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;
}
- /// UpdateLastUses - Update the last use information of all stack slots whose
+ /// 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 UpdateLastUse(unsigned PhysReg, MachineInstr *Use) {
+ void removeLastUse(unsigned PhysReg, MachineInstr *Use) {
std::multimap<unsigned, int>::iterator I =
PhysRegsAvailable.lower_bound(PhysReg);
while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
assert(II != SpillSlotsAvailable.end() && "Slot not available!");
unsigned Val = II->second.first;
assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!");
- SpillSlotsAvailable.erase(Slot);
- SpillSlotsAvailable[Slot] = std::make_pair(Val, Use);
+ if (II->second.second.back() == Use)
+ II->second.second.pop_back();
}
}
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
// same stack slot, the original store is deleted.
std::map<int, MachineInstr*> MaybeDeadStores;
- bool *PhysRegsUsed = MBB.getParent()->getUsedPhysregs();
-
+ MachineFunction &MF = *MBB.getParent();
for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
MII != E; ) {
MachineInstr &MI = *MII;
// 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) {
- PhysRegsUsed[*ImpDef] = true;
+ MF.setPhysRegUsed(*ImpDef);
ReusedOperands.markClobbered(*ImpDef);
Spills.ClobberPhysReg(*ImpDef);
}
if (MRegisterInfo::isPhysicalRegister(MO.getReg())) {
// Ignore physregs for spilling, but remember that it is used by this
// function.
- PhysRegsUsed[MO.getReg()] = true;
+ MF.setPhysRegUsed(MO.getReg());
ReusedOperands.markClobbered(MO.getReg());
continue;
}
if (!VRM.hasStackSlot(VirtReg)) {
// This virtual register was assigned a physreg!
unsigned Phys = VRM.getPhys(VirtReg);
- PhysRegsUsed[Phys] = true;
+ MF.setPhysRegUsed(Phys);
if (MO.isDef())
ReusedOperands.markClobbered(Phys);
MI.getOperand(i).setReg(Phys);
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.
- MI.getOperand(i).setIsKill();
- Spills.UpdateLastUse(PhysReg, &MI);
+ bool WasKill = false;
+ if (SSMI) {
+ int UIdx = SSMI->findRegisterUseOperandIdx(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
// 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);
continue;
}
- const TargetRegisterClass* RC =
- MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
-
- PhysRegsUsed[DesignatedReg] = true;
+ const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
+ MF.setPhysRegUsed(DesignatedReg);
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) {
- MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true);
- if (MOK) {
- MachineInstr *CopyMI = prior(MII);
- MachineOperand *MOU = CopyMI->findRegisterUseOperand(PhysReg);
- MOU->setIsKill();
- MOK->unsetIsKill();
- Spills.UpdateLastUse(PhysReg, &MI);
+ int UIdx = SSMI->findRegisterUseOperandIdx(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->findRegisterUseOperandIdx(PhysReg);
+ assert(UIdx != -1);
+ MachineOperand &MOU = CopyMI->getOperand(UIdx);
+ MOU.setIsKill();
+ }
+ Spills.addLastUse(PhysReg, CopyMI);
// This invalidates DesignatedReg.
Spills.ClobberPhysReg(DesignatedReg);
// Otherwise, reload it and remember that we have it.
PhysReg = VRM.getPhys(VirtReg);
assert(PhysReg && "Must map virtreg to physreg!");
- const TargetRegisterClass* RC =
- MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
+ const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
// Note that, if we reused a register for a previous operand, the
// register we want to reload into might not actually be
PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
Spills, MaybeDeadStores);
- PhysRegsUsed[PhysReg] = true;
+ MF.setPhysRegUsed(PhysReg);
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);
// 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();
- ++NumLoads;
MI.getOperand(i).setReg(PhysReg);
DOUT << '\t' << *prior(MII);
}
MachineInstr *SSMI = NULL;
if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, SSMI)) {
DOUT << "Promoted Load To Copy: " << MI;
- MachineFunction &MF = *MBB.getParent();
if (DestReg != InReg) {
MRI->copyRegToReg(MBB, &MI, DestReg, InReg,
MF.getSSARegMap()->getRegClass(VirtReg));
// Either way, the live range of the last kill of InReg has been
// extended. Remove its kill.
- MachineOperand *MOK = SSMI->findRegisterUseOperand(InReg, true);
- if (MOK && NextMII != MBB.end()) {
- MOK->unsetIsKill();
- // If NextMII uses InReg (must be the copy?), mark it killed.
- MachineOperand *MOU = NextMII->findRegisterUseOperand(InReg);
- if (MOU) {
- MOU->setIsKill();
- Spills.UpdateLastUse(InReg, &(*NextMII));
+ bool WasKill = false;
+ if (SSMI) {
+ int UIdx = SSMI->findRegisterUseOperandIdx(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->findRegisterUseOperandIdx(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));
}
}
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.UpdateLastUse(Src, NULL);
Spills.disallowClobberPhysReg(VirtReg);
goto ProcessNextInst;
}
// The only vregs left are stack slot definitions.
int StackSlot = VRM.getStackSlot(VirtReg);
- const TargetRegisterClass *RC =
- MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
+ const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(VirtReg);
// If this def is part of a two-address operand, make sure to execute
// the store from the correct physical register.
}
}
- PhysRegsUsed[PhysReg] = true;
+ MF.setPhysRegUsed(PhysReg);
ReusedOperands.markClobbered(PhysReg);
MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
DOUT << "Store:\t" << *next(MII);
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