[Mesa-dev] [PATCH v2] nir/cf: Alter block successors before adding a fake link.

[Connor Abbott]

On Wed, Sep 23, 2015 at 1:09 PM, Kenneth Graunke <kenneth at whitecape.org> wrote:
> Consider the case of "while (...) { break }".  Or in NIR:
>
>         block block_0 (0x7ab640):
>         ...
>         /* succs: block_1 */
>         loop {
>                 block block_1:
>                 /* preds: block_0 */
>                 break
>                 /* succs: block_2 */
>         }
>         block block_2:
>
> Calling nir_handle_remove_jump(block_1, nir_jump_break) will remove the break.
> Unfortunately, it would mangle the predecessors and successors.
>
> Here, block_2->predecessors->entries == 1, so we would create a fake
> link, setting block_1->successors[1] = block_2, and adding block_1 to
> block_2's predecessor set.  This is illegal: a block cannot specify the
> same successor twice.  In particular, adding the predecessor would have
> no effect, as it was already present in the set.
>
> We'd then call unlink_block_successors(), which would delete the fake
> link and remove block_1 from block_2's predecessor set.  It would then
> delete successors[0], and attempt to remove block_1 from block_2's
> predecessor set a second time...except that it wouldn't be present,
> triggering an assertion failure.
>
> The fix appears to be simple: simply unlink the block's successors and
> recreate them to point at the correct blocks first.  Then, add the fake
> link.  In the above example, removing the break would cause block_1 to
> have itself as a successor (as it becomes an infinite loop), so adding
> the fake link won't cause a duplicate successor.
>
> v2: Add comments (requested by Connor Abbott) and fix commit message.
>
> Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
> Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
> ---
>  src/glsl/nir/nir_control_flow.c | 44 ++++++++++++++++++++++++++---------------
>  1 file changed, 28 insertions(+), 16 deletions(-)
>
> Here are some more comments.  I also realized I never finished editing the
> commit message, so there were fragments of paragraphs all over the place.
> That's fixed now too.  (The code is identical.)
>
> diff --git a/src/glsl/nir/nir_control_flow.c b/src/glsl/nir/nir_control_flow.c
> index 2b23f38..87bc716 100644
> --- a/src/glsl/nir/nir_control_flow.c
> +++ b/src/glsl/nir/nir_control_flow.c
> @@ -551,31 +551,43 @@ remove_phi_src(nir_block *block, nir_block *pred)
>  static void
>  unlink_jump(nir_block *block, nir_jump_type type, bool add_normal_successors)
>  {
> +   nir_block *next = block->successors[0];
> +
>     if (block->successors[0])
>        remove_phi_src(block->successors[0], block);
>     if (block->successors[1])
>        remove_phi_src(block->successors[1], block);
>
> -   if (type == nir_jump_break) {
> -      nir_block *next = block->successors[0];
> +   unlink_block_successors(block);
> +   if (add_normal_successors)
> +      block_add_normal_succs(block);
>
> -      if (next->predecessors->entries == 1) {
> -         nir_loop *loop =
> -            nir_cf_node_as_loop(nir_cf_node_prev(&next->cf_node));
> +   /* If we've just removed a break, and the block we were jumping to (after
> +    * the loop) now has zero predecessors, we've created a new infinite loop.
> +    *
> +    * NIR doesn't allow blocks (other than the start block) to have zero
> +    * predecessors.  In particular, dominance assumes all blocks are reachable.
> +    * So, we insert a "fake link" by making successors[1] point after the loop.
> +    *
> +    * Note that we have to do this after unlinking/recreating the block's
> +    * successors.  If we removed a "break" at the end of the loop, then
> +    * block == last_block, so block->successors[0] would already be "next",
> +    * and adding a fake link would create two identical successors.  Doing
> +    * this afterward works, as we'll have changed block->successors[0] to
> +    * be the top of the loop.
> +    */
> +   if (type == nir_jump_break && next->predecessors->entries == 0) {
> +      nir_loop *loop =
> +         nir_cf_node_as_loop(nir_cf_node_prev(&next->cf_node));
>
> -         /* insert fake link */
> -         nir_cf_node *last = nir_loop_last_cf_node(loop);
> -         assert(last->type == nir_cf_node_block);
> -         nir_block *last_block = nir_cf_node_as_block(last);
> +      /* insert fake link */
> +      nir_cf_node *last = nir_loop_last_cf_node(loop);
> +      assert(last->type == nir_cf_node_block);
> +      nir_block *last_block = nir_cf_node_as_block(last);
>
> -         last_block->successors[1] = next;
> -         block_add_pred(next, last_block);
> -      }
> +      last_block->successors[1] = next;
> +      block_add_pred(next, last_block);
>     }
> -
> -   unlink_block_successors(block);
> -   if (add_normal_successors)
> -      block_add_normal_succs(block);
>  }
>
>  void
> --
> 2.5.3
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev

LGTM.