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.
-- v4: vkd3d-shader/ir: Fixup PHI nodes when lowering switches to selection ladders. vkd3d-shader/ir: Lower monolithic switches to selection ladders.
From: Giovanni Mascellani gmascellani@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));
From: Giovanni Mascellani gmascellani@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/spirv.c | 5 +- libs/vkd3d-shader/vkd3d_shader_private.h | 2 + 3 files changed, 153 insertions(+), 3 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 45ccea45f..3d1702f40 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_bool(struct vkd3d_shader_src_param *src, unsigned int idx) +{ + vsir_src_param_init(src, VKD3DSPR_SSA, VKD3D_DATA_BOOL, 1); + src->reg.idx[0].offset = idx; +} + +static void dst_param_init_ssa_bool(struct vkd3d_shader_dst_param *dst, unsigned int idx) +{ + vsir_dst_param_init(dst, VKD3DSPR_SSA, VKD3D_DATA_BOOL, 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_bool(&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_bool(&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/spirv.c b/libs/vkd3d-shader/spirv.c index 3ce5d0146..022df995e 100644 --- a/libs/vkd3d-shader/spirv.c +++ b/libs/vkd3d-shader/spirv.c @@ -7826,8 +7826,9 @@ static void spirv_compiler_emit_branch(struct spirv_compiler *compiler, }
condition_id = spirv_compiler_emit_load_src(compiler, &src[0], VKD3DSP_WRITEMASK_0); - condition_id = spirv_compiler_emit_int_to_bool(compiler, - VKD3D_SHADER_CONDITIONAL_OP_NZ, src[0].reg.data_type, 1, condition_id); + if (src[0].reg.data_type != VKD3D_DATA_BOOL) + 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. */ if (instruction->src_count >= 4) spirv_compiler_emit_merge(compiler, src[3].reg.idx[0].offset, 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
From: Giovanni Mascellani gmascellani@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 3d1702f40..466730cc7 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; }
On Thu Jan 25 14:58:17 2024 +0000, Conor McCarthy wrote:
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.
Right now if I disable this I get failures in the following pass to materialize SSAs to TEMPs, precisely because a PHI node misses a reference to one of its own immediate predecessors. I've seen this happening only with cases that have no code (i.e., `case 3: break;`), for which DXC generates a jump directly to the merge block. So the merge block has the switch block as predecessor, and then PHI nodes there must be fixed up.
On Thu Jan 25 14:58:48 2024 +0000, Conor McCarthy wrote:
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.
Should be done in the latest revision, if I understand what you meant.
This merge request was approved by Giovanni Mascellani.
This merge request was approved by Conor McCarthy.
This merge request was approved by Henri Verbeet.
-
Conor McCarthy (＠cmccarthy) -
Giovanni Mascellani
-
Giovanni Mascellani (＠giomasce)
-
Henri Verbeet (＠hverbeet)