[PATCH v3 0/3] MR598: vkd3d-shader/ir: Lower monolithic switches to selection ladders.
This is a preliminary pass for the control flow graph structurizer. The plan, at least for the first version of the structurizer, is to have this pass, then another pass that converts all SSA registers to TEMPs (and correspondingly PHI nodes to MOVs/MOVCs), then a simple structurizer based on the so-called Böhm–Jacopini theorem. Some changes to the SPIR-V backend will also be needed, for supporting BOOL TEMP registers and fixing some details of 64 bit types. But this pass is already quite complicated, so large enough for its own MR. -- v3: vkd3d-shader/ir: Fixup PHI nodes when lowering switches to selection ladders. vkd3d-shader/ir: Lower monolithic switches to selection ladders. https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> Instead of crashing. --- libs/vkd3d-shader/spirv.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) diff --git a/libs/vkd3d-shader/spirv.c b/libs/vkd3d-shader/spirv.c index 299b4e965..3ce5d0146 100644 --- a/libs/vkd3d-shader/spirv.c +++ b/libs/vkd3d-shader/spirv.c @@ -7809,7 +7809,10 @@ static void spirv_compiler_emit_branch(struct spirv_compiler *compiler, if (instruction->src_count > 1) { /* Loop merge only. Must have a merge block and a continue block. */ - spirv_compiler_emit_merge(compiler, src[1].reg.idx[0].offset, src[2].reg.idx[0].offset); + if (instruction->src_count == 3) + spirv_compiler_emit_merge(compiler, src[1].reg.idx[0].offset, src[2].reg.idx[0].offset); + else + ERR("Invalid branch with %u sources.\n", instruction->src_count); } vkd3d_spirv_build_op_branch(builder, spirv_compiler_get_label_id(compiler, src[0].reg.idx[0].offset)); return; @@ -7826,8 +7829,11 @@ static void spirv_compiler_emit_branch(struct spirv_compiler *compiler, condition_id = spirv_compiler_emit_int_to_bool(compiler, VKD3D_SHADER_CONDITIONAL_OP_NZ, src[0].reg.data_type, 1, condition_id); /* Emit the merge immediately before the branch instruction. */ - spirv_compiler_emit_merge(compiler, src[3].reg.idx[0].offset, - (instruction->src_count > 4) ? src[4].reg.idx[0].offset : 0); + if (instruction->src_count >= 4) + spirv_compiler_emit_merge(compiler, src[3].reg.idx[0].offset, + (instruction->src_count > 4) ? src[4].reg.idx[0].offset : 0); + else + ERR("Invalid branch with %u sources.\n", instruction->src_count); vkd3d_spirv_build_op_branch_conditional(builder, condition_id, spirv_compiler_get_label_id(compiler, src[1].reg.idx[0].offset), spirv_compiler_get_label_id(compiler, src[2].reg.idx[0].offset)); -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> PHI nodes must be fixed up after this pass, because the block references might have become broken. For simplicitly this is not handled yet. The goal for this pass is to make the CFG structurizer simpler, because only conditional and unconditional branches must be supported. Eventually this limitation might be lifted if there is advantage in doing so. --- libs/vkd3d-shader/ir.c | 149 ++++++++++++++++++++++- libs/vkd3d-shader/vkd3d_shader_private.h | 2 + 2 files changed, 150 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 45ccea45f..4f1ffd3c6 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -442,6 +442,15 @@ void vsir_src_param_init(struct vkd3d_shader_src_param *param, enum vkd3d_shader param->modifiers = VKD3DSPSM_NONE; } +void vsir_dst_param_init(struct vkd3d_shader_dst_param *param, enum vkd3d_shader_register_type reg_type, + enum vkd3d_data_type data_type, unsigned int idx_count) +{ + vsir_register_init(¶m->reg, reg_type, data_type, idx_count); + param->write_mask = VKD3DSP_WRITEMASK_0; + param->modifiers = VKD3DSPDM_NONE; + param->shift = 0; +} + void vsir_src_param_init_label(struct vkd3d_shader_src_param *param, unsigned int label_id) { vsir_src_param_init(param, VKD3DSPR_LABEL, VKD3D_DATA_UINT, 1); @@ -449,6 +458,18 @@ void vsir_src_param_init_label(struct vkd3d_shader_src_param *param, unsigned in param->reg.idx[0].offset = label_id; } +static void src_param_init_ssa_uint(struct vkd3d_shader_src_param *src, unsigned int idx) +{ + vsir_src_param_init(src, VKD3DSPR_SSA, VKD3D_DATA_UINT, 1); + src->reg.idx[0].offset = idx; +} + +static void dst_param_init_ssa_uint(struct vkd3d_shader_dst_param *dst, unsigned int idx) +{ + vsir_dst_param_init(dst, VKD3DSPR_SSA, VKD3D_DATA_UINT, 1); + dst->reg.idx[0].offset = idx; +} + void vsir_instruction_init(struct vkd3d_shader_instruction *ins, const struct vkd3d_shader_location *location, enum vkd3d_shader_opcode handler_idx) { @@ -2350,6 +2371,127 @@ static enum vkd3d_result flatten_control_flow_constructs(struct vkd3d_shader_par return result; } +static unsigned int label_from_src_param(const struct vkd3d_shader_src_param *param) +{ + assert(param->reg.type == VKD3DSPR_LABEL); + return param->reg.idx[0].offset; +} + +static bool reserve_instructions(struct vkd3d_shader_instruction **instructions, size_t *capacity, size_t count) +{ + if (!vkd3d_array_reserve((void **)instructions, capacity, count, sizeof(**instructions))) + { + ERR("Failed to allocate instructions.\n"); + return false; + } + + return true; +} + +static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *parser) +{ + unsigned int block_count = parser->program.block_count, ssa_count = parser->program.ssa_count; + struct vkd3d_shader_instruction *instructions = NULL; + size_t ins_capacity = 0, ins_count = 0, i; + + if (!reserve_instructions(&instructions, &ins_capacity, parser->program.instructions.count)) + goto fail; + + for (i = 0; i < parser->program.instructions.count; ++i) + { + struct vkd3d_shader_instruction *ins = &parser->program.instructions.elements[i]; + unsigned int case_count, j, default_label; + + switch (ins->handler_idx) + { + case VKD3DSIH_SWITCH_MONOLITHIC: + break; + + case VKD3DSIH_PHI: + WARN("Unhandled PHI when lowering switch.\n"); + vkd3d_shader_parser_error(parser, VKD3D_SHADER_ERROR_VSIR_NOT_IMPLEMENTED, + "Unhandled PHI when lowering switch."); + return VKD3D_ERROR_NOT_IMPLEMENTED; + + default: + if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1)) + goto fail; + instructions[ins_count++] = *ins; + continue; + } + + case_count = (ins->src_count - 3) / 2; + default_label = label_from_src_param(&ins->src[1]); + + /* In principle we can have a switch with no cases, and we + * just have to jump to the default label. */ + if (case_count == 0) + { + if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1)) + goto fail; + + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_BRANCH, 0, 1)) + goto fail; + vsir_src_param_init_label(&instructions[ins_count].src[0], default_label); + ++ins_count; + } + + if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 3 * case_count - 1)) + goto fail; + + for (j = 0; j < case_count; ++j) + { + unsigned int fallthrough_label, case_label = label_from_src_param(&ins->src[3 + 2 * j + 1]); + + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_IEQ, 1, 2)) + goto fail; + dst_param_init_ssa_uint(&instructions[ins_count].dst[0], ssa_count); + instructions[ins_count].src[0] = ins->src[0]; + instructions[ins_count].src[1] = ins->src[3 + 2 * j]; + ++ins_count; + + /* For all cases except the last one we fall through to + * the following case; the last one has to jump to the + * default label. */ + if (j == case_count - 1) + fallthrough_label = default_label; + else + fallthrough_label = block_count + 1; + + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_BRANCH, 0, 3)) + goto fail; + src_param_init_ssa_uint(&instructions[ins_count].src[0], ssa_count); + vsir_src_param_init_label(&instructions[ins_count].src[1], case_label); + vsir_src_param_init_label(&instructions[ins_count].src[2], fallthrough_label); + ++ins_count; + + ++ssa_count; + + if (j != case_count - 1) + { + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_LABEL, 0, 1)) + goto fail; + vsir_src_param_init_label(&instructions[ins_count].src[0], ++block_count); + ++ins_count; + } + } + } + + vkd3d_free(parser->program.instructions.elements); + parser->program.instructions.elements = instructions; + parser->program.instructions.capacity = ins_capacity; + parser->program.instructions.count = ins_count; + parser->program.block_count = block_count; + parser->program.ssa_count = ssa_count; + + return VKD3D_OK; + +fail: + vkd3d_free(instructions); + + 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) { @@ -2361,7 +2503,12 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, if ((result = instruction_array_lower_texkills(parser)) < 0) return result; - if (!parser->shader_desc.is_dxil) + if (parser->shader_desc.is_dxil) + { + if ((result = lower_switch_to_if_ladder(parser)) < 0) + return result; + } + else { if (parser->program.shader_version.type != VKD3D_SHADER_TYPE_PIXEL) { diff --git a/libs/vkd3d-shader/vkd3d_shader_private.h b/libs/vkd3d-shader/vkd3d_shader_private.h index 51daf2153..6e58525ff 100644 --- a/libs/vkd3d-shader/vkd3d_shader_private.h +++ b/libs/vkd3d-shader/vkd3d_shader_private.h @@ -892,6 +892,8 @@ struct vkd3d_shader_src_param void vsir_src_param_init(struct vkd3d_shader_src_param *param, enum vkd3d_shader_register_type reg_type, enum vkd3d_data_type data_type, unsigned int idx_count); +void vsir_dst_param_init(struct vkd3d_shader_dst_param *param, enum vkd3d_shader_register_type reg_type, + enum vkd3d_data_type data_type, unsigned int idx_count); void vsir_src_param_init_label(struct vkd3d_shader_src_param *param, unsigned int label_id); struct vkd3d_shader_index_range -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598
From: Giovanni Mascellani <gmascellani(a)codeweavers.com> A map between the blocks before and after the pass is built and then used to fix the PHI nodes. --- libs/vkd3d-shader/ir.c | 158 ++++++++++++++++++++++++++++++++++++++--- 1 file changed, 149 insertions(+), 9 deletions(-) diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 4f1ffd3c6..00234d660 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -2388,15 +2388,47 @@ static bool reserve_instructions(struct vkd3d_shader_instruction **instructions, return true; } +/* A record represents replacing a jump from block `switch_label' to + * block `target_label' with a jump from block `if_label' to block + * `target_label'. */ +struct lower_switch_to_if_ladder_block_mapping +{ + unsigned int switch_label; + unsigned int if_label; + unsigned int target_label; +}; + +static bool lower_switch_to_if_ladder_add_block_mapping(struct lower_switch_to_if_ladder_block_mapping **block_map, + size_t *map_capacity, size_t *map_count, unsigned int switch_label, unsigned int if_label, unsigned int target_label) +{ + if (!vkd3d_array_reserve((void **)block_map, map_capacity, *map_count + 1, sizeof(**block_map))) + { + ERR("Failed to allocate block mapping.\n"); + return false; + } + + (*block_map)[*map_count].switch_label = switch_label; + (*block_map)[*map_count].if_label = if_label; + (*block_map)[*map_count].target_label = target_label; + + *map_count += 1; + + return true; +} + static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *parser) { - unsigned int block_count = parser->program.block_count, ssa_count = parser->program.ssa_count; + unsigned int block_count = parser->program.block_count, ssa_count = parser->program.ssa_count, current_label = 0, if_label; + size_t ins_capacity = 0, ins_count = 0, i, map_capacity = 0, map_count = 0; struct vkd3d_shader_instruction *instructions = NULL; - size_t ins_capacity = 0, ins_count = 0, i; + struct lower_switch_to_if_ladder_block_mapping *block_map = NULL; if (!reserve_instructions(&instructions, &ins_capacity, parser->program.instructions.count)) goto fail; + /* First subpass: convert SWITCH_MONOLITHIC instructions to + * selection ladders, keeping a map between blocks before and + * after the subpass. */ for (i = 0; i < parser->program.instructions.count; ++i) { struct vkd3d_shader_instruction *ins = &parser->program.instructions.elements[i]; @@ -2404,15 +2436,16 @@ static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *p switch (ins->handler_idx) { + case VKD3DSIH_LABEL: + current_label = label_from_src_param(&ins->src[0]); + if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1)) + goto fail; + instructions[ins_count++] = *ins; + continue; + case VKD3DSIH_SWITCH_MONOLITHIC: break; - case VKD3DSIH_PHI: - WARN("Unhandled PHI when lowering switch.\n"); - vkd3d_shader_parser_error(parser, VKD3D_SHADER_ERROR_VSIR_NOT_IMPLEMENTED, - "Unhandled PHI when lowering switch."); - return VKD3D_ERROR_NOT_IMPLEMENTED; - default: if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1)) goto fail; @@ -2439,6 +2472,8 @@ static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *p if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 3 * case_count - 1)) goto fail; + if_label = current_label; + for (j = 0; j < case_count; ++j) { unsigned int fallthrough_label, case_label = label_from_src_param(&ins->src[3 + 2 * j + 1]); @@ -2467,17 +2502,121 @@ static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *p ++ssa_count; - if (j != case_count - 1) + if (!lower_switch_to_if_ladder_add_block_mapping(&block_map, &map_capacity, &map_count, + current_label, if_label, case_label)) + goto fail; + + if (j == case_count - 1) + { + if (!lower_switch_to_if_ladder_add_block_mapping(&block_map, &map_capacity, &map_count, + current_label, if_label, default_label)) + goto fail; + } + else { if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_LABEL, 0, 1)) goto fail; vsir_src_param_init_label(&instructions[ins_count].src[0], ++block_count); ++ins_count; + + if_label = block_count; } } } + /* Second subpass: creating new blocks might have broken + * references in PHI instructions, so we use the block map to fix + * them. */ + current_label = 0; + for (i = 0; i < ins_count; ++i) + { + struct vkd3d_shader_instruction *ins = &instructions[i]; + struct vkd3d_shader_src_param *new_src; + unsigned int j, l, new_src_count = 0; + + switch (ins->handler_idx) + { + case VKD3DSIH_LABEL: + current_label = label_from_src_param(&ins->src[0]); + continue; + + case VKD3DSIH_PHI: + break; + + default: + continue; + } + + /* First count how many source parameters we need. */ + for (j = 0; j < ins->src_count; j += 2) + { + unsigned int source_label = label_from_src_param(&ins->src[j + 1]); + size_t k, match_count = 0; + + for (k = 0; k < map_count; ++k) + { + struct lower_switch_to_if_ladder_block_mapping *mapping = &block_map[k]; + + if (mapping->switch_label == source_label && mapping->target_label == current_label) + match_count += 1; + } + + new_src_count += (match_count != 0) ? 2 * match_count : 2; + } + + assert(new_src_count >= ins->src_count); + + /* Allocate more source parameters if needed. */ + if (new_src_count == ins->src_count) + { + new_src = ins->src; + } + else + { + if (!(new_src = shader_parser_get_src_params(parser, new_src_count))) + { + ERR("Failed to allocate %u source parameters.\n", new_src_count); + goto fail; + } + } + + /* Then do the copy. */ + for (j = 0, l = 0; j < ins->src_count; j += 2) + { + unsigned int source_label = label_from_src_param(&ins->src[j + 1]); + size_t k, match_count = 0; + + for (k = 0; k < map_count; ++k) + { + struct lower_switch_to_if_ladder_block_mapping *mapping = &block_map[k]; + + if (mapping->switch_label == source_label && mapping->target_label == current_label) + { + match_count += 1; + + new_src[l] = ins->src[j]; + new_src[l + 1] = ins->src[j + 1]; + new_src[l + 1].reg.idx[0].offset = mapping->if_label; + l += 2; + } + } + + if (match_count == 0) + { + new_src[l] = ins->src[j]; + new_src[l + 1] = ins->src[j + 1]; + l += 2; + } + } + + assert(l == new_src_count); + + ins->src_count = new_src_count; + ins->src = new_src; + } + vkd3d_free(parser->program.instructions.elements); + vkd3d_free(block_map); parser->program.instructions.elements = instructions; parser->program.instructions.capacity = ins_capacity; parser->program.instructions.count = ins_count; @@ -2488,6 +2627,7 @@ static enum vkd3d_result lower_switch_to_if_ladder(struct vkd3d_shader_parser *p fail: vkd3d_free(instructions); + vkd3d_free(block_map); return VKD3D_ERROR_OUT_OF_MEMORY; } -- GitLab https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598
Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/ir.c:
+ goto fail; + } + else { if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_LABEL, 0, 1)) goto fail; vsir_src_param_init_label(&instructions[ins_count].src[0], ++block_count); ++ins_count; + + if_label = block_count; } } }
+ /* Second subpass: creating new blocks might have broken + * references in PHI instructions, so we use the block map to fix Do validation failures occur without this? AFAIK it's still valid to have a `phi` incoming from the original `switch` block. If block `1` contained the `switch`, block `5` is a switch case, and the conditional branch to `5` could instead branch to a new label `11`, we can still have incomings from `1` and `5`. If control flowed through `5` it gets the second value, otherwise it get the first.
-- https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598#note_58991
Conor McCarthy (@cmccarthy) commented about libs/vkd3d-shader/ir.c:
+ goto fail; + + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_BRANCH, 0, 1)) + goto fail; + vsir_src_param_init_label(&instructions[ins_count].src[0], default_label); + ++ins_count; + } + + if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 3 * case_count - 1)) + goto fail; + + for (j = 0; j < case_count; ++j) + { + unsigned int fallthrough_label, case_label = label_from_src_param(&ins->src[3 + 2 * j + 1]); + + if (!vsir_instruction_init_with_params(parser, &instructions[ins_count], &ins->location, VKD3DSIH_IEQ, 1, 2)) While `bool` conditions are not yet implemented for `VKD3DSIH_BRANCH`, perhaps this is a good time to add the `if (src[0].reg.data_type != VKD3D_DATA_BOOL)` to `spirv_compiler_emit_branch()` and use bool here, since we'll need it elsewhere anyway, and it avoids bool-to-int and int-to-bool spam.
-- https://gitlab.winehq.org/wine/vkd3d/-/merge_requests/598#note_58992
participants (3)
-
Conor McCarthy (＠cmccarthy) -
Giovanni Mascellani
-
Giovanni Mascellani (＠giomasce)