[Mesa-dev] [PATCH 04/12] nir: Add a LCSAA-pass
Timothy Arceri
timothy.arceri at collabora.com
Wed Dec 21 00:45:00 UTC 2016
On Tue, 2016-12-20 at 16:34 -0800, Jason Ekstrand wrote:
> On Tue, Dec 20, 2016 at 3:36 PM, Timothy Arceri <timothy.arceri at colla
> bora.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 at c
> > olla
> > > 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?
> >
>
> Nope. I just can't read. Leave it as-is. :-)
>
> > >
> > > > + 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.
>
> My pass calls to_lcssa and assumes that it means nothing will escape
> the loop it's called on unless it goes through a phi in the break
> block. If that assumption is broken, it will cause problems. So,
> yes, unless there is a good reason for this, I have a strong opinion.
> :-)
Fair enough. There may not even be a problem since I first added this
will give it a try.
>
> > >
> > > > + 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
> >
>
> _______________________________________________
> 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