/*
* 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"
#include "nir_builder.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 {
nir_builder builder;
void *dead_ctx;
bool phi_webs_only;
struct hash_table *merge_node_table;
nir_instr *instr;
bool progress;
};
/* 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 "dominance 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_nodes in dominance order of the ssa definitions. (Since the
* liveness analysis pass indexes the SSA values in dominance 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 *dead_ctx)
{
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(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 *dead_ctx)
{
nir_instr *last_phi_instr = NULL;
nir_foreach_instr(instr, block) {
/* 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 phis, 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(dead_ctx);
nir_instr_insert_after(last_phi_instr, &block_pcopy->instr);
nir_foreach_instr(instr, block) {
/* 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(src, phi) {
nir_parallel_copy_instr *pcopy =
get_parallel_copy_at_end_of_block(src->pred);
assert(pcopy);
nir_parallel_copy_entry *entry = rzalloc(dead_ctx,
nir_parallel_copy_entry);
nir_ssa_dest_init(&pcopy->instr, &entry->dest,
phi->dest.ssa.num_components,
phi->dest.ssa.bit_size, 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(dead_ctx,
nir_parallel_copy_entry);
nir_ssa_dest_init(&block_pcopy->instr, &entry->dest,
phi->dest.ssa.num_components, phi->dest.ssa.bit_size,
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, struct from_ssa_state *state)
{
nir_foreach_instr(instr, block) {
/* 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(src, phi) {
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(entry, pcopy) {
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, struct from_ssa_state *state)
{
nir_parallel_copy_instr *start_pcopy = NULL;
nir_foreach_instr(instr, block) {
/* 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 nir_register *
create_reg_for_ssa_def(nir_ssa_def *def, nir_function_impl *impl)
{
nir_register *reg = nir_local_reg_create(impl);
reg->name = def->name;
reg->num_components = def->num_components;
reg->bit_size = def->bit_size;
reg->num_array_elems = 0;
return reg;
}
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 = create_reg_for_ssa_def(def, state->builder.impl);
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 = create_reg_for_ssa_def(def, state->builder.impl);
}
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);
state->progress = true;
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));
state->progress = true;
return true;
}
/* Resolves ssa definitions to registers. While we're at it, we also
* remove phi nodes.
*/
static void
resolve_registers_block(nir_block *block, struct from_ssa_state *state)
{
nir_foreach_instr_safe(instr, block) {
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->progress = true;
}
}
state->instr = NULL;
}
static void
emit_copy(nir_builder *b, nir_src src, nir_src dest_src)
{
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(b->shader, 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_builder_instr_insert(b, &mov->instr);
}
/* Resolves a single parallel copy operation into a sequence of movs
*
* 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(entry, pcopy) {
/* 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;
state->builder.cursor = nir_before_instr(&pcopy->instr);
/* 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(entry, pcopy) {
/* 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(&state->builder, values[loc[a]], values[b]);
/* 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->builder.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(&state->builder, values[b], values[num_vals]);
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, struct from_ssa_state *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 bool
nir_convert_from_ssa_impl(nir_function_impl *impl, bool phi_webs_only)
{
struct from_ssa_state state;
nir_builder_init(&state.builder, impl);
state.dead_ctx = ralloc_context(NULL);
state.phi_webs_only = phi_webs_only;
state.merge_node_table = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
_mesa_key_pointer_equal);
state.progress = false;
nir_foreach_block(block, impl) {
add_parallel_copy_to_end_of_block(block, state.dead_ctx);
}
nir_foreach_block(block, impl) {
isolate_phi_nodes_block(block, state.dead_ctx);
}
/* 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(block, impl) {
coalesce_phi_nodes_block(block, &state);
}
nir_foreach_block(block, impl) {
aggressive_coalesce_block(block, &state);
}
nir_foreach_block(block, impl) {
resolve_registers_block(block, &state);
}
nir_foreach_block(block, impl) {
resolve_parallel_copies_block(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);
return state.progress;
}
bool
nir_convert_from_ssa(nir_shader *shader, bool phi_webs_only)
{
bool progress = false;
nir_foreach_function(function, shader) {
if (function->impl)
progress |= nir_convert_from_ssa_impl(function->impl, phi_webs_only);
}
return progress;
}
static void
place_phi_read(nir_shader *shader, nir_register *reg,
nir_ssa_def *def, nir_block *block)
{
if (block != def->parent_instr->block) {
/* Try to go up the single-successor tree */
bool all_single_successors = true;
struct set_entry *entry;
set_foreach(block->predecessors, entry) {
nir_block *pred = (nir_block *)entry->key;
if (pred->successors[0] && pred->successors[1]) {
all_single_successors = false;
break;
}
}
if (all_single_successors) {
/* All predecessors of this block have exactly one successor and it
* is this block so they must eventually lead here without
* intersecting each other. Place the reads in the predecessors
* instead of this block.
*/
set_foreach(block->predecessors, entry)
place_phi_read(shader, reg, def, (nir_block *)entry->key);
return;
}
}
nir_alu_instr *mov = nir_alu_instr_create(shader, nir_op_imov);
mov->src[0].src = nir_src_for_ssa(def);
mov->dest.dest = nir_dest_for_reg(reg);
mov->dest.write_mask = (1 << reg->num_components) - 1;
nir_instr_insert(nir_after_block_before_jump(block), &mov->instr);
}
/** Lower all of the phi nodes in a block to imovs to and from a register
*
* This provides a very quick-and-dirty out-of-SSA pass that you can run on a
* single block to convert all of its phis to a register and some imovs.
* The code that is generated, while not optimal for actual codegen in a
* back-end, is easy to generate, correct, and will turn into the same set of
* phis after you call regs_to_ssa and do some copy propagation.
*
* The one intelligent thing this pass does is that it places the moves from
* the phi sources as high up the predecessor tree as possible instead of in
* the exact predecessor. This means that, in particular, it will crawl into
* the deepest nesting of any if-ladders. In order to ensure that doing so is
* safe, it stops as soon as one of the predecessors has multiple successors.
*/
bool
nir_lower_phis_to_regs_block(nir_block *block)
{
nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
nir_shader *shader = impl->function->shader;
bool progress = false;
nir_foreach_instr_safe(instr, block) {
if (instr->type != nir_instr_type_phi)
break;
nir_phi_instr *phi = nir_instr_as_phi(instr);
assert(phi->dest.is_ssa);
nir_register *reg = create_reg_for_ssa_def(&phi->dest.ssa, impl);
nir_alu_instr *mov = nir_alu_instr_create(shader, nir_op_imov);
mov->src[0].src = nir_src_for_reg(reg);
mov->dest.write_mask = (1 << phi->dest.ssa.num_components) - 1;
nir_ssa_dest_init(&mov->instr, &mov->dest.dest,
phi->dest.ssa.num_components, phi->dest.ssa.bit_size,
phi->dest.ssa.name);
nir_instr_insert(nir_after_instr(&phi->instr), &mov->instr);
nir_ssa_def_rewrite_uses(&phi->dest.ssa,
nir_src_for_ssa(&mov->dest.dest.ssa));
nir_foreach_phi_src(src, phi) {
assert(src->src.is_ssa);
place_phi_read(shader, reg, src->src.ssa, src->pred);
}
nir_instr_remove(&phi->instr);
progress = true;
}
return progress;
}
struct ssa_def_to_reg_state {
nir_function_impl *impl;
bool progress;
};
static bool
dest_replace_ssa_with_reg(nir_dest *dest, void *void_state)
{
struct ssa_def_to_reg_state *state = void_state;
if (!dest->is_ssa)
return true;
nir_register *reg = create_reg_for_ssa_def(&dest->ssa, state->impl);
nir_ssa_def_rewrite_uses(&dest->ssa, nir_src_for_reg(reg));
nir_instr *instr = dest->ssa.parent_instr;
*dest = nir_dest_for_reg(reg);
dest->reg.parent_instr = instr;
list_addtail(&dest->reg.def_link, ®->defs);
state->progress = true;
return true;
}
/** Lower all of the SSA defs in a block to registers
*
* This performs the very simple operation of blindly replacing all of the SSA
* defs in the given block with registers. If not used carefully, this may
* result in phi nodes with register sources which is technically invalid.
* Fortunately, the register-based into-SSA pass handles them anyway.
*/
bool
nir_lower_ssa_defs_to_regs_block(nir_block *block)
{
nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
nir_shader *shader = impl->function->shader;
struct ssa_def_to_reg_state state = {
.impl = impl,
.progress = false,
};
nir_foreach_instr(instr, block) {
if (instr->type == nir_instr_type_ssa_undef) {
/* Undefs are just a read of something never written. */
nir_ssa_undef_instr *undef = nir_instr_as_ssa_undef(instr);
nir_register *reg = create_reg_for_ssa_def(&undef->def, state.impl);
nir_ssa_def_rewrite_uses(&undef->def, nir_src_for_reg(reg));
} else if (instr->type == nir_instr_type_load_const) {
/* Constant loads are SSA-only, we need to insert a move */
nir_load_const_instr *load = nir_instr_as_load_const(instr);
nir_register *reg = create_reg_for_ssa_def(&load->def, state.impl);
nir_ssa_def_rewrite_uses(&load->def, nir_src_for_reg(reg));
nir_alu_instr *mov = nir_alu_instr_create(shader, nir_op_imov);
mov->src[0].src = nir_src_for_ssa(&load->def);
mov->dest.dest = nir_dest_for_reg(reg);
mov->dest.write_mask = (1 << reg->num_components) - 1;
nir_instr_insert(nir_after_instr(&load->instr), &mov->instr);
} else {
nir_foreach_dest(instr, dest_replace_ssa_with_reg, &state);
}
}
return state.progress;
}