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