[Mesa-dev] [PATCH 2/7] nir/phi_builder: Use hash table to store [value, block] -> def mapping
Jason Ekstrand
jason at jlekstrand.net
Wed Nov 21 19:01:59 UTC 2018
On Tue, Nov 20, 2018 at 6:40 PM Ian Romanick <idr at freedesktop.org> wrote:
> From: Ian Romanick <ian.d.romanick at intel.com>
>
> Changes in peak memory usage according to Valgrind massif:
>
> mean soft fp64 using uint64: 5,499,881,802 => 1,343,998,123
> gfxbench5 aztec ruins high 11: 62,415,414 => 62,415,414
> deus ex mankind divided 148: 62,317,965 => 62,317,965
> deus ex mankind divided 2890: 72,585,466 => 72,585,466
> dirt showdown 676: 74,473,151 => 75,203,703
> dolphin ubershaders 210: 109,637,096 => 83,185,248
>
> Signed-off-by: Ian Romanick <ian.d.romanick at intel.com>
> ---
> src/compiler/nir/nir_phi_builder.c | 115
> ++++++++++++++++++++++++++++++-------
> 1 file changed, 93 insertions(+), 22 deletions(-)
>
> diff --git a/src/compiler/nir/nir_phi_builder.c
> b/src/compiler/nir/nir_phi_builder.c
> index add3efd2dfc..36ab9888f48 100644
> --- a/src/compiler/nir/nir_phi_builder.c
> +++ b/src/compiler/nir/nir_phi_builder.c
> @@ -41,6 +41,25 @@ struct nir_phi_builder {
> unsigned iter_count;
> unsigned *work;
> nir_block **W;
> +
> + /**
> + * Tables of SSA defs, indexed by block and nir_phi_builder_value.
> + *
> + * For each [value, block] tuple, this table has one of three types of
> + * values:
> + *
> + * - NULL (i.e., not in the table). Indicates that there is no known
> + * definition in this block. If you need to find one, look at the
> + * block's immediate dominator.
> + *
> + * - NEEDS_PHI. Indicates that the block may need a phi node but none
> has
> + * been created yet. If a def is requested for a block, a phi will
> need
> + * to be created.
> + *
> + * - A regular SSA def. This will be either the result of a phi node
> or
> + * one of the defs provided by
> nir_phi_builder_value_set_blocK_def().
> + */
> + struct hash_table *value_block_def_hash;
> };
>
> #define NEEDS_PHI ((nir_ssa_def *)(intptr_t)-1)
> @@ -61,23 +80,34 @@ struct nir_phi_builder_value {
> * blocks.
> */
> struct exec_list phis;
> +};
>
> - /* Array of SSA defs, indexed by block. For each block, this array
> has has
> - * one of three types of values:
> - *
> - * - NULL. Indicates that there is no known definition in this
> block. If
> - * you need to find one, look at the block's immediate dominator.
> - *
> - * - NEEDS_PHI. Indicates that the block may need a phi node but none
> has
> - * been created yet. If a def is requested for a block, a phi will
> need
> - * to be created.
> - *
> - * - A regular SSA def. This will be either the result of a phi node
> or
> - * one of the defs provided by
> nir_phi_builder_value_set_blocK_def().
> - */
> - nir_ssa_def *defs[0];
> +/**
> + * Key for the nir_phi_builder::value_block_def_hash.
> + */
> +struct phi_builder_key {
> + struct nir_phi_builder_value *val;
> + unsigned block_index;
> };
>
> +static uint32_t
> +phi_builder_key_hash(const void *_k)
> +{
> + const struct phi_builder_key *k = (const struct phi_builder_key *)_k;
> +
> + return _mesa_fnv32_1a_accumulate(_mesa_fnv32_1a_accumulate(0, k->val),
> + k->block_index);
> +}
> +
> +static bool
> +phi_builder_key_equals(const void *_a, const void *_b)
> +{
> + const struct phi_builder_key *a = (const struct phi_builder_key *)_a;
> + const struct phi_builder_key *b = (const struct phi_builder_key *)_b;
> +
> + return a->val == b->val && a->block_index == b->block_index;
> +}
>
Would it be better to have a hash table per value? A whole hash table
sounds like a lot of overhead but it may be less than a tiny allocation
(plus a ralloc header!) for every (block, value) pair. I guess it depends
on the number of defs we expect to be registered per-value.
Running some on-the-fly numbers... A ralloc header is 6 pointers so a
ralloc'd phi_builder_key is 8 pointers worth of data and a ralloc'd
hash_table struct is 15 pointers worth. Throwing in the actual hash table
with 7 entries and you have a header and two pointers per entry so that's
another 20 pointers for a total of 35. That's the same as four
phi_builder_keys (without including malloc's own overhead). So if you have
at least four blocks involved (there have to be at least 3 or there is no
phi), it's break-even and if there are more involved, one table per value
is a win.
We could also consider doing some optimizations for the case where the
value is defined in only one block but that gets tricky as everything has
an implicit undef at the top so that's probably best left for another time
unless it's a super-common case in the fp64 code.
> +
> struct nir_phi_builder *
> nir_phi_builder_create(nir_function_impl *impl)
> {
> @@ -100,6 +130,9 @@ nir_phi_builder_create(nir_function_impl *impl)
> pb->iter_count = 0;
> pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
> pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
> + pb->value_block_def_hash = _mesa_hash_table_create(pb,
> +
> phi_builder_key_hash,
> +
> phi_builder_key_equals);
>
> return pb;
> }
> @@ -111,7 +144,7 @@ nir_phi_builder_add_value(struct nir_phi_builder *pb,
> unsigned num_components,
> struct nir_phi_builder_value *val;
> unsigned i, w_start = 0, w_end = 0;
>
> - val = rzalloc_size(pb, sizeof(*val) + sizeof(val->defs[0]) *
> pb->num_blocks);
> + val = rzalloc_size(pb, sizeof(*val));
> val->builder = pb;
> val->num_components = num_components;
> val->bit_size = bit_size;
> @@ -142,7 +175,9 @@ nir_phi_builder_add_value(struct nir_phi_builder *pb,
> unsigned num_components,
> if (next == pb->impl->end_block)
> continue;
>
> - if (val->defs[next->index] == NULL) {
> + const struct phi_builder_key k = { val, next->index };
> +
> + if (_mesa_hash_table_search(pb->value_block_def_hash, &k) ==
> NULL) {
> /* Instead of creating a phi node immediately, we simply set
> the
> * value to the magic value NEEDS_PHI. Later, we create phi
> nodes
> * on demand in nir_phi_builder_value_get_block_def().
> @@ -164,7 +199,24 @@ void
> nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
> nir_block *block, nir_ssa_def *def)
> {
> - val->defs[block->index] = def;
> + struct hash_table *ht = val->builder->value_block_def_hash;
> + const struct phi_builder_key k = { val, block->index };
> + const uint32_t h = ht->key_hash_function(&k);
> +
> + /* This doesn't just use _mesa_hash_table_insert because we only want
> to
> + * allocate memory for the key if we know that the value needs to be
> added
> + * to the hash table.
> + */
> + struct hash_entry *const he = _mesa_hash_table_search_pre_hashed(ht,
> h, &k);
> + if (he != NULL) {
> + he->data = def;
> + } else {
> + struct phi_builder_key *kp = ralloc(val->builder, struct
> phi_builder_key);
> +
> + kp->val = k.val;
> + kp->block_index = k.block_index;
> + _mesa_hash_table_insert_pre_hashed(ht, h, kp, def);
> + }
> }
>
> nir_ssa_def *
> @@ -175,8 +227,20 @@ nir_phi_builder_value_get_block_def(struct
> nir_phi_builder_value *val,
> * have a valid ssa_def, if any.
> */
> nir_block *dom = block;
> - while (dom && val->defs[dom->index] == NULL)
> + struct hash_entry *he = NULL;
> +
> + while (dom != NULL) {
> + const struct phi_builder_key k = { val, dom->index };
> +
> + he = _mesa_hash_table_search(val->builder->value_block_def_hash,
> &k);
> + if (he != NULL)
> + break;
> +
> dom = dom->imm_dom;
> + }
> +
> + /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
> + assert((he != NULL) != (dom == NULL));
>
> nir_ssa_def *def;
> if (dom == NULL) {
> @@ -191,7 +255,7 @@ nir_phi_builder_value_get_block_def(struct
> nir_phi_builder_value *val,
> nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
> &undef->instr);
> def = &undef->def;
> - } else if (val->defs[dom->index] == NEEDS_PHI) {
> + } else if (he->data == NEEDS_PHI) {
> /* The magic value NEEDS_PHI indicates that the block needs a phi
> node
> * but none has been created. We need to create one now so we can
> * return it to the caller.
> @@ -215,13 +279,14 @@ nir_phi_builder_value_get_block_def(struct
> nir_phi_builder_value *val,
> val->bit_size, NULL);
> phi->instr.block = dom;
> exec_list_push_tail(&val->phis, &phi->instr.node);
> - def = val->defs[dom->index] = &phi->dest.ssa;
> + def = &phi->dest.ssa;
> + he->data = def;
> } else {
> /* In this case, we have an actual SSA def. It's either the result
> of a
> * phi node created by the case above or one passed to us through
> * nir_phi_builder_value_set_block_def().
> */
> - def = val->defs[dom->index];
> + def = (struct nir_ssa_def *) he->data;
> }
>
> /* Walk the chain and stash the def in all of the applicable blocks.
> We do
> @@ -231,8 +296,14 @@ nir_phi_builder_value_get_block_def(struct
> nir_phi_builder_value *val,
> * block that is not dominated by this one.
> * 2) To avoid unneeded recreation of phi nodes and undefs.
> */
> - for (dom = block; dom && val->defs[dom->index] == NULL; dom =
> dom->imm_dom)
> + for (dom = block; dom != NULL; dom = dom->imm_dom) {
> + const struct phi_builder_key k = { val, dom->index };
> +
> + if (_mesa_hash_table_search(val->builder->value_block_def_hash, &k)
> != NULL)
> + break;
> +
> nir_phi_builder_value_set_block_def(val, dom, def);
> + }
>
> return def;
> }
> --
> 2.14.4
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20181121/aa01fa2b/attachment-0001.html>
More information about the mesa-dev
mailing list