• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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@gmail.com)
25  *
26  */
27 
28 #include "nir.h"
29 #include "nir_builder.h"
30 
31 static nir_alu_instr *
get_parent_mov(nir_ssa_def * ssa)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_mov) ? alu : NULL;
39 }
40 
41 static bool
matching_mov(nir_alu_instr * mov1,nir_ssa_def * ssa)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 always 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
remove_phis_block(nir_block * block,nir_builder * b)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 if (src->src.ssa->parent_instr->type == nir_instr_type_ssa_undef &&
102                     nir_block_dominates(def->parent_instr->block, src->pred)) {
103             /* Ignore this undef source. */
104          } else {
105             if (src->src.ssa != def && !matching_mov(mov, src->src.ssa)) {
106                srcs_same = false;
107                break;
108             }
109          }
110       }
111 
112       if (!srcs_same)
113          continue;
114 
115       if (!def) {
116          /* In this case, the phi had no sources. So turn it into an undef. */
117 
118          b->cursor = nir_after_phis(block);
119          def = nir_ssa_undef(b, phi->dest.ssa.num_components,
120                              phi->dest.ssa.bit_size);
121       } else if (mov) {
122          /* If the sources were all movs from the same source with the same
123           * swizzle, then we can't just pick a random move because it may not
124           * dominate the phi node. Instead, we need to emit our own move after
125           * the phi which uses the shared source, and rewrite uses of the phi
126           * to use the move instead. This is ok, because while the movs may
127           * not all dominate the phi node, their shared source does.
128           */
129 
130          b->cursor = nir_after_phis(block);
131          def = nir_mov_alu(b, mov->src[0], def->num_components);
132       }
133 
134       assert(phi->dest.is_ssa);
135       nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def));
136       nir_instr_remove(instr);
137 
138       progress = true;
139    }
140 
141    return progress;
142 }
143 
144 bool
nir_opt_remove_phis_block(nir_block * block)145 nir_opt_remove_phis_block(nir_block *block)
146 {
147    nir_builder b;
148    nir_builder_init(&b, nir_cf_node_get_function(&block->cf_node));
149    return remove_phis_block(block, &b);
150 }
151 
152 static bool
nir_opt_remove_phis_impl(nir_function_impl * impl)153 nir_opt_remove_phis_impl(nir_function_impl *impl)
154 {
155    bool progress = false;
156    nir_builder bld;
157    nir_builder_init(&bld, impl);
158 
159    nir_metadata_require(impl, nir_metadata_dominance);
160 
161    nir_foreach_block(block, impl) {
162       progress |= remove_phis_block(block, &bld);
163    }
164 
165    if (progress) {
166       nir_metadata_preserve(impl, nir_metadata_block_index |
167                                   nir_metadata_dominance);
168    } else {
169       nir_metadata_preserve(impl, nir_metadata_all);
170    }
171 
172    return progress;
173 }
174 
175 bool
nir_opt_remove_phis(nir_shader * shader)176 nir_opt_remove_phis(nir_shader *shader)
177 {
178    bool progress = false;
179 
180    nir_foreach_function(function, shader)
181       if (function->impl)
182          progress = nir_opt_remove_phis_impl(function->impl) || progress;
183 
184    return progress;
185 }
186 
187