#define DEBUG_TYPE "virtregrewriter"
#include "VirtRegRewriter.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
STATISTIC(NumModRefUnfold, "Number of modref unfolded");
namespace {
- enum RewriterName { simple, local, trivial };
+ 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 {
-
- 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;
- }
-
- 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());
- }
- }
- }
- DOUT << '\t' << MI;
- LoadedRegs.clear();
- }
- }
- return true;
- }
-
-};
/// 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
std::vector<MachineOperand*> &KillOps) {
if (RegKills[Reg]) {
KillOps[Reg]->setIsKill(false);
- KillOps[Reg] = NULL;
- RegKills.reset(Reg);
- for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
+ // 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;
SmallVector<unsigned, 2> *KillRegs = NULL) {
for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI.getOperand(i);
- if (!MO.isReg() || !MO.isUse() || !MO.isKill())
+ if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
continue;
unsigned Reg = MO.getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg))
MachineOperand *DefOp = NULL;
for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = DefMI->getOperand(i);
- if (MO.isReg() && MO.isDef()) {
- if (MO.getReg() == Reg)
- DefOp = &MO;
- else if (!MO.isDead())
- HasLiveDef = true;
- }
+ if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
+ continue;
+ if (MO.getReg() == Reg)
+ DefOp = &MO;
+ else if (!MO.isDead())
+ HasLiveDef = true;
}
if (!DefOp)
return false;
std::vector<MachineOperand*> &KillOps) {
for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI.getOperand(i);
- if (!MO.isReg() || !MO.isUse())
+ if (!MO.isReg() || !MO.isUse() || MO.isUndef())
continue;
unsigned Reg = MO.getReg();
if (Reg == 0)
// 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();
// Unfold current MI.
SmallVector<MachineInstr*, 4> NewMIs;
if (!TII->unfoldMemoryOperand(MF, &MI, VirtReg, false, false, NewMIs))
- assert(0 && "Unable unfold the load / store folding instruction!");
+ LLVM_UNREACHABLE("Unable unfold the load / store folding instruction!");
assert(NewMIs.size() == 1);
AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
VRM.transferRestorePts(&MI, NewMIs[0]);
NextMII = next(NextMII);
NewMIs.clear();
if (!TII->unfoldMemoryOperand(MF, &NextMI, VirtReg, false, false, NewMIs))
- assert(0 && "Unable unfold the load / store folding instruction!");
+ LLVM_UNREACHABLE("Unable unfold the load / store folding instruction!");
assert(NewMIs.size() == 1);
AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
VRM.transferRestorePts(&NextMI, NewMIs[0]);
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.
return false;
}
+ /// CommuteChangesDestination - We are looking for r0 = op r1, r2 and
+ /// where SrcReg is r1 and it is tied to r0. Return true if after
+ /// commuting this instruction it will be r0 = op r2, r1.
+ static bool CommuteChangesDestination(MachineInstr *DefMI,
+ const TargetInstrDesc &TID,
+ unsigned SrcReg,
+ const TargetInstrInfo *TII,
+ unsigned &DstIdx) {
+ if (TID.getNumDefs() != 1 && TID.getNumOperands() != 3)
+ return false;
+ if (!DefMI->getOperand(1).isReg() ||
+ DefMI->getOperand(1).getReg() != SrcReg)
+ return false;
+ unsigned DefIdx;
+ if (!DefMI->isRegTiedToDefOperand(1, &DefIdx) || DefIdx != 0)
+ return false;
+ unsigned SrcIdx1, SrcIdx2;
+ if (!TII->findCommutedOpIndices(DefMI, SrcIdx1, SrcIdx2))
+ return false;
+ if (SrcIdx1 == 1 && SrcIdx2 == 2) {
+ DstIdx = 2;
+ return true;
+ }
+ return false;
+ }
+
/// CommuteToFoldReload -
/// Look for
/// r1 = load fi#1
unsigned NewDstIdx;
if (DefMII != MBB.begin() &&
TID.isCommutable() &&
- TII->CommuteChangesDestination(DefMI, NewDstIdx)) {
+ CommuteChangesDestination(DefMI, TID, SrcReg, TII, NewDstIdx)) {
MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
unsigned NewReg = NewDstMO.getReg();
if (!NewDstMO.isKill() || TRI->regsOverlap(NewReg, SrcReg))
if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
MachineInstr *DeadDef = PrevMII;
if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
- // FIXME: This assumes a remat def does not have side
- // effects.
+ // FIXME: This assumes a remat def does not have side effects.
VRM.RemoveMachineInstrFromMaps(DeadDef);
MBB.erase(DeadDef);
++NumDRM;
assert(RC && "Unable to determine register class!");
int SS = VRM.getEmergencySpillSlot(RC);
if (UsedSS.count(SS))
- assert(0 && "Need to spill more than one physical registers!");
+ LLVM_UNREACHABLE("Need to spill more than one physical registers!");
UsedSS.insert(SS);
TII->storeRegToStackSlot(MBB, MII, PhysReg, true, SS, RC);
MachineInstr *StoreMI = prior(MII);
if (MO.isImplicit())
// If the virtual register is implicitly defined, emit a implicit_def
// before so scavenger knows it's "defined".
+ // FIXME: This is a horrible hack done the by register allocator to
+ // remat a definition with virtual register operand.
VirtUseOps.insert(VirtUseOps.begin(), i);
else
VirtUseOps.push_back(i);
MI.getOperand(i).setReg(RReg);
MI.getOperand(i).setSubReg(0);
if (VRM.isImplicitlyDefined(VirtReg))
+ // FIXME: Is this needed?
BuildMI(MBB, &MI, MI.getDebugLoc(),
TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
continue;
if (!MO.isUse())
continue; // Handle defs in the loop below (handle use&def here though)
- bool AvoidReload = false;
- if (LIs->hasInterval(VirtReg)) {
- LiveInterval &LI = LIs->getInterval(VirtReg);
- if (!LI.liveAt(LIs->getUseIndex(LI.beginNumber())))
- // Must be defined by an implicit def. It should not be spilled. Note,
- // this is for correctness reason. e.g.
- // 8 %reg1024<def> = IMPLICIT_DEF
- // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
- // The live range [12, 14) are not part of the r1024 live interval since
- // it's defined by an implicit def. It will not conflicts with live
- // interval of r1025. Now suppose both registers are spilled, you can
- // easily see a situation where both registers are reloaded before
- // the INSERT_SUBREG and both target registers that would overlap.
- AvoidReload = true;
- }
-
+ bool AvoidReload = MO.isUndef();
+ // Check if it is defined by an implicit def. It should not be spilled.
+ // Note, this is for correctness reason. e.g.
+ // 8 %reg1024<def> = IMPLICIT_DEF
+ // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
+ // The live range [12, 14) are not part of the r1024 live interval since
+ // it's defined by an implicit def. It will not conflicts with live
+ // interval of r1025. Now suppose both registers are spilled, you can
+ // easily see a situation where both registers are reloaded before
+ // the INSERT_SUBREG and both target registers that would overlap.
bool DoReMat = VRM.isReMaterialized(VirtReg);
int SSorRMId = DoReMat
? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
if (!TargetRegisterInfo::isVirtualRegister(VirtReg)) {
// Check to see if this is a noop copy. If so, eliminate the
// instruction before considering the dest reg to be changed.
+ // Also check if it's copying from an "undef", if so, we can't
+ // eliminate this or else the undef marker is lost and it will
+ // confuses the scavenger. This is extremely rare.
unsigned Src, Dst, SrcSR, DstSR;
- if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
+ if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst &&
+ !MI.findRegisterUseOperand(Src)->isUndef()) {
++NumDCE;
DOUT << "Removing now-noop copy: " << MI;
SmallVector<unsigned, 2> KillRegs;
Spills.disallowClobberPhysReg(VirtReg);
goto ProcessNextInst;
}
-
+
// If it's not a no-op copy, it clobbers the value in the destreg.
Spills.ClobberPhysReg(VirtReg);
ReusedOperands.markClobbered(VirtReg);
llvm::VirtRegRewriter* llvm::createVirtRegRewriter() {
switch (RewriterOpt) {
- default: assert(0 && "Unreachable!");
+ default: LLVM_UNREACHABLE("Unreachable!");
case local:
return new LocalRewriter();
- case simple:
- return new SimpleRewriter();
case trivial:
return new TrivialRewriter();
}