From 4d083b52c04745d18d8f5446be5805077fa2c51a Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Tue, 17 Jan 2017 18:38:35 -0800 Subject: [PATCH] nir/dominance: Better handle unreachable blocks v2: Fix minor comments (Ken) Reviewed-by: Kenneth Graunke Part-of: --- src/compiler/nir/nir.h | 9 +++++++- src/compiler/nir/nir_dominance.c | 37 ++++++++++++++++++++++++++------ 2 files changed, 38 insertions(+), 8 deletions(-) diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h index b9a5637e68e..105e09347b5 100644 --- a/src/compiler/nir/nir.h +++ b/src/compiler/nir/nir.h @@ -2406,13 +2406,20 @@ typedef struct nir_block { * dom_pre_index and dom_post_index for this block, which makes testing if * a given block is dominated by another block an O(1) operation. */ - unsigned dom_pre_index, dom_post_index; + int16_t dom_pre_index, dom_post_index; /* live in and out for this block; used for liveness analysis */ BITSET_WORD *live_in; BITSET_WORD *live_out; } nir_block; +static inline bool +nir_block_is_reachable(nir_block *b) +{ + /* See also nir_block_dominates */ + return b->dom_post_index != -1; +} + static inline nir_instr * nir_block_first_instr(nir_block *block) { diff --git a/src/compiler/nir/nir_dominance.c b/src/compiler/nir/nir_dominance.c index 8369c28984d..192d3305801 100644 --- 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); } @@ -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,6 +254,10 @@ 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; } -- 2.30.2