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