Module: vkd3d
Branch: master
Commit: 070c4af8b3d3d6910344f1786d11709f9b4a1909
URL: https://gitlab.winehq.org/wine/vkd3d/-/commit/070c4af8b3d3d6910344f1786d117…
Author: Giovanni Mascellani <gmascellani(a)codeweavers.com>
Date: Mon Feb 5 11:15:24 2024 +0100
vkd3d-shader/ir: Generate synthetic intervals for forward edges.
---
libs/vkd3d-shader/ir.c | 159 +++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 153 insertions(+), 6 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 67f5b5fd..88d54e56 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3068,7 +3068,7 @@ static void vsir_block_list_remove_index(struct vsir_block_list *list, size_t id
struct vsir_block
{
- unsigned int label;
+ unsigned int label, order_pos;
/* `begin' points to the instruction immediately following the
* LABEL that introduces the block. `end' points to the terminator
* instruction (either BRANCH or RET). They can coincide, meaning
@@ -3151,6 +3151,27 @@ struct vsir_cfg
* `continue' instruction would jump and `end' is where a
* `break' instruction would jump. */
unsigned int begin, end;
+ /* Each loop interval can be natural or synthetic. Natural
+ * intervals are added to represent loops given by CFG back
+ * edges. Synthetic intervals do not correspond to loops in
+ * the input CFG, but are added to leverage their `break'
+ * instruction in order to execute forward edges.
+ *
+ * For a synthetic loop interval it's not really important
+ * which one is the `begin' block, since we don't need to
+ * execute `continue' for them. So we have some leeway for
+ * moving it provided that these conditions are met: 1. the
+ * interval must contain all `break' instructions that target
+ * it, which in practice means that `begin' can be moved
+ * backward and not forward; 2. intervals must remain properly
+ * nested (for each pair of intervals, either one contains the
+ * other or they are disjoint).
+ *
+ * Subject to these conditions, we try to reuse the same loop
+ * as much as possible (if many forward edges target the same
+ * block), but we still try to keep `begin' as forward as
+ * possible, to keep the loop scope as small as possible. */
+ bool synthetic;
} *loop_intervals;
size_t loop_interval_count, loop_interval_capacity;
};
@@ -3177,7 +3198,7 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg)
}
static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsigned int begin,
- unsigned int end)
+ unsigned int end, bool synthetic)
{
struct cfg_loop_interval *interval;
@@ -3189,6 +3210,7 @@ static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsign
interval->begin = begin;
interval->end = end;
+ interval->synthetic = synthetic;
return VKD3D_OK;
}
@@ -3661,6 +3683,7 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg)
}
vsir_block_list_remove_index(&sorter.available_blocks, i);
+ block->order_pos = cfg->order.count;
if ((ret = vsir_block_list_add_checked(&cfg->order, block)) < 0)
goto fail;
@@ -3680,7 +3703,7 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg)
break;
if ((ret = vsir_cfg_add_loop_interval(cfg, inner_stack_item->begin,
- cfg->order.count)) < 0)
+ cfg->order.count, false)) < 0)
goto fail;
new_seen_count = inner_stack_item->loop->count;
@@ -3731,9 +3754,6 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg)
TRACE("%s\n", cfg->debug_buffer.buffer);
vkd3d_string_buffer_clear(&cfg->debug_buffer);
-
- for (i = 0; i < cfg->loop_interval_count; ++i)
- TRACE("Loop interval %u - %u\n", cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end);
}
return VKD3D_OK;
@@ -3746,6 +3766,127 @@ fail:
return ret;
}
+static enum vkd3d_result vsir_cfg_generate_synthetic_loop_intervals(struct vsir_cfg *cfg)
+{
+ enum vkd3d_result ret;
+ size_t i, j, k;
+
+ for (i = 0; i < cfg->block_count; ++i)
+ {
+ struct vsir_block *block = &cfg->blocks[i];
+
+ if (block->label == 0)
+ continue;
+
+ for (j = 0; j < block->successors.count; ++j)
+ {
+ struct vsir_block *successor = block->successors.blocks[j];
+ struct cfg_loop_interval *extend = NULL;
+ unsigned int begin;
+ enum
+ {
+ ACTION_DO_NOTHING,
+ ACTION_CREATE_NEW,
+ ACTION_EXTEND,
+ } action = ACTION_CREATE_NEW;
+
+ /* We've already contructed loop intervals for the back
+ * edges, there's nothing more to do. */
+ if (vsir_block_dominates(successor, block))
+ continue;
+
+ assert(block->order_pos < successor->order_pos);
+
+ /* Jumping from a block to the following one is always
+ * possible, so nothing to do. */
+ if (block->order_pos + 1 == successor->order_pos)
+ continue;
+
+ /* Let's look for a loop interval that already breaks at
+ * `successor' and either contains or can be extended to
+ * contain `block'. */
+ for (k = 0; k < cfg->loop_interval_count; ++k)
+ {
+ struct cfg_loop_interval *interval = &cfg->loop_intervals[k];
+
+ if (interval->end != successor->order_pos)
+ continue;
+
+ if (interval->begin <= block->order_pos)
+ {
+ action = ACTION_DO_NOTHING;
+ break;
+ }
+
+ if (interval->synthetic)
+ {
+ action = ACTION_EXTEND;
+ extend = interval;
+ break;
+ }
+ }
+
+ if (action == ACTION_DO_NOTHING)
+ continue;
+
+ /* Ok, we have to decide where the new or replacing
+ * interval has to begin. These are the rules: 1. it must
+ * begin before `block'; 2. intervals must be properly
+ * nested; 3. the new interval should begin as late as
+ * possible, to limit control flow depth and extension. */
+ begin = block->order_pos;
+
+ /* Our candidate interval is always [begin,
+ * successor->order_pos), and we move `begin' backward
+ * until the candidate interval contains all the intervals
+ * whose endpoint lies in the candidate interval
+ * itself. */
+ for (k = 0; k < cfg->loop_interval_count; ++k)
+ {
+ struct cfg_loop_interval *interval = &cfg->loop_intervals[k];
+
+ if (begin < interval->end && interval->end < successor->order_pos)
+ begin = min(begin, interval->begin);
+ }
+
+ /* New we have to care about the intervals whose begin
+ * point lies in the candidate interval. We cannot move
+ * the candidate interval endpoint, because it is
+ * important that the loop break target matches
+ * `successor'. So we have to move that interval's begin
+ * point to the begin point of the candidate interval,
+ * i.e. `begin'. But what if the interval we should extend
+ * backward is not synthetic? This cannot happen,
+ * fortunately, because it would mean that there is a jump
+ * entering a loop via a block which is not the loop
+ * header, so the CFG would not be reducible. */
+ for (k = 0; k < cfg->loop_interval_count; ++k)
+ {
+ struct cfg_loop_interval *interval = &cfg->loop_intervals[k];
+
+ if (interval->begin < successor->order_pos && successor->order_pos < interval->end)
+ {
+ if (interval->synthetic)
+ interval->begin = min(begin, interval->begin);
+ assert(begin >= interval->begin);
+ }
+ }
+
+ if (action == ACTION_EXTEND)
+ extend->begin = begin;
+ else if ((ret = vsir_cfg_add_loop_interval(cfg, begin, successor->order_pos, true)) < 0)
+ return ret;
+ }
+ }
+
+ if (TRACE_ON())
+ for (i = 0; i < cfg->loop_interval_count; ++i)
+ TRACE("%s loop interval %u - %u\n", cfg->loop_intervals[i].synthetic ? "Synthetic" : "Natural",
+ cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end);
+
+ return VKD3D_OK;
+}
+
enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
const struct vkd3d_shader_compile_info *compile_info)
{
@@ -3784,6 +3925,12 @@ enum vkd3d_result vkd3d_shader_normalise(struct vkd3d_shader_parser *parser,
return result;
}
+ if ((result = vsir_cfg_generate_synthetic_loop_intervals(&cfg)) < 0)
+ {
+ vsir_cfg_cleanup(&cfg);
+ return result;
+ }
+
if ((result = simple_structurizer_run(parser)) < 0)
{
vsir_cfg_cleanup(&cfg);
Module: vkd3d
Branch: master
Commit: 1d606123401640fcf0e9c1cb35caf72755327b43
URL: https://gitlab.winehq.org/wine/vkd3d/-/commit/1d606123401640fcf0e9c1cb35caf…
Author: Giovanni Mascellani <gmascellani(a)codeweavers.com>
Date: Sun Feb 4 20:21:20 2024 +0100
vkd3d-shader/ir: Compute loop as intervals of the block order.
---
libs/vkd3d-shader/ir.c | 53 ++++++++++++++++++++++++++++++++++++++++++--------
1 file changed, 45 insertions(+), 8 deletions(-)
diff --git a/libs/vkd3d-shader/ir.c b/libs/vkd3d-shader/ir.c
index 14aea329..67f5b5fd 100644
--- a/libs/vkd3d-shader/ir.c
+++ b/libs/vkd3d-shader/ir.c
@@ -3143,6 +3143,16 @@ struct vsir_cfg
size_t *loops_by_header;
struct vsir_block_list order;
+ struct cfg_loop_interval
+ {
+ /* `begin' is the position of the first block of the loop in
+ * the topological sort; `end' is the position of the first
+ * block after the loop. In other words, `begin' is where a
+ * `continue' instruction would jump and `end' is where a
+ * `break' instruction would jump. */
+ unsigned int begin, end;
+ } *loop_intervals;
+ size_t loop_interval_count, loop_interval_capacity;
};
static void vsir_cfg_cleanup(struct vsir_cfg *cfg)
@@ -3160,11 +3170,29 @@ static void vsir_cfg_cleanup(struct vsir_cfg *cfg)
vkd3d_free(cfg->blocks);
vkd3d_free(cfg->loops);
vkd3d_free(cfg->loops_by_header);
+ vkd3d_free(cfg->loop_intervals);
if (TRACE_ON())
vkd3d_string_buffer_cleanup(&cfg->debug_buffer);
}
+static enum vkd3d_result vsir_cfg_add_loop_interval(struct vsir_cfg *cfg, unsigned int begin,
+ unsigned int end)
+{
+ struct cfg_loop_interval *interval;
+
+ if (!vkd3d_array_reserve((void **)&cfg->loop_intervals, &cfg->loop_interval_capacity,
+ cfg->loop_interval_count + 1, sizeof(*cfg->loop_intervals)))
+ return VKD3D_ERROR_OUT_OF_MEMORY;
+
+ interval = &cfg->loop_intervals[cfg->loop_interval_count++];
+
+ interval->begin = begin;
+ interval->end = end;
+
+ return VKD3D_OK;
+}
+
static bool vsir_block_dominates(struct vsir_block *b1, struct vsir_block *b2)
{
return bitmap_is_set(b1->dominates, b2->label - 1);
@@ -3399,14 +3427,14 @@ static void vsir_cfg_compute_dominators(struct vsir_cfg *cfg)
* block without passing through the header block) belong to the same
* loop.
*
- * If the input CFG is reducible, each two loops are either disjoint
- * or one is a strict subset of the other, provided that each block
- * has at most one incoming back edge. If this condition does not
- * hold, a synthetic block can be introduced as the only back edge
- * block for the given header block, with all the previous back edge
- * now being forward edges to the synthetic block. This is not
- * currently implemented (but it is rarely found in practice
- * anyway). */
+ * If the input CFG is reducible its loops are properly nested (i.e.,
+ * each two loops are either disjoint or one is contained in the
+ * other), provided that each block has at most one incoming back
+ * edge. If this condition does not hold, a synthetic block can be
+ * introduced as the only back edge block for the given header block,
+ * with all the previous back edge now being forward edges to the
+ * synthetic block. This is not currently implemented (but it is
+ * rarely found in practice anyway). */
static enum vkd3d_result vsir_cfg_scan_loop(struct vsir_block_list *loop, struct vsir_block *block,
struct vsir_block *header)
{
@@ -3499,6 +3527,7 @@ struct vsir_cfg_node_sorter
{
struct vsir_block_list *loop;
unsigned int seen_count;
+ unsigned int begin;
} *stack;
size_t stack_count, stack_capacity;
struct vsir_block_list available_blocks;
@@ -3525,6 +3554,7 @@ static enum vkd3d_result vsir_cfg_node_sorter_make_node_available(struct vsir_cf
item = &sorter->stack[sorter->stack_count++];
item->loop = loop;
item->seen_count = 0;
+ item->begin = sorter->cfg->order.count;
return VKD3D_OK;
}
@@ -3649,6 +3679,10 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg)
if (inner_stack_item->seen_count != inner_stack_item->loop->count)
break;
+ if ((ret = vsir_cfg_add_loop_interval(cfg, inner_stack_item->begin,
+ cfg->order.count)) < 0)
+ goto fail;
+
new_seen_count = inner_stack_item->loop->count;
--sorter.stack_count;
}
@@ -3697,6 +3731,9 @@ static enum vkd3d_result vsir_cfg_sort_nodes(struct vsir_cfg *cfg)
TRACE("%s\n", cfg->debug_buffer.buffer);
vkd3d_string_buffer_clear(&cfg->debug_buffer);
+
+ for (i = 0; i < cfg->loop_interval_count; ++i)
+ TRACE("Loop interval %u - %u\n", cfg->loop_intervals[i].begin, cfg->loop_intervals[i].end);
}
return VKD3D_OK;