src/glsl/nir/nir_to_ssa.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  *    Connor Abbott (cwabbott0@gmail.com)
  25  *
  26  */
  27
  28 #include "nir.h"
  29 #include <stdlib.h>
  30 #include <unistd.h>
  31
  32 /*
  33  * Implements the classic to-SSA algorithm described by Cytron et. al. in
  34  * "Efficiently Computing Static Single Assignment Form and the Control
  35  * Dependence Graph."
  36  */
  37
  38 /* inserts a phi node of the form reg = phi(reg, reg, reg, ...) */
  39
  40 static void
  41 insert_trivial_phi(nir_register *reg, nir_block *block, void *mem_ctx)
  42 {
  43    nir_phi_instr *instr = nir_phi_instr_create(mem_ctx);
  44
  45    instr->dest.reg.reg = reg;
  46    struct set_entry *entry;
  47    set_foreach(block->predecessors, entry) {
  48       nir_block *pred = (nir_block *) entry->key;
  49
  50       nir_phi_src *src = ralloc(mem_ctx, nir_phi_src);
  51       src->pred = pred;
  52       src->src.is_ssa = false;
  53       src->src.reg.base_offset = 0;
  54       src->src.reg.indirect = NULL;
  55       src->src.reg.reg = reg;
  56       exec_list_push_tail(&instr->srcs, &src->node);
  57    }
  58
  59    nir_instr_insert_before_block(block, &instr->instr);
  60 }
  61
  62 static void
  63 insert_phi_nodes(nir_function_impl *impl)
  64 {
  65    void *mem_ctx = ralloc_parent(impl);
  66
  67    unsigned *work = calloc(impl->num_blocks, sizeof(unsigned));
  68    unsigned *has_already = calloc(impl->num_blocks, sizeof(unsigned));
  69
  70    /*
  71     * Since the work flags already prevent us from inserting a node that has
  72     * ever been inserted into W, we don't need to use a set to represent W.
  73     * Also, since no block can ever be inserted into W more than once, we know
  74     * that the maximum size of W is the number of basic blocks in the
  75     * function. So all we need to handle W is an array and a pointer to the
  76     * next element to be inserted and the next element to be removed.
  77     */
  78    nir_block **W = malloc(impl->num_blocks * sizeof(nir_block *));
  79    unsigned w_start, w_end;
  80
  81    unsigned iter_count = 0;
  82
  83    nir_index_blocks(impl);
  84
  85    foreach_list_typed(nir_register, reg, node, &impl->registers) {
  86       if (reg->num_array_elems != 0)
  87          continue;
  88
  89       w_start = w_end = 0;
  90       iter_count++;
  91
  92       struct set_entry *entry;
  93       set_foreach(reg->defs, entry) {
  94          nir_instr *def = (nir_instr *) entry->key;
  95          if (work[def->block->index] < iter_count)
  96             W[w_end++] = def->block;
  97          work[def->block->index] = iter_count;
  98       }
  99
 100       while (w_start != w_end) {
 101          nir_block *cur = W[w_start++];
 102          set_foreach(cur->dom_frontier, entry) {
 103             nir_block *next = (nir_block *) entry->key;
 104
 105             /*
 106              * If there's more than one return statement, then the end block
 107              * can be a join point for some definitions. However, there are
 108              * no instructions in the end block, so nothing would use those
 109              * phi nodes. Of course, we couldn't place those phi nodes
 110              * anyways due to the restriction of having no instructions in the
 111              * end block...
 112              */
 113             if (next == impl->end_block)
 114                continue;
 115
 116             if (has_already[next->index] < iter_count) {
 117                insert_trivial_phi(reg, next, mem_ctx);
 118                has_already[next->index] = iter_count;
 119                if (work[next->index] < iter_count) {
 120                   work[next->index] = iter_count;
 121                   W[w_end++] = next;
 122                }
 123             }
 124          }
 125       }
 126    }
 127
 128    free(work);
 129    free(has_already);
 130    free(W);
 131 }
 132
 133 typedef struct {
 134    nir_ssa_def **stack;
 135    int index;
 136    unsigned num_defs; /** < used to add indices to debug names */
 137 #ifdef DEBUG
 138    unsigned stack_size;
 139 #endif
 140 } reg_state;
 141
 142 typedef struct {
 143    reg_state *states;
 144    void *mem_ctx;
 145    nir_instr *parent_instr;
 146    nir_if *parent_if;
 147    nir_function_impl *impl;
 148
 149    /* map from SSA value -> original register */
 150    struct hash_table *ssa_map;
 151 } rewrite_state;
 152
 153 static nir_ssa_def *get_ssa_src(nir_register *reg, rewrite_state *state)
 154 {
 155    unsigned index = reg->index;
 156
 157    if (state->states[index].index == -1) {
 158       /*
 159        * We're using an undefined register, create a new undefined SSA value
 160        * to preserve the information that this source is undefined
 161        */
 162       nir_ssa_undef_instr *instr =
 163          nir_ssa_undef_instr_create(state->mem_ctx, reg->num_components);
 164
 165       /*
 166        * We could just insert the undefined instruction before the instruction
 167        * we're rewriting, but we could be rewriting a phi source in which case
 168        * we can't do that, so do the next easiest thing - insert it at the
 169        * beginning of the program. In the end, it doesn't really matter where
 170        * the undefined instructions are because they're going to be ignored
 171        * in the backend.
 172        */
 173       nir_instr_insert_before_cf_list(&state->impl->body, &instr->instr);
 174       return &instr->def;
 175    }
 176
 177    return state->states[index].stack[state->states[index].index];
 178 }
 179
 180 static bool
 181 rewrite_use(nir_src *src, void *_state)
 182 {
 183    rewrite_state *state = (rewrite_state *) _state;
 184
 185    if (src->is_ssa)
 186       return true;
 187
 188    unsigned index = src->reg.reg->index;
 189
 190    if (state->states[index].stack == NULL)
 191       return true;
 192
 193    src->is_ssa = true;
 194    src->ssa = get_ssa_src(src->reg.reg, state);
 195
 196    if (state->parent_instr)
 197       _mesa_set_add(src->ssa->uses, state->parent_instr);
 198    else
 199       _mesa_set_add(src->ssa->if_uses, state->parent_if);
 200    return true;
 201 }
 202
 203 static bool
 204 rewrite_def_forwards(nir_dest *dest, void *_state)
 205 {
 206    rewrite_state *state = (rewrite_state *) _state;
 207
 208    if (dest->is_ssa)
 209       return true;
 210
 211    nir_register *reg = dest->reg.reg;
 212    unsigned index = reg->index;
 213
 214    if (state->states[index].stack == NULL)
 215       return true;
 216
 217    dest->is_ssa = true;
 218
 219    char *name = NULL;
 220    if (dest->reg.reg->name)
 221       name = ralloc_asprintf(state->mem_ctx, "%s_%u", dest->reg.reg->name,
 222                              state->states[index].num_defs);
 223
 224    nir_ssa_def_init(state->parent_instr, &dest->ssa,
 225                     reg->num_components, name);
 226
 227    /* push our SSA destination on the stack */
 228    state->states[index].index++;
 229    assert(state->states[index].index < state->states[index].stack_size);
 230    state->states[index].stack[state->states[index].index] = &dest->ssa;
 231    state->states[index].num_defs++;
 232
 233    _mesa_hash_table_insert(state->ssa_map, &dest->ssa, reg);
 234
 235    return true;
 236 }
 237
 238 static void
 239 rewrite_alu_instr_forward(nir_alu_instr *instr, rewrite_state *state)
 240 {
 241    state->parent_instr = &instr->instr;
 242
 243    nir_foreach_src(&instr->instr, rewrite_use, state);
 244
 245    nir_register *reg = instr->dest.dest.reg.reg;
 246    unsigned index = reg->index;
 247
 248    if (state->states[index].stack == NULL)
 249       return;
 250
 251    unsigned write_mask = instr->dest.write_mask;
 252    if (write_mask != (1 << instr->dest.dest.reg.reg->num_components) - 1) {
 253       /*
 254        * Calculate the number of components the final instruction, which for
 255        * per-component things is the number of output components of the
 256        * instruction and non-per-component things is the number of enabled
 257        * channels in the write mask.
 258        */
 259       unsigned num_components;
 260       if (nir_op_infos[instr->op].output_size == 0) {
 261          unsigned temp = (write_mask & 0x5) + ((write_mask >> 1) & 0x5);
 262          num_components = (temp & 0x3) + ((temp >> 2) & 0x3);
 263       } else {
 264          num_components = nir_op_infos[instr->op].output_size;
 265       }
 266
 267       char *name = NULL;
 268       if (instr->dest.dest.reg.reg->name)
 269          name = ralloc_asprintf(state->mem_ctx, "%s_%u",
 270                                 reg->name, state->states[index].num_defs);
 271
 272       instr->dest.write_mask = (1 << num_components) - 1;
 273       instr->dest.dest.is_ssa = true;
 274       nir_ssa_def_init(&instr->instr, &instr->dest.dest.ssa,
 275                        num_components, name);
 276
 277       if (nir_op_infos[instr->op].output_size == 0) {
 278          /*
 279           * When we change the output writemask, we need to change the
 280           * swizzles for per-component inputs too
 281           */
 282          for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
 283             if (nir_op_infos[instr->op].input_sizes[i] != 0)
 284                continue;
 285
 286             unsigned new_swizzle[4] = {0, 0, 0, 0};
 287
 288             /*
 289              * We keep two indices:
 290              * 1. The index of the original (non-SSA) component
 291              * 2. The index of the post-SSA, compacted, component
 292              *
 293              * We need to map the swizzle component at index 1 to the swizzle
 294              * component at index 2.
 295              */
 296
 297             unsigned ssa_index = 0;
 298             for (unsigned index = 0; index < 4; index++) {
 299                if (!((write_mask >> index) & 1))
 300                   continue;
 301
 302                new_swizzle[ssa_index] = instr->src[i].swizzle[index];
 303                ssa_index++;
 304             }
 305
 306             for (unsigned j = 0; j < 4; j++)
 307                instr->src[i].swizzle[j] = new_swizzle[j];
 308          }
 309       }
 310
 311       nir_op op;
 312       switch (reg->num_components) {
 313       case 2: op = nir_op_vec2; break;
 314       case 3: op = nir_op_vec3; break;
 315       case 4: op = nir_op_vec4; break;
 316       default: assert(0); break;
 317       }
 318
 319       nir_alu_instr *vec = nir_alu_instr_create(state->mem_ctx, op);
 320
 321       vec->dest.dest.reg.reg = reg;
 322       vec->dest.write_mask = (1 << reg->num_components) - 1;
 323
 324       nir_ssa_def *old_src = get_ssa_src(reg, state);
 325       nir_ssa_def *new_src = &instr->dest.dest.ssa;
 326
 327       unsigned ssa_index = 0;
 328       for (unsigned i = 0; i < reg->num_components; i++) {
 329          vec->src[i].src.is_ssa = true;
 330          if ((write_mask >> i) & 1) {
 331             vec->src[i].src.ssa = new_src;
 332             if (nir_op_infos[instr->op].output_size == 0)
 333                vec->src[i].swizzle[0] = ssa_index;
 334             else
 335                vec->src[i].swizzle[0] = i;
 336             ssa_index++;
 337          } else {
 338             vec->src[i].src.ssa = old_src;
 339             vec->src[i].swizzle[0] = i;
 340          }
 341       }
 342
 343       nir_instr_insert_after(&instr->instr, &vec->instr);
 344
 345       state->parent_instr = &vec->instr;
 346       rewrite_def_forwards(&vec->dest.dest, state);
 347    } else {
 348       rewrite_def_forwards(&instr->dest.dest, state);
 349    }
 350 }
 351
 352 static void
 353 rewrite_phi_instr(nir_phi_instr *instr, rewrite_state *state)
 354 {
 355    state->parent_instr = &instr->instr;
 356    rewrite_def_forwards(&instr->dest, state);
 357 }
 358
 359 static void
 360 rewrite_instr_forward(nir_instr *instr, rewrite_state *state)
 361 {
 362    if (instr->type == nir_instr_type_alu) {
 363       rewrite_alu_instr_forward(nir_instr_as_alu(instr), state);
 364       return;
 365    }
 366
 367    if (instr->type == nir_instr_type_phi) {
 368       rewrite_phi_instr(nir_instr_as_phi(instr), state);
 369       return;
 370    }
 371
 372    state->parent_instr = instr;
 373
 374    nir_foreach_src(instr, rewrite_use, state);
 375    nir_foreach_dest(instr, rewrite_def_forwards, state);
 376 }
 377
 378 static void
 379 rewrite_phi_sources(nir_block *block, nir_block *pred, rewrite_state *state)
 380 {
 381    nir_foreach_instr(block, instr) {
 382       if (instr->type != nir_instr_type_phi)
 383          break;
 384
 385       nir_phi_instr *phi_instr = nir_instr_as_phi(instr);
 386
 387       state->parent_instr = instr;
 388
 389       foreach_list_typed(nir_phi_src, src, node, &phi_instr->srcs) {
 390          if (src->pred == pred) {
 391             rewrite_use(&src->src, state);
 392             break;
 393          }
 394       }
 395    }
 396 }
 397
 398 static bool
 399 rewrite_def_backwards(nir_dest *dest, void *_state)
 400 {
 401    rewrite_state *state = (rewrite_state *) _state;
 402
 403    if (!dest->is_ssa)
 404       return true;
 405
 406    struct hash_entry *entry =
 407       _mesa_hash_table_search(state->ssa_map, &dest->ssa);
 408
 409    if (!entry)
 410       return true;
 411
 412    nir_register *reg = (nir_register *) entry->data;
 413    unsigned index = reg->index;
 414
 415    state->states[index].index--;
 416    assert(state->states[index].index >= -1);
 417
 418    return true;
 419 }
 420
 421 static void
 422 rewrite_instr_backwards(nir_instr *instr, rewrite_state *state)
 423 {
 424    nir_foreach_dest(instr, rewrite_def_backwards, state);
 425 }
 426
 427 static void
 428 rewrite_block(nir_block *block, rewrite_state *state)
 429 {
 430    /* This will skip over any instructions after the current one, which is
 431     * what we want because those instructions (vector gather, conditional
 432     * select) will already be in SSA form.
 433     */
 434    nir_foreach_instr_safe(block, instr) {
 435       rewrite_instr_forward(instr, state);
 436    }
 437
 438    if (block != state->impl->end_block &&
 439        !nir_cf_node_is_last(&block->cf_node) &&
 440        nir_cf_node_next(&block->cf_node)->type == nir_cf_node_if) {
 441       nir_if *if_stmt = nir_cf_node_as_if(nir_cf_node_next(&block->cf_node));
 442       state->parent_instr = NULL;
 443       state->parent_if = if_stmt;
 444       rewrite_use(&if_stmt->condition, state);
 445    }
 446
 447    if (block->successors[0])
 448       rewrite_phi_sources(block->successors[0], block, state);
 449    if (block->successors[1])
 450       rewrite_phi_sources(block->successors[1], block, state);
 451
 452    for (unsigned i = 0; i < block->num_dom_children; i++)
 453       rewrite_block(block->dom_children[i], state);
 454
 455    nir_foreach_instr_reverse(block, instr) {
 456       rewrite_instr_backwards(instr, state);
 457    }
 458 }
 459
 460 static void
 461 remove_unused_regs(nir_function_impl *impl, rewrite_state *state)
 462 {
 463    foreach_list_typed_safe(nir_register, reg, node, &impl->registers) {
 464       if (state->states[reg->index].stack != NULL)
 465          exec_node_remove(&reg->node);
 466    }
 467 }
 468
 469 static void
 470 init_rewrite_state(nir_function_impl *impl, rewrite_state *state)
 471 {
 472    state->impl = impl;
 473    state->mem_ctx = ralloc_parent(impl);
 474    state->ssa_map = _mesa_hash_table_create(NULL, _mesa_hash_pointer,
 475                                             _mesa_key_pointer_equal);
 476    state->states = ralloc_array(NULL, reg_state, impl->reg_alloc);
 477
 478    foreach_list_typed(nir_register, reg, node, &impl->registers) {
 479       assert(reg->index < impl->reg_alloc);
 480       if (reg->num_array_elems > 0) {
 481          state->states[reg->index].stack = NULL;
 482       } else {
 483          /*
 484           * Calculate a conservative estimate of the stack size based on the
 485           * number of definitions there are. Note that this function *must* be
 486           * called after phi nodes are inserted so we can count phi node
 487           * definitions too.
 488           */
 489          unsigned stack_size = reg->defs->entries;
 490
 491          state->states[reg->index].stack = ralloc_array(state->states,
 492                                                         nir_ssa_def *,
 493                                                         stack_size);
 494 #ifdef DEBUG
 495          state->states[reg->index].stack_size = stack_size;
 496 #endif
 497          state->states[reg->index].index = -1;
 498          state->states[reg->index].num_defs = 0;
 499       }
 500    }
 501 }
 502
 503 static void
 504 destroy_rewrite_state(rewrite_state *state)
 505 {
 506    _mesa_hash_table_destroy(state->ssa_map, NULL);
 507    ralloc_free(state->states);
 508 }
 509
 510 void
 511 nir_convert_to_ssa_impl(nir_function_impl *impl)
 512 {
 513    nir_metadata_require(impl, nir_metadata_dominance);
 514
 515    insert_phi_nodes(impl);
 516
 517    rewrite_state state;
 518    init_rewrite_state(impl, &state);
 519
 520    rewrite_block(impl->start_block, &state);
 521
 522    remove_unused_regs(impl, &state);
 523
 524    nir_metadata_preserve(impl, nir_metadata_block_index |
 525                                nir_metadata_dominance);
 526
 527    destroy_rewrite_state(&state);
 528 }
 529
 530 void
 531 nir_convert_to_ssa(nir_shader *shader)
 532 {
 533    nir_foreach_overload(shader, overload) {
 534       if (overload->impl)
 535          nir_convert_to_ssa_impl(overload->impl);
 536    }
 537 }