<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">I did have a couple of "real" comments on this one that I'd like to at least see a reply to. Does look pretty good though. </div><div class="gmail_quote"> On Sun, Dec 18, 2016 at 9:47 PM, Timothy Arceri <<a href="mailto:timothy.arceri@collabora.com" target="_blank">timothy.arceri@collabora.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">From: Thomas Helland <<a href="mailto:thomashelland90@gmail.com">thomashelland90@gmail.com</a>> V2: Do a "depth first search" to convert to LCSSA V3: Small comment fixup V4: Rebase, adapt to removal of function overloads V5: Rebase, adapt to relocation of nir to compiler/nir Still need to adapt to potential if-uses Work around nir_validate issue V6 (Timothy): - tidy lcssa and stop leaking memory - dont rewrite the src for the lcssa phi node - validate lcssa phi srcs to avoid postvalidate assert - don't add new phi if one already exists - more lcssa phi validation fixes - Rather than marking ssa defs inside a loop just mark blocks inside a loop. This is simpler and fixes lcssa for intrinsics which do not have a destination. - don't create LCSSA phis for loops we won't unroll - require loop metadata for lcssa pass - handle case were the ssa defs use outside the loop is already a phi V7: (Timothy) - pass indirect mask to metadata call v8: (Timothy) - make convert to lcssa a helper function rather than a nir pass - replace inside loop bitset with on the fly block index logic. - remove lcssa phi validation special cases - inline code from useless helpers, suggested by Jason. - always do lcssa on loops, suggested by Jason. - stop making lcssa phis special. Add as many source as the block has predecessors, suggested by Jason. V9: (Timothy) - fix regression with the is_lcssa_phi field not being initialised to false now that ralloc() doesn't zero out memory. V10: (Timothy) - remove extra braces in SSA example, pointed out by Topi V11: (Timothy) - add missing support for LCSSA phis in if conditions. --- src/compiler/Makefile.sources | 1 + src/compiler/nir/nir.c | 1 + src/compiler/nir/nir.h | 4 + src/compiler/nir/nir_to_lcssa.c | 215 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 221 insertions(+) create mode 100644 src/compiler/nir/nir_to_lcssa.c diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources index ca8a056..e8f7b02 100644 --- a/src/compiler/Makefile.sources +++ b/src/compiler/Makefile.sources @@ -254,6 +254,7 @@ NIR_FILES = \ nir/nir_split_var_copies.c \ nir/nir_sweep.c \ nir/nir_to_ssa.c \ + nir/nir_to_lcssa.c \ nir/nir_validate.c \ nir/nir_vla.h \ nir/nir_worklist.c \ diff --git a/src/compiler/nir/nir.c b/src/compiler/nir/nir.c index 2c3531c..e522a67 100644 --- a/src/compiler/nir/nir.c +++ b/src/compiler/nir/nir.c @@ -561,6 +561,7 @@ nir_phi_instr_create(nir_shader *shader) { nir_phi_instr *instr = ralloc(shader, nir_phi_instr); instr_init(&instr->instr, nir_instr_type_phi); + instr->is_lcssa_phi = false; dest_init(&instr->dest); exec_list_make_empty(&instr->srcs); diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h index 28010aa..75a91ea 100644 --- a/src/compiler/nir/nir.h +++ b/src/compiler/nir/nir.h @@ -1360,6 +1360,8 @@ typedef struct { struct exec_list srcs; /** < list of nir_phi_src */ nir_dest dest; + + bool is_lcssa_phi; } nir_phi_instr; typedef struct { @@ -2526,6 +2528,8 @@ void nir_convert_to_ssa(nir_shader *shader); bool nir_repair_ssa_impl(nir_function_impl *impl); bool nir_repair_ssa(nir_shader *shader); +void nir_convert_loop_to_lcssa(nir_loop *loop); + /* If phi_webs_only is true, only convert SSA values involved in phi nodes to * registers. If false, convert all values (even those not involved in a phi * node) to registers. diff --git a/src/compiler/nir/nir_to_lcssa.c b/src/compiler/nir/nir_to_lcssa.c new file mode 100644 index 0000000..8afdc54 --- /dev/null +++ b/src/compiler/nir/nir_to_lcssa.c @@ -0,0 +1,215 @@ +/* + * Copyright © 2015 Thomas Helland + * + * 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 = lcssa_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; + +} 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) { </blockquote><div> </div><div>I'm not sure you want "<=" and ">=" here. It seems like you either want <= and nir_loop_first_block above or keep what you have above and use <. As currently written, this will return true if it's used in the block before or after the loop not just inside the loop. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + 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) { </blockquote><div> </div><div>Same here </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + return false; + } + + return true; +} + +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; + + nir_block *block_after_loop = + nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node)); + + /* If a LCSSA-phi from a nested loop is use outside the parent loop there + * is no reason to create another LCSSA-phi for the parent loop. + */ </blockquote><div> </div><div>I don't think this is true. The whole point of LCSSA is that no SSA def declared inside a loop is able to escape the loop except through a phi in the block after the loop. If it's an LCSSA phi from an inner loop, I think you very much want it to have another phi for the outer loop.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + if (def->parent_instr->type == nir_instr_type_phi && + nir_instr_as_phi(def->parent_instr)->is_lcssa_phi) { + return true; + } + + nir_foreach_use(use, def) { + if (use->parent_instr->type == nir_instr_type_phi && + block_after_loop == use->parent_instr->block) { </blockquote><div> </div><div>I'm silly but would you mind flipping this equality around? That way the LHS is use->parent_instr->something for both clauses. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + 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); + phi->instr.block = block_after_loop; </blockquote><div> </div><div>You don't need this. nir_instr_insert will set it for you. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + nir_ssa_dest_init(&phi->instr, &phi->dest, + def->num_components, def->bit_size, "LCSSA-phi"); + phi->is_lcssa_phi = true; + + /* Create a phi node with as many sources pointing to the same ssa_def as + * the block has predecessors. + */ + struct set_entry *entry; + 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); + + /* This is a lie to pass validation */ + phi_src->pred = (nir_block *) entry->key; </blockquote><div> </div><div>This is not a lie. It really is the value we get coming in from that predecessor. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + + exec_list_push_tail(&phi->srcs, &phi_src->node); + } + + nir_instr_insert_before_block(phi->instr.block, &phi->instr); + + /* 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(&phi->dest.ssa)); + } + } + + 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(&phi->dest.ssa)); + } + } + + return true; +} + +static void +convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state) +{ + switch (cf_node->type) { + case nir_cf_node_block: + nir_foreach_instr(instr, nir_cf_node_as_block(cf_node)) + nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); + 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: { + nir_loop *parent_loop = state->loop; + state->loop = nir_cf_node_as_loop(cf_node); + + foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body) + convert_to_lcssa(nested_node, state); + + state->loop = parent_loop; + return; + } + default: + unreachable("unknown cf node type"); + } </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> +} + +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; + + foreach_list_typed(nir_cf_node, node, node, &state->loop->body) + convert_to_lcssa(node, state); </blockquote><div> <div>We have better iterators now! This and the whole convert_to_lcssa function can be replaced with </div><div> </div><div>nir_foreach_block_in_cf_node(block, &loop->cf_node) { </div><div> nir_foreach_instr(instr, block) </div><div> nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); </div>} </div><div>Much simpler! </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + + ralloc_free(state); +} -- 2.9.3 _______________________________________________ mesa-dev mailing list <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div></div>