966a982516e3c4c5a52ca3f98ff2a737e2c2f421
[mesa.git] / src / compiler / nir / nir_opt_remove_phis.c
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 *
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
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 if (!def) {
113 /* In this case, the phi had no sources. So turn it into an undef. */
114
115 b->cursor = nir_after_phis(block);
116 def = nir_ssa_undef(b, phi->dest.ssa.num_components,
117 phi->dest.ssa.bit_size);
118 } else if (mov) {
119 /* If the sources were all movs from the same source with the same
120 * swizzle, then we can't just pick a random move because it may not
121 * dominate the phi node. Instead, we need to emit our own move after
122 * the phi which uses the shared source, and rewrite uses of the phi
123 * to use the move instead. This is ok, because while the movs may
124 * not all dominate the phi node, their shared source does.
125 */
126
127 b->cursor = nir_after_phis(block);
128 def = nir_mov_alu(b, mov->src[0], def->num_components);
129 }
130
131 assert(phi->dest.is_ssa);
132 nir_ssa_def_rewrite_uses(&phi->dest.ssa, nir_src_for_ssa(def));
133 nir_instr_remove(instr);
134
135 progress = true;
136 }
137
138 return progress;
139 }
140
141 bool
142 nir_opt_remove_phis_block(nir_block *block)
143 {
144 nir_builder b;
145 nir_builder_init(&b, nir_cf_node_get_function(&block->cf_node));
146 return remove_phis_block(block, &b);
147 }
148
149 static bool
150 nir_opt_remove_phis_impl(nir_function_impl *impl)
151 {
152 bool progress = false;
153 nir_builder bld;
154 nir_builder_init(&bld, impl);
155
156 nir_foreach_block(block, impl) {
157 progress |= remove_phis_block(block, &bld);
158 }
159
160 if (progress) {
161 nir_metadata_preserve(impl, nir_metadata_block_index |
162 nir_metadata_dominance);
163 } else {
164 nir_metadata_preserve(impl, nir_metadata_all);
165 }
166
167 return progress;
168 }
169
170 bool
171 nir_opt_remove_phis(nir_shader *shader)
172 {
173 bool progress = false;
174
175 nir_foreach_function(function, shader)
176 if (function->impl)
177 progress = nir_opt_remove_phis_impl(function->impl) || progress;
178
179 return progress;
180 }
181