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 <[email protected]> On Fri, May 22, 2015 at 11:24 AM, Connor Abbott <[email protected]> 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 <[email protected]> > --- > 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 ([email protected]) > + * Connor Abbott ([email protected]) > * > */ > > -#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 > [email protected] > http://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/mesa-dev
