Just to clarify (and as the abstract says), that paper's result is not restricted to programs in SSA form but to structured programs.
The chordal interference graphs that arise from (not necessarily structured) programs in SSA form are optimally colorable in linear time. That approach is a solid basis for a register allocator but it's worth noting that it's not solving the same problem because the introduced phi nodes split the original live ranges at CFG join points, so you're not coloring the same interference graph the program had prior to SSA conversion. In practice a good register allocator already needs to have well-tuned heuristics for spill/fill/split/coalesce placement regardless of whether it uses SSA-based coloring, so the extra splits introduced by the SSA conversion are optimized as part of that process.
In the special case where your SSA program is structured and the code is presented to the backend in its natural order, the perfect elimination order for the chordal interference graph is just backward code order. As a result you can do optimal register coloring for such programs in a single backward pass (which can be integrated into a backward code generation pass if you're trying to go fast).
Since it's too late to edit my post: It's not just the phi nodes that correspond to splitting. A straight-line program can generate a non-chordal interference graphs if variables are assigned multiple times. During SSA conversion, each time a given variable is assigned in a straight-line program, its original live range is split at that point.
The chordal interference graphs that arise from (not necessarily structured) programs in SSA form are optimally colorable in linear time. That approach is a solid basis for a register allocator but it's worth noting that it's not solving the same problem because the introduced phi nodes split the original live ranges at CFG join points, so you're not coloring the same interference graph the program had prior to SSA conversion. In practice a good register allocator already needs to have well-tuned heuristics for spill/fill/split/coalesce placement regardless of whether it uses SSA-based coloring, so the extra splits introduced by the SSA conversion are optimized as part of that process.
In the special case where your SSA program is structured and the code is presented to the backend in its natural order, the perfect elimination order for the chordal interference graph is just backward code order. As a result you can do optimal register coloring for such programs in a single backward pass (which can be integrated into a backward code generation pass if you're trying to go fast).