STATISTIC(NumModRefUnfold, "Number of modref unfolded");
namespace {
- enum RewriterName { simple, local };
+ enum RewriterName { local, trivial };
}
static cl::opt<RewriterName>
RewriterOpt("rewriter",
cl::desc("Rewriter to use: (default: local)"),
cl::Prefix,
- cl::values(clEnumVal(simple, "simple rewriter"),
- clEnumVal(local, "local rewriter"),
+ cl::values(clEnumVal(local, "local rewriter"),
+ clEnumVal(trivial, "trivial rewriter"),
clEnumValEnd),
cl::init(local));
VirtRegRewriter::~VirtRegRewriter() {}
-
-// ****************************** //
-// Simple Spiller Implementation //
-// ****************************** //
-struct VISIBILITY_HIDDEN SimpleRewriter : public VirtRegRewriter {
+
+/// This class is intended for use with the new spilling framework only. It
+/// rewrites vreg def/uses to use the assigned preg, but does not insert any
+/// spill code.
+struct VISIBILITY_HIDDEN TrivialRewriter : public VirtRegRewriter {
bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
LiveIntervals* LIs) {
DOUT << "********** REWRITE MACHINE CODE **********\n";
DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
- const TargetMachine &TM = MF.getTarget();
- const TargetInstrInfo &TII = *TM.getInstrInfo();
- const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
-
-
- // 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
- // operands). This is always smaller than the number of operands to the
- // current machine instr, so it should be small.
- std::vector<unsigned> LoadedRegs;
-
- for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
- MBBI != E; ++MBBI) {
- DOUT << MBBI->getBasicBlock()->getName() << ":\n";
- MachineBasicBlock &MBB = *MBBI;
- for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
- MII != E; ++MII) {
- MachineInstr &MI = *MII;
- for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI.getOperand(i);
- if (MO.isReg() && MO.getReg()) {
- if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
- unsigned VirtReg = MO.getReg();
- unsigned SubIdx = MO.getSubReg();
- unsigned PhysReg = VRM.getPhys(VirtReg);
- unsigned RReg = SubIdx ? TRI.getSubReg(PhysReg, SubIdx) : PhysReg;
- if (!VRM.isAssignedReg(VirtReg)) {
- int StackSlot = VRM.getStackSlot(VirtReg);
- const TargetRegisterClass* RC =
- MF.getRegInfo().getRegClass(VirtReg);
-
- if (MO.isUse() &&
- std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
- == LoadedRegs.end()) {
- TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
- MachineInstr *LoadMI = prior(MII);
- VRM.addSpillSlotUse(StackSlot, LoadMI);
- LoadedRegs.push_back(VirtReg);
- ++NumLoads;
- DOUT << '\t' << *LoadMI;
- }
+ MachineRegisterInfo *mri = &MF.getRegInfo();
- if (MO.isDef()) {
- TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true,
- StackSlot, RC);
- MachineInstr *StoreMI = next(MII);
- VRM.addSpillSlotUse(StackSlot, StoreMI);
- ++NumStores;
- }
- }
- MF.getRegInfo().setPhysRegUsed(RReg);
- MI.getOperand(i).setReg(RReg);
- MI.getOperand(i).setSubReg(0);
- } else {
- MF.getRegInfo().setPhysRegUsed(MO.getReg());
- }
- }
- }
+ bool changed = false;
- DOUT << '\t' << MI;
- LoadedRegs.clear();
+ for (LiveIntervals::iterator liItr = LIs->begin(), liEnd = LIs->end();
+ liItr != liEnd; ++liItr) {
+
+ if (TargetRegisterInfo::isVirtualRegister(liItr->first)) {
+ if (VRM.hasPhys(liItr->first)) {
+ unsigned preg = VRM.getPhys(liItr->first);
+ mri->replaceRegWith(liItr->first, preg);
+ mri->setPhysRegUsed(preg);
+ changed = true;
+ }
+ }
+ else {
+ if (!liItr->second->empty()) {
+ mri->setPhysRegUsed(liItr->first);
+ }
}
}
- return true;
+
+ return changed;
}
};
-
+
// ************************************************************************ //
/// AvailableSpills - As the local rewriter is scanning and rewriting an MBB
// Utility Functions //
// ****************** //
-/// InvalidateKill - A MI that defines the specified register is being deleted,
-/// invalidate the register kill information.
-static void InvalidateKill(unsigned Reg, BitVector &RegKills,
- std::vector<MachineOperand*> &KillOps) {
- if (RegKills[Reg]) {
- KillOps[Reg]->setIsKill(false);
- KillOps[Reg] = NULL;
- RegKills.reset(Reg);
- }
-}
-
/// findSinglePredSuccessor - Return via reference a vector of machine basic
/// blocks each of which is a successor of the specified BB and has no other
/// predecessor.
}
}
+/// InvalidateKill - Invalidate register kill information for a specific
+/// register. This also unsets the kills marker on the last kill operand.
+static void InvalidateKill(unsigned Reg,
+ const TargetRegisterInfo* TRI,
+ BitVector &RegKills,
+ std::vector<MachineOperand*> &KillOps) {
+ if (RegKills[Reg]) {
+ KillOps[Reg]->setIsKill(false);
+ // KillOps[Reg] might be a def of a super-register.
+ unsigned KReg = KillOps[Reg]->getReg();
+ KillOps[KReg] = NULL;
+ RegKills.reset(KReg);
+ for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
+ if (RegKills[*SR]) {
+ KillOps[*SR]->setIsKill(false);
+ KillOps[*SR] = NULL;
+ RegKills.reset(*SR);
+ }
+ }
+ }
+}
+
/// InvalidateKills - MI is going to be deleted. If any of its operands are
/// marked kill, then invalidate the information.
-static void InvalidateKills(MachineInstr &MI, BitVector &RegKills,
+static void InvalidateKills(MachineInstr &MI,
+ const TargetRegisterInfo* TRI,
+ BitVector &RegKills,
std::vector<MachineOperand*> &KillOps,
SmallVector<unsigned, 2> *KillRegs = NULL) {
for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
KillRegs->push_back(Reg);
assert(Reg < KillOps.size());
if (KillOps[Reg] == &MO) {
- RegKills.reset(Reg);
KillOps[Reg] = NULL;
+ RegKills.reset(Reg);
+ for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
+ if (RegKills[*SR]) {
+ KillOps[*SR] = NULL;
+ RegKills.reset(*SR);
+ }
+ }
}
}
}
/// UpdateKills - Track and update kill info. If a MI reads a register that is
/// marked kill, then it must be due to register reuse. Transfer the kill info
/// over.
-static void UpdateKills(MachineInstr &MI, BitVector &RegKills,
- std::vector<MachineOperand*> &KillOps,
- const TargetRegisterInfo* TRI) {
+static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI,
+ BitVector &RegKills,
+ std::vector<MachineOperand*> &KillOps) {
for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI.getOperand(i);
if (!MO.isReg() || !MO.isUse())
// That can't be right. Register is killed but not re-defined and it's
// being reused. Let's fix that.
KillOps[Reg]->setIsKill(false);
- KillOps[Reg] = NULL;
- RegKills.reset(Reg);
+ // KillOps[Reg] might be a def of a super-register.
+ unsigned KReg = KillOps[Reg]->getReg();
+ KillOps[KReg] = NULL;
+ RegKills.reset(KReg);
+
+ // Must be a def of a super-register. Its other sub-regsters are no
+ // longer killed as well.
+ for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
+ KillOps[*SR] = NULL;
+ RegKills.reset(*SR);
+ }
+
if (!MI.isRegTiedToDefOperand(i))
// Unless it's a two-address operand, this is the new kill.
MO.setIsKill();
if (MO.isKill()) {
RegKills.set(Reg);
KillOps[Reg] = &MO;
+ for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
+ RegKills.set(*SR);
+ KillOps[*SR] = &MO;
+ }
}
}
RegKills.reset(Reg);
KillOps[Reg] = NULL;
// It also defines (or partially define) aliases.
- for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
- RegKills.reset(*AS);
- KillOps[*AS] = NULL;
+ for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
+ RegKills.reset(*SR);
+ KillOps[*SR] = NULL;
}
}
}
NotAvailable.insert(Reg);
else {
MBB.addLiveIn(Reg);
- InvalidateKill(Reg, RegKills, KillOps);
+ InvalidateKill(Reg, TRI, RegKills, KillOps);
}
// Skip over the same register.
Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg);
--MII;
- UpdateKills(*MII, RegKills, KillOps, TRI);
+ UpdateKills(*MII, TRI, RegKills, KillOps);
DOUT << '\t' << *MII;
DOUT << "Reuse undone!\n";
}
}
+namespace {
+ struct RefSorter {
+ bool operator()(const std::pair<MachineInstr*, int> &A,
+ const std::pair<MachineInstr*, int> &B) {
+ return A.second < B.second;
+ }
+ };
+}
// ***************************** //
// Local Spiller Implementation //
AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
VRM.transferRestorePts(&MI, NewMIs[0]);
MII = MBB.insert(MII, NewMIs[0]);
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
++NumModRefUnfold;
AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
VRM.transferRestorePts(&NextMI, NewMIs[0]);
MBB.insert(NextMII, NewMIs[0]);
- InvalidateKills(NextMI, RegKills, KillOps);
+ InvalidateKills(NextMI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&NextMI);
MBB.erase(&NextMI);
++NumModRefUnfold;
+ if (NextMII == MBB.end())
+ break;
} while (FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM));
// Store the value back into SS.
VRM.assignVirt2Phys(UnfoldVR, UnfoldPR);
VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
MII = MBB.insert(MII, FoldedMI);
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
MF.DeleteMachineInstr(NewMI);
MII = MBB.insert(MII, FoldedMI); // Update MII to backtrack.
// Delete all 3 old instructions.
- InvalidateKills(*ReloadMI, RegKills, KillOps);
+ InvalidateKills(*ReloadMI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(ReloadMI);
MBB.erase(ReloadMI);
- InvalidateKills(*DefMI, RegKills, KillOps);
+ InvalidateKills(*DefMI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(DefMI);
MBB.erase(DefMI);
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
DOUT << "Removed dead store:\t" << *LastStore;
++NumDSE;
SmallVector<unsigned, 2> KillRegs;
- InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs);
+ InvalidateKills(*LastStore, TRI, RegKills, KillOps, &KillRegs);
MachineBasicBlock::iterator PrevMII = LastStore;
bool CheckDef = PrevMII != MBB.begin();
if (CheckDef)
/// removed. Find the last def or use and mark it as dead / kill.
void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
unsigned Reg, BitVector &RegKills,
- std::vector<MachineOperand*> &KillOps) {
- int LastUDDist = -1;
- MachineInstr *LastUDMI = NULL;
+ std::vector<MachineOperand*> &KillOps,
+ VirtRegMap &VRM) {
+ SmallPtrSet<MachineInstr*, 4> Seens;
+ SmallVector<std::pair<MachineInstr*, int>,8> Refs;
for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg),
RE = RegInfo->reg_end(); RI != RE; ++RI) {
MachineInstr *UDMI = &*RI;
DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
if (DI == DistanceMap.end() || DI->second > CurDist)
continue;
- if ((int)DI->second < LastUDDist)
- continue;
- LastUDDist = DI->second;
- LastUDMI = UDMI;
+ if (Seens.insert(UDMI))
+ Refs.push_back(std::make_pair(UDMI, DI->second));
}
- if (LastUDMI) {
+ if (Refs.empty())
+ return;
+ std::sort(Refs.begin(), Refs.end(), RefSorter());
+
+ while (!Refs.empty()) {
+ MachineInstr *LastUDMI = Refs.back().first;
+ Refs.pop_back();
+
MachineOperand *LastUD = NULL;
for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = LastUDMI->getOperand(i);
if (!LastUD || (LastUD->isUse() && MO.isDef()))
LastUD = &MO;
if (LastUDMI->isRegTiedToDefOperand(i))
- return;
+ break;
}
- if (LastUD->isDef())
- LastUD->setIsDead();
- else {
+ if (LastUD->isDef()) {
+ // If the instruction has no side effect, delete it and propagate
+ // backward further. Otherwise, mark is dead and we are done.
+ const TargetInstrDesc &TID = LastUDMI->getDesc();
+ if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
+ TID.hasUnmodeledSideEffects()) {
+ LastUD->setIsDead();
+ break;
+ }
+ VRM.RemoveMachineInstrFromMaps(LastUDMI);
+ MBB->erase(LastUDMI);
+ } else {
LastUD->setIsKill();
RegKills.set(Reg);
KillOps[Reg] = LastUD;
+ break;
}
}
}
MachineInstr *CopyMI = prior(MII);
MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg);
KillOpnd->setIsKill();
- UpdateKills(*CopyMI, RegKills, KillOps, TRI);
+ UpdateKills(*CopyMI, TRI, RegKills, KillOps);
DOUT << '\t' << *CopyMI;
++NumCopified;
// Remember it's available.
Spills.addAvailable(SSorRMId, Phys);
- UpdateKills(*prior(MII), RegKills, KillOps, TRI);
+ UpdateKills(*prior(MII), TRI, RegKills, KillOps);
DOUT << '\t' << *prior(MII);
}
}
TII->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC);
MachineInstr *CopyMI = prior(MII);
- UpdateKills(*CopyMI, RegKills, KillOps, TRI);
+ UpdateKills(*CopyMI, TRI, RegKills, KillOps);
// This invalidates DesignatedReg.
Spills.ClobberPhysReg(DesignatedReg);
KilledMIRegs.insert(VirtReg);
}
- UpdateKills(*prior(MII), RegKills, KillOps, TRI);
+ UpdateKills(*prior(MII), TRI, RegKills, KillOps);
DOUT << '\t' << *prior(MII);
}
unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
MachineInstr* DeadStore = MaybeDeadStores[PDSSlot];
if (DeadStore) {
DOUT << "Removed dead store:\t" << *DeadStore;
- InvalidateKills(*DeadStore, RegKills, KillOps);
+ InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(DeadStore);
MBB.erase(DeadStore);
MaybeDeadStores[PDSSlot] = NULL;
} else {
DOUT << "Removing now-noop copy: " << MI;
// Unset last kill since it's being reused.
- InvalidateKill(InReg, RegKills, KillOps);
+ InvalidateKill(InReg, TRI, RegKills, KillOps);
Spills.disallowClobberPhysReg(InReg);
}
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
Erased = true;
if (PhysReg &&
TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) {
MBB.insert(MII, NewMIs[0]);
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
Erased = true;
NewStore = NewMIs[1];
MBB.insert(MII, NewStore);
VRM.addSpillSlotUse(SS, NewStore);
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
Erased = true;
if (isDead) { // Previous store is dead.
// If we get here, the store is dead, nuke it now.
DOUT << "Removed dead store:\t" << *DeadStore;
- InvalidateKills(*DeadStore, RegKills, KillOps);
+ InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(DeadStore);
MBB.erase(DeadStore);
if (!NewStore)
++NumDCE;
DOUT << "Removing now-noop copy: " << MI;
SmallVector<unsigned, 2> KillRegs;
- InvalidateKills(MI, RegKills, KillOps, &KillRegs);
+ InvalidateKills(MI, TRI, RegKills, KillOps, &KillRegs);
if (MO.isDead() && !KillRegs.empty()) {
// Source register or an implicit super/sub-register use is killed.
assert(KillRegs[0] == Dst ||
TRI->isSubRegister(KillRegs[0], Dst) ||
TRI->isSuperRegister(KillRegs[0], Dst));
// Last def is now dead.
- TransferDeadness(&MBB, Dist, Src, RegKills, KillOps);
+ TransferDeadness(&MBB, Dist, Src, RegKills, KillOps, VRM);
}
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
++NumDCE;
DOUT << "Removing now-noop copy: " << MI;
- InvalidateKills(MI, RegKills, KillOps);
+ InvalidateKills(MI, TRI, RegKills, KillOps);
VRM.RemoveMachineInstrFromMaps(&MI);
MBB.erase(&MI);
Erased = true;
- UpdateKills(*LastStore, RegKills, KillOps, TRI);
+ UpdateKills(*LastStore, TRI, RegKills, KillOps);
goto ProcessNextInst;
}
}
DistanceMap.insert(std::make_pair(&MI, Dist++));
if (!Erased && !BackTracked) {
for (MachineBasicBlock::iterator II = &MI; II != NextMII; ++II)
- UpdateKills(*II, RegKills, KillOps, TRI);
+ UpdateKills(*II, TRI, RegKills, KillOps);
}
MII = NextMII;
}
default: assert(0 && "Unreachable!");
case local:
return new LocalRewriter();
- case simple:
- return new SimpleRewriter();
+ case trivial:
+ return new TrivialRewriter();
}
}