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