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 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
I'm pretty sure LLVM's PBQP implementation is 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.
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-...
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.