nir_opt_dead_cf.c revision 8c4d9afb7e770f312079994994f42ddebf7e641c
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 is when 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_list_extract(&list, cf_list); 132 nir_cf_reinsert(&list, nir_after_cf_node(&if_stmt->cf_node)); 133 nir_cf_node_remove(&if_stmt->cf_node); 134} 135 136static bool 137cf_node_has_side_effects(nir_cf_node *node) 138{ 139 nir_foreach_block_in_cf_node(block, node) { 140 nir_foreach_instr(instr, block) { 141 if (instr->type == nir_instr_type_call) 142 return true; 143 144 /* Return instructions can cause us to skip over other side-effecting 145 * instructions after the loop, so consider them to have side effects 146 * here. 147 */ 148 149 if (instr->type == nir_instr_type_jump && 150 nir_instr_as_jump(instr)->type == nir_jump_return) 151 return true; 152 153 if (instr->type != nir_instr_type_intrinsic) 154 continue; 155 156 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr); 157 if (!(nir_intrinsic_infos[intrin->intrinsic].flags & 158 NIR_INTRINSIC_CAN_ELIMINATE)) 159 return true; 160 } 161 } 162 163 return false; 164} 165 166static bool 167def_not_live_out(nir_ssa_def *def, void *state) 168{ 169 nir_block *after = state; 170 171 return !BITSET_TEST(after->live_in, def->live_index); 172} 173 174/* 175 * Test if a loop is dead. A loop is dead if: 176 * 177 * 1) It has no side effects (i.e. intrinsics which could possibly affect the 178 * state of the program aside from producing an SSA value, indicated by a lack 179 * of NIR_INTRINSIC_CAN_ELIMINATE). 180 * 181 * 2) It has no phi nodes after it, since those indicate values inside the 182 * loop being used after the loop. 183 * 184 * 3) If there are no phi nodes after the loop, then the only way a value 185 * defined inside the loop can be used outside the loop is if its definition 186 * dominates the block after the loop. If none of the definitions that 187 * dominate the loop exit are used outside the loop, then the loop is dead 188 * and it can be deleted. 189 */ 190 191static bool 192loop_is_dead(nir_loop *loop) 193{ 194 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 195 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 196 197 if (!exec_list_is_empty(&after->instr_list) && 198 nir_block_first_instr(after)->type == nir_instr_type_phi) 199 return false; 200 201 if (cf_node_has_side_effects(&loop->cf_node)) 202 return false; 203 204 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); 205 nir_metadata_require(impl, nir_metadata_live_ssa_defs | 206 nir_metadata_dominance); 207 208 for (nir_block *cur = after->imm_dom; cur != before; cur = cur->imm_dom) { 209 nir_foreach_instr(instr, cur) { 210 if (!nir_foreach_ssa_def(instr, def_not_live_out, after)) 211 return false; 212 } 213 } 214 215 return true; 216} 217 218static bool 219dead_cf_block(nir_block *block) 220{ 221 nir_if *following_if = nir_block_get_following_if(block); 222 if (following_if) { 223 nir_const_value *const_value = 224 nir_src_as_const_value(following_if->condition); 225 226 if (!const_value) 227 return false; 228 229 opt_constant_if(following_if, const_value->u32[0] != 0); 230 return true; 231 } 232 233 nir_loop *following_loop = nir_block_get_following_loop(block); 234 if (!following_loop) 235 return false; 236 237 if (!loop_is_dead(following_loop)) 238 return false; 239 240 nir_cf_node_remove(&following_loop->cf_node); 241 return true; 242} 243 244static bool 245ends_in_jump(nir_block *block) 246{ 247 if (exec_list_is_empty(&block->instr_list)) 248 return false; 249 250 nir_instr *instr = nir_block_last_instr(block); 251 return instr->type == nir_instr_type_jump; 252} 253 254static bool 255dead_cf_list(struct exec_list *list, bool *list_ends_in_jump) 256{ 257 bool progress = false; 258 *list_ends_in_jump = false; 259 260 nir_cf_node *prev = NULL; 261 262 foreach_list_typed(nir_cf_node, cur, node, list) { 263 switch (cur->type) { 264 case nir_cf_node_block: { 265 nir_block *block = nir_cf_node_as_block(cur); 266 if (dead_cf_block(block)) { 267 /* We just deleted the if or loop after this block, so we may have 268 * deleted the block before or after it -- which one is an 269 * implementation detail. Therefore, to recover the place we were 270 * at, we have to use the previous cf_node. 271 */ 272 273 if (prev) { 274 cur = nir_cf_node_next(prev); 275 } else { 276 cur = exec_node_data(nir_cf_node, exec_list_get_head(list), 277 node); 278 } 279 280 block = nir_cf_node_as_block(cur); 281 282 progress = true; 283 } 284 285 if (ends_in_jump(block)) { 286 *list_ends_in_jump = true; 287 288 if (!exec_node_is_tail_sentinel(cur->node.next)) { 289 remove_after_cf_node(cur); 290 return true; 291 } 292 } 293 294 break; 295 } 296 297 case nir_cf_node_if: { 298 nir_if *if_stmt = nir_cf_node_as_if(cur); 299 bool then_ends_in_jump, else_ends_in_jump; 300 progress |= dead_cf_list(&if_stmt->then_list, &then_ends_in_jump); 301 progress |= dead_cf_list(&if_stmt->else_list, &else_ends_in_jump); 302 303 if (then_ends_in_jump && else_ends_in_jump) { 304 *list_ends_in_jump = true; 305 nir_block *next = nir_cf_node_as_block(nir_cf_node_next(cur)); 306 if (!exec_list_is_empty(&next->instr_list) || 307 !exec_node_is_tail_sentinel(next->cf_node.node.next)) { 308 remove_after_cf_node(cur); 309 return true; 310 } 311 } 312 313 break; 314 } 315 316 case nir_cf_node_loop: { 317 nir_loop *loop = nir_cf_node_as_loop(cur); 318 bool dummy; 319 progress |= dead_cf_list(&loop->body, &dummy); 320 321 break; 322 } 323 324 default: 325 unreachable("unknown cf node type"); 326 } 327 328 prev = cur; 329 } 330 331 return progress; 332} 333 334static bool 335opt_dead_cf_impl(nir_function_impl *impl) 336{ 337 bool dummy; 338 bool progress = dead_cf_list(&impl->body, &dummy); 339 340 if (progress) 341 nir_metadata_preserve(impl, nir_metadata_none); 342 343 return progress; 344} 345 346bool 347nir_opt_dead_cf(nir_shader *shader) 348{ 349 bool progress = false; 350 351 nir_foreach_function(function, shader) 352 if (function->impl) 353 progress |= opt_dead_cf_impl(function->impl); 354 355 return progress; 356} 357