X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.cpp;h=ceb4acee69827290867ebd27c675ba935505834f;hb=de4e942faa12a52242915e3334c25f19687f36e2;hp=a79585609a8d73b26de13e339a580515358d1f96;hpb=ba59a1e453e110f7b84233f07613f9c5d9a39b87;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index a79585609a8..ceb4acee698 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -27,19 +27,21 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Compiler.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallSet.h" #include using namespace llvm; -namespace { - static Statistic<> NumSpills("spiller", "Number of register spills"); - static Statistic<> NumStores("spiller", "Number of stores added"); - static Statistic<> NumLoads ("spiller", "Number of loads added"); - static Statistic<> NumReused("spiller", "Number of values reused"); - static Statistic<> NumDSE ("spiller", "Number of dead stores elided"); - static Statistic<> NumDCE ("spiller", "Number of copies elided"); +STATISTIC(NumSpills, "Number of register spills"); +STATISTIC(NumStores, "Number of stores added"); +STATISTIC(NumLoads , "Number of loads added"); +STATISTIC(NumReused, "Number of values reused"); +STATISTIC(NumDSE , "Number of dead stores elided"); +STATISTIC(NumDCE , "Number of copies elided"); +namespace { enum SpillerName { simple, local }; static cl::opt @@ -97,7 +99,9 @@ void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, } ModRef MRInfo; - if (TII.getOperandConstraint(OldMI->getOpcode(), OpNo, TOI::TIED_TO)) { + const TargetInstrDescriptor *TID = OldMI->getInstrDescriptor(); + if (TID->getOperandConstraint(OpNo, TOI::TIED_TO) != -1 || + TID->findTiedToSrcOperand(OpNo) != -1) { // Folded a two-address operand. MRInfo = isModRef; } else if (OldMI->getOperand(OpNo).isDef()) { @@ -111,11 +115,6 @@ void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, } void VirtRegMap::print(std::ostream &OS) const { - llvm_ostream LOS(OS); - print(LOS); -} - -void VirtRegMap::print(llvm_ostream &OS) const { const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo(); OS << "********** REGISTER MAP **********\n"; @@ -134,8 +133,7 @@ void VirtRegMap::print(llvm_ostream &OS) const { } void VirtRegMap::dump() const { - llvm_ostream OS = DOUT; - print(OS); + print(DOUT); } @@ -236,12 +234,6 @@ namespace { } private: void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); - void ClobberPhysReg(unsigned PR, std::map &SpillSlots, - std::multimap &PhysRegs); - void ClobberPhysRegOnly(unsigned PR, std::map &SpillSlots, - std::multimap &PhysRegs); - void ModifyStackSlot(int Slot, std::map &SpillSlots, - std::multimap &PhysRegs); }; } @@ -262,54 +254,87 @@ class VISIBILITY_HIDDEN AvailableSpills { // SpillSlotsAvailable - This map keeps track of all of the spilled virtual // register values that are still available, due to being loaded or stored to, - // but not invalidated yet. - std::map SpillSlotsAvailable; + // but not invalidated yet. It also tracks the instruction that last defined + // or used the register. + typedef std::pair SSInfo; + std::map SpillSlotsAvailable; // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating // which stack slot values are currently held by a physreg. This is used to // invalidate entries in SpillSlotsAvailable when a physreg is modified. std::multimap PhysRegsAvailable; + void disallowClobberPhysRegOnly(unsigned PhysReg); + void ClobberPhysRegOnly(unsigned PhysReg); public: AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii) : MRI(mri), TII(tii) { } + const MRegisterInfo *getRegInfo() const { return MRI; } + /// getSpillSlotPhysReg - If the specified stack slot is available in a - /// physical register, return that PhysReg, otherwise return 0. - unsigned getSpillSlotPhysReg(int Slot) const { - std::map::const_iterator I = SpillSlotsAvailable.find(Slot); - if (I != SpillSlotsAvailable.end()) - return I->second >> 1; // Remove the CanClobber bit. + /// physical register, return that PhysReg, otherwise return 0. It also + /// returns by reference the instruction that either defines or last uses + /// the register. + unsigned getSpillSlotPhysReg(int Slot, MachineInstr *&SSMI) const { + std::map::const_iterator I = SpillSlotsAvailable.find(Slot); + if (I != SpillSlotsAvailable.end()) { + SSMI = I->second.second; + return I->second.first >> 1; // Remove the CanClobber bit. + } return 0; } - - const MRegisterInfo *getRegInfo() const { return MRI; } + /// UpdateLastUses - Update the last use information of all stack slots whose + /// values are available in the specific register. + void UpdateLastUse(unsigned PhysReg, MachineInstr *Use) { + std::multimap::iterator I = + PhysRegsAvailable.lower_bound(PhysReg); + while (I != PhysRegsAvailable.end() && I->first == PhysReg) { + int Slot = I->second; + I++; + + std::map::iterator II = SpillSlotsAvailable.find(Slot); + assert(II != SpillSlotsAvailable.end() && "Slot not available!"); + unsigned Val = II->second.first; + assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!"); + SpillSlotsAvailable.erase(Slot); + SpillSlotsAvailable[Slot] = std::make_pair(Val, Use); + } + } + /// addAvailable - Mark that the specified stack slot is available in the /// specified physreg. If CanClobber is true, the physreg can be modified at /// any time without changing the semantics of the program. - void addAvailable(int Slot, unsigned Reg, bool CanClobber = true) { + void addAvailable(int Slot, MachineInstr *MI, unsigned Reg, + bool CanClobber = true) { // If this stack slot is thought to be available in some other physreg, // remove its record. ModifyStackSlot(Slot); PhysRegsAvailable.insert(std::make_pair(Reg, Slot)); - SpillSlotsAvailable[Slot] = (Reg << 1) | (unsigned)CanClobber; + SpillSlotsAvailable[Slot] = + std::make_pair((Reg << 1) | (unsigned)CanClobber, MI); DOUT << "Remembering SS#" << Slot << " in physreg " << MRI->getName(Reg) << "\n"; } - + /// canClobberPhysReg - Return true if the spiller is allowed to change the /// value of the specified stackslot register if it desires. The specified /// stack slot must be available in a physreg for this query to make sense. bool canClobberPhysReg(int Slot) const { assert(SpillSlotsAvailable.count(Slot) && "Slot not available!"); - return SpillSlotsAvailable.find(Slot)->second & 1; + return SpillSlotsAvailable.find(Slot)->second.first & 1; } + /// disallowClobberPhysReg - Unset the CanClobber bit of the specified + /// stackslot register. The register is still available but is no longer + /// allowed to be modifed. + void disallowClobberPhysReg(unsigned PhysReg); + /// ClobberPhysReg - This is called when the specified physreg changes /// value. We use this to invalidate any info about stuff we thing lives in /// it and any of its aliases. @@ -322,6 +347,32 @@ public: }; } +/// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified +/// stackslot register. The register is still available but is no longer +/// allowed to be modifed. +void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) { + std::multimap::iterator I = + PhysRegsAvailable.lower_bound(PhysReg); + while (I != PhysRegsAvailable.end() && I->first == PhysReg) { + int Slot = I->second; + I++; + assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg && + "Bidirectional map mismatch!"); + SpillSlotsAvailable[Slot].first &= ~1; + DOUT << "PhysReg " << MRI->getName(PhysReg) + << " copied, it is available for use but can no longer be modified\n"; + } +} + +/// disallowClobberPhysReg - Unset the CanClobber bit of the specified +/// stackslot register and its aliases. The register and its aliases may +/// still available but is no longer allowed to be modifed. +void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) { + for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) + disallowClobberPhysRegOnly(*AS); + disallowClobberPhysRegOnly(PhysReg); +} + /// ClobberPhysRegOnly - This is called when the specified physreg changes /// value. We use this to invalidate any info about stuff we thing lives in it. void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { @@ -330,7 +381,7 @@ void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { while (I != PhysRegsAvailable.end() && I->first == PhysReg) { int Slot = I->second; PhysRegsAvailable.erase(I++); - assert((SpillSlotsAvailable[Slot] >> 1) == PhysReg && + assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg && "Bidirectional map mismatch!"); SpillSlotsAvailable.erase(Slot); DOUT << "PhysReg " << MRI->getName(PhysReg) @@ -351,9 +402,9 @@ void AvailableSpills::ClobberPhysReg(unsigned PhysReg) { /// changes. This removes information about which register the previous value /// for this slot lives in (as the previous value is dead now). void AvailableSpills::ModifyStackSlot(int Slot) { - std::map::iterator It = SpillSlotsAvailable.find(Slot); + std::map::iterator It = SpillSlotsAvailable.find(Slot); if (It == SpillSlotsAvailable.end()) return; - unsigned Reg = It->second >> 1; + unsigned Reg = It->second.first >> 1; SpillSlotsAvailable.erase(It); // This register may hold the value of multiple stack slots, only remove this @@ -399,14 +450,10 @@ namespace { class VISIBILITY_HIDDEN ReuseInfo { MachineInstr &MI; std::vector Reuses; - bool *PhysRegsClobbered; + BitVector PhysRegsClobbered; public: ReuseInfo(MachineInstr &mi, const MRegisterInfo *mri) : MI(mi) { - PhysRegsClobbered = new bool[mri->getNumRegs()]; - std::fill(PhysRegsClobbered, PhysRegsClobbered+mri->getNumRegs(), false); - } - ~ReuseInfo() { - delete[] PhysRegsClobbered; + PhysRegsClobbered.resize(mri->getNumRegs()); } bool hasReuses() const { @@ -428,11 +475,11 @@ namespace { } void markClobbered(unsigned PhysReg) { - PhysRegsClobbered[PhysReg] = true; + PhysRegsClobbered.set(PhysReg); } bool isClobbered(unsigned PhysReg) const { - return PhysRegsClobbered[PhysReg]; + return PhysRegsClobbered.test(PhysReg); } /// GetRegForReload - We are about to emit a reload into PhysReg. If there @@ -440,18 +487,23 @@ namespace { /// a new register to use, or evict the previous reload and use this reg. unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, AvailableSpills &Spills, - std::map &MaybeDeadStores) { + std::map &MaybeDeadStores, + SmallSet &Rejected) { if (Reuses.empty()) return PhysReg; // This is most often empty. for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) { ReusedOp &Op = Reuses[ro]; // If we find some other reuse that was supposed to use this register // exactly for its reload, we can change this reload to use ITS reload - // register. - if (Op.PhysRegReused == PhysReg) { + // register. That is, unless its reload register has already been + // considered and subsequently rejected because it has also been reused + // by another operand. + if (Op.PhysRegReused == PhysReg && + Rejected.count(Op.AssignedPhysReg) == 0) { // Yup, use the reload register that we didn't use before. - unsigned NewReg = Op.AssignedPhysReg; - return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores); + unsigned NewReg = Op.AssignedPhysReg; + Rejected.insert(PhysReg); + return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected); } else { // Otherwise, we might also have a problem if a previously reused // value aliases the new register. If so, codegen the previous reload @@ -476,7 +528,7 @@ namespace { // 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); + MI, Spills, MaybeDeadStores, Rejected); MRI->loadRegFromStackSlot(*MBB, MI, NewPhysReg, NewOp.StackSlot, AliasRC); @@ -488,7 +540,7 @@ namespace { MI->getOperand(NewOp.Operand).setReg(NewPhysReg); - Spills.addAvailable(NewOp.StackSlot, NewPhysReg); + Spills.addAvailable(NewOp.StackSlot, MI, NewPhysReg); ++NumLoads; DEBUG(MachineBasicBlock::iterator MII = MI; DOUT << '\t' << *prior(MII)); @@ -503,6 +555,24 @@ namespace { } return PhysReg; } + + /// GetRegForReload - Helper for the above GetRegForReload(). Add a + /// 'Rejected' set to remember which registers have been considered and + /// rejected for the reload. This avoids infinite looping in case like + /// this: + /// t1 := op t2, t3 + /// t2 <- assigned r0 for use by the reload but ended up reuse r1 + /// t3 <- assigned r1 for use by the reload but ended up reuse r0 + /// t1 <- desires r1 + /// 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, + AvailableSpills &Spills, + std::map &MaybeDeadStores) { + SmallSet Rejected; + return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected); + } }; } @@ -538,7 +608,8 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // Loop over all of the implicit defs, clearing them from our available // sets. - const unsigned *ImpDef = TII->getImplicitDefs(MI.getOpcode()); + const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); + const unsigned *ImpDef = TID->ImplicitDefs; if (ImpDef) { for ( ; *ImpDef; ++ImpDef) { PhysRegsUsed[*ImpDef] = true; @@ -583,21 +654,21 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { unsigned PhysReg; // Check to see if this stack slot is available. - if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot))) { - + MachineInstr *SSMI = NULL; + if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot, SSMI))) { // This spilled operand might be part of a two-address operand. If this // is the case, then changing it will necessarily require changing the // def part of the instruction as well. However, in some cases, we // aren't allowed to modify the reused register. If none of these cases // apply, reuse it. bool CanReuse = true; - int ti = TII->getOperandConstraint(MI.getOpcode(), i, TOI::TIED_TO); + int ti = TID->getOperandConstraint(i, TOI::TIED_TO); if (ti != -1 && MI.getOperand(ti).isReg() && MI.getOperand(ti).getReg() == VirtReg) { // Okay, we have a two address operand. We can reuse this physreg as - // long as we are allowed to clobber the value and there is an earlier - // def that has already clobbered the physreg. + // long as we are allowed to clobber the value and there isn't an + // earlier def that has already clobbered the physreg. CanReuse = Spills.canClobberPhysReg(StackSlot) && !ReusedOperands.isClobbered(PhysReg); } @@ -610,6 +681,19 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { << MRI->getName(VRM.getPhys(VirtReg)) << "\n"; MI.getOperand(i).setReg(PhysReg); + // Extend the live range of the MI that last kill the register if + // necessary. + MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true); + if (MOK) { + MOK->unsetIsKill(); + if (ti == -1) { + // Unless it's the use of a two-address code, transfer the kill + // of the reused register to this use. + MI.getOperand(i).setIsKill(); + Spills.UpdateLastUse(PhysReg, &MI); + } + } + // The only technical detail we have is that we don't know that // PhysReg won't be clobbered by a reloaded stack slot that occurs // later in the instruction. In particular, consider 'op V1, V2'. @@ -674,11 +758,24 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { PhysRegsUsed[DesignatedReg] = true; ReusedOperands.markClobbered(DesignatedReg); MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC); - + + // Extend the live range of the MI that last kill the register if + // necessary. + if (SSMI) { + MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true); + if (MOK) { + MachineInstr *CopyMI = prior(MII); + MachineOperand *MOU = CopyMI->findRegisterUseOperand(PhysReg); + MOU->setIsKill(); + MOK->unsetIsKill(); + Spills.UpdateLastUse(PhysReg, &MI); + } + } + // This invalidates DesignatedReg. Spills.ClobberPhysReg(DesignatedReg); - Spills.addAvailable(StackSlot, DesignatedReg); + Spills.addAvailable(StackSlot, &MI, DesignatedReg); MI.getOperand(i).setReg(DesignatedReg); DOUT << '\t' << *prior(MII); ++NumReused; @@ -707,7 +804,11 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // Any stores to this stack slot are not dead anymore. MaybeDeadStores.erase(StackSlot); - Spills.addAvailable(StackSlot, PhysReg); + Spills.addAvailable(StackSlot, &MI, PhysReg); + // Assumes this is the last use. IsKill will be unset if reg is reused + // unless it's a two-address operand. + if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1) + MI.getOperand(i).setIsKill(); ++NumLoads; MI.getOperand(i).setReg(PhysReg); DOUT << '\t' << *prior(MII); @@ -739,7 +840,8 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (FrameIdx == SS) { // If this spill slot is available, turn it into a copy (or nothing) // instead of leaving it as a load! - if (unsigned InReg = Spills.getSpillSlotPhysReg(SS)) { + MachineInstr *SSMI = NULL; + if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, SSMI)) { DOUT << "Promoted Load To Copy: " << MI; MachineFunction &MF = *MBB.getParent(); if (DestReg != InReg) { @@ -750,7 +852,21 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // virtual or needing to clobber any values if it's physical). NextMII = &MI; --NextMII; // backtrack to the copy. + } else + DOUT << "Removing now-noop copy: " << MI; + + // Extend the live range of the MI that last kill the register if + // the next MI reuse it. + MachineOperand *MOK = SSMI->findRegisterUseOperand(InReg, true); + if (MOK && NextMII != MBB.end()) { + MachineOperand *MOU = NextMII->findRegisterUseOperand(InReg); + if (MOU) { + MOU->setIsKill(); + MOK->unsetIsKill(); + Spills.UpdateLastUse(InReg, &(*NextMII)); + } } + VRM.RemoveFromFoldedVirtMap(&MI); MBB.erase(&MI); goto ProcessNextInst; @@ -799,7 +915,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // If the stack slot value was previously available in some other // register, change it now. Otherwise, make the register available, // in PhysReg. - Spills.addAvailable(StackSlot, SrcReg, false /*don't clobber*/); + Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/); } } } @@ -820,6 +936,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { DOUT << "Removing now-noop copy: " << MI; MBB.erase(&MI); VRM.RemoveFromFoldedVirtMap(&MI); + Spills.disallowClobberPhysReg(VirtReg); goto ProcessNextInst; } @@ -834,7 +951,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { assert(DestReg == VirtReg && "Unknown load situation!"); // Otherwise, if it wasn't available, remember that it is now! - Spills.addAvailable(FrameIdx, DestReg); + Spills.addAvailable(FrameIdx, &MI, DestReg); goto ProcessNextInst; } @@ -849,7 +966,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // If this def is part of a two-address operand, make sure to execute // the store from the correct physical register. unsigned PhysReg; - int TiedOp = TII->findTiedToSrcOperand(MI.getOpcode(), i); + int TiedOp = MI.getInstrDescriptor()->findTiedToSrcOperand(i); if (TiedOp != -1) PhysReg = MI.getOperand(TiedOp).getReg(); else { @@ -868,19 +985,6 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { DOUT << "Store:\t" << *next(MII); MI.getOperand(i).setReg(PhysReg); - // Check to see if this is a noop copy. If so, eliminate the - // instruction before considering the dest reg to be changed. - { - unsigned Src, Dst; - if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { - ++NumDCE; - DOUT << "Removing now-noop copy: " << MI; - MBB.erase(&MI); - VRM.RemoveFromFoldedVirtMap(&MI); - goto ProcessNextInst; - } - } - // If there is a dead store to this stack slot, nuke it now. MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; if (LastStore) { @@ -896,8 +1000,21 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // in PhysReg. Spills.ModifyStackSlot(StackSlot); Spills.ClobberPhysReg(PhysReg); - Spills.addAvailable(StackSlot, PhysReg); + Spills.addAvailable(StackSlot, LastStore, PhysReg); ++NumStores; + + // Check to see if this is a noop copy. If so, eliminate the + // instruction before considering the dest reg to be changed. + { + unsigned Src, Dst; + if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { + ++NumDCE; + DOUT << "Removing now-noop copy: " << MI; + MBB.erase(&MI); + VRM.RemoveFromFoldedVirtMap(&MI); + goto ProcessNextInst; + } + } } } ProcessNextInst: