[PATCH vkd3d v2 1/3] vkd3d-shader/hlsl: Handle branches in copy propagation.

[Francisco Casas]

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 at codeweavers.com> wrote:

> Signed-off-by: Giovanni Mascellani <gmascellani at 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