src/amd/compiler/aco_register_allocation.cpp

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