Hacker News Reader

I'm going to guess you have misunderstood what Chris said (with no offense meant) :)

Spilling is actually a very well known and very well studied problem, and in fact, most compilers and research spend a lot of time figuring out how to place spill code and coealesce copies, not how to color things. Chris knows this. I had discussions with him (many many years ago, before he ever started at Apple) about GCC's register allocation approach vs what he was thinking of doing for LLVM.

There are actually only so many good approaches to spill code /rematerialization/live range splitting you can use. At some point, it's really just a large integer-linear programming problem.

Note that coloring is essentially free on SSA form. It's linear time or better.

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?

For example:

"Live ranges being spilled without being split first cause the mess that the rewriter is working so hard to clean up. We would much rather split them into smaller pieces that might be assignable, but this would require the linear scan algorithm to backtrack. This is very expensive, and full live range splitting isn't really feasible with linear scan."

i.e. a weakness of linear scan is that the active list approach helps it solve the coloring problem quickly and accurately, but it comes with a big drawback that live range splitting is hard, which is the wrong tradeoff in practice.

"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

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-...

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.

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.

The fact that x86 is not a "pure" register-only architecture also matters --- it also has register-memory/memory-register operations, and push/pop (1 byte each) for efficient saving and restoring of values.

I've looked at a lot of compiler-generated code, and compared to hand-written Asm (which I have also done quite a bit of), register allocation is one of the things that compilers are very noticeably worse at. Thanks to their use of spilling, which doesn't really apply to something like x86, they shuffle data between registers and memory far more than they have to, instead of keeping values in memory or registers and using memory-register operations (which automatically "allocate" one of the many unnamed registers on the CPU, via register renaming.) A nested use structure could be handled easily with push/pop. It's good to see that compilers are slowly moving in the direction of allocating registers like a human programmer would.

There are very few academic papers that just consider the coloring problem of register allocation. One of the reasons for tis is that there is essentially no progress to be made on the instances of graph coloring that arise in register allocation. As far as I know, all graph coloring register allocators use the greedy coloring algorithm given by Chaitin, which was actually first published by Kempe in the 19th century. There are better graph coloring algorithms, but the interference graphs that arise from real programs are sufficiently uninteresting that they don't matter. And if you're using an SSA IR in your backend, things get even simpler: the greedy algorithm is optimal, and you can perfectly color the interference graph without even constructing it.

Most of the work on register allocation (both in academia and production compilers) happens on the aspects of the problem that are not reflected in the graph coloring formulation:

1) Copy elimination. You can approximate this problem by adding affinity weights to edges of the interference graph and asking for a coloring that minimizes the cost of unfulfilled affinities. This doesn't actually represent the problem as it exists on a real computer, because you can sometimes get rid of copies by other means than just choosing a lucky assignment, e.g. you can restructure the program to move a copy outside of a hot loop. This is especially relevant given the use of SSA form in modern compilers, because if you do nothing then you will end up inserting copies all over the place to implement phis.

2) Spill code insertion. If you perform a coloring of the interference graph and find that you don't have enough physical registers, then you have to restructure the program to spill registers to the stack and reload them. The particulars of which variables to spill and where to insert the stores and loads are very important for code quality. This includes things like rematerialization that let you insert other instruction sequences instead of loads to recreate the spilled value.

3) Live range splitting. In a sense, the idea that live range splitting is a distinct problem from the other problems of register allocation is relevant more to the implementation of register allocators than register allocation as an abstract optimization problem. If your allocator operates on a per-variable basis, then it often makes sense to split a variable into two separate variables and insert a copy merging the two live ranges. For example, a variable might be used frequently in one control-flow region and not used at all down another, and you want the register allocator to be able to make distinct decisions about those two regions. This problem is worsened by compiler optimizations, because compilers can often realize that multiple variables in a function have the same value and optimize them to use a common definition.

The area where academic register allocation research has the largest gap from actual practice is probably the consideration of architectural constraints on registers like instructions with fixed registers, pairs of adjacent registers, etc. and register files that have overlapping registers. You can always insert copies around an instruction to satisfy almost any constraint, but that doesn't work out so well. :) Most of the academic work I have seen on this problem is either overly simplified and doesn't handle all of the constraints that befall a production compiler, or it is considerably expensive to implement. This gets worse when you write a portable compiler; while the constraints of any single architecture may be manageable, it's harder when you have to handle the union of the constraints imposed by all architectures that you want to support. The aliasing between the various ARM floating-point register files was a strong motivator in the design of LLVM's greedy allocator.

The LLVM 'greedy' allocator is probably poorly named. It started out as a simple greedy register allocator, and over time it gained mechanisms like register eviction that make it a non-greedy algorithm. You don't have to squint too hard at it before it looks like a variation of priority allocation:

http://dl.acm.org/citation.cfm?id=88621

The allocator described in that paper uses an interference graph for liveness and interference checks and a different method of choosing the priorities, but if you abstract away those details it's pretty similar.