From c9a608c0907ccdd745c8cb496e982bca68f8e6e4 Mon Sep 17 00:00:00 2001
From: Francisco Jerez <currojerez@riseup.net>
Date: Thu, 10 Mar 2016 20:49:54 -0800
Subject: [PATCH] intel/compiler: Move dominance tree data structure into
 idom_tree object

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.

Reviewed-by: Matt Turner <mattst88@gmail.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4012>
---
 src/intel/compiler/brw_cfg.cpp | 51 ++++++++++++++++++----------------
 src/intel/compiler/brw_cfg.h   | 22 +++++++++++++--
 2 files changed, 47 insertions(+), 26 deletions(-)

diff --git a/src/intel/compiler/brw_cfg.cpp b/src/intel/compiler/brw_cfg.cpp
index b71c36ed68b..b681e098ab6 100644
--- a/src/intel/compiler/brw_cfg.cpp
+++ b/src/intel/compiler/brw_cfg.cpp
@@ -63,7 +63,7 @@ push_stack(exec_list *list, 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), cycle_count(0)
+   cfg(cfg), start_ip(0), end_ip(0), num(0), cycle_count(0)
 {
    instructions.make_empty();
    parents.make_empty();
@@ -504,8 +504,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);
 
@@ -535,14 +536,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;
 
@@ -551,24 +552,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
 {
@@ -578,23 +584,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/intel/compiler/brw_cfg.h b/src/intel/compiler/brw_cfg.h
index 21431cd46d0..404a49c28b7 100644
--- a/src/intel/compiler/brw_cfg.h
+++ b/src/intel/compiler/brw_cfg.h
@@ -111,7 +111,6 @@ struct bblock_t {
 
    struct exec_node link;
    struct cfg_t *cfg;
-   struct bblock_t *idom;
 
    int start_ip;
    int end_ip;
@@ -387,6 +386,7 @@ namespace brw {
     */
    struct idom_tree {
       idom_tree(const backend_shader *s);
+      ~idom_tree();
 
       bool
       validate(const backend_shader *) const
@@ -401,11 +401,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.30.2