[PATCH vkd3d 3/5] vkd3d-shader/hlsl: Handle conditionals in copy propagation.

[Giovanni Mascellani]

Signed-off-by: Giovanni Mascellani <gmascellani at codeweavers.com>
---
 libs/vkd3d-shader/hlsl_codegen.c | 138 +++++++++++++++++++++++++++----
 1 file changed, 123 insertions(+), 15 deletions(-)

diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c
index 8db8bfc9..78bcd079 100644
--- a/libs/vkd3d-shader/hlsl_codegen.c
+++ b/libs/vkd3d-shader/hlsl_codegen.c
@@ -239,15 +239,17 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new)
 
 /* struct copy_propagation_state represents the accumulated knowledge
  * of the copy propagation pass while it scans through the code. Field
- * "variables" is a tree whose elements have type struct
- * copy_propagation_varible, and represent each of the variables the
- * pass has already encountered (except those with special semantics,
- * which are ignored). For each variable, the array "values" (whose
- * length is the register size of the variable) represent which node
- * and which index inside that node (i.e., which of the at most four
- * entries of a vector) provided that value last time. Field "node"
- * can be NULL, meaning that the pass was not able to statically
- * determine the node.
+ * "variables" is an stack of trees: each stack entry represents an
+ * embedded block (of type either HLSL_IR_IF or HLSL_IR_TREE); the
+ * elements of the tree have type struct copy_propagation_variable,
+ * and represent each of the variables the pass has already
+ * encountered (except those with special semantics, which are
+ * ignored). For each variable, the array "values" (whose length is
+ * the register size of the variable) represent which node and which
+ * index inside that node (i.e., which of the at most four entries of
+ * a vector) provided that value last time. Field "node" can be NULL,
+ * meaning that the pass was not able to statically determine the
+ * node.
  */
 
 struct copy_propagation_value
@@ -265,7 +267,9 @@ struct copy_propagation_variable
 
 struct copy_propagation_state
 {
-    struct rb_tree variables;
+    struct rb_tree *variables;
+    unsigned int depth;
+    unsigned int capacity;
 };
 
 static int copy_propagation_variable_compare(const void *key, const struct rb_entry *entry)
