Re: [Mesa-dev] [PATCH 03/12] nir: Add a loop analysis pass

[Jason Ekstrand]

I made a bunch more comments but they're all cosmetic.  The one
non-cosmetic thing I'd like to see changed before we merge is that we fix
the case where the break is in the else.  Feel free to grab the tip of my
jenkins_vulkan branch and squash it in if you like the approach I took.  Or
you can do something slightly different so long as it has the same effect.

Reviewed-by: Jason Ekstrand 

--Jason

On Sun, Dec 18, 2016 at 9:47 PM, 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: (Timothy Arceri)
> - 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
>
> V5: (Timothy Arceri)
> - fix metadata mask value 0x10 vs 0x16
>
> V6: (Timothy Arceri)
> - merge loop_variable and nir_loop_variable structs and lists suggested by
> Jason
> - remove induction var hash table and store pointer to induction
> information in
>   the loop_variable suggested by Jason.
> - use lowercase list_addtail() suggested by Jason.
> - tidy up init_loop_block() as per Jasons suggestions.
> - replace switch with nir_op_infos[alu->op].num_inputs == 2 in
>   is_var_basic_induction_var() as suggested by Jason.
> - use nir_block_last_instr() in and rename foreach_cf_node_ex_loop() as
> suggested
>   by Jason.
> - fix else check for is_trivial_loop_terminator() as per Connors
> suggetions.
> - simplify offset for induction valiables incremented before the exit
> conditions is
>   checked.
> - replace nir_op_isub check with assert() as it should have been lowered
> away.
>
> V7: (Timothy Arceri)
> - use rzalloc() on nir_loop struct creation. Worked previously because
> ralloc()
>   was broken and always zeroed the struct.
> - fix cf_node_find_loop_jumps() to find jumps when loops contain
>   nested if statements. Code is tidier as a result.
>
> V8: (Timothy Arceri)
> - move is_trivial_loop_terminator() to nir.h so we can use it to assert is
>   the loop unroll pass
> - fix analysis to not bail when looking for terminator when the break is
> in the else
>   rather then the if
> - added new loop terminator fields: break_block, continue_from_block and
>   continue_from_then so we don't have to gather these when doing unrolling.
> - get correct array length when forcing unrolling of variables
>   indexed arrays that are the same size as the iteration count
> - add support for induction variables of type float
> - update trival loop terminator check to allow an if containing
>   instructions as long as both branches contain only a single
>   block.
>
> V9:
>  - bunch of tidy ups and simplifications suggested by Jason.
>  - rewrote trivial terminator detection, now the only restriction is there
>must be no nested jumps, anything else goes.
>  - rewrote the iteration test to use nir_eval_const_opcode().
>  - count instruction properly even when forcing an unroll.
>  - bunch of other tidy ups and simplifications.
> ---
>  src/compiler/Makefile.sources   |   2 +
>  src/compiler/nir/nir.c  |   2 +-
>  src/compiler/nir/nir.h  |  41 +-
>  src/compiler/nir/nir_loop_analyze.c | 852 ++
> ++
>  src/compiler/nir/nir_loop_analyze.h |  92 
>  src/compiler/nir/nir_metadata.c |   8 +-
>  6 files changed, 994 insertions(+), 3 deletions(-)
>  create mode 100644 src/compiler/nir/nir_loop_analyze.c
>  create mode 100644 src/compiler/nir/nir_loop_analyze.h
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index 17b15de..ca8a056 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -193,6 +193,8 @@ NIR_FILES = \
> nir/nir_intrinsics.c \
> nir/nir_intrinsics.h 

[Mesa-dev] [PATCH 03/12] 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: (Timothy Arceri)
- 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

V5: (Timothy Arceri)
- fix metadata mask value 0x10 vs 0x16

V6: (Timothy Arceri)
- merge loop_variable and nir_loop_variable structs and lists suggested by Jason
- remove induction var hash table and store pointer to induction information in
  the loop_variable suggested by Jason.
- use lowercase list_addtail() suggested by Jason.
- tidy up init_loop_block() as per Jasons suggestions.
- replace switch with nir_op_infos[alu->op].num_inputs == 2 in
  is_var_basic_induction_var() as suggested by Jason.
- use nir_block_last_instr() in and rename foreach_cf_node_ex_loop() as 
suggested
  by Jason.
- fix else check for is_trivial_loop_terminator() as per Connors suggetions.
- simplify offset for induction valiables incremented before the exit 
conditions is
  checked.
