src/glsl/nir/nir_opt_cse.c

   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@jlekstrand.net)
  25  *
  26  */
  27
  28 #include "nir.h"
  29
  30 /*
  31  * Implements common subexpression elimination
  32  */
  33
  34 struct cse_state {
  35    void *mem_ctx;
  36    bool progress;
  37 };
  38
  39 static bool
  40 nir_alu_srcs_equal(nir_alu_src src1, nir_alu_src src2, uint8_t read_mask)
  41 {
  42    if (src1.abs != src2.abs || src1.negate != src2.negate)
  43       return false;
  44
  45    for (int i = 0; i < 4; ++i) {
  46       if (!(read_mask & (1 << i)))
  47          continue;
  48
  49       if (src1.swizzle[i] != src2.swizzle[i])
  50          return false;
  51    }
  52
  53    return nir_srcs_equal(src1.src, src2.src);
  54 }
  55
  56 static bool
  57 nir_instrs_equal(nir_instr *instr1, nir_instr *instr2)
  58 {
  59    if (instr1->type != instr2->type)
  60       return false;
  61
  62    switch (instr1->type) {
  63    case nir_instr_type_alu: {
  64       nir_alu_instr *alu1 = nir_instr_as_alu(instr1);
  65       nir_alu_instr *alu2 = nir_instr_as_alu(instr2);
  66
  67       if (alu1->op != alu2->op)
  68          return false;
  69
  70       /* TODO: We can probably acutally do something more inteligent such
  71        * as allowing different numbers and taking a maximum or something
  72        * here */
  73       if (alu1->dest.dest.ssa.num_components != alu2->dest.dest.ssa.num_components)
  74          return false;
  75
  76       for (unsigned i = 0; i < nir_op_infos[alu1->op].num_inputs; i++) {
  77          if (!nir_alu_srcs_equal(alu1->src[i], alu2->src[i],
  78                                  (1 << alu1->dest.dest.ssa.num_components) - 1))
  79             return false;
  80       }
  81       return true;
  82    }
  83    case nir_instr_type_tex:
  84       return false;
  85    case nir_instr_type_load_const: {
  86       nir_load_const_instr *load1 = nir_instr_as_load_const(instr1);
  87       nir_load_const_instr *load2 = nir_instr_as_load_const(instr2);
  88
  89       if (load1->num_components != load2->num_components)
  90          return false;
  91
  92       return memcmp(load1->value.f, load2->value.f,
  93                     load1->num_components * sizeof load2->value.f) == 0;
  94    }
  95    case nir_instr_type_phi: {
  96       nir_phi_instr *phi1 = nir_instr_as_phi(instr1);
  97       nir_phi_instr *phi2 = nir_instr_as_phi(instr2);
  98
  99       if (phi1->instr.block != phi2->instr.block)
 100          return false;
 101
 102       foreach_list_typed(nir_phi_src, src1, node, &phi1->srcs) {
 103          foreach_list_typed(nir_phi_src, src2, node, &phi2->srcs) {
 104             if (src1->pred == src2->pred) {
 105                if (!nir_srcs_equal(src1->src, src2->src))
 106                   return false;
 107
 108                break;
 109             }
 110          }
 111       }
 112
 113       return true;
 114    }
 115    case nir_instr_type_intrinsic:
 116    case nir_instr_type_call:
 117    case nir_instr_type_jump:
 118    case nir_instr_type_ssa_undef:
 119    case nir_instr_type_parallel_copy:
 120    default:
 121       unreachable("Invalid instruction type");
 122    }
 123
 124    return false;
 125 }
 126
 127 static bool
 128 src_is_ssa(nir_src *src, void *data)
 129 {
 130    return src->is_ssa;
 131 }
 132
 133 static bool
 134 dest_is_ssa(nir_dest *dest, void *data)
 135 {
 136    return dest->is_ssa;
 137 }
 138
 139 static bool
 140 nir_instr_can_cse(nir_instr *instr)
 141 {
 142    switch (instr->type) {
 143    case nir_instr_type_alu:
 144    case nir_instr_type_load_const:
 145    case nir_instr_type_phi:
 146       return nir_foreach_dest(instr, dest_is_ssa, NULL) &&
 147              nir_foreach_src(instr, src_is_ssa, NULL);
 148    case nir_instr_type_tex:
 149       return false; /* TODO */
 150    case nir_instr_type_intrinsic:
 151    case nir_instr_type_call:
 152    case nir_instr_type_jump:
 153    case nir_instr_type_ssa_undef:
 154       return false;
 155    case nir_instr_type_parallel_copy:
 156    default:
 157       unreachable("Invalid instruction type");
 158    }
 159
 160    return false;
 161 }
 162
 163 static nir_ssa_def *
 164 nir_instr_get_dest_ssa_def(nir_instr *instr)
 165 {
 166    switch (instr->type) {
 167    case nir_instr_type_alu:
 168       assert(nir_instr_as_alu(instr)->dest.dest.is_ssa);
 169       return &nir_instr_as_alu(instr)->dest.dest.ssa;
 170    case nir_instr_type_load_const:
 171       assert(nir_instr_as_load_const(instr)->dest.is_ssa);
 172       return &nir_instr_as_load_const(instr)->dest.ssa;
 173    case nir_instr_type_phi:
 174       assert(nir_instr_as_phi(instr)->dest.is_ssa);
 175       return &nir_instr_as_phi(instr)->dest.ssa;
 176    default:
 177       unreachable("We never ask for any of these");
 178    }
 179 }
 180
 181 static void
 182 nir_opt_cse_instr(nir_instr *instr, struct cse_state *state)
 183 {
 184    if (!nir_instr_can_cse(instr))
 185       return;
 186
 187    for (struct exec_node *node = instr->node.prev;
 188         !exec_node_is_head_sentinel(node); node = node->prev) {
 189       nir_instr *other = exec_node_data(nir_instr, node, node);
 190       if (nir_instrs_equal(instr, other)) {
 191          nir_src other_dest_src = {
 192             .is_ssa = true,
 193             .ssa = nir_instr_get_dest_ssa_def(other),
 194          };
 195          nir_ssa_def_rewrite_uses(nir_instr_get_dest_ssa_def(instr),
 196                                   other_dest_src, state->mem_ctx);
 197          nir_instr_remove(instr);
 198          state->progress = true;
 199          return;
 200       }
 201    }
 202
 203    for (nir_block *block = instr->block->imm_dom;
 204         block != NULL; block = block->imm_dom) {
 205       nir_foreach_instr_reverse(block, other) {
 206          if (nir_instrs_equal(instr, other)) {
 207             nir_src other_dest_src = {
 208                .is_ssa = true,
 209                .ssa = nir_instr_get_dest_ssa_def(other),
 210             };
 211             nir_ssa_def_rewrite_uses(nir_instr_get_dest_ssa_def(instr),
 212                                      other_dest_src, state->mem_ctx);
 213             nir_instr_remove(instr);
 214             state->progress = true;
 215             return;
 216          }
 217       }
 218    }
 219 }
 220
 221 static bool
 222 nir_opt_cse_block(nir_block *block, void *void_state)
 223 {
 224    struct cse_state *state = void_state;
 225
 226    nir_foreach_instr_safe(block, instr)
 227       nir_opt_cse_instr(instr, state);
 228
 229    return true;
 230 }
 231
 232 static bool
 233 nir_opt_cse_impl(nir_function_impl *impl)
 234 {
 235    struct cse_state state;
 236
 237    state.mem_ctx = ralloc_parent(impl);
 238    state.progress = false;
 239
 240    nir_metadata_require(impl, nir_metadata_dominance);
 241
 242    nir_foreach_block(impl, nir_opt_cse_block, &state);
 243
 244    if (state.progress)
 245       nir_metadata_preserve(impl, nir_metadata_block_index |
 246                                   nir_metadata_dominance);
 247
 248    return state.progress;
 249 }
 250
 251 bool
 252 nir_opt_cse(nir_shader *shader)
 253 {
 254    bool progress = false;
 255
 256    nir_foreach_overload(shader, overload) {
 257       if (overload->impl)
 258          progress |= nir_opt_cse_impl(overload->impl);
 259    }
 260
 261    return progress;
 262 }