intel/ir: Represent physical and logical subsets of the CFG.

This represents two control flow graphs in the same cfg_t data
structure: The physical CFG that will include all possible control
flow paths the EU can physically take, and the logical CFG restricted
to the control flow paths that exist in the original scalar program.
The latter is a subset of the former because in case of divergence the
SIMD vectorized program will take control flow paths that aren't part
of the original scalar program.

The bblock_link constructor and bblock_t::add_successor() now take a
"kind" parameter that specifies whether the edge is purely physical or
whether it's part of both the logical and physical CFGs (a logical
edge is of course always guaranteed to be in the physical CFG as
well).  bblock_t::is_predecessor_of() and ::is_successor_of() also
take a kind parameter specifying which CFG is being queried.  The '~>'
notation will be used now in order to represent purely physical edges
in IR dumps.

This commit doesn't actually add nor remove any edges from the CFG
(the only edges marked as purely physical here are the two WHILE loop
ones that already existed).  Optimization passes should continue using
the same (incomplete) physical CFG they were using before until
they're fixed to do something smarter in a later commit, so this
shouldn't lead to any functional changes.

v2: Remove tabs from lines changed in this file (Caio).

Reviewed-by: Jordan Justen <[email protected]>
Reviewed-by: Caio Marcelo de Oliveira Filho <[email protected]>

3 files changed, 81 insertions, 40 deletions

diff --git a/src/intel/compiler/brw_cfg.cpp b/src/intel/compiler/brw_cfg.cpp
index 6c40889088d..0d6c6fc5f5b 100644
--- a/src/intel/compiler/brw_cfg.cpp
+++ b/src/intel/compiler/brw_cfg.cpp
@@ -44,9 +44,9 @@ pop_stack(exec_list *list)
 }
 
 static exec_node *
-link(void *mem_ctx, bblock_t *block)
+link(void *mem_ctx, bblock_t *block, enum bblock_link_kind kind)
 {
-   bblock_link *l = new(mem_ctx) bblock_link(block);
+   bblock_link *l = new(mem_ctx) bblock_link(block, kind);
    return &l->link;
 }
 
@@ -59,17 +59,19 @@ bblock_t::bblock_t(cfg_t *cfg) :
 }
 
 void
-bblock_t::add_successor(void *mem_ctx, bblock_t *successor)
+bblock_t::add_successor(void *mem_ctx, bblock_t *successor,
+                        enum bblock_link_kind kind)
 {
-   successor->parents.push_tail(::link(mem_ctx, this));
-   children.push_tail(::link(mem_ctx, successor));
+   successor->parents.push_tail(::link(mem_ctx, this, kind));
+   children.push_tail(::link(mem_ctx, successor, kind));
 }
 
 bool
