Comment by azakai | Hacker News Reader

Comment by azakai | Hacker News Reader

Parent Full thread

I understand that by making the bytecode constant a lot of optimization become possible. But I can't see how you can unroll the interpreter loop past unknown inputs to the program?

That is, if the program is a pure function like power(x, y) (from the top of the article) then I understand if the bytecode is constant and the inputs x, y are constant then you can unroll completely. In fact, in that case, you can just do a full evaluation of the entire program to a constant. But, if x and y are unknown at compile time then you can do very little, I think?

I guess the example at the top of the article is saying that if you know y but not x then partial evaluation can still help a lot. But in a real-world program the first unknown input that causes a significant branch in execution will block progress, won't it? (edit: in particular unrolling has to stop, unless you consider multiple paths)

Weval has intrinsics that unroll the loop and specialize on the PC, merging paths with the same PC. So if you pick a good specialization context like PC, the unrolling stops eventually.

For a given function like `power`, you can unroll the interpreter loop and eliminate branches on the instruction, so the code has less branching overall.

But can you only do that when you know what the inputs are? That is, if x and y are determined only at runtime for power(x, y) then I don't see what can be optimized. But that seems like the common case to me. Likely I'm missing something and maybe not asking the question clearly, sorry.

> That is, if x and y are determined only at runtime for power(x, y) then I don't see what can be optimized.

Yes, the example in Max's post is specifically assuming one wants to generate a specialized version of `power` where `y` is fixed.

To take it back to weval: we can know what the bytecode input to the interpreter is; we provide an intrinsic (part of the "wevaling" request) to indicate that some function argument is a pointer to memory with constant, guaranteed-not-to-change content. That, together with context specialization on PC (another intrinsic), allows us to unroll the interpreter loop and branch-fold it so we get the equivalent of a template method compiler that reconstitutes the CFG embedded in the bytecode.

Thanks, I think I see now. So `y` is the bytecode, in the analogy. Makes sense.

(For me at least a concrete example would have helped, something like showing the specialized output of running on the bytecode for `power` with that interpreter. But maybe that would be too verbose...)

Reply on news.ycombinator.com