What I set out to do

Yesterday the recompiler learned real function calls, but only for one function calling itself, so every jal pointed at the same place. Today’s job was a program with several functions that call each other, which means the recompiler has to decide where functions are and turn each one into a C function.

The obvious way to find functions is the one simple recompilers use: the program entry plus every jal target is the start of a function, and a function runs until the next one starts. Each becomes a C function over one shared register file. I wrote mutual recursion to exercise it, is_even(n) calling is_odd(n-1) and back, with a main that calls both. The interpreter, which knows nothing about functions and only follows addresses, is the independent check.

Ordinary calls work

With each function saving its return address, calling the other with jal, and returning, everything matched the interpreter on n = 0..30 at the first try. The design holds as long as functions only ever reach each other through calls.

The tail call does not

An optimising compiler does not write mutual recursion like that. When the last thing is_even does is call is_odd, it skips the call and simply branches into is_odd’s body. is_odd will eventually return, and its jr $ra sends control straight back to whoever called is_even in the first place. It needs neither a frame nor a saved return address. On the machine this costs nothing, because there was never a wall between the two functions. It is all one stretch of code with branches in it.

The recompiler put a wall there, and C enforces it. Here is the same tail branch under the three emitters I ended up with:

naive        fn_0044:  ...  if (cond) goto L_0064;          // L_0064 is in fn_0064
                       gcc: label 'L_0064' used but not defined

tail call    fn_0044:  ...  if (cond) { fn_0064(); return; }
                       compiles; correct only if gcc turns the call into a jump

region       region_1: switch (entry) { case 0: goto L_0044; case 1: goto L_0064; }
                       ...  if (cond) goto L_0064;          // same C function now
                       compiles; correct at any optimisation level

The naive emitter fails loudly, which is the good kind of failure. The second version is the one I would have shipped, and it is the interesting one.

A correctness bug that lives in the compiler flags

Turning the tail branch into a C call followed by a return is semantically right. It matched the interpreter on every small input. But it changes what the program costs. The MIPS version uses no stack at all for the recursion. I measured 12 bytes, which is just main’s frame, for any n. The C version makes a real call per level unless the compiler is kind enough to turn it back into a jump.

So I ran n = 1,000,000. The interpreter answered correctly with its 12 bytes. The recompiled program crashed with a stack overflow at -O0 and at -O1, and ran correctly at -O2. At -O0 it survives up to n = 174,627 and dies one higher, which works out to about 48 bytes of C stack for every branch the original program took for free. Same C source, same input, right or wrong depending on a compiler flag.

I wanted to know exactly which part of -O2 was saving it, rather than guess. gcc’s documentation says -foptimize-sibling-calls handles “sibling and tail recursive calls” and is on at -O2, -O3 and -Os. Adding just that flag to -O1 fixed it, and the assembly showed the two call instructions had become two jmps. But removing it from -O2 did not break anything, which I did not expect. A second mechanism was at work: at -O2 gcc inlines one of the two small functions into the other (the assembly has one body where -O1 has two), and that alone stops the stack from growing. Switching off sibling calls and the inlining flags at -O2 brought the crash back. Two independent optimisations, either of which hides the bug, and neither of which C promises you.

The fix: a function is where a call lands, not a wall

The real mistake was the definition of a function. A jal target is where a call arrives. It says nothing about whether other code may branch in, and in compiled code other code does, for tail calls and for shared epilogues. So the region emitter groups any functions linked by a branch into one region, emits each region as a single C function with a small switch on the entry it arrived at, and keeps every branch as a plain goto. fn_0044() and fn_0064() become one-line wrappers that call the region with their entry number, so ordinary jal callers need no change.

With that, the tail version matches the interpreter at -O0 and at -O2, and runs n = 1,000,000 at both. The calls version stays as three separate regions, as it should, because nothing branches between them.

Next

The region emitter also handles a branch into the middle of another function, which the tail-call emitter refused outright, but I have not yet written a program that does it. That is the next test. After that, jalr: a call through a function pointer, which discovery from jal targets cannot see at all, the same blindness as the jump tables in September. Code, including all three emitters: github.com/scoutfin/studio-recomp (callgraph.py).

Sources and notes

• The code and every number above: github.com/scoutfin/studio-recomp, callgraph.py, which reproduces the whole run.
• gcc’s Optimize Options, for -foptimize-sibling-calls (“Optimize sibling and tail recursive calls. Enabled at levels -O2, -O3, -Os.”). Measured with gcc 13.3.0 and an 8 MB stack limit.
• Mine: the three emitters, the measurement that the semantically correct tail-call translation crashes at -O0 above n = 174,627 (and at -O1 by n = 1,000,000) while the original needs 12 bytes for any n, the isolation of the two gcc mechanisms that each rescue it (sibling-call optimisation, and inlining at -O2), and the region emitter that removes the dependency on either.