~~This applies on top of !704, the last two commits belong here.~~
Here we finally emit the structured program, replacing the older simple structurizer. The advantage of the new structurizer is that the CFG if statically described in the generated program, without having to trace the value of a variable. Upcoming MRs will make the CFG even simpler, easier to read and hopefully to optimize for downstream compilers.
From: Giovanni Mascellani gmascellani@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 759c89957..5d3f6f910 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3129,6 +3129,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; @@ -3174,6 +3241,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) @@ -3188,6 +3257,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); @@ -3903,6 +3974,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) { @@ -3947,6 +4082,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 ff361a2bb..120243064 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 ba018070f..f973bc64d 100644 --- a/libs/vkd3d-shader/vkd3d_shader_private.h +++ b/libs/vkd3d-shader/vkd3d_shader_private.h @@ -1413,6 +1413,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);
From: Giovanni Mascellani gmascellani@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 5d3f6f910..7cf232bf4 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3144,6 +3144,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 { @@ -3153,6 +3158,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; };
@@ -3974,6 +3994,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; @@ -3988,6 +4072,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); @@ -4011,9 +4096,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)
From: Giovanni Mascellani gmascellani@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 7cf232bf4..1b0760ed2 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3366,6 +3366,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) { @@ -4192,6 +4262,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;
From: Giovanni Mascellani gmascellani@codeweavers.com
Multilevel jumps are not supported yet, and trigger a fallback to the simple structurizer. --- libs/vkd3d-shader/ir.c | 150 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 147 insertions(+), 3 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 1b0760ed2..50ab7e550 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -3263,6 +3263,9 @@ struct vsir_cfg size_t loop_interval_count, loop_interval_capacity;
struct vsir_cfg_structure_list structured_program; + + struct vkd3d_shader_instruction *instructions; + size_t ins_capacity, ins_count; };
static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -4275,6 +4278,136 @@ fail: return VKD3D_ERROR_OUT_OF_MEMORY; }
+static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg, + struct vsir_cfg_structure_list *list, unsigned int loop_idx) +{ + const struct vkd3d_shader_location no_loc = {0}; + enum vkd3d_result ret; + 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: + { + struct vsir_block *block = structure->u.block; + + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + (block->end - block->begin))) + return VKD3D_ERROR_OUT_OF_MEMORY; + + memcpy(&cfg->instructions[cfg->ins_count], block->begin, (char *)block->end - (char *)block->begin); + + cfg->ins_count += block->end - block->begin; + break; + } + + case STRUCTURE_TYPE_LOOP: + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + vsir_instruction_init(&cfg->instructions[cfg->ins_count++], &no_loc, VKD3DSIH_LOOP); + + if ((ret = vsir_cfg_structure_list_emit(cfg, &structure->u.loop.body, structure->u.loop.idx)) < 0) + return ret; + + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + vsir_instruction_init(&cfg->instructions[cfg->ins_count++], &no_loc, VKD3DSIH_ENDLOOP); + break; + + case STRUCTURE_TYPE_JUMP: + { + enum vkd3d_shader_opcode opcode; + + if (structure->u.jump.target != loop_idx) + { + WARN("Multilevel jumps are not supported yet, falling back to the simple structurizer.\n"); + return VKD3D_ERROR_NOT_IMPLEMENTED; + } + + switch (structure->u.jump.type) + { + case JUMP_BREAK: + opcode = structure->u.jump.condition ? VKD3DSIH_BREAKP : VKD3DSIH_BREAK; + break; + + case JUMP_CONTINUE: + opcode = structure->u.jump.condition ? VKD3DSIH_CONTINUEP : VKD3DSIH_CONTINUE; + break; + + case JUMP_RET: + assert(!structure->u.jump.condition); + opcode = VKD3DSIH_RET; + break; + + default: + vkd3d_unreachable(); + } + + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, opcode, 0, !!structure->u.jump.condition)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + if (structure->u.jump.invert_condition) + cfg->instructions[cfg->ins_count].flags |= VKD3D_SHADER_CONDITIONAL_OP_Z; + + if (structure->u.jump.condition) + cfg->instructions[cfg->ins_count].src[0] = *structure->u.jump.condition; + + ++cfg->ins_count; + break; + } + + default: + vkd3d_unreachable(); + } + } + + return VKD3D_OK; +} + +static enum vkd3d_result vsir_cfg_emit_structured_program(struct vsir_cfg *cfg) +{ + enum vkd3d_result ret; + size_t i; + + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->program->instructions.count)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + /* Copy declarations until the first block. */ + for (i = 0; i < cfg->program->instructions.count; ++i) + { + struct vkd3d_shader_instruction *ins = &cfg->program->instructions.elements[i]; + + if (ins->handler_idx == VKD3DSIH_LABEL) + break; + + cfg->instructions[cfg->ins_count++] = *ins; + } + + if ((ret = vsir_cfg_structure_list_emit(cfg, &cfg->structured_program, UINT_MAX)) < 0) + goto fail; + + vkd3d_free(cfg->program->instructions.elements); + cfg->program->instructions.elements = cfg->instructions; + cfg->program->instructions.capacity = cfg->ins_capacity; + cfg->program->instructions.count = cfg->ins_count; + + return VKD3D_OK; + +fail: + vkd3d_free(cfg->instructions); + + return ret; +} + enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, const struct vkd3d_shader_compile_info *compile_info) { @@ -4325,10 +4458,21 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser, return result; }
- if ((result = simple_structurizer_run(parser)) < 0) + if ((result = vsir_cfg_emit_structured_program(&cfg)) < 0) { - vsir_cfg_cleanup(&cfg); - return result; + if (result == VKD3D_ERROR_NOT_IMPLEMENTED) + { + if ((result = simple_structurizer_run(parser)) < 0) + { + vsir_cfg_cleanup(&cfg); + return result; + } + } + else + { + vsir_cfg_cleanup(&cfg); + return result; + } }
vsir_cfg_cleanup(&cfg);
From: Giovanni Mascellani gmascellani@codeweavers.com
The new structurizer therefore reaches feature parity with the older simple one, except for a couple of points:
* the old structurizer accepts any CFG, without requiring reducibilty; however, the DXIL specification requires the CFG to be reducible anyway, so we're not really losing anything;
* the new structurizer additionally requires that no block has two incoming back arrows; AFAIK this is condition that can happen, but in practice it seems to be rare; also, it's not hard to add support for it, as soon as it is decided it is useful.
Taking these considerations into account, the old structurizer is considered superseded and is therefore removed. --- libs/vkd3d-shader/ir.c | 256 ++++++++++++++++++----------------------- 1 file changed, 112 insertions(+), 144 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c index 50ab7e550..b2a5de199 100644 --- a/libs/vkd3d-shader/ir.c +++ b/libs/vkd3d-shader/ir.c @@ -467,12 +467,24 @@ static void src_param_init_ssa_bool(struct vkd3d_shader_src_param *src, unsigned src->reg.idx[0].offset = idx; }
+static void src_param_init_temp_bool(struct vkd3d_shader_src_param *src, unsigned int idx) +{ + vsir_src_param_init(src, VKD3DSPR_TEMP, 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; }
+static void dst_param_init_temp_bool(struct vkd3d_shader_dst_param *dst, unsigned int idx) +{ + vsir_dst_param_init(dst, VKD3DSPR_TEMP, VKD3D_DATA_BOOL, 1); + dst->reg.idx[0].offset = idx; +} + static void dst_param_init_temp_uint(struct vkd3d_shader_dst_param *dst, unsigned int idx) { vsir_dst_param_init(dst, VKD3DSPR_TEMP, VKD3D_DATA_UINT, 1); @@ -2900,125 +2912,6 @@ fail: return VKD3D_ERROR_OUT_OF_MEMORY; }
-static enum vkd3d_result simple_structurizer_run(struct vkd3d_shader_parser *parser) -{ - const unsigned int block_temp_idx = parser->program.temp_count; - struct vkd3d_shader_instruction *instructions = NULL; - const struct vkd3d_shader_location no_loc = {0}; - size_t ins_capacity = 0, ins_count = 0, i; - bool first_label_found = false; - - 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]; - - switch (ins->handler_idx) - { - case VKD3DSIH_PHI: - case VKD3DSIH_SWITCH_MONOLITHIC: - vkd3d_unreachable(); - - case VKD3DSIH_LABEL: - if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 4)) - goto fail; - - if (!first_label_found) - { - first_label_found = true; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_MOV, 1, 1)) - goto fail; - dst_param_init_temp_uint(&instructions[ins_count].dst[0], block_temp_idx); - src_param_init_const_uint(&instructions[ins_count].src[0], label_from_src_param(&ins->src[0])); - ins_count++; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_LOOP, 0, 0)) - goto fail; - ins_count++; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_SWITCH, 0, 1)) - goto fail; - src_param_init_temp_uint(&instructions[ins_count].src[0], block_temp_idx); - ins_count++; - } - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_CASE, 0, 1)) - goto fail; - src_param_init_const_uint(&instructions[ins_count].src[0], label_from_src_param(&ins->src[0])); - ins_count++; - break; - - case VKD3DSIH_BRANCH: - if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 2)) - goto fail; - - if (vsir_register_is_label(&ins->src[0].reg)) - { - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_MOV, 1, 1)) - goto fail; - dst_param_init_temp_uint(&instructions[ins_count].dst[0], block_temp_idx); - src_param_init_const_uint(&instructions[ins_count].src[0], label_from_src_param(&ins->src[0])); - ins_count++; - } - else - { - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_MOVC, 1, 3)) - goto fail; - dst_param_init_temp_uint(&instructions[ins_count].dst[0], block_temp_idx); - instructions[ins_count].src[0] = ins->src[0]; - src_param_init_const_uint(&instructions[ins_count].src[1], label_from_src_param(&ins->src[1])); - src_param_init_const_uint(&instructions[ins_count].src[2], label_from_src_param(&ins->src[2])); - ins_count++; - } - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_BREAK, 0, 0)) - goto fail; - ins_count++; - break; - - case VKD3DSIH_RET: - default: - if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 1)) - goto fail; - - instructions[ins_count++] = *ins; - break; - } - } - - assert(first_label_found); - - if (!reserve_instructions(&instructions, &ins_capacity, ins_count + 3)) - goto fail; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_ENDSWITCH, 0, 0)) - goto fail; - ins_count++; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_ENDLOOP, 0, 0)) - goto fail; - ins_count++; - - if (!vsir_instruction_init_with_params(&parser->program, &instructions[ins_count], &no_loc, VKD3DSIH_RET, 0, 0)) - goto fail; - 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.temp_count += 1; - - return VKD3D_OK; - -fail: - vkd3d_free(instructions); - return VKD3D_ERROR_OUT_OF_MEMORY; -} - struct vsir_block_list { struct vsir_block **blocks; @@ -3266,6 +3159,8 @@ struct vsir_cfg
struct vkd3d_shader_instruction *instructions; size_t ins_capacity, ins_count; + unsigned int jump_target_temp_idx; + unsigned int temp_count; };
static void vsir_cfg_cleanup(struct vsir_cfg *cfg) @@ -4305,6 +4200,7 @@ static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg, }
case STRUCTURE_TYPE_LOOP: + { if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) return VKD3D_ERROR_OUT_OF_MEMORY;
@@ -4313,32 +4209,99 @@ static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg, if ((ret = vsir_cfg_structure_list_emit(cfg, &structure->u.loop.body, structure->u.loop.idx)) < 0) return ret;
- if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 5)) return VKD3D_ERROR_OUT_OF_MEMORY;
vsir_instruction_init(&cfg->instructions[cfg->ins_count++], &no_loc, VKD3DSIH_ENDLOOP); + + /* Add a trampoline to implement multilevel jumping + * depending on the stored jump_target value. */ + if (loop_idx != UINT_MAX) + { + /* 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'. */ + const unsigned int outer_continue_target = loop_idx << 1 | 1; + /* If the multilevel jump is a `continue' to any + * other target, or if it is a `break' and the + * target is not the loop we just finished + * emitting, then it means that we have to reach + * an outer loop, so we keep breaking. */ + const unsigned int inner_break_target = structure->u.loop.idx << 1; + + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, VKD3DSIH_IEQ, 1, 2)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + dst_param_init_temp_bool(&cfg->instructions[cfg->ins_count].dst[0], cfg->temp_count); + src_param_init_temp_uint(&cfg->instructions[cfg->ins_count].src[0], cfg->jump_target_temp_idx); + src_param_init_const_uint(&cfg->instructions[cfg->ins_count].src[1], outer_continue_target); + + ++cfg->ins_count; + + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, VKD3DSIH_CONTINUEP, 0, 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + src_param_init_temp_bool(&cfg->instructions[cfg->ins_count].src[0], cfg->temp_count); + + ++cfg->ins_count; + ++cfg->temp_count; + + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, VKD3DSIH_IEQ, 1, 2)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + dst_param_init_temp_bool(&cfg->instructions[cfg->ins_count].dst[0], cfg->temp_count); + src_param_init_temp_uint(&cfg->instructions[cfg->ins_count].src[0], cfg->jump_target_temp_idx); + src_param_init_const_uint(&cfg->instructions[cfg->ins_count].src[1], inner_break_target); + + ++cfg->ins_count; + + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, VKD3DSIH_BREAKP, 0, 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + cfg->instructions[cfg->ins_count].flags |= VKD3D_SHADER_CONDITIONAL_OP_Z; + + src_param_init_temp_bool(&cfg->instructions[cfg->ins_count].src[0], cfg->temp_count); + + ++cfg->ins_count; + ++cfg->temp_count; + } + break; + }
case STRUCTURE_TYPE_JUMP: { + /* Encode the jump target as the loop index plus a bit + * to remember whether we're breaking or + * continueing. */ + unsigned int jump_target = structure->u.jump.target << 1; enum vkd3d_shader_opcode opcode;
- if (structure->u.jump.target != loop_idx) - { - WARN("Multilevel jumps are not supported yet, falling back to the simple structurizer.\n"); - return VKD3D_ERROR_NOT_IMPLEMENTED; - } - switch (structure->u.jump.type) { + case JUMP_CONTINUE: + /* If we're continueing the loop we're + * directly inside, then we can emit a + * `continue'. Otherwise we first have to + * break all the loops between here and the + * loop to continue, recording our intention + * to continue in the lowest bit of + * jump_target. */ + if (structure->u.jump.target == loop_idx) + { + opcode = structure->u.jump.condition ? VKD3DSIH_CONTINUEP : VKD3DSIH_CONTINUE; + break; + } + jump_target |= 1; + /* fall through */ + case JUMP_BREAK: opcode = structure->u.jump.condition ? VKD3DSIH_BREAKP : VKD3DSIH_BREAK; break;
- case JUMP_CONTINUE: - opcode = structure->u.jump.condition ? VKD3DSIH_CONTINUEP : VKD3DSIH_CONTINUE; - break; - case JUMP_RET: assert(!structure->u.jump.condition); opcode = VKD3DSIH_RET; @@ -4348,9 +4311,21 @@ static enum vkd3d_result vsir_cfg_structure_list_emit(struct vsir_cfg *cfg, vkd3d_unreachable(); }
- if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->ins_count + 1)) + 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 (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], + &no_loc, VKD3DSIH_MOV, 1, 1)) + return VKD3D_ERROR_OUT_OF_MEMORY; + + dst_param_init_temp_uint(&cfg->instructions[cfg->ins_count].dst[0], cfg->jump_target_temp_idx); + src_param_init_const_uint(&cfg->instructions[cfg->ins_count].src[0], jump_target); + + ++cfg->ins_count; + } + if (!vsir_instruction_init_with_params(cfg->program, &cfg->instructions[cfg->ins_count], &no_loc, opcode, 0, !!structure->u.jump.condition)) return VKD3D_ERROR_OUT_OF_MEMORY; @@ -4378,6 +4353,9 @@ static enum vkd3d_result vsir_cfg_emit_structured_program(struct vsir_cfg *cfg) enum vkd3d_result ret; size_t i;
+ cfg->jump_target_temp_idx = cfg->program->temp_count; + cfg->temp_count = cfg->program->temp_count + 1; + if (!reserve_instructions(&cfg->instructions, &cfg->ins_capacity, cfg->program->instructions.count)) return VKD3D_ERROR_OUT_OF_MEMORY;
@@ -4399,6 +4377,7 @@ static enum vkd3d_result vsir_cfg_emit_structured_program(struct vsir_cfg *cfg) cfg->program->instructions.elements = cfg->instructions; cfg->program->instructions.capacity = cfg->ins_capacity; cfg->program->instructions.count = cfg->ins_count; + cfg->program->temp_count = cfg->temp_count;
return VKD3D_OK;
@@ -4460,19 +4439,8 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
if ((result = vsir_cfg_emit_structured_program(&cfg)) < 0) { - if (result == VKD3D_ERROR_NOT_IMPLEMENTED) - { - if ((result = simple_structurizer_run(parser)) < 0) - { - vsir_cfg_cleanup(&cfg); - return result; - } - } - else - { - vsir_cfg_cleanup(&cfg); - return result; - } + vsir_cfg_cleanup(&cfg); + return result; }
vsir_cfg_cleanup(&cfg);
-
Giovanni Mascellani -
Giovanni Mascellani (＠giomasce)