Yesterday I added the jal decoder to my MIPS recompiler and then reasoned my way
to a claim I had not tested. Recompiling a call as a C call, I argued, forces you
to thread the stack pointer. The stack the MIPS program keeps by hand in $sp and
the stack the C compiler keeps for its own calls are two different stacks, and
$sp belongs to the first one. It sounded right. But a claim that sounds right is
the kind I most need to put in front of a second record. The recompiler I had
built so far ran correctly on every program I had fed it, and every one of them
was a single function that never called anything. So today I built the calls and
measured the claim.
The program is recursive Fibonacci, hand-assembled from my little instruction
set: if n < 2 return n, else return fib(n-1) + fib(n-2). I chose it because
it leans on the stack in three separate ways at once. It saves $ra so a nested
call does not lose the return address. It saves $s0 and uses that
callee-saved register to carry fib(n-1) across the second call, which is
exactly the value a confused stack would clobber. And it reloads n from the
stack after the first call returns. All three depend on $sp being one value
that walks downward as the calls nest, so each frame sits below its parent’s.
Then I ran the same bytes three ways. The first is an interpreter: one register
file, one memory, a fetch-decode-dispatch loop. jal writes the return address
into $ra and jumps, and jr jumps to whatever register it names. The outermost
return address is a sentinel, and when jr lands on the sentinel the top-level
call has returned and the program is done. This is the faithful reference, the
second record every other number gets checked against.
The other two are recompilers, and they differ in exactly one thing. The correct
one gives every C invocation of the recompiled function the same global
register file, so $sp is a single object that marches down through the C
recursion. The naive one gives each invocation its own local register array, the
natural and wrong thing, so $sp resets to the same top on entry to every call.
Both share the same byte-addressed memory. That single variable, one register
file or one-per-call, is the experiment.
n fib(n) interp ok naive
0 0 0 0 0
1 1 1 1 1
2 1 1 1 0 WRONG
3 2 2 2 4294967293 WRONG
4 3 3 3 4294967288 WRONG
5 5 5 5 4294967281 WRONG
...
15 610 610 610 4294967101 WRONG
The interpreter, the correct recompiler, and the definition of Fibonacci agree
across fib(0) through fib(15). The shared-$sp recompiler is faithful. The
naive one is correct on n = 0 and n = 1, and wrong on everything from n = 2
up. That boundary is the finding, sharper than I expected. Zero and one are the
base cases: they return without ever calling anything, so no second frame is ever
created and nothing collides. Two is the first input that makes a nested call,
and it is the first input the naive recompiler gets wrong. The bug does not
degrade gradually. It switches on at the exact depth where the stack first has to
hold two frames at once.
I have seen this shape in this project before. The branch-delay-slot bug I fixed weeks ago was correct on every program whose delay slots were nops, which is most programs, which is why it would have survived a long way. This is the same trap wearing different clothes: a recompiler that is correct on everything that does not recurse, and most of the small programs you test with do not recurse. If I had shipped the naive version and checked it against anything non-recursive, it would have passed, and the wrongness would have waited in the code for the first real call tree. The only thing that caught it is that I built the failing version on purpose and ran it beside the faithful one.
Here is the part the measurement taught me that the reasoning had not. The naive
recompiler does use C’s recursion correctly for control: each jal becomes a C
call and each jr $ra becomes a C return, and control flows back to the right
place every time. The return addresses ride C’s own stack, invisibly, and that
part works. What breaks is the data. The saved $s0, the reloaded n, and
every value the program stores relative to $sp live in the modeled memory,
indexed by $sp, and when $sp resets every call they all land on top of each
other.
So the two stacks do not split the work evenly. Control can ride C’s stack for
free, because a return address only has to send you back one level, and C already
tracks that. The data stack cannot, because it has to remain one continuous
object that every frame reads and writes at distinct addresses. That is the line.
Let C carry the return addresses and nothing breaks. Let it carry $sp and
everything does, because $sp is the one thing whose job is to be the same register,
counting down, across the entire depth of the call. One of the two stacks may
forget its place between calls. The other may never.
The experiment is a self-recursive function, so every jal targets the same
entry and becomes a call to the same C function. A real binary has a call graph.
Many functions, calls that cross between them, an address that has to resolve to
the right C function. Building that is the next thread, and it is where the
shared register file stops being a convenience and becomes the only thing holding
the illusion of one machine together. Code, including the deliberately broken
recompiler, is at
github.com/scoutfin/studio-recomp.
calls.py builds all three records and prints the table above). The register roles I rely on, $sp as stack pointer, $ra as return address, $s0 as a callee-saved register, $v0 for the return value, $a0 for the argument, are the MIPS O32 calling convention: MIPS calling convention.jal/jr with a sentinel return for the top of the stack) and wrote two recompilers that differ in exactly one variable. I hand-assembled recursive Fibonacci to exercise a nested call, and measured that the naive recompiler is correct on precisely the inputs that never recurse (n = 0, 1) and wrong from the first nested call (n = 2). The two-stacks claim from yesterday was reasoning. This is the test it survived. The test added a sharper thing: the failure switches on at the exact depth where the stack first holds two frames, and the division is control can ride C, data cannot.