spirv: Rewrite CFG construction

This commit completely rewrites the way we extract a structured CFG from
SPIR-V.  The new approach is different in a few ways:

 1. It does a breadth-first search instead of depth-first.  This means
    that we've visited the merge node for a construct before we visit
    any of the nodes inside the construct.  This makes it easier to
    validate things like loop and switch nesting.

 2. We record more information in the CFG.  Earlier commits added a
    parent pointer to vtn_cf_node but we now record all of the merge and
    other special blocks for each CFG node.  This lets us validate
    things more precisely.

 3. It makes heavy use of merge blocks for walking the CFG.  Previously,
    we sort of used them as hints for trying to guess the CFG structure
    but things got dicey whenever a merge was missing.  We had some
    heuristics for how to handle short-circuiting if statements but it
    was a bunch of special cases.

    Now, we make them a fundamental part of walking the CFG.  When we
    encounter a control-flow construct, we add the body components of
    the construct to the BFS work list and then jump to the merge block
    if one exists to continue scanning the current CFG nesting level.
    If no merge block exists, we assume that means that control-flow
    never re-converges in a normal way and that the only way to get back
    to normality is with a direct jump such as a loop break or continue.
    This should make things far more robust when trying to deal with the
    more creative placement (or lack thereof) of merge instructions.

Reviewed-by: Alan Baker <[email protected]>
Reviewed-by: Caio Marcelo de Oliveira Filho <[email protected]>
Tested-by: Marge Bot <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/3820>
Closes: #2760
Acked-by: Samuel Pitoiset <[email protected]>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4446>

1 files changed, 19 insertions, 3 deletions

diff --git a/src/compiler/spirv/vtn_private.h b/src/compiler/spirv/vtn_private.h
index 13f1cf65a83..787dfdb244e 100644
--- a/src/compiler/spirv/vtn_private.h
+++ b/src/compiler/spirv/vtn_private.h
@@ -123,10 +123,12 @@ enum vtn_value_type {
 
 enum vtn_branch_type {
    vtn_branch_type_none,
+   vtn_branch_type_if_merge,
    vtn_branch_type_switch_break,
    vtn_branch_type_switch_fallthrough,
    vtn_branch_type_loop_break,
    vtn_branch_type_loop_continue,
+   vtn_branch_type_loop_back_edge,
    vtn_branch_type_discard,
    vtn_branch_type_return,
 };
@@ -157,6 +159,10 @@ struct vtn_loop {
     */
    struct list_head cont_body;
 
+   struct vtn_block *header_block;
+   struct vtn_block *cont_block;
+   struct vtn_block *break_block;
+
    SpvLoopControlMask control;
 };
 
@@ -171,17 +177,17 @@ struct vtn_if {
    enum vtn_branch_type else_type;
    struct list_head else_body;
 
+   struct vtn_block *merge_block;
+
    SpvSelectionControlMask control;
 };
 
 struct vtn_case {
    struct vtn_cf_node node;
 
+   enum vtn_branch_type type;
    struct list_head body;
 
-   /* The block that starts this case */
-   struct vtn_block *start_block;
-
    /* The fallthrough case, if any */
    struct vtn_case *fallthrough;
 
@@ -201,6 +207,8 @@ struct vtn_switch {
    uint32_t selector;
 
    struct list_head cases;
+
+   struct vtn_block *break_block;
 };
 
 struct vtn_block {
@@ -217,6 +225,14 @@ struct vtn_block {
 
    enum vtn_branch_type branch_type;
 
+   /* The CF node for which this is a merge target
+    *
+    * The SPIR-V spec requires that any given block can be the merge target
+    * for at most one merge instruction.  If this block is a merge target,
+    * this points back to the block containing that merge instruction.
+    */
+   struct vtn_cf_node *merge_cf_node;
+
    /** Points to the loop that this block starts (if it starts a loop) */
    struct vtn_loop *loop;