diff options
author | Emil Velikov <emil.velikov@collabora.com> | 2016-01-18 12:54:03 +0200 |
---|---|---|
committer | Emil Velikov <emil.l.velikov@gmail.com> | 2016-01-26 16:08:30 +0000 |
commit | a39a8fbbaa129f4e52f2a3ad2747182e9a74d910 (patch) | |
tree | 823e881d54c149cde315bb140e46a8b781cdccb7 /src/glsl/nir/nir_dominance.c | |
parent | f694da80c75cb2a51d0af3b24d68aae9c53d61aa (diff) |
nir: move to compiler/
Signed-off-by: Emil Velikov <emil.velikov@collabora.com>
Acked-by: Matt Turner <mattst88@gmail.com>
Acked-by: Jose Fonseca <jfonseca@vmware.com>
Diffstat (limited to 'src/glsl/nir/nir_dominance.c')
-rw-r--r-- | src/glsl/nir/nir_dominance.c | 350 |
1 files changed, 0 insertions, 350 deletions
diff --git a/src/glsl/nir/nir_dominance.c b/src/glsl/nir/nir_dominance.c deleted file mode 100644 index b345b85e8a0..00000000000 --- a/src/glsl/nir/nir_dominance.c +++ /dev/null @@ -1,350 +0,0 @@ -/* - * 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@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 == nir_start_block(state->impl)) - 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 == nir_start_block(state->impl)) - 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, 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); -} - -static void -calc_dfs_indicies(nir_block *block, unsigned *index) -{ - block->dom_pre_index = (*index)++; - - for (unsigned i = 0; i < block->num_dom_children; i++) - calc_dfs_indicies(block->dom_children[i], index); - - block->dom_post_index = (*index)++; -} - -void -nir_calc_dominance_impl(nir_function_impl *impl) -{ - if (impl->valid_metadata & nir_metadata_dominance) - return; - - nir_metadata_require(impl, nir_metadata_block_index); - - 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); - - nir_block *start_block = nir_start_block(impl); - start_block->imm_dom = NULL; - - calc_dom_children(impl); - - unsigned dfs_index = 0; - calc_dfs_indicies(start_block, &dfs_index); -} - -void -nir_calc_dominance(nir_shader *shader) -{ - nir_foreach_function(shader, function) { - if (function->impl) - nir_calc_dominance_impl(function->impl); - } -} - -/** - * Computes the least common anscestor of two blocks. If one of the blocks - * is null, the other block is returned. - */ -nir_block * -nir_dominance_lca(nir_block *b1, nir_block *b2) -{ - if (b1 == NULL) - return b2; - - if (b2 == NULL) - return b1; - - assert(nir_cf_node_get_function(&b1->cf_node) == - nir_cf_node_get_function(&b2->cf_node)); - - assert(nir_cf_node_get_function(&b1->cf_node)->valid_metadata & - nir_metadata_dominance); - - return intersect(b1, b2); -} - -/** - * Returns true if parent dominates child - */ -bool -nir_block_dominates(nir_block *parent, nir_block *child) -{ - assert(nir_cf_node_get_function(&parent->cf_node) == - nir_cf_node_get_function(&child->cf_node)); - - assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata & - nir_metadata_dominance); - - return child->dom_pre_index >= parent->dom_pre_index && - child->dom_post_index <= parent->dom_post_index; -} - -static bool -dump_block_dom(nir_block *block, void *state) -{ - FILE *fp = 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->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_function(shader, function) { - if (function->impl) - nir_dump_dom_tree_impl(function->impl, fp); - } -} - -static bool -dump_block_dom_frontier(nir_block *block, void *state) -{ - FILE *fp = 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_function(shader, function) { - if (function->impl) - nir_dump_dom_frontier_impl(function->impl, fp); - } -} - -static bool -dump_block_succs(nir_block *block, void *state) -{ - FILE *fp = 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->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_function(shader, function) { - if (function->impl) - nir_dump_cfg_impl(function->impl, fp); - } -} |