Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Timothy Arceri]

On Fri, 2016-09-16 at 15:25 -0700, Jason Ekstrand wrote:
> > On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri  wrote:
> > > > From: Thomas Helland 
> > 
> > 
> > This pass detects induction variables and calculates the
> > 
> > trip count of loops to be used for loop unrolling.
> > 
> > 
> > 
> > I've removed support for float induction values for now, for the
> > 
> > simple reason that they don't appear in my shader-db collection,
> > 
> > and so I don't see it as common enough that we want to pollute the
> > 
> > pass with this in the initial version.
> > 
> > 
> > 
> > V2: Rebase, adapt to removal of function overloads
> > 
> > 
> > 
> > V3: (Timothy Arceri)
> > 
> > > >  - don't try to find trip count if loop terminator conditional is a
phi
> > 
> >  - fix trip count for do-while loops
> > 
> >  - replace conditional type != alu assert with return
> > 
> >  - disable unrolling of loops with continues
> > 
> > > >  - multiple fixes to memory allocation, stop leaking and don't
destroy
> > 
> >    structs we want to use for unrolling.
> > 
> > > >  - fix iteration count bugs when induction var not on RHS of
condition
> > 
> >  - add FIXME for && conditions
> > 
> >  - calculate trip count for unsigned induction/limit vars
> > 
> > 
> > 
> > V4:
> > 
> > - count instructions in a loop
> > 
> > > > - set the limiting_terminator even if we can't find the trip count
for
> > 
> > > >  all terminators. This is needed for complex unrolling where we
handle
> > 
> >  2 terminators and the trip count is unknown for one of them.
> > 
> > - restruct structs so we don't keep information not required after
> > 
> >  analysis and remove dead fields.
> > 
> > > > - force unrolling in some cases as per the rules in the GLSL IR
pass
> > 
> > ---
> > 
> >  src/compiler/Makefile.sources       |    2 +
> > 
> >  src/compiler/nir/nir.h              |   36 +-
> > 
> > > >  src/compiler/nir/nir_loop_analyze.c | 1012
+++
> > 
> >  src/compiler/nir/nir_metadata.c     |    8 +-
> > 
> >  4 files changed, 1056 insertions(+), 2 deletions(-)
> > 
> >  create mode 100644 src/compiler/nir/nir_loop_analyze.c
> > 
> > 
> > 
> > > > diff --git a/src/compiler/Makefile.sources
b/src/compiler/Makefile.sources
> > 
> > index f5b4f9c..7ed26a9 100644
> > 
> > --- a/src/compiler/Makefile.sources
> > 
> > +++ b/src/compiler/Makefile.sources
> > 
> > @@ -190,6 +190,8 @@ NIR_FILES = \
> > 
> >         nir/nir_intrinsics.c \
> > 
> >         nir/nir_intrinsics.h \
> > 
> >         nir/nir_liveness.c \
> > 
> > +       nir/nir_loop_analyze.c \
> > 
> > +       nir/nir_loop_analyze.h \
> > 
> >         nir/nir_lower_alu_to_scalar.c \
> > 
> >         nir/nir_lower_atomics.c \
> > 
> >         nir/nir_lower_bitmap.c \
> > 
> > diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> > 
> > index ff7c422..49e8cd8 100644
> > 
> > --- a/src/compiler/nir/nir.h
> > 
> > +++ b/src/compiler/nir/nir.h
> > 
> > @@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
> > 
> >  }
> > 
> > 
> > 
> >  typedef struct {
> > 
> > +   nir_if *nif;
> > 
> > +
> > 
> > +   nir_instr *conditional_instr;
> > 
> > +
> > 
> > +   struct list_head loop_terminator_link;
> > 
> > +} nir_loop_terminator;
> > 
> > +
> > 
> > +typedef struct {
> > 
> > +   /* Number of instructions in the loop */
> > 
> > +   unsigned num_instructions;
> > 
> > +
> > 
> > +   /* How many times the loop is run (if known) */
> > 
> > +   unsigned trip_count;
> > 
> > +   bool is_trip_count_known;
> > We could use 0 or -1 to indicate "I don't know trip count" instead of
an extra boolean.  Not sure that it matters much.
>  
> > +
> > 
> > +   /* Unroll the loop regardless of its size */
> > 
> > +   bool force_unroll;
> > It seems a bit odd to have this decide to force-unroll.  This is an
analysis pass, not a "make decisions" pass.
> 
> 
> 
>  
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Timothy Arceri]

