1 /*
2 * Copyright © 2018 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
24 #include "nir.h"
25 #include "nir_builder.h"
26 #include "nir_control_flow.h"
27 #include "nir_worklist.h"
28
29 static bool
nir_op_is_derivative(nir_op op)30 nir_op_is_derivative(nir_op op)
31 {
32 return op == nir_op_fddx ||
33 op == nir_op_fddy ||
34 op == nir_op_fddx_fine ||
35 op == nir_op_fddy_fine ||
36 op == nir_op_fddx_coarse ||
37 op == nir_op_fddy_coarse;
38 }
39
40 static bool
nir_texop_implies_derivative(nir_texop op)41 nir_texop_implies_derivative(nir_texop op)
42 {
43 return op == nir_texop_tex ||
44 op == nir_texop_txb ||
45 op == nir_texop_lod;
46 }
47 #define MOVE_INSTR_FLAG 1
48 #define STOP_PROCESSING_INSTR_FLAG 2
49
50 /** Check recursively if the source can be moved to the top of the shader.
51 * Sets instr->pass_flags to MOVE_INSTR_FLAG and adds the instr
52 * to the given worklist
53 */
54 static bool
can_move_src(nir_src * src,void * worklist)55 can_move_src(nir_src *src, void *worklist)
56 {
57 if (!src->is_ssa)
58 return false;
59
60 nir_instr *instr = src->ssa->parent_instr;
61 if (instr->pass_flags)
62 return true;
63
64 /* Phi instructions can't be moved at all. Also, if we're dependent on
65 * a phi then we are dependent on some other bit of control flow and
66 * it's hard to figure out the proper condition.
67 */
68 if (instr->type == nir_instr_type_phi)
69 return false;
70
71 if (instr->type == nir_instr_type_intrinsic) {
72 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
73 if (intrin->intrinsic == nir_intrinsic_load_deref) {
74 nir_deref_instr *deref = nir_src_as_deref(intrin->src[0]);
75 if (!nir_deref_mode_is_one_of(deref, nir_var_read_only_modes))
76 return false;
77 } else if (!(nir_intrinsic_infos[intrin->intrinsic].flags &
78 NIR_INTRINSIC_CAN_REORDER)) {
79 return false;
80 }
81 }
82
83 /* set pass_flags and remember the instruction for potential cleanup */
84 instr->pass_flags = MOVE_INSTR_FLAG;
85 nir_instr_worklist_push_tail(worklist, instr);
86
87 if (!nir_foreach_src(instr, can_move_src, worklist)) {
88 return false;
89 }
90 return true;
91 }
92
93 /** Try to mark a discard or demote instruction for moving
94 *
95 * This function does two things. One is that it searches through the
96 * dependency chain to see if this discard is an instruction that we can move
97 * up to the top. Second, if the discard is one we can move, it tags the
98 * discard and its dependencies (using pass_flags = 1).
99 * Demote are handled the same way, except that they can still be moved up
100 * when implicit derivatives are used.
101 */
102 static bool
try_move_discard(nir_intrinsic_instr * discard)103 try_move_discard(nir_intrinsic_instr *discard)
104 {
105 /* We require the discard to be in the top level of control flow. We
106 * could, in theory, move discards that are inside ifs or loops but that
107 * would be a lot more work.
108 */
109 if (discard->instr.block->cf_node.parent->type != nir_cf_node_function)
110 return false;
111
112 /* Build the set of all instructions discard depends on to be able to
113 * clear the flags in case the discard cannot be moved.
114 */
115 nir_instr_worklist *work = nir_instr_worklist_create();
116 if (!work)
117 return false;
118 discard->instr.pass_flags = MOVE_INSTR_FLAG;
119
120 bool can_move_discard = can_move_src(&discard->src[0], work);
121 if (!can_move_discard) {
122 /* Moving the discard is impossible: clear the flags */
123 discard->instr.pass_flags = 0;
124 nir_foreach_instr_in_worklist(instr, work)
125 instr->pass_flags = 0;
126 }
127
128 nir_instr_worklist_destroy(work);
129
130 return can_move_discard;
131 }
132
133 static bool
opt_move_discards_to_top_impl(nir_function_impl * impl)134 opt_move_discards_to_top_impl(nir_function_impl *impl)
135 {
136 bool progress = false;
137 bool consider_discards = true;
138 bool moved = false;
139
140 /* Walk through the instructions and look for a discard that we can move
141 * to the top of the program. If we hit any operation along the way that
142 * we cannot safely move a discard above, break out of the loop and stop
143 * trying to move any more discards.
144 */
145 nir_foreach_block(block, impl) {
146 nir_foreach_instr_safe(instr, block) {
147 instr->pass_flags = 0;
148
149 switch (instr->type) {
150 case nir_instr_type_alu: {
151 nir_alu_instr *alu = nir_instr_as_alu(instr);
152 if (nir_op_is_derivative(alu->op))
153 consider_discards = false;
154 continue;
155 }
156
157 case nir_instr_type_deref:
158 case nir_instr_type_load_const:
159 case nir_instr_type_ssa_undef:
160 case nir_instr_type_phi:
161 /* These are all safe */
162 continue;
163
164 case nir_instr_type_call:
165 instr->pass_flags = STOP_PROCESSING_INSTR_FLAG;
166 /* We don't know what the function will do */
167 goto break_all;
168
169 case nir_instr_type_tex: {
170 nir_tex_instr *tex = nir_instr_as_tex(instr);
171 if (nir_texop_implies_derivative(tex->op))
172 consider_discards = false;
173 continue;
174 }
175
176 case nir_instr_type_intrinsic: {
177 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
178 if (nir_intrinsic_writes_external_memory(intrin)) {
179 instr->pass_flags = STOP_PROCESSING_INSTR_FLAG;
180 goto break_all;
181 }
182
183 if ((intrin->intrinsic == nir_intrinsic_discard_if && consider_discards) ||
184 intrin->intrinsic == nir_intrinsic_demote_if)
185 moved = moved || try_move_discard(intrin);
186 continue;
187 }
188
189 case nir_instr_type_jump: {
190 nir_jump_instr *jump = nir_instr_as_jump(instr);
191 /* A return would cause the discard to not get executed */
192 if (jump->type == nir_jump_return) {
193 instr->pass_flags = STOP_PROCESSING_INSTR_FLAG;
194 goto break_all;
195 }
196 continue;
197 }
198
199 case nir_instr_type_parallel_copy:
200 unreachable("Unhanded instruction type");
201 }
202 }
203 }
204 break_all:
205
206 if (moved) {
207 /* Walk the list of instructions and move the discard/demote and
208 * everything it depends on to the top. We walk the instruction list
209 * here because it ensures that everything stays in its original order.
210 * This provides stability for the algorithm and ensures that we don't
211 * accidentally get dependencies out-of-order.
212 */
213 nir_cursor cursor = nir_before_block(nir_start_block(impl));
214 nir_foreach_block(block, impl) {
215 nir_foreach_instr_safe(instr, block) {
216 if (instr->pass_flags == STOP_PROCESSING_INSTR_FLAG)
217 return progress;
218 if (instr->pass_flags == MOVE_INSTR_FLAG) {
219 progress |= nir_instr_move(cursor, instr);
220 cursor = nir_after_instr(instr);
221 }
222 }
223 }
224 }
225
226 return progress;
227 }
228
229 /* This optimization only operates on discard_if/demoe_if so
230 * nir_opt_conditional_discard and nir_lower_discard_or_demote
231 * should have been called before.
232 */
233 bool
nir_opt_move_discards_to_top(nir_shader * shader)234 nir_opt_move_discards_to_top(nir_shader *shader)
235 {
236 assert(shader->info.stage == MESA_SHADER_FRAGMENT);
237
238 bool progress = false;
239
240 if (!shader->info.fs.uses_discard)
241 return false;
242
243 nir_foreach_function(function, shader) {
244 if (function->impl && opt_move_discards_to_top_impl(function->impl)) {
245 nir_metadata_preserve(function->impl, nir_metadata_block_index |
246 nir_metadata_dominance);
247 progress = true;
248 }
249 }
250
251 return progress;
252 }
253