src/amd/compiler/aco_register_allocation.cpp

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