[Mesa-dev] [PATCH v2 3/4] ra: consider all spillable nodes for spilling

[Connor Abbott]

On Wed, Jul 30, 2014 at 10:50 PM, Eric Anholt <eric at anholt.net> wrote:
> Connor Abbott <cwabbott0 at gmail.com> writes:
>
>> Before, we would only consider nodes for spilling if they were
>> optimistically pushed onto the stack. But the logic for this was
>> complicated, and duplicated some things; also, we might want to spill
>> nodes that are not optimistically colored if our heuristic says we
>> should. This becomes a problem especially after the next commit, where
>> duplicating the current behavior of only spilling optimistically colored
>> nodes can sometimes leave the backend in a position where it has no
>> registers to spill. So just drop the original logic, and consider
>> everything that has its spill cost set for spilling.
>>
>> HURT:   shaders/steam/dungeon-defenders/5008.shader_test SIMD8: 434 -> 439 (1.15%)
>>
>> total instructions in shared programs: 4547617 -> 4547622 (0.00%)
>> instructions in affected programs:     434 -> 439 (1.15%)
>> GAINED:                                0
>> LOST:                                  0
>
> Interesting.  Is this our only shader that's spilling in the db?

Well, in the shader-db results for the next patch, there are two
shaders that are helped - that must've been because they were
spilling, or else that change wouldn't have made any difference.

> (though, also, something spilling that's only 434 instructions long?  I
> don't think I've ever seen that.  Wow.).  Sometimes for poking at this
> kind of stuff I'll just reduce the maximum number of registers I let the
> allocator handle, so that I have more spilling shaders to look at.

Yeah, that probably sounds like a good thing to try out.

>
> I think this change is a bad idea.  If the register was trivially
> colorable, then you don't want to spill it -- it won't help solve your
> inability to color whatever node you failed to allocate last time.

That's not necessarily true - you could want to spill a trivially
colored register that interferes with a non trivially colored
register, especially if the spill cost of the non trivially colored
register is higher than that of the trivially colored register because
e.g. the non trivially colored register is used in a loop. Especially,
I ran into trouble with the varying packing tests in piglit which
after a few rounds of spilling looked something like:

r0 = interpolate ...
r1 = interpolate ...
r2 = interpolate ...
...
r99 = interpolate ...
(register pressure is at the maximum allowable now)
r100 = interpolate ...
(now register pressure is one more than the maximum, we have to spill)
store r100
r101 = interpolate ...
store r101
...
r102 = load
use r102
...
r103 = load
use r103
...
use r2
use r1
use r0

Since we now know better which registers we might not be able to
allocate, we happen to push the spilled registers (r101, r102, etc)
before r99 and then only mark them as optimistically colored, so we
only consider them for spilling... except we can't spill them, so we
return -1 and the backend throws up its hands and says "OMG no
registers to spill!" I also ran into a similar problem on one of the
shader-db shaders.

We could simply keep the present behavior (i.e. pretend that
everything past the point where we started optimistically coloring
nodes is optimistically colored) but given that the whole point of
this seems to be to only spill nodes that we might not be able to
allocate, that doesn't seem too good of a solution, as well as being
rather fragile and non-obvious.

I think a better idea might be to not bail out early from ra_select()
but instead just don't touch the nodes we couldn't color, then later
only consider those nodes for spilling (then moving on to other nodes
if we couldn't find any spillable ones, to fix the bug I mentioned
earlier) - this seems to be the way Briggs originally intended
optimistic coloring to work [1], and it seems like it might be even
better than what we have now. What do you think?

I still think we should include this patch before the next one so we
don't break shader-db and piglit, and then later add in something more
sophisticated like what I mentioned above. Does this seem like a good
plan to you?

Connor

[1] http://www.cs.utexas.edu/~mckinley/380C/lecs/briggs-thesis-1992.pdf
page 27 (page 38 of the PDF)