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