/* * Copyright © 2015 Thomas Helland * Copyright © 2019 Valve 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. */ /* * This pass converts the ssa-graph into "Loop Closed SSA form". This is * done by placing phi nodes at the exits of the loop for all values * that are used outside the loop. The result is it transforms: * * loop { -> loop { * ssa2 = .... -> ssa2 = ... * if (cond) -> if (cond) * break; -> break; * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4 * } -> } * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2) * ssa6 = ssa5 + 4 */ #include "nir.h" typedef struct { /* The nir_shader we are transforming */ nir_shader *shader; /* The loop we store information for */ nir_loop *loop; /* Whether to skip loop invariant variables */ bool skip_invariants; bool skip_bool_invariants; bool progress; } lcssa_state; static bool is_if_use_inside_loop(nir_src *use, nir_loop *loop) { nir_block *block_before_loop = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); nir_block *block_after_loop = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); nir_block *prev_block = nir_cf_node_as_block(nir_cf_node_prev(&use->parent_if->cf_node)); if (prev_block->index <= block_before_loop->index || prev_block->index >= block_after_loop->index) { return false; } return true; } static bool is_use_inside_loop(nir_src *use, nir_loop *loop) { nir_block *block_before_loop = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); nir_block *block_after_loop = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); if (use->parent_instr->block->index <= block_before_loop->index || use->parent_instr->block->index >= block_after_loop->index) { return false; } return true; } static bool is_defined_before_loop(nir_ssa_def *def, nir_loop *loop) { nir_instr *instr = def->parent_instr; nir_block *block_before_loop = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); return instr->block->index <= block_before_loop->index; } typedef enum instr_invariance { undefined = 0, invariant, not_invariant, } instr_invariance; static instr_invariance instr_is_invariant(nir_instr *instr, nir_loop *loop); static bool def_is_invariant(nir_ssa_def *def, nir_loop *loop) { if (is_defined_before_loop(def, loop)) return invariant; if (def->parent_instr->pass_flags == undefined) def->parent_instr->pass_flags = instr_is_invariant(def->parent_instr, loop); return def->parent_instr->pass_flags == invariant; } static bool src_is_invariant(nir_src *src, void *state) { assert(src->is_ssa); return def_is_invariant(src->ssa, (nir_loop *)state); } static instr_invariance phi_is_invariant(nir_phi_instr *instr, nir_loop *loop) { /* Base case: it's a phi at the loop header * Loop-header phis are updated in each loop iteration with * the loop-carried value, and thus control-flow dependent * on the loop itself. */ if (instr->instr.block == nir_loop_first_block(loop)) return not_invariant; nir_foreach_phi_src(src, instr) { if (!src_is_invariant(&src->src, loop)) return not_invariant; } /* All loop header- and LCSSA-phis should be handled by this point. */ nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node); assert(prev && prev->type == nir_cf_node_if); /* Invariance of phis after if-nodes also depends on the invariance * of the branch condition. */ nir_if *if_node = nir_cf_node_as_if(prev); if (!def_is_invariant(if_node->condition.ssa, loop)) return not_invariant; return invariant; } /* An instruction is said to be loop-invariant if it * - has no sideeffects and * - solely depends on variables defined outside of the loop or * by other invariant instructions */ static instr_invariance instr_is_invariant(nir_instr *instr, nir_loop *loop) { assert(instr->pass_flags == undefined); switch (instr->type) { case nir_instr_type_load_const: case nir_instr_type_ssa_undef: return invariant; case nir_instr_type_call: return not_invariant; case nir_instr_type_phi: return phi_is_invariant(nir_instr_as_phi(instr), loop); case nir_instr_type_intrinsic: { nir_intrinsic_instr *intrinsic = nir_instr_as_intrinsic(instr); if (!(nir_intrinsic_infos[intrinsic->intrinsic].flags & NIR_INTRINSIC_CAN_REORDER)) return not_invariant; /* fallthrough */ } default: return nir_foreach_src(instr, src_is_invariant, loop) ? invariant : not_invariant; } return invariant; } static bool convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state) { lcssa_state *state = void_state; bool all_uses_inside_loop = true; /* Don't create LCSSA-Phis for loop-invariant variables */ if (state->skip_invariants && (def->bit_size != 1 || state->skip_bool_invariants)) { assert(def->parent_instr->pass_flags != undefined); if (def->parent_instr->pass_flags == invariant) return true; } nir_block *block_after_loop = nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node)); nir_foreach_use(use, def) { if (use->parent_instr->type == nir_instr_type_phi && use->parent_instr->block == block_after_loop) { continue; } if (!is_use_inside_loop(use, state->loop)) { all_uses_inside_loop = false; } } nir_foreach_if_use(use, def) { if (!is_if_use_inside_loop(use, state->loop)) { all_uses_inside_loop = false; } } /* There where no sources that had defs outside the loop */ if (all_uses_inside_loop) return true; /* Initialize a phi-instruction */ nir_phi_instr *phi = nir_phi_instr_create(state->shader); nir_ssa_dest_init(&phi->instr, &phi->dest, def->num_components, def->bit_size, "LCSSA-phi"); /* Create a phi node with as many sources pointing to the same ssa_def as * the block has predecessors. */ set_foreach(block_after_loop->predecessors, entry) { nir_phi_src *phi_src = ralloc(phi, nir_phi_src); phi_src->src = nir_src_for_ssa(def); phi_src->pred = (nir_block *) entry->key; exec_list_push_tail(&phi->srcs, &phi_src->node); } nir_instr_insert_before_block(block_after_loop, &phi->instr); nir_ssa_def *dest = &phi->dest.ssa; /* deref instructions need a cast after the phi */ if (def->parent_instr->type == nir_instr_type_deref) { nir_deref_instr *cast = nir_deref_instr_create(state->shader, nir_deref_type_cast); nir_deref_instr *instr = nir_instr_as_deref(def->parent_instr); cast->mode = instr->mode; cast->type = instr->type; cast->parent = nir_src_for_ssa(&phi->dest.ssa); cast->cast.ptr_stride = nir_deref_instr_ptr_as_array_stride(instr); nir_ssa_dest_init(&cast->instr, &cast->dest, phi->dest.ssa.num_components, phi->dest.ssa.bit_size, NULL); nir_instr_insert(nir_after_phis(block_after_loop), &cast->instr); dest = &cast->dest.ssa; } /* Run through all uses and rewrite those outside the loop to point to * the phi instead of pointing to the ssa-def. */ nir_foreach_use_safe(use, def) { if (use->parent_instr->type == nir_instr_type_phi && block_after_loop == use->parent_instr->block) { continue; } if (!is_use_inside_loop(use, state->loop)) { nir_instr_rewrite_src(use->parent_instr, use, nir_src_for_ssa(dest)); } } nir_foreach_if_use_safe(use, def) { if (!is_if_use_inside_loop(use, state->loop)) { nir_if_rewrite_condition(use->parent_if, nir_src_for_ssa(dest)); } } state->progress = true; return true; } static void convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state) { switch (cf_node->type) { case nir_cf_node_block: return; case nir_cf_node_if: { nir_if *if_stmt = nir_cf_node_as_if(cf_node); foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list) convert_to_lcssa(nested_node, state); foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list) convert_to_lcssa(nested_node, state); return; } case nir_cf_node_loop: { if (state->skip_invariants) { nir_foreach_block_in_cf_node(block, cf_node) { nir_foreach_instr(instr, block) instr->pass_flags = undefined; } } /* first, convert inner loops */ nir_loop *loop = nir_cf_node_as_loop(cf_node); foreach_list_typed(nir_cf_node, nested_node, node, &loop->body) convert_to_lcssa(nested_node, state); /* mark loop-invariant instructions */ if (state->skip_invariants) { nir_foreach_block_in_cf_node(block, cf_node) { nir_foreach_instr(instr, block) { if (instr->pass_flags == undefined) instr->pass_flags = instr_is_invariant(instr, nir_cf_node_as_loop(cf_node)); } } } state->loop = loop; nir_foreach_block_in_cf_node(block, cf_node) { nir_foreach_instr(instr, block) { nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); /* for outer loops, invariant instructions can be variant */ if (state->skip_invariants && instr->pass_flags == invariant) instr->pass_flags = undefined; } } /* For outer loops, the LCSSA-phi should be considered not invariant */ if (state->skip_invariants) { nir_block *block_after_loop = nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node)); nir_foreach_instr(instr, block_after_loop) { if (instr->type == nir_instr_type_phi) instr->pass_flags = not_invariant; else break; } } return; } default: unreachable("unknown cf node type"); } } void nir_convert_loop_to_lcssa(nir_loop *loop) { nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); nir_metadata_require(impl, nir_metadata_block_index); lcssa_state *state = rzalloc(NULL, lcssa_state); state->loop = loop; state->shader = impl->function->shader; state->skip_invariants = false; state->skip_bool_invariants = false; nir_foreach_block_in_cf_node (block, &loop->cf_node) { nir_foreach_instr(instr, block) nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); } ralloc_free(state); } bool nir_convert_to_lcssa(nir_shader *shader, bool skip_invariants, bool skip_bool_invariants) { bool progress = false; lcssa_state *state = rzalloc(NULL, lcssa_state); state->shader = shader; state->skip_invariants = skip_invariants; state->skip_bool_invariants = skip_bool_invariants; nir_foreach_function(function, shader) { if (function->impl == NULL) continue; state->progress = false; nir_metadata_require(function->impl, nir_metadata_block_index); foreach_list_typed(nir_cf_node, node, node, &function->impl->body) convert_to_lcssa(node, state); if (state->progress) { progress = true; nir_metadata_preserve(function->impl, nir_metadata_block_index | nir_metadata_dominance); } else { #ifndef NDEBUG function->impl->valid_metadata &= ~nir_metadata_not_properly_reset; #endif } } ralloc_free(state); return progress; }