[PATCH v7 0/4] MR656: vkd3d-shader/ir: Introduce a better CFG structurizer, part 1.

[Giovanni Mascellani (＠giomasce)]

This first MR create an internal structured representation of the CFG and computes the domination relationship. Over a few other MRs I will implement an algorithm inspired to [this article](https://medium.com/leaningtech/solving-the-structured-control-flow-problem-o...) to compute a better structure than the one we already have, but for the moment the computed data is immediately wasted. A working prototype of the new structurizer is now available in https://gitlab.winehq.org/giomasce/vkd3d/-/commits/cfg4, though further improvement is planned on top of that too.

--
  v7: vkd3d-shader/ir: Dump the domination relationship.
      vkd3d-shader/ir: Compute the domination relationship.
      vkd3d-shader/ir: Dump the control flow graph in the GraphViz format.
      vkd3d-shader/ir: Build a representation of the control flow graph.
 
https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/656

[PATCH v7 1/4] vkd3d-shader/ir: Build a representation of the control flow graph.

[Giovanni Mascellani]

From: Giovanni Mascellani <gmascellani(a)codeweavers.com>

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

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 886344874..4da8c0cb4 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3009,6 +3009,194 @@ fail:
     return VKD3D_ERROR_OUT_OF_MEMORY;
 }
 
