Mesa (master): i965/cfg: Calculate the immediate dominators.

[Matt Turner]

Module: Mesa
Branch: master
Commit: 0e3dbc0248340bebd1a3012f18db5383ec90b077
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=0e3dbc0248340bebd1a3012f18db5383ec90b077

Author: Matt Turner <mattst88 at gmail.com>
Date:   Tue Feb 18 16:35:56 2014 -0800

i965/cfg: Calculate the immediate dominators.

Reviewed-by: Kenneth Graunke <kenneth at whitecape.org>

---

 src/mesa/drivers/dri/i965/brw_cfg.cpp |   73 +++++++++++++++++++++++++++++++--
 src/mesa/drivers/dri/i965/brw_cfg.h   |    7 +++-
 2 files changed, 76 insertions(+), 4 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index ca5b01c..b8e5e2e 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;
+}
diff --git a/src/mesa/drivers/dri/i965/brw_cfg.h b/src/mesa/drivers/dri/i965/brw_cfg.h
index 0b60fec..215f248 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.h
+++ b/src/mesa/drivers/dri/i965/brw_cfg.h
@@ -81,6 +81,7 @@ struct bblock_t {
 
    struct exec_node link;
    struct cfg_t *cfg;
+   struct bblock_t *idom;
 
    int start_ip;
    int end_ip;
@@ -269,8 +270,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;
 
@@ -278,6 +281,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