[Mesa-dev] [PATCH 05/12] nir: Add a LCSAA-pass
Matt Turner
mattst88 at gmail.com
Sun Aug 28 04:54:16 UTC 2016
On Fri, Aug 26, 2016 at 11:03 PM, Timothy Arceri
<timothy.arceri at collabora.com> wrote:
> 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
> ---
> src/compiler/Makefile.sources | 1 +
> src/compiler/nir/nir.h | 5 +
> src/compiler/nir/nir_form_lcssa.c | 225 ++++++++++++++++++++++++++++++++++++++
> src/compiler/nir/nir_validate.c | 11 +-
> 4 files changed, 239 insertions(+), 3 deletions(-)
> create mode 100644 src/compiler/nir/nir_form_lcssa.c
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index 1bf1c52..55eb399 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -178,6 +178,7 @@ NIR_FILES = \
> nir/nir_control_flow.h \
> nir/nir_control_flow_private.h \
> nir/nir_dominance.c \
> + nir/nir_form_lcssa.c \
This name is confusing. I initially thought it was a typo of "from". I
think it'd be better to call it nir_to_lcssa.c (like nir_to_ssa.c).
> nir/nir_from_ssa.c \
> nir/nir_gather_info.c \
> nir/nir_gs_count_vertices.c \
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index 6b0a73f..d8c5e8e 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -1377,6 +1377,8 @@ typedef struct {
> struct exec_list srcs; /** < list of nir_phi_src */
>
> nir_dest dest;
> +
> + bool is_lcssa_phi;
> } nir_phi_instr;
>
> typedef struct {
> @@ -2633,6 +2635,9 @@ 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_form_LCSSA_impl(nir_function_impl *impl);
> +void nir_form_LCSSA(nir_shader *shader);
> +
> /* 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_form_lcssa.c b/src/compiler/nir/nir_form_lcssa.c
> new file mode 100644
> index 0000000..86e78cd
> --- /dev/null
> +++ b/src/compiler/nir/nir_form_lcssa.c
> @@ -0,0 +1,225 @@
> +/*
> + * Copyright © 2015 Thomas Helland (for Google's Summer of Code)
I don't think it's appropriate to put "(for Google's Summer of Code)"
as part of a copyright statement.
> + *
> + * 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
> + *
> + * This will make a lot of other passes like loop unrolling and LICM simpler.
> + * It is also beneficial as it makes it trivial to keep control of which
> + * ssa-defs are live across the loop-boundary. It will also simplify doing
> + * loop-unswitching a lot, as one just needs to copy the conditional out of
> + * the loop, put one copy of the loop into the then branch, and the other
> + * into the else branch, set the condition true and false respectively in
> + * these loops, and rewrite the LCSSA-phi's to have both the "true"-loop
> + * and the "false"-loop versions of the ssa-def as source.
> + *
Extra newline at the end of this comment, which is itself kind of
tangential to what this code is doing...
> + */
> +
> +#include "nir.h"
> +
> +typedef struct {
> + /* The nir_shader we are transforming */
> + nir_shader *shader;
> +
> + /* The loop we store information for */
> + nir_loop *loop;
> +
> + /* Keep track of which defs are in the loop */
> + BITSET_WORD *is_in_loop;
> +
> + /* General purpose bool */
> + bool flag;
> +} lcssa_state;
> +
> +static void
> +mark_block_as_in_loop(nir_block *blk, void *state)
> +{
> + lcssa_state *state_cast = (lcssa_state *) state;
> + BITSET_SET(state_cast->is_in_loop, blk->index);
> +}
> +
> +static void
> +is_block_outside_loop(nir_block *blk, void *void_state)
> +{
> + lcssa_state *state = void_state;
> + if (!BITSET_TEST(state->is_in_loop, blk->index)) {
> + state->flag = true;
> + }
> +}
> +
> +static bool
> +convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state)
> +{
> + lcssa_state *state = void_state;
> +
> + state->flag = false;
> +
> + nir_foreach_use_safe(src, def) {
> + is_block_outside_loop(src->parent_instr->block, void_state);
> + }
> +
> + /* There where no sources that had defs outside the loop */
> + if (!state->flag)
> + return true;
> +
> + /* Initialize a phi-instruction */
> + nir_phi_instr *phi = nir_phi_instr_create(state->shader);
> + phi->instr.block =
> + nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node));
> + nir_ssa_dest_init(&phi->instr, &phi->dest,
> + def->num_components, def->bit_size, "LCSSA-phi");
> + phi->is_lcssa_phi = true;
> +
> + /* Connect the ssa-def and the phi instruction */
> + nir_phi_src *phi_src = ralloc(phi, nir_phi_src);
> + phi_src->pred = def->parent_instr->block;
> + phi_src->src = nir_src_for_ssa(def);
> +
> + 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(src, def) {
> + state->flag = false;
> +
> + if (src->parent_instr->type == nir_instr_type_phi &&
> + nir_instr_as_phi(src->parent_instr)->is_lcssa_phi)
> + continue;
> +
> + is_block_outside_loop(src->parent_instr->block, state);
> +
> + if (!state->flag)
> + continue;
> +
> + nir_instr_rewrite_src(src->parent_instr, src,
> + 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;
> + }
I don't think the braces are needed here.
> + 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:
> + /* Since we are going depth first the innermost loop will already have
> + * been rewritten, and so there should be no defs inside the inner loop
> + * that are not already rewritten with LCSSA-phis in our current loop.
> + */
> + return;
> + default:
> + unreachable("unknown cf node type");
> + }
> +}
> +
> +static void
> +compute_lcssa(nir_cf_node *cf_node, nir_function_impl *impl)
> +{
> + nir_loop *loop;
> +
> + switch (cf_node->type) {
> + case nir_cf_node_block:
> + 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)
> + compute_lcssa(nested_node, impl);
> + foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list)
> + compute_lcssa(nested_node, impl);
> + return;
> + }
> + case nir_cf_node_loop: {
> + loop = nir_cf_node_as_loop(cf_node);
> + foreach_list_typed(nir_cf_node, nested_node, node, &loop->body)
> + compute_lcssa(nested_node, impl);
> + break;
> + }
> + default:
> + unreachable("unknown cf node type");
> + }
> +
> + nir_function *fn = nir_cf_node_get_function(&loop->cf_node)->function;
> + if (!is_simple_for_loop(fn->shader, loop->info))
> + return;
> +
> + lcssa_state *state = rzalloc(NULL, lcssa_state);
> + state->is_in_loop = rzalloc_array(state, BITSET_WORD,
> + BITSET_WORDS(impl->ssa_alloc));
> + state->loop = loop;
> +
> + nir_foreach_block_in_cf_node(block, cf_node) {
> + mark_block_as_in_loop(block, state);
> + }
> +
> + foreach_list_typed(nir_cf_node, node, node, &loop->body)
> + convert_to_lcssa(node, state);
> +
> + ralloc_free(state);
> +}
> +
> +void
> +nir_form_LCSSA_impl(nir_function_impl *impl)
> +{
> + nir_metadata_require(impl, nir_metadata_loop_analysis);
> +
> + foreach_list_typed(nir_cf_node, node, node, &impl->body)
> + compute_lcssa(node, impl);
> +}
> +
> +void
> +nir_form_LCSSA(nir_shader *shader)
> +{
> + nir_foreach_function(func, shader) {
> + if (func->impl)
> + nir_form_LCSSA_impl(func->impl);
Please put braces around nested control flow.
More information about the mesa-dev
mailing list