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