[PATCH v2 0/6] 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. -- v2: vkd3d-shader/ir: Dump the reconstructed structured program. vkd3d-shader/ir: Add jumps to the structured programs. vkd3d-shader/ir: Reconstruct a structured program. vkd3d-shader/ir: Sort loop intervals. vkd3d-shader/ir: Generate synthetic intervals for forward edges. vkd3d-shader/ir: Compute loop as intervals of the block order. https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 53 +++++++++++++++++++++++++++++++++++------- 1 file changed, 45 insertions(+), 8 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 3c862f33e..d26341d54 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3140,6 +3140,16 @@ struct vsir_cfg size_t *loops_by_header; struct vsir_block_list order; + struct cfg_loop_interval + { + /* `begin' is the position of the first block of the loop in + * the topological sort; `end' is the position of the first + * block after the loop. In other words, `begin' is where a + * `continue' instruction would jump and `end' is where a + * `break' instruction would jump. */ + unsigned int begin, end; + } *loop_intervals; + size_t loop_interval_count, loop_interval_capacity; }; static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -3157,11 +3167,29 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) vkd3d_free(cfg->blocks); vkd3d_free(cfg->loops); vkd3d_free(cfg->loops_by_header); + vkd3d_free(cfg->loop_intervals); if (TRACE_ON()) vkd3d_string_buffer_cleanup(&cfg->debug_buffer); } +static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsigned int begin, + unsigned int end) +{ + struct cfg_loop_interval *interval; + + if (!vkd3d_array_reserve((void **)&cfg->loop_intervals, &cfg->loop_interval_capacity, + cfg->loop_interval_count + 1, sizeof(*cfg->loop_intervals))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + interval = &cfg->loop_intervals[cfg->loop_interval_count++]; + + interval->begin = begin; + interval->end = end; + + return VKD3D_OK; +} + static bool vsir_block_dominates(struct vsir_block *b1, struct vsir_block *b2) { return bitmap_is_set(b1->dominates, b2->label - 1); @@ -3396,14 +3424,14 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg) * 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). */ + * If the input CFG is reducible its loops are properly nested (i.e., + * each two loops are either disjoint or one is contained in 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) { @@ -3496,6 +3524,7 @@ struct vsir_cfg_node_sorter { struct vsir_block_list *loop; unsigned int seen_count; + unsigned int begin; } *stack; size_t stack_count, stack_capacity; struct vsir_block_list available_blocks; @@ -3522,6 +3551,7 @@ static enum vkd3d_result vsir_cfg_node_sorter_make_node_available(struct vsir_cf item = &sorter->stack[sorter->stack_count++]; item->loop = loop; item->seen_count = 0; + item->begin = sorter->cfg->order.count; return VKD3D_OK; } @@ -3646,6 +3676,10 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg) if (inner_stack_item->seen_count != inner_stack_item->loop->count) break; + if ((ret = vsir_cfg_add_loop_interval(cfg, inner_stack_item->begin, + cfg->order.count)) < 0) + goto fail; + new_seen_count = inner_stack_item->loop->count; --sorter.stack_count; } @@ -3694,6 +3728,9 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg) TRACE("%s\n", cfg->debug_buffer.buffer); vkd3d_string_buffer_clear(&cfg->debug_buffer); + + for (i = 0; i < cfg->loop_interval_count; ++i) + TRACE("Loop interval %u - %u\n", cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end); } return VKD3D_OK; -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 159 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 153 insertions(+), 6 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index d26341d54..4997b475a 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3065,7 +3065,7 @@ static void vsir_block_list_remove_index(struct vsir_block_list *list, size_t id struct vsir_block { - unsigned int label; + unsigned int label, order_pos; /* `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 @@ -3148,6 +3148,27 @@ struct vsir_cfg * `continue' instruction would jump and `end' is where a * `break' instruction would jump. */ unsigned int begin, end; + /* Each loop interval can be natural or synthetic. Natural + * intervals are added to represent loops given by CFG back + * edges. Synthetic intervals do not correspond to loops in + * the input CFG, but are added to leverage their `break' + * instruction in order to execute forward edges. + * + * For a synthetic loop interval it's not really important + * which one is the `begin' block, since we don't need to + * execute `continue' for them. So we have some leeway for + * moving it provided that these conditions are met: 1. the + * interval must contain all `break' instructions that target + * it, which in practice means that `begin' can be moved + * backward and not forward; 2. intervals must remain properly + * nested (for each pair of intervals, either one contains the + * other or they are disjoint). + * + * Subject to these conditions, we try to reuse the same loop + * as much as possible (if many forward edges target the same + * block), but we still try to keep `begin' as forward as + * possible, to keep the loop scope as small as possible. */ + bool synthetic; } *loop_intervals; size_t loop_interval_count, loop_interval_capacity; }; @@ -3174,7 +3195,7 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg) } static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsigned int begin, - unsigned int end) + unsigned int end, bool synthetic) { struct cfg_loop_interval *interval; @@ -3186,6 +3207,7 @@ static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsign interval->begin = begin; interval->end = end; + interval->synthetic = synthetic; return VKD3D_OK; } @@ -3658,6 +3680,7 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg) } vsir_block_list_remove_index(&sorter.available_blocks, i); + block->order_pos = cfg->order.count; if ((ret = vsir_block_list_add_checked(&cfg->order, block)) < 0) goto fail; @@ -3677,7 +3700,7 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg) break; if ((ret = vsir_cfg_add_loop_interval(cfg, inner_stack_item->begin, - cfg->order.count)) < 0) + cfg->order.count, false)) < 0) goto fail; new_seen_count = inner_stack_item->loop->count; @@ -3728,9 +3751,6 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg) TRACE("%s\n", cfg->debug_buffer.buffer); vkd3d_string_buffer_clear(&cfg->debug_buffer); - - for (i = 0; i < cfg->loop_interval_count; ++i) - TRACE("Loop interval %u - %u\n", cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end); } return VKD3D_OK; @@ -3743,6 +3763,127 @@ fail: return ret; } +static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_cfg *cfg) +{ + enum vkd3d_result ret; + size_t i, j, k; + + 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 *successor = block->successors.blocks[j]; + struct cfg_loop_interval *extend = NULL; + unsigned int begin; + enum + { + ACTION_DO_NOTHING, + ACTION_CREATE_NEW, + ACTION_EXTEND, + } action = ACTION_CREATE_NEW; + + /* We've already contructed loop intervals for the back + * edges, there's nothing more to do. */ + if (vsir_block_dominates(successor, block)) + continue; + + assert(block->order_pos < successor->order_pos); + + /* Jumping from a block to the following one is always + * possible, so nothing to do. */ + if (block->order_pos + 1 == successor->order_pos) + continue; + + /* Let's look for a loop interval that already breaks at + * `successor' and either contains or can be extended to + * contain `block'. */ + for (k = 0; k < cfg->loop_interval_count; ++k) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[k]; + + if (interval->end != successor->order_pos) + continue; + + if (interval->begin <= block->order_pos) + { + action = ACTION_DO_NOTHING; + break; + } + + if (interval->synthetic) + { + action = ACTION_EXTEND; + extend = interval; + break; + } + } + + if (action == ACTION_DO_NOTHING) + continue; + + /* Ok, we have to decide where the new or replacing + * interval has to begin. These are the rules: 1. it must + * begin before `block'; 2. intervals must be properly + * nested; 3. the new interval should begin as late as + * possible, to limit control flow depth and extension. */ + begin = block->order_pos; + + /* Our candidate interval is always [begin, + * successor->order_pos), and we move `begin' backward + * until the candidate interval contains all the intervals + * whose endpoint lies in the candidate interval + * itself. */ + for (k = 0; k < cfg->loop_interval_count; ++k) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[k]; + + if (begin < interval->end && interval->end < successor->order_pos) + begin = min(begin, interval->begin); + } + + /* New we have to care about the intervals whose begin + * point lies in the candidate interval. We cannot move + * the candidate interval endpoint, because it is + * important that the loop break target matches + * `successor'. So we have to move that interval's begin + * point to the begin point of the candidate interval, + * i.e. `begin'. But what if the interval we should extend + * backward is not synthetic? This cannot happen, + * fortunately, because it would mean that there is a jump + * entering a loop via a block which is not the loop + * header, so the CFG would not be reducible. */ + for (k = 0; k < cfg->loop_interval_count; ++k) + { + struct cfg_loop_interval *interval = &cfg->loop_intervals[k]; + + if (interval->begin < successor->order_pos && successor->order_pos < interval->end) + { + if (interval->synthetic) + interval->begin = min(begin, interval->begin); + assert(begin >= interval->begin); + } + } + + if (action == ACTION_EXTEND) + extend->begin = begin; + else if ((ret = vsir_cfg_add_loop_interval(cfg, begin, successor->order_pos, true)) < 0) + return ret; + } + } + + if (TRACE_ON()) + for (i = 0; i < cfg->loop_interval_count; ++i) + TRACE("%s loop interval %u - %u\n", cfg->loop_intervals[i].synthetic ? "Synthetic" : "Natural", + cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end); + + return VKD3D_OK; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -3781,6 +3922,12 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, return result; } + if ((result = vsir_cfg_generate_synthetic_loop_intervals(&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/704
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 4997b475a..bf565c2bc 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3763,6 +3763,20 @@ fail: return ret; } +/* Sort loop intervals first by ascending begin time and then by + * descending end time, so that inner intervals appear after outer + * ones and disjoint intervals appear in their proper order. */ +static int compare_loop_intervals(const void *ptr1, const void *ptr2) +{ + const struct cfg_loop_interval *interval1 = ptr1; + const struct cfg_loop_interval *interval2 = ptr2; + + if (interval1->begin != interval2->begin) + return vkd3d_u32_compare(interval1->begin, interval2->begin); + + return -vkd3d_u32_compare(interval1->end, interval2->end); +} + static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_cfg *cfg) { enum vkd3d_result ret; @@ -3876,6 +3890,8 @@ static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_ } } + qsort(cfg->loop_intervals, cfg->loop_interval_count, sizeof(*cfg->loop_intervals), compare_loop_intervals); + if (TRACE_ON()) for (i = 0; i < cfg->loop_interval_count; ++i) TRACE("%s loop interval %u - %u\n", cfg->loop_intervals[i].synthetic ? "Synthetic" : "Natural", -- GitLab 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 bf565c2bc..d681e1143 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3126,6 +3126,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; @@ -3171,6 +3238,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) @@ -3185,6 +3254,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); @@ -3900,6 +3971,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) { @@ -3944,6 +4079,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 = simple_structurizer_run(parser)) < 0) { vsir_cfg_cleanup(&cfg); diff --git a/libs/vkd3d-shader/vkd3d_shader_main.c b/libs/vkd3d-shader/vkd3d_shader_main.c index 96f2bf26f..ec852a5ef 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 831fb9bc4..69a975b34 100644 --- a/libs/vkd3d-shader/vkd3d_shader_private.h +++ b/libs/vkd3d-shader/vkd3d_shader_private.h @@ -1403,6 +1403,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 d681e1143..1019352be 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3141,6 +3141,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 { @@ -3150,6 +3155,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; }; @@ -3971,6 +3991,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; @@ -3985,6 +4069,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); @@ -4008,9 +4093,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 1019352be..3263a2f30 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3363,6 +3363,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) { @@ -4189,6 +4259,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
participants (2)
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)