+struct vsir_block_list
+{
+    struct vsir_block **blocks;
+    size_t count, capacity;
+};
+
+static void vsir_block_list_init(struct vsir_block_list *list)
+{
+    memset(list, 0, sizeof(*list));
+}
+
+static void vsir_block_list_cleanup(struct vsir_block_list *list)
+{
+    vkd3d_free(list->blocks);
+}
+
+static enum vkd3d_result vsir_block_list_add(struct vsir_block_list *list, struct vsir_block *block)
+{
+    size_t i;
+
+    for (i = 0; i < list->count; ++i)
+        if (block == list->blocks[i])
+            return VKD3D_OK;
+
+    if (!vkd3d_array_reserve((void **)&list->blocks, &list->capacity, list->count + 1, sizeof(*list->blocks)))
+    {
+        ERR("Cannot extend block list.\n");
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+    }
+
+    list->blocks[list->count++] = block;
+
+    return VKD3D_OK;
+}
+
+struct vsir_block
+{
+    unsigned int label;
+    /* `begin' points to the instruction immediately following the
+     * LABEL that introduces the block. `end' points to the terminator
+     * instruction (either BRANCH or RET). They can coincide, meaning
+     * that the block is empty. */
+    struct vkd3d_shader_instruction *begin, *end;
+    struct vsir_block_list predecessors, successors;
+};
+
+static void vsir_block_init(struct vsir_block *block, unsigned int label)
+{
+    assert(label);
+    memset(block, 0, sizeof(*block));
+    block->label = label;
+    vsir_block_list_init(&block->predecessors);
+    vsir_block_list_init(&block->successors);
+}
+
+static void vsir_block_cleanup(struct vsir_block *block)
+{
+    vsir_block_list_cleanup(&block->predecessors);
+    vsir_block_list_cleanup(&block->successors);
+}
+
+struct vsir_cfg
+{
+    struct vsir_program *program;
+    struct vsir_block *blocks;
+    struct vsir_block *entry;
+    size_t block_count;
+};
+
+static void vsir_cfg_cleanup(struct vsir_cfg *cfg)
+{
+    size_t i;
+
+    for (i = 0; i < cfg->block_count; ++i)
+        vsir_block_cleanup(&cfg->blocks[i]);
+
+    vkd3d_free(cfg->blocks);
+}
+
+static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_block *block,
+        struct vkd3d_shader_src_param *successor_param)
+{
+    unsigned int target = label_from_src_param(successor_param);
+    struct vsir_block *successor = &cfg->blocks[target - 1];
+    enum vkd3d_result ret;
+
+    assert(successor->label != 0);
+
+    if ((ret = vsir_block_list_add(&block->successors, successor)) < 0)
+        return ret;
+
+    if ((ret = vsir_block_list_add(&successor->predecessors, block)) < 0)
+        return ret;
+
+    return VKD3D_OK;
+}
+
+static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program)
+{
+    struct vsir_block *current_block = NULL;
+    enum vkd3d_result ret;
+    size_t i;
+
+    memset(cfg, 0, sizeof(*cfg));
+    cfg->program = program;
+    cfg->block_count = program->block_count;
+
+    if (!(cfg->blocks = vkd3d_calloc(cfg->block_count, sizeof(*cfg->blocks))))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    for (i = 0; i < program->instructions.count; ++i)
+    {
+        struct vkd3d_shader_instruction *instruction = &program->instructions.elements[i];
+
+        switch (instruction->handler_idx)
+        {
+            case VKD3DSIH_PHI:
+            case VKD3DSIH_SWITCH_MONOLITHIC:
+                vkd3d_unreachable();
+
+            case VKD3DSIH_LABEL:
+            {
+                unsigned int label = label_from_src_param(&instruction->src[0]);
+
+                assert(!current_block);
+                assert(label > 0);
+                assert(label <= cfg->block_count);
+                current_block = &cfg->blocks[label - 1];
+                vsir_block_init(current_block, label);
+                current_block->begin = &program->instructions.elements[i + 1];
+                if (!cfg->entry)
+                    cfg->entry = current_block;
+                break;
+            }
+
+            case VKD3DSIH_BRANCH:
+            case VKD3DSIH_RET:
+                assert(current_block);
+                current_block->end = instruction;
+                current_block = NULL;
+                break;
+
+            default:
+                break;
+        }
+    }
+
+    for (i = 0; i < cfg->block_count; ++i)
+    {
+        struct vsir_block *block = &cfg->blocks[i];
+
+        if (block->label == 0)
+            continue;
+
+        switch (block->end->handler_idx)
+        {
+            case VKD3DSIH_RET:
+                break;
+
+            case VKD3DSIH_BRANCH:
+                if (vsir_register_is_label(&block->end->src[0].reg))
+                {
+                    if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[0])) < 0)
+                        goto fail;
+                }
+                else
+                {
+                    if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[1])) < 0)
+                        goto fail;
+
+                    if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[2])) < 0)
+                        goto fail;
+                }
+                break;
+
+            default:
+                vkd3d_unreachable();
+        }
+    }
+
+    return VKD3D_OK;
+
+fail:
+    vsir_cfg_cleanup(cfg);
+
+    return ret;
+}
+
 enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
         const struct vkd3d_shader_compile_info *compile_info)
 {
@@ -3022,14 +3210,24 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
 
     if (parser->shader_desc.is_dxil)
     {
+        struct vsir_cfg cfg;
+
         if ((result = lower_switch_to_if_ladder(&parser->program)) < 0)
             return result;
 
         if ((result = materialize_ssas_to_temps(parser)) < 0)
             return result;
 
+        if ((result = vsir_cfg_init(&cfg, &parser->program)) < 0)
+            return result;
+
         if ((result = simple_structurizer_run(parser)) < 0)
+        {
+            vsir_cfg_cleanup(&cfg);
             return result;
+        }
+
+        vsir_cfg_cleanup(&cfg);
     }
     else
     {
-- 
GitLab


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

[PATCH v7 2/4] vkd3d-shader/ir: Dump the control flow graph in the GraphViz format.

[Giovanni Mascellani]

From: Giovanni Mascellani <gmascellani(a)codeweavers.com>

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

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 4da8c0cb4..646a71a2d 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3106,6 +3106,43 @@ static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_blo
     return VKD3D_OK;
 }
 
+static void vsir_cfg_dump_dot(struct vsir_cfg *cfg)
+{
+    size_t i, j;
+
+    TRACE("digraph cfg {\n");
+
+    for (i = 0; i < cfg->block_count; ++i)
+    {
+        struct vsir_block *block = &cfg->blocks[i];
+        const char *shape;
+
+        if (block->label == 0)
+            continue;
+
+        switch (block->end->handler_idx)
+        {
+            case VKD3DSIH_RET:
+                shape = "trapezium";
+                break;
+
+            case VKD3DSIH_BRANCH:
+                shape = vsir_register_is_label(&block->end->src[0].reg) ? "ellipse" : "box";
+                break;
+
+            default:
+                vkd3d_unreachable();
+        }
+
+        TRACE("  n%u [label=\"%u\", shape=\"%s\"];\n", block->label, block->label, shape);
+
+        for (j = 0; j < block->successors.count; ++j)
+            TRACE("  n%u -> n%u;\n", block->label, block->successors.blocks[j]->label);
+    }
+
+    TRACE("}\n");
+}
+
 static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program)
 {
     struct vsir_block *current_block = NULL;
@@ -3189,6 +3226,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program
         }
     }
 
