[Mesa-dev] [PATCH 2/7] nir/phi_builder: Use hash table to store [value, block] -> def mapping
Ian Romanick
idr at freedesktop.org
Wed Nov 21 21:05:16 UTC 2018
On IRC, Jason had asked about performance overhead of using the hash
table. A full run of shader-db on a release build (with -march=native)
on my Skylake laptop is a barely measurable amount slower:
x before
+ after
+------------------------------------------------------------------------+
| + |
|xx x + xx*x x + * + * + + +|
| |______________|M____________|_M_A________________| |
+------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 10 108.5 109.3 108.86 108.838 0.25620304
+ 10 108.76 109.73 109.12 109.155 0.3003424
Difference at 95.0% confidence
0.317 +/- 0.262285
0.291259% +/- 0.240986%
(Student's t, pooled s = 0.279147)
On 11/20/2018 04:39 PM, Ian Romanick 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;
> +}
> +
> 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;
> }
>
More information about the mesa-dev
mailing list