2 * Copyright © 2014 Connor Abbott
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
24 #include "nir_instr_set.h"
27 #define HASH(hash, data) _mesa_fnv32_1a_accumulate((hash), (data))
30 hash_src(uint32_t hash
, const nir_src
*src
)
33 hash
= HASH(hash
, src
->ssa
);
38 hash_alu_src(uint32_t hash
, const nir_alu_src
*src
, unsigned num_components
)
40 hash
= HASH(hash
, src
->abs
);
41 hash
= HASH(hash
, src
->negate
);
43 for (unsigned i
= 0; i
< num_components
; i
++)
44 hash
= HASH(hash
, src
->swizzle
[i
]);
46 hash
= hash_src(hash
, &src
->src
);
51 hash_alu(uint32_t hash
, const nir_alu_instr
*instr
)
53 hash
= HASH(hash
, instr
->op
);
54 hash
= HASH(hash
, instr
->dest
.dest
.ssa
.num_components
);
55 hash
= HASH(hash
, instr
->dest
.dest
.ssa
.bit_size
);
56 /* We explicitly don't hash instr->dest.dest.exact */
58 if (nir_op_infos
[instr
->op
].algebraic_properties
& NIR_OP_IS_COMMUTATIVE
) {
59 assert(nir_op_infos
[instr
->op
].num_inputs
== 2);
60 uint32_t hash0
= hash_alu_src(hash
, &instr
->src
[0],
61 nir_ssa_alu_instr_src_components(instr
, 0));
62 uint32_t hash1
= hash_alu_src(hash
, &instr
->src
[1],
63 nir_ssa_alu_instr_src_components(instr
, 1));
64 /* For commutative operations, we need some commutative way of
65 * combining the hashes. One option would be to XOR them but that
66 * means that anything with two identical sources will hash to 0 and
67 * that's common enough we probably don't want the guaranteed
68 * collision. Either addition or multiplication will also work.
72 for (unsigned i
= 0; i
< nir_op_infos
[instr
->op
].num_inputs
; i
++) {
73 hash
= hash_alu_src(hash
, &instr
->src
[i
],
74 nir_ssa_alu_instr_src_components(instr
, i
));
82 hash_deref(uint32_t hash
, const nir_deref_instr
*instr
)
84 hash
= HASH(hash
, instr
->deref_type
);
85 hash
= HASH(hash
, instr
->mode
);
86 hash
= HASH(hash
, instr
->type
);
88 if (instr
->deref_type
== nir_deref_type_var
)
89 return HASH(hash
, instr
->var
);
91 hash
= hash_src(hash
, &instr
->parent
);
93 switch (instr
->deref_type
) {
94 case nir_deref_type_struct
:
95 hash
= HASH(hash
, instr
->strct
.index
);
98 case nir_deref_type_array
:
99 case nir_deref_type_ptr_as_array
:
100 hash
= hash_src(hash
, &instr
->arr
.index
);
103 case nir_deref_type_cast
:
104 hash
= HASH(hash
, instr
->cast
.ptr_stride
);
107 case nir_deref_type_var
:
108 case nir_deref_type_array_wildcard
:
113 unreachable("Invalid instruction deref type");
120 hash_load_const(uint32_t hash
, const nir_load_const_instr
*instr
)
122 hash
= HASH(hash
, instr
->def
.num_components
);
124 if (instr
->def
.bit_size
== 1) {
125 for (unsigned i
= 0; i
< instr
->def
.num_components
; i
++) {
126 uint8_t b
= instr
->value
.b
[i
];
127 hash
= HASH(hash
, b
);
130 unsigned size
= instr
->def
.num_components
* (instr
->def
.bit_size
/ 8);
131 hash
= _mesa_fnv32_1a_accumulate_block(hash
, instr
->value
.f32
, size
);
138 cmp_phi_src(const void *data1
, const void *data2
)
140 nir_phi_src
*src1
= *(nir_phi_src
**)data1
;
141 nir_phi_src
*src2
= *(nir_phi_src
**)data2
;
142 return src1
->pred
- src2
->pred
;
146 hash_phi(uint32_t hash
, const nir_phi_instr
*instr
)
148 hash
= HASH(hash
, instr
->instr
.block
);
150 /* sort sources by predecessor, since the order shouldn't matter */
151 unsigned num_preds
= instr
->instr
.block
->predecessors
->entries
;
152 NIR_VLA(nir_phi_src
*, srcs
, num_preds
);
154 nir_foreach_phi_src(src
, instr
) {
158 qsort(srcs
, num_preds
, sizeof(nir_phi_src
*), cmp_phi_src
);
160 for (i
= 0; i
< num_preds
; i
++) {
161 hash
= hash_src(hash
, &srcs
[i
]->src
);
162 hash
= HASH(hash
, srcs
[i
]->pred
);
169 hash_intrinsic(uint32_t hash
, const nir_intrinsic_instr
*instr
)
171 const nir_intrinsic_info
*info
= &nir_intrinsic_infos
[instr
->intrinsic
];
172 hash
= HASH(hash
, instr
->intrinsic
);
174 if (info
->has_dest
) {
175 hash
= HASH(hash
, instr
->dest
.ssa
.num_components
);
176 hash
= HASH(hash
, instr
->dest
.ssa
.bit_size
);
179 hash
= _mesa_fnv32_1a_accumulate_block(hash
, instr
->const_index
,
181 * sizeof(instr
->const_index
[0]));
186 hash_tex(uint32_t hash
, const nir_tex_instr
*instr
)
188 hash
= HASH(hash
, instr
->op
);
189 hash
= HASH(hash
, instr
->num_srcs
);
191 for (unsigned i
= 0; i
< instr
->num_srcs
; i
++) {
192 hash
= HASH(hash
, instr
->src
[i
].src_type
);
193 hash
= hash_src(hash
, &instr
->src
[i
].src
);
196 hash
= HASH(hash
, instr
->coord_components
);
197 hash
= HASH(hash
, instr
->sampler_dim
);
198 hash
= HASH(hash
, instr
->is_array
);
199 hash
= HASH(hash
, instr
->is_shadow
);
200 hash
= HASH(hash
, instr
->is_new_style_shadow
);
201 unsigned component
= instr
->component
;
202 hash
= HASH(hash
, component
);
203 hash
= HASH(hash
, instr
->texture_index
);
204 hash
= HASH(hash
, instr
->texture_array_size
);
205 hash
= HASH(hash
, instr
->sampler_index
);
210 /* Computes a hash of an instruction for use in a hash table. Note that this
211 * will only work for instructions where instr_can_rewrite() returns true, and
212 * it should return identical hashes for two instructions that are the same
213 * according nir_instrs_equal().
217 hash_instr(const void *data
)
219 const nir_instr
*instr
= data
;
220 uint32_t hash
= _mesa_fnv32_1a_offset_bias
;
222 switch (instr
->type
) {
223 case nir_instr_type_alu
:
224 hash
= hash_alu(hash
, nir_instr_as_alu(instr
));
226 case nir_instr_type_deref
:
227 hash
= hash_deref(hash
, nir_instr_as_deref(instr
));
229 case nir_instr_type_load_const
:
230 hash
= hash_load_const(hash
, nir_instr_as_load_const(instr
));
232 case nir_instr_type_phi
:
233 hash
= hash_phi(hash
, nir_instr_as_phi(instr
));
235 case nir_instr_type_intrinsic
:
236 hash
= hash_intrinsic(hash
, nir_instr_as_intrinsic(instr
));
238 case nir_instr_type_tex
:
239 hash
= hash_tex(hash
, nir_instr_as_tex(instr
));
242 unreachable("Invalid instruction type");
249 nir_srcs_equal(nir_src src1
, nir_src src2
)
253 return src1
.ssa
== src2
.ssa
;
261 if ((src1
.reg
.indirect
== NULL
) != (src2
.reg
.indirect
== NULL
))
264 if (src1
.reg
.indirect
) {
265 if (!nir_srcs_equal(*src1
.reg
.indirect
, *src2
.reg
.indirect
))
269 return src1
.reg
.reg
== src2
.reg
.reg
&&
270 src1
.reg
.base_offset
== src2
.reg
.base_offset
;
276 nir_alu_srcs_equal(const nir_alu_instr
*alu1
, const nir_alu_instr
*alu2
,
277 unsigned src1
, unsigned src2
)
279 if (alu1
->src
[src1
].abs
!= alu2
->src
[src2
].abs
||
280 alu1
->src
[src1
].negate
!= alu2
->src
[src2
].negate
)
283 for (unsigned i
= 0; i
< nir_ssa_alu_instr_src_components(alu1
, src1
); i
++) {
284 if (alu1
->src
[src1
].swizzle
[i
] != alu2
->src
[src2
].swizzle
[i
])
288 return nir_srcs_equal(alu1
->src
[src1
].src
, alu2
->src
[src2
].src
);
291 /* Returns "true" if two instructions are equal. Note that this will only
292 * work for the subset of instructions defined by instr_can_rewrite(). Also,
293 * it should only return "true" for instructions that hash_instr() will return
294 * the same hash for (ignoring collisions, of course).
298 nir_instrs_equal(const nir_instr
*instr1
, const nir_instr
*instr2
)
300 if (instr1
->type
!= instr2
->type
)
303 switch (instr1
->type
) {
304 case nir_instr_type_alu
: {
305 nir_alu_instr
*alu1
= nir_instr_as_alu(instr1
);
306 nir_alu_instr
*alu2
= nir_instr_as_alu(instr2
);
308 if (alu1
->op
!= alu2
->op
)
311 /* TODO: We can probably acutally do something more inteligent such
312 * as allowing different numbers and taking a maximum or something
314 if (alu1
->dest
.dest
.ssa
.num_components
!= alu2
->dest
.dest
.ssa
.num_components
)
317 if (alu1
->dest
.dest
.ssa
.bit_size
!= alu2
->dest
.dest
.ssa
.bit_size
)
320 /* We explicitly don't hash instr->dest.dest.exact */
322 if (nir_op_infos
[alu1
->op
].algebraic_properties
& NIR_OP_IS_COMMUTATIVE
) {
323 assert(nir_op_infos
[alu1
->op
].num_inputs
== 2);
324 return (nir_alu_srcs_equal(alu1
, alu2
, 0, 0) &&
325 nir_alu_srcs_equal(alu1
, alu2
, 1, 1)) ||
326 (nir_alu_srcs_equal(alu1
, alu2
, 0, 1) &&
327 nir_alu_srcs_equal(alu1
, alu2
, 1, 0));
329 for (unsigned i
= 0; i
< nir_op_infos
[alu1
->op
].num_inputs
; i
++) {
330 if (!nir_alu_srcs_equal(alu1
, alu2
, i
, i
))
336 case nir_instr_type_deref
: {
337 nir_deref_instr
*deref1
= nir_instr_as_deref(instr1
);
338 nir_deref_instr
*deref2
= nir_instr_as_deref(instr2
);
340 if (deref1
->deref_type
!= deref2
->deref_type
||
341 deref1
->mode
!= deref2
->mode
||
342 deref1
->type
!= deref2
->type
)
345 if (deref1
->deref_type
== nir_deref_type_var
)
346 return deref1
->var
== deref2
->var
;
348 if (!nir_srcs_equal(deref1
->parent
, deref2
->parent
))
351 switch (deref1
->deref_type
) {
352 case nir_deref_type_struct
:
353 if (deref1
->strct
.index
!= deref2
->strct
.index
)
357 case nir_deref_type_array
:
358 case nir_deref_type_ptr_as_array
:
359 if (!nir_srcs_equal(deref1
->arr
.index
, deref2
->arr
.index
))
363 case nir_deref_type_cast
:
364 if (deref1
->cast
.ptr_stride
!= deref2
->cast
.ptr_stride
)
368 case nir_deref_type_var
:
369 case nir_deref_type_array_wildcard
:
374 unreachable("Invalid instruction deref type");
378 case nir_instr_type_tex
: {
379 nir_tex_instr
*tex1
= nir_instr_as_tex(instr1
);
380 nir_tex_instr
*tex2
= nir_instr_as_tex(instr2
);
382 if (tex1
->op
!= tex2
->op
)
385 if (tex1
->num_srcs
!= tex2
->num_srcs
)
387 for (unsigned i
= 0; i
< tex1
->num_srcs
; i
++) {
388 if (tex1
->src
[i
].src_type
!= tex2
->src
[i
].src_type
||
389 !nir_srcs_equal(tex1
->src
[i
].src
, tex2
->src
[i
].src
)) {
394 if (tex1
->coord_components
!= tex2
->coord_components
||
395 tex1
->sampler_dim
!= tex2
->sampler_dim
||
396 tex1
->is_array
!= tex2
->is_array
||
397 tex1
->is_shadow
!= tex2
->is_shadow
||
398 tex1
->is_new_style_shadow
!= tex2
->is_new_style_shadow
||
399 tex1
->component
!= tex2
->component
||
400 tex1
->texture_index
!= tex2
->texture_index
||
401 tex1
->texture_array_size
!= tex2
->texture_array_size
||
402 tex1
->sampler_index
!= tex2
->sampler_index
) {
408 case nir_instr_type_load_const
: {
409 nir_load_const_instr
*load1
= nir_instr_as_load_const(instr1
);
410 nir_load_const_instr
*load2
= nir_instr_as_load_const(instr2
);
412 if (load1
->def
.num_components
!= load2
->def
.num_components
)
415 if (load1
->def
.bit_size
!= load2
->def
.bit_size
)
418 if (load1
->def
.bit_size
== 1) {
419 unsigned size
= load1
->def
.num_components
* sizeof(bool);
420 return memcmp(load1
->value
.b
, load2
->value
.b
, size
) == 0;
422 unsigned size
= load1
->def
.num_components
* (load1
->def
.bit_size
/ 8);
423 return memcmp(load1
->value
.f32
, load2
->value
.f32
, size
) == 0;
426 case nir_instr_type_phi
: {
427 nir_phi_instr
*phi1
= nir_instr_as_phi(instr1
);
428 nir_phi_instr
*phi2
= nir_instr_as_phi(instr2
);
430 if (phi1
->instr
.block
!= phi2
->instr
.block
)
433 nir_foreach_phi_src(src1
, phi1
) {
434 nir_foreach_phi_src(src2
, phi2
) {
435 if (src1
->pred
== src2
->pred
) {
436 if (!nir_srcs_equal(src1
->src
, src2
->src
))
446 case nir_instr_type_intrinsic
: {
447 nir_intrinsic_instr
*intrinsic1
= nir_instr_as_intrinsic(instr1
);
448 nir_intrinsic_instr
*intrinsic2
= nir_instr_as_intrinsic(instr2
);
449 const nir_intrinsic_info
*info
=
450 &nir_intrinsic_infos
[intrinsic1
->intrinsic
];
452 if (intrinsic1
->intrinsic
!= intrinsic2
->intrinsic
||
453 intrinsic1
->num_components
!= intrinsic2
->num_components
)
456 if (info
->has_dest
&& intrinsic1
->dest
.ssa
.num_components
!=
457 intrinsic2
->dest
.ssa
.num_components
)
460 if (info
->has_dest
&& intrinsic1
->dest
.ssa
.bit_size
!=
461 intrinsic2
->dest
.ssa
.bit_size
)
464 for (unsigned i
= 0; i
< info
->num_srcs
; i
++) {
465 if (!nir_srcs_equal(intrinsic1
->src
[i
], intrinsic2
->src
[i
]))
469 for (unsigned i
= 0; i
< info
->num_indices
; i
++) {
470 if (intrinsic1
->const_index
[i
] != intrinsic2
->const_index
[i
])
476 case nir_instr_type_call
:
477 case nir_instr_type_jump
:
478 case nir_instr_type_ssa_undef
:
479 case nir_instr_type_parallel_copy
:
481 unreachable("Invalid instruction type");
484 unreachable("All cases in the above switch should return");
488 src_is_ssa(nir_src
*src
, void *data
)
495 dest_is_ssa(nir_dest
*dest
, void *data
)
501 /* This function determines if uses of an instruction can safely be rewritten
502 * to use another identical instruction instead. Note that this function must
503 * be kept in sync with hash_instr() and nir_instrs_equal() -- only
504 * instructions that pass this test will be handed on to those functions, and
505 * conversely they must handle everything that this function returns true for.
509 instr_can_rewrite(nir_instr
*instr
)
511 /* We only handle SSA. */
512 if (!nir_foreach_dest(instr
, dest_is_ssa
, NULL
) ||
513 !nir_foreach_src(instr
, src_is_ssa
, NULL
))
516 switch (instr
->type
) {
517 case nir_instr_type_alu
:
518 case nir_instr_type_deref
:
519 case nir_instr_type_tex
:
520 case nir_instr_type_load_const
:
521 case nir_instr_type_phi
:
523 case nir_instr_type_intrinsic
: {
524 const nir_intrinsic_info
*info
=
525 &nir_intrinsic_infos
[nir_instr_as_intrinsic(instr
)->intrinsic
];
526 return (info
->flags
& NIR_INTRINSIC_CAN_ELIMINATE
) &&
527 (info
->flags
& NIR_INTRINSIC_CAN_REORDER
);
529 case nir_instr_type_call
:
530 case nir_instr_type_jump
:
531 case nir_instr_type_ssa_undef
:
533 case nir_instr_type_parallel_copy
:
535 unreachable("Invalid instruction type");
542 nir_instr_get_dest_ssa_def(nir_instr
*instr
)
544 switch (instr
->type
) {
545 case nir_instr_type_alu
:
546 assert(nir_instr_as_alu(instr
)->dest
.dest
.is_ssa
);
547 return &nir_instr_as_alu(instr
)->dest
.dest
.ssa
;
548 case nir_instr_type_deref
:
549 assert(nir_instr_as_deref(instr
)->dest
.is_ssa
);
550 return &nir_instr_as_deref(instr
)->dest
.ssa
;
551 case nir_instr_type_load_const
:
552 return &nir_instr_as_load_const(instr
)->def
;
553 case nir_instr_type_phi
:
554 assert(nir_instr_as_phi(instr
)->dest
.is_ssa
);
555 return &nir_instr_as_phi(instr
)->dest
.ssa
;
556 case nir_instr_type_intrinsic
:
557 assert(nir_instr_as_intrinsic(instr
)->dest
.is_ssa
);
558 return &nir_instr_as_intrinsic(instr
)->dest
.ssa
;
559 case nir_instr_type_tex
:
560 assert(nir_instr_as_tex(instr
)->dest
.is_ssa
);
561 return &nir_instr_as_tex(instr
)->dest
.ssa
;
563 unreachable("We never ask for any of these");
568 cmp_func(const void *data1
, const void *data2
)
570 return nir_instrs_equal(data1
, data2
);
574 nir_instr_set_create(void *mem_ctx
)
576 return _mesa_set_create(mem_ctx
, hash_instr
, cmp_func
);
580 nir_instr_set_destroy(struct set
*instr_set
)
582 _mesa_set_destroy(instr_set
, NULL
);
586 nir_instr_set_add_or_rewrite(struct set
*instr_set
, nir_instr
*instr
)
588 if (!instr_can_rewrite(instr
))
591 struct set_entry
*entry
= _mesa_set_search(instr_set
, instr
);
593 nir_ssa_def
*def
= nir_instr_get_dest_ssa_def(instr
);
594 nir_instr
*match
= (nir_instr
*) entry
->key
;
595 nir_ssa_def
*new_def
= nir_instr_get_dest_ssa_def(match
);
597 /* It's safe to replace an exact instruction with an inexact one as
598 * long as we make it exact. If we got here, the two instructions are
599 * exactly identical in every other way so, once we've set the exact
600 * bit, they are the same.
602 if (instr
->type
== nir_instr_type_alu
&& nir_instr_as_alu(instr
)->exact
)
603 nir_instr_as_alu(match
)->exact
= true;
605 nir_ssa_def_rewrite_uses(def
, nir_src_for_ssa(new_def
));
609 _mesa_set_add(instr_set
, instr
);
614 nir_instr_set_remove(struct set
*instr_set
, nir_instr
*instr
)
616 if (!instr_can_rewrite(instr
))
619 struct set_entry
*entry
= _mesa_set_search(instr_set
, instr
);
621 _mesa_set_remove(instr_set
, entry
);