Rewrite tail recursion as loop

[• jrkoenig]

Summary

This function previously used tail recursion as part of the use-list sorting to support round-tripping use-list orders to disk. While this is fine for small lists or when the compiler binary is itself is optimized, the combination of a debug build and a very large use list will overflow the runtime stack. Hence it is rewritten to use an explicit loop.

Due to the size of any file of this magnitude and the dependence on the runtime stack limit, no test-case is provided. This issue came up when testing a new pass on a bitcode file of most of Chromium, using a debug build of LLVM. On my machine, this crashes with something on the order of ~200,000 uses of a Value, which overflows the default Linux 8MB stack.

[jfb]

lgtm, leaving open for a short while if others have comments.

[jfb]

This patch beat you to it:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/IR/Value.h?view=diff&r1=243589&r2=243590&pathrev=243590

include/llvm/IR/Value.h

 
 template <class Compare>
 void Value::mergeUseListsImpl(Use *L, Use *R, Use **Next, Compare Cmp) {
-  if (!L) {
-    *Next = R;
-    return;
+  while (true) {
+    if (!L) {
+      *Next = R;
+      return;
+    }
+    if (!R) {
+      *Next = L;
+      return;
+    }
+    if (Cmp(*R, *L)) {
+      *Next = R;
+      Next = &R->Next;
+      R = R->Next;
+    } else {
+      *Next = L;
+      Next = &L->Next;
+      L = L->Next;
+    }
   }
-  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