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    unsigned bit_size;
  56
  57    /* The list of phi nodes associated with this value.  Phi nodes are not
  58     * added directly.  Instead, they are created, the instr->block pointer
  59     * set, and then added to this list.  Later, in phi_builder_finish, we
  60     * set up their sources and add them to the top of their respective
  61     * blocks.
  62     */
  63    struct exec_list phis;
  64
  65    /* Array of SSA defs, indexed by block.  For each block, this array has has
  66     * one of three types of values:
  67     *
  68     *  - NULL. Indicates that there is no known definition in this block.  If
  69     *    you need to find one, look at the block's immediate dominator.
  70     *
  71     *  - NEEDS_PHI. Indicates that the block may need a phi node but none has
  72     *    been created yet.  If a def is requested for a block, a phi will need
  73     *    to be created.
  74     *
  75     *  - A regular SSA def.  This will be either the result of a phi node or
  76     *    one of the defs provided by nir_phi_builder_value_set_blocK_def().
  77     */
  78    struct hash_table ht;
  79 };
  80
  81 /**
  82  * Convert a block index into a value that can be used as a key for a hash table
  83  *
  84  * The hash table functions want a pointer that is not \c NULL.
  85  * _mesa_hash_pointer drops the two least significant bits, but that's where
  86  * most of our data likely is.  Shift by 2 and add 1 to make everything happy.
  87  */
  88 #define INDEX_TO_KEY(x) ((void *)(uintptr_t) ((x << 2) + 1))
  89
  90 struct nir_phi_builder *
  91 nir_phi_builder_create(nir_function_impl *impl)
  92 {
  93    struct nir_phi_builder *pb = rzalloc(NULL, struct nir_phi_builder);
  94
  95    pb->shader = impl->function->shader;
  96    pb->impl = impl;
  97
  98    assert(impl->valid_metadata & (nir_metadata_block_index |
  99                                   nir_metadata_dominance));
 100
 101    pb->num_blocks = impl->num_blocks;
 102    pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks);
 103    nir_foreach_block(block, impl) {
 104       pb->blocks[block->index] = block;
 105    }
 106
 107    exec_list_make_empty(&pb->values);
 108
 109    pb->iter_count = 0;
 110    pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
 111    pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
 112
 113    return pb;
 114 }
 115
 116 struct nir_phi_builder_value *
 117 nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
 118                           unsigned bit_size, const BITSET_WORD *defs)
 119 {
 120    struct nir_phi_builder_value *val;
 121    unsigned i, w_start = 0, w_end = 0;
 122
 123    val = rzalloc_size(pb, sizeof(*val));
 124    val->builder = pb;
 125    val->num_components = num_components;
 126    val->bit_size = bit_size;
 127    exec_list_make_empty(&val->phis);
 128    exec_list_push_tail(&pb->values, &val->node);
 129
 130    _mesa_hash_table_init(&val->ht, pb, _mesa_hash_pointer,
 131                          _mesa_key_pointer_equal);
 132
 133    pb->iter_count++;
 134
 135    BITSET_WORD tmp;
 136    BITSET_FOREACH_SET(i, tmp, defs, pb->num_blocks) {
 137       if (pb->work[i] < pb->iter_count)
 138          pb->W[w_end++] = pb->blocks[i];
 139       pb->work[i] = pb->iter_count;
 140    }
 141
 142    while (w_start != w_end) {
 143       nir_block *cur = pb->W[w_start++];
 144       set_foreach(cur->dom_frontier, dom_entry) {
 145          nir_block *next = (nir_block *) dom_entry->key;
 146
 147          /* If there's more than one return statement, then the end block
 148           * can be a join point for some definitions. However, there are
 149           * no instructions in the end block, so nothing would use those
 150           * phi nodes. Of course, we couldn't place those phi nodes
 151           * anyways due to the restriction of having no instructions in the
 152           * end block...
 153           */
 154          if (next == pb->impl->end_block)
 155             continue;
 156
 157          if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(next->index)) == NULL) {
 158             /* Instead of creating a phi node immediately, we simply set the
 159              * value to the magic value NEEDS_PHI.  Later, we create phi nodes
 160              * on demand in nir_phi_builder_value_get_block_def().
 161              */
 162             nir_phi_builder_value_set_block_def(val, next, NEEDS_PHI);
 163
 164             if (pb->work[next->index] < pb->iter_count) {
 165                pb->work[next->index] = pb->iter_count;
 166                pb->W[w_end++] = next;
 167             }
 168          }
 169       }
 170    }
 171
 172    return val;
 173 }
 174
 175 void
 176 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
 177                                     nir_block *block, nir_ssa_def *def)
 178 {
 179    _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def);
 180 }
 181
 182 nir_ssa_def *
 183 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
 184                                     nir_block *block)
 185 {
 186    /* Crawl up the dominance tree and find the closest dominator for which we
 187     * have a valid ssa_def, if any.
 188     */
 189    nir_block *dom = block;
 190    struct hash_entry *he = NULL;
 191
 192    while (dom != NULL) {
 193       he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index));
 194       if (he != NULL)
 195          break;
 196
 197       dom = dom->imm_dom;
 198    }
 199
 200    /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
 201    assert((he != NULL) != (dom == NULL));
 202
 203    nir_ssa_def *def;
 204    if (dom == NULL) {
 205       /* No dominator means either that we crawled to the top without ever
 206        * finding a definition or that this block is unreachable.  In either
 207        * case, the value is undefined so we need an SSA undef.
 208        */
 209       nir_ssa_undef_instr *undef =
 210          nir_ssa_undef_instr_create(val->builder->shader,
 211                                     val->num_components,
 212                                     val->bit_size);
 213       nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
 214                        &undef->instr);
 215       def = &undef->def;
 216    } else if (he->data == NEEDS_PHI) {
 217       /* The magic value NEEDS_PHI indicates that the block needs a phi node
 218        * but none has been created.  We need to create one now so we can
 219        * return it to the caller.
 220        *
 221        * Because a phi node may use SSA defs that it does not dominate (this
 222        * happens in loops), we do not yet have enough information to fully
 223        * fill out the phi node.  Instead, the phi nodes we create here will be
 224        * empty (have no sources) and won't actually be placed in the block's
 225        * instruction list yet.  Later, in nir_phi_builder_finish(), we walk
 226        * over all of the phi instructions, fill out the sources lists, and
 227        * place them at the top of their respective block's instruction list.
 228        *
 229        * Creating phi nodes on-demand allows us to avoid creating dead phi
 230        * nodes that will just get deleted later. While this probably isn't a
 231        * big win for a full into-SSA pass, other users may use the phi builder
 232        * to make small SSA form repairs where most of the phi nodes will never
 233        * be used.
 234        */
 235       nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
 236       nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components,
 237                         val->bit_size, NULL);
 238       phi->instr.block = dom;
 239       exec_list_push_tail(&val->phis, &phi->instr.node);
 240       def = &phi->dest.ssa;
 241       he->data = def;
 242    } else {
 243       /* In this case, we have an actual SSA def.  It's either the result of a
 244        * phi node created by the case above or one passed to us through
 245        * nir_phi_builder_value_set_block_def().
 246        */
 247       def = (struct nir_ssa_def *) he->data;
 248    }
 249
 250    /* Walk the chain and stash the def in all of the applicable blocks.  We do
 251     * this for two reasons:
 252     *
 253     *  1) To speed up lookup next time even if the next time is called from a
 254     *     block that is not dominated by this one.
 255     *  2) To avoid unneeded recreation of phi nodes and undefs.
 256     */
 257    for (dom = block; dom != NULL; dom = dom->imm_dom) {
 258       if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL)
 259          break;
 260
 261       nir_phi_builder_value_set_block_def(val, dom, def);
 262    }
 263
 264    return def;
 265 }
 266
 267 static int
 268 compare_blocks(const void *_a, const void *_b)
 269 {
 270    const nir_block * const * a = _a;
 271    const nir_block * const * b = _b;
 272
 273    return (*a)->index - (*b)->index;
 274 }
 275
 276 void
 277 nir_phi_builder_finish(struct nir_phi_builder *pb)
 278 {
 279    const unsigned num_blocks = pb->num_blocks;
 280    nir_block **preds = rzalloc_array(pb, nir_block *, num_blocks);
 281
 282    foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
 283       /* We treat the linked list of phi nodes like a worklist.  The list is
 284        * pre-populated by calls to nir_phi_builder_value_get_block_def() that
 285        * create phi nodes.  As we fill in the sources of phi nodes, more may
 286        * be created and are added to the end of the list.
 287        *
 288        * Because we are adding and removing phi nodes from the list as we go,
 289        * we can't iterate over it normally.  Instead, we just iterate until
 290        * the list is empty.
 291        */
 292       while (!exec_list_is_empty(&val->phis)) {
 293          struct exec_node *head = exec_list_get_head(&val->phis);
 294          nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
 295          assert(phi->instr.type == nir_instr_type_phi);
 296
 297          exec_node_remove(&phi->instr.node);
 298
 299          /* Construct an array of predecessors.  We sort it to ensure
 300           * determinism in the phi insertion algorithm.
 301           *
 302           * XXX: Calling qsort this many times seems expensive.
 303           */
 304          int num_preds = 0;
 305          set_foreach(phi->instr.block->predecessors, entry)
 306             preds[num_preds++] = (nir_block *)entry->key;
 307          qsort(preds, num_preds, sizeof(*preds), compare_blocks);
 308
 309          for (unsigned i = 0; i < num_preds; i++) {
 310             nir_phi_src *src = ralloc(phi, nir_phi_src);
 311             src->pred = preds[i];
 312             src->src = nir_src_for_ssa(
 313                nir_phi_builder_value_get_block_def(val, preds[i]));
 314             exec_list_push_tail(&phi->srcs, &src->node);
 315          }
 316
 317          nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
 318       }
 319    }
 320
 321    ralloc_free(pb);
 322 }