/* Needed so we can create phis and undefs */
unsigned num_components;
+ unsigned bit_size;
/* The list of phi nodes associated with this value. Phi nodes are not
* added directly. Instead, they are created, the instr->block pointer
*/
struct exec_list phis;
- /* Array of SSA defs, indexed by block. If a phi needs to be inserted
- * in a given block, it will have the magic value NEEDS_PHI.
+ /* 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];
+ 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;
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);
struct nir_phi_builder_value *
nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
- const BITSET_WORD *defs)
+ unsigned bit_size, const BITSET_WORD *defs)
{
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;
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;
- /*
- * If there's more than one return statement, then the end block
+ /* If there's more than one return statement, then the end block
* can be a join point for some definitions. However, there are
* no instructions in the end block, so nothing would use those
* phi nodes. Of course, we couldn't place those phi nodes
if (next == pb->impl->end_block)
continue;
- if (val->defs[next->index] == NULL) {
- val->defs[next->index] = NEEDS_PHI;
+ 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().
+ */
+ 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;
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)
{
- if (val->defs[block->index] == NULL) {
- 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);
- 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) {
- /* If we need a phi instruction, go ahead and create one but don't
- * add it to the program yet. Later, we'll go through and set up phi
- * sources and add the instructions will be added at that time.
+ /* 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.
+ *
+ * Because a phi node may use SSA defs that it does not dominate (this
+ * happens in loops), we do not yet have enough information to fully
+ * fill out the phi node. Instead, the phi nodes we create here will be
+ * empty (have no sources) and won't actually be placed in the block's
+ * instruction list yet. Later, in nir_phi_builder_finish(), we walk
+ * over all of the phi instructions, fill out the sources lists, and
+ * place them at the top of their respective block's instruction list.
+ *
+ * Creating phi nodes on-demand allows us to avoid creating dead phi
+ * nodes that will just get deleted later. While this probably isn't a
+ * big win for a full into-SSA pass, other users may use the phi builder
+ * to make small SSA form repairs where most of the phi nodes will never
+ * be used.
*/
nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
- nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components, NULL);
- phi->instr.block = block;
+ nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components,
+ val->bit_size, NULL);
+ 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 {
- return val->defs[block->index];
+ /* 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 = (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;
}
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 can't iterate over the list of phis normally because we are
- * removing them as we go and, in some cases, adding new phis as we
- * build the source lists of others.
+ /* We treat the linked list of phi nodes like a worklist. The list is
+ * pre-populated by calls to nir_phi_builder_value_get_block_def() that
+ * create phi nodes. As we fill in the sources of phi nodes, more may
+ * be created and are added to the end of the list.
+ *
+ * Because we are adding and removing phi nodes from the list as we go,
+ * we can't iterate over it normally. Instead, we just iterate until
+ * the list is empty.
*/
while (!exec_list_is_empty(&val->phis)) {
struct exec_node *head = exec_list_get_head(&val->phis);
* 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);
projects / mesa.git / blobdiff