[PATCH vkd3d v2 1/3] vkd3d-shader/hlsl: Handle branches in copy propagation.
Signed-off-by: Giovanni Mascellani <gmascellani(a)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
Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- v2: No changes. Technically this was already signed off by Matteo, but since everything around has changed, maybe he wants to have another check any way. --- libs/vkd3d-shader/hlsl_codegen.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 1c334f88..787191d2 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -568,6 +568,21 @@ static bool copy_propagation_process_if(struct hlsl_ctx *ctx, struct hlsl_ir_if return progress; } +static bool copy_propagation_process_loop(struct hlsl_ctx *ctx, struct hlsl_ir_loop *loop, + struct copy_propagation_state *state) +{ + struct copy_propagation_state inner_state; + bool progress = false; + + copy_propagation_invalidate_from_block(ctx, state, &loop->body); + + copy_propagation_state_init(ctx, &inner_state, state); + progress |= copy_propagation_transform_block(ctx, &loop->body, &inner_state); + copy_propagation_state_destroy(&inner_state); + + return progress; +} + static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block, struct copy_propagation_state *state) { @@ -591,8 +606,8 @@ static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_b break; case HLSL_IR_LOOP: - FIXME("Copy propagation doesn't support loops yet, leaving.\n"); - return progress; + progress |= copy_propagation_process_loop(ctx, hlsl_ir_loop(instr), state); + break; default: break; -- 2.34.1
Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- v2: Fixed for the new copy propagation architecture. --- libs/vkd3d-shader/hlsl_codegen.c | 75 +++++++++++++++++++++++++++----- 1 file changed, 65 insertions(+), 10 deletions(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 787191d2..76f88bc2 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -405,6 +405,52 @@ static void copy_propagation_set_value(struct copy_propagation_var_def *var_def, } } +static struct hlsl_ir_node *copy_propagation_compute_constant(struct hlsl_ctx *ctx, struct copy_propagation_state *state, + struct hlsl_ir_var *var, unsigned int offset, unsigned int count, + const struct vkd3d_shader_location *loc) +{ + enum hlsl_base_type type = HLSL_TYPE_VOID; + struct hlsl_ir_constant *constant = NULL; + struct hlsl_ir_node *store_nodes[4]; + unsigned store_components[4]; + unsigned int i; + + assert(offset + count <= var->data_type->reg_size); + + for (i = 0; i < count; ++i) + { + struct copy_propagation_value *value = copy_propagation_get_value(state, var, offset + i); + struct hlsl_ir_node *store_node; + enum hlsl_base_type store_type; + + if (!value || value->state != VALUE_STATE_STATICALLY_WRITTEN) + return NULL; + + store_node = value->node; + if (!store_node || store_node->type != HLSL_IR_CONSTANT) + return NULL; + + store_type = store_node->data_type->base_type; + + if (type == HLSL_TYPE_VOID) + type = store_type; + else if (type != store_type) + return NULL; + + store_nodes[i] = store_node; + store_components[i] = value->component; + } + + if (!(constant = hlsl_new_uint_constant(ctx, 0, *loc))) + return NULL; + constant->node.data_type = hlsl_get_vector_type(ctx, type, count); + + for (i = 0; i < count; ++i) + constant->value[i] = hlsl_ir_constant(store_nodes[i])->value[store_components[i]]; + + return &constant->node; +} + 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) { @@ -448,19 +494,28 @@ static bool copy_propagation_analyze_load(struct hlsl_ctx *ctx, struct hlsl_ir_l if (!hlsl_offset_from_deref(src, &offset)) return false; - if (!(new_node = copy_propagation_compute_replacement(state, var, offset, type->dimx, &swizzle))) + if ((new_node = copy_propagation_compute_constant(ctx, state, var, offset, type->dimx, &load->node.loc))) { - TRACE("No single source for propagating load from %s[%u-%u].\n", var->name, offset, offset + type->dimx); - return false; + TRACE("Load from %s[%d-%d] reconstructed as constant value.\n", + var->name, offset, offset + type->dimx); + list_add_before(&node->entry, &new_node->entry); + replace_node(node, new_node); + return true; } - TRACE("Load from %s[%u-%u] propagated as instruction %p%s.\n", - var->name, offset, offset + type->dimx, new_node, debug_hlsl_swizzle(swizzle, 4)); - if (!(swizzle_node = hlsl_new_swizzle(ctx, swizzle, type->dimx, new_node, &node->loc))) - return false; - list_add_before(&node->entry, &swizzle_node->node.entry); - replace_node(node, &swizzle_node->node); - return true; + if ((new_node = copy_propagation_compute_replacement(state, var, offset, type->dimx, &swizzle))) + { + TRACE("Load from %s[%u-%u] propagated as instruction %p%s.\n", + var->name, offset, offset + type->dimx, new_node, debug_hlsl_swizzle(swizzle, 4)); + if (!(swizzle_node = hlsl_new_swizzle(ctx, swizzle, type->dimx, new_node, &node->loc))) + return false; + list_add_before(&node->entry, &swizzle_node->node.entry); + replace_node(node, &swizzle_node->node); + return true; + } + + TRACE("No single source for propagating load from %s[%u-%u].\n", var->name, offset, offset + type->dimx); + return false; } static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_store *store, -- 2.34.1
On 1/20/22 05:23, Giovanni Mascellani wrote:
@@ -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)
Why not just check for VALUE_STATE_STATICALLY_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]));
This memset() doesn't seem necessary anymore.
+ 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);
Note that you don't need this memset() anymore either.
+ + 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_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; + } + } +}
As an alternative, you could iterate over the whole state, marking the parent as "dynamically written" wherever the child state is written.
Hi, Il 21/01/22 03:19, Zebediah Figura (she/her) ha scritto:
- 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)
Why not just check for VALUE_STATE_STATICALLY_WRITTEN?
It's not the same thing. If the value has been dynamically written I have to stop searching, it's the answer the caller needs to get. Otherwise I risk returning an outer statically written value enabling an invalid optimization.
+ for (i = 0; i < 4; ++i) + { + if (writemask & (1u << i)) + { + memset(&var_def->values[offset + i], 0, sizeof(var_def->values[offset + i]));
This memset() doesn't seem necessary anymore.
I agree it is not, given that when the value is not statically written, node and component should not even be checked. I thought it would be cleaner to reset them to zero anyway (e.g., it might help debugging in the future), but if it bothers you I can remove it.
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);
Note that you don't need this memset() anymore either.
Same as above.
As an alternative, you could iterate over the whole state, marking the parent as "dynamically written" wherever the child state is written.
That's what I did in my first implementation, and from some point of view it would be nicer, but it doesn't play well with loops, because there you have to know what you are going to invalidate before iterating into the loop itself. Having two different ways to invalidate the outer state looks like a useless amount of code to maintain, so I think it is better to just do this way (copy_propagation_invalidate_from_block()). Giovanni.
On 1/21/22 03:15, Giovanni Mascellani wrote:
Hi,
Il 21/01/22 03:19, Zebediah Figura (she/her) ha scritto:
- 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)
Why not just check for VALUE_STATE_STATICALLY_WRITTEN?
It's not the same thing. If the value has been dynamically written I have to stop searching, it's the answer the caller needs to get. Otherwise I risk returning an outer statically written value enabling an invalid optimization.
Ah, right, I can't read... I would suggest folding the subsequent check for VALUE_STATE_STATICALLY_WRITTEN into this function, though.
+ for (i = 0; i < 4; ++i) + { + if (writemask & (1u << i)) + { + memset(&var_def->values[offset + i], 0, sizeof(var_def->values[offset + i]));
This memset() doesn't seem necessary anymore.
I agree it is not, given that when the value is not statically written, node and component should not even be checked. I thought it would be cleaner to reset them to zero anyway (e.g., it might help debugging in the future), but if it bothers you I can remove it.
I don't feel strongly about it, but we don't tend to bother zeroing invalidated pointers as a rule.
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);
Note that you don't need this memset() anymore either.
Same as above.
As an alternative, you could iterate over the whole state, marking the parent as "dynamically written" wherever the child state is written.
That's what I did in my first implementation, and from some point of view it would be nicer, but it doesn't play well with loops, because there you have to know what you are going to invalidate before iterating into the loop itself. Having two different ways to invalidate the outer state looks like a useless amount of code to maintain, so I think it is better to just do this way (copy_propagation_invalidate_from_block()).
Ah, right. I probably knew that already but forgot. In that case can you please add a comment so I don't forget again?
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(a)codeweavers.com> wrote:
Signed-off-by: Giovanni Mascellani <gmascellani(a)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
participants (3)
-
Francisco Casas -
Giovanni Mascellani -
Zebediah Figura (she/her)