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

[Connor Abbott]

On Tue, Feb 17, 2015 at 3:17 PM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> 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.

Err, I meant the first MIN2 that changes the value of
stack_optimistic_start of course.

>
>>
>>> 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
>>