[PATCH 0/6] MR785: Draft: vkd3d-shader/ir: Only emit trampolines and launchers when needed.
This goes atop !773. The last three commits belong to this MR.
Trampolines and launchers allow us to handle code doing multilevel jumps, but they partially virtualize the control flow, which potentially makes the jobs of downstream compilers harder. So we avoid them every time we can.
From: Giovanni Mascellani gmascellani@codeweavers.com
--- libs/vkd3d-shader/ir.c | 33 ++++++++++++++++----------------- 1 file changed, 16 insertions(+), 17 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index e0928ff78..da23e2288 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4307,19 +4307,21 @@ 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) - goto fail; + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) + goto out; memset(loop, 0, sizeof(*loop)); continue; } @@ -4328,8 +4330,8 @@ 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) - goto fail; + if ((ret = vsir_cfg_structure_list_append_from_region(new_list, loop, 1)) < 0) + goto out; memset(loop, 0, sizeof(*loop)); continue; } @@ -4337,22 +4339,19 @@ static enum vkd3d_result vsir_cfg_optimize_recurse(struct vsir_cfg *cfg, struct vsir_cfg_remove_trailing_continue(cfg, loop_body, loop->u.loop.idx);
if ((ret = vsir_cfg_optimize_recurse(cfg, loop_body)) < 0) - goto fail; + goto out;
if ((ret = vsir_cfg_synthesize_selections(cfg, loop_body)) < 0) - goto fail; + goto out;
- if ((ret = vsir_cfg_append_loop(cfg, &new_list, loop)) < 0) - goto fail; + if ((ret = vsir_cfg_append_loop(cfg, new_list, loop)) < 0) + goto out; }
- vsir_cfg_structure_list_cleanup(list); - *list = new_list; + ret = VKD3D_OK;
- return VKD3D_OK; - -fail: - vsir_cfg_structure_list_cleanup(list); +out: + vsir_cfg_structure_list_cleanup(&old_list);
return ret; }
From: Giovanni Mascellani gmascellani@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 da23e2288..a95882797 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4315,7 +4315,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) @@ -4346,6 +4346,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 out; + + /* 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;
From: Giovanni Mascellani gmascellani@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 a95882797..6d428e22a 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4200,6 +4200,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) { @@ -4364,7 +4383,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);
out: vsir_cfg_structure_list_cleanup(&old_list);
From: Giovanni Mascellani gmascellani@codeweavers.com
--- libs/vkd3d-shader/ir.c | 11 +++++++++++ 1 file changed, 11 insertions(+)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 6d428e22a..e57f67bb2 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -4197,6 +4197,17 @@ static enum vkd3d_result vsir_cfg_move_breaks_out_of_selections(struct vsir_cfg --cfg->loop_intervals[else_target].target_count; }
+ /* If a branch becomes empty, make it the else branch, so we save a block. */ + if (selection->u.selection.if_body.count == 0) + { + struct vsir_cfg_structure_list tmp; + + selection->u.selection.invert_condition = !selection->u.selection.invert_condition; + tmp = selection->u.selection.if_body; + selection->u.selection.if_body = selection->u.selection.else_body; + selection->u.selection.else_body = tmp; + } + return VKD3D_OK; }
From: Giovanni Mascellani gmascellani@codeweavers.com
--- libs/vkd3d-shader/ir.c | 54 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 52 insertions(+), 2 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index e57f67bb2..d1c555dc0 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -2921,6 +2921,8 @@ struct vsir_cfg_structure { struct vsir_cfg_structure_list body; unsigned idx; + bool needs_trampoline; + struct vsir_cfg_structure *outer_loop; } loop; struct { @@ -3187,7 +3189,8 @@ static void vsir_cfg_structure_dump(struct vsir_cfg *cfg, struct vsir_cfg_struct
vsir_cfg_structure_list_dump(cfg, &structure->u.loop.body);
- TRACE("%s} # %u\n", cfg->debug_buffer.buffer, structure->u.loop.idx); + TRACE("%s} # %u%s\n", cfg->debug_buffer.buffer, structure->u.loop.idx, + structure->u.loop.needs_trampoline ? ", tramp" : ""); break;
case STRUCTURE_TYPE_SELECTION: @@ -4432,6 +4435,51 @@ static void vsir_cfg_count_targets(struct vsir_cfg *cfg, struct vsir_cfg_structu } }
+/* Trampolines are code gadgets used to emulate multilevel jumps (which are not natively supported + * by SPIR-V). A trampoline is inserted just after a loop and checks whether control has reached the + * intended site (i.e., we just jumped out of the target block) or if other levels of jumping are + * needed. For each jump a trampoline is required for all the loops between the jump itself and the + * target loop, excluding the target loop itself. */ +static void vsir_cfg_mark_trampolines(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list, + struct vsir_cfg_structure *loop) +{ + 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: + structure->u.loop.outer_loop = loop; + vsir_cfg_mark_trampolines(cfg, &structure->u.loop.body, structure); + break; + + case STRUCTURE_TYPE_SELECTION: + vsir_cfg_mark_trampolines(cfg, &structure->u.selection.if_body, loop); + vsir_cfg_mark_trampolines(cfg, &structure->u.selection.else_body, loop); + break; + + case STRUCTURE_TYPE_JUMP: + { + struct vsir_cfg_structure *l; + if (structure->u.jump.type != JUMP_BREAK && structure->u.jump.type != JUMP_CONTINUE) + break; + for (l = loop; l && l->u.loop.idx != structure->u.jump.target; l = l->u.loop.outer_loop) + { + assert(l->type == STRUCTURE_TYPE_LOOP); + l->u.loop.needs_trampoline = true; + } + break; + } + } + } +} + static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg) { enum vkd3d_result ret; @@ -4440,6 +4488,8 @@ static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg)
ret = vsir_cfg_optimize_recurse(cfg, &cfg->structured_program);
+ vsir_cfg_mark_trampolines(cfg, &cfg->structured_program, NULL); + if (TRACE_ON()) vsir_cfg_dump_structured_program(cfg);
@@ -4489,7 +4539,7 @@ static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg,
/* Add a trampoline to implement multilevel jumping depending on the stored * jump_target value. */ - if (loop_idx != UINT_MAX) + if (structure->u.loop.needs_trampoline) { /* If the multilevel jump is a `continue' and the target is the loop we're inside * right now, then we can finally do the `continue'. */
From: Giovanni Mascellani gmascellani@codeweavers.com
--- libs/vkd3d-shader/ir.c | 53 +++++++++++++++++++++++++++++++++++++++--- 1 file changed, 50 insertions(+), 3 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index d1c555dc0..f7de7cc1d 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -2945,6 +2945,7 @@ struct vsir_cfg_structure unsigned int target; struct vkd3d_shader_src_param *condition; bool invert_condition; + bool needs_launcher; } jump; } u; }; @@ -3234,8 +3235,9 @@ static void vsir_cfg_structure_dump(struct vsir_cfg *cfg, struct vsir_cfg_struct vkd3d_unreachable(); }
- TRACE("%s%s%s %u\n", cfg->debug_buffer.buffer, type_str, - structure->u.jump.condition ? "c" : "", structure->u.jump.target); + TRACE("%s%s%s %u%s\n", cfg->debug_buffer.buffer, type_str, + structure->u.jump.condition ? "c" : "", structure->u.jump.target, + structure->u.jump.needs_launcher ? " # launch" : ""); break; }
@@ -4480,6 +4482,45 @@ static void vsir_cfg_mark_trampolines(struct vsir_cfg *cfg, struct vsir_cfg_stru } }
+/* Launchers are the counterpart of trampolines. A launcher is inserted just before a jump, and + * writes in a well-known variable what is the target of the jump. Trampolines will then read that + * variable to decide how to redirect the jump to its intended target. A launcher is needed each + * time the innermost loop containing the jump itself has a trampoline (independently of whether the + * jump is targeting that loop or not). */ +static void vsir_cfg_mark_launchers(struct vsir_cfg *cfg, struct vsir_cfg_structure_list *list, + struct vsir_cfg_structure *loop) +{ + 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_mark_launchers(cfg, &structure->u.loop.body, structure); + break; + + case STRUCTURE_TYPE_SELECTION: + vsir_cfg_mark_launchers(cfg, &structure->u.selection.if_body, loop); + vsir_cfg_mark_launchers(cfg, &structure->u.selection.else_body, loop); + break; + + case STRUCTURE_TYPE_JUMP: + if (structure->u.jump.type != JUMP_BREAK && structure->u.jump.type != JUMP_CONTINUE) + break; + assert(loop && loop->type == STRUCTURE_TYPE_LOOP); + if (loop->u.loop.needs_trampoline) + structure->u.jump.needs_launcher = true; + break; + } + } +} + static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg) { enum vkd3d_result ret; @@ -4488,7 +4529,13 @@ static enum vkd3d_result vsir_cfg_optimize(struct vsir_cfg *cfg)
ret = vsir_cfg_optimize_recurse(cfg, &cfg->structured_program);
+ /* Trampolines and launchers cannot be marked with the same pass, + * because a jump might have to be marked as launcher even when it + * targets its innermost loop, if other jumps in the same loop + * need a trampoline anyway. So launchers can be discovered only + * once all the trampolines are known. */ vsir_cfg_mark_trampolines(cfg, &cfg->structured_program, NULL); + vsir_cfg_mark_launchers(cfg, &cfg->structured_program, NULL);
if (TRACE_ON()) vsir_cfg_dump_structured_program(cfg); @@ -4665,7 +4712,7 @@ static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg, if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 2)) return VKD3D_ERROR_OUT_OF_MEMORY;
- if (opcode == VKD3DSIH_BREAK || opcode == VKD3DSIH_BREAKP) + if (structure->u.jump.needs_launcher) { if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], &no_loc, VKD3DSIH_MOV, 1, 1))
This merge request was approved by Giovanni Mascellani.
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)