[Mesa-dev] [PATCH] ra: Disable round-robin strategy for optimistically colorable nodes.
Francisco Jerez
currojerez at riseup.net
Wed Feb 18 05:31:19 PST 2015
Connor Abbott <cwabbott0 at gmail.com> writes:
> On Tue, Feb 17, 2015 at 3:04 PM, Francisco Jerez <currojerez at riseup.net> wrote:
>> Jason Ekstrand <jason at jlekstrand.net> writes:
>>
>>> On Mon, Feb 16, 2015 at 11:39 AM, Francisco Jerez <currojerez at riseup.net>
>>> wrote:
>>>
>>>> The round-robin allocation strategy is expected to decrease the amount
>>>> of false dependencies created by the register allocator and give the
>>>> post-RA scheduling pass more freedom to move instructions around. On
>>>> the other hand it has the disadvantage of increasing fragmentation and
>>>> decreasing the number of equally-colored nearby nodes, what increases
>>>> the likelihood of failure in presence of optimistically colorable
>>>> nodes.
>>>>
>>>> This patch disables the round-robin strategy for optimistically
>>>> colorable nodes. These typically arise in situations of high register
>>>> pressure or for registers with large live intervals, in both cases the
>>>> task of the instruction scheduler shouldn't be constrained excessively
>>>> by the dense packing of those nodes, and a spill (or on Intel hardware
>>>> a fall-back to SIMD8 mode) is invariably worse than a slightly less
>>>> optimal scheduling.
>>>>
>>>> Shader-db results on the i965 driver:
>>>>
>>>> total instructions in shared programs: 5488539 -> 5488489 (-0.00%)
>>>> instructions in affected programs: 1121 -> 1071 (-4.46%)
>>>> helped: 1
>>>> HURT: 0
>>>> GAINED: 49
>>>> LOST: 5
>>>> ---
>>>> src/util/register_allocate.c | 22 +++++++++++++++++++++-
>>>> 1 file changed, 21 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/src/util/register_allocate.c b/src/util/register_allocate.c
>>>> index af7a20c..d63d8eb 100644
>>>> --- a/src/util/register_allocate.c
>>>> +++ b/src/util/register_allocate.c
>>>> @@ -168,6 +168,12 @@ struct ra_graph {
>>>>
>>>> unsigned int *stack;
>>>> unsigned int stack_count;
>>>> +
>>>> + /**
>>>> + * Tracks the start of the set of optimistically-colored registers in
>>>> the
>>>> + * stack.
>>>> + */
>>>> + unsigned int stack_optimistic_start;
>>>> };
>>>>
>>>> /**
>>>> @@ -454,6 +460,7 @@ static void
>>>> ra_simplify(struct ra_graph *g)
>>>> {
>>>> bool progress = true;
>>>> + unsigned int stack_optimistic_start = ~0;
>>>>
>>>
>>> UINT_MAX would be clearer than ~0
>>>
>> Sure, either works as identity for MIN2. Do you want me to send a v3
>> for this or should I fix it locally and add your R-b?
>>
>>>
>>>> int i;
>>>>
>>>> while (progress) {
>>>> @@ -483,12 +490,16 @@ ra_simplify(struct ra_graph *g)
>>>>
>>>> if (!progress && best_optimistic_node != ~0U) {
>>>>
>>>
>>> I guess we're using ~0 other places... oh well...
>>>
>>>
>>>> decrement_q(g, best_optimistic_node);
>>>> + stack_optimistic_start =
>>>> + MIN2(stack_optimistic_start, g->stack_count);
>>>>
>>>
>>> It might be clearer to explicitly use an if here instead of the MIN2
>>> because what this really means is "if (stack_optimistic_start == ~0)
>>> stack_optimistic_start = g->stack_count;"
>>>
>> What I really meant to calculate here is the minimum of the indices of
>> all optimistic nodes inserted into the stack. What you say works too
>> because we happen to be growing the stack monotonically. How can using
>> MIN2 possibly obscure the meaning of taking the minimum?
>
> Because you're finding stack_optimistic_*start*, i.e. the *first*
> thing on the stack that's optimistic. It's a pretty common idiom in C,
> when you're going through a bunch of stuff and you want to record the
> first thing that satisfies some property, to do:
>
> result = some_default_value (NULL, UINT_MAX, etc.)
> for_each_thing {
> ...
> if (has_the_property(thing) && result == some_default_value) {
> result = thing;
> }
> }
>
> so if you do what Jason suggested, people will see the pattern and go
> "ah, it's recording the first thing we pushed optimistically, that
> makes sense" as opposed to thinking about what the minimum is doing;
> it's not obvious at first that after the first MIN2
> stack_optimistic_start is never going to change.
>
Yeah, I completely agree with your argumentation, actually it's funny
that this was precisely the reason that led me to intentionally write
MIN2() rather than your open-coded equivalent. I consider the way how
something is going to change or not along your incidental control flow a
distraction from its formal definition. But I'm not going spend a
single second more of my time in this discussion because it is a matter
of personal taste and there's no objectively better or worse choice,
there's no point in being categorical here. If you insist in stressing
the how over the what and cannot tolerate somebody else's personal
inclination I'm just going to do as you say because this has long
crossed the line of bike-shedding.
Did you actually intend to review this patch? And if so do you want a
resend with the trivial codestyle changes?
>>
>>> Other than that (and connor's comment), it looks fine to me.
>>>
>>> --Jason
>>>
>>>
>>>> g->stack[g->stack_count] = best_optimistic_node;
>>>> g->stack_count++;
>>>> g->nodes[best_optimistic_node].in_stack = true;
>>>> progress = true;
>>>> }
>>>> }
>>>> +
>>>> + g->stack_optimistic_start = stack_optimistic_start;
>>>> }
>>>>
>>>> /**
>>>> @@ -542,7 +553,16 @@ ra_select(struct ra_graph *g)
>>>> g->nodes[n].reg = r;
>>>> g->stack_count--;
>>>>
>>>> - if (g->regs->round_robin)
>>>> + /* Rotate the starting point except for optimistically colorable
>>>> nodes.
>>>> + * The likelihood that we will succeed at allocating optimistically
>>>> + * colorable nodes is highly dependent on the way that the previous
>>>> + * nodes popped off the stack are laid out. The round-robin
>>>> strategy
>>>> + * increases the fragmentation of the register file and decreases
>>>> the
>>>> + * number of nearby nodes assigned to the same color, what
>>>> increases the
>>>> + * likelihood of spilling with respect to the dense packing
>>>> strategy.
>>>> + */
>>>> + if (g->regs->round_robin &&
>>>> + g->stack_count <= g->stack_optimistic_start)
>>>> start_search_reg = r + 1;
>>>> }
>>>>
>>>> --
>>>> 2.1.3
>>>>
>>>> _______________________________________________
>>>> mesa-dev mailing list
>>>> mesa-dev at lists.freedesktop.org
>>>> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>>>>
>>
>> _______________________________________________
>> mesa-dev mailing list
>> mesa-dev at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>>
-------------- 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/20150218/05a6a910/attachment.sig>
More information about the mesa-dev
mailing list