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