nir: Add and use nir_foreach_block_unstructured helpers

[mesa.git] / src / compiler / nir / nir_dominance.c

diff --git a/src/compiler/nir/nir_dominance.c b/src/compiler/nir/nir_dominance.c
index c678727b471c10b3735aea0b5647cc268a61f8e3..e13210bb6e2b6fab2f961800b8f989fd73e31849 100644 (file)
--- a/src/compiler/nir/nir_dominance.c
+++ b/src/compiler/nir/nir_dominance.c
@@ -42,6 +42,10 @@ init_block(nir_block *block, nir_function_impl *impl)
       block->imm_dom = NULL;
    block->num_dom_children = 0;
 
+   /* See nir_block_dominates */
+   block->dom_pre_index = INT16_MAX;
+   block->dom_post_index = -1;
+
    set_foreach(block->dom_frontier, entry) {
       _mesa_set_remove(block->dom_frontier, entry);
    }
@@ -127,18 +131,18 @@ calc_dom_children(nir_function_impl* impl)
 {
    void *mem_ctx = ralloc_parent(impl);
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       if (block->imm_dom)
          block->imm_dom->num_dom_children++;
    }
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       block->dom_children = ralloc_array(mem_ctx, nir_block *,
                                          block->num_dom_children);
       block->num_dom_children = 0;
    }
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       if (block->imm_dom) {
          block->imm_dom->dom_children[block->imm_dom->num_dom_children++]
             = block;
@@ -166,20 +170,20 @@ nir_calc_dominance_impl(nir_function_impl *impl)
    nir_metadata_require(impl, nir_metadata_block_index);
 
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       init_block(block, impl);
    }
 
    bool progress = true;
    while (progress) {
       progress = false;
-      nir_foreach_block(block, impl) {
+      nir_foreach_block_unstructured(block, impl) {
          if (block != nir_start_block(impl))
             progress |= calc_dominance(block);
       }
    }
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       calc_dom_frontier(block);
    }
 
@@ -201,18 +205,25 @@ nir_calc_dominance(nir_shader *shader)
    }
 }
 
+static nir_block *
+block_return_if_reachable(nir_block *b)
+{
+   return (b && nir_block_is_reachable(b)) ? b : NULL;
+}
+
 /**
- * Computes the least common anscestor of two blocks.  If one of the blocks
- * is null, the other block is returned.
+ * Computes the least common ancestor of two blocks.  If one of the blocks
+ * is null or unreachable, the other block is returned or NULL if it's
+ * unreachable.
  */
 nir_block *
 nir_dominance_lca(nir_block *b1, nir_block *b2)
 {
-   if (b1 == NULL)
-      return b2;
+   if (b1 == NULL || !nir_block_is_reachable(b1))
+      return block_return_if_reachable(b2);
 
-   if (b2 == NULL)
-      return b1;
+   if (b2 == NULL || !nir_block_is_reachable(b2))
+      return block_return_if_reachable(b1);
 
    assert(nir_cf_node_get_function(&b1->cf_node) ==
           nir_cf_node_get_function(&b2->cf_node));
@@ -224,7 +235,15 @@ nir_dominance_lca(nir_block *b1, nir_block *b2)
 }
 
 /**
- * Returns true if parent dominates child
+ * Returns true if parent dominates child according to the following
+ * definition:
+ *
+ *    "The block A dominates the block B if every path from the start block
+ *    to block B passes through A."
+ *
+ * This means, in particular, that any unreachable block is dominated by every
+ * other block and an unreachable block does not dominate anything except
+ * another unreachable block.
  */
 bool
 nir_block_dominates(nir_block *parent, nir_block *child)
@@ -235,16 +254,34 @@ nir_block_dominates(nir_block *parent, nir_block *child)
    assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
           nir_metadata_dominance);
 
+   /* If a block is unreachable, then nir_block::dom_pre_index == INT16_MAX
+    * and nir_block::dom_post_index == -1.  This allows us to trivially handle
+    * unreachable blocks here with zero extra work.
+    */
    return child->dom_pre_index >= parent->dom_pre_index &&
           child->dom_post_index <= parent->dom_post_index;
 }
 
+bool
+nir_block_is_unreachable(nir_block *block)
+{
+   assert(nir_cf_node_get_function(&block->cf_node)->valid_metadata &
+          nir_metadata_dominance);
+   assert(nir_cf_node_get_function(&block->cf_node)->valid_metadata &
+          nir_metadata_block_index);
+
+   /* Unreachable blocks have no dominator.  The only reachable block with no
+    * dominator is the start block which has index 0.
+    */
+   return block->index > 0 && block->imm_dom == NULL;
+}
+
 void
 nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp)
 {
    fprintf(fp, "digraph doms_%s {\n", impl->function->name);
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       if (block->imm_dom)
          fprintf(fp, "\t%u -> %u\n", block->imm_dom->index, block->index);
    }
@@ -264,7 +301,7 @@ nir_dump_dom_tree(nir_shader *shader, FILE *fp)
 void
 nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp)
 {
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       fprintf(fp, "DF(%u) = {", block->index);
       set_foreach(block->dom_frontier, entry) {
          nir_block *df = (nir_block *) entry->key;
@@ -288,7 +325,7 @@ nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp)
 {
    fprintf(fp, "digraph cfg_%s {\n", impl->function->name);
 
-   nir_foreach_block(block, impl) {
+   nir_foreach_block_unstructured(block, impl) {
       if (block->successors[0])
          fprintf(fp, "\t%u -> %u\n", block->index, block->successors[0]->index);
       if (block->successors[1])