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 * Jason Ekstrand (jason (at) jlekstrand.net) 25 * Connor Abbott (cwabbott0 (at) gmail.com) 26 * 27 */ 28 29 #include "nir_instr_set.h" 30 31 /* 32 * Implements common subexpression elimination 33 */ 34 35 /* 36 * Visits and CSEs the given block and all its descendants in the dominance 37 * tree recursively. Note that the instr_set is guaranteed to only ever 38 * contain instructions that dominate the current block. 39 */ 40 41 static bool 42 cse_block(nir_block *block, struct set *instr_set) 43 { 44 bool progress = false; 45 46 nir_foreach_instr_safe(instr, block) { 47 if (nir_instr_set_add_or_rewrite(instr_set, instr)) { 48 progress = true; 49 nir_instr_remove(instr); 50 } 51 } 52 53 for (unsigned i = 0; i < block->num_dom_children; i++) { 54 nir_block *child = block->dom_children[i]; 55 progress |= cse_block(child, instr_set); 56 } 57 58 nir_foreach_instr(instr, block) 59 nir_instr_set_remove(instr_set, instr); 60 61 return progress; 62 } 63 64 static bool 65 nir_opt_cse_impl(nir_function_impl *impl) 66 { 67 struct set *instr_set = nir_instr_set_create(NULL); 68 69 nir_metadata_require(impl, nir_metadata_dominance); 70 71 bool progress = cse_block(nir_start_block(impl), instr_set); 72 73 if (progress) 74 nir_metadata_preserve(impl, nir_metadata_block_index | 75 nir_metadata_dominance); 76 77 nir_instr_set_destroy(instr_set); 78 return progress; 79 } 80 81 bool 82 nir_opt_cse(nir_shader *shader) 83 { 84 bool progress = false; 85 86 nir_foreach_function(function, shader) { 87 if (function->impl) 88 progress |= nir_opt_cse_impl(function->impl); 89 } 90 91 return progress; 92 } 93 94