src/compiler/nir/nir_phi_builder.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_phi_builder.h"
  25 #include "nir/nir_vla.h"
  26
  27 struct nir_phi_builder {
  28    nir_shader *shader;
  29    nir_function_impl *impl;
  30
  31    /* Copied from the impl for easy access */
  32    unsigned num_blocks;
  33
  34    /* Array of all blocks indexed by block->index. */
  35    nir_block **blocks;
  36
  37    /* Hold on to the values so we can easily iterate over them. */
  38    struct exec_list values;
  39
  40    /* Worklist for phi adding */
  41    unsigned iter_count;
  42    unsigned *work;
  43    nir_block **W;
  44 };
  45
  46 #define NEEDS_PHI ((nir_ssa_def *)(intptr_t)-1)
  47
  48 struct nir_phi_builder_value {
  49    struct exec_node node;
  50
  51    struct nir_phi_builder *builder;
  52
  53    /* Needed so we can create phis and undefs */
  54    unsigned num_components;
  55
  56    /* The list of phi nodes associated with this value.  Phi nodes are not
  57     * added directly.  Instead, they are created, the instr->block pointer
  58     * set, and then added to this list.  Later, in phi_builder_finish, we
  59     * set up their sources and add them to the top of their respective
  60     * blocks.
  61     */
  62    struct exec_list phis;
  63
  64    /* Array of SSA defs, indexed by block.  If a phi needs to be inserted
  65     * in a given block, it will have the magic value NEEDS_PHI.
  66     */
  67    nir_ssa_def *defs[0];
  68 };
  69
  70 static bool
  71 fill_block_array(nir_block *block, void *void_data)
  72 {
  73    nir_block **blocks = void_data;
  74    blocks[block->index] = block;
  75    return true;
  76 }
  77
  78 struct nir_phi_builder *
  79 nir_phi_builder_create(nir_function_impl *impl)
  80 {
  81    struct nir_phi_builder *pb = ralloc(NULL, struct nir_phi_builder);
  82
  83    pb->shader = impl->function->shader;
  84    pb->impl = impl;
  85
  86    assert(impl->valid_metadata & (nir_metadata_block_index |
  87                                   nir_metadata_dominance));
  88
  89    pb->num_blocks = impl->num_blocks;
  90    pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks);
  91    nir_foreach_block(impl, fill_block_array, pb->blocks);
  92
  93    exec_list_make_empty(&pb->values);
  94
  95    pb->iter_count = 0;
  96    pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
  97    pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
  98
  99    return pb;
 100 }
 101
 102 struct nir_phi_builder_value *
 103 nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
 104                           const BITSET_WORD *defs)
 105 {
 106    struct nir_phi_builder_value *val;
 107    unsigned i, w_start = 0, w_end = 0;
 108
 109    val = rzalloc_size(pb, sizeof(*val) + sizeof(val->defs[0]) * pb->num_blocks);
 110    val->builder = pb;
 111    val->num_components = num_components;
 112    exec_list_make_empty(&val->phis);
 113    exec_list_push_tail(&pb->values, &val->node);
 114
 115    pb->iter_count++;
 116
 117    BITSET_WORD tmp;
 118    BITSET_FOREACH_SET(i, tmp, defs, pb->num_blocks) {
 119       if (pb->work[i] < pb->iter_count)
 120          pb->W[w_end++] = pb->blocks[i];
 121       pb->work[i] = pb->iter_count;
 122    }
 123
 124    while (w_start != w_end) {
 125       nir_block *cur = pb->W[w_start++];
 126       struct set_entry *dom_entry;
 127       set_foreach(cur->dom_frontier, dom_entry) {
 128          nir_block *next = (nir_block *) dom_entry->key;
 129
 130          /*
 131           * If there's more than one return statement, then the end block
 132           * can be a join point for some definitions. However, there are
 133           * no instructions in the end block, so nothing would use those
 134           * phi nodes. Of course, we couldn't place those phi nodes
 135           * anyways due to the restriction of having no instructions in the
 136           * end block...
 137           */
 138          if (next == pb->impl->end_block)
 139             continue;
 140
 141          if (val->defs[next->index] == NULL) {
 142             val->defs[next->index] = NEEDS_PHI;
 143
 144             if (pb->work[next->index] < pb->iter_count) {
 145                pb->work[next->index] = pb->iter_count;
 146                pb->W[w_end++] = next;
 147             }
 148          }
 149       }
 150    }
 151
 152    return val;
 153 }
 154
 155 void
 156 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
 157                                     nir_block *block, nir_ssa_def *def)
 158 {
 159    val->defs[block->index] = def;
 160 }
 161
 162 nir_ssa_def *
 163 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
 164                                     nir_block *block)
 165 {
 166    if (val->defs[block->index] == NULL) {
 167       if (block->imm_dom) {
 168          /* Grab it from our immediate dominator.  We'll stash it here for
 169           * easy access later.
 170           */
 171          val->defs[block->index] =
 172             nir_phi_builder_value_get_block_def(val, block->imm_dom);
 173          return val->defs[block->index];
 174       } else {
 175          /* No immediate dominator means that this block is either the
 176           * start block or unreachable.  In either case, the value is
 177           * undefined so we need an SSA undef.
 178           */
 179          nir_ssa_undef_instr *undef =
 180             nir_ssa_undef_instr_create(val->builder->shader,
 181                                        val->num_components);
 182          nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
 183                           &undef->instr);
 184          val->defs[block->index] = &undef->def;
 185          return &undef->def;
 186       }
 187    } else if (val->defs[block->index] == NEEDS_PHI) {
 188       /* If we need a phi instruction, go ahead and create one but don't
 189        * add it to the program yet.  Later, we'll go through and set up phi
 190        * sources and add the instructions will be added at that time.
 191        */
 192       nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
 193       nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components, NULL);
 194       phi->instr.block = block;
 195       exec_list_push_tail(&val->phis, &phi->instr.node);
 196       val->defs[block->index] = &phi->dest.ssa;
 197       return &phi->dest.ssa;
 198    } else {
 199       return val->defs[block->index];
 200    }
 201 }
 202
 203 static int
 204 compare_blocks(const void *_a, const void *_b)
 205 {
 206    nir_block * const * a = _a;
 207    nir_block * const * b = _b;
 208
 209    return (*a)->index - (*b)->index;
 210 }
 211
 212 void
 213 nir_phi_builder_finish(struct nir_phi_builder *pb)
 214 {
 215    const unsigned num_blocks = pb->num_blocks;
 216    NIR_VLA(nir_block *, preds, num_blocks);
 217
 218    foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
 219       /* We can't iterate over the list of phis normally because we are
 220        * removing them as we go and, in some cases, adding new phis as we
 221        * build the source lists of others.
 222        */
 223       while (!exec_list_is_empty(&val->phis)) {
 224          struct exec_node *head = exec_list_get_head(&val->phis);
 225          nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
 226          assert(phi->instr.type == nir_instr_type_phi);
 227
 228          exec_node_remove(&phi->instr.node);
 229
 230          /* Construct an array of predecessors.  We sort it to ensure
 231           * determinism in the phi insertion algorithm.
 232           *
 233           * XXX: Calling qsort this many times seems expensive.
 234           */
 235          int num_preds = 0;
 236          struct set_entry *entry;
 237          set_foreach(phi->instr.block->predecessors, entry)
 238             preds[num_preds++] = (nir_block *)entry->key;
 239          qsort(preds, num_preds, sizeof(*preds), compare_blocks);
 240
 241          for (unsigned i = 0; i < num_preds; i++) {
 242             nir_phi_src *src = ralloc(phi, nir_phi_src);
 243             src->pred = preds[i];
 244             src->src = nir_src_for_ssa(
 245                nir_phi_builder_value_get_block_def(val, preds[i]));
 246             exec_list_push_tail(&phi->srcs, &src->node);
 247          }
 248
 249          nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
 250       }
 251    }
 252
 253    ralloc_free(pb);
 254 }