2 * Copyright © 2016 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"
28 #include "util/bitscan.h"
29 #include "util/u_dynarray.h"
31 static const bool debug
= false;
34 * Variable-based copy propagation
36 * Normally, NIR trusts in SSA form for most of its copy-propagation needs.
37 * However, there are cases, especially when dealing with indirects, where SSA
38 * won't help you. This pass is for those times. Specifically, it handles
39 * the following things that the rest of NIR can't:
41 * 1) Copy-propagation on variables that have indirect access. This includes
42 * propagating from indirect stores into indirect loads.
44 * 2) Removal of redundant load_deref intrinsics. We can't trust regular CSE
45 * to do this because it isn't aware of variable writes that may alias the
46 * value and make the former load invalid.
48 * This pass uses an intermediate solution between being local / "per-block"
49 * and a complete data-flow analysis. It follows the control flow graph, and
50 * propagate the available copy information forward, invalidating data at each
53 * Removal of dead writes to variables is handled by another pass.
57 nir_variable_mode modes
;
59 /* Key is deref and value is the uintptr_t with the write mask. */
60 struct hash_table
*derefs
;
67 nir_ssa_def
*def
[NIR_MAX_VEC_COMPONENTS
];
68 uint8_t component
[NIR_MAX_VEC_COMPONENTS
];
70 nir_deref_instr
*deref
;
75 value_set_ssa_components(struct value
*value
, nir_ssa_def
*def
,
76 unsigned num_components
)
79 memset(&value
->ssa
, 0, sizeof(value
->ssa
));
81 for (unsigned i
= 0; i
< num_components
; i
++) {
82 value
->ssa
.def
[i
] = def
;
83 value
->ssa
.component
[i
] = i
;
93 struct copy_prop_var_state
{
94 nir_function_impl
*impl
;
99 /* Maps nodes to vars_written. Used to invalidate copy entries when
100 * visiting each node.
102 struct hash_table
*vars_written_map
;
108 value_equals_store_src(struct value
*value
, nir_intrinsic_instr
*intrin
)
110 assert(intrin
->intrinsic
== nir_intrinsic_store_deref
);
111 uintptr_t write_mask
= nir_intrinsic_write_mask(intrin
);
113 for (unsigned i
= 0; i
< intrin
->num_components
; i
++) {
114 if ((write_mask
& (1 << i
)) &&
115 (value
->ssa
.def
[i
] != intrin
->src
[1].ssa
||
116 value
->ssa
.component
[i
] != i
))
123 static struct vars_written
*
124 create_vars_written(struct copy_prop_var_state
*state
)
126 struct vars_written
*written
=
127 linear_zalloc_child(state
->lin_ctx
, sizeof(struct vars_written
));
128 written
->derefs
= _mesa_pointer_hash_table_create(state
->mem_ctx
);
133 gather_vars_written(struct copy_prop_var_state
*state
,
134 struct vars_written
*written
,
135 nir_cf_node
*cf_node
)
137 struct vars_written
*new_written
= NULL
;
139 switch (cf_node
->type
) {
140 case nir_cf_node_function
: {
141 nir_function_impl
*impl
= nir_cf_node_as_function(cf_node
);
142 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &impl
->body
)
143 gather_vars_written(state
, NULL
, cf_node
);
147 case nir_cf_node_block
: {
151 nir_block
*block
= nir_cf_node_as_block(cf_node
);
152 nir_foreach_instr(instr
, block
) {
153 if (instr
->type
== nir_instr_type_call
) {
154 written
->modes
|= nir_var_shader_out
|
155 nir_var_shader_temp
|
156 nir_var_function_temp
|
163 if (instr
->type
!= nir_instr_type_intrinsic
)
166 nir_intrinsic_instr
*intrin
= nir_instr_as_intrinsic(instr
);
167 switch (intrin
->intrinsic
) {
168 case nir_intrinsic_control_barrier
:
169 case nir_intrinsic_group_memory_barrier
:
170 case nir_intrinsic_memory_barrier
:
171 written
->modes
|= nir_var_shader_out
|
177 case nir_intrinsic_scoped_memory_barrier
:
178 if (nir_intrinsic_memory_semantics(intrin
) & NIR_MEMORY_ACQUIRE
)
179 written
->modes
|= nir_intrinsic_memory_modes(intrin
);
182 case nir_intrinsic_emit_vertex
:
183 case nir_intrinsic_emit_vertex_with_counter
:
184 written
->modes
= nir_var_shader_out
;
187 case nir_intrinsic_deref_atomic_add
:
188 case nir_intrinsic_deref_atomic_imin
:
189 case nir_intrinsic_deref_atomic_umin
:
190 case nir_intrinsic_deref_atomic_imax
:
191 case nir_intrinsic_deref_atomic_umax
:
192 case nir_intrinsic_deref_atomic_and
:
193 case nir_intrinsic_deref_atomic_or
:
194 case nir_intrinsic_deref_atomic_xor
:
195 case nir_intrinsic_deref_atomic_exchange
:
196 case nir_intrinsic_deref_atomic_comp_swap
:
197 case nir_intrinsic_store_deref
:
198 case nir_intrinsic_copy_deref
: {
199 /* Destination in all of store_deref, copy_deref and the atomics is src[0]. */
200 nir_deref_instr
*dst
= nir_src_as_deref(intrin
->src
[0]);
202 uintptr_t mask
= intrin
->intrinsic
== nir_intrinsic_store_deref
?
203 nir_intrinsic_write_mask(intrin
) : (1 << glsl_get_vector_elements(dst
->type
)) - 1;
205 struct hash_entry
*ht_entry
= _mesa_hash_table_search(written
->derefs
, dst
);
207 ht_entry
->data
= (void *)(mask
| (uintptr_t)ht_entry
->data
);
209 _mesa_hash_table_insert(written
->derefs
, dst
, (void *)mask
);
222 case nir_cf_node_if
: {
223 nir_if
*if_stmt
= nir_cf_node_as_if(cf_node
);
225 new_written
= create_vars_written(state
);
227 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &if_stmt
->then_list
)
228 gather_vars_written(state
, new_written
, cf_node
);
230 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &if_stmt
->else_list
)
231 gather_vars_written(state
, new_written
, cf_node
);
236 case nir_cf_node_loop
: {
237 nir_loop
*loop
= nir_cf_node_as_loop(cf_node
);
239 new_written
= create_vars_written(state
);
241 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &loop
->body
)
242 gather_vars_written(state
, new_written
, cf_node
);
248 unreachable("Invalid CF node type");
252 /* Merge new information to the parent control flow node. */
254 written
->modes
|= new_written
->modes
;
255 hash_table_foreach(new_written
->derefs
, new_entry
) {
256 struct hash_entry
*old_entry
=
257 _mesa_hash_table_search_pre_hashed(written
->derefs
, new_entry
->hash
,
260 nir_component_mask_t merged
= (uintptr_t) new_entry
->data
|
261 (uintptr_t) old_entry
->data
;
262 old_entry
->data
= (void *) ((uintptr_t) merged
);
264 _mesa_hash_table_insert_pre_hashed(written
->derefs
, new_entry
->hash
,
265 new_entry
->key
, new_entry
->data
);
269 _mesa_hash_table_insert(state
->vars_written_map
, cf_node
, new_written
);
273 static struct copy_entry
*
274 copy_entry_create(struct util_dynarray
*copies
,
275 nir_deref_instr
*dst_deref
)
277 struct copy_entry new_entry
= {
280 util_dynarray_append(copies
, struct copy_entry
, new_entry
);
281 return util_dynarray_top_ptr(copies
, struct copy_entry
);
284 /* Remove copy entry by swapping it with the last element and reducing the
285 * size. If used inside an iteration on copies, it must be a reverse
286 * (backwards) iteration. It is safe to use in those cases because the swap
287 * will not affect the rest of the iteration.
290 copy_entry_remove(struct util_dynarray
*copies
,
291 struct copy_entry
*entry
)
293 /* This also works when removing the last element since pop don't shrink
294 * the memory used by the array, so the swap is useless but not invalid.
296 *entry
= util_dynarray_pop(copies
, struct copy_entry
);
300 is_array_deref_of_vector(nir_deref_instr
*deref
)
302 if (deref
->deref_type
!= nir_deref_type_array
)
304 nir_deref_instr
*parent
= nir_deref_instr_parent(deref
);
305 return glsl_type_is_vector(parent
->type
);
308 static struct copy_entry
*
309 lookup_entry_for_deref(struct util_dynarray
*copies
,
310 nir_deref_instr
*deref
,
311 nir_deref_compare_result allowed_comparisons
)
313 struct copy_entry
*entry
= NULL
;
314 util_dynarray_foreach(copies
, struct copy_entry
, iter
) {
315 nir_deref_compare_result result
= nir_compare_derefs(iter
->dst
, deref
);
316 if (result
& allowed_comparisons
) {
318 if (result
& nir_derefs_equal_bit
)
320 /* Keep looking in case we have an equal match later in the array. */
326 static struct copy_entry
*
327 lookup_entry_and_kill_aliases(struct util_dynarray
*copies
,
328 nir_deref_instr
*deref
,
331 /* TODO: Take into account the write_mask. */
333 nir_deref_instr
*dst_match
= NULL
;
334 util_dynarray_foreach_reverse(copies
, struct copy_entry
, iter
) {
335 if (!iter
->src
.is_ssa
) {
336 /* If this write aliases the source of some entry, get rid of it */
337 if (nir_compare_derefs(iter
->src
.deref
, deref
) & nir_derefs_may_alias_bit
) {
338 copy_entry_remove(copies
, iter
);
343 nir_deref_compare_result comp
= nir_compare_derefs(iter
->dst
, deref
);
345 if (comp
& nir_derefs_equal_bit
) {
346 /* Removing entries invalidate previous iter pointers, so we'll
347 * collect the matching entry later. Just make sure it is unique.
350 dst_match
= iter
->dst
;
351 } else if (comp
& nir_derefs_may_alias_bit
) {
352 copy_entry_remove(copies
, iter
);
356 struct copy_entry
*entry
= NULL
;
358 util_dynarray_foreach(copies
, struct copy_entry
, iter
) {
359 if (iter
->dst
== dst_match
) {
370 kill_aliases(struct util_dynarray
*copies
,
371 nir_deref_instr
*deref
,
374 /* TODO: Take into account the write_mask. */
376 struct copy_entry
*entry
=
377 lookup_entry_and_kill_aliases(copies
, deref
, write_mask
);
379 copy_entry_remove(copies
, entry
);
382 static struct copy_entry
*
383 get_entry_and_kill_aliases(struct util_dynarray
*copies
,
384 nir_deref_instr
*deref
,
387 /* TODO: Take into account the write_mask. */
389 struct copy_entry
*entry
=
390 lookup_entry_and_kill_aliases(copies
, deref
, write_mask
);
393 entry
= copy_entry_create(copies
, deref
);
399 apply_barrier_for_modes(struct util_dynarray
*copies
,
400 nir_variable_mode modes
)
402 util_dynarray_foreach_reverse(copies
, struct copy_entry
, iter
) {
403 if ((iter
->dst
->mode
& modes
) ||
404 (!iter
->src
.is_ssa
&& (iter
->src
.deref
->mode
& modes
)))
405 copy_entry_remove(copies
, iter
);
410 value_set_from_value(struct value
*value
, const struct value
*from
,
411 unsigned base_index
, unsigned write_mask
)
413 /* We can't have non-zero indexes with non-trivial write masks */
414 assert(base_index
== 0 || write_mask
== 1);
417 /* Clear value if it was being used as non-SSA. */
419 memset(&value
->ssa
, 0, sizeof(value
->ssa
));
420 value
->is_ssa
= true;
421 /* Only overwrite the written components */
422 for (unsigned i
= 0; i
< NIR_MAX_VEC_COMPONENTS
; i
++) {
423 if (write_mask
& (1 << i
)) {
424 value
->ssa
.def
[base_index
+ i
] = from
->ssa
.def
[i
];
425 value
->ssa
.component
[base_index
+ i
] = from
->ssa
.component
[i
];
429 /* Non-ssa stores always write everything */
430 value
->is_ssa
= false;
431 value
->deref
= from
->deref
;
435 /* Try to load a single element of a vector from the copy_entry. If the data
436 * isn't available, just let the original intrinsic do the work.
439 load_element_from_ssa_entry_value(struct copy_prop_var_state
*state
,
440 struct copy_entry
*entry
,
441 nir_builder
*b
, nir_intrinsic_instr
*intrin
,
442 struct value
*value
, unsigned index
)
444 assert(index
< glsl_get_vector_elements(entry
->dst
->type
));
446 /* We don't have the element available, so let the instruction do the work. */
447 if (!entry
->src
.ssa
.def
[index
])
450 b
->cursor
= nir_instr_remove(&intrin
->instr
);
451 intrin
->instr
.block
= NULL
;
453 assert(entry
->src
.ssa
.component
[index
] <
454 entry
->src
.ssa
.def
[index
]->num_components
);
455 nir_ssa_def
*def
= nir_channel(b
, entry
->src
.ssa
.def
[index
],
456 entry
->src
.ssa
.component
[index
]);
458 *value
= (struct value
) {
471 /* Do a "load" from an SSA-based entry return it in "value" as a value with a
472 * single SSA def. Because an entry could reference multiple different SSA
473 * defs, a vecN operation may be inserted to combine them into a single SSA
474 * def before handing it back to the caller. If the load instruction is no
475 * longer needed, it is removed and nir_instr::block is set to NULL. (It is
476 * possible, in some cases, for the load to be used in the vecN operation in
477 * which case it isn't deleted.)
480 load_from_ssa_entry_value(struct copy_prop_var_state
*state
,
481 struct copy_entry
*entry
,
482 nir_builder
*b
, nir_intrinsic_instr
*intrin
,
483 nir_deref_instr
*src
, struct value
*value
)
485 if (is_array_deref_of_vector(src
)) {
486 if (nir_src_is_const(src
->arr
.index
)) {
487 return load_element_from_ssa_entry_value(state
, entry
, b
, intrin
, value
,
488 nir_src_as_uint(src
->arr
.index
));
491 /* An SSA copy_entry for the vector won't help indirect load. */
492 if (glsl_type_is_vector(entry
->dst
->type
)) {
493 assert(entry
->dst
->type
== nir_deref_instr_parent(src
)->type
);
494 /* TODO: If all SSA entries are there, try an if-ladder. */
500 assert(value
->is_ssa
);
502 const struct glsl_type
*type
= entry
->dst
->type
;
503 unsigned num_components
= glsl_get_vector_elements(type
);
505 nir_component_mask_t available
= 0;
506 bool all_same
= true;
507 for (unsigned i
= 0; i
< num_components
; i
++) {
508 if (value
->ssa
.def
[i
])
509 available
|= (1 << i
);
511 if (value
->ssa
.def
[i
] != value
->ssa
.def
[0])
514 if (value
->ssa
.component
[i
] != i
)
519 /* Our work here is done */
520 b
->cursor
= nir_instr_remove(&intrin
->instr
);
521 intrin
->instr
.block
= NULL
;
525 if (available
!= (1 << num_components
) - 1 &&
526 intrin
->intrinsic
== nir_intrinsic_load_deref
&&
527 (available
& nir_ssa_def_components_read(&intrin
->dest
.ssa
)) == 0) {
528 /* If none of the components read are available as SSA values, then we
529 * should just bail. Otherwise, we would end up replacing the uses of
530 * the load_deref a vecN() that just gathers up its components.
535 b
->cursor
= nir_after_instr(&intrin
->instr
);
537 nir_ssa_def
*load_def
=
538 intrin
->intrinsic
== nir_intrinsic_load_deref
? &intrin
->dest
.ssa
: NULL
;
540 bool keep_intrin
= false;
541 nir_ssa_def
*comps
[NIR_MAX_VEC_COMPONENTS
];
542 for (unsigned i
= 0; i
< num_components
; i
++) {
543 if (value
->ssa
.def
[i
]) {
544 comps
[i
] = nir_channel(b
, value
->ssa
.def
[i
], value
->ssa
.component
[i
]);
546 /* We don't have anything for this component in our
547 * list. Just re-use a channel from the load.
549 if (load_def
== NULL
)
550 load_def
= nir_load_deref(b
, entry
->dst
);
552 if (load_def
->parent_instr
== &intrin
->instr
)
555 comps
[i
] = nir_channel(b
, load_def
, i
);
559 nir_ssa_def
*vec
= nir_vec(b
, comps
, num_components
);
560 value_set_ssa_components(value
, vec
, num_components
);
563 /* Removing this instruction should not touch the cursor because we
564 * created the cursor after the intrinsic and have added at least one
565 * instruction (the vec) since then.
567 assert(b
->cursor
.instr
!= &intrin
->instr
);
568 nir_instr_remove(&intrin
->instr
);
569 intrin
->instr
.block
= NULL
;
576 * Specialize the wildcards in a deref chain
578 * This function returns a deref chain identical to \param deref except that
579 * some of its wildcards are replaced with indices from \param specific. The
580 * process is guided by \param guide which references the same type as \param
581 * specific but has the same wildcard array lengths as \param deref.
583 static nir_deref_instr
*
584 specialize_wildcards(nir_builder
*b
,
585 nir_deref_path
*deref
,
586 nir_deref_path
*guide
,
587 nir_deref_path
*specific
)
589 nir_deref_instr
**deref_p
= &deref
->path
[1];
590 nir_deref_instr
**guide_p
= &guide
->path
[1];
591 nir_deref_instr
**spec_p
= &specific
->path
[1];
592 nir_deref_instr
*ret_tail
= deref
->path
[0];
593 for (; *deref_p
; deref_p
++) {
594 if ((*deref_p
)->deref_type
== nir_deref_type_array_wildcard
) {
595 /* This is where things get tricky. We have to search through
596 * the entry deref to find its corresponding wildcard and fill
597 * this slot in with the value from the src.
600 (*guide_p
)->deref_type
!= nir_deref_type_array_wildcard
) {
604 assert(*guide_p
&& *spec_p
);
606 ret_tail
= nir_build_deref_follower(b
, ret_tail
, *spec_p
);
611 ret_tail
= nir_build_deref_follower(b
, ret_tail
, *deref_p
);
618 /* Do a "load" from an deref-based entry return it in "value" as a value. The
619 * deref returned in "value" will always be a fresh copy so the caller can
620 * steal it and assign it to the instruction directly without copying it
624 load_from_deref_entry_value(struct copy_prop_var_state
*state
,
625 struct copy_entry
*entry
,
626 nir_builder
*b
, nir_intrinsic_instr
*intrin
,
627 nir_deref_instr
*src
, struct value
*value
)
631 b
->cursor
= nir_instr_remove(&intrin
->instr
);
633 nir_deref_path entry_dst_path
, src_path
;
634 nir_deref_path_init(&entry_dst_path
, entry
->dst
, state
->mem_ctx
);
635 nir_deref_path_init(&src_path
, src
, state
->mem_ctx
);
637 bool need_to_specialize_wildcards
= false;
638 nir_deref_instr
**entry_p
= &entry_dst_path
.path
[1];
639 nir_deref_instr
**src_p
= &src_path
.path
[1];
640 while (*entry_p
&& *src_p
) {
641 nir_deref_instr
*entry_tail
= *entry_p
++;
642 nir_deref_instr
*src_tail
= *src_p
++;
644 if (src_tail
->deref_type
== nir_deref_type_array
&&
645 entry_tail
->deref_type
== nir_deref_type_array_wildcard
)
646 need_to_specialize_wildcards
= true;
649 /* If the entry deref is longer than the source deref then it refers to a
650 * smaller type and we can't source from it.
652 assert(*entry_p
== NULL
);
654 if (need_to_specialize_wildcards
) {
655 /* The entry has some wildcards that are not in src. This means we need
656 * to construct a new deref based on the entry but using the wildcards
657 * from the source and guided by the entry dst. Oof.
659 nir_deref_path entry_src_path
;
660 nir_deref_path_init(&entry_src_path
, entry
->src
.deref
, state
->mem_ctx
);
661 value
->deref
= specialize_wildcards(b
, &entry_src_path
,
662 &entry_dst_path
, &src_path
);
663 nir_deref_path_finish(&entry_src_path
);
666 /* If our source deref is longer than the entry deref, that's ok because
667 * it just means the entry deref needs to be extended a bit.
670 nir_deref_instr
*src_tail
= *src_p
++;
671 value
->deref
= nir_build_deref_follower(b
, value
->deref
, src_tail
);
674 nir_deref_path_finish(&entry_dst_path
);
675 nir_deref_path_finish(&src_path
);
681 try_load_from_entry(struct copy_prop_var_state
*state
, struct copy_entry
*entry
,
682 nir_builder
*b
, nir_intrinsic_instr
*intrin
,
683 nir_deref_instr
*src
, struct value
*value
)
688 if (entry
->src
.is_ssa
) {
689 return load_from_ssa_entry_value(state
, entry
, b
, intrin
, src
, value
);
691 return load_from_deref_entry_value(state
, entry
, b
, intrin
, src
, value
);
696 invalidate_copies_for_cf_node(struct copy_prop_var_state
*state
,
697 struct util_dynarray
*copies
,
698 nir_cf_node
*cf_node
)
700 struct hash_entry
*ht_entry
= _mesa_hash_table_search(state
->vars_written_map
, cf_node
);
703 struct vars_written
*written
= ht_entry
->data
;
704 if (written
->modes
) {
705 util_dynarray_foreach_reverse(copies
, struct copy_entry
, entry
) {
706 if (entry
->dst
->mode
& written
->modes
)
707 copy_entry_remove(copies
, entry
);
711 hash_table_foreach (written
->derefs
, entry
) {
712 nir_deref_instr
*deref_written
= (nir_deref_instr
*)entry
->key
;
713 kill_aliases(copies
, deref_written
, (uintptr_t)entry
->data
);
718 print_value(struct value
*value
, unsigned num_components
)
720 if (!value
->is_ssa
) {
721 printf(" %s ", glsl_get_type_name(value
->deref
->type
));
722 nir_print_deref(value
->deref
, stdout
);
726 bool same_ssa
= true;
727 for (unsigned i
= 0; i
< num_components
; i
++) {
728 if (value
->ssa
.component
[i
] != i
||
729 (i
> 0 && value
->ssa
.def
[i
- 1] != value
->ssa
.def
[i
])) {
735 printf(" ssa_%d", value
->ssa
.def
[0]->index
);
737 for (int i
= 0; i
< num_components
; i
++) {
738 if (value
->ssa
.def
[i
])
739 printf(" ssa_%d[%u]", value
->ssa
.def
[i
]->index
, value
->ssa
.component
[i
]);
747 print_copy_entry(struct copy_entry
*entry
)
749 printf(" %s ", glsl_get_type_name(entry
->dst
->type
));
750 nir_print_deref(entry
->dst
, stdout
);
753 unsigned num_components
= glsl_get_vector_elements(entry
->dst
->type
);
754 print_value(&entry
->src
, num_components
);
759 dump_instr(nir_instr
*instr
)
762 nir_print_instr(instr
, stdout
);
767 dump_copy_entries(struct util_dynarray
*copies
)
769 util_dynarray_foreach(copies
, struct copy_entry
, iter
)
770 print_copy_entry(iter
);
775 copy_prop_vars_block(struct copy_prop_var_state
*state
,
776 nir_builder
*b
, nir_block
*block
,
777 struct util_dynarray
*copies
)
780 printf("# block%d\n", block
->index
);
781 dump_copy_entries(copies
);
784 nir_foreach_instr_safe(instr
, block
) {
785 if (debug
&& instr
->type
== nir_instr_type_deref
)
788 if (instr
->type
== nir_instr_type_call
) {
789 if (debug
) dump_instr(instr
);
790 apply_barrier_for_modes(copies
, nir_var_shader_out
|
791 nir_var_shader_temp
|
792 nir_var_function_temp
|
796 if (debug
) dump_copy_entries(copies
);
800 if (instr
->type
!= nir_instr_type_intrinsic
)
803 nir_intrinsic_instr
*intrin
= nir_instr_as_intrinsic(instr
);
804 switch (intrin
->intrinsic
) {
805 case nir_intrinsic_control_barrier
:
806 case nir_intrinsic_memory_barrier
:
807 if (debug
) dump_instr(instr
);
809 apply_barrier_for_modes(copies
, nir_var_shader_out
|
815 case nir_intrinsic_memory_barrier_buffer
:
816 if (debug
) dump_instr(instr
);
818 apply_barrier_for_modes(copies
, nir_var_mem_ssbo
|
822 case nir_intrinsic_memory_barrier_shared
:
823 if (debug
) dump_instr(instr
);
825 apply_barrier_for_modes(copies
, nir_var_mem_shared
);
828 case nir_intrinsic_memory_barrier_tcs_patch
:
829 if (debug
) dump_instr(instr
);
831 apply_barrier_for_modes(copies
, nir_var_shader_out
);
834 case nir_intrinsic_scoped_memory_barrier
:
835 if (debug
) dump_instr(instr
);
837 if (nir_intrinsic_memory_semantics(intrin
) & NIR_MEMORY_ACQUIRE
)
838 apply_barrier_for_modes(copies
, nir_intrinsic_memory_modes(intrin
));
841 case nir_intrinsic_emit_vertex
:
842 case nir_intrinsic_emit_vertex_with_counter
:
843 if (debug
) dump_instr(instr
);
845 apply_barrier_for_modes(copies
, nir_var_shader_out
);
848 case nir_intrinsic_load_deref
: {
849 if (debug
) dump_instr(instr
);
851 if (nir_intrinsic_access(intrin
) & ACCESS_VOLATILE
)
854 nir_deref_instr
*src
= nir_src_as_deref(intrin
->src
[0]);
856 /* Direct array_derefs of vectors operate on the vectors (the parent
857 * deref). Indirects will be handled like other derefs.
860 nir_deref_instr
*vec_src
= src
;
861 if (is_array_deref_of_vector(src
) && nir_src_is_const(src
->arr
.index
)) {
862 vec_src
= nir_deref_instr_parent(src
);
863 unsigned vec_comps
= glsl_get_vector_elements(vec_src
->type
);
864 vec_index
= nir_src_as_uint(src
->arr
.index
);
866 /* Loading from an invalid index yields an undef */
867 if (vec_index
>= vec_comps
) {
868 b
->cursor
= nir_instr_remove(instr
);
869 nir_ssa_def
*u
= nir_ssa_undef(b
, 1, intrin
->dest
.ssa
.bit_size
);
870 nir_ssa_def_rewrite_uses(&intrin
->dest
.ssa
, nir_src_for_ssa(u
));
875 struct copy_entry
*src_entry
=
876 lookup_entry_for_deref(copies
, src
, nir_derefs_a_contains_b_bit
);
877 struct value value
= {0};
878 if (try_load_from_entry(state
, src_entry
, b
, intrin
, src
, &value
)) {
880 /* lookup_load has already ensured that we get a single SSA
881 * value that has all of the channels. We just have to do the
882 * rewrite operation. Note for array derefs of vectors, the
885 if (intrin
->instr
.block
) {
886 /* The lookup left our instruction in-place. This means it
887 * must have used it to vec up a bunch of different sources.
888 * We need to be careful when rewriting uses so we don't
889 * rewrite the vecN itself.
891 nir_ssa_def_rewrite_uses_after(&intrin
->dest
.ssa
,
892 nir_src_for_ssa(value
.ssa
.def
[0]),
893 value
.ssa
.def
[0]->parent_instr
);
895 nir_ssa_def_rewrite_uses(&intrin
->dest
.ssa
,
896 nir_src_for_ssa(value
.ssa
.def
[0]));
899 /* We're turning it into a load of a different variable */
900 intrin
->src
[0] = nir_src_for_ssa(&value
.deref
->dest
.ssa
);
902 /* Put it back in again. */
903 nir_builder_instr_insert(b
, instr
);
904 value_set_ssa_components(&value
, &intrin
->dest
.ssa
,
905 intrin
->num_components
);
907 state
->progress
= true;
909 value_set_ssa_components(&value
, &intrin
->dest
.ssa
,
910 intrin
->num_components
);
913 /* Now that we have a value, we're going to store it back so that we
914 * have the right value next time we come looking for it. In order
915 * to do this, we need an exact match, not just something that
916 * contains what we're looking for.
918 struct copy_entry
*entry
=
919 lookup_entry_for_deref(copies
, vec_src
, nir_derefs_equal_bit
);
921 entry
= copy_entry_create(copies
, vec_src
);
923 /* Update the entry with the value of the load. This way
924 * we can potentially remove subsequent loads.
926 value_set_from_value(&entry
->src
, &value
, vec_index
,
927 (1 << intrin
->num_components
) - 1);
931 case nir_intrinsic_store_deref
: {
932 if (debug
) dump_instr(instr
);
934 nir_deref_instr
*dst
= nir_src_as_deref(intrin
->src
[0]);
935 assert(glsl_type_is_vector_or_scalar(dst
->type
));
937 /* Direct array_derefs of vectors operate on the vectors (the parent
938 * deref). Indirects will be handled like other derefs.
941 nir_deref_instr
*vec_dst
= dst
;
942 if (is_array_deref_of_vector(dst
) && nir_src_is_const(dst
->arr
.index
)) {
943 vec_dst
= nir_deref_instr_parent(dst
);
944 unsigned vec_comps
= glsl_get_vector_elements(vec_dst
->type
);
946 vec_index
= nir_src_as_uint(dst
->arr
.index
);
948 /* Storing to an invalid index is a no-op. */
949 if (vec_index
>= vec_comps
) {
950 nir_instr_remove(instr
);
955 if (nir_intrinsic_access(intrin
) & ACCESS_VOLATILE
) {
956 unsigned wrmask
= nir_intrinsic_write_mask(intrin
);
957 kill_aliases(copies
, dst
, wrmask
);
961 struct copy_entry
*entry
=
962 lookup_entry_for_deref(copies
, dst
, nir_derefs_equal_bit
);
963 if (entry
&& value_equals_store_src(&entry
->src
, intrin
)) {
964 /* If we are storing the value from a load of the same var the
965 * store is redundant so remove it.
967 nir_instr_remove(instr
);
969 struct value value
= {0};
970 value_set_ssa_components(&value
, intrin
->src
[1].ssa
,
971 intrin
->num_components
);
972 unsigned wrmask
= nir_intrinsic_write_mask(intrin
);
973 struct copy_entry
*entry
=
974 get_entry_and_kill_aliases(copies
, vec_dst
, wrmask
);
975 value_set_from_value(&entry
->src
, &value
, vec_index
, wrmask
);
981 case nir_intrinsic_copy_deref
: {
982 if (debug
) dump_instr(instr
);
984 nir_deref_instr
*dst
= nir_src_as_deref(intrin
->src
[0]);
985 nir_deref_instr
*src
= nir_src_as_deref(intrin
->src
[1]);
987 /* The copy_deref intrinsic doesn't keep track of num_components, so
990 unsigned num_components
= glsl_get_vector_elements(dst
->type
);
991 unsigned full_mask
= (1 << num_components
) - 1;
993 if ((nir_intrinsic_src_access(intrin
) & ACCESS_VOLATILE
) ||
994 (nir_intrinsic_dst_access(intrin
) & ACCESS_VOLATILE
)) {
995 kill_aliases(copies
, dst
, full_mask
);
999 if (nir_compare_derefs(src
, dst
) & nir_derefs_equal_bit
) {
1000 /* This is a no-op self-copy. Get rid of it */
1001 nir_instr_remove(instr
);
1002 state
->progress
= true;
1006 /* Copy of direct array derefs of vectors are not handled. Just
1007 * invalidate what's written and bail.
1009 if ((is_array_deref_of_vector(src
) && nir_src_is_const(src
->arr
.index
)) ||
1010 (is_array_deref_of_vector(dst
) && nir_src_is_const(dst
->arr
.index
))) {
1011 kill_aliases(copies
, dst
, full_mask
);
1015 struct copy_entry
*src_entry
=
1016 lookup_entry_for_deref(copies
, src
, nir_derefs_a_contains_b_bit
);
1018 if (try_load_from_entry(state
, src_entry
, b
, intrin
, src
, &value
)) {
1019 /* If load works, intrin (the copy_deref) is removed. */
1021 nir_store_deref(b
, dst
, value
.ssa
.def
[0], full_mask
);
1023 /* If this would be a no-op self-copy, don't bother. */
1024 if (nir_compare_derefs(value
.deref
, dst
) & nir_derefs_equal_bit
)
1027 /* Just turn it into a copy of a different deref */
1028 intrin
->src
[1] = nir_src_for_ssa(&value
.deref
->dest
.ssa
);
1030 /* Put it back in again. */
1031 nir_builder_instr_insert(b
, instr
);
1034 state
->progress
= true;
1036 value
= (struct value
) {
1042 nir_variable
*src_var
= nir_deref_instr_get_variable(src
);
1043 if (src_var
&& src_var
->data
.cannot_coalesce
) {
1044 /* The source cannot be coaleseced, which means we can't propagate
1050 struct copy_entry
*dst_entry
=
1051 get_entry_and_kill_aliases(copies
, dst
, full_mask
);
1052 value_set_from_value(&dst_entry
->src
, &value
, 0, full_mask
);
1056 case nir_intrinsic_deref_atomic_add
:
1057 case nir_intrinsic_deref_atomic_imin
:
1058 case nir_intrinsic_deref_atomic_umin
:
1059 case nir_intrinsic_deref_atomic_imax
:
1060 case nir_intrinsic_deref_atomic_umax
:
1061 case nir_intrinsic_deref_atomic_and
:
1062 case nir_intrinsic_deref_atomic_or
:
1063 case nir_intrinsic_deref_atomic_xor
:
1064 case nir_intrinsic_deref_atomic_exchange
:
1065 case nir_intrinsic_deref_atomic_comp_swap
:
1066 if (debug
) dump_instr(instr
);
1068 nir_deref_instr
*dst
= nir_src_as_deref(intrin
->src
[0]);
1069 unsigned num_components
= glsl_get_vector_elements(dst
->type
);
1070 unsigned full_mask
= (1 << num_components
) - 1;
1071 kill_aliases(copies
, dst
, full_mask
);
1075 continue; /* To skip the debug below. */
1078 if (debug
) dump_copy_entries(copies
);
1083 copy_prop_vars_cf_node(struct copy_prop_var_state
*state
,
1084 struct util_dynarray
*copies
,
1085 nir_cf_node
*cf_node
)
1087 switch (cf_node
->type
) {
1088 case nir_cf_node_function
: {
1089 nir_function_impl
*impl
= nir_cf_node_as_function(cf_node
);
1091 struct util_dynarray impl_copies
;
1092 util_dynarray_init(&impl_copies
, state
->mem_ctx
);
1094 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &impl
->body
)
1095 copy_prop_vars_cf_node(state
, &impl_copies
, cf_node
);
1100 case nir_cf_node_block
: {
1101 nir_block
*block
= nir_cf_node_as_block(cf_node
);
1103 nir_builder_init(&b
, state
->impl
);
1104 copy_prop_vars_block(state
, &b
, block
, copies
);
1108 case nir_cf_node_if
: {
1109 nir_if
*if_stmt
= nir_cf_node_as_if(cf_node
);
1111 /* Clone the copies for each branch of the if statement. The idea is
1112 * that they both see the same state of available copies, but do not
1113 * interfere to each other.
1116 struct util_dynarray then_copies
;
1117 util_dynarray_clone(&then_copies
, state
->mem_ctx
, copies
);
1119 struct util_dynarray else_copies
;
1120 util_dynarray_clone(&else_copies
, state
->mem_ctx
, copies
);
1122 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &if_stmt
->then_list
)
1123 copy_prop_vars_cf_node(state
, &then_copies
, cf_node
);
1125 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &if_stmt
->else_list
)
1126 copy_prop_vars_cf_node(state
, &else_copies
, cf_node
);
1128 /* Both branches copies can be ignored, since the effect of running both
1129 * branches was captured in the first pass that collects vars_written.
1132 invalidate_copies_for_cf_node(state
, copies
, cf_node
);
1137 case nir_cf_node_loop
: {
1138 nir_loop
*loop
= nir_cf_node_as_loop(cf_node
);
1140 /* Invalidate before cloning the copies for the loop, since the loop
1141 * body can be executed more than once.
1144 invalidate_copies_for_cf_node(state
, copies
, cf_node
);
1146 struct util_dynarray loop_copies
;
1147 util_dynarray_clone(&loop_copies
, state
->mem_ctx
, copies
);
1149 foreach_list_typed_safe(nir_cf_node
, cf_node
, node
, &loop
->body
)
1150 copy_prop_vars_cf_node(state
, &loop_copies
, cf_node
);
1156 unreachable("Invalid CF node type");
1161 nir_copy_prop_vars_impl(nir_function_impl
*impl
)
1163 void *mem_ctx
= ralloc_context(NULL
);
1166 nir_metadata_require(impl
, nir_metadata_block_index
);
1167 printf("## nir_copy_prop_vars_impl for %s\n", impl
->function
->name
);
1170 struct copy_prop_var_state state
= {
1173 .lin_ctx
= linear_zalloc_parent(mem_ctx
, 0),
1175 .vars_written_map
= _mesa_pointer_hash_table_create(mem_ctx
),
1178 gather_vars_written(&state
, NULL
, &impl
->cf_node
);
1180 copy_prop_vars_cf_node(&state
, NULL
, &impl
->cf_node
);
1182 if (state
.progress
) {
1183 nir_metadata_preserve(impl
, nir_metadata_block_index
|
1184 nir_metadata_dominance
);
1187 impl
->valid_metadata
&= ~nir_metadata_not_properly_reset
;
1191 ralloc_free(mem_ctx
);
1192 return state
.progress
;
1196 nir_opt_copy_prop_vars(nir_shader
*shader
)
1198 bool progress
= false;
1200 nir_foreach_function(function
, shader
) {
1201 if (!function
->impl
)
1203 progress
|= nir_copy_prop_vars_impl(function
->impl
);