[Mesa-dev] [PATCH 04/10] nir: Add a LCSAA-pass

Pohjolainen, Topi topi.pohjolainen at gmail.com
Sat Dec 10 12:21:39 UTC 2016


On Tue, Dec 06, 2016 at 12:12:22PM +1100, Timothy Arceri 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.
> ---
>  src/compiler/Makefile.sources   |   1 +
>  src/compiler/nir/nir.c          |   1 +
>  src/compiler/nir/nir.h          |   4 +
>  src/compiler/nir/nir_to_lcssa.c | 185 ++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 191 insertions(+)
>  create mode 100644 src/compiler/nir/nir_to_lcssa.c
> 
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index 3090677..d3e158a 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -252,6 +252,7 @@ NIR_FILES = \
>  	nir/nir_search_helpers.h \
>  	nir/nir_split_var_copies.c \
>  	nir/nir_sweep.c \
> +	nir/nir_to_lcssa.c \
>  	nir/nir_to_ssa.c \
>  	nir/nir_validate.c \
>  	nir/nir_vla.h \
> diff --git a/src/compiler/nir/nir.c b/src/compiler/nir/nir.c
> index 6e308d5..918cd04 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 b8b44a7..d948e97 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -1400,6 +1400,8 @@ typedef struct {
>     struct exec_list srcs; /** < list of nir_phi_src */
>  
>     nir_dest dest;
> +
> +   bool is_lcssa_phi;
>  } nir_phi_instr;
>  
>  typedef struct {
> @@ -2547,6 +2549,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..93b1c29
> --- /dev/null
> +++ b/src/compiler/nir/nir_to_lcssa.c
> @@ -0,0 +1,185 @@
> +/*
> + * 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     ->          }

Just wondering if right hand side has braces for the 'if' on purpose whereas
left doesn't? Or is this just leftover...

> + * }                         ->          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_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
> +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.
> +    */
> +   if (def->parent_instr->type == nir_instr_type_phi &&
> +       nir_instr_as_phi(def->parent_instr)->is_lcssa_phi) {
> +      return true;
> +   }
> +
> +   nir_foreach_use_safe(use, def) {
> +      if (use->parent_instr->type == nir_instr_type_phi &&
> +          block_after_loop->index == use->parent_instr->block->index) {
> +         continue;
> +      }
> +
> +      if (!is_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;
> +   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;
> +
> +      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));
> +      }
> +   }
> +
> +   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);
> +
> +   ralloc_free(state);
> +}
> -- 
> 2.7.4
> 
> _______________________________________________
> 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