src/compiler/nir/nir_lower_phis_to_scalar.c

   1 /*
   2  * Copyright © 2015 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  *    Jason Ekstrand (jason@jlekstrand.net)
  25  *
  26  */
  27
  28 #include "nir.h"
  29
  30 /*
  31  * Implements a pass that lowers vector phi nodes to scalar phi nodes when
  32  * we don't think it will hurt anything.
  33  */
  34
  35 struct lower_phis_to_scalar_state {
  36    void *mem_ctx;
  37    void *dead_ctx;
  38
  39    /* Hash table marking which phi nodes are scalarizable.  The key is
  40     * pointers to phi instructions and the entry is either NULL for not
  41     * scalarizable or non-null for scalarizable.
  42     */
  43    struct hash_table *phi_table;
  44 };
  45
  46 static bool
  47 should_lower_phi(nir_phi_instr *phi, struct lower_phis_to_scalar_state *state);
  48
  49 static bool
  50 is_phi_src_scalarizable(nir_phi_src *src,
  51                         struct lower_phis_to_scalar_state *state)
  52 {
  53    /* Don't know what to do with non-ssa sources */
  54    if (!src->src.is_ssa)
  55       return false;
  56
  57    nir_instr *src_instr = src->src.ssa->parent_instr;
  58    switch (src_instr->type) {
  59    case nir_instr_type_alu: {
  60       nir_alu_instr *src_alu = nir_instr_as_alu(src_instr);
  61
  62       /* ALU operations with output_size == 0 should be scalarized.  We
  63        * will also see a bunch of vecN operations from scalarizing ALU
  64        * operations and, since they can easily be copy-propagated, they
  65        * are ok too.
  66        */
  67       return nir_op_infos[src_alu->op].output_size == 0 ||
  68              src_alu->op == nir_op_vec2 ||
  69              src_alu->op == nir_op_vec3 ||
  70              src_alu->op == nir_op_vec4;
  71    }
  72
  73    case nir_instr_type_phi:
  74       /* A phi is scalarizable if we're going to lower it */
  75       return should_lower_phi(nir_instr_as_phi(src_instr), state);
  76
  77    case nir_instr_type_load_const:
  78       /* These are trivially scalarizable */
  79       return true;
  80
  81    case nir_instr_type_ssa_undef:
  82       /* The caller of this function is going to OR the results and we don't
  83        * want undefs to count so we return false.
  84        */
  85       return false;
  86
  87    case nir_instr_type_intrinsic: {
  88       nir_intrinsic_instr *src_intrin = nir_instr_as_intrinsic(src_instr);
  89
  90       switch (src_intrin->intrinsic) {
  91       case nir_intrinsic_load_deref: {
  92          nir_deref_instr *deref = nir_src_as_deref(src_intrin->src[0]);
  93          return deref->mode == nir_var_shader_in ||
  94                 deref->mode == nir_var_uniform ||
  95                 deref->mode == nir_var_mem_ubo ||
  96                 deref->mode == nir_var_mem_ssbo ||
  97                 deref->mode == nir_var_mem_global;
  98       }
  99
 100       case nir_intrinsic_interp_deref_at_centroid:
 101       case nir_intrinsic_interp_deref_at_sample:
 102       case nir_intrinsic_interp_deref_at_offset:
 103       case nir_intrinsic_interp_deref_at_vertex:
 104       case nir_intrinsic_load_uniform:
 105       case nir_intrinsic_load_ubo:
 106       case nir_intrinsic_load_ssbo:
 107       case nir_intrinsic_load_global:
 108       case nir_intrinsic_load_input:
 109          return true;
 110       default:
 111          break;
 112       }
 113    }
 114
 115    default:
 116       /* We can't scalarize this type of instruction */
 117       return false;
 118    }
 119 }
 120
 121 /**
 122  * Determines if the given phi node should be lowered.  The only phi nodes
 123  * we will scalarize at the moment are those where all of the sources are
 124  * scalarizable.
 125  *
 126  * The reason for this comes down to coalescing.  Since phi sources can't
 127  * swizzle, swizzles on phis have to be resolved by inserting a mov right
 128  * before the phi.  The choice then becomes between movs to pick off
 129  * components for a scalar phi or potentially movs to recombine components
 130  * for a vector phi.  The problem is that the movs generated to pick off
 131  * the components are almost uncoalescable.  We can't coalesce them in NIR
 132  * because we need them to pick off components and we can't coalesce them
 133  * in the backend because the source register is a vector and the
 134  * destination is a scalar that may be used at other places in the program.
 135  * On the other hand, if we have a bunch of scalars going into a vector
 136  * phi, the situation is much better.  In this case, if the SSA def is
 137  * generated in the predecessor block to the corresponding phi source, the
 138  * backend code will be an ALU op into a temporary and then a mov into the
 139  * given vector component;  this move can almost certainly be coalesced
 140  * away.
 141  */
 142 static bool
 143 should_lower_phi(nir_phi_instr *phi, struct lower_phis_to_scalar_state *state)
 144 {
 145    /* Already scalar */
 146    if (phi->dest.ssa.num_components == 1)
 147       return false;
 148
 149    struct hash_entry *entry = _mesa_hash_table_search(state->phi_table, phi);
 150    if (entry)
 151       return entry->data != NULL;
 152
 153    /* Insert an entry and mark it as scalarizable for now. That way
 154     * we don't recurse forever and a cycle in the dependence graph
 155     * won't automatically make us fail to scalarize.
 156     */
 157    entry = _mesa_hash_table_insert(state->phi_table, phi, (void *)(intptr_t)1);
 158
 159    bool scalarizable = false;
 160
 161    nir_foreach_phi_src(src, phi) {
 162       /* This loop ignores srcs that are not scalarizable because its likely
 163        * still worth copying to temps if another phi source is scalarizable.
 164        * This reduces register spilling by a huge amount in the i965 driver for
 165        * Deus Ex: MD.
 166        */
 167       scalarizable = is_phi_src_scalarizable(src, state);
 168       if (scalarizable)
 169          break;
 170    }
 171
 172    /* The hash table entry for 'phi' may have changed while recursing the
 173     * dependence graph, so we need to reset it */
 174    entry = _mesa_hash_table_search(state->phi_table, phi);
 175    assert(entry);
 176
 177    entry->data = (void *)(intptr_t)scalarizable;
 178
 179    return scalarizable;
 180 }
 181
 182 static bool
 183 lower_phis_to_scalar_block(nir_block *block,
 184                            struct lower_phis_to_scalar_state *state)
 185 {
 186    bool progress = false;
 187
 188    /* Find the last phi node in the block */
 189    nir_phi_instr *last_phi = NULL;
 190    nir_foreach_instr(instr, block) {
 191       if (instr->type != nir_instr_type_phi)
 192          break;
 193
 194       last_phi = nir_instr_as_phi(instr);
 195    }
 196
 197    /* We have to handle the phi nodes in their own pass due to the way
 198     * we're modifying the linked list of instructions.
 199     */
 200    nir_foreach_instr_safe(instr, block) {
 201       if (instr->type != nir_instr_type_phi)
 202          break;
 203
 204       nir_phi_instr *phi = nir_instr_as_phi(instr);
 205
 206       if (!should_lower_phi(phi, state))
 207          continue;
 208
 209       unsigned bit_size = phi->dest.ssa.bit_size;
 210
 211       /* Create a vecN operation to combine the results.  Most of these
 212        * will be redundant, but copy propagation should clean them up for
 213        * us.  No need to add the complexity here.
 214        */
 215       nir_op vec_op;
 216       switch (phi->dest.ssa.num_components) {
 217       case 2: vec_op = nir_op_vec2; break;
 218       case 3: vec_op = nir_op_vec3; break;
 219       case 4: vec_op = nir_op_vec4; break;
 220       default: unreachable("Invalid number of components");
 221       }
 222
 223       nir_alu_instr *vec = nir_alu_instr_create(state->mem_ctx, vec_op);
 224       nir_ssa_dest_init(&vec->instr, &vec->dest.dest,
 225                         phi->dest.ssa.num_components,
 226                         bit_size, NULL);
 227       vec->dest.write_mask = (1 << phi->dest.ssa.num_components) - 1;
 228
 229       for (unsigned i = 0; i < phi->dest.ssa.num_components; i++) {
 230          nir_phi_instr *new_phi = nir_phi_instr_create(state->mem_ctx);
 231          nir_ssa_dest_init(&new_phi->instr, &new_phi->dest, 1,
 232                            phi->dest.ssa.bit_size, NULL);
 233
 234          vec->src[i].src = nir_src_for_ssa(&new_phi->dest.ssa);
 235
 236          nir_foreach_phi_src(src, phi) {
 237             /* We need to insert a mov to grab the i'th component of src */
 238             nir_alu_instr *mov = nir_alu_instr_create(state->mem_ctx,
 239                                                       nir_op_mov);
 240             nir_ssa_dest_init(&mov->instr, &mov->dest.dest, 1, bit_size, NULL);
 241             mov->dest.write_mask = 1;
 242             nir_src_copy(&mov->src[0].src, &src->src, state->mem_ctx);
 243             mov->src[0].swizzle[0] = i;
 244
 245             /* Insert at the end of the predecessor but before the jump */
 246             nir_instr *pred_last_instr = nir_block_last_instr(src->pred);
 247             if (pred_last_instr && pred_last_instr->type == nir_instr_type_jump)
 248                nir_instr_insert_before(pred_last_instr, &mov->instr);
 249             else
 250                nir_instr_insert_after_block(src->pred, &mov->instr);
 251
 252             nir_phi_src *new_src = ralloc(new_phi, nir_phi_src);
 253             new_src->pred = src->pred;
 254             new_src->src = nir_src_for_ssa(&mov->dest.dest.ssa);
 255
 256             exec_list_push_tail(&new_phi->srcs, &new_src->node);
 257          }
 258
 259          nir_instr_insert_before(&phi->instr, &new_phi->instr);
 260       }
 261
 262       nir_instr_insert_after(&last_phi->instr, &vec->instr);
 263
 264       nir_ssa_def_rewrite_uses(&phi->dest.ssa,
 265                                nir_src_for_ssa(&vec->dest.dest.ssa));
 266
 267       ralloc_steal(state->dead_ctx, phi);
 268       nir_instr_remove(&phi->instr);
 269
 270       progress = true;
 271
 272       /* We're using the safe iterator and inserting all the newly
 273        * scalarized phi nodes before their non-scalarized version so that's
 274        * ok.  However, we are also inserting vec operations after all of
 275        * the last phi node so once we get here, we can't trust even the
 276        * safe iterator to stop properly.  We have to break manually.
 277        */
 278       if (instr == &last_phi->instr)
 279          break;
 280    }
 281
 282    return progress;
 283 }
 284
 285 static bool
 286 lower_phis_to_scalar_impl(nir_function_impl *impl)
 287 {
 288    struct lower_phis_to_scalar_state state;
 289    bool progress = false;
 290
 291    state.mem_ctx = ralloc_parent(impl);
 292    state.dead_ctx = ralloc_context(NULL);
 293    state.phi_table = _mesa_pointer_hash_table_create(state.dead_ctx);
 294
 295    nir_foreach_block(block, impl) {
 296       progress = lower_phis_to_scalar_block(block, &state) || progress;
 297    }
 298
 299    nir_metadata_preserve(impl, nir_metadata_block_index |
 300                                nir_metadata_dominance);
 301
 302    ralloc_free(state.dead_ctx);
 303    return progress;
 304 }
 305
 306 /** A pass that lowers vector phi nodes to scalar
 307  *
 308  * This pass loops through the blocks and lowers looks for vector phi nodes
 309  * it can lower to scalar phi nodes.  Not all phi nodes are lowered.  For
 310  * instance, if one of the sources is a non-scalarizable vector, then we
 311  * don't bother lowering because that would generate hard-to-coalesce movs.
 312  */
 313 bool
 314 nir_lower_phis_to_scalar(nir_shader *shader)
 315 {
 316    bool progress = false;
 317
 318    nir_foreach_function(function, shader) {
 319       if (function->impl)
 320          progress = lower_phis_to_scalar_impl(function->impl) || progress;
 321    }
 322
 323    return progress;
 324 }