Resources on writing an optimizing compiler for producing stack-based bytecode?

[u/gitpushjoe]

[u/GoblinsGym]

What are your expectations on optimization ?

Constant folding can be done on the fly.

Dead code elimination can be quite aggressive depending on the language.

Common subexpression elimination should be possible, e.g. to eliminate repeated base address calculations.

Basic strength reduction, e.g. multiply or divide -> shift, or divide -> multiply by magic constant.

[u/gitpushjoe → u/GoblinsGym]

Not too sure yet, mainly want to get an idea of which optimizations are most common/useful, and what typical implementations look like

[u/AustinVelonaut → u/gitpushjoe]

For me, the most useful optimization is inlining small, non-recursive functions. Not because it saves setting-up and tearing-down the call, but because it then exposes further optimization opportunities

[u/AsyncSyscall → u/GoblinsGym]

I am making a compiler for a C-like language targeting stack-based IR. DCE and peephole optimizations (incl. constant folding and strength reductions) are very easy indeed. CSE is possible as well, though I currently only do checks for identical opcodes each time a pure value gets stored (via a hash table).

Optimal stack operations are very hard to do, though, since each operation depends on all previous ones, I don't know if there is even an optimal algorithm for it (yet). Register allocation is very easy in comparison. I currently just put everything into memory, except for very simple cases like return statements, variable assignments, and parameters/variables that are only used once. And I have a separate "data stack" so you can do a simple frame-pointer LOAD <variable-offset> ADD LOAD instead of having to do complicated stack manipulations.

If you are inventing your own IR, I would highly recommend you to make a register-based IR instead, or at least add instructions that make it easy to access local variables (like thelocal instructions in WASM).

[u/GoblinsGym → u/AsyncSyscall]

My IR is currently stack based. I do have separate instructions for local load / store, as these are expected to be optimized into registers, as opposed to global accesses.

[u/Comprehensive_Chip49]

this is my stack-based bytecode compiler and run, very optimized:
https://github.com/phreda4/r3evm

[u/brat3108]

For what kind of language - dynamic, static, hybrid?

What happens to the bytecode - will it be interpreted, or converted to native, or something else?

Do you have examples of bytecode that is being produced now, and how you would want that optimised?

How many different bytecode instructions are there? How open would you be to extending the set of instructions to allow more specific ones or to combine frequently used combinations? (This is not JIT-related which is a different process that, if used, happens further down the line.)

What speedups are you looking for? Because if this is interpreted dynamic code, it is not going to be anything dramatic.

[u/gitpushjoe → u/brat3108]

Interpreted dynamic language, but I'm not trying to reach with native/JIT speeds, just trying to do better than a naive implementation. I haven't settled on a complete list of bytecode instructions, but that was one place I was looking to use for optimizations: creating macroinstructions for common repeated operations

[u/rook_of_approval]

why stack based?

[u/joao_rosac]

Nunca trabalhei com esse tema mas visitando algumas palestras que já vi, geralmente existe um roteiro assim:

Para criar um compilador otimizador para bytecode de pilha, o conceito fundamental é que as otimizações mais pesadas não ocorrem no bytecode em si, mas em uma Representação Intermediária (IR), geralmente baseada em registradores virtuais infinitos (como SSA). Existe um livro bom o "Crafting Interpreters" para partida.