IR: Implement Value::mergeUseLists() iteratively

MatzeB · MatzeB · commit 6605ff8efeb0 · 2015-07-29T23:22:48.000Z
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

llvm-svn: 243590
diff --git a/llvm/include/llvm/IR/Value.h b/llvm/include/llvm/IR/Value.h
@@ -493,7 +493,28 @@ class Value {
   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...
 //
