2 * Copyright (C) 2019 Collabora, Ltd.
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 FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 #include "midgard_ops.h"
27 /* Lowers the invert field on instructions to a dedicated inot (inor)
28 * instruction instead, as invert is not always supported natively by the
32 midgard_lower_invert(compiler_context
*ctx
, midgard_block
*block
)
34 mir_foreach_instr_in_block_safe(block
, ins
) {
35 if (ins
->type
!= TAG_ALU_4
) continue;
36 if (!ins
->invert
) continue;
38 unsigned temp
= make_compiler_temp(ctx
);
40 midgard_instruction
not = {
43 .src
= { temp
, ~0, ~0, ~0 },
44 .swizzle
= SWIZZLE_IDENTITY
,
46 .has_inline_constant
= true,
48 .op
= midgard_alu_op_inor
,
50 .reg_mode
= midgard_reg_mode_32
,
51 .dest_override
= midgard_dest_override_none
,
52 .outmod
= midgard_outmod_int_wrap
58 mir_insert_instruction_before(ctx
, mir_next_op(ins
), not);
62 /* Propagate the .not up to the source */
65 midgard_opt_not_propagate(compiler_context
*ctx
, midgard_block
*block
)
67 bool progress
= false;
69 mir_foreach_instr_in_block_safe(block
, ins
) {
70 if (ins
->type
!= TAG_ALU_4
) continue;
71 if (ins
->alu
.op
!= midgard_alu_op_imov
) continue;
72 if (!ins
->invert
) continue;
73 if (mir_nontrivial_source2_mod_simple(ins
)) continue;
74 if (ins
->src
[1] & IS_REG
) continue;
76 /* Is it beneficial to propagate? */
77 if (!mir_single_use(ctx
, ins
->src
[1])) continue;
79 /* We found an imov.not, propagate the invert back */
81 mir_foreach_instr_in_block_from_rev(block
, v
, mir_prev_op(ins
)) {
82 if (v
->dest
!= ins
->src
[1]) continue;
83 if (v
->type
!= TAG_ALU_4
) break;
85 v
->invert
= !v
->invert
;
95 /* With that lowering out of the way, we can focus on more interesting
96 * optimizations. One easy one is fusing inverts into bitwise operations:
104 mir_is_bitwise(midgard_instruction
*ins
)
106 switch (ins
->alu
.op
) {
107 case midgard_alu_op_iand
:
108 case midgard_alu_op_ior
:
109 case midgard_alu_op_ixor
:
117 mir_is_inverted_bitwise(midgard_instruction
*ins
)
119 switch (ins
->alu
.op
) {
120 case midgard_alu_op_inand
:
121 case midgard_alu_op_inor
:
122 case midgard_alu_op_inxor
:
129 static midgard_alu_op
130 mir_invert_op(midgard_alu_op op
)
133 case midgard_alu_op_iand
:
134 return midgard_alu_op_inand
;
135 case midgard_alu_op_inand
:
136 return midgard_alu_op_iand
;
137 case midgard_alu_op_ior
:
138 return midgard_alu_op_inor
;
139 case midgard_alu_op_inor
:
140 return midgard_alu_op_ior
;
141 case midgard_alu_op_ixor
:
142 return midgard_alu_op_inxor
;
143 case midgard_alu_op_inxor
:
144 return midgard_alu_op_ixor
;
146 unreachable("Op not invertible");
150 static midgard_alu_op
151 mir_demorgan_op(midgard_alu_op op
)
154 case midgard_alu_op_iand
:
155 return midgard_alu_op_inor
;
156 case midgard_alu_op_ior
:
157 return midgard_alu_op_inand
;
159 unreachable("Op not De Morgan-able");
163 static midgard_alu_op
164 mir_notright_op(midgard_alu_op op
)
167 case midgard_alu_op_iand
:
168 return midgard_alu_op_iandnot
;
169 case midgard_alu_op_ior
:
170 return midgard_alu_op_iornot
;
172 unreachable("Op not right able");
177 midgard_opt_fuse_dest_invert(compiler_context
*ctx
, midgard_block
*block
)
179 bool progress
= false;
181 mir_foreach_instr_in_block_safe(block
, ins
) {
182 /* Search for inverted bitwise */
183 if (ins
->type
!= TAG_ALU_4
) continue;
184 if (!mir_is_bitwise(ins
) && !mir_is_inverted_bitwise(ins
)) continue;
185 if (!ins
->invert
) continue;
187 ins
->alu
.op
= mir_invert_op(ins
->alu
.op
);
195 /* Next up, we can fuse inverts into the sources of bitwise ops:
197 * ~a & b = b & ~a = iandnot(b, a)
198 * a & ~b = iandnot(a, b)
199 * ~a & ~b = ~(a | b) = inor(a, b)
201 * ~a | b = b | ~a = iornot(b, a)
202 * a | ~b = iornot(a, b)
203 * ~a | ~b = ~(a & b) = inand(a, b)
205 * ~a ^ b = ~(a ^ b) = inxor(a, b)
206 * a ^ ~b = ~(a ^ b) + inxor(a, b)
208 * ~(a ^ b) = inxor(a, b)
212 mir_strip_inverted(compiler_context
*ctx
, unsigned node
)
214 if (node
>= SSA_FIXED_MINIMUM
)
217 /* Strips and returns the invert off a node */
218 mir_foreach_instr_global(ctx
, ins
) {
219 if (ins
->compact_branch
) continue;
220 if (ins
->dest
!= node
) continue;
222 bool status
= ins
->invert
;
227 unreachable("Invalid node stripped");
231 is_ssa_or_constant(unsigned node
)
233 return !(node
& IS_REG
) || (node
== SSA_FIXED_REGISTER(26));
237 midgard_opt_fuse_src_invert(compiler_context
*ctx
, midgard_block
*block
)
239 bool progress
= false;
241 mir_foreach_instr_in_block_safe(block
, ins
) {
242 /* Search for inverted bitwise */
243 if (ins
->type
!= TAG_ALU_4
) continue;
244 if (!mir_is_bitwise(ins
)) continue;
246 if (!is_ssa_or_constant(ins
->src
[0])) continue;
247 if (!is_ssa_or_constant(ins
->src
[1])) continue;
248 if (!mir_single_use(ctx
, ins
->src
[0])) continue;
249 if (!ins
->has_inline_constant
&& !mir_single_use(ctx
, ins
->src
[1])) continue;
251 bool not_a
= mir_strip_inverted(ctx
, ins
->src
[0]);
253 ins
->has_inline_constant
? false :
254 mir_strip_inverted(ctx
, ins
->src
[1]);
256 /* Edge case: if src0 == src1, it'll've been stripped */
257 if ((ins
->src
[0] == ins
->src
[1]) && !ins
->has_inline_constant
)
260 progress
|= (not_a
|| not_b
);
263 if (!(not_a
|| not_b
)) continue;
265 bool both
= not_a
&& not_b
;
266 bool left
= not_a
&& !not_b
;
267 bool right
= !not_a
&& not_b
;
269 /* No-op, but we got to strip the inverts */
270 if (both
&& ins
->alu
.op
== midgard_alu_op_ixor
)
274 ins
->alu
.op
= mir_demorgan_op(ins
->alu
.op
);
275 } else if (right
|| (left
&& !ins
->has_inline_constant
)) {
276 /* Commute arguments */
280 ins
->alu
.op
= mir_notright_op(ins
->alu
.op
);
281 } else if (left
&& ins
->has_inline_constant
) {
282 /* Some special transformations:
284 * ~A & c = ~(~(~A) | (~c)) = ~(A | ~c) = inor(A, ~c)
285 * ~A | c = ~(~(~A) & (~c)) = ~(A & ~c) = inand(A, ~c)
288 ins
->alu
.op
= mir_demorgan_op(ins
->alu
.op
);
289 ins
->inline_constant
= ~ins
->inline_constant
;
296 /* Optimizes a .not away when used as the source of a conditional select:
298 * csel(a, b, c) = { b if a, c if !a }
299 * csel(!a, b, c) = { b if !a, c if !(!a) } = { c if a, b if !a } = csel(a, c, b)
300 * csel(!a, b, c) = csel(a, c, b)
304 midgard_opt_csel_invert(compiler_context
*ctx
, midgard_block
*block
)
306 bool progress
= false;
308 mir_foreach_instr_in_block_safe(block
, ins
) {
309 if (ins
->type
!= TAG_ALU_4
) continue;
310 if (!OP_IS_CSEL(ins
->alu
.op
)) continue;
311 if (!mir_single_use(ctx
, ins
->src
[2])) continue;
312 if (!mir_strip_inverted(ctx
, ins
->src
[2])) continue;
323 mir_is_inverted(compiler_context
*ctx
, unsigned node
)
325 mir_foreach_instr_global(ctx
, ins
) {
326 if (ins
->compact_branch
) continue;
327 if (ins
->dest
!= node
) continue;
332 unreachable("Invalid node passed");
337 /* Optimizes comparisions which invert both arguments
340 * ieq(not(a), not(b)) = ieq(a, b)
341 * ine(not(a), not(b)) = ine(a, b)
343 * This does apply for ilt and ile if we flip the argument order:
344 * Proofs below provided by Alyssa Rosenzweig
348 * ( not(A) <= not(B) ) <=> ( −(A+1) <= −(B+1) )
352 * On unsigned comparisons (ult / ule) we can perform the same optimization
353 * with the additional restriction that the source registers must
354 * have the same size.
356 * TODO: We may not need them to be of the same size, if we can
357 * prove that they are the same after sext/zext
361 * ( not(A) <= not(B) ) <=> ( 2n−A−1 <= 2n−B−1 )
366 midgard_opt_drop_cmp_invert(compiler_context
*ctx
, midgard_block
*block
)
369 bool progress
= false;
371 mir_foreach_instr_in_block_safe(block
, ins
) {
372 if (ins
->type
!= TAG_ALU_4
) continue;
373 if (!OP_IS_INTEGER_CMP(ins
->alu
.op
)) continue;
375 if ((ins
->src
[0] & IS_REG
) || (ins
->src
[1] & IS_REG
)) continue;
376 if (!mir_single_use(ctx
, ins
->src
[0]) || !mir_single_use(ctx
, ins
->src
[1])) continue;
378 bool a_inverted
= mir_is_inverted(ctx
, ins
->src
[0]);
379 bool b_inverted
= mir_is_inverted(ctx
, ins
->src
[1]);
381 if (!a_inverted
|| !b_inverted
) continue;
382 if (OP_IS_UNSIGNED_CMP(ins
->alu
.op
) && mir_srcsize(ins
, 0) != mir_srcsize(ins
, 1)) continue;
385 mir_strip_inverted(ctx
, ins
->src
[0]);
386 mir_strip_inverted(ctx
, ins
->src
[1]);
388 if (ins
->alu
.op
!= midgard_alu_op_ieq
&& ins
->alu
.op
!= midgard_alu_op_ine
)
397 /* Optimizes branches with inverted arguments by inverting the
398 * branch condition instead of the argument condition.
401 midgard_opt_invert_branch(compiler_context
*ctx
, midgard_block
*block
)
403 bool progress
= false;
405 mir_foreach_instr_in_block_safe(block
, ins
) {
406 if (ins
->type
!= TAG_ALU_4
) continue;
407 if (!midgard_is_branch_unit(ins
->unit
)) continue;
408 if (!ins
->branch
.conditional
) continue;
409 if (ins
->src
[0] & IS_REG
) continue;
411 if (mir_strip_inverted(ctx
, ins
->src
[0])) {
412 ins
->branch
.invert_conditional
= !ins
->branch
.invert_conditional
;