[PATCH vkd3d v3 5/6] vkd3d-shader/hlsl: Handle conditionals in copy propagation.
Giovanni Mascellani
gmascellani at codeweavers.com
Thu Nov 11 05:06:12 CST 2021
Signed-off-by: Giovanni Mascellani <gmascellani at codeweavers.com>
---
libs/vkd3d-shader/hlsl_codegen.c | 157 +++++++++++++++++++++++++++++--
1 file changed, 149 insertions(+), 8 deletions(-)
diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c
index 7a104b45..fec6b87d 100644
--- a/libs/vkd3d-shader/hlsl_codegen.c
+++ b/libs/vkd3d-shader/hlsl_codegen.c
@@ -255,7 +255,18 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new)
* updated. When scanning through a load, it is checked if all the
* registers involved in the load come from a single node. In such
* case, the store can be replaced with a swizzle based on that
- * node. */
+ * node.
+ *
+ * All of the above works when we disregard control flow. With control
+ * flow it becames slightly more complicated: instead of a single map
+ * we keep a stack of them, pushing a new entry each time we enter an
+ * embedded block, and popping the entry when leaving the block.
+ *
+ * When entering a conditional block, both branches ("then" and
+ * "else") can inherit the variable state available just before the
+ * conditional block. After the conditional block, all variables that
+ * might have been written in either branch must be invalidated,
+ * because we don't know which branch has executed. */
struct copy_propagation_value
{
@@ -272,7 +283,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)
@@ -298,7 +311,7 @@ static void copy_propagation_variable_destroy(struct rb_entry *entry, void *cont
static struct copy_propagation_variable *copy_propagation_get_variable(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);
if (entry)
return RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry);
@@ -309,7 +322,7 @@ static struct copy_propagation_variable *copy_propagation_get_variable(struct co
static struct copy_propagation_variable *copy_propagation_create_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;
@@ -328,7 +341,7 @@ static struct copy_propagation_variable *copy_propagation_create_variable(struct
return NULL;
}
- res = rb_put(&state->variables, var, &variable->entry);
+ res = rb_put(&state->variables[state->depth], var, &variable->entry);
assert(!res);
return variable;
@@ -356,6 +369,99 @@ 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)
+ {
+ switch (instr->type)
+ {
+ case 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;
+ unsigned int offset;
+
+ variable = copy_propagation_get_variable(state, var);
+ if (!variable)
+ continue;
+
+ if (hlsl_offset_from_deref(lhs, &offset))
+ copy_propagation_set_value(variable, offset, store->writemask, NULL);
+ else
+ copy_propagation_invalidate_whole_variable(variable);
+
+ break;
+ }
+
+ case HLSL_IR_IF:
+ {
+ struct hlsl_ir_if *iff = hlsl_ir_if(instr);
+
+ copy_propagation_invalidate_from_block(ctx, state, &iff->then_instrs);
+ copy_propagation_invalidate_from_block(ctx, state, &iff->else_instrs);
+
+ break;
+ }
+
+ case HLSL_IR_LOOP:
+ {
+ struct hlsl_ir_loop *loop = hlsl_ir_loop(instr);
+
+ copy_propagation_invalidate_from_block(ctx, state, &loop->body);
+
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+}
+
+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_create_variable(ctx, state, var->var);
+
+ if (!new_var)
+ return false;
+
+ memcpy(new_var->values, var->values, sizeof(*var->values) * var->var->data_type->reg_size);
+ }
+
+ return true;
+}
+
static struct hlsl_ir_node *copy_propagation_find_replacement(struct copy_propagation_variable *variable,
unsigned int offset, unsigned int count, unsigned int *swizzle)
{
@@ -434,6 +540,34 @@ static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_s
copy_propagation_invalidate_whole_variable(variable);
}
+static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block,
+ struct copy_propagation_state *state);
+
+static bool copy_propagation_process_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_transform_block(ctx, &iff->then_instrs, state);
+
+ copy_propagation_pop(state);
+ if (!copy_propagation_duplicate(ctx, state))
+ goto end;
+
+ progress |= copy_propagation_transform_block(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_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block,
struct copy_propagation_state *state)
{
@@ -453,7 +587,7 @@ static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_b
break;
case HLSL_IR_IF:
- FIXME("Copy propagation doesn't support conditionals yet, leaving.\n");
+ progress |= copy_propagation_process_if(ctx, hlsl_ir_if(instr), state);
return progress;
case HLSL_IR_LOOP:
@@ -473,11 +607,18 @@ static bool copy_propagation_execute(struct hlsl_ctx *ctx, struct hlsl_block *bl
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_transform_block(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
More information about the wine-devel
mailing list