From 6821f63c91b111e0e6f427654c4b6272214a57f1 Mon Sep 17 00:00:00 2001
From: Matthias Braun <matze@braunis.de>
Date: Wed, 29 Jul 2015 23:22:48 +0000
Subject: [PATCH] IR: Implement Value::mergeUseLists() iteratively

This avoids stack overflows when the the compiler does not perform tail call
elimination. Apparently this happens for MSVC with the /Ob2 switch which
may be used by external code including this header.

Reported by and based on a patch from Jean-Francois Riendeau.

Related to rdar://21900756

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243590 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/IR/Value.h | 42 +++++++++++++++++++++--------------------
 1 file changed, 22 insertions(+), 20 deletions(-)

diff --git a/include/llvm/IR/Value.h b/include/llvm/IR/Value.h
index 17a80c82d1b..9d83cef76f7 100644
--- a/include/llvm/IR/Value.h
+++ b/include/llvm/IR/Value.h
@@ -493,7 +493,28 @@ private:
   template <class Compare>
   static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
     Use *Merged;
-    mergeUseListsImpl(L, R, &Merged, Cmp);
+    Use **Next = &Merged;
+
+    for (;;) {
+      if (!L) {
+        *Next = R;
+        break;
+      }
+      if (!R) {
+        *Next = L;
+        break;
+      }
+      if (Cmp(*R, *L)) {
+        *Next = R;
+        Next = &R->Next;
+        R = R->Next;
+      } else {
+        *Next = L;
+        Next = &L->Next;
+        L = L->Next;
+      }
+    }
+
     return Merged;
   }
 
@@ -586,25 +607,6 @@ template <class Compare> void Value::sortUseList(Compare Cmp) {
   }
 }
 
-template <class Compare>
-void Value::mergeUseListsImpl(Use *L, Use *R, Use **Next, Compare Cmp) {
-  if (!L) {
-    *Next = R;
-    return;
-  }
-  if (!R) {
-    *Next = L;
-    return;
-  }
-  if (Cmp(*R, *L)) {
-    *Next = R;
-    mergeUseListsImpl(L, R->Next, &R->Next, Cmp);
-    return;
-  }
-  *Next = L;
-  mergeUseListsImpl(L->Next, R, &L->Next, Cmp);
-}
-
 // isa - Provide some specializations of isa so that we don't have to include
 // the subtype header files to test to see if the value is a subclass...
 //
-- 
2.34.1