src/amd/compiler/aco_lower_to_hw_instr.cpp

   1 /*
   2  * Copyright © 2018 Valve 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  * Authors:
  24  *    Daniel Schürmann (daniel.schuermann@campus.tu-berlin.de)
  25  *
  26  */
  27
  28 #include <map>
  29
  30 #include "aco_ir.h"
  31 #include "aco_builder.h"
  32 #include "util/u_math.h"
  33 #include "sid.h"
  34 #include "vulkan/radv_shader.h"
  35
  36
  37 namespace aco {
  38
  39 struct lower_context {
  40    Program *program;
  41    std::vector<aco_ptr<Instruction>> instructions;
  42 };
  43
  44 aco_opcode get_reduce_opcode(chip_class chip, ReduceOp op) {
  45    /* Because some 16-bit instructions are already VOP3 on GFX10, we use the
  46     * 32-bit opcodes (VOP2) which allows to remove the tempory VGPR and to use
  47     * DPP with the arithmetic instructions. This requires to sign-extend.
  48     */
  49    switch (op) {
  50    case iadd8:
  51    case iadd16:
  52       if (chip >= GFX10) {
  53          return aco_opcode::v_add_u32;
  54       } else if (chip >= GFX8) {
  55          return aco_opcode::v_add_u16;
  56       } else {
  57          return aco_opcode::v_add_co_u32;
  58       }
  59       break;
  60    case imul8:
  61    case imul16:
  62       if (chip >= GFX10) {
  63          return aco_opcode::v_mul_lo_u16_e64;
  64       } else if (chip >= GFX8) {
  65          return aco_opcode::v_mul_lo_u16;
  66       } else {
  67          return aco_opcode::v_mul_u32_u24;
  68       }
  69       break;
  70    case fadd16: return aco_opcode::v_add_f16;
  71    case fmul16: return aco_opcode::v_mul_f16;
  72    case imax8:
  73    case imax16:
  74       if (chip >= GFX10) {
  75          return aco_opcode::v_max_i32;
  76       } else if (chip >= GFX8) {
  77          return aco_opcode::v_max_i16;
  78       } else {
  79          return aco_opcode::v_max_i32;
  80       }
  81       break;
  82    case imin8:
  83    case imin16:
  84       if (chip >= GFX10) {
  85          return aco_opcode::v_min_i32;
  86       } else if (chip >= GFX8) {
  87          return aco_opcode::v_min_i16;
  88       } else {
  89          return aco_opcode::v_min_i32;
  90       }
  91       break;
  92    case umin8:
  93    case umin16:
  94       if (chip >= GFX10) {
  95          return aco_opcode::v_min_u32;
  96       } else if (chip >= GFX8) {
  97          return aco_opcode::v_min_u16;
  98       } else {
  99          return aco_opcode::v_min_u32;
 100       }
 101       break;
 102    case umax8:
 103    case umax16:
 104       if (chip >= GFX10) {
 105          return aco_opcode::v_max_u32;
 106       } else if (chip >= GFX8) {
 107          return aco_opcode::v_max_u16;
 108       } else {
 109          return aco_opcode::v_max_u32;
 110       }
 111       break;
 112    case fmin16: return aco_opcode::v_min_f16;
 113    case fmax16: return aco_opcode::v_max_f16;
 114    case iadd32: return chip >= GFX9 ? aco_opcode::v_add_u32 : aco_opcode::v_add_co_u32;
 115    case imul32: return aco_opcode::v_mul_lo_u32;
 116    case fadd32: return aco_opcode::v_add_f32;
 117    case fmul32: return aco_opcode::v_mul_f32;
 118    case imax32: return aco_opcode::v_max_i32;
 119    case imin32: return aco_opcode::v_min_i32;
 120    case umin32: return aco_opcode::v_min_u32;
 121    case umax32: return aco_opcode::v_max_u32;
 122    case fmin32: return aco_opcode::v_min_f32;
 123    case fmax32: return aco_opcode::v_max_f32;
 124    case iand8:
 125    case iand16:
 126    case iand32: return aco_opcode::v_and_b32;
 127    case ixor8:
 128    case ixor16:
 129    case ixor32: return aco_opcode::v_xor_b32;
 130    case ior8:
 131    case ior16:
 132    case ior32: return aco_opcode::v_or_b32;
 133    case iadd64: return aco_opcode::num_opcodes;
 134    case imul64: return aco_opcode::num_opcodes;
 135    case fadd64: return aco_opcode::v_add_f64;
 136    case fmul64: return aco_opcode::v_mul_f64;
 137    case imin64: return aco_opcode::num_opcodes;
 138    case imax64: return aco_opcode::num_opcodes;
 139    case umin64: return aco_opcode::num_opcodes;
 140    case umax64: return aco_opcode::num_opcodes;
 141    case fmin64: return aco_opcode::v_min_f64;
 142    case fmax64: return aco_opcode::v_max_f64;
 143    case iand64: return aco_opcode::num_opcodes;
 144    case ior64: return aco_opcode::num_opcodes;
 145    case ixor64: return aco_opcode::num_opcodes;
 146    default: return aco_opcode::num_opcodes;
 147    }
 148 }
 149
 150 bool is_vop3_reduce_opcode(aco_opcode opcode)
 151 {
 152    /* 64-bit reductions are VOP3. */
 153    if (opcode == aco_opcode::num_opcodes)
 154       return true;
 155
 156    return instr_info.format[(int)opcode] == Format::VOP3;
 157 }
 158
 159 void emit_vadd32(Builder& bld, Definition def, Operand src0, Operand src1)
 160 {
 161    Instruction *instr = bld.vadd32(def, src0, src1, false, Operand(s2), true);
 162    if (instr->definitions.size() >= 2) {
 163       assert(instr->definitions[1].regClass() == bld.lm);
 164       instr->definitions[1].setFixed(vcc);
 165    }
 166 }
 167
 168 void emit_int64_dpp_op(lower_context *ctx, PhysReg dst_reg, PhysReg src0_reg, PhysReg src1_reg,
 169                        PhysReg vtmp_reg, ReduceOp op,
 170                        unsigned dpp_ctrl, unsigned row_mask, unsigned bank_mask, bool bound_ctrl,
 171                        Operand *identity=NULL)
 172 {
 173    Builder bld(ctx->program, &ctx->instructions);
 174    Definition dst[] = {Definition(dst_reg, v1), Definition(PhysReg{dst_reg+1}, v1)};
 175    Definition vtmp_def[] = {Definition(vtmp_reg, v1), Definition(PhysReg{vtmp_reg+1}, v1)};
 176    Operand src0[] = {Operand(src0_reg, v1), Operand(PhysReg{src0_reg+1}, v1)};
 177    Operand src1[] = {Operand(src1_reg, v1), Operand(PhysReg{src1_reg+1}, v1)};
 178    Operand src1_64 = Operand(src1_reg, v2);
 179    Operand vtmp_op[] = {Operand(vtmp_reg, v1), Operand(PhysReg{vtmp_reg+1}, v1)};
 180    Operand vtmp_op64 = Operand(vtmp_reg, v2);
 181    if (op == iadd64) {
 182       if (ctx->program->chip_class >= GFX10) {
 183          if (identity)
 184             bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[0]);
 185          bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[0],
 186                       dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 187          bld.vop3(aco_opcode::v_add_co_u32_e64, dst[0], bld.def(bld.lm, vcc), vtmp_op[0], src1[0]);
 188       } else {
 189          bld.vop2_dpp(aco_opcode::v_add_co_u32, dst[0], bld.def(bld.lm, vcc), src0[0], src1[0],
 190                       dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 191       }
 192       bld.vop2_dpp(aco_opcode::v_addc_co_u32, dst[1], bld.def(bld.lm, vcc), src0[1], src1[1], Operand(vcc, bld.lm),
 193                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 194    } else if (op == iand64) {
 195       bld.vop2_dpp(aco_opcode::v_and_b32, dst[0], src0[0], src1[0],
 196                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 197       bld.vop2_dpp(aco_opcode::v_and_b32, dst[1], src0[1], src1[1],
 198                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 199    } else if (op == ior64) {
 200       bld.vop2_dpp(aco_opcode::v_or_b32, dst[0], src0[0], src1[0],
 201                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 202       bld.vop2_dpp(aco_opcode::v_or_b32, dst[1], src0[1], src1[1],
 203                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 204    } else if (op == ixor64) {
 205       bld.vop2_dpp(aco_opcode::v_xor_b32, dst[0], src0[0], src1[0],
 206                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 207       bld.vop2_dpp(aco_opcode::v_xor_b32, dst[1], src0[1], src1[1],
 208                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 209    } else if (op == umin64 || op == umax64 || op == imin64 || op == imax64) {
 210       aco_opcode cmp = aco_opcode::num_opcodes;
 211       switch (op) {
 212       case umin64:
 213          cmp = aco_opcode::v_cmp_gt_u64;
 214          break;
 215       case umax64:
 216          cmp = aco_opcode::v_cmp_lt_u64;
 217          break;
 218       case imin64:
 219          cmp = aco_opcode::v_cmp_gt_i64;
 220          break;
 221       case imax64:
 222          cmp = aco_opcode::v_cmp_lt_i64;
 223          break;
 224       default:
 225          break;
 226       }
 227
 228       if (identity) {
 229          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[0]);
 230          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[1], identity[1]);
 231       }
 232       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[0],
 233                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 234       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[1], src0[1],
 235                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 236
 237       bld.vopc(cmp, bld.def(bld.lm, vcc), vtmp_op64, src1_64);
 238       bld.vop2(aco_opcode::v_cndmask_b32, dst[0], vtmp_op[0], src1[0], Operand(vcc, bld.lm));
 239       bld.vop2(aco_opcode::v_cndmask_b32, dst[1], vtmp_op[1], src1[1], Operand(vcc, bld.lm));
 240    } else if (op == imul64) {
 241       /* t4 = dpp(x_hi)
 242        * t1 = umul_lo(t4, y_lo)
 243        * t3 = dpp(x_lo)
 244        * t0 = umul_lo(t3, y_hi)
 245        * t2 = iadd(t0, t1)
 246        * t5 = umul_hi(t3, y_lo)
 247        * res_hi = iadd(t2, t5)
 248        * res_lo = umul_lo(t3, y_lo)
 249        * Requires that res_hi != src0[0] and res_hi != src1[0]
 250        * and that vtmp[0] != res_hi.
 251        */
 252       if (identity)
 253          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[1]);
 254       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[1],
 255                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 256       bld.vop3(aco_opcode::v_mul_lo_u32, vtmp_def[1], vtmp_op[0], src1[0]);
 257       if (identity)
 258          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[0]);
 259       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[0],
 260                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 261       bld.vop3(aco_opcode::v_mul_lo_u32, vtmp_def[0], vtmp_op[0], src1[1]);
 262       emit_vadd32(bld, vtmp_def[1], vtmp_op[0], vtmp_op[1]);
 263       if (identity)
 264          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[0]);
 265       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[0],
 266                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 267       bld.vop3(aco_opcode::v_mul_hi_u32, vtmp_def[0], vtmp_op[0], src1[0]);
 268       emit_vadd32(bld, dst[1], vtmp_op[1], vtmp_op[0]);
 269       if (identity)
 270          bld.vop1(aco_opcode::v_mov_b32, vtmp_def[0], identity[0]);
 271       bld.vop1_dpp(aco_opcode::v_mov_b32, vtmp_def[0], src0[0],
 272                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 273       bld.vop3(aco_opcode::v_mul_lo_u32, dst[0], vtmp_op[0], src1[0]);
 274    }
 275 }
 276
 277 void emit_int64_op(lower_context *ctx, PhysReg dst_reg, PhysReg src0_reg, PhysReg src1_reg, PhysReg vtmp, ReduceOp op)
 278 {
 279    Builder bld(ctx->program, &ctx->instructions);
 280    Definition dst[] = {Definition(dst_reg, v1), Definition(PhysReg{dst_reg+1}, v1)};
 281    RegClass src0_rc = src0_reg.reg() >= 256 ? v1 : s1;
 282    Operand src0[] = {Operand(src0_reg, src0_rc), Operand(PhysReg{src0_reg+1}, src0_rc)};
 283    Operand src1[] = {Operand(src1_reg, v1), Operand(PhysReg{src1_reg+1}, v1)};
 284    Operand src0_64 = Operand(src0_reg, src0_reg.reg() >= 256 ? v2 : s2);
 285    Operand src1_64 = Operand(src1_reg, v2);
 286
 287    if (src0_rc == s1 &&
 288        (op == imul64 || op == umin64 || op == umax64 || op == imin64 || op == imax64)) {
 289       assert(vtmp.reg() != 0);
 290       bld.vop1(aco_opcode::v_mov_b32, Definition(vtmp, v1), src0[0]);
 291       bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+1}, v1), src0[1]);
 292       src0_reg = vtmp;
 293       src0[0] = Operand(vtmp, v1);
 294       src0[1] = Operand(PhysReg{vtmp+1}, v1);
 295       src0_64 = Operand(vtmp, v2);
 296    } else if (src0_rc == s1 && op == iadd64) {
 297       assert(vtmp.reg() != 0);
 298       bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+1}, v1), src0[1]);
 299       src0[1] = Operand(PhysReg{vtmp+1}, v1);
 300    }
 301
 302    if (op == iadd64) {
 303       if (ctx->program->chip_class >= GFX10) {
 304          bld.vop3(aco_opcode::v_add_co_u32_e64, dst[0], bld.def(bld.lm, vcc), src0[0], src1[0]);
 305       } else {
 306          bld.vop2(aco_opcode::v_add_co_u32, dst[0], bld.def(bld.lm, vcc), src0[0], src1[0]);
 307       }
 308       bld.vop2(aco_opcode::v_addc_co_u32, dst[1], bld.def(bld.lm, vcc), src0[1], src1[1], Operand(vcc, bld.lm));
 309    } else if (op == iand64) {
 310       bld.vop2(aco_opcode::v_and_b32, dst[0], src0[0], src1[0]);
 311       bld.vop2(aco_opcode::v_and_b32, dst[1], src0[1], src1[1]);
 312    } else if (op == ior64) {
 313       bld.vop2(aco_opcode::v_or_b32, dst[0], src0[0], src1[0]);
 314       bld.vop2(aco_opcode::v_or_b32, dst[1], src0[1], src1[1]);
 315    } else if (op == ixor64) {
 316       bld.vop2(aco_opcode::v_xor_b32, dst[0], src0[0], src1[0]);
 317       bld.vop2(aco_opcode::v_xor_b32, dst[1], src0[1], src1[1]);
 318    } else if (op == umin64 || op == umax64 || op == imin64 || op == imax64) {
 319       aco_opcode cmp = aco_opcode::num_opcodes;
 320       switch (op) {
 321       case umin64:
 322          cmp = aco_opcode::v_cmp_gt_u64;
 323          break;
 324       case umax64:
 325          cmp = aco_opcode::v_cmp_lt_u64;
 326          break;
 327       case imin64:
 328          cmp = aco_opcode::v_cmp_gt_i64;
 329          break;
 330       case imax64:
 331          cmp = aco_opcode::v_cmp_lt_i64;
 332          break;
 333       default:
 334          break;
 335       }
 336
 337       bld.vopc(cmp, bld.def(bld.lm, vcc), src0_64, src1_64);
 338       bld.vop2(aco_opcode::v_cndmask_b32, dst[0], src0[0], src1[0], Operand(vcc, bld.lm));
 339       bld.vop2(aco_opcode::v_cndmask_b32, dst[1], src0[1], src1[1], Operand(vcc, bld.lm));
 340    } else if (op == imul64) {
 341       if (src1_reg == dst_reg) {
 342          /* it's fine if src0==dst but not if src1==dst */
 343          std::swap(src0_reg, src1_reg);
 344          std::swap(src0[0], src1[0]);
 345          std::swap(src0[1], src1[1]);
 346          std::swap(src0_64, src1_64);
 347       }
 348       assert(!(src0_reg == src1_reg));
 349       /* t1 = umul_lo(x_hi, y_lo)
 350        * t0 = umul_lo(x_lo, y_hi)
 351        * t2 = iadd(t0, t1)
 352        * t5 = umul_hi(x_lo, y_lo)
 353        * res_hi = iadd(t2, t5)
 354        * res_lo = umul_lo(x_lo, y_lo)
 355        * assumes that it's ok to modify x_hi/y_hi, since we might not have vtmp
 356        */
 357       Definition tmp0_def(PhysReg{src0_reg+1}, v1);
 358       Definition tmp1_def(PhysReg{src1_reg+1}, v1);
 359       Operand tmp0_op = src0[1];
 360       Operand tmp1_op = src1[1];
 361       bld.vop3(aco_opcode::v_mul_lo_u32, tmp0_def, src0[1], src1[0]);
 362       bld.vop3(aco_opcode::v_mul_lo_u32, tmp1_def, src0[0], src1[1]);
 363       emit_vadd32(bld, tmp0_def, tmp1_op, tmp0_op);
 364       bld.vop3(aco_opcode::v_mul_hi_u32, tmp1_def, src0[0], src1[0]);
 365       emit_vadd32(bld, dst[1], tmp0_op, tmp1_op);
 366       bld.vop3(aco_opcode::v_mul_lo_u32, dst[0], src0[0], src1[0]);
 367    }
 368 }
 369
 370 void emit_dpp_op(lower_context *ctx, PhysReg dst_reg, PhysReg src0_reg, PhysReg src1_reg,
 371                  PhysReg vtmp, ReduceOp op, unsigned size,
 372                  unsigned dpp_ctrl, unsigned row_mask, unsigned bank_mask, bool bound_ctrl,
 373                  Operand *identity=NULL) /* for VOP3 with sparse writes */
 374 {
 375    Builder bld(ctx->program, &ctx->instructions);
 376    RegClass rc = RegClass(RegType::vgpr, size);
 377    Definition dst(dst_reg, rc);
 378    Operand src0(src0_reg, rc);
 379    Operand src1(src1_reg, rc);
 380
 381    aco_opcode opcode = get_reduce_opcode(ctx->program->chip_class, op);
 382    bool vop3 = is_vop3_reduce_opcode(opcode);
 383
 384    if (!vop3) {
 385       if (opcode == aco_opcode::v_add_co_u32)
 386          bld.vop2_dpp(opcode, dst, bld.def(bld.lm, vcc), src0, src1, dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 387       else
 388          bld.vop2_dpp(opcode, dst, src0, src1, dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 389       return;
 390    }
 391
 392    if (opcode == aco_opcode::num_opcodes) {
 393       emit_int64_dpp_op(ctx, dst_reg ,src0_reg, src1_reg, vtmp, op,
 394                         dpp_ctrl, row_mask, bank_mask, bound_ctrl, identity);
 395       return;
 396    }
 397
 398    if (identity)
 399       bld.vop1(aco_opcode::v_mov_b32, Definition(vtmp, v1), identity[0]);
 400    if (identity && size >= 2)
 401       bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+1}, v1), identity[1]);
 402
 403    for (unsigned i = 0; i < size; i++)
 404       bld.vop1_dpp(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{src0_reg+i}, v1),
 405                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 406
 407    bld.vop3(opcode, dst, Operand(vtmp, rc), src1);
 408 }
 409
 410 void emit_op(lower_context *ctx, PhysReg dst_reg, PhysReg src0_reg, PhysReg src1_reg,
 411              PhysReg vtmp, ReduceOp op, unsigned size)
 412 {
 413    Builder bld(ctx->program, &ctx->instructions);
 414    RegClass rc = RegClass(RegType::vgpr, size);
 415    Definition dst(dst_reg, rc);
 416    Operand src0(src0_reg, RegClass(src0_reg.reg() >= 256 ? RegType::vgpr : RegType::sgpr, size));
 417    Operand src1(src1_reg, rc);
 418
 419    aco_opcode opcode = get_reduce_opcode(ctx->program->chip_class, op);
 420    bool vop3 = is_vop3_reduce_opcode(opcode);
 421
 422    if (opcode == aco_opcode::num_opcodes) {
 423       emit_int64_op(ctx, dst_reg, src0_reg, src1_reg, vtmp, op);
 424       return;
 425    }
 426
 427    if (vop3) {
 428       bld.vop3(opcode, dst, src0, src1);
 429    } else if (opcode == aco_opcode::v_add_co_u32) {
 430       bld.vop2(opcode, dst, bld.def(bld.lm, vcc), src0, src1);
 431    } else {
 432       bld.vop2(opcode, dst, src0, src1);
 433    }
 434 }
 435
 436 void emit_dpp_mov(lower_context *ctx, PhysReg dst, PhysReg src0, unsigned size,
 437                   unsigned dpp_ctrl, unsigned row_mask, unsigned bank_mask, bool bound_ctrl)
 438 {
 439    Builder bld(ctx->program, &ctx->instructions);
 440    for (unsigned i = 0; i < size; i++) {
 441       bld.vop1_dpp(aco_opcode::v_mov_b32, Definition(PhysReg{dst+i}, v1), Operand(PhysReg{src0+i}, v1),
 442                    dpp_ctrl, row_mask, bank_mask, bound_ctrl);
 443    }
 444 }
 445
 446 uint32_t get_reduction_identity(ReduceOp op, unsigned idx)
 447 {
 448    switch (op) {
 449    case iadd8:
 450    case iadd16:
 451    case iadd32:
 452    case iadd64:
 453    case fadd16:
 454    case fadd32:
 455    case fadd64:
 456    case ior8:
 457    case ior16:
 458    case ior32:
 459    case ior64:
 460    case ixor8:
 461    case ixor16:
 462    case ixor32:
 463    case ixor64:
 464    case umax8:
 465    case umax16:
 466    case umax32:
 467    case umax64:
 468       return 0;
 469    case imul8:
 470    case imul16:
 471    case imul32:
 472    case imul64:
 473       return idx ? 0 : 1;
 474    case fmul16:
 475       return 0x3c00u; /* 1.0 */
 476    case fmul32:
 477       return 0x3f800000u; /* 1.0 */
 478    case fmul64:
 479       return idx ? 0x3ff00000u : 0u; /* 1.0 */
 480    case imin8:
 481       return INT8_MAX;
 482    case imin16:
 483       return INT16_MAX;
 484    case imin32:
 485       return INT32_MAX;
 486    case imin64:
 487       return idx ? 0x7fffffffu : 0xffffffffu;
 488    case imax8:
 489       return INT8_MIN;
 490    case imax16:
 491       return INT16_MIN;
 492    case imax32:
 493       return INT32_MIN;
 494    case imax64:
 495       return idx ? 0x80000000u : 0;
 496    case umin8:
 497    case umin16:
 498    case iand8:
 499    case iand16:
 500       return 0xffffffffu;
 501    case umin32:
 502    case umin64:
 503    case iand32:
 504    case iand64:
 505       return 0xffffffffu;
 506    case fmin16:
 507       return 0x7c00u; /* infinity */
 508    case fmin32:
 509       return 0x7f800000u; /* infinity */
 510    case fmin64:
 511       return idx ? 0x7ff00000u : 0u; /* infinity */
 512    case fmax16:
 513       return 0xfc00u; /* negative infinity */
 514    case fmax32:
 515       return 0xff800000u; /* negative infinity */
 516    case fmax64:
 517       return idx ? 0xfff00000u : 0u; /* negative infinity */
 518    default:
 519       unreachable("Invalid reduction operation");
 520       break;
 521    }
 522    return 0;
 523 }
 524
 525 void emit_ds_swizzle(Builder bld, PhysReg dst, PhysReg src, unsigned size, unsigned ds_pattern)
 526 {
 527    for (unsigned i = 0; i < size; i++) {
 528       bld.ds(aco_opcode::ds_swizzle_b32, Definition(PhysReg{dst+i}, v1),
 529              Operand(PhysReg{src+i}, v1), ds_pattern);
 530    }
 531 }
 532
 533 void emit_reduction(lower_context *ctx, aco_opcode op, ReduceOp reduce_op, unsigned cluster_size, PhysReg tmp,
 534                     PhysReg stmp, PhysReg vtmp, PhysReg sitmp, Operand src, Definition dst)
 535 {
 536    assert(cluster_size == ctx->program->wave_size || op == aco_opcode::p_reduce);
 537    assert(cluster_size <= ctx->program->wave_size);
 538
 539    Builder bld(ctx->program, &ctx->instructions);
 540
 541    Operand identity[2];
 542    identity[0] = Operand(get_reduction_identity(reduce_op, 0));
 543    identity[1] = Operand(get_reduction_identity(reduce_op, 1));
 544    Operand vcndmask_identity[2] = {identity[0], identity[1]};
 545
 546    /* First, copy the source to tmp and set inactive lanes to the identity */
 547    bld.sop1(Builder::s_or_saveexec, Definition(stmp, bld.lm), Definition(scc, s1), Definition(exec, bld.lm), Operand(UINT64_MAX), Operand(exec, bld.lm));
 548
 549    for (unsigned i = 0; i < src.size(); i++) {
 550       /* p_exclusive_scan needs it to be a sgpr or inline constant for the v_writelane_b32
 551        * except on GFX10, where v_writelane_b32 can take a literal. */
 552       if (identity[i].isLiteral() && op == aco_opcode::p_exclusive_scan && ctx->program->chip_class < GFX10) {
 553          bld.sop1(aco_opcode::s_mov_b32, Definition(PhysReg{sitmp+i}, s1), identity[i]);
 554          identity[i] = Operand(PhysReg{sitmp+i}, s1);
 555
 556          bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{tmp+i}, v1), identity[i]);
 557          vcndmask_identity[i] = Operand(PhysReg{tmp+i}, v1);
 558       } else if (identity[i].isLiteral()) {
 559          bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{tmp+i}, v1), identity[i]);
 560          vcndmask_identity[i] = Operand(PhysReg{tmp+i}, v1);
 561       }
 562    }
 563
 564    for (unsigned i = 0; i < src.size(); i++) {
 565       bld.vop2_e64(aco_opcode::v_cndmask_b32, Definition(PhysReg{tmp + i}, v1),
 566                    vcndmask_identity[i], Operand(PhysReg{src.physReg() + i}, v1),
 567                    Operand(stmp, bld.lm));
 568    }
 569
 570    if (src.regClass() == v1b) {
 571       if (ctx->program->chip_class >= GFX8) {
 572          aco_ptr<SDWA_instruction> sdwa{create_instruction<SDWA_instruction>(aco_opcode::v_mov_b32, asSDWA(Format::VOP1), 1, 1)};
 573          sdwa->operands[0] = Operand(PhysReg{tmp}, v1);
 574          sdwa->definitions[0] = Definition(PhysReg{tmp}, v1);
 575          if (reduce_op == imin8 || reduce_op == imax8)
 576             sdwa->sel[0] = sdwa_sbyte;
 577          else
 578             sdwa->sel[0] = sdwa_ubyte;
 579          sdwa->dst_sel = sdwa_udword;
 580          bld.insert(std::move(sdwa));
 581       } else {
 582          aco_opcode opcode;
 583
 584          if (reduce_op == imin8 || reduce_op == imax8)
 585             opcode = aco_opcode::v_bfe_i32;
 586          else
 587             opcode = aco_opcode::v_bfe_u32;
 588
 589          bld.vop3(opcode, Definition(PhysReg{tmp}, v1),
 590                   Operand(PhysReg{tmp}, v1), Operand(0u), Operand(8u));
 591       }
 592    } else if (src.regClass() == v2b) {
 593       if (ctx->program->chip_class >= GFX10 &&
 594           (reduce_op == iadd16 || reduce_op == imax16 ||
 595            reduce_op == imin16 || reduce_op == umin16 || reduce_op == umax16)) {
 596          aco_ptr<SDWA_instruction> sdwa{create_instruction<SDWA_instruction>(aco_opcode::v_mov_b32, asSDWA(Format::VOP1), 1, 1)};
 597          sdwa->operands[0] = Operand(PhysReg{tmp}, v1);
 598          sdwa->definitions[0] = Definition(PhysReg{tmp}, v1);
 599          if (reduce_op == imin16 || reduce_op == imax16 || reduce_op == iadd16)
 600             sdwa->sel[0] = sdwa_sword;
 601          else
 602             sdwa->sel[0] = sdwa_uword;
 603          sdwa->dst_sel = sdwa_udword;
 604          bld.insert(std::move(sdwa));
 605       } else if (ctx->program->chip_class == GFX6 || ctx->program->chip_class == GFX7) {
 606          aco_opcode opcode;
 607
 608          if (reduce_op == imin16 || reduce_op == imax16 || reduce_op == iadd16)
 609             opcode = aco_opcode::v_bfe_i32;
 610          else
 611             opcode = aco_opcode::v_bfe_u32;
 612
 613          bld.vop3(opcode, Definition(PhysReg{tmp}, v1),
 614                   Operand(PhysReg{tmp}, v1), Operand(0u), Operand(16u));
 615       }
 616    }
 617
 618    bool reduction_needs_last_op = false;
 619    switch (op) {
 620    case aco_opcode::p_reduce:
 621       if (cluster_size == 1) break;
 622
 623       if (ctx->program->chip_class <= GFX7) {
 624          reduction_needs_last_op = true;
 625          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(1, 0, 3, 2));
 626          if (cluster_size == 2) break;
 627          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 628          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(2, 3, 0, 1));
 629          if (cluster_size == 4) break;
 630          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 631          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x04));
 632          if (cluster_size == 8) break;
 633          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 634          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x08));
 635          if (cluster_size == 16) break;
 636          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 637          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x10));
 638          if (cluster_size == 32) break;
 639          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 640          for (unsigned i = 0; i < src.size(); i++)
 641             bld.readlane(Definition(PhysReg{dst.physReg() + i}, s1), Operand(PhysReg{tmp + i}, v1), Operand(0u));
 642          // TODO: it would be more effective to do the last reduction step on SALU
 643          emit_op(ctx, tmp, dst.physReg(), tmp, vtmp, reduce_op, src.size());
 644          reduction_needs_last_op = false;
 645          break;
 646       }
 647
 648       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_quad_perm(1, 0, 3, 2), 0xf, 0xf, false);
 649       if (cluster_size == 2) break;
 650       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_quad_perm(2, 3, 0, 1), 0xf, 0xf, false);
 651       if (cluster_size == 4) break;
 652       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_half_mirror, 0xf, 0xf, false);
 653       if (cluster_size == 8) break;
 654       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_mirror, 0xf, 0xf, false);
 655       if (cluster_size == 16) break;
 656
 657       if (ctx->program->chip_class >= GFX10) {
 658          /* GFX10+ doesn't support row_bcast15 and row_bcast31 */
 659          for (unsigned i = 0; i < src.size(); i++)
 660             bld.vop3(aco_opcode::v_permlanex16_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1), Operand(0u), Operand(0u));
 661
 662          if (cluster_size == 32) {
 663             reduction_needs_last_op = true;
 664             break;
 665          }
 666
 667          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 668          for (unsigned i = 0; i < src.size(); i++)
 669             bld.readlane(Definition(PhysReg{dst.physReg() + i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(0u));
 670          // TODO: it would be more effective to do the last reduction step on SALU
 671          emit_op(ctx, tmp, dst.physReg(), tmp, vtmp, reduce_op, src.size());
 672          break;
 673       }
 674
 675       if (cluster_size == 32) {
 676          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x10));
 677          reduction_needs_last_op = true;
 678          break;
 679       }
 680       assert(cluster_size == 64);
 681       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_bcast15, 0xa, 0xf, false);
 682       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_bcast31, 0xc, 0xf, false);
 683       break;
 684    case aco_opcode::p_exclusive_scan:
 685       if (ctx->program->chip_class >= GFX10) { /* gfx10 doesn't support wf_sr1, so emulate it */
 686          /* shift rows right */
 687          emit_dpp_mov(ctx, vtmp, tmp, src.size(), dpp_row_sr(1), 0xf, 0xf, true);
 688
 689          /* fill in the gaps in rows 1 and 3 */
 690          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x10000u));
 691          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(0x10000u));
 692          for (unsigned i = 0; i < src.size(); i++) {
 693             Instruction *perm = bld.vop3(aco_opcode::v_permlanex16_b32,
 694                                          Definition(PhysReg{vtmp+i}, v1),
 695                                          Operand(PhysReg{tmp+i}, v1),
 696                                          Operand(0xffffffffu), Operand(0xffffffffu)).instr;
 697             static_cast<VOP3A_instruction*>(perm)->opsel = 1; /* FI (Fetch Inactive) */
 698          }
 699          bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(UINT64_MAX));
 700
 701          if (ctx->program->wave_size == 64) {
 702             /* fill in the gap in row 2 */
 703             for (unsigned i = 0; i < src.size(); i++) {
 704                bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 705                bld.writelane(Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{sitmp+i}, s1), Operand(32u), Operand(PhysReg{vtmp+i}, v1));
 706             }
 707          }
 708          std::swap(tmp, vtmp);
 709       } else if (ctx->program->chip_class >= GFX8) {
 710          emit_dpp_mov(ctx, tmp, tmp, src.size(), dpp_wf_sr1, 0xf, 0xf, true);
 711       } else {
 712          // TODO: use LDS on CS with a single write and shifted read
 713          /* wavefront shift_right by 1 on SI/CI */
 714          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(0, 0, 1, 2));
 715          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x07)); /* mirror(8) */
 716          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x10101010u));
 717          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 718          for (unsigned i = 0; i < src.size(); i++)
 719             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 720
 721          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 722          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x08)); /* swap(8) */
 723          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x01000100u));
 724          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 725          for (unsigned i = 0; i < src.size(); i++)
 726             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 727
 728          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 729          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x10)); /* swap(16) */
 730          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(1u), Operand(16u));
 731          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(1u), Operand(16u));
 732          for (unsigned i = 0; i < src.size(); i++)
 733             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 734
 735          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 736          for (unsigned i = 0; i < src.size(); i++) {
 737             bld.writelane(Definition(PhysReg{vtmp+i}, v1), identity[i], Operand(0u), Operand(PhysReg{vtmp+i}, v1));
 738             bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(0u));
 739             bld.writelane(Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{sitmp+i}, s1), Operand(32u), Operand(PhysReg{vtmp+i}, v1));
 740             identity[i] = Operand(0u); /* prevent further uses of identity */
 741          }
 742          std::swap(tmp, vtmp);
 743       }
 744
 745       for (unsigned i = 0; i < src.size(); i++) {
 746          if (!identity[i].isConstant() || identity[i].constantValue()) { /* bound_ctrl should take care of this overwise */
 747             if (ctx->program->chip_class < GFX10)
 748                assert((identity[i].isConstant() && !identity[i].isLiteral()) || identity[i].physReg() == PhysReg{sitmp+i});
 749             bld.writelane(Definition(PhysReg{tmp+i}, v1), identity[i], Operand(0u), Operand(PhysReg{tmp+i}, v1));
 750          }
 751       }
 752       /* fall through */
 753    case aco_opcode::p_inclusive_scan:
 754       assert(cluster_size == ctx->program->wave_size);
 755       if (ctx->program->chip_class <= GFX7) {
 756          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1e, 0x00, 0x00));
 757          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xAAAAAAAAu));
 758          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 759          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 760
 761          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 762          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1c, 0x01, 0x00));
 763          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xCCCCCCCCu));
 764          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 765          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 766
 767          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 768          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x18, 0x03, 0x00));
 769          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xF0F0F0F0u));
 770          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 771          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 772
 773          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 774          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x10, 0x07, 0x00));
 775          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xFF00FF00u));
 776          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 777          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 778
 779          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 780          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x00, 0x0f, 0x00));
 781          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(16u), Operand(16u));
 782          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(16u), Operand(16u));
 783          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 784
 785          for (unsigned i = 0; i < src.size(); i++)
 786             bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 787          bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 788          emit_op(ctx, tmp, sitmp, tmp, vtmp, reduce_op, src.size());
 789          break;
 790       }
 791
 792       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 793                   dpp_row_sr(1), 0xf, 0xf, false, identity);
 794       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 795                   dpp_row_sr(2), 0xf, 0xf, false, identity);
 796       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 797                   dpp_row_sr(4), 0xf, 0xf, false, identity);
 798       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 799                   dpp_row_sr(8), 0xf, 0xf, false, identity);
 800       if (ctx->program->chip_class >= GFX10) {
 801          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(16u), Operand(16u));
 802          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(16u), Operand(16u));
 803          for (unsigned i = 0; i < src.size(); i++) {
 804             Instruction *perm = bld.vop3(aco_opcode::v_permlanex16_b32,
 805                                          Definition(PhysReg{vtmp+i}, v1),
 806                                          Operand(PhysReg{tmp+i}, v1),
 807                                          Operand(0xffffffffu), Operand(0xffffffffu)).instr;
 808             static_cast<VOP3A_instruction*>(perm)->opsel = 1; /* FI (Fetch Inactive) */
 809          }
 810          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 811
 812          if (ctx->program->wave_size == 64) {
 813             bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 814             for (unsigned i = 0; i < src.size(); i++)
 815                bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 816             emit_op(ctx, tmp, sitmp, tmp, vtmp, reduce_op, src.size());
 817          }
 818       } else {
 819          emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 820                      dpp_row_bcast15, 0xa, 0xf, false, identity);
 821          emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 822                      dpp_row_bcast31, 0xc, 0xf, false, identity);
 823       }
 824       break;
 825    default:
 826       unreachable("Invalid reduction mode");
 827    }
 828
 829
 830    if (op == aco_opcode::p_reduce) {
 831       if (reduction_needs_last_op && dst.regClass().type() == RegType::vgpr) {
 832          bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(stmp, bld.lm));
 833          emit_op(ctx, dst.physReg(), tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 834          return;
 835       }
 836
 837       if (reduction_needs_last_op)
 838          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 839    }
 840
 841    /* restore exec */
 842    bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(stmp, bld.lm));
 843
 844    if (dst.regClass().type() == RegType::sgpr) {
 845       for (unsigned k = 0; k < src.size(); k++) {
 846          bld.readlane(Definition(PhysReg{dst.physReg() + k}, s1),
 847                       Operand(PhysReg{tmp + k}, v1), Operand(ctx->program->wave_size - 1));
 848       }
 849    } else if (dst.physReg() != tmp) {
 850       for (unsigned k = 0; k < src.size(); k++) {
 851          bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{dst.physReg() + k}, v1),
 852                   Operand(PhysReg{tmp + k}, v1));
 853       }
 854    }
 855 }
 856
 857 void emit_gfx10_wave64_bpermute(Program *program, aco_ptr<Instruction> &instr, Builder &bld)
 858 {
 859    /* Emulates proper bpermute on GFX10 in wave64 mode.
 860     *
 861     * This is necessary because on GFX10 the bpermute instruction only works
 862     * on half waves (you can think of it as having a cluster size of 32), so we
 863     * manually swap the data between the two halves using two shared VGPRs.
 864     */
 865
 866    assert(program->chip_class >= GFX10);
 867    assert(program->info->wave_size == 64);
 868
 869    unsigned shared_vgpr_reg_0 = align(program->config->num_vgprs, 4) + 256;
 870    Definition dst = instr->definitions[0];
 871    Definition tmp_exec = instr->definitions[1];
 872    Definition clobber_scc = instr->definitions[2];
 873    Operand index_x4 = instr->operands[0];
 874    Operand input_data = instr->operands[1];
 875    Operand same_half = instr->operands[2];
 876
 877    assert(dst.regClass() == v1);
 878    assert(tmp_exec.regClass() == bld.lm);
 879    assert(clobber_scc.isFixed() && clobber_scc.physReg() == scc);
 880    assert(same_half.regClass() == bld.lm);
 881    assert(index_x4.regClass() == v1);
 882    assert(input_data.regClass().type() == RegType::vgpr);
 883    assert(input_data.bytes() <= 4);
 884    assert(dst.physReg() != index_x4.physReg());
 885    assert(dst.physReg() != input_data.physReg());
 886    assert(tmp_exec.physReg() != same_half.physReg());
 887
 888    PhysReg shared_vgpr_lo(shared_vgpr_reg_0);
 889    PhysReg shared_vgpr_hi(shared_vgpr_reg_0 + 1);
 890
 891    /* Permute the input within the same half-wave */
 892    bld.ds(aco_opcode::ds_bpermute_b32, dst, index_x4, input_data);
 893
 894    /* HI: Copy data from high lanes 32-63 to shared vgpr */
 895    bld.vop1_dpp(aco_opcode::v_mov_b32, Definition(shared_vgpr_hi, v1), input_data, dpp_quad_perm(0, 1, 2, 3), 0xc, 0xf, false);
 896    /* Save EXEC */
 897    bld.sop1(aco_opcode::s_mov_b64, tmp_exec, Operand(exec, s2));
 898    /* Set EXEC to enable LO lanes only */
 899    bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(0u));
 900    /* LO: Copy data from low lanes 0-31 to shared vgpr */
 901    bld.vop1(aco_opcode::v_mov_b32, Definition(shared_vgpr_lo, v1), input_data);
 902    /* LO: bpermute shared vgpr (high lanes' data) */
 903    bld.ds(aco_opcode::ds_bpermute_b32, Definition(shared_vgpr_hi, v1), index_x4, Operand(shared_vgpr_hi, v1));
 904    /* Set EXEC to enable HI lanes only */
 905    bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 906    /* HI: bpermute shared vgpr (low lanes' data) */
 907    bld.ds(aco_opcode::ds_bpermute_b32, Definition(shared_vgpr_lo, v1), index_x4, Operand(shared_vgpr_lo, v1));
 908
 909    /* Only enable lanes which use the other half's data */
 910    bld.sop2(aco_opcode::s_andn2_b64, Definition(exec, s2), clobber_scc, Operand(tmp_exec.physReg(), s2), same_half);
 911    /* LO: Copy shared vgpr (high lanes' bpermuted data) to output vgpr */
 912    bld.vop1_dpp(aco_opcode::v_mov_b32, dst, Operand(shared_vgpr_hi, v1), dpp_quad_perm(0, 1, 2, 3), 0x3, 0xf, false);
 913    /* HI: Copy shared vgpr (low lanes' bpermuted data) to output vgpr */
 914    bld.vop1_dpp(aco_opcode::v_mov_b32, dst, Operand(shared_vgpr_lo, v1), dpp_quad_perm(0, 1, 2, 3), 0xc, 0xf, false);
 915
 916    /* Restore saved EXEC */
 917    bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(tmp_exec.physReg(), s2));
 918
 919    /* RA assumes that the result is always in the low part of the register, so we have to shift, if it's not there already */
 920    if (input_data.physReg().byte()) {
 921       unsigned right_shift = input_data.physReg().byte() * 8;
 922       bld.vop2(aco_opcode::v_lshrrev_b32, dst, Operand(right_shift), Operand(dst.physReg(), v1));
 923    }
 924 }
 925
 926 void emit_gfx6_bpermute(Program *program, aco_ptr<Instruction> &instr, Builder &bld)
 927 {
 928    /* Emulates bpermute using readlane instructions */
 929
 930    Operand index = instr->operands[0];
 931    Operand input = instr->operands[1];
 932    Definition dst = instr->definitions[0];
 933    Definition temp_exec = instr->definitions[1];
 934    Definition clobber_vcc = instr->definitions[2];
 935
 936    assert(dst.regClass() == v1);
 937    assert(temp_exec.regClass() == bld.lm);
 938    assert(clobber_vcc.regClass() == bld.lm);
 939    assert(clobber_vcc.physReg() == vcc);
 940    assert(index.regClass() == v1);
 941    assert(index.physReg() != dst.physReg());
 942    assert(input.regClass().type() == RegType::vgpr);
 943    assert(input.bytes() <= 4);
 944    assert(input.physReg() != dst.physReg());
 945
 946    /* Save original EXEC */
 947    bld.sop1(aco_opcode::s_mov_b64, temp_exec, Operand(exec, s2));
 948
 949    /* An "unrolled loop" that is executed per each lane.
 950     * This takes only a few instructions per lane, as opposed to a "real" loop
 951     * with branching, where the branch instruction alone would take 16+ cycles.
 952     */
 953    for (unsigned n = 0; n < program->wave_size; ++n) {
 954       /* Activate the lane which has N for its source index */
 955       bld.vopc(aco_opcode::v_cmpx_eq_u32, Definition(exec, bld.lm), clobber_vcc, Operand(n), index);
 956       /* Read the data from lane N */
 957       bld.readlane(Definition(vcc, s1), input, Operand(n));
 958       /* On the active lane, move the data we read from lane N to the destination VGPR */
 959       bld.vop1(aco_opcode::v_mov_b32, dst, Operand(vcc, s1));
 960       /* Restore original EXEC */
 961       bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(temp_exec.physReg(), s2));
 962    }
 963 }
 964
 965 struct copy_operation {
 966    Operand op;
 967    Definition def;
 968    unsigned bytes;
 969    union {
 970       uint8_t uses[8];
 971       uint64_t is_used = 0;
 972    };
 973 };
 974
 975 void split_copy(unsigned offset, Definition *def, Operand *op, const copy_operation& src, bool ignore_uses, unsigned max_size)
 976 {
 977    PhysReg def_reg = src.def.physReg();
 978    PhysReg op_reg = src.op.physReg();
 979    def_reg.reg_b += offset;
 980    op_reg.reg_b += offset;
 981
 982    max_size = MIN2(max_size, src.def.regClass().type() == RegType::vgpr ? 4 : 8);
 983
 984    /* make sure the size is a power of two and reg % bytes == 0 */
 985    unsigned bytes = 1;
 986    for (; bytes <= max_size; bytes *= 2) {
 987       unsigned next = bytes * 2u;
 988       bool can_increase = def_reg.reg_b % next == 0 &&
 989                           offset + next <= src.bytes && next <= max_size;
 990       if (!src.op.isConstant() && can_increase)
 991          can_increase = op_reg.reg_b % next == 0;
 992       for (unsigned i = 0; !ignore_uses && can_increase && (i < bytes); i++)
 993          can_increase = (src.uses[offset + bytes + i] == 0) == (src.uses[offset] == 0);
 994       if (!can_increase)
 995          break;
 996    }
 997
 998    RegClass def_cls = bytes % 4 == 0 ? RegClass(src.def.regClass().type(), bytes / 4u) :
 999                       RegClass(src.def.regClass().type(), bytes).as_subdword();
1000    *def = Definition(src.def.tempId(), def_reg, def_cls);
1001    if (src.op.isConstant()) {
1002       assert(offset == 0 || (offset == 4 && src.op.bytes() == 8));
1003       if (src.op.bytes() == 8 && bytes == 4)
1004          *op = Operand(uint32_t(src.op.constantValue64() >> (offset * 8u)));
1005       else
1006          *op  = src.op;
1007    } else {
1008       RegClass op_cls = bytes % 4 == 0 ? RegClass(src.op.regClass().type(), bytes / 4u) :
1009                         RegClass(src.op.regClass().type(), bytes).as_subdword();
1010       *op = Operand(op_reg, op_cls);
1011       op->setTemp(Temp(src.op.tempId(), op_cls));
1012    }
1013 }
1014
1015 uint32_t get_intersection_mask(int a_start, int a_size,
1016                                int b_start, int b_size)
1017 {
1018    int intersection_start = MAX2(b_start - a_start, 0);
1019    int intersection_end = MAX2(b_start + b_size - a_start, 0);
1020    if (intersection_start >= a_size || intersection_end == 0)
1021       return 0;
1022
1023    uint32_t mask = u_bit_consecutive(0, a_size);
1024    return u_bit_consecutive(intersection_start, intersection_end - intersection_start) & mask;
1025 }
1026
1027 bool do_copy(lower_context* ctx, Builder& bld, const copy_operation& copy, bool *preserve_scc)
1028 {
1029    bool did_copy = false;
1030    for (unsigned offset = 0; offset < copy.bytes;) {
1031       if (copy.uses[offset]) {
1032          offset++;
1033          continue;
1034       }
1035
1036       Definition def;
1037       Operand op;
1038       split_copy(offset, &def, &op, copy, false, 8);
1039
1040       if (def.physReg() == scc) {
1041          bld.sopc(aco_opcode::s_cmp_lg_i32, def, op, Operand(0u));
1042          *preserve_scc = true;
1043       } else if (def.bytes() == 8 && def.getTemp().type() == RegType::sgpr) {
1044          bld.sop1(aco_opcode::s_mov_b64, def, Operand(op.physReg(), s2));
1045       } else {
1046          bld.copy(def, op);
1047       }
1048
1049       ctx->program->statistics[statistic_copies]++;
1050
1051       did_copy = true;
1052       offset += def.bytes();
1053    }
1054    return did_copy;
1055 }
1056
1057 void do_swap(lower_context *ctx, Builder& bld, const copy_operation& copy, bool preserve_scc, Pseudo_instruction *pi)
1058 {
1059    unsigned offset = 0;
1060
1061    if (copy.bytes == 3 && (copy.def.physReg().reg_b % 4 <= 1) &&
1062        (copy.def.physReg().reg_b % 4) == (copy.op.physReg().reg_b % 4)) {
1063       /* instead of doing a 2-byte and 1-byte swap, do a 4-byte swap and then fixup with a 1-byte swap */
1064       PhysReg op = copy.op.physReg();
1065       PhysReg def = copy.def.physReg();
1066       op.reg_b &= ~0x3;
1067       def.reg_b &= ~0x3;
1068
1069       copy_operation tmp;
1070       tmp.op = Operand(op, v1);
1071       tmp.def = Definition(def, v1);
1072       tmp.bytes = 4;
1073       memset(tmp.uses, 1, 4);
1074       do_swap(ctx, bld, tmp, preserve_scc, pi);
1075
1076       op.reg_b += copy.def.physReg().reg_b % 4 == 0 ? 3 : 0;
1077       def.reg_b += copy.def.physReg().reg_b % 4 == 0 ? 3 : 0;
1078       tmp.op = Operand(op, v1b);
1079       tmp.def = Definition(def, v1b);
1080       tmp.bytes = 1;
1081       tmp.uses[0] = 1;
1082       do_swap(ctx, bld, tmp, preserve_scc, pi);
1083
1084       offset = copy.bytes;
1085    }
1086
1087    for (; offset < copy.bytes;) {
1088       Definition def;
1089       Operand op;
1090       split_copy(offset, &def, &op, copy, true, 8);
1091
1092       assert(op.regClass() == def.regClass());
1093       Operand def_as_op = Operand(def.physReg(), def.regClass());
1094       Definition op_as_def = Definition(op.physReg(), op.regClass());
1095       if (ctx->program->chip_class >= GFX9 && def.regClass() == v1) {
1096          bld.vop1(aco_opcode::v_swap_b32, def, op_as_def, op, def_as_op);
1097          ctx->program->statistics[statistic_copies]++;
1098       } else if (def.regClass() == v1) {
1099          bld.vop2(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1100          bld.vop2(aco_opcode::v_xor_b32, def, op, def_as_op);
1101          bld.vop2(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1102          ctx->program->statistics[statistic_copies] += 3;
1103       } else if (op.physReg() == scc || def.physReg() == scc) {
1104          /* we need to swap scc and another sgpr */
1105          assert(!preserve_scc);
1106
1107          PhysReg other = op.physReg() == scc ? def.physReg() : op.physReg();
1108
1109          bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), Operand(scc, s1));
1110          bld.sopc(aco_opcode::s_cmp_lg_i32, Definition(scc, s1), Operand(other, s1), Operand(0u));
1111          bld.sop1(aco_opcode::s_mov_b32, Definition(other, s1), Operand(pi->scratch_sgpr, s1));
1112          ctx->program->statistics[statistic_copies] += 3;
1113       } else if (def.regClass() == s1) {
1114          if (preserve_scc) {
1115             bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), op);
1116             bld.sop1(aco_opcode::s_mov_b32, op_as_def, def_as_op);
1117             bld.sop1(aco_opcode::s_mov_b32, def, Operand(pi->scratch_sgpr, s1));
1118          } else {
1119             bld.sop2(aco_opcode::s_xor_b32, op_as_def, Definition(scc, s1), op, def_as_op);
1120             bld.sop2(aco_opcode::s_xor_b32, def, Definition(scc, s1), op, def_as_op);
1121             bld.sop2(aco_opcode::s_xor_b32, op_as_def, Definition(scc, s1), op, def_as_op);
1122          }
1123          ctx->program->statistics[statistic_copies] += 3;
1124       } else if (def.regClass() == s2) {
1125          if (preserve_scc)
1126             bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), Operand(scc, s1));
1127          bld.sop2(aco_opcode::s_xor_b64, op_as_def, Definition(scc, s1), op, def_as_op);
1128          bld.sop2(aco_opcode::s_xor_b64, def, Definition(scc, s1), op, def_as_op);
1129          bld.sop2(aco_opcode::s_xor_b64, op_as_def, Definition(scc, s1), op, def_as_op);
1130          if (preserve_scc)
1131             bld.sopc(aco_opcode::s_cmp_lg_i32, Definition(scc, s1), Operand(pi->scratch_sgpr, s1), Operand(0u));
1132          ctx->program->statistics[statistic_copies] += 3;
1133       } else if (ctx->program->chip_class >= GFX9 && def.bytes() == 2 && def.physReg().reg() == op.physReg().reg()) {
1134          aco_ptr<VOP3P_instruction> vop3p{create_instruction<VOP3P_instruction>(aco_opcode::v_pk_add_u16, Format::VOP3P, 2, 1)};
1135          vop3p->operands[0] = Operand(PhysReg{op.physReg().reg()}, v1);
1136          vop3p->operands[1] = Operand(0u);
1137          vop3p->definitions[0] = Definition(PhysReg{op.physReg().reg()}, v1);
1138          vop3p->opsel_lo = 0x1;
1139          vop3p->opsel_hi = 0x2;
1140          bld.insert(std::move(vop3p));
1141       } else {
1142          assert(def.regClass().is_subdword());
1143          bld.vop2_sdwa(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1144          bld.vop2_sdwa(aco_opcode::v_xor_b32, def, op, def_as_op);
1145          bld.vop2_sdwa(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1146          ctx->program->statistics[statistic_copies] += 3;
1147       }
1148
1149       offset += def.bytes();
1150    }
1151
1152    /* fixup in case we swapped bytes we shouldn't have */
1153    copy_operation tmp_copy = copy;
1154    tmp_copy.op.setFixed(copy.def.physReg());
1155    tmp_copy.def.setFixed(copy.op.physReg());
1156    do_copy(ctx, bld, tmp_copy, &preserve_scc);
1157 }
1158
1159 void handle_operands(std::map<PhysReg, copy_operation>& copy_map, lower_context* ctx, chip_class chip_class, Pseudo_instruction *pi)
1160 {
1161    Builder bld(ctx->program, &ctx->instructions);
1162    aco_ptr<Instruction> mov;
1163    std::map<PhysReg, copy_operation>::iterator it = copy_map.begin();
1164    std::map<PhysReg, copy_operation>::iterator target;
1165    bool writes_scc = false;
1166
1167    /* count the number of uses for each dst reg */
1168    while (it != copy_map.end()) {
1169
1170       if (it->second.def.physReg() == scc)
1171          writes_scc = true;
1172
1173       assert(!pi->tmp_in_scc || !(it->second.def.physReg() == pi->scratch_sgpr));
1174
1175       /* if src and dst reg are the same, remove operation */
1176       if (it->first == it->second.op.physReg()) {
1177          it = copy_map.erase(it);
1178          continue;
1179       }
1180
1181       /* split large copies */
1182       if (it->second.bytes > 8) {
1183          assert(!it->second.op.isConstant());
1184          assert(!it->second.def.regClass().is_subdword());
1185          RegClass rc = RegClass(it->second.def.regClass().type(), it->second.def.size() - 2);
1186          Definition hi_def = Definition(PhysReg{it->first + 2}, rc);
1187          rc = RegClass(it->second.op.regClass().type(), it->second.op.size() - 2);
1188          Operand hi_op = Operand(PhysReg{it->second.op.physReg() + 2}, rc);
1189          copy_operation copy = {hi_op, hi_def, it->second.bytes - 8};
1190          copy_map[hi_def.physReg()] = copy;
1191          assert(it->second.op.physReg().byte() == 0 && it->second.def.physReg().byte() == 0);
1192          it->second.op = Operand(it->second.op.physReg(), it->second.op.regClass().type() == RegType::sgpr ? s2 : v2);
1193          it->second.def = Definition(it->second.def.physReg(), it->second.def.regClass().type() == RegType::sgpr ? s2 : v2);
1194          it->second.bytes = 8;
1195       }
1196
1197       /* check if the definition reg is used by another copy operation */
1198       for (std::pair<const PhysReg, copy_operation>& copy : copy_map) {
1199          if (copy.second.op.isConstant())
1200             continue;
1201          for (uint16_t i = 0; i < it->second.bytes; i++) {
1202             /* distance might underflow */
1203             unsigned distance = it->first.reg_b + i - copy.second.op.physReg().reg_b;
1204             if (distance < copy.second.bytes)
1205                it->second.uses[i] += 1;
1206          }
1207       }
1208
1209       ++it;
1210    }
1211
1212    /* first, handle paths in the location transfer graph */
1213    bool preserve_scc = pi->tmp_in_scc && !writes_scc;
1214    it = copy_map.begin();
1215    while (it != copy_map.end()) {
1216
1217       /* try to coalesce 32-bit sgpr copies to 64-bit copies */
1218       if (it->second.is_used == 0 &&
1219           it->second.def.getTemp().type() == RegType::sgpr && it->second.bytes == 4 &&
1220           !it->second.op.isConstant() && it->first % 2 == it->second.op.physReg() % 2) {
1221
1222          PhysReg other_def_reg = PhysReg{it->first % 2 ? it->first - 1 : it->first + 1};
1223          PhysReg other_op_reg = PhysReg{it->first % 2 ? it->second.op.physReg() - 1 : it->second.op.physReg() + 1};
1224          std::map<PhysReg, copy_operation>::iterator other = copy_map.find(other_def_reg);
1225
1226          if (other != copy_map.end() && !other->second.is_used && other->second.bytes == 4 &&
1227              other->second.op.physReg() == other_op_reg && !other->second.op.isConstant()) {
1228             std::map<PhysReg, copy_operation>::iterator to_erase = it->first % 2 ? it : other;
1229             it = it->first % 2 ? other : it;
1230             copy_map.erase(to_erase);
1231             it->second.bytes = 8;
1232          }
1233       }
1234       // TODO: try to coalesce subdword copies
1235
1236       /* find portions where the target reg is not used as operand for any other copy */
1237       if (it->second.is_used) {
1238          if (it->second.op.isConstant()) {
1239             /* we have to skip constants until is_used=0 */
1240             ++it;
1241             continue;
1242          }
1243
1244          unsigned has_zero_use_bytes = 0;
1245          for (unsigned i = 0; i < it->second.bytes; i++)
1246             has_zero_use_bytes |= (it->second.uses[i] == 0) << i;
1247
1248          if (has_zero_use_bytes) {
1249             /* Skipping partial copying and doing a v_swap_b32 and then fixup
1250              * copies is usually beneficial for sub-dword copies, but if doing
1251              * a partial copy allows further copies, it should be done instead. */
1252             bool partial_copy = (has_zero_use_bytes == 0xf) || (has_zero_use_bytes == 0xf0);
1253             for (std::pair<const PhysReg, copy_operation>& copy : copy_map) {
1254                if (partial_copy)
1255                   break;
1256                for (uint16_t i = 0; i < copy.second.bytes; i++) {
1257                   /* distance might underflow */
1258                   unsigned distance = copy.first.reg_b + i - it->second.op.physReg().reg_b;
1259                   if (distance < it->second.bytes && copy.second.uses[i] == 1 &&
1260                       !it->second.uses[distance])
1261                      partial_copy = true;
1262                }
1263             }
1264
1265             if (!partial_copy) {
1266                ++it;
1267                continue;
1268             }
1269          } else {
1270             /* full target reg is used: register swapping needed */
1271             ++it;
1272             continue;
1273          }
1274       }
1275
1276       bool did_copy = do_copy(ctx, bld, it->second, &preserve_scc);
1277
1278       std::pair<PhysReg, copy_operation> copy = *it;
1279
1280       if (it->second.is_used == 0) {
1281          /* the target reg is not used as operand for any other copy, so we
1282           * copied to all of it */
1283          copy_map.erase(it);
1284          it = copy_map.begin();
1285       } else {
1286          /* we only performed some portions of this copy, so split it to only
1287           * leave the portions that still need to be done */
1288          copy_operation original = it->second; /* the map insertion below can overwrite this */
1289          copy_map.erase(it);
1290          for (unsigned offset = 0; offset < original.bytes;) {
1291             if (original.uses[offset] == 0) {
1292                offset++;
1293                continue;
1294             }
1295             Definition def;
1296             Operand op;
1297             split_copy(offset, &def, &op, original, false, 8);
1298
1299             copy_operation copy = {op, def, def.bytes()};
1300             for (unsigned i = 0; i < copy.bytes; i++)
1301                copy.uses[i] = original.uses[i + offset];
1302             copy_map[def.physReg()] = copy;
1303
1304             offset += def.bytes();
1305          }
1306
1307          it = copy_map.begin();
1308       }
1309
1310       /* Reduce the number of uses of the operand reg by one. Do this after
1311        * splitting the copy or removing it in case the copy writes to it's own
1312        * operand (for example, v[7:8] = v[8:9]) */
1313       if (did_copy && !copy.second.op.isConstant()) {
1314          for (std::pair<const PhysReg, copy_operation>& other : copy_map) {
1315              for (uint16_t i = 0; i < other.second.bytes; i++) {
1316                /* distance might underflow */
1317                unsigned distance = other.first.reg_b + i - copy.second.op.physReg().reg_b;
1318                if (distance < copy.second.bytes && !copy.second.uses[distance])
1319                   other.second.uses[i] -= 1;
1320             }
1321          }
1322       }
1323    }
1324
1325    if (copy_map.empty())
1326       return;
1327
1328    /* all target regs are needed as operand somewhere which means, all entries are part of a cycle */
1329    unsigned largest = 0;
1330    for (const std::pair<const PhysReg, copy_operation>& op : copy_map)
1331       largest = MAX2(largest, op.second.bytes);
1332
1333    while (!copy_map.empty()) {
1334
1335       /* Perform larger swaps first, because larger swaps swaps can make other
1336        * swaps unnecessary. */
1337       auto it = copy_map.begin();
1338       for (auto it2 = copy_map.begin(); it2 != copy_map.end(); ++it2) {
1339          if (it2->second.bytes > it->second.bytes) {
1340             it = it2;
1341             if (it->second.bytes == largest)
1342                break;
1343          }
1344       }
1345
1346       /* should already be done */
1347       assert(!it->second.op.isConstant());
1348
1349       assert(it->second.op.isFixed());
1350       assert(it->second.def.regClass() == it->second.op.regClass());
1351
1352       if (it->first == it->second.op.physReg()) {
1353          copy_map.erase(it);
1354          continue;
1355       }
1356
1357       if (preserve_scc && it->second.def.getTemp().type() == RegType::sgpr)
1358          assert(!(it->second.def.physReg() == pi->scratch_sgpr));
1359
1360       /* to resolve the cycle, we have to swap the src reg with the dst reg */
1361       copy_operation swap = it->second;
1362
1363       /* if this is self-intersecting, we have to split it because
1364        * self-intersecting swaps don't make sense */
1365       PhysReg lower = swap.def.physReg();
1366       PhysReg higher = swap.op.physReg();
1367       if (lower.reg_b > higher.reg_b)
1368          std::swap(lower, higher);
1369       if (higher.reg_b - lower.reg_b < (int)swap.bytes) {
1370          unsigned offset = higher.reg_b - lower.reg_b;
1371          RegType type = swap.def.regClass().type();
1372
1373          copy_operation middle;
1374          lower.reg_b += offset;
1375          higher.reg_b += offset;
1376          middle.bytes = swap.bytes - offset * 2;
1377          memcpy(middle.uses, swap.uses + offset, middle.bytes);
1378          middle.op = Operand(lower, RegClass::get(type, middle.bytes));
1379          middle.def = Definition(higher, RegClass::get(type, middle.bytes));
1380          copy_map[higher] = middle;
1381
1382          copy_operation end;
1383          lower.reg_b += middle.bytes;
1384          higher.reg_b += middle.bytes;
1385          end.bytes = swap.bytes - (offset + middle.bytes);
1386          memcpy(end.uses, swap.uses + offset + middle.bytes, end.bytes);
1387          end.op = Operand(lower, RegClass::get(type, end.bytes));
1388          end.def = Definition(higher, RegClass::get(type, end.bytes));
1389          copy_map[higher] = end;
1390
1391          memset(swap.uses + offset, 0, swap.bytes - offset);
1392          swap.bytes = offset;
1393       }
1394
1395       do_swap(ctx, bld, swap, preserve_scc, pi);
1396
1397       /* remove from map */
1398       copy_map.erase(it);
1399
1400       /* change the operand reg of the target's uses and split uses if needed */
1401       target = copy_map.begin();
1402       uint32_t bytes_left = u_bit_consecutive(0, swap.bytes);
1403       for (; target != copy_map.end(); ++target) {
1404          if (target->second.op.physReg() == swap.def.physReg() && swap.bytes == target->second.bytes) {
1405             target->second.op.setFixed(swap.op.physReg());
1406             break;
1407          }
1408
1409          uint32_t imask = get_intersection_mask(swap.def.physReg().reg_b, swap.bytes,
1410                                                 target->second.op.physReg().reg_b, target->second.bytes);
1411
1412          if (!imask)
1413             continue;
1414
1415          assert(target->second.bytes < swap.bytes);
1416
1417          int offset = (int)target->second.op.physReg().reg_b - (int)swap.def.physReg().reg_b;
1418
1419          /* split and update the middle (the portion that reads the swap's
1420           * definition) to read the swap's operand instead */
1421          int target_op_end = target->second.op.physReg().reg_b + target->second.bytes;
1422          int swap_def_end = swap.def.physReg().reg_b + swap.bytes;
1423          int before_bytes = MAX2(-offset, 0);
1424          int after_bytes = MAX2(target_op_end - swap_def_end, 0);
1425          int middle_bytes = target->second.bytes - before_bytes - after_bytes;
1426
1427          if (after_bytes) {
1428             unsigned after_offset = before_bytes + middle_bytes;
1429             assert(after_offset > 0);
1430             copy_operation copy;
1431             copy.bytes = after_bytes;
1432             memcpy(copy.uses, target->second.uses + after_offset, copy.bytes);
1433             RegClass rc = RegClass::get(target->second.op.regClass().type(), after_bytes);
1434             copy.op = Operand(target->second.op.physReg().advance(after_offset), rc);
1435             copy.def = Definition(target->second.def.physReg().advance(after_offset), rc);
1436             copy_map[copy.def.physReg()] = copy;
1437          }
1438
1439          if (middle_bytes) {
1440             copy_operation copy;
1441             copy.bytes = middle_bytes;
1442             memcpy(copy.uses, target->second.uses + before_bytes, copy.bytes);
1443             RegClass rc = RegClass::get(target->second.op.regClass().type(), middle_bytes);
1444             copy.op = Operand(swap.op.physReg().advance(MAX2(offset, 0)), rc);
1445             copy.def = Definition(target->second.def.physReg().advance(before_bytes), rc);
1446             copy_map[copy.def.physReg()] = copy;
1447          }
1448
1449          if (before_bytes) {
1450             copy_operation copy;
1451             target->second.bytes = before_bytes;
1452             RegClass rc = RegClass::get(target->second.op.regClass().type(), before_bytes);
1453             target->second.op = Operand(target->second.op.physReg(), rc);
1454             target->second.def = Definition(target->second.def.physReg(), rc);
1455             memset(target->second.uses + target->second.bytes, 0, 8 - target->second.bytes);
1456          }
1457
1458          /* break early since we know each byte of the swap's definition is used
1459           * at most once */
1460          bytes_left &= ~imask;
1461          if (!bytes_left)
1462             break;
1463       }
1464    }
1465 }
1466
1467 void lower_to_hw_instr(Program* program)
1468 {
1469    Block *discard_block = NULL;
1470
1471    for (size_t i = 0; i < program->blocks.size(); i++)
1472    {
1473       Block *block = &program->blocks[i];
1474       lower_context ctx;
1475       ctx.program = program;
1476       Builder bld(program, &ctx.instructions);
1477
1478       bool set_mode = i == 0 && block->fp_mode.val != program->config->float_mode;
1479       for (unsigned pred : block->linear_preds) {
1480          if (program->blocks[pred].fp_mode.val != block->fp_mode.val) {
1481             set_mode = true;
1482             break;
1483          }
1484       }
1485       if (set_mode) {
1486          /* only allow changing modes at top-level blocks so this doesn't break
1487           * the "jump over empty blocks" optimization */
1488          assert(block->kind & block_kind_top_level);
1489          uint32_t mode = block->fp_mode.val;
1490          /* "((size - 1) << 11) | register" (MODE is encoded as register 1) */
1491          bld.sopk(aco_opcode::s_setreg_imm32_b32, Operand(mode), (7 << 11) | 1);
1492       }
1493
1494       for (size_t j = 0; j < block->instructions.size(); j++) {
1495          aco_ptr<Instruction>& instr = block->instructions[j];
1496          aco_ptr<Instruction> mov;
1497          if (instr->format == Format::PSEUDO) {
1498             Pseudo_instruction *pi = (Pseudo_instruction*)instr.get();
1499
1500             switch (instr->opcode)
1501             {
1502             case aco_opcode::p_extract_vector:
1503             {
1504                PhysReg reg = instr->operands[0].physReg();
1505                Definition& def = instr->definitions[0];
1506                reg.reg_b += instr->operands[1].constantValue() * def.bytes();
1507
1508                if (reg == def.physReg())
1509                   break;
1510
1511                RegClass op_rc = def.regClass().is_subdword() ? def.regClass() :
1512                                 RegClass(instr->operands[0].getTemp().type(), def.size());
1513                std::map<PhysReg, copy_operation> copy_operations;
1514                copy_operations[def.physReg()] = {Operand(reg, op_rc), def, def.bytes()};
1515                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1516                break;
1517             }
1518             case aco_opcode::p_create_vector:
1519             {
1520                std::map<PhysReg, copy_operation> copy_operations;
1521                PhysReg reg = instr->definitions[0].physReg();
1522
1523                for (const Operand& op : instr->operands) {
1524                   if (op.isConstant()) {
1525                      const Definition def = Definition(reg, RegClass(instr->definitions[0].getTemp().type(), op.size()));
1526                      copy_operations[reg] = {op, def, op.bytes()};
1527                      reg.reg_b += op.bytes();
1528                      continue;
1529                   }
1530                   if (op.isUndefined()) {
1531                      // TODO: coalesce subdword copies if dst byte is 0
1532                      reg.reg_b += op.bytes();
1533                      continue;
1534                   }
1535
1536                   RegClass rc_def = op.regClass().is_subdword() ? op.regClass() :
1537                                     RegClass(instr->definitions[0].getTemp().type(), op.size());
1538                   const Definition def = Definition(reg, rc_def);
1539                   copy_operations[def.physReg()] = {op, def, op.bytes()};
1540                   reg.reg_b += op.bytes();
1541                }
1542                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1543                break;
1544             }
1545             case aco_opcode::p_split_vector:
1546             {
1547                std::map<PhysReg, copy_operation> copy_operations;
1548                PhysReg reg = instr->operands[0].physReg();
1549
1550                for (const Definition& def : instr->definitions) {
1551                   RegClass rc_op = def.regClass().is_subdword() ? def.regClass() :
1552                                    RegClass(instr->operands[0].getTemp().type(), def.size());
1553                   const Operand op = Operand(reg, rc_op);
1554                   copy_operations[def.physReg()] = {op, def, def.bytes()};
1555                   reg.reg_b += def.bytes();
1556                }
1557                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1558                break;
1559             }
1560             case aco_opcode::p_parallelcopy:
1561             case aco_opcode::p_wqm:
1562             {
1563                std::map<PhysReg, copy_operation> copy_operations;
1564                for (unsigned i = 0; i < instr->operands.size(); i++) {
1565                   assert(instr->definitions[i].bytes() == instr->operands[i].bytes());
1566                   copy_operations[instr->definitions[i].physReg()] = {instr->operands[i], instr->definitions[i], instr->operands[i].bytes()};
1567                }
1568                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1569                break;
1570             }
1571             case aco_opcode::p_exit_early_if:
1572             {
1573                /* don't bother with an early exit near the end of the program */
1574                if ((block->instructions.size() - 1 - j) <= 4 &&
1575                     block->instructions.back()->opcode == aco_opcode::s_endpgm) {
1576                   unsigned null_exp_dest = (ctx.program->stage & hw_fs) ? 9 /* NULL */ : V_008DFC_SQ_EXP_POS;
1577                   bool ignore_early_exit = true;
1578
1579                   for (unsigned k = j + 1; k < block->instructions.size(); ++k) {
1580                      const aco_ptr<Instruction> &instr = block->instructions[k];
1581                      if (instr->opcode == aco_opcode::s_endpgm ||
1582                          instr->opcode == aco_opcode::p_logical_end)
1583                         continue;
1584                      else if (instr->opcode == aco_opcode::exp &&
1585                               static_cast<Export_instruction *>(instr.get())->dest == null_exp_dest)
1586                         continue;
1587                      else if (instr->opcode == aco_opcode::p_parallelcopy &&
1588                          instr->definitions[0].isFixed() &&
1589                          instr->definitions[0].physReg() == exec)
1590                         continue;
1591
1592                      ignore_early_exit = false;
1593                   }
1594
1595                   if (ignore_early_exit)
1596                      break;
1597                }
1598
1599                if (!discard_block) {
1600                   discard_block = program->create_and_insert_block();
1601                   block = &program->blocks[i];
1602
1603                   bld.reset(discard_block);
1604                   bld.exp(aco_opcode::exp, Operand(v1), Operand(v1), Operand(v1), Operand(v1),
1605                           0, V_008DFC_SQ_EXP_NULL, false, true, true);
1606                   if (program->wb_smem_l1_on_end)
1607                      bld.smem(aco_opcode::s_dcache_wb);
1608                   bld.sopp(aco_opcode::s_endpgm);
1609
1610                   bld.reset(&ctx.instructions);
1611                }
1612
1613                //TODO: exec can be zero here with block_kind_discard
1614
1615                assert(instr->operands[0].physReg() == scc);
1616                bld.sopp(aco_opcode::s_cbranch_scc0, instr->operands[0], discard_block->index);
1617
1618                discard_block->linear_preds.push_back(block->index);
1619                block->linear_succs.push_back(discard_block->index);
1620                break;
1621             }
1622             case aco_opcode::p_spill:
1623             {
1624                assert(instr->operands[0].regClass() == v1.as_linear());
1625                for (unsigned i = 0; i < instr->operands[2].size(); i++)
1626                   bld.writelane(bld.def(v1, instr->operands[0].physReg()),
1627                                 Operand(PhysReg{instr->operands[2].physReg() + i}, s1),
1628                                 Operand(instr->operands[1].constantValue() + i),
1629                                 instr->operands[0]);
1630                break;
1631             }
1632             case aco_opcode::p_reload:
1633             {
1634                assert(instr->operands[0].regClass() == v1.as_linear());
1635                for (unsigned i = 0; i < instr->definitions[0].size(); i++)
1636                   bld.readlane(bld.def(s1, PhysReg{instr->definitions[0].physReg() + i}),
1637                                instr->operands[0],
1638                                Operand(instr->operands[1].constantValue() + i));
1639                break;
1640             }
1641             case aco_opcode::p_as_uniform:
1642             {
1643                if (instr->operands[0].isConstant() || instr->operands[0].regClass().type() == RegType::sgpr) {
1644                   std::map<PhysReg, copy_operation> copy_operations;
1645                   copy_operations[instr->definitions[0].physReg()] = {instr->operands[0], instr->definitions[0], instr->definitions[0].bytes()};
1646                   handle_operands(copy_operations, &ctx, program->chip_class, pi);
1647                } else {
1648                   assert(instr->operands[0].regClass().type() == RegType::vgpr);
1649                   assert(instr->definitions[0].regClass().type() == RegType::sgpr);
1650                   assert(instr->operands[0].size() == instr->definitions[0].size());
1651                   for (unsigned i = 0; i < instr->definitions[0].size(); i++) {
1652                      bld.vop1(aco_opcode::v_readfirstlane_b32,
1653                               bld.def(s1, PhysReg{instr->definitions[0].physReg() + i}),
1654                               Operand(PhysReg{instr->operands[0].physReg() + i}, v1));
1655                   }
1656                }
1657                break;
1658             }
1659             case aco_opcode::p_bpermute:
1660             {
1661                if (ctx.program->chip_class <= GFX7)
1662                   emit_gfx6_bpermute(program, instr, bld);
1663                else if (ctx.program->chip_class == GFX10 && ctx.program->wave_size == 64)
1664                   emit_gfx10_wave64_bpermute(program, instr, bld);
1665                else
1666                   unreachable("Current hardware supports ds_bpermute, don't emit p_bpermute.");
1667             }
1668             default:
1669                break;
1670             }
1671          } else if (instr->format == Format::PSEUDO_BRANCH) {
1672             Pseudo_branch_instruction* branch = static_cast<Pseudo_branch_instruction*>(instr.get());
1673             /* check if all blocks from current to target are empty */
1674             bool can_remove = block->index < branch->target[0];
1675             for (unsigned i = block->index + 1; can_remove && i < branch->target[0]; i++) {
1676                if (program->blocks[i].instructions.size())
1677                   can_remove = false;
1678             }
1679             if (can_remove)
1680                continue;
1681
1682             switch (instr->opcode) {
1683                case aco_opcode::p_branch:
1684                   assert(block->linear_succs[0] == branch->target[0]);
1685                   bld.sopp(aco_opcode::s_branch, branch->target[0]);
1686                   break;
1687                case aco_opcode::p_cbranch_nz:
1688                   assert(block->linear_succs[1] == branch->target[0]);
1689                   if (branch->operands[0].physReg() == exec)
1690                      bld.sopp(aco_opcode::s_cbranch_execnz, branch->target[0]);
1691                   else if (branch->operands[0].physReg() == vcc)
1692                      bld.sopp(aco_opcode::s_cbranch_vccnz, branch->target[0]);
1693                   else {
1694                      assert(branch->operands[0].physReg() == scc);
1695                      bld.sopp(aco_opcode::s_cbranch_scc1, branch->target[0]);
1696                   }
1697                   break;
1698                case aco_opcode::p_cbranch_z:
1699                   assert(block->linear_succs[1] == branch->target[0]);
1700                   if (branch->operands[0].physReg() == exec)
1701                      bld.sopp(aco_opcode::s_cbranch_execz, branch->target[0]);
1702                   else if (branch->operands[0].physReg() == vcc)
1703                      bld.sopp(aco_opcode::s_cbranch_vccz, branch->target[0]);
1704                   else {
1705                      assert(branch->operands[0].physReg() == scc);
1706                      bld.sopp(aco_opcode::s_cbranch_scc0, branch->target[0]);
1707                   }
1708                   break;
1709                default:
1710                   unreachable("Unknown Pseudo branch instruction!");
1711             }
1712
1713          } else if (instr->format == Format::PSEUDO_REDUCTION) {
1714             Pseudo_reduction_instruction* reduce = static_cast<Pseudo_reduction_instruction*>(instr.get());
1715             emit_reduction(&ctx, reduce->opcode, reduce->reduce_op, reduce->cluster_size,
1716                            reduce->operands[1].physReg(), // tmp
1717                            reduce->definitions[1].physReg(), // stmp
1718                            reduce->operands[2].physReg(), // vtmp
1719                            reduce->definitions[2].physReg(), // sitmp
1720                            reduce->operands[0], reduce->definitions[0]);
1721          } else {
1722             ctx.instructions.emplace_back(std::move(instr));
1723          }
1724
1725       }
1726       block->instructions.swap(ctx.instructions);
1727    }
1728 }
1729
1730 }