[Mesa-dev] [PATCH v2 11/12] nir: Add return lowering pass
Jason Ekstrand
jason at jlekstrand.net
Mon Dec 28 13:21:19 PST 2015
On Mon, Dec 28, 2015 at 12:40 PM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> On Mon, Dec 28, 2015 at 2:29 AM, Jason Ekstrand <jason at jlekstrand.net>
> wrote:
> > This commit adds a NIR pass for lowering away returns in functions. If
> the
> > return is in a loop, it is lowered to a break. If it is not in a loop,
> > it's lowered away by moving/deleting code as needed.
> > ---
> > src/glsl/Makefile.sources | 1 +
> > src/glsl/nir/nir.h | 3 +
> > src/glsl/nir/nir_lower_returns.c | 245
> +++++++++++++++++++++++++++++++++++++++
> > 3 files changed, 249 insertions(+)
> > create mode 100644 src/glsl/nir/nir_lower_returns.c
> >
> > diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> > index fc10f14..fa3868c 100644
> > --- a/src/glsl/Makefile.sources
> > +++ b/src/glsl/Makefile.sources
> > @@ -43,6 +43,7 @@ NIR_FILES = \
> > nir/nir_lower_alu_to_scalar.c \
> > nir/nir_lower_atomics.c \
> > nir/nir_lower_clip.c \
> > + nir/nir_lower_returns.c \
> > nir/nir_lower_global_vars_to_local.c \
> > nir/nir_lower_gs_intrinsics.c \
> > nir/nir_lower_load_const_to_scalar.c \
> > diff --git a/src/glsl/nir/nir.h b/src/glsl/nir/nir.h
> > index af95cc4..fa99d47 100644
> > --- a/src/glsl/nir/nir.h
> > +++ b/src/glsl/nir/nir.h
> > @@ -1951,6 +1951,9 @@ int nir_gs_count_vertices(const nir_shader
> *shader);
> >
> > bool nir_split_var_copies(nir_shader *shader);
> >
> > +bool nir_lower_returns_impl(nir_function_impl *impl);
> > +bool nir_lower_returns(nir_shader *shader);
> > +
> > void nir_lower_var_copy_instr(nir_intrinsic_instr *copy, void *mem_ctx);
> > void nir_lower_var_copies(nir_shader *shader);
> >
> > diff --git a/src/glsl/nir/nir_lower_returns.c
> b/src/glsl/nir/nir_lower_returns.c
> > new file mode 100644
> > index 0000000..178e454
> > --- /dev/null
> > +++ b/src/glsl/nir/nir_lower_returns.c
> > @@ -0,0 +1,245 @@
> > +/*
> > + * Copyright © 2015 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_builder.h"
> > +#include "nir_control_flow.h"
> > +
> > +struct lower_returns_state {
> > + nir_builder builder;
> > + struct exec_list *cf_list;
> > + nir_loop *loop;
> > + nir_variable *return_flag;
> > +};
> > +
> > +static bool lower_returns_in_cf_list(struct exec_list *cf_list,
> > + struct lower_returns_state *state);
> > +
> > +static void
> > +predicate_following(nir_cf_node *node, struct lower_returns_state
> *state)
> > +{
> > + nir_builder *b = &state->builder;
> > + b->cursor = nir_after_cf_node_and_phis(node);
>
> BTW, the control flow modification code already interprets "before a
> block" to mean "after any phi nodes," since trying to split a block
> before phi nodes is invalid. The comparison below wouldn't work
> correctly if there were any phi nodes and if we used
> nir_after_cf_node() though, so I guess it's necessary anyways.
>
> > +
> > + if (nir_cursors_equal(b->cursor, nir_after_cf_list(state->cf_list)))
> > + return; /* Nothing to predicate */
> > +
> > + assert(state->return_flag);
> > +
> > + nir_if *if_stmt = nir_if_create(b->shader);
> > + if_stmt->condition = nir_src_for_ssa(nir_load_var(b,
> state->return_flag));
> > + nir_cf_node_insert(b->cursor, &if_stmt->cf_node);
> > +
> > + if (state->loop) {
> > + /* If we're inside of a loop, then all we need to do is insert a
> > + * conditional break.
> > + */
> > + nir_jump_instr *brk =
> > + nir_jump_instr_create(state->builder.shader, nir_jump_break);
> > + nir_instr_insert(nir_before_cf_list(&if_stmt->then_list),
> &brk->instr);
> > + } else {
> > + /* Otherwise, we need to actually move everything into the else
> case
> > + * of the if statement.
> > + */
> > + nir_cf_list list;
> > + nir_cf_extract(&list, nir_after_cf_node(&if_stmt->cf_node),
> > + nir_after_cf_list(state->cf_list));
> > + assert(!exec_list_is_empty(&list.list));
> > + nir_cf_reinsert(&list, nir_before_cf_list(&if_stmt->else_list));
> > + }
> > +}
> > +
> > +static bool
> > +lower_returns_in_loop(nir_loop *loop, struct lower_returns_state *state)
> > +{
> > + nir_loop *parent = state->loop;
> > + state->loop = loop;
> > + bool progress = lower_returns_in_cf_list(&loop->body, state);
> > + state->loop = parent;
> > +
> > + /* If the recursive call made progress, then there were returns
> inside
> > + * of the loop. These would have been lowered to breaks with the
> return
> > + * flag set to true. We need to predicate everything following the
> loop
> > + * on the return flag.
> > + */
> > + if (progress)
> > + predicate_following(&loop->cf_node, state);
> > +
> > + return progress;
> > +}
> > +
> > +static bool
> > +lower_returns_in_if(nir_if *if_stmt, struct lower_returns_state *state)
> > +{
> > + bool progress;
> > +
> > + progress = lower_returns_in_cf_list(&if_stmt->then_list, state);
> > + progress = lower_returns_in_cf_list(&if_stmt->else_list, state) ||
> progress;
> > +
> > + /* If either of the recursive calls made progress, then there were
> > + * returns inside of the body of the if. If we're in a loop, then
> these
> > + * were lowered to breaks which automatically skip to the end of the
> > + * loop so we don't have to do anything. If we're not in a loop,
> then
> > + * all we know is that the return flag is set appropreately and that
> the
> > + * recursive calls ensured that nothing gets executed *inside* the if
> > + * after a return. In order to ensure nothing outside gets executed
> > + * after a return, we need to predicate everything following on the
> > + * return flag.
> > + */
> > + if (progress && !state->loop)
> > + predicate_following(&if_stmt->cf_node, state);
> > +
> > + return progress;
> > +}
> > +
> > +static bool
> > +lower_returns_in_block(nir_block *block, struct lower_returns_state
> *state)
> > +{
> > + if (block->predecessors->entries == 0 &&
> > + block != nir_start_block(state->builder.impl)) {
> > + /* This block is unreachable. Delete it and everything after it.
> */
> > + nir_cf_list list;
> > + nir_cf_extract(&list, nir_before_cf_node(&block->cf_node),
> > + nir_after_cf_list(state->cf_list));
> > +
> > + if (exec_list_is_empty(&list.list)) {
> > + /* There's nothing here, which also means there's nothing in
> this
> > + * block so we have nothing to do.
> > + */
> > + return false;
> > + } else {
> > + nir_cf_delete(&list);
> > + return true;
> > + }
> > + }
> > +
> > + nir_instr *last_instr = nir_block_last_instr(block);
> > + if (last_instr == NULL)
> > + return false;
> > +
> > + if (last_instr->type != nir_instr_type_jump)
> > + return false;
> > +
> > + nir_jump_instr *jump = nir_instr_as_jump(last_instr);
> > + if (jump->type != nir_jump_return)
> > + return false;
> > +
> > + nir_builder *b = &state->builder;
> > + b->cursor = nir_before_instr(&jump->instr);
> > +
> > + /* Set the return flag */
> > + if (state->return_flag == NULL) {
> > + state->return_flag =
> > + nir_local_variable_create(b->impl, glsl_bool_type(), "return");
> > +
> > + /* Set a default value of false */
> > + state->return_flag->constant_initializer =
> > + rzalloc(state->return_flag, nir_constant);
> > + }
> > + nir_store_var(b, state->return_flag, nir_imm_int(b, NIR_TRUE), 1);
> > +
> > + if (state->loop) {
> > + /* We're in a loop. Make the return a break. */
> > + jump->type = nir_jump_return;
>
> nir_jump_break?
>
Yup, thanks!
>
> Other than this, I couldn't find anything wrong, so it's
>
> Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
>
Thanks!
>
> but I hope you can get loops working soon so you can test this (and
> hey, loops are useful for other things too :P).
>
Yeah, I'm starting on adding a real CFG to spirv_to_nir today. It's the
task that I've had on my todo list for a long time that I've been avoiding
and hoping would go away. It didn't go away.
--Jason
>
> > + } else {
> > + /* Not in a loop. Just delete the return; we'll deal with
> > + * predicating later.
> > + */
> > + assert(nir_cf_node_next(&block->cf_node) == NULL);
> > + nir_instr_remove(&jump->instr);
> > + }
> > +
> > + return true;
> > +}
> > +
> > +static bool
> > +lower_returns_in_cf_list(struct exec_list *cf_list,
> > + struct lower_returns_state *state)
> > +{
> > + bool progress = false;
> > +
> > + struct exec_list *parent_list = state->cf_list;
> > + state->cf_list = cf_list;
> > +
> > + /* We iterate over the list backwards because any given lower call
> may
> > + * take everything following the given CF node and predicate it. In
> > + * order to avoid recursion/iteration problems, we want everything
> after
> > + * a given node to already be lowered before this happens.
> > + */
> > + foreach_list_typed_reverse_safe(nir_cf_node, node, node, cf_list) {
> > + switch (node->type) {
> > + case nir_cf_node_block:
> > + if (lower_returns_in_block(nir_cf_node_as_block(node), state))
> > + progress = true;
> > + break;
> > +
> > + case nir_cf_node_if:
> > + if (lower_returns_in_if(nir_cf_node_as_if(node), state))
> > + progress = true;
> > + break;
> > +
> > + case nir_cf_node_loop:
> > + if (lower_returns_in_loop(nir_cf_node_as_loop(node), state))
> > + progress = true;
> > + break;
> > +
> > + default:
> > + unreachable("Invalid inner CF node type");
> > + }
> > + }
> > +
> > + state->cf_list = parent_list;
> > +
> > + return progress;
> > +}
> > +
> > +bool
> > +nir_lower_returns_impl(nir_function_impl *impl)
> > +{
> > + struct lower_returns_state state;
> > +
> > + state.cf_list = &impl->body;
> > + state.loop = NULL;
> > + state.return_flag = NULL;
> > + nir_builder_init(&state.builder, impl);
> > +
> > + bool progress = lower_returns_in_cf_list(&impl->body, &state);
> > +
> > + if (progress)
> > + nir_metadata_preserve(impl, nir_metadata_none);
> > +
> > + return progress;
> > +}
> > +
> > +bool
> > +nir_lower_returns(nir_shader *shader)
> > +{
> > + bool progress = false;
> > +
> > + nir_foreach_function(shader, function) {
> > + if (function->impl)
> > + progress = nir_lower_returns_impl(function->impl) || progress;
> > + }
> > +
> > + return progress;
> > +}
> > --
> > 2.5.0.400.gff86faf
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20151228/4649f0a4/attachment-0001.html>
More information about the mesa-dev
mailing list