1 /*
2 * Copyright (C) 2019 Collabora, Ltd.
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 FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 *
23 * Authors (Collabora):
24 * Alyssa Rosenzweig <[email protected]>
25 */
26
27 #include "compiler.h"
28
29 /* Midgard texture/derivative operations have a pair of bits controlling the
30 * behaviour of helper invocations:
31 *
32 * - Should a helper invocation terminate after executing this instruction?
33 * - Should a helper invocation actually execute this instruction?
34 *
35 * The terminate bit should be set on the last instruction requiring helper
36 * invocations. Without control flow, that's literally the last instruction;
37 * with control flow, there may be multiple such instructions (with ifs) or no
38 * such instruction (with loops).
39 *
40 * The execute bit should be set if the value of this instruction is required
41 * by a future instruction requiring helper invocations. Consider:
42 *
43 * 0 = texture ...
44 * 1 = fmul 0, #10
45 * 2 = dfdx 1
46 * store 2
47 *
48 * Since the derivative calculation 2 requires helper invocations, the value 1
49 * must be calculated by helper invocations, and since it depends on 0, 0 must
50 * be calculated by helpers. Hence the texture op has the execute bit set, and
51 * the derivative op has the terminate bit set.
52 *
53 * Calculating the terminate bit occurs by forward dataflow analysis to
54 * determine which blocks require helper invocations. A block requires
55 * invocations in if any of its instructions use helper invocations, or if it
56 * depends on a block that requires invocation. With that analysis, the
57 * terminate bit is set on the last instruction using invocations within any
58 * block that does *not* require invocations out.
59 *
60 * Likewise, calculating the execute bit requires backward dataflow analysis
61 * with union as the join operation and the generating set being the union of
62 * sources of instructions writing executed values.
63 */
64
65 /* Does a block use helpers directly */
66 static bool
mir_block_uses_helpers(gl_shader_stage stage,midgard_block * block)67 mir_block_uses_helpers(gl_shader_stage stage, midgard_block *block)
68 {
69 mir_foreach_instr_in_block(block, ins) {
70 if (ins->type != TAG_TEXTURE_4)
71 continue;
72 if (mir_op_computes_derivatives(stage, ins->op))
73 return true;
74 }
75
76 return false;
77 }
78
79 static bool
mir_block_terminates_helpers(midgard_block * block)80 mir_block_terminates_helpers(midgard_block *block)
81 {
82 /* Can't terminate if there are no helpers */
83 if (!block->helpers_in)
84 return false;
85
86 /* Can't terminate if a successor needs helpers */
87 pan_foreach_successor((&block->base), succ) {
88 if (((midgard_block *)succ)->helpers_in)
89 return false;
90 }
91
92 /* Otherwise we terminate */
93 return true;
94 }
95
96 void
mir_analyze_helper_terminate(compiler_context * ctx)97 mir_analyze_helper_terminate(compiler_context *ctx)
98 {
99 /* Set blocks as directly requiring helpers, and if they do add them to
100 * the worklist to propagate to their predecessors */
101
102 struct set *worklist =
103 _mesa_set_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal);
104
105 struct set *visited =
106 _mesa_set_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal);
107
108 mir_foreach_block(ctx, _block) {
109 midgard_block *block = (midgard_block *)_block;
110 block->helpers_in |= mir_block_uses_helpers(ctx->stage, block);
111
112 if (block->helpers_in)
113 _mesa_set_add(worklist, _block);
114 }
115
116 /* Next, propagate back. Since there are a finite number of blocks, the
117 * worklist (a subset of all the blocks) is finite. Since a block can
118 * only be added to the worklist if it is not on the visited list and
119 * the visited list - also a subset of the blocks - grows every
120 * iteration, the algorithm must terminate. */
121
122 struct set_entry *cur;
123
124 while ((cur = _mesa_set_next_entry(worklist, NULL)) != NULL) {
125 /* Pop off a block requiring helpers */
126 pan_block *blk = (struct pan_block *)cur->key;
127 _mesa_set_remove(worklist, cur);
128
129 /* Its predecessors also require helpers */
130 pan_foreach_predecessor(blk, pred) {
131 if (!_mesa_set_search(visited, pred)) {
132 ((midgard_block *)pred)->helpers_in = true;
133 _mesa_set_add(worklist, pred);
134 }
135 }
136
137 _mesa_set_add(visited, blk);
138 }
139
140 _mesa_set_destroy(visited, NULL);
141 _mesa_set_destroy(worklist, NULL);
142
143 /* Finally, set helper_terminate on the last derivative-calculating
144 * instruction in a block that terminates helpers */
145 mir_foreach_block(ctx, _block) {
146 midgard_block *block = (midgard_block *)_block;
147
148 if (!mir_block_terminates_helpers(block))
149 continue;
150
151 mir_foreach_instr_in_block_rev(block, ins) {
152 if (ins->type != TAG_TEXTURE_4)
153 continue;
154 if (!mir_op_computes_derivatives(ctx->stage, ins->op))
155 continue;
156
157 ins->helper_terminate = true;
158 break;
159 }
160 }
161 }
162
163 static bool
mir_helper_block_update(BITSET_WORD * deps,pan_block * _block,unsigned temp_count)164 mir_helper_block_update(BITSET_WORD *deps, pan_block *_block,
165 unsigned temp_count)
166 {
167 bool progress = false;
168 midgard_block *block = (midgard_block *)_block;
169
170 mir_foreach_instr_in_block_rev(block, ins) {
171 /* Ensure we write to a helper dependency */
172 if (ins->dest >= temp_count || !BITSET_TEST(deps, ins->dest))
173 continue;
174
175 /* Then add all of our dependencies */
176 mir_foreach_src(ins, s) {
177 if (ins->src[s] >= temp_count)
178 continue;
179
180 /* Progress if the dependency set changes */
181 progress |= !BITSET_TEST(deps, ins->src[s]);
182 BITSET_SET(deps, ins->src[s]);
183 }
184 }
185
186 return progress;
187 }
188
189 void
mir_analyze_helper_requirements(compiler_context * ctx)190 mir_analyze_helper_requirements(compiler_context *ctx)
191 {
192 mir_compute_temp_count(ctx);
193 unsigned temp_count = ctx->temp_count;
194 BITSET_WORD *deps = calloc(sizeof(BITSET_WORD), BITSET_WORDS(temp_count));
195
196 /* Initialize with the sources of instructions consuming
197 * derivatives */
198
199 mir_foreach_instr_global(ctx, ins) {
200 if (ins->type != TAG_TEXTURE_4)
201 continue;
202 if (ins->dest >= ctx->temp_count)
203 continue;
204 if (!mir_op_computes_derivatives(ctx->stage, ins->op))
205 continue;
206
207 mir_foreach_src(ins, s) {
208 if (ins->src[s] < temp_count)
209 BITSET_SET(deps, ins->src[s]);
210 }
211 }
212
213 /* Propagate that up */
214
215 struct set *work_list =
216 _mesa_set_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal);
217
218 struct set *visited =
219 _mesa_set_create(NULL, _mesa_hash_pointer, _mesa_key_pointer_equal);
220
221 struct set_entry *cur =
222 _mesa_set_add(work_list, pan_exit_block(&ctx->blocks));
223
224 do {
225 pan_block *blk = (struct pan_block *)cur->key;
226 _mesa_set_remove(work_list, cur);
227
228 bool progress = mir_helper_block_update(deps, blk, temp_count);
229
230 if (progress || !_mesa_set_search(visited, blk)) {
231 pan_foreach_predecessor(blk, pred)
232 _mesa_set_add(work_list, pred);
233 }
234
235 _mesa_set_add(visited, blk);
236 } while ((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);
237
238 _mesa_set_destroy(visited, NULL);
239 _mesa_set_destroy(work_list, NULL);
240
241 /* Set the execute bits */
242
243 mir_foreach_instr_global(ctx, ins) {
244 if (ins->type != TAG_TEXTURE_4)
245 continue;
246 if (ins->dest >= ctx->temp_count)
247 continue;
248
249 ins->helper_execute = BITSET_TEST(deps, ins->dest);
250 }
251
252 free(deps);
253 }
254