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