[Mesa-dev] [PATCH 27/30] i965/ir: Move dominance tree data structure into idom_tree object.

[Francisco Jerez]

It makes sense to keep the result of analysis passes independent from
the IR itself.  Instead of representing the idom tree as a pointer in
each basic block pointing to its immediate dominator, the whole
dominator tree is represented separately from the IR as an array of
pointers inside the idom_tree object.  This has the advantage that
it's no longer possible to use stale dominance results by accident
without having called require() beforehand, which makes sure that the
idom tree is recalculated if necessary.
---
 src/mesa/drivers/dri/i965/brw_cfg.cpp | 51 ++++++++++++++++++-----------------
 src/mesa/drivers/dri/i965/brw_cfg.h   | 22 +++++++++++++--
 2 files changed, 47 insertions(+), 26 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.cpp b/src/mesa/drivers/dri/i965/brw_cfg.cpp
index f586dd0..f951f44 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.cpp
+++ b/src/mesa/drivers/dri/i965/brw_cfg.cpp
@@ -54,7 +54,7 @@ link(void *mem_ctx, bblock_t *block)
 }
 
 bblock_t::bblock_t(cfg_t *cfg) :
-   cfg(cfg), idom(NULL), start_ip(0), end_ip(0), num(0)
+   cfg(cfg), start_ip(0), end_ip(0), num(0)
 {
    instructions.make_empty();
    parents.make_empty();
@@ -426,8 +426,9 @@ cfg_t::dump(backend_shader *s)
    const idom_tree *idom = (s ? &s->idom_analysis.require() : NULL);
 
    foreach_block (block, this) {
-      if (block->idom)
-         fprintf(stderr, "START B%d IDOM(B%d)", block->num, block->idom->num);
+      if (idom && idom->parent(block))
+         fprintf(stderr, "START B%d IDOM(B%d)", block->num,
+                 idom->parent(block)->num);
       else
          fprintf(stderr, "START B%d IDOM(none)", block->num);
 
@@ -455,14 +456,14 @@ cfg_t::dump(backend_shader *s)
  * (less than 1000 nodes) that this algorithm is significantly faster than
  * others like Lengauer-Tarjan.
  */
-idom_tree::idom_tree(const backend_shader *s)
+idom_tree::idom_tree(const backend_shader *s) :
+   num_parents(s->cfg->num_blocks),
+   parents(new bblock_t *[num_parents]())
 {
-   foreach_block(block, s->cfg) {
-      block->idom = NULL;
-   }
-   s->cfg->blocks[0]->idom = s->cfg->blocks[0];
-
    bool changed;
+
+   parents[0] = s->cfg->blocks[0];
+
    do {
       changed = false;
 
@@ -471,24 +472,29 @@ idom_tree::idom_tree(const backend_shader *s)
             continue;
 
          bblock_t *new_idom = NULL;
-         foreach_list_typed(bblock_link, parent, link, &block->parents) {
-            if (parent->block->idom) {
+         foreach_list_typed(bblock_link, parent_link, link, &block->parents) {
+            if (parent(parent_link->block)) {
                if (new_idom == NULL) {
-                  new_idom = parent->block;
-               } else if (parent->block->idom != NULL) {
-                  new_idom = intersect(parent->block, new_idom);
+                  new_idom = parent_link->block;
+               } else if (parent(parent_link->block) != NULL) {
+                  new_idom = intersect(parent_link->block, new_idom);
                }
             }
          }
 
-         if (block->idom != new_idom) {
-            block->idom = new_idom;
+         if (parent(block) != new_idom) {
+            parents[block->num] = new_idom;
             changed = true;
          }
       }
    } while (changed);
 }
 
+idom_tree::~idom_tree()
+{
+   delete parents;
+}
+
 bblock_t *
 idom_tree::intersect(bblock_t *b1, bblock_t *b2) const
 {
@@ -498,23 +504,20 @@ idom_tree::intersect(bblock_t *b1, bblock_t *b2) const
     */
    while (b1->num != b2->num) {
       while (b1->num > b2->num)
-         b1 = b1->idom;
+         b1 = parent(b1);
       while (b2->num > b1->num)
-         b2 = b2->idom;
+         b2 = parent(b2);
    }
    assert(b1);
    return b1;
 }
 
 void
-idom_tree::dump(const backend_shader *s) const
+idom_tree::dump() const
 {
    printf("digraph DominanceTree {\n");
-   foreach_block(block, s->cfg) {
-      if (block->idom) {
-         printf("\t%d -> %d\n", block->idom->num, block->num);
-      }
-   }
+   for (unsigned i = 0; i < num_parents; i++)
+      printf("\t%d -> %d\n", parents[i]->num, i);
    printf("}\n");
 }
 
diff --git a/src/mesa/drivers/dri/i965/brw_cfg.h b/src/mesa/drivers/dri/i965/brw_cfg.h
index 1c9207c..fe6aa44 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.h
+++ b/src/mesa/drivers/dri/i965/brw_cfg.h
@@ -84,7 +84,6 @@ struct bblock_t {
 
    struct exec_node link;
    struct cfg_t *cfg;
-   struct bblock_t *idom;
 
    int start_ip;
    int end_ip;
@@ -349,6 +348,7 @@ namespace brw {
     */
    struct idom_tree {
       idom_tree(const backend_shader *s);
+      ~idom_tree();
 
       bool
       validate(const backend_shader *) const
@@ -363,11 +363,29 @@ namespace brw {
          return DEPENDENCY_BLOCKS;
       }
 
+      const bblock_t *
+      parent(const bblock_t *b) const
+      {
+         assert(unsigned(b->num) < num_parents);
+         return parents[b->num];
+      }
+
+      bblock_t *
+      parent(bblock_t *b) const
+      {
+         assert(unsigned(b->num) < num_parents);
+         return parents[b->num];
+      }
+
       bblock_t *
       intersect(bblock_t *b1, bblock_t *b2) const;
 
       void
-      dump(const backend_shader *s) const;
+      dump() const;
+
+   private:
+      unsigned num_parents;
+      bblock_t **parents;
    };
 }
 #endif
-- 
2.7.0