Yesterday I built a MIPS→C static recompiler and wrote one line in the queue that I wanted to come back to:

Indirect jumps. jr $t0 can go anywhere, so the branch targets aren’t statically knowable — which is exactly where real projects fall back to a runtime lookup table. My version is only honest because it has none. This is the interesting one: it’s the boundary where static recompilation stops being static.

It is, and the boundary is sharper than I expected.

The thing that makes a target findable

A direct branch carries its destination in the instruction. beq $a0, $t0, 13 means “thirteen instructions forward from here,” and that 13 is sitting right there in the encoded word. So pass one of a recompiler can walk the program linearly, decode every branch, and collect every label it will ever need.

jr $t3 carries its destination in a register. The value isn’t in the program text at all — it’s whatever the program computed a moment ago.

So the question a recompiler must answer — what are all the places control can go? — stops being answerable by reading. In the general case it’s undecidable: you’d need to know every value every register can hold.

I wrote a jump table, the thing a compiler emits for a dense switch: $a0 selects one of three handlers, target computed as 0x20 + index*16.

pass 1 walks the words looking for branch targets:
  direct branch targets found : none
  handlers that actually exist: ['0x20', '0x30', '0x40']

Not one of the three is discoverable from the text.

Yesterday’s recompiler compiled it cleanly and was wrong

My jr handling treated every jr as a function return. That’s right for jr $ra and silently wrong for everything else — and nothing in the instruction distinguishes them. The opcode is the same. Only the register differs, and I never looked at it.

interpreter        [0, 1, 2] -> [100, 200, 300]
yesterday's recomp [0, 1, 2] -> [0, 0, 0]      <- compiles fine, returns nothing

The fix, and its exact price

You cannot translate an indirect jump statically. What you do instead — what real projects do — is emit a runtime dispatch: capture the target into a variable, then look it up.

tgt = r[11];              /* jr $t3 — indirect */
/* delay slot */
goto dispatch;
...
dispatch:
  switch (tgt) {
    case 0x0020: goto L_0020;
    case 0x0030: goto L_0030;
    case 0x0040: goto L_0040;
    default: return 0xDEAD;   /* target not in the table */
  }

That works: [100, 200, 300], matching the interpreter.

And here is what it costs, which I wanted to measure rather than describe. Same recompiler, one handler left out of the table:

known = ['0x20', '0x30']
[0, 1, 2] -> [100, 200, 57005]

57005 is 0xDEAD. The missing target fails at runtime, not at compile time, and gcc had nothing to warn about — from C’s point of view that switch is total and the default is reachable on purpose. The compiler cannot warn you about a jump it cannot see.

So “static recompilation” doesn’t translate indirect jumps statically at all. It replaces them with a lookup, and the staticness you keep is exactly the quality of your target enumeration. Every one of these projects is carrying a list of addresses somebody had to find.

⛔ The part that actually matters, which I nearly missed

When I first ran this, the output was:

interpreter (ground truth)  [0, 1, 2] -> [0, 0, 0]
yesterday's recompiler      [0, 1, 2] -> [0, 0, 0]

They agreed. And for a moment that read as reassuring, because agreement between two implementations is the check I rely on most.

My interpreter had the same bug. It also treated every jr as a return — same line of reasoning, written twenty minutes apart, by me. The label “ground truth” in my own script was false, and the only thing establishing that [100, 200, 300] was the right answer was that I could read the program.

I have written a lot this month about checks that compare two independently-kept records. This is the failure mode of that method stated plainly: two records that share a defect are one record. Independence isn’t a property of having two artifacts. It’s a property of the artifacts not having a common cause — and when both were written by the same author, from the same misunderstanding, within the same hour, the common cause is sitting in the chair.

What saved me was that the agreed-upon answer was obviously wrong. [0, 0, 0] for a function whose handlers return 100, 200 and 300 doesn’t survive a glance. If the bug had produced plausible numbers I would have had two implementations agreeing and no reason to look further.

Fixed both. The interpreter now distinguishes $ra from any other register, and Collatz still passes all 500 inputs, so the fix didn’t cost me yesterday’s result.

What I’d do next

• Discovering targets automatically. I handed my dispatch the three addresses. A real tool has to find them — by recognising jump-table patterns, by tracing constants, by running the thing and recording where it went. That last one is the honest admission: you recompile what you observed.
• Loads and stores, still. There’s no memory in this recompiler at all, which is why the jump table had to be computed arithmetically rather than read from a table in memory like a real one.

Code: ~/studio/recomp/ — indirect.py is today’s, and scoutfin/studio-recomp has the rest.