Implement optimizations

[avborup]

Currently, the compiler emits entirely unoptimized bytecode. There are tons of optimizations that could be applied.

Tip

If you're reading this and want to contribute, I think good ones to start out with below would be "useless addition," "reuse buffers," and "compile-time evaluation of constant expressions". Or maybe just set up some way to run a profiler to gain some insight on what the worst offender is. :)

Off the top of my head:

• Useless addition: [n, 0, add] should just be [n]
  • This happens often in cases like [get_bp, 0, add, load/store].
  • I have (unintentionally) optimised global variables since their address is constant at the beginning of the stack, meaning no additions have to be performed at all.
• Loop cleanup instructions. For example [swap, pop, swap, pop], which could be done much more efficiently in Rust-land rather than having to decode and execute 4 separate instructions.
• Reuse buffers
  • I doubt this is a bottleneck at the moment, but it would be beneficial to reuse buffers in the VM rather than constantly allocate new Vecs. One example is when multiple arguments are loaded from the stack, they're collected into a vector. But this vector is a one-off that will be discarded after the instruction is done executing. Instead, have a buffer in the VM that is reused every time (meaning only allocated once).
• Specialised type instructions. Currently, all types on the stack are arbitrary "runtime values". But it's possible (quite often) to analyse the input program statically and determine the type of most values, variables, and functions.
  • There could be
• Statements versus expressions
  • Currently everything is an expression, meaning everything leaves a value on the stack. For a sequence of expressions, that causes each expression to leave a value on the stack that is immediately popped again. An optimisation could be to analyse the program statically to see which expressions act as statements, and provide instructions for those that do not leave values on the stack. But I'm assuming this will lead to pretty extreme bloat of instructions.
• Compile-time evaluation of constant expressions.
  • Something like a hardcoded list [1, 2, 3] takes O(n) instructions on runtime to evaluate. Instead, we could make a static analyzer that just constructs the value at compile-time. There are two levels to this approach:
    1. Just evaluate literals. Easy peasy, just check if everything within the expression is a Value
    2. For each expression in the AST (bottom-up), attempt to evaluate any constant subtree expression. This would require implementing an interpreter (easy), allowing code execution at compile-time.
• The extremely spicy one: add an LLVM-based JIT compiler. This probably requires stupendous effort.
• And many more...

But of course, please use profiling to discover the worst bottlenecks. I saw there's something called Callgrind from Valgrind, which seems super cool - and there's a Rust crate for it.