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