X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;ds=sidebyside;f=src%2Fmesa%2Fdrivers%2Fdri%2Fi965%2Fbrw_cfg.cpp;h=5d46615bc7b98b28229aebcb02c87d028e51e7fc;hb=98c8bef01cae5fd70dda22fd7ac0b5694c4dfb5f;hp=62cc23970d6fb6fbc547c75b3cc2ef71b700481c;hpb=7f813bf53d1c728c888ceffae2140f32697b8ffd;p=mesa.git

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index 62cc23970d6..5d46615bc7b 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.cpp
+++ b/src/mesa/drivers/dri/i965/brw_cfg.cpp
@@ -51,7 +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)
+   cfg(cfg), idom(NULL), start_ip(0), end_ip(0), num(0)
 {
    instructions.make_empty();
    parents.make_empty();
@@ -141,12 +141,12 @@ bblock_t::combine_with(bblock_t *that)
 }
 
 void
-bblock_t::dump(backend_visitor *v) const
+bblock_t::dump(backend_shader *s) const
 {
    int ip = this->start_ip;
    foreach_inst_in_block(backend_instruction, inst, this) {
       fprintf(stderr, "%5d: ", ip);
-      v->dump_instruction(inst);
+      s->dump_instruction(inst);
       ip++;
    }
 }
@@ -157,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;
@@ -207,6 +208,7 @@ cfg_t::cfg_t(exec_list *instructions)
          cur_else = cur;
 
 	 next = new_block();
+         assert(cur_if != NULL);
 	 cur_if->add_successor(mem_ctx, next);
 
 	 set_next_block(&cur, next, ip);
@@ -230,6 +232,7 @@ cfg_t::cfg_t(exec_list *instructions)
          if (cur_else) {
             cur_else->add_successor(mem_ctx, cur_endif);
          } else {
+            assert(cur_if != NULL);
             cur_if->add_successor(mem_ctx, cur_endif);
          }
 
@@ -272,6 +275,7 @@ cfg_t::cfg_t(exec_list *instructions)
          inst->exec_node::remove();
          cur->instructions.push_tail(inst);
 
+         assert(cur_do != NULL);
 	 cur->add_successor(mem_ctx, cur_do);
 
 	 next = new_block();
@@ -285,6 +289,7 @@ cfg_t::cfg_t(exec_list *instructions)
          inst->exec_node::remove();
          cur->instructions.push_tail(inst);
 
+         assert(cur_while != NULL);
 	 cur->add_successor(mem_ctx, cur_while);
 
 	 next = new_block();
@@ -298,7 +303,12 @@ cfg_t::cfg_t(exec_list *instructions)
          inst->exec_node::remove();
          cur->instructions.push_tail(inst);
 
+         assert(cur_do != NULL && cur_while != NULL);
 	 cur->add_successor(mem_ctx, cur_do);
+
+         if (inst->predicate)
+            cur->add_successor(mem_ctx, cur_while);
+
 	 set_next_block(&cur, cur_while, ip);
 
 	 /* Pop the stack so we're in the previous loop */
@@ -373,6 +383,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 *
@@ -409,16 +420,24 @@ cfg_t::make_block_array()
 }
 
 void
-cfg_t::dump(backend_visitor *v) const
+cfg_t::dump(backend_shader *s)
 {
+   if (idom_dirty)
+      calculate_idom();
+
    foreach_block (block, this) {
-      fprintf(stderr, "START B%d", block->num);
+      if (block->idom)
+         fprintf(stderr, "START B%d IDOM(B%d)", block->num, block->idom->num);
+      else
+         fprintf(stderr, "START B%d IDOM(none)", block->num);
+
       foreach_list_typed(bblock_link, link, link, &block->parents) {
          fprintf(stderr, " <-B%d",
                  link->block->num);
       }
       fprintf(stderr, "\n");
-      block->dump(v);
+      if (s != NULL)
+         block->dump(s);
       fprintf(stderr, "END B%d", block->num);
       foreach_list_typed(bblock_link, link, link, &block->children) {
          fprintf(stderr, " ->B%d",
@@ -427,3 +446,91 @@ 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) {
+      if (block->idom) {
+         printf("\t%d -> %d\n", block->idom->num, block->num);
+      }
+   }
+   printf("}\n");
+}