1 /*
2 * Copyright © 2014 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_search.h"
25 #include <inttypes.h>
26 #include "util/half_float.h"
27 #include "nir_builder.h"
28 #include "nir_worklist.h"
29
30 /* This should be the same as nir_search_max_comm_ops in nir_algebraic.py. */
31 #define NIR_SEARCH_MAX_COMM_OPS 8
32
33 struct match_state {
34 bool inexact_match;
35 bool has_exact_alu;
36 uint8_t comm_op_direction;
37 unsigned variables_seen;
38
39 /* Used for running the automaton on newly-constructed instructions. */
40 struct util_dynarray *states;
41 const struct per_op_table *pass_op_table;
42 const nir_algebraic_table *table;
43
44 nir_alu_src variables[NIR_SEARCH_MAX_VARIABLES];
45 struct hash_table *range_ht;
46 };
47
48 static bool
49 match_expression(const nir_algebraic_table *table, const nir_search_expression *expr, nir_alu_instr *instr,
50 unsigned num_components, const uint8_t *swizzle,
51 struct match_state *state);
52 static bool
53 nir_algebraic_automaton(nir_instr *instr, struct util_dynarray *states,
54 const struct per_op_table *pass_op_table);
55
56 static const uint8_t identity_swizzle[NIR_MAX_VEC_COMPONENTS] = {
57 0,
58 1,
59 2,
60 3,
61 4,
62 5,
63 6,
64 7,
65 8,
66 9,
67 10,
68 11,
69 12,
70 13,
71 14,
72 15,
73 };
74
75 /**
76 * Check if a source produces a value of the given type.
77 *
78 * Used for satisfying 'a@type' constraints.
79 */
80 static bool
src_is_type(nir_src src,nir_alu_type type)81 src_is_type(nir_src src, nir_alu_type type)
82 {
83 assert(type != nir_type_invalid);
84
85 if (src.ssa->parent_instr->type == nir_instr_type_alu) {
86 nir_alu_instr *src_alu = nir_instr_as_alu(src.ssa->parent_instr);
87 nir_alu_type output_type = nir_op_infos[src_alu->op].output_type;
88
89 if (type == nir_type_bool) {
90 switch (src_alu->op) {
91 case nir_op_iand:
92 case nir_op_ior:
93 case nir_op_ixor:
94 return src_is_type(src_alu->src[0].src, nir_type_bool) &&
95 src_is_type(src_alu->src[1].src, nir_type_bool);
96 case nir_op_inot:
97 return src_is_type(src_alu->src[0].src, nir_type_bool);
98 default:
99 break;
100 }
101 }
102
103 return nir_alu_type_get_base_type(output_type) == type;
104 } else if (src.ssa->parent_instr->type == nir_instr_type_intrinsic) {
105 nir_intrinsic_instr *intr = nir_instr_as_intrinsic(src.ssa->parent_instr);
106
107 if (type == nir_type_bool) {
108 return intr->intrinsic == nir_intrinsic_load_front_face ||
109 intr->intrinsic == nir_intrinsic_load_helper_invocation;
110 }
111 }
112
113 /* don't know */
114 return false;
115 }
116
117 static bool
nir_op_matches_search_op(nir_op nop,uint16_t sop)118 nir_op_matches_search_op(nir_op nop, uint16_t sop)
119 {
120 if (sop <= nir_last_opcode)
121 return nop == sop;
122
123 #define MATCH_FCONV_CASE(op) \
124 case nir_search_op_##op: \
125 return nop == nir_op_##op##16 || \
126 nop == nir_op_##op##32 || \
127 nop == nir_op_##op##64;
128
129 #define MATCH_ICONV_CASE(op) \
130 case nir_search_op_##op: \
131 return nop == nir_op_##op##8 || \
132 nop == nir_op_##op##16 || \
133 nop == nir_op_##op##32 || \
134 nop == nir_op_##op##64;
135
136 switch (sop) {
137 MATCH_FCONV_CASE(i2f)
138 MATCH_FCONV_CASE(u2f)
139 MATCH_FCONV_CASE(f2f)
140 MATCH_ICONV_CASE(f2u)
141 MATCH_ICONV_CASE(f2i)
142 MATCH_ICONV_CASE(u2u)
143 MATCH_ICONV_CASE(i2i)
144 MATCH_FCONV_CASE(b2f)
145 MATCH_ICONV_CASE(b2i)
146 default:
147 unreachable("Invalid nir_search_op");
148 }
149
150 #undef MATCH_FCONV_CASE
151 #undef MATCH_ICONV_CASE
152 }
153
154 uint16_t
nir_search_op_for_nir_op(nir_op nop)155 nir_search_op_for_nir_op(nir_op nop)
156 {
157 #define MATCH_FCONV_CASE(op) \
158 case nir_op_##op##16: \
159 case nir_op_##op##32: \
160 case nir_op_##op##64: \
161 return nir_search_op_##op;
162
163 #define MATCH_ICONV_CASE(op) \
164 case nir_op_##op##8: \
165 case nir_op_##op##16: \
166 case nir_op_##op##32: \
167 case nir_op_##op##64: \
168 return nir_search_op_##op;
169
170 switch (nop) {
171 MATCH_FCONV_CASE(i2f)
172 MATCH_FCONV_CASE(u2f)
173 MATCH_FCONV_CASE(f2f)
174 MATCH_ICONV_CASE(f2u)
175 MATCH_ICONV_CASE(f2i)
176 MATCH_ICONV_CASE(u2u)
177 MATCH_ICONV_CASE(i2i)
178 MATCH_FCONV_CASE(b2f)
179 MATCH_ICONV_CASE(b2i)
180 default:
181 return nop;
182 }
183
184 #undef MATCH_FCONV_CASE
185 #undef MATCH_ICONV_CASE
186 }
187
188 static nir_op
nir_op_for_search_op(uint16_t sop,unsigned bit_size)189 nir_op_for_search_op(uint16_t sop, unsigned bit_size)
190 {
191 if (sop <= nir_last_opcode)
192 return sop;
193
194 #define RET_FCONV_CASE(op) \
195 case nir_search_op_##op: \
196 switch (bit_size) { \
197 case 16: \
198 return nir_op_##op##16; \
199 case 32: \
200 return nir_op_##op##32; \
201 case 64: \
202 return nir_op_##op##64; \
203 default: \
204 unreachable("Invalid bit size"); \
205 }
206
207 #define RET_ICONV_CASE(op) \
208 case nir_search_op_##op: \
209 switch (bit_size) { \
210 case 8: \
211 return nir_op_##op##8; \
212 case 16: \
213 return nir_op_##op##16; \
214 case 32: \
215 return nir_op_##op##32; \
216 case 64: \
217 return nir_op_##op##64; \
218 default: \
219 unreachable("Invalid bit size"); \
220 }
221
222 switch (sop) {
223 RET_FCONV_CASE(i2f)
224 RET_FCONV_CASE(u2f)
225 RET_FCONV_CASE(f2f)
226 RET_ICONV_CASE(f2u)
227 RET_ICONV_CASE(f2i)
228 RET_ICONV_CASE(u2u)
229 RET_ICONV_CASE(i2i)
230 RET_FCONV_CASE(b2f)
231 RET_ICONV_CASE(b2i)
232 default:
233 unreachable("Invalid nir_search_op");
234 }
235
236 #undef RET_FCONV_CASE
237 #undef RET_ICONV_CASE
238 }
239
240 static bool
match_value(const nir_algebraic_table * table,const nir_search_value * value,nir_alu_instr * instr,unsigned src,unsigned num_components,const uint8_t * swizzle,struct match_state * state)241 match_value(const nir_algebraic_table *table,
242 const nir_search_value *value, nir_alu_instr *instr, unsigned src,
243 unsigned num_components, const uint8_t *swizzle,
244 struct match_state *state)
245 {
246 uint8_t new_swizzle[NIR_MAX_VEC_COMPONENTS];
247
248 /* If the source is an explicitly sized source, then we need to reset
249 * both the number of components and the swizzle.
250 */
251 if (nir_op_infos[instr->op].input_sizes[src] != 0) {
252 num_components = nir_op_infos[instr->op].input_sizes[src];
253 swizzle = identity_swizzle;
254 }
255
256 for (unsigned i = 0; i < num_components; ++i)
257 new_swizzle[i] = instr->src[src].swizzle[swizzle[i]];
258
259 /* If the value has a specific bit size and it doesn't match, bail */
260 if (value->bit_size > 0 &&
261 nir_src_bit_size(instr->src[src].src) != value->bit_size)
262 return false;
263
264 switch (value->type) {
265 case nir_search_value_expression:
266 if (instr->src[src].src.ssa->parent_instr->type != nir_instr_type_alu)
267 return false;
268
269 return match_expression(table, nir_search_value_as_expression(value),
270 nir_instr_as_alu(instr->src[src].src.ssa->parent_instr),
271 num_components, new_swizzle, state);
272
273 case nir_search_value_variable: {
274 nir_search_variable *var = nir_search_value_as_variable(value);
275 assert(var->variable < NIR_SEARCH_MAX_VARIABLES);
276
277 if (state->variables_seen & (1 << var->variable)) {
278 if (state->variables[var->variable].src.ssa != instr->src[src].src.ssa)
279 return false;
280
281 for (unsigned i = 0; i < num_components; ++i) {
282 if (state->variables[var->variable].swizzle[i] != new_swizzle[i])
283 return false;
284 }
285
286 return true;
287 } else {
288 if (var->is_constant &&
289 instr->src[src].src.ssa->parent_instr->type != nir_instr_type_load_const)
290 return false;
291
292 if (var->cond_index != -1 && !table->variable_cond[var->cond_index](state->range_ht, instr,
293 src, num_components, new_swizzle))
294 return false;
295
296 if (var->type != nir_type_invalid &&
297 !src_is_type(instr->src[src].src, var->type))
298 return false;
299
300 state->variables_seen |= (1 << var->variable);
301 state->variables[var->variable].src = instr->src[src].src;
302
303 for (unsigned i = 0; i < NIR_MAX_VEC_COMPONENTS; ++i) {
304 if (i < num_components)
305 state->variables[var->variable].swizzle[i] = new_swizzle[i];
306 else
307 state->variables[var->variable].swizzle[i] = 0;
308 }
309
310 return true;
311 }
312 }
313
314 case nir_search_value_constant: {
315 nir_search_constant *const_val = nir_search_value_as_constant(value);
316
317 if (!nir_src_is_const(instr->src[src].src))
318 return false;
319
320 switch (const_val->type) {
321 case nir_type_float: {
322 nir_load_const_instr *const load =
323 nir_instr_as_load_const(instr->src[src].src.ssa->parent_instr);
324
325 /* There are 8-bit and 1-bit integer types, but there are no 8-bit or
326 * 1-bit float types. This prevents potential assertion failures in
327 * nir_src_comp_as_float.
328 */
329 if (load->def.bit_size < 16)
330 return false;
331
332 for (unsigned i = 0; i < num_components; ++i) {
333 double val = nir_src_comp_as_float(instr->src[src].src,
334 new_swizzle[i]);
335 if (val != const_val->data.d)
336 return false;
337 }
338 return true;
339 }
340
341 case nir_type_int:
342 case nir_type_uint:
343 case nir_type_bool: {
344 unsigned bit_size = nir_src_bit_size(instr->src[src].src);
345 uint64_t mask = u_uintN_max(bit_size);
346 for (unsigned i = 0; i < num_components; ++i) {
347 uint64_t val = nir_src_comp_as_uint(instr->src[src].src,
348 new_swizzle[i]);
349 if ((val & mask) != (const_val->data.u & mask))
350 return false;
351 }
352 return true;
353 }
354
355 default:
356 unreachable("Invalid alu source type");
357 }
358 }
359
360 default:
361 unreachable("Invalid search value type");
362 }
363 }
364
365 static bool
match_expression(const nir_algebraic_table * table,const nir_search_expression * expr,nir_alu_instr * instr,unsigned num_components,const uint8_t * swizzle,struct match_state * state)366 match_expression(const nir_algebraic_table *table, const nir_search_expression *expr, nir_alu_instr *instr,
367 unsigned num_components, const uint8_t *swizzle,
368 struct match_state *state)
369 {
370 if (expr->cond_index != -1 && !table->expression_cond[expr->cond_index](instr))
371 return false;
372
373 if (!nir_op_matches_search_op(instr->op, expr->opcode))
374 return false;
375
376 if (expr->value.bit_size > 0 &&
377 instr->def.bit_size != expr->value.bit_size)
378 return false;
379
380 state->inexact_match = expr->inexact || state->inexact_match;
381 state->has_exact_alu = (instr->exact && !expr->ignore_exact) || state->has_exact_alu;
382 if (state->inexact_match && state->has_exact_alu)
383 return false;
384
385 assert(nir_op_infos[instr->op].num_inputs > 0);
386
387 /* If we have an explicitly sized destination, we can only handle the
388 * identity swizzle. While dot(vec3(a, b, c).zxy) is a valid
389 * expression, we don't have the information right now to propagate that
390 * swizzle through. We can only properly propagate swizzles if the
391 * instruction is vectorized.
392 */
393 if (nir_op_infos[instr->op].output_size != 0) {
394 for (unsigned i = 0; i < num_components; i++) {
395 if (swizzle[i] != i)
396 return false;
397 }
398 }
399
400 /* If this is a commutative expression and it's one of the first few, look
401 * up its direction for the current search operation. We'll use that value
402 * to possibly flip the sources for the match.
403 */
404 unsigned comm_op_flip =
405 (expr->comm_expr_idx >= 0 &&
406 expr->comm_expr_idx < NIR_SEARCH_MAX_COMM_OPS)
407 ? ((state->comm_op_direction >> expr->comm_expr_idx) & 1)
408 : 0;
409
410 bool matched = true;
411 for (unsigned i = 0; i < nir_op_infos[instr->op].num_inputs; i++) {
412 /* 2src_commutative instructions that have 3 sources are only commutative
413 * in the first two sources. Source 2 is always source 2.
414 */
415 if (!match_value(table, &state->table->values[expr->srcs[i]].value, instr,
416 i < 2 ? i ^ comm_op_flip : i,
417 num_components, swizzle, state)) {
418 matched = false;
419 break;
420 }
421 }
422
423 return matched;
424 }
425
426 static unsigned
replace_bitsize(const nir_search_value * value,unsigned search_bitsize,struct match_state * state)427 replace_bitsize(const nir_search_value *value, unsigned search_bitsize,
428 struct match_state *state)
429 {
430 if (value->bit_size > 0)
431 return value->bit_size;
432 if (value->bit_size < 0)
433 return nir_src_bit_size(state->variables[-value->bit_size - 1].src);
434 return search_bitsize;
435 }
436
437 static nir_alu_src
construct_value(nir_builder * build,const nir_search_value * value,unsigned num_components,unsigned search_bitsize,struct match_state * state,nir_instr * instr)438 construct_value(nir_builder *build,
439 const nir_search_value *value,
440 unsigned num_components, unsigned search_bitsize,
441 struct match_state *state,
442 nir_instr *instr)
443 {
444 switch (value->type) {
445 case nir_search_value_expression: {
446 const nir_search_expression *expr = nir_search_value_as_expression(value);
447 unsigned dst_bit_size = replace_bitsize(value, search_bitsize, state);
448 nir_op op = nir_op_for_search_op(expr->opcode, dst_bit_size);
449
450 if (nir_op_infos[op].output_size != 0)
451 num_components = nir_op_infos[op].output_size;
452
453 nir_alu_instr *alu = nir_alu_instr_create(build->shader, op);
454 nir_def_init(&alu->instr, &alu->def, num_components,
455 dst_bit_size);
456
457 /* We have no way of knowing what values in a given search expression
458 * map to a particular replacement value. Therefore, if the
459 * expression we are replacing has any exact values, the entire
460 * replacement should be exact.
461 */
462 alu->exact = state->has_exact_alu || expr->exact;
463
464 for (unsigned i = 0; i < nir_op_infos[op].num_inputs; i++) {
465 /* If the source is an explicitly sized source, then we need to reset
466 * the number of components to match.
467 */
468 if (nir_op_infos[alu->op].input_sizes[i] != 0)
469 num_components = nir_op_infos[alu->op].input_sizes[i];
470
471 alu->src[i] = construct_value(build, &state->table->values[expr->srcs[i]].value,
472 num_components, search_bitsize,
473 state, instr);
474 }
475
476 nir_builder_instr_insert(build, &alu->instr);
477
478 assert(alu->def.index ==
479 util_dynarray_num_elements(state->states, uint16_t));
480 util_dynarray_append(state->states, uint16_t, 0);
481 nir_algebraic_automaton(&alu->instr, state->states, state->pass_op_table);
482
483 nir_alu_src val;
484 val.src = nir_src_for_ssa(&alu->def);
485 memcpy(val.swizzle, identity_swizzle, sizeof val.swizzle);
486
487 return val;
488 }
489
490 case nir_search_value_variable: {
491 const nir_search_variable *var = nir_search_value_as_variable(value);
492 assert(state->variables_seen & (1 << var->variable));
493
494 nir_alu_src val = { NIR_SRC_INIT };
495 nir_alu_src_copy(&val, &state->variables[var->variable]);
496 assert(!var->is_constant);
497
498 for (unsigned i = 0; i < NIR_MAX_VEC_COMPONENTS; i++)
499 val.swizzle[i] = state->variables[var->variable].swizzle[var->swizzle[i]];
500
501 return val;
502 }
503
504 case nir_search_value_constant: {
505 const nir_search_constant *c = nir_search_value_as_constant(value);
506 unsigned bit_size = replace_bitsize(value, search_bitsize, state);
507
508 nir_def *cval;
509 switch (c->type) {
510 case nir_type_float:
511 cval = nir_imm_floatN_t(build, c->data.d, bit_size);
512 break;
513
514 case nir_type_int:
515 case nir_type_uint:
516 cval = nir_imm_intN_t(build, c->data.i, bit_size);
517 break;
518
519 case nir_type_bool:
520 cval = nir_imm_boolN_t(build, c->data.u, bit_size);
521 break;
522
523 default:
524 unreachable("Invalid alu source type");
525 }
526
527 assert(cval->index ==
528 util_dynarray_num_elements(state->states, uint16_t));
529 util_dynarray_append(state->states, uint16_t, 0);
530 nir_algebraic_automaton(cval->parent_instr, state->states,
531 state->pass_op_table);
532
533 nir_alu_src val;
534 val.src = nir_src_for_ssa(cval);
535 memset(val.swizzle, 0, sizeof val.swizzle);
536
537 return val;
538 }
539
540 default:
541 unreachable("Invalid search value type");
542 }
543 }
544
545 UNUSED static void
dump_value(const nir_algebraic_table * table,const nir_search_value * val)546 dump_value(const nir_algebraic_table *table, const nir_search_value *val)
547 {
548 switch (val->type) {
549 case nir_search_value_constant: {
550 const nir_search_constant *sconst = nir_search_value_as_constant(val);
551 switch (sconst->type) {
552 case nir_type_float:
553 fprintf(stderr, "%f", sconst->data.d);
554 break;
555 case nir_type_int:
556 fprintf(stderr, "%" PRId64, sconst->data.i);
557 break;
558 case nir_type_uint:
559 fprintf(stderr, "0x%" PRIx64, sconst->data.u);
560 break;
561 case nir_type_bool:
562 fprintf(stderr, "%s", sconst->data.u != 0 ? "True" : "False");
563 break;
564 default:
565 unreachable("bad const type");
566 }
567 break;
568 }
569
570 case nir_search_value_variable: {
571 const nir_search_variable *var = nir_search_value_as_variable(val);
572 if (var->is_constant)
573 fprintf(stderr, "#");
574 fprintf(stderr, "%c", var->variable + 'a');
575 break;
576 }
577
578 case nir_search_value_expression: {
579 const nir_search_expression *expr = nir_search_value_as_expression(val);
580 fprintf(stderr, "(");
581 if (expr->inexact)
582 fprintf(stderr, "~");
583 switch (expr->opcode) {
584 #define CASE(n) \
585 case nir_search_op_##n: \
586 fprintf(stderr, #n); \
587 break;
588 CASE(b2f)
589 CASE(b2i)
590 CASE(i2i)
591 CASE(f2i)
592 CASE(i2f)
593 #undef CASE
594 default:
595 fprintf(stderr, "%s", nir_op_infos[expr->opcode].name);
596 }
597
598 unsigned num_srcs = 1;
599 if (expr->opcode <= nir_last_opcode)
600 num_srcs = nir_op_infos[expr->opcode].num_inputs;
601
602 for (unsigned i = 0; i < num_srcs; i++) {
603 fprintf(stderr, " ");
604 dump_value(table, &table->values[expr->srcs[i]].value);
605 }
606
607 fprintf(stderr, ")");
608 break;
609 }
610 }
611
612 if (val->bit_size > 0)
613 fprintf(stderr, "@%d", val->bit_size);
614 }
615
616 static void
add_uses_to_worklist(nir_instr * instr,nir_instr_worklist * worklist,struct util_dynarray * states,const struct per_op_table * pass_op_table)617 add_uses_to_worklist(nir_instr *instr,
618 nir_instr_worklist *worklist,
619 struct util_dynarray *states,
620 const struct per_op_table *pass_op_table)
621 {
622 nir_def *def = nir_instr_def(instr);
623
624 nir_foreach_use_safe(use_src, def) {
625 if (nir_algebraic_automaton(nir_src_parent_instr(use_src), states, pass_op_table))
626 nir_instr_worklist_push_tail(worklist, nir_src_parent_instr(use_src));
627 }
628 }
629
630 static void
nir_algebraic_update_automaton(nir_instr * new_instr,nir_instr_worklist * algebraic_worklist,struct util_dynarray * states,const struct per_op_table * pass_op_table)631 nir_algebraic_update_automaton(nir_instr *new_instr,
632 nir_instr_worklist *algebraic_worklist,
633 struct util_dynarray *states,
634 const struct per_op_table *pass_op_table)
635 {
636
637 nir_instr_worklist *automaton_worklist = nir_instr_worklist_create();
638
639 /* Walk through the tree of uses of our new instruction's SSA value,
640 * recursively updating the automaton state until it stabilizes.
641 */
642 add_uses_to_worklist(new_instr, automaton_worklist, states, pass_op_table);
643
644 nir_instr *instr;
645 while ((instr = nir_instr_worklist_pop_head(automaton_worklist))) {
646 nir_instr_worklist_push_tail(algebraic_worklist, instr);
647 add_uses_to_worklist(instr, automaton_worklist, states, pass_op_table);
648 }
649
650 nir_instr_worklist_destroy(automaton_worklist);
651 }
652
653 static nir_def *
nir_replace_instr(nir_builder * build,nir_alu_instr * instr,struct hash_table * range_ht,struct util_dynarray * states,const nir_algebraic_table * table,const nir_search_expression * search,const nir_search_value * replace,nir_instr_worklist * algebraic_worklist,struct exec_list * dead_instrs)654 nir_replace_instr(nir_builder *build, nir_alu_instr *instr,
655 struct hash_table *range_ht,
656 struct util_dynarray *states,
657 const nir_algebraic_table *table,
658 const nir_search_expression *search,
659 const nir_search_value *replace,
660 nir_instr_worklist *algebraic_worklist,
661 struct exec_list *dead_instrs)
662 {
663 uint8_t swizzle[NIR_MAX_VEC_COMPONENTS] = { 0 };
664
665 for (unsigned i = 0; i < instr->def.num_components; ++i)
666 swizzle[i] = i;
667
668 struct match_state state;
669 state.inexact_match = false;
670 state.has_exact_alu = false;
671 state.range_ht = range_ht;
672 state.pass_op_table = table->pass_op_table;
673 state.table = table;
674
675 STATIC_ASSERT(sizeof(state.comm_op_direction) * 8 >= NIR_SEARCH_MAX_COMM_OPS);
676
677 unsigned comm_expr_combinations =
678 1 << MIN2(search->comm_exprs, NIR_SEARCH_MAX_COMM_OPS);
679
680 bool found = false;
681 for (unsigned comb = 0; comb < comm_expr_combinations; comb++) {
682 /* The bitfield of directions is just the current iteration. Hooray for
683 * binary.
684 */
685 state.comm_op_direction = comb;
686 state.variables_seen = 0;
687
688 if (match_expression(table, search, instr,
689 instr->def.num_components,
690 swizzle, &state)) {
691 found = true;
692 break;
693 }
694 }
695 if (!found)
696 return NULL;
697
698 #if 0
699 fprintf(stderr, "matched: ");
700 dump_value(&search->value);
701 fprintf(stderr, " -> ");
702 dump_value(replace);
703 fprintf(stderr, " ssa_%d\n", instr->def.index);
704 #endif
705
706 /* If the instruction at the root of the expression tree being replaced is
707 * a unary operation, insert the replacement instructions at the location
708 * of the source of the unary operation. Otherwise, insert the replacement
709 * instructions at the location of the expression tree root.
710 *
711 * For the unary operation case, this is done to prevent some spurious code
712 * motion that can dramatically extend live ranges. Imagine an expression
713 * like -(A+B) where the addtion and the negation are separated by flow
714 * control and thousands of instructions. If this expression is replaced
715 * with -A+-B, inserting the new instructions at the site of the negation
716 * could extend the live range of A and B dramtically. This could increase
717 * register pressure and cause spilling.
718 *
719 * It may well be that moving instructions around is a good thing, but
720 * keeping algebraic optimizations and code motion optimizations separate
721 * seems safest.
722 */
723 nir_alu_instr *const src_instr = nir_src_as_alu_instr(instr->src[0].src);
724 if (src_instr != NULL &&
725 (instr->op == nir_op_fneg || instr->op == nir_op_fabs ||
726 instr->op == nir_op_ineg || instr->op == nir_op_iabs ||
727 instr->op == nir_op_inot)) {
728 /* Insert new instructions *after*. Otherwise a hypothetical
729 * replacement fneg(X) -> fabs(X) would insert the fabs() instruction
730 * before X! This can also occur for things like fneg(X.wzyx) -> X.wzyx
731 * in vector mode. A move instruction to handle the swizzle will get
732 * inserted before X.
733 *
734 * This manifested in a single OpenGL ES 2.0 CTS vertex shader test on
735 * older Intel GPU that use vector-mode vertex processing.
736 */
737 build->cursor = nir_after_instr(&src_instr->instr);
738 } else {
739 build->cursor = nir_before_instr(&instr->instr);
740 }
741
742 state.states = states;
743
744 nir_alu_src val = construct_value(build, replace,
745 instr->def.num_components,
746 instr->def.bit_size,
747 &state, &instr->instr);
748
749 /* Note that NIR builder will elide the MOV if it's a no-op, which may
750 * allow more work to be done in a single pass through algebraic.
751 */
752 nir_def *ssa_val =
753 nir_mov_alu(build, val, instr->def.num_components);
754 if (ssa_val->index == util_dynarray_num_elements(states, uint16_t)) {
755 util_dynarray_append(states, uint16_t, 0);
756 nir_algebraic_automaton(ssa_val->parent_instr, states, table->pass_op_table);
757 }
758
759 /* Rewrite the uses of the old SSA value to the new one, and recurse
760 * through the uses updating the automaton's state.
761 */
762 nir_def_rewrite_uses(&instr->def, ssa_val);
763 nir_algebraic_update_automaton(ssa_val->parent_instr, algebraic_worklist,
764 states, table->pass_op_table);
765
766 /* Nothing uses the instr any more, so drop it out of the program. Note
767 * that the instr may be in the worklist still, so we can't free it
768 * directly.
769 */
770 assert(instr->instr.pass_flags == 0);
771 instr->instr.pass_flags = 1;
772 nir_instr_remove(&instr->instr);
773 exec_list_push_tail(dead_instrs, &instr->instr.node);
774
775 return ssa_val;
776 }
777
778 static bool
nir_algebraic_automaton(nir_instr * instr,struct util_dynarray * states,const struct per_op_table * pass_op_table)779 nir_algebraic_automaton(nir_instr *instr, struct util_dynarray *states,
780 const struct per_op_table *pass_op_table)
781 {
782 switch (instr->type) {
783 case nir_instr_type_alu: {
784 nir_alu_instr *alu = nir_instr_as_alu(instr);
785 nir_op op = alu->op;
786 uint16_t search_op = nir_search_op_for_nir_op(op);
787 const struct per_op_table *tbl = &pass_op_table[search_op];
788 if (tbl->num_filtered_states == 0)
789 return false;
790
791 /* Calculate the index into the transition table. Note the index
792 * calculated must match the iteration order of Python's
793 * itertools.product(), which was used to emit the transition
794 * table.
795 */
796 unsigned index = 0;
797 for (unsigned i = 0; i < nir_op_infos[op].num_inputs; i++) {
798 index *= tbl->num_filtered_states;
799 if (tbl->filter)
800 index += tbl->filter[*util_dynarray_element(states, uint16_t,
801 alu->src[i].src.ssa->index)];
802 }
803
804 uint16_t *state = util_dynarray_element(states, uint16_t,
805 alu->def.index);
806 if (*state != tbl->table[index]) {
807 *state = tbl->table[index];
808 return true;
809 }
810 return false;
811 }
812
813 case nir_instr_type_load_const: {
814 nir_load_const_instr *load_const = nir_instr_as_load_const(instr);
815 uint16_t *state = util_dynarray_element(states, uint16_t,
816 load_const->def.index);
817 if (*state != CONST_STATE) {
818 *state = CONST_STATE;
819 return true;
820 }
821 return false;
822 }
823
824 default:
825 return false;
826 }
827 }
828
829 static bool
nir_algebraic_instr(nir_builder * build,nir_instr * instr,struct hash_table * range_ht,const bool * condition_flags,const nir_algebraic_table * table,struct util_dynarray * states,nir_instr_worklist * worklist,struct exec_list * dead_instrs)830 nir_algebraic_instr(nir_builder *build, nir_instr *instr,
831 struct hash_table *range_ht,
832 const bool *condition_flags,
833 const nir_algebraic_table *table,
834 struct util_dynarray *states,
835 nir_instr_worklist *worklist,
836 struct exec_list *dead_instrs)
837 {
838
839 if (instr->type != nir_instr_type_alu)
840 return false;
841
842 nir_alu_instr *alu = nir_instr_as_alu(instr);
843
844 unsigned bit_size = alu->def.bit_size;
845 const unsigned execution_mode =
846 build->shader->info.float_controls_execution_mode;
847 const bool ignore_inexact =
848 nir_is_float_control_signed_zero_inf_nan_preserve(execution_mode, bit_size) ||
849 nir_is_denorm_flush_to_zero(execution_mode, bit_size);
850
851 int xform_idx = *util_dynarray_element(states, uint16_t,
852 alu->def.index);
853 for (const struct transform *xform = &table->transforms[table->transform_offsets[xform_idx]];
854 xform->condition_offset != ~0;
855 xform++) {
856 if (condition_flags[xform->condition_offset] &&
857 !(table->values[xform->search].expression.inexact && ignore_inexact) &&
858 nir_replace_instr(build, alu, range_ht, states, table,
859 &table->values[xform->search].expression,
860 &table->values[xform->replace].value, worklist, dead_instrs)) {
861 _mesa_hash_table_clear(range_ht, NULL);
862 return true;
863 }
864 }
865
866 return false;
867 }
868
869 bool
nir_algebraic_impl(nir_function_impl * impl,const bool * condition_flags,const nir_algebraic_table * table)870 nir_algebraic_impl(nir_function_impl *impl,
871 const bool *condition_flags,
872 const nir_algebraic_table *table)
873 {
874 bool progress = false;
875
876 nir_builder build = nir_builder_create(impl);
877
878 /* Note: it's important here that we're allocating a zeroed array, since
879 * state 0 is the default state, which means we don't have to visit
880 * anything other than constants and ALU instructions.
881 */
882 struct util_dynarray states = { 0 };
883 if (!util_dynarray_resize(&states, uint16_t, impl->ssa_alloc)) {
884 nir_metadata_preserve(impl, nir_metadata_all);
885 return false;
886 }
887 memset(states.data, 0, states.size);
888
889 struct hash_table *range_ht = _mesa_pointer_hash_table_create(NULL);
890
891 nir_instr_worklist *worklist = nir_instr_worklist_create();
892
893 /* Walk top-to-bottom setting up the automaton state. */
894 nir_foreach_block(block, impl) {
895 nir_foreach_instr(instr, block) {
896 nir_algebraic_automaton(instr, &states, table->pass_op_table);
897 }
898 }
899
900 /* Put our instrs in the worklist such that we're popping the last instr
901 * first. This will encourage us to match the biggest source patterns when
902 * possible.
903 */
904 nir_foreach_block_reverse(block, impl) {
905 nir_foreach_instr_reverse(instr, block) {
906 instr->pass_flags = 0;
907 if (instr->type == nir_instr_type_alu)
908 nir_instr_worklist_push_tail(worklist, instr);
909 }
910 }
911
912 struct exec_list dead_instrs;
913 exec_list_make_empty(&dead_instrs);
914
915 nir_instr *instr;
916 while ((instr = nir_instr_worklist_pop_head(worklist))) {
917 /* The worklist can have an instr pushed to it multiple times if it was
918 * the src of multiple instrs that also got optimized, so make sure that
919 * we don't try to re-optimize an instr we already handled.
920 */
921 if (instr->pass_flags)
922 continue;
923
924 progress |= nir_algebraic_instr(&build, instr,
925 range_ht, condition_flags,
926 table, &states, worklist, &dead_instrs);
927 }
928
929 nir_instr_free_list(&dead_instrs);
930
931 nir_instr_worklist_destroy(worklist);
932 ralloc_free(range_ht);
933 util_dynarray_fini(&states);
934
935 if (progress) {
936 nir_metadata_preserve(impl, nir_metadata_block_index |
937 nir_metadata_dominance);
938 } else {
939 nir_metadata_preserve(impl, nir_metadata_all);
940 }
941
942 return progress;
943 }
944