- replace nir_op_isub check with assert() as it should have been lowered away.

V7: (Timothy Arceri)
- use rzalloc() on nir_loop struct creation. Worked previously because ralloc()
  was broken and always zeroed the struct.
- fix cf_node_find_loop_jumps() to find jumps when loops contain
  nested if statements. Code is tidier as a result.

V8: (Timothy Arceri)
- move is_trivial_loop_terminator() to nir.h so we can use it to assert is
  the loop unroll pass
- fix analysis to not bail when looking for terminator when the break is in the 
else
  rather then the if
- added new loop terminator fields: break_block, continue_from_block and
  continue_from_then so we don't have to gather these when doing unrolling.
- get correct array length when forcing unrolling of variables
  indexed arrays that are the same size as the iteration count
- add support for induction variables of type float
- update trival loop terminator check to allow an if containing
  instructions as long as both branches contain only a single
  block.

V9:
 - bunch of tidy ups and simplifications suggested by Jason.
 - rewrote trivial terminator detection, now the only restriction is there
   must be no nested jumps, anything else goes.
 - rewrote the iteration test to use nir_eval_const_opcode().
 - count instruction properly even when forcing an unroll.
 - bunch of other tidy ups and simplifications.
---
 src/compiler/Makefile.sources   |   2 +
 src/compiler/nir/nir.c  |   2 +-
 src/compiler/nir/nir.h  |  41 +-
 src/compiler/nir/nir_loop_analyze.c | 852 
 src/compiler/nir/nir_loop_analyze.h |  92 
 src/compiler/nir/nir_metadata.c |   8 +-
 6 files changed, 994 insertions(+), 3 deletions(-)
 create mode 100644 src/compiler/nir/nir_loop_analyze.c
 create mode 100644 src/compiler/nir/nir_loop_analyze.h

diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
index 17b15de..ca8a056 100644
--- a/src/compiler/Makefile.sources
+++ b/src/compiler/Makefile.sources
@@ -193,6 +193,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.c b/src/compiler/nir/nir.c
index 2d882f7..2c3531c 100644
--- a/src/compiler/nir/nir.c
+++ b/src/compiler/nir/nir.c
@@ -393,7 +393,7 @@ nir_if_create(nir_shader *shader)
 nir_loop *
 nir_loop_create(nir_shader *shader)
 {
-   nir_loop *loop = ralloc(shader, nir_loop);
+   nir_loop *loop = rzalloc(shader, nir_loop);
 
cf_init(>cf_node, nir_cf_node_loop);
 
diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
index ba88a24..28010aa 100644
--- 

Re: [Mesa-dev] [PATCH 03/12] nir: Add a loop analysis pass

[Timothy Arceri]

On Sat, 2016-08-27 at 14:08 +0200, Thomas Helland wrote:
> 2016-08-27 8:03 GMT+02:00 Timothy Arceri  m>:
> > 
> > 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.
> >  - find induction var when copy propagation disabled
> >  - fix iteration count bugs when induction var not on RHS of
> > condition
> >  - add FIXME for && conditions
> >  - calculate trip count for unsigned induction/limit vars
> > ---
> >  src/compiler/Makefile.sources   |   2 +
> >  src/compiler/nir/nir.h  |  75 +++
> >  src/compiler/nir/nir_loop_analyze.c | 922
> > 
> >  3 files changed, 999 insertions(+)
> >  create mode 100644 src/compiler/nir/nir_loop_analyze.c
> > 
> > diff --git a/src/compiler/Makefile.sources
> > b/src/compiler/Makefile.sources
> > index cfb6359..1bf1c52 100644
> > --- a/src/compiler/Makefile.sources
> > +++ b/src/compiler/Makefile.sources
> > @@ -187,6 +187,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 e3e06b1..f85e829 100644
> > --- a/src/compiler/nir/nir.h
> > +++ b/src/compiler/nir/nir.h
> > @@ -1541,10 +1541,78 @@ nir_if_last_else_node(nir_if *if_stmt)
> > return exec_node_data(nir_cf_node, tail, node);
> >  }
> > 
> > +typedef enum {
> > +   undefined,
> > +   invariant,
> > +   basic_induction
> > +} nir_loop_variable_type;
> > +
> > +typedef struct {
> > +   /* The ssa_def associated with this info */
> > +   nir_ssa_def *def;
> > +
> > +   /* The type of this ssa_def */
> > +   nir_loop_variable_type type;
> > +
> > +   /* Link to the loop_variable list for the loop */
> > +   struct list_head loop_vars_link;
> > +
> > +   /* A link for a list of invariant variables */
> > +   struct list_head invariant_link;
> > +
> > +   /* A link for a list of induction variables */
> > +   struct list_head induction_link;
> > +
> > +   /* If the ssa-def is constant */
> > +   bool is_constant;
> > +
> > +   bool in_conditional_block;
> > +
> > +   bool in_nested_loop;
> > +} nir_loop_variable;
> > +
> > +typedef struct {
> > +   nir_op alu_op;/* The type of
> > alu-operation*/
> > +   nir_loop_variable *alu_def;   /* The def of the
> > alu-operation */
> > +   nir_loop_variable *invariant; /* The invariant
> > alu-operand*/
> > +   nir_loop_variable *phi;   /* The other alu-
> > operand*/
> > +   nir_loop_variable *def_outside_loop;  /* The phi-src
> > outside the loop */
> > +} nir_basic_induction_var;
> > +
> > +typedef struct {
> > +   nir_if *nif;
> > +
> > +   /* Some more suitable fields like maybe indicated trip-count?
> > */
> > +   nir_instr *conditional_instr;
> 
> This question here should probably be answered, or removed.
> 
> > 
> > +
> > +   struct list_head loop_terminator_link;
> > +} nir_loop_terminator;
> > +
> > +typedef struct {
> > +   /* Loop_variable for all ssa_defs in loop */
> > +   struct list_head loop_vars_list;
> > +
> > +   /* How many times the loop is run (if known) */
> > +   uint32_t trip_count;
> > +   bool is_trip_count_known;
> > +
> > +   nir_loop_terminator *limiting_terminator;
> > +
> > +   /* A list of loop_terminators terminating this loop XXX: These
> > (apart from the limiting terminator) can be dead-code-eliminated */
> > +   struct list_head loop_terminator_list;
> > +
> 
> Line wrapping.
> 
> > 
> > +   /* The ssa_defs that are invariant */
> > +   struct list_head invariant_list;
> > +
> > +   struct hash_table *var_to_basic_ind;
> > +} 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 *
> > @@ -1569,6 +1637,7 @@ typedef enum {
> > nir_metadata_dominance = 0x2,
> > nir_metadata_live_ssa_defs = 0x4,
> > 

Re: [Mesa-dev] [PATCH 03/12] nir: Add a loop analysis pass

[Thomas Helland]

2016-08-27 8:03 GMT+02:00 Timothy Arceri :
> 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.
>  - find induction var when copy propagation disabled
>  - fix iteration count bugs when induction var not on RHS of condition
>  - add FIXME for && conditions
>  - calculate trip count for unsigned induction/limit vars
> ---
>  src/compiler/Makefile.sources   |   2 +
>  src/compiler/nir/nir.h  |  75 +++
>  src/compiler/nir/nir_loop_analyze.c | 922 
> 
>  3 files changed, 999 insertions(+)
>  create mode 100644 src/compiler/nir/nir_loop_analyze.c
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index cfb6359..1bf1c52 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -187,6 +187,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 e3e06b1..f85e829 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -1541,10 +1541,78 @@ nir_if_last_else_node(nir_if *if_stmt)
> return exec_node_data(nir_cf_node, tail, node);
>  }
>
> +typedef enum {
> +   undefined,
> +   invariant,
> +   basic_induction
> +} nir_loop_variable_type;
> +
> +typedef struct {
> +   /* The ssa_def associated with this info */
> +   nir_ssa_def *def;
> +
> +   /* The type of this ssa_def */
> +   nir_loop_variable_type type;
> +
> +   /* Link to the loop_variable list for the loop */
> +   struct list_head loop_vars_link;
> +
> +   /* A link for a list of invariant variables */
> +   struct list_head invariant_link;
> +
> +   /* A link for a list of induction variables */
> +   struct list_head induction_link;
> +
> +   /* If the ssa-def is constant */
> +   bool is_constant;
> +
> +   bool in_conditional_block;
> +
> +   bool in_nested_loop;
> +} nir_loop_variable;
> +
> +typedef struct {
> +   nir_op alu_op;/* The type of 
> alu-operation*/
> +   nir_loop_variable *alu_def;   /* The def of the 
> alu-operation */
> +   nir_loop_variable *invariant; /* The invariant 
> alu-operand*/
> +   nir_loop_variable *phi;   /* The other alu-operand
> */
> +   nir_loop_variable *def_outside_loop;  /* The phi-src outside the 
> loop */
> +} nir_basic_induction_var;
> +
> +typedef struct {
> +   nir_if *nif;
> +
> +   /* Some more suitable fields like maybe indicated trip-count? */
> +   nir_instr *conditional_instr;

This question here should probably be answered, or removed.

> +
> +   struct list_head loop_terminator_link;
> +} nir_loop_terminator;
> +
> +typedef struct {
> +   /* Loop_variable for all ssa_defs in loop */
> +   struct list_head loop_vars_list;
> +
> +   /* How many times the loop is run (if known) */
> +   uint32_t trip_count;
> +   bool is_trip_count_known;
> +
> +   nir_loop_terminator *limiting_terminator;
> +
> +   /* A list of loop_terminators terminating this loop XXX: These (apart 
> from the limiting terminator) can be dead-code-eliminated */
> +   struct list_head loop_terminator_list;
> +

Line wrapping.

> +   /* The ssa_defs that are invariant */
> +   struct list_head invariant_list;
> +
> +   struct hash_table *var_to_basic_ind;
> +} 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 *
> @@ -1569,6 +1637,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 {
> @@ -1751,6 +1820,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;
>  } 

