return true;
}
+/** Calculate an estimated cost in number of instructions
+ *
+ * We do this so that we don't unroll loops which will later get massively
+ * inflated due to int64 or fp64 lowering. The estimates provided here don't
+ * have to be massively accurate; they just have to be good enough that loop
+ * unrolling doesn't cause things to blow up too much.
+ */
+static unsigned
+instr_cost(nir_instr *instr, const nir_shader_compiler_options *options)
+{
+ if (instr->type == nir_instr_type_intrinsic ||
+ instr->type == nir_instr_type_tex)
+ return 1;
+
+ if (instr->type != nir_instr_type_alu)
+ return 0;
+
+ nir_alu_instr *alu = nir_instr_as_alu(instr);
+ const nir_op_info *info = &nir_op_infos[alu->op];
+
+ /* Assume everything 16 or 32-bit is cheap.
+ *
+ * There are no 64-bit ops that don't have a 64-bit thing as their
+ * destination or first source.
+ */
+ if (nir_dest_bit_size(alu->dest.dest) < 64 &&
+ nir_src_bit_size(alu->src[0].src) < 64)
+ return 1;
+
+ bool is_fp64 = nir_dest_bit_size(alu->dest.dest) == 64 &&
+ nir_alu_type_get_base_type(info->output_type) == nir_type_float;
+ for (unsigned i = 0; i < info->num_inputs; i++) {
+ if (nir_src_bit_size(alu->src[i].src) == 64 &&
+ nir_alu_type_get_base_type(info->input_types[i]) == nir_type_float)
+ is_fp64 = true;
+ }
+
+ if (is_fp64) {
+ /* If it's something lowered normally, it's expensive. */
+ unsigned cost = 1;
+ if (options->lower_doubles_options &
+ nir_lower_doubles_op_to_options_mask(alu->op))
+ cost *= 20;
+
+ /* If it's full software, it's even more expensive */
+ if (options->lower_doubles_options & nir_lower_fp64_full_software)
+ cost *= 100;
+
+ return cost;
+ } else {
+ if (options->lower_int64_options &
+ nir_lower_int64_op_to_options_mask(alu->op)) {
+ /* These require a doing the division algorithm. */
+ if (alu->op == nir_op_idiv || alu->op == nir_op_udiv ||
+ alu->op == nir_op_imod || alu->op == nir_op_umod ||
+ alu->op == nir_op_irem)
+ return 100;
+
+ /* Other int64 lowering isn't usually all that expensive */
+ return 5;
+ }
+
+ return 1;
+ }
+}
+
static bool
init_loop_block(nir_block *block, loop_info_state *state,
- bool in_if_branch, bool in_nested_loop)
+ bool in_if_branch, bool in_nested_loop,
+ const nir_shader_compiler_options *options)
{
init_loop_state init_state = {.in_if_branch = in_if_branch,
.in_nested_loop = in_nested_loop,
.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++;
- }
-
+ state->loop->info->instr_cost += instr_cost(instr, options);
nir_foreach_ssa_def(instr, init_loop_def, &init_state);
}
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 one of the sources is in an if branch or nested loop then don't
+ * attempt to go any further.
*/
if (src_var->in_if_branch || src_var->in_nested_loop)
break;
+ /* Detect inductions variables that are incremented in both branches
+ * of an unnested if rather than in a loop block.
+ */
+ if (is_var_phi(src_var)) {
+ nir_phi_instr *src_phi =
+ nir_instr_as_phi(src_var->def->parent_instr);
+
+ nir_op alu_op = nir_num_opcodes; /* avoid uninitialized warning */
+ nir_ssa_def *alu_srcs[2] = {0};
+ nir_foreach_phi_src(src2, src_phi) {
+ nir_loop_variable *src_var2 =
+ get_loop_var(src2->src.ssa, state);
+
+ if (!src_var2->in_if_branch || !is_var_alu(src_var2))
+ break;
+
+ nir_alu_instr *alu =
+ nir_instr_as_alu(src_var2->def->parent_instr);
+ if (nir_op_infos[alu->op].num_inputs != 2)
+ break;
+
+ if (alu->src[0].src.ssa == alu_srcs[0] &&
+ alu->src[1].src.ssa == alu_srcs[1] &&
+ alu->op == alu_op) {
+ /* Both branches perform the same calculation so we can use
+ * one of them to find the induction variable.
+ */
+ src_var = src_var2;
+ } else {
+ alu_srcs[0] = alu->src[0].src.ssa;
+ alu_srcs[1] = alu->src[1].src.ssa;
+ alu_op = alu->op;
+ }
+ }
+ }
+
if (!src_var->in_loop) {
biv->def_outside_loop = src_var;
} else if (is_var_alu(src_var)) {
*array_index_out = array_index;
nir_deref_instr *parent = nir_deref_instr_parent(d);
- assert(glsl_type_is_array_or_matrix(parent->type));
-
- return glsl_get_length(parent->type);
+ if (glsl_type_is_array_or_matrix(parent->type)) {
+ return glsl_get_length(parent->type);
+ } else {
+ assert(glsl_type_is_vector(parent->type));
+ return glsl_get_vector_elements(parent->type);
+ }
}
return 0;
}
+static bool
+guess_loop_limit(loop_info_state *state, nir_const_value *limit_val,
+ nir_loop_variable *basic_ind)
+{
+ unsigned min_array_size = 0;
+
+ nir_foreach_block_in_cf_node(block, &state->loop->cf_node) {
+ 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. */
+ if (intrin->intrinsic == nir_intrinsic_load_deref ||
+ intrin->intrinsic == nir_intrinsic_store_deref ||
+ intrin->intrinsic == nir_intrinsic_copy_deref) {
+
+ nir_loop_variable *array_idx = NULL;
+ unsigned array_size =
+ find_array_access_via_induction(state,
+ nir_src_as_deref(intrin->src[0]),
+ &array_idx);
+ if (basic_ind == array_idx &&
+ (min_array_size == 0 || min_array_size > array_size)) {
+ min_array_size = array_size;
+ }
+
+ if (intrin->intrinsic != nir_intrinsic_copy_deref)
+ continue;
+
+ array_size =
+ find_array_access_via_induction(state,
+ nir_src_as_deref(intrin->src[1]),
+ &array_idx);
+ if (basic_ind == array_idx &&
+ (min_array_size == 0 || min_array_size > array_size)) {
+ min_array_size = array_size;
+ }
+ }
+ }
+ }
+
+ if (min_array_size) {
+ limit_val->i32 = min_array_size;
+ return true;
+ }
+
+ return false;
+}
+
+static bool
+try_find_limit_of_alu(nir_loop_variable *limit, nir_const_value *limit_val,
+ nir_loop_terminator *terminator, loop_info_state *state)
+{
+ if(!is_var_alu(limit))
+ return false;
+
+ nir_alu_instr *limit_alu = nir_instr_as_alu(limit->def->parent_instr);
+
+ if (limit_alu->op == nir_op_imin ||
+ limit_alu->op == nir_op_fmin) {
+ limit = get_loop_var(limit_alu->src[0].src.ssa, state);
+
+ if (!is_var_constant(limit))
+ limit = get_loop_var(limit_alu->src[1].src.ssa, state);
+
+ if (!is_var_constant(limit))
+ return false;
+
+ *limit_val = nir_instr_as_load_const(limit->def->parent_instr)->value[0];
+
+ terminator->exact_trip_count_unknown = true;
+
+ return true;
+ }
+
+ return false;
+}
+
static int32_t
get_iteration(nir_op cond_op, nir_const_value *initial, nir_const_value *step,
nir_const_value *limit)
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];
+ int32_t initial_val = initial->i32;
+ int32_t span = limit->i32 - initial_val;
+ iter = span / step->i32;
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];
+ uint32_t initial_val = initial->u32;
+ uint32_t span = limit->u32 - initial_val;
+ iter = span / step->u32;
break;
}
case nir_op_fge:
case nir_op_flt:
case nir_op_feq:
case nir_op_fne: {
- float initial_val = initial->f32[0];
- float span = limit->f32[0] - initial_val;
- iter = span / step->f32[0];
+ float initial_val = initial->f32;
+ float span = limit->f32 - initial_val;
+ iter = span / step->f32;
break;
}
default:
{
assert(nir_op_infos[cond_op].num_inputs == 2);
- nir_const_value iter_src = { {0, } };
+ 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;
+ iter_src.f32 = (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;
+ iter_src.i32 = iter_int;
mul_op = nir_op_imul;
add_op = nir_op_iadd;
break;
/* 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);
+ nir_const_value *mul_src[2] = { &iter_src, step };
+ nir_const_value mul_result;
+ nir_eval_const_opcode(mul_op, &mul_result, 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 *add_src[2] = { &mul_result, initial };
+ nir_const_value add_result;
+ nir_eval_const_opcode(add_op, &add_result, 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;
+ nir_const_value *src[2];
+ 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);
+ nir_const_value result;
+ nir_eval_const_opcode(cond_op, &result, 1, bit_size, src);
- return invert_cond ? (result.u32[0] == 0) : (result.u32[0] != 0);
+ return invert_cond ? !result.b : result.b;
}
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)
+ nir_alu_instr *cond_alu, nir_op alu_op, bool limit_rhs,
+ bool invert_cond)
{
assert(initial != NULL && step != NULL && limit != NULL);
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);
+ assert(nir_alu_type_get_base_type(nir_op_infos[alu_op].input_types[1]) == nir_type_int ||
+ nir_alu_type_get_base_type(nir_op_infos[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]) ==
+ assert(nir_alu_type_get_base_type(nir_op_infos[alu_op].input_types[0]) ==
induction_base_type);
}
trip_offset = 1;
}
- int iter_int = get_iteration(cond_alu->op, initial, step, limit);
+ int iter_int = get_iteration(alu_op, initial, step, limit);
/* 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.
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,
+ if (test_iterations(iter_bias, step, limit, alu_op, bit_size,
induction_base_type, initial,
limit_rhs, invert_cond)) {
return iter_bias > 0 ? iter_bias - trip_offset : iter_bias;
return -1;
}
+static nir_op
+inverse_comparison(nir_alu_instr *alu)
+{
+ switch (alu->op) {
+ case nir_op_fge:
+ return nir_op_flt;
+ case nir_op_ige:
+ return nir_op_ilt;
+ case nir_op_uge:
+ return nir_op_ult;
+ case nir_op_flt:
+ return nir_op_fge;
+ case nir_op_ilt:
+ return nir_op_ige;
+ case nir_op_ult:
+ return nir_op_uge;
+ case nir_op_feq:
+ return nir_op_fne;
+ case nir_op_ieq:
+ return nir_op_ine;
+ case nir_op_fne:
+ return nir_op_feq;
+ case nir_op_ine:
+ return nir_op_ieq;
+ default:
+ unreachable("Unsuported comparison!");
+ }
+}
+
+static bool
+is_supported_terminator_condition(nir_alu_instr *alu)
+{
+ return nir_alu_instr_is_comparison(alu) &&
+ nir_op_infos[alu->op].num_inputs == 2;
+}
+
+static bool
+get_induction_and_limit_vars(nir_alu_instr *alu, nir_loop_variable **ind,
+ nir_loop_variable **limit,
+ loop_info_state *state)
+{
+ bool limit_rhs = true;
+
+ /* We assume that the limit is the "right" operand */
+ *ind = get_loop_var(alu->src[0].src.ssa, state);
+ *limit = get_loop_var(alu->src[1].src.ssa, state);
+
+ if ((*ind)->type != basic_induction) {
+ /* We had it the wrong way, flip things around */
+ *ind = get_loop_var(alu->src[1].src.ssa, state);
+ *limit = get_loop_var(alu->src[0].src.ssa, state);
+ limit_rhs = false;
+ }
+
+ return limit_rhs;
+}
+
+static void
+try_find_trip_count_vars_in_iand(nir_alu_instr **alu,
+ nir_loop_variable **ind,
+ nir_loop_variable **limit,
+ bool *limit_rhs,
+ loop_info_state *state)
+{
+ assert((*alu)->op == nir_op_ieq || (*alu)->op == nir_op_inot);
+
+ nir_ssa_def *iand_def = (*alu)->src[0].src.ssa;
+
+ if ((*alu)->op == nir_op_ieq) {
+ nir_ssa_def *zero_def = (*alu)->src[1].src.ssa;
+
+ if (iand_def->parent_instr->type != nir_instr_type_alu ||
+ zero_def->parent_instr->type != nir_instr_type_load_const) {
+
+ /* Maybe we had it the wrong way, flip things around */
+ iand_def = (*alu)->src[1].src.ssa;
+ zero_def = (*alu)->src[0].src.ssa;
+
+ /* If we still didn't find what we need then return */
+ if (zero_def->parent_instr->type != nir_instr_type_load_const)
+ return;
+ }
+
+ /* If the loop is not breaking on (x && y) == 0 then return */
+ nir_const_value *zero =
+ nir_instr_as_load_const(zero_def->parent_instr)->value;
+ if (zero[0].i32 != 0)
+ return;
+ }
+
+ if (iand_def->parent_instr->type != nir_instr_type_alu)
+ return;
+
+ nir_alu_instr *iand = nir_instr_as_alu(iand_def->parent_instr);
+ if (iand->op != nir_op_iand)
+ return;
+
+ /* Check if iand src is a terminator condition and try get induction var
+ * and trip limit var.
+ */
+ nir_ssa_def *src = iand->src[0].src.ssa;
+ if (src->parent_instr->type == nir_instr_type_alu) {
+ *alu = nir_instr_as_alu(src->parent_instr);
+ if (is_supported_terminator_condition(*alu))
+ *limit_rhs = get_induction_and_limit_vars(*alu, ind, limit, state);
+ }
+
+ /* Try the other iand src if needed */
+ if (*ind == NULL || (*ind && (*ind)->type != basic_induction) ||
+ !is_var_constant(*limit)) {
+ src = iand->src[1].src.ssa;
+ if (src->parent_instr->type == nir_instr_type_alu) {
+ nir_alu_instr *tmp_alu = nir_instr_as_alu(src->parent_instr);
+ if (is_supported_terminator_condition(tmp_alu)) {
+ *alu = tmp_alu;
+ *limit_rhs = get_induction_and_limit_vars(*alu, ind, limit, state);
+ }
+ }
+ }
+}
+
/* 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
find_trip_count(loop_info_state *state)
{
bool trip_count_known = true;
+ bool guessed_trip_count = false;
nir_loop_terminator *limiting_terminator = NULL;
int max_trip_count = -1;
}
nir_alu_instr *alu = nir_instr_as_alu(terminator->conditional_instr);
+ nir_op alu_op = alu->op;
+
+ bool limit_rhs;
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;
+ nir_loop_variable *limit;
+ if (alu->op == nir_op_inot || alu->op == nir_op_ieq) {
+ nir_alu_instr *new_alu = alu;
+ try_find_trip_count_vars_in_iand(&new_alu, &basic_ind, &limit,
+ &limit_rhs, state);
+
+ /* The loop is exiting on (x && y) == 0 so we need to get the
+ * inverse of x or y (i.e. which ever contained the induction var) in
+ * order to compute the trip count.
+ */
+ if (basic_ind && basic_ind->type == basic_induction) {
+ alu = new_alu;
+ alu_op = inverse_comparison(alu);
+ trip_count_known = false;
+ terminator->exact_trip_count_unknown = true;
}
+ }
- /* 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)) {
+ if (!basic_ind) {
+ if (!is_supported_terminator_condition(alu)) {
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
- */
+ limit_rhs = get_induction_and_limit_vars(alu, &basic_ind, &limit,
+ state);
+ }
- nir_const_value initial_val =
- nir_instr_as_load_const(basic_ind->ind->def_outside_loop->
- def->parent_instr)->value;
+ /* The comparison has to have a basic induction variable for us to be
+ * able to find trip counts.
+ */
+ if (basic_ind->type != basic_induction) {
+ trip_count_known = false;
+ continue;
+ }
- nir_const_value step_val =
- nir_instr_as_load_const(basic_ind->ind->invariant->def->
- parent_instr)->value;
+ terminator->induction_rhs = !limit_rhs;
- nir_const_value limit_val =
- nir_instr_as_load_const(limit->def->parent_instr)->value;
+ /* Attempt to find a constant limit for the loop */
+ nir_const_value limit_val;
+ if (is_var_constant(limit)) {
+ limit_val =
+ nir_instr_as_load_const(limit->def->parent_instr)->value[0];
+ } else {
+ trip_count_known = false;
- int iterations = calculate_iterations(&initial_val, &step_val,
- &limit_val,
- basic_ind->ind->alu_def, alu,
- limit_rhs,
- terminator->continue_from_then);
+ if (!try_find_limit_of_alu(limit, &limit_val, terminator, state)) {
+ /* Guess loop limit based on array access */
+ if (!guess_loop_limit(state, &limit_val, basic_ind)) {
+ continue;
+ }
- /* Where we not able to calculate the iteration count */
- if (iterations == -1) {
- trip_count_known = false;
- continue;
+ guessed_trip_count = true;
}
+ }
- /* 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 (max_trip_count == -1 || iterations < max_trip_count) {
- max_trip_count = iterations;
- limiting_terminator = terminator;
- }
- break;
+ /* 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;
+
+ int iterations = calculate_iterations(initial_val, step_val,
+ &limit_val,
+ basic_ind->ind->alu_def, alu,
+ alu_op, limit_rhs,
+ terminator->continue_from_then);
- default:
+ /* Where we not able to calculate the iteration count */
+ if (iterations == -1) {
trip_count_known = false;
+ guessed_trip_count = false;
+ continue;
+ }
+
+ if (guessed_trip_count) {
+ guessed_trip_count = false;
+ if (state->loop->info->guessed_trip_count == 0 ||
+ state->loop->info->guessed_trip_count > iterations)
+ state->loop->info->guessed_trip_count = iterations;
+
+ 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 (max_trip_count == -1 || iterations < max_trip_count) {
+ max_trip_count = iterations;
+ limiting_terminator = terminator;
}
}
static void
get_loop_info(loop_info_state *state, nir_function_impl *impl)
{
+ nir_shader *shader = impl->function->shader;
+ const nir_shader_compiler_options *options = shader->options;
+
/* Initialize all variables to "outside_loop". This also marks defs
* invariant and constant if they are nir_instr_type_load_consts
*/
switch (node->type) {
case nir_cf_node_block:
- init_loop_block(nir_cf_node_as_block(node), state, false, false);
+ init_loop_block(nir_cf_node_as_block(node), state,
+ false, false, options);
break;
case nir_cf_node_if:
nir_foreach_block_in_cf_node(block, node)
- init_loop_block(block, state, true, false);
+ init_loop_block(block, state, true, false, options);
break;
case nir_cf_node_loop:
nir_foreach_block_in_cf_node(block, node) {
- init_loop_block(block, state, false, true);
+ init_loop_block(block, state, false, true, options);
}
break;
/* Run through each of the terminators and try to compute a trip-count */
find_trip_count(state);
- nir_shader *ns = impl->function->shader;
nir_foreach_block_in_cf_node(block, &state->loop->cf_node) {
if (force_unroll_heuristics(state, block)) {
state->loop->info->force_unroll = true;
projects / mesa.git / blobdiff