nir_opt_dead_cf.c revision 21424e019d29424e2c09cf8ac197d294cf2edb5f
1/* 2 * Copyright © 2014 Connor Abbott 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#include "nir_control_flow.h" 30 31/* 32 * This file implements an optimization that deletes statically 33 * unreachable/dead code. In NIR, one way this can happen if if an if 34 * statement has a constant condition: 35 * 36 * if (true) { 37 * ... 38 * } 39 * 40 * We delete the if statement and paste the contents of the always-executed 41 * branch into the surrounding control flow, possibly removing more code if 42 * the branch had a jump at the end. 43 * 44 * Another way is that control flow can end in a jump so that code after it 45 * never gets executed. In particular, this can happen after optimizing 46 * something like: 47 * 48 * if (true) { 49 * ... 50 * break; 51 * } 52 * ... 53 * 54 * We also consider the case where both branches of an if end in a jump, e.g.: 55 * 56 * if (...) { 57 * break; 58 * } else { 59 * continue; 60 * } 61 * ... 62 * 63 * Finally, we also handle removing useless loops, i.e. loops with no side 64 * effects and without any definitions that are used elsewhere. This case is a 65 * little different from the first two in that the code is actually run (it 66 * just never does anything), but there are similar issues with needing to 67 * be careful with restarting after deleting the cf_node (see dead_cf_list()) 68 * so this is a convenient place to remove them. 69 */ 70 71static void 72remove_after_cf_node(nir_cf_node *node) 73{ 74 nir_cf_node *end = node; 75 while (!nir_cf_node_is_last(end)) 76 end = nir_cf_node_next(end); 77 78 nir_cf_list list; 79 nir_cf_extract(&list, nir_after_cf_node(node), nir_after_cf_node(end)); 80 nir_cf_delete(&list); 81} 82 83static void 84opt_constant_if(nir_if *if_stmt, bool condition) 85{ 86 /* First, we need to remove any phi nodes after the if by rewriting uses to 87 * point to the correct source. 88 */ 89 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&if_stmt->cf_node)); 90 nir_block *last_block = 91 nir_cf_node_as_block(condition ? nir_if_last_then_node(if_stmt) 92 : nir_if_last_else_node(if_stmt)); 93 94 nir_foreach_instr_safe(instr, after) { 95 if (instr->type != nir_instr_type_phi) 96 break; 97 98 nir_phi_instr *phi = nir_instr_as_phi(instr); 99 nir_ssa_def *def = NULL; 100 nir_foreach_phi_src(phi_src, phi) { 101 if (phi_src->pred != last_block) 102 continue; 103 104 assert(phi_src->src.is_ssa); 105 def = phi_src->src.ssa; 106 } 107 108 assert(def); 109 assert(phi->dest.is_ssa); 110 nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def)); 111 nir_instr_remove(instr); 112 } 113 114 /* The control flow list we're about to paste in may include a jump at the 115 * end, and in that case we have to delete the rest of the control flow 116 * list after the if since it's unreachable and the validator will balk if 117 * we don't. 118 */ 119 120 if (!exec_list_is_empty(&last_block->instr_list)) { 121 nir_instr *last_instr = nir_block_last_instr(last_block); 122 if (last_instr->type == nir_instr_type_jump) 123 remove_after_cf_node(&if_stmt->cf_node); 124 } 125 126 /* Finally, actually paste in the then or else branch and delete the if. */ 127 struct exec_list *cf_list = condition ? &if_stmt->then_list 128 : &if_stmt->else_list; 129 130 nir_cf_list list; 131 nir_cf_extract(&list, nir_before_cf_list(cf_list), 132 nir_after_cf_list(cf_list)); 133 nir_cf_reinsert(&list, nir_after_cf_node(&if_stmt->cf_node)); 134 nir_cf_node_remove(&if_stmt->cf_node); 135} 136 137static bool 138cf_node_has_side_effects(nir_cf_node *node) 139{ 140 nir_foreach_block_in_cf_node(block, node) { 141 nir_foreach_instr(instr, block) { 142 if (instr->type == nir_instr_type_call) 143 return true; 144 145 /* Return instructions can cause us to skip over other side-effecting 146 * instructions after the loop, so consider them to have side effects 147 * here. 148 */ 149 150 if (instr->type == nir_instr_type_jump && 151 nir_instr_as_jump(instr)->type == nir_jump_return) 152 return true; 153 154 if (instr->type != nir_instr_type_intrinsic) 155 continue; 156 157 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr); 158 if (!(nir_intrinsic_infos[intrin->intrinsic].flags & 159 NIR_INTRINSIC_CAN_ELIMINATE)) 160 return true; 161 } 162 } 163 164 return false; 165} 166 167static bool 168def_not_live_out(nir_ssa_def *def, void *state) 169{ 170 nir_block *after = state; 171 172 return !BITSET_TEST(after->live_in, def->live_index); 173} 174 175/* 176 * Test if a loop is dead. A loop is dead if: 177 * 178 * 1) It has no side effects (i.e. intrinsics which could possibly affect the 179 * state of the program aside from producing an SSA value, indicated by a lack 180 * of NIR_INTRINSIC_CAN_ELIMINATE). 181 * 182 * 2) It has no phi nodes after it, since those indicate values inside the 183 * loop being used after the loop. 184 * 185 * 3) If there are no phi nodes after the loop, then the only way a value 186 * defined inside the loop can be used outside the loop is if its definition 187 * dominates the block after the loop. If none of the definitions that 188 * dominate the loop exit are used outside the loop, then the loop is dead 189 * and it can be deleted. 190 */ 191 192static bool 193loop_is_dead(nir_loop *loop) 194{ 195 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 196 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 197 198 if (!exec_list_is_empty(&after->instr_list) && 199 nir_block_first_instr(after)->type == nir_instr_type_phi) 200 return false; 201 202 if (cf_node_has_side_effects(&loop->cf_node)) 203 return false; 204 205 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); 206 nir_metadata_require(impl, nir_metadata_live_ssa_defs | 207 nir_metadata_dominance); 208 209 for (nir_block *cur = after->imm_dom; cur != before; cur = cur->imm_dom) { 210 nir_foreach_instr(instr, cur) { 211 if (!nir_foreach_ssa_def(instr, def_not_live_out, after)) 212 return false; 213 } 214 } 215 216 return true; 217} 218 219static bool 220dead_cf_block(nir_block *block) 221{ 222 nir_if *following_if = nir_block_get_following_if(block); 223 if (following_if) { 224 nir_const_value *const_value = 225 nir_src_as_const_value(following_if->condition); 226 227 if (!const_value) 228 return false; 229 230 opt_constant_if(following_if, const_value->u32[0] != 0); 231 return true; 232 } 233 234 nir_loop *following_loop = nir_block_get_following_loop(block); 235 if (!following_loop) 236 return false; 237 238 if (!loop_is_dead(following_loop)) 239 return false; 240 241 nir_cf_node_remove(&following_loop->cf_node); 242 return true; 243} 244 245static bool 246ends_in_jump(nir_block *block) 247{ 248 if (exec_list_is_empty(&block->instr_list)) 249 return false; 250 251 nir_instr *instr = nir_block_last_instr(block); 252 return instr->type == nir_instr_type_jump; 253} 254 255static bool 256dead_cf_list(struct exec_list *list, bool *list_ends_in_jump) 257{ 258 bool progress = false; 259 *list_ends_in_jump = false; 260 261 nir_cf_node *prev = NULL; 262 263 foreach_list_typed(nir_cf_node, cur, node, list) { 264 switch (cur->type) { 265 case nir_cf_node_block: { 266 nir_block *block = nir_cf_node_as_block(cur); 267 if (dead_cf_block(block)) { 268 /* We just deleted the if or loop after this block, so we may have 269 * deleted the block before or after it -- which one is an 270 * implementation detail. Therefore, to recover the place we were 271 * at, we have to use the previous cf_node. 272 */ 273 274 if (prev) { 275 cur = nir_cf_node_next(prev); 276 } else { 277 cur = exec_node_data(nir_cf_node, exec_list_get_head(list), 278 node); 279 } 280 281 block = nir_cf_node_as_block(cur); 282 283 progress = true; 284 } 285 286 if (ends_in_jump(block)) { 287 *list_ends_in_jump = true; 288 289 if (!exec_node_is_tail_sentinel(cur->node.next)) { 290 remove_after_cf_node(cur); 291 return true; 292 } 293 } 294 295 break; 296 } 297 298 case nir_cf_node_if: { 299 nir_if *if_stmt = nir_cf_node_as_if(cur); 300 bool then_ends_in_jump, else_ends_in_jump; 301 progress |= dead_cf_list(&if_stmt->then_list, &then_ends_in_jump); 302 progress |= dead_cf_list(&if_stmt->else_list, &else_ends_in_jump); 303 304 if (then_ends_in_jump && else_ends_in_jump) { 305 *list_ends_in_jump = true; 306 nir_block *next = nir_cf_node_as_block(nir_cf_node_next(cur)); 307 if (!exec_list_is_empty(&next->instr_list) || 308 !exec_node_is_tail_sentinel(next->cf_node.node.next)) { 309 remove_after_cf_node(cur); 310 return true; 311 } 312 } 313 314 break; 315 } 316 317 case nir_cf_node_loop: { 318 nir_loop *loop = nir_cf_node_as_loop(cur); 319 bool dummy; 320 progress |= dead_cf_list(&loop->body, &dummy); 321 322 break; 323 } 324 325 default: 326 unreachable("unknown cf node type"); 327 } 328 329 prev = cur; 330 } 331 332 return progress; 333} 334 335static bool 336opt_dead_cf_impl(nir_function_impl *impl) 337{ 338 bool dummy; 339 bool progress = dead_cf_list(&impl->body, &dummy); 340 341 if (progress) 342 nir_metadata_preserve(impl, nir_metadata_none); 343 344 return progress; 345} 346 347bool 348nir_opt_dead_cf(nir_shader *shader) 349{ 350 bool progress = false; 351 352 nir_foreach_function(function, shader) 353 if (function->impl) 354 progress |= opt_dead_cf_impl(function->impl); 355 356 return progress; 357} 358