Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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 == state->impl->start_block)
  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 == state->impl->start_block)
  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.    impl->start_block->imm_dom = NULL;
  213.  
  214.    calc_dom_children(impl);
  215.  
  216.    unsigned dfs_index = 0;
  217.    calc_dfs_indicies(impl->start_block, &dfs_index);
  218. }
  219.  
  220. void
  221. nir_calc_dominance(nir_shader *shader)
  222. {
  223.    nir_foreach_overload(shader, overload) {
  224.       if (overload->impl)
  225.          nir_calc_dominance_impl(overload->impl);
  226.    }
  227. }
  228.  
  229. /**
  230.  * Computes the least common anscestor of two blocks.  If one of the blocks
  231.  * is null, the other block is returned.
  232.  */
  233. nir_block *
  234. nir_dominance_lca(nir_block *b1, nir_block *b2)
  235. {
  236.    if (b1 == NULL)
  237.       return b2;
  238.  
  239.    if (b2 == NULL)
  240.       return b1;
  241.  
  242.    assert(nir_cf_node_get_function(&b1->cf_node) ==
  243.           nir_cf_node_get_function(&b2->cf_node));
  244.  
  245.    assert(nir_cf_node_get_function(&b1->cf_node)->valid_metadata &
  246.           nir_metadata_dominance);
  247.  
  248.    return intersect(b1, b2);
  249. }
  250.  
  251. /**
  252.  * Returns true if parent dominates child
  253.  */
  254. bool
  255. nir_block_dominates(nir_block *parent, nir_block *child)
  256. {
  257.    assert(nir_cf_node_get_function(&parent->cf_node) ==
  258.           nir_cf_node_get_function(&child->cf_node));
  259.  
  260.    assert(nir_cf_node_get_function(&parent->cf_node)->valid_metadata &
  261.           nir_metadata_dominance);
  262.  
  263.    return child->dom_pre_index >= parent->dom_pre_index &&
  264.           child->dom_post_index <= parent->dom_post_index;
  265. }
  266.  
  267. static bool
  268. dump_block_dom(nir_block *block, void *state)
  269. {
  270.    FILE *fp = state;
  271.    if (block->imm_dom)
  272.       fprintf(fp, "\t%u -> %u\n", block->imm_dom->index, block->index);
  273.    return true;
  274. }
  275.  
  276. void
  277. nir_dump_dom_tree_impl(nir_function_impl *impl, FILE *fp)
  278. {
  279.    fprintf(fp, "digraph doms_%s {\n", impl->overload->function->name);
  280.    nir_foreach_block(impl, dump_block_dom, fp);
  281.    fprintf(fp, "}\n\n");
  282. }
  283.  
  284. void
  285. nir_dump_dom_tree(nir_shader *shader, FILE *fp)
  286. {
  287.    nir_foreach_overload(shader, overload) {
  288.       if (overload->impl)
  289.          nir_dump_dom_tree_impl(overload->impl, fp);
  290.    }
  291. }
  292.  
  293. static bool
  294. dump_block_dom_frontier(nir_block *block, void *state)
  295. {
  296.    FILE *fp = state;
  297.  
  298.    fprintf(fp, "DF(%u) = {", block->index);
  299.    struct set_entry *entry;
  300.    set_foreach(block->dom_frontier, entry) {
  301.       nir_block *df = (nir_block *) entry->key;
  302.       fprintf(fp, "%u, ", df->index);
  303.    }
  304.    fprintf(fp, "}\n");
  305.    return true;
  306. }
  307.  
  308. void
  309. nir_dump_dom_frontier_impl(nir_function_impl *impl, FILE *fp)
  310. {
  311.    nir_foreach_block(impl, dump_block_dom_frontier, fp);
  312. }
  313.  
  314. void
  315. nir_dump_dom_frontier(nir_shader *shader, FILE *fp)
  316. {
  317.    nir_foreach_overload(shader, overload) {
  318.       if (overload->impl)
  319.          nir_dump_dom_frontier_impl(overload->impl, fp);
  320.    }
  321. }
  322.  
  323. static bool
  324. dump_block_succs(nir_block *block, void *state)
  325. {
  326.    FILE *fp = state;
  327.    if (block->successors[0])
  328.       fprintf(fp, "\t%u -> %u\n", block->index, block->successors[0]->index);
  329.    if (block->successors[1])
  330.       fprintf(fp, "\t%u -> %u\n", block->index, block->successors[1]->index);
  331.    return true;
  332. }
  333.  
  334. void
  335. nir_dump_cfg_impl(nir_function_impl *impl, FILE *fp)
  336. {
  337.    fprintf(fp, "digraph cfg_%s {\n", impl->overload->function->name);
  338.    nir_foreach_block(impl, dump_block_succs, fp);
  339.    fprintf(fp, "}\n\n");
  340. }
  341.  
  342. void
  343. nir_dump_cfg(nir_shader *shader, FILE *fp)
  344. {
  345.    nir_foreach_overload(shader, overload) {
  346.       if (overload->impl)
  347.          nir_dump_cfg_impl(overload->impl, fp);
  348.    }
  349. }
  350.