[Mesa-dev] [PATCH 5/6] nir: Add a pass for moving SPIR-V continue blocks to the ends of loops
Timothy Arceri
timothy.arceri at collabora.com
Thu Dec 22 03:11:49 UTC 2016
On Mon, 2016-12-19 at 20:11 -0800, Jason Ekstrand wrote:
> 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" */
After the trivial opt continue pass. Shouldn't this say something like:
/* It must contain no continues */
> + 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 */
This comment feels a little out of place. It could be reworded/expanded
but probably best to just remove it.
Or if you like restructure this block slightly:
/* We already know we have exactly one continue */
assert(exec_list_length(&cond_phi->srcs) == 2);
uint32_t entry_val, cont_val;
...
Although again we have no continues so a slight rewording here would
still be needed.
> + uint32_t entry_val, cont_val;
> + 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) {
I stumbled over this at first. Is it possible to just rename cont_block
-> continue_block having it next to const_src is confusing for those of
use who can't read properly :)
Looking over the rest of this function I don't think this will result
in any line wrapping.
> + 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))
> + return false;
> +
> + struct exec_list *cont_list, *entry_list;
I guess to be consistent you might want to rename cont_list ->
continue_list also.
> + 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) {
I think in my loop analysis pass I added a loop over all instructions
and assert if I find a jump in case dead cf hasn't run or failed for
some reason.
> + 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);
Do we really need to clone it the second time? Is there any reason we
can't just use the original header here?
> + 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)
nir_opt_if is a fairly generic name and this pass is pretty specific.
Is there a better name we could use for this pass?
> +{
> + 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;
> +}
More information about the mesa-dev
mailing list