[PATCH 3/4] vkd3d-shader/ir: Compute dominated blocks.

[Giovanni Mascellani]

From: Giovanni Mascellani

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

diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 86b43317b..c1cc8ddfc 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3009,6 +3009,52 @@ fail:
     return VKD3D_ERROR_OUT_OF_MEMORY;
 }

+struct vkd3d_bitvector
+{
+    uint32_t *elements;
+    size_t size;
+};
+
+static enum vkd3d_result vkd3d_bitvector_init(struct vkd3d_bitvector *vector, size_t size, bool set)
+{
+    const size_t element_bit_size = sizeof(*vector->elements) * CHAR_BIT;
+    const size_t element_count = align(size, element_bit_size) / element_bit_size;
+
+    memset(vector, 0, sizeof(*vector));
+
+    if (!(vector->elements = vkd3d_calloc(element_count, sizeof(*vector->elements))))
+        return VKD3D_ERROR_OUT_OF_MEMORY;
+
+    vector->size = size;
+
+    if (set)
+        memset(vector->elements, ~0u, element_count * sizeof(*vector->elements));
+
+    return VKD3D_OK;
+}
+
+static void vkd3d_bitvector_cleanup(struct vkd3d_bitvector *vector)
+{
+    vkd3d_free(vector->elements);
+}
+
+static bool vkd3d_bitvector_get(struct vkd3d_bitvector *vector, size_t pos)
+{
+    const size_t element_size = sizeof(*vector->elements) * CHAR_BIT;
+
+    return !!(vector->elements[pos / element_size] & (1u << (pos % element_size)));
+}
+
+static void vkd3d_bitvector_set(struct vkd3d_bitvector *vector, size_t pos, bool value)
+{
+    const size_t element_size = sizeof(*vector->elements) * CHAR_BIT;
+
+    if (value)
+        vector->elements[pos / element_size] |= 1u << (pos % element_size);
+    else
+        vector->elements[pos / element_size] &= ~(1u << (pos % element_size));
+}
+
 struct vsir_block_list
 {
     struct vsir_block **blocks;
@@ -3053,21 +3099,26 @@ struct vsir_block
      * that the block is empty. */
     struct vkd3d_shader_instruction *begin, *end;
     struct vsir_block_list predecessors, successors;
+    struct vkd3d_bitvector 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)
 {
     assert(label);
     memset(block, 0, sizeof(*block));
     block->label = label;
     vsir_block_list_init(&block->predecessors);
     vsir_block_list_init(&block->successors);
+    return vkd3d_bitvector_init(&block->dominates, block_count, true);
 }

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_bitvector_cleanup(&block->dominates);
 }

struct vsir_cfg
@@ -3174,7 +3225,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 +3290,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(struct vkd3d_bitvector *vector, struct vsir_block *current,
+        struct vsir_block *reference)
+{
+    size_t i;
+
+    assert(current->label != 0);
+
+    if (current == reference)
+        return;
+
+    if (!vkd3d_bitvector_get(vector, current->label - 1))
+        return;
+
+    vkd3d_bitvector_set(vector, current->label - 1, false);
+
+    for (i = 0; i < current->successors.count; ++i)
+        vsir_cfg_compute_dominators_recurse(vector, 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 +3355,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);