<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Mon, Dec 28, 2015 at 12:40 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Mon, Dec 28, 2015 at 2:29 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> 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); </div></div>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. <div><div class="h5"> > + > + 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; </div></div>nir_jump_break? </blockquote><div> </div><div>Yup, thanks! </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> Other than this, I couldn't find anything wrong, so it's Reviewed-by: Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> </blockquote><div> </div><div>Thanks! </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> but I hope you can get loops working soon so you can test this (and hey, loops are useful for other things too :P). </blockquote><div> </div><div>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. </div><div>--Jason </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div><div class="h5"> > + } 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 > </div></div>> _______________________________________________ > mesa-dev mailing list > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div></div>