<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Tue, Nov 20, 2018 at 6:40 PM Ian Romanick <<a href="mailto:idr@freedesktop.org">idr@freedesktop.org</a>> wrote: </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">From: Ian Romanick <<a href="mailto:ian.d.romanick@intel.com" target="_blank">ian.d.romanick@intel.com</a>> 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 <<a href="mailto:ian.d.romanick@intel.com" target="_blank">ian.d.romanick@intel.com</a>> --- 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; +} </blockquote><div> </div><div>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.</div><div> </div><div>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.</div><div> </div><div>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. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> + 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 <a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div></div>