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