-bblock_t::is_predecessor_of(const bblock_t *block) const
+bblock_t::is_predecessor_of(const bblock_t *block,
+                            enum bblock_link_kind kind) const
 {
    foreach_list_typed_safe (bblock_link, parent, link, &block->parents) {
-      if (parent->block == this) {
+      if (parent->block == this && parent->kind <= kind) {
          return true;
       }
    }
@@ -78,10 +80,11 @@ bblock_t::is_predecessor_of(const bblock_t *block) const
 }
 
 bool
-bblock_t::is_successor_of(const bblock_t *block) const
+bblock_t::is_successor_of(const bblock_t *block,
+                          enum bblock_link_kind kind) const
 {
    foreach_list_typed_safe (bblock_link, child, link, &block->children) {
-      if (child->block == this) {
+      if (child->block == this && child->kind <= kind) {
          return true;
       }
    }
@@ -185,8 +188,8 @@ cfg_t::cfg_t(exec_list *instructions)
 	 /* Push our information onto a stack so we can recover from
 	  * nested ifs.
 	  */
-	 if_stack.push_tail(link(mem_ctx, cur_if));
-	 else_stack.push_tail(link(mem_ctx, cur_else));
+         if_stack.push_tail(link(mem_ctx, cur_if, bblock_link_logical));
+         else_stack.push_tail(link(mem_ctx, cur_else, bblock_link_logical));
 
 	 cur_if = cur;
 	 cur_else = NULL;
@@ -196,7 +199,7 @@ cfg_t::cfg_t(exec_list *instructions)
 	  * instructions.
 	  */
 	 next = new_block();
-	 cur_if->add_successor(mem_ctx, next);
+         cur_if->add_successor(mem_ctx, next, bblock_link_logical);
 
 	 set_next_block(&cur, next, ip);
 	 break;
@@ -208,7 +211,7 @@ cfg_t::cfg_t(exec_list *instructions)
 
 	 next = new_block();
          assert(cur_if != NULL);
-	 cur_if->add_successor(mem_ctx, next);
+         cur_if->add_successor(mem_ctx, next, bblock_link_logical);
 
 	 set_next_block(&cur, next, ip);
 	 break;
@@ -220,7 +223,7 @@ cfg_t::cfg_t(exec_list *instructions)
          } else {
             cur_endif = new_block();
 
-            cur->add_successor(mem_ctx, cur_endif);
+            cur->add_successor(mem_ctx, cur_endif, bblock_link_logical);
 
             set_next_block(&cur, cur_endif, ip - 1);
          }
@@ -228,10 +231,10 @@ cfg_t::cfg_t(exec_list *instructions)
          cur->instructions.push_tail(inst);
 
          if (cur_else) {
-            cur_else->add_successor(mem_ctx, cur_endif);
+            cur_else->add_successor(mem_ctx, cur_endif, bblock_link_logical);
          } else {
             assert(cur_if != NULL);
-            cur_if->add_successor(mem_ctx, cur_endif);
+            cur_if->add_successor(mem_ctx, cur_endif, bblock_link_logical);
          }
 
          assert(cur_if->end()->opcode == BRW_OPCODE_IF);
@@ -246,8 +249,8 @@ cfg_t::cfg_t(exec_list *instructions)
 	 /* Push our information onto a stack so we can recover from
 	  * nested loops.
 	  */
-	 do_stack.push_tail(link(mem_ctx, cur_do));
-	 while_stack.push_tail(link(mem_ctx, cur_while));
+         do_stack.push_tail(link(mem_ctx, cur_do, bblock_link_logical));
+         while_stack.push_tail(link(mem_ctx, cur_while, bblock_link_logical));
 
 	 /* Set up the block just after the while.  Don't know when exactly
 	  * it will start, yet.
@@ -260,7 +263,7 @@ cfg_t::cfg_t(exec_list *instructions)
          } else {
             cur_do = new_block();
 
-            cur->add_successor(mem_ctx, cur_do);
+            cur->add_successor(mem_ctx, cur_do, bblock_link_logical);
 
             set_next_block(&cur, cur_do, ip - 1);
          }
@@ -294,8 +297,8 @@ cfg_t::cfg_t(exec_list *instructions)
           * corruption.
           */
          next = new_block();
-         cur->add_successor(mem_ctx, next);
-         cur->add_successor(mem_ctx, cur_while);
+         cur->add_successor(mem_ctx, next, bblock_link_logical);
+         cur->add_successor(mem_ctx, cur_while, bblock_link_physical);
          set_next_block(&cur, next, ip);
 	 break;
 
@@ -316,11 +319,11 @@ cfg_t::cfg_t(exec_list *instructions)
           * loop, the top of the loop again, into a use of the variable).
           */
          assert(cur_do != NULL);
-         cur->add_successor(mem_ctx, cur_do->next());
+         cur->add_successor(mem_ctx, cur_do->next(), bblock_link_logical);
 
 	 next = new_block();
 	 if (inst->predicate)
-	    cur->add_successor(mem_ctx, next);
+            cur->add_successor(mem_ctx, next, bblock_link_logical);
 
 	 set_next_block(&cur, next, ip);
 	 break;
@@ -339,11 +342,11 @@ cfg_t::cfg_t(exec_list *instructions)
           * See the DO case for additional explanation.
           */
          assert(cur_do != NULL);
-         cur->add_successor(mem_ctx, cur_do);
+         cur->add_successor(mem_ctx, cur_do, bblock_link_physical);
 
 	 next = new_block();
 	 if (inst->predicate)
-	    cur->add_successor(mem_ctx, next);
+            cur->add_successor(mem_ctx, next, bblock_link_logical);
 
 	 set_next_block(&cur, next, ip);
 	 break;
@@ -362,8 +365,11 @@ cfg_t::cfg_t(exec_list *instructions)
           * channels, so we may skip over the divergence point at the top of
           * the loop to keep the CFG as unambiguous as possible.
           */
-         cur->add_successor(mem_ctx, inst->predicate ? cur_do :
-                                     cur_do->next());
+         if (inst->predicate) {
+            cur->add_successor(mem_ctx, cur_do, bblock_link_logical);
+         } else {
+            cur->add_successor(mem_ctx, cur_do->next(), bblock_link_logical);
+         }
 
 	 set_next_block(&cur, cur_while, ip);
 
@@ -403,9 +409,11 @@ cfg_t::remove_block(bblock_t *block)
 
       /* Add removed-block's successors to its predecessors' successor lists. */
       foreach_list_typed (bblock_link, successor, link, &block->children) {
-         if (!successor->block->is_successor_of(predecessor->block)) {
+         if (!successor->block->is_successor_of(predecessor->block,
+                                                successor->kind)) {
             predecessor->block->children.push_tail(link(mem_ctx,
-                                                        successor->block));
+                                                        successor->block,
+                                                        successor->kind));
          }
       }
    }
