2016-08-27 8:03 GMT+02:00 Timothy Arceri <timothy.arc...@collabora.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. > - 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. 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