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

[Connor Abbott]

On Mon, Aug 4, 2014 at 10:42 AM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> 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.

By the way, I can see how spilling A might help as of now - since we
marked A and B as optimistic at the same time, some of the other
optimistic nodes above B on the stack might become trivial as we
reduced their interference count. But after the next patch, this
behavior changes - nodes above A on the stack are pushed on the stack
and popped off the stack without considering A at all, so spilling A
now won't make any difference. I can update the commit message to
explain this if you would like (and if you agree with what I'm
saying!).