# [Mesa-dev] [PATCH] ra: Disable round-robin strategy for optimistically colorable nodes.

Francisco Jerez currojerez at riseup.net
Tue Feb 17 12:16:04 PST 2015

```Connor Abbott <cwabbott0 at gmail.com> writes:

> On Tue, Feb 17, 2015 at 8:15 AM, Francisco Jerez <currojerez at riseup.net> wrote:
>> Connor Abbott <cwabbott0 at gmail.com> writes:
>>
>>> Hi Francisco,
>>>
>> Hi Connor, and thank you for your feedback.
>>
>>>
>>> 1) This is just a difference in definitions, but to me an
>>> optimistically-colored node is a node that we pushed onto the stack
>>> without knowing whether we could color it or not. There may be (and
>>> most certainly are) nodes above the optimistically-colored node on the
>>> stack that we know we can color, so I wouldn't call those
>>> optimistically colored even though they probably have the
>>> characteristics you mentioned.
>>
>> Yeah, I mostly agree on the definition, but the distinction is somewhat
>> arbitrary and consequence of the min-q heuristic, which picks a
>> preferred node among the whole set of remaining non-trivially colorable
>> nodes, but that's by no means the only possible choice.  We may indeed
>> know we can trivially color some of the nodes left after we push the
>> first optimistically node onto the stack, but even that's dependent on
>> the assumption that we can take the optimistically colored node below
>> them out of the picture, and that's a bit of an overstatement because we
>> have no guarantee that the coloring we choose for these nodes won't lead
>> to a contradiction later on.
>>
>>> The distinction is useful since the optimistically colored nodes are
>>> those which we may have to spill.
>>>
>> Now you're using "optimistically colored nodes" to refer to the nodes we
>> potentially consider for spilling (at most the first optimistically
>> colorable node and everything above it), which is precisely the same set
>> of nodes I'm disabling round-robin for. ;)
>
> Whoops, I meant "those which we may fail to find a color for." Goes to
> show what happens when you try to be pedantic...
>
>>
>>> 2) Given the above, what you're doing here is disabling the
>>> round-robin strategy for the nodes above the lowest
>>> optimistically-colored node as well as the lowest
>>> optimistically-colored node itself. But you don't need to disable
>>> round-robin for the lowest optimistically-colored node itself, since
>>> once we're able to find a register (any register!) for that one, we
>>> know we'll be able to find a register for everything else that's left,
>>> so it doesn't really matter which register we start searching at.
>>>
>> Heh, fair enough, I'll send a v2.
>>
>>> 3) Usually, there are a series of registers that are pushed onto the
>>> stack optimistically until we can go back to the normal strategy, and
>>> it's one of the registers in the middle of the stack we fail to place,
>>> so we don't need to disable round-robin for *all* the optimistically
>>> colored nodes, only everything above the node that would've failed to
>>> allocate. Another way to think of it is that when I changed the
>>> handling of optimistic coloring a while ago, we gained ~150 SIMD16
>>> shaders. So of the >200 SIMD16 shaders that we optimistically color
>>> but still successfully allocate after your patch, only 50 -- less than
>>> a quarter -- actually need to have round-robin disabled. This is just
>>> an idea, but maybe we could handle this similarly to how we handle
>>> spilling: first, try ra_select() using round-robin all the way, and
>>> only when it fails do we disable round-robin for everything above the
>>> thing that we failed to allocate and try ra_select() again. We would
>>> keep doing this until disabling round-robin wouldn't make a
>>> difference.
>>
>> We already discussed this shortly on IRC, but let me summarize here.
>>
>> I did consider doing that to avoid the regressions (and actually went as
>> far as to implement it), but it seemed rather ugly to add another loop
>> of trial-and-error to the already ugly schedule-regalloc loop which
>> tries out three different scheduling heuristics for two different
>> dispatch widths until one succeeds, and then you have one more iteration
>> for each spill.
>>
>> I admit that the additional back-tracking would be unlikely to affect
>> the running time of the register allocator significantly, but I suspect
>> that the pre-regalloc scheduler is also at fault in the regressing cases
>> and there's likely to be a better solution for them.  I don't have any
>> measurable improvement in any of the other cases (actually I would be
>> very surprised if that's the case), so this suggestion seems a bit of a
>> premature optimization to me, how about we KISS for now.
>
> That sounds sensible to me. By the way, did you ever send a patch to
> fix the silliness you found in the pre-regalloc scheduler?

Nope, haven't had time to finish that yet.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 212 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150217/7cb33786/attachment.sig>
```