[Mesa-dev] [PATCH 04/12] nir: Add a LCSAA-pass
Timothy Arceri
timothy.arceri at collabora.com
Tue Dec 20 23:36:00 UTC 2016
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 at colla
> bora.com> wrote:
> > From: Thomas Helland <thomashelland90 at 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.
I think this is correct. We return false for this condition, I guess I
could flip the logic and return true if you think its easier to follow
that way?
>
> > + 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
Again the logic is correct as far as I can tell. Because we are
returning false 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.
I'm not sure it really matters if the phi is in the block after the
loop as long as we are only escaping via an lcssa phi. Lcssa phi srcs
are both the same which is in this case is a src that comes from the
inner loop there is no added value in adding another one to the outer
loop that just points to the inner lcssa phi. If I recall correctly I
added this to avoid a problem ... I think maybe validation related I
can quite recall.
If you feel strongly I can remove it and see what happens and try to
fix it but I really don't see how its helpful to add and additional
phi.
>
> > + 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!
>
> > +
> > + ralloc_free(state);
> > +}
> > --
> > 2.9.3
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
> >
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list