From 063eb4e38935f2c55620feb5135f6d3b9fa2450f Mon Sep 17 00:00:00 2001
From: JF Bastien <jfb@google.com>
Date: Wed, 15 Jul 2015 21:51:33 +0000
Subject: [PATCH] Fix mergefunc infinite loop

Self-referential constants containing references to a merged function
no longer cause the MergeFunctions pass to infinite loop. Also adds a
reproduction IR which would otherwise fail, which was isolated from a similar
issue in Chromium.

Author: jrkoenig
Reviewers: nlewycky, jfb
Subscribers: llvm-commits, nlewycky, jfb

Differential Revision: http://reviews.llvm.org/D11208

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@242337 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/IPO/MergeFunctions.cpp         |  8 +++-
 .../MergeFunc/self-referential-global.ll      | 40 +++++++++++++++++++
 2 files changed, 46 insertions(+), 2 deletions(-)
 create mode 100644 test/Transforms/MergeFunc/self-referential-global.ll

diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp
index 2e3519eac6a..109cac7fece 100644
--- a/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/lib/Transforms/IPO/MergeFunctions.cpp
@@ -1516,6 +1516,8 @@ void MergeFunctions::remove(Function *F) {
 void MergeFunctions::removeUsers(Value *V) {
   std::vector<Value *> Worklist;
   Worklist.push_back(V);
+  SmallSet<Value*, 8> Visited;
+  Visited.insert(V);
   while (!Worklist.empty()) {
     Value *V = Worklist.back();
     Worklist.pop_back();
@@ -1526,8 +1528,10 @@ void MergeFunctions::removeUsers(Value *V) {
       } else if (isa<GlobalValue>(U)) {
         // do nothing
       } else if (Constant *C = dyn_cast<Constant>(U)) {
-        for (User *UU : C->users())
-          Worklist.push_back(UU);
+        for (User *UU : C->users()) {
+          if (!Visited.insert(UU).second)
+            Worklist.push_back(UU);
+        }
       }
     }
   }
diff --git a/test/Transforms/MergeFunc/self-referential-global.ll b/test/Transforms/MergeFunc/self-referential-global.ll
new file mode 100644
index 00000000000..d3d1c62aa7f
--- /dev/null
+++ b/test/Transforms/MergeFunc/self-referential-global.ll
@@ -0,0 +1,40 @@
+; RUN: opt -mergefunc -disable-output < %s
+
+; A linked list type and simple payload
+%LL = type { %S, %LL* }
+%S = type { void (%S*, i32)* }
+
+; Table refers to itself via GEP
+@Table = internal global [3 x %LL] [%LL { %S { void (%S*, i32)* @B }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }, %LL { %S { void (%S*, i32)* @A }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }, %LL { %S { void (%S*, i32)* @A }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }], align 16
+
+; The body of this is irrelevant; it is long so that mergefunc doesn't skip it as a small function.
+define internal void @A(%S* %self, i32 %a) {
+  %1 = add i32 %a, 32
+  %2 = add i32 %1, 32
+  %3 = add i32 %2, 32
+  %4 = add i32 %3, 32
+  %5 = add i32 %4, 32
+  %6 = add i32 %5, 32
+  %7 = add i32 %6, 32
+  %8 = add i32 %7, 32
+  %9 = add i32 %8, 32
+  %10 = add i32 %9, 32
+  %11 = add i32 %10, 32
+  ret void
+}
+
+define internal void @B(%S* %self, i32 %a) {
+  %1 = add i32 %a, 32
+  %2 = add i32 %1, 32
+  %3 = add i32 %2, 32
+  %4 = add i32 %3, 32
+  %5 = add i32 %4, 32
+  %6 = add i32 %5, 32
+  %7 = add i32 %6, 32
+  %8 = add i32 %7, 32
+  %9 = add i32 %8, 32
+  %10 = add i32 %9, 32
+  %11 = add i32 %10, 32
+  ret void
+}
+
-- 
2.34.1