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