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

Implement looping #8

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

Implement looping #8

chc4 opened this issue Sep 12, 2021 · 2 comments

Comments

@chc4
Copy link
Owner

chc4 commented Sep 12, 2021

Similar to #7, but loop instead.

The problem with looping is we don't know where a loop starts until we hit jump to an instruction we have already marked in our Context.seen bitmap. Which means we always "unroll" one interation of a loop no matter what, and then seen the condition for looping and jump back to the beginning.

We can either

  1. build a CFG, and use that to collect all the entry points of a loop
  2. Unroll one execution, and stop advancing any paths that are backwards jumps when we are emitting. Then, once we have JIT compiled all non-loop paths we can, we have a set of entry points to loop and their entry contexts, and can union them all together to create symbolic values for the body of the loop, which we compile.

The context for the fallthrough branches of the loop then have a context where we clobber whatever values in the loop context are different between the start of the loop and the end, allowing us to slightly optimize through loops by giving us a set of registers/stack slots that are invariant the entire loop body.

The problem with option 2 is that we optimally want to recompile functions multiple times in the final version of Lineiform, and if we're unrolling one loop iteration each time it's Bad. We can probably just keep around function compilation metadata after we JIT, and feed it into the JIT of any consumers of the function so that it knows a loop starts at X without having to unroll it once and find back edges though? In the CFG building case we'd probably want to keep that metadata around too so we don't have to re-build a CFG from our JIT output, so I'm not sure if it's any faster or not.

@chc4
Copy link
Owner Author

chc4 commented Sep 12, 2021

Once we have this I'd like to do a bunch of cool optimizations like loop invariant code motion and intelligent loop unrolling. They're probably really hard to implement without a CFG or DFG, though, which is a Future Chc4 problem.

@chc4
Copy link
Owner Author

chc4 commented Sep 13, 2021

Instead of doing 1 or 2, we do technically have a third option: do an initial "slow" instrumented execution of the function while collecting trace information, and do lazy basic block version lite where we only compile the path we have branch information from (with adding new branches if the JIT tries to run them).

This is how redmagic works, along with any tracing JIT (including Graal and RPython and Higgs and LuaJIT and...). I don't really want to do it since Lineiform is mostly geared towards a method based JIT instead of a tracing JIT for now, collecting trace information is kinda hard (you either need to single step emulation of instructions, using something like https://github.com/lifting-bits/microx or Unicorn, or Intel PT which is processor specific), and the lazy part of LBBV means you have to call back into and continue JITing from potentially any 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