[PATCH v11 0/8] MR662: vkd3d-shader/ir: Introduce a better CFG structurizer, part 2.
~~This applies on top of !656, the last three commits belong here.~~ -- v11: vkd3d-shader/ir: Sort each loop by block label. vkd3d-shader/ir: Dump the loops in the control flow graph. vkd3d-shader/ir: Keep track of loops by header block. 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> --- libs/vkd3d-shader/ir.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 2e05d19ca..4ffdd0cb1 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3118,6 +3118,11 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) 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 +3325,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); -- 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 | 93 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 94 insertions(+), 1 deletion(-) 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 4ffdd0cb1..05997241f 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))) { @@ -3103,6 +3103,9 @@ 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; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3112,7 +3115,11 @@ 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); if (TRACE_ON()) vkd3d_string_buffer_cleanup(&cfg->debug_buffer); @@ -3334,6 +3341,84 @@ 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. + * + * If the input CFG is reducible, each two loops are either disjoint + * or one is a strict subset of the other, provided that each block + * has at most one incoming back edge. If this condition does not + * hold, a synthetic block can be introduced as the only back edge + * block for the given header block, with all the previous back edge + * now being forward edges to the synthetic block. This is not + * currently implemented (but it is rarely found in practice + * anyway). */ +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 ((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; + + 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; + + /* Is this a back edge? */ + 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; + } + } + + return VKD3D_OK; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3360,6 +3445,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
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 05997241f..8fb52175d 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3098,6 +3098,7 @@ static void vsir_block_cleanup(struct vsir_block *block) struct vsir_cfg { + struct vkd3d_shader_message_context *message_context; struct vsir_program *program; struct vsir_block *blocks; struct vsir_block *entry; @@ -3185,13 +3186,15 @@ static void vsir_cfg_dump_dot(struct vsir_cfg *cfg) TRACE("}\n"); } -static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program) +static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program, + struct vkd3d_shader_message_context *message_context) { struct vsir_block *current_block = NULL; enum vkd3d_result ret; size_t i; memset(cfg, 0, sizeof(*cfg)); + cfg->message_context = message_context; cfg->program = program; cfg->block_count = program->block_count; @@ -3440,7 +3443,7 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, if ((result = materialize_ssas_to_temps(parser)) < 0) return result; - if ((result = vsir_cfg_init(&cfg, &parser->program)) < 0) + if ((result = vsir_cfg_init(&cfg, &parser->program, parser->message_context)) < 0) return result; vsir_cfg_compute_dominators(&cfg); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 8fb52175d..218e38a9c 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3107,6 +3107,7 @@ struct vsir_cfg struct vsir_block_list *loops; size_t loops_count, loops_capacity; + size_t *loops_by_header; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3121,6 +3122,7 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) vkd3d_free(cfg->blocks); vkd3d_free(cfg->loops); + vkd3d_free(cfg->loops_by_header); if (TRACE_ON()) vkd3d_string_buffer_cleanup(&cfg->debug_buffer); @@ -3391,6 +3393,10 @@ static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) { size_t i, j; + if (!(cfg->loops_by_header = vkd3d_calloc(cfg->block_count, sizeof(*cfg->loops_by_header)))) + return VKD3D_ERROR_OUT_OF_MEMORY; + memset(cfg->loops_by_header, 0xff, cfg->block_count * sizeof(*cfg->loops_by_header)); + for (i = 0; i < cfg->block_count; ++i) { struct vsir_block *block = &cfg->blocks[i]; @@ -3411,11 +3417,23 @@ static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) 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++]; + loop = &cfg->loops[cfg->loops_count]; vsir_block_list_init(loop); if ((ret = vsir_cfg_scan_loop(loop, block, header)) < 0) return ret; + + if (cfg->loops_by_header[header->label - 1] != SIZE_MAX) + { + FIXME("Block %u is header to more than one loop, this is not implemented.\n", header->label); + vkd3d_shader_error(cfg->message_context, &header->begin->location, VKD3D_SHADER_ERROR_VSIR_NOT_IMPLEMENTED, + "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] = cfg->loops_count; + + ++cfg->loops_count; } } -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 218e38a9c..58237152b 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3391,7 +3391,7 @@ static enum vkd3d_result vsir_cfg_scan_loop(struct vsir_block_list *loop, struct static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) { - size_t i, j; + 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; @@ -3423,6 +3423,17 @@ static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) if ((ret = vsir_cfg_scan_loop(loop, block, header)) < 0) return ret; + 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] != SIZE_MAX) { FIXME("Block %u is header to more than one loop, this is not implemented.\n", header->label); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 58237152b..50a2287c9 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3096,6 +3096,19 @@ static void vsir_block_cleanup(struct vsir_block *block) vkd3d_free(block->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 void vsir_block_list_sort(struct vsir_block_list *list) +{ + qsort(list->blocks, list->count, sizeof(*list->blocks), block_compare); +} + struct vsir_cfg { struct vkd3d_shader_message_context *message_context; @@ -3423,6 +3436,8 @@ static enum vkd3d_result vsir_cfg_compute_loops(struct vsir_cfg *cfg) 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); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662
I realized that `loops_by_header` kept references to an array that gets reallocated; so I replaced those pointers with indices in the `loops` array. -- https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662#note_62933
```diff +static enum vkd3d_result vsir_cfg_init(struct vsir_cfg *cfg, struct vsir_program *program, + struct vkd3d_shader_message_context *message_context) ```
Minor formatting issue. -- https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/662#note_63733
participants (3)
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)
-
Henri Verbeet (＠hverbeet)