[PATCH v2 0/7] MR662: Draft: vkd3d-shader/ir: Introduce a better CFG structurizer, part 2.
This applies on top of !656, the last three commits belong here. -- v2: vkd3d-shader/ir: Compute the loops in the control flow graph. vkd3d-shader/ir: Add a debug buffer to struct vsir_cfg. vkd3d-shader/ir: Properly handle function-local indexable temps when flattening control flow. vkd3d-shader/ir: Dump the domination relationship. vkd3d-shader/ir: Compute the domination relationship. vkd3d-shader/ir: Dump the control flow graph in the GraphViz format. vkd3d-shader/ir: Build a representation of the control flow graph. https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 198 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 198 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 886344874..4da8c0cb4 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3009,6 +3009,194 @@ fail: return VKD3D_ERROR_OUT_OF_MEMORY; } +struct vsir_block_list +{ + struct vsir_block **blocks; + size_t count, capacity; +}; + +static void vsir_block_list_init(struct vsir_block_list *list) +{ + memset(list, 0, sizeof(*list)); +} + +static void vsir_block_list_cleanup(struct vsir_block_list *list) +{ + vkd3d_free(list->blocks); +} + +static enum vkd3d_result vsir_block_list_add(struct vsir_block_list *list, struct vsir_block *block) +{ + size_t i; + + for (i = 0; i < list->count; ++i) + if (block == list->blocks[i]) + return VKD3D_OK; + + if (!vkd3d_array_reserve((void **)&list->blocks, &list->capacity, list->count + 1, sizeof(*list->blocks))) + { + ERR("Cannot extend block list.\n"); + return VKD3D_ERROR_OUT_OF_MEMORY; + } + + list->blocks[list->count++] = block; + + return VKD3D_OK; +} + +struct vsir_block +{ + unsigned int label; + /* `begin' points to the instruction immediately following the + * LABEL that introduces the block. `end' points to the terminator + * instruction (either BRANCH or RET). They can coincide, meaning + * that the block is empty. */ + struct vkd3d_shader_instruction *begin, *end; + struct vsir_block_list predecessors, successors; +}; + +static void vsir_block_init(struct vsir_block *block, unsigned int label) +{ + assert(label); + memset(block, 0, sizeof(*block)); + block->label = label; + vsir_block_list_init(&block->predecessors); + vsir_block_list_init(&block->successors); +} + +static void vsir_block_cleanup(struct vsir_block *block) +{ + vsir_block_list_cleanup(&block->predecessors); + vsir_block_list_cleanup(&block->successors); +} + +struct vsir_cfg +{ + struct vsir_program *program; + struct vsir_block *blocks; + struct vsir_block *entry; + size_t block_count; +}; + +static void vsir_cfg_cleanup(struct vsir_cfg *cfg) +{ + size_t i; + + for (i = 0; i < cfg->block_count; ++i) + vsir_block_cleanup(&cfg->blocks[i]); + + vkd3d_free(cfg->blocks); +} + +static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_block *block, + struct vkd3d_shader_src_param *successor_param) +{ + unsigned int target = label_from_src_param(successor_param); + struct vsir_block *successor = &cfg->blocks[target - 1]; + enum vkd3d_result ret; + + assert(successor->label != 0); + + if ((ret = vsir_block_list_add(&block->successors, successor)) < 0) + return ret; + + if ((ret = vsir_block_list_add(&successor->predecessors, block)) < 0) + return ret; + + return VKD3D_OK; +} + +static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program) +{ + struct vsir_block *current_block = NULL; + enum vkd3d_result ret; + size_t i; + + memset(cfg, 0, sizeof(*cfg)); + cfg->program = program; + cfg->block_count = program->block_count; + + if (!(cfg->blocks = vkd3d_calloc(cfg->block_count, sizeof(*cfg->blocks)))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + for (i = 0; i < program->instructions.count; ++i) + { + struct vkd3d_shader_instruction *instruction = &program->instructions.elements[i]; + + switch (instruction->handler_idx) + { + case VKD3DSIH_PHI: + case VKD3DSIH_SWITCH_MONOLITHIC: + vkd3d_unreachable(); + + case VKD3DSIH_LABEL: + { + unsigned int label = label_from_src_param(&instruction->src[0]); + + assert(!current_block); + assert(label > 0); + assert(label <= cfg->block_count); + current_block = &cfg->blocks[label - 1]; + vsir_block_init(current_block, label); + current_block->begin = &program->instructions.elements[i + 1]; + if (!cfg->entry) + cfg->entry = current_block; + break; + } + + case VKD3DSIH_BRANCH: + case VKD3DSIH_RET: + assert(current_block); + current_block->end = instruction; + current_block = NULL; + break; + + default: + break; + } + } + + for (i = 0; i < cfg->block_count; ++i) + { + struct vsir_block *block = &cfg->blocks[i]; + + if (block->label == 0) + continue; + + switch (block->end->handler_idx) + { + case VKD3DSIH_RET: + break; + + case VKD3DSIH_BRANCH: + if (vsir_register_is_label(&block->end->src[0].reg)) + { + if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[0])) < 0) + goto fail; + } + else + { + if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[1])) < 0) + goto fail; + + if ((ret = vsir_cfg_add_edge(cfg, block, &block->end->src[2])) < 0) + goto fail; + } + break; + + default: + vkd3d_unreachable(); + } + } + + return VKD3D_OK; + +fail: + vsir_cfg_cleanup(cfg); + + return ret; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3022,14 +3210,24 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, if (parser->shader_desc.is_dxil) { + struct vsir_cfg cfg; + if ((result = lower_switch_to_if_ladder(&parser->program)) < 0) return result; if ((result = materialize_ssas_to_temps(parser)) < 0) return result; + if ((result = vsir_cfg_init(&cfg, &parser->program)) < 0) + return result; + if ((result = simple_structurizer_run(parser)) < 0) + { + vsir_cfg_cleanup(&cfg); return result; + } + + vsir_cfg_cleanup(&cfg); } else { -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 4da8c0cb4..646a71a2d 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3106,6 +3106,43 @@ static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_blo return VKD3D_OK; } +static void vsir_cfg_dump_dot(struct vsir_cfg *cfg) +{ + size_t i, j; + + TRACE("digraph cfg {\n"); + + for (i = 0; i < cfg->block_count; ++i) + { + struct vsir_block *block = &cfg->blocks[i]; + const char *shape; + + if (block->label == 0) + continue; + + switch (block->end->handler_idx) + { + case VKD3DSIH_RET: + shape = "trapezium"; + break; + + case VKD3DSIH_BRANCH: + shape = vsir_register_is_label(&block->end->src[0].reg) ? "ellipse" : "box"; + break; + + default: + vkd3d_unreachable(); + } + + TRACE(" n%u [label=\"%u\", shape=\"%s\"];\n", block->label, block->label, shape); + + for (j = 0; j < block->successors.count; ++j) + TRACE(" n%u -> n%u;\n", block->label, block->successors.blocks[j]->label); + } + + TRACE("}\n"); +} + static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program) { struct vsir_block *current_block = NULL; @@ -3189,6 +3226,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program } } + if (TRACE_ON()) + vsir_cfg_dump_dot(cfg); + return VKD3D_OK; fail: -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 67 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 65 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 646a71a2d..536b19e13 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3053,21 +3053,40 @@ struct vsir_block * that the block is empty. */ struct vkd3d_shader_instruction *begin, *end; struct vsir_block_list predecessors, successors; + uint32_t *dominates; }; -static void vsir_block_init(struct vsir_block *block, unsigned int label) +static enum vkd3d_result vsir_block_init(struct vsir_block *block, unsigned int label, size_t block_count) { + size_t byte_count; + + if (block_count > SIZE_MAX - (sizeof(*block->dominates) * CHAR_BIT - 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + block_count = align(block_count, sizeof(*block->dominates) * CHAR_BIT); + byte_count = block_count / CHAR_BIT; + assert(label); memset(block, 0, sizeof(*block)); block->label = label; vsir_block_list_init(&block->predecessors); vsir_block_list_init(&block->successors); + + if (!(block->dominates = vkd3d_malloc(byte_count))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + memset(block->dominates, 0xff, byte_count); + + return VKD3D_OK; } static void vsir_block_cleanup(struct vsir_block *block) { + if (block->label == 0) + return; vsir_block_list_cleanup(&block->predecessors); vsir_block_list_cleanup(&block->successors); + vkd3d_free(block->dominates); } struct vsir_cfg @@ -3174,7 +3193,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program assert(label > 0); assert(label <= cfg->block_count); current_block = &cfg->blocks[label - 1]; - vsir_block_init(current_block, label); + assert(current_block->label == 0); + if ((ret = vsir_block_init(current_block, label, program->block_count)) < 0) + goto fail; current_block->begin = &program->instructions.elements[i + 1]; if (!cfg->entry) cfg->entry = current_block; @@ -3237,6 +3258,46 @@ fail: return ret; } +/* Block A dominates block B if every path from the entry point to B + * must pass through A. Naively compute the set of blocks that are + * dominated by `reference' by running a graph visit starting from the + * entry point (which must be the initial value of `current') and + * avoiding `reference'. Running this for all the blocks takes + * quadratic time: if in the future something better is sought after, + * the standard tool seems to be the Lengauer-Tarjan algorithm. */ +static void vsir_cfg_compute_dominators_recurse(struct vsir_block *current, struct vsir_block *reference) +{ + size_t i; + + assert(current->label != 0); + + if (current == reference) + return; + + if (!bitmap_is_set(reference->dominates, current->label - 1)) + return; + + bitmap_clear(reference->dominates, current->label - 1); + + for (i = 0; i < current->successors.count; ++i) + vsir_cfg_compute_dominators_recurse(current->successors.blocks[i], reference); +} + +static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) +{ + size_t i; + + for (i = 0; i < cfg->block_count; ++i) + { + struct vsir_block *block = &cfg->blocks[i]; + + if (block->label == 0) + continue; + + vsir_cfg_compute_dominators_recurse(cfg->entry, block); + } +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3261,6 +3322,8 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, if ((result = vsir_cfg_init(&cfg, &parser->program)) < 0) return result; + vsir_cfg_compute_dominators(&cfg); + if ((result = simple_structurizer_run(parser)) < 0) { vsir_cfg_cleanup(&cfg); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 26 +++++++++++++++++++++++- libs/vkd3d-shader/vkd3d_shader_main.c | 2 +- libs/vkd3d-shader/vkd3d_shader_private.h | 1 + 3 files changed, 27 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 536b19e13..f0bd85338 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3285,7 +3285,11 @@ static void vsir_cfg_compute_dominators_recurse(struct vsir_block *current, stru static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) { - size_t i; + struct vkd3d_string_buffer buf; + size_t i, j; + + if (TRACE_ON()) + vkd3d_string_buffer_init(&buf); for (i = 0; i < cfg->block_count; ++i) { @@ -3295,7 +3299,27 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) continue; vsir_cfg_compute_dominators_recurse(cfg->entry, block); + + if (TRACE_ON()) + { + vkd3d_string_buffer_printf(&buf, "Block %u dominates:", block->label); + for (j = 0; j < cfg->block_count; j++) + { + struct vsir_block *block2 = &cfg->blocks[j]; + + if (block2->label == 0) + continue; + + if (bitmap_is_set(block->dominates, j)) + vkd3d_string_buffer_printf(&buf, " %u", block2->label); + } + TRACE("%s\n", buf.buffer); + vkd3d_string_buffer_clear(&buf); + } } + + if (TRACE_ON()) + vkd3d_string_buffer_cleanup(&buf); } enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, diff --git a/libs/vkd3d-shader/vkd3d_shader_main.c b/libs/vkd3d-shader/vkd3d_shader_main.c index 20c4c2e2d..462a5c25e 100644 --- a/libs/vkd3d-shader/vkd3d_shader_main.c +++ b/libs/vkd3d-shader/vkd3d_shader_main.c @@ -71,7 +71,7 @@ void vkd3d_string_buffer_cleanup(struct vkd3d_string_buffer *buffer) vkd3d_free(buffer->buffer); } -static void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer) +void vkd3d_string_buffer_clear(struct vkd3d_string_buffer *buffer) { buffer->buffer[0] = '\0'; buffer->content_size = 0; diff --git a/libs/vkd3d-shader/vkd3d_shader_private.h b/libs/vkd3d-shader/vkd3d_shader_private.h index 7239beaf7..4b322b95b 100644 --- a/libs/vkd3d-shader/vkd3d_shader_private.h +++ b/libs/vkd3d-shader/vkd3d_shader_private.h @@ -1399,6 +1399,7 @@ struct vkd3d_string_buffer *vkd3d_string_buffer_get(struct vkd3d_string_buffer_c 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); 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/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> They have to be considered code rather than declarations, as required for instance by the SPIR-V backend. --- libs/vkd3d-shader/ir.c | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index f0bd85338..a379ba6dd 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -2041,12 +2041,19 @@ static enum vkd3d_result cf_flattener_iterate_instruction_array(struct cf_flatte flattener->location = instruction->location; /* Declarations should occur before the first code block, which in hull shaders is marked by the first - * phase instruction, and in all other shader types begins with the first label instruction. */ - if (!after_declarations_section && !vsir_instruction_is_dcl(instruction) - && instruction->handler_idx != VKD3DSIH_NOP) + * phase instruction, and in all other shader types begins with the first label instruction. + * Declaring an indexable temp with function scope is not considered a declaration, + * because it needs to live inside a function. */ + if (!after_declarations_section && instruction->handler_idx != VKD3DSIH_NOP) { - after_declarations_section = true; - cf_flattener_emit_label(flattener, cf_flattener_alloc_block_id(flattener)); + bool is_function_indexable = instruction->handler_idx == VKD3DSIH_DCL_INDEXABLE_TEMP + && instruction->declaration.indexable_temp.has_function_scope; + + if (!vsir_instruction_is_dcl(instruction) || is_function_indexable) + { + after_declarations_section = true; + cf_flattener_emit_label(flattener, cf_flattener_alloc_block_id(flattener)); + } } cf_info = flattener->control_flow_depth -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index a379ba6dd..2e05d19ca 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3102,6 +3102,7 @@ struct vsir_cfg struct vsir_block *blocks; struct vsir_block *entry; size_t block_count; + struct vkd3d_string_buffer debug_buffer; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3112,6 +3113,9 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) vsir_block_cleanup(&cfg->blocks[i]); vkd3d_free(cfg->blocks); + + if (TRACE_ON()) + vkd3d_string_buffer_cleanup(&cfg->debug_buffer); } static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_block *block, @@ -3182,6 +3186,9 @@ static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program if (!(cfg->blocks = vkd3d_calloc(cfg->block_count, sizeof(*cfg->blocks)))) return VKD3D_ERROR_OUT_OF_MEMORY; + if (TRACE_ON()) + vkd3d_string_buffer_init(&cfg->debug_buffer); + for (i = 0; i < program->instructions.count; ++i) { struct vkd3d_shader_instruction *instruction = &program->instructions.elements[i]; @@ -3292,12 +3299,8 @@ static void vsir_cfg_compute_dominators_recurse(struct vsir_block *current, stru static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) { - struct vkd3d_string_buffer buf; size_t i, j; - if (TRACE_ON()) - vkd3d_string_buffer_init(&buf); - for (i = 0; i < cfg->block_count; ++i) { struct vsir_block *block = &cfg->blocks[i]; @@ -3309,7 +3312,7 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) if (TRACE_ON()) { - vkd3d_string_buffer_printf(&buf, "Block %u dominates:", block->label); + vkd3d_string_buffer_printf(&cfg->debug_buffer, "Block %u dominates:", block->label); for (j = 0; j < cfg->block_count; j++) { struct vsir_block *block2 = &cfg->blocks[j]; @@ -3318,15 +3321,12 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) continue; if (bitmap_is_set(block->dominates, j)) - vkd3d_string_buffer_printf(&buf, " %u", block2->label); + vkd3d_string_buffer_printf(&cfg->debug_buffer, " %u", block2->label); } - TRACE("%s\n", buf.buffer); - vkd3d_string_buffer_clear(&buf); + TRACE("%s\n", cfg->debug_buffer.buffer); + vkd3d_string_buffer_clear(&cfg->debug_buffer); } } - - if (TRACE_ON()) - vkd3d_string_buffer_cleanup(&buf); } enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- include/vkd3d_types.h | 2 + libs/vkd3d-shader/ir.c | 132 ++++++++++++++++++++++++++++++++++++++++- 2 files changed, 132 insertions(+), 2 deletions(-) diff --git a/include/vkd3d_types.h b/include/vkd3d_types.h index 4a7aca236..9060fa087 100644 --- a/include/vkd3d_types.h +++ b/include/vkd3d_types.h @@ -41,6 +41,8 @@ enum vkd3d_result { /** Success. */ VKD3D_OK = 0, + /** Success as a result of there being nothing to do. */ + VKD3D_FALSE = 1, /** An unspecified failure occurred. */ VKD3D_ERROR = -1, /** There are not enough resources available to complete the operation. */ diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 2e05d19ca..7e4afe3fd 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3038,7 +3038,7 @@ static enum vkd3d_result vsir_block_list_add(struct vsir_block_list *list, struc for (i = 0; i < list->count; ++i) if (block == list->blocks[i]) - return VKD3D_OK; + return VKD3D_FALSE; if (!vkd3d_array_reserve((void **)&list->blocks, &list->capacity, list->count + 1, sizeof(*list->blocks))) { @@ -3051,6 +3051,13 @@ static enum vkd3d_result vsir_block_list_add(struct vsir_block_list *list, struc return VKD3D_OK; } +static int block_compare(const void *ptr1, const void *ptr2); + +static void vsir_block_list_sort(struct vsir_block_list *list) +{ + qsort(list->blocks, list->count, sizeof(*list->blocks), block_compare); +} + struct vsir_block { unsigned int label; @@ -3063,6 +3070,14 @@ struct vsir_block uint32_t *dominates; }; +static int block_compare(const void *ptr1, const void *ptr2) +{ + const struct vsir_block *block1 = *(const struct vsir_block **)ptr1; + const struct vsir_block *block2 = *(const struct vsir_block **)ptr2; + + return vkd3d_u32_compare(block1->label, block2->label); +} + static enum vkd3d_result vsir_block_init(struct vsir_block *block, unsigned int label, size_t block_count) { size_t byte_count; @@ -3103,6 +3118,10 @@ struct vsir_cfg struct vsir_block *entry; size_t block_count; struct vkd3d_string_buffer debug_buffer; + + struct vsir_block_list *loops; + size_t loops_count, loops_capacity; + struct vsir_block_list **loops_by_header; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3112,12 +3131,22 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) for (i = 0; i < cfg->block_count; ++i) vsir_block_cleanup(&cfg->blocks[i]); + for (i = 0; i < cfg->loops_count; ++i) + vsir_block_list_cleanup(&cfg->loops[i]); + vkd3d_free(cfg->blocks); + vkd3d_free(cfg->loops); + vkd3d_free(cfg->loops_by_header); if (TRACE_ON()) vkd3d_string_buffer_cleanup(&cfg->debug_buffer); } +static bool vsir_block_dominates(struct vsir_block *b1, struct vsir_block *b2) +{ + return bitmap_is_set(b1->dominates, b2->label - 1); +} + static enum vkd3d_result vsir_cfg_add_edge(struct vsir_cfg *cfg, struct vsir_block *block, struct vkd3d_shader_src_param *successor_param) { @@ -3320,7 +3349,7 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) if (block2->label == 0) continue; - if (bitmap_is_set(block->dominates, j)) + if (vsir_block_dominates(block, block2)) vkd3d_string_buffer_printf(&cfg->debug_buffer, " %u", block2->label); } TRACE("%s\n", cfg->debug_buffer.buffer); @@ -3329,6 +3358,99 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) } } +/* A back edge is an edge X -> Y for which block Y dominates block + * X. All the other edges are forward edges, and it is required that + * the input CFG is reducible, i.e., it is acyclic once you strip away + * the back edges. Each back edge X -> Y defines a loop: block X is + * the header block, block Y is the back edge block, and the loop + * consists of all the blocks which are dominated by the header block + * and have a path to the back edge block that doesn't pass through + * the header block (including the header block itself). It can be + * proved that all the blocks in such a path (connecting a loop block + * to the back edge block without passing through the header block) + * belong to the same loop. */ +static enum vkd3d_result vsir_cfg_scan_loop(struct vsir_block_list *loop, struct vsir_block *block, + struct vsir_block *header) +{ + enum vkd3d_result ret; + size_t i; + + if (!vsir_block_dominates(header, block)) + return VKD3D_OK; + + if ((ret = vsir_block_list_add(loop, block)) < 0) + return ret; + + if (ret == VKD3D_FALSE || block == header) + return VKD3D_OK; + + for (i = 0; i < block->predecessors.count; ++i) + { + if ((ret = vsir_cfg_scan_loop(loop, block->predecessors.blocks[i], header)) < 0) + return ret; + } + + return VKD3D_OK; +} + +static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) +{ + size_t i, j, k; + + if (!(cfg->loops_by_header = vkd3d_calloc(cfg->block_count, sizeof(*cfg->loops_by_header)))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + for (i = 0; i < cfg->block_count; ++i) + { + struct vsir_block *block = &cfg->blocks[i]; + + if (block->label == 0) + continue; + + for (j = 0; j < block->successors.count; ++j) + { + struct vsir_block *header = block->successors.blocks[j]; + struct vsir_block_list *loop; + enum vkd3d_result ret; + + if (!vsir_block_dominates(header, block)) + continue; + + if (!vkd3d_array_reserve((void **)&cfg->loops, &cfg->loops_capacity, cfg->loops_count + 1, sizeof(*cfg->loops))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + loop = &cfg->loops[cfg->loops_count++]; + vsir_block_list_init(loop); + + if ((ret = vsir_cfg_scan_loop(loop, block, header)) < 0) + return ret; + + vsir_block_list_sort(loop); + + if (TRACE_ON()) + { + vkd3d_string_buffer_printf(&cfg->debug_buffer, "Back edge %u -> %u with loop:", block->label, header->label); + + for (k = 0; k < loop->count; ++k) + vkd3d_string_buffer_printf(&cfg->debug_buffer, " %u", loop->blocks[k]->label); + + TRACE("%s\n", cfg->debug_buffer.buffer); + vkd3d_string_buffer_clear(&cfg->debug_buffer); + } + + if (cfg->loops_by_header[header->label - 1]) + { + FIXME("Block %u is header to more than one loop, this is not implemented.", header->label); + return VKD3D_ERROR_NOT_IMPLEMENTED; + } + + cfg->loops_by_header[header->label - 1] = loop; + } + } + + return VKD3D_OK; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3355,6 +3477,12 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, vsir_cfg_compute_dominators(&cfg); + if ((result = vsir_cfg_compute_loops(&cfg)) < 0) + { + vsir_cfg_cleanup(&cfg); + return result; + } + if ((result = simple_structurizer_run(parser)) < 0) { vsir_cfg_cleanup(&cfg); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
participants (2)
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)