@@ -291,7 +295,7 @@ static void copy_propagation_variable_destroy(struct rb_entry *entry, void *cont
 static struct copy_propagation_variable *copy_propagation_get_variable(struct hlsl_ctx *ctx,
         struct copy_propagation_state *state, struct hlsl_ir_var *var)
 {
-    struct rb_entry *entry = rb_get(&state->variables, var);
+    struct rb_entry *entry = rb_get(&state->variables[state->depth], var);
     struct copy_propagation_variable *variable;
     int res;
 
@@ -310,7 +314,7 @@ static struct copy_propagation_variable *copy_propagation_get_variable(struct hl
         return NULL;
     }
 
-    res = rb_put(&state->variables, var, &variable->entry);
+    res = rb_put(&state->variables[state->depth], var, &variable->entry);
     assert(!res);
 
     return variable;
@@ -342,6 +346,71 @@ static void copy_propagation_set_value(struct copy_propagation_variable *variabl
     }
 }
 
+static void copy_propagation_invalidate_from_block(struct hlsl_ctx *ctx, struct copy_propagation_state *state,
+        struct hlsl_block *block)
+{
+    struct hlsl_ir_node *instr;
+
+    LIST_FOR_EACH_ENTRY(instr, &block->instrs, struct hlsl_ir_node, entry)
+    {
+        if (instr->type == HLSL_IR_STORE)
+        {
+            struct hlsl_ir_store *store = hlsl_ir_store(instr);
+            struct copy_propagation_variable *variable;
+            struct hlsl_deref *lhs = &store->lhs;
+            struct hlsl_ir_var *var = lhs->var;
+
+            if (var->is_input_semantic || var->is_output_semantic || var->is_uniform)
+                continue;
+
+            variable = copy_propagation_get_variable(ctx, state, var);
+            if (!variable)
+                continue;
+
+            copy_propagation_set_value(variable, hlsl_offset_from_deref(lhs), store->writemask, NULL);
+        }
+    }
+}
+
+static void copy_propagation_pop(struct copy_propagation_state *state)
+{
+    assert(state->depth > 0);
+    rb_destroy(&state->variables[state->depth], copy_propagation_variable_destroy, NULL);
+    --state->depth;
+}
+
+static bool copy_propagation_duplicate(struct hlsl_ctx *ctx, struct copy_propagation_state *state)
+{
+    struct copy_propagation_variable *var;
+
+    if (state->depth + 1 == state->capacity)
+    {
+        unsigned int new_capacity = 2 * state->capacity;
+        struct rb_tree *new_vars;
+
+        new_vars = hlsl_realloc(ctx, state->variables, sizeof(*state->variables) * new_capacity);
+        if (!new_vars)
+            return false;
+        state->capacity = new_capacity;
+        state->variables = new_vars;
+    }
+    ++state->depth;
+
+    rb_init(&state->variables[state->depth], copy_propagation_variable_compare);
+
+    RB_FOR_EACH_ENTRY(var, &state->variables[state->depth - 1], struct copy_propagation_variable, entry)
+    {
+        struct copy_propagation_variable *new_var = copy_propagation_get_variable(ctx, state, var->var);
+
+        if (!new_var)
+            continue;
+
+        memcpy(new_var->values, var->values, sizeof(*var->values) * var->var->data_type->reg_size);
+    }
+
+    return true;
+}
+
 /* Check if locations [offset, offset+count) in variable were all
  * written from the same node. If so return the node the corresponding
  * indices, otherwise return NULL (and undefined indices). */
@@ -436,6 +505,38 @@ static bool copy_propagation_store(struct hlsl_ctx *ctx, struct hlsl_ir_store *s
     return false;
 }
 
+static bool copy_propagation_recursive(struct hlsl_ctx *ctx, struct hlsl_block *block,
+        struct copy_propagation_state *state);
+
+/* Both branches can inherit the variable state available when
+ * entering the "if". After the "if", all variables that might have
+ * been written in either branch must be invalidated, because we don't
+ * know which branch has executed. */
+static bool copy_propagation_if(struct hlsl_ctx *ctx, struct hlsl_ir_if *iff,
+        struct copy_propagation_state *state)
+{
+    bool progress = false;
+
+    if (!copy_propagation_duplicate(ctx, state))
+        goto end;
+
+    progress |= copy_propagation_recursive(ctx, &iff->then_instrs, state);
+
+    copy_propagation_pop(state);
+    if (!copy_propagation_duplicate(ctx, state))
+        goto end;
+
+    progress |= copy_propagation_recursive(ctx, &iff->else_instrs, state);
+
+    copy_propagation_pop(state);
+
+end:
+    copy_propagation_invalidate_from_block(ctx, state, &iff->then_instrs);
+    copy_propagation_invalidate_from_block(ctx, state, &iff->else_instrs);
+
+    return progress;
+}
+
 static bool copy_propagation_recursive(struct hlsl_ctx *ctx, struct hlsl_block *block,
         struct copy_propagation_state *state)
 {
@@ -455,7 +556,7 @@ static bool copy_propagation_recursive(struct hlsl_ctx *ctx, struct hlsl_block *
                 break;
 
             case HLSL_IR_IF:
-                FIXME("Copy propagation doesn't support conditionals yet, leaving.\n");
+                progress |= copy_propagation_if(ctx, hlsl_ir_if(instr), state);
                 return progress;
 
             case HLSL_IR_LOOP:
@@ -475,11 +576,18 @@ static bool copy_propagation_pass(struct hlsl_ctx *ctx, struct hlsl_block *block
     struct copy_propagation_state state;
     bool progress;
 
-    rb_init(&state.variables, copy_propagation_variable_compare);
+    state.depth = 0;
+    state.capacity = 1;
+    state.variables = hlsl_alloc(ctx, sizeof(*state.variables) * state.capacity);
+    if (!state.variables)
+        return false;
+    rb_init(&state.variables[state.depth], copy_propagation_variable_compare);
 
     progress = copy_propagation_recursive(ctx, block, &state);
 
-    rb_destroy(&state.variables, copy_propagation_variable_destroy, NULL);
+    assert(state.depth == 0);
+    rb_destroy(&state.variables[state.depth], copy_propagation_variable_destroy, NULL);
+    vkd3d_free(state.variables);
 
     return progress;
 }
-- 
2.33.1