diff options
author | Connor Abbott <cwabbott0@gmail.com> | 2021-02-19 12:03:47 +0100 |
---|---|---|
committer | Emma Anholt <emma@anholt.net> | 2021-06-10 12:20:38 -0700 |
commit | d4b5a550ede675748cc2ededd3f19cefcdbc20e1 (patch) | |
tree | 537a9a596d3ca3358a3fb0007b50f3e644c12e03 /src/freedreno | |
parent | 1f3546c9e2de1bdbb0bd76186471022eb66d6163 (diff) |
ir3: Add dominance infrastructure
Mostly lifted from nir.
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/9842>
Diffstat (limited to 'src/freedreno')
-rw-r--r-- | src/freedreno/ir3/ir3.h | 11 | ||||
-rw-r--r-- | src/freedreno/ir3/ir3_dominance.c | 126 | ||||
-rw-r--r-- | src/freedreno/ir3/meson.build | 1 |
3 files changed, 138 insertions, 0 deletions
diff --git a/src/freedreno/ir3/ir3.h b/src/freedreno/ir3/ir3.h index a62eee40dd3..29a4da40875 100644 --- a/src/freedreno/ir3/ir3.h +++ b/src/freedreno/ir3/ir3.h @@ -577,6 +577,14 @@ struct ir3_block { */ void *data; + uint32_t index; + + struct ir3_block *imm_dom; + DECLARE_ARRAY(struct ir3_block *, dom_children); + + uint32_t dom_pre_index; + uint32_t dom_post_index; + #ifdef DEBUG uint32_t serialno; #endif @@ -602,6 +610,9 @@ void ir3_block_add_predecessor(struct ir3_block *block, struct ir3_block *pred); void ir3_block_remove_predecessor(struct ir3_block *block, struct ir3_block *pred); unsigned ir3_block_get_pred_index(struct ir3_block *block, struct ir3_block *pred); +void ir3_calc_dominance(struct ir3 *ir); +bool ir3_block_dominates(struct ir3_block *a, struct ir3_block *b); + struct ir3_shader_variant; struct ir3 * ir3_create(struct ir3_compiler *compiler, struct ir3_shader_variant *v); diff --git a/src/freedreno/ir3/ir3_dominance.c b/src/freedreno/ir3/ir3_dominance.c new file mode 100644 index 00000000000..0b6062ecf1f --- /dev/null +++ b/src/freedreno/ir3/ir3_dominance.c @@ -0,0 +1,126 @@ +/* + * Copyright © 2014 Intel Corporation + * Copyright © 2021 Valve 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. + * + */ + +#include "ir3.h" +#include "ralloc.h" + +/* + * Implements the algorithms for computing the dominance tree and the + * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper, + * Harvey, and Kennedy. + */ + +static struct ir3_block * +intersect(struct ir3_block *b1, struct ir3_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(struct ir3_block *block) +{ + struct ir3_block *new_idom = NULL; + for (unsigned i = 0; i < block->predecessors_count; i++) { + struct ir3_block *pred = block->predecessors[i]; + + if (pred->imm_dom) { + if (new_idom) + new_idom = intersect(pred, new_idom); + else + new_idom = pred; + } + } + + if (block->imm_dom != new_idom) { + block->imm_dom = new_idom; + return true; + } + + return false; +} + +static unsigned +calc_dfs_indices(struct ir3_block *block, unsigned index) +{ + block->dom_pre_index = index++; + for (unsigned i = 0; i < block->dom_children_count; i++) + index = calc_dfs_indices(block->dom_children[i], index); + block->dom_post_index = index++; + return index; +} + +void +ir3_calc_dominance(struct ir3 *ir) +{ + unsigned i = 0; + foreach_block (block, &ir->block_list) { + block->index = i++; + if (block == ir3_start_block(ir)) + block->imm_dom = block; + else + block->imm_dom = NULL; + block->dom_children = NULL; + block->dom_children_count = block->dom_children_sz = 0; + } + + bool progress = true; + while (progress) { + progress = false; + foreach_block (block, &ir->block_list) { + if (block != ir3_start_block(ir)) + progress |= calc_dominance(block); + } + } + + ir3_start_block(ir)->imm_dom = NULL; + + foreach_block (block, &ir->block_list) { + if (block->imm_dom) + array_insert(block->imm_dom, block->imm_dom->dom_children, block); + } + + calc_dfs_indices(ir3_start_block(ir), 0); +} + +/* Return true if a dominates b. This includes if a == b. */ +bool ir3_block_dominates(struct ir3_block *a, struct ir3_block *b) +{ + return a->dom_pre_index <= b->dom_pre_index && + a->dom_post_index >= b->dom_post_index; +} + diff --git a/src/freedreno/ir3/meson.build b/src/freedreno/ir3/meson.build index 534dd02b84d..38e04f6a805 100644 --- a/src/freedreno/ir3/meson.build +++ b/src/freedreno/ir3/meson.build @@ -78,6 +78,7 @@ libfreedreno_ir3_files = files( 'ir3_cp_postsched.c', 'ir3_dce.c', 'ir3_delay.c', + 'ir3_dominance.c', 'ir3_disk_cache.c', 'ir3_group.c', 'ir3_image.c', |