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

[Giovanni Mascellani (＠giomasce)]

Another round of optimizations for the CFG structurizer. Here we begin getting rid of many of the loops that were generated during structurization to represent forward jumps, but that are better expressed with selection constructs when possible. More optimizations will follow.

--
  v2: 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/764

[PATCH v2 1/3] 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/3] 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/3] 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 0/3] MR764: vkd3d-shader/ir: Remove loops that terminate with a `break'. - approved

[Conor McCarthy (＠cmccarthy)]

This merge request was approved by Conor McCarthy.

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

[Henri Verbeet (＠hverbeet)]

This merge request was approved by Henri Verbeet.