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