src/amd/compiler/aco_register_allocation.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  *    Bas Nieuwenhuizen (bas@basnieuwenhuizen.nl)
  26  *
  27  */
  28
  29 #include <algorithm>
  30 #include <array>
  31 #include <map>
  32 #include <unordered_map>
  33
  34 #include "aco_ir.h"
  35 #include "sid.h"
  36 #include "util/u_math.h"
  37
  38 namespace aco {
  39 namespace {
  40
  41 unsigned get_subdword_operand_stride(chip_class chip, const aco_ptr<Instruction>& instr, unsigned idx, RegClass rc);
  42 void add_subdword_operand(chip_class chip, aco_ptr<Instruction>& instr, unsigned idx, unsigned byte, RegClass rc);
  43 std::pair<unsigned, unsigned> get_subdword_definition_info(Program *program, const aco_ptr<Instruction>& instr, RegClass rc);
  44 void add_subdword_definition(Program *program, aco_ptr<Instruction>& instr, unsigned idx, PhysReg reg, bool is_partial);
  45
  46 struct assignment {
  47    PhysReg reg;
  48    RegClass rc;
  49    uint8_t assigned = 0;
  50    assignment() = default;
  51    assignment(PhysReg reg, RegClass rc) : reg(reg), rc(rc), assigned(-1) {}
  52 };
  53
  54 struct phi_info {
  55    Instruction* phi;
  56    unsigned block_idx;
  57    std::set<Instruction*> uses;
  58 };
  59
  60 struct ra_ctx {
  61    std::bitset<512> war_hint;
  62    Program* program;
  63    std::vector<assignment> assignments;
  64    std::vector<std::unordered_map<unsigned, Temp>> renames;
  65    std::vector<std::vector<Instruction*>> incomplete_phis;
  66    std::vector<bool> filled;
  67    std::vector<bool> sealed;
  68    std::unordered_map<unsigned, Temp> orig_names;
  69    std::unordered_map<unsigned, phi_info> phi_map;
  70    std::unordered_map<unsigned, unsigned> affinities;
  71    std::unordered_map<unsigned, Instruction*> vectors;
  72    std::unordered_map<unsigned, Instruction*> split_vectors;
  73    aco_ptr<Instruction> pseudo_dummy;
  74    unsigned max_used_sgpr = 0;
  75    unsigned max_used_vgpr = 0;
  76    std::bitset<64> defs_done; /* see MAX_ARGS in aco_instruction_selection_setup.cpp */
  77
  78    ra_ctx(Program* program) : program(program),
  79                               assignments(program->peekAllocationId()),
  80                               renames(program->blocks.size()),
  81                               incomplete_phis(program->blocks.size()),
  82                               filled(program->blocks.size()),
  83                               sealed(program->blocks.size())
  84    {
  85       pseudo_dummy.reset(create_instruction<Instruction>(aco_opcode::p_parallelcopy, Format::PSEUDO, 0, 0));
  86    }
  87 };
  88
  89 struct DefInfo {
  90    uint16_t lb;
  91    uint16_t ub;
  92    uint8_t size;
  93    uint8_t stride;
  94    RegClass rc;
  95
  96    DefInfo(ra_ctx& ctx, aco_ptr<Instruction>& instr, RegClass rc_, int operand) : rc(rc_) {
  97       size = rc.size();
  98       stride = 1;
  99
 100       if (rc.type() == RegType::vgpr) {
 101          lb = 256;
 102          ub = 256 + ctx.program->max_reg_demand.vgpr;
 103       } else {
 104          lb = 0;
 105          ub = ctx.program->max_reg_demand.sgpr;
 106          if (size == 2)
 107             stride = 2;
 108          else if (size >= 4)
 109             stride = 4;
 110       }
 111
 112       if (rc.is_subdword() && operand >= 0) {
 113          /* stride in bytes */
 114          stride = get_subdword_operand_stride(ctx.program->chip_class, instr, operand, rc);
 115       } else if (rc.is_subdword()) {
 116          std::pair<unsigned, unsigned> info = get_subdword_definition_info(ctx.program, instr, rc);
 117          stride = info.first;
 118          if (info.second > rc.bytes()) {
 119             rc = RegClass::get(rc.type(), info.second);
 120             size = rc.size();
 121             /* we might still be able to put the definition in the high half,
 122              * but that's only useful for affinities and this information isn't
 123              * used for them */
 124             stride = align(stride, info.second);
 125             if (!rc.is_subdword())
 126                stride = DIV_ROUND_UP(stride, 4);
 127          }
 128          assert(stride > 0);
 129       }
 130    }
 131 };
 132
 133 class RegisterFile {
 134 public:
 135    RegisterFile() {regs.fill(0);}
 136
 137    std::array<uint32_t, 512> regs;
 138    std::map<uint32_t, std::array<uint32_t, 4>> subdword_regs;
 139
 140    const uint32_t& operator [] (unsigned index) const {
 141       return regs[index];
 142    }
 143
 144    uint32_t& operator [] (unsigned index) {
 145       return regs[index];
 146    }
 147
 148    unsigned count_zero(PhysReg start, unsigned size) {
 149       unsigned res = 0;
 150       for (unsigned i = 0; i < size; i++)
 151          res += !regs[start + i];
 152       return res;
 153    }
 154
 155    bool test(PhysReg start, unsigned num_bytes) {
 156       for (PhysReg i = start; i.reg_b < start.reg_b + num_bytes; i = PhysReg(i + 1)) {
 157          if (regs[i] & 0x0FFFFFFF)
 158             return true;
 159          if (regs[i] == 0xF0000000) {
 160             assert(subdword_regs.find(i) != subdword_regs.end());
 161             for (unsigned j = i.byte(); i * 4 + j < start.reg_b + num_bytes && j < 4; j++) {
 162                if (subdword_regs[i][j])
 163                   return true;
 164             }
 165          }
 166       }
 167       return false;
 168    }
 169
 170    void block(PhysReg start, RegClass rc) {
 171       if (rc.is_subdword())
 172          fill_subdword(start, rc.bytes(), 0xFFFFFFFF);
 173       else
 174          fill(start, rc.size(), 0xFFFFFFFF);
 175    }
 176
 177    bool is_blocked(PhysReg start) {
 178       if (regs[start] == 0xFFFFFFFF)
 179          return true;
 180       if (regs[start] == 0xF0000000) {
 181          for (unsigned i = start.byte(); i < 4; i++)
 182             if (subdword_regs[start][i] == 0xFFFFFFFF)
 183                return true;
 184       }
 185       return false;
 186    }
 187
 188    void clear(PhysReg start, RegClass rc) {
 189       if (rc.is_subdword())
 190          fill_subdword(start, rc.bytes(), 0);
 191       else
 192          fill(start, rc.size(), 0);
 193    }
 194
 195    void fill(Operand op) {
 196       if (op.regClass().is_subdword())
 197          fill_subdword(op.physReg(), op.bytes(), op.tempId());
 198       else
 199          fill(op.physReg(), op.size(), op.tempId());
 200    }
 201
 202    void clear(Operand op) {
 203       clear(op.physReg(), op.regClass());
 204    }
 205
 206    void fill(Definition def) {
 207       if (def.regClass().is_subdword())
 208          fill_subdword(def.physReg(), def.bytes(), def.tempId());
 209       else
 210          fill(def.physReg(), def.size(), def.tempId());
 211    }
 212
 213    void clear(Definition def) {
 214       clear(def.physReg(), def.regClass());
 215    }
 216
 217 private:
 218    void fill(PhysReg start, unsigned size, uint32_t val) {
 219       for (unsigned i = 0; i < size; i++)
 220          regs[start + i] = val;
 221    }
 222
 223    void fill_subdword(PhysReg start, unsigned num_bytes, uint32_t val) {
 224       fill(start, DIV_ROUND_UP(num_bytes, 4), 0xF0000000);
 225       for (PhysReg i = start; i.reg_b < start.reg_b + num_bytes; i = PhysReg(i + 1)) {
 226          /* emplace or get */
 227          std::array<uint32_t, 4>& sub = subdword_regs.emplace(i, std::array<uint32_t, 4>{0, 0, 0, 0}).first->second;
 228          for (unsigned j = i.byte(); i * 4 + j < start.reg_b + num_bytes && j < 4; j++)
 229             sub[j] = val;
 230
 231          if (sub == std::array<uint32_t, 4>{0, 0, 0, 0}) {
 232             subdword_regs.erase(i);
 233             regs[i] = 0;
 234          }
 235       }
 236    }
 237 };
 238
 239
 240 /* helper function for debugging */
 241 #if 0
 242 void print_regs(ra_ctx& ctx, bool vgprs, RegisterFile& reg_file)
 243 {
 244    unsigned max = vgprs ? ctx.program->max_reg_demand.vgpr : ctx.program->max_reg_demand.sgpr;
 245    unsigned lb = vgprs ? 256 : 0;
 246    unsigned ub = lb + max;
 247    char reg_char = vgprs ? 'v' : 's';
 248
 249    /* print markers */
 250    printf("       ");
 251    for (unsigned i = lb; i < ub; i += 3) {
 252       printf("%.2u ", i - lb);
 253    }
 254    printf("\n");
 255
 256    /* print usage */
 257    printf("%cgprs: ", reg_char);
 258    unsigned free_regs = 0;
 259    unsigned prev = 0;
 260    bool char_select = false;
 261    for (unsigned i = lb; i < ub; i++) {
 262       if (reg_file[i] == 0xFFFF) {
 263          printf("~");
 264       } else if (reg_file[i]) {
 265          if (reg_file[i] != prev) {
 266             prev = reg_file[i];
 267             char_select = !char_select;
 268          }
 269          printf(char_select ? "#" : "@");
 270       } else {
 271          free_regs++;
 272          printf(".");
 273       }
 274    }
 275    printf("\n");
 276
 277    printf("%u/%u used, %u/%u free\n", max - free_regs, max, free_regs, max);
 278
 279    /* print assignments */
 280    prev = 0;
 281    unsigned size = 0;
 282    for (unsigned i = lb; i < ub; i++) {
 283       if (reg_file[i] != prev) {
 284          if (prev && size > 1)
 285             printf("-%d]\n", i - 1 - lb);
 286          else if (prev)
 287             printf("]\n");
 288          prev = reg_file[i];
 289          if (prev && prev != 0xFFFF) {
 290             if (ctx.orig_names.count(reg_file[i]) && ctx.orig_names[reg_file[i]].id() != reg_file[i])
 291                printf("%%%u (was %%%d) = %c[%d", reg_file[i], ctx.orig_names[reg_file[i]].id(), reg_char, i - lb);
 292             else
 293                printf("%%%u = %c[%d", reg_file[i], reg_char, i - lb);
 294          }
 295          size = 1;
 296       } else {
 297          size++;
 298       }
 299    }
 300    if (prev && size > 1)
 301       printf("-%d]\n", ub - lb - 1);
 302    else if (prev)
 303       printf("]\n");
 304 }
 305 #endif
 306
 307
 308 unsigned get_subdword_operand_stride(chip_class chip, const aco_ptr<Instruction>& instr, unsigned idx, RegClass rc)
 309 {
 310    if (instr->format == Format::PSEUDO && chip >= GFX8)
 311       return rc.bytes() % 2 == 0 ? 2 : 1;
 312
 313    if (instr->opcode == aco_opcode::v_cvt_f32_ubyte0) {
 314       return 1;
 315    } else if (can_use_SDWA(chip, instr)) {
 316       return rc.bytes() % 2 == 0 ? 2 : 1;
 317    } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, idx, 1)) {
 318       return 2;
 319    }
 320
 321    switch (instr->opcode) {
 322    case aco_opcode::ds_write_b8:
 323    case aco_opcode::ds_write_b16:
 324       return chip >= GFX8 ? 2 : 4;
 325    case aco_opcode::buffer_store_byte:
 326    case aco_opcode::buffer_store_short:
 327    case aco_opcode::flat_store_byte:
 328    case aco_opcode::flat_store_short:
 329    case aco_opcode::scratch_store_byte:
 330    case aco_opcode::scratch_store_short:
 331    case aco_opcode::global_store_byte:
 332    case aco_opcode::global_store_short:
 333       return chip >= GFX9 ? 2 : 4;
 334    default:
 335       break;
 336    }
 337
 338    return 4;
 339 }
 340
 341 void add_subdword_operand(chip_class chip, aco_ptr<Instruction>& instr, unsigned idx, unsigned byte, RegClass rc)
 342 {
 343    if (instr->format == Format::PSEUDO || byte == 0)
 344       return;
 345
 346    assert(rc.bytes() <= 2);
 347
 348    if (!instr->usesModifiers() && instr->opcode == aco_opcode::v_cvt_f32_ubyte0) {
 349       switch (byte) {
 350       case 0:
 351          instr->opcode = aco_opcode::v_cvt_f32_ubyte0;
 352          break;
 353       case 1:
 354          instr->opcode = aco_opcode::v_cvt_f32_ubyte1;
 355          break;
 356       case 2:
 357          instr->opcode = aco_opcode::v_cvt_f32_ubyte2;
 358          break;
 359       case 3:
 360          instr->opcode = aco_opcode::v_cvt_f32_ubyte3;
 361          break;
 362       }
 363       return;
 364    } else if (can_use_SDWA(chip, instr)) {
 365       convert_to_SDWA(chip, instr);
 366       return;
 367    } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, idx, byte / 2)) {
 368       VOP3A_instruction *vop3 = static_cast<VOP3A_instruction *>(instr.get());
 369       vop3->opsel |= (byte / 2) << idx;
 370       return;
 371    }
 372
 373    if (chip >= GFX8 && instr->opcode == aco_opcode::ds_write_b8 && byte == 2) {
 374       instr->opcode = aco_opcode::ds_write_b8_d16_hi;
 375       return;
 376    }
 377    if (chip >= GFX8 && instr->opcode == aco_opcode::ds_write_b16 && byte == 2) {
 378       instr->opcode = aco_opcode::ds_write_b16_d16_hi;
 379       return;
 380    }
 381
 382    if (chip >= GFX9 && byte == 2) {
 383       if (instr->opcode == aco_opcode::buffer_store_byte)
 384          instr->opcode = aco_opcode::buffer_store_byte_d16_hi;
 385       else if (instr->opcode == aco_opcode::buffer_store_short)
 386          instr->opcode = aco_opcode::buffer_store_short_d16_hi;
 387       else if (instr->opcode == aco_opcode::flat_store_byte)
 388          instr->opcode = aco_opcode::flat_store_byte_d16_hi;
 389       else if (instr->opcode == aco_opcode::flat_store_short)
 390          instr->opcode = aco_opcode::flat_store_short_d16_hi;
 391       else if (instr->opcode == aco_opcode::scratch_store_byte)
 392          instr->opcode = aco_opcode::scratch_store_byte_d16_hi;
 393       else if (instr->opcode == aco_opcode::scratch_store_short)
 394          instr->opcode = aco_opcode::scratch_store_short_d16_hi;
 395       else if (instr->opcode == aco_opcode::global_store_byte)
 396          instr->opcode = aco_opcode::global_store_byte_d16_hi;
 397       else if (instr->opcode == aco_opcode::global_store_short)
 398          instr->opcode = aco_opcode::global_store_short_d16_hi;
 399       else
 400          unreachable("Something went wrong: Impossible register assignment.");
 401    }
 402 }
 403
 404 /* minimum_stride, bytes_written */
 405 std::pair<unsigned, unsigned> get_subdword_definition_info(Program *program, const aco_ptr<Instruction>& instr, RegClass rc)
 406 {
 407    chip_class chip = program->chip_class;
 408
 409    if (instr->format == Format::PSEUDO && chip >= GFX8)
 410       return std::make_pair(rc.bytes() % 2 == 0 ? 2 : 1, rc.bytes());
 411    else if (instr->format == Format::PSEUDO)
 412       return std::make_pair(4, rc.size() * 4u);
 413
 414    unsigned bytes_written = chip >= GFX10 ? rc.bytes() : 4u;
 415    switch (instr->opcode) {
 416    case aco_opcode::v_mad_f16:
 417    case aco_opcode::v_mad_u16:
 418    case aco_opcode::v_mad_i16:
 419    case aco_opcode::v_fma_f16:
 420    case aco_opcode::v_div_fixup_f16:
 421    case aco_opcode::v_interp_p2_f16:
 422       bytes_written = chip >= GFX9 ? rc.bytes() : 4u;
 423       break;
 424    default:
 425       break;
 426    }
 427    bytes_written = MAX2(bytes_written, instr_info.definition_size[(int)instr->opcode] / 8u);
 428
 429    if (can_use_SDWA(chip, instr)) {
 430       return std::make_pair(rc.bytes(), rc.bytes());
 431    } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, -1, 1)) {
 432       return std::make_pair(2u, chip >= GFX10 ? 2u : 4u);
 433    }
 434
 435    switch (instr->opcode) {
 436    case aco_opcode::buffer_load_ubyte_d16:
 437    case aco_opcode::buffer_load_short_d16:
 438    case aco_opcode::flat_load_ubyte_d16:
 439    case aco_opcode::flat_load_short_d16:
 440    case aco_opcode::scratch_load_ubyte_d16:
 441    case aco_opcode::scratch_load_short_d16:
 442    case aco_opcode::global_load_ubyte_d16:
 443    case aco_opcode::global_load_short_d16:
 444    case aco_opcode::ds_read_u8_d16:
 445    case aco_opcode::ds_read_u16_d16:
 446       if (chip >= GFX9 && !program->sram_ecc_enabled)
 447          return std::make_pair(2u, 2u);
 448       else
 449          return std::make_pair(2u, 4u);
 450    default:
 451       break;
 452    }
 453
 454    return std::make_pair(4u, bytes_written);
 455 }
 456
 457 void add_subdword_definition(Program *program, aco_ptr<Instruction>& instr, unsigned idx, PhysReg reg, bool is_partial)
 458 {
 459    RegClass rc = instr->definitions[idx].regClass();
 460    chip_class chip = program->chip_class;
 461
 462    instr->definitions[idx].setFixed(reg);
 463
 464    if (instr->format == Format::PSEUDO) {
 465       return;
 466    } else if (can_use_SDWA(chip, instr)) {
 467       if (reg.byte() || (is_partial && chip < GFX10))
 468          convert_to_SDWA(chip, instr);
 469       return;
 470    } else if (reg.byte() && rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, -1, reg.byte() / 2)) {
 471       VOP3A_instruction *vop3 = static_cast<VOP3A_instruction *>(instr.get());
 472       if (reg.byte() == 2)
 473          vop3->opsel |= (1 << 3); /* dst in high half */
 474       return;
 475    }
 476
 477    if (reg.byte() == 2) {
 478       if (instr->opcode == aco_opcode::buffer_load_ubyte_d16)
 479          instr->opcode = aco_opcode::buffer_load_ubyte_d16_hi;
 480       else if (instr->opcode == aco_opcode::buffer_load_short_d16)
 481          instr->opcode = aco_opcode::buffer_load_short_d16_hi;
 482       else if (instr->opcode == aco_opcode::flat_load_ubyte_d16)
 483          instr->opcode = aco_opcode::flat_load_ubyte_d16_hi;
 484       else if (instr->opcode == aco_opcode::flat_load_short_d16)
 485          instr->opcode = aco_opcode::flat_load_short_d16_hi;
 486       else if (instr->opcode == aco_opcode::scratch_load_ubyte_d16)
 487          instr->opcode = aco_opcode::scratch_load_ubyte_d16_hi;
 488       else if (instr->opcode == aco_opcode::scratch_load_short_d16)
 489          instr->opcode = aco_opcode::scratch_load_short_d16_hi;
 490       else if (instr->opcode == aco_opcode::global_load_ubyte_d16)
 491          instr->opcode = aco_opcode::global_load_ubyte_d16_hi;
 492       else if (instr->opcode == aco_opcode::global_load_short_d16)
 493          instr->opcode = aco_opcode::global_load_short_d16_hi;
 494       else if (instr->opcode == aco_opcode::ds_read_u8_d16)
 495          instr->opcode = aco_opcode::ds_read_u8_d16_hi;
 496       else if (instr->opcode == aco_opcode::ds_read_u16_d16)
 497          instr->opcode = aco_opcode::ds_read_u16_d16_hi;
 498       else
 499          unreachable("Something went wrong: Impossible register assignment.");
 500    }
 501 }
 502
 503 void adjust_max_used_regs(ra_ctx& ctx, RegClass rc, unsigned reg)
 504 {
 505    unsigned max_addressible_sgpr = ctx.program->sgpr_limit;
 506    unsigned size = rc.size();
 507    if (rc.type() == RegType::vgpr) {
 508       assert(reg >= 256);
 509       unsigned hi = reg - 256 + size - 1;
 510       ctx.max_used_vgpr = std::max(ctx.max_used_vgpr, hi);
 511    } else if (reg + rc.size() <= max_addressible_sgpr) {
 512       unsigned hi = reg + size - 1;
 513       ctx.max_used_sgpr = std::max(ctx.max_used_sgpr, std::min(hi, max_addressible_sgpr));
 514    }
 515 }
 516
 517
 518 void update_renames(ra_ctx& ctx, RegisterFile& reg_file,
 519                     std::vector<std::pair<Operand, Definition>>& parallelcopies,
 520                     aco_ptr<Instruction>& instr, bool rename_not_killed_ops)
 521 {
 522    /* allocate id's and rename operands: this is done transparently here */
 523    for (std::pair<Operand, Definition>& copy : parallelcopies) {
 524       /* the definitions with id are not from this function and already handled */
 525       if (copy.second.isTemp())
 526          continue;
 527
 528       /* check if we we moved another parallelcopy definition */
 529       for (std::pair<Operand, Definition>& other : parallelcopies) {
 530          if (!other.second.isTemp())
 531             continue;
 532          if (copy.first.getTemp() == other.second.getTemp()) {
 533             copy.first.setTemp(other.first.getTemp());
 534             copy.first.setFixed(other.first.physReg());
 535          }
 536       }
 537       // FIXME: if a definition got moved, change the target location and remove the parallelcopy
 538       copy.second.setTemp(Temp(ctx.program->allocateId(), copy.second.regClass()));
 539       ctx.assignments.emplace_back(copy.second.physReg(), copy.second.regClass());
 540       assert(ctx.assignments.size() == ctx.program->peekAllocationId());
 541       reg_file.fill(copy.second);
 542
 543       /* check if we moved an operand */
 544       bool first = true;
 545       for (unsigned i = 0; i < instr->operands.size(); i++) {
 546          Operand& op = instr->operands[i];
 547          if (!op.isTemp())
 548             continue;
 549          if (op.tempId() == copy.first.tempId()) {
 550             bool omit_renaming = !rename_not_killed_ops && !op.isKillBeforeDef();
 551             for (std::pair<Operand, Definition>& pc : parallelcopies) {
 552                PhysReg def_reg = pc.second.physReg();
 553                omit_renaming &= def_reg > copy.first.physReg() ?
 554                                 (copy.first.physReg() + copy.first.size() <= def_reg.reg()) :
 555                                 (def_reg + pc.second.size() <= copy.first.physReg().reg());
 556             }
 557             if (omit_renaming) {
 558                if (first)
 559                   op.setFirstKill(true);
 560                else
 561                   op.setKill(true);
 562                first = false;
 563                continue;
 564             }
 565             op.setTemp(copy.second.getTemp());
 566             op.setFixed(copy.second.physReg());
 567          }
 568       }
 569    }
 570 }
 571
 572 std::pair<PhysReg, bool> get_reg_simple(ra_ctx& ctx,
 573                                         RegisterFile& reg_file,
 574                                         DefInfo info)
 575 {
 576    uint32_t lb = info.lb;
 577    uint32_t ub = info.ub;
 578    uint32_t size = info.size;
 579    uint32_t stride = info.rc.is_subdword() ? DIV_ROUND_UP(info.stride, 4) : info.stride;
 580    RegClass rc = info.rc;
 581
 582    if (stride == 1) {
 583
 584       for (unsigned stride = 8; stride > 1; stride /= 2) {
 585          if (size % stride)
 586             continue;
 587          info.stride = stride;
 588          std::pair<PhysReg, bool> res = get_reg_simple(ctx, reg_file, info);
 589          if (res.second)
 590             return res;
 591       }
 592
 593       /* best fit algorithm: find the smallest gap to fit in the variable */
 594       unsigned best_pos = 0xFFFF;
 595       unsigned gap_size = 0xFFFF;
 596       unsigned last_pos = 0xFFFF;
 597
 598       for (unsigned current_reg = lb; current_reg < ub; current_reg++) {
 599
 600          if (reg_file[current_reg] == 0 && !ctx.war_hint[current_reg]) {
 601             if (last_pos == 0xFFFF)
 602                last_pos = current_reg;
 603
 604             /* stop searching after max_used_gpr */
 605             if (current_reg == ctx.max_used_sgpr + 1 || current_reg == 256 + ctx.max_used_vgpr + 1)
 606                break;
 607             else
 608                continue;
 609          }
 610
 611          if (last_pos == 0xFFFF)
 612             continue;
 613
 614          /* early return on exact matches */
 615          if (last_pos + size == current_reg) {
 616             adjust_max_used_regs(ctx, rc, last_pos);
 617             return {PhysReg{last_pos}, true};
 618          }
 619
 620          /* check if it fits and the gap size is smaller */
 621          if (last_pos + size < current_reg && current_reg - last_pos < gap_size) {
 622             best_pos = last_pos;
 623             gap_size = current_reg - last_pos;
 624          }
 625          last_pos = 0xFFFF;
 626       }
 627
 628       /* final check */
 629       if (last_pos + size <= ub && ub - last_pos < gap_size) {
 630          best_pos = last_pos;
 631          gap_size = ub - last_pos;
 632       }
 633
 634       if (best_pos == 0xFFFF)
 635          return {{}, false};
 636
 637       /* find best position within gap by leaving a good stride for other variables*/
 638       unsigned buffer = gap_size - size;
 639       if (buffer > 1) {
 640          if (((best_pos + size) % 8 != 0 && (best_pos + buffer) % 8 == 0) ||
 641              ((best_pos + size) % 4 != 0 && (best_pos + buffer) % 4 == 0) ||
 642              ((best_pos + size) % 2 != 0 && (best_pos + buffer) % 2 == 0))
 643             best_pos = best_pos + buffer;
 644       }
 645
 646       adjust_max_used_regs(ctx, rc, best_pos);
 647       return {PhysReg{best_pos}, true};
 648    }
 649
 650    bool found = false;
 651    unsigned reg_lo = lb;
 652    unsigned reg_hi = lb + size - 1;
 653    while (!found && reg_lo + size <= ub) {
 654       if (reg_file[reg_lo] != 0) {
 655          reg_lo += stride;
 656          continue;
 657       }
 658       reg_hi = reg_lo + size - 1;
 659       found = true;
 660       for (unsigned reg = reg_lo + 1; found && reg <= reg_hi; reg++) {
 661          if (reg_file[reg] != 0 || ctx.war_hint[reg])
 662             found = false;
 663       }
 664       if (found) {
 665          adjust_max_used_regs(ctx, rc, reg_lo);
 666          return {PhysReg{reg_lo}, true};
 667       }
 668
 669       reg_lo += stride;
 670    }
 671
 672    /* do this late because using the upper bytes of a register can require
 673     * larger instruction encodings or copies
 674     * TODO: don't do this in situations where it doesn't benefit */
 675    if (rc.is_subdword()) {
 676       for (std::pair<uint32_t, std::array<uint32_t, 4>> entry : reg_file.subdword_regs) {
 677          assert(reg_file[entry.first] == 0xF0000000);
 678          if (lb > entry.first || entry.first >= ub)
 679             continue;
 680
 681          for (unsigned i = 0; i < 4; i+= info.stride) {
 682             if (entry.second[i] != 0)
 683                continue;
 684
 685             bool reg_found = true;
 686             for (unsigned j = 1; reg_found && i + j < 4 && j < rc.bytes(); j++)
 687                reg_found &= entry.second[i + j] == 0;
 688
 689             /* check neighboring reg if needed */
 690             reg_found &= ((int)i <= 4 - (int)rc.bytes() || reg_file[entry.first + 1] == 0);
 691             if (reg_found) {
 692                PhysReg res{entry.first};
 693                res.reg_b += i;
 694                adjust_max_used_regs(ctx, rc, entry.first);
 695                return {res, true};
 696             }
 697          }
 698       }
 699    }
 700
 701    return {{}, false};
 702 }
 703
 704 /* collect variables from a register area and clear reg_file */
 705 std::set<std::pair<unsigned, unsigned>> collect_vars(ra_ctx& ctx, RegisterFile& reg_file,
 706                                                      PhysReg reg, unsigned size)
 707 {
 708    std::set<std::pair<unsigned, unsigned>> vars;
 709    for (unsigned j = reg; j < reg + size; j++) {
 710       if (reg_file.is_blocked(PhysReg{j}))
 711          continue;
 712       if (reg_file[j] == 0xF0000000) {
 713          for (unsigned k = 0; k < 4; k++) {
 714             unsigned id = reg_file.subdword_regs[j][k];
 715             if (id) {
 716                assignment& var = ctx.assignments[id];
 717                vars.emplace(var.rc.bytes(), id);
 718                reg_file.clear(var.reg, var.rc);
 719                if (!reg_file[j])
 720                   break;
 721             }
 722          }
 723       } else if (reg_file[j] != 0) {
 724          unsigned id = reg_file[j];
 725          assignment& var = ctx.assignments[id];
 726          vars.emplace(var.rc.bytes(), id);
 727          reg_file.clear(var.reg, var.rc);
 728       }
 729    }
 730    return vars;
 731 }
 732
 733 bool get_regs_for_copies(ra_ctx& ctx,
 734                          RegisterFile& reg_file,
 735                          std::vector<std::pair<Operand, Definition>>& parallelcopies,
 736                          const std::set<std::pair<unsigned, unsigned>> &vars,
 737                          uint32_t lb, uint32_t ub,
 738                          aco_ptr<Instruction>& instr,
 739                          uint32_t def_reg_lo,
 740                          uint32_t def_reg_hi)
 741 {
 742
 743    /* variables are sorted from small sized to large */
 744    /* NOTE: variables are also sorted by ID. this only affects a very small number of shaders slightly though. */
 745    for (std::set<std::pair<unsigned, unsigned>>::const_reverse_iterator it = vars.rbegin(); it != vars.rend(); ++it) {
 746       unsigned id = it->second;
 747       assignment& var = ctx.assignments[id];
 748       DefInfo info = DefInfo(ctx, ctx.pseudo_dummy, var.rc, -1);
 749       uint32_t size = info.size;
 750
 751       /* check if this is a dead operand, then we can re-use the space from the definition
 752        * also use the correct stride for sub-dword operands */
 753       bool is_dead_operand = false;
 754       for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) {
 755          if (instr->operands[i].isTemp() && instr->operands[i].tempId() == id) {
 756             if (instr->operands[i].isKillBeforeDef())
 757                is_dead_operand = true;
 758             info = DefInfo(ctx, instr, var.rc, i);
 759             break;
 760          }
 761       }
 762
 763       std::pair<PhysReg, bool> res;
 764       if (is_dead_operand) {
 765          if (instr->opcode == aco_opcode::p_create_vector) {
 766             PhysReg reg(def_reg_lo);
 767             for (unsigned i = 0; i < instr->operands.size(); i++) {
 768                if (instr->operands[i].isTemp() && instr->operands[i].tempId() == id) {
 769                   assert(!reg_file.test(reg, var.rc.bytes()));
 770                   res = {reg, !var.rc.is_subdword() || (reg.byte() % info.stride == 0)};
 771                   break;
 772                }
 773                reg.reg_b += instr->operands[i].bytes();
 774             }
 775          } else {
 776             info.lb = def_reg_lo;
 777             info.ub = def_reg_hi + 1;
 778             res = get_reg_simple(ctx, reg_file, info);
 779          }
 780       } else {
 781          info.lb = lb;
 782          info.ub = MIN2(def_reg_lo, ub);
 783          res = get_reg_simple(ctx, reg_file, info);
 784          if (!res.second && def_reg_hi < ub) {
 785             info.lb = (def_reg_hi + info.stride) & ~(info.stride - 1);
 786             info.ub = ub;
 787             res = get_reg_simple(ctx, reg_file, info);
 788          }
 789       }
 790
 791       if (res.second) {
 792          /* mark the area as blocked */
 793          reg_file.block(res.first, var.rc);
 794
 795          /* create parallelcopy pair (without definition id) */
 796          Temp tmp = Temp(id, var.rc);
 797          Operand pc_op = Operand(tmp);
 798          pc_op.setFixed(var.reg);
 799          Definition pc_def = Definition(res.first, pc_op.regClass());
 800          parallelcopies.emplace_back(pc_op, pc_def);
 801          continue;
 802       }
 803
 804       unsigned best_pos = lb;
 805       unsigned num_moves = 0xFF;
 806       unsigned num_vars = 0;
 807
 808       /* we use a sliding window to find potential positions */
 809       unsigned reg_lo = lb;
 810       unsigned reg_hi = lb + size - 1;
 811       unsigned stride = var.rc.is_subdword() ? 1 : info.stride;
 812       for (reg_lo = lb, reg_hi = lb + size - 1; reg_hi < ub; reg_lo += stride, reg_hi += stride) {
 813          if (!is_dead_operand && ((reg_lo >= def_reg_lo && reg_lo <= def_reg_hi) ||
 814                                   (reg_hi >= def_reg_lo && reg_hi <= def_reg_hi)))
 815             continue;
 816
 817          /* second, check that we have at most k=num_moves elements in the window
 818           * and no element is larger than the currently processed one */
 819          unsigned k = 0;
 820          unsigned n = 0;
 821          unsigned last_var = 0;
 822          bool found = true;
 823          for (unsigned j = reg_lo; found && j <= reg_hi; j++) {
 824             if (reg_file[j] == 0 || reg_file[j] == last_var)
 825                continue;
 826
 827             if (reg_file.is_blocked(PhysReg{j}) || k > num_moves) {
 828                found = false;
 829                break;
 830             }
 831             if (reg_file[j] == 0xF0000000) {
 832                k += 1;
 833                n++;
 834                continue;
 835             }
 836             /* we cannot split live ranges of linear vgprs */
 837             if (ctx.assignments[reg_file[j]].rc & (1 << 6)) {
 838                found = false;
 839                break;
 840             }
 841             bool is_kill = false;
 842             for (const Operand& op : instr->operands) {
 843                if (op.isTemp() && op.isKillBeforeDef() && op.tempId() == reg_file[j]) {
 844                   is_kill = true;
 845                   break;
 846                }
 847             }
 848             if (!is_kill && ctx.assignments[reg_file[j]].rc.size() >= size) {
 849                found = false;
 850                break;
 851             }
 852
 853             k += ctx.assignments[reg_file[j]].rc.size();
 854             last_var = reg_file[j];
 855             n++;
 856             if (k > num_moves || (k == num_moves && n <= num_vars)) {
 857                found = false;
 858                break;
 859             }
 860          }
 861
 862          if (found) {
 863             best_pos = reg_lo;
 864             num_moves = k;
 865             num_vars = n;
 866          }
 867       }
 868
 869       /* FIXME: we messed up and couldn't find space for the variables to be copied */
 870       if (num_moves == 0xFF)
 871          return false;
 872
 873       reg_lo = best_pos;
 874       reg_hi = best_pos + size - 1;
 875
 876       /* collect variables and block reg file */
 877       std::set<std::pair<unsigned, unsigned>> new_vars = collect_vars(ctx, reg_file, PhysReg{reg_lo}, size);
 878
 879       /* mark the area as blocked */
 880       reg_file.block(PhysReg{reg_lo}, var.rc);
 881
 882       if (!get_regs_for_copies(ctx, reg_file, parallelcopies, new_vars, lb, ub, instr, def_reg_lo, def_reg_hi))
 883          return false;
 884
 885       adjust_max_used_regs(ctx, var.rc, reg_lo);
 886
 887       /* create parallelcopy pair (without definition id) */
 888       Temp tmp = Temp(id, var.rc);
 889       Operand pc_op = Operand(tmp);
 890       pc_op.setFixed(var.reg);
 891       Definition pc_def = Definition(PhysReg{reg_lo}, pc_op.regClass());
 892       parallelcopies.emplace_back(pc_op, pc_def);
 893    }
 894
 895    return true;
 896 }
 897
 898
 899 std::pair<PhysReg, bool> get_reg_impl(ra_ctx& ctx,
 900                                       RegisterFile& reg_file,
 901                                       std::vector<std::pair<Operand, Definition>>& parallelcopies,
 902                                       DefInfo info,
 903                                       aco_ptr<Instruction>& instr)
 904 {
 905    uint32_t lb = info.lb;
 906    uint32_t ub = info.ub;
 907    uint32_t size = info.size;
 908    uint32_t stride = info.stride;
 909    RegClass rc = info.rc;
 910
 911    /* check how many free regs we have */
 912    unsigned regs_free = reg_file.count_zero(PhysReg{lb}, ub-lb);
 913
 914    /* mark and count killed operands */
 915    unsigned killed_ops = 0;
 916    for (unsigned j = 0; !is_phi(instr) && j < instr->operands.size(); j++) {
 917       if (instr->operands[j].isTemp() &&
 918           instr->operands[j].isFirstKillBeforeDef() &&
 919           instr->operands[j].physReg() >= lb &&
 920           instr->operands[j].physReg() < ub &&
 921           !reg_file.test(instr->operands[j].physReg(), instr->operands[j].bytes())) {
 922          assert(instr->operands[j].isFixed());
 923          reg_file.block(instr->operands[j].physReg(), instr->operands[j].regClass());
 924          killed_ops += instr->operands[j].getTemp().size();
 925       }
 926    }
 927
 928    assert(regs_free >= size);
 929    /* we might have to move dead operands to dst in order to make space */
 930    unsigned op_moves = 0;
 931
 932    if (size > (regs_free - killed_ops))
 933       op_moves = size - (regs_free - killed_ops);
 934
 935    /* find the best position to place the definition */
 936    unsigned best_pos = lb;
 937    unsigned num_moves = 0xFF;
 938    unsigned num_vars = 0;
 939
 940    /* we use a sliding window to check potential positions */
 941    unsigned reg_lo = lb;
 942    unsigned reg_hi = lb + size - 1;
 943    for (reg_lo = lb, reg_hi = lb + size - 1; reg_hi < ub; reg_lo += stride, reg_hi += stride) {
 944       /* first check the edges: this is what we have to fix to allow for num_moves > size */
 945       if (reg_lo > lb && reg_file[reg_lo] != 0 && reg_file[reg_lo] == reg_file[reg_lo - 1])
 946          continue;
 947       if (reg_hi < ub - 1 && reg_file[reg_hi] != 0 && reg_file[reg_hi] == reg_file[reg_hi + 1])
 948          continue;
 949
 950       /* second, check that we have at most k=num_moves elements in the window
 951        * and no element is larger than the currently processed one */
 952       unsigned k = op_moves;
 953       unsigned n = 0;
 954       unsigned remaining_op_moves = op_moves;
 955       unsigned last_var = 0;
 956       bool found = true;
 957       bool aligned = rc == RegClass::v4 && reg_lo % 4 == 0;
 958       for (unsigned j = reg_lo; found && j <= reg_hi; j++) {
 959          if (reg_file[j] == 0 || reg_file[j] == last_var)
 960             continue;
 961
 962          /* dead operands effectively reduce the number of estimated moves */
 963          if (reg_file.is_blocked(PhysReg{j})) {
 964             if (remaining_op_moves) {
 965                k--;
 966                remaining_op_moves--;
 967             }
 968             continue;
 969          }
 970
 971          if (reg_file[j] == 0xF0000000) {
 972             k += 1;
 973             n++;
 974             continue;
 975          }
 976
 977          if (ctx.assignments[reg_file[j]].rc.size() >= size) {
 978             found = false;
 979             break;
 980          }
 981
 982          /* we cannot split live ranges of linear vgprs */
 983          if (ctx.assignments[reg_file[j]].rc & (1 << 6)) {
 984             found = false;
 985             break;
 986          }
 987
 988          k += ctx.assignments[reg_file[j]].rc.size();
 989          n++;
 990          last_var = reg_file[j];
 991       }
 992
 993       if (!found || k > num_moves)
 994          continue;
 995       if (k == num_moves && n < num_vars)
 996          continue;
 997       if (!aligned && k == num_moves && n == num_vars)
 998          continue;
 999
1000       if (found) {
1001          best_pos = reg_lo;
1002          num_moves = k;
1003          num_vars = n;
1004       }
1005    }
1006
1007    if (num_moves == 0xFF) {
1008       /* remove killed operands from reg_file once again */
1009       for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) {
1010          if (instr->operands[i].isTemp() && instr->operands[i].isFirstKillBeforeDef())
1011             reg_file.clear(instr->operands[i]);
1012       }
1013       for (unsigned i = 0; i < instr->definitions.size(); i++) {
1014          Definition def = instr->definitions[i];
1015          if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i))
1016             reg_file.fill(def);
1017       }
1018       return {{}, false};
1019    }
1020
1021    RegisterFile register_file = reg_file;
1022
1023    /* now, we figured the placement for our definition */
1024    std::set<std::pair<unsigned, unsigned>> vars = collect_vars(ctx, reg_file, PhysReg{best_pos}, size);
1025
1026    if (instr->opcode == aco_opcode::p_create_vector) {
1027       /* move killed operands which aren't yet at the correct position (GFX9+)
1028        * or which are in the definition space */
1029       PhysReg reg = PhysReg{best_pos};
1030       for (Operand& op : instr->operands) {
1031          if (op.isTemp() && op.isFirstKillBeforeDef() &&
1032              op.getTemp().type() == rc.type()) {
1033             if (op.physReg() != reg &&
1034                 (ctx.program->chip_class >= GFX9 ||
1035                  (op.physReg().advance(op.bytes()) > PhysReg{best_pos} &&
1036                   op.physReg() < PhysReg{best_pos + size}))) {
1037                vars.emplace(op.bytes(), op.tempId());
1038                reg_file.clear(op);
1039             } else {
1040                reg_file.fill(op);
1041             }
1042          }
1043          reg.reg_b += op.bytes();
1044       }
1045    } else if (!is_phi(instr)) {
1046       /* re-enable killed operands */
1047       for (Operand& op : instr->operands) {
1048          if (op.isTemp() && op.isFirstKillBeforeDef())
1049             reg_file.fill(op);
1050       }
1051    }
1052
1053    std::vector<std::pair<Operand, Definition>> pc;
1054    if (!get_regs_for_copies(ctx, reg_file, pc, vars, lb, ub, instr, best_pos, best_pos + size - 1)) {
1055       reg_file = std::move(register_file);
1056       /* remove killed operands from reg_file once again */
1057       if (!is_phi(instr)) {
1058          for (const Operand& op : instr->operands) {
1059             if (op.isTemp() && op.isFirstKillBeforeDef())
1060                reg_file.clear(op);
1061          }
1062       }
1063       for (unsigned i = 0; i < instr->definitions.size(); i++) {
1064          Definition& def = instr->definitions[i];
1065          if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i))
1066             reg_file.fill(def);
1067       }
1068       return {{}, false};
1069    }
1070
1071    parallelcopies.insert(parallelcopies.end(), pc.begin(), pc.end());
1072
1073    /* we set the definition regs == 0. the actual caller is responsible for correct setting */
1074    reg_file.clear(PhysReg{best_pos}, rc);
1075
1076    update_renames(ctx, reg_file, parallelcopies, instr, instr->opcode != aco_opcode::p_create_vector);
1077
1078    /* remove killed operands from reg_file once again */
1079    for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) {
1080       if (!instr->operands[i].isTemp() || !instr->operands[i].isFixed())
1081          continue;
1082       assert(!instr->operands[i].isUndefined());
1083       if (instr->operands[i].isFirstKillBeforeDef())
1084          reg_file.clear(instr->operands[i]);
1085    }
1086    for (unsigned i = 0; i < instr->definitions.size(); i++) {
1087       Definition def = instr->definitions[i];
1088       if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i))
1089          reg_file.fill(def);
1090    }
1091
1092    adjust_max_used_regs(ctx, rc, best_pos);
1093    return {PhysReg{best_pos}, true};
1094 }
1095
1096 bool get_reg_specified(ra_ctx& ctx,
1097                        RegisterFile& reg_file,
1098                        RegClass rc,
1099                        std::vector<std::pair<Operand, Definition>>& parallelcopies,
1100                        aco_ptr<Instruction>& instr,
1101                        PhysReg reg)
1102 {
1103    std::pair<unsigned, unsigned> sdw_def_info;
1104    if (rc.is_subdword())
1105       sdw_def_info = get_subdword_definition_info(ctx.program, instr, rc);
1106
1107    if (rc.is_subdword() && reg.byte() % sdw_def_info.first)
1108       return false;
1109    if (!rc.is_subdword() && reg.byte())
1110       return false;
1111
1112    uint32_t size = rc.size();
1113    uint32_t stride = 1;
1114    uint32_t lb, ub;
1115
1116    if (rc.type() == RegType::vgpr) {
1117       lb = 256;
1118       ub = 256 + ctx.program->max_reg_demand.vgpr;
1119    } else {
1120       if (size == 2)
1121          stride = 2;
1122       else if (size >= 4)
1123          stride = 4;
1124       if (reg % stride != 0)
1125          return false;
1126       lb = 0;
1127       ub = ctx.program->max_reg_demand.sgpr;
1128    }
1129
1130    uint32_t reg_lo = reg.reg();
1131    uint32_t reg_hi = reg + (size - 1);
1132
1133    if (reg_lo < lb || reg_hi >= ub || reg_lo > reg_hi)
1134       return false;
1135
1136    if (rc.is_subdword()) {
1137       PhysReg test_reg;
1138       test_reg.reg_b = reg.reg_b & ~(sdw_def_info.second - 1);
1139       if (reg_file.test(test_reg, sdw_def_info.second))
1140          return false;
1141    } else {
1142       if (reg_file.test(reg, rc.bytes()))
1143          return false;
1144    }
1145
1146    adjust_max_used_regs(ctx, rc, reg_lo);
1147    return true;
1148 }
1149
1150 PhysReg get_reg(ra_ctx& ctx,
1151                 RegisterFile& reg_file,
1152                 Temp temp,
1153                 std::vector<std::pair<Operand, Definition>>& parallelcopies,
1154                 aco_ptr<Instruction>& instr,
1155                 int operand_index=-1)
1156 {
1157    auto split_vec = ctx.split_vectors.find(temp.id());
1158    if (split_vec != ctx.split_vectors.end()) {
1159       unsigned offset = 0;
1160       for (Definition def : split_vec->second->definitions) {
1161          auto affinity_it = ctx.affinities.find(def.tempId());
1162          if (affinity_it != ctx.affinities.end() && ctx.assignments[affinity_it->second].assigned) {
1163             PhysReg reg = ctx.assignments[affinity_it->second].reg;
1164             reg.reg_b -= offset;
1165             if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg))
1166                return reg;
1167          }
1168          offset += def.bytes();
1169       }
1170    }
1171
1172    if (ctx.affinities.find(temp.id()) != ctx.affinities.end() &&
1173        ctx.assignments[ctx.affinities[temp.id()]].assigned) {
1174       PhysReg reg = ctx.assignments[ctx.affinities[temp.id()]].reg;
1175       if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg))
1176          return reg;
1177    }
1178
1179    if (ctx.vectors.find(temp.id()) != ctx.vectors.end()) {
1180       Instruction* vec = ctx.vectors[temp.id()];
1181       unsigned byte_offset = 0;
1182       for (const Operand& op : vec->operands) {
1183          if (op.isTemp() && op.tempId() == temp.id())
1184             break;
1185          else
1186             byte_offset += op.bytes();
1187       }
1188       unsigned k = 0;
1189       for (const Operand& op : vec->operands) {
1190          if (op.isTemp() &&
1191              op.tempId() != temp.id() &&
1192              op.getTemp().type() == temp.type() &&
1193              ctx.assignments[op.tempId()].assigned) {
1194             PhysReg reg = ctx.assignments[op.tempId()].reg;
1195             reg.reg_b += (byte_offset - k);
1196             if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg))
1197                return reg;
1198          }
1199          k += op.bytes();
1200       }
1201
1202       DefInfo info(ctx, ctx.pseudo_dummy, vec->definitions[0].regClass(), -1);
1203       std::pair<PhysReg, bool> res = get_reg_simple(ctx, reg_file, info);
1204       PhysReg reg = res.first;
1205       if (res.second) {
1206          reg.reg_b += byte_offset;
1207          /* make sure to only use byte offset if the instruction supports it */
1208          if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg))
1209             return reg;
1210       }
1211    }
1212
1213    DefInfo info(ctx, instr, temp.regClass(), operand_index);
1214
1215    /* try to find space without live-range splits */
1216    std::pair<PhysReg, bool> res = get_reg_simple(ctx, reg_file, info);
1217
1218    if (res.second)
1219       return res.first;
1220
1221    /* try to find space with live-range splits */
1222    res = get_reg_impl(ctx, reg_file, parallelcopies, info, instr);
1223
1224    if (res.second)
1225       return res.first;
1226
1227    /* try using more registers */
1228
1229    /* We should only fail here because keeping under the limit would require
1230     * too many moves. */
1231    assert(reg_file.count_zero(PhysReg{info.lb}, info.ub-info.lb) >= info.size);
1232
1233    uint16_t max_addressible_sgpr = ctx.program->sgpr_limit;
1234    uint16_t max_addressible_vgpr = ctx.program->vgpr_limit;
1235    if (info.rc.type() == RegType::vgpr && ctx.program->max_reg_demand.vgpr < max_addressible_vgpr) {
1236       update_vgpr_sgpr_demand(ctx.program, RegisterDemand(ctx.program->max_reg_demand.vgpr + 1, ctx.program->max_reg_demand.sgpr));
1237       return get_reg(ctx, reg_file, temp, parallelcopies, instr, operand_index);
1238    } else if (info.rc.type() == RegType::sgpr && ctx.program->max_reg_demand.sgpr < max_addressible_sgpr) {
1239       update_vgpr_sgpr_demand(ctx.program,  RegisterDemand(ctx.program->max_reg_demand.vgpr, ctx.program->max_reg_demand.sgpr + 1));
1240       return get_reg(ctx, reg_file, temp, parallelcopies, instr, operand_index);
1241    }
1242
1243    //FIXME: if nothing helps, shift-rotate the registers to make space
1244
1245    fprintf(stderr, "ACO: failed to allocate registers during shader compilation\n");
1246    abort();
1247 }
1248
1249 PhysReg get_reg_create_vector(ra_ctx& ctx,
1250                               RegisterFile& reg_file,
1251                               Temp temp,
1252                               std::vector<std::pair<Operand, Definition>>& parallelcopies,
1253                               aco_ptr<Instruction>& instr)
1254 {
1255    RegClass rc = temp.regClass();
1256    /* create_vector instructions have different costs w.r.t. register coalescing */
1257    uint32_t size = rc.size();
1258    uint32_t bytes = rc.bytes();
1259    uint32_t stride = 1;
1260    uint32_t lb, ub;
1261    if (rc.type() == RegType::vgpr) {
1262       lb = 256;
1263       ub = 256 + ctx.program->max_reg_demand.vgpr;
1264    } else {
1265       lb = 0;
1266       ub = ctx.program->max_reg_demand.sgpr;
1267       if (size == 2)
1268          stride = 2;
1269       else if (size >= 4)
1270          stride = 4;
1271    }
1272
1273    //TODO: improve p_create_vector for sub-dword vectors
1274
1275    unsigned best_pos = -1;
1276    unsigned num_moves = 0xFF;
1277    bool best_war_hint = true;
1278
1279    /* test for each operand which definition placement causes the least shuffle instructions */
1280    for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) {
1281       // TODO: think about, if we can alias live operands on the same register
1282       if (!instr->operands[i].isTemp() || !instr->operands[i].isKillBeforeDef() || instr->operands[i].getTemp().type() != rc.type())
1283          continue;
1284
1285       if (offset > instr->operands[i].physReg().reg_b)
1286          continue;
1287
1288       unsigned reg_lo = instr->operands[i].physReg().reg_b - offset;
1289       if (reg_lo % 4)
1290          continue;
1291       reg_lo /= 4;
1292       unsigned reg_hi = reg_lo + size - 1;
1293       unsigned k = 0;
1294
1295       /* no need to check multiple times */
1296       if (reg_lo == best_pos)
1297          continue;
1298
1299       /* check borders */
1300       // TODO: this can be improved */
1301       if (reg_lo < lb || reg_hi >= ub || reg_lo % stride != 0)
1302          continue;
1303       if (reg_lo > lb && reg_file[reg_lo] != 0 && reg_file[reg_lo] == reg_file[reg_lo - 1])
1304          continue;
1305       if (reg_hi < ub - 1 && reg_file[reg_hi] != 0 && reg_file[reg_hi] == reg_file[reg_hi + 1])
1306          continue;
1307
1308       /* count variables to be moved and check war_hint */
1309       bool war_hint = false;
1310       bool linear_vgpr = false;
1311       for (unsigned j = reg_lo; j <= reg_hi && !linear_vgpr; j++) {
1312          if (reg_file[j] != 0) {
1313             if (reg_file[j] == 0xF0000000) {
1314                PhysReg reg;
1315                reg.reg_b = j * 4;
1316                unsigned bytes_left = bytes - (j - reg_lo) * 4;
1317                for (unsigned k = 0; k < MIN2(bytes_left, 4); k++, reg.reg_b++)
1318                   k += reg_file.test(reg, 1);
1319             } else {
1320                k += 4;
1321                /* we cannot split live ranges of linear vgprs */
1322                if (ctx.assignments[reg_file[j]].rc & (1 << 6))
1323                   linear_vgpr = true;
1324             }
1325          }
1326          war_hint |= ctx.war_hint[j];
1327       }
1328       if (linear_vgpr || (war_hint && !best_war_hint))
1329          continue;
1330
1331       /* count operands in wrong positions */
1332       for (unsigned j = 0, offset = 0; j < instr->operands.size(); offset += instr->operands[j].bytes(), j++) {
1333          if (j == i ||
1334              !instr->operands[j].isTemp() ||
1335              instr->operands[j].getTemp().type() != rc.type())
1336             continue;
1337          if (instr->operands[j].physReg().reg_b != reg_lo * 4 + offset)
1338             k += instr->operands[j].bytes();
1339       }
1340       bool aligned = rc == RegClass::v4 && reg_lo % 4 == 0;
1341       if (k > num_moves || (!aligned && k == num_moves))
1342          continue;
1343
1344       best_pos = reg_lo;
1345       num_moves = k;
1346       best_war_hint = war_hint;
1347    }
1348
1349    if (num_moves >= bytes)
1350       return get_reg(ctx, reg_file, temp, parallelcopies, instr);
1351
1352    /* re-enable killed operands which are in the wrong position */
1353    for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) {
1354       if (instr->operands[i].isTemp() &&
1355           instr->operands[i].isFirstKillBeforeDef() &&
1356           instr->operands[i].physReg().reg_b != best_pos * 4 + offset)
1357          reg_file.fill(instr->operands[i]);
1358    }
1359
1360    /* collect variables to be moved */
1361    std::set<std::pair<unsigned, unsigned>> vars = collect_vars(ctx, reg_file, PhysReg{best_pos}, size);
1362
1363    /* GFX9+: move killed operands which aren't yet at the correct position
1364     * Moving all killed operands generally leads to more register swaps.
1365     * This is only done on GFX9+ because of the cheap v_swap instruction.
1366     */
1367    if (ctx.program->chip_class >= GFX9) {
1368       for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) {
1369          if (instr->operands[i].isTemp() &&
1370              instr->operands[i].isFirstKillBeforeDef() &&
1371              instr->operands[i].getTemp().type() == rc.type() &&
1372              instr->operands[i].physReg().reg_b != best_pos * 4 + offset) {
1373             vars.emplace(instr->operands[i].bytes(), instr->operands[i].tempId());
1374             reg_file.clear(instr->operands[i]);
1375          }
1376       }
1377    }
1378    ASSERTED bool success = false;
1379    success = get_regs_for_copies(ctx, reg_file, parallelcopies, vars, lb, ub, instr, best_pos, best_pos + size - 1);
1380    assert(success);
1381
1382    update_renames(ctx, reg_file, parallelcopies, instr, false);
1383    adjust_max_used_regs(ctx, rc, best_pos);
1384
1385    /* remove killed operands from reg_file once again */
1386    for (unsigned i = 0; i < instr->operands.size(); i++) {
1387       if (!instr->operands[i].isTemp() || !instr->operands[i].isFixed())
1388          continue;
1389       assert(!instr->operands[i].isUndefined());
1390       if (instr->operands[i].isFirstKillBeforeDef())
1391          reg_file.clear(instr->operands[i]);
1392    }
1393
1394    return PhysReg{best_pos};
1395 }
1396
1397 void handle_pseudo(ra_ctx& ctx,
1398                    const RegisterFile& reg_file,
1399                    Instruction* instr)
1400 {
1401    if (instr->format != Format::PSEUDO)
1402       return;
1403
1404    /* all instructions which use handle_operands() need this information */
1405    switch (instr->opcode) {
1406    case aco_opcode::p_extract_vector:
1407    case aco_opcode::p_create_vector:
1408    case aco_opcode::p_split_vector:
1409    case aco_opcode::p_parallelcopy:
1410    case aco_opcode::p_wqm:
1411       break;
1412    default:
1413       return;
1414    }
1415
1416    /* if all definitions are vgpr, no need to care for SCC */
1417    bool writes_sgpr = false;
1418    for (Definition& def : instr->definitions) {
1419       if (def.getTemp().type() == RegType::sgpr) {
1420          writes_sgpr = true;
1421          break;
1422       }
1423    }
1424    /* if all operands are constant, no need to care either */
1425    bool reads_sgpr = false;
1426    bool reads_subdword = false;
1427    for (Operand& op : instr->operands) {
1428       if (op.isTemp() && op.getTemp().type() == RegType::sgpr) {
1429          reads_sgpr = true;
1430          break;
1431       }
1432       if (op.isTemp() && op.regClass().is_subdword())
1433          reads_subdword = true;
1434    }
1435    bool needs_scratch_reg = (writes_sgpr && reads_sgpr) ||
1436                             (ctx.program->chip_class <= GFX7 && reads_subdword);
1437    if (!needs_scratch_reg)
1438       return;
1439
1440    Pseudo_instruction *pi = (Pseudo_instruction *)instr;
1441    if (reg_file[scc.reg()]) {
1442       pi->tmp_in_scc = true;
1443
1444       int reg = ctx.max_used_sgpr;
1445       for (; reg >= 0 && reg_file[reg]; reg--)
1446          ;
1447       if (reg < 0) {
1448          reg = ctx.max_used_sgpr + 1;
1449          for (; reg < ctx.program->max_reg_demand.sgpr && reg_file[reg]; reg++)
1450             ;
1451          if (reg == ctx.program->max_reg_demand.sgpr) {
1452             assert(reads_subdword && reg_file[m0] == 0);
1453             reg = m0;
1454          }
1455       }
1456
1457       adjust_max_used_regs(ctx, s1, reg);
1458       pi->scratch_sgpr = PhysReg{(unsigned)reg};
1459    } else {
1460       pi->tmp_in_scc = false;
1461    }
1462 }
1463
1464 bool operand_can_use_reg(chip_class chip, aco_ptr<Instruction>& instr, unsigned idx, PhysReg reg, RegClass rc)
1465 {
1466    if (instr->operands[idx].isFixed())
1467       return instr->operands[idx].physReg() == reg;
1468
1469    if (reg.byte()) {
1470       unsigned stride = get_subdword_operand_stride(chip, instr, idx, rc);
1471       if (reg.byte() % stride)
1472          return false;
1473    }
1474
1475    switch (instr->format) {
1476    case Format::SMEM:
1477       return reg != scc &&
1478              reg != exec &&
1479              (reg != m0 || idx == 1 || idx == 3) && /* offset can be m0 */
1480              (reg != vcc || (instr->definitions.empty() && idx == 2)); /* sdata can be vcc */
1481    default:
1482       // TODO: there are more instructions with restrictions on registers
1483       return true;
1484    }
1485 }
1486
1487 void get_reg_for_operand(ra_ctx& ctx, RegisterFile& register_file,
1488                          std::vector<std::pair<Operand, Definition>>& parallelcopy,
1489                          aco_ptr<Instruction>& instr, Operand& operand, unsigned operand_index)
1490 {
1491    /* check if the operand is fixed */
1492    PhysReg dst;
1493    if (operand.isFixed()) {
1494       assert(operand.physReg() != ctx.assignments[operand.tempId()].reg);
1495
1496       /* check if target reg is blocked, and move away the blocking var */
1497       if (register_file[operand.physReg().reg()]) {
1498          assert(register_file[operand.physReg()] != 0xF0000000);
1499          uint32_t blocking_id = register_file[operand.physReg().reg()];
1500          RegClass rc = ctx.assignments[blocking_id].rc;
1501          Operand pc_op = Operand(Temp{blocking_id, rc});
1502          pc_op.setFixed(operand.physReg());
1503
1504          /* find free reg */
1505          PhysReg reg = get_reg(ctx, register_file, pc_op.getTemp(), parallelcopy, ctx.pseudo_dummy);
1506          Definition pc_def = Definition(PhysReg{reg}, pc_op.regClass());
1507          register_file.clear(pc_op);
1508          parallelcopy.emplace_back(pc_op, pc_def);
1509       }
1510       dst = operand.physReg();
1511
1512    } else {
1513       dst = get_reg(ctx, register_file, operand.getTemp(), parallelcopy, instr, operand_index);
1514    }
1515
1516    Operand pc_op = operand;
1517    pc_op.setFixed(ctx.assignments[operand.tempId()].reg);
1518    Definition pc_def = Definition(dst, pc_op.regClass());
1519    register_file.clear(pc_op);
1520    parallelcopy.emplace_back(pc_op, pc_def);
1521    update_renames(ctx, register_file, parallelcopy, instr, true);
1522 }
1523
1524 Temp read_variable(ra_ctx& ctx, Temp val, unsigned block_idx)
1525 {
1526    std::unordered_map<unsigned, Temp>::iterator it = ctx.renames[block_idx].find(val.id());
1527    if (it == ctx.renames[block_idx].end())
1528       return val;
1529    else
1530       return it->second;
1531 }
1532
1533 Temp handle_live_in(ra_ctx& ctx, Temp val, Block* block)
1534 {
1535    std::vector<unsigned>& preds = val.is_linear() ? block->linear_preds : block->logical_preds;
1536    if (preds.size() == 0 || val.regClass() == val.regClass().as_linear())
1537       return val;
1538
1539    assert(preds.size() > 0);
1540
1541    Temp new_val;
1542    if (!ctx.sealed[block->index]) {
1543       /* consider rename from already processed predecessor */
1544       Temp tmp = read_variable(ctx, val, preds[0]);
1545
1546       /* if the block is not sealed yet, we create an incomplete phi (which might later get removed again) */
1547       new_val = Temp{ctx.program->allocateId(), val.regClass()};
1548       ctx.assignments.emplace_back();
1549       aco_opcode opcode = val.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi;
1550       aco_ptr<Instruction> phi{create_instruction<Pseudo_instruction>(opcode, Format::PSEUDO, preds.size(), 1)};
1551       phi->definitions[0] = Definition(new_val);
1552       for (unsigned i = 0; i < preds.size(); i++)
1553          phi->operands[i] = Operand(val);
1554       if (tmp.regClass() == new_val.regClass())
1555          ctx.affinities[new_val.id()] = tmp.id();
1556
1557       ctx.phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index});
1558       ctx.incomplete_phis[block->index].emplace_back(phi.get());
1559       block->instructions.insert(block->instructions.begin(), std::move(phi));
1560
1561    } else if (preds.size() == 1) {
1562       /* if the block has only one predecessor, just look there for the name */
1563       new_val = read_variable(ctx, val, preds[0]);
1564    } else {
1565       /* there are multiple predecessors and the block is sealed */
1566       Temp ops[preds.size()];
1567
1568       /* get the rename from each predecessor and check if they are the same */
1569       bool needs_phi = false;
1570       for (unsigned i = 0; i < preds.size(); i++) {
1571          ops[i] = read_variable(ctx, val, preds[i]);
1572          if (i == 0)
1573             new_val = ops[i];
1574          else
1575             needs_phi |= !(new_val == ops[i]);
1576       }
1577
1578       if (needs_phi) {
1579          /* the variable has been renamed differently in the predecessors: we need to insert a phi */
1580          aco_opcode opcode = val.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi;
1581          aco_ptr<Instruction> phi{create_instruction<Pseudo_instruction>(opcode, Format::PSEUDO, preds.size(), 1)};
1582          new_val = Temp{ctx.program->allocateId(), val.regClass()};
1583          phi->definitions[0] = Definition(new_val);
1584          for (unsigned i = 0; i < preds.size(); i++) {
1585             phi->operands[i] = Operand(ops[i]);
1586             phi->operands[i].setFixed(ctx.assignments[ops[i].id()].reg);
1587             if (ops[i].regClass() == new_val.regClass())
1588                ctx.affinities[new_val.id()] = ops[i].id();
1589          }
1590          ctx.assignments.emplace_back();
1591          assert(ctx.assignments.size() == ctx.program->peekAllocationId());
1592          ctx.phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index});
1593          block->instructions.insert(block->instructions.begin(), std::move(phi));
1594       }
1595    }
1596
1597    if (new_val != val) {
1598       ctx.renames[block->index][val.id()] = new_val;
1599       ctx.orig_names[new_val.id()] = val;
1600    }
1601    return new_val;
1602 }
1603
1604 void try_remove_trivial_phi(ra_ctx& ctx, Temp temp)
1605 {
1606    std::unordered_map<unsigned, phi_info>::iterator info = ctx.phi_map.find(temp.id());
1607
1608    if (info == ctx.phi_map.end() || !ctx.sealed[info->second.block_idx])
1609       return;
1610
1611    assert(info->second.block_idx != 0);
1612    Instruction* phi = info->second.phi;
1613    Temp same = Temp();
1614    Definition def = phi->definitions[0];
1615
1616    /* a phi node is trivial if all operands are the same as the definition of the phi */
1617    for (const Operand& op : phi->operands) {
1618       const Temp t = op.getTemp();
1619       if (t == same || t == def.getTemp()) {
1620          assert(t == same || op.physReg() == def.physReg());
1621          continue;
1622       }
1623       if (same != Temp())
1624          return;
1625
1626       same = t;
1627    }
1628    assert(same != Temp() || same == def.getTemp());
1629
1630    /* reroute all uses to same and remove phi */
1631    std::vector<Temp> phi_users;
1632    std::unordered_map<unsigned, phi_info>::iterator same_phi_info = ctx.phi_map.find(same.id());
1633    for (Instruction* instr : info->second.uses) {
1634       assert(phi != instr);
1635       /* recursively try to remove trivial phis */
1636       if (is_phi(instr)) {
1637          /* ignore if the phi was already flagged trivial */
1638          if (instr->definitions.empty())
1639             continue;
1640
1641          if (instr->definitions[0].getTemp() != temp)
1642             phi_users.emplace_back(instr->definitions[0].getTemp());
1643       }
1644       for (Operand& op : instr->operands) {
1645          if (op.isTemp() && op.tempId() == def.tempId()) {
1646             op.setTemp(same);
1647             if (same_phi_info != ctx.phi_map.end())
1648                same_phi_info->second.uses.emplace(instr);
1649          }
1650       }
1651    }
1652
1653    auto it = ctx.orig_names.find(same.id());
1654    unsigned orig_var = it != ctx.orig_names.end() ? it->second.id() : same.id();
1655    for (unsigned i = 0; i < ctx.program->blocks.size(); i++) {
1656       auto it = ctx.renames[i].find(orig_var);
1657       if (it != ctx.renames[i].end() && it->second == def.getTemp())
1658          ctx.renames[i][orig_var] = same;
1659    }
1660
1661    phi->definitions.clear(); /* this indicates that the phi can be removed */
1662    ctx.phi_map.erase(info);
1663    for (Temp t : phi_users)
1664       try_remove_trivial_phi(ctx, t);
1665
1666    return;
1667 }
1668
1669 } /* end namespace */
1670
1671
1672 void register_allocation(Program *program, std::vector<TempSet>& live_out_per_block)
1673 {
1674    ra_ctx ctx(program);
1675    std::vector<std::vector<Temp>> phi_ressources;
1676    std::unordered_map<unsigned, unsigned> temp_to_phi_ressources;
1677
1678    for (std::vector<Block>::reverse_iterator it = program->blocks.rbegin(); it != program->blocks.rend(); it++) {
1679       Block& block = *it;
1680
1681       /* first, compute the death points of all live vars within the block */
1682       TempSet& live = live_out_per_block[block.index];
1683
1684       std::vector<aco_ptr<Instruction>>::reverse_iterator rit;
1685       for (rit = block.instructions.rbegin(); rit != block.instructions.rend(); ++rit) {
1686          aco_ptr<Instruction>& instr = *rit;
1687          if (is_phi(instr)) {
1688             if (instr->definitions[0].isKill() || instr->definitions[0].isFixed()) {
1689                live.erase(instr->definitions[0].getTemp());
1690                continue;
1691             }
1692             /* collect information about affinity-related temporaries */
1693             std::vector<Temp> affinity_related;
1694             /* affinity_related[0] is the last seen affinity-related temp */
1695             affinity_related.emplace_back(instr->definitions[0].getTemp());
1696             affinity_related.emplace_back(instr->definitions[0].getTemp());
1697             for (const Operand& op : instr->operands) {
1698                if (op.isTemp() && op.regClass() == instr->definitions[0].regClass()) {
1699                   affinity_related.emplace_back(op.getTemp());
1700                   temp_to_phi_ressources[op.tempId()] = phi_ressources.size();
1701                }
1702             }
1703             phi_ressources.emplace_back(std::move(affinity_related));
1704          } else {
1705             /* add vector affinities */
1706             if (instr->opcode == aco_opcode::p_create_vector) {
1707                for (const Operand& op : instr->operands) {
1708                   if (op.isTemp() && op.isFirstKill() && op.getTemp().type() == instr->definitions[0].getTemp().type())
1709                      ctx.vectors[op.tempId()] = instr.get();
1710                }
1711             }
1712
1713             if (instr->opcode == aco_opcode::p_split_vector && instr->operands[0].isFirstKillBeforeDef())
1714                ctx.split_vectors[instr->operands[0].tempId()] = instr.get();
1715
1716             /* add operands to live variables */
1717             for (const Operand& op : instr->operands) {
1718                if (op.isTemp())
1719                   live.emplace(op.getTemp());
1720             }
1721          }
1722
1723          /* erase definitions from live */
1724          for (unsigned i = 0; i < instr->definitions.size(); i++) {
1725             const Definition& def = instr->definitions[i];
1726             if (!def.isTemp())
1727                continue;
1728             live.erase(def.getTemp());
1729             /* mark last-seen phi operand */
1730             std::unordered_map<unsigned, unsigned>::iterator it = temp_to_phi_ressources.find(def.tempId());
1731             if (it != temp_to_phi_ressources.end() && def.regClass() == phi_ressources[it->second][0].regClass()) {
1732                phi_ressources[it->second][0] = def.getTemp();
1733                /* try to coalesce phi affinities with parallelcopies */
1734                Operand op = Operand();
1735                if (!def.isFixed() && instr->opcode == aco_opcode::p_parallelcopy)
1736                   op = instr->operands[i];
1737                else if ((instr->opcode == aco_opcode::v_mad_f32 ||
1738                         (instr->opcode == aco_opcode::v_fma_f32 && program->chip_class >= GFX10)) && !instr->usesModifiers())
1739                   op = instr->operands[2];
1740
1741                if (op.isTemp() && op.isFirstKillBeforeDef() && def.regClass() == op.regClass()) {
1742                   phi_ressources[it->second].emplace_back(op.getTemp());
1743                   temp_to_phi_ressources[op.tempId()] = it->second;
1744                }
1745             }
1746          }
1747       }
1748    }
1749    /* create affinities */
1750    for (std::vector<Temp>& vec : phi_ressources) {
1751       assert(vec.size() > 1);
1752       for (unsigned i = 1; i < vec.size(); i++)
1753          if (vec[i].id() != vec[0].id())
1754             ctx.affinities[vec[i].id()] = vec[0].id();
1755    }
1756
1757    /* state of register file after phis */
1758    std::vector<std::bitset<128>> sgpr_live_in(program->blocks.size());
1759
1760    for (Block& block : program->blocks) {
1761       TempSet& live = live_out_per_block[block.index];
1762       /* initialize register file */
1763       assert(block.index != 0 || live.empty());
1764       RegisterFile register_file;
1765       ctx.war_hint.reset();
1766
1767       for (Temp t : live) {
1768          Temp renamed = handle_live_in(ctx, t, &block);
1769          assignment& var = ctx.assignments[renamed.id()];
1770          /* due to live-range splits, the live-in might be a phi, now */
1771          if (var.assigned)
1772             register_file.fill(Definition(renamed.id(), var.reg, var.rc));
1773       }
1774
1775       std::vector<aco_ptr<Instruction>> instructions;
1776       std::vector<aco_ptr<Instruction>>::iterator it;
1777
1778       /* this is a slight adjustment from the paper as we already have phi nodes:
1779        * We consider them incomplete phis and only handle the definition. */
1780
1781       /* handle fixed phi definitions */
1782       for (it = block.instructions.begin(); it != block.instructions.end(); ++it) {
1783          aco_ptr<Instruction>& phi = *it;
1784          if (!is_phi(phi))
1785             break;
1786          Definition& definition = phi->definitions[0];
1787          if (!definition.isFixed())
1788             continue;
1789
1790          /* check if a dead exec mask phi is needed */
1791          if (definition.isKill()) {
1792             for (Operand& op : phi->operands) {
1793                assert(op.isTemp());
1794                if (!ctx.assignments[op.tempId()].assigned ||
1795                    ctx.assignments[op.tempId()].reg != exec) {
1796                    definition.setKill(false);
1797                    break;
1798                }
1799             }
1800          }
1801
1802          if (definition.isKill())
1803             continue;
1804
1805          assert(definition.physReg() == exec);
1806          assert(!register_file.test(definition.physReg(), definition.bytes()));
1807          register_file.fill(definition);
1808          ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()};
1809       }
1810
1811       /* look up the affinities */
1812       for (it = block.instructions.begin(); it != block.instructions.end(); ++it) {
1813          aco_ptr<Instruction>& phi = *it;
1814          if (!is_phi(phi))
1815             break;
1816          Definition& definition = phi->definitions[0];
1817          if (definition.isKill() || definition.isFixed())
1818              continue;
1819
1820          if (ctx.affinities.find(definition.tempId()) != ctx.affinities.end() &&
1821              ctx.assignments[ctx.affinities[definition.tempId()]].assigned) {
1822             assert(ctx.assignments[ctx.affinities[definition.tempId()]].rc == definition.regClass());
1823             PhysReg reg = ctx.assignments[ctx.affinities[definition.tempId()]].reg;
1824             bool try_use_special_reg = reg == scc || reg == exec;
1825             if (try_use_special_reg) {
1826                for (const Operand& op : phi->operands) {
1827                   if (!(op.isTemp() && ctx.assignments[op.tempId()].assigned &&
1828                         ctx.assignments[op.tempId()].reg == reg)) {
1829                      try_use_special_reg = false;
1830                      break;
1831                   }
1832                }
1833                if (!try_use_special_reg)
1834                   continue;
1835             }
1836             /* only assign if register is still free */
1837             if (!register_file.test(reg, definition.bytes())) {
1838                definition.setFixed(reg);
1839                register_file.fill(definition);
1840                ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()};
1841             }
1842          }
1843       }
1844
1845       /* find registers for phis without affinity or where the register was blocked */
1846       for (it = block.instructions.begin();it != block.instructions.end(); ++it) {
1847          aco_ptr<Instruction>& phi = *it;
1848          if (!is_phi(phi))
1849             break;
1850
1851          Definition& definition = phi->definitions[0];
1852          if (definition.isKill())
1853             continue;
1854
1855          if (!definition.isFixed()) {
1856             std::vector<std::pair<Operand, Definition>> parallelcopy;
1857             /* try to find a register that is used by at least one operand */
1858             for (const Operand& op : phi->operands) {
1859                if (!(op.isTemp() && ctx.assignments[op.tempId()].assigned))
1860                   continue;
1861                PhysReg reg = ctx.assignments[op.tempId()].reg;
1862                /* we tried this already on the previous loop */
1863                if (reg == scc || reg == exec)
1864                   continue;
1865                if (get_reg_specified(ctx, register_file, definition.regClass(), parallelcopy, phi, reg)) {
1866                   definition.setFixed(reg);
1867                   break;
1868                }
1869             }
1870             if (!definition.isFixed())
1871                definition.setFixed(get_reg(ctx, register_file, definition.getTemp(), parallelcopy, phi));
1872
1873             /* process parallelcopy */
1874             for (std::pair<Operand, Definition> pc : parallelcopy) {
1875                /* see if it's a copy from a different phi */
1876                //TODO: prefer moving some previous phis over live-ins
1877                //TODO: somehow prevent phis fixed before the RA from being updated (shouldn't be a problem in practice since they can only be fixed to exec)
1878                Instruction *prev_phi = NULL;
1879                std::vector<aco_ptr<Instruction>>::iterator phi_it;
1880                for (phi_it = instructions.begin(); phi_it != instructions.end(); ++phi_it) {
1881                   if ((*phi_it)->definitions[0].tempId() == pc.first.tempId())
1882                      prev_phi = phi_it->get();
1883                }
1884                phi_it = it;
1885                while (!prev_phi && is_phi(*++phi_it)) {
1886                   if ((*phi_it)->definitions[0].tempId() == pc.first.tempId())
1887                      prev_phi = phi_it->get();
1888                }
1889                if (prev_phi) {
1890                   /* if so, just update that phi's register */
1891                   register_file.clear(prev_phi->definitions[0]);
1892                   prev_phi->definitions[0].setFixed(pc.second.physReg());
1893                   ctx.assignments[prev_phi->definitions[0].tempId()] = {pc.second.physReg(), pc.second.regClass()};
1894                   register_file.fill(prev_phi->definitions[0]);
1895                   continue;
1896                }
1897
1898                /* rename */
1899                std::unordered_map<unsigned, Temp>::iterator orig_it = ctx.orig_names.find(pc.first.tempId());
1900                Temp orig = pc.first.getTemp();
1901                if (orig_it != ctx.orig_names.end())
1902                   orig = orig_it->second;
1903                else
1904                   ctx.orig_names[pc.second.tempId()] = orig;
1905                ctx.renames[block.index][orig.id()] = pc.second.getTemp();
1906
1907                /* otherwise, this is a live-in and we need to create a new phi
1908                 * to move it in this block's predecessors */
1909                aco_opcode opcode = pc.first.getTemp().is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi;
1910                std::vector<unsigned>& preds = pc.first.getTemp().is_linear() ? block.linear_preds : block.logical_preds;
1911                aco_ptr<Instruction> new_phi{create_instruction<Pseudo_instruction>(opcode, Format::PSEUDO, preds.size(), 1)};
1912                new_phi->definitions[0] = pc.second;
1913                for (unsigned i = 0; i < preds.size(); i++)
1914                   new_phi->operands[i] = Operand(pc.first);
1915                instructions.emplace_back(std::move(new_phi));
1916             }
1917
1918             register_file.fill(definition);
1919             ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()};
1920          }
1921          live.emplace(definition.getTemp());
1922
1923          /* update phi affinities */
1924          for (const Operand& op : phi->operands) {
1925             if (op.isTemp() && op.regClass() == phi->definitions[0].regClass())
1926                ctx.affinities[op.tempId()] = definition.tempId();
1927          }
1928
1929          instructions.emplace_back(std::move(*it));
1930       }
1931
1932       /* fill in sgpr_live_in */
1933       for (unsigned i = 0; i <= ctx.max_used_sgpr; i++)
1934          sgpr_live_in[block.index][i] = register_file[i];
1935       sgpr_live_in[block.index][127] = register_file[scc.reg()];
1936
1937       /* Handle all other instructions of the block */
1938       for (; it != block.instructions.end(); ++it) {
1939          aco_ptr<Instruction>& instr = *it;
1940
1941          /* parallelcopies from p_phi are inserted here which means
1942           * live ranges of killed operands end here as well */
1943          if (instr->opcode == aco_opcode::p_logical_end) {
1944             /* no need to process this instruction any further */
1945             if (block.logical_succs.size() != 1) {
1946                instructions.emplace_back(std::move(instr));
1947                continue;
1948             }
1949
1950             Block& succ = program->blocks[block.logical_succs[0]];
1951             unsigned idx = 0;
1952             for (; idx < succ.logical_preds.size(); idx++) {
1953                if (succ.logical_preds[idx] == block.index)
1954                   break;
1955             }
1956             for (aco_ptr<Instruction>& phi : succ.instructions) {
1957                if (phi->opcode == aco_opcode::p_phi) {
1958                   if (phi->operands[idx].isTemp() &&
1959                       phi->operands[idx].getTemp().type() == RegType::sgpr &&
1960                       phi->operands[idx].isFirstKillBeforeDef()) {
1961                      Temp phi_op = read_variable(ctx, phi->operands[idx].getTemp(), block.index);
1962                      PhysReg reg = ctx.assignments[phi_op.id()].reg;
1963                      assert(register_file[reg] == phi_op.id());
1964                      register_file[reg] = 0;
1965                   }
1966                } else if (phi->opcode != aco_opcode::p_linear_phi) {
1967                   break;
1968                }
1969             }
1970             instructions.emplace_back(std::move(instr));
1971             continue;
1972          }
1973
1974          std::vector<std::pair<Operand, Definition>> parallelcopy;
1975
1976          assert(!is_phi(instr));
1977
1978          /* handle operands */
1979          for (unsigned i = 0; i < instr->operands.size(); ++i) {
1980             auto& operand = instr->operands[i];
1981             if (!operand.isTemp())
1982                continue;
1983
1984             /* rename operands */
1985             operand.setTemp(read_variable(ctx, operand.getTemp(), block.index));
1986             assert(ctx.assignments[operand.tempId()].assigned);
1987
1988             PhysReg reg = ctx.assignments[operand.tempId()].reg;
1989             if (operand_can_use_reg(program->chip_class, instr, i, reg, operand.regClass()))
1990                operand.setFixed(reg);
1991             else
1992                get_reg_for_operand(ctx, register_file, parallelcopy, instr, operand, i);
1993
1994             if (instr->format == Format::EXP ||
1995                 (instr->isVMEM() && i == 3 && ctx.program->chip_class == GFX6) ||
1996                 (instr->format == Format::DS && static_cast<DS_instruction*>(instr.get())->gds)) {
1997                for (unsigned j = 0; j < operand.size(); j++)
1998                   ctx.war_hint.set(operand.physReg().reg() + j);
1999             }
2000
2001             std::unordered_map<unsigned, phi_info>::iterator phi = ctx.phi_map.find(operand.getTemp().id());
2002             if (phi != ctx.phi_map.end())
2003                phi->second.uses.emplace(instr.get());
2004          }
2005
2006          /* remove dead vars from register file */
2007          for (const Operand& op : instr->operands) {
2008             if (op.isTemp() && op.isFirstKillBeforeDef())
2009                register_file.clear(op);
2010          }
2011
2012          /* try to optimize v_mad_f32 -> v_mac_f32 */
2013          if ((instr->opcode == aco_opcode::v_mad_f32 ||
2014               (instr->opcode == aco_opcode::v_fma_f32 && program->chip_class >= GFX10)) &&
2015              instr->operands[2].isTemp() &&
2016              instr->operands[2].isKillBeforeDef() &&
2017              instr->operands[2].getTemp().type() == RegType::vgpr &&
2018              instr->operands[1].isTemp() &&
2019              instr->operands[1].getTemp().type() == RegType::vgpr &&
2020              !instr->usesModifiers()) {
2021             unsigned def_id = instr->definitions[0].tempId();
2022             auto it = ctx.affinities.find(def_id);
2023             if (it == ctx.affinities.end() || !ctx.assignments[it->second].assigned ||
2024                 instr->operands[2].physReg() == ctx.assignments[it->second].reg ||
2025                 register_file.test(ctx.assignments[it->second].reg, instr->operands[2].bytes())) {
2026                instr->format = Format::VOP2;
2027                switch (instr->opcode) {
2028                case aco_opcode::v_mad_f32:
2029                   instr->opcode = aco_opcode::v_mac_f32;
2030                   break;
2031                case aco_opcode::v_fma_f32:
2032                   instr->opcode = aco_opcode::v_fmac_f32;
2033                   break;
2034                default:
2035                   break;
2036                }
2037             }
2038          }
2039
2040          /* handle definitions which must have the same register as an operand */
2041          if (instr->opcode == aco_opcode::v_interp_p2_f32 ||
2042              instr->opcode == aco_opcode::v_mac_f32 ||
2043              instr->opcode == aco_opcode::v_fmac_f32 ||
2044              instr->opcode == aco_opcode::v_writelane_b32 ||
2045              instr->opcode == aco_opcode::v_writelane_b32_e64) {
2046             instr->definitions[0].setFixed(instr->operands[2].physReg());
2047          } else if (instr->opcode == aco_opcode::s_addk_i32 ||
2048                     instr->opcode == aco_opcode::s_mulk_i32) {
2049             instr->definitions[0].setFixed(instr->operands[0].physReg());
2050          } else if (instr->format == Format::MUBUF &&
2051                     instr->definitions.size() == 1 &&
2052                     instr->operands.size() == 4) {
2053             instr->definitions[0].setFixed(instr->operands[3].physReg());
2054          } else if (instr->format == Format::MIMG &&
2055                     instr->definitions.size() == 1 &&
2056                     instr->operands[1].regClass().type() == RegType::vgpr) {
2057             instr->definitions[0].setFixed(instr->operands[1].physReg());
2058          }
2059
2060          ctx.defs_done.reset();
2061
2062          /* handle fixed definitions first */
2063          for (unsigned i = 0; i < instr->definitions.size(); ++i) {
2064             auto& definition = instr->definitions[i];
2065             if (!definition.isFixed())
2066                continue;
2067
2068             adjust_max_used_regs(ctx, definition.regClass(), definition.physReg());
2069             /* check if the target register is blocked */
2070             if (register_file[definition.physReg().reg()] != 0) {
2071                /* create parallelcopy pair to move blocking vars */
2072                std::set<std::pair<unsigned, unsigned>> vars = collect_vars(ctx, register_file, definition.physReg(), definition.size());
2073
2074                /* re-enable the killed operands, so that we don't move the blocking vars there */
2075                for (const Operand& op : instr->operands) {
2076                   if (op.isTemp() && op.isFirstKillBeforeDef())
2077                      register_file.fill(op);
2078                }
2079
2080                ASSERTED bool success = false;
2081                DefInfo info(ctx, instr, definition.regClass(), -1);
2082                success = get_regs_for_copies(ctx, register_file, parallelcopy,
2083                                              vars, info.lb, info.ub, instr,
2084                                              definition.physReg(),
2085                                              definition.physReg() + definition.size() - 1);
2086                assert(success);
2087
2088                update_renames(ctx, register_file, parallelcopy, instr, false);
2089
2090                /* once again, disable killed operands */
2091                for (const Operand& op : instr->operands) {
2092                   if (op.isTemp() && op.isFirstKillBeforeDef())
2093                      register_file.clear(op);
2094                }
2095                for (unsigned k = 0; k < i; k++) {
2096                   if (instr->definitions[k].isTemp() && ctx.defs_done.test(k) && !instr->definitions[k].isKill())
2097                      register_file.fill(instr->definitions[k]);
2098                }
2099             }
2100             ctx.defs_done.set(i);
2101
2102             if (!definition.isTemp())
2103                continue;
2104
2105             /* set live if it has a kill point */
2106             if (!definition.isKill())
2107                live.emplace(definition.getTemp());
2108
2109             ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()};
2110             register_file.fill(definition);
2111          }
2112
2113          /* handle all other definitions */
2114          for (unsigned i = 0; i < instr->definitions.size(); ++i) {
2115             Definition *definition = &instr->definitions[i];
2116
2117             if (definition->isFixed() || !definition->isTemp())
2118                continue;
2119
2120             /* find free reg */
2121             if (definition->hasHint() && register_file[definition->physReg().reg()] == 0)
2122                definition->setFixed(definition->physReg());
2123             else if (instr->opcode == aco_opcode::p_split_vector) {
2124                PhysReg reg = instr->operands[0].physReg();
2125                for (unsigned j = 0; j < i; j++)
2126                   reg.reg_b += instr->definitions[j].bytes();
2127                if (get_reg_specified(ctx, register_file, definition->regClass(), parallelcopy, instr, reg))
2128                   definition->setFixed(reg);
2129             } else if (instr->opcode == aco_opcode::p_wqm || instr->opcode == aco_opcode::p_parallelcopy) {
2130                PhysReg reg = instr->operands[i].physReg();
2131                if (instr->operands[i].isTemp() &&
2132                    instr->operands[i].getTemp().type() == definition->getTemp().type() &&
2133                    !register_file.test(reg, definition->bytes()))
2134                   definition->setFixed(reg);
2135             } else if (instr->opcode == aco_opcode::p_extract_vector) {
2136                PhysReg reg;
2137                if (instr->operands[0].isKillBeforeDef() &&
2138                    instr->operands[0].getTemp().type() == definition->getTemp().type()) {
2139                   reg = instr->operands[0].physReg();
2140                   reg.reg_b += definition->bytes() * instr->operands[1].constantValue();
2141                   assert(!register_file.test(reg, definition->bytes()));
2142                   definition->setFixed(reg);
2143                }
2144             } else if (instr->opcode == aco_opcode::p_create_vector) {
2145                PhysReg reg = get_reg_create_vector(ctx, register_file, definition->getTemp(),
2146                                                    parallelcopy, instr);
2147                definition->setFixed(reg);
2148             }
2149
2150             if (!definition->isFixed()) {
2151                Temp tmp = definition->getTemp();
2152                if (definition->regClass().is_subdword() && definition->bytes() < 4) {
2153                   PhysReg reg = get_reg(ctx, register_file, tmp, parallelcopy, instr);
2154                   bool partial = !(tmp.bytes() <= 4 && reg.byte() == 0 && !register_file.test(reg, 4));
2155                   add_subdword_definition(program, instr, i, reg, partial);
2156                   definition = &instr->definitions[i]; /* add_subdword_definition can invalidate the reference */
2157                } else {
2158                   definition->setFixed(get_reg(ctx, register_file, tmp, parallelcopy, instr));
2159                }
2160             }
2161
2162             assert(definition->isFixed() && ((definition->getTemp().type() == RegType::vgpr && definition->physReg() >= 256) ||
2163                                              (definition->getTemp().type() != RegType::vgpr && definition->physReg() < 256)));
2164             ctx.defs_done.set(i);
2165
2166             /* set live if it has a kill point */
2167             if (!definition->isKill())
2168                live.emplace(definition->getTemp());
2169
2170             ctx.assignments[definition->tempId()] = {definition->physReg(), definition->regClass()};
2171             register_file.fill(*definition);
2172          }
2173
2174          handle_pseudo(ctx, register_file, instr.get());
2175
2176          /* kill definitions and late-kill operands and ensure that sub-dword operands can actually be read */
2177          for (const Definition& def : instr->definitions) {
2178              if (def.isTemp() && def.isKill())
2179                 register_file.clear(def);
2180          }
2181          for (unsigned i = 0; i < instr->operands.size(); i++) {
2182             const Operand& op = instr->operands[i];
2183             if (op.isTemp() && op.isFirstKill() && op.isLateKill())
2184                register_file.clear(op);
2185             if (op.isTemp() && op.physReg().byte() != 0)
2186                add_subdword_operand(program->chip_class, instr, i, op.physReg().byte(), op.regClass());
2187          }
2188
2189          /* emit parallelcopy */
2190          if (!parallelcopy.empty()) {
2191             aco_ptr<Pseudo_instruction> pc;
2192             pc.reset(create_instruction<Pseudo_instruction>(aco_opcode::p_parallelcopy, Format::PSEUDO, parallelcopy.size(), parallelcopy.size()));
2193             bool temp_in_scc = register_file[scc.reg()];
2194             bool sgpr_operands_alias_defs = false;
2195             uint64_t sgpr_operands[4] = {0, 0, 0, 0};
2196             for (unsigned i = 0; i < parallelcopy.size(); i++) {
2197                if (temp_in_scc && parallelcopy[i].first.isTemp() && parallelcopy[i].first.getTemp().type() == RegType::sgpr) {
2198                   if (!sgpr_operands_alias_defs) {
2199                      unsigned reg = parallelcopy[i].first.physReg().reg();
2200                      unsigned size = parallelcopy[i].first.getTemp().size();
2201                      sgpr_operands[reg / 64u] |= ((1u << size) - 1) << (reg % 64u);
2202
2203                      reg = parallelcopy[i].second.physReg().reg();
2204                      size = parallelcopy[i].second.getTemp().size();
2205                      if (sgpr_operands[reg / 64u] & ((1u << size) - 1) << (reg % 64u))
2206                         sgpr_operands_alias_defs = true;
2207                   }
2208                }
2209
2210                pc->operands[i] = parallelcopy[i].first;
2211                pc->definitions[i] = parallelcopy[i].second;
2212                assert(pc->operands[i].size() == pc->definitions[i].size());
2213
2214                /* it might happen that the operand is already renamed. we have to restore the original name. */
2215                std::unordered_map<unsigned, Temp>::iterator it = ctx.orig_names.find(pc->operands[i].tempId());
2216                Temp orig = it != ctx.orig_names.end() ? it->second : pc->operands[i].getTemp();
2217                ctx.orig_names[pc->definitions[i].tempId()] = orig;
2218                ctx.renames[block.index][orig.id()] = pc->definitions[i].getTemp();
2219
2220                std::unordered_map<unsigned, phi_info>::iterator phi = ctx.phi_map.find(pc->operands[i].tempId());
2221                if (phi != ctx.phi_map.end())
2222                   phi->second.uses.emplace(pc.get());
2223             }
2224
2225             if (temp_in_scc && sgpr_operands_alias_defs) {
2226                /* disable definitions and re-enable operands */
2227                for (const Definition& def : instr->definitions) {
2228                   if (def.isTemp() && !def.isKill())
2229                      register_file.clear(def);
2230                }
2231                for (const Operand& op : instr->operands) {
2232                   if (op.isTemp() && op.isFirstKill())
2233                      register_file.block(op.physReg(), op.regClass());
2234                }
2235
2236                handle_pseudo(ctx, register_file, pc.get());
2237
2238                /* re-enable live vars */
2239                for (const Operand& op : instr->operands) {
2240                   if (op.isTemp() && op.isFirstKill())
2241                      register_file.clear(op);
2242                }
2243                for (const Definition& def : instr->definitions) {
2244                   if (def.isTemp() && !def.isKill())
2245                      register_file.fill(def);
2246                }
2247             } else {
2248                pc->tmp_in_scc = false;
2249             }
2250
2251             instructions.emplace_back(std::move(pc));
2252          }
2253
2254          /* some instructions need VOP3 encoding if operand/definition is not assigned to VCC */
2255          bool instr_needs_vop3 = !instr->isVOP3() &&
2256                                  ((instr->format == Format::VOPC && !(instr->definitions[0].physReg() == vcc)) ||
2257                                   (instr->opcode == aco_opcode::v_cndmask_b32 && !(instr->operands[2].physReg() == vcc)) ||
2258                                   ((instr->opcode == aco_opcode::v_add_co_u32 ||
2259                                     instr->opcode == aco_opcode::v_addc_co_u32 ||
2260                                     instr->opcode == aco_opcode::v_sub_co_u32 ||
2261                                     instr->opcode == aco_opcode::v_subb_co_u32 ||
2262                                     instr->opcode == aco_opcode::v_subrev_co_u32 ||
2263                                     instr->opcode == aco_opcode::v_subbrev_co_u32) &&
2264                                    !(instr->definitions[1].physReg() == vcc)) ||
2265                                   ((instr->opcode == aco_opcode::v_addc_co_u32 ||
2266                                     instr->opcode == aco_opcode::v_subb_co_u32 ||
2267                                     instr->opcode == aco_opcode::v_subbrev_co_u32) &&
2268                                    !(instr->operands[2].physReg() == vcc)));
2269          if (instr_needs_vop3) {
2270
2271             /* if the first operand is a literal, we have to move it to a reg */
2272             if (instr->operands.size() && instr->operands[0].isLiteral() && program->chip_class < GFX10) {
2273                bool can_sgpr = true;
2274                /* check, if we have to move to vgpr */
2275                for (const Operand& op : instr->operands) {
2276                   if (op.isTemp() && op.getTemp().type() == RegType::sgpr) {
2277                      can_sgpr = false;
2278                      break;
2279                   }
2280                }
2281                /* disable definitions and re-enable operands */
2282                for (const Definition& def : instr->definitions)
2283                   register_file.clear(def);
2284                for (const Operand& op : instr->operands) {
2285                   if (op.isTemp() && op.isFirstKill())
2286                      register_file.block(op.physReg(), op.regClass());
2287                }
2288                Temp tmp = {program->allocateId(), can_sgpr ? s1 : v1};
2289                ctx.assignments.emplace_back();
2290                PhysReg reg = get_reg(ctx, register_file, tmp, parallelcopy, instr);
2291
2292                aco_ptr<Instruction> mov;
2293                if (can_sgpr)
2294                   mov.reset(create_instruction<SOP1_instruction>(aco_opcode::s_mov_b32, Format::SOP1, 1, 1));
2295                else
2296                   mov.reset(create_instruction<VOP1_instruction>(aco_opcode::v_mov_b32, Format::VOP1, 1, 1));
2297                mov->operands[0] = instr->operands[0];
2298                mov->definitions[0] = Definition(tmp);
2299                mov->definitions[0].setFixed(reg);
2300
2301                instr->operands[0] = Operand(tmp);
2302                instr->operands[0].setFixed(reg);
2303                instructions.emplace_back(std::move(mov));
2304                /* re-enable live vars */
2305                for (const Operand& op : instr->operands) {
2306                   if (op.isTemp() && op.isFirstKill())
2307                      register_file.clear(op);
2308                }
2309                for (const Definition& def : instr->definitions) {
2310                   if (def.isTemp() && !def.isKill())
2311                      register_file.fill(def);
2312                }
2313             }
2314
2315             /* change the instruction to VOP3 to enable an arbitrary register pair as dst */
2316             aco_ptr<Instruction> tmp = std::move(instr);
2317             Format format = asVOP3(tmp->format);
2318             instr.reset(create_instruction<VOP3A_instruction>(tmp->opcode, format, tmp->operands.size(), tmp->definitions.size()));
2319             for (unsigned i = 0; i < instr->operands.size(); i++) {
2320                Operand& operand = tmp->operands[i];
2321                instr->operands[i] = operand;
2322                /* keep phi_map up to date */
2323                if (operand.isTemp()) {
2324                   std::unordered_map<unsigned, phi_info>::iterator phi = ctx.phi_map.find(operand.tempId());
2325                   if (phi != ctx.phi_map.end()) {
2326                      phi->second.uses.erase(tmp.get());
2327                      phi->second.uses.emplace(instr.get());
2328                   }
2329                }
2330             }
2331             std::copy(tmp->definitions.begin(), tmp->definitions.end(), instr->definitions.begin());
2332          }
2333
2334          instructions.emplace_back(std::move(*it));
2335
2336       } /* end for Instr */
2337
2338       block.instructions = std::move(instructions);
2339
2340       ctx.filled[block.index] = true;
2341       for (unsigned succ_idx : block.linear_succs) {
2342          Block& succ = program->blocks[succ_idx];
2343          /* seal block if all predecessors are filled */
2344          bool all_filled = true;
2345          for (unsigned pred_idx : succ.linear_preds) {
2346             if (!ctx.filled[pred_idx]) {
2347                all_filled = false;
2348                break;
2349             }
2350          }
2351          if (all_filled) {
2352             ctx.sealed[succ_idx] = true;
2353
2354             /* finish incomplete phis and check if they became trivial */
2355             for (Instruction* phi : ctx.incomplete_phis[succ_idx]) {
2356                std::vector<unsigned> preds = phi->definitions[0].getTemp().is_linear() ? succ.linear_preds : succ.logical_preds;
2357                for (unsigned i = 0; i < phi->operands.size(); i++) {
2358                   phi->operands[i].setTemp(read_variable(ctx, phi->operands[i].getTemp(), preds[i]));
2359                   phi->operands[i].setFixed(ctx.assignments[phi->operands[i].tempId()].reg);
2360                }
2361                try_remove_trivial_phi(ctx, phi->definitions[0].getTemp());
2362             }
2363             /* complete the original phi nodes, but no need to check triviality */
2364             for (aco_ptr<Instruction>& instr : succ.instructions) {
2365                if (!is_phi(instr))
2366                   break;
2367                std::vector<unsigned> preds = instr->opcode == aco_opcode::p_phi ? succ.logical_preds : succ.linear_preds;
2368
2369                for (unsigned i = 0; i < instr->operands.size(); i++) {
2370                   auto& operand = instr->operands[i];
2371                   if (!operand.isTemp())
2372                      continue;
2373                   operand.setTemp(read_variable(ctx, operand.getTemp(), preds[i]));
2374                   operand.setFixed(ctx.assignments[operand.tempId()].reg);
2375                   std::unordered_map<unsigned, phi_info>::iterator phi = ctx.phi_map.find(operand.getTemp().id());
2376                   if (phi != ctx.phi_map.end())
2377                      phi->second.uses.emplace(instr.get());
2378                }
2379             }
2380          }
2381       }
2382    } /* end for BB */
2383
2384    /* remove trivial phis */
2385    for (Block& block : program->blocks) {
2386       auto end = std::find_if(block.instructions.begin(), block.instructions.end(),
2387                               [](aco_ptr<Instruction>& instr) { return !is_phi(instr);});
2388       auto middle = std::remove_if(block.instructions.begin(), end,
2389                                    [](const aco_ptr<Instruction>& instr) { return instr->definitions.empty();});
2390       block.instructions.erase(middle, end);
2391    }
2392
2393    /* find scc spill registers which may be needed for parallelcopies created by phis */
2394    for (Block& block : program->blocks) {
2395       if (block.linear_preds.size() <= 1)
2396          continue;
2397
2398       std::bitset<128> regs = sgpr_live_in[block.index];
2399       if (!regs[127])
2400          continue;
2401
2402       /* choose a register */
2403       int16_t reg = 0;
2404       for (; reg < ctx.program->max_reg_demand.sgpr && regs[reg]; reg++)
2405          ;
2406       assert(reg < ctx.program->max_reg_demand.sgpr);
2407       adjust_max_used_regs(ctx, s1, reg);
2408
2409       /* update predecessors */
2410       for (unsigned& pred_index : block.linear_preds) {
2411          Block& pred = program->blocks[pred_index];
2412          pred.scc_live_out = true;
2413          pred.scratch_sgpr = PhysReg{(uint16_t)reg};
2414       }
2415    }
2416
2417    /* num_gpr = rnd_up(max_used_gpr + 1) */
2418    program->config->num_vgprs = align(ctx.max_used_vgpr + 1, 4);
2419    if (program->family == CHIP_TONGA || program->family == CHIP_ICELAND) /* workaround hardware bug */
2420       program->config->num_sgprs = get_sgpr_alloc(program, program->sgpr_limit);
2421    else
2422       program->config->num_sgprs = align(ctx.max_used_sgpr + 1 + get_extra_sgprs(program), 8);
2423 }
2424
2425 }