On Fri, 2016-09-16 at 15:25 -0700, Jason Ekstrand wrote:
> > On Thu, Sep 15, 2016 at 12:03 AM, Timothy Arceri <timothy.arceri@coll
abora.com> wrote:
> > > > From: Thomas Helland <thomashellan...@gmail.com>
> >
> >
> > 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,
+ 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 0000000..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 deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include "nir.h"
+
+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;
+
+ /* 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 {
+ /* A link for the work list */
+ struct list_head process_link;
+
+ bool in_loop;
+
+ nir_loop_variable *nir_loop_var;
+} loop_variable;
+
+typedef struct {
+ bool contains_break;
+ bool contains_continue;
+} loop_jumps;
+
+typedef struct {
+ /* The loop we store information for */
+ nir_loop *loop;
+
+ /* Loop_variable for all ssa_defs in function */
+ loop_variable *loop_vars;
+
+ /* Loop_variable for all ssa_defs in function */
+ nir_loop_variable *nir_loop_vars;
>
> Why are these two separate things? You have two arrays both indexed by
> nir_ssa_def::index and both called loop_vars and one has a pointer to the
> other. Can we just make 1 array?
No really sure. There is other stuff I've removed from this pass Thomas
may have had other ideas for this or just never cleaned it up. Will see
if I can combine them.
>
> > > > > > > > > > > > > > > > > >
+
+ /* A list of the loop_vars to analyze */
+ struct list_head process_list;
+
+ nir_loop_info *info;
+
+ nir_variable_mode indirect_mask;
+
+ struct hash_table *var_to_basic_ind;
>
> Also, this seems like an unneeded level of indirection. Just put a pointer
> in loop_variable that points to the induction var struct.
Sure.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+} loop_info_state;
+
+static loop_variable *
+get_loop_var(nir_ssa_def *value, loop_info_state *state)
+{
+ return &(state->loop_vars[value->index]);
+}
+
+static nir_loop_variable *
+get_nir_loop_var(nir_ssa_def *value, loop_info_state *state)
+{
+ return &(state->nir_loop_vars[value->index]);
+}
+
+typedef struct {
+ loop_info_state *state;
+ bool mark_nested;
+ bool mark_in_conditional;
+} init_loop_state;
+
+static bool
+init_loop_def(nir_ssa_def *def, void *void_init_loop_state)
+{
+ init_loop_state *loop_init_state = void_init_loop_state;
+ loop_variable *var = get_loop_var(def, loop_init_state->state);
+
+ /* Add to the tail of the list. That way we start at the beginning of the
+ * defs in the loop instead of the end when walking the list. This means
+ * less recursive calls. Only add defs that are not in nested loops or
+ * conditional blocks.
+ */
+ if (!(loop_init_state->mark_in_conditional ||
+ loop_init_state->mark_nested))
+ LIST_ADDTAIL(&(var->process_link),
+ &(loop_init_state->state->process_list));
>
> I have a mild preference for the lower-case variants. As I recall, they are
> more for legacy.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+
+ if (loop_init_state->mark_in_conditional)
+ var->nir_loop_var->in_conditional_block = true;
+
+ if (loop_init_state->mark_nested)
+ var->nir_loop_var->in_nested_loop = true;
+
+ var->in_loop = true;
+
+ return true;
+}
+
+static bool
+init_loop_block(nir_block *block, void *void_init_loop_state)
>
> Can we make this function take the actual parameters and limit
> init_loop_state to being the thing we use for init_loop_def. Passing piles
> of pointers through made sense when Thomas originally wrote it but now that
> we have better loop iteration macros, we can just pass arguments.
Sure.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+{
+ init_loop_state *loop_init_state = void_init_loop_state;
+
+ nir_foreach_instr(instr, block)
+ nir_foreach_ssa_def(instr, init_loop_def, loop_init_state);
+
+ return true;
+}
+
+static inline bool
+is_var_alu(loop_variable *var)
+{
+ return (var->nir_loop_var->def->parent_instr->type == nir_instr_type_alu);
+}
+
+static inline bool
+is_var_phi(loop_variable *var)
+{
+ return (var->nir_loop_var->def->parent_instr->type == nir_instr_type_phi);
+}
+
+static inline bool
+is_ssa_def_invariant(nir_ssa_def *def, loop_info_state *state)
+{
+ loop_variable *var = get_loop_var(def, state);
+
+ if (var->nir_loop_var->type == invariant)
+ return true;
+
+ if (!var->in_loop) {
+ var->nir_loop_var->type = invariant;
+ return true;
+ }
+
+ if (var->nir_loop_var->type == basic_induction)
+ return false;
+
+ if (is_var_alu(var)) {
+ nir_alu_instr *alu = nir_instr_as_alu(def->parent_instr);
+
+ for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) {
+ if (!is_ssa_def_invariant(alu->src[i].src.ssa, state))
+ return false;
+ }
+ var->nir_loop_var->type = invariant;
+ return true;
+ }
+
+ /* Phis shouldn't be invariant except if one operand is invariant, and the
+ * other is the phi itself. These should be removed by opt_remove_phis.
+ * load_consts are already set to invariant and constant during init,
+ * and so should return earlier. Remaining op_codes are set undefined.
+ */
+ var->nir_loop_var->type = undefined;
+ return false;
+}
+
+static void
+compute_invariance_information(loop_info_state *state)
+{
+ /* An expression is invariant in a loop L if:
+ * (base cases)
+ * – it’s a constant
+ * – it’s a variable use, all of whose single defs are outside of L
+ * (inductive cases)
+ * – it’s a pure computation all of whose args are loop invariant
+ * – it’s a variable use whose single reaching def, and the
+ * rhs of that def is loop-invariant
+ */
+ bool changes;
+
+ do {
+ changes = false;
+ list_for_each_entry_safe(loop_variable, var,
+ &state->process_list, process_link) {
+
+ if (var->nir_loop_var->in_conditional_block ||
+ var->nir_loop_var->in_nested_loop) {
+ LIST_DEL(&var->process_link);
+ continue;
+ }
+
+ if (is_ssa_def_invariant(var->nir_loop_var->def, state)) {
+ LIST_DEL(&var->process_link);
+ changes = true;
+ }
+ }
+ } while (changes);
+}
+
+static inline bool
+is_var_basic_induction_var(loop_variable *var, loop_info_state *state)
+{
+ if (var->nir_loop_var->type == basic_induction)
+ return true;
+
+ /* We are only interested in checking phi's for the basic induction
+ * variable case as its simple to detect. All basic induction variables
+ * have a phi node
+ */
+ if (!is_var_phi(var))
+ return false;
+
+ nir_phi_instr *phi = nir_instr_as_phi(var->nir_loop_var->def->parent_instr);
+
+ nir_basic_induction_var *biv = rzalloc(state, nir_basic_induction_var);
+ biv->phi = var->nir_loop_var;
+
+ nir_foreach_phi_src(src, phi) {
+ loop_variable *src_var = get_loop_var(src->src.ssa, state);
+
+ /* If one of the sources is in a conditional or nested block then panic.
+ */
+ if (src_var->nir_loop_var->in_conditional_block ||
+ src_var->nir_loop_var->in_nested_loop)
+ break;
+
+ if (!src_var->in_loop)
+ biv->def_outside_loop = src_var->nir_loop_var;
>
> Could we assert biv->def_outside_loop == NULL
>
> > > > > > > > > > > > > > > > > > > > > >
+
+ if (src_var->in_loop && is_var_alu(src_var)) {
+ nir_alu_instr *alu =
+ nir_instr_as_alu(src_var->nir_loop_var->def->parent_instr);
+
+ switch (alu->op) {
+ case nir_op_fadd: case nir_op_iadd: case nir_op_uadd_carry:
+ case nir_op_fsub: case nir_op_isub: case nir_op_usub_borrow:
+ case nir_op_fmul: case nir_op_imul: case nir_op_umul_high:
+ case nir_op_fdiv: case nir_op_idiv: case nir_op_udiv:
>
> Is there a reason why this is an explicit list and not simply
> "nir_op_infos[alu->op].num_inputs == 2"?
No sure. This is just they way Thomas did it. If that makes sense also
I'll make the change.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+
+ biv->alu_def = src_var->nir_loop_var;
+
+ for (unsigned i = 0; i < 2; i++) {
+ /* Is one of the operands invariant, and the other the phi */
+ if (is_ssa_def_invariant(alu->src[i].src.ssa, state) &&
+ alu->src[1-i].src.ssa->index == phi->dest.ssa.index)
+ biv->invariant = get_nir_loop_var(alu->src[i].src.ssa,
+ state);
+ }
+
+ biv->alu_op = alu->op;
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ if (biv->alu_def && biv->def_outside_loop && biv->invariant && biv->phi) {
+ biv->alu_def->type = basic_induction;
+ biv->phi->type = basic_induction;
+ _mesa_hash_table_insert(state->var_to_basic_ind, biv->alu_def, biv);
+ _mesa_hash_table_insert(state->var_to_basic_ind, biv->phi, biv);
+ return true;
+ }
+
+ /* The requirements for a basic induction variable are not fulfilled */
+ ralloc_free(biv);
+ return false;
+}
+
+static bool
+compute_induction_information(loop_info_state *state)
+{
+ bool changes;
+ bool found_induction_var = false;
+
+ do {
+ changes = false;
+ list_for_each_entry_safe(loop_variable, var,
+ &state->process_list, process_link) {
+
+ /* It can't be an induction variable if it is invariant. We don't
+ * want to deal with things in nested loops or conditionals.
+ */
+ if (var->nir_loop_var->type == invariant ||
+ var->nir_loop_var->in_conditional_block ||
+ var->nir_loop_var->in_nested_loop) {
+ LIST_DEL(&(var->process_link));
+ continue;
+ }
+
+ if (is_var_basic_induction_var(var, state)) {
+ /* If a phi is marked basic_ind we also mark the alu_def basic_ind
+ * at the same time. It will then be detected as basic_ind here,
+ * on the second passing, and be removed from the list.
+ */
+ LIST_DEL(&(var->process_link));
+ changes = true;
+ found_induction_var = true;
+ }
+ }
+ } while (changes);
+
+ return found_induction_var;
+}
+
+static bool
+initialize_ssa_def(nir_ssa_def *def, void *void_state)
+{
+ loop_info_state *state = void_state;
+ loop_variable *var = get_loop_var(def, state);
+
+ var->nir_loop_var = get_nir_loop_var(def, state);
+
+ var->in_loop = false;
+ var->nir_loop_var->def = def;
+
+ if (def->parent_instr->type == nir_instr_type_load_const) {
+ var->nir_loop_var->type = invariant;
+ var->nir_loop_var->is_constant = true;
+ } else {
+ var->nir_loop_var->type = undefined;
+ }
+
+ return true;
+}
+
+static bool
+foreach_cf_node_ex_loop(nir_cf_node *node, void *state)
>
> There's no good reason for this to be a void *; it just leads to extra
> casting. Also, this function could use a better name. Maybe
> cf_node_find_loop_jumps?
>
> > > > > > > > > > > > > >
+{
+ nir_block *block;
+
+ switch (node->type) {
+ case nir_cf_node_block:
+ block = nir_cf_node_as_block(node);
+ nir_foreach_instr(instr, block) {
>
> Jumps are always the last instruction in a block. There's no sense in
> walking all of them just to find the jump. Use nir_block_last_instr()
> instead.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ if (instr->type == nir_instr_type_jump) {
+ if (nir_instr_as_jump(instr)->type == nir_jump_break) {
+ ((loop_jumps *) state)->contains_break = true;
+ } else if (nir_instr_as_jump(instr)->type == nir_jump_continue) {
+ ((loop_jumps *) state)->contains_continue = true;
+ }
+ }
+ }
+ return true;
+
+ case nir_cf_node_if: {
+ nir_if *if_stmt = nir_cf_node_as_if(node);
+
+ foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list)
+ if (!foreach_cf_node_ex_loop(node, state))
+ return false;
+
+ foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list)
+ if (!foreach_cf_node_ex_loop(node, state))
+ return false;
+
+ break;
+ }
>
> Maybe add an explicit case for nir_cf_node_loop with a comment that we don't
> care about inner loops.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+
+ default:
+ break;
+ }
+
+ return false;
+}
+
+static bool
+is_trivial_loop_terminator(nir_if *nif)
+{
+ /* If there is stuff in the else-block that means that this is not a
+ * simple break on true if-statement and so we bail
+ */
+ foreach_list_typed_safe(nir_cf_node, node, node, &nif->else_list)
+ if (node->type == nir_cf_node_block)
+ nir_foreach_instr(instr, nir_cf_node_as_block(node))
+ return false;
>
> > How about "if (!exec_list_empty(&nif->else_list)) return false;"? That
> > seems far simpler.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+
+ nir_cf_node *first_then = nir_if_first_then_node(nif);
+ nir_block *first_then_block = nir_cf_node_as_block(first_then);
+ nir_instr *first_instr = nir_block_first_instr(first_then_block);
+
+ if (first_instr && first_instr->type == nir_instr_type_jump &&
+ nir_instr_as_jump(first_instr)->type == nir_jump_break) {
+ return true;
+ }
+
+ return false;
+}
+
+static bool
+find_loop_terminators(loop_info_state *state)
+{
+ bool success = false;
+ foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
+ if (node->type == nir_cf_node_if) {
+ nir_if *nif = nir_cf_node_as_if(node);
+
+ /* Don't check the nested loops if there are breaks */
+ loop_jumps lj;
+ lj.contains_break = false;
+ lj.contains_continue = false;
+
+ foreach_cf_node_ex_loop(&nif->cf_node, &lj);
+
+ if (lj.contains_continue)
+ return false;
+
+ if (!lj.contains_break)
+ continue;
+
+ /* If there is a break then we should find a terminator. If we can
+ * not find a loop terminator, but there is a break-statement then
+ * we should return false so that we do not try to find trip-count
+ */
+ if (!is_trivial_loop_terminator(nif))
+ return false;
+
+ if (nif->condition.ssa->parent_instr->type == nir_instr_type_phi)
+ return false;
+
+ nir_loop_terminator *terminator =
+ rzalloc(state->info, nir_loop_terminator);
+
+ list_add(&terminator->loop_terminator_link,
+ &state->info->loop_terminator_list);
+
+ terminator->nif = nif;
+ terminator->conditional_instr = nif->condition.ssa->parent_instr;
+
+ success = true;
+ }
+ }
+
+ return success;
+}
+
+static nir_basic_induction_var *
+get_basic_ind_var_for_loop_var(loop_variable *var, loop_info_state *state)
+{
+ assert(var->nir_loop_var->type == basic_induction);
+
+ struct hash_entry *entry =
+ _mesa_hash_table_search(state->var_to_basic_ind, var->nir_loop_var);
+
+ return entry->data;
+}
+
+static int32_t
+get_iteration(nir_op cond_op, nir_const_value *initial, nir_const_value *step,
+ nir_const_value *limit, nir_alu_instr *alu, int32_t *init_val,
+ bool increment_before)
+{
+ int32_t iter;
+
+ switch (cond_op) {
+ case nir_op_ige:
+ case nir_op_ilt:
+ case nir_op_ieq:
+ case nir_op_ine: {
+ int32_t initial_val = initial->i32[0];
+ if (increment_before) {
+ initial_val = alu->op == nir_op_iadd ?
+ initial_val + step->i32[0] : initial_val - step->i32[0];
+ }
+
+ int32_t span = limit->i32[0] - initial_val;
+ iter = span / step->i32[0];
+ *init_val = initial_val;
+ break;
+ }
+ case nir_op_uge:
+ case nir_op_ult: {
+ uint32_t initial_val = initial->u32[0];
+ if (increment_before) {
+ initial_val = alu->op == nir_op_iadd ?
+ initial_val + step->u32[0] : initial_val - step->u32[0];
+ }
+
+ uint32_t span = limit->u32[0] - initial_val;
+ iter = span / step->u32[0];
+ *init_val = initial_val;
+ break;
+ }
+ default:
+ return -1;
+ }
+
+ return iter;
+}
+
+static uint32_t
+utest_interations(int32_t iter_int, nir_const_value *step,
+ nir_const_value *limit, nir_op cond_op,
+ uint32_t initial_val, bool limit_rhs)
+{
+ bool valid_loop = false;
+ uint32_t mul = iter_int * step->u32[0];
+ uint32_t uadd = mul + initial_val;
+
+ switch (cond_op) {
+ case nir_op_uge:
+ valid_loop = limit_rhs ? uadd >= limit->u32[0] : uadd <= limit->u32[0];
+ break;
+ case nir_op_ult:
+ valid_loop = limit_rhs ? uadd < limit->u32[0] : uadd > limit->u32[0];
+ break;
+ default:
+ unreachable("Unhandled loop condition!");
+ }
+
+ return valid_loop;
+}
+
+static int32_t
+itest_interations(int32_t iter_int, nir_const_value *step,
+ nir_const_value *limit, nir_op cond_op,
+ int32_t initial_val, bool limit_rhs)
+{
+ bool valid_loop = false;
+ int32_t mul = iter_int * step->i32[0];
+ int32_t iadd = mul + initial_val;
+
+ switch (cond_op) {
+ case nir_op_ige:
+ valid_loop = limit_rhs ? iadd >= limit->i32[0] : iadd <= limit->i32[0];
+ break;
+ case nir_op_ilt:
+ valid_loop = limit_rhs ? iadd < limit->i32[0] : iadd > limit->i32[0];
+ break;
+ case nir_op_ieq:
+ valid_loop = iadd == limit->i32[0];
+ break;
+ case nir_op_ine:
+ valid_loop = iadd != limit->i32[0];
+ break;
+ default:
+ unreachable("Unhandled loop condition!");
+ }
+
+ return valid_loop;
+}
+
+static int
+calculate_iterations(nir_const_value *initial, nir_const_value *step,
+ nir_const_value *limit, nir_op cond_op,
+ nir_loop_variable *alu_def, nir_alu_instr *cond_alu,
+ bool limit_rhs)
+{
+ assert(initial != NULL && step != NULL && limit != NULL);
+
+ nir_alu_instr *alu = nir_instr_as_alu(alu_def->def->parent_instr);
+
+ /* Unsupported alu operation */
+ if (!(alu->op == nir_op_iadd || alu->op == nir_op_isub))
>
> You only allow iadd and isub except that we lower away isub so you'll never
> see it. Probably best to remove the dead code. Also...
ok thats interesting, out of interest why do we do that? And in what
pass? Also I think I should probably add support for other ops I
believe I've seen shaders that use
either / or * possibly both.
>
> 1) You don't handle swizzles at all
I recall there being a TODO for this originally. Probably a dumb
question but can you give a small shader example? I wasn't sure what I
need to handle exactly.
> 2) You don't handle things other than 64 or 16-bit. Those are coming soon;
> they need to be supported.
Do we need this for the first implementation?
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ 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.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ }
+
+ int32_t initial_val;
+ int iter_int = get_iteration(cond_op, initial, step, limit, alu,
+ &initial_val, increment_before);
+
+ /* If iter_int is negative the loop is ill-formed or is the conditional is
+ * unsigned with a huge iteration count so don't bother going any further.
+ */
+ if (iter_int < 0)
+ return -1;
+
+ /* An explanation from the GLSL unrolling pass:
+ *
+ * Make sure that the calculated number of iterations satisfies the exit
+ * condition. This is needed to catch off-by-one errors and some types of
+ * ill-formed loops. For example, we need to detect that the following
+ * loop does not have a maximum iteration count.
+ *
+ * for (float x = 0.0; x != 0.9; x += 0.2);
+ */
+ 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;
>
> I think it would be clearer if we combined these two functions.
I started out trying to do that but ended up at this. I think my
concern was that the initial value could be negative so we need to
handle that somehow. This seemed slightly nicer than doing "int32_t
iadd = mul + initial_val;" in each struct case.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ }
+ break;
+ default:
+ return -1;
+ }
+ }
+
+ return -1;
+}
+
+/* Run through each of the terminators of the loop and try to infer a possible
+ * trip-count. We need to check them all, and set the lowest trip-count as the
+ * trip-count of our loop. If one of the terminators has an undecidable
+ * trip-count we can not safely assume anything about the duration of the
+ * loop.
+ */
+static void
+find_trip_count(loop_info_state *state)
+{
+ bool trip_count_known = true;
+ nir_loop_terminator *limiting_terminator = NULL;
+ int min_trip_count = -2;
+
+ list_for_each_entry(nir_loop_terminator, terminator,
+ &state->info->loop_terminator_list,
+ loop_terminator_link) {
+
+ if (terminator->conditional_instr->type != nir_instr_type_alu) {
+ /* If we get here the loop is likely not really a loop and will get
+ * cleaned up elsewhere.
+ */
>
> The if statement (and its contents) seem fine but the comment here seems
> sketchy.
I think I was seeing things like this get cleaned up by the dead cf
pass.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ trip_count_known = false;
+ continue;
+ }
+
+ nir_alu_instr *alu = nir_instr_as_alu(terminator->conditional_instr);
+ loop_variable *basic_ind = NULL;
+ loop_variable *limit = NULL;
+ bool limit_rhs = true;
+ nir_op cond_op;
+
+ switch (alu->op) {
+ case nir_op_fge: case nir_op_ige: case nir_op_uge:
+ case nir_op_flt: case nir_op_ilt: case nir_op_ult:
+ case nir_op_feq: case nir_op_ieq:
+ case nir_op_fne: case nir_op_ine:
+
+ /* We assume that the limit is the "right" operand */
+ basic_ind = get_loop_var(alu->src[0].src.ssa, state);
+ limit = get_loop_var(alu->src[1].src.ssa, state);
+ cond_op = alu->op;
+
+ if (basic_ind->nir_loop_var->type != basic_induction) {
+ /* We had it the wrong way, flip things around */
+ basic_ind = get_loop_var(alu->src[1].src.ssa, state);
+ limit = get_loop_var(alu->src[0].src.ssa, state);
+ limit_rhs = false;
+ }
+
+ /* The comparison has to have a basic induction variable
+ * and a constant for us to be able to find trip counts
+ */
+ if (basic_ind->nir_loop_var->type != basic_induction ||
+ !limit->nir_loop_var->is_constant) {
+ trip_count_known = false;
+ continue;
+ }
+
+ nir_basic_induction_var *ind =
+ get_basic_ind_var_for_loop_var(basic_ind, state);
+
+ if (!ind->def_outside_loop->is_constant ||
+ !ind->invariant->is_constant) {
+ trip_count_known = false;
+ continue;
+ }
+
+ /* We have determined that we have the following constants:
+ * (With the typical int i = 0; i < x; i++; as an example)
+ * - Upper limit.
+ * - Starting value
+ * - Step / iteration size
+ * Thats all thats needed to calculate the trip-count
+ */
+
+ nir_load_const_instr *initial_instr =
+ nir_instr_as_load_const(
+ ind->def_outside_loop->def->parent_instr);
+
+ nir_const_value initial_val = initial_instr->value;
+
+ nir_load_const_instr *step_instr =
+ nir_instr_as_load_const(
+ ind->invariant->def->parent_instr);
+
+ nir_const_value step_val = step_instr->value;
+
+ nir_load_const_instr *limit_instr =
+ nir_instr_as_load_const(
+ limit->nir_loop_var->def->parent_instr);
+
+ nir_const_value limit_val = limit_instr->value;
+
+ int iterations = calculate_iterations(&initial_val, &step_val,
+ &limit_val, cond_op,
+ ind->alu_def, alu, limit_rhs);
+
+ /* Where we not able to calculate the iteration count */
+ if (iterations == -1) {
+ trip_count_known = false;
+ continue;
+ }
+
+ /* If this is the first run or we have found a smaller amount of
+ * iterations than previously (we have identified a more limiting
+ * terminator) set the trip count and limiting terminator.
+ */
+ if (min_trip_count == -2 || iterations < min_trip_count) {
>
> Can we have a #define for -2 so that it has a name.
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ min_trip_count = iterations;
+ limiting_terminator = terminator;
+ }
+ break;
+
+ default:
+ trip_count_known = false;
+ }
+ }
+
+ state->info->is_trip_count_known = trip_count_known;
+ if (min_trip_count > -2)
+ state->info->trip_count = min_trip_count;
+ state->info->limiting_terminator = limiting_terminator;
+}
+
+/* Checks if we should force the loop to be unrolled regardless of size */
+static bool
+force_unroll(loop_info_state *state, nir_shader *ns, nir_deref_var *variable)
+{
+ nir_deref *tail = &variable->deref;
+
+ while (tail->child != NULL) {
+ tail = tail->child;
+
+ if (tail->deref_type == nir_deref_type_array) {
+
+ nir_deref_array *deref_array = nir_deref_as_array(tail);
+ if (deref_array->deref_array_type != nir_deref_array_type_indirect)
+ continue;
+
+ nir_loop_variable *array_index =
+ get_nir_loop_var(deref_array->indirect.ssa, state);
+
+ if (array_index->type != basic_induction)
+ continue;
+
+ /* If an array is indexed by a loop induction variable, and the
+ * array size is exactly the number of loop iterations, this is
+ * probably a simple for-loop trying to access each element in
+ * turn; the application may expect it to be unrolled.
+ */
+ if (glsl_get_length(tail->type) == state->info->trip_count) {
+ state->info->force_unroll = true;
+ return state->info->force_unroll;
+ }
+
+ if (variable->var->data.mode & state->indirect_mask) {
+ state->info->force_unroll = true;
+ return state->info->force_unroll;
+ }
>
> Thinking a bit about analysis vs. lowering...>
> I wonder if it wouldn't be better to make the loop anlaysis pass be a bit
> more informational and less decision making. For instance, it could record
> what all variable modes it has seen be indexed by an induction variable and
> let the pass using the analysis decide whether or not to force-unroll.
Seems reasonable.
> For that matter, it could just produce a hash map from induction variables
> to the loop for which they are an induction variable.
I guess so but the above suggestion seems simpler.
> You could also just record the trip count per-loop.
No sure what you mean as we do this already.
> That all seems a bit more like things an analysis pass would do than just
> setting a force_unroll bit.>
> Please don't feel like you need to make any changes in this direction yet.
> I'm mostly trying to open the discussion up a bit and feel out exactly how we
> want things to be structured.>
> I think I've written you a long enough book for now. I'll try to look at the
> others as I get time.
Thanks for taking a look.
>
> --Jason
>
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
+ }
+ }
+
+ return false;
+}
+
+static bool
+count_instructions(loop_info_state *state, nir_shader *ns, nir_block *block)
+{
+ nir_foreach_instr(instr, block) {
+ if (instr->type == nir_instr_type_intrinsic ||
+ instr->type == nir_instr_type_alu) {
+ state->info->num_instructions++;
+ }
+
+ if (instr->type != nir_instr_type_intrinsic)
+ continue;
+
+ nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
+
+ /* Check for arrays variably-indexed by a loop induction variable.
+ * Unrolling the loop may convert that access into constant-indexing.
+ */
+ if (intrin->intrinsic == nir_intrinsic_load_var ||
+ intrin->intrinsic == nir_intrinsic_store_var ||
+ intrin->intrinsic == nir_intrinsic_copy_var) {
+ unsigned num_vars =
+ nir_intrinsic_infos[intrin->intrinsic].num_variables;
+ for (unsigned i = 0; i < num_vars; i++) {
+ if (force_unroll(state, ns, intrin->variables[i]))
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+static void
+get_loop_info(loop_info_state *state, nir_function_impl *impl)
+{
+ /* Initialize all variables to "outside_loop". This also marks defs
+ * invariant and constant if they are nir_instr_type_load_const's
+ */
+ nir_foreach_block(block, impl) {
+ nir_foreach_instr(instr, block)
+ nir_foreach_ssa_def(instr, initialize_ssa_def, state);
+ }
+
+ init_loop_state init_state = {.mark_in_conditional = false,
+ .mark_nested = false, .state = state };
+
+ /* Add all entries in the outermost part of the loop to the processing list
+ * Mark the entries in conditionals or in nested loops accordingly
+ */
+ foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
+ switch (node->type) {
+
+ case nir_cf_node_block:
+ init_state.mark_in_conditional = false;
+ init_state.mark_nested = false;
+ init_loop_block(nir_cf_node_as_block(node), &init_state);
+ break;
+
+ case nir_cf_node_if:
+ init_state.mark_in_conditional = true;
+ init_state.mark_nested = false;
+ nir_foreach_block_in_cf_node(block, node)
+ init_loop_block(block, &init_state);
+ break;
+
+ case nir_cf_node_loop:
+ init_state.mark_in_conditional = false;
+ init_state.mark_nested = true;
+ nir_foreach_block_in_cf_node(block, node) {
+ init_loop_block(block, &init_state);
+ }
+ break;
+
+ case nir_cf_node_function:
+ break;
+ }
+ }
+
+ /* Induction analysis needs invariance information so get that first */
+ compute_invariance_information(state);
+
+ /* We may now have filled the process_list with instructions from inside
+ * the nested blocks in the loop. Remove all instructions from the list
+ * nir_foreach_block_in_cf_node before we start computing induction
+ * information.
+ */
+ list_inithead(&state->process_list);
+
+ /* Add all entries in the outermost part of the loop to the processing list.
+ * Don't include defs inn nested loops or in conditionals.
+ */
+ init_state.mark_in_conditional = false;
+ init_state.mark_nested = false;
+
+ foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body)
+ if (node->type == nir_cf_node_block)
+ init_loop_block(nir_cf_node_as_block(node), &init_state);
+
+ /* We have invariance information so try to find induction variables */
+ if (!compute_induction_information(state))
+ return;
+
+ /* Try to find all simple terminators of the loop. If we can't find any,
+ * or we find possible terminators that have side effects then bail.
+ */
+ if (!find_loop_terminators(state))
+ return;
+
+ /* Run through each of the terminators and try to compute a trip-count */
+ find_trip_count(state);
+
+ nir_shader *ns = impl->function->shader;
+ foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) {
+ if (node->type == nir_cf_node_block) {
+ if (count_instructions(state, ns, nir_cf_node_as_block(node)))
+ break;
+ } else {
+ nir_foreach_block_in_cf_node(block, node) {
+ if (count_instructions(state, ns, block))
+ break;
+ }
+ }
+ }
+}
+
+static loop_info_state *
+initialize_loop_info_state(nir_loop *loop, void *mem_ctx, nir_function_impl
*impl)
+{
+ loop_info_state *state = rzalloc(mem_ctx, loop_info_state);
+ state->loop_vars = rzalloc_array(mem_ctx, loop_variable, impl->ssa_alloc);
+ state->loop = loop;
+ state->nir_loop_vars = rzalloc_array(mem_ctx, nir_loop_variable,
+ impl->ssa_alloc);
+
+ LIST_INITHEAD(&state->process_list);
+
+ if (loop->info)
+ ralloc_free(loop->info);
+
+ state->info = rzalloc(loop, nir_loop_info);
+
+ LIST_INITHEAD(&state->info->loop_terminator_list);
+
+ state->var_to_basic_ind =
+ _mesa_hash_table_create(state->info, _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
+
+ return state;
+}
+
+static void
+process_loops(nir_cf_node *cf_node, nir_variable_mode indirect_mask)
+{
+ switch (cf_node->type) {
+ case nir_cf_node_block:
+ return;
+ case nir_cf_node_if: {
+ nir_if *if_stmt = nir_cf_node_as_if(cf_node);
+ foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list)
+ process_loops(nested_node, indirect_mask);
+ foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
+ process_loops(nested_node, indirect_mask);
+ return;
+ }
+ case nir_cf_node_loop: {
+ nir_loop *loop = nir_cf_node_as_loop(cf_node);
+ foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
+ process_loops(nested_node, indirect_mask);
+ break;
+ }
+ default:
+ unreachable("unknown cf node type");
+ }
+
+ nir_loop *loop = nir_cf_node_as_loop(cf_node);
+ nir_function_impl *impl = nir_cf_node_get_function(cf_node);
+ void *mem_ctx = ralloc_context(NULL);
+
+ loop_info_state *state = initialize_loop_info_state(loop, mem_ctx, impl);
+ state->indirect_mask = indirect_mask;
+
+ get_loop_info(state, impl);
+
+ loop->info = state->info;
+
+ ralloc_free(mem_ctx);
+}
+
+void
+nir_loop_analyze_impl(nir_function_impl *impl,
+ nir_variable_mode indirect_mask)
+{
+ if (impl->function->shader->options->max_unroll_iterations == 0)
+ return;
+
+ nir_index_ssa_defs(impl);
+ foreach_list_typed(nir_cf_node, node, node, &impl->body)
+ process_loops(node, indirect_mask);
+}
diff --git a/src/compiler/nir/nir_metadata.c b/src/compiler/nir/nir_metadata.c
index 9e1cff5..f71cf43 100644
--- a/src/compiler/nir/nir_metadata.c
+++ b/src/compiler/nir/nir_metadata.c
@@ -31,7 +31,7 @@
*/
void
-nir_metadata_require(nir_function_impl *impl, nir_metadata required)
+nir_metadata_require(nir_function_impl *impl, nir_metadata required, ...)
{
#define NEEDS_UPDATE(X) ((required & ~impl->valid_metadata) & (X))
@@ -41,6 +41,12 @@ nir_metadata_require(nir_function_impl *impl, nir_metadata
required)
nir_calc_dominance_impl(impl);
if (NEEDS_UPDATE(nir_metadata_live_ssa_defs))
nir_live_ssa_defs_impl(impl);
+ if (NEEDS_UPDATE(nir_metadata_loop_analysis)) {
+ va_list ap;
+ va_start(ap, required);
+ nir_loop_analyze_impl(impl, va_arg(ap, nir_variable_mode));
+ va_end(ap);
+ }
#undef NEEDS_UPDATE
> > > > > > > > > > > > > > > > > >
--
2.7.4
_______________________________________________
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
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
