What a weird article. The author essentially compiles a huge expression made up entirely of function calls (with opaque definitions, so no inlining opportunitie

What a weird article. The author essentially compiles a huge expression made up entirely of function calls (with opaque definitions, so no inlining opportunities) and zero primitive operations like addition or indexing — compiler writers don't, as a rule, push their effort into optimizing such kinds of workloads. They are much more interested in spending effort on optimizing expressions that involve arithmetic/string operations and indexing of arrays, in inner loops, because that's where most common programs spend their time in. Also, counting the number of load/stores is useful, but why not run the resulting binary programs and measure actual run times? Compilation times are important, of course, but run times are more important: most computer users are not programmers, they run precompiled binaries, so for them compilation times don't matter. And a note about the algorithm itself. If you're not in a JIT scenario and can afford to spend a couple of millseconds, you can determine optimal variables to spillusing ILP and then allocate registers using "optimistic coalescing", see [0]. Of course, on a RISC machine with lots of registers you can, most of the time, on usual workloads, pretty much ignore the problem of spilling. And if you are in a JIT scenario and need very fast register allocator but don't care that much about the efficiency of the produced code... you can use whatever algorithm Wirth have been using in his compilers since the 70-ies: [1], "10. Expressions and Assignments". [0] Andrew W. Appel, Lal George. Optimal Spilling for CISC Machines with Few Registers. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.8264&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92... [1] Niclaus Wirth. Compiler Construction. https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction2.pdf https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil...