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

[Kenneth Graunke]

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