Debian Codegraph @

src/imagination/pco/pco_ra.c

raw
1 /*
2 * Copyright © 2024 Imagination Technologies Ltd.
3 *
4 * based in part on asahi driver which is:
5 * Copyright 2022 Alyssa Rosenzweig
6 *
7 * SPDX-License-Identifier: MIT
8 */
9
10 /**
11 * \file pco_ra.c
12 *
13 * \brief PCO register allocator.
14 */
15
16 #include "hwdef/rogue_hw_utils.h"
17 #include "pco.h"
18 #include "pco_builder.h"
19 #include "pco_internal.h"
20 #include "util/bitset.h"
21 #include "util/hash_table.h"
22 #include "util/macros.h"
23 #include "util/register_allocate.h"
24 #include "util/sparse_array.h"
25 #include "util/u_dynarray.h"
26
27 #include <assert.h>
28 #include <inttypes.h>
29 #include <stdbool.h>
30 #include <stdint.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33
34 /** Live range of an SSA variable. */
35 struct live_range {
36 unsigned start;
37 unsigned end;
38 };
39
40 /** Vector override information. */
41 struct vec_override {
42 pco_ref ref;
43 unsigned offset;
44 };
45
46 typedef struct _pco_ra_ctx {
47 unsigned allocable_temps;
48 unsigned allocable_vtxins;
49 unsigned allocable_interns;
50
51 unsigned temp_alloc_offset;
52
53 bool spilling_setup;
54 pco_ref spill_inst_addr_comps[2];
55 pco_ref spill_addr_comps[2];
56 pco_ref spill_data;
57 pco_ref spill_addr;
58 pco_ref spill_addr_data;
59 unsigned spilled_temps;
60
61 bool done;
62 } pco_ra_ctx;
63
64 /**
65 * \brief Checks if a vec has ssa sources that are referenced more than once.
66 *
67 * \param[in] vec Vec instruction.
68 * \return True if the vec has ssa sources that are referenced more than once.
69 */
70 static bool vec_has_repeated_ssas(pco_instr *vec)
71 {
72 assert(vec->op == PCO_OP_VEC);
73
74 pco_foreach_instr_src_ssa (psrc, vec) {
75 pco_foreach_instr_src_ssa_from (psrc_inner, vec, psrc) {
76 if (psrc_inner->val == psrc->val)
77 return true;
78 }
79 }
80
81 return false;
82 }
83
84 static void pco_extend_live_range(pco_ref origin,
85 pco_ref current_ref,
86 pco_instr *current_instr,
87 struct hash_table_u64 *overrides,
88 struct live_range *live_ranges)
89 {
90 pco_foreach_instr_in_func_from (instr, current_instr) {
91 pco_foreach_instr_src_ssa (psrc, instr) {
92 if (current_ref.val != psrc->val)
93 continue;
94
95 pco_foreach_instr_dest_ssa (pdest, instr) {
96 struct vec_override *override =
97 _mesa_hash_table_u64_search(overrides, pdest->val);
98
99 if (override) {
100 live_ranges[origin.val].end =
101 MAX2(live_ranges[origin.val].end,
102 live_ranges[override->ref.val].end);
103 break;
104 }
105
106 live_ranges[origin.val].end =
107 MAX2(live_ranges[origin.val].end, instr->index);
108 }
109
110 break;
111 }
112 }
113 }
114
115 typedef struct _pco_use {
116 pco_instr *instr;
117 pco_ref *ref;
118 } pco_use;
119
120 static void preproc_vecs(pco_func *func)
121 {
122 unsigned num_ssas = func->next_ssa;
123
124 void *mem_ctx = ralloc_context(NULL);
125 BITSET_WORD *multi_use_elems = rzalloc_array_size(mem_ctx,
126 sizeof(*multi_use_elems),
127 BITSET_WORDS(num_ssas));
128 struct hash_table_u64 *elem_uses = _mesa_hash_table_u64_create(mem_ctx);
129
130 bool needs_reindex = false;
131 pco_foreach_instr_in_func (instr, func) {
132 if (instr->op != PCO_OP_VEC)
133 continue;
134
135 pco_foreach_instr_src_ssa (psrc, instr) {
136 struct util_dynarray *uses =
137 _mesa_hash_table_u64_search(elem_uses, psrc->val);
138 if (!uses) {
139 uses = rzalloc_size(elem_uses, sizeof(*uses));
140 util_dynarray_init(uses, uses);
141 _mesa_hash_table_u64_insert(elem_uses, psrc->val, uses);
142 }
143
144 if (uses->size > 0)
145 BITSET_SET(multi_use_elems, psrc->val);
146
147 pco_use use = {
148 .instr = instr,
149 .ref = psrc,
150 };
151 util_dynarray_append(uses, use);
152 }
153 }
154
155 unsigned b;
156 BITSET_FOREACH_SET (b, multi_use_elems, num_ssas) {
157 struct util_dynarray *uses = _mesa_hash_table_u64_search(elem_uses, b);
158
159 pco_instr *producer = NULL;
160 pco_ref var;
161 pco_foreach_instr_in_func (instr, func) {
162 pco_foreach_instr_dest_ssa (pdest, instr) {
163 if (pdest->val == b) {
164 producer = instr;
165 var = *pdest;
166 break;
167 }
168 }
169
170 if (producer)
171 break;
172 }
173 assert(producer);
174
175 pco_builder b =
176 pco_builder_create(func, pco_cursor_after_instr(producer));
177
178 util_dynarray_foreach (uses, pco_use, use) {
179 b.cursor = pco_cursor_before_instr(use->instr);
180 if (pco_ref_get_chans(var) <= 4) {
181 pco_ref dest = pco_ref_new_ssa_clone(func, var);
182 pco_mbyp(&b,
183 dest,
184 var,
185 .exec_cnd = pco_instr_has_exec_cnd(producer)
186 ? pco_instr_get_exec_cnd(producer)
187 : PCO_EXEC_CND_E1_ZX,
188 .rpt = pco_ref_get_chans(var));
189 *use->ref = dest;
190 } else {
191 assert(use->instr->op == PCO_OP_VEC && producer->op == PCO_OP_VEC);
192
193 pco_instr *instr =
194 pco_instr_create(func,
195 1,
196 use->instr->num_srcs + producer->num_srcs - 1);
197 instr->op = PCO_OP_VEC;
198
199 instr->dest[0] = use->instr->dest[0];
200
201 unsigned num_srcs = 0;
202 for (unsigned s = 0; s < use->instr->num_srcs; ++s) {
203 if (&use->instr->src[s] != use->ref) {
204 instr->src[num_srcs++] = use->instr->src[s];
205 } else {
206 for (unsigned t = 0; t < producer->num_srcs; ++t)
207 instr->src[num_srcs++] = producer->src[t];
208 }
209 }
210
211 pco_instr_set_exec_cnd(instr, pco_instr_get_exec_cnd(use->instr));
212 pco_builder_insert_instr(&b, instr);
213
214 pco_instr_delete(use->instr);
215 needs_reindex = true;
216 }
217 }
218 }
219
220 ralloc_free(mem_ctx);
221
222 if (needs_reindex)
223 pco_index(func->parent_shader, false);
224 }
225
226 typedef struct _pco_copy {
227 pco_ref src;
228 pco_ref dest;
229 bool s1;
230
231 bool done;
232 } pco_copy;
233
234 static inline bool
235 copy_blocked(pco_copy *copy, unsigned *temp_use_counts, unsigned lowest_temp)
236 {
237 return temp_use_counts[pco_ref_get_temp(copy->dest) - lowest_temp] > 0;
238 }
239
240 static inline void
241 do_copy(pco_builder *b, enum pco_exec_cnd exec_cnd, pco_copy *copy)
242 {
243 if (copy->s1)
244 pco_movs1(b, copy->dest, copy->src, .exec_cnd = exec_cnd);
245 else
246 pco_mbyp(b, copy->dest, copy->src, .exec_cnd = exec_cnd);
247 }
248
249 static inline void
250 do_swap(pco_builder *b, enum pco_exec_cnd exec_cnd, pco_copy *copy)
251 {
252 assert(!copy->s1);
253
254 pco_mbyp2(b,
255 copy->dest,
256 pco_ref_reset_mods(copy->src),
257 copy->src,
258 copy->dest,
259 .exec_cnd = exec_cnd);
260 }
261
262 static void emit_copies(pco_builder *b,
263 struct util_dynarray *copies,
264 enum pco_exec_cnd exec_cnd,
265 unsigned highest_temp,
266 unsigned lowest_temp)
267 {
268 unsigned temp_range = highest_temp - lowest_temp + 1;
269 unsigned *temp_use_counts =
270 rzalloc_array_size(NULL, sizeof(*temp_use_counts), temp_range);
271 pco_copy **temp_writes =
272 rzalloc_array_size(NULL, sizeof(*temp_writes), temp_range);
273
274 util_dynarray_foreach (copies, pco_copy, copy) {
275 if (pco_ref_is_temp(copy->src))
276 ++temp_use_counts[pco_ref_get_temp(copy->src) - lowest_temp];
277
278 temp_writes[pco_ref_get_temp(copy->dest) - lowest_temp] = copy;
279 }
280
281 bool progress = true;
282 while (progress) {
283 progress = false;
284
285 util_dynarray_foreach (copies, pco_copy, copy) {
286 if (!copy->done && !copy_blocked(copy, temp_use_counts, lowest_temp)) {
287 copy->done = true;
288 progress = true;
289 do_copy(b, exec_cnd, copy);
290
291 if (pco_ref_is_temp(copy->src))
292 --temp_use_counts[pco_ref_get_temp(copy->src) - lowest_temp];
293
294 temp_writes[pco_ref_get_temp(copy->dest) - lowest_temp] = NULL;
295 }
296 }
297
298 if (progress)
299 continue;
300
301 util_dynarray_foreach (copies, pco_copy, copy) {
302 if (copy->done)
303 continue;
304
305 if (pco_refs_are_equal(copy->src, copy->dest, true)) {
306 copy->done = true;
307 continue;
308 }
309
310 do_swap(b, exec_cnd, copy);
311 copy->src = pco_ref_reset_mods(copy->src);
312
313 util_dynarray_foreach (copies, pco_copy, blocking) {
314 if (pco_ref_get_temp(blocking->src) >=
315 pco_ref_get_temp(copy->dest) &&
316 pco_ref_get_temp(blocking->src) <
317 (pco_ref_get_temp(copy->dest) + 1)) {
318 blocking->src = pco_ref_offset(blocking->src,
319 pco_ref_get_temp(copy->src) -
320 pco_ref_get_temp(copy->dest));
321 }
322 }
323
324 copy->done = true;
325 }
326 }
327
328 util_dynarray_foreach (copies, pco_copy, copy) {
329 assert(copy->done);
330 }
331
332 ralloc_free(temp_writes);
333 ralloc_free(temp_use_counts);
334 }
335
336 static void setup_spill_base(pco_shader *shader,
337 pco_ref spill_inst_addr_comps[2])
338 {
339 pco_func *entry = pco_entrypoint(shader);
340 pco_block *first_block = pco_func_first_block(entry);
341 pco_builder b =
342 pco_builder_create(entry, pco_cursor_before_block(first_block));
343
344 assert(shader->data.common.spill_info.count > 0);
345 unsigned base_addr_lo_idx = shader->data.common.spill_info.start;
346 unsigned base_addr_hi_idx = shader->data.common.spill_info.start + 1;
347 unsigned block_size_idx = shader->data.common.spill_info.start + 2;
348
349 pco_ref base_addr_lo = pco_ref_hwreg(base_addr_lo_idx, PCO_REG_CLASS_SHARED);
350 pco_ref base_addr_hi = pco_ref_hwreg(base_addr_hi_idx, PCO_REG_CLASS_SHARED);
351 pco_ref block_size = pco_ref_hwreg(block_size_idx, PCO_REG_CLASS_SHARED);
352 pco_ref local_addr_inst_num =
353 pco_ref_hwreg(PCO_SR_LOCAL_ADDR_INST_NUM, PCO_REG_CLASS_SPEC);
354
355 pco_imadd64(&b,
356 spill_inst_addr_comps[0],
357 spill_inst_addr_comps[1],
358 block_size,
359 local_addr_inst_num,
360 base_addr_lo,
361 base_addr_hi,
362 pco_ref_null());
363 }
364
365 static void spill(unsigned spill_index, pco_func *func, pco_ra_ctx *ctx)
366 {
367 unsigned spill_offset = ctx->spilled_temps++;
368
369 pco_foreach_instr_in_func (instr, func) {
370 pco_builder b = pco_builder_create(func, pco_cursor_before_instr(instr));
371 pco_foreach_instr_dest_ssa (pdest, instr) {
372 if (pdest->val != spill_index)
373 continue;
374
375 pco_ref imm_off = pco_ref_imm32(spill_offset);
376 pco_movi32(&b, ctx->spill_data, imm_off);
377 pco_imadd64(&b,
378 ctx->spill_addr_comps[0],
379 ctx->spill_addr_comps[1],
380 ctx->spill_data,
381 pco_4,
382 ctx->spill_inst_addr_comps[0],
383 ctx->spill_inst_addr_comps[1],
384 pco_ref_null());
385
386 /**/
387
388 *pdest = ctx->spill_data;
389
390 pco_instr *next_instr = pco_next_instr(instr);
391 if (next_instr && next_instr->op == PCO_OP_WDF)
392 b.cursor = pco_cursor_after_instr(next_instr);
393 else
394 b.cursor = pco_cursor_after_instr(instr);
395
396 pco_st32(&b,
397 ctx->spill_data,
398 pco_ref_drc(PCO_DRC_0),
399 pco_ref_imm8(1),
400 ctx->spill_addr_data,
401 pco_ref_null());
402
403 pco_wdf(&b, pco_ref_drc(PCO_DRC_0));
404
405 break;
406 }
407
408 b.cursor = pco_cursor_before_instr(instr);
409 bool load_done = false;
410 pco_foreach_instr_src_ssa (pdest, instr) {
411 if (pdest->val != spill_index)
412 continue;
413
414 if (!load_done) {
415 pco_ref imm_off = pco_ref_imm32(spill_offset);
416 pco_movi32(&b, ctx->spill_data, imm_off);
417 pco_imadd64(&b,
418 ctx->spill_addr_comps[0],
419 ctx->spill_addr_comps[1],
420 ctx->spill_data,
421 pco_4,
422 ctx->spill_inst_addr_comps[0],
423 ctx->spill_inst_addr_comps[1],
424 pco_ref_null());
425
426 pco_ld(&b,
427 ctx->spill_data,
428 pco_ref_drc(PCO_DRC_0),
429 pco_ref_imm8(1),
430 ctx->spill_addr);
431
432 pco_wdf(&b, pco_ref_drc(PCO_DRC_0));
433
434 load_done = true;
435 }
436
437 *pdest = ctx->spill_data;
438 }
439 }
440
441 pco_index(func->parent_shader, false);
442 }
443
444 /**
445 * \brief Performs register allocation on a function.
446 *
447 * \param[in,out] func PCO shader.
448 * \param[in] allocable_temps Number of allocatable temp registers.
449 * \param[in] allocable_vtxins Number of allocatable vertex input registers.
450 * \param[in] allocable_interns Number of allocatable internal registers.
451 * \return True if registers were allocated.
452 */
453 static bool pco_ra_func(pco_func *func, pco_ra_ctx *ctx)
454 {
455 /* TODO: support multiple functions and calls. */
456 assert(func->type == PCO_FUNC_TYPE_ENTRYPOINT);
457
458 /* TODO: loop lifetime extension.
459 * TODO: track successors/predecessors.
460 */
461
462 preproc_vecs(func);
463
464 unsigned num_rsvd_vtxins = func->parent_shader->data.common.vtxins;
465 unsigned num_ssas = func->next_ssa;
466 unsigned num_vregs = func->next_vreg;
467 unsigned num_vars = num_ssas + num_vregs + num_rsvd_vtxins;
468
469 /* Collect used bit sizes. */
470 uint8_t used_bits = 0;
471 pco_foreach_instr_in_func (instr, func) {
472 pco_foreach_instr_dest_ssa (pdest, instr) {
473 used_bits |= (1 << pdest->bits);
474 }
475 }
476
477 /* vregs are always 32x1. */
478 if (num_vregs > 0) {
479 used_bits |= (1 << PCO_BITS_32);
480 }
481
482 /* No registers to allocate. */
483 if (!used_bits) {
484 ctx->done = true;
485 return false;
486 }
487
488 /* 64-bit vars should've been lowered by now. */
489 assert(!(used_bits & (1 << PCO_BITS_64)));
490
491 /* TODO: support multiple bit sizes. */
492 bool only_32bit = used_bits == (1 << PCO_BITS_32);
493 assert(only_32bit);
494
495 struct ra_regs *ra_regs =
496 ra_alloc_reg_set(func,
497 ctx->allocable_temps + ctx->allocable_vtxins,
498 !only_32bit);
499
500 BITSET_WORD *comps =
501 rzalloc_array_size(ra_regs, sizeof(*comps), BITSET_WORDS(num_ssas));
502
503 /* Overrides for vector coalescing. */
504 struct hash_table_u64 *overrides = _mesa_hash_table_u64_create(ra_regs);
505 pco_foreach_instr_in_func_rev (instr, func) {
506 if (instr->op != PCO_OP_VEC)
507 continue;
508
509 /* Can't override vec ssa sources if they're referenced more than once. */
510 if (vec_has_repeated_ssas(instr))
511 continue;
512
513 pco_ref dest = instr->dest[0];
514 unsigned offset = 0;
515
516 struct vec_override *src_override =
517 _mesa_hash_table_u64_search(overrides, dest.val);
518
519 if (src_override) {
520 dest = src_override->ref;
521 offset += src_override->offset;
522 }
523
524 pco_foreach_instr_src (psrc, instr) {
525 /* TODO: skip if vector producer is used by multiple things in a way
526 * that doesn't allow coalescing. */
527 /* TODO: can NIR scalarise things so that the only remaining vectors
528 * can be used in this way? */
529
530 if (pco_ref_is_ssa(*psrc)) {
531 /* Make sure this hasn't already been overridden somewhere else! */
532 #if 1
533 if (_mesa_hash_table_u64_search(overrides, psrc->val)) {
534 BITSET_SET(comps, psrc->val);
535 continue;
536 }
537 #else
538 assert(!_mesa_hash_table_u64_search(overrides, psrc->val));
539 #endif
540
541 struct vec_override *src_override =
542 rzalloc_size(overrides, sizeof(*src_override));
543 src_override->ref = dest;
544 src_override->offset = offset;
545
546 _mesa_hash_table_u64_insert(overrides, psrc->val, src_override);
547 }
548
549 offset += pco_ref_get_chans(*psrc);
550 }
551 }
552
553 /* Overrides for vector component uses. */
554 pco_foreach_instr_in_func (instr, func) {
555 if (instr->op != PCO_OP_COMP)
556 continue;
557
558 pco_ref dest = instr->dest[0];
559 pco_ref src = instr->src[0];
560 unsigned offset = pco_ref_get_imm(instr->src[1]);
561
562 BITSET_SET(comps, dest.val);
563
564 assert(pco_ref_is_ssa(src));
565 assert(pco_ref_is_ssa(dest));
566
567 struct vec_override *vec_override =
568 _mesa_hash_table_u64_search(overrides, src.val);
569
570 if (vec_override) {
571 src = vec_override->ref;
572 offset += vec_override->offset;
573 }
574
575 struct vec_override *src_override =
576 rzalloc_size(overrides, sizeof(*src_override));
577 src_override->ref = src;
578 src_override->offset = offset;
579 _mesa_hash_table_u64_insert(overrides, dest.val, src_override);
580 }
581
582 /* Allocate classes. */
583 struct hash_table_u64 *ra_classes = _mesa_hash_table_u64_create(ra_regs);
584 pco_foreach_instr_in_func (instr, func) {
585 pco_foreach_instr_dest_ssa (pdest, instr) {
586 unsigned chans = pco_ref_get_chans(*pdest);
587 /* TODO: bitset instead of search? */
588 if (_mesa_hash_table_u64_search(ra_classes, chans))
589 continue;
590
591 /* Skip if collated. */
592 if (_mesa_hash_table_u64_search(overrides, pdest->val))
593 continue;
594
595 struct ra_class *ra_class = ra_alloc_contig_reg_class(ra_regs, chans);
596 _mesa_hash_table_u64_insert(ra_classes, chans, ra_class);
597 }
598 }
599
600 /* vregs are always 32x1. */
601 if (num_vregs > 0) {
602 if (!_mesa_hash_table_u64_search(ra_classes, 1)) {
603 struct ra_class *ra_class = ra_alloc_contig_reg_class(ra_regs, 1);
604 _mesa_hash_table_u64_insert(ra_classes, 1, ra_class);
605 }
606 }
607
608 /* Assign registers to classes. */
609 hash_table_u64_foreach (ra_classes, entry) {
610 const unsigned stride = entry.key;
611 struct ra_class *ra_class = entry.data;
612
613 for (unsigned t = 0; t < ctx->allocable_temps - (stride - 1); ++t)
614 ra_class_add_reg(ra_class, t);
615
616 for (unsigned t = ctx->allocable_temps;
617 t < ctx->allocable_temps + ctx->allocable_vtxins - (stride - 1);
618 ++t)
619 ra_class_add_reg(ra_class, t);
620 }
621
622 ra_set_finalize(ra_regs, NULL);
623
624 struct ra_graph *ra_graph = ra_alloc_interference_graph(ra_regs, num_vars);
625 ralloc_steal(ra_regs, ra_graph);
626
627 /* Allocate and calculate live ranges. */
628 struct live_range *live_ranges =
629 rzalloc_array_size(ra_regs, sizeof(*live_ranges), num_vars);
630
631 for (unsigned u = 0; u < num_vars; ++u)
632 live_ranges[u].start = ~0U;
633
634 pco_foreach_instr_in_func (instr, func) {
635 pco_foreach_instr_dest_ssa (pdest, instr) {
636 pco_ref dest = *pdest;
637 struct vec_override *override =
638 _mesa_hash_table_u64_search(overrides, dest.val);
639
640 if (override)
641 dest = override->ref;
642
643 live_ranges[dest.val].start =
644 MIN2(live_ranges[dest.val].start, instr->index);
645
646 if (override)
647 continue;
648
649 /* Set class if it hasn't already been set up in an override. */
650 unsigned chans = pco_ref_get_chans(dest);
651 struct ra_class *ra_class =
652 _mesa_hash_table_u64_search(ra_classes, chans);
653 assert(ra_class);
654
655 ra_set_node_class(ra_graph, dest.val, ra_class);
656 }
657
658 pco_foreach_instr_src_ssa (psrc, instr) {
659 pco_ref src = *psrc;
660 struct vec_override *override =
661 _mesa_hash_table_u64_search(overrides, src.val);
662
663 if (override)
664 src = override->ref;
665
666 live_ranges[src.val].end =
667 MAX2(live_ranges[src.val].end, instr->index);
668 }
669
670 pco_foreach_instr_dest_vreg (pdest, instr) {
671 pco_ref dest = *pdest;
672
673 /* Place vregs after ssa vars. */
674 dest.val += num_ssas;
675
676 live_ranges[dest.val].start =
677 MIN2(live_ranges[dest.val].start, instr->index);
678
679 /* Set class if it hasn't already been set up in an override. */
680 unsigned chans = pco_ref_get_chans(dest);
681 struct ra_class *ra_class =
682 _mesa_hash_table_u64_search(ra_classes, chans);
683 assert(ra_class);
684
685 ra_set_node_class(ra_graph, dest.val, ra_class);
686 }
687
688 pco_foreach_instr_src_vreg (psrc, instr) {
689 pco_ref src = *psrc;
690
691 /* Place vregs after ssa vars. */
692 src.val += num_ssas;
693
694 live_ranges[src.val].end =
695 MAX2(live_ranges[src.val].end, instr->index);
696 }
697
698 /* Ensure that vertex input registers with pre-initialised data are not
699 * clobbered too early.
700 */
701 if (ctx->allocable_vtxins > 0) {
702 pco_foreach_instr_src_vtxin_reg (psrc, instr) {
703 pco_ref src = *psrc;
704
705 /* Place vtxin regs after ssa vars and vregs. */
706 src.val += num_ssas + num_vregs;
707
708 live_ranges[src.val].end =
709 MAX2(live_ranges[src.val].end, instr->index);
710 live_ranges[src.val].start = 0;
711
712 ra_set_node_reg(ra_graph,
713 src.val,
714 psrc->val + ctx->allocable_temps);
715 }
716 }
717 }
718
719 /* Extend lifetimes of non-overriden vecs that have comp instructions. */
720 pco_foreach_instr_in_func (instr, func) {
721 if (instr->op != PCO_OP_COMP)
722 continue;
723
724 pco_ref dest = instr->dest[0];
725 pco_ref src_vec = instr->src[0];
726
727 struct vec_override *vec_override =
728 _mesa_hash_table_u64_search(overrides, src_vec.val);
729
730 /* Already taken care of. */
731 if (vec_override) {
732 assert(live_ranges[src_vec.val].start == ~0U &&
733 live_ranges[src_vec.val].end == 0);
734 continue;
735 }
736
737 pco_extend_live_range(src_vec, dest, instr, overrides, live_ranges);
738 }
739
740 /* Extend lifetimes of vars in loops. */
741 pco_foreach_loop_in_func (loop, func) {
742 pco_block *prologue_block =
743 pco_cf_node_as_block(pco_cf_node_head(&loop->prologue));
744
745 pco_block *epilogue_block =
746 pco_cf_node_as_block(pco_cf_node_tail(&loop->epilogue));
747
748 unsigned loop_start_index = pco_first_instr(prologue_block)->index;
749 unsigned loop_end_index = pco_last_instr(epilogue_block)->index;
750
751 /* If a var is defined before a loop and stops being used during it,
752 * extend its lifetime to the end of the loop.
753 */
754
755 for (unsigned var = 0; var < num_vars; ++var) {
756 if (live_ranges[var].start < loop_start_index &&
757 live_ranges[var].end > loop_start_index &&
758 live_ranges[var].end < loop_end_index) {
759 live_ranges[var].end = loop_end_index;
760 }
761 }
762 }
763
764 /* If there are instructions left with any unused dests that aren't/couldn't
765 * be DCEd (e.g. because of side effects), ensure their range ends are setup
766 * to avoid missing overlaps and clobbering regs.
767 */
768 for (unsigned var = 0; var < num_vars; ++var)
769 if (live_ranges[var].start != ~0U && live_ranges[var].end == 0)
770 live_ranges[var].end = live_ranges[var].start;
771
772 /* Build interference graph from overlapping live ranges. */
773 for (unsigned var0 = 0; var0 < num_vars; ++var0) {
774 for (unsigned var1 = var0 + 1; var1 < num_vars; ++var1) {
775 /* If the live ranges overlap, the register nodes interfere. */
776 if ((live_ranges[var0].start != ~0U && live_ranges[var1].end != ~0U) &&
777 !(live_ranges[var0].start >= live_ranges[var1].end ||
778 live_ranges[var1].start >= live_ranges[var0].end)) {
779 ra_add_node_interference(ra_graph, var0, var1);
780 }
781 }
782 }
783
784 pco_foreach_instr_in_func_rev (vec, func) {
785 if (vec->op != PCO_OP_VEC)
786 continue;
787
788 pco_foreach_instr_src_ssa (psrc, vec) {
789 ra_add_node_interference(ra_graph, vec->dest[0].val, psrc->val);
790 }
791 }
792
793 /* Make srcs and dests interfere for instructions with repeat > 1. */
794 pco_foreach_instr_in_func_rev (instr, func) {
795 if (!pco_instr_has_rpt(instr))
796 continue;
797
798 if (pco_instr_get_rpt(instr) < 2)
799 continue;
800
801 pco_foreach_instr_dest_ssa (pdest, instr) {
802 pco_foreach_instr_src_ssa (psrc, instr) {
803 ra_add_node_interference(ra_graph, pdest->val, psrc->val);
804 }
805 }
806 }
807
808 bool allocated = ra_allocate(ra_graph);
809 bool force_spill = false;
810 if (!allocated || force_spill) {
811 if (!ctx->spilling_setup) {
812 ctx->spill_inst_addr_comps[0] = pco_ref_hwreg(0, PCO_REG_CLASS_TEMP);
813 ctx->spill_inst_addr_comps[1] = pco_ref_hwreg(1, PCO_REG_CLASS_TEMP);
814
815 ctx->spill_addr_comps[0] = pco_ref_hwreg(2, PCO_REG_CLASS_TEMP);
816 ctx->spill_addr_comps[1] = pco_ref_hwreg(3, PCO_REG_CLASS_TEMP);
817
818 ctx->spill_data = pco_ref_hwreg(4, PCO_REG_CLASS_TEMP);
819
820 ctx->spill_addr = pco_ref_hwreg_vec(2, PCO_REG_CLASS_TEMP, 2);
821 ctx->spill_addr_data = pco_ref_hwreg_vec(2, PCO_REG_CLASS_TEMP, 3);
822
823 ctx->allocable_temps -= 5;
824 ctx->temp_alloc_offset = 5;
825
826 setup_spill_base(func->parent_shader, ctx->spill_inst_addr_comps);
827 ctx->spilling_setup = true;
828 }
829
830 unsigned *uses = rzalloc_array_size(ra_regs, sizeof(*uses), num_ssas);
831 pco_foreach_instr_in_func (instr, func) {
832 pco_foreach_instr_src_ssa (psrc, instr) {
833 if (pco_ref_get_chans(*psrc) > 1)
834 continue;
835
836 ++uses[psrc->val];
837 }
838 }
839
840 for (unsigned u = 0; u < num_ssas; ++u)
841 ra_set_node_spill_cost(ra_graph, u, (float)uses[u]);
842
843 unsigned spill_index = ra_get_best_spill_node(ra_graph);
844 if (spill_index == ~0) {
845 fprintf(stderr, "FATAL: Failed to get best spill node.\n");
846 abort();
847 }
848
849 spill(spill_index, func, ctx);
850
851 ralloc_free(ra_regs);
852 return false;
853 }
854
855 if (pco_should_print_shader(func->parent_shader) && PCO_DEBUG_PRINT(RA)) {
856 printf("RA live ranges:\n");
857 for (unsigned u = 0; u < num_vars; ++u)
858 printf(" %c%u: %u, %u\n",
859 u >= num_ssas ? '$' : '%',
860 u >= num_ssas ? u - num_ssas : u,
861 live_ranges[u].start,
862 live_ranges[u].end);
863
864 if (_mesa_hash_table_u64_num_entries(overrides)) {
865 printf("RA overrides:\n");
866 hash_table_u64_foreach (overrides, entry) {
867 struct vec_override *override = entry.data;
868 printf(" %%%" PRIu64 ": ref = ", entry.key);
869 pco_print_ref(func->parent_shader, override->ref);
870 printf(", offset = %u\n", override->offset);
871 }
872 printf("\n");
873 }
874 }
875
876 /* Replace vars with allocated registers. */
877 unsigned temps = 0;
878 unsigned vtxins = 0;
879 unsigned interns = 0;
880 pco_foreach_instr_in_func_safe (instr, func) {
881 #if 1
882 if (pco_should_print_shader(func->parent_shader) && PCO_DEBUG_PRINT(RA))
883 pco_print_shader(func->parent_shader, stdout, "ra debug");
884 #endif
885
886 /* Insert movs for scalar components of super vecs. */
887 if (instr->op == PCO_OP_VEC) {
888 pco_builder b =
889 pco_builder_create(func, pco_cursor_before_instr(instr));
890
891 struct vec_override *override =
892 _mesa_hash_table_u64_search(overrides, instr->dest[0].val);
893
894 unsigned offset = override ? override->offset : 0;
895
896 unsigned temp_dest_base =
897 override ? ra_get_node_reg(ra_graph, override->ref.val)
898 : ra_get_node_reg(ra_graph, instr->dest[0].val);
899
900 struct util_dynarray copies = UTIL_DYNARRAY_INIT;
901
902 unsigned highest_temp = 0;
903 unsigned lowest_temp = ~0;
904
905 enum pco_exec_cnd exec_cnd = pco_instr_get_exec_cnd(instr);
906 pco_foreach_instr_src (psrc, instr) {
907 if (!pco_ref_is_ssa(*psrc) ||
908 !_mesa_hash_table_u64_search(overrides, psrc->val) ||
909 BITSET_TEST(comps, psrc->val)) {
910 unsigned chans = pco_ref_get_chans(*psrc);
911
912 unsigned temp_src_base = ~0U;
913 if (pco_ref_is_ssa(*psrc)) {
914 temp_src_base = ra_get_node_reg(ra_graph, psrc->val);
915
916 struct vec_override *src_override =
917 _mesa_hash_table_u64_search(overrides, psrc->val);
918 if (src_override) {
919 temp_src_base =
920 ra_get_node_reg(ra_graph, src_override->ref.val);
921 temp_src_base += src_override->offset;
922 }
923 } else if (pco_ref_is_vreg(*psrc)) {
924 temp_src_base =
925 ra_get_node_reg(ra_graph, psrc->val + num_ssas);
926 }
927
928 for (unsigned u = 0; u < chans; ++u) {
929 pco_ref dest;
930 if (temp_dest_base + offset >= ctx->allocable_temps) {
931 dest = pco_ref_hwreg(temp_dest_base + offset -
932 ctx->allocable_temps,
933 PCO_REG_CLASS_VTXIN);
934 } else {
935 dest = pco_ref_hwreg(temp_dest_base + offset,
936 PCO_REG_CLASS_TEMP);
937 }
938
939 dest = pco_ref_offset(dest, u);
940 dest = pco_ref_offset(dest, ctx->temp_alloc_offset);
941
942 pco_ref src;
943 if (pco_ref_is_ssa(*psrc) || pco_ref_is_vreg(*psrc)) {
944 if (temp_src_base >= ctx->allocable_temps) {
945 src =
946 pco_ref_hwreg(temp_src_base - ctx->allocable_temps,
947 PCO_REG_CLASS_VTXIN);
948 } else {
949 src = pco_ref_hwreg(temp_src_base, PCO_REG_CLASS_TEMP);
950 }
951 } else {
952 src = pco_ref_chans(*psrc, 1);
953 }
954
955 src = pco_ref_offset(src, u);
956 src = pco_ref_offset(src, ctx->temp_alloc_offset);
957
958 pco_ref_xfer_mods(&src, psrc, false);
959
960 /* if (!pco_refs_are_equal(src, dest, true)) */ {
961 highest_temp =
962 MAX3(highest_temp,
963 pco_ref_is_temp(src) ? pco_ref_get_temp(src)
964 : highest_temp,
965 pco_ref_is_temp(dest) ? pco_ref_get_temp(dest)
966 : highest_temp);
967
968 lowest_temp =
969 MIN3(lowest_temp,
970 pco_ref_is_temp(src) ? pco_ref_get_temp(src)
971 : lowest_temp,
972 pco_ref_is_temp(dest) ? pco_ref_get_temp(dest)
973 : lowest_temp);
974 pco_copy copy = {
975 .src = src,
976 .dest = dest,
977 .s1 = pco_ref_is_reg(src) &&
978 pco_ref_get_reg_class(src) == PCO_REG_CLASS_SPEC,
979 };
980
981 /*
982 if (pco_ref_is_reg(src) &&
983 pco_ref_get_reg_class(src) == PCO_REG_CLASS_SPEC) {
984 pco_movs1(&b, dest, src, .exec_cnd = exec_cnd);
985 } else {
986 pco_mbyp(&b, dest, src, .exec_cnd = exec_cnd);
987 }
988 */
989
990 util_dynarray_append(&copies, copy);
991 }
992 }
993
994 temps = MAX2(temps, temp_dest_base + offset + chans);
995 }
996
997 offset += pco_ref_get_chans(*psrc);
998 }
999
1000 /* Emit copies. */
1001 emit_copies(&b, &copies, exec_cnd, highest_temp, lowest_temp);
1002
1003 util_dynarray_fini(&copies);
1004
1005 pco_instr_delete(instr);
1006 continue;
1007 } else if (instr->op == PCO_OP_COMP) {
1008 pco_instr_delete(instr);
1009 continue;
1010 }
1011
1012 pco_foreach_instr_dest_ssa (pdest, instr) {
1013 struct vec_override *override =
1014 _mesa_hash_table_u64_search(overrides, pdest->val);
1015
1016 unsigned val = ra_get_node_reg(ra_graph, pdest->val);
1017 unsigned dest_temps = val + pco_ref_get_chans(*pdest);
1018 if (override) {
1019 val = ra_get_node_reg(ra_graph, override->ref.val);
1020 dest_temps = val + pco_ref_get_chans(override->ref);
1021 val += override->offset;
1022 }
1023
1024 pdest->type = PCO_REF_TYPE_REG;
1025 pdest->reg_class = PCO_REG_CLASS_TEMP;
1026 pdest->val = val + ctx->temp_alloc_offset;
1027
1028 /* Got a vertex input register. */
1029 if (val >= ctx->allocable_temps) {
1030 pdest->reg_class = PCO_REG_CLASS_VTXIN;
1031 pdest->val = val - ctx->allocable_temps;
1032 vtxins = MAX2(vtxins, dest_temps - ctx->allocable_temps);
1033 } else {
1034 temps = MAX2(temps, dest_temps + ctx->temp_alloc_offset);
1035 }
1036 }
1037
1038 pco_foreach_instr_src_ssa (psrc, instr) {
1039 struct vec_override *override =
1040 _mesa_hash_table_u64_search(overrides, psrc->val);
1041
1042 unsigned val =
1043 override
1044 ? ra_get_node_reg(ra_graph, override->ref.val) + override->offset
1045 : ra_get_node_reg(ra_graph, psrc->val);
1046
1047 psrc->type = PCO_REF_TYPE_REG;
1048 psrc->reg_class = PCO_REG_CLASS_TEMP;
1049 psrc->val = val + ctx->temp_alloc_offset;
1050
1051 /* Got a vertex input register. */
1052 if (val >= ctx->allocable_temps) {
1053 psrc->reg_class = PCO_REG_CLASS_VTXIN;
1054 psrc->val = val - ctx->allocable_temps;
1055 }
1056 }
1057
1058 pco_foreach_instr_dest_vreg (pdest, instr) {
1059 unsigned val = ra_get_node_reg(ra_graph, pdest->val + num_ssas);
1060 unsigned dest_temps = val + 1;
1061
1062 pdest->type = PCO_REF_TYPE_REG;
1063 pdest->reg_class = PCO_REG_CLASS_TEMP;
1064 pdest->val = val + ctx->temp_alloc_offset;
1065
1066 /* Got a vertex input register. */
1067 if (val >= ctx->allocable_temps) {
1068 pdest->reg_class = PCO_REG_CLASS_VTXIN;
1069 pdest->val = val - ctx->allocable_temps;
1070 vtxins = MAX2(vtxins, dest_temps - ctx->allocable_temps);
1071 } else {
1072 temps = MAX2(temps, dest_temps);
1073 }
1074 }
1075
1076 pco_foreach_instr_src_vreg (psrc, instr) {
1077 unsigned val = ra_get_node_reg(ra_graph, psrc->val + num_ssas);
1078
1079 psrc->type = PCO_REF_TYPE_REG;
1080 psrc->reg_class = PCO_REG_CLASS_TEMP;
1081 psrc->val = val + ctx->temp_alloc_offset;
1082
1083 /* Got a vertex input register. */
1084 if (val >= ctx->allocable_temps) {
1085 psrc->reg_class = PCO_REG_CLASS_VTXIN;
1086 psrc->val = val - ctx->allocable_temps;
1087 }
1088 }
1089
1090 /* Drop no-ops. */
1091 if (instr->op == PCO_OP_MBYP &&
1092 (pco_ref_is_ssa(instr->src[0]) || pco_ref_is_vreg(instr->src[0])) &&
1093 pco_refs_are_equal(instr->src[0], instr->dest[0], true)) {
1094 pco_instr_delete(instr);
1095 }
1096 }
1097
1098 ralloc_free(ra_regs);
1099
1100 func->temps = temps;
1101 func->vtxins = vtxins;
1102
1103 if (pco_should_print_shader(func->parent_shader) && PCO_DEBUG_PRINT(RA)) {
1104 printf(
1105 "RA allocated %u temps, %u vtxins, %u interns from %u SSA vars, %u vregs.\n",
1106 temps,
1107 vtxins,
1108 interns,
1109 num_ssas,
1110 num_vregs);
1111 }
1112
1113 ctx->done = true;
1114 return true;
1115 }
1116
1117 /**
1118 * \brief Register allocation pass.
1119 *
1120 * \param[in,out] shader PCO shader.
1121 * \return True if the pass made progress.
1122 */
1123 bool pco_ra(pco_shader *shader)
1124 {
1125 assert(!shader->is_grouped);
1126
1127 /* Instruction indices need to be ordered for live ranges. */
1128 pco_index(shader, false);
1129
1130 unsigned hw_temps = rogue_get_temps(shader->ctx->dev_info);
1131 /* TODO:
1132 * unsigned opt_temps = rogue_get_optimal_temps(shader->ctx->dev_info);
1133 */
1134
1135 /* If any vertex input registers are already used, round up to the nearest
1136 * multiple of 4 as vertex input registers are allocated in blocks of 4.
1137 *
1138 * This number is used by default as the maximum safe number of vertex input
1139 * registers that can be used is not currently known.
1140 */
1141 unsigned hw_vtxins = ALIGN_POT(shader->data.common.vtxins,
1142 ROGUE_USRM_GRANULARITY_IN_REGISTERS);
1143
1144 if (shader->stage != MESA_SHADER_FRAGMENT && !shader->is_internal) {
1145 if (PCO_DEBUG(ALLOC_EXTRA_VTXINS)) {
1146 hw_vtxins = MAX2(hw_vtxins, rogue_get_vtxins());
1147 }
1148 }
1149
1150 /* TODO: different number of temps available if preamble/phase change. */
1151 /* TODO: different number of temps available if barriers are in use. */
1152 /* TODO: support for internal registers. */
1153 pco_ra_ctx ctx = {
1154 .allocable_temps = hw_temps,
1155 .allocable_vtxins = hw_vtxins,
1156 .allocable_interns = 0,
1157 };
1158
1159 if (shader->stage == MESA_SHADER_COMPUTE) {
1160 unsigned wg_size = shader->data.cs.workgroup_size[0] *
1161 shader->data.cs.workgroup_size[1] *
1162 shader->data.cs.workgroup_size[2];
1163 ctx.allocable_temps =
1164 rogue_max_wg_temps(shader->ctx->dev_info,
1165 ctx.allocable_temps,
1166 wg_size,
1167 shader->data.common.uses.barriers);
1168 }
1169
1170 /* Perform register allocation for each function. */
1171 bool progress = false;
1172 pco_foreach_func_in_shader (func, shader) {
1173 ctx.done = false;
1174 while (!ctx.done)
1175 progress |= pco_ra_func(func, &ctx);
1176
1177 shader->data.common.temps = MAX2(shader->data.common.temps, func->temps);
1178 shader->data.common.vtxins =
1179 MAX2(shader->data.common.vtxins, func->vtxins);
1180 }
1181
1182 shader->data.common.spilled_temps = ctx.spilled_temps;
1183 return progress;
1184 }