+    if (TRACE_ON())
+        vsir_cfg_dump_dot(cfg);
+
     return VKD3D_OK;
 
 fail:
-- 
GitLab


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

[PATCH v7 3/4] vkd3d-shader/ir: Compute the domination relationship.

[Giovanni Mascellani]

From: Giovanni Mascellani <gmascellani(a)codeweavers.com>

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

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 646a71a2d..536b19e13 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3053,21 +3053,40 @@ struct vsir_block
      * that the block is empty. */
     struct vkd3d_shader_instruction *begin, *end;
     struct vsir_block_list predecessors, successors;
+    uint32_t *dominates;
 };
 
-static void vsir_block_init(struct vsir_block *block, unsigned int label)
+static enum vkd3d_result vsir_block_init(struct vsir_block *block, unsigned int label, size_t block_count)
 {
+    size_t byte_count;
+
+    if (block_count > SIZE_MAX - (sizeof(*block->dominates) * CHAR_BIT - 1))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    block_count = align(block_count, sizeof(*block->dominates) * CHAR_BIT);
+    byte_count = block_count / CHAR_BIT;
+
     assert(label);
     memset(block, 0, sizeof(*block));
     block->label = label;
     vsir_block_list_init(&block->predecessors);
     vsir_block_list_init(&block->successors);
+
+    if (!(block->dominates = vkd3d_malloc(byte_count)))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    memset(block->dominates, 0xff, byte_count);
+
+    return VKD3D_OK;
 }
 
 static void vsir_block_cleanup(struct vsir_block *block)
 {
+    if (block->label == 0)
+        return;
     vsir_block_list_cleanup(&block->predecessors);
     vsir_block_list_cleanup(&block->successors);
+    vkd3d_free(block->dominates);
 }
 
 struct vsir_cfg
@@ -3174,7 +3193,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program
                 assert(label > 0);
                 assert(label <= cfg->block_count);
                 current_block = &cfg->blocks[label - 1];
-                vsir_block_init(current_block, label);
+                assert(current_block->label == 0);
+                if ((ret = vsir_block_init(current_block, label, program->block_count)) < 0)
+                    goto fail;
                 current_block->begin = &program->instructions.elements[i + 1];
                 if (!cfg->entry)
                     cfg->entry = current_block;
@@ -3237,6 +3258,46 @@ fail:
     return ret;
 }
 
