src/compiler/nir/nir_repair_ssa.c

   1 /*
   2  * Copyright © 2016 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_phi_builder.h"
  26
  27 struct repair_ssa_state {
  28    nir_function_impl *impl;
  29
  30    BITSET_WORD *def_set;
  31    struct nir_phi_builder *phi_builder;
  32
  33    bool progress;
  34 };
  35
  36 /* Get ready to build a phi and return the builder */
  37 static struct nir_phi_builder *
  38 prep_build_phi(struct repair_ssa_state *state)
  39 {
  40    const unsigned num_words = BITSET_WORDS(state->impl->num_blocks);
  41
  42    /* We create the phi builder on-demand. */
  43    if (state->phi_builder == NULL) {
  44       state->phi_builder = nir_phi_builder_create(state->impl);
  45       state->def_set = ralloc_array(NULL, BITSET_WORD, num_words);
  46    }
  47
  48    /* We're going to build a phi.  That's progress. */
  49    state->progress = true;
  50
  51    /* Set the defs set to empty */
  52    memset(state->def_set, 0, num_words * sizeof(*state->def_set));
  53
  54    return state->phi_builder;
  55 }
  56
  57 static nir_block *
  58 get_src_block(nir_src *src)
  59 {
  60    if (src->parent_instr->type == nir_instr_type_phi) {
  61       return exec_node_data(nir_phi_src, src, src)->pred;
  62    } else {
  63       return src->parent_instr->block;
  64    }
  65 }
  66
  67 static bool
  68 repair_ssa_def(nir_ssa_def *def, void *void_state)
  69 {
  70    struct repair_ssa_state *state = void_state;
  71
  72    bool is_valid = true;
  73    nir_foreach_use(src, def) {
  74       if (nir_block_is_unreachable(get_src_block(src)) ||
  75           !nir_block_dominates(def->parent_instr->block, get_src_block(src))) {
  76          is_valid = false;
  77          break;
  78       }
  79    }
  80
  81    nir_foreach_if_use(src, def) {
  82       nir_block *block_before_if =
  83          nir_cf_node_as_block(nir_cf_node_prev(&src->parent_if->cf_node));
  84       if (nir_block_is_unreachable(block_before_if) ||
  85           !nir_block_dominates(def->parent_instr->block, block_before_if)) {
  86          is_valid = false;
  87          break;
  88       }
  89    }
  90
  91    if (is_valid)
  92       return true;
  93
  94    struct nir_phi_builder *pb = prep_build_phi(state);
  95
  96    BITSET_SET(state->def_set, def->parent_instr->block->index);
  97
  98    struct nir_phi_builder_value *val =
  99       nir_phi_builder_add_value(pb, def->num_components, def->bit_size,
 100                                 state->def_set);
 101
 102    nir_phi_builder_value_set_block_def(val, def->parent_instr->block, def);
 103
 104    nir_foreach_use_safe(src, def) {
 105       nir_block *src_block = get_src_block(src);
 106       if (src_block == def->parent_instr->block) {
 107          assert(nir_phi_builder_value_get_block_def(val, src_block) == def);
 108          continue;
 109       }
 110
 111       nir_ssa_def *block_def =
 112          nir_phi_builder_value_get_block_def(val, src_block);
 113       if (block_def == def)
 114          continue;
 115
 116       /* If def was a deref and the use we're looking at is a deref that
 117        * isn't a cast, we need to wrap it in a cast so we don't loose any
 118        * deref information.
 119        */
 120       if (def->parent_instr->type == nir_instr_type_deref &&
 121           src->parent_instr->type == nir_instr_type_deref &&
 122           nir_instr_as_deref(src->parent_instr)->deref_type != nir_deref_type_cast) {
 123          nir_deref_instr *cast =
 124             nir_deref_instr_create(state->impl->function->shader,
 125                                    nir_deref_type_cast);
 126
 127          nir_deref_instr *deref = nir_instr_as_deref(def->parent_instr);
 128          cast->mode = deref->mode;
 129          cast->type = deref->type;
 130          cast->parent = nir_src_for_ssa(block_def);
 131          cast->cast.ptr_stride = nir_deref_instr_ptr_as_array_stride(deref);
 132
 133          nir_ssa_dest_init(&cast->instr, &cast->dest,
 134                            def->num_components, def->bit_size, NULL);
 135          nir_instr_insert(nir_before_instr(src->parent_instr),
 136                           &cast->instr);
 137          block_def = &cast->dest.ssa;
 138       }
 139
 140       nir_instr_rewrite_src(src->parent_instr, src, nir_src_for_ssa(block_def));
 141    }
 142
 143    nir_foreach_if_use_safe(src, def) {
 144       nir_block *block_before_if =
 145          nir_cf_node_as_block(nir_cf_node_prev(&src->parent_if->cf_node));
 146       if (block_before_if == def->parent_instr->block) {
 147          assert(nir_phi_builder_value_get_block_def(val, block_before_if) == def);
 148          continue;
 149       }
 150
 151       nir_ssa_def *block_def =
 152          nir_phi_builder_value_get_block_def(val, block_before_if);
 153       if (block_def == def)
 154          continue;
 155
 156       nir_if_rewrite_condition(src->parent_if, nir_src_for_ssa(block_def));
 157    }
 158
 159    return true;
 160 }
 161
 162 bool
 163 nir_repair_ssa_impl(nir_function_impl *impl)
 164 {
 165    struct repair_ssa_state state;
 166
 167    state.impl = impl;
 168    state.phi_builder = NULL;
 169    state.progress = false;
 170
 171    nir_metadata_require(impl, nir_metadata_block_index |
 172                               nir_metadata_dominance);
 173
 174    nir_foreach_block(block, impl) {
 175       nir_foreach_instr_safe(instr, block) {
 176          nir_foreach_ssa_def(instr, repair_ssa_def, &state);
 177       }
 178    }
 179
 180    if (state.progress)
 181       nir_metadata_preserve(impl, nir_metadata_block_index |
 182                                   nir_metadata_dominance);
 183
 184    if (state.phi_builder) {
 185       nir_phi_builder_finish(state.phi_builder);
 186       ralloc_free(state.def_set);
 187    }
 188
 189    return state.progress;
 190 }
 191
 192 /** This pass can be used to repair SSA form in a shader.
 193  *
 194  * Sometimes a transformation (such as return lowering) will have to make
 195  * changes to a shader which, while still correct, break some of NIR's SSA
 196  * invariants.  This pass will insert ssa_undefs and phi nodes as needed to
 197  * get the shader back into SSA that the validator will like.
 198  */
 199 bool
 200 nir_repair_ssa(nir_shader *shader)
 201 {
 202    bool progress = false;
 203
 204    nir_foreach_function(function, shader) {
 205       if (function->impl)
 206          progress = nir_repair_ssa_impl(function->impl) || progress;
 207    }
 208
 209    return progress;
 210 }