src/compiler/nir/nir_dominance.c

   1 /*
   2  * Copyright © 2014 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *    Connor Abbott (cwabbott0@gmail.com)
  25  *
  26  */
  27
  28 #include "nir.h"
  29
  30 /*
  31  * Implements the algorithms for computing the dominance tree and the
  32  * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper,
  33  * Harvey, and Kennedy.
  34  */
  35
  36 static bool
  37 init_block(nir_block *block, nir_function_impl *impl)
  38 {
  39    if (block == nir_start_block(impl))
  40       block->imm_dom = block;
  41    else
  42       block->imm_dom = NULL;
  43    block->num_dom_children = 0;
  44
  45    /* See nir_block_dominates */
  46    block->dom_pre_index = INT16_MAX;
  47    block->dom_post_index = -1;
  48
  49    set_foreach(block->dom_frontier, entry) {
  50       _mesa_set_remove(block->dom_frontier, entry);
  51    }
  52
  53    return true;
  54 }
  55
  56 static nir_block *
  57 intersect(nir_block *b1, nir_block *b2)
  58 {
  59    while (b1 != b2) {
  60       /*
  61        * Note, the comparisons here are the opposite of what the paper says
  62        * because we index blocks from beginning -> end (i.e. reverse
  63        * post-order) instead of post-order like they assume.
  64        */
  65       while (b1->index > b2->index)
  66          b1 = b1->imm_dom;
  67       while (b2->index > b1->index)
  68          b2 = b2->imm_dom;
  69    }
  70
  71    return b1;
  72 }
  73
  74 static bool
  75 calc_dominance(nir_block *block)
  76 {
  77    nir_block *new_idom = NULL;
  78    set_foreach(block->predecessors, entry) {
  79       nir_block *pred = (nir_block *) entry->key;
  80
  81       if (pred->imm_dom) {
  82          if (new_idom)
  83             new_idom = intersect(pred, new_idom);
  84          else
  85             new_idom = pred;
  86       }
  87    }
  88
  89    if (block->imm_dom != new_idom) {
  90       block->imm_dom = new_idom;
  91       return true;
  92    }
  93
  94    return false;
  95 }
  96
  97 static bool
  98 calc_dom_frontier(nir_block *block)
  99 {
 100    if (block->predecessors->entries > 1) {
 101       set_foreach(block->predecessors, entry) {
 102          nir_block *runner = (nir_block *) entry->key;
 103
 104          /* Skip unreachable predecessors */
 105          if (runner->imm_dom == NULL)
 106             continue;
 107
 108          while (runner != block->imm_dom) {
 109             _mesa_set_add(runner->dom_frontier, block);
 110             runner = runner->imm_dom;
 111          }
 112       }
 113    }
 114
 115    return true;
 116 }
 117
 118 /*
 119  * Compute each node's children in the dominance tree from the immediate
 120  * dominator information. We do this in three stages:
 121  *
 122  * 1. Calculate the number of children each node has
 123  * 2. Allocate arrays, setting the number of children to 0 again
 124  * 3. For each node, add itself to its parent's list of children, using
 125  *    num_dom_children as an index - at the end of this step, num_dom_children
 126  *    for each node will be the same as it was at the end of step #1.
 127  */
 128
 129 static void
 130 calc_dom_children(nir_function_impl* impl)
 131 {
 132    void *mem_ctx = ralloc_parent(impl);
 133
 134    nir_foreach_block_unstructured(block, impl) {
 135       if (block->imm_dom)
 136          block->imm_dom->num_dom_children++;
 137    }
 138
 139    nir_foreach_block_unstructured(block, impl) {
 140       block->dom_children = ralloc_array(mem_ctx, nir_block *,
 141                                          block->num_dom_children);
 142       block->num_dom_children = 0;
 143    }
 144
 145    nir_foreach_block_unstructured(block, impl) {
 146       if (block->imm_dom) {
 147          block->imm_dom->dom_children[block->imm_dom->num_dom_children++]
 148             = block;
 149       }
 150    }
 151 }
 152
 153 static void
 154 calc_dfs_indicies(nir_block *block, unsigned *index)
 155 {
 156    block->dom_pre_index = (*index)++;
 157
 158    for (unsigned i = 0; i < block->num_dom_children; i++)
 159       calc_dfs_indicies(block->dom_children[i], index);
 160
 161    block->dom_post_index = (*index)++;
 162 }
 163
 164 void
 165 nir_calc_dominance_impl(nir_function_impl *impl)
 166 {
 167    if (impl->valid_metadata & nir_metadata_dominance)
 168       return;
 169
 170    nir_metadata_require(impl, nir_metadata_block_index);
 171
 172
 173    nir_foreach_block_unstructured(block, impl) {
 174       init_block(block, impl);
 175    }
 176
 177    bool progress = true;
 178    while (progress) {
 179       progress = false;
 180       nir_foreach_block_unstructured(block, impl) {
 181          if (block != nir_start_block(impl))
 182             progress |= calc_dominance(block);
 183       }
 184    }
 185
 186    nir_foreach_block_unstructured(block, impl) {
 187       calc_dom_frontier(block);
 188    }
 189
 190    nir_block *start_block = nir_start_block(impl);
 191    start_block->imm_dom = NULL;
 192
 193    calc_dom_children(impl);
 194
 195    unsigned dfs_index = 0;
 196    calc_dfs_indicies(start_block, &dfs_index);
 197 }
 198
 199 void
 200 nir_calc_dominance(nir_shader *shader)
 201 {
 202    nir_foreach_function(function, shader) {
 203       if (function->impl)
 204          nir_calc_dominance_impl(function->impl);
 205    }
 206 }
 207
 208 static nir_block *
 209 block_return_if_reachable(nir_block *b)
 210 {
 211    return (b && nir_block_is_reachable(b)) ? b : NULL;
 212 }
 213
 214 /**
 215  * Computes the least common ancestor of two blocks.  If one of the blocks
 216  * is null or unreachable, the other block is returned or NULL if it's
 217  * unreachable.
 218  */
 219 nir_block *
 220 nir_dominance_lca(nir_block *b1, nir_block *b2)
 221 {
 222    if (b1 == NULL || !nir_block_is_reachable(b1))
 223       return block_return_if_reachable(b2);
 224
 225    if (b2 == NULL || !nir_block_is_reachable(b2))
 226       return block_return_if_reachable(b1);
 227
 228    assert(nir_cf_node_get_function(&b1->cf_node) ==
 229           nir_cf_node_get_function(&b2->cf_node));
 230
 231    assert(nir_cf_node_get_function(&b1->cf_node)->valid_metadata &
 232           nir_metadata_dominance);
 233
 234    return intersect(b1, b2);
 235 }
 236
 237 /**
 238  * Returns true if parent dominates child according to the following
 239  * definition:
 240  *
 241  *    "The block A dominates the block B if every path from the start block
 242  *    to block B passes through A."
 243  *
 244  * This means, in particular, that any unreachable block is dominated by every
 245  * other block and an unreachable block does not dominate anything except
 246  * another unreachable block.
 247  */
 248 bool
 249 nir_block_dominates(nir_block *parent, nir_block *child)
 250 {
 251    assert(nir_cf_node_get_function(&parent->cf_node) ==
 252           nir_cf_node_get_function(&child->cf_node));
 253
 254    assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
 255           nir_metadata_dominance);
 256
 257    /* If a block is unreachable, then nir_block::dom_pre_index == INT16_MAX
 258     * and nir_block::dom_post_index == -1.  This allows us to trivially handle
 259     * unreachable blocks here with zero extra work.
 260     */
 261    return child->dom_pre_index >= parent->dom_pre_index &&
 262           child->dom_post_index <= parent->dom_post_index;
 263 }
 264
 265 bool
 266 nir_block_is_unreachable(nir_block *block)
 267 {
 268    assert(nir_cf_node_get_function(&block->cf_node)->valid_metadata &
 269           nir_metadata_dominance);
 270    assert(nir_cf_node_get_function(&block->cf_node)->valid_metadata &
 271           nir_metadata_block_index);
 272
 273    /* Unreachable blocks have no dominator.  The only reachable block with no
 274     * dominator is the start block which has index 0.
 275     */
 276    return block->index > 0 && block->imm_dom == NULL;
 277 }
 278
 279 void
 280 nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp)
 281 {
 282    fprintf(fp, "digraph doms_%s {\n", impl->function->name);
 283
 284    nir_foreach_block_unstructured(block, impl) {
 285       if (block->imm_dom)
 286          fprintf(fp, "\t%u -> %u\n", block->imm_dom->index, block->index);
 287    }
 288
 289    fprintf(fp, "}\n\n");
 290 }
 291
 292 void
 293 nir_dump_dom_tree(nir_shader *shader, FILE *fp)
 294 {
 295    nir_foreach_function(function, shader) {
 296       if (function->impl)
 297          nir_dump_dom_tree_impl(function->impl, fp);
 298    }
 299 }
 300
 301 void
 302 nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp)
 303 {
 304    nir_foreach_block_unstructured(block, impl) {
 305       fprintf(fp, "DF(%u) = {", block->index);
 306       set_foreach(block->dom_frontier, entry) {
 307          nir_block *df = (nir_block *) entry->key;
 308          fprintf(fp, "%u, ", df->index);
 309       }
 310       fprintf(fp, "}\n");
 311    }
 312 }
 313
 314 void
 315 nir_dump_dom_frontier(nir_shader *shader, FILE *fp)
 316 {
 317    nir_foreach_function(function, shader) {
 318       if (function->impl)
 319          nir_dump_dom_frontier_impl(function->impl, fp);
 320    }
 321 }
 322
 323 void
 324 nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp)
 325 {
 326    fprintf(fp, "digraph cfg_%s {\n", impl->function->name);
 327
 328    nir_foreach_block_unstructured(block, impl) {
 329       if (block->successors[0])
 330          fprintf(fp, "\t%u -> %u\n", block->index, block->successors[0]->index);
 331       if (block->successors[1])
 332          fprintf(fp, "\t%u -> %u\n", block->index, block->successors[1]->index);
 333    }
 334
 335    fprintf(fp, "}\n\n");
 336 }
 337
 338 void
 339 nir_dump_cfg(nir_shader *shader, FILE *fp)
 340 {
 341    nir_foreach_function(function, shader) {
 342       if (function->impl)
 343          nir_dump_cfg_impl(function->impl, fp);
 344    }
 345 }