"Fossies" - the Fresh Open Source Software Archive

Member "mesa-20.1.8/src/compiler/nir/nir_dominance.c" (16 Sep 2020, 9328 Bytes) of package /linux/misc/mesa-20.1.8.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "nir_dominance.c" see the Fossies "Dox" file reference documentation.

    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(block, impl) {
  135       if (block->imm_dom)
  136          block->imm_dom->num_dom_children++;
  137    }
  138 
  139    nir_foreach_block(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(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(block, impl) {
  174       init_block(block, impl);
  175    }
  176 
  177    bool progress = true;
  178    while (progress) {
  179       progress = false;
  180       nir_foreach_block(block, impl) {
  181          if (block != nir_start_block(impl))
  182             progress |= calc_dominance(block);
  183       }
  184    }
  185 
  186    nir_foreach_block(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(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(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(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 }