On Tue, Dec 20, 2016 at 8:03 PM, Timothy Arceri < timothy.arc...@collabora.com> wrote:
> On Tue, 2016-12-20 at 15:14 -0800, Jason Ekstrand wrote: > > 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. > > > > On Sun, Dec 18, 2016 at 9:47 PM, Timothy Arceri <timothy.arceri@colla > > bora.com> wrote: > > > From: Thomas Helland <thomashellan...@gmail.com> > > > > > > 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) { > > > > 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. > > > > > + 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) > > > { > > > > Same here > > > > > + 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. > > > + */ > > > > 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. > > > > > + 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) { > > > > I'm silly but would you mind flipping this equality around? That way > > the LHS is use->parent_instr->something for both clauses. > > > > > + 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; > > > > You don't need this. nir_instr_insert will set it for you. > > > > > + 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; > > > > This is not a lie. It really is the value we get coming in from that > > predecessor. > > > > > + > > > + 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"); > > > + } > > > +} > > > + > > > +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); > > > > We have better iterators now! This and the whole convert_to_lcssa > > function can be replaced with > > > > 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); > > } > > > > Much simpler! > > I don't think I can use that or we won't be setting state->loop > Bummer. :( > > > > > + > > > + ralloc_free(state); > > > +} > > > -- > > > 2.9.3 > > > > > > _______________________________________________ > > > mesa-dev mailing list > > > mesa-dev@lists.freedesktop.org > > > https://lists.freedesktop.org/mailman/listinfo/mesa-dev > > > > > > > _______________________________________________ > > mesa-dev mailing list > > mesa-dev@lists.freedesktop.org > > https://lists.freedesktop.org/mailman/listinfo/mesa-dev >
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev