src/amd/compiler/aco_spill.cpp

   1 /*
   2  * Copyright © 2018 Valve Corporation
   3  * Copyright © 2018 Google
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22  * IN THE SOFTWARE.
  23  *
  24  */
  25
  26 #include "aco_ir.h"
  27 #include <map>
  28 #include <stack>
  29 #include "vulkan/radv_shader.h"
  30
  31
  32 /*
  33  * Implements the spilling algorithm on SSA-form from
  34  * "Register Spilling and Live-Range Splitting for SSA-Form Programs"
  35  * by Matthias Braun and Sebastian Hack.
  36  */
  37
  38 namespace aco {
  39
  40 namespace {
  41
  42 struct remat_info {
  43    Instruction *instr;
  44 };
  45
  46 struct spill_ctx {
  47    RegisterDemand target_pressure;
  48    Program* program;
  49    std::vector<std::vector<RegisterDemand>> register_demand;
  50    std::vector<std::map<Temp, Temp>> renames;
  51    std::vector<std::map<Temp, uint32_t>> spills_entry;
  52    std::vector<std::map<Temp, uint32_t>> spills_exit;
  53    std::vector<bool> processed;
  54    std::stack<Block*> loop_header;
  55    std::vector<std::map<Temp, std::pair<uint32_t, uint32_t>>> next_use_distances_start;
  56    std::vector<std::map<Temp, std::pair<uint32_t, uint32_t>>> next_use_distances_end;
  57    std::vector<std::pair<RegClass, std::set<uint32_t>>> interferences;
  58    std::vector<std::vector<uint32_t>> affinities;
  59    std::vector<bool> is_reloaded;
  60    std::map<Temp, remat_info> remat;
  61    std::map<Instruction *, bool> remat_used;
  62
  63    spill_ctx(const RegisterDemand target_pressure, Program* program,
  64              std::vector<std::vector<RegisterDemand>> register_demand)
  65       : target_pressure(target_pressure), program(program),
  66         register_demand(register_demand), renames(program->blocks.size()),
  67         spills_entry(program->blocks.size()), spills_exit(program->blocks.size()),
  68         processed(program->blocks.size(), false) {}
  69
  70    void add_affinity(uint32_t first, uint32_t second)
  71    {
  72       unsigned found_first = affinities.size();
  73       unsigned found_second = affinities.size();
  74       for (unsigned i = 0; i < affinities.size(); i++) {
  75          std::vector<uint32_t>& vec = affinities[i];
  76          for (uint32_t entry : vec) {
  77             if (entry == first)
  78                found_first = i;
  79             else if (entry == second)
  80                found_second = i;
  81          }
  82       }
  83       if (found_first == affinities.size() && found_second == affinities.size()) {
  84          affinities.emplace_back(std::vector<uint32_t>({first, second}));
  85       } else if (found_first < affinities.size() && found_second == affinities.size()) {
  86          affinities[found_first].push_back(second);
  87       } else if (found_second < affinities.size() && found_first == affinities.size()) {
  88          affinities[found_second].push_back(first);
  89       } else if (found_first != found_second) {
  90          /* merge second into first */
  91          affinities[found_first].insert(affinities[found_first].end(), affinities[found_second].begin(), affinities[found_second].end());
  92          affinities.erase(std::next(affinities.begin(), found_second));
  93       } else {
  94          assert(found_first == found_second);
  95       }
  96    }
  97
  98    uint32_t allocate_spill_id(RegClass rc)
  99    {
 100       interferences.emplace_back(rc, std::set<uint32_t>());
 101       is_reloaded.push_back(false);
 102       return next_spill_id++;
 103    }
 104
 105    uint32_t next_spill_id = 0;
 106 };
 107
 108 int32_t get_dominator(int idx_a, int idx_b, Program* program, bool is_linear)
 109 {
 110
 111    if (idx_a == -1)
 112       return idx_b;
 113    if (idx_b == -1)
 114       return idx_a;
 115    if (is_linear) {
 116       while (idx_a != idx_b) {
 117          if (idx_a > idx_b)
 118             idx_a = program->blocks[idx_a].linear_idom;
 119          else
 120             idx_b = program->blocks[idx_b].linear_idom;
 121       }
 122    } else {
 123       while (idx_a != idx_b) {
 124          if (idx_a > idx_b)
 125             idx_a = program->blocks[idx_a].logical_idom;
 126          else
 127             idx_b = program->blocks[idx_b].logical_idom;
 128       }
 129    }
 130    assert(idx_a != -1);
 131    return idx_a;
 132 }
 133
 134 void next_uses_per_block(spill_ctx& ctx, unsigned block_idx, std::set<uint32_t>& worklist)
 135 {
 136    Block* block = &ctx.program->blocks[block_idx];
 137    std::map<Temp, std::pair<uint32_t, uint32_t>> next_uses = ctx.next_use_distances_end[block_idx];
 138
 139    /* to compute the next use distance at the beginning of the block, we have to add the block's size */
 140    for (std::map<Temp, std::pair<uint32_t, uint32_t>>::iterator it = next_uses.begin(); it != next_uses.end(); ++it)
 141       it->second.second = it->second.second + block->instructions.size();
 142
 143    int idx = block->instructions.size() - 1;
 144    while (idx >= 0) {
 145       aco_ptr<Instruction>& instr = block->instructions[idx];
 146
 147       if (instr->opcode == aco_opcode::p_linear_phi ||
 148           instr->opcode == aco_opcode::p_phi)
 149          break;
 150
 151       for (const Definition& def : instr->definitions) {
 152          if (def.isTemp())
 153             next_uses.erase(def.getTemp());
 154       }
 155
 156       for (const Operand& op : instr->operands) {
 157          /* omit exec mask */
 158          if (op.isFixed() && op.physReg() == exec)
 159             continue;
 160          if (op.isTemp())
 161             next_uses[op.getTemp()] = {block_idx, idx};
 162       }
 163       idx--;
 164    }
 165
 166    assert(block_idx != 0 || next_uses.empty());
 167    ctx.next_use_distances_start[block_idx] = next_uses;
 168    while (idx >= 0) {
 169       aco_ptr<Instruction>& instr = block->instructions[idx];
 170       assert(instr->opcode == aco_opcode::p_linear_phi || instr->opcode == aco_opcode::p_phi);
 171
 172       for (unsigned i = 0; i < instr->operands.size(); i++) {
 173          unsigned pred_idx = instr->opcode == aco_opcode::p_phi ?
 174                              block->logical_preds[i] :
 175                              block->linear_preds[i];
 176          if (instr->operands[i].isTemp()) {
 177             if (instr->operands[i].getTemp() == ctx.program->blocks[pred_idx].live_out_exec)
 178                continue;
 179             if (ctx.next_use_distances_end[pred_idx].find(instr->operands[i].getTemp()) == ctx.next_use_distances_end[pred_idx].end() ||
 180                 ctx.next_use_distances_end[pred_idx][instr->operands[i].getTemp()] != std::pair<uint32_t, uint32_t>{block_idx, 0})
 181                worklist.insert(pred_idx);
 182             ctx.next_use_distances_end[pred_idx][instr->operands[i].getTemp()] = {block_idx, 0};
 183          }
 184       }
 185       next_uses.erase(instr->definitions[0].getTemp());
 186       idx--;
 187    }
 188
 189    /* all remaining live vars must be live-out at the predecessors */
 190    for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : next_uses) {
 191       Temp temp = pair.first;
 192       uint32_t distance = pair.second.second;
 193       uint32_t dom = pair.second.first;
 194       std::vector<unsigned>& preds = temp.is_linear() ? block->linear_preds : block->logical_preds;
 195       for (unsigned pred_idx : preds) {
 196          if (temp == ctx.program->blocks[pred_idx].live_out_exec)
 197             continue;
 198          if (ctx.program->blocks[pred_idx].loop_nest_depth > block->loop_nest_depth)
 199             distance += 0xFFFF;
 200          if (ctx.next_use_distances_end[pred_idx].find(temp) != ctx.next_use_distances_end[pred_idx].end()) {
 201             dom = get_dominator(dom, ctx.next_use_distances_end[pred_idx][temp].first, ctx.program, temp.is_linear());
 202             distance = std::min(ctx.next_use_distances_end[pred_idx][temp].second, distance);
 203          }
 204          if (ctx.next_use_distances_end[pred_idx][temp] != std::pair<uint32_t, uint32_t>{dom, distance})
 205             worklist.insert(pred_idx);
 206          ctx.next_use_distances_end[pred_idx][temp] = {dom, distance};
 207       }
 208    }
 209
 210 }
 211
 212 void compute_global_next_uses(spill_ctx& ctx, std::vector<std::set<Temp>>& live_out)
 213 {
 214    ctx.next_use_distances_start.resize(ctx.program->blocks.size());
 215    ctx.next_use_distances_end.resize(ctx.program->blocks.size());
 216    std::set<uint32_t> worklist;
 217    for (Block& block : ctx.program->blocks)
 218       worklist.insert(block.index);
 219
 220    while (!worklist.empty()) {
 221       std::set<unsigned>::reverse_iterator b_it = worklist.rbegin();
 222       unsigned block_idx = *b_it;
 223       worklist.erase(block_idx);
 224       next_uses_per_block(ctx, block_idx, worklist);
 225    }
 226 }
 227
 228 bool should_rematerialize(aco_ptr<Instruction>& instr)
 229 {
 230    /* TODO: rematerialization is only supported for VOP1, SOP1 and PSEUDO */
 231    if (instr->format != Format::VOP1 && instr->format != Format::SOP1 && instr->format != Format::PSEUDO)
 232       return false;
 233    /* TODO: pseudo-instruction rematerialization is only supported for p_create_vector */
 234    if (instr->format == Format::PSEUDO && instr->opcode != aco_opcode::p_create_vector)
 235       return false;
 236
 237    for (const Operand& op : instr->operands) {
 238       /* TODO: rematerialization using temporaries isn't yet supported */
 239       if (op.isTemp())
 240          return false;
 241    }
 242
 243    /* TODO: rematerialization with multiple definitions isn't yet supported */
 244    if (instr->definitions.size() > 1)
 245       return false;
 246
 247    return true;
 248 }
 249
 250 aco_ptr<Instruction> do_reload(spill_ctx& ctx, Temp tmp, Temp new_name, uint32_t spill_id)
 251 {
 252    std::map<Temp, remat_info>::iterator remat = ctx.remat.find(tmp);
 253    if (remat != ctx.remat.end()) {
 254       Instruction *instr = remat->second.instr;
 255       assert((instr->format == Format::VOP1 || instr->format == Format::SOP1 || instr->format == Format::PSEUDO) && "unsupported");
 256       assert((instr->format != Format::PSEUDO || instr->opcode == aco_opcode::p_create_vector) && "unsupported");
 257       assert(instr->definitions.size() == 1 && "unsupported");
 258
 259       aco_ptr<Instruction> res;
 260       if (instr->format == Format::VOP1) {
 261          res.reset(create_instruction<VOP1_instruction>(instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
 262       } else if (instr->format == Format::SOP1) {
 263          res.reset(create_instruction<SOP1_instruction>(instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
 264       } else if (instr->format == Format::PSEUDO) {
 265          res.reset(create_instruction<Instruction>(instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
 266       }
 267       for (unsigned i = 0; i < instr->operands.size(); i++) {
 268          res->operands[i] = instr->operands[i];
 269          if (instr->operands[i].isTemp()) {
 270             assert(false && "unsupported");
 271             if (ctx.remat.count(instr->operands[i].getTemp()))
 272                ctx.remat_used[ctx.remat[instr->operands[i].getTemp()].instr] = true;
 273          }
 274       }
 275       res->definitions[0] = Definition(new_name);
 276       return res;
 277    } else {
 278       aco_ptr<Pseudo_instruction> reload{create_instruction<Pseudo_instruction>(aco_opcode::p_reload, Format::PSEUDO, 1, 1)};
 279       reload->operands[0] = Operand(spill_id);
 280       reload->definitions[0] = Definition(new_name);
 281       ctx.is_reloaded[spill_id] = true;
 282       return reload;
 283    }
 284 }
 285
 286 void get_rematerialize_info(spill_ctx& ctx)
 287 {
 288    for (Block& block : ctx.program->blocks) {
 289       bool logical = false;
 290       for (aco_ptr<Instruction>& instr : block.instructions) {
 291          if (instr->opcode == aco_opcode::p_logical_start)
 292             logical = true;
 293          else if (instr->opcode == aco_opcode::p_logical_end)
 294             logical = false;
 295          if (logical && should_rematerialize(instr)) {
 296             for (const Definition& def : instr->definitions) {
 297                if (def.isTemp()) {
 298                   ctx.remat[def.getTemp()] = (remat_info){instr.get()};
 299                   ctx.remat_used[instr.get()] = false;
 300                }
 301             }
 302          }
 303       }
 304    }
 305 }
 306
 307 std::vector<std::map<Temp, uint32_t>> local_next_uses(spill_ctx& ctx, Block* block)
 308 {
 309    std::vector<std::map<Temp, uint32_t>> local_next_uses(block->instructions.size());
 310
 311    std::map<Temp, uint32_t> next_uses;
 312    for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_end[block->index])
 313       next_uses[pair.first] = pair.second.second + block->instructions.size();
 314
 315    for (int idx = block->instructions.size() - 1; idx >= 0; idx--) {
 316       aco_ptr<Instruction>& instr = block->instructions[idx];
 317       if (!instr)
 318          break;
 319       if (instr->opcode == aco_opcode::p_phi || instr->opcode == aco_opcode::p_linear_phi)
 320          break;
 321
 322       for (const Operand& op : instr->operands) {
 323          if (op.isFixed() && op.physReg() == exec)
 324             continue;
 325          if (op.isTemp())
 326             next_uses[op.getTemp()] = idx;
 327       }
 328       for (const Definition& def : instr->definitions) {
 329          if (def.isTemp())
 330             next_uses.erase(def.getTemp());
 331       }
 332       local_next_uses[idx] = next_uses;
 333    }
 334    return local_next_uses;
 335 }
 336
 337
 338 RegisterDemand init_live_in_vars(spill_ctx& ctx, Block* block, unsigned block_idx)
 339 {
 340    RegisterDemand spilled_registers;
 341
 342    /* first block, nothing was spilled before */
 343    if (block_idx == 0)
 344       return {0, 0};
 345
 346    /* loop header block */
 347    if (block->loop_nest_depth > ctx.program->blocks[block_idx - 1].loop_nest_depth) {
 348       assert(block->linear_preds[0] == block_idx - 1);
 349       assert(block->logical_preds[0] == block_idx - 1);
 350
 351       /* create new loop_info */
 352       ctx.loop_header.emplace(block);
 353
 354       /* check how many live-through variables should be spilled */
 355       RegisterDemand new_demand;
 356       unsigned i = block_idx;
 357       while (ctx.program->blocks[i].loop_nest_depth >= block->loop_nest_depth) {
 358          assert(ctx.program->blocks.size() > i);
 359          new_demand.update(ctx.program->blocks[i].register_demand);
 360          i++;
 361       }
 362       unsigned loop_end = i;
 363
 364       /* select live-through vgpr variables */
 365       while (new_demand.vgpr - spilled_registers.vgpr > ctx.target_pressure.vgpr) {
 366          unsigned distance = 0;
 367          Temp to_spill;
 368          for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_end[block_idx - 1]) {
 369             if (pair.first.type() == RegType::vgpr &&
 370                 pair.second.first >= loop_end &&
 371                 pair.second.second > distance &&
 372                 ctx.spills_entry[block_idx].find(pair.first) == ctx.spills_entry[block_idx].end()) {
 373                to_spill = pair.first;
 374                distance = pair.second.second;
 375             }
 376          }
 377          if (distance == 0)
 378             break;
 379
 380          uint32_t spill_id;
 381          if (ctx.spills_exit[block_idx - 1].find(to_spill) == ctx.spills_exit[block_idx - 1].end()) {
 382             spill_id = ctx.allocate_spill_id(to_spill.regClass());
 383          } else {
 384             spill_id = ctx.spills_exit[block_idx - 1][to_spill];
 385          }
 386
 387          ctx.spills_entry[block_idx][to_spill] = spill_id;
 388          spilled_registers.vgpr += to_spill.size();
 389       }
 390
 391       /* select live-through sgpr variables */
 392       while (new_demand.sgpr - spilled_registers.sgpr > ctx.target_pressure.sgpr) {
 393          unsigned distance = 0;
 394          Temp to_spill;
 395          for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_end[block_idx - 1]) {
 396             if (pair.first.type() == RegType::sgpr &&
 397                 pair.second.first >= loop_end &&
 398                 pair.second.second > distance &&
 399                 ctx.spills_entry[block_idx].find(pair.first) == ctx.spills_entry[block_idx].end()) {
 400                to_spill = pair.first;
 401                distance = pair.second.second;
 402             }
 403          }
 404          if (distance == 0)
 405             break;
 406
 407          uint32_t spill_id;
 408          if (ctx.spills_exit[block_idx - 1].find(to_spill) == ctx.spills_exit[block_idx - 1].end()) {
 409             spill_id = ctx.allocate_spill_id(to_spill.regClass());
 410          } else {
 411             spill_id = ctx.spills_exit[block_idx - 1][to_spill];
 412          }
 413
 414          ctx.spills_entry[block_idx][to_spill] = spill_id;
 415          spilled_registers.sgpr += to_spill.size();
 416       }
 417
 418
 419
 420       /* shortcut */
 421       if (!RegisterDemand(new_demand - spilled_registers).exceeds(ctx.target_pressure))
 422          return spilled_registers;
 423
 424       /* if reg pressure is too high at beginning of loop, add variables with furthest use */
 425       unsigned idx = 0;
 426       while (block->instructions[idx]->opcode == aco_opcode::p_phi || block->instructions[idx]->opcode == aco_opcode::p_linear_phi)
 427          idx++;
 428
 429       assert(idx != 0 && "loop without phis: TODO");
 430       idx--;
 431       RegisterDemand reg_pressure = ctx.register_demand[block_idx][idx] - spilled_registers;
 432       while (reg_pressure.sgpr > ctx.target_pressure.sgpr) {
 433          unsigned distance = 0;
 434          Temp to_spill;
 435          for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_start[block_idx]) {
 436             if (pair.first.type() == RegType::sgpr &&
 437                 pair.second.second > distance &&
 438                 ctx.spills_entry[block_idx].find(pair.first) == ctx.spills_entry[block_idx].end()) {
 439                to_spill = pair.first;
 440                distance = pair.second.second;
 441             }
 442          }
 443          assert(distance != 0);
 444
 445          ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
 446          spilled_registers.sgpr += to_spill.size();
 447          reg_pressure.sgpr -= to_spill.size();
 448       }
 449       while (reg_pressure.vgpr > ctx.target_pressure.vgpr) {
 450          unsigned distance = 0;
 451          Temp to_spill;
 452          for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_start[block_idx]) {
 453             if (pair.first.type() == RegType::vgpr &&
 454                 pair.second.second > distance &&
 455                 ctx.spills_entry[block_idx].find(pair.first) == ctx.spills_entry[block_idx].end()) {
 456                to_spill = pair.first;
 457                distance = pair.second.second;
 458             }
 459          }
 460          assert(distance != 0);
 461          ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
 462          spilled_registers.vgpr += to_spill.size();
 463          reg_pressure.vgpr -= to_spill.size();
 464       }
 465
 466       return spilled_registers;
 467    }
 468
 469    /* branch block */
 470    if (block->linear_preds.size() == 1 && !(block->kind & block_kind_loop_exit)) {
 471       /* keep variables spilled if they are alive and not used in the current block */
 472       unsigned pred_idx = block->linear_preds[0];
 473       for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
 474          if (pair.first.type() == RegType::sgpr &&
 475              ctx.next_use_distances_start[block_idx].find(pair.first) != ctx.next_use_distances_start[block_idx].end() &&
 476              ctx.next_use_distances_start[block_idx][pair.first].second > block_idx) {
 477             ctx.spills_entry[block_idx].insert(pair);
 478             spilled_registers.sgpr += pair.first.size();
 479          }
 480       }
 481       if (block->logical_preds.size() == 1) {
 482          pred_idx = block->logical_preds[0];
 483          for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
 484             if (pair.first.type() == RegType::vgpr &&
 485                 ctx.next_use_distances_start[block_idx].find(pair.first) != ctx.next_use_distances_start[block_idx].end() &&
 486                 ctx.next_use_distances_end[pred_idx][pair.first].second > block_idx) {
 487                ctx.spills_entry[block_idx].insert(pair);
 488                spilled_registers.vgpr += pair.first.size();
 489             }
 490          }
 491       }
 492
 493       /* if register demand is still too high, we just keep all spilled live vars and process the block */
 494       if (block->register_demand.sgpr - spilled_registers.sgpr > ctx.target_pressure.sgpr) {
 495          pred_idx = block->linear_preds[0];
 496          for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
 497             if (pair.first.type() == RegType::sgpr &&
 498                 ctx.next_use_distances_start[block_idx].find(pair.first) != ctx.next_use_distances_start[block_idx].end() &&
 499                 ctx.spills_entry[block_idx].insert(pair).second) {
 500                spilled_registers.sgpr += pair.first.size();
 501             }
 502          }
 503       }
 504       if (block->register_demand.vgpr - spilled_registers.vgpr > ctx.target_pressure.vgpr && block->logical_preds.size() == 1) {
 505          pred_idx = block->logical_preds[0];
 506          for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
 507             if (pair.first.type() == RegType::vgpr &&
 508                 ctx.next_use_distances_start[block_idx].find(pair.first) != ctx.next_use_distances_start[block_idx].end() &&
 509                 ctx.spills_entry[block_idx].insert(pair).second) {
 510                spilled_registers.vgpr += pair.first.size();
 511             }
 512          }
 513       }
 514
 515       return spilled_registers;
 516    }
 517
 518    /* else: merge block */
 519    std::set<Temp> partial_spills;
 520
 521    /* keep variables spilled on all incoming paths */
 522    for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_start[block_idx]) {
 523       std::vector<unsigned>& preds = pair.first.type() == RegType::vgpr ? block->logical_preds : block->linear_preds;
 524       /* If it can be rematerialized, keep the variable spilled if all predecessors do not reload it.
 525        * Otherwise, if any predecessor reloads it, ensure it's reloaded on all other predecessors.
 526        * The idea is that it's better in practice to rematerialize redundantly than to create lots of phis. */
 527       /* TODO: test this idea with more than Dawn of War III shaders (the current pipeline-db doesn't seem to exercise this path much) */
 528       bool remat = ctx.remat.count(pair.first);
 529       bool spill = !remat;
 530       uint32_t spill_id = 0;
 531       for (unsigned pred_idx : preds) {
 532          /* variable is not even live at the predecessor: probably from a phi */
 533          if (ctx.next_use_distances_end[pred_idx].find(pair.first) == ctx.next_use_distances_end[pred_idx].end()) {
 534             spill = false;
 535             break;
 536          }
 537          if (ctx.spills_exit[pred_idx].find(pair.first) == ctx.spills_exit[pred_idx].end()) {
 538             if (!remat)
 539                spill = false;
 540          } else {
 541             partial_spills.insert(pair.first);
 542             /* it might be that on one incoming path, the variable has a different spill_id, but add_couple_code() will take care of that. */
 543             spill_id = ctx.spills_exit[pred_idx][pair.first];
 544             if (remat)
 545                spill = true;
 546          }
 547       }
 548       if (spill) {
 549          ctx.spills_entry[block_idx][pair.first] = spill_id;
 550          partial_spills.erase(pair.first);
 551          spilled_registers += pair.first;
 552       }
 553    }
 554
 555    /* same for phis */
 556    unsigned idx = 0;
 557    while (block->instructions[idx]->opcode == aco_opcode::p_linear_phi ||
 558           block->instructions[idx]->opcode == aco_opcode::p_phi) {
 559       aco_ptr<Instruction>& phi = block->instructions[idx];
 560       std::vector<unsigned>& preds = phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
 561       bool spill = true;
 562
 563       for (unsigned i = 0; i < phi->operands.size(); i++) {
 564          if (phi->operands[i].isUndefined())
 565             continue;
 566          assert(phi->operands[i].isTemp());
 567          if (ctx.spills_exit[preds[i]].find(phi->operands[i].getTemp()) == ctx.spills_exit[preds[i]].end())
 568             spill = false;
 569          else
 570             partial_spills.insert(phi->definitions[0].getTemp());
 571       }
 572       if (spill) {
 573          ctx.spills_entry[block_idx][phi->definitions[0].getTemp()] = ctx.allocate_spill_id(phi->definitions[0].regClass());
 574          partial_spills.erase(phi->definitions[0].getTemp());
 575          spilled_registers += phi->definitions[0].getTemp();
 576       }
 577
 578       idx++;
 579    }
 580
 581    /* if reg pressure at first instruction is still too high, add partially spilled variables */
 582    RegisterDemand reg_pressure;
 583    if (idx == 0) {
 584       for (const Definition& def : block->instructions[idx]->definitions) {
 585          if (def.isTemp()) {
 586             reg_pressure -= def.getTemp();
 587          }
 588       }
 589       for (const Operand& op : block->instructions[idx]->operands) {
 590          if (op.isTemp() && op.isFirstKill()) {
 591             reg_pressure += op.getTemp();
 592          }
 593       }
 594    } else {
 595       idx--;
 596    }
 597    reg_pressure += ctx.register_demand[block_idx][idx] - spilled_registers;
 598
 599    while (reg_pressure.sgpr > ctx.target_pressure.sgpr) {
 600       assert(!partial_spills.empty());
 601
 602       std::set<Temp>::iterator it = partial_spills.begin();
 603       Temp to_spill = *it;
 604       unsigned distance = ctx.next_use_distances_start[block_idx][*it].second;
 605       while (it != partial_spills.end()) {
 606          assert(ctx.spills_entry[block_idx].find(*it) == ctx.spills_entry[block_idx].end());
 607
 608          if (it->type() == RegType::sgpr && ctx.next_use_distances_start[block_idx][*it].second > distance) {
 609             distance = ctx.next_use_distances_start[block_idx][*it].second;
 610             to_spill = *it;
 611          }
 612          ++it;
 613       }
 614       assert(distance != 0);
 615
 616       ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
 617       partial_spills.erase(to_spill);
 618       spilled_registers.sgpr += to_spill.size();
 619       reg_pressure.sgpr -= to_spill.size();
 620    }
 621
 622    while (reg_pressure.vgpr > ctx.target_pressure.vgpr) {
 623       assert(!partial_spills.empty());
 624
 625       std::set<Temp>::iterator it = partial_spills.begin();
 626       Temp to_spill = *it;
 627       unsigned distance = ctx.next_use_distances_start[block_idx][*it].second;
 628       while (it != partial_spills.end()) {
 629          assert(ctx.spills_entry[block_idx].find(*it) == ctx.spills_entry[block_idx].end());
 630
 631          if (it->type() == RegType::vgpr && ctx.next_use_distances_start[block_idx][*it].second > distance) {
 632             distance = ctx.next_use_distances_start[block_idx][*it].second;
 633             to_spill = *it;
 634          }
 635          ++it;
 636       }
 637       assert(distance != 0);
 638
 639       ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
 640       partial_spills.erase(to_spill);
 641       spilled_registers.vgpr += to_spill.size();
 642       reg_pressure.vgpr -= to_spill.size();
 643    }
 644
 645    return spilled_registers;
 646 }
 647
 648
 649 void add_coupling_code(spill_ctx& ctx, Block* block, unsigned block_idx)
 650 {
 651    /* no coupling code necessary */
 652    if (block->linear_preds.size() == 0)
 653       return;
 654
 655    std::vector<aco_ptr<Instruction>> instructions;
 656    /* branch block: TODO take other branch into consideration */
 657    if (block->linear_preds.size() == 1 && !(block->kind & block_kind_loop_exit)) {
 658       assert(ctx.processed[block->linear_preds[0]]);
 659       assert(ctx.register_demand[block_idx].size() == block->instructions.size());
 660       std::vector<RegisterDemand> reg_demand;
 661       unsigned insert_idx = 0;
 662       unsigned pred_idx = block->linear_preds[0];
 663
 664       for (std::pair<Temp, std::pair<uint32_t, uint32_t>> live : ctx.next_use_distances_start[block_idx]) {
 665          if (!live.first.is_linear())
 666             continue;
 667          /* still spilled */
 668          if (ctx.spills_entry[block_idx].find(live.first) != ctx.spills_entry[block_idx].end())
 669             continue;
 670
 671          /* in register at end of predecessor */
 672          if (ctx.spills_exit[pred_idx].find(live.first) == ctx.spills_exit[pred_idx].end()) {
 673             std::map<Temp, Temp>::iterator it = ctx.renames[pred_idx].find(live.first);
 674             if (it != ctx.renames[pred_idx].end())
 675                ctx.renames[block_idx].insert(*it);
 676             continue;
 677          }
 678
 679          /* variable is spilled at predecessor and live at current block: create reload instruction */
 680          Temp new_name = {ctx.program->allocateId(), live.first.regClass()};
 681          aco_ptr<Instruction> reload = do_reload(ctx, live.first, new_name, ctx.spills_exit[pred_idx][live.first]);
 682          instructions.emplace_back(std::move(reload));
 683          reg_demand.push_back(RegisterDemand());
 684          ctx.renames[block_idx][live.first] = new_name;
 685       }
 686
 687       if (block->logical_preds.size() == 1) {
 688          do {
 689             assert(insert_idx < block->instructions.size());
 690             instructions.emplace_back(std::move(block->instructions[insert_idx]));
 691             reg_demand.push_back(ctx.register_demand[block_idx][insert_idx]);
 692             insert_idx++;
 693          } while (instructions.back()->opcode != aco_opcode::p_logical_start);
 694
 695          unsigned pred_idx = block->logical_preds[0];
 696          for (std::pair<Temp, std::pair<uint32_t, uint32_t>> live : ctx.next_use_distances_start[block_idx]) {
 697             if (live.first.is_linear())
 698                continue;
 699             /* still spilled */
 700             if (ctx.spills_entry[block_idx].find(live.first) != ctx.spills_entry[block_idx].end())
 701                continue;
 702
 703             /* in register at end of predecessor */
 704             if (ctx.spills_exit[pred_idx].find(live.first) == ctx.spills_exit[pred_idx].end()) {
 705                std::map<Temp, Temp>::iterator it = ctx.renames[pred_idx].find(live.first);
 706                if (it != ctx.renames[pred_idx].end())
 707                   ctx.renames[block_idx].insert(*it);
 708                continue;
 709             }
 710
 711             /* variable is spilled at predecessor and live at current block: create reload instruction */
 712             Temp new_name = {ctx.program->allocateId(), live.first.regClass()};
 713             aco_ptr<Instruction> reload = do_reload(ctx, live.first, new_name, ctx.spills_exit[pred_idx][live.first]);
 714             instructions.emplace_back(std::move(reload));
 715             reg_demand.emplace_back(reg_demand.back());
 716             ctx.renames[block_idx][live.first] = new_name;
 717          }
 718       }
 719
 720       /* combine new reload instructions with original block */
 721       if (!instructions.empty()) {
 722          reg_demand.insert(reg_demand.end(), std::next(ctx.register_demand[block->index].begin(), insert_idx),
 723                            ctx.register_demand[block->index].end());
 724          ctx.register_demand[block_idx] = std::move(reg_demand);
 725          instructions.insert(instructions.end(),
 726                              std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(std::next(block->instructions.begin(), insert_idx)),
 727                              std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(block->instructions.end()));
 728          block->instructions = std::move(instructions);
 729       }
 730       return;
 731    }
 732
 733    /* loop header and merge blocks: check if all (linear) predecessors have been processed */
 734    for (ASSERTED unsigned pred : block->linear_preds)
 735       assert(ctx.processed[pred]);
 736
 737    /* iterate the phi nodes for which operands to spill at the predecessor */
 738    for (aco_ptr<Instruction>& phi : block->instructions) {
 739       if (phi->opcode != aco_opcode::p_phi &&
 740           phi->opcode != aco_opcode::p_linear_phi)
 741          break;
 742
 743       /* if the phi is not spilled, add to instructions */
 744       if (ctx.spills_entry[block_idx].find(phi->definitions[0].getTemp()) == ctx.spills_entry[block_idx].end()) {
 745          instructions.emplace_back(std::move(phi));
 746          continue;
 747       }
 748
 749       std::vector<unsigned>& preds = phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
 750       uint32_t def_spill_id = ctx.spills_entry[block_idx][phi->definitions[0].getTemp()];
 751
 752       for (unsigned i = 0; i < phi->operands.size(); i++) {
 753          if (phi->operands[i].isUndefined())
 754             continue;
 755
 756          unsigned pred_idx = preds[i];
 757          assert(phi->operands[i].isTemp() && phi->operands[i].isKill());
 758          Temp var = phi->operands[i].getTemp();
 759
 760          /* build interferences between the phi def and all spilled variables at the predecessor blocks */
 761          for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
 762             if (var == pair.first)
 763                continue;
 764             ctx.interferences[def_spill_id].second.emplace(pair.second);
 765             ctx.interferences[pair.second].second.emplace(def_spill_id);
 766          }
 767
 768          /* check if variable is already spilled at predecessor */
 769          std::map<Temp, uint32_t>::iterator spilled = ctx.spills_exit[pred_idx].find(var);
 770          if (spilled != ctx.spills_exit[pred_idx].end()) {
 771             if (spilled->second != def_spill_id)
 772                ctx.add_affinity(def_spill_id, spilled->second);
 773             continue;
 774          }
 775
 776          /* rename if necessary */
 777          std::map<Temp, Temp>::iterator rename_it = ctx.renames[pred_idx].find(var);
 778          if (rename_it != ctx.renames[pred_idx].end()) {
 779             var = rename_it->second;
 780             ctx.renames[pred_idx].erase(rename_it);
 781          }
 782
 783          uint32_t spill_id = ctx.allocate_spill_id(phi->definitions[0].regClass());
 784          ctx.add_affinity(def_spill_id, spill_id);
 785          aco_ptr<Pseudo_instruction> spill{create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
 786          spill->operands[0] = Operand(var);
 787          spill->operands[1] = Operand(spill_id);
 788          Block& pred = ctx.program->blocks[pred_idx];
 789          unsigned idx = pred.instructions.size();
 790          do {
 791             assert(idx != 0);
 792             idx--;
 793          } while (phi->opcode == aco_opcode::p_phi && pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
 794          std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
 795          pred.instructions.insert(it, std::move(spill));
 796          ctx.spills_exit[pred_idx][phi->operands[i].getTemp()] = spill_id;
 797       }
 798
 799       /* remove phi from instructions */
 800       phi.reset();
 801    }
 802
 803    /* iterate all (other) spilled variables for which to spill at the predecessor */
 804    // TODO: would be better to have them sorted: first vgprs and first with longest distance
 805    for (std::pair<Temp, uint32_t> pair : ctx.spills_entry[block_idx]) {
 806       std::vector<unsigned> preds = pair.first.type() == RegType::vgpr ? block->logical_preds : block->linear_preds;
 807
 808       for (unsigned pred_idx : preds) {
 809          /* variable is already spilled at predecessor */
 810          std::map<Temp, uint32_t>::iterator spilled = ctx.spills_exit[pred_idx].find(pair.first);
 811          if (spilled != ctx.spills_exit[pred_idx].end()) {
 812             if (spilled->second != pair.second)
 813                ctx.add_affinity(pair.second, spilled->second);
 814             continue;
 815          }
 816
 817          /* variable is dead at predecessor, it must be from a phi: this works because of CSSA form */
 818          if (ctx.next_use_distances_end[pred_idx].find(pair.first) == ctx.next_use_distances_end[pred_idx].end())
 819             continue;
 820
 821          /* add interferences between spilled variable and predecessors exit spills */
 822          for (std::pair<Temp, uint32_t> exit_spill : ctx.spills_exit[pred_idx]) {
 823             if (exit_spill.first == pair.first)
 824                continue;
 825             ctx.interferences[exit_spill.second].second.emplace(pair.second);
 826             ctx.interferences[pair.second].second.emplace(exit_spill.second);
 827          }
 828
 829          /* variable is in register at predecessor and has to be spilled */
 830          /* rename if necessary */
 831          Temp var = pair.first;
 832          std::map<Temp, Temp>::iterator rename_it = ctx.renames[pred_idx].find(var);
 833          if (rename_it != ctx.renames[pred_idx].end()) {
 834             var = rename_it->second;
 835             ctx.renames[pred_idx].erase(rename_it);
 836          }
 837
 838          aco_ptr<Pseudo_instruction> spill{create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
 839          spill->operands[0] = Operand(var);
 840          spill->operands[1] = Operand(pair.second);
 841          Block& pred = ctx.program->blocks[pred_idx];
 842          unsigned idx = pred.instructions.size();
 843          do {
 844             assert(idx != 0);
 845             idx--;
 846          } while (pair.first.type() == RegType::vgpr && pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
 847          std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
 848          pred.instructions.insert(it, std::move(spill));
 849          ctx.spills_exit[pred.index][pair.first] = pair.second;
 850       }
 851    }
 852
 853    /* iterate phis for which operands to reload */
 854    for (aco_ptr<Instruction>& phi : instructions) {
 855       assert(phi->opcode == aco_opcode::p_phi || phi->opcode == aco_opcode::p_linear_phi);
 856       assert(ctx.spills_entry[block_idx].find(phi->definitions[0].getTemp()) == ctx.spills_entry[block_idx].end());
 857
 858       std::vector<unsigned>& preds = phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
 859       for (unsigned i = 0; i < phi->operands.size(); i++) {
 860          if (!phi->operands[i].isTemp())
 861             continue;
 862          unsigned pred_idx = preds[i];
 863
 864          /* rename operand */
 865          if (ctx.spills_exit[pred_idx].find(phi->operands[i].getTemp()) == ctx.spills_exit[pred_idx].end()) {
 866             std::map<Temp, Temp>::iterator it = ctx.renames[pred_idx].find(phi->operands[i].getTemp());
 867             if (it != ctx.renames[pred_idx].end())
 868                phi->operands[i].setTemp(it->second);
 869             continue;
 870          }
 871
 872          Temp tmp = phi->operands[i].getTemp();
 873
 874          /* reload phi operand at end of predecessor block */
 875          Temp new_name = {ctx.program->allocateId(), tmp.regClass()};
 876          Block& pred = ctx.program->blocks[pred_idx];
 877          unsigned idx = pred.instructions.size();
 878          do {
 879             assert(idx != 0);
 880             idx--;
 881          } while (phi->opcode == aco_opcode::p_phi && pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
 882          std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
 883
 884          aco_ptr<Instruction> reload = do_reload(ctx, tmp, new_name, ctx.spills_exit[pred_idx][tmp]);
 885          pred.instructions.insert(it, std::move(reload));
 886
 887          ctx.spills_exit[pred_idx].erase(tmp);
 888          ctx.renames[pred_idx][tmp] = new_name;
 889          phi->operands[i].setTemp(new_name);
 890       }
 891    }
 892
 893    /* iterate live variables for which to reload */
 894    // TODO: reload at current block if variable is spilled on all predecessors
 895    for (std::pair<Temp, std::pair<uint32_t, uint32_t>> pair : ctx.next_use_distances_start[block_idx]) {
 896       /* skip spilled variables */
 897       if (ctx.spills_entry[block_idx].find(pair.first) != ctx.spills_entry[block_idx].end())
 898          continue;
 899       std::vector<unsigned> preds = pair.first.type() == RegType::vgpr ? block->logical_preds : block->linear_preds;
 900
 901       /* variable is dead at predecessor, it must be from a phi */
 902       bool is_dead = false;
 903       for (unsigned pred_idx : preds) {
 904          if (ctx.next_use_distances_end[pred_idx].find(pair.first) == ctx.next_use_distances_end[pred_idx].end())
 905             is_dead = true;
 906       }
 907       if (is_dead)
 908          continue;
 909       for (unsigned pred_idx : preds) {
 910          /* the variable is not spilled at the predecessor */
 911          if (ctx.spills_exit[pred_idx].find(pair.first) == ctx.spills_exit[pred_idx].end())
 912             continue;
 913
 914          /* variable is spilled at predecessor and has to be reloaded */
 915          Temp new_name = {ctx.program->allocateId(), pair.first.regClass()};
 916          Block& pred = ctx.program->blocks[pred_idx];
 917          unsigned idx = pred.instructions.size();
 918          do {
 919             assert(idx != 0);
 920             idx--;
 921          } while (pair.first.type() == RegType::vgpr && pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
 922          std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
 923
 924          aco_ptr<Instruction> reload = do_reload(ctx, pair.first, new_name, ctx.spills_exit[pred.index][pair.first]);
 925          pred.instructions.insert(it, std::move(reload));
 926
 927          ctx.spills_exit[pred.index].erase(pair.first);
 928          ctx.renames[pred.index][pair.first] = new_name;
 929       }
 930
 931       /* check if we have to create a new phi for this variable */
 932       Temp rename = Temp();
 933       bool is_same = true;
 934       for (unsigned pred_idx : preds) {
 935          if (ctx.renames[pred_idx].find(pair.first) == ctx.renames[pred_idx].end()) {
 936             if (rename == Temp())
 937                rename = pair.first;
 938             else
 939                is_same = rename == pair.first;
 940          } else {
 941             if (rename == Temp())
 942                rename = ctx.renames[pred_idx][pair.first];
 943             else
 944                is_same = rename == ctx.renames[pred_idx][pair.first];
 945          }
 946
 947          if (!is_same)
 948             break;
 949       }
 950
 951       if (!is_same) {
 952          /* the variable was renamed differently in the predecessors: we have to create a phi */
 953          aco_opcode opcode = pair.first.type() == RegType::vgpr ? aco_opcode::p_phi : aco_opcode::p_linear_phi;
 954          aco_ptr<Pseudo_instruction> phi{create_instruction<Pseudo_instruction>(opcode, Format::PSEUDO, preds.size(), 1)};
 955          rename = {ctx.program->allocateId(), pair.first.regClass()};
 956          for (unsigned i = 0; i < phi->operands.size(); i++) {
 957             Temp tmp;
 958             if (ctx.renames[preds[i]].find(pair.first) != ctx.renames[preds[i]].end())
 959                tmp = ctx.renames[preds[i]][pair.first];
 960             else if (preds[i] >= block_idx)
 961                tmp = rename;
 962             else
 963                tmp = pair.first;
 964             phi->operands[i] = Operand(tmp);
 965          }
 966          phi->definitions[0] = Definition(rename);
 967          instructions.emplace_back(std::move(phi));
 968       }
 969
 970       /* the variable was renamed: add new name to renames */
 971       if (!(rename == Temp() || rename == pair.first))
 972          ctx.renames[block_idx][pair.first] = rename;
 973    }
 974
 975    /* combine phis with instructions */
 976    unsigned idx = 0;
 977    while (!block->instructions[idx]) {
 978       idx++;
 979    }
 980
 981    ctx.register_demand[block->index].erase(ctx.register_demand[block->index].begin(), ctx.register_demand[block->index].begin() + idx);
 982    ctx.register_demand[block->index].insert(ctx.register_demand[block->index].begin(), instructions.size(), RegisterDemand());
 983
 984    std::vector<aco_ptr<Instruction>>::iterator start = std::next(block->instructions.begin(), idx);
 985    instructions.insert(instructions.end(), std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(start),
 986                std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(block->instructions.end()));
 987    block->instructions = std::move(instructions);
 988 }
 989
 990 void process_block(spill_ctx& ctx, unsigned block_idx, Block* block,
 991                    std::map<Temp, uint32_t> &current_spills, RegisterDemand spilled_registers)
 992 {
 993    std::vector<std::map<Temp, uint32_t>> local_next_use_distance;
 994    std::vector<aco_ptr<Instruction>> instructions;
 995    unsigned idx = 0;
 996
 997    /* phis are handled separetely */
 998    while (block->instructions[idx]->opcode == aco_opcode::p_phi ||
 999           block->instructions[idx]->opcode == aco_opcode::p_linear_phi) {
1000       aco_ptr<Instruction>& instr = block->instructions[idx];
1001       for (const Operand& op : instr->operands) {
1002          /* prevent it's definining instruction from being DCE'd if it could be rematerialized */
1003          if (op.isTemp() && ctx.remat.count(op.getTemp()))
1004             ctx.remat_used[ctx.remat[op.getTemp()].instr] = true;
1005       }
1006       instructions.emplace_back(std::move(instr));
1007       idx++;
1008    }
1009
1010    if (block->register_demand.exceeds(ctx.target_pressure))
1011       local_next_use_distance = local_next_uses(ctx, block);
1012
1013    while (idx < block->instructions.size()) {
1014       aco_ptr<Instruction>& instr = block->instructions[idx];
1015
1016       std::map<Temp, std::pair<Temp, uint32_t>> reloads;
1017       std::map<Temp, uint32_t> spills;
1018       /* rename and reload operands */
1019       for (Operand& op : instr->operands) {
1020          if (!op.isTemp())
1021             continue;
1022          if (current_spills.find(op.getTemp()) == current_spills.end()) {
1023             /* the Operand is in register: check if it was renamed */
1024             if (ctx.renames[block_idx].find(op.getTemp()) != ctx.renames[block_idx].end())
1025                op.setTemp(ctx.renames[block_idx][op.getTemp()]);
1026             /* prevent it's definining instruction from being DCE'd if it could be rematerialized */
1027             if (ctx.remat.count(op.getTemp()))
1028                ctx.remat_used[ctx.remat[op.getTemp()].instr] = true;
1029             continue;
1030          }
1031          /* the Operand is spilled: add it to reloads */
1032          Temp new_tmp = {ctx.program->allocateId(), op.regClass()};
1033          ctx.renames[block_idx][op.getTemp()] = new_tmp;
1034          reloads[new_tmp] = std::make_pair(op.getTemp(), current_spills[op.getTemp()]);
1035          current_spills.erase(op.getTemp());
1036          op.setTemp(new_tmp);
1037          spilled_registers -= new_tmp;
1038       }
1039
1040       /* check if register demand is low enough before and after the current instruction */
1041       if (block->register_demand.exceeds(ctx.target_pressure)) {
1042
1043          RegisterDemand new_demand = ctx.register_demand[block_idx][idx];
1044          if (idx == 0) {
1045             RegisterDemand demand_before = new_demand;
1046             for (const Definition& def : instr->definitions)
1047                demand_before -= def.getTemp();
1048             for (const Operand& op : instr->operands) {
1049                if (op.isFirstKill())
1050                   demand_before += op.getTemp();
1051             }
1052             new_demand.update(demand_before);
1053          } else {
1054             new_demand.update(ctx.register_demand[block_idx][idx - 1]);
1055          }
1056
1057          assert(!local_next_use_distance.empty());
1058
1059          /* if reg pressure is too high, spill variable with furthest next use */
1060          while (RegisterDemand(new_demand - spilled_registers).exceeds(ctx.target_pressure)) {
1061             unsigned distance = 0;
1062             Temp to_spill;
1063             bool do_rematerialize = false;
1064             if (new_demand.vgpr - spilled_registers.vgpr > ctx.target_pressure.vgpr) {
1065                for (std::pair<Temp, uint32_t> pair : local_next_use_distance[idx]) {
1066                   bool can_rematerialize = ctx.remat.count(pair.first);
1067                   if (pair.first.type() == RegType::vgpr &&
1068                       ((pair.second > distance && can_rematerialize == do_rematerialize) ||
1069                        (can_rematerialize && !do_rematerialize && pair.second > idx)) &&
1070                       current_spills.find(pair.first) == current_spills.end() &&
1071                       ctx.spills_exit[block_idx].find(pair.first) == ctx.spills_exit[block_idx].end()) {
1072                      to_spill = pair.first;
1073                      distance = pair.second;
1074                      do_rematerialize = can_rematerialize;
1075                   }
1076                }
1077             } else {
1078                for (std::pair<Temp, uint32_t> pair : local_next_use_distance[idx]) {
1079                   bool can_rematerialize = ctx.remat.count(pair.first);
1080                   if (pair.first.type() == RegType::sgpr &&
1081                       ((pair.second > distance && can_rematerialize == do_rematerialize) ||
1082                        (can_rematerialize && !do_rematerialize && pair.second > idx)) &&
1083                       current_spills.find(pair.first) == current_spills.end() &&
1084                       ctx.spills_exit[block_idx].find(pair.first) == ctx.spills_exit[block_idx].end()) {
1085                      to_spill = pair.first;
1086                      distance = pair.second;
1087                      do_rematerialize = can_rematerialize;
1088                   }
1089                }
1090             }
1091
1092             assert(distance != 0 && distance > idx);
1093             uint32_t spill_id = ctx.allocate_spill_id(to_spill.regClass());
1094
1095             /* add interferences with currently spilled variables */
1096             for (std::pair<Temp, uint32_t> pair : current_spills) {
1097                ctx.interferences[spill_id].second.emplace(pair.second);
1098                ctx.interferences[pair.second].second.emplace(spill_id);
1099             }
1100             for (std::pair<Temp, std::pair<Temp, uint32_t>> pair : reloads) {
1101                ctx.interferences[spill_id].second.emplace(pair.second.second);
1102                ctx.interferences[pair.second.second].second.emplace(spill_id);
1103             }
1104
1105             current_spills[to_spill] = spill_id;
1106             spilled_registers += to_spill;
1107
1108             /* rename if necessary */
1109             if (ctx.renames[block_idx].find(to_spill) != ctx.renames[block_idx].end()) {
1110                to_spill = ctx.renames[block_idx][to_spill];
1111             }
1112
1113             /* add spill to new instructions */
1114             aco_ptr<Pseudo_instruction> spill{create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
1115             spill->operands[0] = Operand(to_spill);
1116             spill->operands[1] = Operand(spill_id);
1117             instructions.emplace_back(std::move(spill));
1118          }
1119       }
1120
1121       /* add reloads and instruction to new instructions */
1122       for (std::pair<Temp, std::pair<Temp, uint32_t>> pair : reloads) {
1123          aco_ptr<Instruction> reload = do_reload(ctx, pair.second.first, pair.first, pair.second.second);
1124          instructions.emplace_back(std::move(reload));
1125       }
1126       instructions.emplace_back(std::move(instr));
1127       idx++;
1128    }
1129
1130    block->instructions = std::move(instructions);
1131    ctx.spills_exit[block_idx].insert(current_spills.begin(), current_spills.end());
1132 }
1133
1134 void spill_block(spill_ctx& ctx, unsigned block_idx)
1135 {
1136    Block* block = &ctx.program->blocks[block_idx];
1137    ctx.processed[block_idx] = true;
1138
1139    /* determine set of variables which are spilled at the beginning of the block */
1140    RegisterDemand spilled_registers = init_live_in_vars(ctx, block, block_idx);
1141
1142    /* add interferences for spilled variables */
1143    for (std::pair<Temp, uint32_t> x : ctx.spills_entry[block_idx]) {
1144       for (std::pair<Temp, uint32_t> y : ctx.spills_entry[block_idx])
1145          if (x.second != y.second)
1146             ctx.interferences[x.second].second.emplace(y.second);
1147    }
1148
1149    bool is_loop_header = block->loop_nest_depth && ctx.loop_header.top()->index == block_idx;
1150    if (!is_loop_header) {
1151       /* add spill/reload code on incoming control flow edges */
1152       add_coupling_code(ctx, block, block_idx);
1153    }
1154
1155    std::map<Temp, uint32_t> current_spills = ctx.spills_entry[block_idx];
1156
1157    /* check conditions to process this block */
1158    bool process = RegisterDemand(block->register_demand - spilled_registers).exceeds(ctx.target_pressure) ||
1159                   !ctx.renames[block_idx].empty() ||
1160                   ctx.remat_used.size();
1161
1162    std::map<Temp, uint32_t>::iterator it = current_spills.begin();
1163    while (!process && it != current_spills.end()) {
1164       if (ctx.next_use_distances_start[block_idx][it->first].first == block_idx)
1165          process = true;
1166       ++it;
1167    }
1168
1169    if (process)
1170       process_block(ctx, block_idx, block, current_spills, spilled_registers);
1171    else
1172       ctx.spills_exit[block_idx].insert(current_spills.begin(), current_spills.end());
1173
1174    /* check if the next block leaves the current loop */
1175    if (block->loop_nest_depth == 0 || ctx.program->blocks[block_idx + 1].loop_nest_depth >= block->loop_nest_depth)
1176       return;
1177
1178    Block* loop_header = ctx.loop_header.top();
1179
1180    /* preserve original renames at end of loop header block */
1181    std::map<Temp, Temp> renames = std::move(ctx.renames[loop_header->index]);
1182
1183    /* add coupling code to all loop header predecessors */
1184    add_coupling_code(ctx, loop_header, loop_header->index);
1185
1186    /* update remat_used for phis added in add_coupling_code() */
1187    for (aco_ptr<Instruction>& instr : loop_header->instructions) {
1188       if (!is_phi(instr))
1189          break;
1190       for (const Operand& op : instr->operands) {
1191          if (op.isTemp() && ctx.remat.count(op.getTemp()))
1192             ctx.remat_used[ctx.remat[op.getTemp()].instr] = true;
1193       }
1194    }
1195
1196    /* propagate new renames through loop: i.e. repair the SSA */
1197    renames.swap(ctx.renames[loop_header->index]);
1198    for (std::pair<Temp, Temp> rename : renames) {
1199       for (unsigned idx = loop_header->index; idx <= block_idx; idx++) {
1200          Block& current = ctx.program->blocks[idx];
1201          std::vector<aco_ptr<Instruction>>::iterator instr_it = current.instructions.begin();
1202
1203          /* first rename phis */
1204          while (instr_it != current.instructions.end()) {
1205             aco_ptr<Instruction>& phi = *instr_it;
1206             if (phi->opcode != aco_opcode::p_phi && phi->opcode != aco_opcode::p_linear_phi)
1207                break;
1208             /* no need to rename the loop header phis once again. this happened in add_coupling_code() */
1209             if (idx == loop_header->index) {
1210                instr_it++;
1211                continue;
1212             }
1213
1214             for (Operand& op : phi->operands) {
1215                if (!op.isTemp())
1216                   continue;
1217                if (op.getTemp() == rename.first)
1218                   op.setTemp(rename.second);
1219             }
1220             instr_it++;
1221          }
1222
1223          std::map<Temp, std::pair<uint32_t, uint32_t>>::iterator it = ctx.next_use_distances_start[idx].find(rename.first);
1224
1225          /* variable is not live at beginning of this block */
1226          if (it == ctx.next_use_distances_start[idx].end())
1227             continue;
1228
1229          /* if the variable is live at the block's exit, add rename */
1230          if (ctx.next_use_distances_end[idx].find(rename.first) != ctx.next_use_distances_end[idx].end())
1231             ctx.renames[idx].insert(rename);
1232
1233          /* rename all uses in this block */
1234          bool renamed = false;
1235          while (!renamed && instr_it != current.instructions.end()) {
1236             aco_ptr<Instruction>& instr = *instr_it;
1237             for (Operand& op : instr->operands) {
1238                if (!op.isTemp())
1239                   continue;
1240                if (op.getTemp() == rename.first) {
1241                   op.setTemp(rename.second);
1242                   /* we can stop with this block as soon as the variable is spilled */
1243                   if (instr->opcode == aco_opcode::p_spill)
1244                     renamed = true;
1245                }
1246             }
1247             instr_it++;
1248          }
1249       }
1250    }
1251
1252    /* remove loop header info from stack */
1253    ctx.loop_header.pop();
1254 }
1255
1256 void assign_spill_slots(spill_ctx& ctx, unsigned spills_to_vgpr) {
1257    std::map<uint32_t, uint32_t> sgpr_slot;
1258    std::map<uint32_t, uint32_t> vgpr_slot;
1259    std::vector<bool> is_assigned(ctx.interferences.size());
1260
1261    /* first, handle affinities: just merge all interferences into both spill ids */
1262    for (std::vector<uint32_t>& vec : ctx.affinities) {
1263       for (unsigned i = 0; i < vec.size(); i++) {
1264          for (unsigned j = i + 1; j < vec.size(); j++) {
1265             assert(vec[i] != vec[j]);
1266             for (uint32_t id : ctx.interferences[vec[i]].second)
1267                ctx.interferences[id].second.insert(vec[j]);
1268             for (uint32_t id : ctx.interferences[vec[j]].second)
1269                ctx.interferences[id].second.insert(vec[i]);
1270             ctx.interferences[vec[i]].second.insert(ctx.interferences[vec[j]].second.begin(), ctx.interferences[vec[j]].second.end());
1271             ctx.interferences[vec[j]].second.insert(ctx.interferences[vec[i]].second.begin(), ctx.interferences[vec[i]].second.end());
1272
1273             bool reloaded = ctx.is_reloaded[vec[i]] || ctx.is_reloaded[vec[j]];
1274             ctx.is_reloaded[vec[i]] = reloaded;
1275             ctx.is_reloaded[vec[j]] = reloaded;
1276          }
1277       }
1278    }
1279    for (ASSERTED uint32_t i = 0; i < ctx.interferences.size(); i++)
1280       for (ASSERTED uint32_t id : ctx.interferences[i].second)
1281          assert(i != id);
1282
1283    /* for each spill slot, assign as many spill ids as possible */
1284    std::vector<std::set<uint32_t>> spill_slot_interferences;
1285    unsigned slot_idx = 0;
1286    bool done = false;
1287
1288    /* assign sgpr spill slots */
1289    while (!done) {
1290       done = true;
1291       for (unsigned id = 0; id < ctx.interferences.size(); id++) {
1292          if (is_assigned[id] || !ctx.is_reloaded[id])
1293             continue;
1294          if (ctx.interferences[id].first.type() != RegType::sgpr)
1295             continue;
1296
1297          /* check interferences */
1298          bool interferes = false;
1299          for (unsigned i = slot_idx; i < slot_idx + ctx.interferences[id].first.size(); i++) {
1300             if (i == spill_slot_interferences.size())
1301                spill_slot_interferences.emplace_back(std::set<uint32_t>());
1302             if (spill_slot_interferences[i].find(id) != spill_slot_interferences[i].end() || i / 64 != slot_idx / 64) {
1303                interferes = true;
1304                break;
1305             }
1306          }
1307          if (interferes) {
1308             done = false;
1309             continue;
1310          }
1311
1312          /* we found a spill id which can be assigned to current spill slot */
1313          sgpr_slot[id] = slot_idx;
1314          is_assigned[id] = true;
1315          for (unsigned i = slot_idx; i < slot_idx + ctx.interferences[id].first.size(); i++)
1316             spill_slot_interferences[i].insert(ctx.interferences[id].second.begin(), ctx.interferences[id].second.end());
1317
1318          /* add all affinities: there are no additional interferences */
1319          for (std::vector<uint32_t>& vec : ctx.affinities) {
1320             bool found_affinity = false;
1321             for (uint32_t entry : vec) {
1322                if (entry == id) {
1323                   found_affinity = true;
1324                   break;
1325                }
1326             }
1327             if (!found_affinity)
1328                continue;
1329             for (uint32_t entry : vec) {
1330                sgpr_slot[entry] = slot_idx;
1331                is_assigned[entry] = true;
1332             }
1333          }
1334       }
1335       slot_idx++;
1336    }
1337
1338    slot_idx = 0;
1339    done = false;
1340
1341    /* assign vgpr spill slots */
1342    while (!done) {
1343       done = true;
1344       for (unsigned id = 0; id < ctx.interferences.size(); id++) {
1345          if (is_assigned[id] || !ctx.is_reloaded[id])
1346             continue;
1347          if (ctx.interferences[id].first.type() != RegType::vgpr)
1348             continue;
1349
1350          /* check interferences */
1351          bool interferes = false;
1352          for (unsigned i = slot_idx; i < slot_idx + ctx.interferences[id].first.size(); i++) {
1353             if (i == spill_slot_interferences.size())
1354                spill_slot_interferences.emplace_back(std::set<uint32_t>());
1355             /* check for interference and ensure that vector regs are stored next to each other */
1356             if (spill_slot_interferences[i].find(id) != spill_slot_interferences[i].end() || i / 64 != slot_idx / 64) {
1357                interferes = true;
1358                break;
1359             }
1360          }
1361          if (interferes) {
1362             done = false;
1363             continue;
1364          }
1365
1366          /* we found a spill id which can be assigned to current spill slot */
1367          vgpr_slot[id] = slot_idx;
1368          is_assigned[id] = true;
1369          for (unsigned i = slot_idx; i < slot_idx + ctx.interferences[id].first.size(); i++)
1370             spill_slot_interferences[i].insert(ctx.interferences[id].second.begin(), ctx.interferences[id].second.end());
1371       }
1372       slot_idx++;
1373    }
1374
1375    for (unsigned id = 0; id < is_assigned.size(); id++)
1376       assert(is_assigned[id] || !ctx.is_reloaded[id]);
1377
1378    for (std::vector<uint32_t>& vec : ctx.affinities) {
1379       for (unsigned i = 0; i < vec.size(); i++) {
1380          for (unsigned j = i + 1; j < vec.size(); j++) {
1381             assert(is_assigned[vec[i]] == is_assigned[vec[j]]);
1382             if (!is_assigned[vec[i]])
1383                continue;
1384             assert(ctx.is_reloaded[vec[i]] == ctx.is_reloaded[vec[j]]);
1385             assert(ctx.interferences[vec[i]].first.type() == ctx.interferences[vec[j]].first.type());
1386             if (ctx.interferences[vec[i]].first.type() == RegType::sgpr)
1387                assert(sgpr_slot[vec[i]] == sgpr_slot[vec[j]]);
1388             else
1389                assert(vgpr_slot[vec[i]] == vgpr_slot[vec[j]]);
1390          }
1391       }
1392    }
1393
1394    /* hope, we didn't mess up */
1395    std::vector<Temp> vgpr_spill_temps((spill_slot_interferences.size() + 63) / 64);
1396    assert(vgpr_spill_temps.size() <= spills_to_vgpr);
1397
1398    /* replace pseudo instructions with actual hardware instructions */
1399    unsigned last_top_level_block_idx = 0;
1400    std::vector<bool> reload_in_loop(vgpr_spill_temps.size());
1401    for (Block& block : ctx.program->blocks) {
1402
1403       /* after loops, we insert a user if there was a reload inside the loop */
1404       if (block.loop_nest_depth == 0) {
1405          int end_vgprs = 0;
1406          for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1407             if (reload_in_loop[i])
1408                end_vgprs++;
1409          }
1410
1411          if (end_vgprs > 0) {
1412             aco_ptr<Instruction> destr{create_instruction<Pseudo_instruction>(aco_opcode::p_end_linear_vgpr, Format::PSEUDO, end_vgprs, 0)};
1413             int k = 0;
1414             for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1415                if (reload_in_loop[i])
1416                   destr->operands[k++] = Operand(vgpr_spill_temps[i]);
1417                reload_in_loop[i] = false;
1418             }
1419             /* find insertion point */
1420             std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
1421             while ((*it)->opcode == aco_opcode::p_linear_phi || (*it)->opcode == aco_opcode::p_phi)
1422                ++it;
1423             block.instructions.insert(it, std::move(destr));
1424          }
1425       }
1426
1427       if (block.kind & block_kind_top_level && !block.linear_preds.empty()) {
1428          last_top_level_block_idx = block.index;
1429
1430          /* check if any spilled variables use a created linear vgpr, otherwise destroy them */
1431          for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1432             if (vgpr_spill_temps[i] == Temp())
1433                continue;
1434
1435             bool can_destroy = true;
1436             for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[block.linear_preds[0]]) {
1437
1438                if (sgpr_slot.find(pair.second) != sgpr_slot.end() &&
1439                    sgpr_slot[pair.second] / 64 == i) {
1440                   can_destroy = false;
1441                   break;
1442                }
1443             }
1444             if (can_destroy)
1445                vgpr_spill_temps[i] = Temp();
1446          }
1447       }
1448
1449       std::vector<aco_ptr<Instruction>>::iterator it;
1450       std::vector<aco_ptr<Instruction>> instructions;
1451       instructions.reserve(block.instructions.size());
1452       for (it = block.instructions.begin(); it != block.instructions.end(); ++it) {
1453
1454          if ((*it)->opcode == aco_opcode::p_spill) {
1455             uint32_t spill_id = (*it)->operands[1].constantValue();
1456
1457             if (!ctx.is_reloaded[spill_id]) {
1458                /* never reloaded, so don't spill */
1459             } else if (vgpr_slot.find(spill_id) != vgpr_slot.end()) {
1460                /* spill vgpr */
1461                ctx.program->config->spilled_vgprs += (*it)->operands[0].size();
1462
1463                assert(false && "vgpr spilling not yet implemented.");
1464             } else if (sgpr_slot.find(spill_id) != sgpr_slot.end()) {
1465                ctx.program->config->spilled_sgprs += (*it)->operands[0].size();
1466
1467                uint32_t spill_slot = sgpr_slot[spill_id];
1468
1469                /* check if the linear vgpr already exists */
1470                if (vgpr_spill_temps[spill_slot / 64] == Temp()) {
1471                   Temp linear_vgpr = {ctx.program->allocateId(), v1.as_linear()};
1472                   vgpr_spill_temps[spill_slot / 64] = linear_vgpr;
1473                   aco_ptr<Pseudo_instruction> create{create_instruction<Pseudo_instruction>(aco_opcode::p_start_linear_vgpr, Format::PSEUDO, 0, 1)};
1474                   create->definitions[0] = Definition(linear_vgpr);
1475                   /* find the right place to insert this definition */
1476                   if (last_top_level_block_idx == block.index) {
1477                      /* insert right before the current instruction */
1478                      instructions.emplace_back(std::move(create));
1479                   } else {
1480                      assert(last_top_level_block_idx < block.index);
1481                      /* insert before the branch at last top level block */
1482                      std::vector<aco_ptr<Instruction>>& instructions = ctx.program->blocks[last_top_level_block_idx].instructions;
1483                      instructions.insert(std::next(instructions.begin(), instructions.size() - 1), std::move(create));
1484                   }
1485                }
1486
1487                /* spill sgpr: just add the vgpr temp to operands */
1488                Pseudo_instruction* spill = create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 3, 0);
1489                spill->operands[0] = Operand(vgpr_spill_temps[spill_slot / 64]);
1490                spill->operands[1] = Operand(spill_slot % 64);
1491                spill->operands[2] = (*it)->operands[0];
1492                instructions.emplace_back(aco_ptr<Instruction>(spill));
1493             } else {
1494                unreachable("No spill slot assigned for spill id");
1495             }
1496
1497          } else if ((*it)->opcode == aco_opcode::p_reload) {
1498             uint32_t spill_id = (*it)->operands[0].constantValue();
1499             assert(ctx.is_reloaded[spill_id]);
1500
1501             if (vgpr_slot.find(spill_id) != vgpr_slot.end()) {
1502                /* reload vgpr */
1503                assert(false && "vgpr spilling not yet implemented.");
1504
1505             } else if (sgpr_slot.find(spill_id) != sgpr_slot.end()) {
1506                uint32_t spill_slot = sgpr_slot[spill_id];
1507                reload_in_loop[spill_slot / 64] = block.loop_nest_depth > 0;
1508
1509                /* check if the linear vgpr already exists */
1510                if (vgpr_spill_temps[spill_slot / 64] == Temp()) {
1511                   Temp linear_vgpr = {ctx.program->allocateId(), v1.as_linear()};
1512                   vgpr_spill_temps[spill_slot / 64] = linear_vgpr;
1513                   aco_ptr<Pseudo_instruction> create{create_instruction<Pseudo_instruction>(aco_opcode::p_start_linear_vgpr, Format::PSEUDO, 0, 1)};
1514                   create->definitions[0] = Definition(linear_vgpr);
1515                   /* find the right place to insert this definition */
1516                   if (last_top_level_block_idx == block.index) {
1517                      /* insert right before the current instruction */
1518                      instructions.emplace_back(std::move(create));
1519                   } else {
1520                      assert(last_top_level_block_idx < block.index);
1521                      /* insert before the branch at last top level block */
1522                      std::vector<aco_ptr<Instruction>>& instructions = ctx.program->blocks[last_top_level_block_idx].instructions;
1523                      instructions.insert(std::next(instructions.begin(), instructions.size() - 1), std::move(create));
1524                   }
1525                }
1526
1527                /* reload sgpr: just add the vgpr temp to operands */
1528                Pseudo_instruction* reload = create_instruction<Pseudo_instruction>(aco_opcode::p_reload, Format::PSEUDO, 2, 1);
1529                reload->operands[0] = Operand(vgpr_spill_temps[spill_slot / 64]);
1530                reload->operands[1] = Operand(spill_slot % 64);
1531                reload->definitions[0] = (*it)->definitions[0];
1532                instructions.emplace_back(aco_ptr<Instruction>(reload));
1533             } else {
1534                unreachable("No spill slot assigned for spill id");
1535             }
1536          } else if (!ctx.remat_used.count(it->get()) || ctx.remat_used[it->get()]) {
1537             instructions.emplace_back(std::move(*it));
1538          }
1539
1540       }
1541       block.instructions = std::move(instructions);
1542    }
1543
1544    /* SSA elimination inserts copies for logical phis right before p_logical_end
1545     * So if a linear vgpr is used between that p_logical_end and the branch,
1546     * we need to ensure logical phis don't choose a definition which aliases
1547     * the linear vgpr.
1548     * TODO: Moving the spills and reloads to before p_logical_end might produce
1549     *       slightly better code. */
1550    for (Block& block : ctx.program->blocks) {
1551       /* loops exits are already handled */
1552       if (block.logical_preds.size() <= 1)
1553          continue;
1554
1555       bool has_logical_phis = false;
1556       for (aco_ptr<Instruction>& instr : block.instructions) {
1557          if (instr->opcode == aco_opcode::p_phi) {
1558             has_logical_phis = true;
1559             break;
1560          } else if (instr->opcode != aco_opcode::p_linear_phi) {
1561             break;
1562          }
1563       }
1564       if (!has_logical_phis)
1565          continue;
1566
1567       std::set<Temp> vgprs;
1568       for (unsigned pred_idx : block.logical_preds) {
1569          Block& pred = ctx.program->blocks[pred_idx];
1570          for (int i = pred.instructions.size() - 1; i >= 0; i--) {
1571             aco_ptr<Instruction>& pred_instr = pred.instructions[i];
1572             if (pred_instr->opcode == aco_opcode::p_logical_end) {
1573                break;
1574             } else if (pred_instr->opcode == aco_opcode::p_spill ||
1575                        pred_instr->opcode == aco_opcode::p_reload) {
1576                vgprs.insert(pred_instr->operands[0].getTemp());
1577             }
1578          }
1579       }
1580       if (!vgprs.size())
1581          continue;
1582
1583       aco_ptr<Instruction> destr{create_instruction<Pseudo_instruction>(aco_opcode::p_end_linear_vgpr, Format::PSEUDO, vgprs.size(), 0)};
1584       int k = 0;
1585       for (Temp tmp : vgprs) {
1586          destr->operands[k++] = Operand(tmp);
1587       }
1588       /* find insertion point */
1589       std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
1590       while ((*it)->opcode == aco_opcode::p_linear_phi || (*it)->opcode == aco_opcode::p_phi)
1591          ++it;
1592       block.instructions.insert(it, std::move(destr));
1593    }
1594 }
1595
1596 } /* end namespace */
1597
1598
1599 void spill(Program* program, live& live_vars, const struct radv_nir_compiler_options *options)
1600 {
1601    program->config->spilled_vgprs = 0;
1602    program->config->spilled_sgprs = 0;
1603
1604    /* no spilling when register pressure is low enough */
1605    if (program->num_waves > 0)
1606       return;
1607
1608    /* lower to CSSA before spilling to ensure correctness w.r.t. phis */
1609    lower_to_cssa(program, live_vars, options);
1610
1611    /* calculate target register demand */
1612    RegisterDemand register_target = program->max_reg_demand;
1613    if (register_target.sgpr > program->sgpr_limit)
1614       register_target.vgpr += (register_target.sgpr - program->sgpr_limit + 63 + 32) / 64;
1615    register_target.sgpr = program->sgpr_limit;
1616
1617    if (register_target.vgpr > program->vgpr_limit)
1618       register_target.sgpr = program->sgpr_limit - 5;
1619    register_target.vgpr = program->vgpr_limit - (register_target.vgpr - program->max_reg_demand.vgpr);
1620
1621    int spills_to_vgpr = (program->max_reg_demand.sgpr - register_target.sgpr + 63 + 32) / 64;
1622
1623    /* initialize ctx */
1624    spill_ctx ctx(register_target, program, live_vars.register_demand);
1625    compute_global_next_uses(ctx, live_vars.live_out);
1626    get_rematerialize_info(ctx);
1627
1628    /* create spills and reloads */
1629    for (unsigned i = 0; i < program->blocks.size(); i++)
1630       spill_block(ctx, i);
1631
1632    /* assign spill slots and DCE rematerialized code */
1633    assign_spill_slots(ctx, spills_to_vgpr);
1634
1635    /* update live variable information */
1636    live_vars = live_var_analysis(program, options);
1637
1638    assert(program->num_waves >= 0);
1639 }
1640
1641 }
1642