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