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