src/compiler/nir/nir_deref.c

   1 /*
   2  * Copyright © 2018 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
  24 #include "nir.h"
  25 #include "nir_builder.h"
  26 #include "nir_deref.h"
  27
  28 void
  29 nir_deref_path_init(nir_deref_path *path,
  30                     nir_deref_instr *deref, void *mem_ctx)
  31 {
  32    assert(deref != NULL);
  33
  34    /* The length of the short path is at most ARRAY_SIZE - 1 because we need
  35     * room for the NULL terminator.
  36     */
  37    static const int max_short_path_len = ARRAY_SIZE(path->_short_path) - 1;
  38
  39    int count = 0;
  40
  41    nir_deref_instr **tail = &path->_short_path[max_short_path_len];
  42    nir_deref_instr **head = tail;
  43
  44    *tail = NULL;
  45    for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
  46       count++;
  47       if (count <= max_short_path_len)
  48          *(--head) = d;
  49    }
  50
  51    if (count <= max_short_path_len) {
  52       /* If we're under max_short_path_len, just use the short path. */
  53       path->path = head;
  54       goto done;
  55    }
  56
  57 #ifndef NDEBUG
  58    /* Just in case someone uses short_path by accident */
  59    for (unsigned i = 0; i < ARRAY_SIZE(path->_short_path); i++)
  60       path->_short_path[i] = (void *)0xdeadbeef;
  61 #endif
  62
  63    path->path = ralloc_array(mem_ctx, nir_deref_instr *, count + 1);
  64    head = tail = path->path + count;
  65    *tail = NULL;
  66    for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d))
  67       *(--head) = d;
  68
  69 done:
  70    assert(head == path->path);
  71    assert(tail == head + count);
  72    assert((*head)->deref_type == nir_deref_type_var);
  73    assert(*tail == NULL);
  74 }
  75
  76 void
  77 nir_deref_path_finish(nir_deref_path *path)
  78 {
  79    if (path->path < &path->_short_path[0] ||
  80        path->path > &path->_short_path[ARRAY_SIZE(path->_short_path) - 1])
  81       ralloc_free(path->path);
  82 }
  83
  84 /**
  85  * Recursively removes unused deref instructions
  86  */
  87 bool
  88 nir_deref_instr_remove_if_unused(nir_deref_instr *instr)
  89 {
  90    bool progress = false;
  91
  92    for (nir_deref_instr *d = instr; d; d = nir_deref_instr_parent(d)) {
  93       /* If anyone is using this deref, leave it alone */
  94       assert(d->dest.is_ssa);
  95       if (!list_empty(&d->dest.ssa.uses))
  96          break;
  97
  98       nir_instr_remove(&d->instr);
  99       progress = true;
 100    }
 101
 102    return progress;
 103 }
 104
 105 bool
 106 nir_deref_instr_has_indirect(nir_deref_instr *instr)
 107 {
 108    while (instr->deref_type != nir_deref_type_var) {
 109       /* Consider casts to be indirects */
 110       if (instr->deref_type == nir_deref_type_cast)
 111          return true;
 112
 113       if (instr->deref_type == nir_deref_type_array &&
 114           !nir_src_as_const_value(instr->arr.index))
 115          return true;
 116
 117       instr = nir_deref_instr_parent(instr);
 118    }
 119
 120    return false;
 121 }
 122
 123 static unsigned
 124 type_get_array_stride(const struct glsl_type *elem_type,
 125                       glsl_type_size_align_func size_align)
 126 {
 127    unsigned elem_size, elem_align;
 128    glsl_get_natural_size_align_bytes(elem_type, &elem_size, &elem_align);
 129    return ALIGN_POT(elem_size, elem_align);
 130 }
 131
 132 static unsigned
 133 struct_type_get_field_offset(const struct glsl_type *struct_type,
 134                              glsl_type_size_align_func size_align,
 135                              unsigned field_idx)
 136 {
 137    assert(glsl_type_is_struct(struct_type));
 138    unsigned offset = 0;
 139    for (unsigned i = 0; i <= field_idx; i++) {
 140       unsigned elem_size, elem_align;
 141       glsl_get_natural_size_align_bytes(glsl_get_struct_field(struct_type, i),
 142                                         &elem_size, &elem_align);
 143       offset = ALIGN_POT(offset, elem_align);
 144       if (i < field_idx)
 145          offset += elem_size;
 146    }
 147    return offset;
 148 }
 149
 150 unsigned
 151 nir_deref_instr_get_const_offset(nir_deref_instr *deref,
 152                                  glsl_type_size_align_func size_align)
 153 {
 154    nir_deref_path path;
 155    nir_deref_path_init(&path, deref, NULL);
 156
 157    assert(path.path[0]->deref_type == nir_deref_type_var);
 158
 159    unsigned offset = 0;
 160    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 161       if ((*p)->deref_type == nir_deref_type_array) {
 162          offset += nir_src_as_const_value((*p)->arr.index)->u32[0] *
 163                    type_get_array_stride((*p)->type, size_align);
 164       } else if ((*p)->deref_type == nir_deref_type_struct) {
 165          /* p starts at path[1], so this is safe */
 166          nir_deref_instr *parent = *(p - 1);
 167          offset += struct_type_get_field_offset(parent->type, size_align,
 168                                                 (*p)->strct.index);
 169       } else {
 170          unreachable("Unsupported deref type");
 171       }
 172    }
 173
 174    nir_deref_path_finish(&path);
 175
 176    return offset;
 177 }
 178
 179 nir_ssa_def *
 180 nir_build_deref_offset(nir_builder *b, nir_deref_instr *deref,
 181                        glsl_type_size_align_func size_align)
 182 {
 183    nir_deref_path path;
 184    nir_deref_path_init(&path, deref, NULL);
 185
 186    assert(path.path[0]->deref_type == nir_deref_type_var);
 187
 188    nir_ssa_def *offset = nir_imm_int(b, 0);
 189    for (nir_deref_instr **p = &path.path[1]; *p; p++) {
 190       if ((*p)->deref_type == nir_deref_type_array) {
 191          nir_ssa_def *index = nir_ssa_for_src(b, (*p)->arr.index, 1);
 192          nir_ssa_def *stride =
 193             nir_imm_int(b, type_get_array_stride((*p)->type, size_align));
 194          offset = nir_iadd(b, offset, nir_imul(b, index, stride));
 195       } else if ((*p)->deref_type == nir_deref_type_struct) {
 196          /* p starts at path[1], so this is safe */
 197          nir_deref_instr *parent = *(p - 1);
 198          unsigned field_offset =
 199             struct_type_get_field_offset(parent->type, size_align,
 200                                          (*p)->strct.index);
 201          nir_iadd(b, offset, nir_imm_int(b, field_offset));
 202       } else {
 203          unreachable("Unsupported deref type");
 204       }
 205    }
 206
 207    nir_deref_path_finish(&path);
 208
 209    return offset;
 210 }
 211
 212 bool
 213 nir_remove_dead_derefs_impl(nir_function_impl *impl)
 214 {
 215    bool progress = false;
 216
 217    nir_foreach_block(block, impl) {
 218       nir_foreach_instr_safe(instr, block) {
 219          if (instr->type == nir_instr_type_deref &&
 220              nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
 221             progress = true;
 222       }
 223    }
 224
 225    if (progress)
 226       nir_metadata_preserve(impl, nir_metadata_block_index |
 227                                   nir_metadata_dominance);
 228
 229    return progress;
 230 }
 231
 232 bool
 233 nir_remove_dead_derefs(nir_shader *shader)
 234 {
 235    bool progress = false;
 236    nir_foreach_function(function, shader) {
 237       if (function->impl && nir_remove_dead_derefs_impl(function->impl))
 238          progress = true;
 239    }
 240
 241    return progress;
 242 }
 243
 244 void
 245 nir_fixup_deref_modes(nir_shader *shader)
 246 {
 247    nir_foreach_function(function, shader) {
 248       if (!function->impl)
 249          continue;
 250
 251       nir_foreach_block(block, function->impl) {
 252          nir_foreach_instr(instr, block) {
 253             if (instr->type != nir_instr_type_deref)
 254                continue;
 255
 256             nir_deref_instr *deref = nir_instr_as_deref(instr);
 257
 258             nir_variable_mode parent_mode;
 259             if (deref->deref_type == nir_deref_type_var) {
 260                parent_mode = deref->var->data.mode;
 261             } else {
 262                assert(deref->parent.is_ssa);
 263                nir_deref_instr *parent =
 264                   nir_instr_as_deref(deref->parent.ssa->parent_instr);
 265                parent_mode = parent->mode;
 266             }
 267
 268             deref->mode = parent_mode;
 269          }
 270       }
 271    }
 272 }
 273
 274 /** Returns true if the storage referrenced to by deref completely contains
 275  * the storage referenced by sub.
 276  */
 277 nir_deref_compare_result
 278 nir_compare_deref_paths(nir_deref_path *a_path,
 279                         nir_deref_path *b_path)
 280 {
 281    if (a_path->path[0]->var != b_path->path[0]->var)
 282       return 0;
 283
 284    /* Start off assuming they fully compare.  We ignore equality for now.  In
 285     * the end, we'll determine that by containment.
 286     */
 287    nir_deref_compare_result result = nir_derefs_may_alias_bit |
 288                                      nir_derefs_a_contains_b_bit |
 289                                      nir_derefs_b_contains_a_bit;
 290
 291    nir_deref_instr **a_p = &a_path->path[1];
 292    nir_deref_instr **b_p = &b_path->path[1];
 293    while (*a_p != NULL && *b_p != NULL) {
 294       nir_deref_instr *a_tail = *(a_p++);
 295       nir_deref_instr *b_tail = *(b_p++);
 296
 297       switch (a_tail->deref_type) {
 298       case nir_deref_type_array:
 299       case nir_deref_type_array_wildcard: {
 300          assert(b_tail->deref_type == nir_deref_type_array ||
 301                 b_tail->deref_type == nir_deref_type_array_wildcard);
 302
 303          if (a_tail->deref_type == nir_deref_type_array_wildcard) {
 304             if (b_tail->deref_type != nir_deref_type_array_wildcard)
 305                result &= ~nir_derefs_b_contains_a_bit;
 306          } else if (b_tail->deref_type == nir_deref_type_array_wildcard) {
 307             if (a_tail->deref_type != nir_deref_type_array_wildcard)
 308                result &= ~nir_derefs_a_contains_b_bit;
 309          } else {
 310             assert(a_tail->deref_type == nir_deref_type_array &&
 311                    b_tail->deref_type == nir_deref_type_array);
 312             assert(a_tail->arr.index.is_ssa && b_tail->arr.index.is_ssa);
 313
 314             nir_const_value *a_index_const =
 315                nir_src_as_const_value(a_tail->arr.index);
 316             nir_const_value *b_index_const =
 317                nir_src_as_const_value(b_tail->arr.index);
 318             if (a_index_const && b_index_const) {
 319                /* If they're both direct and have different offsets, they
 320                 * don't even alias much less anything else.
 321                 */
 322                if (a_index_const->u32[0] != b_index_const->u32[0])
 323                   return 0;
 324             } else if (a_tail->arr.index.ssa == b_tail->arr.index.ssa) {
 325                /* They're the same indirect, continue on */
 326             } else {
 327                /* They're not the same index so we can't prove anything about
 328                 * containment.
 329                 */
 330                result &= ~(nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit);
 331             }
 332          }
 333          break;
 334       }
 335
 336       case nir_deref_type_struct: {
 337          /* If they're different struct members, they don't even alias */
 338          if (a_tail->strct.index != b_tail->strct.index)
 339             return 0;
 340          break;
 341       }
 342
 343       default:
 344          unreachable("Invalid deref type");
 345       }
 346    }
 347
 348    /* If a is longer than b, then it can't contain b */
 349    if (*a_p != NULL)
 350       result &= ~nir_derefs_a_contains_b_bit;
 351    if (*b_p != NULL)
 352       result &= ~nir_derefs_b_contains_a_bit;
 353
 354    /* If a contains b and b contains a they must be equal. */
 355    if ((result & nir_derefs_a_contains_b_bit) && (result & nir_derefs_b_contains_a_bit))
 356       result |= nir_derefs_equal_bit;
 357
 358    return result;
 359 }
 360
 361 nir_deref_compare_result
 362 nir_compare_derefs(nir_deref_instr *a, nir_deref_instr *b)
 363 {
 364    if (a == b) {
 365       return nir_derefs_equal_bit | nir_derefs_may_alias_bit |
 366              nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit;
 367    }
 368
 369    nir_deref_path a_path, b_path;
 370    nir_deref_path_init(&a_path, a, NULL);
 371    nir_deref_path_init(&b_path, b, NULL);
 372    assert(a_path.path[0]->deref_type == nir_deref_type_var);
 373    assert(b_path.path[0]->deref_type == nir_deref_type_var);
 374
 375    nir_deref_compare_result result = nir_compare_deref_paths(&a_path, &b_path);
 376
 377    nir_deref_path_finish(&a_path);
 378    nir_deref_path_finish(&b_path);
 379
 380    return result;
 381 }