[Mesa-dev] [PATCH 5/6] nir: Add a pass for moving SPIR-V continue blocks to the ends of loops
Jason Ekstrand
jason at jlekstrand.net
Sun Dec 25 20:21:55 UTC 2016
On Dec 25, 2016 2:15 PM, "Mark Janes" <mark.a.janes at intel.com> wrote:
Jason Ekstrand <jason at jlekstrand.net> writes:
> When shaders come in from SPIR-V, we handle continue blocks by placing
> the contents of the continue inside of a "if (!first_iteration)". We do
> this so that we can properly handle the fact that continues in SPIR-V
> jump to the continue block at the end of the loop rather than jumping
> directly to the top of the loop like they do in NIR. In particular, the
> increment step of a simple for loop ends up in the continue block. This
> pass looks for this case in loops that don't actually have any continues
> and moves the continue contents to the end of the loop instead. We need
> this because loop unrolling doesn't work if the increment is inside of a
> condition.
> ---
> src/compiler/Makefile.sources | 1 +
> src/compiler/nir/nir.h | 2 +
> src/compiler/nir/nir_opt_if.c | 253 ++++++++++++++++++++++++++++++
++++++++++++
> 3 files changed, 256 insertions(+)
> create mode 100644 src/compiler/nir/nir_opt_if.c
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index a0abede..6f701af 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -239,6 +239,7 @@ NIR_FILES = \
> nir/nir_opt_dead_cf.c \
> nir/nir_opt_gcm.c \
> nir/nir_opt_global_to_local.c \
> + nir/nir_opt_if.c \
> nir/nir_opt_loop_unroll.c \
> nir/nir_opt_peephole_select.c \
> nir/nir_opt_remove_phis.c \
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index a6c8956..7b582a6 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -2557,6 +2557,8 @@ bool nir_opt_dead_cf(nir_shader *shader);
>
> bool nir_opt_gcm(nir_shader *shader, bool value_number);
>
> +bool nir_opt_if(nir_shader *shader);
> +
> bool nir_opt_loop_unroll(nir_shader *shader, nir_variable_mode
indirect_mask);
>
> bool nir_opt_peephole_select(nir_shader *shader, unsigned limit);
> diff --git a/src/compiler/nir/nir_opt_if.c b/src/compiler/nir/nir_opt_if.c
> new file mode 100644
> index 0000000..5590684
> --- /dev/null
> +++ b/src/compiler/nir/nir_opt_if.c
> @@ -0,0 +1,253 @@
> +/*
> + * Copyright © 2016 Intel Corporation
> + *
> + * 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.
> + */
> +
> +#include "nir.h"
> +#include "nir_control_flow.h"
> +
> +/**
> + * This optimization detects if statements at the tops of loops where the
> + * condition is a phi node of two constants and moves half of the if to
above
> + * the loop and the other half of the if to the end of the loop. A
simple for
> + * loop "for (int i = 0; i < 4; i++)", when run through the SPIR-V
front-end,
> + * ends up looking something like this:
> + *
> + * vec1 32 ssa_0 = load_const (0x00000000)
> + * vec1 32 ssa_1 = load_const (0xffffffff)
> + * loop {
> + * block block_1:
> + * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5
> + * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1
> + * if ssa_2 {
> + * block block_2:
> + * vec1 32 ssa_4 = load_const (0x00000001)
> + * vec1 32 ssa_5 = iadd ssa_2, ssa_4
> + * } else {
> + * block block_3:
> + * }
> + * block block_4:
> + * vec1 32 ssa_6 = load_const (0x00000004)
> + * vec1 32 ssa_7 = ilt ssa_5, ssa_6
> + * if ssa_7 {
> + * block block_5:
> + * } else {
> + * block block_6:
> + * break
> + * }
> + * block block_7:
> + * }
> + *
> + * This turns it into something like this:
> + *
> + * // Stuff from block 1
> + * // Stuff from block 3
> + * loop {
> + * block block_1:
> + * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1
> + * vec1 32 ssa_6 = load_const (0x00000004)
> + * vec1 32 ssa_7 = ilt ssa_5, ssa_6
> + * if ssa_7 {
> + * block block_5:
> + * } else {
> + * block block_6:
> + * break
> + * }
> + * block block_7:
> + * // Stuff from block 1
> + * // Stuff from block 2
> + * vec1 32 ssa_4 = load_const (0x00000001)
> + * vec1 32 ssa_5 = iadd ssa_2, ssa_4
> + * }
> + */
> +static bool
> +opt_peel_loop_initial_if(nir_loop *loop)
> +{
> + nir_block *header_block = nir_loop_first_block(loop);
> + nir_block *prev_block =
> + nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
> +
> + /* It would be insane if this were not true */
> + assert(_mesa_set_search(header_block->predecessors, prev_block));
> + /* It must have exactly one "continue" */
> + if (header_block->predecessors->entries != 2)
> + return false;
> +
> + nir_block *cont_block = NULL;
> + struct set_entry *pred_entry;
> + set_foreach(header_block->predecessors, pred_entry) {
> + if (pred_entry->key != prev_block)
> + cont_block = (void *)pred_entry->key;
> + }
> +
> + nir_cf_node *if_node = nir_cf_node_next(&header_block->cf_node);
> + if (!if_node || if_node->type != nir_cf_node_if)
> + return false;
> +
> + nir_if *nif = nir_cf_node_as_if(if_node);
> + assert(nif->condition.is_ssa);
> +
> + nir_ssa_def *cond = nif->condition.ssa;
> + if (cond->parent_instr->type != nir_instr_type_phi)
> + return false;
> +
> + nir_phi_instr *cond_phi = nir_instr_as_phi(cond->parent_instr);
> + if (cond->parent_instr->block != header_block)
> + return false;
> +
> + /* We already know we have exactly one continue */
> + uint32_t entry_val, cont_val;
Coverity complains in CID 1397794 that entry_val and cont_val need to be
initialized.
Initializing them both to zero probably wouldn't hurt but... If they don't
both get initialized, something has gone terribly wrong. I don't think
this one is worth wiring about.
> + assert(exec_list_length(&cond_phi->srcs) == 2);
> + nir_foreach_phi_src(src, cond_phi) {
> + assert(src->src.is_ssa);
> + nir_const_value *const_src = nir_src_as_const_value(src->src);
> + if (!const_src)
> + return false;
> +
> + if (src->pred == cont_block) {
> + cont_val = const_src->u32[0];
> + } else {
> + assert(src->pred == prev_block);
> + entry_val = const_src->u32[0];
> + }
> + }
> +
> + /* If they both execute or both don't execute, this is a job for
> + * nir_dead_cf, not this pass.
> + */
> + if ((entry_val && cont_val) || (!entry_val && !cont_val))
Might the variables still be undefined at this point?
> + return false;
> +
> + struct exec_list *cont_list, *entry_list;
> + if (cont_val) {
> + cont_list = &nif->then_list;
> + entry_list = &nif->else_list;
> + } else {
> + cont_list = &nif->else_list;
> + entry_list = &nif->then_list;
> + }
> +
> + /* We want to be moving the contents of entry_list to above the loop
so it
> + * can't contain any break or continue instructions.
> + */
> + foreach_list_typed(nir_cf_node, cf_node, node, entry_list) {
> + nir_foreach_block_in_cf_node(block, cf_node) {
> + nir_instr *last_instr = nir_block_last_instr(block);
> + if (last_instr && last_instr->type == nir_instr_type_jump)
> + return false;
> + }
> + }
> +
> + /* Before we do anything, convert the loop to LCSSA. We're about to
> + * replace a bunch of SSA defs with registers and this will prevent
any of
> + * it from leaking outside the loop.
> + */
> + nir_convert_loop_to_lcssa(loop);
> +
> + nir_block *after_if_block =
> + nir_cf_node_as_block(nir_cf_node_next(&nif->cf_node));
> +
> + /* Get rid of phis in the header block since we will be duplicating
it */
> + nir_lower_phis_to_regs_block(header_block);
> + /* Get rid of phis after the if since dominance will change */
> + nir_lower_phis_to_regs_block(after_if_block);
> +
> + /* Get rid of SSA defs in the pieces we're about to move around */
> + nir_lower_ssa_defs_to_regs_block(header_block);
> + nir_foreach_block_in_cf_node(block, &nif->cf_node)
> + nir_lower_ssa_defs_to_regs_block(block);
> +
> + nir_cf_list header, tmp;
> + nir_cf_extract(&header, nir_before_block(header_block),
> + nir_after_block(header_block));
> +
> + nir_cf_list_clone(&tmp, &header, &loop->cf_node, NULL);
> + nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_node));
> + nir_cf_extract(&tmp, nir_before_cf_list(entry_list),
> + nir_after_cf_list(entry_list));
> + nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_node));
> +
> + nir_cf_list_clone(&tmp, &header, &loop->cf_node, NULL);
> + nir_cf_reinsert(&tmp, nir_after_block_before_jump(cont_block));
> + nir_cf_extract(&tmp, nir_before_cf_list(cont_list),
> + nir_after_cf_list(cont_list));
> + nir_cf_reinsert(&tmp, nir_after_block_before_jump(cont_block));
> +
> + nir_cf_delete(&header);
> + nir_cf_node_remove(&nif->cf_node);
> +
> + return true;
> +}
> +
> +static bool
> +opt_if_cf_list(struct exec_list *cf_list)
> +{
> + bool progress = false;
> + foreach_list_typed(nir_cf_node, cf_node, node, cf_list) {
> + switch (cf_node->type) {
> + case nir_cf_node_block:
> + break;
> +
> + case nir_cf_node_if: {
> + nir_if *nif = nir_cf_node_as_if(cf_node);
> + progress |= opt_if_cf_list(&nif->then_list);
> + progress |= opt_if_cf_list(&nif->else_list);
> + break;
> + }
> +
> + case nir_cf_node_loop: {
> + nir_loop *loop = nir_cf_node_as_loop(cf_node);
> + progress |= opt_if_cf_list(&loop->body);
> + progress |= opt_peel_loop_initial_if(loop);
> + break;
> + }
> +
> + case nir_cf_node_function:
> + unreachable("Invalid cf type");
> + }
> + }
> +
> + return progress;
> +}
> +
> +bool
> +nir_opt_if(nir_shader *shader)
> +{
> + bool progress = false;
> +
> + nir_foreach_function(function, shader) {
> + if (function->impl == NULL)
> + continue;
> +
> + if (opt_if_cf_list(&function->impl->body)) {
> + nir_metadata_preserve(function->impl, nir_metadata_none);
> +
> + /* If that made progress, we're no longer really in SSA form.
We
> + * need to convert registers back into SSA defs and clean up
SSA defs
> + * that don't dominate their uses.
> + */
> + nir_convert_to_ssa_impl(function->impl);
> + progress = true;
> + }
> + }
> +
> + return progress;
> +}
> --
> 2.5.0.400.gff86faf
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20161225/1d32b4e2/attachment-0001.html>
More information about the mesa-dev
mailing list