diff options
Diffstat (limited to 'src/compiler/nir/nir_from_ssa.c')
| -rw-r--r-- | src/compiler/nir/nir_from_ssa.c | 805 |
1 files changed, 805 insertions, 0 deletions
diff --git a/src/compiler/nir/nir_from_ssa.c b/src/compiler/nir/nir_from_ssa.c new file mode 100644 index 00000000000..8bc9f24e406 --- /dev/null +++ b/src/compiler/nir/nir_from_ssa.c @@ -0,0 +1,805 @@ +/* + * 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 ([email protected]) + * + */ + +#include "nir.h" +#include "nir_vla.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; + bool phi_webs_only; + 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) +{ + NIR_VLA(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_insert(nir_after_block_before_jump(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 = rzalloc(state->dead_ctx, + nir_parallel_copy_entry); + nir_ssa_dest_init(&pcopy->instr, &entry->dest, + phi->dest.ssa.num_components, src->src.ssa->name); + exec_list_push_tail(&pcopy->entries, &entry->node); + + assert(src->src.is_ssa); + nir_instr_rewrite_src(&pcopy->instr, &entry->src, src->src); + + nir_instr_rewrite_src(&phi->instr, &src->src, + nir_src_for_ssa(&entry->dest.ssa)); + } + + nir_parallel_copy_entry *entry = rzalloc(state->dead_ctx, + nir_parallel_copy_entry); + nir_ssa_dest_init(&block_pcopy->instr, &entry->dest, + phi->dest.ssa.num_components, phi->dest.ssa.name); + exec_list_push_tail(&block_pcopy->entries, &entry->node); + + nir_ssa_def_rewrite_uses(&phi->dest.ssa, + nir_src_for_ssa(&entry->dest.ssa)); + + nir_instr_rewrite_src(&block_pcopy->instr, &entry->src, + nir_src_for_ssa(&phi->dest.ssa)); + } + + 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 +aggressive_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 +aggressive_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); + + aggressive_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) + aggressive_coalesce_parallel_copy(end_pcopy, state); + + return true; +} + +static bool +rewrite_ssa_def(nir_ssa_def *def, void *void_state) +{ + struct from_ssa_state *state = void_state; + nir_register *reg; + + struct hash_entry *entry = + _mesa_hash_table_search(state->merge_node_table, def); + if (entry) { + /* In this case, we're part of a phi web. Use the web's register. */ + 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; + } + + reg = node->set->reg; + } else { + if (state->phi_webs_only) + return true; + + /* 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 true; + + reg = nir_local_reg_create(state->impl); + reg->name = def->name; + reg->num_components = def->num_components; + reg->num_array_elems = 0; + } + + nir_ssa_def_rewrite_uses(def, nir_src_for_reg(reg)); + assert(list_empty(&def->uses) && list_empty(&def->if_uses)); + + if (def->parent_instr->type == nir_instr_type_ssa_undef) { + /* If it's an ssa_undef instruction, remove it since we know we just got + * rid of all its uses. + */ + nir_instr *parent_instr = def->parent_instr; + nir_instr_remove(parent_instr); + ralloc_steal(state->dead_ctx, parent_instr); + return true; + } + + assert(def->parent_instr->type != nir_instr_type_load_const); + + /* At this point we know a priori that this SSA def is part of a + * nir_dest. We can use exec_node_data to get the dest pointer. + */ + nir_dest *dest = exec_node_data(nir_dest, def, ssa); + + nir_instr_rewrite_dest(state->instr, dest, nir_dest_for_reg(reg)); + + return true; +} + +/* Resolves ssa definitions to registers. While we're at it, we also + * remove phi nodes. + */ +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_ssa_def(instr, rewrite_ssa_def, state); + + if (instr->type == nir_instr_type_phi) { + nir_instr_remove(instr); + ralloc_steal(state->dead_ctx, instr); + } + } + state->instr = NULL; + + 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, mov); + 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 receive. 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_VLA_ZERO(nir_src, values, num_copies * 2); + + /* The current location of a given piece of data. We will use -1 for "null" */ + NIR_VLA_FILL(int, loc, num_copies * 2, -1); + + /* The piece of data that the given piece of data is to be copied from. We will use -1 for "null" */ + NIR_VLA_FILL(int, pred, num_copies * 2, -1); + + /* The destinations we have yet to properly fill */ + NIR_VLA(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 */ + NIR_VLA(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, bool phi_webs_only) +{ + struct from_ssa_state state; + + state.mem_ctx = ralloc_parent(impl); + state.dead_ctx = ralloc_context(NULL); + state.impl = impl; + state.phi_webs_only = phi_webs_only; + 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_ssa_defs | + nir_metadata_dominance); + + nir_foreach_block(impl, coalesce_phi_nodes_block, &state); + nir_foreach_block(impl, aggressive_coalesce_block, &state); + + 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.merge_node_table, NULL); + ralloc_free(state.dead_ctx); +} + +void +nir_convert_from_ssa(nir_shader *shader, bool phi_webs_only) +{ + nir_foreach_function(shader, function) { + if (function->impl) + nir_convert_from_ssa_impl(function->impl, phi_webs_only); + } +} |