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
24 #include "nir_instr_set.h"
25 #include "nir_search_helpers.h"
26 #include "nir_builder.h"
27 #include "util/u_vector.h"
29 /* Partial redundancy elimination of compares
31 * Seaches for comparisons of the form 'a cmp b' that dominate arithmetic
32 * instructions like 'b - a'. The comparison is replaced by the arithmetic
33 * instruction, and the result is compared with zero. For example,
35 * vec1 32 ssa_111 = flt 0.37, ssa_110.w
38 * vec1 32 ssa_112 = fadd ssa_110.w, -0.37
43 * vec1 32 ssa_111 = fadd ssa_110.w, -0.37
44 * vec1 32 ssa_112 = flt 0.0, ssa_111
52 * Stack of blocks from the current location in the CFG to the entry point
55 * This is sort of a poor man's dominator tree.
57 struct exec_list blocks
;
59 /** List of freed block_instructions structures that can be reused. */
60 struct exec_list reusable_blocks
;
63 struct block_instructions
{
64 struct exec_node node
;
67 * Set of comparison instructions from the block that are candidates for
68 * being replaced by add instructions.
70 struct u_vector instructions
;
74 block_queue_init(struct block_queue
*bq
)
76 exec_list_make_empty(&bq
->blocks
);
77 exec_list_make_empty(&bq
->reusable_blocks
);
81 block_queue_finish(struct block_queue
*bq
)
83 struct block_instructions
*n
;
85 while ((n
= (struct block_instructions
*) exec_list_pop_head(&bq
->blocks
)) != NULL
) {
86 u_vector_finish(&n
->instructions
);
90 while ((n
= (struct block_instructions
*) exec_list_pop_head(&bq
->reusable_blocks
)) != NULL
) {
95 static struct block_instructions
*
96 push_block(struct block_queue
*bq
)
98 struct block_instructions
*bi
=
99 (struct block_instructions
*) exec_list_pop_head(&bq
->reusable_blocks
);
102 bi
= calloc(1, sizeof(struct block_instructions
));
108 if (!u_vector_init(&bi
->instructions
,
109 sizeof(nir_alu_instr
*),
110 8 * sizeof(nir_alu_instr
*))) {
115 exec_list_push_tail(&bq
->blocks
, &bi
->node
);
121 pop_block(struct block_queue
*bq
, struct block_instructions
*bi
)
123 u_vector_finish(&bi
->instructions
);
124 exec_node_remove(&bi
->node
);
125 exec_list_push_head(&bq
->reusable_blocks
, &bi
->node
);
129 add_instruction_for_block(struct block_instructions
*bi
,
132 nir_alu_instr
**data
=
133 u_vector_add(&bi
->instructions
);
139 rewrite_compare_instruction(nir_builder
*bld
, nir_alu_instr
*orig_cmp
,
140 nir_alu_instr
*orig_add
, bool zero_on_left
)
142 void *const mem_ctx
= ralloc_parent(orig_cmp
);
144 bld
->cursor
= nir_before_instr(&orig_cmp
->instr
);
146 /* This is somewhat tricky. The compare instruction may be something like
147 * (fcmp, a, b) while the add instruction is something like (fadd, fneg(a),
148 * b). This is problematic because the SSA value for the fneg(a) may not
149 * exist yet at the compare instruction.
151 * We fabricate the operands of the new add. This is done using
152 * information provided by zero_on_left. If zero_on_left is true, we know
153 * the resulting compare instruction is (fcmp, 0.0, (fadd, x, y)). If the
154 * original compare instruction was (fcmp, a, b), x = b and y = -a. If
155 * zero_on_left is false, the resulting compare instruction is (fcmp,
156 * (fadd, x, y), 0.0) and x = a and y = -b.
158 nir_ssa_def
*const a
= nir_ssa_for_alu_src(bld
, orig_cmp
, 0);
159 nir_ssa_def
*const b
= nir_ssa_for_alu_src(bld
, orig_cmp
, 1);
161 nir_ssa_def
*const fadd
= zero_on_left
162 ? nir_fadd(bld
, b
, nir_fneg(bld
, a
))
163 : nir_fadd(bld
, a
, nir_fneg(bld
, b
));
165 nir_ssa_def
*const zero
=
166 nir_imm_floatN_t(bld
, 0.0, orig_add
->dest
.dest
.ssa
.bit_size
);
168 nir_ssa_def
*const cmp
= zero_on_left
169 ? nir_build_alu(bld
, orig_cmp
->op
, zero
, fadd
, NULL
, NULL
)
170 : nir_build_alu(bld
, orig_cmp
->op
, fadd
, zero
, NULL
, NULL
);
172 /* Generating extra moves of the results is the easy way to make sure the
173 * writemasks match the original instructions. Later optimization passes
174 * will clean these up. This is similar to nir_replace_instr (in
177 nir_alu_instr
*mov_add
= nir_alu_instr_create(mem_ctx
, nir_op_mov
);
178 mov_add
->dest
.write_mask
= orig_add
->dest
.write_mask
;
179 nir_ssa_dest_init(&mov_add
->instr
, &mov_add
->dest
.dest
,
180 orig_add
->dest
.dest
.ssa
.num_components
,
181 orig_add
->dest
.dest
.ssa
.bit_size
, NULL
);
182 mov_add
->src
[0].src
= nir_src_for_ssa(fadd
);
184 nir_builder_instr_insert(bld
, &mov_add
->instr
);
186 nir_alu_instr
*mov_cmp
= nir_alu_instr_create(mem_ctx
, nir_op_mov
);
187 mov_cmp
->dest
.write_mask
= orig_cmp
->dest
.write_mask
;
188 nir_ssa_dest_init(&mov_cmp
->instr
, &mov_cmp
->dest
.dest
,
189 orig_cmp
->dest
.dest
.ssa
.num_components
,
190 orig_cmp
->dest
.dest
.ssa
.bit_size
, NULL
);
191 mov_cmp
->src
[0].src
= nir_src_for_ssa(cmp
);
193 nir_builder_instr_insert(bld
, &mov_cmp
->instr
);
195 nir_ssa_def_rewrite_uses(&orig_cmp
->dest
.dest
.ssa
,
196 nir_src_for_ssa(&mov_cmp
->dest
.dest
.ssa
));
197 nir_ssa_def_rewrite_uses(&orig_add
->dest
.dest
.ssa
,
198 nir_src_for_ssa(&mov_add
->dest
.dest
.ssa
));
200 /* We know these have no more uses because we just rewrote them all, so we
203 nir_instr_remove(&orig_cmp
->instr
);
204 nir_instr_remove(&orig_add
->instr
);
208 comparison_pre_block(nir_block
*block
, struct block_queue
*bq
, nir_builder
*bld
)
210 bool progress
= false;
212 struct block_instructions
*bi
= push_block(bq
);
216 /* Starting with the current block, examine each instruction. If the
217 * instruction is a comparison that matches the '±a cmp ±b' pattern, add it
218 * to the block_instructions::instructions set. If the instruction is an
219 * add instruction, walk up the block queue looking at the stored
220 * instructions. If a matching comparison is found, move the addition and
221 * replace the comparison with a different comparison based on the result
222 * of the addition. All of the blocks in the queue are guaranteed to be
223 * dominators of the current block.
225 * After processing the current block, recurse into the blocks dominated by
228 nir_foreach_instr_safe(instr
, block
) {
229 if (instr
->type
!= nir_instr_type_alu
)
232 nir_alu_instr
*const alu
= nir_instr_as_alu(instr
);
234 if (alu
->dest
.dest
.ssa
.num_components
!= 1)
237 if (alu
->dest
.saturate
)
240 static const uint8_t swizzle
[4] = { 0, 0, 0, 0 };
244 /* If the instruction is fadd, check it against comparison
245 * instructions that dominate it.
247 struct block_instructions
*b
=
248 (struct block_instructions
*) exec_list_get_head_raw(&bq
->blocks
);
250 while (b
->node
.next
!= NULL
) {
252 bool rewrote_compare
= false;
254 u_vector_foreach(a
, &b
->instructions
) {
255 nir_alu_instr
*const cmp
= *a
;
260 /* The operands of both instructions are, with some liberty,
261 * commutative. Check all four permutations. The third and
262 * fourth permutations are negations of the first two.
264 if ((nir_alu_srcs_equal(cmp
, alu
, 0, 0) &&
265 nir_alu_srcs_negative_equal(cmp
, alu
, 1, 1)) ||
266 (nir_alu_srcs_equal(cmp
, alu
, 0, 1) &&
267 nir_alu_srcs_negative_equal(cmp
, alu
, 1, 0))) {
268 /* These are the cases where (A cmp B) matches either (A +
271 * A cmp B <=> A + -B cmp 0
273 rewrite_compare_instruction(bld
, cmp
, alu
, false);
276 rewrote_compare
= true;
278 } else if ((nir_alu_srcs_equal(cmp
, alu
, 1, 0) &&
279 nir_alu_srcs_negative_equal(cmp
, alu
, 0, 1)) ||
280 (nir_alu_srcs_equal(cmp
, alu
, 1, 1) &&
281 nir_alu_srcs_negative_equal(cmp
, alu
, 0, 0))) {
282 /* This is the case where (A cmp B) matches (B + -A) or (-A
285 * A cmp B <=> 0 cmp B + -A
287 rewrite_compare_instruction(bld
, cmp
, alu
, true);
290 rewrote_compare
= true;
295 /* Bail after a compare in the most dominating block is found.
296 * This is necessary because 'alu' has been removed from the
297 * instruction stream. Should there be a matching compare in
298 * another block, calling rewrite_compare_instruction again will
299 * try to operate on a node that is not in the list as if it were
302 * FINISHME: There may be opportunity for additional optimization
303 * here. I discovered this problem due to a shader in Guacamelee.
304 * It may be possible to rewrite the matching compares that are
305 * encountered later to reuse the result from the compare that was
306 * first rewritten. It's also possible that this is just taken
307 * care of by calling the optimization pass repeatedly.
309 if (rewrote_compare
) {
314 b
= (struct block_instructions
*) b
->node
.next
;
324 /* If the instruction is a comparison that is used by an if-statement
325 * and neither operand is immediate value 0, add it to the set.
327 if (is_used_by_if(alu
) &&
328 is_not_const_zero(NULL
, alu
, 0, 1, swizzle
) &&
329 is_not_const_zero(NULL
, alu
, 1, 1, swizzle
))
330 add_instruction_for_block(bi
, alu
);
339 for (unsigned i
= 0; i
< block
->num_dom_children
; i
++) {
340 nir_block
*child
= block
->dom_children
[i
];
342 if (comparison_pre_block(child
, bq
, bld
))
352 nir_opt_comparison_pre_impl(nir_function_impl
*impl
)
354 struct block_queue bq
;
357 block_queue_init(&bq
);
358 nir_builder_init(&bld
, impl
);
360 nir_metadata_require(impl
, nir_metadata_dominance
);
362 const bool progress
=
363 comparison_pre_block(nir_start_block(impl
), &bq
, &bld
);
365 block_queue_finish(&bq
);
368 nir_metadata_preserve(impl
, nir_metadata_block_index
|
369 nir_metadata_dominance
);
375 nir_opt_comparison_pre(nir_shader
*shader
)
377 bool progress
= false;
379 nir_foreach_function(function
, shader
) {
381 progress
|= nir_opt_comparison_pre_impl(function
->impl
);