[Mesa-dev] [PATCH 3/5] nir: Do opt_algebraic in reverse order.

[Matt Turner]

On Sun, Feb 7, 2016 at 6:04 AM, Eduardo Lima Mitev <elima at igalia.com> wrote:
> On 02/05/2016 02:47 AM, Matt Turner wrote:
>> Walking the SSA definitions in order means that we consider the smallest
>> algebraic optimizations before larger optimizations. So if a smaller
>> rule is part of a larger rule, the smaller one will happen first,
>> preventing the larger one from happening.
>>
>> instructions in affected programs: 32721 -> 32611 (-0.34%)
>> helped: 106
>>
>> Prevents regressions and annoyances in the next commits.
>> ---
>>  src/compiler/nir/nir_algebraic.py | 4 ++--
>>  1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/src/compiler/nir/nir_algebraic.py b/src/compiler/nir/nir_algebraic.py
>> index a30652f..77ad35e 100644
>> --- a/src/compiler/nir/nir_algebraic.py
>> +++ b/src/compiler/nir/nir_algebraic.py
>> @@ -216,7 +216,7 @@ ${pass_name}_block(nir_block *block, void *void_state)
>>  {
>>     struct opt_state *state = void_state;
>>
>> -   nir_foreach_instr_safe(block, instr) {
>> +   nir_foreach_instr_reverse_safe(block, instr) {
>
> I would add an explicit comment here as to why walk in reverse order. It
> is not immediately clear (at least to me) that the smallest algebraic
> optimizations come before the larger ones. I could not find any comment
> in opt_algebraic.py or anywhere else that would suggest this is the case.

I think you've misunderstood. The walk, reverse or otherwise, isn't
over the optimizations in nir_opt_algebraic. It's over the NIR
instructions.

Walking the instructions in reverse is beneficial because it
necessarily allows larger patterns to be recognized before smaller
patterns. Take for instance a portion of the bitfield_reverse pattern
in patch 5:

('ior', ('ishl', u, 16), ('ushr', u, 16))

If there were also a rule that matched ('ushr', u, 16) (as
('extract_u16', u, 1) for example), walking the instructions in order
would cause the extract_u16 rule to match first. Once that had
happened, the bitfield_reverse pattern would not match.

Walking the NIR in reverse means that you look at the largest
expression trees first.

>>        if (instr->type != nir_instr_type_alu)
>>           continue;
>>
>> @@ -255,7 +255,7 @@ ${pass_name}_impl(nir_function_impl *impl, const bool *condition_flags)
>>     state.progress = false;
>>     state.condition_flags = condition_flags;
>>
>> -   nir_foreach_block(impl, ${pass_name}_block, &state);
>> +   nir_foreach_block_reverse(impl, ${pass_name}_block, &state);
>>
>
> Does it make sense to reverse traversing of blocks too? As far as I
> understand opt_algebraic rules don't expand to other blocks (maybe I'm
> wrong). I also don't see any difference in shader-db results running
> with or without this chunk.

I think it does make sense, because the expression trees can span
multiple basic blocks.

> These are my results on HSW (with patches 1 to 3):
>
> total instructions in shared programs: 6265414 -> 6265312 (-0.00%)
> instructions in affected programs: 31499 -> 31397 (-0.32%)
> helped: 98
> HURT: 0
>
> total cycles in shared programs: 56081290 -> 56078442 (-0.01%)
> cycles in affected programs: 562440 -> 559592 (-0.51%)
> helped: 102
> HURT: 6
>
>
> Patches 1 to 3 are:
>
> Reviewed-by: Eduardo Lima Mitev <elima at igalia.com>

Thanks!