Home | History | Annotate | Download | only in nir 
      1 /*
      2  * Copyright  2015 Connor Abbott
      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 (at) gmail.com)
     25  *
     26  */
     27 
     28 #include "nir.h"
     29 #include "nir_builder.h"
     30 
     31 static nir_alu_instr *
     32 get_parent_mov(nir_ssa_def *ssa)
     33 {
     34    if (ssa->parent_instr->type != nir_instr_type_alu)
     35       return NULL;
     36 
     37    nir_alu_instr *alu = nir_instr_as_alu(ssa->parent_instr);
     38    return (alu->op == nir_op_imov || alu->op == nir_op_fmov) ? alu : NULL;
     39 }
     40 
     41 static bool
     42 matching_mov(nir_alu_instr *mov1, nir_ssa_def *ssa)
     43 {
     44    if (!mov1)
     45       return false;
     46 
     47    nir_alu_instr *mov2 = get_parent_mov(ssa);
     48    return mov2 && nir_alu_srcs_equal(mov1, mov2, 0, 0);
     49 }
     50 
     51 /*
     52  * This is a pass for removing phi nodes that look like:
     53  * a = phi(b, b, b, ...)
     54  *
     55  * Note that we can't ignore undef sources here, or else we may create a
     56  * situation where the definition of b isn't dominated by its uses. We're
     57  * allowed to do this since the definition of b must dominate all of the
     58  * phi node's predecessors, which means it must dominate the phi node as well
     59  * as all of the phi node's uses. In essence, the phi node acts as a copy
     60  * instruction. b can't be another phi node in the same block, since the only
     61  * time when phi nodes can source other phi nodes defined in the same block is
     62  * at the loop header, and in that case one of the sources of the phi has to
     63  * be from before the loop and that source can't be b.
     64  */
     65 
     66 static bool
     67 remove_phis_block(nir_block *block, nir_builder *b)
     68 {
     69    bool progress = false;
     70 
     71    nir_foreach_instr_safe(instr, block) {
     72       if (instr->type != nir_instr_type_phi)
     73          break;
     74 
     75       nir_phi_instr *phi = nir_instr_as_phi(instr);
     76 
     77       nir_ssa_def *def = NULL;
     78       nir_alu_instr *mov = NULL;
     79       bool srcs_same = true;
     80 
     81       nir_foreach_phi_src(src, phi) {
     82          assert(src->src.is_ssa);
     83 
     84          /* For phi nodes at the beginning of loops, we may encounter some
     85           * sources from backedges that point back to the destination of the
     86           * same phi, i.e. something like:
     87           *
     88           * a = phi(a, b, ...)
     89           *
     90           * We can safely ignore these sources, since if all of the normal
     91           * sources point to the same definition, then that definition must
     92           * still dominate the phi node, and the phi will still always take
     93           * the value of that definition.
     94           */
     95          if (src->src.ssa == &phi->dest.ssa)
     96             continue;
     97 
     98          if (def == NULL) {
     99             def  = src->src.ssa;
    100             mov = get_parent_mov(def);
    101          } else {
    102             if (src->src.ssa != def && !matching_mov(mov, src->src.ssa)) {
    103                srcs_same = false;
    104                break;
    105             }
    106          }
    107       }
    108 
    109       if (!srcs_same)
    110          continue;
    111 
    112       /* We must have found at least one definition, since there must be at
    113        * least one forward edge.
    114        */
    115       assert(def != NULL);
    116 
    117       if (mov) {
    118          /* If the sources were all mov's from the same source with the same
    119           * swizzle, then we can't just pick a random move because it may not
    120           * dominate the phi node. Instead, we need to emit our own move after
    121           * the phi which uses the shared source, and rewrite uses of the phi
    122           * to use the move instead. This is ok, because while the mov's may
    123           * not all dominate the phi node, their shared source does.
    124           */
    125 
    126          b->cursor = nir_after_phis(block);
    127          def = mov->op == nir_op_imov ?
    128             nir_imov_alu(b, mov->src[0], def->num_components) :
    129             nir_fmov_alu(b, mov->src[0], def->num_components);
    130       }
    131 
    132       assert(phi->dest.is_ssa);
    133       nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def));
    134       nir_instr_remove(instr);
    135 
    136       progress = true;
    137    }
    138 
    139    return progress;
    140 }
    141 
    142 static bool
    143 remove_phis_impl(nir_function_impl *impl)
    144 {
    145    bool progress = false;
    146    nir_builder bld;
    147    nir_builder_init(&bld, impl);
    148 
    149    nir_foreach_block(block, impl) {
    150       progress |= remove_phis_block(block, &bld);
    151    }
    152 
    153    if (progress) {
    154       nir_metadata_preserve(impl, nir_metadata_block_index |
    155                                   nir_metadata_dominance);
    156    }
    157 
    158    return progress;
    159 }
    160 
    161 bool
    162 nir_opt_remove_phis(nir_shader *shader)
    163 {
    164    bool progress = false;
    165 
    166    nir_foreach_function(function, shader)
    167       if (function->impl)
    168          progress = remove_phis_impl(function->impl) || progress;
    169 
    170    return progress;
    171 }
    172 
    173