X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegRewriter.cpp;h=460b508a804b64c28eb1a551ee83b8030a994eca;hb=ad88bc4076d088baad8a5ee9561e46ac08a1c88a;hp=36d169754949216a813ee3b904f455d4551bb2df;hpb=427a6b666bce6069b0578ce75b63d80dc684b09d;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegRewriter.cpp b/lib/CodeGen/VirtRegRewriter.cpp index 36d16975494..460b508a804 100644 --- a/lib/CodeGen/VirtRegRewriter.cpp +++ b/lib/CodeGen/VirtRegRewriter.cpp @@ -10,6 +10,9 @@ #define DEBUG_TYPE "virtregrewriter" #include "VirtRegRewriter.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetLowering.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" @@ -33,99 +36,71 @@ 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)); +cl::opt +ScheduleSpills("schedule-spills", + cl::desc("Schedule spill code"), + cl::init(false)); + 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 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() << "********** Function: " + << MF.getFunction()->getName() << '\n'); + DOUT << "**** 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(); - DOUT << '\t' << MI; - LoadedRegs.clear(); + bool changed = false; + + 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; + + + DOUT << "**** Post Machine Instrs ****\n"; + DEBUG(MF.dump()); + + return changed; } }; - + // ************************************************************************ // /// AvailableSpills - As the local rewriter is scanning and rewriting an MBB @@ -252,6 +227,76 @@ public: // ************************************************************************ // +// 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; +} + // 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. @@ -317,7 +362,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,15 +382,17 @@ 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); } }; @@ -374,9 +422,11 @@ static void InvalidateKill(unsigned Reg, std::vector &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; @@ -395,7 +445,7 @@ static void InvalidateKills(MachineInstr &MI, 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)) @@ -429,12 +479,12 @@ static bool InvalidateRegDef(MachineBasicBlock::iterator 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.isUse() || !MO.isKill() || MO.isUndef()) + continue; + if (MO.getReg() == Reg) + DefOp = &MO; + else if (!MO.isDead()) + HasLiveDef = true; } if (!DefOp) return false; @@ -469,7 +519,7 @@ static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI, 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) @@ -479,8 +529,18 @@ static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI, // 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(); @@ -518,7 +578,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); MachineInstr *NewMI = prior(MII); for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { MachineOperand &MO = NewMI->getOperand(i); @@ -679,15 +746,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. @@ -699,18 +768,18 @@ 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)) { // Okay, we found out that an alias of a reused register // was used. This isn't good because it means we have @@ -728,17 +797,26 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, // 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; @@ -753,9 +831,8 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, MI->getOperand(NewOp.Operand).setSubReg(0); Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg); - --MII; - UpdateKills(*MII, TRI, RegKills, KillOps); - DOUT << '\t' << *MII; + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); + DOUT << '\t' << *prior(InsertLoc); DOUT << "Reuse undone!\n"; --NumReused; @@ -899,8 +976,8 @@ public: TRI = MF.getTarget().getRegisterInfo(); TII = MF.getTarget().getInstrInfo(); AllocatableRegs = TRI->getAllocatableSet(MF); - DOUT << "\n**** Local spiller rewriting function '" - << MF.getFunction()->getName() << "':\n"; + DEBUG(errs() << "\n**** Local spiller rewriting function '" + << MF.getFunction()->getName() << "':\n"); DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)" " ****\n"; DEBUG(MF.dump()); @@ -1017,6 +1094,10 @@ private: if (!FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM)) return false; + // Back-schedule reloads and remats. + MachineBasicBlock::iterator InsertLoc = + 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. @@ -1028,7 +1109,7 @@ 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]); @@ -1044,7 +1125,7 @@ private: 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]); @@ -1053,6 +1134,8 @@ private: 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. @@ -1184,6 +1267,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 @@ -1212,7 +1321,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)) @@ -1316,8 +1425,7 @@ private: 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; @@ -1379,9 +1487,7 @@ private: 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()) { + if (!TII->isDeadInstruction(LastUDMI)) { LastUD->setIsDead(); break; } @@ -1403,8 +1509,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.getBasicBlock()->getName() << "':\n"); MachineFunction &MF = *MBB.getParent(); @@ -1453,13 +1559,20 @@ 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(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; } @@ -1516,7 +1629,13 @@ private: // 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); @@ -1524,7 +1643,7 @@ private: Spills.addAvailable(SSorRMId, Phys); // Mark is killed. - MachineInstr *CopyMI = prior(MII); + MachineInstr *CopyMI = prior(InsertLoc); MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg); KillOpnd->setIsKill(); UpdateKills(*CopyMI, TRI, RegKills, KillOps); @@ -1534,12 +1653,17 @@ private: 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; } @@ -1549,7 +1673,7 @@ private: // Remember it's available. Spills.addAvailable(SSorRMId, Phys); - UpdateKills(*prior(MII), TRI, RegKills, KillOps); + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); DOUT << '\t' << *prior(MII); } } @@ -1596,6 +1720,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); @@ -1622,6 +1748,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; @@ -1631,22 +1758,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); @@ -1764,8 +1885,9 @@ 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. @@ -1789,9 +1911,15 @@ 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); + // 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); UpdateKills(*CopyMI, TRI, RegKills, KillOps); // This invalidates DesignatedReg. @@ -1816,20 +1944,25 @@ 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; } @@ -1848,8 +1981,8 @@ private: KilledMIRegs.insert(VirtReg); } - UpdateKills(*prior(MII), TRI, RegKills, KillOps); - DOUT << '\t' << *prior(MII); + UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps); + DOUT << '\t' << *prior(InsertLoc); } unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg; MI.getOperand(i).setReg(RReg); @@ -2060,8 +2193,12 @@ 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; SmallVector KillRegs; @@ -2080,7 +2217,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); @@ -2127,8 +2264,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); } } @@ -2163,7 +2300,15 @@ private: } } ProcessNextInst: - DistanceMap.insert(std::make_pair(&MI, Dist++)); + // Delete dead instructions without side effects. + if (!Erased && !BackTracked && TII->isDeadInstruction(&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, TRI, RegKills, KillOps); @@ -2177,10 +2322,10 @@ 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(); } }