[PATCH v2 0/6] MR773: Draft: vkd3d-shader/ir: Try harder to move `break's to the end of loops.

[Giovanni Mascellani (＠giomasce)]

This goes atop !764. The last three commits belong to this MR.

Since we want to get rid of loops and `break's as much as possible, we try to move `break's out of selection constructs as much as possible so it's easier to match them with loops. This MR introduces a few other tricks to help that.

--
  v2: vkd3d-shader/ir: Move breaks out of selections again after having optimized loops.
      vkd3d-shader/ir: Append code to the non-breaking branch if there is breaking one.
      vkd3d-shader/ir: Prepare for changing the destination list in vsir_cfg_optimize_recurse().
      vkd3d-shader/ir: Remove loops that terminate with a `break'.
      vkd3d-shader/ir: Count how many jumps target each loop.

https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773

[PATCH v2 1/6] vkd3d-shader/ir: Move `break's out of selection constructs when possible.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 68 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 8af537390..7e43dff39 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -4259,6 +4259,71 @@ static void vsir_cfg_remove_trailing_continue(struct vsir_cfg_structure_list *li
         --list->count;
 }

+static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_structure_list *list)
+{
+    struct vsir_cfg_structure *structure;
+    size_t count = list->count;
+
+    if (count == 0)
+        return NULL;
+
+    structure = &list->structures[count - 1];
+
+    if (structure->type != STRUCTURE_TYPE_JUMP || structure->u.jump.type != JUMP_BREAK
+            || structure->u.jump.condition)
+        return NULL;
+
+    return structure;
+}
+
+/* When the last instruction in both branches of a selection construct
+ * is an unconditional break, any of them can be moved after the
+ * selection construct. If they break the same loop both of them can
+ * be moved out, otherwise we can choose which one: we choose the one
+ * that breaks the innermost loop, because we hope to eventually
+ * remove the loop itself.
+ *
+ * In principle a similar movement could be done when the last
+ * instructions are continue and continue, or continue and break. But
+ * in practice I don't think those situations can happen given the
+ * previous passes we do on the program, so we don't care. */
+static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_structure_list *list)
+{
+    struct vsir_cfg_structure *selection, *if_break, *else_break, *new_break;
+    unsigned int if_target, else_target, max_target;
+    size_t pos = list->count - 1;
+
+    selection = &list->structures[pos];
+    assert(selection->type == STRUCTURE_TYPE_SELECTION);
+
+    if_break = vsir_cfg_get_trailing_break(&selection->u.selection.if_body);
+    else_break = vsir_cfg_get_trailing_break(&selection->u.selection.else_body);
+
+    if (!if_break || !else_break)
+        return VKD3D_OK;
+
+    if_target = if_break->u.jump.target;
+    else_target = else_break->u.jump.target;
+    max_target = max(if_target, else_target);
+
+    if (!(new_break = vsir_cfg_structure_list_append(list, STRUCTURE_TYPE_JUMP)))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+    new_break->u.jump.type = JUMP_BREAK;
+    new_break->u.jump.target = max_target;
+
+    /* Pointer `selection' could have been invalidated by the append
+     * operation. */
+    selection = &list->structures[pos];
+    assert(selection->type == STRUCTURE_TYPE_SELECTION);
+
+    if (if_target == max_target)
+        --selection->u.selection.if_body.count;
+    if (else_target == max_target)
+        --selection->u.selection.else_body.count;
+
+    return VKD3D_OK;
+}
+
 static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structure_list *list)
 {
     enum vkd3d_result ret;
@@ -4299,6 +4364,9 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structur
         if ((ret = vsir_cfg_synthesize_selections(&structure->u.selection.else_body)) < 0)
             return ret;

+        if ((ret = vsir_cfg_move_breaks_out_of_selections(list)) < 0)
+            return ret;
+
         break;
     }

