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

[Ian Romanick]

On 02/08/2016 04:21 PM, Matt Turner wrote:
> On Mon, Feb 8, 2016 at 3:57 PM, Ian Romanick  wrote:
>> On 02/04/2016 05:47 PM, 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.
>>
>> Doesn't that just mean that our "larger pattern" space is somehow
>> incompletely?  This seems to indicate that applications could (but
>> probably don't?) open-code these patterns and we'll miss them.
> 
> I don't understand the question. Does my reply to Eduardo perhaps
> answer your question?

No.  I understood what he was asking about.  Let me provide a somewhat
contrived example.  Say we had only the following set of algebraic
optimizations:

   (('fadd', ('fmul', a, b), c), ('ffma', a, b, c)),
   # Replace c*b - c*a + a with flrp
   (('fsub', ('fmul', a, b), ('fadd', ('fmul', c, a), a)),
('flrp', a, b, c)),

Without your patch, the first optimization would occur, and the second
would never happen.  With your patch, the larger tree is examined first,
so the second optimization patter matches.

However, an application could still open code (a*b)-fma(c, a, a), and
we'll miss it with or without your patch.  The patch prevents the
optimizer from fooling itself, but the application can still fool it.
Are we better off adding more patterns so that the application can't
fool it too?
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Jason Ekstrand]

On Feb 8, 2016 9:17 AM, "Matt Turner"  wrote:
>
> On Sun, Feb 7, 2016 at 8:06 AM, Jason Ekstrand 
wrote:
> >
> > On Feb 4, 2016 5:45 PM, "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.
> >
> > Mind doing just a little tooling to try and determine whether or not
this
> > increases the number of times the optimization loop runs?  Some
> > Optimizations may immediately allow some other optimization on their
result
> > which will now have to wait until the next time through the loop.
>
> In affected programs (129 of them):
>
> before:  1164 optimization loops
> after: 1071 optimization loops
>
> Of the 129 affected, 16 programs' optimization loop counts increased.

Good enough for me. Please add that to the commit message. R-B
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Matt Turner]

On Sun, Feb 7, 2016 at 8:06 AM, Jason Ekstrand  wrote:
>
> On Feb 4, 2016 5:45 PM, "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.
>
> Mind doing just a little tooling to try and determine whether or not this
> increases the number of times the optimization loop runs?  Some
> Optimizations may immediately allow some other optimization on their result
> which will now have to wait until the next time through the loop.

In affected programs (129 of them):

before:  1164 optimization loops
after: 1071 optimization loops

Of the 129 affected, 16 programs' optimization loop counts increased.
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Matt Turner]

On Mon, Feb 8, 2016 at 9:52 AM, Jason Ekstrand  wrote:
> Good enough for me. Please add that to the commit message. R-B

Thanks, will do.

Do you plan to review any of the others in the series?
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Matt Turner]

On Mon, Feb 8, 2016 at 3:57 PM, Ian Romanick  wrote:
> On 02/04/2016 05:47 PM, 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.
>
> Doesn't that just mean that our "larger pattern" space is somehow
> incompletely?  This seems to indicate that applications could (but
> probably don't?) open-code these patterns and we'll miss them.

I don't understand the question. Does my reply to Eduardo perhaps
answer your question?
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Ian Romanick]

On 02/04/2016 05:47 PM, 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.

Doesn't that just mean that our "larger pattern" space is somehow
incompletely?  This seems to indicate that applications could (but
probably don't?) open-code these patterns and we'll miss them.

> 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) {
>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, );
> +   nir_foreach_block_reverse(impl, ${pass_name}_block, );
>  
> if (state.progress)
>nir_metadata_preserve(impl, nir_metadata_block_index |
> 

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Eduardo Lima Mitev]

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.

>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, );
> +   nir_foreach_block_reverse(impl, ${pass_name}_block, );
>

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.

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 

> if (state.progress)
>nir_metadata_preserve(impl, nir_metadata_block_index |
> 

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Jason Ekstrand]

On Feb 4, 2016 5:45 PM, "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.

Mind doing just a little tooling to try and determine whether or not this
increases the number of times the optimization loop runs?  Some
Optimizations may immediately allow some other optimization on their result
which will now have to wait until the next time through the loop.
--Jason

> ---
>  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) {
>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, );
> +   nir_foreach_block_reverse(impl, ${pass_name}_block, );
>
> if (state.progress)
>nir_metadata_preserve(impl, nir_metadata_block_index |
> --
> 2.4.10
>
> ___
> mesa-dev mailing list
> mesa-dev@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [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  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, );
>> +   nir_foreach_block_reverse(impl, ${pass_name}_block, );
>>
>
> 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 

Thanks!
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

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

[Matt Turner]

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) {
   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, );
+   nir_foreach_block_reverse(impl, ${pass_name}_block, );
 
if (state.progress)
   nir_metadata_preserve(impl, nir_metadata_block_index |
-- 
2.4.10

___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev