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 (at) 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 71 static void 72 remove_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 83 static void 84 opt_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 = condition ? nir_if_last_then_block(if_stmt) 91 : nir_if_last_else_block(if_stmt); 92 93 nir_foreach_instr_safe(instr, after) { 94 if (instr->type != nir_instr_type_phi) 95 break; 96 97 nir_phi_instr *phi = nir_instr_as_phi(instr); 98 nir_ssa_def *def = NULL; 99 nir_foreach_phi_src(phi_src, phi) { 100 if (phi_src->pred != last_block) 101 continue; 102 103 assert(phi_src->src.is_ssa); 104 def = phi_src->src.ssa; 105 } 106 107 assert(def); 108 assert(phi->dest.is_ssa); 109 nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def)); 110 nir_instr_remove(instr); 111 } 112 113 /* The control flow list we're about to paste in may include a jump at the 114 * end, and in that case we have to delete the rest of the control flow 115 * list after the if since it's unreachable and the validator will balk if 116 * we don't. 117 */ 118 119 if (!exec_list_is_empty(&last_block->instr_list)) { 120 nir_instr *last_instr = nir_block_last_instr(last_block); 121 if (last_instr->type == nir_instr_type_jump) 122 remove_after_cf_node(&if_stmt->cf_node); 123 } 124 125 /* Finally, actually paste in the then or else branch and delete the if. */ 126 struct exec_list *cf_list = condition ? &if_stmt->then_list 127 : &if_stmt->else_list; 128 129 nir_cf_list list; 130 nir_cf_list_extract(&list, cf_list); 131 nir_cf_reinsert(&list, nir_after_cf_node(&if_stmt->cf_node)); 132 nir_cf_node_remove(&if_stmt->cf_node); 133 } 134 135 static bool 136 cf_node_has_side_effects(nir_cf_node *node) 137 { 138 nir_foreach_block_in_cf_node(block, node) { 139 nir_foreach_instr(instr, block) { 140 if (instr->type == nir_instr_type_call) 141 return true; 142 143 /* Return instructions can cause us to skip over other side-effecting 144 * instructions after the loop, so consider them to have side effects 145 * here. 146 */ 147 148 if (instr->type == nir_instr_type_jump && 149 nir_instr_as_jump(instr)->type == nir_jump_return) 150 return true; 151 152 if (instr->type != nir_instr_type_intrinsic) 153 continue; 154 155 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr); 156 if (!(nir_intrinsic_infos[intrin->intrinsic].flags & 157 NIR_INTRINSIC_CAN_ELIMINATE)) 158 return true; 159 } 160 } 161 162 return false; 163 } 164 165 static bool 166 def_not_live_out(nir_ssa_def *def, void *state) 167 { 168 nir_block *after = state; 169 170 return !BITSET_TEST(after->live_in, def->live_index); 171 } 172 173 /* 174 * Test if a loop is dead. A loop is dead if: 175 * 176 * 1) It has no side effects (i.e. intrinsics which could possibly affect the 177 * state of the program aside from producing an SSA value, indicated by a lack 178 * of NIR_INTRINSIC_CAN_ELIMINATE). 179 * 180 * 2) It has no phi nodes after it, since those indicate values inside the 181 * loop being used after the loop. 182 * 183 * 3) If there are no phi nodes after the loop, then the only way a value 184 * defined inside the loop can be used outside the loop is if its definition 185 * dominates the block after the loop. If none of the definitions that 186 * dominate the loop exit are used outside the loop, then the loop is dead 187 * and it can be deleted. 188 */ 189 190 static bool 191 loop_is_dead(nir_loop *loop) 192 { 193 nir_block *before = nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 194 nir_block *after = nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 195 196 if (!exec_list_is_empty(&after->instr_list) && 197 nir_block_first_instr(after)->type == nir_instr_type_phi) 198 return false; 199 200 if (cf_node_has_side_effects(&loop->cf_node)) 201 return false; 202 203 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); 204 nir_metadata_require(impl, nir_metadata_live_ssa_defs | 205 nir_metadata_dominance); 206 207 for (nir_block *cur = after->imm_dom; cur && cur != before; 208 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 218 static bool 219 dead_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 244 static bool 245 ends_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 254 static bool 255 dead_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 334 static bool 335 opt_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 346 bool 347 nir_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