[PATCH v2 2/6] vkd3d-shader/ir: Count how many jumps target each loop.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 67 +++++++++++++++++++++++++++++++++++++-----
 1 file changed, 60 insertions(+), 7 deletions(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 7e43dff39..be5e94220 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3200,6 +3200,9 @@ struct vsir_cfg
          * block), but we still try to keep `begin' as forward as
          * possible, to keep the loop scope as small as possible. */
         bool synthetic;
+        /* The number of jump instructions (both conditional and
+         * unconditional) that target this loop. */
+        unsigned int target_count;
     } *loop_intervals;
     size_t loop_interval_count, loop_interval_capacity;

@@ -3248,6 +3251,7 @@ static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsign
     interval->begin = begin;
     interval->end = end;
     interval->synthetic = synthetic;
+    interval->target_count = 0;

return VKD3D_OK;
 }
@@ -4250,13 +4254,18 @@ fail:
     return VKD3D_ERROR_OUT_OF_MEMORY;
 }

-static void vsir_cfg_remove_trailing_continue(struct vsir_cfg_structure_list *list, unsigned int target)
+static void vsir_cfg_remove_trailing_continue(struct vsir_cfg *cfg,
+        struct vsir_cfg_structure_list *list, unsigned int target)
 {
     struct vsir_cfg_structure *last = &list->structures[list->count - 1];

if (last->type == STRUCTURE_TYPE_JUMP && last->u.jump.type == JUMP_CONTINUE
             && !last->u.jump.condition && last->u.jump.target == target)
+    {
         --list->count;
+        assert(cfg->loop_intervals[target].target_count > 0);
+        --cfg->loop_intervals[target].target_count;
+    }
 }

static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_structure_list *list)
@@ -4287,7 +4296,8 @@ static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_st
  * instructions are continue and continue, or continue and break. But
  * in practice I don't think those situations can happen given the
  * previous passes we do on the program, so we don't care. */
-static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_structure_list *list)
+static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg *cfg,
+        struct vsir_cfg_structure_list *list)
 {
     struct vsir_cfg_structure *selection, *if_break, *else_break, *new_break;
     unsigned int if_target, else_target, max_target;
@@ -4310,6 +4320,7 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_
         return VKD3D_ERROR_OUT_OF_MEMORY;
     new_break->u.jump.type = JUMP_BREAK;
     new_break->u.jump.target = max_target;
+    ++cfg->loop_intervals[max_target].target_count;

/* Pointer `selection' could have been invalidated by the append
      * operation. */
@@ -4317,14 +4328,24 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_
     assert(selection->type == STRUCTURE_TYPE_SELECTION);

if (if_target == max_target)
+    {
         --selection->u.selection.if_body.count;
+        assert(cfg->loop_intervals[if_target].target_count > 0);
+        --cfg->loop_intervals[if_target].target_count;
+    }
+
     if (else_target == max_target)
+    {
         --selection->u.selection.else_body.count;
+        assert(cfg->loop_intervals[else_target].target_count > 0);
+        --cfg->loop_intervals[else_target].target_count;
+    }

return VKD3D_OK;
 }

-static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structure_list *list)
+static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg,
+        struct vsir_cfg_structure_list *list)
 {
     enum vkd3d_result ret;
     size_t i;
@@ -4361,10 +4382,10 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structur
         *structure = new_selection;
         list->count = i + 1;

-        if ((ret = vsir_cfg_synthesize_selections(&structure->u.selection.else_body)) < 0)
+        if ((ret = vsir_cfg_synthesize_selections(cfg, &structure->u.selection.else_body)) < 0)
             return ret;

-        if ((ret = vsir_cfg_move_breaks_out_of_selections(list)) < 0)
+        if ((ret = vsir_cfg_move_breaks_out_of_selections(cfg, list)) < 0)
             return ret;

break;
@@ -4391,22 +4412,54 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct
         if (loop_body->count == 0)
             continue;

-        vsir_cfg_remove_trailing_continue(loop_body, loop->u.loop.idx);
+        vsir_cfg_remove_trailing_continue(cfg, loop_body, loop->u.loop.idx);

if ((ret = vsir_cfg_optimize_recurse(cfg, loop_body)) < 0)
             return ret;

-        if ((ret = vsir_cfg_synthesize_selections(loop_body)) < 0)
+        if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0)
             return ret;
     }

return VKD3D_OK;
 }

