[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:57:09 UTC 2018
On Wed, Nov 21, 2018 at 1:35 PM Ian Romanick <idr at freedesktop.org> wrote:
> On 11/21/2018 11:01 AM, Jason Ekstrand wrote:
> > On Tue, Nov 20, 2018 at 6:40 PM Ian Romanick <idr at freedesktop.org
> > <mailto:idr at freedesktop.org>> wrote:
> >
> > From: Ian Romanick <ian.d.romanick at intel.com
> > <mailto: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
> > <mailto: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.
>
> I also considered implementing a different data structure entirely. I
> discounted that because I thought I could get a pretty large bang for a
> very small buck. I suspect that a radix tree or similar would have even
> less space overhead. Even with the inefficiencies in this patch, this
> part is no longer the peak memory usage for the pessimal test. Reducing
> the overhead in patch 4 does not change the peak usage for that test. :)
>
> I thought of table-per-entry initially, but I discounted it. That was
> before I realized that I needed an extra allocation for the key.
>
My original thinking for table-per-entry was to make things simpler as much
as anything.
> Starting with patch 4, the ralloc overhead for keys is gone, so that
> effects the calculus a bit. There is still overhead, but for large
> numbers of keys it asymptotically approaches 16 bytes per 1023 keys on
> 64-bit.
Right. I hadn't gotten to reading patch 4 in enough detail to really get
what it's doing. After this discussion, it makes much more sense. I agree
that with a slab allocation strategy, the memory overhead calculus probably
weighs back in favor of the single table approach.
> My gut tells me that the case of one explicit write (ignoring
> the undef) is common since we generate a lot of compiler temporaries.
>
Same here. That case shouldn't matter with the one big table approach but
with smaller tables, we may want to optimize for it at which point you've
lost the simplicity advantage.
> It shouldn't be too much effort to try table-per-value and collect
> actual data.
>
> I also considered adding a _mesa_hash_table_init function (we already
> have _mesa_hash_table_clear) so that a hash table can be embedded in
> another structure to avoid the ralloc (time and space) overhead. If we
> go the table-per-value route, I would definitely want to do that.
>
I've thought about adding that on multiple occasions as well. I never have
because the ralloc overhead of the hash_table struct usually gets lost in
the size of the table. Maybe for really small tables it makes sense; I'm
not sure.
> > 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 <mailto:
> 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/a799489b/attachment-0001.html>
More information about the mesa-dev
mailing list