2 * Copyright © 2014 Intel Corporation
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:
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
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
24 * Connor Abbott (cwabbott0@gmail.com)
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.
37 init_block(nir_block
*block
, nir_function_impl
*impl
)
39 if (block
== nir_start_block(impl
))
40 block
->imm_dom
= block
;
42 block
->imm_dom
= NULL
;
43 block
->num_dom_children
= 0;
45 /* See nir_block_dominates */
46 block
->dom_pre_index
= INT16_MAX
;
47 block
->dom_post_index
= -1;
49 set_foreach(block
->dom_frontier
, entry
) {
50 _mesa_set_remove(block
->dom_frontier
, entry
);
57 intersect(nir_block
*b1
, nir_block
*b2
)
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.
65 while (b1
->index
> b2
->index
)
67 while (b2
->index
> b1
->index
)
75 calc_dominance(nir_block
*block
)
77 nir_block
*new_idom
= NULL
;
78 set_foreach(block
->predecessors
, entry
) {
79 nir_block
*pred
= (nir_block
*) entry
->key
;
83 new_idom
= intersect(pred
, new_idom
);
89 if (block
->imm_dom
!= new_idom
) {
90 block
->imm_dom
= new_idom
;
98 calc_dom_frontier(nir_block
*block
)
100 if (block
->predecessors
->entries
> 1) {
101 set_foreach(block
->predecessors
, entry
) {
102 nir_block
*runner
= (nir_block
*) entry
->key
;
104 /* Skip unreachable predecessors */
105 if (runner
->imm_dom
== NULL
)
108 while (runner
!= block
->imm_dom
) {
109 _mesa_set_add(runner
->dom_frontier
, block
);
110 runner
= runner
->imm_dom
;
119 * Compute each node's children in the dominance tree from the immediate
120 * dominator information. We do this in three stages:
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.
130 calc_dom_children(nir_function_impl
* impl
)
132 void *mem_ctx
= ralloc_parent(impl
);
134 nir_foreach_block(block
, impl
) {
136 block
->imm_dom
->num_dom_children
++;
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;
145 nir_foreach_block(block
, impl
) {
146 if (block
->imm_dom
) {
147 block
->imm_dom
->dom_children
[block
->imm_dom
->num_dom_children
++]
154 calc_dfs_indicies(nir_block
*block
, unsigned *index
)
156 block
->dom_pre_index
= (*index
)++;
158 for (unsigned i
= 0; i
< block
->num_dom_children
; i
++)
159 calc_dfs_indicies(block
->dom_children
[i
], index
);
161 block
->dom_post_index
= (*index
)++;
165 nir_calc_dominance_impl(nir_function_impl
*impl
)
167 if (impl
->valid_metadata
& nir_metadata_dominance
)
170 nir_metadata_require(impl
, nir_metadata_block_index
);
173 nir_foreach_block(block
, impl
) {
174 init_block(block
, impl
);
177 bool progress
= true;
180 nir_foreach_block(block
, impl
) {
181 if (block
!= nir_start_block(impl
))
182 progress
|= calc_dominance(block
);
186 nir_foreach_block(block
, impl
) {
187 calc_dom_frontier(block
);
190 nir_block
*start_block
= nir_start_block(impl
);
191 start_block
->imm_dom
= NULL
;
193 calc_dom_children(impl
);
195 unsigned dfs_index
= 0;
196 calc_dfs_indicies(start_block
, &dfs_index
);
200 nir_calc_dominance(nir_shader
*shader
)
202 nir_foreach_function(function
, shader
) {
204 nir_calc_dominance_impl(function
->impl
);
209 block_return_if_reachable(nir_block
*b
)
211 return (b
&& nir_block_is_reachable(b
)) ? b
: NULL
;
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
220 nir_dominance_lca(nir_block
*b1
, nir_block
*b2
)
222 if (b1
== NULL
|| !nir_block_is_reachable(b1
))
223 return block_return_if_reachable(b2
);
225 if (b2
== NULL
|| !nir_block_is_reachable(b2
))
226 return block_return_if_reachable(b1
);
228 assert(nir_cf_node_get_function(&b1
->cf_node
) ==
229 nir_cf_node_get_function(&b2
->cf_node
));
231 assert(nir_cf_node_get_function(&b1
->cf_node
)->valid_metadata
&
232 nir_metadata_dominance
);
234 return intersect(b1
, b2
);
238 * Returns true if parent dominates child according to the following
241 * "The block A dominates the block B if every path from the start block
242 * to block B passes through A."
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.
249 nir_block_dominates(nir_block
*parent
, nir_block
*child
)
251 assert(nir_cf_node_get_function(&parent
->cf_node
) ==
252 nir_cf_node_get_function(&child
->cf_node
));
254 assert(nir_cf_node_get_function(&parent
->cf_node
)->valid_metadata
&
255 nir_metadata_dominance
);
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.
261 return child
->dom_pre_index
>= parent
->dom_pre_index
&&
262 child
->dom_post_index
<= parent
->dom_post_index
;
266 nir_block_is_unreachable(nir_block
*block
)
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
);
273 /* Unreachable blocks have no dominator. The only reachable block with no
274 * dominator is the start block which has index 0.
276 return block
->index
> 0 && block
->imm_dom
== NULL
;
280 nir_dump_dom_tree_impl(nir_function_impl
*impl
, FILE *fp
)
282 fprintf(fp
, "digraph doms_%s {\n", impl
->function
->name
);
284 nir_foreach_block(block
, impl
) {
286 fprintf(fp
, "\t%u -> %u\n", block
->imm_dom
->index
, block
->index
);
289 fprintf(fp
, "}\n\n");
293 nir_dump_dom_tree(nir_shader
*shader
, FILE *fp
)
295 nir_foreach_function(function
, shader
) {
297 nir_dump_dom_tree_impl(function
->impl
, fp
);
302 nir_dump_dom_frontier_impl(nir_function_impl
*impl
, FILE *fp
)
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
);
315 nir_dump_dom_frontier(nir_shader
*shader
, FILE *fp
)
317 nir_foreach_function(function
, shader
) {
319 nir_dump_dom_frontier_impl(function
->impl
, fp
);
324 nir_dump_cfg_impl(nir_function_impl
*impl
, FILE *fp
)
326 fprintf(fp
, "digraph cfg_%s {\n", impl
->function
->name
);
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
);
335 fprintf(fp
, "}\n\n");
339 nir_dump_cfg(nir_shader
*shader
, FILE *fp
)
341 nir_foreach_function(function
, shader
) {
343 nir_dump_cfg_impl(function
->impl
, fp
);