nir: Handle all array stride cases in nir_deref_instr_array_stride
[mesa.git] / src / compiler / nir / nir_deref.c
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_deref.h"
27 #include "util/hash_table.h"
28
29 static bool
30 is_trivial_deref_cast(nir_deref_instr *cast)
31 {
32 nir_deref_instr *parent = nir_src_as_deref(cast->parent);
33 if (!parent)
34 return false;
35
36 return cast->mode == parent->mode &&
37 cast->type == parent->type &&
38 cast->dest.ssa.num_components == parent->dest.ssa.num_components &&
39 cast->dest.ssa.bit_size == parent->dest.ssa.bit_size;
40 }
41
42 void
43 nir_deref_path_init(nir_deref_path *path,
44 nir_deref_instr *deref, void *mem_ctx)
45 {
46 assert(deref != NULL);
47
48 /* The length of the short path is at most ARRAY_SIZE - 1 because we need
49 * room for the NULL terminator.
50 */
51 static const int max_short_path_len = ARRAY_SIZE(path->_short_path) - 1;
52
53 int count = 0;
54
55 nir_deref_instr **tail = &path->_short_path[max_short_path_len];
56 nir_deref_instr **head = tail;
57
58 *tail = NULL;
59 for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
60 if (d->deref_type == nir_deref_type_cast && is_trivial_deref_cast(d))
61 continue;
62 count++;
63 if (count <= max_short_path_len)
64 *(--head) = d;
65 }
66
67 if (count <= max_short_path_len) {
68 /* If we're under max_short_path_len, just use the short path. */
69 path->path = head;
70 goto done;
71 }
72
73 #ifndef NDEBUG
74 /* Just in case someone uses short_path by accident */
75 for (unsigned i = 0; i < ARRAY_SIZE(path->_short_path); i++)
76 path->_short_path[i] = (void *)(uintptr_t)0xdeadbeef;
77 #endif
78
79 path->path = ralloc_array(mem_ctx, nir_deref_instr *, count + 1);
80 head = tail = path->path + count;
81 *tail = NULL;
82 for (nir_deref_instr *d = deref; d; d = nir_deref_instr_parent(d)) {
83 if (d->deref_type == nir_deref_type_cast && is_trivial_deref_cast(d))
84 continue;
85 *(--head) = d;
86 }
87
88 done:
89 assert(head == path->path);
90 assert(tail == head + count);
91 assert(*tail == NULL);
92 }
93
94 void
95 nir_deref_path_finish(nir_deref_path *path)
96 {
97 if (path->path < &path->_short_path[0] ||
98 path->path > &path->_short_path[ARRAY_SIZE(path->_short_path) - 1])
99 ralloc_free(path->path);
100 }
101
102 /**
103 * Recursively removes unused deref instructions
104 */
105 bool
106 nir_deref_instr_remove_if_unused(nir_deref_instr *instr)
107 {
108 bool progress = false;
109
110 for (nir_deref_instr *d = instr; d; d = nir_deref_instr_parent(d)) {
111 /* If anyone is using this deref, leave it alone */
112 assert(d->dest.is_ssa);
113 if (!list_is_empty(&d->dest.ssa.uses))
114 break;
115
116 nir_instr_remove(&d->instr);
117 progress = true;
118 }
119
120 return progress;
121 }
122
123 bool
124 nir_deref_instr_has_indirect(nir_deref_instr *instr)
125 {
126 while (instr->deref_type != nir_deref_type_var) {
127 /* Consider casts to be indirects */
128 if (instr->deref_type == nir_deref_type_cast)
129 return true;
130
131 if ((instr->deref_type == nir_deref_type_array ||
132 instr->deref_type == nir_deref_type_ptr_as_array) &&
133 !nir_src_is_const(instr->arr.index))
134 return true;
135
136 instr = nir_deref_instr_parent(instr);
137 }
138
139 return false;
140 }
141
142 bool
143 nir_deref_instr_is_known_out_of_bounds(nir_deref_instr *instr)
144 {
145 for (; instr; instr = nir_deref_instr_parent(instr)) {
146 if (instr->deref_type == nir_deref_type_array &&
147 nir_src_is_const(instr->arr.index) &&
148 nir_src_as_uint(instr->arr.index) >=
149 glsl_get_length(nir_deref_instr_parent(instr)->type))
150 return true;
151 }
152
153 return false;
154 }
155
156 bool
157 nir_deref_instr_has_complex_use(nir_deref_instr *deref)
158 {
159 nir_foreach_use(use_src, &deref->dest.ssa) {
160 nir_instr *use_instr = use_src->parent_instr;
161
162 switch (use_instr->type) {
163 case nir_instr_type_deref: {
164 nir_deref_instr *use_deref = nir_instr_as_deref(use_instr);
165
166 /* A var deref has no sources */
167 assert(use_deref->deref_type != nir_deref_type_var);
168
169 /* If a deref shows up in an array index or something like that, it's
170 * a complex use.
171 */
172 if (use_src != &use_deref->parent)
173 return true;
174
175 /* Anything that isn't a basic struct or array deref is considered to
176 * be a "complex" use. In particular, we don't allow ptr_as_array
177 * because we assume that opt_deref will turn any non-complex
178 * ptr_as_array derefs into regular array derefs eventually so passes
179 * which only want to handle simple derefs will pick them up in a
180 * later pass.
181 */
182 if (use_deref->deref_type != nir_deref_type_struct &&
183 use_deref->deref_type != nir_deref_type_array_wildcard &&
184 use_deref->deref_type != nir_deref_type_array)
185 return true;
186
187 if (nir_deref_instr_has_complex_use(use_deref))
188 return true;
189
190 continue;
191 }
192
193 case nir_instr_type_intrinsic: {
194 nir_intrinsic_instr *use_intrin = nir_instr_as_intrinsic(use_instr);
195 switch (use_intrin->intrinsic) {
196 case nir_intrinsic_load_deref:
197 assert(use_src == &use_intrin->src[0]);
198 continue;
199
200 case nir_intrinsic_copy_deref:
201 assert(use_src == &use_intrin->src[0] ||
202 use_src == &use_intrin->src[1]);
203 continue;
204
205 case nir_intrinsic_store_deref:
206 /* A use in src[1] of a store means we're taking that pointer and
207 * writing it to a variable. Because we have no idea who will
208 * read that variable and what they will do with the pointer, it's
209 * considered a "complex" use. A use in src[0], on the other
210 * hand, is a simple use because we're just going to dereference
211 * it and write a value there.
212 */
213 if (use_src == &use_intrin->src[0])
214 continue;
215 return true;
216
217 default:
218 return true;
219 }
220 unreachable("Switch default failed");
221 }
222
223 default:
224 return true;
225 }
226 }
227
228 nir_foreach_if_use(use, &deref->dest.ssa)
229 return true;
230
231 return false;
232 }
233
234 static unsigned
235 type_scalar_size_bytes(const struct glsl_type *type)
236 {
237 assert(glsl_type_is_vector_or_scalar(type) ||
238 glsl_type_is_matrix(type));
239 return glsl_type_is_boolean(type) ? 4 : glsl_get_bit_size(type) / 8;
240 }
241
242 unsigned
243 nir_deref_instr_array_stride(nir_deref_instr *deref)
244 {
245 switch (deref->deref_type) {
246 case nir_deref_type_array:
247 case nir_deref_type_array_wildcard: {
248 const struct glsl_type *arr_type = nir_deref_instr_parent(deref)->type;
249 unsigned stride = glsl_get_explicit_stride(arr_type);
250
251 if ((glsl_type_is_matrix(arr_type) &&
252 glsl_matrix_type_is_row_major(arr_type)) ||
253 (glsl_type_is_vector(arr_type) && stride == 0))
254 stride = type_scalar_size_bytes(arr_type);
255
256 return stride;
257 }
258 case nir_deref_type_ptr_as_array:
259 return nir_deref_instr_array_stride(nir_deref_instr_parent(deref));
260 case nir_deref_type_cast:
261 return deref->cast.ptr_stride;
262 default:
263 return 0;
264 }
265 }
266
267 static unsigned
268 type_get_array_stride(const struct glsl_type *elem_type,
269 glsl_type_size_align_func size_align)
270 {
271 unsigned elem_size, elem_align;
272 size_align(elem_type, &elem_size, &elem_align);
273 return ALIGN_POT(elem_size, elem_align);
274 }
275
276 static unsigned
277 struct_type_get_field_offset(const struct glsl_type *struct_type,
278 glsl_type_size_align_func size_align,
279 unsigned field_idx)
280 {
281 assert(glsl_type_is_struct_or_ifc(struct_type));
282 unsigned offset = 0;
283 for (unsigned i = 0; i <= field_idx; i++) {
284 unsigned elem_size, elem_align;
285 size_align(glsl_get_struct_field(struct_type, i), &elem_size, &elem_align);
286 offset = ALIGN_POT(offset, elem_align);
287 if (i < field_idx)
288 offset += elem_size;
289 }
290 return offset;
291 }
292
293 unsigned
294 nir_deref_instr_get_const_offset(nir_deref_instr *deref,
295 glsl_type_size_align_func size_align)
296 {
297 nir_deref_path path;
298 nir_deref_path_init(&path, deref, NULL);
299
300 unsigned offset = 0;
301 for (nir_deref_instr **p = &path.path[1]; *p; p++) {
302 switch ((*p)->deref_type) {
303 case nir_deref_type_array:
304 offset += nir_src_as_uint((*p)->arr.index) *
305 type_get_array_stride((*p)->type, size_align);
306 break;
307 case nir_deref_type_struct: {
308 /* p starts at path[1], so this is safe */
309 nir_deref_instr *parent = *(p - 1);
310 offset += struct_type_get_field_offset(parent->type, size_align,
311 (*p)->strct.index);
312 break;
313 }
314 case nir_deref_type_cast:
315 /* A cast doesn't contribute to the offset */
316 break;
317 default:
318 unreachable("Unsupported deref type");
319 }
320 }
321
322 nir_deref_path_finish(&path);
323
324 return offset;
325 }
326
327 nir_ssa_def *
328 nir_build_deref_offset(nir_builder *b, nir_deref_instr *deref,
329 glsl_type_size_align_func size_align)
330 {
331 nir_deref_path path;
332 nir_deref_path_init(&path, deref, NULL);
333
334 nir_ssa_def *offset = nir_imm_intN_t(b, 0, deref->dest.ssa.bit_size);
335 for (nir_deref_instr **p = &path.path[1]; *p; p++) {
336 switch ((*p)->deref_type) {
337 case nir_deref_type_array: {
338 nir_ssa_def *index = nir_ssa_for_src(b, (*p)->arr.index, 1);
339 int stride = type_get_array_stride((*p)->type, size_align);
340 offset = nir_iadd(b, offset, nir_amul_imm(b, index, stride));
341 break;
342 }
343 case nir_deref_type_struct: {
344 /* p starts at path[1], so this is safe */
345 nir_deref_instr *parent = *(p - 1);
346 unsigned field_offset =
347 struct_type_get_field_offset(parent->type, size_align,
348 (*p)->strct.index);
349 offset = nir_iadd_imm(b, offset, field_offset);
350 break;
351 }
352 case nir_deref_type_cast:
353 /* A cast doesn't contribute to the offset */
354 break;
355 default:
356 unreachable("Unsupported deref type");
357 }
358 }
359
360 nir_deref_path_finish(&path);
361
362 return offset;
363 }
364
365 bool
366 nir_remove_dead_derefs_impl(nir_function_impl *impl)
367 {
368 bool progress = false;
369
370 nir_foreach_block(block, impl) {
371 nir_foreach_instr_safe(instr, block) {
372 if (instr->type == nir_instr_type_deref &&
373 nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
374 progress = true;
375 }
376 }
377
378 if (progress)
379 nir_metadata_preserve(impl, nir_metadata_block_index |
380 nir_metadata_dominance);
381
382 return progress;
383 }
384
385 bool
386 nir_remove_dead_derefs(nir_shader *shader)
387 {
388 bool progress = false;
389 nir_foreach_function(function, shader) {
390 if (function->impl && nir_remove_dead_derefs_impl(function->impl))
391 progress = true;
392 }
393
394 return progress;
395 }
396
397 void
398 nir_fixup_deref_modes(nir_shader *shader)
399 {
400 nir_foreach_function(function, shader) {
401 if (!function->impl)
402 continue;
403
404 nir_foreach_block(block, function->impl) {
405 nir_foreach_instr(instr, block) {
406 if (instr->type != nir_instr_type_deref)
407 continue;
408
409 nir_deref_instr *deref = nir_instr_as_deref(instr);
410 if (deref->deref_type == nir_deref_type_cast)
411 continue;
412
413 nir_variable_mode parent_mode;
414 if (deref->deref_type == nir_deref_type_var) {
415 parent_mode = deref->var->data.mode;
416 } else {
417 assert(deref->parent.is_ssa);
418 nir_deref_instr *parent =
419 nir_instr_as_deref(deref->parent.ssa->parent_instr);
420 parent_mode = parent->mode;
421 }
422
423 deref->mode = parent_mode;
424 }
425 }
426 }
427 }
428
429 static bool
430 modes_may_alias(nir_variable_mode a, nir_variable_mode b)
431 {
432 /* Generic pointers can alias with SSBOs */
433 if ((a == nir_var_mem_ssbo || a == nir_var_mem_global) &&
434 (b == nir_var_mem_ssbo || b == nir_var_mem_global))
435 return true;
436
437 /* In the general case, pointers can only alias if they have the same mode.
438 *
439 * NOTE: In future, with things like OpenCL generic pointers, this may not
440 * be true and will have to be re-evaluated. However, with graphics only,
441 * it should be safe.
442 */
443 return a == b;
444 }
445
446 static bool
447 deref_path_contains_coherent_decoration(nir_deref_path *path)
448 {
449 assert(path->path[0]->deref_type == nir_deref_type_var);
450
451 if (path->path[0]->var->data.access & ACCESS_COHERENT)
452 return true;
453
454 for (nir_deref_instr **p = &path->path[1]; *p; p++) {
455 if ((*p)->deref_type != nir_deref_type_struct)
456 continue;
457
458 const struct glsl_type *struct_type = (*(p - 1))->type;
459 const struct glsl_struct_field *field =
460 glsl_get_struct_field_data(struct_type, (*p)->strct.index);
461 if (field->memory_coherent)
462 return true;
463 }
464
465 return false;
466 }
467
468 nir_deref_compare_result
469 nir_compare_deref_paths(nir_deref_path *a_path,
470 nir_deref_path *b_path)
471 {
472 if (!modes_may_alias(b_path->path[0]->mode, a_path->path[0]->mode))
473 return nir_derefs_do_not_alias;
474
475 if (a_path->path[0]->deref_type != b_path->path[0]->deref_type)
476 return nir_derefs_may_alias_bit;
477
478 if (a_path->path[0]->deref_type == nir_deref_type_var) {
479 if (a_path->path[0]->var != b_path->path[0]->var) {
480 /* Shader and function temporaries aren't backed by memory so two
481 * distinct variables never alias.
482 */
483 static const nir_variable_mode temp_var_modes =
484 nir_var_shader_temp | nir_var_function_temp;
485 if ((a_path->path[0]->mode & temp_var_modes) ||
486 (b_path->path[0]->mode & temp_var_modes))
487 return nir_derefs_do_not_alias;
488
489 /* If they are both declared coherent or have coherent somewhere in
490 * their path (due to a member of an interface being declared
491 * coherent), we have to assume we that we could have any kind of
492 * aliasing. Otherwise, they could still alias but the client didn't
493 * tell us and that's their fault.
494 */
495 if (deref_path_contains_coherent_decoration(a_path) &&
496 deref_path_contains_coherent_decoration(b_path))
497 return nir_derefs_may_alias_bit;
498
499 /* If we can chase the deref all the way back to the variable and
500 * they're not the same variable and at least one is not declared
501 * coherent, we know they can't possibly alias.
502 */
503 return nir_derefs_do_not_alias;
504 }
505 } else {
506 assert(a_path->path[0]->deref_type == nir_deref_type_cast);
507 /* If they're not exactly the same cast, it's hard to compare them so we
508 * just assume they alias. Comparing casts is tricky as there are lots
509 * of things such as mode, type, etc. to make sure work out; for now, we
510 * just assume nit_opt_deref will combine them and compare the deref
511 * instructions.
512 *
513 * TODO: At some point in the future, we could be clever and understand
514 * that a float[] and int[] have the same layout and aliasing structure
515 * but double[] and vec3[] do not and we could potentially be a bit
516 * smarter here.
517 */
518 if (a_path->path[0] != b_path->path[0])
519 return nir_derefs_may_alias_bit;
520 }
521
522 /* Start off assuming they fully compare. We ignore equality for now. In
523 * the end, we'll determine that by containment.
524 */
525 nir_deref_compare_result result = nir_derefs_may_alias_bit |
526 nir_derefs_a_contains_b_bit |
527 nir_derefs_b_contains_a_bit;
528
529 nir_deref_instr **a_p = &a_path->path[1];
530 nir_deref_instr **b_p = &b_path->path[1];
531 while (*a_p != NULL && *a_p == *b_p) {
532 a_p++;
533 b_p++;
534 }
535
536 /* We're at either the tail or the divergence point between the two deref
537 * paths. Look to see if either contains cast or a ptr_as_array deref. If
538 * it does we don't know how to safely make any inferences. Hopefully,
539 * nir_opt_deref will clean most of these up and we can start inferring
540 * things again.
541 *
542 * In theory, we could do a bit better. For instance, we could detect the
543 * case where we have exactly one ptr_as_array deref in the chain after the
544 * divergence point and it's matched in both chains and the two chains have
545 * different constant indices.
546 */
547 for (nir_deref_instr **t_p = a_p; *t_p; t_p++) {
548 if ((*t_p)->deref_type == nir_deref_type_cast ||
549 (*t_p)->deref_type == nir_deref_type_ptr_as_array)
550 return nir_derefs_may_alias_bit;
551 }
552 for (nir_deref_instr **t_p = b_p; *t_p; t_p++) {
553 if ((*t_p)->deref_type == nir_deref_type_cast ||
554 (*t_p)->deref_type == nir_deref_type_ptr_as_array)
555 return nir_derefs_may_alias_bit;
556 }
557
558 while (*a_p != NULL && *b_p != NULL) {
559 nir_deref_instr *a_tail = *(a_p++);
560 nir_deref_instr *b_tail = *(b_p++);
561
562 switch (a_tail->deref_type) {
563 case nir_deref_type_array:
564 case nir_deref_type_array_wildcard: {
565 assert(b_tail->deref_type == nir_deref_type_array ||
566 b_tail->deref_type == nir_deref_type_array_wildcard);
567
568 if (a_tail->deref_type == nir_deref_type_array_wildcard) {
569 if (b_tail->deref_type != nir_deref_type_array_wildcard)
570 result &= ~nir_derefs_b_contains_a_bit;
571 } else if (b_tail->deref_type == nir_deref_type_array_wildcard) {
572 if (a_tail->deref_type != nir_deref_type_array_wildcard)
573 result &= ~nir_derefs_a_contains_b_bit;
574 } else {
575 assert(a_tail->deref_type == nir_deref_type_array &&
576 b_tail->deref_type == nir_deref_type_array);
577 assert(a_tail->arr.index.is_ssa && b_tail->arr.index.is_ssa);
578
579 if (nir_src_is_const(a_tail->arr.index) &&
580 nir_src_is_const(b_tail->arr.index)) {
581 /* If they're both direct and have different offsets, they
582 * don't even alias much less anything else.
583 */
584 if (nir_src_as_uint(a_tail->arr.index) !=
585 nir_src_as_uint(b_tail->arr.index))
586 return nir_derefs_do_not_alias;
587 } else if (a_tail->arr.index.ssa == b_tail->arr.index.ssa) {
588 /* They're the same indirect, continue on */
589 } else {
590 /* They're not the same index so we can't prove anything about
591 * containment.
592 */
593 result &= ~(nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit);
594 }
595 }
596 break;
597 }
598
599 case nir_deref_type_struct: {
600 /* If they're different struct members, they don't even alias */
601 if (a_tail->strct.index != b_tail->strct.index)
602 return nir_derefs_do_not_alias;
603 break;
604 }
605
606 default:
607 unreachable("Invalid deref type");
608 }
609 }
610
611 /* If a is longer than b, then it can't contain b */
612 if (*a_p != NULL)
613 result &= ~nir_derefs_a_contains_b_bit;
614 if (*b_p != NULL)
615 result &= ~nir_derefs_b_contains_a_bit;
616
617 /* If a contains b and b contains a they must be equal. */
618 if ((result & nir_derefs_a_contains_b_bit) && (result & nir_derefs_b_contains_a_bit))
619 result |= nir_derefs_equal_bit;
620
621 return result;
622 }
623
624 nir_deref_compare_result
625 nir_compare_derefs(nir_deref_instr *a, nir_deref_instr *b)
626 {
627 if (a == b) {
628 return nir_derefs_equal_bit | nir_derefs_may_alias_bit |
629 nir_derefs_a_contains_b_bit | nir_derefs_b_contains_a_bit;
630 }
631
632 nir_deref_path a_path, b_path;
633 nir_deref_path_init(&a_path, a, NULL);
634 nir_deref_path_init(&b_path, b, NULL);
635 assert(a_path.path[0]->deref_type == nir_deref_type_var ||
636 a_path.path[0]->deref_type == nir_deref_type_cast);
637 assert(b_path.path[0]->deref_type == nir_deref_type_var ||
638 b_path.path[0]->deref_type == nir_deref_type_cast);
639
640 nir_deref_compare_result result = nir_compare_deref_paths(&a_path, &b_path);
641
642 nir_deref_path_finish(&a_path);
643 nir_deref_path_finish(&b_path);
644
645 return result;
646 }
647
648 struct rematerialize_deref_state {
649 bool progress;
650 nir_builder builder;
651 nir_block *block;
652 struct hash_table *cache;
653 };
654
655 static nir_deref_instr *
656 rematerialize_deref_in_block(nir_deref_instr *deref,
657 struct rematerialize_deref_state *state)
658 {
659 if (deref->instr.block == state->block)
660 return deref;
661
662 if (!state->cache) {
663 state->cache = _mesa_pointer_hash_table_create(NULL);
664 }
665
666 struct hash_entry *cached = _mesa_hash_table_search(state->cache, deref);
667 if (cached)
668 return cached->data;
669
670 nir_builder *b = &state->builder;
671 nir_deref_instr *new_deref =
672 nir_deref_instr_create(b->shader, deref->deref_type);
673 new_deref->mode = deref->mode;
674 new_deref->type = deref->type;
675
676 if (deref->deref_type == nir_deref_type_var) {
677 new_deref->var = deref->var;
678 } else {
679 nir_deref_instr *parent = nir_src_as_deref(deref->parent);
680 if (parent) {
681 parent = rematerialize_deref_in_block(parent, state);
682 new_deref->parent = nir_src_for_ssa(&parent->dest.ssa);
683 } else {
684 nir_src_copy(&new_deref->parent, &deref->parent, new_deref);
685 }
686 }
687
688 switch (deref->deref_type) {
689 case nir_deref_type_var:
690 case nir_deref_type_array_wildcard:
691 /* Nothing more to do */
692 break;
693
694 case nir_deref_type_cast:
695 new_deref->cast.ptr_stride = deref->cast.ptr_stride;
696 break;
697
698 case nir_deref_type_array:
699 case nir_deref_type_ptr_as_array:
700 assert(!nir_src_as_deref(deref->arr.index));
701 nir_src_copy(&new_deref->arr.index, &deref->arr.index, new_deref);
702 break;
703
704 case nir_deref_type_struct:
705 new_deref->strct.index = deref->strct.index;
706 break;
707
708 default:
709 unreachable("Invalid deref instruction type");
710 }
711
712 nir_ssa_dest_init(&new_deref->instr, &new_deref->dest,
713 deref->dest.ssa.num_components,
714 deref->dest.ssa.bit_size,
715 deref->dest.ssa.name);
716 nir_builder_instr_insert(b, &new_deref->instr);
717
718 return new_deref;
719 }
720
721 static bool
722 rematerialize_deref_src(nir_src *src, void *_state)
723 {
724 struct rematerialize_deref_state *state = _state;
725
726 nir_deref_instr *deref = nir_src_as_deref(*src);
727 if (!deref)
728 return true;
729
730 nir_deref_instr *block_deref = rematerialize_deref_in_block(deref, state);
731 if (block_deref != deref) {
732 nir_instr_rewrite_src(src->parent_instr, src,
733 nir_src_for_ssa(&block_deref->dest.ssa));
734 nir_deref_instr_remove_if_unused(deref);
735 state->progress = true;
736 }
737
738 return true;
739 }
740
741 /** Re-materialize derefs in every block
742 *
743 * This pass re-materializes deref instructions in every block in which it is
744 * used. After this pass has been run, every use of a deref will be of a
745 * deref in the same block as the use. Also, all unused derefs will be
746 * deleted as a side-effect.
747 *
748 * Derefs used as sources of phi instructions are not rematerialized.
749 */
750 bool
751 nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl *impl)
752 {
753 struct rematerialize_deref_state state = { 0 };
754 nir_builder_init(&state.builder, impl);
755
756 nir_foreach_block_unstructured(block, impl) {
757 state.block = block;
758
759 /* Start each block with a fresh cache */
760 if (state.cache)
761 _mesa_hash_table_clear(state.cache, NULL);
762
763 nir_foreach_instr_safe(instr, block) {
764 if (instr->type == nir_instr_type_deref &&
765 nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr)))
766 continue;
767
768 /* If a deref is used in a phi, we can't rematerialize it, as the new
769 * derefs would appear before the phi, which is not valid.
770 */
771 if (instr->type == nir_instr_type_phi)
772 continue;
773
774 state.builder.cursor = nir_before_instr(instr);
775 nir_foreach_src(instr, rematerialize_deref_src, &state);
776 }
777
778 #ifndef NDEBUG
779 nir_if *following_if = nir_block_get_following_if(block);
780 if (following_if)
781 assert(!nir_src_as_deref(following_if->condition));
782 #endif
783 }
784
785 _mesa_hash_table_destroy(state.cache, NULL);
786
787 return state.progress;
788 }
789
790 static void
791 nir_deref_instr_fixup_child_types(nir_deref_instr *parent)
792 {
793 nir_foreach_use(use, &parent->dest.ssa) {
794 if (use->parent_instr->type != nir_instr_type_deref)
795 continue;
796
797 nir_deref_instr *child = nir_instr_as_deref(use->parent_instr);
798 switch (child->deref_type) {
799 case nir_deref_type_var:
800 unreachable("nir_deref_type_var cannot be a child");
801
802 case nir_deref_type_array:
803 case nir_deref_type_array_wildcard:
804 child->type = glsl_get_array_element(parent->type);
805 break;
806
807 case nir_deref_type_ptr_as_array:
808 child->type = parent->type;
809 break;
810
811 case nir_deref_type_struct:
812 child->type = glsl_get_struct_field(parent->type,
813 child->strct.index);
814 break;
815
816 case nir_deref_type_cast:
817 /* We stop the recursion here */
818 continue;
819 }
820
821 /* Recurse into children */
822 nir_deref_instr_fixup_child_types(child);
823 }
824 }
825
826 static bool
827 is_trivial_array_deref_cast(nir_deref_instr *cast)
828 {
829 assert(is_trivial_deref_cast(cast));
830
831 nir_deref_instr *parent = nir_src_as_deref(cast->parent);
832
833 if (parent->deref_type == nir_deref_type_array) {
834 return cast->cast.ptr_stride ==
835 glsl_get_explicit_stride(nir_deref_instr_parent(parent)->type);
836 } else if (parent->deref_type == nir_deref_type_ptr_as_array) {
837 return cast->cast.ptr_stride ==
838 nir_deref_instr_array_stride(parent);
839 } else {
840 return false;
841 }
842 }
843
844 static bool
845 is_deref_ptr_as_array(nir_instr *instr)
846 {
847 return instr->type == nir_instr_type_deref &&
848 nir_instr_as_deref(instr)->deref_type == nir_deref_type_ptr_as_array;
849 }
850
851 /**
852 * Remove casts that just wrap other casts.
853 */
854 static bool
855 opt_remove_cast_cast(nir_deref_instr *cast)
856 {
857 nir_deref_instr *first_cast = cast;
858
859 while (true) {
860 nir_deref_instr *parent = nir_deref_instr_parent(first_cast);
861 if (parent == NULL || parent->deref_type != nir_deref_type_cast)
862 break;
863 first_cast = parent;
864 }
865 if (cast == first_cast)
866 return false;
867
868 nir_instr_rewrite_src(&cast->instr, &cast->parent,
869 nir_src_for_ssa(first_cast->parent.ssa));
870 return true;
871 }
872
873 static bool
874 opt_remove_sampler_cast(nir_deref_instr *cast)
875 {
876 assert(cast->deref_type == nir_deref_type_cast);
877 nir_deref_instr *parent = nir_src_as_deref(cast->parent);
878 if (parent == NULL)
879 return false;
880
881 /* Strip both types down to their non-array type and bail if there are any
882 * discrepancies in array lengths.
883 */
884 const struct glsl_type *parent_type = parent->type;
885 const struct glsl_type *cast_type = cast->type;
886 while (glsl_type_is_array(parent_type) && glsl_type_is_array(cast_type)) {
887 if (glsl_get_length(parent_type) != glsl_get_length(cast_type))
888 return false;
889 parent_type = glsl_get_array_element(parent_type);
890 cast_type = glsl_get_array_element(cast_type);
891 }
892
893 if (glsl_type_is_array(parent_type) || glsl_type_is_array(cast_type))
894 return false;
895
896 if (!glsl_type_is_sampler(parent_type) ||
897 cast_type != glsl_bare_sampler_type())
898 return false;
899
900 /* We're a cast from a more detailed sampler type to a bare sampler */
901 nir_ssa_def_rewrite_uses(&cast->dest.ssa,
902 nir_src_for_ssa(&parent->dest.ssa));
903 nir_instr_remove(&cast->instr);
904
905 /* Recursively crawl the deref tree and clean up types */
906 nir_deref_instr_fixup_child_types(parent);
907
908 return true;
909 }
910
911 /**
912 * Is this casting a struct to a contained struct.
913 * struct a { struct b field0 };
914 * ssa_5 is structa;
915 * deref_cast (structb *)ssa_5 (function_temp structb);
916 * converts to
917 * deref_struct &ssa_5->field0 (function_temp structb);
918 * This allows subsequent copy propagation to work.
919 */
920 static bool
921 opt_replace_struct_wrapper_cast(nir_builder *b, nir_deref_instr *cast)
922 {
923 nir_deref_instr *parent = nir_src_as_deref(cast->parent);
924 if (!parent)
925 return false;
926
927 if (!glsl_type_is_struct(parent->type))
928 return false;
929
930 if (glsl_get_struct_field_offset(parent->type, 0) != 0)
931 return false;
932
933 if (cast->type != glsl_get_struct_field(parent->type, 0))
934 return false;
935
936 nir_deref_instr *replace = nir_build_deref_struct(b, parent, 0);
937 nir_ssa_def_rewrite_uses(&cast->dest.ssa, nir_src_for_ssa(&replace->dest.ssa));
938 nir_deref_instr_remove_if_unused(cast);
939 return true;
940 }
941
942 static bool
943 opt_deref_cast(nir_builder *b, nir_deref_instr *cast)
944 {
945 bool progress;
946
947 if (opt_replace_struct_wrapper_cast(b, cast))
948 return true;
949
950 if (opt_remove_sampler_cast(cast))
951 return true;
952
953 progress = opt_remove_cast_cast(cast);
954 if (!is_trivial_deref_cast(cast))
955 return progress;
956
957 bool trivial_array_cast = is_trivial_array_deref_cast(cast);
958
959 assert(cast->dest.is_ssa);
960 assert(cast->parent.is_ssa);
961
962 nir_foreach_use_safe(use_src, &cast->dest.ssa) {
963 /* If this isn't a trivial array cast, we can't propagate into
964 * ptr_as_array derefs.
965 */
966 if (is_deref_ptr_as_array(use_src->parent_instr) &&
967 !trivial_array_cast)
968 continue;
969
970 nir_instr_rewrite_src(use_src->parent_instr, use_src, cast->parent);
971 progress = true;
972 }
973
974 /* If uses would be a bit crazy */
975 assert(list_is_empty(&cast->dest.ssa.if_uses));
976
977 if (nir_deref_instr_remove_if_unused(cast))
978 progress = true;
979
980 return progress;
981 }
982
983 static bool
984 opt_deref_ptr_as_array(nir_builder *b, nir_deref_instr *deref)
985 {
986 assert(deref->deref_type == nir_deref_type_ptr_as_array);
987
988 nir_deref_instr *parent = nir_deref_instr_parent(deref);
989
990 if (nir_src_is_const(deref->arr.index) &&
991 nir_src_as_int(deref->arr.index) == 0) {
992 /* If it's a ptr_as_array deref with an index of 0, it does nothing
993 * and we can just replace its uses with its parent.
994 *
995 * The source of a ptr_as_array deref always has a deref_type of
996 * nir_deref_type_array or nir_deref_type_cast. If it's a cast, it
997 * may be trivial and we may be able to get rid of that too. Any
998 * trivial cast of trivial cast cases should be handled already by
999 * opt_deref_cast() above.
1000 */
1001 if (parent->deref_type == nir_deref_type_cast &&
1002 is_trivial_deref_cast(parent))
1003 parent = nir_deref_instr_parent(parent);
1004 nir_ssa_def_rewrite_uses(&deref->dest.ssa,
1005 nir_src_for_ssa(&parent->dest.ssa));
1006 nir_instr_remove(&deref->instr);
1007 return true;
1008 }
1009
1010 if (parent->deref_type != nir_deref_type_array &&
1011 parent->deref_type != nir_deref_type_ptr_as_array)
1012 return false;
1013
1014 assert(parent->parent.is_ssa);
1015 assert(parent->arr.index.is_ssa);
1016 assert(deref->arr.index.is_ssa);
1017
1018 nir_ssa_def *new_idx = nir_iadd(b, parent->arr.index.ssa,
1019 deref->arr.index.ssa);
1020
1021 deref->deref_type = parent->deref_type;
1022 nir_instr_rewrite_src(&deref->instr, &deref->parent, parent->parent);
1023 nir_instr_rewrite_src(&deref->instr, &deref->arr.index,
1024 nir_src_for_ssa(new_idx));
1025 return true;
1026 }
1027
1028 bool
1029 nir_opt_deref_impl(nir_function_impl *impl)
1030 {
1031 bool progress = false;
1032
1033 nir_builder b;
1034 nir_builder_init(&b, impl);
1035
1036 nir_foreach_block(block, impl) {
1037 nir_foreach_instr_safe(instr, block) {
1038 if (instr->type != nir_instr_type_deref)
1039 continue;
1040
1041 b.cursor = nir_before_instr(instr);
1042
1043 nir_deref_instr *deref = nir_instr_as_deref(instr);
1044 switch (deref->deref_type) {
1045 case nir_deref_type_ptr_as_array:
1046 if (opt_deref_ptr_as_array(&b, deref))
1047 progress = true;
1048 break;
1049
1050 case nir_deref_type_cast:
1051 if (opt_deref_cast(&b, deref))
1052 progress = true;
1053 break;
1054
1055 default:
1056 /* Do nothing */
1057 break;
1058 }
1059 }
1060 }
1061
1062 if (progress) {
1063 nir_metadata_preserve(impl, nir_metadata_block_index |
1064 nir_metadata_dominance);
1065 } else {
1066 nir_metadata_preserve(impl, nir_metadata_all);
1067 }
1068
1069 return progress;
1070 }
1071
1072 bool
1073 nir_opt_deref(nir_shader *shader)
1074 {
1075 bool progress = false;
1076
1077 nir_foreach_function(func, shader) {
1078 if (func->impl && nir_opt_deref_impl(func->impl))
1079 progress = true;
1080 }
1081
1082 return progress;
1083 }