+/* Block A dominates block B if every path from the entry point to B
+ * must pass through A. Naively compute the set of blocks that are
+ * dominated by `reference' by running a graph visit starting from the
+ * entry point (which must be the initial value of `current') and
+ * avoiding `reference'. Running this for all the blocks takes
+ * quadratic time: if in the future something better is sought after,
+ * the standard tool seems to be the Lengauer-Tarjan algorithm. */
+static void vsir_cfg_compute_dominators_recurse(struct vsir_block *current, struct vsir_block *reference)
+{
+    size_t i;
+
+    assert(current->label != 0);
+
+    if (current == reference)
+        return;
+
+    if (!bitmap_is_set(reference->dominates, current->label - 1))
+        return;
+
+    bitmap_clear(reference->dominates, current->label - 1);
+
+    for (i = 0; i < current->successors.count; ++i)
+        vsir_cfg_compute_dominators_recurse(current->successors.blocks[i], reference);
+}
+
+static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg)
+{
+    size_t i;
+
+    for (i = 0; i < cfg->block_count; ++i)
+    {
+        struct vsir_block *block = &cfg->blocks[i];
+
+        if (block->label == 0)
+            continue;
+
+        vsir_cfg_compute_dominators_recurse(cfg->entry, block);
+    }
+}
+
 enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
         const struct vkd3d_shader_compile_info *compile_info)
 {
@@ -3261,6 +3322,8 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
         if ((result = vsir_cfg_init(&cfg, &parser->program)) < 0)
             return result;
 
+        vsir_cfg_compute_dominators(&cfg);
+
         if ((result = simple_structurizer_run(parser)) < 0)
         {
             vsir_cfg_cleanup(&cfg);
-- 
GitLab


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

[PATCH v7 4/4] vkd3d-shader/ir: Dump the domination relationship.

[Giovanni Mascellani]

From: Giovanni Mascellani <gmascellani(a)codeweavers.com>

---
 libs/vkd3d-shader/ir.c                   | 26 +++++++++++++++++++++++-
 libs/vkd3d-shader/vkd3d_shader_main.c    |  2 +-
 libs/vkd3d-shader/vkd3d_shader_private.h |  1 +
 3 files changed, 27 insertions(+), 2 deletions(-)

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 536b19e13..f0bd85338 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3285,7 +3285,11 @@ static void vsir_cfg_compute_dominators_recurse(struct vsir_block *current, stru
 
 static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg)
 {
-    size_t i;
+    struct vkd3d_string_buffer buf;
+    size_t i, j;
+
+    if (TRACE_ON())
+        vkd3d_string_buffer_init(&buf);
 
     for (i = 0; i < cfg->block_count; ++i)
     {
@@ -3295,7 +3299,27 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg)
             continue;
 
         vsir_cfg_compute_dominators_recurse(cfg->entry, block);
+
+        if (TRACE_ON())
+        {
+            vkd3d_string_buffer_printf(&buf, "Block %u dominates:", block->label);
+            for (j = 0; j < cfg->block_count; j++)
+            {
+                struct vsir_block *block2 = &cfg->blocks[j];
+
+                if (block2->label == 0)
+                    continue;
+
+                if (bitmap_is_set(block->dominates, j))
+                    vkd3d_string_buffer_printf(&buf, " %u", block2->label);
+            }
+            TRACE("%s\n", buf.buffer);
+            vkd3d_string_buffer_clear(&buf);
+        }
     }
+
+    if (TRACE_ON())
+        vkd3d_string_buffer_cleanup(&buf);
 }
 
 enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
diff --git a/libs/vkd3d-shader/vkd3d_shader_main.c b/libs/vkd3d-shader/vkd3d_shader_main.c
index 20c4c2e2d..462a5c25e 100644
--- a/libs/vkd3d-shader/vkd3d_shader_main.c
+++ b/libs/vkd3d-shader/vkd3d_shader_main.c
@@ -71,7 +71,7 @@ void vkd3d_string_buffer_cleanup(struct vkd3d_string_buffer *buffer)
     vkd3d_free(buffer->buffer);
 }
 
-static void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer)
+void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer)
 {
     buffer->buffer[0] = '\0';
     buffer->content_size = 0;
diff --git a/libs/vkd3d-shader/vkd3d_shader_private.h b/libs/vkd3d-shader/vkd3d_shader_private.h
index 7239beaf7..4b322b95b 100644
--- a/libs/vkd3d-shader/vkd3d_shader_private.h
+++ b/libs/vkd3d-shader/vkd3d_shader_private.h
@@ -1399,6 +1399,7 @@ struct vkd3d_string_buffer *vkd3d_string_buffer_get(struct vkd3d_string_buffer_c
 void vkd3d_string_buffer_init(struct vkd3d_string_buffer *buffer);
 void vkd3d_string_buffer_cache_cleanup(struct vkd3d_string_buffer_cache *list);
 void vkd3d_string_buffer_cache_init(struct vkd3d_string_buffer_cache *list);
+void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer);
 int vkd3d_string_buffer_print_f32(struct vkd3d_string_buffer *buffer, float f);
 int vkd3d_string_buffer_print_f64(struct vkd3d_string_buffer *buffer, double d);
 int vkd3d_string_buffer_printf(struct vkd3d_string_buffer *buffer, const char *format, ...) VKD3D_PRINTF_FUNC(2, 3);
-- 
GitLab

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

[Giovanni Mascellani (＠giomasce)]

Hopefully the latest revision addresses all the feedback so far.

-- 
https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/656#note_62235

[PATCH v7 0/4] MR656: vkd3d-shader/ir: Introduce a better CFG structurizer, part 1. - approved

[Henri Verbeet (＠hverbeet)]

This merge request was approved by Henri Verbeet.
-- 
https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/656