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_builder.h"
27#include "aco_ir.h"
28
29#include "common/sid.h"
30
31#include <algorithm>
32#include <cstring>
33#include <map>
34#include <set>
35#include <stack>
36#include <unordered_map>
37#include <unordered_set>
38#include <vector>
39
40namespace std {
41template <> struct hash<aco::Temp> {
42   size_t operator()(aco::Temp temp) const noexcept
43   {
44      uint32_t v;
45      std::memcpy(&v, &temp, sizeof(temp));
46      return std::hash<uint32_t>{}(v);
47   }
48};
49} // namespace std
50
51/*
52 * Implements the spilling algorithm on SSA-form from
53 * "Register Spilling and Live-Range Splitting for SSA-Form Programs"
54 * by Matthias Braun and Sebastian Hack.
55 */
56
57namespace aco {
58
59namespace {
60
61struct remat_info {
62   Instruction* instr;
63};
64
65struct spill_ctx {
66   RegisterDemand target_pressure;
67   Program* program;
68   std::vector<std::vector<RegisterDemand>> register_demand;
69   std::vector<std::map<Temp, Temp>> renames;
70   std::vector<std::unordered_map<Temp, uint32_t>> spills_entry;
71   std::vector<std::unordered_map<Temp, uint32_t>> spills_exit;
72
73   std::vector<bool> processed;
74   std::stack<Block*, std::vector<Block*>> loop_header;
75   std::vector<std::unordered_map<Temp, std::pair<uint32_t, uint32_t>>> next_use_distances_start;
76   std::vector<std::unordered_map<Temp, std::pair<uint32_t, uint32_t>>> next_use_distances_end;
77   std::vector<std::vector<std::pair<Temp, uint32_t>>> local_next_use_distance; /* Working buffer */
78   std::vector<std::pair<RegClass, std::unordered_set<uint32_t>>> interferences;
79   std::vector<std::vector<uint32_t>> affinities;
80   std::vector<bool> is_reloaded;
81   std::unordered_map<Temp, remat_info> remat;
82   std::set<Instruction*> unused_remats;
83   unsigned wave_size;
84
85   unsigned sgpr_spill_slots;
86   unsigned vgpr_spill_slots;
87   Temp scratch_rsrc;
88
89   spill_ctx(const RegisterDemand target_pressure_, Program* program_,
90             std::vector<std::vector<RegisterDemand>> register_demand_)
91       : target_pressure(target_pressure_), program(program_),
92         register_demand(std::move(register_demand_)), renames(program->blocks.size()),
93         spills_entry(program->blocks.size()), spills_exit(program->blocks.size()),
94         processed(program->blocks.size(), false), wave_size(program->wave_size),
95         sgpr_spill_slots(0), vgpr_spill_slots(0)
96   {}
97
98   void add_affinity(uint32_t first, uint32_t second)
99   {
100      unsigned found_first = affinities.size();
101      unsigned found_second = affinities.size();
102      for (unsigned i = 0; i < affinities.size(); i++) {
103         std::vector<uint32_t>& vec = affinities[i];
104         for (uint32_t entry : vec) {
105            if (entry == first)
106               found_first = i;
107            else if (entry == second)
108               found_second = i;
109         }
110      }
111      if (found_first == affinities.size() && found_second == affinities.size()) {
112         affinities.emplace_back(std::vector<uint32_t>({first, second}));
113      } else if (found_first < affinities.size() && found_second == affinities.size()) {
114         affinities[found_first].push_back(second);
115      } else if (found_second < affinities.size() && found_first == affinities.size()) {
116         affinities[found_second].push_back(first);
117      } else if (found_first != found_second) {
118         /* merge second into first */
119         affinities[found_first].insert(affinities[found_first].end(),
120                                        affinities[found_second].begin(),
121                                        affinities[found_second].end());
122         affinities.erase(std::next(affinities.begin(), found_second));
123      } else {
124         assert(found_first == found_second);
125      }
126   }
127
128   void add_interference(uint32_t first, uint32_t second)
129   {
130      if (interferences[first].first.type() != interferences[second].first.type())
131         return;
132
133      bool inserted = interferences[first].second.insert(second).second;
134      if (inserted)
135         interferences[second].second.insert(first);
136   }
137
138   uint32_t allocate_spill_id(RegClass rc)
139   {
140      interferences.emplace_back(rc, std::unordered_set<uint32_t>());
141      is_reloaded.push_back(false);
142      return next_spill_id++;
143   }
144
145   uint32_t next_spill_id = 0;
146};
147
148int32_t
149get_dominator(int idx_a, int idx_b, Program* program, bool is_linear)
150{
151
152   if (idx_a == -1)
153      return idx_b;
154   if (idx_b == -1)
155      return idx_a;
156   if (is_linear) {
157      while (idx_a != idx_b) {
158         if (idx_a > idx_b)
159            idx_a = program->blocks[idx_a].linear_idom;
160         else
161            idx_b = program->blocks[idx_b].linear_idom;
162      }
163   } else {
164      while (idx_a != idx_b) {
165         if (idx_a > idx_b)
166            idx_a = program->blocks[idx_a].logical_idom;
167         else
168            idx_b = program->blocks[idx_b].logical_idom;
169      }
170   }
171   assert(idx_a != -1);
172   return idx_a;
173}
174
175void
176next_uses_per_block(spill_ctx& ctx, unsigned block_idx, uint32_t& worklist)
177{
178   Block* block = &ctx.program->blocks[block_idx];
179   ctx.next_use_distances_start[block_idx] = ctx.next_use_distances_end[block_idx];
180   auto& next_use_distances_start = ctx.next_use_distances_start[block_idx];
181
182   /* to compute the next use distance at the beginning of the block, we have to add the block's
183    * size */
184   for (std::unordered_map<Temp, std::pair<uint32_t, uint32_t>>::iterator it =
185           next_use_distances_start.begin();
186        it != next_use_distances_start.end(); ++it)
187      it->second.second = it->second.second + block->instructions.size();
188
189   int idx = block->instructions.size() - 1;
190   while (idx >= 0) {
191      aco_ptr<Instruction>& instr = block->instructions[idx];
192
193      if (instr->opcode == aco_opcode::p_linear_phi || instr->opcode == aco_opcode::p_phi)
194         break;
195
196      for (const Definition& def : instr->definitions) {
197         if (def.isTemp())
198            next_use_distances_start.erase(def.getTemp());
199      }
200
201      for (const Operand& op : instr->operands) {
202         /* omit exec mask */
203         if (op.isFixed() && op.physReg() == exec)
204            continue;
205         if (op.regClass().type() == RegType::vgpr && op.regClass().is_linear())
206            continue;
207         if (op.isTemp())
208            next_use_distances_start[op.getTemp()] = {block_idx, idx};
209      }
210      idx--;
211   }
212
213   assert(block_idx != 0 || next_use_distances_start.empty());
214   std::unordered_set<Temp> phi_defs;
215   while (idx >= 0) {
216      aco_ptr<Instruction>& instr = block->instructions[idx];
217      assert(instr->opcode == aco_opcode::p_linear_phi || instr->opcode == aco_opcode::p_phi);
218
219      std::pair<uint32_t, uint32_t> distance{block_idx, 0};
220
221      auto it = instr->definitions[0].isTemp() ? next_use_distances_start.find(instr->definitions[0].getTemp())
222                                               : next_use_distances_start.end();
223      if (it != next_use_distances_start.end() &&
224         phi_defs.insert(instr->definitions[0].getTemp()).second) {
225         distance = it->second;
226      }
227
228      for (unsigned i = 0; i < instr->operands.size(); i++) {
229         unsigned pred_idx =
230            instr->opcode == aco_opcode::p_phi ? block->logical_preds[i] : block->linear_preds[i];
231         if (instr->operands[i].isTemp()) {
232            auto insert_result = ctx.next_use_distances_end[pred_idx].insert(
233               std::make_pair(instr->operands[i].getTemp(), distance));
234            const bool inserted = insert_result.second;
235            std::pair<uint32_t, uint32_t>& entry_distance = insert_result.first->second;
236            if (inserted || entry_distance != distance)
237               worklist = std::max(worklist, pred_idx + 1);
238            entry_distance = distance;
239         }
240      }
241      idx--;
242   }
243
244   /* all remaining live vars must be live-out at the predecessors */
245   for (std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair : next_use_distances_start) {
246      Temp temp = pair.first;
247      if (phi_defs.count(temp)) {
248         continue;
249      }
250      uint32_t distance = pair.second.second;
251      uint32_t dom = pair.second.first;
252      std::vector<unsigned>& preds = temp.is_linear() ? block->linear_preds : block->logical_preds;
253      for (unsigned pred_idx : preds) {
254         if (ctx.program->blocks[pred_idx].loop_nest_depth > block->loop_nest_depth)
255            distance += 0xFFFF;
256         auto insert_result = ctx.next_use_distances_end[pred_idx].insert(
257            std::make_pair(temp, std::pair<uint32_t, uint32_t>{}));
258         const bool inserted = insert_result.second;
259         std::pair<uint32_t, uint32_t>& entry_distance = insert_result.first->second;
260
261         if (!inserted) {
262            dom = get_dominator(dom, entry_distance.first, ctx.program, temp.is_linear());
263            distance = std::min(entry_distance.second, distance);
264         }
265         if (entry_distance != std::pair<uint32_t, uint32_t>{dom, distance}) {
266            worklist = std::max(worklist, pred_idx + 1);
267            entry_distance = {dom, distance};
268         }
269      }
270   }
271}
272
273void
274compute_global_next_uses(spill_ctx& ctx)
275{
276   ctx.next_use_distances_start.resize(ctx.program->blocks.size());
277   ctx.next_use_distances_end.resize(ctx.program->blocks.size());
278
279   uint32_t worklist = ctx.program->blocks.size();
280   while (worklist) {
281      unsigned block_idx = --worklist;
282      next_uses_per_block(ctx, block_idx, worklist);
283   }
284}
285
286bool
287should_rematerialize(aco_ptr<Instruction>& instr)
288{
289   /* TODO: rematerialization is only supported for VOP1, SOP1 and PSEUDO */
290   if (instr->format != Format::VOP1 && instr->format != Format::SOP1 &&
291       instr->format != Format::PSEUDO && instr->format != Format::SOPK)
292      return false;
293   /* TODO: pseudo-instruction rematerialization is only supported for
294    * p_create_vector/p_parallelcopy */
295   if (instr->isPseudo() && instr->opcode != aco_opcode::p_create_vector &&
296       instr->opcode != aco_opcode::p_parallelcopy)
297      return false;
298   if (instr->isSOPK() && instr->opcode != aco_opcode::s_movk_i32)
299      return false;
300
301   for (const Operand& op : instr->operands) {
302      /* TODO: rematerialization using temporaries isn't yet supported */
303      if (!op.isConstant())
304         return false;
305   }
306
307   /* TODO: rematerialization with multiple definitions isn't yet supported */
308   if (instr->definitions.size() > 1)
309      return false;
310
311   return true;
312}
313
314aco_ptr<Instruction>
315do_reload(spill_ctx& ctx, Temp tmp, Temp new_name, uint32_t spill_id)
316{
317   std::unordered_map<Temp, remat_info>::iterator remat = ctx.remat.find(tmp);
318   if (remat != ctx.remat.end()) {
319      Instruction* instr = remat->second.instr;
320      assert((instr->isVOP1() || instr->isSOP1() || instr->isPseudo() || instr->isSOPK()) &&
321             "unsupported");
322      assert((instr->format != Format::PSEUDO || instr->opcode == aco_opcode::p_create_vector ||
323              instr->opcode == aco_opcode::p_parallelcopy) &&
324             "unsupported");
325      assert(instr->definitions.size() == 1 && "unsupported");
326
327      aco_ptr<Instruction> res;
328      if (instr->isVOP1()) {
329         res.reset(create_instruction<VOP1_instruction>(
330            instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
331      } else if (instr->isSOP1()) {
332         res.reset(create_instruction<SOP1_instruction>(
333            instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
334      } else if (instr->isPseudo()) {
335         res.reset(create_instruction<Pseudo_instruction>(
336            instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
337      } else if (instr->isSOPK()) {
338         res.reset(create_instruction<SOPK_instruction>(
339            instr->opcode, instr->format, instr->operands.size(), instr->definitions.size()));
340         res->sopk().imm = instr->sopk().imm;
341      }
342      for (unsigned i = 0; i < instr->operands.size(); i++) {
343         res->operands[i] = instr->operands[i];
344         if (instr->operands[i].isTemp()) {
345            assert(false && "unsupported");
346            if (ctx.remat.count(instr->operands[i].getTemp()))
347               ctx.unused_remats.erase(ctx.remat[instr->operands[i].getTemp()].instr);
348         }
349      }
350      res->definitions[0] = Definition(new_name);
351      return res;
352   } else {
353      aco_ptr<Pseudo_instruction> reload{
354         create_instruction<Pseudo_instruction>(aco_opcode::p_reload, Format::PSEUDO, 1, 1)};
355      reload->operands[0] = Operand::c32(spill_id);
356      reload->definitions[0] = Definition(new_name);
357      ctx.is_reloaded[spill_id] = true;
358      return reload;
359   }
360}
361
362void
363get_rematerialize_info(spill_ctx& ctx)
364{
365   for (Block& block : ctx.program->blocks) {
366      bool logical = false;
367      for (aco_ptr<Instruction>& instr : block.instructions) {
368         if (instr->opcode == aco_opcode::p_logical_start)
369            logical = true;
370         else if (instr->opcode == aco_opcode::p_logical_end)
371            logical = false;
372         if (logical && should_rematerialize(instr)) {
373            for (const Definition& def : instr->definitions) {
374               if (def.isTemp()) {
375                  ctx.remat[def.getTemp()] = remat_info{instr.get()};
376                  ctx.unused_remats.insert(instr.get());
377               }
378            }
379         }
380      }
381   }
382}
383
384void
385update_local_next_uses(spill_ctx& ctx, Block* block,
386                std::vector<std::vector<std::pair<Temp, uint32_t>>>& local_next_uses)
387{
388   if (local_next_uses.size() < block->instructions.size()) {
389      /* Allocate more next-use-maps. Note that by never reducing the vector size, we enable
390       * future calls to this function to re-use already allocated map memory. */
391      local_next_uses.resize(block->instructions.size());
392   }
393
394   local_next_uses[block->instructions.size() - 1].clear();
395   for (std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair :
396        ctx.next_use_distances_end[block->index]) {
397      local_next_uses[block->instructions.size() - 1].push_back(std::make_pair<Temp, uint32_t>(
398         (Temp)pair.first, pair.second.second + block->instructions.size()));
399   }
400
401   for (int idx = block->instructions.size() - 1; idx >= 0; idx--) {
402      aco_ptr<Instruction>& instr = block->instructions[idx];
403      if (!instr)
404         break;
405      if (instr->opcode == aco_opcode::p_phi || instr->opcode == aco_opcode::p_linear_phi)
406         break;
407
408      if (idx != (int)block->instructions.size() - 1) {
409         local_next_uses[idx] = local_next_uses[idx + 1];
410      }
411
412      for (const Operand& op : instr->operands) {
413         if (op.isFixed() && op.physReg() == exec)
414            continue;
415         if (op.regClass().type() == RegType::vgpr && op.regClass().is_linear())
416            continue;
417         if (op.isTemp()) {
418            auto it = std::find_if(local_next_uses[idx].begin(), local_next_uses[idx].end(),
419                                   [op](auto& pair) { return pair.first == op.getTemp(); });
420            if (it == local_next_uses[idx].end()) {
421               local_next_uses[idx].push_back(std::make_pair<Temp, uint32_t>(op.getTemp(), idx));
422            } else {
423               it->second = idx;
424            }
425         }
426      }
427      for (const Definition& def : instr->definitions) {
428         if (def.isTemp()) {
429            auto it = std::find_if(local_next_uses[idx].begin(), local_next_uses[idx].end(),
430                                   [def](auto& pair) { return pair.first == def.getTemp(); });
431            if (it != local_next_uses[idx].end()) {
432               local_next_uses[idx].erase(it);
433            }
434         }
435      }
436   }
437}
438
439RegisterDemand
440get_demand_before(spill_ctx& ctx, unsigned block_idx, unsigned idx)
441{
442   if (idx == 0) {
443      RegisterDemand demand = ctx.register_demand[block_idx][idx];
444      aco_ptr<Instruction>& instr = ctx.program->blocks[block_idx].instructions[idx];
445      aco_ptr<Instruction> instr_before(nullptr);
446      return get_demand_before(demand, instr, instr_before);
447   } else {
448      return ctx.register_demand[block_idx][idx - 1];
449   }
450}
451
452RegisterDemand
453get_live_in_demand(spill_ctx& ctx, unsigned block_idx)
454{
455   unsigned idx = 0;
456   RegisterDemand reg_pressure = RegisterDemand();
457   Block& block = ctx.program->blocks[block_idx];
458   for (aco_ptr<Instruction>& phi : block.instructions) {
459      if (!is_phi(phi))
460         break;
461      idx++;
462
463      /* Killed phi definitions increase pressure in the predecessor but not
464       * the block they're in. Since the loops below are both to control
465       * pressure of the start of this block and the ends of it's
466       * predecessors, we need to count killed unspilled phi definitions here. */
467      if (phi->definitions[0].isTemp() && phi->definitions[0].isKill() &&
468          !ctx.spills_entry[block_idx].count(phi->definitions[0].getTemp()))
469         reg_pressure += phi->definitions[0].getTemp();
470   }
471
472   reg_pressure += get_demand_before(ctx, block_idx, idx);
473
474   /* Consider register pressure from linear predecessors. This can affect
475    * reg_pressure if the branch instructions define sgprs. */
476   for (unsigned pred : block.linear_preds)
477      reg_pressure.sgpr =
478         std::max<int16_t>(reg_pressure.sgpr, ctx.register_demand[pred].back().sgpr);
479
480   return reg_pressure;
481}
482
483RegisterDemand
484init_live_in_vars(spill_ctx& ctx, Block* block, unsigned block_idx)
485{
486   RegisterDemand spilled_registers;
487
488   /* first block, nothing was spilled before */
489   if (block_idx == 0)
490      return {0, 0};
491
492   /* next use distances at the beginning of the current block */
493   const auto& next_use_distances = ctx.next_use_distances_start[block_idx];
494
495   /* loop header block */
496   if (block->loop_nest_depth > ctx.program->blocks[block_idx - 1].loop_nest_depth) {
497      assert(block->linear_preds[0] == block_idx - 1);
498      assert(block->logical_preds[0] == block_idx - 1);
499
500      /* create new loop_info */
501      ctx.loop_header.emplace(block);
502
503      /* check how many live-through variables should be spilled */
504      RegisterDemand reg_pressure = get_live_in_demand(ctx, block_idx);
505      RegisterDemand loop_demand = reg_pressure;
506      unsigned i = block_idx;
507      while (ctx.program->blocks[i].loop_nest_depth >= block->loop_nest_depth) {
508         assert(ctx.program->blocks.size() > i);
509         loop_demand.update(ctx.program->blocks[i++].register_demand);
510      }
511      unsigned loop_end = i;
512
513      for (auto spilled : ctx.spills_exit[block_idx - 1]) {
514         auto it = next_use_distances.find(spilled.first);
515
516         /* variable is not live at loop entry: probably a phi operand */
517         if (it == next_use_distances.end())
518            continue;
519
520         /* keep constants and live-through variables spilled */
521         if (it->second.first >= loop_end || ctx.remat.count(spilled.first)) {
522            ctx.spills_entry[block_idx][spilled.first] = spilled.second;
523            spilled_registers += spilled.first;
524            loop_demand -= spilled.first;
525         }
526      }
527
528      /* select live-through variables and constants */
529      RegType type = RegType::vgpr;
530      while (loop_demand.exceeds(ctx.target_pressure)) {
531         /* if VGPR demand is low enough, select SGPRs */
532         if (type == RegType::vgpr && loop_demand.vgpr <= ctx.target_pressure.vgpr)
533            type = RegType::sgpr;
534         /* if SGPR demand is low enough, break */
535         if (type == RegType::sgpr && loop_demand.sgpr <= ctx.target_pressure.sgpr)
536            break;
537
538         unsigned distance = 0;
539         Temp to_spill;
540         for (const std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair :
541              next_use_distances) {
542            if (pair.first.type() == type &&
543                (pair.second.first >= loop_end ||
544                 (ctx.remat.count(pair.first) && type == RegType::sgpr)) &&
545                pair.second.second > distance && !ctx.spills_entry[block_idx].count(pair.first)) {
546               to_spill = pair.first;
547               distance = pair.second.second;
548            }
549         }
550
551         /* select SGPRs or break */
552         if (distance == 0) {
553            if (type == RegType::sgpr)
554               break;
555            type = RegType::sgpr;
556            continue;
557         }
558
559         uint32_t spill_id;
560         if (!ctx.spills_exit[block_idx - 1].count(to_spill)) {
561            spill_id = ctx.allocate_spill_id(to_spill.regClass());
562         } else {
563            spill_id = ctx.spills_exit[block_idx - 1][to_spill];
564         }
565
566         ctx.spills_entry[block_idx][to_spill] = spill_id;
567         spilled_registers += to_spill;
568         loop_demand -= to_spill;
569      }
570
571      /* shortcut */
572      if (!loop_demand.exceeds(ctx.target_pressure))
573         return spilled_registers;
574
575      /* if reg pressure is too high at beginning of loop, add variables with furthest use */
576      reg_pressure -= spilled_registers;
577
578      while (reg_pressure.exceeds(ctx.target_pressure)) {
579         unsigned distance = 0;
580         Temp to_spill;
581         type = reg_pressure.vgpr > ctx.target_pressure.vgpr ? RegType::vgpr : RegType::sgpr;
582
583         for (const std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair :
584              next_use_distances) {
585            if (pair.first.type() == type && pair.second.second > distance &&
586                !ctx.spills_entry[block_idx].count(pair.first)) {
587               to_spill = pair.first;
588               distance = pair.second.second;
589            }
590         }
591         assert(distance != 0);
592         ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
593         spilled_registers += to_spill;
594         reg_pressure -= to_spill;
595      }
596
597      return spilled_registers;
598   }
599
600   /* branch block */
601   if (block->linear_preds.size() == 1 && !(block->kind & block_kind_loop_exit)) {
602      /* keep variables spilled if they are alive and not used in the current block */
603      unsigned pred_idx = block->linear_preds[0];
604      for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
605         if (pair.first.type() != RegType::sgpr) {
606            continue;
607         }
608         auto next_use_distance_it = next_use_distances.find(pair.first);
609         if (next_use_distance_it != next_use_distances.end() &&
610             next_use_distance_it->second.first != block_idx) {
611            ctx.spills_entry[block_idx].insert(pair);
612            spilled_registers.sgpr += pair.first.size();
613         }
614      }
615      if (block->logical_preds.size() == 1) {
616         pred_idx = block->logical_preds[0];
617         for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
618            if (pair.first.type() != RegType::vgpr) {
619               continue;
620            }
621            auto next_use_distance_it = next_use_distances.find(pair.first);
622            if (next_use_distance_it != next_use_distances.end() &&
623                next_use_distance_it->second.first != block_idx) {
624               ctx.spills_entry[block_idx].insert(pair);
625               spilled_registers.vgpr += pair.first.size();
626            }
627         }
628      }
629
630      /* if register demand is still too high, we just keep all spilled live vars
631       * and process the block */
632      if (block->register_demand.sgpr - spilled_registers.sgpr > ctx.target_pressure.sgpr) {
633         pred_idx = block->linear_preds[0];
634         for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
635            if (pair.first.type() == RegType::sgpr && next_use_distances.count(pair.first) &&
636                ctx.spills_entry[block_idx].insert(pair).second) {
637               spilled_registers.sgpr += pair.first.size();
638            }
639         }
640      }
641      if (block->register_demand.vgpr - spilled_registers.vgpr > ctx.target_pressure.vgpr &&
642          block->logical_preds.size() == 1) {
643         pred_idx = block->logical_preds[0];
644         for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx]) {
645            if (pair.first.type() == RegType::vgpr && next_use_distances.count(pair.first) &&
646                ctx.spills_entry[block_idx].insert(pair).second) {
647               spilled_registers.vgpr += pair.first.size();
648            }
649         }
650      }
651
652      return spilled_registers;
653   }
654
655   /* else: merge block */
656   std::set<Temp> partial_spills;
657
658   /* keep variables spilled on all incoming paths */
659   for (const std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair : next_use_distances) {
660      std::vector<unsigned>& preds =
661         pair.first.is_linear() ? block->linear_preds : block->logical_preds;
662      /* If it can be rematerialized, keep the variable spilled if all predecessors do not reload
663       * it. Otherwise, if any predecessor reloads it, ensure it's reloaded on all other
664       * predecessors. The idea is that it's better in practice to rematerialize redundantly than to
665       * create lots of phis. */
666      /* TODO: test this idea with more than Dawn of War III shaders (the current pipeline-db
667       * doesn't seem to exercise this path much) */
668      bool remat = ctx.remat.count(pair.first);
669      bool spill = !remat;
670      uint32_t spill_id = 0;
671      for (unsigned pred_idx : preds) {
672         /* variable is not even live at the predecessor: probably from a phi */
673         if (!ctx.next_use_distances_end[pred_idx].count(pair.first)) {
674            spill = false;
675            break;
676         }
677         if (!ctx.spills_exit[pred_idx].count(pair.first)) {
678            if (!remat)
679               spill = false;
680         } else {
681            partial_spills.insert(pair.first);
682            /* it might be that on one incoming path, the variable has a different spill_id, but
683             * add_couple_code() will take care of that. */
684            spill_id = ctx.spills_exit[pred_idx][pair.first];
685            if (remat)
686               spill = true;
687         }
688      }
689      if (spill) {
690         ctx.spills_entry[block_idx][pair.first] = spill_id;
691         partial_spills.erase(pair.first);
692         spilled_registers += pair.first;
693      }
694   }
695
696   /* same for phis */
697   for (aco_ptr<Instruction>& phi : block->instructions) {
698      if (!is_phi(phi))
699         break;
700      if (!phi->definitions[0].isTemp())
701         continue;
702
703      std::vector<unsigned>& preds =
704         phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
705      bool is_all_spilled = true;
706      for (unsigned i = 0; i < phi->operands.size(); i++) {
707         if (phi->operands[i].isUndefined())
708            continue;
709         is_all_spilled &= phi->operands[i].isTemp() &&
710                           ctx.spills_exit[preds[i]].count(phi->operands[i].getTemp());
711      }
712
713      if (is_all_spilled) {
714         /* The phi is spilled at all predecessors. Keep it spilled. */
715         ctx.spills_entry[block_idx][phi->definitions[0].getTemp()] =
716            ctx.allocate_spill_id(phi->definitions[0].regClass());
717         spilled_registers += phi->definitions[0].getTemp();
718      } else {
719         /* Phis might increase the register pressure. */
720         partial_spills.insert(phi->definitions[0].getTemp());
721      }
722   }
723
724   /* if reg pressure at first instruction is still too high, add partially spilled variables */
725   RegisterDemand reg_pressure = get_live_in_demand(ctx, block_idx);
726   reg_pressure -= spilled_registers;
727
728   while (reg_pressure.exceeds(ctx.target_pressure)) {
729      assert(!partial_spills.empty());
730      std::set<Temp>::iterator it = partial_spills.begin();
731      Temp to_spill = Temp();
732      unsigned distance = 0;
733      RegType type = reg_pressure.vgpr > ctx.target_pressure.vgpr ? RegType::vgpr : RegType::sgpr;
734
735      while (it != partial_spills.end()) {
736         assert(!ctx.spills_entry[block_idx].count(*it));
737
738         if (it->type() == type && next_use_distances.at(*it).second > distance) {
739            distance = next_use_distances.at(*it).second;
740            to_spill = *it;
741         }
742         ++it;
743      }
744      assert(distance != 0);
745
746      ctx.spills_entry[block_idx][to_spill] = ctx.allocate_spill_id(to_spill.regClass());
747      partial_spills.erase(to_spill);
748      spilled_registers += to_spill;
749      reg_pressure -= to_spill;
750   }
751
752   return spilled_registers;
753}
754
755void
756add_coupling_code(spill_ctx& ctx, Block* block, unsigned block_idx)
757{
758   /* no coupling code necessary */
759   if (block->linear_preds.size() == 0)
760      return;
761
762   std::vector<aco_ptr<Instruction>> instructions;
763   /* branch block: TODO take other branch into consideration */
764   if (block->linear_preds.size() == 1 &&
765       !(block->kind & (block_kind_loop_exit | block_kind_loop_header))) {
766      assert(ctx.processed[block->linear_preds[0]]);
767      assert(ctx.register_demand[block_idx].size() == block->instructions.size());
768      std::vector<RegisterDemand> reg_demand;
769      unsigned insert_idx = 0;
770      RegisterDemand demand_before = get_demand_before(ctx, block_idx, 0);
771
772      for (std::pair<const Temp, std::pair<uint32_t, uint32_t>>& live :
773           ctx.next_use_distances_start[block_idx]) {
774         const unsigned pred_idx = block->linear_preds[0];
775
776         if (!live.first.is_linear())
777            continue;
778         /* still spilled */
779         if (ctx.spills_entry[block_idx].count(live.first))
780            continue;
781
782         /* in register at end of predecessor */
783         auto spills_exit_it = ctx.spills_exit[pred_idx].find(live.first);
784         if (spills_exit_it == ctx.spills_exit[pred_idx].end()) {
785            std::map<Temp, Temp>::iterator it = ctx.renames[pred_idx].find(live.first);
786            if (it != ctx.renames[pred_idx].end())
787               ctx.renames[block_idx].insert(*it);
788            continue;
789         }
790
791         /* variable is spilled at predecessor and live at current block: create reload instruction */
792         Temp new_name = ctx.program->allocateTmp(live.first.regClass());
793         aco_ptr<Instruction> reload = do_reload(ctx, live.first, new_name, spills_exit_it->second);
794         instructions.emplace_back(std::move(reload));
795         reg_demand.push_back(demand_before);
796         ctx.renames[block_idx][live.first] = new_name;
797      }
798
799      if (block->logical_preds.size() == 1) {
800         do {
801            assert(insert_idx < block->instructions.size());
802            instructions.emplace_back(std::move(block->instructions[insert_idx]));
803            reg_demand.push_back(ctx.register_demand[block_idx][insert_idx]);
804            insert_idx++;
805         } while (instructions.back()->opcode != aco_opcode::p_logical_start);
806
807         unsigned pred_idx = block->logical_preds[0];
808         for (std::pair<const Temp, std::pair<uint32_t, uint32_t>>& live :
809              ctx.next_use_distances_start[block_idx]) {
810            if (live.first.is_linear())
811               continue;
812            /* still spilled */
813            if (ctx.spills_entry[block_idx].count(live.first))
814               continue;
815
816            /* in register at end of predecessor */
817            auto spills_exit_it = ctx.spills_exit[pred_idx].find(live.first);
818            if (spills_exit_it == ctx.spills_exit[pred_idx].end()) {
819               std::map<Temp, Temp>::iterator it = ctx.renames[pred_idx].find(live.first);
820               if (it != ctx.renames[pred_idx].end())
821                  ctx.renames[block_idx].insert(*it);
822               continue;
823            }
824
825            /* variable is spilled at predecessor and live at current block:
826             * create reload instruction */
827            Temp new_name = ctx.program->allocateTmp(live.first.regClass());
828            aco_ptr<Instruction> reload =
829               do_reload(ctx, live.first, new_name, spills_exit_it->second);
830            instructions.emplace_back(std::move(reload));
831            reg_demand.emplace_back(reg_demand.back());
832            ctx.renames[block_idx][live.first] = new_name;
833         }
834      }
835
836      /* combine new reload instructions with original block */
837      if (!instructions.empty()) {
838         reg_demand.insert(reg_demand.end(),
839                           std::next(ctx.register_demand[block->index].begin(), insert_idx),
840                           ctx.register_demand[block->index].end());
841         ctx.register_demand[block_idx] = std::move(reg_demand);
842         instructions.insert(instructions.end(),
843                             std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(
844                                std::next(block->instructions.begin(), insert_idx)),
845                             std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(
846                                block->instructions.end()));
847         block->instructions = std::move(instructions);
848      }
849      return;
850   }
851
852   /* loop header and merge blocks: check if all (linear) predecessors have been processed */
853   for (ASSERTED unsigned pred : block->linear_preds)
854      assert(ctx.processed[pred]);
855
856   /* iterate the phi nodes for which operands to spill at the predecessor */
857   for (aco_ptr<Instruction>& phi : block->instructions) {
858      if (!is_phi(phi))
859         break;
860
861      /* if the phi is not spilled, add to instructions */
862      if (!phi->definitions[0].isTemp() ||
863          !ctx.spills_entry[block_idx].count(phi->definitions[0].getTemp())) {
864         instructions.emplace_back(std::move(phi));
865         continue;
866      }
867
868      std::vector<unsigned>& preds =
869         phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
870      uint32_t def_spill_id = ctx.spills_entry[block_idx][phi->definitions[0].getTemp()];
871
872      for (unsigned i = 0; i < phi->operands.size(); i++) {
873         if (phi->operands[i].isUndefined())
874            continue;
875
876         unsigned pred_idx = preds[i];
877         Operand spill_op = phi->operands[i];
878
879         if (spill_op.isTemp()) {
880            assert(phi->operands[i].isKill());
881            Temp var = phi->operands[i].getTemp();
882
883            std::map<Temp, Temp>::iterator rename_it = ctx.renames[pred_idx].find(var);
884            /* prevent the definining instruction from being DCE'd if it could be rematerialized */
885            if (rename_it == ctx.renames[preds[i]].end() && ctx.remat.count(var))
886               ctx.unused_remats.erase(ctx.remat[var].instr);
887
888            /* check if variable is already spilled at predecessor */
889            auto spilled = ctx.spills_exit[pred_idx].find(var);
890            if (spilled != ctx.spills_exit[pred_idx].end()) {
891               if (spilled->second != def_spill_id)
892                  ctx.add_affinity(def_spill_id, spilled->second);
893               continue;
894            }
895
896            /* rename if necessary */
897            if (rename_it != ctx.renames[pred_idx].end()) {
898               spill_op.setTemp(rename_it->second);
899               ctx.renames[pred_idx].erase(rename_it);
900            }
901         }
902
903         uint32_t spill_id = ctx.allocate_spill_id(phi->definitions[0].regClass());
904
905         /* add interferences and affinity */
906         for (std::pair<Temp, uint32_t> pair : ctx.spills_exit[pred_idx])
907            ctx.add_interference(spill_id, pair.second);
908         ctx.add_affinity(def_spill_id, spill_id);
909
910         aco_ptr<Pseudo_instruction> spill{
911            create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
912         spill->operands[0] = spill_op;
913         spill->operands[1] = Operand::c32(spill_id);
914         Block& pred = ctx.program->blocks[pred_idx];
915         unsigned idx = pred.instructions.size();
916         do {
917            assert(idx != 0);
918            idx--;
919         } while (phi->opcode == aco_opcode::p_phi &&
920                  pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
921         std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
922         pred.instructions.insert(it, std::move(spill));
923
924         /* Add the original name to predecessor's spilled variables */
925         if (spill_op.isTemp())
926            ctx.spills_exit[pred_idx][phi->operands[i].getTemp()] = spill_id;
927      }
928
929      /* remove phi from instructions */
930      phi.reset();
931   }
932
933   /* iterate all (other) spilled variables for which to spill at the predecessor */
934   // TODO: would be better to have them sorted: first vgprs and first with longest distance
935   for (std::pair<Temp, uint32_t> pair : ctx.spills_entry[block_idx]) {
936      std::vector<unsigned> preds =
937         pair.first.is_linear() ? block->linear_preds : block->logical_preds;
938
939      for (unsigned pred_idx : preds) {
940         /* variable is already spilled at predecessor */
941         auto spilled = ctx.spills_exit[pred_idx].find(pair.first);
942         if (spilled != ctx.spills_exit[pred_idx].end()) {
943            if (spilled->second != pair.second)
944               ctx.add_affinity(pair.second, spilled->second);
945            continue;
946         }
947
948         /* variable is dead at predecessor, it must be from a phi: this works because of CSSA form */
949         if (!ctx.next_use_distances_end[pred_idx].count(pair.first))
950            continue;
951
952         /* add interferences between spilled variable and predecessors exit spills */
953         for (std::pair<Temp, uint32_t> exit_spill : ctx.spills_exit[pred_idx]) {
954            if (exit_spill.first == pair.first)
955               continue;
956            ctx.add_interference(exit_spill.second, pair.second);
957         }
958
959         /* variable is in register at predecessor and has to be spilled */
960         /* rename if necessary */
961         Temp var = pair.first;
962         std::map<Temp, Temp>::iterator rename_it = ctx.renames[pred_idx].find(var);
963         if (rename_it != ctx.renames[pred_idx].end()) {
964            var = rename_it->second;
965            ctx.renames[pred_idx].erase(rename_it);
966         }
967
968         aco_ptr<Pseudo_instruction> spill{
969            create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
970         spill->operands[0] = Operand(var);
971         spill->operands[1] = Operand::c32(pair.second);
972         Block& pred = ctx.program->blocks[pred_idx];
973         unsigned idx = pred.instructions.size();
974         do {
975            assert(idx != 0);
976            idx--;
977         } while (pair.first.type() == RegType::vgpr &&
978                  pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
979         std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
980         pred.instructions.insert(it, std::move(spill));
981         ctx.spills_exit[pred.index][pair.first] = pair.second;
982      }
983   }
984
985   /* iterate phis for which operands to reload */
986   for (aco_ptr<Instruction>& phi : instructions) {
987      assert(phi->opcode == aco_opcode::p_phi || phi->opcode == aco_opcode::p_linear_phi);
988      assert(!phi->definitions[0].isTemp() ||
989             !ctx.spills_entry[block_idx].count(phi->definitions[0].getTemp()));
990
991      std::vector<unsigned>& preds =
992         phi->opcode == aco_opcode::p_phi ? block->logical_preds : block->linear_preds;
993      for (unsigned i = 0; i < phi->operands.size(); i++) {
994         if (!phi->operands[i].isTemp())
995            continue;
996         unsigned pred_idx = preds[i];
997
998         /* if the operand was reloaded, rename */
999         if (!ctx.spills_exit[pred_idx].count(phi->operands[i].getTemp())) {
1000            std::map<Temp, Temp>::iterator it =
1001               ctx.renames[pred_idx].find(phi->operands[i].getTemp());
1002            if (it != ctx.renames[pred_idx].end()) {
1003               phi->operands[i].setTemp(it->second);
1004            /* prevent the definining instruction from being DCE'd if it could be rematerialized */
1005            } else {
1006               auto remat_it = ctx.remat.find(phi->operands[i].getTemp());
1007               if (remat_it != ctx.remat.end()) {
1008                  ctx.unused_remats.erase(remat_it->second.instr);
1009               }
1010            }
1011            continue;
1012         }
1013
1014         Temp tmp = phi->operands[i].getTemp();
1015
1016         /* reload phi operand at end of predecessor block */
1017         Temp new_name = ctx.program->allocateTmp(tmp.regClass());
1018         Block& pred = ctx.program->blocks[pred_idx];
1019         unsigned idx = pred.instructions.size();
1020         do {
1021            assert(idx != 0);
1022            idx--;
1023         } while (phi->opcode == aco_opcode::p_phi &&
1024                  pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
1025         std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
1026         aco_ptr<Instruction> reload =
1027            do_reload(ctx, tmp, new_name, ctx.spills_exit[pred_idx][tmp]);
1028
1029         /* reload spilled exec mask directly to exec */
1030         if (!phi->definitions[0].isTemp()) {
1031            assert(phi->definitions[0].isFixed() && phi->definitions[0].physReg() == exec);
1032            reload->definitions[0] = phi->definitions[0];
1033            phi->operands[i] = Operand(exec, ctx.program->lane_mask);
1034         } else {
1035            ctx.spills_exit[pred_idx].erase(tmp);
1036            ctx.renames[pred_idx][tmp] = new_name;
1037            phi->operands[i].setTemp(new_name);
1038         }
1039
1040         pred.instructions.insert(it, std::move(reload));
1041      }
1042   }
1043
1044   /* iterate live variables for which to reload */
1045   // TODO: reload at current block if variable is spilled on all predecessors
1046   for (std::pair<const Temp, std::pair<uint32_t, uint32_t>>& pair :
1047        ctx.next_use_distances_start[block_idx]) {
1048      /* skip spilled variables */
1049      if (ctx.spills_entry[block_idx].count(pair.first))
1050         continue;
1051      std::vector<unsigned> preds =
1052         pair.first.is_linear() ? block->linear_preds : block->logical_preds;
1053
1054      /* variable is dead at predecessor, it must be from a phi */
1055      bool is_dead = false;
1056      for (unsigned pred_idx : preds) {
1057         if (!ctx.next_use_distances_end[pred_idx].count(pair.first))
1058            is_dead = true;
1059      }
1060      if (is_dead)
1061         continue;
1062      for (unsigned pred_idx : preds) {
1063         /* the variable is not spilled at the predecessor */
1064         if (!ctx.spills_exit[pred_idx].count(pair.first))
1065            continue;
1066
1067         /* variable is spilled at predecessor and has to be reloaded */
1068         Temp new_name = ctx.program->allocateTmp(pair.first.regClass());
1069         Block& pred = ctx.program->blocks[pred_idx];
1070         unsigned idx = pred.instructions.size();
1071         do {
1072            assert(idx != 0);
1073            idx--;
1074         } while (pair.first.type() == RegType::vgpr &&
1075                  pred.instructions[idx]->opcode != aco_opcode::p_logical_end);
1076         std::vector<aco_ptr<Instruction>>::iterator it = std::next(pred.instructions.begin(), idx);
1077
1078         aco_ptr<Instruction> reload =
1079            do_reload(ctx, pair.first, new_name, ctx.spills_exit[pred.index][pair.first]);
1080         pred.instructions.insert(it, std::move(reload));
1081
1082         ctx.spills_exit[pred.index].erase(pair.first);
1083         ctx.renames[pred.index][pair.first] = new_name;
1084      }
1085
1086      /* check if we have to create a new phi for this variable */
1087      Temp rename = Temp();
1088      bool is_same = true;
1089      for (unsigned pred_idx : preds) {
1090         if (!ctx.renames[pred_idx].count(pair.first)) {
1091            if (rename == Temp())
1092               rename = pair.first;
1093            else
1094               is_same = rename == pair.first;
1095         } else {
1096            if (rename == Temp())
1097               rename = ctx.renames[pred_idx][pair.first];
1098            else
1099               is_same = rename == ctx.renames[pred_idx][pair.first];
1100         }
1101
1102         if (!is_same)
1103            break;
1104      }
1105
1106      if (!is_same) {
1107         /* the variable was renamed differently in the predecessors: we have to create a phi */
1108         aco_opcode opcode = pair.first.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi;
1109         aco_ptr<Pseudo_instruction> phi{
1110            create_instruction<Pseudo_instruction>(opcode, Format::PSEUDO, preds.size(), 1)};
1111         rename = ctx.program->allocateTmp(pair.first.regClass());
1112         for (unsigned i = 0; i < phi->operands.size(); i++) {
1113            Temp tmp;
1114            if (ctx.renames[preds[i]].count(pair.first)) {
1115               tmp = ctx.renames[preds[i]][pair.first];
1116            } else if (preds[i] >= block_idx) {
1117               tmp = rename;
1118            } else {
1119               tmp = pair.first;
1120               /* prevent the definining instruction from being DCE'd if it could be rematerialized */
1121               if (ctx.remat.count(tmp))
1122                  ctx.unused_remats.erase(ctx.remat[tmp].instr);
1123            }
1124            phi->operands[i] = Operand(tmp);
1125         }
1126         phi->definitions[0] = Definition(rename);
1127         instructions.emplace_back(std::move(phi));
1128      }
1129
1130      /* the variable was renamed: add new name to renames */
1131      if (!(rename == Temp() || rename == pair.first))
1132         ctx.renames[block_idx][pair.first] = rename;
1133   }
1134
1135   /* combine phis with instructions */
1136   unsigned idx = 0;
1137   while (!block->instructions[idx]) {
1138      idx++;
1139   }
1140
1141   if (!ctx.processed[block_idx]) {
1142      assert(!(block->kind & block_kind_loop_header));
1143      RegisterDemand demand_before = get_demand_before(ctx, block_idx, idx);
1144      ctx.register_demand[block->index].erase(ctx.register_demand[block->index].begin(),
1145                                              ctx.register_demand[block->index].begin() + idx);
1146      ctx.register_demand[block->index].insert(ctx.register_demand[block->index].begin(),
1147                                               instructions.size(), demand_before);
1148   }
1149
1150   std::vector<aco_ptr<Instruction>>::iterator start = std::next(block->instructions.begin(), idx);
1151   instructions.insert(
1152      instructions.end(), std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(start),
1153      std::move_iterator<std::vector<aco_ptr<Instruction>>::iterator>(block->instructions.end()));
1154   block->instructions = std::move(instructions);
1155}
1156
1157void
1158process_block(spill_ctx& ctx, unsigned block_idx, Block* block, RegisterDemand spilled_registers)
1159{
1160   assert(!ctx.processed[block_idx]);
1161
1162   std::vector<aco_ptr<Instruction>> instructions;
1163   unsigned idx = 0;
1164
1165   /* phis are handled separetely */
1166   while (block->instructions[idx]->opcode == aco_opcode::p_phi ||
1167          block->instructions[idx]->opcode == aco_opcode::p_linear_phi) {
1168      instructions.emplace_back(std::move(block->instructions[idx++]));
1169   }
1170
1171   if (block->register_demand.exceeds(ctx.target_pressure)) {
1172      update_local_next_uses(ctx, block, ctx.local_next_use_distance);
1173   } else {
1174      /* We won't use local_next_use_distance, so no initialization needed */
1175   }
1176
1177   auto& current_spills = ctx.spills_exit[block_idx];
1178
1179   while (idx < block->instructions.size()) {
1180      aco_ptr<Instruction>& instr = block->instructions[idx];
1181
1182      std::map<Temp, std::pair<Temp, uint32_t>> reloads;
1183
1184      /* rename and reload operands */
1185      for (Operand& op : instr->operands) {
1186         if (!op.isTemp())
1187            continue;
1188         if (!current_spills.count(op.getTemp())) {
1189            /* the Operand is in register: check if it was renamed */
1190            auto rename_it = ctx.renames[block_idx].find(op.getTemp());
1191            if (rename_it != ctx.renames[block_idx].end()) {
1192               op.setTemp(rename_it->second);
1193            } else {
1194               /* prevent its definining instruction from being DCE'd if it could be rematerialized */
1195               auto remat_it = ctx.remat.find(op.getTemp());
1196               if (remat_it != ctx.remat.end()) {
1197                  ctx.unused_remats.erase(remat_it->second.instr);
1198               }
1199            }
1200            continue;
1201         }
1202         /* the Operand is spilled: add it to reloads */
1203         Temp new_tmp = ctx.program->allocateTmp(op.regClass());
1204         ctx.renames[block_idx][op.getTemp()] = new_tmp;
1205         reloads[new_tmp] = std::make_pair(op.getTemp(), current_spills[op.getTemp()]);
1206         current_spills.erase(op.getTemp());
1207         op.setTemp(new_tmp);
1208         spilled_registers -= new_tmp;
1209      }
1210
1211      /* check if register demand is low enough before and after the current instruction */
1212      if (block->register_demand.exceeds(ctx.target_pressure)) {
1213
1214         RegisterDemand new_demand = ctx.register_demand[block_idx][idx];
1215         new_demand.update(get_demand_before(ctx, block_idx, idx));
1216
1217         assert(!ctx.local_next_use_distance.empty());
1218
1219         /* if reg pressure is too high, spill variable with furthest next use */
1220         while ((new_demand - spilled_registers).exceeds(ctx.target_pressure)) {
1221            unsigned distance = 0;
1222            Temp to_spill;
1223            bool do_rematerialize = false;
1224            RegType type = RegType::sgpr;
1225            if (new_demand.vgpr - spilled_registers.vgpr > ctx.target_pressure.vgpr)
1226               type = RegType::vgpr;
1227
1228            for (std::pair<Temp, uint32_t> pair : ctx.local_next_use_distance[idx]) {
1229               if (pair.first.type() != type)
1230                  continue;
1231               bool can_rematerialize = ctx.remat.count(pair.first);
1232               if (((pair.second > distance && can_rematerialize == do_rematerialize) ||
1233                    (can_rematerialize && !do_rematerialize && pair.second > idx)) &&
1234                   !current_spills.count(pair.first)) {
1235                  to_spill = pair.first;
1236                  distance = pair.second;
1237                  do_rematerialize = can_rematerialize;
1238               }
1239            }
1240
1241            assert(distance != 0 && distance > idx);
1242            uint32_t spill_id = ctx.allocate_spill_id(to_spill.regClass());
1243
1244            /* add interferences with currently spilled variables */
1245            for (std::pair<Temp, uint32_t> pair : current_spills)
1246               ctx.add_interference(spill_id, pair.second);
1247            for (std::pair<const Temp, std::pair<Temp, uint32_t>>& pair : reloads)
1248               ctx.add_interference(spill_id, pair.second.second);
1249
1250            current_spills[to_spill] = spill_id;
1251            spilled_registers += to_spill;
1252
1253            /* rename if necessary */
1254            if (ctx.renames[block_idx].count(to_spill)) {
1255               to_spill = ctx.renames[block_idx][to_spill];
1256            }
1257
1258            /* add spill to new instructions */
1259            aco_ptr<Pseudo_instruction> spill{
1260               create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 2, 0)};
1261            spill->operands[0] = Operand(to_spill);
1262            spill->operands[1] = Operand::c32(spill_id);
1263            instructions.emplace_back(std::move(spill));
1264         }
1265      }
1266
1267      /* add reloads and instruction to new instructions */
1268      for (std::pair<const Temp, std::pair<Temp, uint32_t>>& pair : reloads) {
1269         aco_ptr<Instruction> reload =
1270            do_reload(ctx, pair.second.first, pair.first, pair.second.second);
1271         instructions.emplace_back(std::move(reload));
1272      }
1273      instructions.emplace_back(std::move(instr));
1274      idx++;
1275   }
1276
1277   block->instructions = std::move(instructions);
1278}
1279
1280void
1281spill_block(spill_ctx& ctx, unsigned block_idx)
1282{
1283   Block* block = &ctx.program->blocks[block_idx];
1284
1285   /* determine set of variables which are spilled at the beginning of the block */
1286   RegisterDemand spilled_registers = init_live_in_vars(ctx, block, block_idx);
1287
1288   /* add interferences for spilled variables */
1289   for (auto it = ctx.spills_entry[block_idx].begin(); it != ctx.spills_entry[block_idx].end();
1290        ++it) {
1291      for (auto it2 = std::next(it); it2 != ctx.spills_entry[block_idx].end(); ++it2)
1292         ctx.add_interference(it->second, it2->second);
1293   }
1294
1295   bool is_loop_header = block->loop_nest_depth && ctx.loop_header.top()->index == block_idx;
1296   if (!is_loop_header) {
1297      /* add spill/reload code on incoming control flow edges */
1298      add_coupling_code(ctx, block, block_idx);
1299   }
1300
1301   const auto& current_spills = ctx.spills_entry[block_idx];
1302
1303   /* check conditions to process this block */
1304   bool process = (block->register_demand - spilled_registers).exceeds(ctx.target_pressure) ||
1305                  !ctx.renames[block_idx].empty() || ctx.unused_remats.size();
1306
1307   for (auto it = current_spills.begin(); !process && it != current_spills.end(); ++it) {
1308      if (ctx.next_use_distances_start[block_idx].at(it->first).first == block_idx)
1309         process = true;
1310   }
1311
1312   assert(ctx.spills_exit[block_idx].empty());
1313   ctx.spills_exit[block_idx] = current_spills;
1314   if (process) {
1315      process_block(ctx, block_idx, block, spilled_registers);
1316   }
1317
1318   ctx.processed[block_idx] = true;
1319
1320   /* check if the next block leaves the current loop */
1321   if (block->loop_nest_depth == 0 ||
1322       ctx.program->blocks[block_idx + 1].loop_nest_depth >= block->loop_nest_depth)
1323      return;
1324
1325   Block* loop_header = ctx.loop_header.top();
1326
1327   /* preserve original renames at end of loop header block */
1328   std::map<Temp, Temp> renames = std::move(ctx.renames[loop_header->index]);
1329
1330   /* add coupling code to all loop header predecessors */
1331   add_coupling_code(ctx, loop_header, loop_header->index);
1332
1333   /* propagate new renames through loop: i.e. repair the SSA */
1334   renames.swap(ctx.renames[loop_header->index]);
1335   for (std::pair<Temp, Temp> rename : renames) {
1336      for (unsigned idx = loop_header->index; idx <= block_idx; idx++) {
1337         Block& current = ctx.program->blocks[idx];
1338         std::vector<aco_ptr<Instruction>>::iterator instr_it = current.instructions.begin();
1339
1340         /* first rename phis */
1341         while (instr_it != current.instructions.end()) {
1342            aco_ptr<Instruction>& phi = *instr_it;
1343            if (phi->opcode != aco_opcode::p_phi && phi->opcode != aco_opcode::p_linear_phi)
1344               break;
1345            /* no need to rename the loop header phis once again. this happened in
1346             * add_coupling_code() */
1347            if (idx == loop_header->index) {
1348               instr_it++;
1349               continue;
1350            }
1351
1352            for (Operand& op : phi->operands) {
1353               if (!op.isTemp())
1354                  continue;
1355               if (op.getTemp() == rename.first)
1356                  op.setTemp(rename.second);
1357            }
1358            instr_it++;
1359         }
1360
1361         /* variable is not live at beginning of this block */
1362         if (ctx.next_use_distances_start[idx].count(rename.first) == 0)
1363            continue;
1364
1365         /* if the variable is live at the block's exit, add rename */
1366         if (ctx.next_use_distances_end[idx].count(rename.first) != 0)
1367            ctx.renames[idx].insert(rename);
1368
1369         /* rename all uses in this block */
1370         bool renamed = false;
1371         while (!renamed && instr_it != current.instructions.end()) {
1372            aco_ptr<Instruction>& instr = *instr_it;
1373            for (Operand& op : instr->operands) {
1374               if (!op.isTemp())
1375                  continue;
1376               if (op.getTemp() == rename.first) {
1377                  op.setTemp(rename.second);
1378                  /* we can stop with this block as soon as the variable is spilled */
1379                  if (instr->opcode == aco_opcode::p_spill)
1380                     renamed = true;
1381               }
1382            }
1383            instr_it++;
1384         }
1385      }
1386   }
1387
1388   /* remove loop header info from stack */
1389   ctx.loop_header.pop();
1390}
1391
1392Temp
1393load_scratch_resource(spill_ctx& ctx, Temp& scratch_offset, Block& block,
1394                      std::vector<aco_ptr<Instruction>>& instructions, unsigned offset)
1395{
1396   Builder bld(ctx.program);
1397   if (block.kind & block_kind_top_level) {
1398      bld.reset(&instructions);
1399   } else {
1400      for (int block_idx = block.index; block_idx >= 0; block_idx--) {
1401         if (!(ctx.program->blocks[block_idx].kind & block_kind_top_level))
1402            continue;
1403
1404         /* find p_logical_end */
1405         std::vector<aco_ptr<Instruction>>& prev_instructions = ctx.program->blocks[block_idx].instructions;
1406         unsigned idx = prev_instructions.size() - 1;
1407         while (prev_instructions[idx]->opcode != aco_opcode::p_logical_end)
1408            idx--;
1409         bld.reset(&prev_instructions, std::next(prev_instructions.begin(), idx));
1410         break;
1411      }
1412   }
1413
1414   /* GFX9+ uses scratch_* instructions, which don't use a resource. Return a SADDR instead. */
1415   if (ctx.program->gfx_level >= GFX9)
1416      return bld.copy(bld.def(s1), Operand::c32(offset));
1417
1418   Temp private_segment_buffer = ctx.program->private_segment_buffer;
1419   if (ctx.program->stage.hw != HWStage::CS)
1420      private_segment_buffer =
1421         bld.smem(aco_opcode::s_load_dwordx2, bld.def(s2), private_segment_buffer, Operand::zero());
1422
1423   if (offset)
1424      scratch_offset = bld.sop2(aco_opcode::s_add_u32, bld.def(s1), bld.def(s1, scc),
1425                                scratch_offset, Operand::c32(offset));
1426
1427   uint32_t rsrc_conf =
1428      S_008F0C_ADD_TID_ENABLE(1) | S_008F0C_INDEX_STRIDE(ctx.program->wave_size == 64 ? 3 : 2);
1429
1430   if (ctx.program->gfx_level >= GFX10) {
1431      rsrc_conf |= S_008F0C_FORMAT(V_008F0C_GFX10_FORMAT_32_FLOAT) |
1432                   S_008F0C_OOB_SELECT(V_008F0C_OOB_SELECT_RAW) |
1433                   S_008F0C_RESOURCE_LEVEL(ctx.program->gfx_level < GFX11);
1434   } else if (ctx.program->gfx_level <= GFX7) {
1435      /* dfmt modifies stride on GFX8/GFX9 when ADD_TID_EN=1 */
1436      rsrc_conf |= S_008F0C_NUM_FORMAT(V_008F0C_BUF_NUM_FORMAT_FLOAT) |
1437                   S_008F0C_DATA_FORMAT(V_008F0C_BUF_DATA_FORMAT_32);
1438   }
1439   /* older generations need element size = 4 bytes. element size removed in GFX9 */
1440   if (ctx.program->gfx_level <= GFX8)
1441      rsrc_conf |= S_008F0C_ELEMENT_SIZE(1);
1442
1443   return bld.pseudo(aco_opcode::p_create_vector, bld.def(s4), private_segment_buffer,
1444                     Operand::c32(-1u), Operand::c32(rsrc_conf));
1445}
1446
1447void
1448setup_vgpr_spill_reload(spill_ctx& ctx, Block& block,
1449                        std::vector<aco_ptr<Instruction>>& instructions, uint32_t spill_slot,
1450                        unsigned* offset)
1451{
1452   Temp scratch_offset = ctx.program->scratch_offset;
1453
1454   *offset = spill_slot * 4;
1455   if (ctx.program->gfx_level >= GFX9) {
1456      *offset += ctx.program->dev.scratch_global_offset_min;
1457
1458      if (ctx.scratch_rsrc == Temp()) {
1459         int32_t saddr = ctx.program->config->scratch_bytes_per_wave / ctx.program->wave_size -
1460                         ctx.program->dev.scratch_global_offset_min;
1461         ctx.scratch_rsrc =
1462            load_scratch_resource(ctx, scratch_offset, block, instructions, saddr);
1463      }
1464   } else {
1465      bool add_offset_to_sgpr =
1466         ctx.program->config->scratch_bytes_per_wave / ctx.program->wave_size +
1467            ctx.vgpr_spill_slots * 4 >
1468         4096;
1469      if (!add_offset_to_sgpr)
1470         *offset += ctx.program->config->scratch_bytes_per_wave / ctx.program->wave_size;
1471
1472      if (ctx.scratch_rsrc == Temp()) {
1473         unsigned rsrc_offset =
1474            add_offset_to_sgpr ? ctx.program->config->scratch_bytes_per_wave : 0;
1475         ctx.scratch_rsrc =
1476            load_scratch_resource(ctx, scratch_offset, block, instructions, rsrc_offset);
1477      }
1478   }
1479}
1480
1481void
1482spill_vgpr(spill_ctx& ctx, Block& block, std::vector<aco_ptr<Instruction>>& instructions,
1483           aco_ptr<Instruction>& spill, std::vector<uint32_t>& slots)
1484{
1485   ctx.program->config->spilled_vgprs += spill->operands[0].size();
1486
1487   uint32_t spill_id = spill->operands[1].constantValue();
1488   uint32_t spill_slot = slots[spill_id];
1489
1490   unsigned offset;
1491   setup_vgpr_spill_reload(ctx, block, instructions, spill_slot, &offset);
1492
1493   assert(spill->operands[0].isTemp());
1494   Temp temp = spill->operands[0].getTemp();
1495   assert(temp.type() == RegType::vgpr && !temp.is_linear());
1496
1497   Builder bld(ctx.program, &instructions);
1498   if (temp.size() > 1) {
1499      Instruction* split{create_instruction<Pseudo_instruction>(aco_opcode::p_split_vector,
1500                                                                Format::PSEUDO, 1, temp.size())};
1501      split->operands[0] = Operand(temp);
1502      for (unsigned i = 0; i < temp.size(); i++)
1503         split->definitions[i] = bld.def(v1);
1504      bld.insert(split);
1505      for (unsigned i = 0; i < temp.size(); i++, offset += 4) {
1506         Temp elem = split->definitions[i].getTemp();
1507         if (ctx.program->gfx_level >= GFX9) {
1508            bld.scratch(aco_opcode::scratch_store_dword, Operand(v1), ctx.scratch_rsrc, elem,
1509                        offset, memory_sync_info(storage_vgpr_spill, semantic_private));
1510         } else {
1511            Instruction* instr =
1512               bld.mubuf(aco_opcode::buffer_store_dword, ctx.scratch_rsrc, Operand(v1),
1513                         ctx.program->scratch_offset, elem, offset, false, true);
1514            instr->mubuf().sync = memory_sync_info(storage_vgpr_spill, semantic_private);
1515         }
1516      }
1517   } else if (ctx.program->gfx_level >= GFX9) {
1518      bld.scratch(aco_opcode::scratch_store_dword, Operand(v1), ctx.scratch_rsrc, temp, offset,
1519                  memory_sync_info(storage_vgpr_spill, semantic_private));
1520   } else {
1521      Instruction* instr = bld.mubuf(aco_opcode::buffer_store_dword, ctx.scratch_rsrc, Operand(v1),
1522                                     ctx.program->scratch_offset, temp, offset, false, true);
1523      instr->mubuf().sync = memory_sync_info(storage_vgpr_spill, semantic_private);
1524   }
1525}
1526
1527void
1528reload_vgpr(spill_ctx& ctx, Block& block, std::vector<aco_ptr<Instruction>>& instructions,
1529            aco_ptr<Instruction>& reload, std::vector<uint32_t>& slots)
1530{
1531   uint32_t spill_id = reload->operands[0].constantValue();
1532   uint32_t spill_slot = slots[spill_id];
1533
1534   unsigned offset;
1535   setup_vgpr_spill_reload(ctx, block, instructions, spill_slot, &offset);
1536
1537   Definition def = reload->definitions[0];
1538
1539   Builder bld(ctx.program, &instructions);
1540   if (def.size() > 1) {
1541      Instruction* vec{create_instruction<Pseudo_instruction>(aco_opcode::p_create_vector,
1542                                                              Format::PSEUDO, def.size(), 1)};
1543      vec->definitions[0] = def;
1544      for (unsigned i = 0; i < def.size(); i++, offset += 4) {
1545         Temp tmp = bld.tmp(v1);
1546         vec->operands[i] = Operand(tmp);
1547         if (ctx.program->gfx_level >= GFX9) {
1548            bld.scratch(aco_opcode::scratch_load_dword, Definition(tmp), Operand(v1),
1549                        ctx.scratch_rsrc, offset,
1550                        memory_sync_info(storage_vgpr_spill, semantic_private));
1551         } else {
1552            Instruction* instr =
1553               bld.mubuf(aco_opcode::buffer_load_dword, Definition(tmp), ctx.scratch_rsrc,
1554                         Operand(v1), ctx.program->scratch_offset, offset, false, true);
1555            instr->mubuf().sync = memory_sync_info(storage_vgpr_spill, semantic_private);
1556         }
1557      }
1558      bld.insert(vec);
1559   } else if (ctx.program->gfx_level >= GFX9) {
1560      bld.scratch(aco_opcode::scratch_load_dword, def, Operand(v1), ctx.scratch_rsrc, offset,
1561                  memory_sync_info(storage_vgpr_spill, semantic_private));
1562   } else {
1563      Instruction* instr = bld.mubuf(aco_opcode::buffer_load_dword, def, ctx.scratch_rsrc,
1564                                     Operand(v1), ctx.program->scratch_offset, offset, false, true);
1565      instr->mubuf().sync = memory_sync_info(storage_vgpr_spill, semantic_private);
1566   }
1567}
1568
1569void
1570add_interferences(spill_ctx& ctx, std::vector<bool>& is_assigned, std::vector<uint32_t>& slots,
1571                  std::vector<bool>& slots_used, unsigned id)
1572{
1573   for (unsigned other : ctx.interferences[id].second) {
1574      if (!is_assigned[other])
1575         continue;
1576
1577      RegClass other_rc = ctx.interferences[other].first;
1578      unsigned slot = slots[other];
1579      std::fill(slots_used.begin() + slot, slots_used.begin() + slot + other_rc.size(), true);
1580   }
1581}
1582
1583unsigned
1584find_available_slot(std::vector<bool>& used, unsigned wave_size, unsigned size, bool is_sgpr)
1585{
1586   unsigned wave_size_minus_one = wave_size - 1;
1587   unsigned slot = 0;
1588
1589   while (true) {
1590      bool available = true;
1591      for (unsigned i = 0; i < size; i++) {
1592         if (slot + i < used.size() && used[slot + i]) {
1593            available = false;
1594            break;
1595         }
1596      }
1597      if (!available) {
1598         slot++;
1599         continue;
1600      }
1601
1602      if (is_sgpr && ((slot & wave_size_minus_one) > wave_size - size)) {
1603         slot = align(slot, wave_size);
1604         continue;
1605      }
1606
1607      std::fill(used.begin(), used.end(), false);
1608
1609      if (slot + size > used.size())
1610         used.resize(slot + size);
1611
1612      return slot;
1613   }
1614}
1615
1616void
1617assign_spill_slots_helper(spill_ctx& ctx, RegType type, std::vector<bool>& is_assigned,
1618                          std::vector<uint32_t>& slots, unsigned* num_slots)
1619{
1620   std::vector<bool> slots_used;
1621
1622   /* assign slots for ids with affinities first */
1623   for (std::vector<uint32_t>& vec : ctx.affinities) {
1624      if (ctx.interferences[vec[0]].first.type() != type)
1625         continue;
1626
1627      for (unsigned id : vec) {
1628         if (!ctx.is_reloaded[id])
1629            continue;
1630
1631         add_interferences(ctx, is_assigned, slots, slots_used, id);
1632      }
1633
1634      unsigned slot = find_available_slot(
1635         slots_used, ctx.wave_size, ctx.interferences[vec[0]].first.size(), type == RegType::sgpr);
1636
1637      for (unsigned id : vec) {
1638         assert(!is_assigned[id]);
1639
1640         if (ctx.is_reloaded[id]) {
1641            slots[id] = slot;
1642            is_assigned[id] = true;
1643         }
1644      }
1645   }
1646
1647   /* assign slots for ids without affinities */
1648   for (unsigned id = 0; id < ctx.interferences.size(); id++) {
1649      if (is_assigned[id] || !ctx.is_reloaded[id] || ctx.interferences[id].first.type() != type)
1650         continue;
1651
1652      add_interferences(ctx, is_assigned, slots, slots_used, id);
1653
1654      unsigned slot = find_available_slot(
1655         slots_used, ctx.wave_size, ctx.interferences[id].first.size(), type == RegType::sgpr);
1656
1657      slots[id] = slot;
1658      is_assigned[id] = true;
1659   }
1660
1661   *num_slots = slots_used.size();
1662}
1663
1664void
1665assign_spill_slots(spill_ctx& ctx, unsigned spills_to_vgpr)
1666{
1667   std::vector<uint32_t> slots(ctx.interferences.size());
1668   std::vector<bool> is_assigned(ctx.interferences.size());
1669
1670   /* first, handle affinities: just merge all interferences into both spill ids */
1671   for (std::vector<uint32_t>& vec : ctx.affinities) {
1672      for (unsigned i = 0; i < vec.size(); i++) {
1673         for (unsigned j = i + 1; j < vec.size(); j++) {
1674            assert(vec[i] != vec[j]);
1675            bool reloaded = ctx.is_reloaded[vec[i]] || ctx.is_reloaded[vec[j]];
1676            ctx.is_reloaded[vec[i]] = reloaded;
1677            ctx.is_reloaded[vec[j]] = reloaded;
1678         }
1679      }
1680   }
1681   for (ASSERTED uint32_t i = 0; i < ctx.interferences.size(); i++)
1682      for (ASSERTED uint32_t id : ctx.interferences[i].second)
1683         assert(i != id);
1684
1685   /* for each spill slot, assign as many spill ids as possible */
1686   assign_spill_slots_helper(ctx, RegType::sgpr, is_assigned, slots, &ctx.sgpr_spill_slots);
1687   assign_spill_slots_helper(ctx, RegType::vgpr, is_assigned, slots, &ctx.vgpr_spill_slots);
1688
1689   for (unsigned id = 0; id < is_assigned.size(); id++)
1690      assert(is_assigned[id] || !ctx.is_reloaded[id]);
1691
1692   for (std::vector<uint32_t>& vec : ctx.affinities) {
1693      for (unsigned i = 0; i < vec.size(); i++) {
1694         for (unsigned j = i + 1; j < vec.size(); j++) {
1695            assert(is_assigned[vec[i]] == is_assigned[vec[j]]);
1696            if (!is_assigned[vec[i]])
1697               continue;
1698            assert(ctx.is_reloaded[vec[i]] == ctx.is_reloaded[vec[j]]);
1699            assert(ctx.interferences[vec[i]].first.type() ==
1700                   ctx.interferences[vec[j]].first.type());
1701            assert(slots[vec[i]] == slots[vec[j]]);
1702         }
1703      }
1704   }
1705
1706   /* hope, we didn't mess up */
1707   std::vector<Temp> vgpr_spill_temps((ctx.sgpr_spill_slots + ctx.wave_size - 1) / ctx.wave_size);
1708   assert(vgpr_spill_temps.size() <= spills_to_vgpr);
1709
1710   /* replace pseudo instructions with actual hardware instructions */
1711   unsigned last_top_level_block_idx = 0;
1712   std::vector<bool> reload_in_loop(vgpr_spill_temps.size());
1713   for (Block& block : ctx.program->blocks) {
1714
1715      /* after loops, we insert a user if there was a reload inside the loop */
1716      if (block.loop_nest_depth == 0) {
1717         int end_vgprs = 0;
1718         for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1719            if (reload_in_loop[i])
1720               end_vgprs++;
1721         }
1722
1723         if (end_vgprs > 0) {
1724            aco_ptr<Instruction> destr{create_instruction<Pseudo_instruction>(
1725               aco_opcode::p_end_linear_vgpr, Format::PSEUDO, end_vgprs, 0)};
1726            int k = 0;
1727            for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1728               if (reload_in_loop[i])
1729                  destr->operands[k++] = Operand(vgpr_spill_temps[i]);
1730               reload_in_loop[i] = false;
1731            }
1732            /* find insertion point */
1733            std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
1734            while ((*it)->opcode == aco_opcode::p_linear_phi || (*it)->opcode == aco_opcode::p_phi)
1735               ++it;
1736            block.instructions.insert(it, std::move(destr));
1737         }
1738      }
1739
1740      if (block.kind & block_kind_top_level && !block.linear_preds.empty()) {
1741         last_top_level_block_idx = block.index;
1742
1743         /* check if any spilled variables use a created linear vgpr, otherwise destroy them */
1744         for (unsigned i = 0; i < vgpr_spill_temps.size(); i++) {
1745            if (vgpr_spill_temps[i] == Temp())
1746               continue;
1747
1748            bool can_destroy = true;
1749            for (std::pair<Temp, uint32_t> pair : ctx.spills_entry[block.index]) {
1750
1751               if (ctx.interferences[pair.second].first.type() == RegType::sgpr &&
1752                   slots[pair.second] / ctx.wave_size == i) {
1753                  can_destroy = false;
1754                  break;
1755               }
1756            }
1757            if (can_destroy)
1758               vgpr_spill_temps[i] = Temp();
1759         }
1760      }
1761
1762      std::vector<aco_ptr<Instruction>>::iterator it;
1763      std::vector<aco_ptr<Instruction>> instructions;
1764      instructions.reserve(block.instructions.size());
1765      Builder bld(ctx.program, &instructions);
1766      for (it = block.instructions.begin(); it != block.instructions.end(); ++it) {
1767
1768         if ((*it)->opcode == aco_opcode::p_spill) {
1769            uint32_t spill_id = (*it)->operands[1].constantValue();
1770
1771            if (!ctx.is_reloaded[spill_id]) {
1772               /* never reloaded, so don't spill */
1773            } else if (!is_assigned[spill_id]) {
1774               unreachable("No spill slot assigned for spill id");
1775            } else if (ctx.interferences[spill_id].first.type() == RegType::vgpr) {
1776               spill_vgpr(ctx, block, instructions, *it, slots);
1777            } else {
1778               ctx.program->config->spilled_sgprs += (*it)->operands[0].size();
1779
1780               uint32_t spill_slot = slots[spill_id];
1781
1782               /* check if the linear vgpr already exists */
1783               if (vgpr_spill_temps[spill_slot / ctx.wave_size] == Temp()) {
1784                  Temp linear_vgpr = ctx.program->allocateTmp(v1.as_linear());
1785                  vgpr_spill_temps[spill_slot / ctx.wave_size] = linear_vgpr;
1786                  aco_ptr<Pseudo_instruction> create{create_instruction<Pseudo_instruction>(
1787                     aco_opcode::p_start_linear_vgpr, Format::PSEUDO, 0, 1)};
1788                  create->definitions[0] = Definition(linear_vgpr);
1789                  /* find the right place to insert this definition */
1790                  if (last_top_level_block_idx == block.index) {
1791                     /* insert right before the current instruction */
1792                     instructions.emplace_back(std::move(create));
1793                  } else {
1794                     assert(last_top_level_block_idx < block.index);
1795                     /* insert before the branch at last top level block */
1796                     std::vector<aco_ptr<Instruction>>& block_instrs =
1797                        ctx.program->blocks[last_top_level_block_idx].instructions;
1798                     block_instrs.insert(std::prev(block_instrs.end()), std::move(create));
1799                  }
1800               }
1801
1802               /* spill sgpr: just add the vgpr temp to operands */
1803               Pseudo_instruction* spill =
1804                  create_instruction<Pseudo_instruction>(aco_opcode::p_spill, Format::PSEUDO, 3, 0);
1805               spill->operands[0] = Operand(vgpr_spill_temps[spill_slot / ctx.wave_size]);
1806               spill->operands[1] = Operand::c32(spill_slot % ctx.wave_size);
1807               spill->operands[2] = (*it)->operands[0];
1808               instructions.emplace_back(aco_ptr<Instruction>(spill));
1809            }
1810
1811         } else if ((*it)->opcode == aco_opcode::p_reload) {
1812            uint32_t spill_id = (*it)->operands[0].constantValue();
1813            assert(ctx.is_reloaded[spill_id]);
1814
1815            if (!is_assigned[spill_id]) {
1816               unreachable("No spill slot assigned for spill id");
1817            } else if (ctx.interferences[spill_id].first.type() == RegType::vgpr) {
1818               reload_vgpr(ctx, block, instructions, *it, slots);
1819            } else {
1820               uint32_t spill_slot = slots[spill_id];
1821               reload_in_loop[spill_slot / ctx.wave_size] = block.loop_nest_depth > 0;
1822
1823               /* check if the linear vgpr already exists */
1824               if (vgpr_spill_temps[spill_slot / ctx.wave_size] == Temp()) {
1825                  Temp linear_vgpr = ctx.program->allocateTmp(v1.as_linear());
1826                  vgpr_spill_temps[spill_slot / ctx.wave_size] = linear_vgpr;
1827                  aco_ptr<Pseudo_instruction> create{create_instruction<Pseudo_instruction>(
1828                     aco_opcode::p_start_linear_vgpr, Format::PSEUDO, 0, 1)};
1829                  create->definitions[0] = Definition(linear_vgpr);
1830                  /* find the right place to insert this definition */
1831                  if (last_top_level_block_idx == block.index) {
1832                     /* insert right before the current instruction */
1833                     instructions.emplace_back(std::move(create));
1834                  } else {
1835                     assert(last_top_level_block_idx < block.index);
1836                     /* insert before the branch at last top level block */
1837                     std::vector<aco_ptr<Instruction>>& block_instrs =
1838                        ctx.program->blocks[last_top_level_block_idx].instructions;
1839                     block_instrs.insert(std::prev(block_instrs.end()), std::move(create));
1840                  }
1841               }
1842
1843               /* reload sgpr: just add the vgpr temp to operands */
1844               Pseudo_instruction* reload = create_instruction<Pseudo_instruction>(
1845                  aco_opcode::p_reload, Format::PSEUDO, 2, 1);
1846               reload->operands[0] = Operand(vgpr_spill_temps[spill_slot / ctx.wave_size]);
1847               reload->operands[1] = Operand::c32(spill_slot % ctx.wave_size);
1848               reload->definitions[0] = (*it)->definitions[0];
1849               instructions.emplace_back(aco_ptr<Instruction>(reload));
1850            }
1851         } else if (!ctx.unused_remats.count(it->get())) {
1852            instructions.emplace_back(std::move(*it));
1853         }
1854      }
1855      block.instructions = std::move(instructions);
1856   }
1857
1858   /* update required scratch memory */
1859   ctx.program->config->scratch_bytes_per_wave +=
1860      align(ctx.vgpr_spill_slots * 4 * ctx.program->wave_size, 1024);
1861
1862   /* SSA elimination inserts copies for logical phis right before p_logical_end
1863    * So if a linear vgpr is used between that p_logical_end and the branch,
1864    * we need to ensure logical phis don't choose a definition which aliases
1865    * the linear vgpr.
1866    * TODO: Moving the spills and reloads to before p_logical_end might produce
1867    *       slightly better code. */
1868   for (Block& block : ctx.program->blocks) {
1869      /* loops exits are already handled */
1870      if (block.logical_preds.size() <= 1)
1871         continue;
1872
1873      bool has_logical_phis = false;
1874      for (aco_ptr<Instruction>& instr : block.instructions) {
1875         if (instr->opcode == aco_opcode::p_phi) {
1876            has_logical_phis = true;
1877            break;
1878         } else if (instr->opcode != aco_opcode::p_linear_phi) {
1879            break;
1880         }
1881      }
1882      if (!has_logical_phis)
1883         continue;
1884
1885      std::set<Temp> vgprs;
1886      for (unsigned pred_idx : block.logical_preds) {
1887         Block& pred = ctx.program->blocks[pred_idx];
1888         for (int i = pred.instructions.size() - 1; i >= 0; i--) {
1889            aco_ptr<Instruction>& pred_instr = pred.instructions[i];
1890            if (pred_instr->opcode == aco_opcode::p_logical_end) {
1891               break;
1892            } else if (pred_instr->opcode == aco_opcode::p_spill ||
1893                       pred_instr->opcode == aco_opcode::p_reload) {
1894               vgprs.insert(pred_instr->operands[0].getTemp());
1895            }
1896         }
1897      }
1898      if (!vgprs.size())
1899         continue;
1900
1901      aco_ptr<Instruction> destr{create_instruction<Pseudo_instruction>(
1902         aco_opcode::p_end_linear_vgpr, Format::PSEUDO, vgprs.size(), 0)};
1903      int k = 0;
1904      for (Temp tmp : vgprs) {
1905         destr->operands[k++] = Operand(tmp);
1906      }
1907      /* find insertion point */
1908      std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
1909      while ((*it)->opcode == aco_opcode::p_linear_phi || (*it)->opcode == aco_opcode::p_phi)
1910         ++it;
1911      block.instructions.insert(it, std::move(destr));
1912   }
1913}
1914
1915} /* end namespace */
1916
1917void
1918spill(Program* program, live& live_vars)
1919{
1920   program->config->spilled_vgprs = 0;
1921   program->config->spilled_sgprs = 0;
1922
1923   program->progress = CompilationProgress::after_spilling;
1924
1925   /* no spilling when register pressure is low enough */
1926   if (program->num_waves > 0)
1927      return;
1928
1929   /* lower to CSSA before spilling to ensure correctness w.r.t. phis */
1930   lower_to_cssa(program, live_vars);
1931
1932   /* calculate target register demand */
1933   const RegisterDemand demand = program->max_reg_demand; /* current max */
1934   const uint16_t sgpr_limit = get_addr_sgpr_from_waves(program, program->min_waves);
1935   const uint16_t vgpr_limit = get_addr_vgpr_from_waves(program, program->min_waves);
1936   uint16_t extra_vgprs = 0;
1937   uint16_t extra_sgprs = 0;
1938
1939   /* calculate extra VGPRs required for spilling SGPRs */
1940   if (demand.sgpr > sgpr_limit) {
1941      unsigned sgpr_spills = demand.sgpr - sgpr_limit;
1942      extra_vgprs = DIV_ROUND_UP(sgpr_spills, program->wave_size) + 1;
1943   }
1944   /* add extra SGPRs required for spilling VGPRs */
1945   if (demand.vgpr + extra_vgprs > vgpr_limit) {
1946      if (program->gfx_level >= GFX9)
1947         extra_sgprs = 1; /* SADDR */
1948      else
1949         extra_sgprs = 5; /* scratch_resource (s4) + scratch_offset (s1) */
1950      if (demand.sgpr + extra_sgprs > sgpr_limit) {
1951         /* re-calculate in case something has changed */
1952         unsigned sgpr_spills = demand.sgpr + extra_sgprs - sgpr_limit;
1953         extra_vgprs = DIV_ROUND_UP(sgpr_spills, program->wave_size) + 1;
1954      }
1955   }
1956   /* the spiller has to target the following register demand */
1957   const RegisterDemand target(vgpr_limit - extra_vgprs, sgpr_limit - extra_sgprs);
1958
1959   /* initialize ctx */
1960   spill_ctx ctx(target, program, live_vars.register_demand);
1961   compute_global_next_uses(ctx);
1962   get_rematerialize_info(ctx);
1963
1964   /* create spills and reloads */
1965   for (unsigned i = 0; i < program->blocks.size(); i++)
1966      spill_block(ctx, i);
1967
1968   /* assign spill slots and DCE rematerialized code */
1969   assign_spill_slots(ctx, extra_vgprs);
1970
1971   /* update live variable information */
1972   live_vars = live_var_analysis(program);
1973
1974   assert(program->num_waves > 0);
1975}
1976
1977} // namespace aco
1978