lineiform icon indicating copy to clipboard operation
lineiform copied to clipboard

Merge flow control back together after a branch

Open chc4 opened this issue 2 years ago • 2 comments

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:

  1. 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...)
  2. 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 as false, they're both laid out in assembly before the fallthrough 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.

chc4 avatar Sep 12 '21 21:09 chc4

Ok I think the correct answer is to stop being dumb and just build a CFG for functions. Doing a single pre-process pass before JIT compilation realistically isn't going to be very slow, and gives us good and useful information, like for example having a "complexity" metric to feed into #15. The basic block layout heuristic would also fall on its face if we ever tried to inline a JIT compiled function, since Cranelift is dumb and doesn't know that you should put cold code outside the instruction fetch pipeline.

chc4 avatar Sep 14 '21 01:09 chc4

(If we want to be even smarter we could do the CFG pass async, and only block on it the first time we hit a branch)

chc4 avatar Sep 14 '21 01:09 chc4