Teach RecursivelyDeleteDeadPHINodes to handle multiple self-references. Patch

by Andrew Clinton!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126077 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 30e88e976f2f9fae2d8ec123bfb23fd29276c8e5..063c76e9522cd0eca0483953993d4868388c3a7a 100644 (file)
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -260,29 +260,45 @@ bool llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) {
   return true;
 }
 
   return true;
 }
 

+/// areAllUsesEqual - Check whether the uses of a value are all the same.
+/// This is similar to Instruction::hasOneUse() except this will also return
+/// true when there are multiple uses that all refer to the same value.
+static bool areAllUsesEqual(Instruction *I) {
+  Value::use_iterator UI = I->use_begin();
+  Value::use_iterator UE = I->use_end();
+  if (UI == UE)
+    return false;
+
+  User *TheUse = *UI;
+  for (++UI; UI != UE; ++UI) {
+    if (*UI != TheUse)
+      return false;
+  }
+  return true;
+}
+

 /// 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.  Return true if the PHI node is actually deleted.
 /// 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.  Return true if the PHI node is actually deleted.

-bool
-llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) {
+bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) {

   // 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.
   // 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())
+  if (!areAllUsesEqual(PN))

     return false;
 
   bool Changed = false;
   SmallPtrSet<PHINode *, 4> PHIs;
   PHIs.insert(PN);
   for (Instruction *J = cast<Instruction>(*PN->use_begin());
     return false;
 
   bool Changed = false;
   SmallPtrSet<PHINode *, 4> PHIs;
   PHIs.insert(PN);
   for (Instruction *J = cast<Instruction>(*PN->use_begin());

-       J->hasOneUse() && !J->mayHaveSideEffects();
+       areAllUsesEqual(J) && !J->mayHaveSideEffects();

        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))
        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))) {
+      if (!PHIs.insert(JP)) {

         // Break the cycle and delete the PHI and its operands.
         JP->replaceAllUsesWith(UndefValue::get(JP->getType()));
         (void)RecursivelyDeleteTriviallyDeadInstructions(JP);
         // Break the cycle and delete the PHI and its operands.
         JP->replaceAllUsesWith(UndefValue::get(JP->getType()));
         (void)RecursivelyDeleteTriviallyDeadInstructions(JP);

diff --git a/test/Transforms/LoopStrengthReduce/pr2570.ll b/test/Transforms/LoopStrengthReduce/pr2570.ll
index aafd24ebba1eb7ae0f3a62c29a97823620eb5aae..80efb9f87e53f0aa1e431a50622c619fa849b7c2 100644 (file)
--- a/test/Transforms/LoopStrengthReduce/pr2570.ll
+++ b/test/Transforms/LoopStrengthReduce/pr2570.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -loop-reduce -S | grep {phi\\>} | count 10
+; RUN: opt < %s -loop-reduce -S | grep {phi\\>} | count 8

 ; PR2570
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
 ; PR2570
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"

diff --git a/unittests/Transforms/Utils/Local.cpp b/unittests/Transforms/Utils/Local.cpp
new file mode 100644 (file)
index 0000000..e969e95
--- /dev/null
+++ b/unittests/Transforms/Utils/Local.cpp
@@ -0,0 +1,49 @@
+//===- Local.cpp - Unit tests for Local -----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
+#include "llvm/Support/IRBuilder.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+using namespace llvm;
+
+TEST(Local, RecursivelyDeleteDeadPHINodes) {
+  LLVMContext &C(getGlobalContext());
+
+  IRBuilder<> builder(C);
+
+  // Make blocks
+  BasicBlock *bb0 = BasicBlock::Create(C);
+  BasicBlock *bb1 = BasicBlock::Create(C);
+
+  builder.SetInsertPoint(bb0);
+  PHINode    *phi = builder.CreatePHI(Type::getInt32Ty(C));
+  BranchInst *br0 = builder.CreateCondBr(builder.getTrue(), bb0, bb1);
+
+  builder.SetInsertPoint(bb1);
+  BranchInst *br1 = builder.CreateBr(bb0);
+
+  phi->addIncoming(phi, bb0);
+  phi->addIncoming(phi, bb1);
+
+  // The PHI will be removed
+  EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
+
+  // Make sure the blocks only contain the branches
+  EXPECT_EQ(&bb0->front(), br0);
+  EXPECT_EQ(&bb1->front(), br1);
+
+  bb0->dropAllReferences();
+  bb1->dropAllReferences();
+  delete bb0;
+  delete bb1;
+}