It is interesting to see that this approach has been used by Niklaus Wirth in most of his compilers, see "Compiler Construction - The Art of Niklaus Wirth" by Hanspeter Mössenböck [0].
This technique was also described by David R. Hanson in "Code Improvement via Lazy Evaluation", 1980 [1] and "Simple Code Optimizations", 1983 [2].<p>[0] <a href="https://github.com/lboasso/oberonc/blob/master/doc/Moe00b.pdf">https://github.com/lboasso/oberonc/blob/master/doc/Moe00b.pd...</a><p>[1] <a href="http://storage.webhop.net/documents/lazyevaluation.pdf" rel="nofollow noreferrer">http://storage.webhop.net/documents/lazyevaluation.pdf</a><p>[2] <a href="http://storage.webhop.net/documents/simpleopt.pdf" rel="nofollow noreferrer">http://storage.webhop.net/documents/simpleopt.pdf</a>
> Nothing too fancy. No control-flow. No function calls. No data structures.<p>If that's the problem statement, then you may as well perform register allocation: all you need is Sethi–Ullman's algorithm [0][1], and it's quite simple.<p>Register allocation only becomes complicated when the control flow comes into the picture, especially the loops. Even then, there are some more or less obvious ways to do it, if you don't want to do graph colouring after Chaitin et al. (remember, people had to write register allocators before Chaitin's publication in 1981). For instance, you can do what the very first FORTRAN compiler did: you look at registerts as a cache for memory, in which case the Bélády's algorithm can be used for spilling. And with loops over arrays you can leverage the knowledge that you're looping over arrays quite nicely [2].<p>[0] <a href="https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm</a><p>[1] <a href="https://dl.acm.org/doi/pdf/10.1145/321607.321620" rel="nofollow noreferrer">https://dl.acm.org/doi/pdf/10.1145/321607.321620</a><p>[2] <a href="https://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf" rel="nofollow noreferrer">https://archive.computerhistory.org/resources/text/Fortran/1...</a>