<div dir="auto"><div><div class="gmail_extra"><div class="gmail_quote">On Dec 21, 2016 9:12 PM, "Timothy Arceri" <<a href="mailto:timothy.arceri@collabora.com">timothy.arceri@collabora.com</a>> wrote:<br type="attribution"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">On Mon, 2016-12-19 at 20:11 -0800, Jason Ekstrand wrote:<br>
> When shaders come in from SPIR-V, we handle continue blocks by<br>
> placing<br>
> the contents of the continue inside of a "if (!first_iteration)". We<br>
> do<br>
> this so that we can properly handle the fact that continues in SPIR-V<br>
> jump to the continue block at the end of the loop rather than jumping<br>
> directly to the top of the loop like they do in NIR. In particular,<br>
> the<br>
> increment step of a simple for loop ends up in the continue<br>
> block. This<br>
> pass looks for this case in loops that don't actually have any<br>
> continues<br>
> and moves the continue contents to the end of the loop instead. We<br>
> need<br>
> this because loop unrolling doesn't work if the increment is inside<br>
> of a<br>
> condition.<br>
> ---<br>
> src/compiler/Makefile.sources | 1 +<br>
> src/compiler/nir/nir.h <wbr> | 2 +<br>
> src/compiler/nir/nir_opt_if.c | 253<br>
> ++++++++++++++++++++++++++++++<wbr>++++++++++++<br>
> 3 files changed, 256 insertions(+)<br>
> create mode 100644 src/compiler/nir/nir_opt_if.c<br>
><br>
> diff --git a/src/compiler/Makefile.<wbr>sources<br>
> b/src/compiler/Makefile.<wbr>sources<br>
> index a0abede..6f701af 100644<br>
> --- a/src/compiler/Makefile.<wbr>sources<br>
> +++ b/src/compiler/Makefile.<wbr>sources<br>
> @@ -239,6 +239,7 @@ NIR_FILES = \<br>
> nir/nir_opt_dead_cf.c \<br>
> nir/nir_opt_gcm.c \<br>
> nir/nir_opt_global_to_local.c \<br>
> + nir/nir_opt_if.c \<br>
> nir/nir_opt_loop_unroll.c \<br>
> nir/nir_opt_peephole_select.c \<br>
> nir/nir_opt_remove_phis.c \<br>
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h<br>
> index a6c8956..7b582a6 100644<br>
> --- a/src/compiler/nir/nir.h<br>
> +++ b/src/compiler/nir/nir.h<br>
> @@ -2557,6 +2557,8 @@ bool nir_opt_dead_cf(nir_shader *shader);<br>
> <br>
> bool nir_opt_gcm(nir_shader *shader, bool value_number);<br>
> <br>
> +bool nir_opt_if(nir_shader *shader);<br>
> +<br>
> bool nir_opt_loop_unroll(nir_shader *shader, nir_variable_mode<br>
> indirect_mask);<br>
> <br>
> bool nir_opt_peephole_select(nir_<wbr>shader *shader, unsigned limit);<br>
> diff --git a/src/compiler/nir/nir_opt_if.<wbr>c<br>
> b/src/compiler/nir/nir_opt_if.<wbr>c<br>
> new file mode 100644<br>
> index 0000000..5590684<br>
> --- /dev/null<br>
> +++ b/src/compiler/nir/nir_opt_if.<wbr>c<br>
> @@ -0,0 +1,253 @@<br>
> +/*<br>
> + * Copyright © 2016 Intel Corporation<br>
> + *<br>
> + * Permission is hereby granted, free of charge, to any person<br>
> obtaining a<br>
> + * copy of this software and associated documentation files (the<br>
> "Software"),<br>
> + * to deal in the Software without restriction, including without<br>
> limitation<br>
> + * the rights to use, copy, modify, merge, publish, distribute,<br>
> sublicense,<br>
> + * and/or sell copies of the Software, and to permit persons to whom<br>
> the<br>
> + * Software is furnished to do so, subject to the following<br>
> conditions:<br>
> + *<br>
> + * The above copyright notice and this permission notice (including<br>
> the next<br>
> + * paragraph) shall be included in all copies or substantial<br>
> portions of the<br>
> + * Software.<br>
> + *<br>
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,<br>
> EXPRESS OR<br>
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF<br>
> MERCHANTABILITY,<br>
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO<br>
> EVENT SHALL<br>
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES<br>
> OR OTHER<br>
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,<br>
> ARISING<br>
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR<br>
> OTHER DEALINGS<br>
> + * IN THE SOFTWARE.<br>
> + */<br>
> +<br>
> +#include "nir.h"<br>
> +#include "nir_control_flow.h"<br>
> +<br>
> +/**<br>
> + * This optimization detects if statements at the tops of loops<br>
> where the<br>
> + * condition is a phi node of two constants and moves half of the if<br>
> to above<br>
> + * the loop and the other half of the if to the end of the loop. A<br>
> simple for<br>
> + * loop "for (int i = 0; i < 4; i++)", when run through the SPIR-V<br>
> front-end,<br>
> + * ends up looking something like this:<br>
> + *<br>
> + * vec1 32 ssa_0 = load_const (0x00000000)<br>
> + * vec1 32 ssa_1 = load_const (0xffffffff)<br>
> + * loop {<br>
> + * block block_1:<br>
> + * vec1 32 ssa_2 = phi block_0: ssa_0, block_7: ssa_5<br>
> + * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1<br>
> + * if ssa_2 {<br>
> + * block block_2:<br>
> + * vec1 32 ssa_4 = load_const (0x00000001)<br>
> + * vec1 32 ssa_5 = iadd ssa_2, ssa_4<br>
> + * } else {<br>
> + * block block_3:<br>
> + * }<br>
> + * block block_4:<br>
> + * vec1 32 ssa_6 = load_const (0x00000004)<br>
> + * vec1 32 ssa_7 = ilt ssa_5, ssa_6<br>
> + * if ssa_7 {<br>
> + * block block_5:<br>
> + * } else {<br>
> + * block block_6:<br>
> + * break<br>
> + * }<br>
> + * block block_7:<br>
> + * }<br>
> + *<br>
> + * This turns it into something like this:<br>
> + *<br>
> + * // Stuff from block 1<br>
> + * // Stuff from block 3<br>
> + * loop {<br>
> + * block block_1:<br>
> + * vec1 32 ssa_3 = phi block_0: ssa_0, block_7: ssa_1<br>
> + * vec1 32 ssa_6 = load_const (0x00000004)<br>
> + * vec1 32 ssa_7 = ilt ssa_5, ssa_6<br>
> + * if ssa_7 {<br>
> + * block block_5:<br>
> + * } else {<br>
> + * block block_6:<br>
> + * break<br>
> + * }<br>
> + * block block_7:<br>
> + * // Stuff from block 1<br>
> + * // Stuff from block 2<br>
> + * vec1 32 ssa_4 = load_const (0x00000001)<br>
> + * vec1 32 ssa_5 = iadd ssa_2, ssa_4<br>
> + * }<br>
> + */<br>
> +static bool<br>
> +opt_peel_loop_initial_if(nir_<wbr>loop *loop)<br>
> +{<br>
> + nir_block *header_block = nir_loop_first_block(loop);<br>
> + nir_block *prev_block =<br>
> + nir_cf_node_as_block(<wbr>nir_cf_node_prev(&loop->cf_<wbr>node));<br>
> +<br>
> + /* It would be insane if this were not true */<br>
> + assert(_mesa_set_search(<wbr>header_block->predecessors, prev_block));<br>
> + /* It must have exactly one "continue" */<br>
<br>
</div>After the trivial opt continue pass. Shouldn't this say something like:<br>
<br>
/* It must contain no continues */</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">Actually... The pass should be able a single nontrivial continue if that happened to come up. Originally, I wrote it to only handle the no continues case, but as I continued to refactor, it was easy enough to support the other. I'll happily rework it for only a single continue at the end. I could probably get rid of a few (not many) lines that way and I doubt it's all that likely to come up.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">
> + if (header_block->predecessors-><wbr>entries != 2)<br>
> + return false;<br>
> +<br>
> + nir_block *cont_block = NULL;<br>
> + struct set_entry *pred_entry;<br>
> + set_foreach(header_block-><wbr>predecessors, pred_entry) {<br>
> + if (pred_entry->key != prev_block)<br>
> + cont_block = (void *)pred_entry->key;<br>
> + }<br>
> +<br>
> + nir_cf_node *if_node = nir_cf_node_next(&header_<wbr>block->cf_node);<br>
> + if (!if_node || if_node->type != nir_cf_node_if)<br>
> + return false;<br>
> +<br>
> + nir_if *nif = nir_cf_node_as_if(if_node);<br>
> + assert(nif->condition.is_<wbr>ssa);<br>
> +<br>
> + nir_ssa_def *cond = nif->condition.ssa;<br>
> + if (cond->parent_instr->type != nir_instr_type_phi)<br>
> + return false;<br>
> +<br>
> + nir_phi_instr *cond_phi = nir_instr_as_phi(cond->parent_<wbr>instr);<br>
> + if (cond->parent_instr->block != header_block)<br>
> + return false;<br>
> +<br>
> + /* We already know we have exactly one continue */<br>
<br>
</div>This comment feels a little out of place. It could be reworded/expanded<br>
but probably best to just remove it.<br>
<br>
Or if you like restructure this block slightly:<br>
<div class="quoted-text"><br>
/* We already know we have exactly one continue */<br>
</div> assert(exec_list_length(&cond_<wbr>phi->srcs) == 2);<br>
<br>
uint32_t entry_val, cont_val;<br>
...<br></blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">Fair point.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Although again we have no continues so a slight rewording here would<br>
still be needed.</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">I'll wait for your response to the above before changing it though.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="quoted-text">
> + uint32_t entry_val, cont_val;<br>
> + assert(exec_list_length(&<wbr>cond_phi->srcs) == 2);<br>
> + nir_foreach_phi_src(src, cond_phi) {<br>
> + assert(src->src.is_ssa)<wbr>;<br>
> + nir_const_value *const_src = nir_src_as_const_value(src-><wbr>src);<br>
> + if (!const_src)<br>
> + return false;<br>
> +<br>
> + if (src->pred == cont_block) {<br>
<br>
</div>I stumbled over this at first. Is it possible to just rename cont_block<br>
-> continue_block having it next to const_src is confusing for those of<br>
use who can't read properly :)<br>
<br>
Looking over the rest of this function I don't think this will result<br>
in any line wrapping.</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">Sure, I can name it continue.</div><div dir="auto"><br></div><div dir="auto"></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="quoted-text">
> + cont_val = const_src->u32[0];<br>
> + } else {<br>
> + assert(src->pred == prev_block);<br>
> + entry_val = const_src->u32[0];<br>
> + }<br>
> + }<br>
> +<br>
> + /* If they both execute or both don't execute, this is a job for<br>
> + * nir_dead_cf, not this pass.<br>
> + */<br>
> + if ((entry_val && cont_val) || (!entry_val && !cont_val))<br>
> + return false;<br>
> +<br>
> + struct exec_list *cont_list, *entry_list;<br>
<br>
</div>I guess to be consistent you might want to rename cont_list -><br>
continue_list also.</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">Sure</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="quoted-text">
> + if (cont_val) {<br>
> + cont_list = &nif->then_list;<br>
> + entry_list = &nif->else_list;<br>
> + } else {<br>
> + cont_list = &nif->else_list;<br>
> + entry_list = &nif->then_list;<br>
> + }<br>
> +<br>
> + /* We want to be moving the contents of entry_list to above the<br>
> loop so it<br>
> + * can't contain any break or continue instructions.<br>
> + */<br>
> + foreach_list_typed(nir_cf_<wbr>node, cf_node, node, entry_list) {<br>
> + nir_foreach_block_in_<wbr>cf_node(block, cf_node) {<br>
<br>
</div>I think in my loop analysis pass I added a loop over all instructions<br>
and assert if I find a jump in case dead cf hasn't run or failed for<br>
some reason.</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">I don't think they are the same thing. This is looking at arbitrary loops and ifs. It could contain anything.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">
> + nir_instr *last_instr = nir_block_last_instr(block);<br>
> + if (last_instr && last_instr->type == nir_instr_type_jump)<br>
> + return false;<br>
> + }<br>
> + }<br>
> +<br>
> + /* Before we do anything, convert the loop to LCSSA. We're about<br>
> to<br>
> + * replace a bunch of SSA defs with registers and this will<br>
> prevent any of<br>
> + * it from leaking outside the loop.<br>
> + */<br>
> + nir_convert_loop_to_lcssa(<wbr>loop);<br>
> +<br>
> + nir_block *after_if_block =<br>
> + nir_cf_node_as_block(<wbr>nir_cf_node_next(&nif->cf_<wbr>node));<br>
> +<br>
> + /* Get rid of phis in the header block since we will be<br>
> duplicating it */<br>
> + nir_lower_phis_to_regs_<wbr>block(header_block);<br>
> + /* Get rid of phis after the if since dominance will change */<br>
> + nir_lower_phis_to_regs_<wbr>block(after_if_block);<br>
> +<br>
> + /* Get rid of SSA defs in the pieces we're about to move around<br>
> */<br>
> + nir_lower_ssa_defs_to_<wbr>regs_block(header_block);<br>
> + nir_foreach_block_in_cf_<wbr>node(block, &nif->cf_node)<br>
> + nir_lower_ssa_defs_to_<wbr>regs_block(block);<br>
> +<br>
> + nir_cf_list header, tmp;<br>
> + nir_cf_extract(&header, nir_before_block(header_block)<wbr>,<br>
> + <wbr>nir_after_block(header_block))<wbr>;<br>
> +<br>
> + nir_cf_list_clone(&tmp, &header, &loop->cf_node, NULL);<br>
> + nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_<wbr>node));<br>
> + nir_cf_extract(&tmp, nir_before_cf_list(entry_list)<wbr>,<br>
> + nir_<wbr>after_cf_list(entry_list));<br>
> + nir_cf_reinsert(&tmp, nir_before_cf_node(&loop->cf_<wbr>node));<br>
> +<br>
> + nir_cf_list_clone(&tmp, &header, &loop->cf_node, NULL);<br>
<br>
</div>Do we really need to clone it the second time? Is there any reason we<br>
can't just use the original header here?</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">No we don't. This is a relic of when I was still trying to massage SSA defs. I left it in so that it would be easier to catch things if I made a mistake going out of SSA. I'm happy to only clone once of you'd prefer.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">
> + nir_cf_reinsert(&tmp, nir_after_block_before_jump(<wbr>cont_block));<br>
> + nir_cf_extract(&tmp, nir_before_cf_list(cont_list),<br>
> + nir_<wbr>after_cf_list(cont_list));<br>
> + nir_cf_reinsert(&tmp, nir_after_block_before_jump(<wbr>cont_block));<br>
> +<br>
> + nir_cf_delete(&header);<br>
> + nir_cf_node_remove(&nif-><wbr>cf_node);<br>
> +<br>
> + return true;<br>
> +}<br>
> +<br>
> +static bool<br>
> +opt_if_cf_list(struct exec_list *cf_list)<br>
> +{<br>
> + bool progress = false;<br>
> + foreach_list_typed(nir_cf_<wbr>node, cf_node, node, cf_list) {<br>
> + switch (cf_node->type) {<br>
> + case nir_cf_node_block:<br>
> + break;<br>
> +<br>
> + case nir_cf_node_if: {<br>
> + nir_if *nif = nir_cf_node_as_if(cf_node);<br>
> + progress |= opt_if_cf_list(&nif->then_<wbr>list);<br>
> + progress |= opt_if_cf_list(&nif->else_<wbr>list);<br>
> + break;<br>
> + }<br>
> +<br>
> + case nir_cf_node_loop: {<br>
> + nir_loop *loop = nir_cf_node_as_loop(cf_node);<br>
> + progress |= opt_if_cf_list(&loop->body);<br>
> + progress |= opt_peel_loop_initial_if(loop)<wbr>;<br>
> + break;<br>
> + }<br>
> +<br>
> + case nir_cf_node_function:<br>
> + unreachable("Invalid cf type");<br>
> + }<br>
> + }<br>
> +<br>
> + return progress;<br>
> +}<br>
> +<br>
> +bool<br>
> +nir_opt_if(nir_shader *shader)<br>
<br>
</div>nir_opt_if is a fairly generic name and this pass is pretty specific.<br>
Is there a better name we could use for this pass?</blockquote></div></div></div><div dir="auto"><br></div><div dir="auto">Good question. I'm glad you asked. This pass had many names in my head, if not real life, while I was working on it. For a long time, the two passes were in the same file and were called nir_opt_loop_continues. In the end, I decided it was really more about ifs than about loops and bore more similarity with your if merging pass than anything else. (I wrote half of an if-merge in the process. It's been deleted but I still have it in the git history.) I figured we should just start an opt_if file and put if merging in with it since if merging doesn't really belong in dead_cf.</div><div dir="auto"><br></div><div dir="auto">That's my story. Feel free to disagree. I'm really not attached to it at all. Better ideas welcome.</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="elided-text">
> +{<br>
> + bool progress = false;<br>
> +<br>
> + nir_foreach_function(<wbr>function, shader) {<br>
> + if (function->impl == NULL)<br>
> + continue;<br>
> +<br>
> + if (opt_if_cf_list(&function-><wbr>impl->body)) {<br>
> + nir_metadata_<wbr>preserve(function->impl, nir_metadata_none);<br>
> +<br>
> + /* If that made progress, we're no longer really in SSA<br>
> form. We<br>
> + * need to convert registers back into SSA defs and clean<br>
> up SSA defs<br>
> + * that don't dominate their uses.<br>
> + */<br>
> + nir_convert_to_ssa_<wbr>impl(function->impl);<br>
> + progress = true;<br>
> + }<br>
> + }<br>
> +<br>
> + return progress;<br>
> +}<br>
</div></blockquote></div><br></div></div></div>