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

[Connor Abbott]

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.
>
>> A few comments:
>>
>> 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
> evidence either that the additional back-tracking will lead to 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?