src/panfrost/midgard/midgard_opt_invert.c

   1 /*
   2  * Copyright (C) 2019 Collabora, Ltd.
   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 FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23
  24 #include "compiler.h"
  25 #include "midgard_ops.h"
  26
  27 /* Lowers the invert field on instructions to a dedicated inot (inor)
  28  * instruction instead, as invert is not always supported natively by the
  29  * hardware */
  30
  31 void
  32 midgard_lower_invert(compiler_context *ctx, midgard_block *block)
  33 {
  34         mir_foreach_instr_in_block_safe(block, ins) {
  35                 if (ins->type != TAG_ALU_4) continue;
  36                 if (!ins->invert) continue;
  37
  38                 unsigned temp = make_compiler_temp(ctx);
  39
  40                 midgard_instruction not = {
  41                         .type = TAG_ALU_4,
  42                         .mask = ins->mask,
  43                         .src = { temp, ~0, ~0, ~0 },
  44                         .swizzle = SWIZZLE_IDENTITY,
  45                         .dest = ins->dest,
  46                         .has_inline_constant = true,
  47                         .alu = {
  48                                 .op = midgard_alu_op_inor,
  49                                 /* TODO: i16 */
  50                                 .reg_mode = midgard_reg_mode_32,
  51                                 .dest_override = midgard_dest_override_none,
  52                                 .outmod = midgard_outmod_int_wrap
  53                         },
  54                 };
  55
  56                 ins->dest = temp;
  57                 ins->invert = false;
  58                 mir_insert_instruction_before(ctx, mir_next_op(ins), not);
  59         }
  60 }
  61
  62 /* Propagate the .not up to the source */
  63
  64 bool
  65 midgard_opt_not_propagate(compiler_context *ctx, midgard_block *block)
  66 {
  67         bool progress = false;
  68
  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] & PAN_IS_REG) continue;
  75
  76                 /* Is it beneficial to propagate? */
  77                 if (!mir_single_use(ctx, ins->src[1])) continue;
  78
  79                 /* We found an imov.not, propagate the invert back */
  80
  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;
  84
  85                         v->invert = !v->invert;
  86                         ins->invert = false;
  87                         progress |= true;
  88                         break;
  89                 }
  90         }
  91
  92         return progress;
  93 }
  94
  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:
  97  *
  98  * ~iand = inand
  99  * ~ior  = inor
 100  * ~ixor = inxor
 101  */
 102
 103 static bool
 104 mir_is_bitwise(midgard_instruction *ins)
 105 {
 106         switch (ins->alu.op) {
 107         case midgard_alu_op_iand:
 108         case midgard_alu_op_ior:
 109         case midgard_alu_op_ixor:
 110                 return true;
 111         default:
 112                 return false;
 113         }
 114 }
 115
 116 static bool
 117 mir_is_inverted_bitwise(midgard_instruction *ins)
 118 {
 119         switch (ins->alu.op) {
 120         case midgard_alu_op_inand:
 121         case midgard_alu_op_inor:
 122         case midgard_alu_op_inxor:
 123                 return true;
 124         default:
 125                 return false;
 126         }
 127 }
 128
 129 static midgard_alu_op
 130 mir_invert_op(midgard_alu_op op)
 131 {
 132         switch (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;
 145         default:
 146                 unreachable("Op not invertible");
 147         }
 148 }
 149
 150 static midgard_alu_op
 151 mir_demorgan_op(midgard_alu_op op)
 152 {
 153         switch (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;
 158         default:
 159                 unreachable("Op not De Morgan-able");
 160         }
 161 }
 162
 163 static midgard_alu_op
 164 mir_notright_op(midgard_alu_op op)
 165 {
 166         switch (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;
 171         default:
 172                 unreachable("Op not right able");
 173         }
 174 }
 175
 176 bool
 177 midgard_opt_fuse_dest_invert(compiler_context *ctx, midgard_block *block)
 178 {
 179         bool progress = false;
 180
 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;
 186
 187                 ins->alu.op = mir_invert_op(ins->alu.op);
 188                 ins->invert = false;
 189                 progress |= true;
 190         }
 191
 192         return progress;
 193 }
 194
 195 /* Next up, we can fuse inverts into the sources of bitwise ops:
 196  *
 197  * ~a & b = b & ~a = iandnot(b, a)
 198  * a & ~b = iandnot(a, b)
 199  * ~a & ~b = ~(a | b) = inor(a, b)
 200  *
 201  * ~a | b = b | ~a = iornot(b, a)
 202  *  a | ~b = iornot(a, b)
 203  * ~a | ~b = ~(a & b) = inand(a, b)
 204  *
 205  * ~a ^ b = ~(a ^ b) = inxor(a, b)
 206  * a ^ ~b = ~(a ^ b) + inxor(a, b)
 207  * ~a ^ ~b = a ^ b
 208  * ~(a ^ b) = inxor(a, b)
 209  */
 210
 211 static bool
 212 mir_strip_inverted(compiler_context *ctx, unsigned node)
 213 {
 214         if (node == SSA_FIXED_REGISTER(26))
 215                 return false;
 216
 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;
 221
 222                bool status = ins->invert;
 223                ins->invert = false;
 224                return status;
 225        }
 226
 227        unreachable("Invalid node stripped");
 228 }
 229
 230 static bool
 231 is_ssa_or_constant(unsigned node)
 232 {
 233         return !(node & PAN_IS_REG) || (node == SSA_FIXED_REGISTER(26));
 234 }
 235
 236 bool
 237 midgard_opt_fuse_src_invert(compiler_context *ctx, midgard_block *block)
 238 {
 239         bool progress = false;
 240
 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;
 245
 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;
 250
 251                 bool not_a = mir_strip_inverted(ctx, ins->src[0]);
 252                 bool not_b =
 253                         ins->has_inline_constant ? false :
 254                         mir_strip_inverted(ctx, ins->src[1]);
 255
 256                 /* Edge case: if src0 == src1, it'll've been stripped */
 257                 if ((ins->src[0] == ins->src[1]) && !ins->has_inline_constant)
 258                         not_b = not_a;
 259
 260                 progress |= (not_a || not_b);
 261
 262                 /* No point */
 263                 if (!(not_a || not_b)) continue;
 264
 265                 bool both = not_a && not_b;
 266                 bool left = not_a && !not_b;
 267                 bool right = !not_a && not_b;
 268
 269                 /* No-op, but we got to strip the inverts */
 270                 if (both && ins->alu.op == midgard_alu_op_ixor)
 271                         continue;
 272
 273                 if (both) {
 274                         ins->alu.op = mir_demorgan_op(ins->alu.op);
 275                 } else if (right || (left && !ins->has_inline_constant)) {
 276                         /* Commute arguments */
 277                         if (left)
 278                                 mir_flip(ins);
 279
 280                         ins->alu.op = mir_notright_op(ins->alu.op);
 281                 } else if (left && ins->has_inline_constant) {
 282                         /* Some special transformations:
 283                          *
 284                          * ~A & c = ~(~(~A) | (~c)) = ~(A | ~c) = inor(A, ~c)
 285                          * ~A | c = ~(~(~A) & (~c)) = ~(A & ~c) = inand(A, ~c)
 286                          */
 287
 288                         ins->alu.op = mir_demorgan_op(ins->alu.op);
 289                         ins->inline_constant = ~ins->inline_constant;
 290                 }
 291         }
 292
 293         return progress;
 294 }
 295
 296 /* Optimizes a .not away when used as the source of a conditional select:
 297  *
 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)
 301  */
 302
 303 bool
 304 midgard_opt_csel_invert(compiler_context *ctx, midgard_block *block)
 305 {
 306         bool progress = false;
 307
 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 (!is_ssa_or_constant(ins->src[2])) continue;
 312                 if (!mir_single_use(ctx, ins->src[2])) continue;
 313                 if (!mir_strip_inverted(ctx, ins->src[2])) continue;
 314
 315                 mir_flip(ins);
 316                 progress |= true;
 317         }
 318
 319         return progress;
 320 }
 321
 322
 323 static bool
 324 mir_is_inverted(compiler_context *ctx, unsigned node)
 325 {
 326         mir_foreach_instr_global(ctx, ins) {
 327                 if (ins->compact_branch) continue;
 328                 if (ins->dest != node) continue;
 329
 330                 return ins->invert;
 331         }
 332
 333         unreachable("Invalid node passed");
 334 }
 335
 336
 337
 338 /* Optimizes comparisions which invert both arguments
 339  *
 340  *
 341  * ieq(not(a), not(b)) = ieq(a, b)
 342  * ine(not(a), not(b)) = ine(a, b)
 343  *
 344  * This does apply for ilt and ile if we flip the argument order:
 345  * Proofs below provided by Alyssa Rosenzweig
 346  *
 347  * not(x) = −(x+1)
 348  *
 349  * ( not(A) <= not(B) ) <=> ( −(A+1) <= −(B+1) )
 350  *                      <=> ( A+1 >= B+1)
 351  *                      <=> ( B <= A )
 352  *
 353  * On unsigned comparisons (ult / ule) we can perform the same optimization
 354  * with the additional restriction that the source registers must
 355  * have the same size.
 356  *
 357  * TODO: We may not need them to be of the same size, if we can
 358  *       prove that they are the same after sext/zext
 359  *
 360  * not(x) = 2n−x−1
 361  *
 362  * ( not(A) <= not(B) ) <=> ( 2n−A−1 <= 2n−B−1 )
 363  *                      <=> ( −A <= −B )
 364  *                      <=> ( B <= A )
 365  */
 366 bool
 367 midgard_opt_drop_cmp_invert(compiler_context *ctx, midgard_block *block)
 368 {
 369
 370         bool progress = false;
 371
 372         mir_foreach_instr_in_block_safe(block, ins) {
 373                 if (ins->type != TAG_ALU_4) continue;
 374                 if (!OP_IS_INTEGER_CMP(ins->alu.op)) continue;
 375
 376                 if ((ins->src[0] & PAN_IS_REG) || (ins->src[1] & PAN_IS_REG)) continue;
 377                 if (!mir_single_use(ctx, ins->src[0]) || !mir_single_use(ctx, ins->src[1])) continue;
 378
 379                 bool a_inverted = mir_is_inverted(ctx, ins->src[0]);
 380                 bool b_inverted = mir_is_inverted(ctx, ins->src[1]);
 381
 382                 if (!a_inverted || !b_inverted) continue;
 383                 if (OP_IS_UNSIGNED_CMP(ins->alu.op) && mir_srcsize(ins, 0) != mir_srcsize(ins, 1)) continue;
 384
 385
 386                 mir_strip_inverted(ctx, ins->src[0]);
 387                 mir_strip_inverted(ctx, ins->src[1]);
 388
 389                 if (ins->alu.op != midgard_alu_op_ieq && ins->alu.op != midgard_alu_op_ine)
 390                         mir_flip(ins);
 391
 392                 progress |= true;
 393         }
 394
 395         return progress;
 396 }
 397
 398 /* Optimizes branches with inverted arguments by inverting the
 399  * branch condition instead of the argument condition.
 400  */
 401 bool
 402 midgard_opt_invert_branch(compiler_context *ctx, midgard_block *block)
 403 {
 404         bool progress = false;
 405
 406         mir_foreach_instr_in_block_safe(block, ins) {
 407                 if (ins->type != TAG_ALU_4) continue;
 408                 if (!midgard_is_branch_unit(ins->unit)) continue;
 409                 if (!ins->branch.conditional) continue;
 410                 if (ins->src[0] & PAN_IS_REG) continue;
 411
 412                 if (mir_strip_inverted(ctx, ins->src[0])) {
 413                         ins->branch.invert_conditional = !ins->branch.invert_conditional;
 414
 415                         progress |= true;
 416                 }
 417         }
 418
 419         return progress;
 420 }