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

[Connor Abbott]

On Mon, Aug 4, 2014 at 10:17 AM, Eric Anholt <eric at anholt.net> wrote:
> Connor Abbott <cwabbott0 at gmail.com> writes:
>
>> On Mon, Aug 4, 2014 at 9:46 AM, Eric Anholt <eric at anholt.net> wrote:
>>> Connor Abbott <cwabbott0 at gmail.com> writes:
>>>
>>>> On Fri, Aug 1, 2014 at 12:25 PM, Eric Anholt <eric at anholt.net> wrote:
>>>>> Connor Abbott <cwabbott0 at gmail.com> writes:
>>>>>
>>>>>> On Fri, Aug 1, 2014 at 11:51 AM, Eric Anholt <eric at anholt.net> wrote:
>>>>>>> Connor Abbott <cwabbott0 at gmail.com> writes:
>>>>>>>
>>>>>>>> On Thu, Jul 31, 2014 at 1:05 PM, Eric Anholt <eric at anholt.net> wrote:
>>>>>>>>> Connor Abbott <cwabbott0 at gmail.com> writes:
>>>>>>>>>> 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:
>>>>>>>>>
>>>>>>>>> If it's trivially colorable, then when you're trying to get a
>>>>>>>>> non-conflicting color for a difficult neighbor (an optimistic-coloring
>>>>>>>>> one near the top of the stack that's triggering the need for spilling),
>>>>>>>>> it's out consideration because it's deeper in the stack.
>>>>>>>>
>>>>>>>> Right... so in that case, can't we just ignore everything on the stack
>>>>>>>> below the node that couldn't be colored in ra_select()?
>>>>>>>
>>>>>>> Yep, that's what the code's doing currently.
>>>>>>
>>>>>> No, it's also considering other optimistically colored nodes below the
>>>>>> one that failed on the stack... see patch 3 in v3 of my series, which
>>>>>> changes the code to actually do that.
>>>>>
>>>>> Oh, I misread you as saying s/couldn't be colored/first couldn't be
>>>>> trivially colored/.  It seems like obviously the behavior we want, to
>>>>> me.
>>>>
>>>> Cool, then can you put your r-b on the last two patches of the v3
>>>> series so we can push it?
>>>
>>> Not really -- I'm saying that we *do* want to consider the other
>>> optimistically colored nodes.  Those ones lower in the stack might
>>> actually be useful to spill, since if spilled they could potentially
>>> make other values trivially colorable, which would change the order of
>>> pushes and might make our node colorable.
>>>
>>
>> Well, you could apply that same argument to *any* spillable node in
>> the graph, which brings us right back to where we started. I think
>> what we have now is a rather arbitrary compromise between "consider
>> everything for spilling because it might make other things trivially
>> colorable" and "only spill the things we know are likely to help." I
>> still think we should go with the former, since it produces numbers
>> equivalent to what we have right now instead of slightly worse
>> numbers. And besides, as I noted in the commit message, considering
>> those nodes doesn't seem to be useful in practice since we get the
>> exact same code anyways - even with reducing the number of registers
>> to make more things spill.
>
> I don't believe that's true.  The argument before was about
> trivially-colorable things -- things that always appear in the stack
> before the optimistic things.  They can't have an effect on the things
> higher in the stack, becuase they're already in the stack and you know
> you can color them regardless of choices higher in the stack, so you
> don't have to spill them ever.
>
> For your optimistic nodes, though, even though you've put them in the
> stack, you want to consider them for spilling because even once you
> resolve the spills and manage to color things high in the stack (in your
> scheme), you may have to spill that lower-down optimistic node anyway.
> So you failed to consider an important node for spilling, that might
> have also resolved your higher-in-the-stack troubles, and got extra
> spilling as a result.

How, exactly, could spilling in this case ever resolve the
"higher-in-the-stack troubles"? Say we have an optimistically colored
node A, that is lower on the stack than the optimistically colored
node B that is currently failing to be colored. There are two effects
of spilling A:

1) Some of the nodes that we split A into may become trivially
colorable, which will push them down on the stack - but this is all
happening below B on the stack anyways, so it doesn't make any
difference for now.

2) Some of the nodes that were interfering with A may no longer
interfere with any of the nodes we split A into - but again, we only
care about B or nodes above B on the stack, so we don't count that
interference anyways, and therefore we still haven't gained anything.

So although spilling A may help in the future, I still fail to see how
it could help now - we still have to spill nodes above B (or B itself)
before we can make progress.