X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fcompiler%2Fnir%2Fnir_phi_builder.c;h=97edea777f4dfabfcc437effbc9d9fdba4a32698;hb=eb3047c094abfa03e071453d7c373e9c2c574370;hp=1f1388a73dd9f5f97de3a1c8d596ceee73dcd19a;hpb=e3edaec739a72a36d54b60ddf5c952d377324f00;p=mesa.git diff --git a/src/compiler/nir/nir_phi_builder.c b/src/compiler/nir/nir_phi_builder.c index 1f1388a73dd..97edea777f4 100644 --- a/src/compiler/nir/nir_phi_builder.c +++ b/src/compiler/nir/nir_phi_builder.c @@ -75,21 +75,22 @@ struct nir_phi_builder_value { * - 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]; + struct hash_table ht; }; -static bool -fill_block_array(nir_block *block, void *void_data) -{ - nir_block **blocks = void_data; - blocks[block->index] = block; - return true; -} +/** + * Convert a block index into a value that can be used as a key for a hash table + * + * The hash table functions want a pointer that is not \c NULL. + * _mesa_hash_pointer drops the two least significant bits, but that's where + * most of our data likely is. Shift by 2 and add 1 to make everything happy. + */ +#define INDEX_TO_KEY(x) ((void *)(uintptr_t) ((x << 2) + 1)) struct nir_phi_builder * nir_phi_builder_create(nir_function_impl *impl) { - struct nir_phi_builder *pb = ralloc(NULL, struct nir_phi_builder); + struct nir_phi_builder *pb = rzalloc(NULL, struct nir_phi_builder); pb->shader = impl->function->shader; pb->impl = impl; @@ -99,7 +100,9 @@ nir_phi_builder_create(nir_function_impl *impl) pb->num_blocks = impl->num_blocks; pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks); - nir_foreach_block(impl, fill_block_array, pb->blocks); + nir_foreach_block(block, impl) { + pb->blocks[block->index] = block; + } exec_list_make_empty(&pb->values); @@ -117,13 +120,16 @@ 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; exec_list_make_empty(&val->phis); exec_list_push_tail(&pb->values, &val->node); + _mesa_hash_table_init(&val->ht, pb, _mesa_hash_pointer, + _mesa_key_pointer_equal); + pb->iter_count++; BITSET_WORD tmp; @@ -135,7 +141,6 @@ nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components, while (w_start != w_end) { nir_block *cur = pb->W[w_start++]; - struct set_entry *dom_entry; set_foreach(cur->dom_frontier, dom_entry) { nir_block *next = (nir_block *) dom_entry->key; @@ -149,12 +154,12 @@ 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) { + if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(next->index)) == 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(). */ - val->defs[next->index] = NEEDS_PHI; + nir_phi_builder_value_set_block_def(val, next, NEEDS_PHI); if (pb->work[next->index] < pb->iter_count) { pb->work[next->index] = pb->iter_count; @@ -171,38 +176,44 @@ 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; + _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def); } nir_ssa_def * nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val, nir_block *block) { - /* For each block, we have one of three types of values */ - if (val->defs[block->index] == NULL) { - /* NULL indicates that we have no SSA def for this block. */ - if (block->imm_dom) { - /* Grab it from our immediate dominator. We'll stash it here for - * easy access later. - */ - val->defs[block->index] = - nir_phi_builder_value_get_block_def(val, block->imm_dom); - return val->defs[block->index]; - } else { - /* No immediate dominator means that this block is either the - * start block or unreachable. In either case, the value is - * undefined so we need an SSA undef. - */ - nir_ssa_undef_instr *undef = - nir_ssa_undef_instr_create(val->builder->shader, - val->num_components, - val->bit_size); - nir_instr_insert(nir_before_cf_list(&val->builder->impl->body), - &undef->instr); - val->defs[block->index] = &undef->def; - return &undef->def; - } - } else if (val->defs[block->index] == NEEDS_PHI) { + /* Crawl up the dominance tree and find the closest dominator for which we + * have a valid ssa_def, if any. + */ + nir_block *dom = block; + struct hash_entry *he = NULL; + + while (dom != NULL) { + he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)); + 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) { + /* No dominator means either that we crawled to the top without ever + * finding a definition or that this block is unreachable. In either + * case, the value is undefined so we need an SSA undef. + */ + nir_ssa_undef_instr *undef = + nir_ssa_undef_instr_create(val->builder->shader, + val->num_components, + val->bit_size); + nir_instr_insert(nir_before_cf_list(&val->builder->impl->body), + &undef->instr); + def = &undef->def; + } 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. @@ -224,24 +235,40 @@ nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val, nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader); nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components, val->bit_size, NULL); - phi->instr.block = block; + phi->instr.block = dom; exec_list_push_tail(&val->phis, &phi->instr.node); - val->defs[block->index] = &phi->dest.ssa; - return &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(). */ - return val->defs[block->index]; + def = (struct nir_ssa_def *) he->data; } + + /* Walk the chain and stash the def in all of the applicable blocks. We do + * this for two reasons: + * + * 1) To speed up lookup next time even if the next time is called from a + * block that is not dominated by this one. + * 2) To avoid unneeded recreation of phi nodes and undefs. + */ + for (dom = block; dom != NULL; dom = dom->imm_dom) { + if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL) + break; + + nir_phi_builder_value_set_block_def(val, dom, def); + } + + return def; } static int compare_blocks(const void *_a, const void *_b) { - nir_block * const * a = _a; - nir_block * const * b = _b; + const nir_block * const * a = _a; + const nir_block * const * b = _b; return (*a)->index - (*b)->index; } @@ -250,7 +277,7 @@ void nir_phi_builder_finish(struct nir_phi_builder *pb) { const unsigned num_blocks = pb->num_blocks; - NIR_VLA(nir_block *, preds, num_blocks); + nir_block **preds = rzalloc_array(pb, nir_block *, num_blocks); foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) { /* We treat the linked list of phi nodes like a worklist. The list is @@ -275,7 +302,6 @@ nir_phi_builder_finish(struct nir_phi_builder *pb) * XXX: Calling qsort this many times seems expensive. */ int num_preds = 0; - struct set_entry *entry; set_foreach(phi->instr.block->predecessors, entry) preds[num_preds++] = (nir_block *)entry->key; qsort(preds, num_preds, sizeof(*preds), compare_blocks);