X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegRewriter.cpp;h=054c3b631b96a5b7b2203c39b687962635e64ba5;hb=ce90c245ffee6fbd7cb569a6a53682feb12d5983;hp=025ce1bd30923a2eaa60774974b2e0750fe49c8b;hpb=87e3bcab736e5af501b1cfbf880563d3d2244497;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegRewriter.cpp b/lib/CodeGen/VirtRegRewriter.cpp index 025ce1bd309..054c3b631b9 100644 --- a/lib/CodeGen/VirtRegRewriter.cpp +++ b/lib/CodeGen/VirtRegRewriter.cpp @@ -9,10 +9,18 @@ #define DEBUG_TYPE "virtregrewriter" #include "VirtRegRewriter.h" -#include "llvm/Support/Compiler.h" +#include "llvm/Function.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetLowering.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" #include using namespace llvm; @@ -33,101 +41,89 @@ STATISTIC(NumSUnfold , "Number of stores unfolded"); STATISTIC(NumModRefUnfold, "Number of modref unfolded"); namespace { - enum RewriterName { simple, local }; + enum RewriterName { local, trivial }; } static cl::opt 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)); +static cl::opt +ScheduleSpills("schedule-spills", + cl::desc("Schedule spill code"), + cl::init(false)); + VirtRegRewriter::~VirtRegRewriter() {} - -// ****************************** // -// Simple Spiller Implementation // -// ****************************** // +namespace { -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 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 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; - } + DEBUG(errs() << "********** REWRITE MACHINE CODE **********\n"); + DEBUG(errs() << "********** Function: " + << MF.getFunction()->getName() << '\n'); + DEBUG(errs() << "**** Machine Instrs" + << "(NOTE! Does not include spills and reloads!) ****\n"); + DEBUG(MF.dump()); - 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()); - } - } - } + MachineRegisterInfo *mri = &MF.getRegInfo(); + const TargetRegisterInfo *tri = MF.getTarget().getRegisterInfo(); - DOUT << '\t' << MI; - LoadedRegs.clear(); + bool changed = false; + + for (LiveIntervals::iterator liItr = LIs->begin(), liEnd = LIs->end(); + liItr != liEnd; ++liItr) { + + const LiveInterval *li = liItr->second; + unsigned reg = li->reg; + + if (TargetRegisterInfo::isPhysicalRegister(reg)) { + if (!li->empty()) + mri->setPhysRegUsed(reg); + } + else { + if (!VRM.hasPhys(reg)) + continue; + unsigned pReg = VRM.getPhys(reg); + mri->setPhysRegUsed(pReg); + for (MachineRegisterInfo::reg_iterator regItr = mri->reg_begin(reg), + regEnd = mri->reg_end(); regItr != regEnd;) { + MachineOperand &mop = regItr.getOperand(); + assert(mop.isReg() && mop.getReg() == reg && "reg_iterator broken?"); + ++regItr; + unsigned subRegIdx = mop.getSubReg(); + unsigned pRegOp = subRegIdx ? tri->getSubReg(pReg, subRegIdx) : pReg; + mop.setReg(pRegOp); + mop.setSubReg(0); + changed = true; + } } } - return true; + + DEBUG(errs() << "**** Post Machine Instrs ****\n"); + DEBUG(MF.dump()); + + return changed; } }; - + +} + // ************************************************************************ // +namespace { + /// AvailableSpills - As the local rewriter is scanning and rewriting an MBB /// from top down, keep track of which spill slots or remat are available in /// each register. @@ -139,7 +135,7 @@ struct VISIBILITY_HIDDEN SimpleRewriter : public VirtRegRewriter { /// on a per-stack-slot / remat id basis as the low bit in the value of the /// SpillSlotsAvailable entries. The predicate 'canClobberPhysReg()' checks /// this bit and addAvailable sets it if. -class VISIBILITY_HIDDEN AvailableSpills { +class AvailableSpills { const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; @@ -195,10 +191,11 @@ public: (unsigned)CanClobber; if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) - DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1; + DEBUG(errs() << "Remembering RM#" + << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1); else - DOUT << "Remembering SS#" << SlotOrReMat; - DOUT << " in physreg " << TRI->getName(Reg) << "\n"; + DEBUG(errs() << "Remembering SS#" << SlotOrReMat); + DEBUG(errs() << " in physreg " << TRI->getName(Reg) << "\n"); } /// canClobberPhysRegForSS - Return true if the spiller is allowed to change @@ -250,8 +247,82 @@ public: std::vector &KillOps); }; +} + // ************************************************************************ // +// Given a location where a reload of a spilled register or a remat of +// a constant is to be inserted, attempt to find a safe location to +// insert the load at an earlier point in the basic-block, to hide +// latency of the load and to avoid address-generation interlock +// issues. +static MachineBasicBlock::iterator +ComputeReloadLoc(MachineBasicBlock::iterator const InsertLoc, + MachineBasicBlock::iterator const Begin, + unsigned PhysReg, + const TargetRegisterInfo *TRI, + bool DoReMat, + int SSorRMId, + const TargetInstrInfo *TII, + const MachineFunction &MF) +{ + if (!ScheduleSpills) + return InsertLoc; + + // Spill backscheduling is of primary interest to addresses, so + // don't do anything if the register isn't in the register class + // used for pointers. + + const TargetLowering *TL = MF.getTarget().getTargetLowering(); + + if (!TL->isTypeLegal(TL->getPointerTy())) + // Believe it or not, this is true on PIC16. + return InsertLoc; + + const TargetRegisterClass *ptrRegClass = + TL->getRegClassFor(TL->getPointerTy()); + if (!ptrRegClass->contains(PhysReg)) + return InsertLoc; + + // Scan upwards through the preceding instructions. If an instruction doesn't + // reference the stack slot or the register we're loading, we can + // backschedule the reload up past it. + MachineBasicBlock::iterator NewInsertLoc = InsertLoc; + while (NewInsertLoc != Begin) { + MachineBasicBlock::iterator Prev = prior(NewInsertLoc); + for (unsigned i = 0; i < Prev->getNumOperands(); ++i) { + MachineOperand &Op = Prev->getOperand(i); + if (!DoReMat && Op.isFI() && Op.getIndex() == SSorRMId) + goto stop; + } + if (Prev->findRegisterUseOperandIdx(PhysReg) != -1 || + Prev->findRegisterDefOperand(PhysReg)) + goto stop; + for (const unsigned *Alias = TRI->getAliasSet(PhysReg); *Alias; ++Alias) + if (Prev->findRegisterUseOperandIdx(*Alias) != -1 || + Prev->findRegisterDefOperand(*Alias)) + goto stop; + NewInsertLoc = Prev; + } +stop:; + + // If we made it to the beginning of the block, turn around and move back + // down just past any existing reloads. They're likely to be reloads/remats + // for instructions earlier than what our current reload/remat is for, so + // they should be scheduled earlier. + if (NewInsertLoc == Begin) { + int FrameIdx; + while (InsertLoc != NewInsertLoc && + (TII->isLoadFromStackSlot(NewInsertLoc, FrameIdx) || + TII->isTriviallyReMaterializable(NewInsertLoc))) + ++NewInsertLoc; + } + + return NewInsertLoc; +} + +namespace { + // ReusedOp - For each reused operand, we keep track of a bit of information, // in case we need to rollback upon processing a new operand. See comments // below. @@ -279,7 +350,7 @@ struct ReusedOp { /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that /// is reused instead of reloaded. -class VISIBILITY_HIDDEN ReuseInfo { +class ReuseInfo { MachineInstr &MI; std::vector Reuses; BitVector PhysRegsClobbered; @@ -317,7 +388,8 @@ public: /// GetRegForReload - We are about to emit a reload into PhysReg. If there /// is some other operand that is using the specified register, either pick /// a new register to use, or evict the previous reload and use this reg. - unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, + unsigned GetRegForReload(const TargetRegisterClass *RC, unsigned PhysReg, + MachineFunction &MF, MachineInstr *MI, AvailableSpills &Spills, std::vector &MaybeDeadStores, SmallSet &Rejected, @@ -336,34 +408,26 @@ public: /// sees r1 is taken by t2, tries t2's reload register r0 /// sees r0 is taken by t3, tries t3's reload register r1 /// sees r1 is taken by t2, tries t2's reload register r0 ... - unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, + unsigned GetRegForReload(unsigned VirtReg, unsigned PhysReg, MachineInstr *MI, AvailableSpills &Spills, std::vector &MaybeDeadStores, BitVector &RegKills, std::vector &KillOps, VirtRegMap &VRM) { SmallSet Rejected; - return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected, - RegKills, KillOps, VRM); + MachineFunction &MF = *MI->getParent()->getParent(); + const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(VirtReg); + return GetRegForReload(RC, PhysReg, MF, MI, Spills, MaybeDeadStores, + Rejected, RegKills, KillOps, VRM); } }; +} // ****************** // // 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 &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. @@ -377,14 +441,38 @@ static void findSinglePredSuccessor(MachineBasicBlock *MBB, } } +/// 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 &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 &KillOps, SmallVector *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)) @@ -393,31 +481,38 @@ static void InvalidateKills(MachineInstr &MI, BitVector &RegKills, 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); + } + } } } } /// InvalidateRegDef - If the def operand of the specified def MI is now dead -/// (since it's spill instruction is removed), mark it isDead. Also checks if +/// (since its spill instruction is removed), mark it isDead. Also checks if /// the def MI has other definition operands that are not dead. Returns it by /// reference. static bool InvalidateRegDef(MachineBasicBlock::iterator I, MachineInstr &NewDef, unsigned Reg, - bool &HasLiveDef) { + bool &HasLiveDef, + const TargetRegisterInfo *TRI) { // Due to remat, it's possible this reg isn't being reused. That is, // the def of this reg (by prev MI) is now dead. MachineInstr *DefMI = I; 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.isDef() || !MO.isKill() || MO.isUndef()) + continue; + if (MO.getReg() == Reg) + DefOp = &MO; + else if (!MO.isDead()) + HasLiveDef = true; } if (!DefOp) return false; @@ -429,7 +524,8 @@ static bool InvalidateRegDef(MachineBasicBlock::iterator I, MachineInstr *NMI = I; for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = NMI->getOperand(j); - if (!MO.isReg() || MO.getReg() != Reg) + if (!MO.isReg() || MO.getReg() == 0 || + (MO.getReg() != Reg && !TRI->isSubRegister(Reg, MO.getReg()))) continue; if (MO.isUse()) FoundUse = true; @@ -447,12 +543,12 @@ static bool InvalidateRegDef(MachineBasicBlock::iterator I, /// 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 &KillOps, - const TargetRegisterInfo* TRI) { +static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI, + BitVector &RegKills, + std::vector &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) @@ -462,29 +558,66 @@ static void UpdateKills(MachineInstr &MI, BitVector &RegKills, // 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); - if (!MI.isRegTiedToDefOperand(i)) - // Unless it's a two-address operand, this is the new kill. - MO.setIsKill(); + // 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); + } + } else { + // Check for subreg kills as well. + // d4 = + // store d4, fi#0 + // ... + // = s8 + // ... + // = d4 + for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) { + unsigned SReg = *SR; + if (RegKills[SReg] && KillOps[SReg]->getParent() != &MI) { + KillOps[SReg]->setIsKill(false); + unsigned KReg = KillOps[SReg]->getReg(); + KillOps[KReg] = NULL; + RegKills.reset(KReg); + + for (const unsigned *SSR = TRI->getSubRegisters(KReg); *SSR; ++SSR) { + KillOps[*SSR] = NULL; + RegKills.reset(*SSR); + } + } + } } + if (MO.isKill()) { RegKills.set(Reg); KillOps[Reg] = &MO; + for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) { + RegKills.set(*SR); + KillOps[*SR] = &MO; + } } } for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg() || !MO.isDef()) + if (!MO.isReg() || !MO.getReg() || !MO.isDef()) continue; unsigned Reg = MO.getReg(); 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; + } + for (const unsigned *SR = TRI->getSuperRegisters(Reg); *SR; ++SR) { + RegKills.reset(*SR); + KillOps[*SR] = NULL; } } } @@ -497,7 +630,14 @@ static void ReMaterialize(MachineBasicBlock &MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, VirtRegMap &VRM) { - TII->reMaterialize(MBB, MII, DestReg, VRM.getReMaterializedMI(Reg)); + MachineInstr *ReMatDefMI = VRM.getReMaterializedMI(Reg); +#ifndef NDEBUG + const TargetInstrDesc &TID = ReMatDefMI->getDesc(); + assert(TID.getNumDefs() == 1 && + "Don't know how to remat instructions that define > 1 values!"); +#endif + TII->reMaterialize(MBB, MII, DestReg, + ReMatDefMI->getOperand(0).getSubReg(), ReMatDefMI, TRI); MachineInstr *NewMI = prior(MII); for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { MachineOperand &MO = NewMI->getOperand(i); @@ -509,7 +649,7 @@ static void ReMaterialize(MachineBasicBlock &MBB, assert(MO.isUse()); unsigned SubIdx = MO.getSubReg(); unsigned Phys = VRM.getPhys(VirtReg); - assert(Phys); + assert(Phys && "Virtual register is not assigned a register?"); unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys; MO.setReg(RReg); MO.setSubReg(0); @@ -546,8 +686,8 @@ void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) { assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && "Bidirectional map mismatch!"); SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1; - DOUT << "PhysReg " << TRI->getName(PhysReg) - << " copied, it is available for use but can no longer be modified\n"; + DEBUG(errs() << "PhysReg " << TRI->getName(PhysReg) + << " copied, it is available for use but can no longer be modified\n"); } } @@ -571,12 +711,12 @@ void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && "Bidirectional map mismatch!"); SpillSlotsOrReMatsAvailable.erase(SlotOrReMat); - DOUT << "PhysReg " << TRI->getName(PhysReg) - << " clobbered, invalidating "; + DEBUG(errs() << "PhysReg " << TRI->getName(PhysReg) + << " clobbered, invalidating "); if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) - DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n"; + DEBUG(errs() << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 <<"\n"); else - DOUT << "SS#" << SlotOrReMat << "\n"; + DEBUG(errs() << "SS#" << SlotOrReMat << "\n"); } } @@ -610,11 +750,11 @@ void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, NotAvailable.insert(Reg); else { MBB.addLiveIn(Reg); - InvalidateKill(Reg, RegKills, KillOps); + InvalidateKill(Reg, TRI, RegKills, KillOps); } // Skip over the same register. - std::multimap::iterator NI = next(I); + std::multimap::iterator NI = llvm::next(I); while (NI != E && NI->first == Reg) { ++I; ++NI; @@ -658,15 +798,17 @@ void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) { /// GetRegForReload - We are about to emit a reload into PhysReg. If there /// is some other operand that is using the specified register, either pick /// a new register to use, or evict the previous reload and use this reg. -unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, - AvailableSpills &Spills, +unsigned ReuseInfo::GetRegForReload(const TargetRegisterClass *RC, + unsigned PhysReg, + MachineFunction &MF, + MachineInstr *MI, AvailableSpills &Spills, std::vector &MaybeDeadStores, SmallSet &Rejected, BitVector &RegKills, std::vector &KillOps, VirtRegMap &VRM) { - const TargetInstrInfo* TII = MI->getParent()->getParent()->getTarget() - .getInstrInfo(); + const TargetInstrInfo* TII = MF.getTarget().getInstrInfo(); + const TargetRegisterInfo *TRI = Spills.getRegInfo(); if (Reuses.empty()) return PhysReg; // This is most often empty. @@ -678,19 +820,19 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, // considered and subsequently rejected because it has also been reused // by another operand. if (Op.PhysRegReused == PhysReg && - Rejected.count(Op.AssignedPhysReg) == 0) { + Rejected.count(Op.AssignedPhysReg) == 0 && + RC->contains(Op.AssignedPhysReg)) { // Yup, use the reload register that we didn't use before. unsigned NewReg = Op.AssignedPhysReg; Rejected.insert(PhysReg); - return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected, + return GetRegForReload(RC, NewReg, MF, MI, Spills, MaybeDeadStores, Rejected, RegKills, KillOps, VRM); } else { // Otherwise, we might also have a problem if a previously reused - // value aliases the new register. If so, codegen the previous reload + // value aliases the new register. If so, codegen the previous reload // and use this one. unsigned PRRU = Op.PhysRegReused; - const TargetRegisterInfo *TRI = Spills.getRegInfo(); - if (TRI->areAliases(PRRU, PhysReg)) { + if (TRI->regsOverlap(PRRU, PhysReg)) { // Okay, we found out that an alias of a reused register // was used. This isn't good because it means we have // to undo a previous reuse. @@ -703,21 +845,42 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, ReusedOp NewOp = Op; Reuses.erase(Reuses.begin()+ro); + // MI may be using only a sub-register of PhysRegUsed. + unsigned RealPhysRegUsed = MI->getOperand(NewOp.Operand).getReg(); + unsigned SubIdx = 0; + assert(TargetRegisterInfo::isPhysicalRegister(RealPhysRegUsed) && + "A reuse cannot be a virtual register"); + if (PRRU != RealPhysRegUsed) { + // What was the sub-register index? + SubIdx = TRI->getSubRegIndex(PRRU, RealPhysRegUsed); + assert(SubIdx && + "Operand physreg is not a sub-register of PhysRegUsed"); + } + // Ok, we're going to try to reload the assigned physreg into the // slot that we were supposed to in the first place. However, that // register could hold a reuse. Check to see if it conflicts or // would prefer us to use a different register. - unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg, - MI, Spills, MaybeDeadStores, - Rejected, RegKills, KillOps, VRM); - - MachineBasicBlock::iterator MII = MI; - if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) { - ReMaterialize(*MBB, MII, NewPhysReg, NewOp.VirtReg, TII, TRI,VRM); - } else { - TII->loadRegFromStackSlot(*MBB, MII, NewPhysReg, + unsigned NewPhysReg = GetRegForReload(RC, NewOp.AssignedPhysReg, + MF, MI, Spills, MaybeDeadStores, + Rejected, RegKills, KillOps, VRM); + + bool DoReMat = NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT; + int SSorRMId = DoReMat + ? VRM.getReMatId(NewOp.VirtReg) : NewOp.StackSlotOrReMat; + + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(MI, MBB->begin(), PhysReg, TRI, + DoReMat, SSorRMId, TII, MF); + + if (DoReMat) { + ReMaterialize(*MBB, InsertLoc, NewPhysReg, NewOp.VirtReg, TII, + TRI, VRM); + } else { + TII->loadRegFromStackSlot(*MBB, InsertLoc, NewPhysReg, NewOp.StackSlotOrReMat, AliasRC); - MachineInstr *LoadMI = prior(MII); + MachineInstr *LoadMI = prior(InsertLoc); VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI); // Any stores to this stack slot are not dead anymore. MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL; @@ -726,17 +889,15 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, Spills.ClobberPhysReg(NewPhysReg); Spills.ClobberPhysReg(NewOp.PhysRegReused); - unsigned SubIdx = MI->getOperand(NewOp.Operand).getSubReg(); - unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) : NewPhysReg; + unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) :NewPhysReg; MI->getOperand(NewOp.Operand).setReg(RReg); MI->getOperand(NewOp.Operand).setSubReg(0); Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg); - --MII; - UpdateKills(*MII, RegKills, KillOps, TRI); - DOUT << '\t' << *MII; + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); + DEBUG(errs() << '\t' << *prior(InsertLoc)); - DOUT << "Reuse undone!\n"; + DEBUG(errs() << "Reuse undone!\n"); --NumReused; // Finally, PhysReg is now available, go ahead and use it. @@ -851,12 +1012,22 @@ void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg) { } } +namespace { + struct RefSorter { + bool operator()(const std::pair &A, + const std::pair &B) { + return A.second < B.second; + } + }; +} // ***************************** // // Local Spiller Implementation // // ***************************** // -class VISIBILITY_HIDDEN LocalRewriter : public VirtRegRewriter { +namespace { + +class LocalRewriter : public VirtRegRewriter { MachineRegisterInfo *RegInfo; const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; @@ -870,10 +1041,10 @@ public: TRI = MF.getTarget().getRegisterInfo(); TII = MF.getTarget().getInstrInfo(); AllocatableRegs = TRI->getAllocatableSet(MF); - DOUT << "\n**** Local spiller rewriting function '" - << MF.getFunction()->getName() << "':\n"; - DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)" - " ****\n"; + DEBUG(errs() << "\n**** Local spiller rewriting function '" + << MF.getFunction()->getName() << "':\n"); + DEBUG(errs() << "**** Machine Instrs (NOTE! Does not include spills and" + " reloads!) ****\n"); DEBUG(MF.dump()); // Spills - Keep track of which spilled values are available in physregs @@ -924,7 +1095,7 @@ public: Spills.clear(); } - DOUT << "**** Post Machine Instrs ****\n"; + DEBUG(errs() << "**** Post Machine Instrs ****\n"); DEBUG(MF.dump()); // Mark unused spill slots. @@ -962,7 +1133,7 @@ private: std::vector &KillOps, VirtRegMap &VRM) { - MachineBasicBlock::iterator NextMII = next(MII); + MachineBasicBlock::iterator NextMII = llvm::next(MII); if (NextMII == MBB.end()) return false; @@ -988,6 +1159,9 @@ private: if (!FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM)) return false; + // Back-schedule reloads and remats. + ComputeReloadLoc(MII, MBB.begin(), PhysReg, TRI, false, SS, TII, MF); + // Load from SS to the spare physical register. TII->loadRegFromStackSlot(MBB, MII, PhysReg, SS, RC); // This invalidates Phys. @@ -999,12 +1173,12 @@ private: // Unfold current MI. SmallVector 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]); MII = MBB.insert(MII, NewMIs[0]); - InvalidateKills(MI, RegKills, KillOps); + InvalidateKills(MI, TRI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); ++NumModRefUnfold; @@ -1012,18 +1186,20 @@ private: // Unfold next instructions that fold the same SS. do { MachineInstr &NextMI = *NextMII; - NextMII = next(NextMII); + NextMII = llvm::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]); 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. @@ -1142,7 +1318,7 @@ private: 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); @@ -1155,6 +1331,32 @@ private: 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 @@ -1183,7 +1385,7 @@ private: 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)) @@ -1226,13 +1428,13 @@ private: 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); @@ -1261,17 +1463,18 @@ private: std::vector &KillOps, VirtRegMap &VRM) { - TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC); - MachineInstr *StoreMI = next(MII); + MachineBasicBlock::iterator oldNextMII = llvm::next(MII); + TII->storeRegToStackSlot(MBB, llvm::next(MII), PhysReg, true, StackSlot, RC); + MachineInstr *StoreMI = prior(oldNextMII); VRM.addSpillSlotUse(StackSlot, StoreMI); - DOUT << "Store:\t" << *StoreMI; + DEBUG(errs() << "Store:\t" << *StoreMI); // If there is a dead store to this stack slot, nuke it now. if (LastStore) { - DOUT << "Removed dead store:\t" << *LastStore; + DEBUG(errs() << "Removed dead store:\t" << *LastStore); ++NumDSE; SmallVector KillRegs; - InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs); + InvalidateKills(*LastStore, TRI, RegKills, KillOps, &KillRegs); MachineBasicBlock::iterator PrevMII = LastStore; bool CheckDef = PrevMII != MBB.begin(); if (CheckDef) @@ -1284,11 +1487,10 @@ private: // being reused. for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) { bool HasOtherDef = false; - if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) { + if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef, TRI)) { 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; @@ -1298,7 +1500,9 @@ private: } } - LastStore = next(MII); + // Allow for multi-instruction spill sequences, as on PPC Altivec. Presume + // the last of multiple instructions is the actual store. + LastStore = prior(oldNextMII); // If the stack slot value was previously available in some other // register, change it now. Otherwise, make the register available, @@ -1309,13 +1513,37 @@ private: ++NumStores; } + /// isSafeToDelete - Return true if this instruction doesn't produce any side + /// effect and all of its defs are dead. + static bool isSafeToDelete(MachineInstr &MI) { + const TargetInstrDesc &TID = MI.getDesc(); + if (TID.mayLoad() || TID.mayStore() || TID.isCall() || TID.isTerminator() || + TID.isCall() || TID.isBarrier() || TID.isReturn() || + TID.hasUnmodeledSideEffects()) + return false; + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (!MO.isReg() || !MO.getReg()) + continue; + if (MO.isDef() && !MO.isDead()) + return false; + if (MO.isUse() && MO.isKill()) + // FIXME: We can't remove kill markers or else the scavenger will assert. + // An alternative is to add a ADD pseudo instruction to replace kill + // markers. + return false; + } + return true; + } + /// TransferDeadness - A identity copy definition is dead and it's being /// 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 &KillOps) { - int LastUDDist = -1; - MachineInstr *LastUDMI = NULL; + std::vector &KillOps, + VirtRegMap &VRM) { + SmallPtrSet Seens; + SmallVector,8> Refs; for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg), RE = RegInfo->reg_end(); RI != RE; ++RI) { MachineInstr *UDMI = &*RI; @@ -1324,13 +1552,18 @@ private: DenseMap::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); @@ -1339,14 +1572,22 @@ private: 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. + if (!isSafeToDelete(*LastUDMI)) { + LastUD->setIsDead(); + break; + } + VRM.RemoveMachineInstrFromMaps(LastUDMI); + MBB->erase(LastUDMI); + } else { LastUD->setIsKill(); RegKills.set(Reg); KillOps[Reg] = LastUD; + break; } } } @@ -1358,8 +1599,8 @@ private: AvailableSpills &Spills, BitVector &RegKills, std::vector &KillOps) { - DOUT << "\n**** Local spiller rewriting MBB '" - << MBB.getBasicBlock()->getName() << "':\n"; + DEBUG(errs() << "\n**** Local spiller rewriting MBB '" + << MBB.getName() << "':\n"); MachineFunction &MF = *MBB.getParent(); @@ -1385,14 +1626,14 @@ private: DistanceMap.clear(); for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); MII != E; ) { - MachineBasicBlock::iterator NextMII = next(MII); + MachineBasicBlock::iterator NextMII = llvm::next(MII); VirtRegMap::MI2VirtMapTy::const_iterator I, End; bool Erased = false; bool BackTracked = false; if (OptimizeByUnfold(MBB, MII, MaybeDeadStores, Spills, RegKills, KillOps, VRM)) - NextMII = next(MII); + NextMII = llvm::next(MII); MachineInstr &MI = *MII; @@ -1408,17 +1649,25 @@ private: 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); VRM.addSpillSlotUse(SS, StoreMI); - TII->loadRegFromStackSlot(MBB, next(MII), PhysReg, SS, RC); - MachineInstr *LoadMI = next(MII); + + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(llvm::next(MII), MBB.begin(), PhysReg, TRI, false, + SS, TII, MF); + + TII->loadRegFromStackSlot(MBB, InsertLoc, PhysReg, SS, RC); + + MachineInstr *LoadMI = prior(InsertLoc); VRM.addSpillSlotUse(SS, LoadMI); ++NumPSpills; + DistanceMap.insert(std::make_pair(LoadMI, Dist++)); } - NextMII = next(MII); + NextMII = llvm::next(MII); } // Insert restores here if asked to. @@ -1450,28 +1699,36 @@ private: // If the value is already available in the expected register, save // a reload / remat. if (SSorRMId) - DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1; + DEBUG(errs() << "Reusing RM#" + << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1); else - DOUT << "Reusing SS#" << SSorRMId; - DOUT << " from physreg " - << TRI->getName(InReg) << " for vreg" - << VirtReg <<" instead of reloading into physreg " - << TRI->getName(Phys) << "\n"; + DEBUG(errs() << "Reusing SS#" << SSorRMId); + DEBUG(errs() << " from physreg " + << TRI->getName(InReg) << " for vreg" + << VirtReg <<" instead of reloading into physreg " + << TRI->getName(Phys) << '\n'); ++NumOmitted; continue; } else if (InReg && InReg != Phys) { if (SSorRMId) - DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1; + DEBUG(errs() << "Reusing RM#" + << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1); else - DOUT << "Reusing SS#" << SSorRMId; - DOUT << " from physreg " - << TRI->getName(InReg) << " for vreg" - << VirtReg <<" by copying it into physreg " - << TRI->getName(Phys) << "\n"; + DEBUG(errs() << "Reusing SS#" << SSorRMId); + DEBUG(errs() << " from physreg " + << TRI->getName(InReg) << " for vreg" + << VirtReg <<" by copying it into physreg " + << TRI->getName(Phys) << '\n'); // If the reloaded / remat value is available in another register, // copy it to the desired register. - TII->copyRegToReg(MBB, &MI, Phys, InReg, RC, RC); + + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(MII, MBB.begin(), Phys, TRI, DoReMat, + SSorRMId, TII, MF); + + TII->copyRegToReg(MBB, InsertLoc, Phys, InReg, RC, RC); // This invalidates Phys. Spills.ClobberPhysReg(Phys); @@ -1479,24 +1736,31 @@ private: Spills.addAvailable(SSorRMId, Phys); // Mark is killed. - MachineInstr *CopyMI = prior(MII); + MachineInstr *CopyMI = prior(InsertLoc); + CopyMI->setAsmPrinterFlag(AsmPrinter::ReloadReuse); MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg); KillOpnd->setIsKill(); - UpdateKills(*CopyMI, RegKills, KillOps, TRI); + UpdateKills(*CopyMI, TRI, RegKills, KillOps); - DOUT << '\t' << *CopyMI; + DEBUG(errs() << '\t' << *CopyMI); ++NumCopified; continue; } + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(MII, MBB.begin(), Phys, TRI, DoReMat, + SSorRMId, TII, MF); + if (VRM.isReMaterialized(VirtReg)) { - ReMaterialize(MBB, MII, Phys, VirtReg, TII, TRI, VRM); + ReMaterialize(MBB, InsertLoc, Phys, VirtReg, TII, TRI, VRM); } else { const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); - TII->loadRegFromStackSlot(MBB, &MI, Phys, SSorRMId, RC); - MachineInstr *LoadMI = prior(MII); + TII->loadRegFromStackSlot(MBB, InsertLoc, Phys, SSorRMId, RC); + MachineInstr *LoadMI = prior(InsertLoc); VRM.addSpillSlotUse(SSorRMId, LoadMI); ++NumLoads; + DistanceMap.insert(std::make_pair(LoadMI, Dist++)); } // This invalidates Phys. @@ -1504,8 +1768,8 @@ private: // Remember it's available. Spills.addAvailable(SSorRMId, Phys); - UpdateKills(*prior(MII), RegKills, KillOps, TRI); - DOUT << '\t' << *prior(MII); + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); + DEBUG(errs() << '\t' << *prior(MII)); } } @@ -1521,13 +1785,14 @@ private: const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg); unsigned Phys = VRM.getPhys(VirtReg); int StackSlot = VRM.getStackSlot(VirtReg); - TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC); - MachineInstr *StoreMI = next(MII); + MachineBasicBlock::iterator oldNextMII = llvm::next(MII); + TII->storeRegToStackSlot(MBB, llvm::next(MII), Phys, isKill, StackSlot, RC); + MachineInstr *StoreMI = prior(oldNextMII); VRM.addSpillSlotUse(StackSlot, StoreMI); - DOUT << "Store:\t" << *StoreMI; + DEBUG(errs() << "Store:\t" << *StoreMI); VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod); } - NextMII = next(MII); + NextMII = llvm::next(MII); } /// ReusedOperands - Keep track of operand reuse in case we need to undo @@ -1551,6 +1816,8 @@ private: 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); @@ -1577,6 +1844,7 @@ private: 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; @@ -1586,22 +1854,16 @@ private: 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 = IMPLICIT_DEF - // 12 %reg1024 = INSERT_SUBREG %reg1024, %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 = IMPLICIT_DEF + // 12 %reg1024 = INSERT_SUBREG %reg1024, %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); @@ -1646,13 +1908,14 @@ private: if (CanReuse) { // If this stack slot value is already available, reuse it! if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) - DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; + DEBUG(errs() << "Reusing RM#" + << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1); else - DOUT << "Reusing SS#" << ReuseSlot; - DOUT << " from physreg " - << TRI->getName(PhysReg) << " for vreg" - << VirtReg <<" instead of reloading into physreg " - << TRI->getName(VRM.getPhys(VirtReg)) << "\n"; + DEBUG(errs() << "Reusing SS#" << ReuseSlot); + DEBUG(errs() << " from physreg " + << TRI->getName(PhysReg) << " for vreg" + << VirtReg <<" instead of reloading into physreg " + << TRI->getName(VRM.getPhys(VirtReg)) << '\n'); unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg; MI.getOperand(i).setReg(RReg); MI.getOperand(i).setSubReg(0); @@ -1719,20 +1982,22 @@ private: // available. If this occurs, use the register indicated by the // reuser. if (ReusedOperands.hasReuses()) - DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI, - Spills, MaybeDeadStores, RegKills, KillOps, VRM); + DesignatedReg = ReusedOperands.GetRegForReload(VirtReg, + DesignatedReg, &MI, + Spills, MaybeDeadStores, RegKills, KillOps, VRM); // If the mapped designated register is actually the physreg we have // incoming, we don't need to inserted a dead copy. if (DesignatedReg == PhysReg) { // If this stack slot value is already available, reuse it! if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) - DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; + DEBUG(errs() << "Reusing RM#" + << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1); else - DOUT << "Reusing SS#" << ReuseSlot; - DOUT << " from physreg " << TRI->getName(PhysReg) - << " for vreg" << VirtReg - << " instead of reloading into same physreg.\n"; + DEBUG(errs() << "Reusing SS#" << ReuseSlot); + DEBUG(errs() << " from physreg " << TRI->getName(PhysReg) + << " for vreg" << VirtReg + << " instead of reloading into same physreg.\n"); unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg; MI.getOperand(i).setReg(RReg); MI.getOperand(i).setSubReg(0); @@ -1744,10 +2009,17 @@ private: const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); RegInfo->setPhysRegUsed(DesignatedReg); ReusedOperands.markClobbered(DesignatedReg); - TII->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC); - MachineInstr *CopyMI = prior(MII); - UpdateKills(*CopyMI, RegKills, KillOps, TRI); + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(&MI, MBB.begin(), PhysReg, TRI, DoReMat, + SSorRMId, TII, MF); + + TII->copyRegToReg(MBB, InsertLoc, DesignatedReg, PhysReg, RC, RC); + + MachineInstr *CopyMI = prior(InsertLoc); + CopyMI->setAsmPrinterFlag(AsmPrinter::ReloadReuse); + UpdateKills(*CopyMI, TRI, RegKills, KillOps); // This invalidates DesignatedReg. Spills.ClobberPhysReg(DesignatedReg); @@ -1757,7 +2029,7 @@ private: SubIdx ? TRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg; MI.getOperand(i).setReg(RReg); MI.getOperand(i).setSubReg(0); - DOUT << '\t' << *prior(MII); + DEBUG(errs() << '\t' << *prior(MII)); ++NumReused; continue; } // if (PhysReg) @@ -1771,22 +2043,28 @@ private: // available. If this occurs, use the register indicated by the // reuser. if (ReusedOperands.hasReuses()) - PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, - Spills, MaybeDeadStores, RegKills, KillOps, VRM); + PhysReg = ReusedOperands.GetRegForReload(VirtReg, PhysReg, &MI, + Spills, MaybeDeadStores, RegKills, KillOps, VRM); RegInfo->setPhysRegUsed(PhysReg); ReusedOperands.markClobbered(PhysReg); if (AvoidReload) ++NumAvoided; else { + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + ComputeReloadLoc(MII, MBB.begin(), PhysReg, TRI, DoReMat, + SSorRMId, TII, MF); + if (DoReMat) { - ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM); + ReMaterialize(MBB, InsertLoc, PhysReg, VirtReg, TII, TRI, VRM); } else { const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); - TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC); - MachineInstr *LoadMI = prior(MII); + TII->loadRegFromStackSlot(MBB, InsertLoc, PhysReg, SSorRMId, RC); + MachineInstr *LoadMI = prior(InsertLoc); VRM.addSpillSlotUse(SSorRMId, LoadMI); ++NumLoads; + DistanceMap.insert(std::make_pair(LoadMI, Dist++)); } // This invalidates PhysReg. Spills.ClobberPhysReg(PhysReg); @@ -1803,8 +2081,8 @@ private: KilledMIRegs.insert(VirtReg); } - UpdateKills(*prior(MII), RegKills, KillOps, TRI); - DOUT << '\t' << *prior(MII); + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); + DEBUG(errs() << '\t' << *prior(InsertLoc)); } unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg; MI.getOperand(i).setReg(RReg); @@ -1818,8 +2096,8 @@ private: int PDSSlot = PotentialDeadStoreSlots[j]; MachineInstr* DeadStore = MaybeDeadStores[PDSSlot]; if (DeadStore) { - DOUT << "Removed dead store:\t" << *DeadStore; - InvalidateKills(*DeadStore, RegKills, KillOps); + DEBUG(errs() << "Removed dead store:\t" << *DeadStore); + InvalidateKills(*DeadStore, TRI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(DeadStore); MBB.erase(DeadStore); MaybeDeadStores[PDSSlot] = NULL; @@ -1828,7 +2106,7 @@ private: } - DOUT << '\t' << MI; + DEBUG(errs() << '\t' << MI); // If we have folded references to memory operands, make sure we clear all @@ -1838,7 +2116,7 @@ private: for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) { unsigned VirtReg = I->second.first; VirtRegMap::ModRef MR = I->second.second; - DOUT << "Folded vreg: " << VirtReg << " MR: " << MR; + DEBUG(errs() << "Folded vreg: " << VirtReg << " MR: " << MR); // MI2VirtMap be can updated which invalidate the iterator. // Increment the iterator first. @@ -1847,7 +2125,7 @@ private: if (SS == VirtRegMap::NO_STACK_SLOT) continue; FoldedSS.insert(SS); - DOUT << " - StackSlot: " << SS << "\n"; + DEBUG(errs() << " - StackSlot: " << SS << "\n"); // If this folded instruction is just a use, check to see if it's a // straight load from the virt reg slot. @@ -1858,7 +2136,7 @@ private: // If this spill slot is available, turn it into a copy (or nothing) // instead of leaving it as a load! if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) { - DOUT << "Promoted Load To Copy: " << MI; + DEBUG(errs() << "Promoted Load To Copy: " << MI); if (DestReg != InReg) { const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg); TII->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC); @@ -1869,6 +2147,7 @@ private: // virtual or needing to clobber any values if it's physical). NextMII = &MI; --NextMII; // backtrack to the copy. + NextMII->setAsmPrinterFlag(AsmPrinter::ReloadReuse); // Propagate the sub-register index over. if (SubIdx) { DefMO = NextMII->findRegisterDefOperand(DestReg); @@ -1881,13 +2160,13 @@ private: BackTracked = true; } else { - DOUT << "Removing now-noop copy: " << MI; + DEBUG(errs() << "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; @@ -1899,7 +2178,7 @@ private: 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; @@ -1936,7 +2215,7 @@ private: 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; @@ -1951,8 +2230,8 @@ private: 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); + DEBUG(errs() << "Removed dead store:\t" << *DeadStore); + InvalidateKills(*DeadStore, TRI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(DeadStore); MBB.erase(DeadStore); if (!NewStore) @@ -1986,7 +2265,7 @@ private: if (CommuteToFoldReload(MBB, MII, VirtReg, SrcReg, StackSlot, Spills, RegKills, KillOps, TRI, VRM)) { - NextMII = next(MII); + NextMII = llvm::next(MII); BackTracked = true; goto ProcessNextInst; } @@ -2015,19 +2294,23 @@ private: 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; + DEBUG(errs() << "Removing now-noop copy: " << MI); SmallVector 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); @@ -2035,7 +2318,7 @@ private: 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); @@ -2082,8 +2365,8 @@ private: if (ReusedOperands.isClobbered(PhysReg)) { // Another def has taken the assigned physreg. It must have been a // use&def which got it due to reuse. Undo the reuse! - PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, - Spills, MaybeDeadStores, RegKills, KillOps, VRM); + PhysReg = ReusedOperands.GetRegForReload(VirtReg, PhysReg, &MI, + Spills, MaybeDeadStores, RegKills, KillOps, VRM); } } @@ -2098,7 +2381,7 @@ private: MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true, LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM); - NextMII = next(MII); + NextMII = llvm::next(MII); // Check to see if this is a noop copy. If so, eliminate the // instruction before considering the dest reg to be changed. @@ -2106,22 +2389,30 @@ private: unsigned Src, Dst, SrcSR, DstSR; if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) { ++NumDCE; - DOUT << "Removing now-noop copy: " << MI; - InvalidateKills(MI, RegKills, KillOps); + DEBUG(errs() << "Removing now-noop copy: " << MI); + 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; } } } } ProcessNextInst: - DistanceMap.insert(std::make_pair(&MI, Dist++)); + // Delete dead instructions without side effects. + if (!Erased && !BackTracked && isSafeToDelete(MI)) { + InvalidateKills(MI, TRI, RegKills, KillOps); + VRM.RemoveMachineInstrFromMaps(&MI); + MBB.erase(&MI); + Erased = true; + } + if (!Erased) + 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; } @@ -2130,12 +2421,14 @@ private: }; +} + 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(); } }