On Sat, 2016-08-27 at 14:08 +0200, Thomas Helland wrote: > 2016-08-27 8:03 GMT+02:00 Timothy Arceri <timothy.arc...@collabora.co > 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, > > 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 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..a01a4b5 > > --- /dev/null > > +++ b/src/compiler/nir/nir_loop_analyze.c > > @@ -0,0 +1,922 @@ > > +/* > > + * Copyright © 2015 Thomas Helland (for Google's Summer of Code) > > + * > > + * 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 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; > > + > > + /* A list of the loop_vars to analyze */ > > + struct list_head process_list; > > + > > + nir_loop_info *info; > > +} 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)); > > + > > + 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) > > +{ > > + 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 in the > > + * initialization. Skip both of these, and the rest of the > > operations. > > + */ > > This comment is kinda weird. A more correct wording would be: > > /* 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 then > > panic */ > > This comment is missing "block". > > This was just a fast run through of the patch correcting some of the > stuff I know I left behind. I'll try to get a more thorough look at > the > patch later on.
That would be great thanks. I'll fix up these and send out a new series in a couple of days as I spotted a couple of things myself. Thanks, Tim > > Regards, > Thomas > > > > > + if (src_var->nir_loop_var->in_conditional_block || > > + src_var->nir_loop_var->in_nested_loop) > > + break; > > + > > + /* We disable copy propagation inside loops to simplify > > unrolling so > > + * follow moves when looking for induction variable. > > + */ > > + bool copy_prop; > > + nir_alu_instr *alu = NULL; > > + do { > > + copy_prop = false; > > + if (!src_var->in_loop) > > + biv->def_outside_loop = src_var->nir_loop_var; > > + > > + if (src_var->in_loop && is_var_alu(src_var) && > > + !src_var->nir_loop_var->in_nested_loop && > > + !src_var->nir_loop_var->in_conditional_block) { > > + > > + alu = nir_instr_as_alu(src_var->nir_loop_var->def- > > >parent_instr); > > + > > + if (alu->op == nir_op_imov || alu->op == nir_op_fmov) > > { > > + src_var = get_loop_var(alu->src[0].src.ssa, state); > > + copy_prop = true; > > + } > > + } > > + } while (copy_prop); > > + > > + > > + if (src_var->in_loop && is_var_alu(src_var) && > > + !src_var->nir_loop_var->in_nested_loop && > > + !src_var->nir_loop_var->in_conditional_block) { > > + 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: > > + > > + 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->info->var_to_basic_ind, biv- > > >alu_def, biv); > > + _mesa_hash_table_insert(state->info->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) > > +{ > > + nir_block *block; > > + > > + switch (node->type) { > > + case nir_cf_node_block: > > + block = nir_cf_node_as_block(node); > > + nir_foreach_instr(instr, block) { > > + 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; > > + } > > + > > + 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; > > + > > + 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->loop, 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->info->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) > > +{ > > + /* Superfluous assert */ > > + 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)) > > + 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; > > + > > + 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; > > + } > > + 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) > > +{ > > + state->info->is_trip_count_known = false; > > + 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. > > + */ > > + return; > > + } > > + > > + 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; > > + > > + /* FIXME: We should also be able to handle nir_op_iand for > > example > > + * if ((i >= minLights) && (i >= lightProps_count)) break; > > + */ > > + 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) > > + return; > > + > > + 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) > > + return; > > + > > + /* 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); > > + > > + /* If this is the first run then overwrite the value */ > > + if (min_trip_count == -2) > > + min_trip_count = iterations; > > + > > + /* Where we not able to calculate the iterations? */ > > + if (iterations == -1) > > + return; > > + > > + /* If we have found a smaller amount of iterations than > > previously > > + * that means we have identified a more limiting > > terminator > > + */ > > + if (iterations < min_trip_count) { > > + min_trip_count = iterations; > > + limiting_terminator = terminator; > > + } > > + break; > > + > > + default: > > + return; > > + } > > + } > > + > > + state->info->is_trip_count_known = true; > > + state->info->trip_count = min_trip_count; > > + state->info->limiting_terminator = limiting_terminator; > > +} > > + > > +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); > > +} > > + > > +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); > > + LIST_INITHEAD(&state->info->loop_vars_list); > > + > > + state->info->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) > > +{ > > + 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); > > + foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt- > > >else_list) > > + process_loops(nested_node); > > + 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); > > + 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); > > + > > + get_loop_info(state, impl); > > + > > + loop->info = state->info; > > + > > + for (int i = 0; i < impl->ssa_alloc; i++) { > > + loop_variable *var = &state->loop_vars[i]; > > + list_add(&var->nir_loop_var->loop_vars_link, &loop->info- > > >loop_vars_list); > > + } > > + > > + ralloc_free(mem_ctx); > > +} > > + > > +void > > +nir_loop_analyze_impl(nir_function_impl *impl) > > +{ > > + 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); > > +} > > + > > +void > > +nir_loop_analyze(nir_shader *shader) > > +{ > > + nir_foreach_function(func, shader) { > > + if (func->impl) > > + nir_loop_analyze_impl(func->impl); > > + } > > +} > > -- > > 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