[Mesa-dev] [PATCH 5/5] nir/cse: use the instr_hash helper

[Jason Ekstrand]

I really like this.  It's nice, straight-forward, and to-the-point.
Once the other issues have been cleared up,

Reviewed-by: Jason Ekstrand <jason at jlekstrand.net>

On Fri, May 22, 2015 at 11:24 AM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> This replaces an O(n^2) algorithm with an O(n) one, while allowing us to
> import most of the infrastructure required for GVN. The idea is to walk
> the dominance tree depth-first, similar when converting to SSA, and
> remove the instructions from the set when we're done visiting the
> sub-tree of the dominance tree so that the only instructions in the set
> are the instructions that dominate the current block.
>
> No piglit regressions. No changes in the result of the public shader-db.
>
> Difference at 95.0% confidence
>         -0.998 +/- 0.312663
>         -5.96961% +/- 1.87022%
>         (Student's t, pooled s = 0.332763)
>
> Signed-off-by: Connor Abbott <cwabbott0 at gmail.com>
> ---
>  src/glsl/nir/nir_opt_cse.c | 134 ++++++++-------------------------------------
>  1 file changed, 24 insertions(+), 110 deletions(-)
>
> diff --git a/src/glsl/nir/nir_opt_cse.c b/src/glsl/nir/nir_opt_cse.c
> index a6a4a21..7894147 100644
> --- a/src/glsl/nir/nir_opt_cse.c
> +++ b/src/glsl/nir/nir_opt_cse.c
> @@ -22,10 +22,11 @@
>   *
>   * Authors:
>   *    Jason Ekstrand (jason at jlekstrand.net)
> + *    Connor Abbott (cwabbott0 at gmail.com)
>   *
>   */
>
> -#include "nir.h"
> +#include "nir_instr_hash.h"
>
>  /*
>   * Implements common subexpression elimination
> @@ -33,141 +34,54 @@
>
>  struct cse_state {
>     void *mem_ctx;
> +   struct set *instr_set;
>     bool progress;
>  };
>
> -static bool
> -src_is_ssa(nir_src *src, void *data)
> -{
> -   (void) data;
> -   return src->is_ssa;
> -}
> -
> -static bool
> -dest_is_ssa(nir_dest *dest, void *data)
> -{
> -   (void) data;
> -   return dest->is_ssa;
> -}
> +/*
> + * Visits and CSE's the given block and all its descendants in the dominance
> + * tree recursively. Note that the instr_set is guaranteed to only ever
> + * contain instructions that dominate the current block.
> + */
>
>  static bool
> -nir_instr_can_cse(nir_instr *instr)
> +cse_block(nir_block *block, struct set *instr_set)
>  {
> -   /* We only handle SSA. */
> -   if (!nir_foreach_dest(instr, dest_is_ssa, NULL) ||
> -       !nir_foreach_src(instr, src_is_ssa, NULL))
> -      return false;
> -
> -   switch (instr->type) {
> -   case nir_instr_type_alu:
> -   case nir_instr_type_load_const:
> -   case nir_instr_type_phi:
> -      return true;
> -   case nir_instr_type_tex:
> -      return false; /* TODO */
> -   case nir_instr_type_intrinsic: {
> -      const nir_intrinsic_info *info =
> -         &nir_intrinsic_infos[nir_instr_as_intrinsic(instr)->intrinsic];
> -      return (info->flags & NIR_INTRINSIC_CAN_ELIMINATE) &&
> -             (info->flags & NIR_INTRINSIC_CAN_REORDER) &&
> -             info->num_variables == 0; /* not implemented yet */
> -   }
> -   case nir_instr_type_call:
> -   case nir_instr_type_jump:
> -   case nir_instr_type_ssa_undef:
> -      return false;
> -   case nir_instr_type_parallel_copy:
> -   default:
> -      unreachable("Invalid instruction type");
> -   }
> -
> -   return false;
> -}
> -
> -static nir_ssa_def *
> -nir_instr_get_dest_ssa_def(nir_instr *instr)
> -{
> -   switch (instr->type) {
> -   case nir_instr_type_alu:
> -      assert(nir_instr_as_alu(instr)->dest.dest.is_ssa);
> -      return &nir_instr_as_alu(instr)->dest.dest.ssa;
> -   case nir_instr_type_load_const:
> -      return &nir_instr_as_load_const(instr)->def;
> -   case nir_instr_type_phi:
> -      assert(nir_instr_as_phi(instr)->dest.is_ssa);
> -      return &nir_instr_as_phi(instr)->dest.ssa;
> -   case nir_instr_type_intrinsic:
> -      assert(nir_instr_as_intrinsic(instr)->dest.is_ssa);
> -      return &nir_instr_as_intrinsic(instr)->dest.ssa;
> -   default:
> -      unreachable("We never ask for any of these");
> -   }
> -}
> +   bool progress = false;
>
> -static void
> -nir_opt_cse_instr(nir_instr *instr, struct cse_state *state)
> -{
> -   if (!nir_instr_can_cse(instr))
> -      return;
> -
> -   for (struct exec_node *node = instr->node.prev;
> -        !exec_node_is_head_sentinel(node); node = node->prev) {
> -      nir_instr *other = exec_node_data(nir_instr, node, node);
> -      if (nir_instrs_equal(instr, other)) {
> -         nir_ssa_def *other_def = nir_instr_get_dest_ssa_def(other);
> -         nir_ssa_def_rewrite_uses(nir_instr_get_dest_ssa_def(instr),
> -                                  nir_src_for_ssa(other_def),
> -                                  state->mem_ctx);
> +   nir_foreach_instr_safe(block, instr) {
> +      if (nir_instr_set_add(instr_set, instr)) {
> +         progress = true;
>           nir_instr_remove(instr);
> -         state->progress = true;
> -         return;
>        }
>     }
>
> -   for (nir_block *block = instr->block->imm_dom;
> -        block != NULL; block = block->imm_dom) {
> -      nir_foreach_instr_reverse(block, other) {
> -         if (nir_instrs_equal(instr, other)) {
> -            nir_ssa_def *other_def = nir_instr_get_dest_ssa_def(other);
> -            nir_ssa_def_rewrite_uses(nir_instr_get_dest_ssa_def(instr),
> -                                     nir_src_for_ssa(other_def),
> -                                     state->mem_ctx);
> -            nir_instr_remove(instr);
> -            state->progress = true;
> -            return;
> -         }
> -      }
> +   for (unsigned i = 0; i < block->num_dom_children; i++) {
> +      nir_block *child = block->dom_children[i];
> +      progress |= cse_block(child, instr_set);
>     }
> -}
>
> -static bool
> -nir_opt_cse_block(nir_block *block, void *void_state)
> -{
> -   struct cse_state *state = void_state;
> -
> -   nir_foreach_instr_safe(block, instr)
> -      nir_opt_cse_instr(instr, state);
> +   nir_foreach_instr(block, instr)
> +     nir_instr_set_remove(instr_set, instr);
>
> -   return true;
> +   return progress;
>  }
>
>  static bool
>  nir_opt_cse_impl(nir_function_impl *impl)
>  {
> -   struct cse_state state;
> -
> -   state.mem_ctx = ralloc_parent(impl);
> -   state.progress = false;
> +   struct set *instr_set = nir_instr_set_create(NULL);
>
>     nir_metadata_require(impl, nir_metadata_dominance);
>
> -   nir_foreach_block(impl, nir_opt_cse_block, &state);
> +   bool progress = cse_block(impl->start_block, instr_set);
>
> -   if (state.progress)
> +   if (progress)
>        nir_metadata_preserve(impl, nir_metadata_block_index |
>                                    nir_metadata_dominance);
>
> -   return state.progress;
> +   nir_instr_set_destroy(instr_set);
> +   return progress;
>  }
>
>  bool
> --
> 2.1.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev