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 (at) 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 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 * 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 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 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 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 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 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 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 * 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 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 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 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 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 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 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 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