I sent this reply on Saturday however is seems something went wrong and
it didn't make it out so here it is again.

On Fri, 2016-09-16 at 15:25 -0700, Jason Ekstrand wrote:
> On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri  abora.com> wrote:
> > From: Thomas Helland 
> > 
> > This pass detects induction variables and calculates the
> > trip count of loops to be used for loop unrolling.
> > 
> > I've removed support for float induction values for now, for the
> > simple reason that they don't appear in my shader-db collection,
> > and so I don't see it as common enough that we want to pollute the
> > pass with this in the initial version.
> > 
> > V2: Rebase, adapt to removal of function overloads
> > 
> > V3: (Timothy Arceri)
> >  - don't try to find trip count if loop terminator conditional is a
> > phi
> >  - fix trip count for do-while loops
> >  - replace conditional type != alu assert with return
> >  - disable unrolling of loops with continues
> >  - multiple fixes to memory allocation, stop leaking and don't
> > destroy
> >    structs we want to use for unrolling.
> >  - fix iteration count bugs when induction var not on RHS of
> > condition
> >  - add FIXME for && conditions
> >  - calculate trip count for unsigned induction/limit vars
> > 
> > V4:
> > - count instructions in a loop
> > - set the limiting_terminator even if we can't find the trip count
> > for
> >  all terminators. This is needed for complex unrolling where we
> > handle
> >  2 terminators and the trip count is unknown for one of them.
> > - restruct structs so we don't keep information not required after
> >  analysis and remove dead fields.
> > - force unrolling in some cases as per the rules in the GLSL IR
> > pass
> > ---
> >  src/compiler/Makefile.sources       |    2 +
> >  src/compiler/nir/nir.h              |   36 +-
> >  src/compiler/nir/nir_loop_analyze.c | 1012
> > +++
> >  src/compiler/nir/nir_metadata.c     |    8 +-
> >  4 files changed, 1056 insertions(+), 2 deletions(-)
> >  create mode 100644 src/compiler/nir/nir_loop_analyze.c
> > 
> > diff --git a/src/compiler/Makefile.sources
> > b/src/compiler/Makefile.sources
> > index f5b4f9c..7ed26a9 100644
> > --- a/src/compiler/Makefile.sources
> > +++ b/src/compiler/Makefile.sources
> > @@ -190,6 +190,8 @@ NIR_FILES = \
> >         nir/nir_intrinsics.c \
> >         nir/nir_intrinsics.h \
> >         nir/nir_liveness.c \
> > +       nir/nir_loop_analyze.c \
> > +       nir/nir_loop_analyze.h \
> >         nir/nir_lower_alu_to_scalar.c \
> >         nir/nir_lower_atomics.c \
> >         nir/nir_lower_bitmap.c \
> > diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> > index ff7c422..49e8cd8 100644
> > --- a/src/compiler/nir/nir.h
> > +++ b/src/compiler/nir/nir.h
> > @@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
> >  }
> > 
> >  typedef struct {
> > +   nir_if *nif;
> > +
> > +   nir_instr *conditional_instr;
> > +
> > +   struct list_head loop_terminator_link;
> > +} nir_loop_terminator;
> > +
> > +typedef struct {
> > +   /* Number of instructions in the loop */
> > +   unsigned num_instructions;
> > +
> > +   /* How many times the loop is run (if known) */
> > +   unsigned trip_count;
> > +   bool is_trip_count_known;
> 
> We could use 0 or -1 to indicate "I don't know trip count" instead of
> an extra boolean.  Not sure that it matters much.
>  
> > +
> > +   /* Unroll the loop regardless of its size */
> > +   bool force_unroll;
> 
> It seems a bit odd to have this decide to force-unroll.  This is an
> analysis pass, not a "make decisions" pass.
>  
> > +
> > +   nir_loop_terminator *limiting_terminator;
> > +
> > +   /* A list of loop_terminators terminating this loop. */
> > +   struct list_head loop_terminator_list;
> > +} nir_loop_info;
> > +
> > +typedef struct {
> >     nir_cf_node cf_node;
> > 
> >     struct exec_list body; /** < list of nir_cf_node */
> > +
> > +   nir_loop_info *info;
> >  } nir_loop;
> > 
> >  static inline nir_cf_node *
> > @@ -1576,6 +1603,7 @@ typedef enum {
> >     nir_metadata_dominance = 0x2,
> >     nir_metadata_live_ssa_defs = 0x4,
> >     nir_metadata_not_properly_reset = 0x8,
> > +   nir_metadata_loop_analysis = 0x16,
> >  } nir_metadata;
> > 
> >  typedef struct {
> > @@ -1758,6 +1786,8 @@ typedef struct nir_shader_compiler_options {
> >      * information must be inferred from the list of input
> > nir_variables.
> >      */
> >     bool use_interpolated_input_intrinsics;
> > +
> > +   unsigned max_unroll_iterations;
> >  } nir_shader_compiler_options;
> > 
> >  typedef struct nir_shader_info {
> > @@ -1962,7 +1992,7 @@ nir_loop *nir_loop_create(nir_shader
> > *shader);
> >  nir_function_impl *nir_cf_node_get_function(nir_cf_node *node);
> > 
> >  /** requests that the given pieces of metadata be generated */
> > -void nir_metadata_require(nir_function_impl *impl, nir_metadata
> > required);
> > +void 

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Jason Ekstrand]

On Fri, Sep 16, 2016 at 5:36 PM, Connor Abbott  wrote:

> On Fri, Sep 16, 2016 at 6:25 PM, Jason Ekstrand 
> wrote:
> > On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri
> >  wrote:
> >>
> >> From: Thomas Helland 
> >>
> >> This pass detects induction variables and calculates the
> >> trip count of loops to be used for loop unrolling.
> >>
> >> I've removed support for float induction values for now, for the
> >> simple reason that they don't appear in my shader-db collection,
> >> and so I don't see it as common enough that we want to pollute the
> >> pass with this in the initial version.
> >>
> >> V2: Rebase, adapt to removal of function overloads
> >>
> >> V3: (Timothy Arceri)
> >>  - don't try to find trip count if loop terminator conditional is a phi
> >>  - fix trip count for do-while loops
> >>  - replace conditional type != alu assert with return
> >>  - disable unrolling of loops with continues
> >>  - multiple fixes to memory allocation, stop leaking and don't destroy
> >>structs we want to use for unrolling.
> >>  - fix iteration count bugs when induction var not on RHS of condition
> >>  - add FIXME for && conditions
> >>  - calculate trip count for unsigned induction/limit vars
> >>
> >> V4:
> >> - count instructions in a loop
> >> - set the limiting_terminator even if we can't find the trip count for
> >>  all terminators. This is needed for complex unrolling where we handle
> >>  2 terminators and the trip count is unknown for one of them.
> >> - restruct structs so we don't keep information not required after
> >>  analysis and remove dead fields.
> >> - force unrolling in some cases as per the rules in the GLSL IR pass
> >> ---
> >>  src/compiler/Makefile.sources   |2 +
> >>  src/compiler/nir/nir.h  |   36 +-
> >>  src/compiler/nir/nir_loop_analyze.c | 1012
> >> +++
> >>  src/compiler/nir/nir_metadata.c |8 +-
> >>  4 files changed, 1056 insertions(+), 2 deletions(-)
> >>  create mode 100644 src/compiler/nir/nir_loop_analyze.c
> >>
> >> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.
> sources
> >> index f5b4f9c..7ed26a9 100644
> >> --- a/src/compiler/Makefile.sources
> >> +++ b/src/compiler/Makefile.sources
> >> @@ -190,6 +190,8 @@ NIR_FILES = \
> >> nir/nir_intrinsics.c \
> >> nir/nir_intrinsics.h \
> >> nir/nir_liveness.c \
> >> +   nir/nir_loop_analyze.c \
> >> +   nir/nir_loop_analyze.h \
> >> nir/nir_lower_alu_to_scalar.c \
> >> nir/nir_lower_atomics.c \
> >> nir/nir_lower_bitmap.c \
> >> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> >> index ff7c422..49e8cd8 100644
> >> --- a/src/compiler/nir/nir.h
> >> +++ b/src/compiler/nir/nir.h
> >> @@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
> >>  }
> >>
> >>  typedef struct {
> >> +   nir_if *nif;
> >> +
> >> +   nir_instr *conditional_instr;
> >> +
> >> +   struct list_head loop_terminator_link;
> >> +} nir_loop_terminator;
> >> +
> >> +typedef struct {
> >> +   /* Number of instructions in the loop */
> >> +   unsigned num_instructions;
> >> +
> >> +   /* How many times the loop is run (if known) */
> >> +   unsigned trip_count;
> >> +   bool is_trip_count_known;
> >
> >
> > We could use 0 or -1 to indicate "I don't know trip count" instead of an
> > extra boolean.  Not sure that it matters much.
> >
> >>
> >> +
> >> +   /* Unroll the loop regardless of its size */
> >> +   bool force_unroll;
> >
> >
> > It seems a bit odd to have this decide to force-unroll.  This is an
> analysis
> > pass, not a "make decisions" pass.
> >
> >>
> >> +
> >> +   nir_loop_terminator *limiting_terminator;
> >> +
> >> +   /* A list of loop_terminators terminating this loop. */
> >> +   struct list_head loop_terminator_list;
> >> +} nir_loop_info;
> >> +
> >> +typedef struct {
> >> nir_cf_node cf_node;
> >>
> >> struct exec_list body; /** < list of nir_cf_node */
> >> +
> >> +   nir_loop_info *info;
> >>  } nir_loop;
> >>
> >>  static inline nir_cf_node *
> >> @@ -1576,6 +1603,7 @@ typedef enum {
> >> nir_metadata_dominance = 0x2,
> >> nir_metadata_live_ssa_defs = 0x4,
> >> nir_metadata_not_properly_reset = 0x8,
> >> +   nir_metadata_loop_analysis = 0x16,
> >>  } nir_metadata;
> >>
> >>  typedef struct {
> >> @@ -1758,6 +1786,8 @@ typedef struct nir_shader_compiler_options {
> >>  * information must be inferred from the list of input
> nir_variables.
> >>  */
> >> bool use_interpolated_input_intrinsics;
> >> +
> >> +   unsigned max_unroll_iterations;
> >>  } nir_shader_compiler_options;
> >>
> >>  typedef struct nir_shader_info {
> >> @@ -1962,7 +1992,7 @@ nir_loop *nir_loop_create(nir_shader *shader);
> >>  nir_function_impl *nir_cf_node_get_function(nir_cf_node *node);
> >>
> >>  /** requests that the given pieces of metadata be generated */
> >> -void 

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Connor Abbott]

On Fri, Sep 16, 2016 at 6:25 PM, Jason Ekstrand  wrote:
> On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri
>  wrote:
>>
>> From: Thomas Helland 
>>
>> This pass detects induction variables and calculates the
>> trip count of loops to be used for loop unrolling.
>>
>> I've removed support for float induction values for now, for the
>> simple reason that they don't appear in my shader-db collection,
>> and so I don't see it as common enough that we want to pollute the
>> pass with this in the initial version.
>>
>> V2: Rebase, adapt to removal of function overloads
>>
>> V3: (Timothy Arceri)
>>  - don't try to find trip count if loop terminator conditional is a phi
>>  - fix trip count for do-while loops
>>  - replace conditional type != alu assert with return
>>  - disable unrolling of loops with continues
>>  - multiple fixes to memory allocation, stop leaking and don't destroy
>>structs we want to use for unrolling.
>>  - fix iteration count bugs when induction var not on RHS of condition
>>  - add FIXME for && conditions
>>  - calculate trip count for unsigned induction/limit vars
>>
>> V4:
>> - count instructions in a loop
>> - set the limiting_terminator even if we can't find the trip count for
>>  all terminators. This is needed for complex unrolling where we handle
>>  2 terminators and the trip count is unknown for one of them.
>> - restruct structs so we don't keep information not required after
>>  analysis and remove dead fields.
>> - force unrolling in some cases as per the rules in the GLSL IR pass
>> ---
>>  src/compiler/Makefile.sources   |2 +
>>  src/compiler/nir/nir.h  |   36 +-
>>  src/compiler/nir/nir_loop_analyze.c | 1012
>> +++
>>  src/compiler/nir/nir_metadata.c |8 +-
>>  4 files changed, 1056 insertions(+), 2 deletions(-)
>>  create mode 100644 src/compiler/nir/nir_loop_analyze.c
>>
>> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
>> index f5b4f9c..7ed26a9 100644
>> --- a/src/compiler/Makefile.sources
>> +++ b/src/compiler/Makefile.sources
>> @@ -190,6 +190,8 @@ NIR_FILES = \
>> nir/nir_intrinsics.c \
>> nir/nir_intrinsics.h \
>> nir/nir_liveness.c \
>> +   nir/nir_loop_analyze.c \
>> +   nir/nir_loop_analyze.h \
>> nir/nir_lower_alu_to_scalar.c \
>> nir/nir_lower_atomics.c \
>> nir/nir_lower_bitmap.c \
>> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
>> index ff7c422..49e8cd8 100644
>> --- a/src/compiler/nir/nir.h
>> +++ b/src/compiler/nir/nir.h
>> @@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
>>  }
>>
>>  typedef struct {
>> +   nir_if *nif;
>> +
>> +   nir_instr *conditional_instr;
>> +
>> +   struct list_head loop_terminator_link;
>> +} nir_loop_terminator;
>> +
>> +typedef struct {
>> +   /* Number of instructions in the loop */
>> +   unsigned num_instructions;
>> +
>> +   /* How many times the loop is run (if known) */
>> +   unsigned trip_count;
>> +   bool is_trip_count_known;
>
>
> We could use 0 or -1 to indicate "I don't know trip count" instead of an
> extra boolean.  Not sure that it matters much.
>
>>
>> +
>> +   /* Unroll the loop regardless of its size */
>> +   bool force_unroll;
>
>
> It seems a bit odd to have this decide to force-unroll.  This is an analysis
> pass, not a "make decisions" pass.
>
>>
>> +
>> +   nir_loop_terminator *limiting_terminator;
>> +
>> +   /* A list of loop_terminators terminating this loop. */
>> +   struct list_head loop_terminator_list;
>> +} nir_loop_info;
>> +
>> +typedef struct {
>> nir_cf_node cf_node;
>>
>> struct exec_list body; /** < list of nir_cf_node */
>> +
>> +   nir_loop_info *info;
>>  } nir_loop;
>>
>>  static inline nir_cf_node *
>> @@ -1576,6 +1603,7 @@ typedef enum {
>> nir_metadata_dominance = 0x2,
>> nir_metadata_live_ssa_defs = 0x4,
>> nir_metadata_not_properly_reset = 0x8,
>> +   nir_metadata_loop_analysis = 0x16,
>>  } nir_metadata;
>>
>>  typedef struct {
>> @@ -1758,6 +1786,8 @@ typedef struct nir_shader_compiler_options {
>>  * information must be inferred from the list of input nir_variables.
>>  */
>> bool use_interpolated_input_intrinsics;
>> +
>> +   unsigned max_unroll_iterations;
>>  } nir_shader_compiler_options;
>>
>>  typedef struct nir_shader_info {
>> @@ -1962,7 +1992,7 @@ nir_loop *nir_loop_create(nir_shader *shader);
>>  nir_function_impl *nir_cf_node_get_function(nir_cf_node *node);
>>
>>  /** requests that the given pieces of metadata be generated */
>> -void nir_metadata_require(nir_function_impl *impl, nir_metadata
>> required);
>> +void nir_metadata_require(nir_function_impl *impl, nir_metadata required,
>> ...);
>>  /** dirties all but the preserved metadata */
>>  void nir_metadata_preserve(nir_function_impl *impl, nir_metadata
>> preserved);
>>
>> @@ -2559,6 +2589,10 @@ void 

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Timothy Arceri]

On Sat, 2016-09-17 at 09:40 +1000, Timothy Arceri wrote:
> On Fri, 2016-09-16 at 15:25 -0700, Jason Ekstrand wrote:
> > > > On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri  wrote:
> > > > > > From: Thomas Helland 
> > 
> > 

snip

> 
> >  
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 
+      return -1;

+

+   /* do-while loops can increment the starting value before the condition is

+    * checked. e.g.

+    *

+    *    do {

+    *        ndx++;

+    *     } while (ndx < 3);

+    *

+    * Here we check if the induction variable is used directly by the loop

+    * condition and if so we assume we need to step the initial value.

+    */

+   bool increment_before = false;

+   if (cond_alu->src[0].src.ssa == alu_def->def ||

+       cond_alu->src[1].src.ssa == alu_def->def) {

+      increment_before = true;
> > 
> > Is there a reason why this can't be handled as "trip_count + 1"?  This 
> > seems way overcomplicated.
> 
> Yes there is. We don't know that we will increment by 1 it could be by 10, 
> also if we support more opts we may have to do a mul etc.
> We could set the initial value here but I decided to keep it all in 
> get_iteration() I guess I could move this logic there also.
> 
Ingonre that I see what you are getting at but it would be trip_count -
1. That should be ok if sub is lowered as you say.
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Timothy Arceri]

On Fri, 2016-09-16 at 17:01 +0200, Erik Faye-Lund wrote:
> On Thu, Sep 15, 2016 at 9:03 AM, Timothy Arceri
>  wrote:
> > 
> > +   const int bias[] = { -1, 1, 1 };
> > +
> > +   for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) {
> > +  iter_int = iter_int + bias[i];
> > +
> > +  switch (cond_op) {
> > +  case nir_op_ige:
> > +  case nir_op_ilt:
> > +  case nir_op_ieq:
> > +  case nir_op_ine:
> > + if (itest_interations(iter_int, step, limit, cond_op,
> > initial_val,
> > +   limit_rhs)) {
> > +return iter_int;
> > + }
> > + break;
> > +  case nir_op_uge:
> > +  case nir_op_ult:
> > + if (utest_interations(iter_int, step, limit, cond_op,
> > +   (uint32_t) initial_val, limit_rhs))
> > {
> > +return iter_int;
> > + }
> > + break;
> > +  default:
> > + return -1;
> > +  }
> > +   }
> 
> Can't this be easier written as:

