76847847d64400ebb391391af5089eee37449c09
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 nir_function_impl
*impl
;
42 init_block_cb(nir_block
*block
, void *_state
)
44 dom_state
*state
= (dom_state
*) _state
;
45 if (block
== state
->impl
->start_block
)
46 block
->imm_dom
= block
;
48 block
->imm_dom
= NULL
;
49 block
->num_dom_children
= 0;
51 struct set_entry
*entry
;
52 set_foreach(block
->dom_frontier
, entry
) {
53 _mesa_set_remove(block
->dom_frontier
, entry
);
60 intersect(nir_block
*b1
, nir_block
*b2
)
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.
68 while (b1
->index
> b2
->index
)
70 while (b2
->index
> b1
->index
)
78 calc_dominance_cb(nir_block
*block
, void *_state
)
80 dom_state
*state
= (dom_state
*) _state
;
81 if (block
== state
->impl
->start_block
)
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
;
91 new_idom
= intersect(pred
, new_idom
);
98 if (block
->imm_dom
!= new_idom
) {
99 block
->imm_dom
= new_idom
;
100 state
->progress
= true;
107 calc_dom_frontier_cb(nir_block
*block
, void *state
)
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
, _mesa_hash_pointer(block
),
118 runner
= runner
->imm_dom
;
127 * Compute each node's children in the dominance tree from the immediate
128 * dominator information. We do this in three stages:
130 * 1. Calculate the number of children each node has
131 * 2. Allocate arrays, setting the number of children to 0 again
132 * 3. For each node, add itself to its parent's list of children, using
133 * num_dom_children as an index - at the end of this step, num_dom_children
134 * for each node will be the same as it was at the end of step #1.
138 block_count_children(nir_block
*block
, void *state
)
143 block
->imm_dom
->num_dom_children
++;
149 block_alloc_children(nir_block
*block
, void *state
)
151 void *mem_ctx
= state
;
153 block
->dom_children
= ralloc_array(mem_ctx
, nir_block
*,
154 block
->num_dom_children
);
155 block
->num_dom_children
= 0;
161 block_add_child(nir_block
*block
, void *state
)
166 block
->imm_dom
->dom_children
[block
->imm_dom
->num_dom_children
++] = block
;
172 calc_dom_children(nir_function_impl
* impl
)
174 void *mem_ctx
= ralloc_parent(impl
);
176 nir_foreach_block(impl
, block_count_children
, NULL
);
177 nir_foreach_block(impl
, block_alloc_children
, mem_ctx
);
178 nir_foreach_block(impl
, block_add_child
, NULL
);
182 nir_calc_dominance_impl(nir_function_impl
*impl
)
184 if (impl
->valid_metadata
& nir_metadata_dominance
)
187 nir_metadata_require(impl
, nir_metadata_block_index
);
191 state
.progress
= true;
193 nir_foreach_block(impl
, init_block_cb
, &state
);
195 while (state
.progress
) {
196 state
.progress
= false;
197 nir_foreach_block(impl
, calc_dominance_cb
, &state
);
200 nir_foreach_block(impl
, calc_dom_frontier_cb
, &state
);
202 impl
->start_block
->imm_dom
= NULL
;
204 calc_dom_children(impl
);
208 nir_calc_dominance(nir_shader
*shader
)
210 nir_foreach_overload(shader
, overload
) {
212 nir_calc_dominance_impl(overload
->impl
);
217 dump_block_dom(nir_block
*block
, void *state
)
219 FILE *fp
= (FILE *) state
;
221 fprintf(fp
, "\t%u -> %u\n", block
->imm_dom
->index
, block
->index
);
226 nir_dump_dom_tree_impl(nir_function_impl
*impl
, FILE *fp
)
228 fprintf(fp
, "digraph doms_%s {\n", impl
->overload
->function
->name
);
229 nir_foreach_block(impl
, dump_block_dom
, fp
);
230 fprintf(fp
, "}\n\n");
234 nir_dump_dom_tree(nir_shader
*shader
, FILE *fp
)
236 nir_foreach_overload(shader
, overload
) {
238 nir_dump_dom_tree_impl(overload
->impl
, fp
);
243 dump_block_dom_frontier(nir_block
*block
, void *state
)
245 FILE *fp
= (FILE *) state
;
247 fprintf(fp
, "DF(%u) = {", block
->index
);
248 struct set_entry
*entry
;
249 set_foreach(block
->dom_frontier
, entry
) {
250 nir_block
*df
= (nir_block
*) entry
->key
;
251 fprintf(fp
, "%u, ", df
->index
);
258 nir_dump_dom_frontier_impl(nir_function_impl
*impl
, FILE *fp
)
260 nir_foreach_block(impl
, dump_block_dom_frontier
, fp
);
264 nir_dump_dom_frontier(nir_shader
*shader
, FILE *fp
)
266 nir_foreach_overload(shader
, overload
) {
268 nir_dump_dom_frontier_impl(overload
->impl
, fp
);
273 dump_block_succs(nir_block
*block
, void *state
)
275 FILE *fp
= (FILE *) state
;
276 if (block
->successors
[0])
277 fprintf(fp
, "\t%u -> %u\n", block
->index
, block
->successors
[0]->index
);
278 if (block
->successors
[1])
279 fprintf(fp
, "\t%u -> %u\n", block
->index
, block
->successors
[1]->index
);
284 nir_dump_cfg_impl(nir_function_impl
*impl
, FILE *fp
)
286 fprintf(fp
, "digraph cfg_%s {\n", impl
->overload
->function
->name
);
287 nir_foreach_block(impl
, dump_block_succs
, fp
);
288 fprintf(fp
, "}\n\n");
292 nir_dump_cfg(nir_shader
*shader
, FILE *fp
)
294 nir_foreach_overload(shader
, overload
) {
296 nir_dump_cfg_impl(overload
->impl
, fp
);