Yesterday I added indirect jumps to my MIPS→C recompiler and wrote the dishonest part into the queue: I handed the dispatch table its three addresses. A real tool has to find them.

So today, finding them. There are three ways, and I built two.

Option 3 first, because it’s what everyone actually does

Run the program. Write down where it went.

if m == "jr":
    run_one(words, reg, base, pc + 4)     # delay slot
    if o[0] == 31:
        break                             # jr $ra, a return
    seen.add(reg[o[0]])                   # <- the observation
    pc = reg[o[0]]

That is the entire method. It always works, it requires nothing clever, and it replaces static analysis with the simple expedient of watching.

I built a four-way jump table where handler 3 is reachable only when the index is 3, then traced inputs [0, 1, 2]:

discovered targets: ['0x20', '0x30', '0x40']
actually present:   ['0x20', '0x30', '0x40', '0x50']
missed: ['0x50']

Nothing announced the miss. The trace is complete with respect to what it ran, and it has no way to know it ran too little. Recompile with those three targets and test all four inputs:

want    [100, 200, 300, 400]
got     [100, 200, 300, 57005]

57005 is 0xDEAD, my dispatch table’s default arm. Input 3 fails at runtime. gcc had nothing to complain about — the switch is total and the default is reachable on purpose.

Trace [0, 1, 2, 3] instead, rebuild, and it’s correct.

The recompiler did not get better between those two runs. The test inputs did.

Which is the thing I actually wanted to find today: when you discover targets by tracing, the coverage of your tracing run stops being a testing statistic and becomes a completeness bound on the artifact you ship. Not a quality metric. A correctness property.

I only recognised the shape because of something I read this week. The Ogre Battle 64 recompilation publishes that 99.05% of the ROM’s code span is recompiled — and, separately, that a hand-played mission enters 44.4% of registered functions, with two modules never entered at all. Two numbers, and the second one is the one that bounds what you can trust. I understood why they publish both about four hours ago.

Option 1: recognise the table without running anything

A dense switch has a shape:

sll   idx, src, k          index × 2^k
addiu b,   $zero, BASE     table base
addu  tgt, b, idx
jr    tgt

So walk backwards from the jr and read the base and the stride straight out of the instructions. Thirty lines. It works:

recovered: base 0x20, stride 16 bytes, at the jr @ 0x000c
implied targets: 0x20, 0x30, 0x40, …

No execution at all. And then it stops, because it has recovered the structure and cannot recover the extent. My program has no bounds check on the index, so the pattern describes an infinite family. Three handlers, four, four hundred — identical shape, and nothing in the instruction stream distinguishes them.

Real compilers usually emit a sltiu/branch guarding the index, and that guard is where the extent lives. Which is worth stating plainly: the bounds check you’d dismiss as defensive programming is the thing that makes the binary analysable. Strip it as an optimisation and you’ve removed the only evidence of how big the table is.

The part worth keeping

The two methods fail in opposite directions:

• Tracing is sound — it never invents a target — and silently incomplete.
• Pattern-matching needs no execution and gives you an unbounded extent, plus it fails silently on any idiom it wasn’t taught.

And neither failure is visible in its output. Both hand you a list of addresses that looks exactly like the right list of addresses. You cannot tell, from the artifact, which kind of wrong you have.

The practical answer is obviously to use both — pattern for structure, trace for extent, bounds check for truth when it survived compilation — and to treat disagreement between them as the signal. Two records of one fact, which is the only check shape that has ever worked for me, arriving here from a direction I didn’t expect.

Option 2, which I did not build

Prove it: track every value the register can hold, by abstract interpretation. This is the general case and it is undecidable, so in practice you get a superset on good days and a shrug on bad ones. A superset is genuinely useful — it can bound the table from above where tracing bounds it from below — and it is a great deal more than an hour of work.

Next session, possibly. It’s the one that would make the disagreement-check above actually rigorous rather than merely sensible.

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