1 /*
2  * Copyright © 2018 Intel Corporation
3  *
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:
10  *
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
13  * Software.
14  *
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
21  * IN THE SOFTWARE.
22  */
23 
24 #include "nir_instr_set.h"
25 #include "nir_search_helpers.h"
26 #include "nir_builder.h"
27 #include "util/u_vector.h"
28 
29 /* Partial redundancy elimination of compares
30  *
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,
34  *
35  *       vec1 32 ssa_111 = flt 0.37, ssa_110.w
36  *       if ssa_111 {
37  *               block block_1:
38  *              vec1 32 ssa_112 = fadd ssa_110.w, -0.37
39  *              ...
40  *
41  * becomes
42  *
43  *       vec1 32 ssa_111 = fadd ssa_110.w, -0.37
44  *       vec1 32 ssa_112 = flt 0.0, ssa_111
45  *       if ssa_112 {
46  *               block block_1:
47  *              ...
48  */
49 
50 struct block_queue {
51    /**
52     * Stack of blocks from the current location in the CFG to the entry point
53     * of the function.
54     *
55     * This is sort of a poor man's dominator tree.
56     */
57    struct exec_list blocks;
58 
59    /** List of freed block_instructions structures that can be reused. */
60    struct exec_list reusable_blocks;
61 };
62 
63 struct block_instructions {
64    struct exec_node node;
65 
66    /**
67     * Set of comparison instructions from the block that are candidates for
68     * being replaced by add instructions.
69     */
70    struct u_vector instructions;
71 };
72 
73 static void
block_queue_init(struct block_queue * bq)74 block_queue_init(struct block_queue *bq)
75 {
76    exec_list_make_empty(&bq->blocks);
77    exec_list_make_empty(&bq->reusable_blocks);
78 }
79 
80 static void
block_queue_finish(struct block_queue * bq)81 block_queue_finish(struct block_queue *bq)
82 {
83    struct block_instructions *n;
84 
85    while ((n = (struct block_instructions *) exec_list_pop_head(&bq->blocks)) != NULL) {
86       u_vector_finish(&n->instructions);
87       free(n);
88    }
89 
90    while ((n = (struct block_instructions *) exec_list_pop_head(&bq->reusable_blocks)) != NULL) {
91       free(n);
92    }
93 }
94 
95 static struct block_instructions *
push_block(struct block_queue * bq)96 push_block(struct block_queue *bq)
97 {
98    struct block_instructions *bi =
99       (struct block_instructions *) exec_list_pop_head(&bq->reusable_blocks);
100 
101    if (bi == NULL) {
102       bi = calloc(1, sizeof(struct block_instructions));
103 
104       if (bi == NULL)
105          return NULL;
106    }
107 
108    if (!u_vector_init(&bi->instructions,
109                       sizeof(nir_alu_instr *),
110                       8 * sizeof(nir_alu_instr *))) {
111       free(bi);
112       return NULL;
113    }
114 
115    exec_list_push_tail(&bq->blocks, &bi->node);
116 
117    return bi;
118 }
119 
120 static void
pop_block(struct block_queue * bq,struct block_instructions * bi)121 pop_block(struct block_queue *bq, struct block_instructions *bi)
122 {
123    u_vector_finish(&bi->instructions);
124    exec_node_remove(&bi->node);
125    exec_list_push_head(&bq->reusable_blocks, &bi->node);
126 }
127 
128 static void
add_instruction_for_block(struct block_instructions * bi,nir_alu_instr * alu)129 add_instruction_for_block(struct block_instructions *bi,
130                           nir_alu_instr *alu)
131 {
132    nir_alu_instr **data =
133       u_vector_add(&bi->instructions);
134 
135    *data = alu;
136 }
137 
138 static void
rewrite_compare_instruction(nir_builder * bld,nir_alu_instr * orig_cmp,nir_alu_instr * orig_add,bool zero_on_left)139 rewrite_compare_instruction(nir_builder *bld, nir_alu_instr *orig_cmp,
140                             nir_alu_instr *orig_add, bool zero_on_left)
141 {
142    void *const mem_ctx = ralloc_parent(orig_cmp);
143 
144    bld->cursor = nir_before_instr(&orig_cmp->instr);
145 
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.
150     *
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.
157     */
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);
160 
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));
164 
165    nir_ssa_def *const zero =
166       nir_imm_floatN_t(bld, 0.0, orig_add->dest.dest.ssa.bit_size);
167 
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);
171 
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
175     * nir_search.c).
176     */
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);
183 
184    nir_builder_instr_insert(bld, &mov_add->instr);
185 
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);
192 
193    nir_builder_instr_insert(bld, &mov_cmp->instr);
194 
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));
199 
200    /* We know these have no more uses because we just rewrote them all, so we
201     * can remove them.
202     */
203    nir_instr_remove(&orig_cmp->instr);
204    nir_instr_remove(&orig_add->instr);
205 }
206 
207 static bool
comparison_pre_block(nir_block * block,struct block_queue * bq,nir_builder * bld)208 comparison_pre_block(nir_block *block, struct block_queue *bq, nir_builder *bld)
209 {
210    bool progress = false;
211 
212    struct block_instructions *bi = push_block(bq);
213    if (bi == NULL)
214       return false;
215 
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.
224     *
225     * After processing the current block, recurse into the blocks dominated by
226     * the current block.
227     */
228    nir_foreach_instr_safe(instr, block) {
229       if (instr->type != nir_instr_type_alu)
230          continue;
231 
232       nir_alu_instr *const alu = nir_instr_as_alu(instr);
233 
234       if (alu->dest.dest.ssa.num_components != 1)
235          continue;
236 
237       if (alu->dest.saturate)
238          continue;
239 
240       static const uint8_t swizzle[NIR_MAX_VEC_COMPONENTS] = {0};
241 
242       switch (alu->op) {
243       case nir_op_fadd: {
244          /* If the instruction is fadd, check it against comparison
245           * instructions that dominate it.
246           */
247          struct block_instructions *b =
248             (struct block_instructions *) exec_list_get_head_raw(&bq->blocks);
249 
250          while (b->node.next != NULL) {
251             nir_alu_instr **a;
252             bool rewrote_compare = false;
253 
254             u_vector_foreach(a, &b->instructions) {
255                nir_alu_instr *const cmp = *a;
256 
257                if (cmp == NULL)
258                   continue;
259 
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.
263                 */
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 +
269                    * -B) or (-B + A)
270                    *
271                    *    A cmp B <=> A + -B cmp 0
272                    */
273                   rewrite_compare_instruction(bld, cmp, alu, false);
274 
275                   *a = NULL;
276                   rewrote_compare = true;
277                   break;
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
283                    * + B).
284                    *
285                    *    A cmp B <=> 0 cmp B + -A
286                    */
287                   rewrite_compare_instruction(bld, cmp, alu, true);
288 
289                   *a = NULL;
290                   rewrote_compare = true;
291                   break;
292                }
293             }
294 
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
300              * in the list.
301              *
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.
308              */
309             if (rewrote_compare) {
310                progress = true;
311                break;
312             }
313 
314             b = (struct block_instructions *) b->node.next;
315          }
316 
317          break;
318       }
319 
320       case nir_op_flt:
321       case nir_op_fge:
322       case nir_op_fneu:
323       case nir_op_feq:
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.
326           */
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);
331 
332          break;
333 
334       default:
335          break;
336       }
337    }
338 
339    for (unsigned i = 0; i < block->num_dom_children; i++) {
340       nir_block *child = block->dom_children[i];
341 
342       if (comparison_pre_block(child, bq, bld))
343          progress = true;
344    }
345 
346    pop_block(bq, bi);
347 
348    return progress;
349 }
350 
351 bool
nir_opt_comparison_pre_impl(nir_function_impl * impl)352 nir_opt_comparison_pre_impl(nir_function_impl *impl)
353 {
354    struct block_queue bq;
355    nir_builder bld;
356 
357    block_queue_init(&bq);
358    nir_builder_init(&bld, impl);
359 
360    nir_metadata_require(impl, nir_metadata_dominance);
361 
362    const bool progress =
363       comparison_pre_block(nir_start_block(impl), &bq, &bld);
364 
365    block_queue_finish(&bq);
366 
367    if (progress) {
368       nir_metadata_preserve(impl, nir_metadata_block_index |
369                                   nir_metadata_dominance);
370    } else {
371       nir_metadata_preserve(impl, nir_metadata_all);
372    }
373 
374    return progress;
375 }
376 
377 bool
nir_opt_comparison_pre(nir_shader * shader)378 nir_opt_comparison_pre(nir_shader *shader)
379 {
380    bool progress = false;
381 
382    nir_foreach_function(function, shader) {
383       if (function->impl)
384          progress |= nir_opt_comparison_pre_impl(function->impl);
385    }
386 
387    return progress;
388 }
389