From 7c393ccd9736428919f59443e8f5104906a0c8f6 Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Wed, 2 Sep 2015 19:52:23 +0000
Subject: [PATCH] [RemoveDuplicatePHINodes] Start over after removing a PHI.

This makes RemoveDuplicatePHINodes more effective and fixes an assertion
failure. Triggering the assertions requires a DenseSet reallocation
so this change only contains a constructive test.

I'll explain the issue with a small example. In the following function
there's a duplicate PHI, %4 and %5 are identical. When this is found
the DenseSet in RemoveDuplicatePHINodes contains %2, %3 and %4.

define void @F() {
  br label %1

; <label>:1                                       ; preds = %1, %0
  %2 = phi i32 [ 42, %0 ], [ %4, %1 ]
  %3 = phi i32 [ 42, %0 ], [ %5, %1 ]
  %4 = phi i32 [ 42, %0 ], [ 23, %1 ]
  %5 = phi i32 [ 42, %0 ], [ 23, %1 ]
  br label %1
}

after RemoveDuplicatePHINodes runs the function looks like this. %3 has
changed and is now identical to %2, but RemoveDuplicatePHINodes never
saw this.

define void @F() {
  br label %1

; <label>:1                                       ; preds = %1, %0
  %2 = phi i32 [ 42, %0 ], [ %4, %1 ]
  %3 = phi i32 [ 42, %0 ], [ %4, %1 ]
  %4 = phi i32 [ 42, %0 ], [ 23, %1 ]
  br label %1
}

If the DenseSet does a reallocation now it will reinsert all
keys and stumble over %3 now having a different hash value than it had
when inserted into the map for the first time. This change clears the
set whenever a PHI is deleted and starts the progress from the
beginning, allowing %3 to be deleted and avoiding inconsistent DenseSet
state. This potentially has a negative performance impact because
it rescans all PHIs, but I don't think that this ever makes a difference
in practice.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@246694 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/Local.cpp       |  5 ++++
 unittests/Transforms/Utils/Local.cpp | 37 ++++++++++++++++++++++++++++
 2 files changed, 42 insertions(+)

diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 8c29ed50b45..b0f729b2703 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -874,6 +874,11 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
       PN->replaceAllUsesWith(*Inserted.first);
       PN->eraseFromParent();
       Changed = true;
+
+      // The RAUW can change PHIs that we already visited. Start over from the
+      // beginning.
+      PHISet.clear();
+      I = BB->begin();
     }
   }
 
diff --git a/unittests/Transforms/Utils/Local.cpp b/unittests/Transforms/Utils/Local.cpp
index f0c3ecfbb9b..2ff56047555 100644
--- a/unittests/Transforms/Utils/Local.cpp
+++ b/unittests/Transforms/Utils/Local.cpp
@@ -58,3 +58,40 @@ TEST(Local, RecursivelyDeleteDeadPHINodes) {
   delete bb0;
   delete bb1;
 }
+
+TEST(Local, RemoveDuplicatePHINodes) {
+  LLVMContext &C(getGlobalContext());
+  IRBuilder<> B(C);
+
+  std::unique_ptr<Function> F(
+      Function::Create(FunctionType::get(B.getVoidTy(), false),
+                       GlobalValue::ExternalLinkage, "F"));
+  BasicBlock *Entry(BasicBlock::Create(C, "", F.get()));
+  BasicBlock *BB(BasicBlock::Create(C, "", F.get()));
+  BranchInst::Create(BB, Entry);
+
+  B.SetInsertPoint(BB);
+
+  AssertingVH<PHINode> P1 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P1->addIncoming(B.getInt32(42), Entry);
+
+  PHINode *P2 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P2->addIncoming(B.getInt32(42), Entry);
+
+  AssertingVH<PHINode> P3 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P3->addIncoming(B.getInt32(42), Entry);
+  P3->addIncoming(B.getInt32(23), BB);
+
+  PHINode *P4 = B.CreatePHI(Type::getInt32Ty(C), 2);
+  P4->addIncoming(B.getInt32(42), Entry);
+  P4->addIncoming(B.getInt32(23), BB);
+
+  P1->addIncoming(P3, BB);
+  P2->addIncoming(P4, BB);
+  BranchInst::Create(BB, BB);
+
+  // Verify that we can eliminate PHIs that become duplicates after chaning PHIs
+  // downstream.
+  EXPECT_TRUE(EliminateDuplicatePHINodes(BB));
+  EXPECT_EQ(3U, BB->size());
+}
-- 
2.34.1