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    set_foreach(block->dom_frontier, entry) {
  46       _mesa_set_remove(block->dom_frontier, entry);
  47    }
  48
  49    return true;
  50 }
  51
  52 static nir_block *
  53 intersect(nir_block *b1, nir_block *b2)
  54 {
  55    while (b1 != b2) {
  56       /*
  57        * Note, the comparisons here are the opposite of what the paper says
  58        * because we index blocks from beginning -> end (i.e. reverse
  59        * post-order) instead of post-order like they assume.
  60        */
  61       while (b1->index > b2->index)
  62          b1 = b1->imm_dom;
  63       while (b2->index > b1->index)
  64          b2 = b2->imm_dom;
  65    }
  66
  67    return b1;
  68 }
  69
  70 static bool
  71 calc_dominance(nir_block *block)
  72 {
  73    nir_block *new_idom = NULL;
  74    set_foreach(block->predecessors, entry) {
  75       nir_block *pred = (nir_block *) entry->key;
  76
  77       if (pred->imm_dom) {
  78          if (new_idom)
  79             new_idom = intersect(pred, new_idom);
  80          else
  81             new_idom = pred;
  82       }
  83    }
  84
  85    if (block->imm_dom != new_idom) {
  86       block->imm_dom = new_idom;
  87       return true;
  88    }
  89
  90    return false;
  91 }
  92
  93 static bool
  94 calc_dom_frontier(nir_block *block)
  95 {
  96    if (block->predecessors->entries > 1) {
  97       set_foreach(block->predecessors, entry) {
  98          nir_block *runner = (nir_block *) entry->key;
  99
 100          /* Skip unreachable predecessors */
 101          if (runner->imm_dom == NULL)
 102             continue;
 103
 104          while (runner != block->imm_dom) {
 105             _mesa_set_add(runner->dom_frontier, block);
 106             runner = runner->imm_dom;
 107          }
 108       }
 109    }
 110
 111    return true;
 112 }
 113
 114 /*
 115  * Compute each node's children in the dominance tree from the immediate
 116  * dominator information. We do this in three stages:
 117  *
 118  * 1. Calculate the number of children each node has
 119  * 2. Allocate arrays, setting the number of children to 0 again
 120  * 3. For each node, add itself to its parent's list of children, using
 121  *    num_dom_children as an index - at the end of this step, num_dom_children
 122  *    for each node will be the same as it was at the end of step #1.
 123  */
 124
 125 static void
 126 calc_dom_children(nir_function_impl* impl)
 127 {
 128    void *mem_ctx = ralloc_parent(impl);
 129
 130    nir_foreach_block(block, impl) {
 131       if (block->imm_dom)
 132          block->imm_dom->num_dom_children++;
 133    }
 134
 135    nir_foreach_block(block, impl) {
 136       block->dom_children = ralloc_array(mem_ctx, nir_block *,
 137                                          block->num_dom_children);
 138       block->num_dom_children = 0;
 139    }
 140
 141    nir_foreach_block(block, impl) {
 142       if (block->imm_dom) {
 143          block->imm_dom->dom_children[block->imm_dom->num_dom_children++]
 144             = block;
 145       }
 146    }
 147 }
 148
 149 static void
 150 calc_dfs_indicies(nir_block *block, unsigned *index)
 151 {
 152    block->dom_pre_index = (*index)++;
 153
 154    for (unsigned i = 0; i < block->num_dom_children; i++)
 155       calc_dfs_indicies(block->dom_children[i], index);
 156
 157    block->dom_post_index = (*index)++;
 158 }
 159
 160 void
 161 nir_calc_dominance_impl(nir_function_impl *impl)
 162 {
 163    if (impl->valid_metadata & nir_metadata_dominance)
 164       return;
 165
 166    nir_metadata_require(impl, nir_metadata_block_index);
 167
 168
 169    nir_foreach_block(block, impl) {
 170       init_block(block, impl);
 171    }
 172
 173    bool progress = true;
 174    while (progress) {
 175       progress = false;
 176       nir_foreach_block(block, impl) {
 177          if (block != nir_start_block(impl))
 178             progress |= calc_dominance(block);
 179       }
 180    }
 181
 182    nir_foreach_block(block, impl) {
 183       calc_dom_frontier(block);
 184    }
 185
 186    nir_block *start_block = nir_start_block(impl);
 187    start_block->imm_dom = NULL;
 188
 189    calc_dom_children(impl);
 190
 191    unsigned dfs_index = 0;
 192    calc_dfs_indicies(start_block, &dfs_index);
 193 }
 194
 195 void
 196 nir_calc_dominance(nir_shader *shader)
 197 {
 198    nir_foreach_function(function, shader) {
 199       if (function->impl)
 200          nir_calc_dominance_impl(function->impl);
 201    }
 202 }
 203
 204 /**
 205  * Computes the least common anscestor of two blocks.  If one of the blocks
 206  * is null, the other block is returned.
 207  */
 208 nir_block *
 209 nir_dominance_lca(nir_block *b1, nir_block *b2)
 210 {
 211    if (b1 == NULL)
 212       return b2;
 213
 214    if (b2 == NULL)
 215       return b1;
 216
 217    assert(nir_cf_node_get_function(&b1->cf_node) ==
 218           nir_cf_node_get_function(&b2->cf_node));
 219
 220    assert(nir_cf_node_get_function(&b1->cf_node)->valid_metadata &
 221           nir_metadata_dominance);
 222
 223    return intersect(b1, b2);
 224 }
 225
 226 /**
 227  * Returns true if parent dominates child
 228  */
 229 bool
 230 nir_block_dominates(nir_block *parent, nir_block *child)
 231 {
 232    assert(nir_cf_node_get_function(&parent->cf_node) ==
 233           nir_cf_node_get_function(&child->cf_node));
 234
 235    assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
 236           nir_metadata_dominance);
 237
 238    return child->dom_pre_index >= parent->dom_pre_index &&
 239           child->dom_post_index <= parent->dom_post_index;
 240 }
 241
 242 void
 243 nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp)
 244 {
 245    fprintf(fp, "digraph doms_%s {\n", impl->function->name);
 246
 247    nir_foreach_block(block, impl) {
 248       if (block->imm_dom)
 249          fprintf(fp, "\t%u -> %u\n", block->imm_dom->index, block->index);
 250    }
 251
 252    fprintf(fp, "}\n\n");
 253 }
 254
 255 void
 256 nir_dump_dom_tree(nir_shader *shader, FILE *fp)
 257 {
 258    nir_foreach_function(function, shader) {
 259       if (function->impl)
 260          nir_dump_dom_tree_impl(function->impl, fp);
 261    }
 262 }
 263
 264 void
 265 nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp)
 266 {
 267    nir_foreach_block(block, impl) {
 268       fprintf(fp, "DF(%u) = {", block->index);
 269       set_foreach(block->dom_frontier, entry) {
 270          nir_block *df = (nir_block *) entry->key;
 271          fprintf(fp, "%u, ", df->index);
 272       }
 273       fprintf(fp, "}\n");
 274    }
 275 }
 276
 277 void
 278 nir_dump_dom_frontier(nir_shader *shader, FILE *fp)
 279 {
 280    nir_foreach_function(function, shader) {
 281       if (function->impl)
 282          nir_dump_dom_frontier_impl(function->impl, fp);
 283    }
 284 }
 285
 286 void
 287 nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp)
 288 {
 289    fprintf(fp, "digraph cfg_%s {\n", impl->function->name);
 290
 291    nir_foreach_block(block, impl) {
 292       if (block->successors[0])
 293          fprintf(fp, "\t%u -> %u\n", block->index, block->successors[0]->index);
 294       if (block->successors[1])
 295          fprintf(fp, "\t%u -> %u\n", block->index, block->successors[1]->index);
 296    }
 297
 298    fprintf(fp, "}\n\n");
 299 }
 300
 301 void
 302 nir_dump_cfg(nir_shader *shader, FILE *fp)
 303 {
 304    nir_foreach_function(function, shader) {
 305       if (function->impl)
 306          nir_dump_cfg_impl(function->impl, fp);
 307    }
 308 }