i965/cfg: Calculate the immediate dominators.

Reviewed-by: Kenneth Graunke <[email protected]>

1 files changed, 70 insertions, 3 deletions

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index ca5b01cd03d..b8e5e2edba3 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();
@@ -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;
@@ -373,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 *
@@ -409,10 +411,13 @@ 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);
@@ -428,3 +433,65 @@ 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;
+}