diff options
| -rw-r--r-- | src/compiler/Makefile.sources | 2 | ||||
| -rw-r--r-- | src/compiler/nir/nir.c | 2 | ||||
| -rw-r--r-- | src/compiler/nir/nir.h | 41 | ||||
| -rw-r--r-- | src/compiler/nir/nir_loop_analyze.c | 844 | ||||
| -rw-r--r-- | src/compiler/nir/nir_loop_analyze.h | 92 | ||||
| -rw-r--r-- | src/compiler/nir/nir_metadata.c | 8 |
6 files changed, 986 insertions, 3 deletions
diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources index 15f410ff621..edc70f7c4c2 100644 --- a/src/compiler/Makefile.sources +++ b/src/compiler/Makefile.sources @@ -195,6 +195,8 @@ NIR_FILES = \ nir/nir_intrinsics.c \ nir/nir_intrinsics.h \ nir/nir_liveness.c \ + nir/nir_loop_analyze.c \ + nir/nir_loop_analyze.h \ nir/nir_lower_alu_to_scalar.c \ nir/nir_lower_atomics.c \ nir/nir_lower_bitmap.c \ diff --git a/src/compiler/nir/nir.c b/src/compiler/nir/nir.c index 2d882f76483..2c3531cc2dd 100644 --- a/src/compiler/nir/nir.c +++ b/src/compiler/nir/nir.c @@ -393,7 +393,7 @@ nir_if_create(nir_shader *shader) nir_loop * nir_loop_create(nir_shader *shader) { - nir_loop *loop = ralloc(shader, nir_loop); + nir_loop *loop = rzalloc(shader, nir_loop); cf_init(&loop->cf_node, nir_cf_node_loop); diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h index 2c7237b4af2..c7da1e779db 100644 --- a/src/compiler/nir/nir.h +++ b/src/compiler/nir/nir.h @@ -1506,9 +1506,41 @@ typedef struct nir_if { } nir_if; typedef struct { + nir_if *nif; + + nir_instr *conditional_instr; + + nir_block *break_block; + nir_block *continue_from_block; + + bool continue_from_then; + + struct list_head loop_terminator_link; +} nir_loop_terminator; + +typedef struct { + /* Number of instructions in the loop */ + unsigned num_instructions; + + /* How many times the loop is run (if known) */ + unsigned trip_count; + bool is_trip_count_known; + + /* Unroll the loop regardless of its size */ + bool force_unroll; + + nir_loop_terminator *limiting_terminator; + + /* A list of loop_terminators terminating this loop. */ + struct list_head loop_terminator_list; +} nir_loop_info; + +typedef struct { nir_cf_node cf_node; struct exec_list body; /** < list of nir_cf_node */ + + nir_loop_info *info; } nir_loop; /** @@ -1521,6 +1553,7 @@ typedef enum { nir_metadata_dominance = 0x2, nir_metadata_live_ssa_defs = 0x4, nir_metadata_not_properly_reset = 0x8, + nir_metadata_loop_analysis = 0x10, } nir_metadata; typedef struct { @@ -1749,6 +1782,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 { @@ -1859,7 +1894,7 @@ nir_loop *nir_loop_create(nir_shader *shader); nir_function_impl *nir_cf_node_get_function(nir_cf_node *node); /** requests that the given pieces of metadata be generated */ -void nir_metadata_require(nir_function_impl *impl, nir_metadata required); +void nir_metadata_require(nir_function_impl *impl, nir_metadata required, ...); /** dirties all but the preserved metadata */ void nir_metadata_preserve(nir_function_impl *impl, nir_metadata preserved); @@ -2479,6 +2514,10 @@ void nir_lower_double_pack(nir_shader *shader); bool nir_normalize_cubemap_coords(nir_shader *shader); void nir_live_ssa_defs_impl(nir_function_impl *impl); + +void nir_loop_analyze_impl(nir_function_impl *impl, + nir_variable_mode indirect_mask); + bool nir_ssa_defs_interfere(nir_ssa_def *a, nir_ssa_def *b); void nir_convert_to_ssa_impl(nir_function_impl *impl); diff --git a/src/compiler/nir/nir_loop_analyze.c b/src/compiler/nir/nir_loop_analyze.c new file mode 100644 index 00000000000..71cbe3c5a8d --- /dev/null +++ b/src/compiler/nir/nir_loop_analyze.c @@ -0,0 +1,844 @@ +/* + * Copyright © 2015 Thomas Helland + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include "nir.h" +#include "nir_constant_expressions.h" +#include "nir_loop_analyze.h" + +typedef enum { + undefined, + invariant, + not_invariant, + basic_induction +} nir_loop_variable_type; + +struct nir_basic_induction_var; + +typedef struct { + /* A link for the work list */ + struct list_head process_link; + + bool in_loop; + + /* The ssa_def associated with this info */ + nir_ssa_def *def; + + /* The type of this ssa_def */ + nir_loop_variable_type type; + + /* If this is of type basic_induction */ + struct nir_basic_induction_var *ind; + + /* True if variable is in an if branch or a nested loop */ + bool in_control_flow; + +} nir_loop_variable; + +typedef struct nir_basic_induction_var { + 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 *def_outside_loop; /* The phi-src outside the loop */ +} nir_basic_induction_var; + +typedef struct { + /* The loop we store information for */ + nir_loop *loop; + + /* Loop_variable for all ssa_defs in function */ + nir_loop_variable *loop_vars; + + /* A list of the loop_vars to analyze */ + struct list_head process_list; + + nir_variable_mode indirect_mask; + +} loop_info_state; + +static nir_loop_variable * +get_loop_var(nir_ssa_def *value, loop_info_state *state) +{ + return &(state->loop_vars[value->index]); +} + +typedef struct { + loop_info_state *state; + bool in_control_flow; +} 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; + nir_loop_variable *var = get_loop_var(def, loop_init_state->state); + + if (loop_init_state->in_control_flow) { + var->in_control_flow = true; + } else { + /* 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. + */ + list_addtail(&var->process_link, &loop_init_state->state->process_list); + } + + var->in_loop = true; + + return true; +} + +static bool +init_loop_block(nir_block *block, loop_info_state *state, + bool in_control_flow) +{ + init_loop_state init_state = {.in_control_flow = in_control_flow, + .state = state }; + + nir_foreach_instr(instr, block) { + if (instr->type == nir_instr_type_intrinsic || + instr->type == nir_instr_type_alu || + instr->type == nir_instr_type_tex) { + state->loop->info->num_instructions++; + } + + nir_foreach_ssa_def(instr, init_loop_def, &init_state); + } + + return true; +} + +static inline bool +is_var_alu(nir_loop_variable *var) +{ + return var->def->parent_instr->type == nir_instr_type_alu; +} + +static inline bool +is_var_constant(nir_loop_variable *var) +{ + return var->def->parent_instr->type == nir_instr_type_load_const; +} + +static inline bool +is_var_phi(nir_loop_variable *var) +{ + return var->def->parent_instr->type == nir_instr_type_phi; +} + +static inline bool +mark_invariant(nir_ssa_def *def, loop_info_state *state) +{ + nir_loop_variable *var = get_loop_var(def, state); + + if (var->type == invariant) + return true; + + if (!var->in_loop) { + var->type = invariant; + return true; + } + + if (var->type == not_invariant) + 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 (!mark_invariant(alu->src[i].src.ssa, state)) { + var->type = not_invariant; + return false; + } + } + var->type = invariant; + return true; + } + + /* Phis shouldn't be invariant except if one operand is invariant, and the + * other is the phi itself. These should be removed by opt_remove_phis. + * load_consts are already set to invariant and constant during init, + * and so should return earlier. Remaining op_codes are set undefined. + */ + var->type = not_invariant; + 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 + */ + list_for_each_entry_safe(nir_loop_variable, var, &state->process_list, + process_link) { + assert(!var->in_control_flow); + + if (mark_invariant(var->def, state)) + list_del(&var->process_link); + } +} + +static bool +compute_induction_information(loop_info_state *state) +{ + bool found_induction_var = false; + list_for_each_entry_safe(nir_loop_variable, var, &state->process_list, + process_link) { + + /* It can't be an induction variable if it is invariant. Invariants and + * things in nested loops or conditionals should have been removed from + * the list by compute_invariance_information(). + */ + assert(!var->in_control_flow && var->type != invariant); + + /* 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)) + continue; + + nir_phi_instr *phi = nir_instr_as_phi(var->def->parent_instr); + nir_basic_induction_var *biv = rzalloc(state, nir_basic_induction_var); + + nir_foreach_phi_src(src, phi) { + nir_loop_variable *src_var = get_loop_var(src->src.ssa, state); + + /* If one of the sources is in a conditional or nested block then + * panic. + */ + if (src_var->in_control_flow) + break; + + if (!src_var->in_loop) { + biv->def_outside_loop = src_var; + } else if (is_var_alu(src_var)) { + nir_alu_instr *alu = nir_instr_as_alu(src_var->def->parent_instr); + + if (nir_op_infos[alu->op].num_inputs == 2) { + biv->alu_def = src_var; + biv->alu_op = alu->op; + + for (unsigned i = 0; i < 2; i++) { + /* Is one of the operands const, and the other the phi */ + if (alu->src[i].src.ssa->parent_instr->type == nir_instr_type_load_const && + alu->src[1-i].src.ssa == &phi->dest.ssa) + biv->invariant = get_loop_var(alu->src[i].src.ssa, state); + } + } + } + } + + if (biv->alu_def && biv->def_outside_loop && biv->invariant && + is_var_constant(biv->def_outside_loop)) { + assert(is_var_constant(biv->invariant)); + biv->alu_def->type = basic_induction; + biv->alu_def->ind = biv; + var->type = basic_induction; + var->ind = biv; + + found_induction_var = true; + } else { + ralloc_free(biv); + } + } + return found_induction_var; +} + +static bool +initialize_ssa_def(nir_ssa_def *def, void *void_state) +{ + loop_info_state *state = void_state; + nir_loop_variable *var = get_loop_var(def, state); + + var->in_loop = false; + var->def = def; + + if (def->parent_instr->type == nir_instr_type_load_const) { + var->type = invariant; + } else { + var->type = undefined; + } + + return true; +} + +static inline bool +ends_in_break(nir_block *block) +{ + if (exec_list_is_empty(&block->instr_list)) + return false; + + nir_instr *instr = nir_block_last_instr(block); + return instr->type == nir_instr_type_jump && + nir_instr_as_jump(instr)->type == nir_jump_break; +} + +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); + + nir_block *break_blk = NULL; + nir_block *continue_from_blk = NULL; + bool continue_from_then = true; + + nir_block *last_then = nir_if_last_then_block(nif); + nir_block *last_else = nir_if_last_else_block(nif); + if (ends_in_break(last_then)) { + break_blk = last_then; + continue_from_blk = last_else; + continue_from_then = false; + } else if (ends_in_break(last_else)) { + break_blk = last_else; + continue_from_blk = last_then; + } + + /* 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 (!nir_is_trivial_loop_if(nif, break_blk)) + return false; + + /* Continue if the if contained no jumps at all */ + if (!break_blk) + continue; + + if (nif->condition.ssa->parent_instr->type == nir_instr_type_phi) + return false; + + nir_loop_terminator *terminator = + rzalloc(state->loop->info, nir_loop_terminator); + + list_add(&terminator->loop_terminator_link, + &state->loop->info->loop_terminator_list); + + terminator->nif = nif; + terminator->break_block = break_blk; + terminator->continue_from_block = continue_from_blk; + terminator->continue_from_then = continue_from_then; + terminator->conditional_instr = nif->condition.ssa->parent_instr; + + success = true; + } + } + + return success; +} + +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 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]; + int32_t span = limit->i32[0] - initial_val; + iter = span / step->i32[0]; + break; + } + case nir_op_uge: + case nir_op_ult: { + uint32_t initial_val = initial->u32[0]; + uint32_t span = limit->u32[0] - initial_val; + iter = span / step->u32[0]; + break; + } + case nir_op_fge: + case nir_op_flt: + case nir_op_feq: + case nir_op_fne: { + int32_t initial_val = initial->f32[0]; + int32_t span = limit->f32[0] - initial_val; + iter = span / step->f32[0]; + break; + } + default: + return -1; + } + + return iter; +} + +static bool +test_iterations(int32_t iter_int, nir_const_value *step, + nir_const_value *limit, nir_op cond_op, unsigned bit_size, + nir_alu_type induction_base_type, + nir_const_value *initial, bool limit_rhs, bool invert_cond) +{ + assert(nir_op_infos[cond_op].num_inputs == 2); + + nir_const_value iter_src = { {0, } }; + nir_op mul_op; + nir_op add_op; + switch (induction_base_type) { + case nir_type_float: + iter_src.f32[0] = (float) iter_int; + mul_op = nir_op_fmul; + add_op = nir_op_fadd; + break; + case nir_type_int: + case nir_type_uint: + iter_src.i32[0] = iter_int; + mul_op = nir_op_imul; + add_op = nir_op_iadd; + break; + default: + unreachable("Unhandled induction variable base type!"); + } + + /* Multiple the iteration count we are testing by the number of times we + * step the induction variable each iteration. + */ + nir_const_value mul_src[2] = { iter_src, *step }; + nir_const_value mul_result = + nir_eval_const_opcode(mul_op, 1, bit_size, mul_src); + + /* Add the initial value to the accumulated induction variable total */ + nir_const_value add_src[2] = { mul_result, *initial }; + nir_const_value add_result = + nir_eval_const_opcode(add_op, 1, bit_size, add_src); + + nir_const_value src[2] = { { {0, } }, { {0, } } }; + src[limit_rhs ? 0 : 1] = add_result; + src[limit_rhs ? 1 : 0] = *limit; + + /* Evaluate the loop exit condition */ + nir_const_value result = nir_eval_const_opcode(cond_op, 1, bit_size, src); + + return invert_cond ? (result.u32[0] == 0) : (result.u32[0] != 0); +} + +static int +calculate_iterations(nir_const_value *initial, nir_const_value *step, + nir_const_value *limit, nir_loop_variable *alu_def, + nir_alu_instr *cond_alu, bool limit_rhs, bool invert_cond) +{ + assert(initial != NULL && step != NULL && limit != NULL); + + nir_alu_instr *alu = nir_instr_as_alu(alu_def->def->parent_instr); + + /* nir_op_isub should have been lowered away by this point */ + assert(alu->op != nir_op_isub); + + /* Make sure the alu type for our induction variable is compatible with the + * conditional alus input type. If its not something has gone really wrong. + */ + nir_alu_type induction_base_type = + nir_alu_type_get_base_type(nir_op_infos[alu->op].output_type); + if (induction_base_type == nir_type_int || induction_base_type == nir_type_uint) { + assert(nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[1]) == nir_type_int || + nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[1]) == nir_type_uint); + } else { + assert(nir_alu_type_get_base_type(nir_op_infos[cond_alu->op].input_types[0]) == + induction_base_type); + } + + /* Check for nsupported alu operations */ + if (alu->op != nir_op_iadd && alu->op != nir_op_fadd) + 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. + */ + unsigned trip_offset = 0; + if (cond_alu->src[0].src.ssa == alu_def->def || + cond_alu->src[1].src.ssa == alu_def->def) { + trip_offset = 1; + } + + int iter_int = get_iteration(cond_alu->op, initial, step, limit, alu); + + /* 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); + */ + assert(nir_src_bit_size(alu->src[0].src) == + nir_src_bit_size(alu->src[1].src)); + unsigned bit_size = nir_src_bit_size(alu->src[0].src); + for (int bias = -1; bias <= 1; bias++) { + const int iter_bias = iter_int + bias; + + if (test_iterations(iter_bias, step, limit, cond_alu->op, bit_size, + induction_base_type, initial, + limit_rhs, invert_cond)) { + return iter_bias > 0 ? iter_bias - trip_offset : iter_bias; + } + } + + return -1; +} + +/* Run through each of the terminators of the loop and try to infer a possible + * trip-count. We need to check them all, and set the lowest trip-count as the + * trip-count of our loop. If one of the terminators has an undecidable + * trip-count we can not safely assume anything about the duration of the + * loop. + */ +static void +find_trip_count(loop_info_state *state) +{ + bool trip_count_known = true; + nir_loop_terminator *limiting_terminator = NULL; + int min_trip_count = -1; + + list_for_each_entry(nir_loop_terminator, terminator, + &state->loop->info->loop_terminator_list, + loop_terminator_link) { + + if (terminator->conditional_instr->type != nir_instr_type_alu) { + /* If we get here the loop is dead and will get cleaned up by the + * nir_opt_dead_cf pass. + */ + trip_count_known = false; + continue; + } + + nir_alu_instr *alu = nir_instr_as_alu(terminator->conditional_instr); + nir_loop_variable *basic_ind = NULL; + nir_loop_variable *limit = NULL; + bool limit_rhs = true; + + 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); + + if (basic_ind->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->type != basic_induction || !is_var_constant(limit)) { + trip_count_known = false; + continue; + } + + /* We have determined that we have the following constants: + * (With the typical int i = 0; i < x; i++; as an example) + * - Upper limit. + * - Starting value + * - Step / iteration size + * Thats all thats needed to calculate the trip-count + */ + + nir_const_value initial_val = + nir_instr_as_load_const(basic_ind->ind->def_outside_loop-> + def->parent_instr)->value; + + nir_const_value step_val = + nir_instr_as_load_const(basic_ind->ind->invariant->def-> + parent_instr)->value; + + nir_const_value limit_val = + nir_instr_as_load_const(limit->def->parent_instr)->value; + + int iterations = calculate_iterations(&initial_val, &step_val, + &limit_val, + basic_ind->ind->alu_def, alu, + limit_rhs, + terminator->continue_from_then); + + /* Where we not able to calculate the iteration count */ + if (iterations == -1) { + trip_count_known = false; + continue; + } + + /* If this is the first run or we have found a smaller amount of + * iterations than previously (we have identified a more limiting + * terminator) set the trip count and limiting terminator. + */ + if (min_trip_count == -1 || iterations < min_trip_count) { + min_trip_count = iterations; + limiting_terminator = terminator; + } + break; + + default: + trip_count_known = false; + } + } + + state->loop->info->is_trip_count_known = trip_count_known; + if (min_trip_count > -1) + state->loop->info->trip_count = min_trip_count; + state->loop->info->limiting_terminator = limiting_terminator; +} + +/* Checks if we should force the loop to be unrolled regardless of size + * due to array access heuristics. + */ +static bool +force_unroll_array_access(loop_info_state *state, nir_shader *ns, + nir_deref_var *variable) +{ + nir_deref *tail = &variable->deref; + + while (tail->child != NULL) { + tail = tail->child; + + if (tail->deref_type == nir_deref_type_array) { + + nir_deref_array *deref_array = nir_deref_as_array(tail); + if (deref_array->deref_array_type != nir_deref_array_type_indirect) + continue; + + nir_loop_variable *array_index = + get_loop_var(deref_array->indirect.ssa, state); + + if (array_index->type != basic_induction) + continue; + + /* If an array is indexed by a loop induction variable, and the + * array size is exactly the number of loop iterations, this is + * probably a simple for-loop trying to access each element in + * turn; the application may expect it to be unrolled. + */ + if (glsl_get_length(variable->deref.type) == + state->loop->info->trip_count) { + state->loop->info->force_unroll = true; + return state->loop->info->force_unroll; + } + + if (variable->var->data.mode & state->indirect_mask) { + state->loop->info->force_unroll = true; + return state->loop->info->force_unroll; + } + } + } + + return false; +} + +static bool +force_unroll_heuristics(loop_info_state *state, nir_shader *ns, + nir_block *block) +{ + nir_foreach_instr(instr, block) { + if (instr->type != nir_instr_type_intrinsic) + continue; + + nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr); + + /* Check for arrays variably-indexed by a loop induction variable. + * Unrolling the loop may convert that access into constant-indexing. + */ + if (intrin->intrinsic == nir_intrinsic_load_var || + intrin->intrinsic == nir_intrinsic_store_var || + intrin->intrinsic == nir_intrinsic_copy_var) { + unsigned num_vars = + nir_intrinsic_infos[intrin->intrinsic].num_variables; + for (unsigned i = 0; i < num_vars; i++) { + if (force_unroll_array_access(state, ns, intrin->variables[i])) + return true; + } + } + } + + return false; +} + +static void +get_loop_info(loop_info_state *state, nir_function_impl *impl) +{ + /* Initialize all variables to "outside_loop". This also marks defs + * invariant and constant if they are nir_instr_type_load_const's + */ + nir_foreach_block(block, impl) { + nir_foreach_instr(instr, block) + nir_foreach_ssa_def(instr, initialize_ssa_def, state); + } + + /* 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_loop_block(nir_cf_node_as_block(node), state, false); + break; + + case nir_cf_node_if: + nir_foreach_block_in_cf_node(block, node) + init_loop_block(block, state, true); + break; + + case nir_cf_node_loop: + nir_foreach_block_in_cf_node(block, node) { + init_loop_block(block, state, true); + } + break; + + case nir_cf_node_function: + break; + } + } + + /* Induction analysis needs invariance information so get that first */ + compute_invariance_information(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)) { + list_for_each_entry_safe(nir_loop_terminator, terminator, + &state->loop->info->loop_terminator_list, + loop_terminator_link) { + list_del(&terminator->loop_terminator_link); + ralloc_free(terminator); + } + return; + } + + /* Run through each of the terminators and try to compute a trip-count */ + find_trip_count(state); + + nir_shader *ns = impl->function->shader; + foreach_list_typed_safe(nir_cf_node, node, node, &state->loop->body) { + if (node->type == nir_cf_node_block) { + if (force_unroll_heuristics(state, ns, nir_cf_node_as_block(node))) + break; + } else { + nir_foreach_block_in_cf_node(block, node) { + if (force_unroll_heuristics(state, ns, block)) + break; + } + } + } +} + +static loop_info_state * +initialize_loop_info_state(nir_loop *loop, void *mem_ctx, + nir_function_impl *impl) +{ + loop_info_state *state = rzalloc(mem_ctx, loop_info_state); + state->loop_vars = rzalloc_array(mem_ctx, nir_loop_variable, + impl->ssa_alloc); + state->loop = loop; + + list_inithead(&state->process_list); + + if (loop->info) + ralloc_free(loop->info); + + loop->info = rzalloc(loop, nir_loop_info); + + list_inithead(&loop->info->loop_terminator_list); + + return state; +} + +static void +process_loops(nir_cf_node *cf_node, nir_variable_mode indirect_mask) +{ + switch (cf_node->type) { + case nir_cf_node_block: + return; + case nir_cf_node_if: { + nir_if *if_stmt = nir_cf_node_as_if(cf_node); + foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list) + process_loops(nested_node, indirect_mask); + foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list) + process_loops(nested_node, indirect_mask); + return; + } + case nir_cf_node_loop: { + nir_loop *loop = nir_cf_node_as_loop(cf_node); + foreach_list_typed(nir_cf_node, nested_node, node, &loop->body) + process_loops(nested_node, indirect_mask); + break; + } + default: + unreachable("unknown cf node type"); + } + + nir_loop *loop = nir_cf_node_as_loop(cf_node); + nir_function_impl *impl = nir_cf_node_get_function(cf_node); + void *mem_ctx = ralloc_context(NULL); + + loop_info_state *state = initialize_loop_info_state(loop, mem_ctx, impl); + state->indirect_mask = indirect_mask; + + get_loop_info(state, impl); + + ralloc_free(mem_ctx); +} + +void +nir_loop_analyze_impl(nir_function_impl *impl, + nir_variable_mode indirect_mask) +{ + nir_index_ssa_defs(impl); + foreach_list_typed(nir_cf_node, node, node, &impl->body) + process_loops(node, indirect_mask); +} diff --git a/src/compiler/nir/nir_loop_analyze.h b/src/compiler/nir/nir_loop_analyze.h new file mode 100644 index 00000000000..b7f862e8c04 --- /dev/null +++ b/src/compiler/nir/nir_loop_analyze.h @@ -0,0 +1,92 @@ +/* + * Copyright © 2016 Intel Corporation + * + * 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. + */ + +#pragma once + +#include "nir.h" + +/* Returns true if nir_cf_node contains a jump other than the expected_jump + * parameter. + */ +static inline bool +contains_other_jump(nir_cf_node *node, nir_instr *expected_jump) +{ + switch (node->type) { + case nir_cf_node_block: { + nir_instr *lst_instr = nir_block_last_instr(nir_cf_node_as_block(node)); + + /* dead_cf should have eliminated any instruction after the first break + */ + nir_foreach_instr(instr, nir_cf_node_as_block(node)) + assert(instr->type != nir_instr_type_jump || instr == lst_instr); + + if (lst_instr && lst_instr->type == nir_instr_type_jump && + lst_instr != expected_jump) + return true; + else + return false; + } + 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 (contains_other_jump(node, expected_jump)) + return true; + } + + foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) { + if (contains_other_jump(node, expected_jump)) + return true; + } + + return false; + } + case nir_cf_node_loop: + return true; + + default: + unreachable("Unhandled cf node type"); + } +} + +/* Here we define a trivial if as containing only a single break that must be + * located at the end of either the then or else branch of the top level if, + * there must be no other breaks or any other type of jump. Or we pass NULL + * to break_block the if must contains no jumps at all. + */ +static inline bool +nir_is_trivial_loop_if(nir_if *nif, nir_block *break_block) +{ + nir_instr *last_instr = NULL; + + if (break_block) { + last_instr = nir_block_last_instr(break_block); + assert(last_instr && last_instr->type == nir_instr_type_jump && + nir_instr_as_jump(last_instr)->type == nir_jump_break); + } + + if (contains_other_jump(&nif->cf_node, last_instr)) + return false; + + return true; +} diff --git a/src/compiler/nir/nir_metadata.c b/src/compiler/nir/nir_metadata.c index 9e1cff5a67f..f71cf432b70 100644 --- a/src/compiler/nir/nir_metadata.c +++ b/src/compiler/nir/nir_metadata.c @@ -31,7 +31,7 @@ */ void -nir_metadata_require(nir_function_impl *impl, nir_metadata required) +nir_metadata_require(nir_function_impl *impl, nir_metadata required, ...) { #define NEEDS_UPDATE(X) ((required & ~impl->valid_metadata) & (X)) @@ -41,6 +41,12 @@ nir_metadata_require(nir_function_impl *impl, nir_metadata required) nir_calc_dominance_impl(impl); if (NEEDS_UPDATE(nir_metadata_live_ssa_defs)) nir_live_ssa_defs_impl(impl); + if (NEEDS_UPDATE(nir_metadata_loop_analysis)) { + va_list ap; + va_start(ap, required); + nir_loop_analyze_impl(impl, va_arg(ap, nir_variable_mode)); + va_end(ap); + } #undef NEEDS_UPDATE |