From f1c2db43dcf35d2cf4715390bd2391c28e42a8c2 Mon Sep 17 00:00:00 2001 From: marha Date: Sun, 22 Feb 2015 14:31:16 +0100 Subject: xwininfo fontconfig libX11 libXdmcp libfontenc libxcb libxcb/xcb-proto mesalib xserver xkeyboard-config mkfontscale git update 22 Feb 2015 xserver commit 3a06faf3fcdb7451125a46181f9152e8e59e9770 libxcb commit e3ec1f74637237ce500dfd0ca59f2e422da4e019 libxcb/xcb-proto commit 4c550465934164aab2449a125f75f4ca07816233 xkeyboard-config commit 26f344c93f8c6141e9233eb68088ba4fd56bc9ef libX11 commit c8e19b393defd53f046ddc2da3a16881221b3c34 libXdmcp commit 9f4cac7656b221ce2a8f97e7bd31e5e23126d001 libfontenc commit de1843aaf76015c9d99416f3122d169fe331b849 mkfontscale commit 87d628f8eec170ec13bb9feefb1ce05aed07d1d6 xwininfo commit 0c49f8f2bd56b1e77721e81030ea948386dcdf4e fontconfig commit d6d5adeb7940c0d0beb86489c2a1c2ce59e5c044 mesa commit 4359954d842caa2a9f8d4b50d70ecc789884b68b --- mesalib/src/glsl/nir/nir_from_ssa.c | 876 ++++++++++++++++++++++++++++++++++++ 1 file changed, 876 insertions(+) create mode 100644 mesalib/src/glsl/nir/nir_from_ssa.c (limited to 'mesalib/src/glsl/nir/nir_from_ssa.c') diff --git a/mesalib/src/glsl/nir/nir_from_ssa.c b/mesalib/src/glsl/nir/nir_from_ssa.c new file mode 100644 index 000000000..7c5009577 --- /dev/null +++ b/mesalib/src/glsl/nir/nir_from_ssa.c @@ -0,0 +1,876 @@ +/* + * Copyright © 2014 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Jason Ekstrand (jason@jlekstrand.net) + * + */ + +#include "nir.h" + +/* + * 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; + struct hash_table *merge_node_table; + nir_instr *instr; + nir_function_impl *impl; +}; + +/* Returns true if a dominates b */ +static bool +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 { + return nir_block_dominates(a->parent_instr->block, + b->parent_instr->block); + } +} + + +/* 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, 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, 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 bool +add_parallel_copy_to_end_of_block(nir_block *block, void *void_state) +{ + struct from_ssa_state *state = void_state; + + bool need_end_copy = false; + if (block->successors[0]) { + nir_instr *instr = nir_block_first_instr(block->successors[0]); + if (instr && instr->type == nir_instr_type_phi) + need_end_copy = true; + } + + if (block->successors[1]) { + nir_instr *instr = nir_block_first_instr(block->successors[1]); + if (instr && instr->type == nir_instr_type_phi) + need_end_copy = true; + } + + if (need_end_copy) { + /* If one of our successors has at least one phi node, we need to + * create a parallel copy at the end of the block but before the jump + * (if there is one). + */ + nir_parallel_copy_instr *pcopy = + nir_parallel_copy_instr_create(state->dead_ctx); + + nir_instr *last_instr = nir_block_last_instr(block); + 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 true; +} + +static nir_parallel_copy_instr * +get_parallel_copy_at_end_of_block(nir_block *block) +{ + nir_instr *last_instr = nir_block_last_instr(block); + if (last_instr == NULL) + return NULL; + + /* The last instruction may be a jump in which case the parallel copy is + * right before it. + */ + 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) + return nir_instr_as_parallel_copy(last_instr); + else + return NULL; +} + +/** Isolate phi nodes with parallel copies + * + * In order to solve the dependency problems with the sources and + * destinations of phi nodes, we first isolate them by adding parallel + * copies to the beginnings and ends of basic blocks. For every block with + * phi nodes, we add a parallel copy immediately following the last phi + * node that copies the destinations of all of the phi nodes to new SSA + * values. We also add a parallel copy to the end of every block that has + * a successor with phi nodes that, for each phi node in each successor, + * copies the corresponding sorce of the phi node and adjust the phi to + * used the destination of the parallel copy. + * + * In SSA form, each value has exactly one definition. What this does is + * ensure that each value used in a phi also has exactly one use. The + * destinations of phis are only used by the parallel copy immediately + * following the phi nodes and. Thanks to the parallel copy at the end of + * the predecessor block, the sources of phi nodes are are the only use of + * that value. This allows us to immediately assign all the sources and + * destinations of any given phi node to the same register without worrying + * about interference at all. We do coalescing to get rid of the parallel + * copies where possible. + * + * Before this pass can be run, we have to iterate over the blocks with + * add_parallel_copy_to_end_of_block to ensure that the parallel copies at + * the ends of blocks exist. We can create the ones at the beginnings as + * we go, but the ones at the ends of blocks need to be created ahead of + * time because of potential back-edges in the CFG. + */ +static bool +isolate_phi_nodes_block(nir_block *block, void *void_state) +{ + struct from_ssa_state *state = void_state; + + 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); + nir_foreach_phi_src(phi, src) { + nir_parallel_copy_instr *pcopy = + get_parallel_copy_at_end_of_block(src->pred); + assert(pcopy); + + nir_parallel_copy_entry *entry = ralloc(state->dead_ctx, + nir_parallel_copy_entry); + exec_list_push_tail(&pcopy->entries, &entry->node); + + nir_src_copy(&entry->src, &src->src, state->dead_ctx); + _mesa_set_add(src->src.ssa->uses, &pcopy->instr); + + nir_ssa_dest_init(&pcopy->instr, &entry->dest, + phi->dest.ssa.num_components, src->src.ssa->name); + + struct set_entry *use_entry = + _mesa_set_search(src->src.ssa->uses, instr); + if (use_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, use_entry); + + src->src.ssa = &entry->dest.ssa; + _mesa_set_add(entry->dest.ssa.uses, instr); + } + + nir_parallel_copy_entry *entry = ralloc(state->dead_ctx, + nir_parallel_copy_entry); + exec_list_push_tail(&block_pcopy->entries, &entry->node); + + nir_ssa_dest_init(&block_pcopy->instr, &entry->dest, + phi->dest.ssa.num_components, phi->dest.ssa.name); + nir_ssa_def_rewrite_uses(&phi->dest.ssa, + nir_src_for_ssa(&entry->dest.ssa), + state->mem_ctx); + + entry->src.is_ssa = true; + entry->src.ssa = &phi->dest.ssa; + _mesa_set_add(phi->dest.ssa.uses, &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); + + nir_foreach_phi_src(phi, src) { + 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) +{ + nir_foreach_parallel_copy_entry(pcopy, entry) { + if (!entry->src.is_ssa) + continue; + + /* Since load_const instructions are SSA only, we can't replace their + * destinations with registers and, therefore, can't coalesce them. + */ + if (entry->src.ssa->parent_instr->type == nir_instr_type_load_const) + continue; + + /* Don't try and coalesce these */ + if (entry->dest.ssa.num_components != entry->src.ssa->num_components) + continue; + + merge_node *src_node = get_merge_node(entry->src.ssa, state); + merge_node *dest_node = get_merge_node(&entry->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_parallel_copy_instr *start_pcopy = NULL; + 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 */ + + start_pcopy = nir_instr_as_parallel_copy(instr); + + agressive_coalesce_parallel_copy(start_pcopy, state); + + break; + } + } + + nir_parallel_copy_instr *end_pcopy = + get_parallel_copy_at_end_of_block(block); + + if (end_pcopy && end_pcopy != start_pcopy) + agressive_coalesce_parallel_copy(end_pcopy, state); + + return true; +} + +static nir_register * +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, 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, def); + if (entry) { + return (nir_register *)entry->data; + } else { + /* We leave load_const SSA values alone. They act as immediates to + * the backend. If it got coalesced into a phi, that's ok. + */ + if (def->parent_instr->type == nir_instr_type_load_const) + return NULL; + + 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, def, reg); + return reg; + } +} + +static bool +rewrite_ssa_src(nir_src *src, void *void_state) +{ + struct from_ssa_state *state = void_state; + + if (src->is_ssa) { + nir_register *reg = get_register_for_ssa_def(src->ssa, state); + + if (reg == NULL) { + assert(src->ssa->parent_instr->type == nir_instr_type_load_const); + return true; + } + + memset(src, 0, sizeof *src); + src->reg.reg = reg; + + /* 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. */ + _mesa_set_add(reg->uses, state->instr); + } + + return true; +} + +static bool +rewrite_ssa_dest(nir_dest *dest, void *void_state) +{ + struct from_ssa_state *state = void_state; + + if (dest->is_ssa) { + nir_register *reg = get_register_for_ssa_def(&dest->ssa, state); + + if (reg == NULL) { + assert(dest->ssa.parent_instr->type == nir_instr_type_load_const); + return true; + } + + _mesa_set_destroy(dest->ssa.uses, NULL); + _mesa_set_destroy(dest->ssa.if_uses, NULL); + + memset(dest, 0, sizeof *dest); + dest->reg.reg = reg; + + _mesa_set_add(reg->defs, 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 +resolve_registers_block(nir_block *block, void *void_state) +{ + struct from_ssa_state *state = void_state; + + nir_foreach_instr_safe(block, instr) { + 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); + } + } + state->instr = NULL; + + nir_if *following_if = nir_block_get_following_if(block); + if (following_if && following_if->condition.is_ssa) { + nir_register *reg = get_register_for_ssa_def(following_if->condition.ssa, + state); + if (reg) { + memset(&following_if->condition, 0, sizeof following_if->condition); + following_if->condition.reg.reg = reg; + + _mesa_set_add(reg->if_uses, following_if); + } else { + /* FIXME: We really shouldn't hit this. We should be doing + * constant control flow propagation. + */ + assert(following_if->condition.ssa->parent_instr->type == nir_instr_type_load_const); + } + } + + 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); + + if (src.is_ssa) + assert(src.ssa->num_components >= dest_src.reg.reg->num_components); + else + assert(src.reg.reg->num_components >= dest_src.reg.reg->num_components); + + nir_alu_instr *mov = nir_alu_instr_create(mem_ctx, nir_op_imov); + nir_src_copy(&mov->src[0].src, &src, mem_ctx); + mov->dest.dest = nir_dest_for_reg(dest_src.reg.reg); + mov->dest.write_mask = (1 << dest_src.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; + nir_foreach_parallel_copy_entry(pcopy, entry) { + /* Sources may be SSA */ + if (!entry->src.is_ssa && entry->src.reg.reg == entry->dest.reg.reg) + continue; + + 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; + nir_foreach_parallel_copy_entry(pcopy, entry) { + /* Sources may be SSA */ + if (!entry->src.is_ssa && entry->src.reg.reg == entry->dest.reg.reg) + continue; + + int src_idx = -1; + for (int i = 0; i < num_vals; ++i) { + if (nir_srcs_equal(values[i], entry->src)) + src_idx = i; + } + if (src_idx < 0) { + src_idx = num_vals++; + values[src_idx] = entry->src; + } + + nir_src dest_src = nir_src_for_reg(entry->dest.reg.reg); + + int dest_idx = -1; + for (int i = 0; i < num_vals; ++i) { + if (nir_srcs_equal(values[i], dest_src)) { + /* Each destination of a parallel copy instruction should be + * unique. A destination may get used as a source, so we still + * have to walk the list. However, the predecessor should not, + * at this point, be set yet, so we should have -1 here. + */ + assert(pred[i] == -1); + 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 +resolve_parallel_copies_block(nir_block *block, void *void_state) +{ + struct from_ssa_state *state = void_state; + + /* 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. */ + + if (first_instr->type == nir_instr_type_parallel_copy) { + nir_parallel_copy_instr *pcopy = nir_instr_as_parallel_copy(first_instr); + + resolve_parallel_copy(pcopy, state); + } + + /* It's possible that the above code already cleaned up the end parallel + * copy. However, doing so removed it form the instructions list so we + * won't find it here. Therefore, it's safe to go ahead and just look + * for one and clean it up if it exists. + */ + nir_parallel_copy_instr *end_pcopy = + get_parallel_copy_at_end_of_block(block); + if (end_pcopy) + resolve_parallel_copy(end_pcopy, state); + + return true; +} + +static void +nir_convert_from_ssa_impl(nir_function_impl *impl) +{ + struct from_ssa_state state; + + state.mem_ctx = ralloc_parent(impl); + state.dead_ctx = ralloc_context(NULL); + state.impl = impl; + state.merge_node_table = _mesa_hash_table_create(NULL, _mesa_hash_pointer, + _mesa_key_pointer_equal); + + nir_foreach_block(impl, add_parallel_copy_to_end_of_block, &state); + nir_foreach_block(impl, isolate_phi_nodes_block, &state); + + /* Mark metadata as dirty before we ask for liveness analysis */ + nir_metadata_preserve(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_hash_pointer, + _mesa_key_pointer_equal); + nir_foreach_block(impl, resolve_registers_block, &state); + + nir_foreach_block(impl, resolve_parallel_copies_block, &state); + + nir_metadata_preserve(impl, nir_metadata_block_index | + nir_metadata_dominance); + + /* 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 +nir_convert_from_ssa(nir_shader *shader) +{ + nir_foreach_overload(shader, overload) { + if (overload->impl) + nir_convert_from_ssa_impl(overload->impl); + } +} -- cgit v1.2.3