[Mesa-dev] [PATCH 4/5] nir: add a helper for finding duplicate instructions
Connor Abbott
cwabbott0 at gmail.com
Wed Sep 23 20:20:26 PDT 2015
On Tue, Aug 18, 2015 at 1:47 PM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> 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.
I don't think it's necessary to have the hashing function return the
pointer if it can't hash the instruction. I think what I'll do instead
is move both the hashing and the comparison to the same file, and make
nir_instr_set_add() and nir_instr_compare() use the same function to
determine if the two instructions can be compared. The comparison will
just return false, and so will the instruction set add function if the
instruction can't be compared; of course, things might break if the
hashing function, comparison function, and "can we compare/rewrite
this" function aren't kept in sync, but in that case there's a bug
anyways, I'd much rather have it fail and let us know that there's a
problem than make it silently degrade. With the instruction scheduler,
we've had lots of problems where we don't notice that code that
doesn't work anymore because nothing actually breaks, and I don't want
that to happen here. Plus, it'll be much less of a concern once all
three are kept in the same file. I think that once we convert CSE over
to the new API, we can remove instruction comparison entirely from the
API and make it implicitly depend on the instruction set API filtering
out unrewriteable instructions, just like the hashing function does.
>
>> +
>> +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