projects / mesa.git / blob
? search:


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