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

4 files changed, 107 insertions, 1 deletions

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<MachineInstr*> &Dead,
+                                      LiveIntervals &LIS,
+                                      const TargetInstrInfo &TII) {
+  SetVector<LiveInterval*,
+            SmallVector<LiveInterval*, 8>,
+            SmallPtrSet<LiveInterval*, 8> > 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<MachineInstr*> &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<LiveInterval*> &Intvs,
   }
 }
 
+void SplitEditor::deleteRematVictims() {
+  SmallVector<MachineInstr*, 8> 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<LiveInterval*> &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.