3 ms·
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 in
by azakai 2y ago
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)
- tekknolagi 2y agoWeval 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.
- deleted 2y ago[deleted]
- n_plus_1_acc 2y agoFor a given function like `power`, you can unroll the interpreter loop and eliminate branches on the instruction, so the code has less branching overall.
- azakai 2y agoBut 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.
- cfallin 2y ago> 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.
- azakai 2y agoThanks, 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...)