[PATCH v4 0/3] MR704: vkd3d-shader/ir: Introduce a better CFG structurizer, part 5.
~~This applies on top of !698, the last three commits belong here.~~ Here we reconstruct an internal representation of a structured program corresponding to the input CFG. The representation can be directly emitted (which will be the following MR) or other passes can be run on it to simplify the loop structure. -- v4: vkd3d-shader/ir: Dump the reconstructed structured program. vkd3d-shader/ir: Add jumps to the structured programs. vkd3d-shader/ir: Reconstruct a structured program. https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> For simplicity jumps are not currently processed. --- libs/vkd3d-shader/ir.c | 141 +++++++++++++++++++++++ libs/vkd3d-shader/vkd3d_shader_main.c | 12 +- libs/vkd3d-shader/vkd3d_shader_private.h | 1 + 3 files changed, 152 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 0dd31af91..034d56f3b 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3142,6 +3142,73 @@ static bool vsir_block_list_search(struct vsir_block_list *list, struct vsir_blo return !!bsearch(&block, list->blocks, list->count, sizeof(*list->blocks), block_compare); } +struct vsir_cfg_structure_list +{ + struct vsir_cfg_structure *structures; + size_t count, capacity; + unsigned int end; +}; + +struct vsir_cfg_structure +{ + enum vsir_cfg_structure_type + { + /* Execute a block of the original VSIR program. */ + STRUCTURE_TYPE_BLOCK, + /* Execute a loop, which is identified by an index. */ + STRUCTURE_TYPE_LOOP, + } type; + union + { + struct vsir_block *block; + struct + { + struct vsir_cfg_structure_list body; + unsigned idx; + } loop; + } u; +}; + +static void vsir_cfg_structure_init(struct vsir_cfg_structure *structure, enum vsir_cfg_structure_type type); +static void vsir_cfg_structure_cleanup(struct vsir_cfg_structure *structure); + +static void vsir_cfg_structure_list_cleanup(struct vsir_cfg_structure_list *list) +{ + unsigned int i; + + for (i = 0; i < list->count; ++i) + vsir_cfg_structure_cleanup(&list->structures[i]); + vkd3d_free(list->structures); +} + +static struct vsir_cfg_structure *vsir_cfg_structure_list_append(struct vsir_cfg_structure_list *list, + enum vsir_cfg_structure_type type) +{ + struct vsir_cfg_structure *ret; + + if (!vkd3d_array_reserve((void **)&list->structures, &list->capacity, list->count + 1, + sizeof(*list->structures))) + return NULL; + + ret = &list->structures[list->count++]; + + vsir_cfg_structure_init(ret, type); + + return ret; +} + +static void vsir_cfg_structure_init(struct vsir_cfg_structure *structure, enum vsir_cfg_structure_type type) +{ + memset(structure, 0, sizeof(*structure)); + structure->type = type; +} + +static void vsir_cfg_structure_cleanup(struct vsir_cfg_structure *structure) +{ + if (structure->type == STRUCTURE_TYPE_LOOP) + vsir_cfg_structure_list_cleanup(&structure->u.loop.body); +} + struct vsir_cfg { struct vkd3d_shader_message_context *message_context; @@ -3187,6 +3254,8 @@ struct vsir_cfg bool synthetic; } *loop_intervals; size_t loop_interval_count, loop_interval_capacity; + + struct vsir_cfg_structure_list structured_program; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3201,6 +3270,8 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) vsir_block_list_cleanup(&cfg->order); + vsir_cfg_structure_list_cleanup(&cfg->structured_program); + vkd3d_free(cfg->blocks); vkd3d_free(cfg->loops); vkd3d_free(cfg->loops_by_header); @@ -3916,6 +3987,70 @@ static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_ return VKD3D_OK; } +static enum vkd3d_result vsir_cfg_build_structured_program(struct vsir_cfg *cfg) +{ + unsigned int i, stack_depth = 1, open_interval_idx = 0; + struct vsir_cfg_structure_list **stack = NULL; + + /* It's enough to allocate up to the maximum interval stacking + * depth (plus one for the full program), but this is simpler. */ + if (!(stack = vkd3d_calloc(cfg->loop_interval_count + 1, sizeof(*stack)))) + goto fail; + cfg->structured_program.end = cfg->order.count; + stack[0] = &cfg->structured_program; + + for (i = 0; i < cfg->order.count; ++i) + { + struct vsir_cfg_structure *structure; + + assert(stack_depth > 0); + + /* Open loop intervals. */ + while (open_interval_idx < cfg->loop_interval_count) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[open_interval_idx]; + + if (interval->begin != i) + break; + + if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_LOOP))) + goto fail; + structure->u.loop.idx = open_interval_idx++; + + structure->u.loop.body.end = interval->end; + stack[stack_depth++] = &structure->u.loop.body; + } + + /* Execute the block. */ + if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_BLOCK))) + goto fail; + structure->u.block = cfg->order.blocks[i]; + + /* TODO: process the jump after the block. */ + + /* Close loop intervals. */ + while (stack_depth > 0) + { + if (stack[stack_depth - 1]->end != i + 1) + break; + + --stack_depth; + } + } + + assert(stack_depth == 0); + assert(open_interval_idx == cfg->loop_interval_count); + + vkd3d_free(stack); + + return VKD3D_OK; + +fail: + vkd3d_free(stack); + + return VKD3D_ERROR_OUT_OF_MEMORY; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3961,6 +4096,12 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, return result; } + if ((result = vsir_cfg_build_structured_program(&cfg)) < 0) + { + vsir_cfg_cleanup(&cfg); + return result; + } + if ((result = vsir_program_structurise(program)) < 0) { vsir_cfg_cleanup(&cfg); diff --git a/libs/vkd3d-shader/vkd3d_shader_main.c b/libs/vkd3d-shader/vkd3d_shader_main.c index ff361a2bb..120243064 100644 --- a/libs/vkd3d-shader/vkd3d_shader_main.c +++ b/libs/vkd3d-shader/vkd3d_shader_main.c @@ -73,8 +73,16 @@ void vkd3d_string_buffer_cleanup(struct vkd3d_string_buffer *buffer) void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer) { - buffer->buffer[0] = '\0'; - buffer->content_size = 0; + vkd3d_string_buffer_truncate(buffer, 0); +} + +void vkd3d_string_buffer_truncate(struct vkd3d_string_buffer *buffer, size_t size) +{ + if (size < buffer->content_size) + { + buffer->buffer[size] = '\0'; + buffer->content_size = size; + } } static bool vkd3d_string_buffer_resize(struct vkd3d_string_buffer *buffer, int rc) diff --git a/libs/vkd3d-shader/vkd3d_shader_private.h b/libs/vkd3d-shader/vkd3d_shader_private.h index ba018070f..f973bc64d 100644 --- a/libs/vkd3d-shader/vkd3d_shader_private.h +++ b/libs/vkd3d-shader/vkd3d_shader_private.h @@ -1413,6 +1413,7 @@ void vkd3d_string_buffer_init(struct vkd3d_string_buffer *buffer); void vkd3d_string_buffer_cache_cleanup(struct vkd3d_string_buffer_cache *list); void vkd3d_string_buffer_cache_init(struct vkd3d_string_buffer_cache *list); void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer); +void vkd3d_string_buffer_truncate(struct vkd3d_string_buffer *buffer, size_t size); int vkd3d_string_buffer_print_f32(struct vkd3d_string_buffer *buffer, float f); int vkd3d_string_buffer_print_f64(struct vkd3d_string_buffer *buffer, double d); int vkd3d_string_buffer_printf(struct vkd3d_string_buffer *buffer, const char *format, ...) VKD3D_PRINTF_FUNC(2, 3); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 168 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 166 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 034d56f3b..8c74f2b08 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3157,6 +3157,11 @@ struct vsir_cfg_structure STRUCTURE_TYPE_BLOCK, /* Execute a loop, which is identified by an index. */ STRUCTURE_TYPE_LOOP, + /* Execute a `return' or a (possibly) multilevel `break' or + * `continue', targeting a loop by its index. If `condition' + * is non-NULL, then the jump is conditional (this is + * currently not allowed for `return'). */ + STRUCTURE_TYPE_JUMP, } type; union { @@ -3166,6 +3171,21 @@ struct vsir_cfg_structure struct vsir_cfg_structure_list body; unsigned idx; } loop; + struct + { + enum vsir_cfg_jump_type + { + /* NONE is available as an intermediate value, but it + * is not allowed in valid structured programs. */ + JUMP_NONE, + JUMP_BREAK, + JUMP_CONTINUE, + JUMP_RET, + } type; + unsigned int target; + struct vkd3d_shader_src_param *condition; + bool invert_condition; + } jump; } u; }; @@ -3987,6 +4007,70 @@ static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_ return VKD3D_OK; } +struct vsir_cfg_edge_action +{ + enum vsir_cfg_jump_type jump_type; + unsigned int target; + struct vsir_block *successor; +}; + +static void vsir_cfg_compute_edge_action(struct vsir_cfg *cfg, struct vsir_block *block, + struct vsir_block *successor, struct vsir_cfg_edge_action *action) +{ + unsigned int i; + + action->target = UINT_MAX; + action->successor = successor; + + if (successor->order_pos <= block->order_pos) + { + /* The successor is before the current block, so we have to + * use `continue'. The target loop is the innermost that + * contains the current block and has the successor as + * `continue' target. */ + for (i = 0; i < cfg->loop_interval_count; ++i) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[i]; + + if (interval->begin == successor->order_pos && block->order_pos < interval->end) + action->target = i; + + if (interval->begin > successor->order_pos) + break; + } + + assert(action->target != UINT_MAX); + action->jump_type = JUMP_CONTINUE; + } + else + { + /* The successor is after the current block, so we have to use + * `break', or possibly just jump to the following block. The + * target loop is the outermost that contains the current + * block and has the successor as `break' target. */ + for (i = 0; i < cfg->loop_interval_count; ++i) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[i]; + + if (interval->begin <= block->order_pos && interval->end == successor->order_pos) + { + action->target = i; + break; + } + } + + if (action->target == UINT_MAX) + { + assert(successor->order_pos == block->order_pos + 1); + action->jump_type = JUMP_NONE; + } + else + { + action->jump_type = JUMP_BREAK; + } + } +} + static enum vkd3d_result vsir_cfg_build_structured_program(struct vsir_cfg *cfg) { unsigned int i, stack_depth = 1, open_interval_idx = 0; @@ -4001,6 +4085,7 @@ static enum vkd3d_result vsir_cfg_build_structured_program(struct vsir_cfg *cfg) for (i = 0; i < cfg->order.count; ++i) { + struct vsir_block *block = cfg->order.blocks[i]; struct vsir_cfg_structure *structure; assert(stack_depth > 0); @@ -4024,9 +4109,88 @@ static enum vkd3d_result vsir_cfg_build_structured_program(struct vsir_cfg *cfg) /* Execute the block. */ if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_BLOCK))) goto fail; - structure->u.block = cfg->order.blocks[i]; + structure->u.block = block; - /* TODO: process the jump after the block. */ + /* Generate between zero and two jump instructions. */ + switch (block->end->handler_idx) + { + case VKD3DSIH_BRANCH: + { + struct vsir_cfg_edge_action action_true, action_false; + bool invert_condition = false; + + if (vsir_register_is_label(&block->end->src[0].reg)) + { + unsigned int target = label_from_src_param(&block->end->src[0]); + struct vsir_block *successor = &cfg->blocks[target - 1]; + + vsir_cfg_compute_edge_action(cfg, block, successor, &action_true); + action_false = action_true; + } + else + { + unsigned int target = label_from_src_param(&block->end->src[1]); + struct vsir_block *successor = &cfg->blocks[target - 1]; + + vsir_cfg_compute_edge_action(cfg, block, successor, &action_true); + + target = label_from_src_param(&block->end->src[2]); + successor = &cfg->blocks[target - 1]; + + vsir_cfg_compute_edge_action(cfg, block, successor, &action_false); + } + + /* This will happen if the branch is unconditional, + * but also if it's conditional with the same target + * in both branches, which can happen in some corner + * cases, e.g. when converting switch instructions to + * selection ladders. */ + if (action_true.successor == action_false.successor) + { + assert(action_true.jump_type == action_false.jump_type); + } + else + { + /* At most one branch can just fall through to the + * next block, in which case we make sure it's the + * false branch. */ + if (action_true.jump_type == JUMP_NONE) + { + struct vsir_cfg_edge_action tmp = action_true; + action_true = action_false; + action_false = tmp; + invert_condition = true; + } + + assert(action_true.jump_type != JUMP_NONE); + + if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_JUMP))) + goto fail; + structure->u.jump.type = action_true.jump_type; + structure->u.jump.target = action_true.target; + structure->u.jump.condition = &block->end->src[0]; + structure->u.jump.invert_condition = invert_condition; + } + + if (action_false.jump_type != JUMP_NONE) + { + if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_JUMP))) + goto fail; + structure->u.jump.type = action_false.jump_type; + structure->u.jump.target = action_false.target; + } + break; + } + + case VKD3DSIH_RET: + if (!(structure = vsir_cfg_structure_list_append(stack[stack_depth - 1], STRUCTURE_TYPE_JUMP))) + goto fail; + structure->u.jump.type = JUMP_RET; + break; + + default: + vkd3d_unreachable(); + } /* Close loop intervals. */ while (stack_depth > 0) -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 73 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 8c74f2b08..6e09b68cd 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3379,6 +3379,76 @@ static void vsir_cfg_dump_dot(struct vsir_cfg *cfg) TRACE("}\n"); } +static void vsir_cfg_structure_list_dump(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list); + +static void vsir_cfg_structure_dump(struct vsir_cfg *cfg, struct vsir_cfg_structure *structure) +{ + switch (structure->type) + { + case STRUCTURE_TYPE_BLOCK: + TRACE("%sblock %u\n", cfg->debug_buffer.buffer, structure->u.block->label); + break; + + case STRUCTURE_TYPE_LOOP: + TRACE("%s%u : loop {\n", cfg->debug_buffer.buffer, structure->u.loop.idx); + + vsir_cfg_structure_list_dump(cfg, &structure->u.loop.body); + + TRACE("%s} # %u\n", cfg->debug_buffer.buffer, structure->u.loop.idx); + break; + + case STRUCTURE_TYPE_JUMP: + { + const char *type_str; + + switch (structure->u.jump.type) + { + case JUMP_RET: + TRACE("%sret\n", cfg->debug_buffer.buffer); + return; + + case JUMP_BREAK: + type_str = "break"; + break; + + case JUMP_CONTINUE: + type_str = "continue"; + break; + + default: + vkd3d_unreachable(); + } + + TRACE("%s%s%s %u\n", cfg->debug_buffer.buffer, type_str, + structure->u.jump.condition ? "c" : "", structure->u.jump.target); + break; + } + + default: + vkd3d_unreachable(); + } +} + +static void vsir_cfg_structure_list_dump(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) +{ + unsigned int i; + + vkd3d_string_buffer_printf(&cfg->debug_buffer, " "); + + for (i = 0; i < list->count; ++i) + vsir_cfg_structure_dump(cfg, &list->structures[i]); + + vkd3d_string_buffer_truncate(&cfg->debug_buffer, cfg->debug_buffer.content_size - 2); +} + +static void vsir_cfg_dump_structured_program(struct vsir_cfg *cfg) +{ + unsigned int i; + + for (i = 0; i < cfg->structured_program.count; ++i) + vsir_cfg_structure_dump(cfg, &cfg->structured_program.structures[i]); +} + static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program, struct vkd3d_shader_message_context *message_context) { @@ -4205,6 +4275,9 @@ static enum vkd3d_result vsir_cfg_build_structured_program(struct vsir_cfg *cfg) assert(stack_depth == 0); assert(open_interval_idx == cfg->loop_interval_count); + if (TRACE_ON()) + vsir_cfg_dump_structured_program(cfg); + vkd3d_free(stack); return VKD3D_OK; -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/vkd3d_shader_main.c:
void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer) { - buffer->buffer[0] = '\0'; - buffer->content_size = 0; + vkd3d_string_buffer_truncate(buffer, 0); +} + +void vkd3d_string_buffer_truncate(struct vkd3d_string_buffer *buffer, size_t size)
This is only used in the last commit. -- https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704#note_64671
participants (3)
-
Conor McCarthy (＠cmccarthy) -
Giovanni Mascellani
-
Giovanni Mascellani (＠giomasce)