If we greedily color T1 with 0, we are out of luck, because spilling wouldn't really change anything here (this is the only instruction in the program).
In fact, who knows which color it's going to pick? But the algorithm is deterministic so if it picks the wrong color, oops.
So the best we can do is
make the algorithm as aggressive as possible without hurting correctness
abort conservatively, when necessary (maybe consider adding another case to indicate that in the result, and have a default
coloring strategy from each backend, e.g., X86).
Practical win
As mentioned in another sub-issue from #52, since we only write to multiple temps in call, and those temps are pre-colored to distinct caller-saved regs, we won't have this issue in practice.
Moreover, this issue can't occur on the read end either, since any temp being read must be active (or from initial live-in, but those are arguments that are distinctly colored anyway). If they are active, they must have distinct coloring already :).
StrongerXi
commented
3 years ago
A re-compilation of an issue discovered at the end of #52
Issue
The greedy register allocation algorithm can't guarantee a coloring deterministically. Consider the following case:
If we greedily color T1 with 0, we are out of luck, because spilling wouldn't really change anything here (this is the only instruction in the program).
In fact, who knows which color it's going to pick? But the algorithm is deterministic so if it picks the wrong color, oops.
So the best we can do is
Practical win
As mentioned in another sub-issue from #52, since we only write to multiple temps in
call, and those temps are pre-colored to distinct caller-saved regs, we won't have this issue in practice.Moreover, this issue can't occur on the read end either, since any temp being read must be active (or from initial live-in, but those are arguments that are distinctly colored anyway). If they are active, they must have distinct coloring already :).