[PATCH v2 0/6] MR773: Draft: vkd3d-shader/ir: Try harder to move `break's to the end of loops.
This goes atop !764. The last three commits belong to this MR. Since we want to get rid of loops and `break's as much as possible, we try to move `break's out of selection constructs as much as possible so it's easier to match them with loops. This MR introduces a few other tricks to help that. -- v2: vkd3d-shader/ir: Move breaks out of selections again after having optimized loops. vkd3d-shader/ir: Append code to the non-breaking branch if there is breaking one. vkd3d-shader/ir: Prepare for changing the destination list in vsir_cfg_optimize_recurse(). vkd3d-shader/ir: Remove loops that terminate with a `break'. vkd3d-shader/ir: Count how many jumps target each loop. https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 68 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 8af537390..7e43dff39 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4259,6 +4259,71 @@ static void vsir_cfg_remove_trailing_continue(struct vsir_cfg_structure_list *li --list->count; } +static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_structure_list *list) +{ + struct vsir_cfg_structure *structure; + size_t count = list->count; + + if (count == 0) + return NULL; + + structure = &list->structures[count - 1]; + + if (structure->type != STRUCTURE_TYPE_JUMP || structure->u.jump.type != JUMP_BREAK + || structure->u.jump.condition) + return NULL; + + return structure; +} + +/* When the last instruction in both branches of a selection construct + * is an unconditional break, any of them can be moved after the + * selection construct. If they break the same loop both of them can + * be moved out, otherwise we can choose which one: we choose the one + * that breaks the innermost loop, because we hope to eventually + * remove the loop itself. + * + * In principle a similar movement could be done when the last + * instructions are continue and continue, or continue and break. But + * in practice I don't think those situations can happen given the + * previous passes we do on the program, so we don't care. */ +static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_structure_list *list) +{ + struct vsir_cfg_structure *selection, *if_break, *else_break, *new_break; + unsigned int if_target, else_target, max_target; + size_t pos = list->count - 1; + + selection = &list->structures[pos]; + assert(selection->type == STRUCTURE_TYPE_SELECTION); + + if_break = vsir_cfg_get_trailing_break(&selection->u.selection.if_body); + else_break = vsir_cfg_get_trailing_break(&selection->u.selection.else_body); + + if (!if_break || !else_break) + return VKD3D_OK; + + if_target = if_break->u.jump.target; + else_target = else_break->u.jump.target; + max_target = max(if_target, else_target); + + if (!(new_break = vsir_cfg_structure_list_append(list, STRUCTURE_TYPE_JUMP))) + return VKD3D_ERROR_OUT_OF_MEMORY; + new_break->u.jump.type = JUMP_BREAK; + new_break->u.jump.target = max_target; + + /* Pointer `selection' could have been invalidated by the append + * operation. */ + selection = &list->structures[pos]; + assert(selection->type == STRUCTURE_TYPE_SELECTION); + + if (if_target == max_target) + --selection->u.selection.if_body.count; + if (else_target == max_target) + --selection->u.selection.else_body.count; + + return VKD3D_OK; +} + static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structure_list *list) { enum vkd3d_result ret; @@ -4299,6 +4364,9 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structur if ((ret = vsir_cfg_synthesize_selections(&structure->u.selection.else_body)) < 0) return ret; + if ((ret = vsir_cfg_move_breaks_out_of_selections(list)) < 0) + return ret; + break; } -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 67 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 60 insertions(+), 7 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 7e43dff39..be5e94220 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3200,6 +3200,9 @@ struct vsir_cfg * block), but we still try to keep `begin' as forward as * possible, to keep the loop scope as small as possible. */ bool synthetic; + /* The number of jump instructions (both conditional and + * unconditional) that target this loop. */ + unsigned int target_count; } *loop_intervals; size_t loop_interval_count, loop_interval_capacity; @@ -3248,6 +3251,7 @@ static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsign interval->begin = begin; interval->end = end; interval->synthetic = synthetic; + interval->target_count = 0; return VKD3D_OK; } @@ -4250,13 +4254,18 @@ fail: return VKD3D_ERROR_OUT_OF_MEMORY; } -static void vsir_cfg_remove_trailing_continue(struct vsir_cfg_structure_list *list, unsigned int target) +static void vsir_cfg_remove_trailing_continue(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *list, unsigned int target) { struct vsir_cfg_structure *last = &list->structures[list->count - 1]; if (last->type == STRUCTURE_TYPE_JUMP && last->u.jump.type == JUMP_CONTINUE && !last->u.jump.condition && last->u.jump.target == target) + { --list->count; + assert(cfg->loop_intervals[target].target_count > 0); + --cfg->loop_intervals[target].target_count; + } } static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_structure_list *list) @@ -4287,7 +4296,8 @@ static struct vsir_cfg_structure *vsir_cfg_get_trailing_break(struct vsir_cfg_st * instructions are continue and continue, or continue and break. But * in practice I don't think those situations can happen given the * previous passes we do on the program, so we don't care. */ -static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_structure_list *list) +static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *list) { struct vsir_cfg_structure *selection, *if_break, *else_break, *new_break; unsigned int if_target, else_target, max_target; @@ -4310,6 +4320,7 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_ return VKD3D_ERROR_OUT_OF_MEMORY; new_break->u.jump.type = JUMP_BREAK; new_break->u.jump.target = max_target; + ++cfg->loop_intervals[max_target].target_count; /* Pointer `selection' could have been invalidated by the append * operation. */ @@ -4317,14 +4328,24 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg_ assert(selection->type == STRUCTURE_TYPE_SELECTION); if (if_target == max_target) + { --selection->u.selection.if_body.count; + assert(cfg->loop_intervals[if_target].target_count > 0); + --cfg->loop_intervals[if_target].target_count; + } + if (else_target == max_target) + { --selection->u.selection.else_body.count; + assert(cfg->loop_intervals[else_target].target_count > 0); + --cfg->loop_intervals[else_target].target_count; + } return VKD3D_OK; } -static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structure_list *list) +static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *list) { enum vkd3d_result ret; size_t i; @@ -4361,10 +4382,10 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg_structur *structure = new_selection; list->count = i + 1; - if ((ret = vsir_cfg_synthesize_selections(&structure->u.selection.else_body)) < 0) + if ((ret = vsir_cfg_synthesize_selections(cfg, &structure->u.selection.else_body)) < 0) return ret; - if ((ret = vsir_cfg_move_breaks_out_of_selections(list)) < 0) + if ((ret = vsir_cfg_move_breaks_out_of_selections(cfg, list)) < 0) return ret; break; @@ -4391,22 +4412,54 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct if (loop_body->count == 0) continue; - vsir_cfg_remove_trailing_continue(loop_body, loop->u.loop.idx); + vsir_cfg_remove_trailing_continue(cfg, loop_body, loop->u.loop.idx); if ((ret = vsir_cfg_optimize_recurse(cfg, loop_body)) < 0) return ret; - if ((ret = vsir_cfg_synthesize_selections(loop_body)) < 0) + if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0) return ret; } return VKD3D_OK; } +static void vsir_cfg_count_targets(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) +{ + size_t i; + + for (i = 0; i < list->count; ++i) + { + struct vsir_cfg_structure *structure = &list->structures[i]; + + switch (structure->type) + { + case STRUCTURE_TYPE_BLOCK: + break; + + case STRUCTURE_TYPE_LOOP: + vsir_cfg_count_targets(cfg, &structure->u.loop.body); + break; + + case STRUCTURE_TYPE_SELECTION: + vsir_cfg_count_targets(cfg, &structure->u.selection.if_body); + vsir_cfg_count_targets(cfg, &structure->u.selection.else_body); + break; + + case STRUCTURE_TYPE_JUMP: + if (structure->u.jump.type == JUMP_BREAK || structure->u.jump.type == JUMP_CONTINUE) + ++cfg->loop_intervals[structure->u.jump.target].target_count; + break; + } + } +} + static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg) { enum vkd3d_result ret; + vsir_cfg_count_targets(cfg, &cfg->structured_program); + ret = vsir_cfg_optimize_recurse(cfg, &cfg->structured_program); if (TRACE_ON()) -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 81 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 79 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index be5e94220..c3a9a6062 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4394,8 +4394,64 @@ static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg, return VKD3D_OK; } +static enum vkd3d_result vsir_cfg_append_loop(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *new_list, struct vsir_cfg_structure *loop) +{ + struct vsir_cfg_structure_list *loop_body = &loop->u.loop.body; + unsigned int target, loop_idx = loop->u.loop.idx; + struct vsir_cfg_structure *trailing_break; + enum vkd3d_result ret; + + trailing_break = vsir_cfg_get_trailing_break(loop_body); + + /* If the loop's last instruction is not a break, we cannot remove + * the loop itself. */ + if (!trailing_break) + { + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) + return ret; + memset(loop, 0, sizeof(*loop)); + return VKD3D_OK; + } + + target = trailing_break->u.jump.target; + assert(cfg->loop_intervals[target].target_count > 0); + + /* If the loop is not targeted by any jump, we can remove it. The + * trailing `break' then targets another loop, so we have to keep + * it. */ + if (cfg->loop_intervals[loop_idx].target_count == 0) + { + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, + &loop_body->structures[0], loop_body->count)) < 0) + return ret; + loop_body->count = 0; + return VKD3D_OK; + } + + /* If the loop is targeted only by its own trailing `break' + * instruction, then we can remove it together with the `break' + * itself. */ + if (target == loop_idx && cfg->loop_intervals[loop_idx].target_count == 1) + { + --cfg->loop_intervals[loop_idx].target_count; + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, + &loop_body->structures[0], loop_body->count - 1)) < 0) + return ret; + loop_body->count = 0; + return VKD3D_OK; + } + + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) + return ret; + memset(loop, 0, sizeof(*loop)); + + return VKD3D_OK; +} + static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) { + struct vsir_cfg_structure_list new_list = {0}; enum vkd3d_result ret; size_t i; @@ -4405,23 +4461,44 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct struct vsir_cfg_structure_list *loop_body; if (loop->type != STRUCTURE_TYPE_LOOP) + { + if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0) + goto fail; + memset(loop, 0, sizeof(*loop)); continue; + } loop_body = &loop->u.loop.body; if (loop_body->count == 0) + { + if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0) + goto fail; + memset(loop, 0, sizeof(*loop)); continue; + } vsir_cfg_remove_trailing_continue(cfg, loop_body, loop->u.loop.idx); if ((ret = vsir_cfg_optimize_recurse(cfg, loop_body)) < 0) - return ret; + goto fail; if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0) - return ret; + goto fail; + + if ((ret = vsir_cfg_append_loop(cfg, &new_list, loop)) < 0) + goto fail; } + vsir_cfg_structure_list_cleanup(list); + *list = new_list; + return VKD3D_OK; + +fail: + vsir_cfg_structure_list_cleanup(list); + + return ret; } static void vsir_cfg_count_targets(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 21 ++++++++++----------- 1 file changed, 10 insertions(+), 11 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index c3a9a6062..0be94def0 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4451,18 +4451,20 @@ static enum vkd3d_result vsir_cfg_append_loop(struct vsir_cfg *cfg, static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) { - struct vsir_cfg_structure_list new_list = {0}; + struct vsir_cfg_structure_list old_list = *list, *new_list = list; enum vkd3d_result ret; size_t i; - for (i = 0; i < list->count; ++i) + memset(new_list, 0, sizeof(*new_list)); + + for (i = 0; i < old_list.count; ++i) { - struct vsir_cfg_structure *loop = &list->structures[i]; + struct vsir_cfg_structure *loop = &old_list.structures[i]; struct vsir_cfg_structure_list *loop_body; if (loop->type != STRUCTURE_TYPE_LOOP) { - if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0) + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) goto fail; memset(loop, 0, sizeof(*loop)); continue; @@ -4472,7 +4474,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct if (loop_body->count == 0) { - if ((ret = vsir_cfg_structure_list_append_from_region(&new_list, loop, 1)) < 0) + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) goto fail; memset(loop, 0, sizeof(*loop)); continue; @@ -4486,17 +4488,14 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0) goto fail; - if ((ret = vsir_cfg_append_loop(cfg, &new_list, loop)) < 0) + if ((ret = vsir_cfg_append_loop(cfg, new_list, loop)) < 0) goto fail; } - vsir_cfg_structure_list_cleanup(list); - *list = new_list; - - return VKD3D_OK; + ret = VKD3D_OK; fail: - vsir_cfg_structure_list_cleanup(list); + vsir_cfg_structure_list_cleanup(&old_list); return ret; } -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 0be94def0..7da37e04b 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4459,7 +4459,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct for (i = 0; i < old_list.count; ++i) { - struct vsir_cfg_structure *loop = &old_list.structures[i]; + struct vsir_cfg_structure *loop = &old_list.structures[i], *selection; struct vsir_cfg_structure_list *loop_body; if (loop->type != STRUCTURE_TYPE_LOOP) @@ -4490,6 +4490,22 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct if ((ret = vsir_cfg_append_loop(cfg, new_list, loop)) < 0) goto fail; + + /* If the last pushed instruction is a selection and one of the branches terminates with a + * `break', start pushing to the other branch, in the hope of eventually push a `break' + * there too and be able to remove a loop. */ + if (new_list->count == 0) + continue; + + selection = &new_list->structures[new_list->count - 1]; + + if (selection->type == STRUCTURE_TYPE_SELECTION) + { + if (vsir_cfg_get_trailing_break(&selection->u.selection.if_body)) + new_list = &selection->u.selection.else_body; + else if (vsir_cfg_get_trailing_break(&selection->u.selection.else_body)) + new_list = &selection->u.selection.if_body; + } } ret = VKD3D_OK; -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/ir.c | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 7da37e04b..a3fae97c8 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4344,6 +4344,25 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg return VKD3D_OK; } +static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections_recursively(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *list) +{ + struct vsir_cfg_structure *trailing; + + if (list->count == 0) + return VKD3D_OK; + + trailing = &list->structures[list->count - 1]; + + if (trailing->type != STRUCTURE_TYPE_SELECTION) + return VKD3D_OK; + + vsir_cfg_move_breaks_out_of_selections_recursively(cfg, &trailing->u.selection.if_body); + vsir_cfg_move_breaks_out_of_selections_recursively(cfg, &trailing->u.selection.else_body); + + return vsir_cfg_move_breaks_out_of_selections(cfg, list); +} + static enum vkd3d_result vsir_cfg_synthesize_selections(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list) { @@ -4508,7 +4527,7 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct } } - ret = VKD3D_OK; + ret = vsir_cfg_move_breaks_out_of_selections_recursively(cfg, list); fail: vsir_cfg_structure_list_cleanup(&old_list); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/773
participants (2)
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)