[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 00:39:44 UTC 2018
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;
}
--
2.14.4
More information about the mesa-dev
mailing list