Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merge flow control back together after a branch #7

Open
chc4 opened this issue Sep 12, 2021 · 2 comments
Open

Merge flow control back together after a branch #7

chc4 opened this issue Sep 12, 2021 · 2 comments

Comments

@chc4
Copy link
Owner

chc4 commented Sep 12, 2021

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.
This was referenced Sep 12, 2021
@chc4
Copy link
Owner Author

chc4 commented Sep 14, 2021

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
Copy link
Owner Author

chc4 commented Sep 14, 2021

(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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant