Description
Currently we're a zero-pass JIT compiler: we just JIT operations as we see instructions, without any initial pass over the function. This is nice because it gives us nice performance (probably), and because any CFG when we're aggressively inlining with partial application is going to have to be updated as we elide branches and inline functions.
Unfortunately, it also means that we don't have any CFG info as we JIT a function. Which means if we have above if cond { true } else { false } fallthrough
, what we do is just split the execution into two paths above -> true -> fallthrough
and above -> false -> fallthrough
. This is fine for simple branches, and means we have full partial application for either version of fallthrough
, but means we have n^2 paths through a function for n branches, which is hilariously bad.
We'd instead like to be able to turn it into above -> [true, false] -> fallthrough
, where fallthrough has an intersection of the symbolic state from the result of true and false. The fact we don't have a CFG means we don't know if a control flow path merges back again though! And in practice either side of a branch aren't the same number of basic blocks, so we can't just advance the JIT for either side of a branch equally and just check if their jump targets are the same.
There's two options:
- give up on being a zero-pass compiler, and do an initial CFG building pass to find where to merge branches back together (which also would help us when doing loop compilation...)
- just use some heuristic and miss some merges - we could instead try to advance whichever side of a branch is at the lowest instruction offset into the function at each step, on the basis that even if the
true
path is a different length asfalse
, they're both laid out in assembly before thefallthrough
branch. This is easier, and maybe faster, but means that we would miss branches that jump to some basic block at the end of a function and back up again. Maybe that's good, because those are mostly "cold" branches, and compiling both side of a cold branch gives us better partial application info on the hot path since we wouldn't have to throw away information in the state unioning to include unlikely path behavior.