[PATCH v4 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.

--
  v4: 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 v4 1/4] vkd3d-shader/ir: Build a representation of the control flow graph.

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 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..18d70c78b 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 vkd3d_shader_parser *parser;
+    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 vkd3d_shader_parser *parser)
+{
+    struct vsir_block *current_block = NULL;
+    enum vkd3d_result ret;
+    size_t i;
+
+    memset(cfg, 0, sizeof(*cfg));
+    cfg->parser = parser;
+    cfg->block_count = parser->program.block_count;
+
+    if (!(cfg->blocks = vkd3d_calloc(cfg->block_count, sizeof(*cfg->blocks))))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    for (i = 0; i < parser->program.instructions.count; ++i)
+    {
+        struct vkd3d_shader_instruction *instruction = &parser->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 = &parser->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)) < 0)
+            return result;
+
         if ((result = simple_structurizer_run(parser)) < 0)
+        {
+            vsir_cfg_cleanup(&cfg);
             return result;
+        }
+
+        vsir_cfg_cleanup(&cfg);
     }
     else
     {

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

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 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 18d70c78b..86b43317b 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)
+            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 vkd3d_shader_parser *parser)
 {
     struct vsir_block *current_block = NULL;
@@ -3189,6 +3226,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vkd3d_shader
         }
     }

+    if (TRACE_ON())
+        vsir_cfg_dump_dot(cfg);
+
     return VKD3D_OK;

fail:

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

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 include/private/vkd3d_common.h |  9 +++++
 libs/vkd3d-shader/ir.c         | 67 +++++++++++++++++++++++++++++++++-
 2 files changed, 74 insertions(+), 2 deletions(-)

diff --git a/include/private/vkd3d_common.h b/include/private/vkd3d_common.h
index 8d6e7b376..add273aa5 100644
--- a/include/private/vkd3d_common.h
+++ b/include/private/vkd3d_common.h
@@ -76,6 +76,15 @@ static inline uint64_t align(uint64_t addr, size_t alignment)
     return (addr + (alignment - 1)) & ~(alignment - 1);
 }

+static inline bool align_to_size(uint64_t addr, size_t alignment, size_t *ret)
+{
+    *ret = align(addr, alignment);
+
+    /* This could fail because align() overflowed or because the
+     * result wouldn't fit in size_t (on 32 bit). */
+    return *ret >= addr;
+}
+
 #if defined(__GNUC__) || defined(__clang__)
 # define VKD3D_NORETURN __attribute__((noreturn))
 # ifdef __MINGW_PRINTF_FORMAT
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 86b43317b..4c4efb813 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3053,21 +3053,39 @@ 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, unsigned int block_count)
 {
+    size_t dominates_size;
+
+    if (!align_to_size(block_count, sizeof(*block->dominates) * CHAR_BIT, &dominates_size))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    dominates_size /= 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(dominates_size)))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    memset(block->dominates, 0xff, dominates_size);
+
+    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 +3192,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vkd3d_shader
                 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, parser->program.block_count)) < 0)
+                    goto fail;
                 current_block->begin = &parser->program.instructions.elements[i + 1];
                 if (!cfg->entry)
                     cfg->entry = current_block;
@@ -3237,6 +3257,47 @@ fail:
     return ret;
 }

+/* Block A dominates block B if every path from the entry point to B
+ * must pass through A. Naively computer 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(uint32_t *dominates, struct vsir_block *current,
+        struct vsir_block *reference)
+{
+    size_t i;
+
+    assert(current->label != 0);
+
+    if (current == reference)
+        return;
+
+    if (!bitmap_is_set(dominates, current->label - 1))
+        return;
+
+    bitmap_clear(dominates, current->label - 1);
+
+    for (i = 0; i < current->successors.count; ++i)
+        vsir_cfg_compute_dominators_recurse(dominates, 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(block->dominates, 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)) < 0)
             return result;

+        vsir_cfg_compute_dominators(&cfg);
+
         if ((result = simple_structurizer_run(parser)) < 0)
         {
             vsir_cfg_cleanup(&cfg);

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

[Giovanni Mascellani]

From: Giovanni Mascellani

---
 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 4c4efb813..34bbda7cd 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3285,7 +3285,11 @@ static void vsir_cfg_compute_dominators_recurse(uint32_t *dominates, struct vsir

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(block->dominates, 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 ebabf50e9..942bc81a9 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 1030adf98..33fbd77a7 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);

[Conor McCarthy (＠cmccarthy)]

Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/ir.c:
>  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)
> -
>        continue;

Is `block` ever `null` here? Looks like it shouldn't be.

[Conor McCarthy (＠cmccarthy)]

Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/ir.c:
>  return ret;
>
> }
>
> +/* Block A dominates block B if every path from the entry point to B
> -
> - must pass through A. Naively computer 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

Very minor nitpick: double-space after full stop.

[Conor McCarthy (＠cmccarthy)]

Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/ir.c:
>   * 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, unsigned int block_count)
>  {
> - size_t dominates_size;
> -
> - if (!align_to_size(block_count, sizeof(*block->dominates) * CHAR_BIT, &dominates_size))

Or something like:

`if (SIZE_MAX / sizeof(*block->dominates) / CHAR_BIT < block_count)`

And then just use the existing `align()`.