[Mesa-dev] [RFC 2/9] i965/cfg: Calculate the immediate dominators.

[Matt Turner]

---
 src/mesa/drivers/dri/i965/brw_cfg.cpp              | 68 +++++++++++++++++++++-
 src/mesa/drivers/dri/i965/brw_cfg.h                |  7 ++-
 .../drivers/dri/i965/brw_dead_control_flow.cpp     |  5 +-
 3 files changed, 75 insertions(+), 5 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index e10ff99..622b7de 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),
    if_block(NULL), else_block(NULL)
 {
    instructions.make_empty();
@@ -159,6 +159,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;
@@ -422,10 +423,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);
@@ -441,3 +445,61 @@ 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)
+{
+   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;
+}
diff --git a/src/mesa/drivers/dri/i965/brw_cfg.h b/src/mesa/drivers/dri/i965/brw_cfg.h
index c06ed61..86bdbf3 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.h
+++ b/src/mesa/drivers/dri/i965/brw_cfg.h
@@ -75,6 +75,7 @@ struct bblock_t {
 
    struct exec_node link;
    struct cfg_t *cfg;
+   struct bblock_t *idom;
 
    int start_ip;
    int end_ip;
@@ -203,8 +204,10 @@ struct cfg_t {
    bblock_t *new_block();
    void set_next_block(bblock_t **cur, bblock_t *block, int ip);
    void make_block_array();
+   void calculate_idom();
+   static bblock_t *intersect(bblock_t *b1, bblock_t *b2);
 
-   void dump(backend_visitor *v) const;
+   void dump(backend_visitor *v);
 #endif
    void *mem_ctx;
 
@@ -212,6 +215,8 @@ struct cfg_t {
    struct exec_list block_list;
    struct bblock_t **blocks;
    int num_blocks;
+
+   bool idom_dirty;
 };
 
 /* Note that this is implemented with a double for loop -- break will
diff --git a/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp b/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
index 4c9d7b9..575dbd4 100644
--- a/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
+++ b/src/mesa/drivers/dri/i965/brw_dead_control_flow.cpp
@@ -122,8 +122,11 @@ dead_control_flow_eliminate(backend_visitor *v)
       }
    }
 
-   if (progress)
+   if (progress) {
       v->invalidate_live_intervals();
 
+      v->cfg->idom_dirty = true;
+   }
+
    return progress;
 }
-- 
2.0.4