[Mesa-dev] [PATCH 057/133] nir: Add a better out-of-SSA pass
Jason Ekstrand
jason at jlekstrand.net
Mon Dec 15 22:05:07 PST 2014
This commit rewrites the out-of-SSA pass to not be nearly as naieve. It's
based on "Revisiting Out-of-SSA Translation for Correctness, Code Quality,
and Efficiency" by Boissinot et. al. It should be fairly close to
state-of-the art.
---
src/glsl/nir/nir_from_ssa.c | 793 +++++++++++++++++++++++++++++++++++++++-----
1 file changed, 715 insertions(+), 78 deletions(-)
diff --git a/src/glsl/nir/nir_from_ssa.c b/src/glsl/nir/nir_from_ssa.c
index a26f0c4..62a54fe 100644
--- a/src/glsl/nir/nir_from_ssa.c
+++ b/src/glsl/nir/nir_from_ssa.c
@@ -28,54 +28,474 @@
#include "nir.h"
/*
- * Implements a quick-and-dirty out-of-ssa pass.
+ * This file implements an out-of-SSA pass as described in "Revisiting
+ * Out-of-SSA Translation for Correctness, Code Quality, and Efficiency" by
+ * Boissinot et. al.
*/
struct from_ssa_state {
void *mem_ctx;
void *dead_ctx;
struct hash_table *ssa_table;
- nir_function_impl *current_impl;
+ struct hash_table *merge_node_table;
+ nir_instr *instr;
+ nir_function_impl *impl;
};
+/* Returns true if a dominates b */
static bool
-rewrite_ssa_src(nir_src *src, void *void_state)
+ssa_def_dominates(nir_ssa_def *a, nir_ssa_def *b)
+{
+ if (a->live_index == 0) {
+ /* SSA undefs always dominate */
+ return true;
+ } else if (b->live_index < a->live_index) {
+ return false;
+ } else if (a->parent_instr->block == b->parent_instr->block) {
+ return a->live_index <= b->live_index;
+ } else {
+ nir_block *block = b->parent_instr->block;
+ while (block->imm_dom != NULL) {
+ if (block->imm_dom == a->parent_instr->block)
+ return true;
+ block = block->imm_dom;
+ }
+ return false;
+ }
+}
+
+
+/* The following data structure, which I have named merge_set is a way of
+ * representing a set registers of non-interfering registers. This is
+ * based on the concept of a "dominence forest" presented in "Fast Copy
+ * Coalescing and Live-Range Identification" by Budimlic et. al. but the
+ * implementation concept is taken from "Revisiting Out-of-SSA Translation
+ * for Correctness, Code Quality, and Efficiency" by Boissinot et. al..
+ *
+ * Each SSA definition is associated with a merge_node and the association
+ * is represented by a combination of a hash table and the "def" parameter
+ * in the merge_node structure. The merge_set stores a linked list of
+ * merge_node's in dominence order of the ssa definitions. (Since the
+ * liveness analysis pass indexes the SSA values in dominence order for us,
+ * this is an easy thing to keep up.) It is assumed that no pair of the
+ * nodes in a given set interfere. Merging two sets or checking for
+ * interference can be done in a single linear-time merge-sort walk of the
+ * two lists of nodes.
+ */
+struct merge_set;
+
+typedef struct {
+ struct exec_node node;
+ struct merge_set *set;
+ nir_ssa_def *def;
+} merge_node;
+
+typedef struct merge_set {
+ struct exec_list nodes;
+ unsigned size;
+ nir_register *reg;
+} merge_set;
+
+#if 0
+static void
+merge_set_dump(merge_set *set, FILE *fp)
+{
+ nir_ssa_def *dom[set->size];
+ int dom_idx = -1;
+
+ foreach_list_typed(merge_node, node, node, &set->nodes) {
+ while (dom_idx >= 0 && !ssa_def_dominates(dom[dom_idx], node->def))
+ dom_idx--;
+
+ for (int i = 0; i <= dom_idx; i++)
+ fprintf(fp, " ");
+
+ if (node->def->name)
+ fprintf(fp, "ssa_%d /* %s */\n", node->def->index, node->def->name);
+ else
+ fprintf(fp, "ssa_%d\n", node->def->index);
+
+ dom[++dom_idx] = node->def;
+ }
+}
+#endif
+
+static merge_node *
+get_merge_node(nir_ssa_def *def, struct from_ssa_state *state)
+{
+ struct hash_entry *entry =
+ _mesa_hash_table_search(state->merge_node_table,
+ _mesa_hash_pointer(def), def);
+ if (entry)
+ return entry->data;
+
+ merge_set *set = ralloc(state->dead_ctx, merge_set);
+ exec_list_make_empty(&set->nodes);
+ set->size = 1;
+ set->reg = NULL;
+
+ merge_node *node = ralloc(state->dead_ctx, merge_node);
+ node->set = set;
+ node->def = def;
+ exec_list_push_head(&set->nodes, &node->node);
+
+ _mesa_hash_table_insert(state->merge_node_table,
+ _mesa_hash_pointer(def), def, node);
+
+ return node;
+}
+
+static bool
+merge_nodes_interfere(merge_node *a, merge_node *b)
+{
+ return nir_ssa_defs_interfere(a->def, b->def);
+}
+
+/* Merges b into a */
+static merge_set *
+merge_merge_sets(merge_set *a, merge_set *b)
+{
+ struct exec_node *an = exec_list_get_head(&a->nodes);
+ struct exec_node *bn = exec_list_get_head(&b->nodes);
+ while (!exec_node_is_tail_sentinel(bn)) {
+ merge_node *a_node = exec_node_data(merge_node, an, node);
+ merge_node *b_node = exec_node_data(merge_node, bn, node);
+
+ if (exec_node_is_tail_sentinel(an) ||
+ a_node->def->live_index > b_node->def->live_index) {
+ struct exec_node *next = bn->next;
+ exec_node_remove(bn);
+ exec_node_insert_node_before(an, bn);
+ exec_node_data(merge_node, bn, node)->set = a;
+ bn = next;
+ } else {
+ an = an->next;
+ }
+ }
+
+ a->size += b->size;
+ b->size = 0;
+
+ return a;
+}
+
+/* Checks for any interference between two merge sets
+ *
+ * This is an implementation of Algorithm 2 in "Revisiting Out-of-SSA
+ * Translation for Correctness, Code Quality, and Efficiency" by
+ * Boissinot et. al.
+ */
+static bool
+merge_sets_interfere(merge_set *a, merge_set *b)
+{
+ merge_node *dom[a->size + b->size];
+ int dom_idx = -1;
+
+ struct exec_node *an = exec_list_get_head(&a->nodes);
+ struct exec_node *bn = exec_list_get_head(&b->nodes);
+ while (!exec_node_is_tail_sentinel(an) ||
+ !exec_node_is_tail_sentinel(bn)) {
+
+ merge_node *current;
+ if (exec_node_is_tail_sentinel(an)) {
+ current = exec_node_data(merge_node, bn, node);
+ bn = bn->next;
+ } else if (exec_node_is_tail_sentinel(bn)) {
+ current = exec_node_data(merge_node, an, node);
+ an = an->next;
+ } else {
+ merge_node *a_node = exec_node_data(merge_node, an, node);
+ merge_node *b_node = exec_node_data(merge_node, bn, node);
+
+ if (a_node->def->live_index <= b_node->def->live_index) {
+ current = a_node;
+ an = an->next;
+ } else {
+ current = b_node;
+ bn = bn->next;
+ }
+ }
+
+ while (dom_idx >= 0 &&
+ !ssa_def_dominates(dom[dom_idx]->def, current->def))
+ dom_idx--;
+
+ if (dom_idx >= 0 && merge_nodes_interfere(current, dom[dom_idx]))
+ return true;
+
+ dom[++dom_idx] = current;
+ }
+
+ return false;
+}
+
+static nir_parallel_copy_instr *
+block_get_parallel_copy_at_end(nir_block *block, void *mem_ctx)
+{
+ nir_instr *last_instr = nir_block_last_instr(block);
+
+ /* First we try and find a parallel copy if it already exists. If the
+ * last instruction is a jump, it will be right before the jump;
+ * otherwise, it will be the last instruction.
+ */
+ nir_instr *pcopy_instr;
+ if (last_instr != NULL && last_instr->type == nir_instr_type_jump)
+ pcopy_instr = nir_instr_prev(last_instr);
+ else
+ pcopy_instr = last_instr;
+
+ if (pcopy_instr != NULL &&
+ pcopy_instr->type == nir_instr_type_parallel_copy) {
+ /* A parallel copy already exists. */
+ nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(pcopy_instr);
+
+ /* This parallel copy may be the copy for the beginning of some
+ * block, so we need to check for that before we return it.
+ */
+ if (pcopy->at_end)
+ return pcopy;
+ }
+
+ /* At this point, we haven't found a suitable parallel copy, so we
+ * have to create one.
+ */
+ nir_parallel_copy_instr *pcopy = nir_parallel_copy_instr_create(mem_ctx);
+ pcopy->at_end = true;
+
+ if (last_instr && last_instr->type == nir_instr_type_jump) {
+ nir_instr_insert_before(last_instr, &pcopy->instr);
+ } else {
+ nir_instr_insert_after_block(block, &pcopy->instr);
+ }
+
+ return pcopy;
+}
+
+static bool
+isolate_phi_nodes_block(nir_block *block, void *void_state)
{
struct from_ssa_state *state = void_state;
- if (src->is_ssa) {
- struct hash_entry *entry =
- _mesa_hash_table_search(state->ssa_table,
- _mesa_hash_pointer(src->ssa),
- src->ssa);
- assert(entry);
- memset(src, 0, sizeof *src);
- src->reg.reg = (nir_register *)entry->data;
+ nir_instr *last_phi_instr = NULL;
+ nir_foreach_instr(block, instr) {
+ /* Phi nodes only ever come at the start of a block */
+ if (instr->type != nir_instr_type_phi)
+ break;
+
+ last_phi_instr = instr;
+ }
+
+ /* If we don't have any phi's, then there's nothing for us to do. */
+ if (last_phi_instr == NULL)
+ return true;
+
+ /* If we have phi nodes, we need to create a parallel copy at the
+ * start of this block but after the phi nodes.
+ */
+ nir_parallel_copy_instr *block_pcopy =
+ nir_parallel_copy_instr_create(state->dead_ctx);
+ nir_instr_insert_after(last_phi_instr, &block_pcopy->instr);
+
+ nir_foreach_instr(block, instr) {
+ /* Phi nodes only ever come at the start of a block */
+ if (instr->type != nir_instr_type_phi)
+ break;
+
+ nir_phi_instr *phi = nir_instr_as_phi(instr);
+ assert(phi->dest.is_ssa);
+ foreach_list_typed(nir_phi_src, src, node, &phi->srcs) {
+ nir_parallel_copy_instr *pcopy =
+ block_get_parallel_copy_at_end(src->pred, state->dead_ctx);
+
+ nir_parallel_copy_copy *copy = ralloc(state->dead_ctx,
+ nir_parallel_copy_copy);
+ exec_list_push_tail(&pcopy->copies, ©->node);
+
+ copy->src = nir_src_copy(src->src, state->dead_ctx);
+ _mesa_set_add(src->src.ssa->uses,
+ _mesa_hash_pointer(&pcopy->instr), &pcopy->instr);
+
+ copy->dest.is_ssa = true;
+ nir_ssa_def_init(state->impl, &pcopy->instr, ©->dest.ssa,
+ phi->dest.ssa.num_components, src->src.ssa->name);
+
+ struct set_entry *entry = _mesa_set_search(src->src.ssa->uses,
+ _mesa_hash_pointer(instr),
+ instr);
+ if (entry)
+ /* It is possible that a phi node can use the same source twice
+ * but for different basic blocks. If that happens, entry will
+ * be NULL because we already deleted it. This is safe
+ * because, by the time the loop is done, we will have deleted
+ * all of the sources of the phi from their respective use sets
+ * and moved them to the parallel copy definitions.
+ */
+ _mesa_set_remove(src->src.ssa->uses, entry);
+
+ src->src.ssa = ©->dest.ssa;
+ _mesa_set_add(copy->dest.ssa.uses, _mesa_hash_pointer(instr), instr);
+ }
+
+ nir_parallel_copy_copy *copy = ralloc(state->dead_ctx,
+ nir_parallel_copy_copy);
+ exec_list_push_tail(&block_pcopy->copies, ©->node);
+
+ copy->dest.is_ssa = true;
+ nir_ssa_def_init(state->impl, &block_pcopy->instr, ©->dest.ssa,
+ phi->dest.ssa.num_components, phi->dest.ssa.name);
+
+ nir_src copy_dest_src = {
+ .ssa = ©->dest.ssa,
+ .is_ssa = true,
+ };
+ nir_ssa_def_rewrite_uses(&phi->dest.ssa, copy_dest_src, state->mem_ctx);
+
+ copy->src.is_ssa = true;
+ copy->src.ssa = &phi->dest.ssa;
+ _mesa_set_add(phi->dest.ssa.uses,
+ _mesa_hash_pointer(&block_pcopy->instr),
+ &block_pcopy->instr);
+ }
+
+ return true;
+}
+
+static bool
+coalesce_phi_nodes_block(nir_block *block, void *void_state)
+{
+ struct from_ssa_state *state = void_state;
+
+ nir_foreach_instr(block, instr) {
+ /* Phi nodes only ever come at the start of a block */
+ if (instr->type != nir_instr_type_phi)
+ break;
+
+ nir_phi_instr *phi = nir_instr_as_phi(instr);
+
+ assert(phi->dest.is_ssa);
+ merge_node *dest_node = get_merge_node(&phi->dest.ssa, state);
+
+ foreach_list_typed(nir_phi_src, src, node, &phi->srcs) {
+ assert(src->src.is_ssa);
+ merge_node *src_node = get_merge_node(src->src.ssa, state);
+ if (src_node->set != dest_node->set)
+ merge_merge_sets(dest_node->set, src_node->set);
+ }
+ }
+
+ return true;
+}
+
+static void
+agressive_coalesce_parallel_copy(nir_parallel_copy_instr *pcopy,
+ struct from_ssa_state *state)
+{
+ foreach_list_typed_safe(nir_parallel_copy_copy, copy, node, &pcopy->copies) {
+ if (!copy->src.is_ssa)
+ continue;
+
+ /* Don't try and coalesce these */
+ if (copy->dest.ssa.num_components != copy->src.ssa->num_components)
+ continue;
+
+ merge_node *src_node = get_merge_node(copy->src.ssa, state);
+ merge_node *dest_node = get_merge_node(©->dest.ssa, state);
+
+ if (src_node->set == dest_node->set)
+ continue;
+
+ if (!merge_sets_interfere(src_node->set, dest_node->set))
+ merge_merge_sets(src_node->set, dest_node->set);
+ }
+}
+
+static bool
+agressive_coalesce_block(nir_block *block, void *void_state)
+{
+ struct from_ssa_state *state = void_state;
+
+ nir_foreach_instr(block, instr) {
+ /* Phi nodes only ever come at the start of a block */
+ if (instr->type != nir_instr_type_phi) {
+ if (instr->type != nir_instr_type_parallel_copy)
+ break; /* The parallel copy must be right after the phis */
+
+ nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(instr);
+
+ agressive_coalesce_parallel_copy(pcopy, state);
+
+ if (pcopy->at_end)
+ return true;
+
+ break;
+ }
+ }
+
+ nir_instr *last_instr = nir_block_last_instr(block);
+ if (last_instr && last_instr->type == nir_instr_type_parallel_copy) {
+ nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(last_instr);
+ if (pcopy->at_end)
+ agressive_coalesce_parallel_copy(pcopy, state);
}
return true;
}
static nir_register *
-reg_create_from_def(nir_ssa_def *def, struct from_ssa_state *state)
+get_register_for_ssa_def(nir_ssa_def *def, struct from_ssa_state *state)
+{
+ struct hash_entry *entry =
+ _mesa_hash_table_search(state->merge_node_table,
+ _mesa_hash_pointer(def), def);
+ if (entry) {
+ merge_node *node = (merge_node *)entry->data;
+
+ /* If it doesn't have a register yet, create one. Note that all of
+ * the things in the merge set should be the same so it doesn't
+ * matter which node's definition we use.
+ */
+ if (node->set->reg == NULL) {
+ node->set->reg = nir_local_reg_create(state->impl);
+ node->set->reg->name = def->name;
+ node->set->reg->num_components = def->num_components;
+ node->set->reg->num_array_elems = 0;
+ }
+
+ return node->set->reg;
+ }
+
+ entry = _mesa_hash_table_search(state->ssa_table,
+ _mesa_hash_pointer(def), def);
+ if (entry) {
+ return (nir_register *)entry->data;
+ } else {
+ nir_register *reg = nir_local_reg_create(state->impl);
+ reg->name = def->name;
+ reg->num_components = def->num_components;
+ reg->num_array_elems = 0;
+
+ _mesa_hash_table_insert(state->ssa_table,
+ _mesa_hash_pointer(def), def, reg);
+ return reg;
+ }
+}
+
+static bool
+rewrite_ssa_src(nir_src *src, void *void_state)
{
- nir_register *reg = nir_local_reg_create(state->current_impl);
- reg->name = def->name;
- reg->num_components = def->num_components;
- reg->num_array_elems = 0;
+ struct from_ssa_state *state = void_state;
- /* Might as well steal the use-def information from SSA */
- _mesa_set_destroy(reg->uses, NULL);
- reg->uses = def->uses;
- _mesa_set_destroy(reg->if_uses, NULL);
- reg->if_uses = def->if_uses;
- _mesa_set_add(reg->defs, _mesa_hash_pointer(def->parent_instr),
- def->parent_instr);
+ if (src->is_ssa) {
+ /* We don't need to remove it from the uses set because that is going
+ * away. We just need to add it to the one for the register. */
+ nir_register *reg = get_register_for_ssa_def(src->ssa, state);
+ memset(src, 0, sizeof *src);
+ src->reg.reg = reg;
- /* Add the new register to the table and rewrite the destination */
- _mesa_hash_table_insert(state->ssa_table, _mesa_hash_pointer(def), def, reg);
+ _mesa_set_add(reg->uses, _mesa_hash_pointer(state->instr), state->instr);
+ }
- return reg;
+ return true;
}
static bool
@@ -84,82 +504,285 @@ rewrite_ssa_dest(nir_dest *dest, void *void_state)
struct from_ssa_state *state = void_state;
if (dest->is_ssa) {
- nir_register *reg = reg_create_from_def(&dest->ssa, state);
+ _mesa_set_destroy(dest->ssa.uses, NULL);
+ _mesa_set_destroy(dest->ssa.if_uses, NULL);
+
+ nir_register *reg = get_register_for_ssa_def(&dest->ssa, state);
memset(dest, 0, sizeof *dest);
dest->reg.reg = reg;
+
+ _mesa_set_add(reg->defs, _mesa_hash_pointer(state->instr), state->instr);
}
return true;
}
+/* Resolves ssa definitions to registers. While we're at it, we also
+ * remove phi nodes and ssa_undef instructions
+ */
static bool
-convert_from_ssa_block(nir_block *block, void *void_state)
+resolve_registers_block(nir_block *block, void *void_state)
{
struct from_ssa_state *state = void_state;
nir_foreach_instr_safe(block, instr) {
- if (instr->type == nir_instr_type_ssa_undef) {
- nir_ssa_undef_instr *undef = nir_instr_as_ssa_undef(instr);
- reg_create_from_def(&undef->def, state);
- exec_node_remove(&instr->node);
+ state->instr = instr;
+ nir_foreach_src(instr, rewrite_ssa_src, state);
+ nir_foreach_dest(instr, rewrite_ssa_dest, state);
+
+ if (instr->type == nir_instr_type_ssa_undef ||
+ instr->type == nir_instr_type_phi) {
+ nir_instr_remove(instr);
ralloc_steal(state->dead_ctx, instr);
- } else {
- nir_foreach_src(instr, rewrite_ssa_src, state);
- nir_foreach_dest(instr, rewrite_ssa_dest, state);
+ continue;
}
}
+ state->instr = NULL;
nir_if *following_if = nir_block_following_if(block);
- if (following_if)
- rewrite_ssa_src(&following_if->condition, state);
+ if (following_if && following_if->condition.is_ssa) {
+ nir_register *reg = get_register_for_ssa_def(following_if->condition.ssa,
+ state);
+ memset(&following_if->condition, 0, sizeof following_if->condition);
+ following_if->condition.reg.reg = reg;
+
+ _mesa_set_add(reg->if_uses, _mesa_hash_pointer(following_if),
+ following_if);
+ }
return true;
}
+static void
+emit_copy(nir_parallel_copy_instr *pcopy, nir_src src, nir_src dest_src,
+ void *mem_ctx)
+{
+ assert(!dest_src.is_ssa &&
+ dest_src.reg.indirect == NULL &&
+ dest_src.reg.base_offset == 0);
+ nir_dest dest = {
+ .reg.reg = dest_src.reg.reg,
+ .reg.indirect = NULL,
+ .reg.base_offset = 0,
+ .is_ssa = false,
+ };
+
+ if (src.is_ssa)
+ assert(src.ssa->num_components >= dest.reg.reg->num_components);
+ else
+ assert(src.reg.reg->num_components >= dest.reg.reg->num_components);
+
+ nir_alu_instr *mov = nir_alu_instr_create(mem_ctx, nir_op_imov);
+ mov->src[0].src = nir_src_copy(src, mem_ctx);
+ mov->dest.dest = nir_dest_copy(dest, mem_ctx);
+ mov->dest.write_mask = (1 << dest.reg.reg->num_components) - 1;
+
+ nir_instr_insert_before(&pcopy->instr, &mov->instr);
+}
+
+/* Resolves a single parallel copy operation into a sequence of mov's
+ *
+ * This is based on Algorithm 1 from "Revisiting Out-of-SSA Translation for
+ * Correctness, Code Quality, and Efficiency" by Boissinot et. al..
+ * However, I never got the algorithm to work as written, so this version
+ * is slightly modified.
+ *
+ * The algorithm works by playing this little shell game with the values.
+ * We start by recording where every source value is and which source value
+ * each destination value should recieve. We then grab any copy whose
+ * destination is "empty", i.e. not used as a source, and do the following:
+ * - Find where its source value currently lives
+ * - Emit the move instruction
+ * - Set the location of the source value to the destination
+ * - Mark the location containing the source value
+ * - Mark the destination as no longer needing to be copied
+ *
+ * When we run out of "empty" destinations, we have a cycle and so we
+ * create a temporary register, copy to that register, and mark the value
+ * we copied as living in that temporary. Now, the cycle is broken, so we
+ * can continue with the above steps.
+ */
+static void
+resolve_parallel_copy(nir_parallel_copy_instr *pcopy,
+ struct from_ssa_state *state)
+{
+ unsigned num_copies = 0;
+ foreach_list_typed_safe(nir_parallel_copy_copy, copy, node, &pcopy->copies) {
+ /* Sources may be SSA */
+ if (!copy->src.is_ssa && copy->src.reg.reg == copy->dest.reg.reg)
+ continue;
+
+ /* Set both indices equal to UINT_MAX to mark them as not indexed yet. */
+ num_copies++;
+ }
+
+ if (num_copies == 0) {
+ /* Hooray, we don't need any copies! */
+ nir_instr_remove(&pcopy->instr);
+ return;
+ }
+
+ /* The register/source corresponding to the given index */
+ nir_src values[num_copies * 2];
+ memset(values, 0, sizeof values);
+
+ /* The current location of a given piece of data */
+ int loc[num_copies * 2];
+
+ /* The piece of data that the given piece of data is to be copied from */
+ int pred[num_copies * 2];
+
+ /* Initialize loc and pred. We will use -1 for "null" */
+ memset(loc, -1, sizeof loc);
+ memset(pred, -1, sizeof pred);
+
+ /* The destinations we have yet to properly fill */
+ int to_do[num_copies * 2];
+ int to_do_idx = -1;
+
+ /* Now we set everything up:
+ * - All values get assigned a temporary index
+ * - Current locations are set from sources
+ * - Predicessors are recorded from sources and destinations
+ */
+ int num_vals = 0;
+ foreach_list_typed(nir_parallel_copy_copy, copy, node, &pcopy->copies) {
+ /* Sources may be SSA */
+ if (!copy->src.is_ssa && copy->src.reg.reg == copy->dest.reg.reg)
+ continue;
+
+ int src_idx = -1;
+ for (int i = 0; i < num_vals; ++i) {
+ if (nir_srcs_equal(values[i], copy->src))
+ src_idx = i;
+ }
+ if (src_idx < 0) {
+ src_idx = num_vals++;
+ values[src_idx] = copy->src;
+ }
+
+ nir_src dest_src = {
+ .reg.reg = copy->dest.reg.reg,
+ .reg.indirect = NULL,
+ .reg.base_offset = 0,
+ .is_ssa = false,
+ };
+
+ int dest_idx = -1;
+ for (int i = 0; i < num_vals; ++i) {
+ if (nir_srcs_equal(values[i], dest_src))
+ dest_idx = i;
+ }
+ if (dest_idx < 0) {
+ dest_idx = num_vals++;
+ values[dest_idx] = dest_src;
+ }
+
+ loc[src_idx] = src_idx;
+ pred[dest_idx] = src_idx;
+
+ to_do[++to_do_idx] = dest_idx;
+ }
+
+ /* Currently empty destinations we can go ahead and fill */
+ int ready[num_copies * 2];
+ int ready_idx = -1;
+
+ /* Mark the ones that are ready for copying. We know an index is a
+ * destination if it has a predecessor and it's ready for copying if
+ * it's not marked as containing data.
+ */
+ for (int i = 0; i < num_vals; i++) {
+ if (pred[i] != -1 && loc[i] == -1)
+ ready[++ready_idx] = i;
+ }
+
+ while (to_do_idx >= 0) {
+ while (ready_idx >= 0) {
+ int b = ready[ready_idx--];
+ int a = pred[b];
+ emit_copy(pcopy, values[loc[a]], values[b], state->mem_ctx);
+
+ /* If any other copies want a they can find it at b */
+ loc[a] = b;
+
+ /* b has been filled, mark it as not needing to be copied */
+ pred[b] = -1;
+
+ /* If a needs to be filled, it's ready for copying now */
+ if (pred[a] != -1)
+ ready[++ready_idx] = a;
+ }
+ int b = to_do[to_do_idx--];
+ if (pred[b] == -1)
+ continue;
+
+ /* If we got here, then we don't have any more trivial copies that we
+ * can do. We have to break a cycle, so we create a new temporary
+ * register for that purpose. Normally, if going out of SSA after
+ * register allocation, you would want to avoid creating temporary
+ * registers. However, we are going out of SSA before register
+ * allocation, so we would rather not create extra register
+ * dependencies for the backend to deal with. If it wants, the
+ * backend can coalesce the (possibly multiple) temporaries.
+ */
+ assert(num_vals < num_copies * 2);
+ nir_register *reg = nir_local_reg_create(state->impl);
+ reg->name = "copy_temp";
+ reg->num_array_elems = 0;
+ if (values[b].is_ssa)
+ reg->num_components = values[b].ssa->num_components;
+ else
+ reg->num_components = values[b].reg.reg->num_components;
+ values[num_vals].is_ssa = false;
+ values[num_vals].reg.reg = reg;
+
+ emit_copy(pcopy, values[b], values[num_vals], state->mem_ctx);
+ loc[b] = num_vals;
+ ready[++ready_idx] = b;
+ num_vals++;
+ }
+
+ nir_instr_remove(&pcopy->instr);
+}
+
+/* Resolves the parallel copies in a block. Each block can have at most
+ * two: One at the beginning, right after all the phi noces, and one at
+ * the end (or right before the final jump if it exists).
+ */
static bool
-remove_phi_nodes(nir_block *block, void *void_state)
+resolve_parallel_copies_block(nir_block *block, void *void_state)
{
struct from_ssa_state *state = void_state;
- nir_foreach_instr_safe(block, instr) {
- /* Phi nodes only ever come at the start of a block */
- if (instr->type != nir_instr_type_phi)
- break;
+ /* At this point, we have removed all of the phi nodes. If a parallel
+ * copy existed right after the phi nodes in this block, it is now the
+ * first instruction.
+ */
+ nir_instr *first_instr = nir_block_first_instr(block);
+ if (first_instr == NULL)
+ return true; /* Empty, nothing to do. */
- nir_foreach_dest(instr, rewrite_ssa_dest, state);
+ if (first_instr->type == nir_instr_type_parallel_copy) {
+ nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(first_instr);
- nir_phi_instr *phi = nir_instr_as_phi(instr);
- foreach_list_typed(nir_phi_src, src, node, &phi->srcs) {
- assert(src->src.is_ssa);
- struct hash_entry *entry =
- _mesa_hash_table_search(state->ssa_table,
- _mesa_hash_pointer(src->src.ssa),
- src->src.ssa);
- nir_alu_instr *mov = nir_alu_instr_create(state->mem_ctx, nir_op_imov);
- mov->dest.dest = nir_dest_copy(phi->dest, state->mem_ctx);
- if (entry) {
- nir_register *reg = (nir_register *)entry->data;
- mov->src[0].src.reg.reg = reg;
- mov->dest.write_mask = (1 << reg->num_components) - 1;
- } else {
- mov->src[0].src = nir_src_copy(src->src, state->mem_ctx);
- mov->dest.write_mask = (1 << src->src.ssa->num_components) - 1;
- }
+ resolve_parallel_copy(pcopy, state);
+ }
- nir_instr *block_end = nir_block_last_instr(src->pred);
- if (block_end && block_end->type == nir_instr_type_jump) {
- /* If the last instruction in the block is a jump, we want to
- * place the moves after the jump. Otherwise, we want to place
- * them at the very end.
- */
- exec_node_insert_node_before(&block_end->node, &mov->instr.node);
- } else {
- exec_list_push_tail(&src->pred->instr_list, &mov->instr.node);
- }
- }
+ nir_instr *last_instr = nir_block_last_instr(block);
+ if (last_instr == NULL)
+ return true; /* Now empty, nothing to do. */
- exec_node_remove(&instr->node);
- ralloc_steal(state->dead_ctx, instr);
+ /* If the last instruction is a jump, the parallel copy will be before
+ * the jump.
+ */
+ if (last_instr->type == nir_instr_type_jump)
+ last_instr = nir_instr_prev(last_instr);
+
+ if (last_instr && last_instr->type == nir_instr_type_parallel_copy) {
+ nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(last_instr);
+ if (pcopy->at_end)
+ resolve_parallel_copy(pcopy, state);
}
return true;
@@ -172,15 +795,29 @@ nir_convert_from_ssa_impl(nir_function_impl *impl)
state.mem_ctx = ralloc_parent(impl);
state.dead_ctx = ralloc_context(NULL);
- state.current_impl = impl;
+ state.impl = impl;
+ state.merge_node_table = _mesa_hash_table_create(NULL,
+ _mesa_key_pointer_equal);
+
+ nir_foreach_block(impl, isolate_phi_nodes_block, &state);
+
+ nir_metadata_dirty(impl, nir_metadata_block_index |
+ nir_metadata_dominance);
+ nir_metadata_require(impl, nir_metadata_live_variables |
+ nir_metadata_dominance);
+
+ nir_foreach_block(impl, coalesce_phi_nodes_block, &state);
+ nir_foreach_block(impl, agressive_coalesce_block, &state);
+
state.ssa_table = _mesa_hash_table_create(NULL, _mesa_key_pointer_equal);
+ nir_foreach_block(impl, resolve_registers_block, &state);
- nir_foreach_block(impl, remove_phi_nodes, &state);
- nir_foreach_block(impl, convert_from_ssa_block, &state);
+ nir_foreach_block(impl, resolve_parallel_copies_block, &state);
- /* Clean up dead instructions and the hash table */
- ralloc_free(state.dead_ctx);
+ /* Clean up dead instructions and the hash tables */
_mesa_hash_table_destroy(state.ssa_table, NULL);
+ _mesa_hash_table_destroy(state.merge_node_table, NULL);
+ ralloc_free(state.dead_ctx);
}
void
--
2.2.0
More information about the mesa-dev
mailing list