This is a follow up to Changes to Code on the evolution of my thinking with respect to Code[_].
One of the challenges we’re facing in the backend is handling JVM limits (e.g. on method bytecode size). The current wrapping logic mostly works, although it complicates the code, but more importantly, it is an issue that cuts across the entire code generator and new code generation (like ndarrays and emit streams) needs to engage with it but don’t.
Thus, we need to decouple method splitting from the code generator. My proposal is what I’m calling the low-level IR (lir). In this model, Code[_] will be a wrapper that will build lir.
- Classx (x to not conflict with the Java builtin Class)
- (basic) Block
- X (for eXpression): StmtX, ControlX, and ValueX.
A Classx is a set of methods and fields.
A Method is a set of locals and basic blocks, with a designated entry block.
A basic block is a list of StmtX. It is straight line code. The last statement in a block must be a ControlX (a switch, if, goto or return).
Non-control statements include loading and storing fields, locals and invocations that return void. Currently, function calls that return values and new instance are ValueX, although they might perform mutation. I think we can revisit that in the future and make them control that writes a local.
Note, the lir has no explicit representation of the JVM stack. ValueX can be nested, so
(add (sub ...) (neg ...) will be compiled to bytecode where the intermediates are put on the stack, but that isn’t visible at the lir level.
What’s more, the JVM stack is not used between basic blocks. This makes splitting at basic blocks simpler. It conflicts with joinpoint’s use of the stack and ParameterPack.push. Those both blocks for this moving forward.
Then plan is for Emit to not wrap, and then post-process the lir to satisfy JVM limits. I have a splitter underway that looks like:
- move all locals to fields, including inputs to control statements
- split large statements
- move body of basic blocks into separate a method(s)
Then each basic block turns into a function call and a control statement (if, branch, etc.) For this simple strategy to work, the control flow of the original method must fit into a single method. I’m not 100% sure that is the case. (@tpoterba?) This will let us simplify the exiting emitter code and give us a place to drop in a smarter splitter (e.g. that minimizes spilling to fields).
How does Code[_] change in this picture? My model of Code[T] is a computation and a value of type T that can be used after that computation is run. The value is represented by a ValueX. So Code looks like:
class Code[+T]( val start: lir.Block, val end: lir.Block, val v: lir.ValueX)
start is a block that represents the beginning of the computation (jump to start if you want to execute it).
end represents where the computation ends up (append things there if you want to do something after, possibly using
v is the value you can use after
There are two exceptional cases to consider: Code[Unit] and non-returning computations, e.g. what to do about
A Code[Unit] has
v = null since there is no value.
In this setup, you can’t write
Code(L.goto, ...) because a basic block must have one and exactly one control statement at the end.
I think we can represent non-returning computations with
Code[Nothing]. For a
end = v = null, since there is no end, nor a value. Then you can’t say
Code(L.goto, ...) but you can say
b.mux(s, t): Code[Nothing] where
b: Code[Boolean] and
s, t: Code[Nothing].
I look into peeling off the Nothing business in the current code. Until then, non-returning computations should be
Code[Unit] and we won’t statically check putting values after non-returning computations.
lir.X has a parent pointer, so values that are reused will immediately throw errors. For generating control instructions (which basically involves appending to a basic block), I’ll make
Code[_] consumers clear out the producer so they can’t be reused (e.g. move semantics).
I have a draft for most of this and I’ll aim for a PR beginning of next week.