[Mesa-dev] [PATCH 03/12] nir: Add a loop analysis pass

[Timothy Arceri]

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.
 - find induction var when copy propagation disabled
 - fix iteration count bugs when induction var not on RHS of condition
 - add FIXME for && conditions
 - calculate trip count for unsigned induction/limit vars
---
 src/compiler/Makefile.sources   |   2 +
 src/compiler/nir/nir.h  |  75 +++
 src/compiler/nir/nir_loop_analyze.c | 922 
 3 files changed, 999 insertions(+)
 create mode 100644 src/compiler/nir/nir_loop_analyze.c

diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
index cfb6359..1bf1c52 100644
--- a/src/compiler/Makefile.sources
+++ b/src/compiler/Makefile.sources
@@ -187,6 +187,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 e3e06b1..f85e829 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -1541,10 +1541,78 @@ nir_if_last_else_node(nir_if *if_stmt)
return exec_node_data(nir_cf_node, tail, node);
 }
 
+typedef enum {
+   undefined,
+   invariant,
+   basic_induction
+} nir_loop_variable_type;
+
+typedef struct {
+   /* The ssa_def associated with this info */
+   nir_ssa_def *def;
+
+   /* The type of this ssa_def */
+   nir_loop_variable_type type;
+
+   /* Link to the loop_variable list for the loop */
+   struct list_head loop_vars_link;
+
+   /* A link for a list of invariant variables */
+   struct list_head invariant_link;
+
+   /* A link for a list of induction variables */
+   struct list_head induction_link;
+
+   /* If the ssa-def is constant */
+   bool is_constant;
+
+   bool in_conditional_block;
+
+   bool in_nested_loop;
+} nir_loop_variable;
+
+typedef struct {
+   nir_op alu_op;/* The type of alu-operation  
  */
+   nir_loop_variable *alu_def;   /* The def of the 
alu-operation */
+   nir_loop_variable *invariant; /* The invariant alu-operand  
  */
+   nir_loop_variable *phi;   /* The other alu-operand  
  */
+   nir_loop_variable *def_outside_loop;  /* The phi-src outside the 
loop */
+} nir_basic_induction_var;
+
+typedef struct {
+   nir_if *nif;
+
+   /* Some more suitable fields like maybe indicated trip-count? */
+   nir_instr *conditional_instr;
+
+   struct list_head loop_terminator_link;
+} nir_loop_terminator;
+
+typedef struct {
+   /* Loop_variable for all ssa_defs in loop */
+   struct list_head loop_vars_list;
+
+   /* How many times the loop is run (if known) */
+   uint32_t trip_count;
+   bool is_trip_count_known;
+
+   nir_loop_terminator *limiting_terminator;
+
+   /* A list of loop_terminators terminating this loop XXX: These (apart from 
the limiting terminator) can be dead-code-eliminated */
+   struct list_head loop_terminator_list;
+
+   /* The ssa_defs that are invariant */
+   struct list_head invariant_list;
+
+   struct hash_table *var_to_basic_ind;
+} 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 *
@@ -1569,6 +1637,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 {
@@ -1751,6 +1820,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 {
@@ -2542,6 +2613,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);
+void nir_loop_analyze(nir_shader *shader);
+
 bool nir_ssa_defs_interfere(nir_ssa_def *a, nir_ssa_def *b);
 
 void