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