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"
29 index_ssa_def_cb(nir_ssa_def
*def
, void *state
)
31 unsigned *index
= (unsigned *) state
;
32 def
->index
= (*index
)++;
37 static nir_deref_instr
*
38 get_deref_for_load_src(nir_src src
, unsigned first_valid_load
)
43 if (src
.ssa
->parent_instr
->type
!= nir_instr_type_intrinsic
)
46 nir_intrinsic_instr
*load
= nir_instr_as_intrinsic(src
.ssa
->parent_instr
);
47 if (load
->intrinsic
!= nir_intrinsic_load_deref
)
50 if (load
->dest
.ssa
.index
< first_valid_load
)
53 return nir_src_as_deref(load
->src
[0]);
57 /* Index into the array of the last copy or -1 for no ongoing copy. */
58 unsigned next_array_idx
;
60 /* Length of the array we're copying */
63 /* Index into the deref path to the array we think is being copied */
64 int src_deref_array_idx
;
65 int dst_deref_array_idx
;
67 /* Deref paths of the first load/store pair or copy */
68 nir_deref_path first_src_path
;
69 nir_deref_path first_dst_path
;
73 match_state_init(struct match_state
*state
)
75 state
->next_array_idx
= 0;
77 state
->src_deref_array_idx
= -1;
78 state
->dst_deref_array_idx
= -1;
82 match_state_finish(struct match_state
*state
)
84 if (state
->next_array_idx
> 0) {
85 nir_deref_path_finish(&state
->first_src_path
);
86 nir_deref_path_finish(&state
->first_dst_path
);
91 match_state_reset(struct match_state
*state
)
93 match_state_finish(state
);
94 match_state_init(state
);
98 try_match_deref(nir_deref_path
*base_path
, int *path_array_idx
,
99 nir_deref_instr
*deref
, int arr_idx
, void *mem_ctx
)
101 nir_deref_path deref_path
;
102 nir_deref_path_init(&deref_path
, deref
, mem_ctx
);
105 for (int i
= 0; ; i
++) {
106 nir_deref_instr
*b
= base_path
->path
[i
];
107 nir_deref_instr
*d
= deref_path
.path
[i
];
108 /* They have to be the same length */
109 if ((b
== NULL
) != (d
== NULL
))
115 /* This can happen if one is a deref_array and the other a wildcard */
116 if (b
->deref_type
!= d
->deref_type
)
119 switch (b
->deref_type
) {
120 case nir_deref_type_var
:
121 if (b
->var
!= d
->var
)
125 case nir_deref_type_array
:
126 assert(b
->arr
.index
.is_ssa
&& d
->arr
.index
.is_ssa
);
127 nir_const_value
*const_b_idx
= nir_src_as_const_value(b
->arr
.index
);
128 nir_const_value
*const_d_idx
= nir_src_as_const_value(d
->arr
.index
);
130 /* If we don't have an index into the path yet or if this entry in
131 * the path is at the array index, see if this is a candidate. We're
132 * looking for an index which is zero in the base deref and arr_idx
133 * in the search deref.
135 if ((*path_array_idx
< 0 || *path_array_idx
== i
) &&
136 const_b_idx
&& const_b_idx
->u32
[0] == 0 &&
137 const_d_idx
&& const_d_idx
->u32
[0] == arr_idx
) {
142 /* We're at the array index but not a candidate */
143 if (*path_array_idx
== i
)
146 /* If we're not the path array index, we must match exactly. We
147 * could probably just compare SSA values and trust in copy
148 * propagation but doing it ourselves means this pass can run a bit
151 if (b
->arr
.index
.ssa
== d
->arr
.index
.ssa
||
152 (const_b_idx
&& const_d_idx
&&
153 const_b_idx
->u32
[0] == const_d_idx
->u32
[0]))
158 case nir_deref_type_array_wildcard
:
161 case nir_deref_type_struct
:
162 if (b
->strct
.index
!= d
->strct
.index
)
167 unreachable("Invalid deref type in a path");
171 /* If we got here without failing, we've matched. However, it isn't an
172 * array match unless we found an altered array index.
174 found
= *path_array_idx
> 0;
177 nir_deref_path_finish(&deref_path
);
181 static nir_deref_instr
*
182 build_wildcard_deref(nir_builder
*b
, nir_deref_path
*path
,
183 unsigned wildcard_idx
)
185 assert(path
->path
[wildcard_idx
]->deref_type
== nir_deref_type_array
);
187 nir_deref_instr
*tail
=
188 nir_build_deref_array_wildcard(b
, path
->path
[wildcard_idx
- 1]);
190 for (unsigned i
= wildcard_idx
+ 1; path
->path
[i
]; i
++)
191 tail
= nir_build_deref_follower(b
, tail
, path
->path
[i
]);
197 opt_find_array_copies_block(nir_builder
*b
, nir_block
*block
,
198 unsigned *num_ssa_defs
, void *mem_ctx
)
200 bool progress
= false;
202 struct match_state s
;
203 match_state_init(&s
);
205 nir_variable
*dst_var
= NULL
;
206 unsigned prev_dst_var_last_write
= *num_ssa_defs
;
207 unsigned dst_var_last_write
= *num_ssa_defs
;
209 nir_foreach_instr(instr
, block
) {
210 /* Index the SSA defs before we do anything else. */
211 nir_foreach_ssa_def(instr
, index_ssa_def_cb
, num_ssa_defs
);
213 if (instr
->type
!= nir_instr_type_intrinsic
)
216 nir_intrinsic_instr
*intrin
= nir_instr_as_intrinsic(instr
);
217 if (intrin
->intrinsic
!= nir_intrinsic_copy_deref
&&
218 intrin
->intrinsic
!= nir_intrinsic_store_deref
)
221 nir_deref_instr
*dst_deref
= nir_src_as_deref(intrin
->src
[0]);
223 /* The destination must be local. If we see a non-local store, we
224 * continue on because it won't affect local stores or read-only
227 if (dst_deref
->mode
!= nir_var_local
)
230 /* We keep track of the SSA indices where the two last-written
231 * variables are written. The prev_dst_var_last_write tells us when
232 * the last store_deref to something other than dst happened. If the
233 * SSA def index from a load is greater than or equal to this number
234 * then we know it happened afterwards and no writes to anything other
235 * than dst occur between the load and the current instruction.
237 if (nir_deref_instr_get_variable(dst_deref
) != dst_var
) {
238 prev_dst_var_last_write
= dst_var_last_write
;
239 dst_var
= nir_deref_instr_get_variable(dst_deref
);
241 dst_var_last_write
= *num_ssa_defs
;
243 /* If it's a full variable store or copy, reset. This will trigger
244 * eventually because we'll fail to match an array element. However,
245 * it's a cheap early-exit.
247 if (dst_deref
->deref_type
== nir_deref_type_var
)
250 nir_deref_instr
*src_deref
;
251 if (intrin
->intrinsic
== nir_intrinsic_copy_deref
) {
252 src_deref
= nir_src_as_deref(intrin
->src
[1]);
254 assert(intrin
->intrinsic
== nir_intrinsic_store_deref
);
255 src_deref
= get_deref_for_load_src(intrin
->src
[1],
256 prev_dst_var_last_write
);
258 /* We can only handle full writes */
259 if (nir_intrinsic_write_mask(intrin
) !=
260 (1 << glsl_get_components(dst_deref
->type
)) - 1)
264 /* If we didn't find a valid src, then we have an unknown store and it
265 * could mess things up.
267 if (src_deref
== NULL
)
270 /* The source must be either local or something that's guaranteed to be
273 const nir_variable_mode read_only_modes
=
274 nir_var_shader_in
| nir_var_uniform
| nir_var_system_value
;
275 if (!(src_deref
->mode
& (nir_var_local
| read_only_modes
)))
278 /* If we don't yet have an active copy, then make this instruction the
281 if (s
.next_array_idx
== 0) {
282 /* We can't combine a copy if there is any chance the source and
283 * destination will end up aliasing. Just bail if they're the same
286 if (nir_deref_instr_get_variable(src_deref
) == dst_var
)
289 /* The load/store pair is enough to guarantee the same bit size and
290 * number of components but a copy_var requires the actual types to
293 if (dst_deref
->type
!= src_deref
->type
)
296 /* The first time we see a store, we don't know which array in the
297 * deref path is the one being copied so we just record the paths
298 * as-is and continue. On the next iteration, it will try to match
299 * based on which array index changed.
301 nir_deref_path_init(&s
.first_dst_path
, dst_deref
, mem_ctx
);
302 nir_deref_path_init(&s
.first_src_path
, src_deref
, mem_ctx
);
303 s
.next_array_idx
= 1;
307 if (!try_match_deref(&s
.first_dst_path
, &s
.dst_deref_array_idx
,
308 dst_deref
, s
.next_array_idx
, mem_ctx
) ||
309 !try_match_deref(&s
.first_src_path
, &s
.src_deref_array_idx
,
310 src_deref
, s
.next_array_idx
, mem_ctx
))
313 if (s
.next_array_idx
== 1) {
314 /* This is our first non-trivial match. We now have indices into
315 * the search paths so we can do a couple more checks.
317 assert(s
.dst_deref_array_idx
> 0 && s
.src_deref_array_idx
> 0);
318 const struct glsl_type
*dst_arr_type
=
319 s
.first_dst_path
.path
[s
.dst_deref_array_idx
- 1]->type
;
320 const struct glsl_type
*src_arr_type
=
321 s
.first_src_path
.path
[s
.src_deref_array_idx
- 1]->type
;
323 assert(glsl_type_is_array(dst_arr_type
) ||
324 glsl_type_is_matrix(dst_arr_type
));
325 assert(glsl_type_is_array(src_arr_type
) ||
326 glsl_type_is_matrix(src_arr_type
));
328 /* They must be the same length */
329 s
.array_len
= glsl_get_length(dst_arr_type
);
330 if (s
.array_len
!= glsl_get_length(src_arr_type
))
336 if (s
.next_array_idx
== s
.array_len
) {
337 /* Hooray, We found a copy! */
338 b
->cursor
= nir_after_instr(instr
);
339 nir_copy_deref(b
, build_wildcard_deref(b
, &s
.first_dst_path
,
340 s
.dst_deref_array_idx
),
341 build_wildcard_deref(b
, &s
.first_src_path
,
342 s
.src_deref_array_idx
));
343 match_state_reset(&s
);
350 match_state_reset(&s
);
357 opt_find_array_copies_impl(nir_function_impl
*impl
)
360 nir_builder_init(&b
, impl
);
362 bool progress
= false;
364 void *mem_ctx
= ralloc_context(NULL
);
366 /* We re-index the SSA defs as we go; it makes it easier to handle
367 * resetting the state machine.
369 unsigned num_ssa_defs
= 0;
371 nir_foreach_block(block
, impl
) {
372 if (opt_find_array_copies_block(&b
, block
, &num_ssa_defs
, mem_ctx
))
376 impl
->ssa_alloc
= num_ssa_defs
;
378 ralloc_free(mem_ctx
);
381 nir_metadata_preserve(impl
, nir_metadata_block_index
|
382 nir_metadata_dominance
);
389 * This peephole optimization looks for a series of load/store_deref or
390 * copy_deref instructions that copy an array from one variable to another and
391 * turns it into a copy_deref that copies the entire array. The pattern it
392 * looks for is extremely specific but it's good enough to pick up on the
393 * input array copies in DXVK and should also be able to pick up the sequence
394 * generated by spirv_to_nir for a OpLoad of a large composite followed by
397 * TODO: Use a hash table approach to support out-of-order and interleaved
401 nir_opt_find_array_copies(nir_shader
*shader
)
403 bool progress
= false;
405 nir_foreach_function(function
, shader
) {
406 if (function
->impl
&& opt_find_array_copies_impl(function
->impl
))