From 5881799d0cccbd814ec1b0f0509df9be1f63c6cb Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 8 Mar 2011 22:46:11 +0000 Subject: Delete dead code after rematerializing. LiveRangeEdit::eliminateDeadDefs() will eventually be used by coalescing, splitting, and spilling for dead code elimination. It can delete chains of dead instructions as long as there are no dependency loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127287 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveRangeEdit.cpp | 59 +++++++++++++++++++++++++++++++++++++++++++ lib/CodeGen/LiveRangeEdit.h | 8 ++++++ lib/CodeGen/SplitKit.cpp | 38 +++++++++++++++++++++++++++- lib/CodeGen/SplitKit.h | 3 +++ 4 files changed, 107 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen') diff --git a/lib/CodeGen/LiveRangeEdit.cpp b/lib/CodeGen/LiveRangeEdit.cpp index 7de1284cb9..4e2c00df38 100644 --- a/lib/CodeGen/LiveRangeEdit.cpp +++ b/lib/CodeGen/LiveRangeEdit.cpp @@ -13,9 +13,12 @@ #include "LiveRangeEdit.h" #include "VirtRegMap.h" +#include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -128,3 +131,59 @@ SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB, return lis.InsertMachineInstrInMaps(--MI).getDefIndex(); } +void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl &Dead, + LiveIntervals &LIS, + const TargetInstrInfo &TII) { + SetVector, + SmallPtrSet > ToShrink; + + for (;;) { + // Erase all dead defs. + while (!Dead.empty()) { + MachineInstr *MI = Dead.pop_back_val(); + assert(MI->allDefsAreDead() && "Def isn't really dead"); + + // Never delete inline asm. + if (MI->isInlineAsm()) + continue; + + // Use the same criteria as DeadMachineInstructionElim. + bool SawStore = false; + if (!MI->isSafeToMove(&TII, 0, SawStore)) + continue; + + SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex(); + DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI); + + // Check for live intervals that may shrink + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + if (!MOI->isReg()) + continue; + unsigned Reg = MOI->getReg(); + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + LiveInterval &LI = LIS.getInterval(Reg); + // Remove defined value. + if (MOI->isDef()) + if (VNInfo *VNI = LI.getVNInfoAt(Idx)) + LI.removeValNo(VNI); + // Shrink read registers. + if (MI->readsVirtualRegister(Reg)) + ToShrink.insert(&LI); + } + + LIS.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + } + + if (ToShrink.empty()) + break; + + // Shrink just one live interval. Then delete new dead defs. + LIS.shrinkToUses(ToShrink.back(), &Dead); + ToShrink.pop_back(); + } +} + diff --git a/lib/CodeGen/LiveRangeEdit.h b/lib/CodeGen/LiveRangeEdit.h index 9518130560..6a4ccfdbc4 100644 --- a/lib/CodeGen/LiveRangeEdit.h +++ b/lib/CodeGen/LiveRangeEdit.h @@ -128,6 +128,14 @@ public: bool didRematerialize(const VNInfo *ParentVNI) const { return rematted_.count(ParentVNI); } + + /// eliminateDeadDefs - Try to delete machine instructions that are now dead + /// (allDefsAreDead returns true). This may cause live intervals to be trimmed + /// and further dead efs to be eliminated. + void eliminateDeadDefs(SmallVectorImpl &Dead, + LiveIntervals&, + const TargetInstrInfo&); + }; } diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index c4ae8c474c..99d05fa655 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -797,6 +797,40 @@ void SplitEditor::rewriteComponents(const SmallVectorImpl &Intvs, } } +void SplitEditor::deleteRematVictims() { + SmallVector Dead; + for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), + E = Edit->getParent().vni_end(); I != E; ++I) { + const VNInfo *VNI = *I; + // Was VNI rematted anywhere? + if (VNI->isUnused() || VNI->isPHIDef() || !Edit->didRematerialize(VNI)) + continue; + unsigned RegIdx = RegAssign.lookup(VNI->def); + LiveInterval *LI = Edit->get(RegIdx); + LiveInterval::const_iterator LII = LI->FindLiveRangeContaining(VNI->def); + assert(LII != LI->end() && "Missing live range for rematted def"); + + // Is this a dead def? + if (LII->end != VNI->def.getNextSlot()) + continue; + + MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); + assert(MI && "Missing instruction for dead def"); + MI->addRegisterDead(LI->reg, &TRI); + + if (!MI->allDefsAreDead()) + continue; + + DEBUG(dbgs() << "All defs dead: " << *MI); + Dead.push_back(MI); + } + + if (Dead.empty()) + return; + + Edit->eliminateDeadDefs(Dead, LIS, TII); +} + void SplitEditor::finish() { assert(OpenIdx == 0 && "Previous LI not closed before rewrite"); ++NumFinished; @@ -835,7 +869,9 @@ void SplitEditor::finish() { // Rewrite virtual registers, possibly extending ranges. rewriteAssigned(Complex); - // FIXME: Delete defs that were rematted everywhere. + // Delete defs that were rematted everywhere. + if (Complex) + deleteRematVictims(); // Get rid of unused values and set phi-kill flags. for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 0e35df0ed6..3f1a03c0ba 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -272,6 +272,9 @@ class SplitEditor { void rewriteComponents(const SmallVectorImpl &Intvs, const ConnectedVNInfoEqClasses &ConEq); + /// deleteRematVictims - Delete defs that are dead after rematerializing. + void deleteRematVictims(); + public: /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. /// Newly created intervals will be appended to newIntervals. -- cgit v1.2.3