[Mesa-dev] [PATCH 4/5] nir: add a helper for finding duplicate instructions
Jason Ekstrand
jason at jlekstrand.net
Tue Aug 18 10:47:37 PDT 2015
On Fri, May 22, 2015 at 11:24 AM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> This can be used for both CSE and value numbering.
>
> Signed-off-by: Connor Abbott <cwabbott0 at gmail.com>
> ---
> src/glsl/Makefile.sources | 2 +
> src/glsl/nir/nir_instr_hash.c | 255 ++++++++++++++++++++++++++++++++++++++++++
> src/glsl/nir/nir_instr_hash.h | 36 ++++++
> 3 files changed, 293 insertions(+)
> create mode 100644 src/glsl/nir/nir_instr_hash.c
> create mode 100644 src/glsl/nir/nir_instr_hash.h
>
> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> index 75e5377..fd10cdd 100644
> --- a/src/glsl/Makefile.sources
> +++ b/src/glsl/Makefile.sources
> @@ -28,6 +28,8 @@ NIR_FILES = \
> nir/nir_dominance.c \
> nir/nir_from_ssa.c \
> nir/nir_instr_compare.c \
> + nir/nir_instr_hash.c \
> + nir/nir_instr_hash.h \
> nir/nir_intrinsics.c \
> nir/nir_intrinsics.h \
> nir/nir_live_variables.c \
> diff --git a/src/glsl/nir/nir_instr_hash.c b/src/glsl/nir/nir_instr_hash.c
> new file mode 100644
> index 0000000..d900b66
> --- /dev/null
> +++ b/src/glsl/nir/nir_instr_hash.c
> @@ -0,0 +1,255 @@
> +#include "nir_instr_hash.h"
> +
> +#define HASH(data) hash = _mesa_fnv32_1a_accumulate(hash, (data))
> +
> +static uint32_t
> +hash_src(uint32_t hash, const nir_src *src)
> +{
> + assert(src->is_ssa);
> + HASH(src->ssa);
> + return hash;
> +}
> +
> +static uint32_t
> +hash_alu_src(uint32_t hash, const nir_alu_src *src, unsigned num_components)
> +{
> + HASH(src->abs);
> + HASH(src->negate);
> +
> + for (unsigned i = 0; i < num_components; i++)
> + HASH(src->swizzle[i]);
> +
> + hash = hash_src(hash, &src->src);
> + return hash;
> +}
> +
> +static uint32_t
> +hash_alu(uint32_t hash, const nir_alu_instr *instr)
> +{
> + HASH(instr->op);
> + HASH(instr->dest.dest.ssa.num_components);
> +
> + if (nir_op_infos[instr->op].algebraic_properties & NIR_OP_IS_COMMUTATIVE) {
> + assert(nir_op_infos[instr->op].num_inputs == 2);
> + uint32_t hash0 = hash_alu_src(hash, &instr->src[0],
> + nir_ssa_alu_instr_src_components(instr, 0));
> + uint32_t hash1 = hash_alu_src(hash, &instr->src[1],
> + nir_ssa_alu_instr_src_components(instr, 1));
> + /* For commutative operations, we need some commutative way of
> + * combining the hashes. One option would be to XOR them but that
> + * means that anything with two identical sources will hash to 0 and
> + * that's common enough we probably don't want the guaranteed
> + * collision. Either addition or multiplication will also work.
> + */
> + hash = hash0 * hash1;
> + } else {
> + for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
> + hash = hash_alu_src(hash, &instr->src[i],
> + nir_ssa_alu_instr_src_components(instr, i));
> + }
> + }
> +
> + return hash;
> +}
> +
> +static uint32_t
> +hash_load_const(uint32_t hash, const nir_load_const_instr *instr)
> +{
> + HASH(instr->def.num_components);
> +
> + hash = _mesa_fnv32_1a_accumulate_block(hash, instr->value.f,
> + instr->def.num_components
> + * sizeof(instr->value.f[0]));
> +
> + return hash;
> +}
> +
> +static int
> +cmp_phi_src(const void *data1, const void *data2)
> +{
> + const nir_phi_src *src1 = data1, *src2 = data2;
> + return src1->pred->index - src2->pred->index;
> +}
> +
> +static uint32_t
> +hash_phi(uint32_t hash, const nir_phi_instr *instr)
> +{
> + HASH(instr->instr.block);
> +
> + /* sort sources by predecessor index, since the order shouldn't matter */
> + unsigned num_preds = instr->instr.block->predecessors->entries;
> + nir_phi_src *srcs = malloc(num_preds * sizeof(nir_phi_src));
> + unsigned i = 0;
> + nir_foreach_phi_src(instr, src) {
> + srcs[i++] = *src;
> + }
> + qsort(srcs, num_preds, sizeof(nir_phi_src), cmp_phi_src);
> + for (i = 0; i < num_preds; i++) {
> + hash = hash_src(hash, &srcs[i].src);
> + HASH(srcs[i].pred);
> + }
> + free(srcs);
> +
> + return hash;
> +}
> +
> +static uint32_t
> +hash_intrinsic(uint32_t hash, const nir_intrinsic_instr *instr)
> +{
> + const nir_intrinsic_info *info = &nir_intrinsic_infos[instr->intrinsic];
> + HASH(instr->intrinsic);
> +
> + if (info->has_dest)
> + HASH(instr->dest.ssa.num_components);
> +
> + assert(info->num_variables == 0);
> +
> + hash = _mesa_fnv32_1a_accumulate_block(hash, instr->const_index,
> + info->num_indices
> + * sizeof(instr->const_index[0]));
> + return hash;
> +}
> +
> +static uint32_t
> +hash_instr(const void *data)
> +{
> + const nir_instr *instr = data;
> + uint32_t hash = _mesa_fnv32_1a_offset_bias;
> +
> + switch (instr->type) {
> + case nir_instr_type_alu:
> + hash = hash_alu(hash, nir_instr_as_alu(instr));
> + break;
> + case nir_instr_type_load_const:
> + hash = hash_load_const(hash, nir_instr_as_load_const(instr));
> + break;
> + case nir_instr_type_phi:
> + hash = hash_phi(hash, nir_instr_as_phi(instr));
> + break;
> + case nir_instr_type_intrinsic:
> + hash = hash_intrinsic(hash, nir_instr_as_intrinsic(instr));
> + break;
> + default:
> + unreachable("Invalid instruction type");
> + }
> +
> + return hash;
> +}
> +
> +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;
> +}
> +
> +static bool
> +instr_can_hash(nir_instr *instr)
> +{
> + /* 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;
> +}
Is this really needed? Now we have the "what things do I know about"
logic three places: can_hash, hash, and equal as opposed to two: hash
and equal. We could just have the hash function return the pointer
hash in the cases where it doesn't know what else to do. Also, I'd
like to see the nir_instrs_equal function moved in here and not
exported. As I commented in the patch for nir_instrs_equal, it's not
actually a full equality check because it can have false negatives.
It's fine for an instruction set which may combine two instructions if
they happen to match, but I don't like having it exported unless we're
going to actually think about what instruction equality means. Also,
the equality function will be very closely tied to the hashing
function so keeping them in the same file is a good idea.
> +
> +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");
> + }
> +}
> +
> +static bool
> +cmp_func(const void *data1, const void *data2)
> +{
> + return nir_instrs_equal(data1, data2);
> +}
> +
> +struct set *
> +nir_instr_set_create(void *mem_ctx)
> +{
> + return _mesa_set_create(mem_ctx, hash_instr, cmp_func);
> +}
> +
> +void
> +nir_instr_set_destroy(struct set *instr_set)
> +{
> + _mesa_set_destroy(instr_set, NULL);
> +}
> +
> +bool
> +nir_instr_set_add(struct set *instr_set, nir_instr *instr)
> +{
> + void *mem_ctx = ralloc_parent(instr);
> +
> + if (!instr_can_hash(instr))
> + return false;
> +
> + struct set_entry *entry = _mesa_set_search(instr_set, instr);
> + if (entry) {
> + nir_ssa_def *def = nir_instr_get_dest_ssa_def(instr);
> + nir_ssa_def *new_def =
> + nir_instr_get_dest_ssa_def((nir_instr *) entry->key);
> + nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(new_def), mem_ctx);
> + return true;
> + }
> +
> + _mesa_set_add(instr_set, instr);
> + return false;
> +}
> +
> +void
> +nir_instr_set_remove(struct set *instr_set, nir_instr *instr)
> +{
> + if (!instr_can_hash(instr))
> + return;
> +
> + struct set_entry *entry = _mesa_set_search(instr_set, instr);
> + if (entry)
> + _mesa_set_remove(instr_set, entry);
> +}
> diff --git a/src/glsl/nir/nir_instr_hash.h b/src/glsl/nir/nir_instr_hash.h
> new file mode 100644
> index 0000000..2ff053f
> --- /dev/null
> +++ b/src/glsl/nir/nir_instr_hash.h
> @@ -0,0 +1,36 @@
> +#ifndef _NIR_INSTR_HASH_H
> +#define _NIR_INSTR_HASH_H
> +
> +#include "nir.h"
> +
> +/**
> + * This file defines functions for creating, destroying, and manipulating an
> + * "instruction set," which is an abstraction for finding duplicate
> + * instructions using a hash set.
> + */
> +
> +/*@{*/
> +
> +/** Creates an instruction set, using a given ralloc mem_ctx */
> +struct set *nir_instr_set_create(void *mem_ctx);
> +
> +/** Destroys an instruction set. */
> +void nir_instr_set_destroy(struct set *instr_set);
> +
> +/**
> + * Adds an instruction to an instruction set if it doesn't exist, or if it
> + * does already exist, rewrites all uses of it to point to the other
> + * already-inserted instruction. Returns 'true' if the uses of the instruction
> + * were rewritten.
> + */
> +bool nir_instr_set_add(struct set *instr_set, nir_instr *instr);
I think this should have a different name.
nir_instr_set_add_or_rewrite would be better. That way it's more
obvious what it's doing. nir_instr_set_add looks like it shouldn't
affect the argument at all.
> +
> +/**
> + * Removes an instruction from an instruction set, so that other instructions
> + * won't be merged with it.
> + */
> +void nir_instr_set_remove(struct set *instr_set, nir_instr *instr);
> +
> +/*@}*/
> +
> +#endif
> --
> 2.1.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list