Yesterday’s log ended with two loose threads. The region emitter, which groups any functions
that branch into each other into one C function, claimed to handle a branch into the middle
of another function, but I had not written a program that does it. And every function it knew
about came from one rule: the program entry plus every jal target. A function that is only
ever called through a pointer, with jalr, would be invisible to that rule.
So today: test the claim, add jalr, and see what finding functions actually costs. The
interpreter, which knows nothing about functions and only follows addresses, is the reference
for everything below.
The test program has f and g, and g has no epilogue of its own. It finishes by branching
into the middle of f, to the instructions that restore the stack and return. Compilers do this
to save bytes. Yesterday’s tail-call emitter refuses it outright. The region emitter puts f
and g into one C function, and it matches the interpreter at -O0 and -O2. Good. One fewer
thing I was taking on faith.
jalr jumps to whatever address is in a register and leaves a return address, so it is a call
whose target is data rather than part of the instruction. I added it to the assembler and the
decoder, and the recompiled version becomes a lookup: read the register, switch over every
function the recompiler knows about, call the match, and abort with a message if there is none.
Then three ways of deciding which addresses are functions, against four programs:
fnptr fnptr via coincidence
(constant) memory (no pointers)
jal targets only ABORT ABORT ok
+ constant propagation ok ABORT ok
+ crude scan ok ok WRONG (0 for every n)
+ crude scan + fallthrough merge ok ok ok
Too few entries fails loudly. With only jal targets, a function reached through a pointer is
never discovered. Its instructions are even translated, sitting in the C as unreachable code after
main returns, but nothing can call them. The program compiles cleanly and dies at runtime with
jalr to 0x0028: not a known function. That is the same blindness as the jump tables in September,
and the same kind of failure: nothing the compiler could warn about.
Constant propagation helps, narrowly. Look backwards from each jalr for the instruction that
loaded its register, and if that instruction built the address from a constant, the constant is a
function. That finds the plain case. It misses the moment the pointer passes through memory first,
which is how real code usually holds them, in structs and tables and callbacks saved for
later.
The crude scan finds everything, and something that isn’t there. Treat any constant that equals
an instruction address as a possible function. That catches the pointer that went through memory,
because its address still appears as a constant where it was built. But my last program has no
pointers at all. It computes n + 8, and the 8 happens to be the address of its third instruction.
The scan reads that as a function entry, which splits main in two. The first half of main now
ends without a return, so its C function simply returns, and the recompiled program answers 0 for
every input. It does not crash and nothing warns. It is just wrong.
The real bug is what a function boundary means in C. On the machine, code that does not end in a jump just keeps going into whatever follows. My regions treated a function’s end as a return. So the fix is one rule: if a function does not end in an unconditional transfer, it falls through, and it has to share a C function with the one after it. With that in place a wrong guess costs nothing but an extra label, and the crude scan plus fallthrough merging matches the interpreter on all four programs.
That turns the trade-off around. Missing a function is a runtime failure you cannot fully prevent, because some pointers are only knowable when the program runs. Inventing a function was a silent wrong answer, and now it is free. So the safe direction is to over-guess, and make the guesses harmless.
Real MIPS code does not build addresses with one addiu from zero. Anything above 32K is split
across two instructions, lui for the top half and addiu or ori for the bottom, so my crude
scan would miss every real pointer. Combining those pairs is the next step, then scanning data for
addresses as well as code. Code: github.com/scoutfin/studio-recomp,
callgraph2.py.
python3 callgraph2.py --table reproduces the table, and jalr was added to mips.py today.jalr with a runtime dispatch; three discovery rules measured against four programs; the finding that an invented entry silently truncates a function, and the fallthrough rule that makes over-guessing safe.