> Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advant

> Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advantages of having a chordal graph goes out of the window. IMO, the most important insights of the work on SSA-based register allocation go beyond the idea that chordal interference graphs are easily colorable. In particular, 1) The idea that register allocation can be decoupled into separate allocation and assignment phases. Without this, you either have to view register allocation as an integrated problem, which makes it difficult to apply heuristics, or you have to have miniature register suballocators inside of different phases of your register allocator. The asymptotic horizon of the last possibility is GCC's reload. Of course, the further your architecture deviates from the theoretical model of SSA register allocation, the less you can see the benefit. In particular, estimating liveness with excessive use of subregisters is difficult, and splitting live ranges to satisfy register constraints can push the majority of the difficult problems back into copy elimination. 2) The recognition of the role of parallel copy semantics of phi pseudofunctions. Even if you were writing a conventional non-SSA register allocator, it would be wise to eliminate SSA form by introducing parallel copies and preserving those as late as possible to avoid spurious interferences. Both of these ideas are actually present in Lueh's work on fusion-based allocation (which decouples allocation by simply repeatedly checking whether graphs are still greedily k-colorable, rather than relying on chordality), but it is easier to see that in hindsight.