X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.cpp;h=3fb84bdd8f74c278c436c60edd13f241a8f47335;hb=2d87734a8ffad5933edbbc15a3b643df1e8a767e;hp=4f1230cd2074da0495c726f02dd6fe98d65c2b82;hpb=50d25d7ff7326adef7c76ba79be3dd1d7240a81f;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index 4f1230cd207..3fb84bdd8f7 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -35,6 +35,7 @@ using namespace llvm; STATISTIC(NumSpills, "Number of register spills"); +STATISTIC(NumReMats, "Number of re-materialization"); STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); STATISTIC(NumReused, "Number of values reused"); @@ -60,7 +61,8 @@ namespace { VirtRegMap::VirtRegMap(MachineFunction &mf) : TII(*mf.getTarget().getInstrInfo()), MF(mf), - Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT) { + Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT), + ReMatId(MAX_STACK_SLOT+1) { grow(); } @@ -85,9 +87,27 @@ void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) { assert(MRegisterInfo::isVirtualRegister(virtReg)); assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && "attempt to assign stack slot to already spilled register"); + assert((frameIndex >= 0 || + (frameIndex >= MF.getFrameInfo()->getObjectIndexBegin())) && + "illegal fixed frame index"); Virt2StackSlotMap[virtReg] = frameIndex; } +int VirtRegMap::assignVirtReMatId(unsigned virtReg) { + assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && + "attempt to assign re-mat id to already spilled register"); + const MachineInstr *DefMI = getReMaterializedMI(virtReg); + int FrameIdx; + if (TII.isLoadFromStackSlot((MachineInstr*)DefMI, FrameIdx)) { + // Load from stack slot is re-materialize as reload from the stack slot! + Virt2StackSlotMap[virtReg] = FrameIdx; + return FrameIdx; + } + Virt2StackSlotMap[virtReg] = ReMatId; + return ReMatId++; +} + void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, unsigned OpNo, MachineInstr *NewMI) { // Move previous memory references folded to new instruction. @@ -227,13 +247,17 @@ namespace { DOUT << "\n**** Local spiller rewriting function '" << MF.getFunction()->getName() << "':\n"; + std::vector ReMatedMIs; for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); MBB != E; ++MBB) - RewriteMBB(*MBB, VRM); + RewriteMBB(*MBB, VRM, ReMatedMIs); + for (unsigned i = 0, e = ReMatedMIs.size(); i != e; ++i) + delete ReMatedMIs[i]; return true; } private: - void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); + void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, + std::vector &ReMatedMIs); }; } @@ -254,8 +278,9 @@ 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. - typedef std::pair SSInfo; + // but not invalidated yet. It also tracks the instructions that defined + // or used the register. + typedef std::pair > SSInfo; std::map SpillSlotsAvailable; // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating @@ -280,11 +305,49 @@ public: unsigned getSpillSlotPhysReg(int Slot, MachineInstr *&SSMI) const { std::map::const_iterator I = SpillSlotsAvailable.find(Slot); if (I != SpillSlotsAvailable.end()) { - SSMI = I->second.second; + if (!I->second.second.empty()) + SSMI = I->second.second.back(); return I->second.first >> 1; // Remove the CanClobber bit. } return 0; } + + /// addLastUse - Add the last use information of all stack slots whose + /// values are available in the specific register. + void addLastUse(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!"); + // This can be true if there are multiple uses of the same register. + if (II->second.second.back() != Use) + II->second.second.push_back(Use); + } + } + + /// removeLastUse - Remove the last use information of all stack slots whose + /// values are available in the specific register. + void removeLastUse(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!"); + if (II->second.second.back() == Use) + II->second.second.pop_back(); + } + } /// addAvailable - Mark that the specified stack slot is available in the /// specified physreg. If CanClobber is true, the physreg can be modified at @@ -296,11 +359,16 @@ public: ModifyStackSlot(Slot); PhysRegsAvailable.insert(std::make_pair(Reg, Slot)); + std::vector DefUses; + DefUses.push_back(MI); SpillSlotsAvailable[Slot] = - std::make_pair((Reg << 1) | (unsigned)CanClobber, MI); + std::make_pair((Reg << 1) | (unsigned)CanClobber, DefUses); - DOUT << "Remembering SS#" << Slot << " in physreg " - << MRI->getName(Reg) << "\n"; + if (Slot > VirtRegMap::MAX_STACK_SLOT) + DOUT << "Remembering RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1; + else + DOUT << "Remembering SS#" << Slot; + DOUT << " in physreg " << MRI->getName(Reg) << "\n"; } /// canClobberPhysReg - Return true if the spiller is allowed to change the @@ -366,7 +434,11 @@ void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { "Bidirectional map mismatch!"); SpillSlotsAvailable.erase(Slot); DOUT << "PhysReg " << MRI->getName(PhysReg) - << " clobbered, invalidating SS#" << Slot << "\n"; + << " clobbered, invalidating "; + if (Slot > VirtRegMap::MAX_STACK_SLOT) + DOUT << "RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1 << "\n"; + else + DOUT << "SS#" << Slot << "\n"; } } @@ -560,8 +632,8 @@ namespace { /// rewriteMBB - Keep track of which spills are available even after the /// register allocator is done with them. If possible, avoid reloading vregs. -void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { - +void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, + std::vector &ReMatedMIs) { DOUT << MBB.getBasicBlock()->getName() << ":\n"; // Spills - Keep track of which spilled values are available in physregs so @@ -590,6 +662,29 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // Loop over all of the implicit defs, clearing them from our available // sets. const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); + + // If this instruction is being rematerialized, just remove it! + int FrameIdx; + if ((TID->Flags & M_REMATERIALIZIBLE) || + TII->isLoadFromStackSlot(&MI, FrameIdx)) { + bool Remove = true; + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (!MO.isRegister() || MO.getReg() == 0) + continue; // Ignore non-register operands. + if (MO.isDef() && !VRM.isReMaterialized(MO.getReg())) { + Remove = false; + break; + } + } + if (Remove) { + VRM.RemoveFromFoldedVirtMap(&MI); + ReMatedMIs.push_back(MI.removeFromParent()); + MII = NextMII; + continue; + } + } + const unsigned *ImpDef = TID->ImplicitDefs; if (ImpDef) { for ( ; *ImpDef; ++ImpDef) { @@ -631,6 +726,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (!MO.isUse()) continue; // Handle defs in the loop below (handle use&def here though) + bool doReMat = VRM.isReMaterialized(VirtReg); int StackSlot = VRM.getStackSlot(VirtReg); unsigned PhysReg; @@ -656,7 +752,11 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (CanReuse) { // If this stack slot value is already available, reuse it! - DOUT << "Reusing SS#" << StackSlot << " from physreg " + if (StackSlot > VirtRegMap::MAX_STACK_SLOT) + DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1; + else + DOUT << "Reusing SS#" << StackSlot; + DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg" << VirtReg <<" instead of reloading into physreg " << MRI->getName(VRM.getPhys(VirtReg)) << "\n"; @@ -664,13 +764,21 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // 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. + bool WasKill = false; + if (SSMI) { + int UIdx = SSMI->findRegisterUseOperand(PhysReg, true); + if (UIdx != -1) { + MachineOperand &MOK = SSMI->getOperand(UIdx); + WasKill = MOK.isKill(); + 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. + if (WasKill) MI.getOperand(i).setIsKill(); + Spills.addLastUse(PhysReg, &MI); } // The only technical detail we have is that we don't know that @@ -721,8 +829,11 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // incoming, we don't need to inserted a dead copy. if (DesignatedReg == PhysReg) { // If this stack slot value is already available, reuse it! - DOUT << "Reusing SS#" << StackSlot << " from physreg " - << MRI->getName(PhysReg) << " for vreg" + if (StackSlot > VirtRegMap::MAX_STACK_SLOT) + DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1; + else + DOUT << "Reusing SS#" << StackSlot; + DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg" << VirtReg << " instead of reloading into same physreg.\n"; MI.getOperand(i).setReg(PhysReg); @@ -737,7 +848,28 @@ 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. + bool WasKill = false; + if (SSMI) { + int UIdx = SSMI->findRegisterUseOperand(PhysReg, true); + if (UIdx != -1) { + MachineOperand &MOK = SSMI->getOperand(UIdx); + WasKill = MOK.isKill(); + MOK.unsetIsKill(); + } + } + MachineInstr *CopyMI = prior(MII); + if (WasKill) { + // Transfer kill to the next use. + int UIdx = CopyMI->findRegisterUseOperand(PhysReg); + assert(UIdx != -1); + MachineOperand &MOU = CopyMI->getOperand(UIdx); + MOU.setIsKill(); + } + Spills.addLastUse(PhysReg, CopyMI); + // This invalidates DesignatedReg. Spills.ClobberPhysReg(DesignatedReg); @@ -764,14 +896,24 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { PhysRegsUsed[PhysReg] = true; ReusedOperands.markClobbered(PhysReg); - MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); + if (doReMat) { + MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg)); + ++NumReMats; + } else { + MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); + ++NumLoads; + } // This invalidates PhysReg. Spills.ClobberPhysReg(PhysReg); // Any stores to this stack slot are not dead anymore. - MaybeDeadStores.erase(StackSlot); + if (!doReMat) + MaybeDeadStores.erase(StackSlot); Spills.addAvailable(StackSlot, &MI, PhysReg); - ++NumLoads; + // 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(); MI.getOperand(i).setReg(PhysReg); DOUT << '\t' << *prior(MII); } @@ -802,8 +944,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! - MachineInstr *Dummy = NULL; - if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, Dummy)) { + MachineInstr *SSMI = NULL; + if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, SSMI)) { DOUT << "Promoted Load To Copy: " << MI; MachineFunction &MF = *MBB.getParent(); if (DestReg != InReg) { @@ -814,7 +956,37 @@ 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; + + // Either way, the live range of the last kill of InReg has been + // extended. Remove its kill. + bool WasKill = false; + if (SSMI) { + int UIdx = SSMI->findRegisterUseOperand(InReg, true); + if (UIdx != -1) { + MachineOperand &MOK = SSMI->getOperand(UIdx); + WasKill = MOK.isKill(); + MOK.unsetIsKill(); + } } + if (NextMII != MBB.end()) { + // If NextMII uses InReg and the use is not a two address + // operand, mark it killed. + int UIdx = NextMII->findRegisterUseOperand(InReg); + if (UIdx != -1) { + MachineOperand &MOU = NextMII->getOperand(UIdx); + if (WasKill) { + const TargetInstrDescriptor *NTID = + NextMII->getInstrDescriptor(); + if (UIdx >= NTID->numOperands || + NTID->getOperandConstraint(UIdx, TOI::TIED_TO) == -1) + MOU.setIsKill(); + } + Spills.addLastUse(InReg, &(*NextMII)); + } + } + VRM.RemoveFromFoldedVirtMap(&MI); MBB.erase(&MI); goto ProcessNextInst; @@ -882,6 +1054,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { ++NumDCE; DOUT << "Removing now-noop copy: " << MI; + Spills.removeLastUse(Src, &MI); MBB.erase(&MI); VRM.RemoveFromFoldedVirtMap(&MI); Spills.disallowClobberPhysReg(VirtReg); @@ -958,6 +1131,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { ++NumDCE; DOUT << "Removing now-noop copy: " << MI; + Spills.removeLastUse(Src, &MI); MBB.erase(&MI); VRM.RemoveFromFoldedVirtMap(&MI); goto ProcessNextInst;