[Mesa-dev] [PATCH 03/12] nir: Add a loop analysis pass
Thomas Helland
thomashelland90 at gmail.com
Sat Aug 27 12:08:53 UTC 2016
2016-08-27 8:03 GMT+02:00 Timothy Arceri <timothy.arceri at 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 at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list