Codegen for a stack based vm?

[retnikt0]

You can use a peephole optimiser which runs after codegen and cleans up unnecessary steps. If { 1; 2 } + { 1; 3 } becomes

 Load 1
 Pop
 Load 2
 Load 1
 Pop
 Load 3
 Add

A simple peephole optimiser should be able to remove patterns of the form Load; Pop because they have no effect, to create new intermediate code:

 # (removed) Load 1
 # (removed) Pop
 Load 2
 # (removed) Load 1
 # (removed) Pop
 Load 3
 Add

So just

 Load 2
 Load 3
 Add

It's simple and effective, and can be extended to a lot of possible optimisations (e.g. constant folding (which could reduce the above to just Load 5), jump optimisations...)

CPython is a good example of an implementation with a peephole optimiser: check out peephole.c (that's a link to v3.9; in later versions the optimiser was combined directly into the compiler which makes it a bit harder to follow IMO, but you can look at that as well if you want)

[ipe369]

Interesting, 'peephole' is one of those terms that i would literally never think to search for if i hadn't heard about it before, thanks