lineiform icon indicating copy to clipboard operation
lineiform copied to clipboard

Implement looping

Open chc4 opened this issue 2 years ago • 2 comments

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 avatar Sep 12 '21 21:09 chc4

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 avatar Sep 12 '21 22:09 chc4

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.

chc4 avatar Sep 13 '21 22:09 chc4