[Mesa-dev] [PATCH 016/133] nir: calculate dominance information
Jason Ekstrand
jason at jlekstrand.net
Mon Dec 15 22:04:26 PST 2014
From: Connor Abbott <connor.abbott at intel.com>
---
src/glsl/Makefile.sources | 1 +
src/glsl/nir/nir.c | 12 +-
src/glsl/nir/nir.h | 25 ++++
src/glsl/nir/nir_dominance.c | 300 +++++++++++++++++++++++++++++++++++++++++++
4 files changed, 337 insertions(+), 1 deletion(-)
create mode 100644 src/glsl/nir/nir_dominance.c
diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
index 6bc7cd7..c736d6a 100644
--- a/src/glsl/Makefile.sources
+++ b/src/glsl/Makefile.sources
@@ -16,6 +16,7 @@ LIBGLCPP_GENERATED_FILES = \
NIR_FILES = \
$(GLSL_SRCDIR)/nir/nir.c \
$(GLSL_SRCDIR)/nir/nir.h \
+ $(GLSL_SRCDIR)/nir/nir_dominance.c \
$(GLSL_SRCDIR)/nir/nir_intrinsics.c \
$(GLSL_SRCDIR)/nir/nir_intrinsics.h \
$(GLSL_SRCDIR)/nir/nir_lower_atomics.c \
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index cad8c6a..3dd9e5a 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -244,6 +244,7 @@ nir_function_impl_create(nir_function_overload *overload)
impl->reg_alloc = 0;
impl->ssa_alloc = 0;
impl->block_index_dirty = true;
+ impl->dominance_dirty = true;
/* create start & end blocks */
nir_block *start_block = nir_block_create(mem_ctx);
@@ -270,6 +271,8 @@ nir_block_create(void *mem_ctx)
block->successors[0] = block->successors[1] = NULL;
block->predecessors = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
+ block->imm_dom = NULL;
+ block->dom_frontier = _mesa_set_create(mem_ctx, _mesa_key_pointer_equal);
exec_list_make_empty(&block->instr_list);
@@ -811,6 +814,9 @@ handle_jump(nir_block *block)
unlink_block_successors(block);
+ nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
+ impl->dominance_dirty = true;
+
if (jump_instr->type == nir_jump_break ||
jump_instr->type == nir_jump_continue) {
nir_loop *loop = nearest_loop(&block->cf_node);
@@ -834,7 +840,6 @@ handle_jump(nir_block *block)
unlink_blocks(last_block, after_block);
}
} else {
- nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
link_blocks(block, impl->end_block, NULL);
}
}
@@ -905,6 +910,9 @@ handle_remove_jump(nir_block *block, nir_jump_type type)
block_add_pred(next_block, last_block);
}
}
+
+ nir_function_impl *impl = nir_cf_node_get_function(&block->cf_node);
+ impl->dominance_dirty = true;
}
/**
@@ -1012,6 +1020,7 @@ nir_cf_node_insert_after(nir_cf_node *node, nir_cf_node *after)
nir_function_impl *impl = nir_cf_node_get_function(node);
impl->block_index_dirty = true;
+ impl->dominance_dirty = true;
}
void
@@ -1054,6 +1063,7 @@ nir_cf_node_insert_before(nir_cf_node *node, nir_cf_node *before)
nir_function_impl *impl = nir_cf_node_get_function(node);
impl->block_index_dirty = true;
+ impl->dominance_dirty = true;
}
void
diff --git a/src/glsl/nir/nir.h b/src/glsl/nir/nir.h
index 7fbe112..daa7dfc 100644
--- a/src/glsl/nir/nir.h
+++ b/src/glsl/nir/nir.h
@@ -979,6 +979,18 @@ typedef struct nir_block {
struct nir_block *successors[2];
struct set *predecessors;
+
+ /*
+ * this node's immediate dominator in the dominance tree - set to NULL for
+ * the start block.
+ */
+ struct nir_block *imm_dom;
+
+ /* This node's children in the dominance tree */
+ unsigned num_dom_children;
+ struct nir_block **dom_children;
+
+ struct set *dom_frontier;
} nir_block;
#define nir_block_first_instr(block) \
@@ -1052,6 +1064,7 @@ typedef struct {
unsigned num_blocks;
bool block_index_dirty;
+ bool dominance_dirty;
} nir_function_impl;
#define nir_cf_node_next(_node) \
@@ -1249,6 +1262,18 @@ void nir_print_shader(nir_shader *shader, FILE *fp);
void nir_validate_shader(nir_shader *shader);
+void nir_calc_dominance_impl(nir_function_impl *impl);
+void nir_calc_dominance(nir_shader *shader);
+
+void nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp);
+void nir_dump_dom_tree(nir_shader *shader, FILE *fp);
+
+void nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp);
+void nir_dump_dom_frontier(nir_shader *shader, FILE *fp);
+
+void nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp);
+void nir_dump_cfg(nir_shader *shader, FILE *fp);
+
void nir_lower_variables_scalar(nir_shader *shader, bool lower_globals,
bool lower_io, bool add_names,
bool native_integers);
diff --git a/src/glsl/nir/nir_dominance.c b/src/glsl/nir/nir_dominance.c
new file mode 100644
index 0000000..988a3fc
--- /dev/null
+++ b/src/glsl/nir/nir_dominance.c
@@ -0,0 +1,300 @@
+/*
+ * Copyright © 2014 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Authors:
+ * Connor Abbott (cwabbott0 at gmail.com)
+ *
+ */
+
+#include "nir.h"
+
+/*
+ * Implements the algorithms for computing the dominance tree and the
+ * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper,
+ * Harvey, and Kennedy.
+ */
+
+typedef struct {
+ nir_function_impl *impl;
+ bool progress;
+} dom_state;
+
+static bool
+init_block_cb(nir_block *block, void *_state)
+{
+ dom_state *state = (dom_state *) _state;
+ if (block == state->impl->start_block)
+ block->imm_dom = block;
+ else
+ block->imm_dom = NULL;
+ block->num_dom_children = 0;
+
+ struct set_entry *entry;
+ set_foreach(block->dom_frontier, entry) {
+ _mesa_set_remove(block->dom_frontier, entry);
+ }
+
+ return true;
+}
+
+static nir_block *
+intersect(nir_block *b1, nir_block *b2)
+{
+ while (b1 != 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->index > b2->index)
+ b1 = b1->imm_dom;
+ while (b2->index > b1->index)
+ b2 = b2->imm_dom;
+ }
+
+ return b1;
+}
+
+static bool
+calc_dominance_cb(nir_block *block, void *_state)
+{
+ dom_state *state = (dom_state *) _state;
+ if (block == state->impl->start_block)
+ return true;
+
+ nir_block *new_idom = NULL;
+ struct set_entry *entry;
+ set_foreach(block->predecessors, entry) {
+ nir_block *pred = (nir_block *) entry->key;
+
+ if (pred->imm_dom) {
+ if (new_idom)
+ new_idom = intersect(pred, new_idom);
+ else
+ new_idom = pred;
+ }
+ }
+
+ assert(new_idom);
+ if (block->imm_dom != new_idom) {
+ block->imm_dom = new_idom;
+ state->progress = true;
+ }
+
+ return true;
+}
+
+static bool
+calc_dom_frontier_cb(nir_block *block, void *state)
+{
+ (void) state;
+
+ if (block->predecessors->entries > 1) {
+ struct set_entry *entry;
+ set_foreach(block->predecessors, entry) {
+ nir_block *runner = (nir_block *) entry->key;
+ while (runner != block->imm_dom) {
+ _mesa_set_add(runner->dom_frontier, _mesa_hash_pointer(block),
+ block);
+ runner = runner->imm_dom;
+ }
+ }
+ }
+
+ return true;
+}
+
+/*
+ * Compute each node's children in the dominance tree from the immediate
+ * dominator information. We do this in three stages:
+ *
+ * 1. Calculate the number of children each node has
+ * 2. Allocate arrays, setting the number of children to 0 again
+ * 3. For each node, add itself to its parent's list of children, using
+ * num_dom_children as an index - at the end of this step, num_dom_children
+ * for each node will be the same as it was at the end of step #1.
+ */
+
+static bool
+block_count_children(nir_block *block, void *state)
+{
+ (void) state;
+
+ if (block->imm_dom)
+ block->imm_dom->num_dom_children++;
+
+ return true;
+}
+
+static bool
+block_alloc_children(nir_block *block, void *state)
+{
+ void *mem_ctx = state;
+
+ block->dom_children = ralloc_array(mem_ctx, nir_block *,
+ block->num_dom_children);
+ block->num_dom_children = 0;
+
+ return true;
+}
+
+static bool
+block_add_child(nir_block *block, void *state)
+{
+ (void) state;
+
+ if (block->imm_dom)
+ block->imm_dom->dom_children[block->imm_dom->num_dom_children++] = block;
+
+ return true;
+}
+
+static void
+calc_dom_children(nir_function_impl* impl)
+{
+ void *mem_ctx = ralloc_parent(impl);
+
+ nir_foreach_block(impl, block_count_children, NULL);
+ nir_foreach_block(impl, block_alloc_children, mem_ctx);
+ nir_foreach_block(impl, block_add_child, NULL);
+}
+
+void
+nir_calc_dominance_impl(nir_function_impl *impl)
+{
+ if (!impl->dominance_dirty)
+ return;
+
+ nir_index_blocks(impl);
+
+ dom_state state;
+ state.impl = impl;
+ state.progress = true;
+
+ nir_foreach_block(impl, init_block_cb, &state);
+
+ while (state.progress) {
+ state.progress = false;
+ nir_foreach_block(impl, calc_dominance_cb, &state);
+ }
+
+ nir_foreach_block(impl, calc_dom_frontier_cb, &state);
+
+ impl->start_block->imm_dom = NULL;
+
+ calc_dom_children(impl);
+
+ impl->dominance_dirty = false;
+}
+
+void
+nir_calc_dominance(nir_shader *shader)
+{
+ nir_foreach_overload(shader, overload) {
+ if (overload->impl)
+ nir_calc_dominance_impl(overload->impl);
+ }
+}
+
+static bool
+dump_block_dom(nir_block *block, void *state)
+{
+ FILE *fp = (FILE *) state;
+ if (block->imm_dom)
+ fprintf(fp, "\t%u -> %u\n", block->imm_dom->index, block->index);
+ return true;
+}
+
+void
+nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp)
+{
+ fprintf(fp, "digraph doms_%s {\n", impl->overload->function->name);
+ nir_foreach_block(impl, dump_block_dom, fp);
+ fprintf(fp, "}\n\n");
+}
+
+void
+nir_dump_dom_tree(nir_shader *shader, FILE *fp)
+{
+ nir_foreach_overload(shader, overload) {
+ if (overload->impl)
+ nir_dump_dom_tree_impl(overload->impl, fp);
+ }
+}
+
+static bool
+dump_block_dom_frontier(nir_block *block, void *state)
+{
+ FILE *fp = (FILE *) state;
+
+ fprintf(fp, "DF(%u) = {", block->index);
+ struct set_entry *entry;
+ set_foreach(block->dom_frontier, entry) {
+ nir_block *df = (nir_block *) entry->key;
+ fprintf(fp, "%u, ", df->index);
+ }
+ fprintf(fp, "}\n");
+ return true;
+}
+
+void
+nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp)
+{
+ nir_foreach_block(impl, dump_block_dom_frontier, fp);
+}
+
+void
+nir_dump_dom_frontier(nir_shader *shader, FILE *fp)
+{
+ nir_foreach_overload(shader, overload) {
+ if (overload->impl)
+ nir_dump_dom_frontier_impl(overload->impl, fp);
+ }
+}
+
+static bool
+dump_block_succs(nir_block *block, void *state)
+{
+ FILE *fp = (FILE *) state;
+ if (block->successors[0])
+ fprintf(fp, "\t%u -> %u\n", block->index, block->successors[0]->index);
+ if (block->successors[1])
+ fprintf(fp, "\t%u -> %u\n", block->index, block->successors[1]->index);
+ return true;
+}
+
+void
+nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp)
+{
+ fprintf(fp, "digraph cfg_%s {\n", impl->overload->function->name);
+ nir_foreach_block(impl, dump_block_succs, fp);
+ fprintf(fp, "}\n\n");
+}
+
+void
+nir_dump_cfg(nir_shader *shader, FILE *fp)
+{
+ nir_foreach_overload(shader, overload) {
+ if (overload->impl)
+ nir_dump_cfg_impl(overload->impl, fp);
+ }
+}
--
2.2.0
More information about the mesa-dev
mailing list