i965/skl: Break down SIMD16 3-source instructions when required.

[mesa.git] / src / mesa / drivers / dri / i965 / brw_cfg.cpp

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index bb49a0ae955b6a0ba659dd9a82c64bd7ebacbf16..7e7770e43cdba1902febb4bb61ce17c785116df9 100644 (file)
--- a/src/mesa/drivers/dri/i965/brw_cfg.cpp
+++ b/src/mesa/drivers/dri/i965/brw_cfg.cpp
@@ -51,8 +51,7 @@ link(void *mem_ctx, bblock_t *block)
 }
 
 bblock_t::bblock_t(cfg_t *cfg) :
-   cfg(cfg), start_ip(0), end_ip(0), num(0),
-   if_block(NULL), else_block(NULL)
+   cfg(cfg), idom(NULL), start_ip(0), end_ip(0), num(0)
 {
    instructions.make_empty();
    parents.make_empty();
@@ -136,7 +135,6 @@ bblock_t::combine_with(bblock_t *that)
    }
 
    this->end_ip = that->end_ip;
-   this->else_block = that->else_block;
    this->instructions.append_list(&that->instructions);
 
    this->cfg->remove_block(that);
@@ -159,6 +157,7 @@ cfg_t::cfg_t(exec_list *instructions)
    block_list.make_empty();
    blocks = NULL;
    num_blocks = 0;
+   idom_dirty = true;
 
    bblock_t *cur = NULL;
    int ip = 0;
@@ -238,17 +237,6 @@ cfg_t::cfg_t(exec_list *instructions)
          assert(cur_if->end()->opcode == BRW_OPCODE_IF);
          assert(!cur_else || cur_else->end()->opcode == BRW_OPCODE_ELSE);
 
-         cur_if->if_block = cur_if;
-         cur_if->else_block = cur_else;
-
-        if (cur_else) {
-            cur_else->if_block = cur_if;
-            cur_else->else_block = cur_else;
-         }
-
-         cur->if_block = cur_if;
-         cur->else_block = cur_else;
-
         /* Pop the stack so we're in the previous if/else/endif */
         cur_if = pop_stack(&if_stack);
         cur_else = pop_stack(&else_stack);
@@ -326,7 +314,7 @@ cfg_t::cfg_t(exec_list *instructions)
       }
    }
 
-   cur->end_ip = ip;
+   cur->end_ip = ip - 1;
 
    make_block_array();
 }
@@ -386,6 +374,7 @@ cfg_t::remove_block(bblock_t *block)
 
    this->blocks[this->num_blocks - 1]->num = this->num_blocks - 2;
    this->num_blocks--;
+   idom_dirty = true;
 }
 
 bblock_t *
@@ -422,16 +411,20 @@ cfg_t::make_block_array()
 }
 
 void
-cfg_t::dump(backend_visitor *v) const
+cfg_t::dump(backend_visitor *v)
 {
+   if (idom_dirty)
+      calculate_idom();
+
    foreach_block (block, this) {
-      fprintf(stderr, "START B%d", block->num);
+      fprintf(stderr, "START B%d IDOM(B%d)", block->num, block->idom->num);
       foreach_list_typed(bblock_link, link, link, &block->parents) {
          fprintf(stderr, " <-B%d",
                  link->block->num);
       }
       fprintf(stderr, "\n");
-      block->dump(v);
+      if (v != NULL)
+         block->dump(v);
       fprintf(stderr, "END B%d", block->num);
       foreach_list_typed(bblock_link, link, link, &block->children) {
          fprintf(stderr, " ->B%d",
@@ -440,3 +433,89 @@ cfg_t::dump(backend_visitor *v) const
       fprintf(stderr, "\n");
    }
 }
+
+/* Calculates the immediate dominator of each block, according to "A Simple,
+ * Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken
+ * Kennedy.
+ *
+ * The authors claim that for control flow graphs of sizes normally encountered
+ * (less than 1000 nodes) that this algorithm is significantly faster than
+ * others like Lengauer-Tarjan.
+ */
+void
+cfg_t::calculate_idom()
+{
+   foreach_block(block, this) {
+      block->idom = NULL;
+   }
+   blocks[0]->idom = blocks[0];
+
+   bool changed;
+   do {
+      changed = false;
+
+      foreach_block(block, this) {
+         if (block->num == 0)
+            continue;
+
+         bblock_t *new_idom = NULL;
+         foreach_list_typed(bblock_link, parent, link, &block->parents) {
+            if (parent->block->idom) {
+               if (new_idom == NULL) {
+                  new_idom = parent->block;
+               } else if (parent->block->idom != NULL) {
+                  new_idom = intersect(parent->block, new_idom);
+               }
+            }
+         }
+
+         if (block->idom != new_idom) {
+            block->idom = new_idom;
+            changed = true;
+         }
+      }
+   } while (changed);
+
+   idom_dirty = false;
+}
+
+bblock_t *
+cfg_t::intersect(bblock_t *b1, bblock_t *b2)
+{
+   /* Note, the comparisons here are the opposite of what the paper says
+    * because we index blocks from beginning -> end (i.e. reverse post-order)
+    * instead of post-order like they assume.
+    */
+   while (b1->num != b2->num) {
+      while (b1->num > b2->num)
+         b1 = b1->idom;
+      while (b2->num > b1->num)
+         b2 = b2->idom;
+   }
+   assert(b1);
+   return b1;
+}
+
+void
+cfg_t::dump_cfg()
+{
+   printf("digraph CFG {\n");
+   for (int b = 0; b < num_blocks; b++) {
+      bblock_t *block = this->blocks[b];
+
+      foreach_list_typed_safe (bblock_link, child, link, &block->children) {
+         printf("\t%d -> %d\n", b, child->block->num);
+      }
+   }
+   printf("}\n");
+}
+
+void
+cfg_t::dump_domtree()
+{
+   printf("digraph DominanceTree {\n");
+   foreach_block(block, this) {
+      printf("\t%d -> %d\n", block->idom->num, block->num);
+   }
+   printf("}\n");
+}