On Wed, Dec 17, 2014 at 3:30 PM, Connor Abbott <cwabbo...@gmail.com> wrote:
>
> Whew! Other than a few minor things below,
>
> Reviewed-by: Connor Abbott <cwabbo...@gmail.com>
>
> I tried to understand it all as much as I could, but it is rather
> tricky... but I can't suggest anything to make it easier to
> understand, after all the paper itself is rather tricky and your
> comments help a lot. If anyone has any ideas, please say something...
>
> On Tue, Dec 16, 2014 at 1:05 AM, Jason Ekstrand <ja...@jlekstrand.net>
> wrote:
> > 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. */
>
> Stale comment?
>
Removed.
>
> > + 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;
>
> Can we add an "assert(pred[dest_idx] == -1);" here to check that we
> don't repeat the same destination more than once in the parallel copy
> (plus a comment explaining what the assertion checks)? More sanity
> checks are always better for tricky code like this.
>
Good plan. I'll go ahead and squash that change in to this patch since
it's so small. I've made a seperate patch for cleaning up the parallel
copy stuff.
--Jason
>
> > + }
> > + 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
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev@lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