+static void vsir_cfg_count_targets(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list)
+{
+    size_t i;
+
+    for (i = 0; i < list->count; ++i)
+    {
+        struct vsir_cfg_structure *structure = &list->structures[i];
+
+        switch (structure->type)
+        {
+            case STRUCTURE_TYPE_BLOCK:
+                break;
+
+            case STRUCTURE_TYPE_LOOP:
+                vsir_cfg_count_targets(cfg, &structure->u.loop.body);
+                break;
+
+            case STRUCTURE_TYPE_SELECTION:
+                vsir_cfg_count_targets(cfg, &structure->u.selection.if_body);
+                vsir_cfg_count_targets(cfg, &structure->u.selection.else_body);
+                break;
+
+            case STRUCTURE_TYPE_JUMP:
+                if (structure->u.jump.type == JUMP_BREAK || structure->u.jump.type == JUMP_CONTINUE)
+                    ++cfg->loop_intervals[structure->u.jump.target].target_count;
+                break;
+        }
+    }
+}
+
 static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg)
 {
     enum vkd3d_result ret;

+    vsir_cfg_count_targets(cfg, &cfg->structured_program);
+
     ret = vsir_cfg_optimize_recurse(cfg, &cfg->structured_program);

if (TRACE_ON())

[PATCH v2 3/6] vkd3d-shader/ir: Remove loops that terminate with a `break'.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 81 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 79 insertions(+), 2 deletions(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index be5e94220..c3a9a6062 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -4394,8 +4394,64 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg,
     return VKD3D_OK;
 }

+static enum vkd3d_result vsir_cfg_append_loop(struct vsir_cfg *cfg,
+        struct vsir_cfg_structure_list *new_list, struct vsir_cfg_structure *loop)
+{
+    struct vsir_cfg_structure_list *loop_body = &loop->u.loop.body;
+    unsigned int target, loop_idx = loop->u.loop.idx;
+    struct vsir_cfg_structure *trailing_break;
+    enum vkd3d_result ret;
+
+    trailing_break = vsir_cfg_get_trailing_break(loop_body);
+
+    /* If the loop's last instruction is not a break, we cannot remove
+     * the loop itself. */
+    if (!trailing_break)
+    {
+        if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0)
+            return ret;
+        memset(loop, 0, sizeof(*loop));
+        return VKD3D_OK;
+    }
+
+    target = trailing_break->u.jump.target;
+    assert(cfg->loop_intervals[target].target_count > 0);
+
+    /* If the loop is not targeted by any jump, we can remove it. The
+     * trailing `break' then targets another loop, so we have to keep
+     * it. */
+    if (cfg->loop_intervals[loop_idx].target_count == 0)
+    {
+        if ((ret = vsir_cfg_structure_list_append_from_region(new_list,
+                &loop_body->structures[0], loop_body->count)) < 0)
+            return ret;
+        loop_body->count = 0;
+        return VKD3D_OK;
+    }
+
+    /* If the loop is targeted only by its own trailing `break'
+     * instruction, then we can remove it together with the `break'
+     * itself. */
+    if (target == loop_idx && cfg->loop_intervals[loop_idx].target_count == 1)
+    {
+        --cfg->loop_intervals[loop_idx].target_count;
+        if ((ret = vsir_cfg_structure_list_append_from_region(new_list,
+                &loop_body->structures[0], loop_body->count - 1)) < 0)
+            return ret;
+        loop_body->count = 0;
+        return VKD3D_OK;
+    }
+
+    if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0)
+        return ret;
+    memset(loop, 0, sizeof(*loop));
+
+    return VKD3D_OK;
+}
+
 static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list)
 {
+    struct vsir_cfg_structure_list new_list = {0};
     enum vkd3d_result ret;
     size_t i;

@@ -4405,23 +4461,44 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct
         struct vsir_cfg_structure_list *loop_body;

if (loop->type != STRUCTURE_TYPE_LOOP)
+        {
+            if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0)
+                goto fail;
+            memset(loop, 0, sizeof(*loop));
             continue;
+        }

loop_body = &loop->u.loop.body;

if (loop_body->count == 0)
+        {
+            if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0)
+                goto fail;
+            memset(loop, 0, sizeof(*loop));
             continue;
+        }

vsir_cfg_remove_trailing_continue(cfg, loop_body, loop->u.loop.idx);

if ((ret = vsir_cfg_optimize_recurse(cfg, loop_body)) < 0)
-            return ret;
+            goto fail;

if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0)
-            return ret;
+            goto fail;
+
+        if ((ret = vsir_cfg_append_loop(cfg, &new_list, loop)) < 0)
+            goto fail;
     }

+    vsir_cfg_structure_list_cleanup(list);
+    *list = new_list;
+
     return VKD3D_OK;
+
+fail:
+    vsir_cfg_structure_list_cleanup(list);
+
+    return ret;
 }

static void vsir_cfg_count_targets(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list)

