"Regardless, the whole point of the greedy allocator is to throw out the fancy list of active intervals that linear scan maintains in favor of doing something simpler that allows more flexibility in spilling/splitting, right?"

Kinda. It's not that simple, either :)

Linear scan is actually just bad all around, IMHO. It's meant for JITs that want to value speed above all else. At the time, I expect Chris was hopeful better spilling algorithms would take care of the fact that Linear Scan sucks.

It's not effective at solving the coloring problem quickly and accurately either :). It's kinda a worst-of-both worlds algorithms

Greedy is closer to what other compilers do: optimistic coloring, splitting if necessary, then remat/spilling.

So it's more accurate to say "LLVM made a bad choice in linear scan. They later fixed that mistake". I"m not away of any other high performance compiler that went down the linear scan path ever, because they didn't think it would work out.

Huh, I was under the impression that linear scan was more well-regarded than it is, then. I guess I hang around JIT folks and LLVM hackers too much. :)

So, there are three main papers on linear scan: Poletto and Sarkar, Traub, Holloway, and Smith, and nowadays, wimmer and franz

Sarkar and Poletto invented it for JITs. They were comparing it against literal chaitin-briggs style graph coloring (this was IBM, and IBM obviously did it that way, since IBM invented it).

The implementation they compared against was not particularly efficient (it happened at a time when I was at IBM research, so i've seen the code).

That said, linear scan made sense for a JIT at that time.

Compared to standard graph coloring algorithms of the time, you got somewhere between 10-30% crappier code, but the algorithm was a lot faster.

(There are papers that seemed to cherry pick linear scan result data to show better results. However, the consensus for implementers was it generated significantly worse code, and that was the tradeoff for faster).

Around this time, everyone started redoing everything in SSA, and noticed some things. Among them, that register allocation on SSA seemed easier.

It took until ~2005, but Sebastian Hack and Bouchez, et al then both independently proved that SSA generates chordal interference graphs, which means you can calculate the number of colors it requires (and color them) in polynomial time.

As an aside, interestingly, outside of special case graphs, you can't even estimate the chromatic number (min number of colors needed) of a graph sanely. The chromatic number is greater than or equal to the clique number, and even that can't be approximated sanely.

See, e.g, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.9...

So this is why so many people were so interested in finding alternatives to graph coloring.

But then it turns out, we can graph color really quickly on SSA.

(Then you still have "out-of-ssa related problems, but ...)

Once that was proven, by 2007/2008, the world had changed.

People were designing brand new SSA based allocators. An intern of mine at the time was working on implementing alternatives, and came up with: http://www.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf

Here's an abstract:

  For SPEC CPU2000, the compilation time of our implementation
  is as fast as that of the extended version of linear scan
  used by LLVM. Our implementation produces x86 code that is 
  of similar quality to the code produced by the slower, 
  state-of-the-art iterated register coalescing of George and 
  Appel with the extensions proposed by Smith, Ramsey, and    
  Holloway in 2004."

As you can see, at that point, there is no point in linear scan :)

As an aside, he also proved optimal live-range-splitting generates elementary graphs, which give you nice properties like being able to color using register pairs and under various alignment constraints, in linear time. (this would still be NP-complete on chordal graphs)

Since then, things have gotten better and better.

Quentin Colombet's(who wrote the current register allocator in LLVM) thesis is a good read for current techniques in spilling: https://tel.archives-ouvertes.fr/tel-00764405v1/document

Another interesting data point is libFirm: http://pp.ipd.kit.edu/firm/ which regalloc's directly over SSA.

Yes, it uses either chordal coloring (written by sebastian hack, who published one of the earlier mentioned graph coloring on SSA papers) or PBQP.

I'm pretty sure LLVM's PBQP implementation is more advanced.

What do you mean by more advanced?

The LLVM implementation is more mature from a software point of view, but libFirm's implementation supports more PBQP reductions, and thus may find a better PBQP solution.

Thank you for this, it was fascinating.

Sure.

If you want a good survey of the world of optimal register allocation/scheduling, someone just wrote one.

http://arxiv.org/pdf/1409.7628.pdf

It's pretty darn well written, and covers the world as it exists today.

The author later went to publish a nice thesis on optimal integrated RA + scheduling. https://www.sics.se/~rcas/publications/TRITA-ICT-ECS-AVH-14-...

The basic linear scan algorithm generates poor code, so you almost always want to extend it with additional heuristics. If any of these heuristics involve reversing a tentative decision then you have to rewind the state of the entire register allocator, because the linear scan algorithm is designed to process the function in one direction. This coarse-grained backtracking is fairly expensive. If you use a better algorithm that lets you consider tentative decisions on a more individual basis, then you scale better than linear scan with these extensions.

Because of the poor output code quality of the linear scan allocator (even with all of the additional heuristics), there was a post-pass that performed local optimizations. Over time it accumulated a lot of special cases to target particular poor code patterns, and it became more expensive than just using a register allocator that produced better code in the first place.