projects / mesa.git / blob
? search:


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