2 * Copyright © 2018 Intel Corporation
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:
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
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
25 #include "nir_builder.h"
26 #include "nir_deref.h"
27 #include "util/hash_table.h"
30 nir_deref_path_init(nir_deref_path
*path
,
31 nir_deref_instr
*deref
, void *mem_ctx
)
33 assert(deref
!= NULL
);
35 /* The length of the short path is at most ARRAY_SIZE - 1 because we need
36 * room for the NULL terminator.
38 static const int max_short_path_len
= ARRAY_SIZE(path
->_short_path
) - 1;
42 nir_deref_instr
**tail
= &path
->_short_path
[max_short_path_len
];
43 nir_deref_instr
**head
= tail
;
46 for (nir_deref_instr
*d
= deref
; d
; d
= nir_deref_instr_parent(d
)) {
48 if (count
<= max_short_path_len
)
52 if (count
<= max_short_path_len
) {
53 /* If we're under max_short_path_len, just use the short path. */
59 /* Just in case someone uses short_path by accident */
60 for (unsigned i
= 0; i
< ARRAY_SIZE(path
->_short_path
); i
++)
61 path
->_short_path
[i
] = (void *)0xdeadbeef;
64 path
->path
= ralloc_array(mem_ctx
, nir_deref_instr
*, count
+ 1);
65 head
= tail
= path
->path
+ count
;
67 for (nir_deref_instr
*d
= deref
; d
; d
= nir_deref_instr_parent(d
))
71 assert(head
== path
->path
);
72 assert(tail
== head
+ count
);
73 assert((*head
)->deref_type
== nir_deref_type_var
);
74 assert(*tail
== NULL
);
78 nir_deref_path_finish(nir_deref_path
*path
)
80 if (path
->path
< &path
->_short_path
[0] ||
81 path
->path
> &path
->_short_path
[ARRAY_SIZE(path
->_short_path
) - 1])
82 ralloc_free(path
->path
);
86 * Recursively removes unused deref instructions
89 nir_deref_instr_remove_if_unused(nir_deref_instr
*instr
)
91 bool progress
= false;
93 for (nir_deref_instr
*d
= instr
; d
; d
= nir_deref_instr_parent(d
)) {
94 /* If anyone is using this deref, leave it alone */
95 assert(d
->dest
.is_ssa
);
96 if (!list_empty(&d
->dest
.ssa
.uses
))
99 nir_instr_remove(&d
->instr
);
107 nir_deref_instr_has_indirect(nir_deref_instr
*instr
)
109 while (instr
->deref_type
!= nir_deref_type_var
) {
110 /* Consider casts to be indirects */
111 if (instr
->deref_type
== nir_deref_type_cast
)
114 if (instr
->deref_type
== nir_deref_type_array
&&
115 !nir_src_as_const_value(instr
->arr
.index
))
118 instr
= nir_deref_instr_parent(instr
);
125 type_get_array_stride(const struct glsl_type
*elem_type
,
126 glsl_type_size_align_func size_align
)
128 unsigned elem_size
, elem_align
;
129 glsl_get_natural_size_align_bytes(elem_type
, &elem_size
, &elem_align
);
130 return ALIGN_POT(elem_size
, elem_align
);
134 struct_type_get_field_offset(const struct glsl_type
*struct_type
,
135 glsl_type_size_align_func size_align
,
138 assert(glsl_type_is_struct(struct_type
));
140 for (unsigned i
= 0; i
<= field_idx
; i
++) {
141 unsigned elem_size
, elem_align
;
142 glsl_get_natural_size_align_bytes(glsl_get_struct_field(struct_type
, i
),
143 &elem_size
, &elem_align
);
144 offset
= ALIGN_POT(offset
, elem_align
);
152 nir_deref_instr_get_const_offset(nir_deref_instr
*deref
,
153 glsl_type_size_align_func size_align
)
156 nir_deref_path_init(&path
, deref
, NULL
);
158 assert(path
.path
[0]->deref_type
== nir_deref_type_var
);
161 for (nir_deref_instr
**p
= &path
.path
[1]; *p
; p
++) {
162 if ((*p
)->deref_type
== nir_deref_type_array
) {
163 offset
+= nir_src_as_const_value((*p
)->arr
.index
)->u32
[0] *
164 type_get_array_stride((*p
)->type
, size_align
);
165 } else if ((*p
)->deref_type
== nir_deref_type_struct
) {
166 /* p starts at path[1], so this is safe */
167 nir_deref_instr
*parent
= *(p
- 1);
168 offset
+= struct_type_get_field_offset(parent
->type
, size_align
,
171 unreachable("Unsupported deref type");
175 nir_deref_path_finish(&path
);
181 nir_build_deref_offset(nir_builder
*b
, nir_deref_instr
*deref
,
182 glsl_type_size_align_func size_align
)
185 nir_deref_path_init(&path
, deref
, NULL
);
187 assert(path
.path
[0]->deref_type
== nir_deref_type_var
);
189 nir_ssa_def
*offset
= nir_imm_int(b
, 0);
190 for (nir_deref_instr
**p
= &path
.path
[1]; *p
; p
++) {
191 if ((*p
)->deref_type
== nir_deref_type_array
) {
192 nir_ssa_def
*index
= nir_ssa_for_src(b
, (*p
)->arr
.index
, 1);
193 nir_ssa_def
*stride
=
194 nir_imm_int(b
, type_get_array_stride((*p
)->type
, size_align
));
195 offset
= nir_iadd(b
, offset
, nir_imul(b
, index
, stride
));
196 } else if ((*p
)->deref_type
== nir_deref_type_struct
) {
197 /* p starts at path[1], so this is safe */
198 nir_deref_instr
*parent
= *(p
- 1);
199 unsigned field_offset
=
200 struct_type_get_field_offset(parent
->type
, size_align
,
202 nir_iadd(b
, offset
, nir_imm_int(b
, field_offset
));
204 unreachable("Unsupported deref type");
208 nir_deref_path_finish(&path
);
214 nir_remove_dead_derefs_impl(nir_function_impl
*impl
)
216 bool progress
= false;
218 nir_foreach_block(block
, impl
) {
219 nir_foreach_instr_safe(instr
, block
) {
220 if (instr
->type
== nir_instr_type_deref
&&
221 nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr
)))
227 nir_metadata_preserve(impl
, nir_metadata_block_index
|
228 nir_metadata_dominance
);
234 nir_remove_dead_derefs(nir_shader
*shader
)
236 bool progress
= false;
237 nir_foreach_function(function
, shader
) {
238 if (function
->impl
&& nir_remove_dead_derefs_impl(function
->impl
))
246 nir_fixup_deref_modes(nir_shader
*shader
)
248 nir_foreach_function(function
, shader
) {
252 nir_foreach_block(block
, function
->impl
) {
253 nir_foreach_instr(instr
, block
) {
254 if (instr
->type
!= nir_instr_type_deref
)
257 nir_deref_instr
*deref
= nir_instr_as_deref(instr
);
259 nir_variable_mode parent_mode
;
260 if (deref
->deref_type
== nir_deref_type_var
) {
261 parent_mode
= deref
->var
->data
.mode
;
263 assert(deref
->parent
.is_ssa
);
264 nir_deref_instr
*parent
=
265 nir_instr_as_deref(deref
->parent
.ssa
->parent_instr
);
266 parent_mode
= parent
->mode
;
269 deref
->mode
= parent_mode
;
275 nir_deref_compare_result
276 nir_compare_deref_paths(nir_deref_path
*a_path
,
277 nir_deref_path
*b_path
)
279 if (a_path
->path
[0]->var
!= b_path
->path
[0]->var
)
282 /* Start off assuming they fully compare. We ignore equality for now. In
283 * the end, we'll determine that by containment.
285 nir_deref_compare_result result
= nir_derefs_may_alias_bit
|
286 nir_derefs_a_contains_b_bit
|
287 nir_derefs_b_contains_a_bit
;
289 nir_deref_instr
**a_p
= &a_path
->path
[1];
290 nir_deref_instr
**b_p
= &b_path
->path
[1];
291 while (*a_p
!= NULL
&& *b_p
!= NULL
) {
292 nir_deref_instr
*a_tail
= *(a_p
++);
293 nir_deref_instr
*b_tail
= *(b_p
++);
295 if (a_tail
== b_tail
)
298 switch (a_tail
->deref_type
) {
299 case nir_deref_type_array
:
300 case nir_deref_type_array_wildcard
: {
301 assert(b_tail
->deref_type
== nir_deref_type_array
||
302 b_tail
->deref_type
== nir_deref_type_array_wildcard
);
304 if (a_tail
->deref_type
== nir_deref_type_array_wildcard
) {
305 if (b_tail
->deref_type
!= nir_deref_type_array_wildcard
)
306 result
&= ~nir_derefs_b_contains_a_bit
;
307 } else if (b_tail
->deref_type
== nir_deref_type_array_wildcard
) {
308 if (a_tail
->deref_type
!= nir_deref_type_array_wildcard
)
309 result
&= ~nir_derefs_a_contains_b_bit
;
311 assert(a_tail
->deref_type
== nir_deref_type_array
&&
312 b_tail
->deref_type
== nir_deref_type_array
);
313 assert(a_tail
->arr
.index
.is_ssa
&& b_tail
->arr
.index
.is_ssa
);
315 nir_const_value
*a_index_const
=
316 nir_src_as_const_value(a_tail
->arr
.index
);
317 nir_const_value
*b_index_const
=
318 nir_src_as_const_value(b_tail
->arr
.index
);
319 if (a_index_const
&& b_index_const
) {
320 /* If they're both direct and have different offsets, they
321 * don't even alias much less anything else.
323 if (a_index_const
->u32
[0] != b_index_const
->u32
[0])
325 } else if (a_tail
->arr
.index
.ssa
== b_tail
->arr
.index
.ssa
) {
326 /* They're the same indirect, continue on */
328 /* They're not the same index so we can't prove anything about
331 result
&= ~(nir_derefs_a_contains_b_bit
| nir_derefs_b_contains_a_bit
);
337 case nir_deref_type_struct
: {
338 /* If they're different struct members, they don't even alias */
339 if (a_tail
->strct
.index
!= b_tail
->strct
.index
)
345 unreachable("Invalid deref type");
349 /* If a is longer than b, then it can't contain b */
351 result
&= ~nir_derefs_a_contains_b_bit
;
353 result
&= ~nir_derefs_b_contains_a_bit
;
355 /* If a contains b and b contains a they must be equal. */
356 if ((result
& nir_derefs_a_contains_b_bit
) && (result
& nir_derefs_b_contains_a_bit
))
357 result
|= nir_derefs_equal_bit
;
362 nir_deref_compare_result
363 nir_compare_derefs(nir_deref_instr
*a
, nir_deref_instr
*b
)
366 return nir_derefs_equal_bit
| nir_derefs_may_alias_bit
|
367 nir_derefs_a_contains_b_bit
| nir_derefs_b_contains_a_bit
;
370 nir_deref_path a_path
, b_path
;
371 nir_deref_path_init(&a_path
, a
, NULL
);
372 nir_deref_path_init(&b_path
, b
, NULL
);
373 assert(a_path
.path
[0]->deref_type
== nir_deref_type_var
);
374 assert(b_path
.path
[0]->deref_type
== nir_deref_type_var
);
376 nir_deref_compare_result result
= nir_compare_deref_paths(&a_path
, &b_path
);
378 nir_deref_path_finish(&a_path
);
379 nir_deref_path_finish(&b_path
);
384 struct rematerialize_deref_state
{
388 struct hash_table
*cache
;
391 static nir_deref_instr
*
392 rematerialize_deref_in_block(nir_deref_instr
*deref
,
393 struct rematerialize_deref_state
*state
)
395 if (deref
->instr
.block
== state
->block
)
399 state
->cache
= _mesa_hash_table_create(NULL
, _mesa_hash_pointer
,
400 _mesa_key_pointer_equal
);
403 struct hash_entry
*cached
= _mesa_hash_table_search(state
->cache
, deref
);
407 nir_builder
*b
= &state
->builder
;
408 nir_deref_instr
*new_deref
=
409 nir_deref_instr_create(b
->shader
, deref
->deref_type
);
410 new_deref
->mode
= deref
->mode
;
411 new_deref
->type
= deref
->type
;
413 if (deref
->deref_type
== nir_deref_type_var
) {
414 new_deref
->var
= deref
->var
;
416 nir_deref_instr
*parent
= nir_src_as_deref(deref
->parent
);
418 parent
= rematerialize_deref_in_block(parent
, state
);
419 new_deref
->parent
= nir_src_for_ssa(&parent
->dest
.ssa
);
421 nir_src_copy(&new_deref
->parent
, &deref
->parent
, new_deref
);
425 switch (deref
->deref_type
) {
426 case nir_deref_type_var
:
427 case nir_deref_type_array_wildcard
:
428 case nir_deref_type_cast
:
429 /* Nothing more to do */
432 case nir_deref_type_array
:
433 assert(!nir_src_as_deref(deref
->arr
.index
));
434 nir_src_copy(&new_deref
->arr
.index
, &deref
->arr
.index
, new_deref
);
437 case nir_deref_type_struct
:
438 new_deref
->strct
.index
= deref
->strct
.index
;
442 unreachable("Invalid deref instruction type");
445 nir_ssa_dest_init(&new_deref
->instr
, &new_deref
->dest
,
446 deref
->dest
.ssa
.num_components
,
447 deref
->dest
.ssa
.bit_size
,
448 deref
->dest
.ssa
.name
);
449 nir_builder_instr_insert(b
, &new_deref
->instr
);
455 rematerialize_deref_src(nir_src
*src
, void *_state
)
457 struct rematerialize_deref_state
*state
= _state
;
459 nir_deref_instr
*deref
= nir_src_as_deref(*src
);
463 nir_deref_instr
*block_deref
= rematerialize_deref_in_block(deref
, state
);
464 if (block_deref
!= deref
) {
465 nir_instr_rewrite_src(src
->parent_instr
, src
,
466 nir_src_for_ssa(&block_deref
->dest
.ssa
));
467 nir_deref_instr_remove_if_unused(deref
);
468 state
->progress
= true;
474 /** Re-materialize derefs in every block
476 * This pass re-materializes deref instructions in every block in which it is
477 * used. After this pass has been run, every use of a deref will be of a
478 * deref in the same block as the use. Also, all unused derefs will be
479 * deleted as a side-effect.
482 nir_rematerialize_derefs_in_use_blocks_impl(nir_function_impl
*impl
)
484 struct rematerialize_deref_state state
= { 0 };
485 nir_builder_init(&state
.builder
, impl
);
487 nir_foreach_block(block
, impl
) {
490 /* Start each block with a fresh cache */
492 _mesa_hash_table_clear(state
.cache
, NULL
);
494 nir_foreach_instr_safe(instr
, block
) {
495 if (instr
->type
== nir_instr_type_deref
) {
496 nir_deref_instr_remove_if_unused(nir_instr_as_deref(instr
));
500 state
.builder
.cursor
= nir_before_instr(instr
);
501 nir_foreach_src(instr
, rematerialize_deref_src
, &state
);
505 nir_if
*following_if
= nir_block_get_following_if(block
);
507 assert(!nir_src_as_deref(following_if
->condition
));
511 _mesa_hash_table_destroy(state
.cache
, NULL
);
513 return state
.progress
;