[Mesa-dev] [PATCH 07/20] nir: add guess trip count support to loop analysis
Timothy Arceri
tarceri at itsqueeze.com
Sat Dec 8 04:10:03 UTC 2018
On 8/12/18 11:16 am, Jason Ekstrand wrote:
> On Thu, Dec 6, 2018 at 9:08 PM Timothy Arceri <tarceri at itsqueeze.com
> <mailto:tarceri at itsqueeze.com>> wrote:
>
> This detects an induction variable used as an array index to guess
> the trip count of the loop. This enables us to do a partial
> unroll of the loop, with can eventually result in the loop being
> eliminated.
> ---
> src/compiler/nir/nir.h | 4 ++
> src/compiler/nir/nir_loop_analyze.c | 78 ++++++++++++++++++++++++++---
> 2 files changed, 76 insertions(+), 6 deletions(-)
>
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index ce4a81fbe1..a40e5a1418 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -1878,6 +1878,7 @@ typedef struct {
> nir_block *continue_from_block;
>
> bool continue_from_then;
> + bool induction_rhs;
>
> struct list_head loop_terminator_link;
> } nir_loop_terminator;
> @@ -1886,6 +1887,9 @@ typedef struct {
> /* Number of instructions in the loop */
> unsigned num_instructions;
>
> + /* Guessed trip count based on array indexing */
> + unsigned guessed_trip_count;
> +
> /* Maximum number of times the loop is run (if known) */
> unsigned max_trip_count;
>
> diff --git a/src/compiler/nir/nir_loop_analyze.c
> b/src/compiler/nir/nir_loop_analyze.c
> index eef224e4d5..ffcf2a3c27 100644
> --- a/src/compiler/nir/nir_loop_analyze.c
> +++ b/src/compiler/nir/nir_loop_analyze.c
> @@ -382,6 +382,50 @@ find_array_access_via_induction(loop_info_state
> *state,
> return 0;
> }
>
> +static bool
> +guess_loop_limit(loop_info_state *state, nir_const_value *limit_val,
> + nir_loop_variable *basic_ind)
> +{
> + 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) {
> + limit_val->i32[0] = array_size;
> + return true;
>
>
> What if it's used for multiple array accesses of different lengths?
> This just takes the first one. It seems like we could be smarter.
Yeah I guess so. I'll have another go at this.
>
> + }
> +
> + 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) {
> + limit_val->i32[0] = array_size;
> + 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)
> @@ -558,6 +602,7 @@ static void
> 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;
>
> @@ -593,16 +638,33 @@ find_trip_count(loop_info_state *state)
> basic_ind = get_loop_var(alu->src[1].src.ssa, state);
> limit = get_loop_var(alu->src[0].src.ssa, state);
> limit_rhs = false;
> + terminator->induction_rhs = true;
> }
>
> - /* The comparison has to have a basic induction variable
> - * and a constant for us to be able to find trip counts
> + /* The comparison has to have a basic induction variable
> for us to be
> + * able to find trip counts.
> */
> - if (basic_ind->type != basic_induction ||
> !is_var_constant(limit)) {
> + if (basic_ind->type != basic_induction) {
> trip_count_known = false;
> continue;
> }
>
> + /* 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;
> + } else {
> + trip_count_known = false;
> +
> + /* Guess loop limit based on array access */
> + if (!guess_loop_limit(state, &limit_val, basic_ind)) {
> + continue;
> + }
> +
> + guessed_trip_count = true;
> + }
> +
> /* We have determined that we have the following constants:
> * (With the typical int i = 0; i < x; i++; as an example)
> * - Upper limit.
> @@ -619,9 +681,6 @@ find_trip_count(loop_info_state *state)
> 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,
> @@ -631,6 +690,13 @@ find_trip_count(loop_info_state *state)
> /* 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;
>
>
> This resetting confuses me. Why not just make it local to the loop?
Yeah it is a little confusing but since we can have multiple terminators
we need a way to only update guessed_trip_count when the trip count was
guessed for the current terminator. This is also why we have a continue
i.e. so we don't update the regular trip count variable.
For example we could have a guessed trip count of 10 but another
terminator could guarantee a known trip count of 4. In which case we can
do a simple unroll and ignore the guessed count.
I can add a comment here to make this more clear.
Also I think this code needs to be updated to handle multiple guessed
trip counts if we want to support that corner case as per your previous
comment.
>
> + state->loop->info->guessed_trip_count = iterations;
> continue;
> }
>
> --
> 2.19.2
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org <mailto:mesa-dev at lists.freedesktop.org>
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
More information about the mesa-dev
mailing list