@@ -422,9 +430,11 @@ cfg_t::remove_block(bblock_t *block)
 
       /* Add removed-block's predecessors to its successors' predecessor lists. */
       foreach_list_typed (bblock_link, predecessor, link, &block->parents) {
-         if (!predecessor->block->is_predecessor_of(successor->block)) {
+         if (!predecessor->block->is_predecessor_of(successor->block,
+                                                    predecessor->kind)) {
             successor->block->parents.push_tail(link(mem_ctx,
-                                                     predecessor->block));
+                                                     predecessor->block,
+                                                     predecessor->kind));
          }
       }
    }
@@ -487,7 +497,8 @@ cfg_t::dump(backend_shader *s)
          fprintf(stderr, "START B%d IDOM(none)", block->num);
 
       foreach_list_typed(bblock_link, link, link, &block->parents) {
-         fprintf(stderr, " <-B%d",
+         fprintf(stderr, " <%cB%d",
+                 link->kind == bblock_link_logical ? '-' : '~',
                  link->block->num);
       }
       fprintf(stderr, "\n");
@@ -495,7 +506,8 @@ cfg_t::dump(backend_shader *s)
          block->dump(s);
       fprintf(stderr, "END B%d", block->num);
       foreach_list_typed(bblock_link, link, link, &block->children) {
-         fprintf(stderr, " ->B%d",
+         fprintf(stderr, " %c>B%d",
+                 link->kind == bblock_link_logical ? '-' : '~',
                  link->block->num);
       }
       fprintf(stderr, "\n");
diff --git a/src/intel/compiler/brw_cfg.h b/src/intel/compiler/brw_cfg.h
index 0c5d1268f1a..7434b190660 100644
--- a/src/intel/compiler/brw_cfg.h
+++ b/src/intel/compiler/brw_cfg.h
@@ -32,18 +32,42 @@
 
 struct bblock_t;
 
+/**
+ * CFG edge types.
+ *
+ * A logical edge represents a potential control flow path of the original
+ * scalar program, while a physical edge represents a control flow path that
+ * may not have existed in the original program but was introduced during
+ * vectorization in order to implement divergent control flow of different
+ * shader invocations within the same SIMD thread.
+ *
+ * All logical edges in the CFG are considered to be physical edges but not
+ * the other way around -- I.e. the logical CFG is a subset of the physical
+ * one.
+ */
+enum bblock_link_kind {
+   bblock_link_logical = 0,
+   bblock_link_physical
+};
+
 struct bblock_link {
 #ifdef __cplusplus
    DECLARE_RALLOC_CXX_OPERATORS(bblock_link)
 
-   bblock_link(bblock_t *block)
-      : block(block)
+   bblock_link(bblock_t *block, enum bblock_link_kind kind)
+      : block(block), kind(kind)
    {
    }
 #endif
 
    struct exec_node link;
    struct bblock_t *block;
+
+   /* Type of this CFG edge.  Because bblock_link_logical also implies
+    * bblock_link_physical, the proper way to test for membership of edge 'l'
+    * in CFG kind 'k' is 'l.kind <= k'.
+    */
+   enum bblock_link_kind kind;
 };
 
 struct backend_instruction;
@@ -54,9 +78,12 @@ struct bblock_t {
 
    explicit bblock_t(cfg_t *cfg);
 
-   void add_successor(void *mem_ctx, bblock_t *successor);
-   bool is_predecessor_of(const bblock_t *block) const;
-   bool is_successor_of(const bblock_t *block) const;
+   void add_successor(void *mem_ctx, bblock_t *successor,
+                      enum bblock_link_kind kind);
+   bool is_predecessor_of(const bblock_t *block,
+                          enum bblock_link_kind kind) const;
+   bool is_successor_of(const bblock_t *block,
+                        enum bblock_link_kind kind) const;
    bool can_combine_with(const bblock_t *that) const;
    void combine_with(bblock_t *that);
    void dump(backend_shader *s) const;
diff --git a/src/intel/compiler/brw_predicated_break.cpp b/src/intel/compiler/brw_predicated_break.cpp
index e60052f3608..0dcb5e50b73 100644
--- a/src/intel/compiler/brw_predicated_break.cpp
+++ b/src/intel/compiler/brw_predicated_break.cpp
@@ -100,13 +100,15 @@ opt_predicated_break(backend_shader *s)
 
       if (!earlier_block->ends_with_control_flow()) {
          earlier_block->children.make_empty();
-         earlier_block->add_successor(s->cfg->mem_ctx, jump_block);
+         earlier_block->add_successor(s->cfg->mem_ctx, jump_block,
+                                      bblock_link_logical);
       }
 
       if (!later_block->starts_with_control_flow()) {
          later_block->parents.make_empty();
       }
-      jump_block->add_successor(s->cfg->mem_ctx, later_block);
+      jump_block->add_successor(s->cfg->mem_ctx, later_block,
+                                bblock_link_logical);
 
       if (earlier_block->can_combine_with(jump_block)) {
          earlier_block->combine_with(jump_block);