Probably. I believe Thomas just copied this code from the GLSL IR pass.

> 
> for (int i = iter_int - 1; i <= iter_int + 1; ++i)
> {
> switch (cond_op) {
> [...]
> if (itest_interations(i, step, limit, cond_op, initial_val,
> limit_rhs))
>  return i;
> [...]
> ?
> ___
> mesa-dev mailing list
> mesa-dev@lists.freedesktop.org
> https://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 02/10] nir: Add a loop analysis pass

[Jason Ekstrand]

On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri <
timothy.arc...@collabora.com> wrote:

> From: Thomas Helland 
>
> This pass detects induction variables and calculates the
> trip count of loops to be used for loop unrolling.
>
> I've removed support for float induction values for now, for the
> simple reason that they don't appear in my shader-db collection,
> and so I don't see it as common enough that we want to pollute the
> pass with this in the initial version.
>
> V2: Rebase, adapt to removal of function overloads
>
> V3: (Timothy Arceri)
>  - don't try to find trip count if loop terminator conditional is a phi
>  - fix trip count for do-while loops
>  - replace conditional type != alu assert with return
>  - disable unrolling of loops with continues
>  - multiple fixes to memory allocation, stop leaking and don't destroy
>structs we want to use for unrolling.
>  - fix iteration count bugs when induction var not on RHS of condition
>  - add FIXME for && conditions
>  - calculate trip count for unsigned induction/limit vars
>
> V4:
> - count instructions in a loop
> - set the limiting_terminator even if we can't find the trip count for
>  all terminators. This is needed for complex unrolling where we handle
>  2 terminators and the trip count is unknown for one of them.
> - restruct structs so we don't keep information not required after
>  analysis and remove dead fields.
> - force unrolling in some cases as per the rules in the GLSL IR pass
> ---
>  src/compiler/Makefile.sources   |2 +
>  src/compiler/nir/nir.h  |   36 +-
>  src/compiler/nir/nir_loop_analyze.c | 1012 ++
> +
>  src/compiler/nir/nir_metadata.c |8 +-
>  4 files changed, 1056 insertions(+), 2 deletions(-)
>  create mode 100644 src/compiler/nir/nir_loop_analyze.c
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index f5b4f9c..7ed26a9 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -190,6 +190,8 @@ NIR_FILES = \
> nir/nir_intrinsics.c \
> nir/nir_intrinsics.h \
> nir/nir_liveness.c \
> +   nir/nir_loop_analyze.c \
> +   nir/nir_loop_analyze.h \
> nir/nir_lower_alu_to_scalar.c \
> nir/nir_lower_atomics.c \
> nir/nir_lower_bitmap.c \
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index ff7c422..49e8cd8 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
>  }
>
>  typedef struct {
> +   nir_if *nif;
> +
> +   nir_instr *conditional_instr;
> +
> +   struct list_head loop_terminator_link;
> +} nir_loop_terminator;
> +
> +typedef struct {
> +   /* Number of instructions in the loop */
> +   unsigned num_instructions;
> +
> +   /* How many times the loop is run (if known) */
> +   unsigned trip_count;
> +   bool is_trip_count_known;
>

We could use 0 or -1 to indicate "I don't know trip count" instead of an
extra boolean.  Not sure that it matters much.


> +
> +   /* Unroll the loop regardless of its size */
> +   bool force_unroll;
>

It seems a bit odd to have this decide to force-unroll.  This is an
analysis pass, not a "make decisions" pass.


> +
> +   nir_loop_terminator *limiting_terminator;
> +
> +   /* A list of loop_terminators terminating this loop. */
> +   struct list_head loop_terminator_list;
> +} nir_loop_info;
> +
> +typedef struct {
> nir_cf_node cf_node;
>
> struct exec_list body; /** < list of nir_cf_node */
> +
> +   nir_loop_info *info;
>  } nir_loop;
>
>  static inline nir_cf_node *
> @@ -1576,6 +1603,7 @@ typedef enum {
> nir_metadata_dominance = 0x2,
> nir_metadata_live_ssa_defs = 0x4,
> nir_metadata_not_properly_reset = 0x8,
> +   nir_metadata_loop_analysis = 0x16,
>  } nir_metadata;
>
>  typedef struct {
> @@ -1758,6 +1786,8 @@ typedef struct nir_shader_compiler_options {
>  * information must be inferred from the list of input nir_variables.
>  */
> bool use_interpolated_input_intrinsics;
> +
> +   unsigned max_unroll_iterations;
>  } nir_shader_compiler_options;
>
>  typedef struct nir_shader_info {
> @@ -1962,7 +1992,7 @@ nir_loop *nir_loop_create(nir_shader *shader);
>  nir_function_impl *nir_cf_node_get_function(nir_cf_node *node);
>
>  /** requests that the given pieces of metadata be generated */
> -void nir_metadata_require(nir_function_impl *impl, nir_metadata
> required);
> +void nir_metadata_require(nir_function_impl *impl, nir_metadata
> required, ...);
>  /** dirties all but the preserved metadata */
>  void nir_metadata_preserve(nir_function_impl *impl, nir_metadata
> preserved);
>
> @@ -2559,6 +2589,10 @@ void nir_lower_double_pack(nir_shader *shader);
>  bool nir_normalize_cubemap_coords(nir_shader *shader);
>
>  void nir_live_ssa_defs_impl(nir_function_impl *impl);
> +
> +void nir_loop_analyze_impl(nir_function_impl *impl,
> +   

Re: [Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Erik Faye-Lund]

On Thu, Sep 15, 2016 at 9:03 AM, Timothy Arceri
 wrote:
> +   const int bias[] = { -1, 1, 1 };
> +
> +   for (unsigned i = 0; i < ARRAY_SIZE(bias); i++) {
> +  iter_int = iter_int + bias[i];
> +
> +  switch (cond_op) {
> +  case nir_op_ige:
> +  case nir_op_ilt:
> +  case nir_op_ieq:
> +  case nir_op_ine:
> + if (itest_interations(iter_int, step, limit, cond_op, initial_val,
> +   limit_rhs)) {
> +return iter_int;
> + }
> + break;
> +  case nir_op_uge:
> +  case nir_op_ult:
> + if (utest_interations(iter_int, step, limit, cond_op,
> +   (uint32_t) initial_val, limit_rhs)) {
> +return iter_int;
> + }
> + break;
> +  default:
> + return -1;
> +  }
> +   }

Can't this be easier written as:

for (int i = iter_int - 1; i <= iter_int + 1; ++i)
{
switch (cond_op) {
[...]
if (itest_interations(i, step, limit, cond_op, initial_val, limit_rhs))
 return i;
[...]
?
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

[Mesa-dev] [PATCH 02/10] nir: Add a loop analysis pass

[Timothy Arceri]

From: Thomas Helland 

This pass detects induction variables and calculates the
trip count of loops to be used for loop unrolling.

I've removed support for float induction values for now, for the
simple reason that they don't appear in my shader-db collection,
and so I don't see it as common enough that we want to pollute the
pass with this in the initial version.

V2: Rebase, adapt to removal of function overloads

V3: (Timothy Arceri)
 - don't try to find trip count if loop terminator conditional is a phi
 - fix trip count for do-while loops
 - replace conditional type != alu assert with return
 - disable unrolling of loops with continues
 - multiple fixes to memory allocation, stop leaking and don't destroy
   structs we want to use for unrolling.
 - fix iteration count bugs when induction var not on RHS of condition
 - add FIXME for && conditions
 - calculate trip count for unsigned induction/limit vars

V4:
- count instructions in a loop
- set the limiting_terminator even if we can't find the trip count for
 all terminators. This is needed for complex unrolling where we handle
 2 terminators and the trip count is unknown for one of them.
- restruct structs so we don't keep information not required after
 analysis and remove dead fields.
- force unrolling in some cases as per the rules in the GLSL IR pass
---
 src/compiler/Makefile.sources   |2 +
 src/compiler/nir/nir.h  |   36 +-
 src/compiler/nir/nir_loop_analyze.c | 1012 +++
 src/compiler/nir/nir_metadata.c |8 +-
 4 files changed, 1056 insertions(+), 2 deletions(-)
 create mode 100644 src/compiler/nir/nir_loop_analyze.c

diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
index f5b4f9c..7ed26a9 100644
--- a/src/compiler/Makefile.sources
+++ b/src/compiler/Makefile.sources
@@ -190,6 +190,8 @@ NIR_FILES = \
nir/nir_intrinsics.c \
nir/nir_intrinsics.h \
nir/nir_liveness.c \
+   nir/nir_loop_analyze.c \
+   nir/nir_loop_analyze.h \
nir/nir_lower_alu_to_scalar.c \
nir/nir_lower_atomics.c \
nir/nir_lower_bitmap.c \
diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
index ff7c422..49e8cd8 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -1549,9 +1549,36 @@ nir_if_last_else_node(nir_if *if_stmt)
 }
 
 typedef struct {
+   nir_if *nif;
+
+   nir_instr *conditional_instr;
+
+   struct list_head loop_terminator_link;
+} nir_loop_terminator;
+
+typedef struct {
+   /* Number of instructions in the loop */
+   unsigned num_instructions;
+
+   /* How many times the loop is run (if known) */
+   unsigned trip_count;
+   bool is_trip_count_known;
+
+   /* Unroll the loop regardless of its size */
+   bool force_unroll;
+
+   nir_loop_terminator *limiting_terminator;
+
+   /* A list of loop_terminators terminating this loop. */
+   struct list_head loop_terminator_list;
+} nir_loop_info;
+
+typedef struct {
nir_cf_node cf_node;
 
struct exec_list body; /** < list of nir_cf_node */
+
+   nir_loop_info *info;
 } nir_loop;
 
 static inline nir_cf_node *
@@ -1576,6 +1603,7 @@ typedef enum {
nir_metadata_dominance = 0x2,
nir_metadata_live_ssa_defs = 0x4,
nir_metadata_not_properly_reset = 0x8,
+   nir_metadata_loop_analysis = 0x16,
 } nir_metadata;
 
 typedef struct {
@@ -1758,6 +1786,8 @@ typedef struct nir_shader_compiler_options {
 * information must be inferred from the list of input nir_variables.
 */
bool use_interpolated_input_intrinsics;
+
+   unsigned max_unroll_iterations;
 } nir_shader_compiler_options;
 
 typedef struct nir_shader_info {
@@ -1962,7 +1992,7 @@ nir_loop *nir_loop_create(nir_shader *shader);
 nir_function_impl *nir_cf_node_get_function(nir_cf_node *node);
 
 /** requests that the given pieces of metadata be generated */
-void nir_metadata_require(nir_function_impl *impl, nir_metadata required);
+void nir_metadata_require(nir_function_impl *impl, nir_metadata required, ...);
 /** dirties all but the preserved metadata */
 void nir_metadata_preserve(nir_function_impl *impl, nir_metadata preserved);
 
@@ -2559,6 +2589,10 @@ void nir_lower_double_pack(nir_shader *shader);
 bool nir_normalize_cubemap_coords(nir_shader *shader);
 
 void nir_live_ssa_defs_impl(nir_function_impl *impl);
+
+void nir_loop_analyze_impl(nir_function_impl *impl,
+   nir_variable_mode indirect_mask);
+
 bool nir_ssa_defs_interfere(nir_ssa_def *a, nir_ssa_def *b);
 
 void nir_convert_to_ssa_impl(nir_function_impl *impl);
diff --git a/src/compiler/nir/nir_loop_analyze.c 
b/src/compiler/nir/nir_loop_analyze.c
new file mode 100644
index 000..6bea9e5
--- /dev/null
+++ b/src/compiler/nir/nir_loop_analyze.c
@@ -0,0 +1,1012 @@
+/*
+ * Copyright © 2015 Thomas Helland
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to