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 rever

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.