Previously, RecursivelyDeleteDeadInstructions provided an option

of returning a list of pointers to Values that are deleted. This was
unsafe, because the pointers in the list are, by nature of what
RecursivelyDeleteDeadInstructions does, always dangling. Replace this
with a simple callback mechanism. This may eventually be removed if
all clients can reasonably be expected to use CallbackVH.

Use this to factor out the dead-phi-cycle-elimination code from LSR
utility function, and generalize it to use the
RecursivelyDeleteTriviallyDeadInstructions utility function.

This makes LSR more aggressive about eliminating dead PHI cycles;
adjust tests to either be less trivial or to simply expect fewer
instructions.

llvm-svn: 70636

3 files changed, 77 insertions, 41 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index e5502002713..b9406651525 100644
--- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -32,6 +32,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ValueHandle.h"
 #include "llvm/Target/TargetLowering.h"
 #include <algorithm>
 using namespace llvm;
@@ -2138,6 +2139,7 @@ ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond,
     CondUse = &IVUsesByStride[*NewStride].Users.back();
     CondStride = NewStride;
     ++NumEliminated;
+    Changed = true;
   }
 
   return Cond;
@@ -2501,44 +2503,21 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
   StrideOrder.clear();
 
   // Clean up after ourselves
-  if (!DeadInsts.empty()) {
+  if (!DeadInsts.empty())
     DeleteTriviallyDeadInstructions();
 
-    BasicBlock::iterator I = L->getHeader()->begin();
-    while (PHINode *PN = dyn_cast<PHINode>(I++)) {
-      // At this point, we know that we have killed one or more IV users.
-      // It is worth checking to see if the cannonical indvar is also
-      // dead, so that we can remove it as well.
-      //
-      // We can remove a PHI if it is on a cycle in the def-use graph
-      // where each node in the cycle has degree one, i.e. only one use,
-      // and is an instruction with no side effects.
-      //
-      // FIXME: this needs to eliminate an induction variable even if it's being
-      // compared against some value to decide loop termination.
-      if (!PN->hasOneUse())
-        continue;
-      
-      SmallPtrSet<PHINode *, 4> PHIs;
-      for (Instruction *J = dyn_cast<Instruction>(*PN->use_begin());
-           J && J->hasOneUse() && !J->mayWriteToMemory();
-           J = dyn_cast<Instruction>(*J->use_begin())) {
-        // If we find the original PHI, we've discovered a cycle.
-        if (J == PN) {
-          // Break the cycle and mark the PHI for deletion.
-          SE->deleteValueFromRecords(PN);
-          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
-          DeadInsts.push_back(PN);
-          Changed = true;
-          break;
-        }
-        // If we find a PHI more than once, we're on a cycle that
-        // won't prove fruitful.
-        if (isa<PHINode>(J) && !PHIs.insert(cast<PHINode>(J)))
-          break;
-      }
+  // At this point, it is worth checking to see if any recurrence PHIs are also
+  // dead, so that we can remove them as well. To keep ScalarEvolution
+  // current, use a ValueDeletionListener class.
+  struct LSRListener : public ValueDeletionListener {
+    ScalarEvolution &SE;
+    explicit LSRListener(ScalarEvolution &se) : SE(se) {}
+
+    virtual void ValueWillBeDeleted(Value *V) {
+      SE.deleteValueFromRecords(V);
     }
-    DeleteTriviallyDeadInstructions();
-  }
+  } VDL(*SE);
+  DeleteDeadPHIs(L->getHeader(), &VDL);
+
   return Changed;
 }
diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
index 97460bf1add..076f89e3374 100644
--- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -22,6 +22,8 @@
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Support/ValueHandle.h"
 #include <algorithm>
 using namespace llvm;
 
@@ -73,6 +75,24 @@ void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) {
 }
 
 
+/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
+/// is dead. Also recursively delete any operands that become dead as
+/// a result. This includes tracing the def-use list from the PHI to see if
+/// it is ultimately unused or if it reaches an unused cycle.  If a
+/// ValueDeletionListener is specified, it is notified of the deletions.
+void llvm::DeleteDeadPHIs(BasicBlock *BB, ValueDeletionListener *VDL) {
+  // Recursively deleting a PHI may cause multiple PHIs to be deleted
+  // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete.
+  SmallVector<WeakVH, 8> PHIs;
+  for (BasicBlock::iterator I = BB->begin();
+       PHINode *PN = dyn_cast<PHINode>(I); ++I)
+    PHIs.push_back(PN);
+
+  for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+    if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
+      RecursivelyDeleteDeadPHINode(PN, VDL);
+}
+
 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
 /// if possible.  The return value indicates success or failure.
 bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index 4be1b8717d2..3b36362bb39 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Instructions.h"
 #include "llvm/Intrinsics.h"
 #include "llvm/IntrinsicInst.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DebugInfo.h"
 #include "llvm/Target/TargetData.h"
@@ -177,14 +178,18 @@ bool llvm::isInstructionTriviallyDead(Instruction *I) {
   return false;
 }
 
+/// ~ValueDeletionListener - A trivial dtor, defined out of line to give the
+/// class a home.
+llvm::ValueDeletionListener::~ValueDeletionListener() {}
+
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands
 /// trivially dead, delete them too, recursively.
 ///
-/// If DeadInst is specified, the vector is filled with the instructions that
-/// are actually deleted.
+/// If a ValueDeletionListener is specified, it is notified of instructions that
+/// are actually deleted (before they are actually deleted).
 void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
-                                      SmallVectorImpl<Instruction*> *DeadInst) {
+                                                   ValueDeletionListener *VDL) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I))
     return;
@@ -197,8 +202,8 @@ void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
     DeadInsts.pop_back();
 
     // If the client wanted to know, tell it about deleted instructions.
-    if (DeadInst)
-      DeadInst->push_back(I);
+    if (VDL)
+      VDL->ValueWillBeDeleted(I);
     
     // Null out all of the instruction's operands to see if any operand becomes
     // dead as we go.
@@ -220,6 +225,38 @@ void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
   }
 }
 
+/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
+/// dead PHI node, due to being a def-use chain of single-use nodes that
+/// either forms a cycle or is terminated by a trivially dead instruction,
+/// delete it.  If that makes any of its operands trivially dead, delete them
+/// too, recursively.
+///
+/// If a ValueDeletionListener is specified, it is notified of instructions that
+/// are actually deleted (before they are actually deleted).
+void
+llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, ValueDeletionListener *VDL) {
+
+  // We can remove a PHI if it is on a cycle in the def-use graph
+  // where each node in the cycle has degree one, i.e. only one use,
+  // and is an instruction with no side effects.
+  if (!PN->hasOneUse())
+    return;
+
+  SmallPtrSet<PHINode *, 4> PHIs;
+  PHIs.insert(PN);
+  for (Instruction *J = cast<Instruction>(*PN->use_begin());
+       J->hasOneUse() && !J->mayWriteToMemory();
+       J = cast<Instruction>(*J->use_begin()))
+    // If we find a PHI more than once, we're on a cycle that
+    // won't prove fruitful.
+    if (PHINode *JP = dyn_cast<PHINode>(J))
+      if (!PHIs.insert(cast<PHINode>(JP))) {
+        // Break the cycle and delete the PHI and its operands.
+        JP->replaceAllUsesWith(UndefValue::get(JP->getType()));
+        RecursivelyDeleteTriviallyDeadInstructions(JP, VDL);
+        break;
+      }
+}
 
 //===----------------------------------------------------------------------===//
 //  Control Flow Graph Restructuring...