[PATCH v2 4/6] vkd3d-shader/ir: Prepare for changing the destination list in vsir_cfg_optimize_recurse().

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 21 ++++++++++-----------
 1 file changed, 10 insertions(+), 11 deletions(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index c3a9a6062..0be94def0 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -4451,18 +4451,20 @@ static enum vkd3d_result vsir_cfg_append_loop(struct vsir_cfg *cfg,

static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list)
 {
-    struct vsir_cfg_structure_list new_list = {0};
+    struct vsir_cfg_structure_list old_list = *list, *new_list = list;
     enum vkd3d_result ret;
     size_t i;

-    for (i = 0; i < list->count; ++i)
+    memset(new_list, 0, sizeof(*new_list));
+
+    for (i = 0; i < old_list.count; ++i)
     {
-        struct vsir_cfg_structure *loop = &list->structures[i];
+        struct vsir_cfg_structure *loop = &old_list.structures[i];
         struct vsir_cfg_structure_list *loop_body;

if (loop->type != STRUCTURE_TYPE_LOOP)
         {
-            if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0)
+            if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0)
                 goto fail;
             memset(loop, 0, sizeof(*loop));
             continue;
@@ -4472,7 +4474,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct

if (loop_body->count == 0)
         {
-            if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0)
+            if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0)
                 goto fail;
             memset(loop, 0, sizeof(*loop));
             continue;
@@ -4486,17 +4488,14 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct
         if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0)
             goto fail;

-        if ((ret = vsir_cfg_append_loop(cfg, &new_list, loop)) < 0)
+        if ((ret = vsir_cfg_append_loop(cfg, new_list, loop)) < 0)
             goto fail;
     }

-    vsir_cfg_structure_list_cleanup(list);
-    *list = new_list;
-
-    return VKD3D_OK;
+    ret = VKD3D_OK;

fail:
-    vsir_cfg_structure_list_cleanup(list);
+    vsir_cfg_structure_list_cleanup(&old_list);

return ret;
 }

[PATCH v2 5/6] vkd3d-shader/ir: Append code to the non-breaking branch if there is breaking one.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 0be94def0..7da37e04b 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -4459,7 +4459,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct

for (i = 0; i < old_list.count; ++i)
     {
-        struct vsir_cfg_structure *loop = &old_list.structures[i];
+        struct vsir_cfg_structure *loop = &old_list.structures[i], *selection;
         struct vsir_cfg_structure_list *loop_body;

if (loop->type != STRUCTURE_TYPE_LOOP)
@@ -4490,6 +4490,22 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct

if ((ret = vsir_cfg_append_loop(cfg, new_list, loop)) < 0)
             goto fail;
+
+        /* If the last pushed instruction is a selection and one of the branches terminates with a
+         * `break', start pushing to the other branch, in the hope of eventually push a `break'
+         * there too and be able to remove a loop. */
+        if (new_list->count == 0)
+            continue;
+
+        selection = &new_list->structures[new_list->count - 1];
+
+        if (selection->type == STRUCTURE_TYPE_SELECTION)
+        {
+            if (vsir_cfg_get_trailing_break(&selection->u.selection.if_body))
+                new_list = &selection->u.selection.else_body;
+            else if (vsir_cfg_get_trailing_break(&selection->u.selection.else_body))
+                new_list = &selection->u.selection.if_body;
+        }
     }

ret = VKD3D_OK;

[PATCH v2 6/6] vkd3d-shader/ir: Move breaks out of selections again after having optimized loops.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 libs/vkd3d-shader/ir.c | 21 ++++++++++++++++++++-
 1 file changed, 20 insertions(+), 1 deletion(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 7da37e04b..a3fae97c8 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -4344,6 +4344,25 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg
     return VKD3D_OK;
 }

+static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections_recursively(struct vsir_cfg *cfg,
+        struct vsir_cfg_structure_list *list)
+{
+    struct vsir_cfg_structure *trailing;
+
+    if (list->count == 0)
+        return VKD3D_OK;
+
+    trailing = &list->structures[list->count - 1];
+
+    if (trailing->type != STRUCTURE_TYPE_SELECTION)
+        return VKD3D_OK;
+
+    vsir_cfg_move_breaks_out_of_selections_recursively(cfg, &trailing->u.selection.if_body);
+    vsir_cfg_move_breaks_out_of_selections_recursively(cfg, &trailing->u.selection.else_body);
+
+    return vsir_cfg_move_breaks_out_of_selections(cfg, list);
+}
+
 static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg,
         struct vsir_cfg_structure_list *list)
 {
@@ -4508,7 +4527,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct
         }
     }

-    ret = VKD3D_OK;
+    ret = vsir_cfg_move_breaks_out_of_selections_recursively(cfg, list);

fail:
     vsir_cfg_structure_list_cleanup(&old_list);