Hi,
Just in case, this no longer applies after 62bcdcda762d87a63f23a29da281637c71608460. But I agree with this somewhat "functional" approach to the problem, it is very readable and hopefully not too expensive.
Francisco.
January 20, 2022 8:42 AM, "Giovanni Mascellani" gmascellani@codeweavers.com wrote:
Signed-off-by: Giovanni Mascellani gmascellani@codeweavers.com
v2 (well, I don't remember which version number we were, but it was over a month ago, so I'll restart over):
- differentiate between a value that was not written in a scope and a value
that was dynamically written (i.e., we don't know statically which node the written value came from);
Maybe "statically" and "dynamically" are not as understandable as possible, I'm open to suggestions.
libs/vkd3d-shader/hlsl_codegen.c | 176 +++++++++++++++++++++++++++---- 1 file changed, 154 insertions(+), 22 deletions(-)
diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 75716bdf..1c334f88 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -274,8 +274,16 @@ static bool lower_broadcasts(struct hlsl_ctx *ctx, struct hlsl_ir_node *instr, v return false; }
+enum copy_propagation_value_state +{
- VALUE_STATE_NOT_WRITTEN = 0,
- VALUE_STATE_STATICALLY_WRITTEN,
- VALUE_STATE_DYNAMICALLY_WRITTEN,
+};
struct copy_propagation_value {
- enum copy_propagation_value_state state;
struct hlsl_ir_node *node; unsigned int component; }; @@ -290,6 +298,7 @@ struct copy_propagation_var_def struct copy_propagation_state { struct rb_tree var_defs;
- struct copy_propagation_state *parent;
};
static int copy_propagation_var_def_compare(const void *key, const struct rb_entry *entry) @@ -307,15 +316,23 @@ static void copy_propagation_var_def_destroy(struct rb_entry *entry, void *conte vkd3d_free(var_def); }
-static struct copy_propagation_var_def *copy_propagation_get_var_def(struct copy_propagation_state *state,
- struct hlsl_ir_var *var)
+static struct copy_propagation_value *copy_propagation_get_value(struct copy_propagation_state *state,
- struct hlsl_ir_var *var, unsigned component)
{
- struct rb_entry *entry = rb_get(&state->var_defs, var);
- for (; state; state = state->parent)
- {
- struct rb_entry *entry = rb_get(&state->var_defs, var);
- if (entry)
- {
- struct copy_propagation_var_def *var_def = RB_ENTRY_VALUE(entry, struct copy_propagation_var_def,
entry);
- assert(component < var_def->var->data_type->reg_size);
- if (entry)
- return RB_ENTRY_VALUE(entry, struct copy_propagation_var_def, entry);
- else
- return NULL;
- if (var_def->values[component].state != VALUE_STATE_NOT_WRITTEN)
- return &var_def->values[component];
- }
- }
- return NULL;
}
static struct copy_propagation_var_def *copy_propagation_create_var_def(struct hlsl_ctx *ctx, @@ -339,10 +356,35 @@ static struct copy_propagation_var_def *copy_propagation_create_var_def(struct h return var_def; }
+static void copy_propagation_invalidate_variable(struct copy_propagation_var_def *var_def,
- unsigned offset, unsigned char writemask)
+{
- unsigned i;
- TRACE("Invalidate variable %s[%u]%s.\n", var_def->var->name, offset,
debug_hlsl_writemask(writemask));
- for (i = 0; i < 4; ++i)
- {
- if (writemask & (1u << i))
- {
- memset(&var_def->values[offset + i], 0, sizeof(var_def->values[offset + i]));
- var_def->values[offset + i].state = VALUE_STATE_DYNAMICALLY_WRITTEN;
- }
- }
+}
static void copy_propagation_invalidate_whole_variable(struct copy_propagation_var_def *var_def) {
- unsigned i;
TRACE("Invalidate variable %s.\n", var_def->var->name);
memset(var_def->values, 0, sizeof(*var_def->values) * var_def->var->data_type->reg_size);
- for (i = 0; i < var_def->var->data_type->reg_size; ++i)
- {
- var_def->values[i].state = VALUE_STATE_DYNAMICALLY_WRITTEN;
- }
}
static void copy_propagation_set_value(struct copy_propagation_var_def *var_def, unsigned int offset, @@ -356,29 +398,35 @@ static void copy_propagation_set_value(struct copy_propagation_var_def *var_def, { TRACE("Variable %s[%u] is written by instruction %p%s.\n", var_def->var->name, offset + i, node, debug_hlsl_writemask(1u << i));
- var_def->values[offset + i].state = VALUE_STATE_STATICALLY_WRITTEN;
var_def->values[offset + i].node = node; var_def->values[offset + i].component = j++; } } }
-static struct hlsl_ir_node *copy_propagation_compute_replacement(struct copy_propagation_var_def *var_def,
- unsigned int offset, unsigned int count, unsigned int *swizzle)
+static struct hlsl_ir_node *copy_propagation_compute_replacement(struct copy_propagation_state *state,
- struct hlsl_ir_var *var, unsigned int offset, unsigned int count, unsigned int *swizzle)
{ struct hlsl_ir_node *node = NULL; unsigned int i;
- assert(offset + count <= var_def->var->data_type->reg_size);
- assert(offset + count <= var->data_type->reg_size);
*swizzle = 0;
for (i = 0; i < count; ++i) {
- struct copy_propagation_value *value = copy_propagation_get_value(state, var, offset + i);
- if (!value || value->state != VALUE_STATE_STATICALLY_WRITTEN)
- return NULL;
if (!node)
- node = var_def->values[offset + i].node;
- else if (node != var_def->values[offset + i].node)
- node = value->node;
- else if (node != value->node)
return NULL;
- *swizzle |= var_def->values[offset + i].component << i * 2;
- *swizzle |= value->component << i * 2;
}
return node; @@ -388,7 +436,6 @@ static bool copy_propagation_analyze_load(struct hlsl_ctx *ctx, struct hlsl_ir_l struct copy_propagation_state *state) { struct hlsl_ir_node *node = &load->node, *new_node;
- struct copy_propagation_var_def *var_def;
struct hlsl_type *type = node->data_type; struct hlsl_ir_swizzle *swizzle_node; struct hlsl_deref *src = &load->src; @@ -401,10 +448,7 @@ static bool copy_propagation_analyze_load(struct hlsl_ctx *ctx, struct hlsl_ir_l if (!hlsl_offset_from_deref(src, &offset)) return false;
- if (!(var_def = copy_propagation_get_var_def(state, var)))
- return false;
- if (!(new_node = copy_propagation_compute_replacement(var_def, offset, type->dimx, &swizzle)))
- if (!(new_node = copy_propagation_compute_replacement(state, var, offset, type->dimx, &swizzle)))
{ TRACE("No single source for propagating load from %s[%u-%u].\n", var->name, offset, offset + type->dimx); return false; @@ -436,6 +480,94 @@ static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_s copy_propagation_invalidate_whole_variable(var_def); }
+static void copy_propagation_state_init(struct hlsl_ctx *ctx, struct copy_propagation_state *state,
- struct copy_propagation_state *parent)
+{
- rb_init(&state->var_defs, copy_propagation_var_def_compare);
- state->parent = parent;
+}
+static void copy_propagation_state_destroy(struct copy_propagation_state *state) +{
- rb_destroy(&state->var_defs, copy_propagation_var_def_destroy, NULL);
+}
+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_var_def *var_def;
- struct hlsl_deref *lhs = &store->lhs;
- struct hlsl_ir_var *var = lhs->var;
- unsigned int offset;
- if (!(var_def = copy_propagation_create_var_def(ctx, state, var)))
- continue;
- if (hlsl_offset_from_deref(lhs, &offset))
- copy_propagation_invalidate_variable(var_def, offset, store->writemask);
- else
- copy_propagation_invalidate_whole_variable(var_def);
- 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 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)
+{
- struct copy_propagation_state inner_state;
- bool progress = false;
- copy_propagation_state_init(ctx, &inner_state, state);
- progress |= copy_propagation_transform_block(ctx, &iff->then_instrs, &inner_state);
- copy_propagation_state_destroy(&inner_state);
- copy_propagation_state_init(ctx, &inner_state, state);
- progress |= copy_propagation_transform_block(ctx, &iff->else_instrs, &inner_state);
- copy_propagation_state_destroy(&inner_state);
- 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) { @@ -455,8 +587,8 @@ 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");
- return progress;
- progress |= copy_propagation_process_if(ctx, hlsl_ir_if(instr), state);
- break;
case HLSL_IR_LOOP: FIXME("Copy propagation doesn't support loops yet, leaving.\n"); @@ -475,11 +607,11 @@ static bool copy_propagation_execute(struct hlsl_ctx *ctx, struct hlsl_block *bl struct copy_propagation_state state; bool progress;
- rb_init(&state.var_defs, copy_propagation_var_def_compare);
- copy_propagation_state_init(ctx, &state, NULL);
progress = copy_propagation_transform_block(ctx, block, &state);
- rb_destroy(&state.var_defs, copy_propagation_var_def_destroy, NULL);
- copy_propagation_state_destroy(&state);
return progress; } -- 2.34.1