projects / mesa.git / blob
? search:


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