Cranelift, Part 4: A New Register Allocator (opens in new tab)

Cranelift is a general-purpose compiler like LLVM is, but its goals are different: it is targeted toward applications like JITs where faster compilation is important. It is intended to be a peer of browser JITs' optimizing tiers. In our README [0] we link some results where we're ~14% slower than LLVM but with ~10x faster compilation.

We also have an explicit focus on correctness, simplicity, and verification. One could argue that in practice LLVM is used everywhere and has dozens of active core contributors, that bugs and missed optimizations are shallow at that scale, and it's hard to compete with that; and there is some merit in that... but our codebase is two orders of magnitude smaller, and we're actively engaging with academics and designing things -- our lowering DSL, our regalloc's symbolic verifier, our fuzzing-first approach -- to get the most mileage we can out of our efforts. It seems to be working OK so far!

[0] https://github.com/bytecodealliance/wasmtime/blob/main/crane...

No. First, most compilers actually abandon SSA by the time they begin register allocation through phi elimination, and once you do this you have given up that property. Beyond that, coloring a perfect graph (an SSA graph) can be done in quadratic time, but coloring is not the most interesting part of the process, since you almost always have to insert spills which modifies the interference graph. Register allocation is more than just coloring. On top of that, most ISAs have complications like specific registers needing to be pinned for specific operations, or register aliasing on x86-64, that make things hairier.

In practice, theoretical optimality matters far less than the actual heuristics you use (e.g. avoid spills inside of a loop.)

One can do optimal regalloc over SSA if one doesn't have to spill, or split to make the spilling better, but spilling and splitting are the most interesting and relevant part of practical register allocation -- so in practice this isn't quite true.

I'll doubt they'll find it to be a convincing argument, because it relies on a fairly uncharitable interpretation of the claim. Rather than interpreting it as "literally no well-written code needs comments" I would interpret it as "well-written code doing straightforward things (like most code is doing) doesn't need comments". Complex algorithms trying to quickly approximate a np-hard search problem in a complicated environment are a fairly obvious exception to the rule, even if you believe the rule is almost always applicable.

I'm also not sure when the last time I heard someone seriously make this claim was...

We all know that is just an excuse for no comments. I haven't heard anyone say that in over 5 years.