mirror of OpenBSD xenocara tree
github.com/openbsd/xenocara
openbsd
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
31static bool
32phi_srcs_equal(nir_def *a, nir_def *b)
33{
34 if (a == b)
35 return true;
36
37 if (a->parent_instr->type != b->parent_instr->type)
38 return false;
39
40 if (a->parent_instr->type != nir_instr_type_alu &&
41 a->parent_instr->type != nir_instr_type_load_const)
42 return false;
43
44 if (!nir_instrs_equal(a->parent_instr, b->parent_instr))
45 return false;
46
47 /* nir_instrs_equal ignores exact/fast_math */
48 if (a->parent_instr->type == nir_instr_type_alu) {
49 nir_alu_instr *a_alu = nir_instr_as_alu(a->parent_instr);
50 nir_alu_instr *b_alu = nir_instr_as_alu(b->parent_instr);
51 if (a_alu->exact != b_alu->exact || a_alu->fp_fast_math != b_alu->fp_fast_math)
52 return false;
53 }
54
55 return true;
56}
57
58static bool
59src_dominates_block(nir_src *src, void *state)
60{
61 nir_block *block = state;
62 return nir_block_dominates(src->ssa->parent_instr->block, block);
63}
64
65static bool
66can_rematerialize_phi_src(nir_block *imm_dom, nir_def *def)
67{
68 if (def->parent_instr->type == nir_instr_type_alu) {
69 return nir_foreach_src(def->parent_instr, src_dominates_block, imm_dom);
70 } else if (def->parent_instr->type == nir_instr_type_load_const) {
71 return true;
72 }
73 return false;
74}
75
76/*
77 * This is a pass for removing phi nodes that look like:
78 * a = phi(b, b, b, ...)
79 *
80 * Note that we can't always ignore undef sources here, or else we may create a
81 * situation where the definition of b isn't dominated by its uses. We're
82 * allowed to do this since the definition of b must dominate all of the
83 * phi node's predecessors, which means it must dominate the phi node as well
84 * as all of the phi node's uses. In essence, the phi node acts as a copy
85 * instruction. b can't be another phi node in the same block, since the only
86 * time when phi nodes can source other phi nodes defined in the same block is
87 * at the loop header, and in that case one of the sources of the phi has to
88 * be from before the loop and that source can't be b.
89 */
90
91static bool
92remove_phis_block(nir_block *block, nir_builder *b)
93{
94 bool progress = false;
95
96 nir_foreach_phi_safe(phi, block) {
97 nir_def *def = NULL;
98 bool srcs_same = true;
99 bool needs_remat = false;
100
101 nir_foreach_phi_src(src, phi) {
102 /* For phi nodes at the beginning of loops, we may encounter some
103 * sources from backedges that point back to the destination of the
104 * same phi, i.e. something like:
105 *
106 * a = phi(a, b, ...)
107 *
108 * We can safely ignore these sources, since if all of the normal
109 * sources point to the same definition, then that definition must
110 * still dominate the phi node, and the phi will still always take
111 * the value of that definition.
112 */
113 if (src->src.ssa == &phi->def)
114 continue;
115
116 /* Ignore undef sources. */
117 if (nir_src_is_undef(src->src))
118 continue;
119
120 if (def == NULL) {
121 def = src->src.ssa;
122 if (!nir_block_dominates(def->parent_instr->block, block->imm_dom)) {
123 if (!can_rematerialize_phi_src(block->imm_dom, def)) {
124 srcs_same = false;
125 break;
126 }
127 needs_remat = true;
128 }
129 } else if (!phi_srcs_equal(src->src.ssa, def)) {
130 srcs_same = false;
131 break;
132 }
133 }
134
135 if (!srcs_same)
136 continue;
137
138 if (!def) {
139 /* In this case, the phi had no non undef sources. So turn it into an undef. */
140 b->cursor = nir_after_phis(block);
141 def = nir_undef(b, phi->def.num_components, phi->def.bit_size);
142 } else if (needs_remat) {
143 b->cursor = nir_after_block_before_jump(block->imm_dom);
144 nir_instr *remat = nir_instr_clone(b->shader, def->parent_instr);
145 nir_builder_instr_insert(b, remat);
146 def = nir_instr_def(remat);
147 }
148
149 nir_def_replace(&phi->def, def);
150
151 progress = true;
152 }
153
154 return progress;
155}
156
157bool
158nir_remove_single_src_phis_block(nir_block *block)
159{
160 assert(block->predecessors->entries <= 1);
161 bool progress = false;
162 nir_foreach_phi_safe(phi, block) {
163 nir_def *def = NULL;
164 nir_foreach_phi_src(src, phi) {
165 def = src->src.ssa;
166 break;
167 }
168
169 if (!def) {
170 nir_builder b = nir_builder_create(nir_cf_node_get_function(&block->cf_node));
171 b.cursor = nir_after_phis(block);
172 def = nir_undef(&b, phi->def.num_components, phi->def.bit_size);
173 }
174
175 nir_def_replace(&phi->def, def);
176 progress = true;
177 }
178 return progress;
179}
180
181static bool
182nir_opt_remove_phis_impl(nir_function_impl *impl)
183{
184 bool progress = false;
185 nir_builder bld = nir_builder_create(impl);
186
187 nir_metadata_require(impl, nir_metadata_dominance);
188
189 nir_foreach_block(block, impl) {
190 progress |= remove_phis_block(block, &bld);
191 }
192
193 if (progress) {
194 nir_metadata_preserve(impl, nir_metadata_control_flow);
195 } else {
196 nir_metadata_preserve(impl, nir_metadata_all);
197 }
198
199 return progress;
200}
201
202bool
203nir_opt_remove_phis(nir_shader *shader)
204{
205 bool progress = false;
206
207 nir_foreach_function_impl(impl, shader)
208 progress = nir_opt_remove_phis_impl(impl) || progress;
209
210 return progress;
211}