If the allocator color T2 first (which it will), it'll need to spill it later, but it should really abort since no coloring is possible.
Essentially, spilling should always "break up" the live-range of the spilled temp. In the case above, the temp's live-range is already at minimum (only in 1 instruction), so if we must spill it, that means we don't have enough registers for this instruction.
Directly accounting for spill-able regs when coloring colored temps is not enough, e.g.,
# 2 regs {0, 1, 2},
# pre-color = [T0 -> 0, T1 -> 1]
... := T0, T1, T2
# T2 -> 0 or 1
# conflict with T0 or T1, can't spill T2, but could've assigned 2 to T2
To make the allocator less conservative, we need to color all the pre-colored temps first (or make them actively used really, since they're already colored), then the rest.
In this case, we can spill one of T1 or T2. But our allocator doesn't allow spilling of temps used in a single instruction (in a single read/write stage really), because we need them to be active simultaneously. One might say that this applies only to temps without coloring yet, but that's not true. See fatal issue.
Fortunately, this isn't an issue in practice, because we only write to multiple temps in call, and those temps are pre-colored to distinct caller-saved regs. Moreover, this is a non-issue if the temps are on the read side, because that means they are active before this instruction, which contradicts the coloring.
Fatal issue
Unfortunately, a fatal issue remains -- the greedy register allocation algorithm simply 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
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).
A follow-up on #29.
Issue
Currently the greedy register allocator only enforces spill-able regs when coloring uncolored temps. That can result in infinite loop, e.g.,
If the allocator color
T2first (which it will), it'll need to spill it later, but it should really abort since no coloring is possible.Essentially, spilling should always "break up" the live-range of the spilled temp. In the case above, the temp's live-range is already at minimum (only in 1 instruction), so if we must spill it, that means we don't have enough registers for this instruction.
Directly accounting for spill-able regs when coloring colored temps is not enough, e.g.,
To make the allocator less conservative, we need to color all the pre-colored temps first (or make them actively used really, since they're already colored), then the rest.
Another issue
In this case, we can spill one of
T1orT2. But our allocator doesn't allow spilling of temps used in a single instruction (in a single read/write stage really), because we need them to be active simultaneously. One might say that this applies only to temps without coloring yet, but that's not true. See fatal issue.Fortunately, this isn't an issue in practice, because we only write to multiple temps in call, and those temps are pre-colored to distinct caller-saved regs. Moreover, this is a non-issue if the temps are on the read side, because that means they are active before this instruction, which contradicts the coloring.
Fatal issue
Unfortunately, a fatal issue remains -- the greedy register allocation algorithm simply can't guarantee a coloring deterministically. Consider the following case:
If we greedily color
T1with0, 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