2 ms·

IMO SSA is not useful for bytecode formats; it is rather for doing optimizations in a compiler. When designing Wasm, several team members work working on PNaCl

by titzer 3y ago

IMO SSA is not useful for bytecode formats; it is rather for doing optimizations in a compiler. When designing Wasm, several team members work working on PNaCl (LLVM bitcode) and others were working on Web VMs. The fact that SSA requires deconstruction would have made baseline compilation and interpretation more complex and we gravitated towards a stack machine without SSA. Don't underestimate how much extra startup time it adds to do even one pass over the code. For really big applications (think 100MB or more of code), you want to avoid touching the code at all. You certainly don't want to compile anything that executes just once.

JonChesterfield 3y ago
SSA doesn't require deconstruction. Keep it all the way to the machine code. When bytecode is designed for ease of interpretation you get a compact form which is easy to interpret. When you're going to translate it to machine code before it runs, that benefit is much reduced. Stack vs register machine might be a preference. I find forth very difficult to reason with and don't particularly mind allocating registers to machine stack slots. I like the idea of interpreting code directly as one walks the ascii file. What example do you have in mind? Most "interpreters" I can think of do a compilation to bytecode and then feed that to a bytecode interpreter. Some walk an AST instead but I'm not aware of any which lazily instantiate that tree from the source code.
- titzer 3y ago
  > SSA doesn't require deconstruction. Keep it all the way to the machine code. At some point you need to insert moves, either before or after register allocation. If you do it after register allocation (i.e. regalloc on SSA form), then there are certain benefits to the regalloc algorithm (a slew of papers from 2005-2015 or so), but there are missed opportunities to reschedule the moves. It's possible to directly interpret SSA form. I am doing that now in my Virgil compiler. But I don't think it's good for a bytecode, because that forces producers to do the transform and requires more locals (because you can only assign to them once). > interpreting code directly as one walks the ascii file. I'm mostly thinking of binary code, e.g. Wasm. I wrote two of the papers referenced in the article.

by titzer 3y ago

JonChesterfield 3y ago

SSA doesn't require deconstruction. Keep it all the way to the machine code. When bytecode is designed for ease of interpretation you get a compact form which is easy to interpret. When you're going to translate it to machine code before it runs, that benefit is much reduced. Stack vs register machine might be a preference. I find forth very difficult to reason with and don't particularly mind allocating registers to machine stack slots. I like the idea of interpreting code directly as one walks the ascii file. What example do you have in mind? Most "interpreters" I can think of do a compilation to bytecode and then feed that to a bytecode interpreter. Some walk an AST instead but I'm not aware of any which lazily instantiate that tree from the source code.

titzer 3y ago
> SSA doesn't require deconstruction. Keep it all the way to the machine code. At some point you need to insert moves, either before or after register allocation. If you do it after register allocation (i.e. regalloc on SSA form), then there are certain benefits to the regalloc algorithm (a slew of papers from 2005-2015 or so), but there are missed opportunities to reschedule the moves. It's possible to directly interpret SSA form. I am doing that now in my Virgil compiler. But I don't think it's good for a bytecode, because that forces producers to do the transform and requires more locals (because you can only assign to them once). > interpreting code directly as one walks the ascii file. I'm mostly thinking of binary code, e.g. Wasm. I wrote two of the papers referenced in the article.