This is an archive of the discontinued LLVM Phabricator instance.

Rewrite tail recursion as loop

Authored by jrkoenig on Aug 3 2015, 1:14 PM.



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.

Diff Detail


Event Timeline

jrkoenig retitled this revision from to Rewrite tail recursion as loop.
jrkoenig updated this object.
jrkoenig added reviewers: jfb, nlewycky.
jrkoenig set the repository for this revision to rL LLVM.
jfb accepted this revision.Aug 3 2015, 1:36 PM
jfb edited edge metadata.

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

This revision is now accepted and ready to land.Aug 3 2015, 1:36 PM
nlewycky accepted this revision.Aug 3 2015, 2:16 PM
nlewycky edited edge metadata.
jfb closed this revision.Aug 3 2015, 2:35 PM