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       aco_ptr<SDWA_instruction> sdwa{create_instruction<SDWA_instruction>(aco_opcode::v_mov_b32, asSDWA(Format::VOP1), 1, 1)};
 572       sdwa->operands[0] = Operand(PhysReg{tmp}, v1);
 573       sdwa->definitions[0] = Definition(PhysReg{tmp}, v1);
 574       if (reduce_op == imin8 || reduce_op == imax8)
 575          sdwa->sel[0] = sdwa_sbyte;
 576       else
 577          sdwa->sel[0] = sdwa_ubyte;
 578       sdwa->dst_sel = sdwa_udword;
 579       bld.insert(std::move(sdwa));
 580    } else if (src.regClass() == v2b) {
 581       if (ctx->program->chip_class >= GFX10 &&
 582           (reduce_op == iadd16 || reduce_op == imax16 ||
 583            reduce_op == imin16 || reduce_op == umin16 || reduce_op == umax16)) {
 584          aco_ptr<SDWA_instruction> sdwa{create_instruction<SDWA_instruction>(aco_opcode::v_mov_b32, asSDWA(Format::VOP1), 1, 1)};
 585          sdwa->operands[0] = Operand(PhysReg{tmp}, v1);
 586          sdwa->definitions[0] = Definition(PhysReg{tmp}, v1);
 587          if (reduce_op == imin16 || reduce_op == imax16 || reduce_op == iadd16)
 588             sdwa->sel[0] = sdwa_sword;
 589          else
 590             sdwa->sel[0] = sdwa_uword;
 591          sdwa->dst_sel = sdwa_udword;
 592          bld.insert(std::move(sdwa));
 593       }
 594    }
 595
 596    bool reduction_needs_last_op = false;
 597    switch (op) {
 598    case aco_opcode::p_reduce:
 599       if (cluster_size == 1) break;
 600
 601       if (ctx->program->chip_class <= GFX7) {
 602          reduction_needs_last_op = true;
 603          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(1, 0, 3, 2));
 604          if (cluster_size == 2) break;
 605          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 606          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(2, 3, 0, 1));
 607          if (cluster_size == 4) break;
 608          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 609          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x04));
 610          if (cluster_size == 8) break;
 611          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 612          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x08));
 613          if (cluster_size == 16) break;
 614          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 615          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x10));
 616          if (cluster_size == 32) break;
 617          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 618          for (unsigned i = 0; i < src.size(); i++)
 619             bld.readlane(Definition(PhysReg{dst.physReg() + i}, s1), Operand(PhysReg{tmp + i}, v1), Operand(0u));
 620          // TODO: it would be more effective to do the last reduction step on SALU
 621          emit_op(ctx, tmp, dst.physReg(), tmp, vtmp, reduce_op, src.size());
 622          reduction_needs_last_op = false;
 623          break;
 624       }
 625
 626       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_quad_perm(1, 0, 3, 2), 0xf, 0xf, false);
 627       if (cluster_size == 2) break;
 628       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_quad_perm(2, 3, 0, 1), 0xf, 0xf, false);
 629       if (cluster_size == 4) break;
 630       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_half_mirror, 0xf, 0xf, false);
 631       if (cluster_size == 8) break;
 632       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_mirror, 0xf, 0xf, false);
 633       if (cluster_size == 16) break;
 634
 635       if (ctx->program->chip_class >= GFX10) {
 636          /* GFX10+ doesn't support row_bcast15 and row_bcast31 */
 637          for (unsigned i = 0; i < src.size(); i++)
 638             bld.vop3(aco_opcode::v_permlanex16_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1), Operand(0u), Operand(0u));
 639
 640          if (cluster_size == 32) {
 641             reduction_needs_last_op = true;
 642             break;
 643          }
 644
 645          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 646          for (unsigned i = 0; i < src.size(); i++)
 647             bld.readlane(Definition(PhysReg{dst.physReg() + i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(0u));
 648          // TODO: it would be more effective to do the last reduction step on SALU
 649          emit_op(ctx, tmp, dst.physReg(), tmp, vtmp, reduce_op, src.size());
 650          break;
 651       }
 652
 653       if (cluster_size == 32) {
 654          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1f, 0, 0x10));
 655          reduction_needs_last_op = true;
 656          break;
 657       }
 658       assert(cluster_size == 64);
 659       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_bcast15, 0xa, 0xf, false);
 660       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(), dpp_row_bcast31, 0xc, 0xf, false);
 661       break;
 662    case aco_opcode::p_exclusive_scan:
 663       if (ctx->program->chip_class >= GFX10) { /* gfx10 doesn't support wf_sr1, so emulate it */
 664          /* shift rows right */
 665          emit_dpp_mov(ctx, vtmp, tmp, src.size(), dpp_row_sr(1), 0xf, 0xf, true);
 666
 667          /* fill in the gaps in rows 1 and 3 */
 668          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x10000u));
 669          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(0x10000u));
 670          for (unsigned i = 0; i < src.size(); i++) {
 671             Instruction *perm = bld.vop3(aco_opcode::v_permlanex16_b32,
 672                                          Definition(PhysReg{vtmp+i}, v1),
 673                                          Operand(PhysReg{tmp+i}, v1),
 674                                          Operand(0xffffffffu), Operand(0xffffffffu)).instr;
 675             static_cast<VOP3A_instruction*>(perm)->opsel = 1; /* FI (Fetch Inactive) */
 676          }
 677          bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(UINT64_MAX));
 678
 679          if (ctx->program->wave_size == 64) {
 680             /* fill in the gap in row 2 */
 681             for (unsigned i = 0; i < src.size(); i++) {
 682                bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 683                bld.writelane(Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{sitmp+i}, s1), Operand(32u), Operand(PhysReg{vtmp+i}, v1));
 684             }
 685          }
 686          std::swap(tmp, vtmp);
 687       } else if (ctx->program->chip_class >= GFX8) {
 688          emit_dpp_mov(ctx, tmp, tmp, src.size(), dpp_wf_sr1, 0xf, 0xf, true);
 689       } else {
 690          // TODO: use LDS on CS with a single write and shifted read
 691          /* wavefront shift_right by 1 on SI/CI */
 692          emit_ds_swizzle(bld, vtmp, tmp, src.size(), (1 << 15) | dpp_quad_perm(0, 0, 1, 2));
 693          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x07)); /* mirror(8) */
 694          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x10101010u));
 695          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 696          for (unsigned i = 0; i < src.size(); i++)
 697             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 698
 699          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 700          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x08)); /* swap(8) */
 701          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0x01000100u));
 702          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 703          for (unsigned i = 0; i < src.size(); i++)
 704             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 705
 706          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 707          emit_ds_swizzle(bld, tmp, tmp, src.size(), ds_pattern_bitmode(0x1F, 0x00, 0x10)); /* swap(16) */
 708          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(1u), Operand(16u));
 709          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(1u), Operand(16u));
 710          for (unsigned i = 0; i < src.size(); i++)
 711             bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{tmp+i}, v1));
 712
 713          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 714          for (unsigned i = 0; i < src.size(); i++) {
 715             bld.writelane(Definition(PhysReg{vtmp+i}, v1), identity[i], Operand(0u), Operand(PhysReg{vtmp+i}, v1));
 716             bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(0u));
 717             bld.writelane(Definition(PhysReg{vtmp+i}, v1), Operand(PhysReg{sitmp+i}, s1), Operand(32u), Operand(PhysReg{vtmp+i}, v1));
 718             identity[i] = Operand(0u); /* prevent further uses of identity */
 719          }
 720          std::swap(tmp, vtmp);
 721       }
 722
 723       for (unsigned i = 0; i < src.size(); i++) {
 724          if (!identity[i].isConstant() || identity[i].constantValue()) { /* bound_ctrl should take care of this overwise */
 725             if (ctx->program->chip_class < GFX10)
 726                assert((identity[i].isConstant() && !identity[i].isLiteral()) || identity[i].physReg() == PhysReg{sitmp+i});
 727             bld.writelane(Definition(PhysReg{tmp+i}, v1), identity[i], Operand(0u), Operand(PhysReg{tmp+i}, v1));
 728          }
 729       }
 730       /* fall through */
 731    case aco_opcode::p_inclusive_scan:
 732       assert(cluster_size == ctx->program->wave_size);
 733       if (ctx->program->chip_class <= GFX7) {
 734          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1e, 0x00, 0x00));
 735          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xAAAAAAAAu));
 736          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 737          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 738
 739          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 740          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x1c, 0x01, 0x00));
 741          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xCCCCCCCCu));
 742          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 743          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 744
 745          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 746          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x18, 0x03, 0x00));
 747          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xF0F0F0F0u));
 748          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 749          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 750
 751          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 752          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x10, 0x07, 0x00));
 753          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_lo, s1), Operand(0xFF00FF00u));
 754          bld.sop1(aco_opcode::s_mov_b32, Definition(exec_hi, s1), Operand(exec_lo, s1));
 755          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 756
 757          bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(UINT64_MAX));
 758          emit_ds_swizzle(bld, vtmp, tmp, src.size(), ds_pattern_bitmode(0x00, 0x0f, 0x00));
 759          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(16u), Operand(16u));
 760          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(16u), Operand(16u));
 761          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 762
 763          for (unsigned i = 0; i < src.size(); i++)
 764             bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 765          bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 766          emit_op(ctx, tmp, sitmp, tmp, vtmp, reduce_op, src.size());
 767          break;
 768       }
 769
 770       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 771                   dpp_row_sr(1), 0xf, 0xf, false, identity);
 772       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 773                   dpp_row_sr(2), 0xf, 0xf, false, identity);
 774       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 775                   dpp_row_sr(4), 0xf, 0xf, false, identity);
 776       emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 777                   dpp_row_sr(8), 0xf, 0xf, false, identity);
 778       if (ctx->program->chip_class >= GFX10) {
 779          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_lo, s1), Operand(16u), Operand(16u));
 780          bld.sop2(aco_opcode::s_bfm_b32, Definition(exec_hi, s1), Operand(16u), Operand(16u));
 781          for (unsigned i = 0; i < src.size(); i++) {
 782             Instruction *perm = bld.vop3(aco_opcode::v_permlanex16_b32,
 783                                          Definition(PhysReg{vtmp+i}, v1),
 784                                          Operand(PhysReg{tmp+i}, v1),
 785                                          Operand(0xffffffffu), Operand(0xffffffffu)).instr;
 786             static_cast<VOP3A_instruction*>(perm)->opsel = 1; /* FI (Fetch Inactive) */
 787          }
 788          emit_op(ctx, tmp, tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 789
 790          if (ctx->program->wave_size == 64) {
 791             bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 792             for (unsigned i = 0; i < src.size(); i++)
 793                bld.readlane(Definition(PhysReg{sitmp+i}, s1), Operand(PhysReg{tmp+i}, v1), Operand(31u));
 794             emit_op(ctx, tmp, sitmp, tmp, vtmp, reduce_op, src.size());
 795          }
 796       } else {
 797          emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 798                      dpp_row_bcast15, 0xa, 0xf, false, identity);
 799          emit_dpp_op(ctx, tmp, tmp, tmp, vtmp, reduce_op, src.size(),
 800                      dpp_row_bcast31, 0xc, 0xf, false, identity);
 801       }
 802       break;
 803    default:
 804       unreachable("Invalid reduction mode");
 805    }
 806
 807
 808    if (op == aco_opcode::p_reduce) {
 809       if (reduction_needs_last_op && dst.regClass().type() == RegType::vgpr) {
 810          bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(stmp, bld.lm));
 811          emit_op(ctx, dst.physReg(), tmp, vtmp, PhysReg{0}, reduce_op, src.size());
 812          return;
 813       }
 814
 815       if (reduction_needs_last_op)
 816          emit_op(ctx, tmp, vtmp, tmp, PhysReg{0}, reduce_op, src.size());
 817    }
 818
 819    /* restore exec */
 820    bld.sop1(Builder::s_mov, Definition(exec, bld.lm), Operand(stmp, bld.lm));
 821
 822    if (dst.regClass().type() == RegType::sgpr) {
 823       for (unsigned k = 0; k < src.size(); k++) {
 824          bld.readlane(Definition(PhysReg{dst.physReg() + k}, s1),
 825                       Operand(PhysReg{tmp + k}, v1), Operand(ctx->program->wave_size - 1));
 826       }
 827    } else if (dst.physReg() != tmp) {
 828       for (unsigned k = 0; k < src.size(); k++) {
 829          bld.vop1(aco_opcode::v_mov_b32, Definition(PhysReg{dst.physReg() + k}, v1),
 830                   Operand(PhysReg{tmp + k}, v1));
 831       }
 832    }
 833 }
 834
 835 void emit_gfx10_wave64_bpermute(Program *program, aco_ptr<Instruction> &instr, Builder &bld)
 836 {
 837    /* Emulates proper bpermute on GFX10 in wave64 mode.
 838     *
 839     * This is necessary because on GFX10 the bpermute instruction only works
 840     * on half waves (you can think of it as having a cluster size of 32), so we
 841     * manually swap the data between the two halves using two shared VGPRs.
 842     */
 843
 844    assert(program->chip_class >= GFX10);
 845    assert(program->info->wave_size == 64);
 846
 847    unsigned shared_vgpr_reg_0 = align(program->config->num_vgprs, 4) + 256;
 848    Definition dst = instr->definitions[0];
 849    Definition tmp_exec = instr->definitions[1];
 850    Definition clobber_scc = instr->definitions[2];
 851    Operand index_x4 = instr->operands[0];
 852    Operand input_data = instr->operands[1];
 853    Operand same_half = instr->operands[2];
 854
 855    assert(dst.regClass() == v1);
 856    assert(tmp_exec.regClass() == bld.lm);
 857    assert(clobber_scc.isFixed() && clobber_scc.physReg() == scc);
 858    assert(same_half.regClass() == bld.lm);
 859    assert(index_x4.regClass() == v1);
 860    assert(input_data.regClass().type() == RegType::vgpr);
 861    assert(input_data.bytes() <= 4);
 862    assert(dst.physReg() != index_x4.physReg());
 863    assert(dst.physReg() != input_data.physReg());
 864    assert(tmp_exec.physReg() != same_half.physReg());
 865
 866    PhysReg shared_vgpr_lo(shared_vgpr_reg_0);
 867    PhysReg shared_vgpr_hi(shared_vgpr_reg_0 + 1);
 868
 869    /* Permute the input within the same half-wave */
 870    bld.ds(aco_opcode::ds_bpermute_b32, dst, index_x4, input_data);
 871
 872    /* HI: Copy data from high lanes 32-63 to shared vgpr */
 873    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);
 874    /* Save EXEC */
 875    bld.sop1(aco_opcode::s_mov_b64, tmp_exec, Operand(exec, s2));
 876    /* Set EXEC to enable LO lanes only */
 877    bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(0u));
 878    /* LO: Copy data from low lanes 0-31 to shared vgpr */
 879    bld.vop1(aco_opcode::v_mov_b32, Definition(shared_vgpr_lo, v1), input_data);
 880    /* LO: bpermute shared vgpr (high lanes' data) */
 881    bld.ds(aco_opcode::ds_bpermute_b32, Definition(shared_vgpr_hi, v1), index_x4, Operand(shared_vgpr_hi, v1));
 882    /* Set EXEC to enable HI lanes only */
 883    bld.sop2(aco_opcode::s_bfm_b64, Definition(exec, s2), Operand(32u), Operand(32u));
 884    /* HI: bpermute shared vgpr (low lanes' data) */
 885    bld.ds(aco_opcode::ds_bpermute_b32, Definition(shared_vgpr_lo, v1), index_x4, Operand(shared_vgpr_lo, v1));
 886
 887    /* Only enable lanes which use the other half's data */
 888    bld.sop2(aco_opcode::s_andn2_b64, Definition(exec, s2), clobber_scc, Operand(tmp_exec.physReg(), s2), same_half);
 889    /* LO: Copy shared vgpr (high lanes' bpermuted data) to output vgpr */
 890    bld.vop1_dpp(aco_opcode::v_mov_b32, dst, Operand(shared_vgpr_hi, v1), dpp_quad_perm(0, 1, 2, 3), 0x3, 0xf, false);
 891    /* HI: Copy shared vgpr (low lanes' bpermuted data) to output vgpr */
 892    bld.vop1_dpp(aco_opcode::v_mov_b32, dst, Operand(shared_vgpr_lo, v1), dpp_quad_perm(0, 1, 2, 3), 0xc, 0xf, false);
 893
 894    /* Restore saved EXEC */
 895    bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(tmp_exec.physReg(), s2));
 896
 897    /* 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 */
 898    if (input_data.physReg().byte()) {
 899       unsigned right_shift = input_data.physReg().byte() * 8;
 900       bld.vop2(aco_opcode::v_lshrrev_b32, dst, Operand(right_shift), Operand(dst.physReg(), v1));
 901    }
 902 }
 903
 904 void emit_gfx6_bpermute(Program *program, aco_ptr<Instruction> &instr, Builder &bld)
 905 {
 906    /* Emulates bpermute using readlane instructions */
 907
 908    Operand index = instr->operands[0];
 909    Operand input = instr->operands[1];
 910    Definition dst = instr->definitions[0];
 911    Definition temp_exec = instr->definitions[1];
 912    Definition clobber_vcc = instr->definitions[2];
 913
 914    assert(dst.regClass() == v1);
 915    assert(temp_exec.regClass() == bld.lm);
 916    assert(clobber_vcc.regClass() == bld.lm);
 917    assert(clobber_vcc.physReg() == vcc);
 918    assert(index.regClass() == v1);
 919    assert(index.physReg() != dst.physReg());
 920    assert(input.regClass().type() == RegType::vgpr);
 921    assert(input.bytes() <= 4);
 922    assert(input.physReg() != dst.physReg());
 923
 924    /* Save original EXEC */
 925    bld.sop1(aco_opcode::s_mov_b64, temp_exec, Operand(exec, s2));
 926
 927    /* An "unrolled loop" that is executed per each lane.
 928     * This takes only a few instructions per lane, as opposed to a "real" loop
 929     * with branching, where the branch instruction alone would take 16+ cycles.
 930     */
 931    for (unsigned n = 0; n < program->wave_size; ++n) {
 932       /* Activate the lane which has N for its source index */
 933       bld.vopc(aco_opcode::v_cmpx_eq_u32, Definition(exec, bld.lm), clobber_vcc, Operand(n), index);
 934       /* Read the data from lane N */
 935       bld.readlane(Definition(vcc, s1), input, Operand(n));
 936       /* On the active lane, move the data we read from lane N to the destination VGPR */
 937       bld.vop1(aco_opcode::v_mov_b32, dst, Operand(vcc, s1));
 938       /* Restore original EXEC */
 939       bld.sop1(aco_opcode::s_mov_b64, Definition(exec, s2), Operand(temp_exec.physReg(), s2));
 940    }
 941 }
 942
 943 struct copy_operation {
 944    Operand op;
 945    Definition def;
 946    unsigned bytes;
 947    union {
 948       uint8_t uses[8];
 949       uint64_t is_used = 0;
 950    };
 951 };
 952
 953 void split_copy(unsigned offset, Definition *def, Operand *op, const copy_operation& src, bool ignore_uses, unsigned max_size)
 954 {
 955    PhysReg def_reg = src.def.physReg();
 956    PhysReg op_reg = src.op.physReg();
 957    def_reg.reg_b += offset;
 958    op_reg.reg_b += offset;
 959
 960    max_size = MIN2(max_size, src.def.regClass().type() == RegType::vgpr ? 4 : 8);
 961
 962    /* make sure the size is a power of two and reg % bytes == 0 */
 963    unsigned bytes = 1;
 964    for (; bytes <= max_size; bytes *= 2) {
 965       unsigned next = bytes * 2u;
 966       bool can_increase = def_reg.reg_b % next == 0 &&
 967                           offset + next <= src.bytes && next <= max_size;
 968       if (!src.op.isConstant() && can_increase)
 969          can_increase = op_reg.reg_b % next == 0;
 970       for (unsigned i = 0; !ignore_uses && can_increase && (i < bytes); i++)
 971          can_increase = (src.uses[offset + bytes + i] == 0) == (src.uses[offset] == 0);
 972       if (!can_increase)
 973          break;
 974    }
 975
 976    RegClass def_cls = bytes % 4 == 0 ? RegClass(src.def.regClass().type(), bytes / 4u) :
 977                       RegClass(src.def.regClass().type(), bytes).as_subdword();
 978    *def = Definition(src.def.tempId(), def_reg, def_cls);
 979    if (src.op.isConstant()) {
 980       assert(offset == 0 || (offset == 4 && src.op.bytes() == 8));
 981       if (src.op.bytes() == 8 && bytes == 4)
 982          *op = Operand(uint32_t(src.op.constantValue64() >> (offset * 8u)));
 983       else
 984          *op  = src.op;
 985    } else {
 986       RegClass op_cls = bytes % 4 == 0 ? RegClass(src.op.regClass().type(), bytes / 4u) :
 987                         RegClass(src.op.regClass().type(), bytes).as_subdword();
 988       *op = Operand(op_reg, op_cls);
 989       op->setTemp(Temp(src.op.tempId(), op_cls));
 990    }
 991 }
 992
 993 uint32_t get_intersection_mask(int a_start, int a_size,
 994                                int b_start, int b_size)
 995 {
 996    int intersection_start = MAX2(b_start - a_start, 0);
 997    int intersection_end = MAX2(b_start + b_size - a_start, 0);
 998    if (intersection_start >= a_size || intersection_end == 0)
 999       return 0;
1000
1001    uint32_t mask = u_bit_consecutive(0, a_size);
1002    return u_bit_consecutive(intersection_start, intersection_end - intersection_start) & mask;
1003 }
1004
1005 bool do_copy(lower_context* ctx, Builder& bld, const copy_operation& copy, bool *preserve_scc)
1006 {
1007    bool did_copy = false;
1008    for (unsigned offset = 0; offset < copy.bytes;) {
1009       if (copy.uses[offset]) {
1010          offset++;
1011          continue;
1012       }
1013
1014       Definition def;
1015       Operand op;
1016       split_copy(offset, &def, &op, copy, false, 8);
1017
1018       if (def.physReg() == scc) {
1019          bld.sopc(aco_opcode::s_cmp_lg_i32, def, op, Operand(0u));
1020          *preserve_scc = true;
1021       } else if (def.bytes() == 8 && def.getTemp().type() == RegType::sgpr) {
1022          bld.sop1(aco_opcode::s_mov_b64, def, Operand(op.physReg(), s2));
1023       } else {
1024          bld.copy(def, op);
1025       }
1026
1027       ctx->program->statistics[statistic_copies]++;
1028
1029       did_copy = true;
1030       offset += def.bytes();
1031    }
1032    return did_copy;
1033 }
1034
1035 void do_swap(lower_context *ctx, Builder& bld, const copy_operation& copy, bool preserve_scc, Pseudo_instruction *pi)
1036 {
1037    unsigned offset = 0;
1038
1039    if (copy.bytes == 3 && (copy.def.physReg().reg_b % 4 <= 1) &&
1040        (copy.def.physReg().reg_b % 4) == (copy.op.physReg().reg_b % 4)) {
1041       /* instead of doing a 2-byte and 1-byte swap, do a 4-byte swap and then fixup with a 1-byte swap */
1042       PhysReg op = copy.op.physReg();
1043       PhysReg def = copy.def.physReg();
1044       op.reg_b &= ~0x3;
1045       def.reg_b &= ~0x3;
1046
1047       copy_operation tmp;
1048       tmp.op = Operand(op, v1);
1049       tmp.def = Definition(def, v1);
1050       tmp.bytes = 4;
1051       memset(tmp.uses, 1, 4);
1052       do_swap(ctx, bld, tmp, preserve_scc, pi);
1053
1054       op.reg_b += copy.def.physReg().reg_b % 4 == 0 ? 3 : 0;
1055       def.reg_b += copy.def.physReg().reg_b % 4 == 0 ? 3 : 0;
1056       tmp.op = Operand(op, v1b);
1057       tmp.def = Definition(def, v1b);
1058       tmp.bytes = 1;
1059       tmp.uses[0] = 1;
1060       do_swap(ctx, bld, tmp, preserve_scc, pi);
1061
1062       offset = copy.bytes;
1063    }
1064
1065    for (; offset < copy.bytes;) {
1066       Definition def;
1067       Operand op;
1068       split_copy(offset, &def, &op, copy, true, 8);
1069
1070       assert(op.regClass() == def.regClass());
1071       Operand def_as_op = Operand(def.physReg(), def.regClass());
1072       Definition op_as_def = Definition(op.physReg(), op.regClass());
1073       if (ctx->program->chip_class >= GFX9 && def.regClass() == v1) {
1074          bld.vop1(aco_opcode::v_swap_b32, def, op_as_def, op, def_as_op);
1075          ctx->program->statistics[statistic_copies]++;
1076       } else if (def.regClass() == v1) {
1077          bld.vop2(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1078          bld.vop2(aco_opcode::v_xor_b32, def, op, def_as_op);
1079          bld.vop2(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1080          ctx->program->statistics[statistic_copies] += 3;
1081       } else if (op.physReg() == scc || def.physReg() == scc) {
1082          /* we need to swap scc and another sgpr */
1083          assert(!preserve_scc);
1084
1085          PhysReg other = op.physReg() == scc ? def.physReg() : op.physReg();
1086
1087          bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), Operand(scc, s1));
1088          bld.sopc(aco_opcode::s_cmp_lg_i32, Definition(scc, s1), Operand(other, s1), Operand(0u));
1089          bld.sop1(aco_opcode::s_mov_b32, Definition(other, s1), Operand(pi->scratch_sgpr, s1));
1090          ctx->program->statistics[statistic_copies] += 3;
1091       } else if (def.regClass() == s1) {
1092          if (preserve_scc) {
1093             bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), op);
1094             bld.sop1(aco_opcode::s_mov_b32, op_as_def, def_as_op);
1095             bld.sop1(aco_opcode::s_mov_b32, def, Operand(pi->scratch_sgpr, s1));
1096          } else {
1097             bld.sop2(aco_opcode::s_xor_b32, op_as_def, Definition(scc, s1), op, def_as_op);
1098             bld.sop2(aco_opcode::s_xor_b32, def, Definition(scc, s1), op, def_as_op);
1099             bld.sop2(aco_opcode::s_xor_b32, op_as_def, Definition(scc, s1), op, def_as_op);
1100          }
1101          ctx->program->statistics[statistic_copies] += 3;
1102       } else if (def.regClass() == s2) {
1103          if (preserve_scc)
1104             bld.sop1(aco_opcode::s_mov_b32, Definition(pi->scratch_sgpr, s1), Operand(scc, s1));
1105          bld.sop2(aco_opcode::s_xor_b64, op_as_def, Definition(scc, s1), op, def_as_op);
1106          bld.sop2(aco_opcode::s_xor_b64, def, Definition(scc, s1), op, def_as_op);
1107          bld.sop2(aco_opcode::s_xor_b64, op_as_def, Definition(scc, s1), op, def_as_op);
1108          if (preserve_scc)
1109             bld.sopc(aco_opcode::s_cmp_lg_i32, Definition(scc, s1), Operand(pi->scratch_sgpr, s1), Operand(0u));
1110          ctx->program->statistics[statistic_copies] += 3;
1111       } else if (ctx->program->chip_class >= GFX9 && def.bytes() == 2 && def.physReg().reg() == op.physReg().reg()) {
1112          aco_ptr<VOP3P_instruction> vop3p{create_instruction<VOP3P_instruction>(aco_opcode::v_pk_add_u16, Format::VOP3P, 2, 1)};
1113          vop3p->operands[0] = Operand(PhysReg{op.physReg().reg()}, v1);
1114          vop3p->operands[1] = Operand(0u);
1115          vop3p->definitions[0] = Definition(PhysReg{op.physReg().reg()}, v1);
1116          vop3p->opsel_lo = 0x1;
1117          vop3p->opsel_hi = 0x2;
1118          bld.insert(std::move(vop3p));
1119       } else {
1120          assert(def.regClass().is_subdword());
1121          bld.vop2_sdwa(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1122          bld.vop2_sdwa(aco_opcode::v_xor_b32, def, op, def_as_op);
1123          bld.vop2_sdwa(aco_opcode::v_xor_b32, op_as_def, op, def_as_op);
1124          ctx->program->statistics[statistic_copies] += 3;
1125       }
1126
1127       offset += def.bytes();
1128    }
1129
1130    /* fixup in case we swapped bytes we shouldn't have */
1131    copy_operation tmp_copy = copy;
1132    tmp_copy.op.setFixed(copy.def.physReg());
1133    tmp_copy.def.setFixed(copy.op.physReg());
1134    do_copy(ctx, bld, tmp_copy, &preserve_scc);
1135 }
1136
1137 void handle_operands(std::map<PhysReg, copy_operation>& copy_map, lower_context* ctx, chip_class chip_class, Pseudo_instruction *pi)
1138 {
1139    Builder bld(ctx->program, &ctx->instructions);
1140    aco_ptr<Instruction> mov;
1141    std::map<PhysReg, copy_operation>::iterator it = copy_map.begin();
1142    std::map<PhysReg, copy_operation>::iterator target;
1143    bool writes_scc = false;
1144
1145    /* count the number of uses for each dst reg */
1146    while (it != copy_map.end()) {
1147
1148       if (it->second.def.physReg() == scc)
1149          writes_scc = true;
1150
1151       assert(!pi->tmp_in_scc || !(it->second.def.physReg() == pi->scratch_sgpr));
1152
1153       /* if src and dst reg are the same, remove operation */
1154       if (it->first == it->second.op.physReg()) {
1155          it = copy_map.erase(it);
1156          continue;
1157       }
1158
1159       /* split large copies */
1160       if (it->second.bytes > 8) {
1161          assert(!it->second.op.isConstant());
1162          assert(!it->second.def.regClass().is_subdword());
1163          RegClass rc = RegClass(it->second.def.regClass().type(), it->second.def.size() - 2);
1164          Definition hi_def = Definition(PhysReg{it->first + 2}, rc);
1165          rc = RegClass(it->second.op.regClass().type(), it->second.op.size() - 2);
1166          Operand hi_op = Operand(PhysReg{it->second.op.physReg() + 2}, rc);
1167          copy_operation copy = {hi_op, hi_def, it->second.bytes - 8};
1168          copy_map[hi_def.physReg()] = copy;
1169          assert(it->second.op.physReg().byte() == 0 && it->second.def.physReg().byte() == 0);
1170          it->second.op = Operand(it->second.op.physReg(), it->second.op.regClass().type() == RegType::sgpr ? s2 : v2);
1171          it->second.def = Definition(it->second.def.physReg(), it->second.def.regClass().type() == RegType::sgpr ? s2 : v2);
1172          it->second.bytes = 8;
1173       }
1174
1175       /* check if the definition reg is used by another copy operation */
1176       for (std::pair<const PhysReg, copy_operation>& copy : copy_map) {
1177          if (copy.second.op.isConstant())
1178             continue;
1179          for (uint16_t i = 0; i < it->second.bytes; i++) {
1180             /* distance might underflow */
1181             unsigned distance = it->first.reg_b + i - copy.second.op.physReg().reg_b;
1182             if (distance < copy.second.bytes)
1183                it->second.uses[i] += 1;
1184          }
1185       }
1186
1187       ++it;
1188    }
1189
1190    /* first, handle paths in the location transfer graph */
1191    bool preserve_scc = pi->tmp_in_scc && !writes_scc;
1192    it = copy_map.begin();
1193    while (it != copy_map.end()) {
1194
1195       /* try to coalesce 32-bit sgpr copies to 64-bit copies */
1196       if (it->second.is_used == 0 &&
1197           it->second.def.getTemp().type() == RegType::sgpr && it->second.bytes == 4 &&
1198           !it->second.op.isConstant() && it->first % 2 == it->second.op.physReg() % 2) {
1199
1200          PhysReg other_def_reg = PhysReg{it->first % 2 ? it->first - 1 : it->first + 1};
1201          PhysReg other_op_reg = PhysReg{it->first % 2 ? it->second.op.physReg() - 1 : it->second.op.physReg() + 1};
1202          std::map<PhysReg, copy_operation>::iterator other = copy_map.find(other_def_reg);
1203
1204          if (other != copy_map.end() && !other->second.is_used && other->second.bytes == 4 &&
1205              other->second.op.physReg() == other_op_reg && !other->second.op.isConstant()) {
1206             std::map<PhysReg, copy_operation>::iterator to_erase = it->first % 2 ? it : other;
1207             it = it->first % 2 ? other : it;
1208             copy_map.erase(to_erase);
1209             it->second.bytes = 8;
1210          }
1211       }
1212       // TODO: try to coalesce subdword copies
1213
1214       /* find portions where the target reg is not used as operand for any other copy */
1215       if (it->second.is_used) {
1216          if (it->second.op.isConstant()) {
1217             /* we have to skip constants until is_used=0 */
1218             ++it;
1219             continue;
1220          }
1221
1222          unsigned has_zero_use_bytes = 0;
1223          for (unsigned i = 0; i < it->second.bytes; i++)
1224             has_zero_use_bytes |= (it->second.uses[i] == 0) << i;
1225
1226          if (has_zero_use_bytes) {
1227             /* Skipping partial copying and doing a v_swap_b32 and then fixup
1228              * copies is usually beneficial for sub-dword copies, but if doing
1229              * a partial copy allows further copies, it should be done instead. */
1230             bool partial_copy = (has_zero_use_bytes == 0xf) || (has_zero_use_bytes == 0xf0);
1231             for (std::pair<const PhysReg, copy_operation>& copy : copy_map) {
1232                if (partial_copy)
1233                   break;
1234                for (uint16_t i = 0; i < copy.second.bytes; i++) {
1235                   /* distance might underflow */
1236                   unsigned distance = copy.first.reg_b + i - it->second.op.physReg().reg_b;
1237                   if (distance < it->second.bytes && copy.second.uses[i] == 1 &&
1238                       !it->second.uses[distance])
1239                      partial_copy = true;
1240                }
1241             }
1242
1243             if (!partial_copy) {
1244                ++it;
1245                continue;
1246             }
1247          } else {
1248             /* full target reg is used: register swapping needed */
1249             ++it;
1250             continue;
1251          }
1252       }
1253
1254       bool did_copy = do_copy(ctx, bld, it->second, &preserve_scc);
1255
1256       std::pair<PhysReg, copy_operation> copy = *it;
1257
1258       if (it->second.is_used == 0) {
1259          /* the target reg is not used as operand for any other copy, so we
1260           * copied to all of it */
1261          copy_map.erase(it);
1262          it = copy_map.begin();
1263       } else {
1264          /* we only performed some portions of this copy, so split it to only
1265           * leave the portions that still need to be done */
1266          copy_operation original = it->second; /* the map insertion below can overwrite this */
1267          copy_map.erase(it);
1268          for (unsigned offset = 0; offset < original.bytes;) {
1269             if (original.uses[offset] == 0) {
1270                offset++;
1271                continue;
1272             }
1273             Definition def;
1274             Operand op;
1275             split_copy(offset, &def, &op, original, false, 8);
1276
1277             copy_operation copy = {op, def, def.bytes()};
1278             for (unsigned i = 0; i < copy.bytes; i++)
1279                copy.uses[i] = original.uses[i + offset];
1280             copy_map[def.physReg()] = copy;
1281
1282             offset += def.bytes();
1283          }
1284
1285          it = copy_map.begin();
1286       }
1287
1288       /* Reduce the number of uses of the operand reg by one. Do this after
1289        * splitting the copy or removing it in case the copy writes to it's own
1290        * operand (for example, v[7:8] = v[8:9]) */
1291       if (did_copy && !copy.second.op.isConstant()) {
1292          for (std::pair<const PhysReg, copy_operation>& other : copy_map) {
1293              for (uint16_t i = 0; i < other.second.bytes; i++) {
1294                /* distance might underflow */
1295                unsigned distance = other.first.reg_b + i - copy.second.op.physReg().reg_b;
1296                if (distance < copy.second.bytes && !copy.second.uses[distance])
1297                   other.second.uses[i] -= 1;
1298             }
1299          }
1300       }
1301    }
1302
1303    if (copy_map.empty())
1304       return;
1305
1306    /* all target regs are needed as operand somewhere which means, all entries are part of a cycle */
1307    unsigned largest = 0;
1308    for (const std::pair<const PhysReg, copy_operation>& op : copy_map)
1309       largest = MAX2(largest, op.second.bytes);
1310
1311    while (!copy_map.empty()) {
1312
1313       /* Perform larger swaps first, because larger swaps swaps can make other
1314        * swaps unnecessary. */
1315       auto it = copy_map.begin();
1316       for (auto it2 = copy_map.begin(); it2 != copy_map.end(); ++it2) {
1317          if (it2->second.bytes > it->second.bytes) {
1318             it = it2;
1319             if (it->second.bytes == largest)
1320                break;
1321          }
1322       }
1323
1324       /* should already be done */
1325       assert(!it->second.op.isConstant());
1326
1327       assert(it->second.op.isFixed());
1328       assert(it->second.def.regClass() == it->second.op.regClass());
1329
1330       if (it->first == it->second.op.physReg()) {
1331          copy_map.erase(it);
1332          continue;
1333       }
1334
1335       if (preserve_scc && it->second.def.getTemp().type() == RegType::sgpr)
1336          assert(!(it->second.def.physReg() == pi->scratch_sgpr));
1337
1338       /* to resolve the cycle, we have to swap the src reg with the dst reg */
1339       copy_operation swap = it->second;
1340
1341       /* if this is self-intersecting, we have to split it because
1342        * self-intersecting swaps don't make sense */
1343       PhysReg lower = swap.def.physReg();
1344       PhysReg higher = swap.op.physReg();
1345       if (lower.reg_b > higher.reg_b)
1346          std::swap(lower, higher);
1347       if (higher.reg_b - lower.reg_b < (int)swap.bytes) {
1348          unsigned offset = higher.reg_b - lower.reg_b;
1349          RegType type = swap.def.regClass().type();
1350
1351          copy_operation middle;
1352          lower.reg_b += offset;
1353          higher.reg_b += offset;
1354          middle.bytes = swap.bytes - offset * 2;
1355          memcpy(middle.uses, swap.uses + offset, middle.bytes);
1356          middle.op = Operand(lower, RegClass::get(type, middle.bytes));
1357          middle.def = Definition(higher, RegClass::get(type, middle.bytes));
1358          copy_map[higher] = middle;
1359
1360          copy_operation end;
1361          lower.reg_b += middle.bytes;
1362          higher.reg_b += middle.bytes;
1363          end.bytes = swap.bytes - (offset + middle.bytes);
1364          memcpy(end.uses, swap.uses + offset + middle.bytes, end.bytes);
1365          end.op = Operand(lower, RegClass::get(type, end.bytes));
1366          end.def = Definition(higher, RegClass::get(type, end.bytes));
1367          copy_map[higher] = end;
1368
1369          memset(swap.uses + offset, 0, swap.bytes - offset);
1370          swap.bytes = offset;
1371       }
1372
1373       do_swap(ctx, bld, swap, preserve_scc, pi);
1374
1375       /* remove from map */
1376       copy_map.erase(it);
1377
1378       /* change the operand reg of the target's uses and split uses if needed */
1379       target = copy_map.begin();
1380       uint32_t bytes_left = u_bit_consecutive(0, swap.bytes);
1381       for (; target != copy_map.end(); ++target) {
1382          if (target->second.op.physReg() == swap.def.physReg() && swap.bytes == target->second.bytes) {
1383             target->second.op.setFixed(swap.op.physReg());
1384             break;
1385          }
1386
1387          uint32_t imask = get_intersection_mask(swap.def.physReg().reg_b, swap.bytes,
1388                                                 target->second.op.physReg().reg_b, target->second.bytes);
1389
1390          if (!imask)
1391             continue;
1392
1393          assert(target->second.bytes < swap.bytes);
1394
1395          int offset = (int)target->second.op.physReg().reg_b - (int)swap.def.physReg().reg_b;
1396
1397          /* split and update the middle (the portion that reads the swap's
1398           * definition) to read the swap's operand instead */
1399          int target_op_end = target->second.op.physReg().reg_b + target->second.bytes;
1400          int swap_def_end = swap.def.physReg().reg_b + swap.bytes;
1401          int before_bytes = MAX2(-offset, 0);
1402          int after_bytes = MAX2(target_op_end - swap_def_end, 0);
1403          int middle_bytes = target->second.bytes - before_bytes - after_bytes;
1404
1405          if (after_bytes) {
1406             unsigned after_offset = before_bytes + middle_bytes;
1407             assert(after_offset > 0);
1408             copy_operation copy;
1409             copy.bytes = after_bytes;
1410             memcpy(copy.uses, target->second.uses + after_offset, copy.bytes);
1411             RegClass rc = RegClass::get(target->second.op.regClass().type(), after_bytes);
1412             copy.op = Operand(target->second.op.physReg().advance(after_offset), rc);
1413             copy.def = Definition(target->second.def.physReg().advance(after_offset), rc);
1414             copy_map[copy.def.physReg()] = copy;
1415          }
1416
1417          if (middle_bytes) {
1418             copy_operation copy;
1419             copy.bytes = middle_bytes;
1420             memcpy(copy.uses, target->second.uses + before_bytes, copy.bytes);
1421             RegClass rc = RegClass::get(target->second.op.regClass().type(), middle_bytes);
1422             copy.op = Operand(swap.op.physReg().advance(MAX2(offset, 0)), rc);
1423             copy.def = Definition(target->second.def.physReg().advance(before_bytes), rc);
1424             copy_map[copy.def.physReg()] = copy;
1425          }
1426
1427          if (before_bytes) {
1428             copy_operation copy;
1429             target->second.bytes = before_bytes;
1430             RegClass rc = RegClass::get(target->second.op.regClass().type(), before_bytes);
1431             target->second.op = Operand(target->second.op.physReg(), rc);
1432             target->second.def = Definition(target->second.def.physReg(), rc);
1433             memset(target->second.uses + target->second.bytes, 0, 8 - target->second.bytes);
1434          }
1435
1436          /* break early since we know each byte of the swap's definition is used
1437           * at most once */
1438          bytes_left &= ~imask;
1439          if (!bytes_left)
1440             break;
1441       }
1442    }
1443 }
1444
1445 void lower_to_hw_instr(Program* program)
1446 {
1447    Block *discard_block = NULL;
1448
1449    for (size_t i = 0; i < program->blocks.size(); i++)
1450    {
1451       Block *block = &program->blocks[i];
1452       lower_context ctx;
1453       ctx.program = program;
1454       Builder bld(program, &ctx.instructions);
1455
1456       bool set_mode = i == 0 && block->fp_mode.val != program->config->float_mode;
1457       for (unsigned pred : block->linear_preds) {
1458          if (program->blocks[pred].fp_mode.val != block->fp_mode.val) {
1459             set_mode = true;
1460             break;
1461          }
1462       }
1463       if (set_mode) {
1464          /* only allow changing modes at top-level blocks so this doesn't break
1465           * the "jump over empty blocks" optimization */
1466          assert(block->kind & block_kind_top_level);
1467          uint32_t mode = block->fp_mode.val;
1468          /* "((size - 1) << 11) | register" (MODE is encoded as register 1) */
1469          bld.sopk(aco_opcode::s_setreg_imm32_b32, Operand(mode), (7 << 11) | 1);
1470       }
1471
1472       for (size_t j = 0; j < block->instructions.size(); j++) {
1473          aco_ptr<Instruction>& instr = block->instructions[j];
1474          aco_ptr<Instruction> mov;
1475          if (instr->format == Format::PSEUDO) {
1476             Pseudo_instruction *pi = (Pseudo_instruction*)instr.get();
1477
1478             switch (instr->opcode)
1479             {
1480             case aco_opcode::p_extract_vector:
1481             {
1482                PhysReg reg = instr->operands[0].physReg();
1483                Definition& def = instr->definitions[0];
1484                reg.reg_b += instr->operands[1].constantValue() * def.bytes();
1485
1486                if (reg == def.physReg())
1487                   break;
1488
1489                RegClass op_rc = def.regClass().is_subdword() ? def.regClass() :
1490                                 RegClass(instr->operands[0].getTemp().type(), def.size());
1491                std::map<PhysReg, copy_operation> copy_operations;
1492                copy_operations[def.physReg()] = {Operand(reg, op_rc), def, def.bytes()};
1493                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1494                break;
1495             }
1496             case aco_opcode::p_create_vector:
1497             {
1498                std::map<PhysReg, copy_operation> copy_operations;
1499                PhysReg reg = instr->definitions[0].physReg();
1500
1501                for (const Operand& op : instr->operands) {
1502                   if (op.isConstant()) {
1503                      const Definition def = Definition(reg, RegClass(instr->definitions[0].getTemp().type(), op.size()));
1504                      copy_operations[reg] = {op, def, op.bytes()};
1505                      reg.reg_b += op.bytes();
1506                      continue;
1507                   }
1508                   if (op.isUndefined()) {
1509                      // TODO: coalesce subdword copies if dst byte is 0
1510                      reg.reg_b += op.bytes();
1511                      continue;
1512                   }
1513
1514                   RegClass rc_def = op.regClass().is_subdword() ? op.regClass() :
1515                                     RegClass(instr->definitions[0].getTemp().type(), op.size());
1516                   const Definition def = Definition(reg, rc_def);
1517                   copy_operations[def.physReg()] = {op, def, op.bytes()};
1518                   reg.reg_b += op.bytes();
1519                }
1520                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1521                break;
1522             }
1523             case aco_opcode::p_split_vector:
1524             {
1525                std::map<PhysReg, copy_operation> copy_operations;
1526                PhysReg reg = instr->operands[0].physReg();
1527
1528                for (const Definition& def : instr->definitions) {
1529                   RegClass rc_op = def.regClass().is_subdword() ? def.regClass() :
1530                                    RegClass(instr->operands[0].getTemp().type(), def.size());
1531                   const Operand op = Operand(reg, rc_op);
1532                   copy_operations[def.physReg()] = {op, def, def.bytes()};
1533                   reg.reg_b += def.bytes();
1534                }
1535                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1536                break;
1537             }
1538             case aco_opcode::p_parallelcopy:
1539             case aco_opcode::p_wqm:
1540             {
1541                std::map<PhysReg, copy_operation> copy_operations;
1542                for (unsigned i = 0; i < instr->operands.size(); i++) {
1543                   assert(instr->definitions[i].bytes() == instr->operands[i].bytes());
1544                   copy_operations[instr->definitions[i].physReg()] = {instr->operands[i], instr->definitions[i], instr->operands[i].bytes()};
1545                }
1546                handle_operands(copy_operations, &ctx, program->chip_class, pi);
1547                break;
1548             }
1549             case aco_opcode::p_exit_early_if:
1550             {
1551                /* don't bother with an early exit near the end of the program */
1552                if ((block->instructions.size() - 1 - j) <= 4 &&
1553                     block->instructions.back()->opcode == aco_opcode::s_endpgm) {
1554                   unsigned null_exp_dest = (ctx.program->stage & hw_fs) ? 9 /* NULL */ : V_008DFC_SQ_EXP_POS;
1555                   bool ignore_early_exit = true;
1556
1557                   for (unsigned k = j + 1; k < block->instructions.size(); ++k) {
1558                      const aco_ptr<Instruction> &instr = block->instructions[k];
1559                      if (instr->opcode == aco_opcode::s_endpgm ||
1560                          instr->opcode == aco_opcode::p_logical_end)
1561                         continue;
1562                      else if (instr->opcode == aco_opcode::exp &&
1563                               static_cast<Export_instruction *>(instr.get())->dest == null_exp_dest)
1564                         continue;
1565                      else if (instr->opcode == aco_opcode::p_parallelcopy &&
1566                          instr->definitions[0].isFixed() &&
1567                          instr->definitions[0].physReg() == exec)
1568                         continue;
1569
1570                      ignore_early_exit = false;
1571                   }
1572
1573                   if (ignore_early_exit)
1574                      break;
1575                }
1576
1577                if (!discard_block) {
1578                   discard_block = program->create_and_insert_block();
1579                   block = &program->blocks[i];
1580
1581                   bld.reset(discard_block);
1582                   bld.exp(aco_opcode::exp, Operand(v1), Operand(v1), Operand(v1), Operand(v1),
1583                           0, V_008DFC_SQ_EXP_NULL, false, true, true);
1584                   if (program->wb_smem_l1_on_end)
1585                      bld.smem(aco_opcode::s_dcache_wb);
1586                   bld.sopp(aco_opcode::s_endpgm);
1587
1588                   bld.reset(&ctx.instructions);
1589                }
1590
1591                //TODO: exec can be zero here with block_kind_discard
1592
1593                assert(instr->operands[0].physReg() == scc);
1594                bld.sopp(aco_opcode::s_cbranch_scc0, instr->operands[0], discard_block->index);
1595
1596                discard_block->linear_preds.push_back(block->index);
1597                block->linear_succs.push_back(discard_block->index);
1598                break;
1599             }
1600             case aco_opcode::p_spill:
1601             {
1602                assert(instr->operands[0].regClass() == v1.as_linear());
1603                for (unsigned i = 0; i < instr->operands[2].size(); i++)
1604                   bld.writelane(bld.def(v1, instr->operands[0].physReg()),
1605                                 Operand(PhysReg{instr->operands[2].physReg() + i}, s1),
1606                                 Operand(instr->operands[1].constantValue() + i),
1607                                 instr->operands[0]);
1608                break;
1609             }
1610             case aco_opcode::p_reload:
1611             {
1612                assert(instr->operands[0].regClass() == v1.as_linear());
1613                for (unsigned i = 0; i < instr->definitions[0].size(); i++)
1614                   bld.readlane(bld.def(s1, PhysReg{instr->definitions[0].physReg() + i}),
1615                                instr->operands[0],
1616                                Operand(instr->operands[1].constantValue() + i));
1617                break;
1618             }
1619             case aco_opcode::p_as_uniform:
1620             {
1621                if (instr->operands[0].isConstant() || instr->operands[0].regClass().type() == RegType::sgpr) {
1622                   std::map<PhysReg, copy_operation> copy_operations;
1623                   copy_operations[instr->definitions[0].physReg()] = {instr->operands[0], instr->definitions[0], instr->definitions[0].bytes()};
1624                   handle_operands(copy_operations, &ctx, program->chip_class, pi);
1625                } else {
1626                   assert(instr->operands[0].regClass().type() == RegType::vgpr);
1627                   assert(instr->definitions[0].regClass().type() == RegType::sgpr);
1628                   assert(instr->operands[0].size() == instr->definitions[0].size());
1629                   for (unsigned i = 0; i < instr->definitions[0].size(); i++) {
1630                      bld.vop1(aco_opcode::v_readfirstlane_b32,
1631                               bld.def(s1, PhysReg{instr->definitions[0].physReg() + i}),
1632                               Operand(PhysReg{instr->operands[0].physReg() + i}, v1));
1633                   }
1634                }
1635                break;
1636             }
1637             case aco_opcode::p_bpermute:
1638             {
1639                if (ctx.program->chip_class <= GFX7)
1640                   emit_gfx6_bpermute(program, instr, bld);
1641                else if (ctx.program->chip_class == GFX10 && ctx.program->wave_size == 64)
1642                   emit_gfx10_wave64_bpermute(program, instr, bld);
1643                else
1644                   unreachable("Current hardware supports ds_bpermute, don't emit p_bpermute.");
1645             }
1646             default:
1647                break;
1648             }
1649          } else if (instr->format == Format::PSEUDO_BRANCH) {
1650             Pseudo_branch_instruction* branch = static_cast<Pseudo_branch_instruction*>(instr.get());
1651             /* check if all blocks from current to target are empty */
1652             bool can_remove = block->index < branch->target[0];
1653             for (unsigned i = block->index + 1; can_remove && i < branch->target[0]; i++) {
1654                if (program->blocks[i].instructions.size())
1655                   can_remove = false;
1656             }
1657             if (can_remove)
1658                continue;
1659
1660             switch (instr->opcode) {
1661                case aco_opcode::p_branch:
1662                   assert(block->linear_succs[0] == branch->target[0]);
1663                   bld.sopp(aco_opcode::s_branch, branch->target[0]);
1664                   break;
1665                case aco_opcode::p_cbranch_nz:
1666                   assert(block->linear_succs[1] == branch->target[0]);
1667                   if (branch->operands[0].physReg() == exec)
1668                      bld.sopp(aco_opcode::s_cbranch_execnz, branch->target[0]);
1669                   else if (branch->operands[0].physReg() == vcc)
1670                      bld.sopp(aco_opcode::s_cbranch_vccnz, branch->target[0]);
1671                   else {
1672                      assert(branch->operands[0].physReg() == scc);
1673                      bld.sopp(aco_opcode::s_cbranch_scc1, branch->target[0]);
1674                   }
1675                   break;
1676                case aco_opcode::p_cbranch_z:
1677                   assert(block->linear_succs[1] == branch->target[0]);
1678                   if (branch->operands[0].physReg() == exec)
1679                      bld.sopp(aco_opcode::s_cbranch_execz, branch->target[0]);
1680                   else if (branch->operands[0].physReg() == vcc)
1681                      bld.sopp(aco_opcode::s_cbranch_vccz, branch->target[0]);
1682                   else {
1683                      assert(branch->operands[0].physReg() == scc);
1684                      bld.sopp(aco_opcode::s_cbranch_scc0, branch->target[0]);
1685                   }
1686                   break;
1687                default:
1688                   unreachable("Unknown Pseudo branch instruction!");
1689             }
1690
1691          } else if (instr->format == Format::PSEUDO_REDUCTION) {
1692             Pseudo_reduction_instruction* reduce = static_cast<Pseudo_reduction_instruction*>(instr.get());
1693             emit_reduction(&ctx, reduce->opcode, reduce->reduce_op, reduce->cluster_size,
1694                            reduce->operands[1].physReg(), // tmp
1695                            reduce->definitions[1].physReg(), // stmp
1696                            reduce->operands[2].physReg(), // vtmp
1697                            reduce->definitions[2].physReg(), // sitmp
1698                            reduce->operands[0], reduce->definitions[0]);
1699          } else {
1700             ctx.instructions.emplace_back(std::move(instr));
1701          }
1702
1703       }
1704       block->instructions.swap(ctx.instructions);
1705    }
1706 }
1707
1708 }