2 * Copyright (C) 2014 Rob Clark <robclark@freedesktop.org>
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:
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
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 FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 * Rob Clark <robclark@freedesktop.org>
27 #include "util/u_math.h"
28 #include "util/register_allocate.h"
29 #include "util/ralloc.h"
30 #include "util/bitset.h"
33 #include "ir3_compiler.h"
36 * Register Assignment:
38 * Uses the register_allocate util, which implements graph coloring
39 * algo with interference classes. To handle the cases where we need
40 * consecutive registers (for example, texture sample instructions),
41 * we model these as larger (double/quad/etc) registers which conflict
42 * with the corresponding registers in other classes.
44 * Additionally we create additional classes for half-regs, which
45 * do not conflict with the full-reg classes. We do need at least
46 * sizes 1-4 (to deal w/ texture sample instructions output to half-
47 * reg). At the moment we don't create the higher order half-reg
48 * classes as half-reg frequently does not have enough precision
49 * for texture coords at higher resolutions.
51 * There are some additional cases that we need to handle specially,
52 * as the graph coloring algo doesn't understand "partial writes".
53 * For example, a sequence like:
56 * sam (f32)(xy)r0.x, ...
58 * sam (f32)(xyzw)r0.w, r0.x, ... ; 3d texture, so r0.xyz are coord
60 * In this scenario, we treat r0.xyz as class size 3, which is written
61 * (from a use/def perspective) at the 'add' instruction and ignore the
62 * subsequent partial writes to r0.xy. So the 'add r0.z, ...' is the
63 * defining instruction, as it is the first to partially write r0.xyz.
65 * Note i965 has a similar scenario, which they solve with a virtual
66 * LOAD_PAYLOAD instruction which gets turned into multiple MOV's after
67 * register assignment. But for us that is horrible from a scheduling
68 * standpoint. Instead what we do is use idea of 'definer' instruction.
69 * Ie. the first instruction (lowest ip) to write to the variable is the
70 * one we consider from use/def perspective when building interference
71 * graph. (Other instructions which write other variable components
72 * just define the variable some more.)
74 * Arrays of arbitrary size are handled via pre-coloring a consecutive
75 * sequence of registers. Additional scalar (single component) reg
76 * names are allocated starting at ctx->class_base[total_class_count]
77 * (see arr->base), which are pre-colored. In the use/def graph direct
78 * access is treated as a single element use/def, and indirect access
79 * is treated as use or def of all array elements. (Only the first
80 * def is tracked, in case of multiple indirect writes, etc.)
82 * TODO arrays that fit in one of the pre-defined class sizes should
83 * not need to be pre-colored, but instead could be given a normal
84 * vreg name. (Ignoring this for now since it is a good way to work
85 * out the kinks with arbitrary sized arrays.)
87 * TODO might be easier for debugging to split this into two passes,
88 * the first assigning vreg names in a way that we could ir3_print()
92 static const unsigned class_sizes
[] = {
94 4 + 4, /* txd + 1d/2d */
97 #define class_count ARRAY_SIZE(class_sizes)
99 static const unsigned half_class_sizes
[] = {
102 #define half_class_count ARRAY_SIZE(half_class_sizes)
104 /* seems to just be used for compute shaders? Seems like vec1 and vec3
105 * are sufficient (for now?)
107 static const unsigned high_class_sizes
[] = {
110 #define high_class_count ARRAY_SIZE(high_class_sizes)
112 #define total_class_count (class_count + half_class_count + high_class_count)
114 /* Below a0.x are normal regs. RA doesn't need to assign a0.x/p0.x. */
115 #define NUM_REGS (4 * 48) /* r0 to r47 */
116 #define NUM_HIGH_REGS (4 * 8) /* r48 to r55 */
117 #define FIRST_HIGH_REG (4 * 48)
118 /* Number of virtual regs in a given class: */
119 #define CLASS_REGS(i) (NUM_REGS - (class_sizes[i] - 1))
120 #define HALF_CLASS_REGS(i) (NUM_REGS - (half_class_sizes[i] - 1))
121 #define HIGH_CLASS_REGS(i) (NUM_HIGH_REGS - (high_class_sizes[i] - 1))
123 #define HALF_OFFSET (class_count)
124 #define HIGH_OFFSET (class_count + half_class_count)
126 /* register-set, created one time, used for all shaders: */
127 struct ir3_ra_reg_set
{
128 struct ra_regs
*regs
;
129 unsigned int classes
[class_count
];
130 unsigned int half_classes
[half_class_count
];
131 unsigned int high_classes
[high_class_count
];
132 /* maps flat virtual register space to base gpr: */
133 uint16_t *ra_reg_to_gpr
;
134 /* maps cls,gpr to flat virtual register space: */
135 uint16_t **gpr_to_ra_reg
;
139 build_q_values(unsigned int **q_values
, unsigned off
,
140 const unsigned *sizes
, unsigned count
)
142 for (unsigned i
= 0; i
< count
; i
++) {
143 q_values
[i
+ off
] = rzalloc_array(q_values
, unsigned, total_class_count
);
145 /* From register_allocate.c:
147 * q(B,C) (indexed by C, B is this register class) in
148 * Runeson/Nyström paper. This is "how many registers of B could
149 * the worst choice register from C conflict with".
151 * If we just let the register allocation algorithm compute these
152 * values, is extremely expensive. However, since all of our
153 * registers are laid out, we can very easily compute them
154 * ourselves. View the register from C as fixed starting at GRF n
155 * somewhere in the middle, and the register from B as sliding back
156 * and forth. Then the first register to conflict from B is the
157 * one starting at n - class_size[B] + 1 and the last register to
158 * conflict will start at n + class_size[B] - 1. Therefore, the
159 * number of conflicts from B is class_size[B] + class_size[C] - 1.
161 * +-+-+-+-+-+-+ +-+-+-+-+-+-+
162 * B | | | | | |n| --> | | | | | | |
163 * +-+-+-+-+-+-+ +-+-+-+-+-+-+
168 * (Idea copied from brw_fs_reg_allocate.cpp)
170 for (unsigned j
= 0; j
< count
; j
++)
171 q_values
[i
+ off
][j
+ off
] = sizes
[i
] + sizes
[j
] - 1;
175 /* One-time setup of RA register-set, which describes all the possible
176 * "virtual" registers and their interferences. Ie. double register
177 * occupies (and conflicts with) two single registers, and so forth.
178 * Since registers do not need to be aligned to their class size, they
179 * can conflict with other registers in the same class too. Ie:
181 * Single (base) | Double
182 * --------------+---------------
189 * (NOTE the disassembler uses notation like r0.x/y/z/w but those are
190 * really just four scalar registers. Don't let that confuse you.)
192 struct ir3_ra_reg_set
*
193 ir3_ra_alloc_reg_set(struct ir3_compiler
*compiler
)
195 struct ir3_ra_reg_set
*set
= rzalloc(compiler
, struct ir3_ra_reg_set
);
196 unsigned ra_reg_count
, reg
, first_half_reg
, first_high_reg
, base
;
197 unsigned int **q_values
;
199 /* calculate # of regs across all classes: */
201 for (unsigned i
= 0; i
< class_count
; i
++)
202 ra_reg_count
+= CLASS_REGS(i
);
203 for (unsigned i
= 0; i
< half_class_count
; i
++)
204 ra_reg_count
+= HALF_CLASS_REGS(i
);
205 for (unsigned i
= 0; i
< high_class_count
; i
++)
206 ra_reg_count
+= HIGH_CLASS_REGS(i
);
208 /* allocate and populate q_values: */
209 q_values
= ralloc_array(set
, unsigned *, total_class_count
);
211 build_q_values(q_values
, 0, class_sizes
, class_count
);
212 build_q_values(q_values
, HALF_OFFSET
, half_class_sizes
, half_class_count
);
213 build_q_values(q_values
, HIGH_OFFSET
, high_class_sizes
, high_class_count
);
215 /* allocate the reg-set.. */
216 set
->regs
= ra_alloc_reg_set(set
, ra_reg_count
, true);
217 set
->ra_reg_to_gpr
= ralloc_array(set
, uint16_t, ra_reg_count
);
218 set
->gpr_to_ra_reg
= ralloc_array(set
, uint16_t *, total_class_count
);
222 for (unsigned i
= 0; i
< class_count
; i
++) {
223 set
->classes
[i
] = ra_alloc_reg_class(set
->regs
);
225 set
->gpr_to_ra_reg
[i
] = ralloc_array(set
, uint16_t, CLASS_REGS(i
));
227 for (unsigned j
= 0; j
< CLASS_REGS(i
); j
++) {
228 ra_class_add_reg(set
->regs
, set
->classes
[i
], reg
);
230 set
->ra_reg_to_gpr
[reg
] = j
;
231 set
->gpr_to_ra_reg
[i
][j
] = reg
;
233 for (unsigned br
= j
; br
< j
+ class_sizes
[i
]; br
++)
234 ra_add_transitive_reg_conflict(set
->regs
, br
, reg
);
240 first_half_reg
= reg
;
243 for (unsigned i
= 0; i
< half_class_count
; i
++) {
244 set
->half_classes
[i
] = ra_alloc_reg_class(set
->regs
);
246 set
->gpr_to_ra_reg
[base
+ i
] =
247 ralloc_array(set
, uint16_t, HALF_CLASS_REGS(i
));
249 for (unsigned j
= 0; j
< HALF_CLASS_REGS(i
); j
++) {
250 ra_class_add_reg(set
->regs
, set
->half_classes
[i
], reg
);
252 set
->ra_reg_to_gpr
[reg
] = j
;
253 set
->gpr_to_ra_reg
[base
+ i
][j
] = reg
;
255 for (unsigned br
= j
; br
< j
+ half_class_sizes
[i
]; br
++)
256 ra_add_transitive_reg_conflict(set
->regs
, br
+ first_half_reg
, reg
);
262 first_high_reg
= reg
;
265 for (unsigned i
= 0; i
< high_class_count
; i
++) {
266 set
->high_classes
[i
] = ra_alloc_reg_class(set
->regs
);
268 set
->gpr_to_ra_reg
[base
+ i
] =
269 ralloc_array(set
, uint16_t, HIGH_CLASS_REGS(i
));
271 for (unsigned j
= 0; j
< HIGH_CLASS_REGS(i
); j
++) {
272 ra_class_add_reg(set
->regs
, set
->high_classes
[i
], reg
);
274 set
->ra_reg_to_gpr
[reg
] = j
;
275 set
->gpr_to_ra_reg
[base
+ i
][j
] = reg
;
277 for (unsigned br
= j
; br
< j
+ high_class_sizes
[i
]; br
++)
278 ra_add_transitive_reg_conflict(set
->regs
, br
+ first_high_reg
, reg
);
284 /* starting a6xx, half precision regs conflict w/ full precision regs: */
285 if (compiler
->gpu_id
>= 600) {
286 /* because of transitivity, we can get away with just setting up
287 * conflicts between the first class of full and half regs:
289 for (unsigned i
= 0; i
< half_class_count
; i
++) {
290 /* NOTE there are fewer half class sizes, but they match the
291 * first N full class sizes.. but assert in case that ever
292 * accidentially changes:
294 debug_assert(class_sizes
[i
] == half_class_sizes
[i
]);
295 for (unsigned j
= 0; j
< CLASS_REGS(i
) / 2; j
++) {
296 unsigned freg
= set
->gpr_to_ra_reg
[i
][j
];
297 unsigned hreg0
= set
->gpr_to_ra_reg
[i
+ HALF_OFFSET
][(j
* 2) + 0];
298 unsigned hreg1
= set
->gpr_to_ra_reg
[i
+ HALF_OFFSET
][(j
* 2) + 1];
300 ra_add_transitive_reg_conflict(set
->regs
, freg
, hreg0
);
301 ra_add_transitive_reg_conflict(set
->regs
, freg
, hreg1
);
305 // TODO also need to update q_values, but for now:
306 ra_set_finalize(set
->regs
, NULL
);
308 ra_set_finalize(set
->regs
, q_values
);
311 ralloc_free(q_values
);
316 /* additional block-data (per-block) */
317 struct ir3_ra_block_data
{
318 BITSET_WORD
*def
; /* variables defined before used in block */
319 BITSET_WORD
*use
; /* variables used before defined in block */
320 BITSET_WORD
*livein
; /* which defs reach entry point of block */
321 BITSET_WORD
*liveout
; /* which defs reach exit point of block */
324 /* additional instruction-data (per-instruction) */
325 struct ir3_ra_instr_data
{
326 /* cached instruction 'definer' info: */
327 struct ir3_instruction
*defn
;
331 /* register-assign context, per-shader */
333 struct ir3_shader_variant
*v
;
336 struct ir3_ra_reg_set
*set
;
338 unsigned alloc_count
;
339 /* one per class, plus one slot for arrays: */
340 unsigned class_alloc_count
[total_class_count
+ 1];
341 unsigned class_base
[total_class_count
+ 1];
343 unsigned *def
, *use
; /* def/use table */
344 struct ir3_ra_instr_data
*instrd
;
347 /* does it conflict? */
349 intersects(unsigned a_start
, unsigned a_end
, unsigned b_start
, unsigned b_end
)
351 return !((a_start
>= b_end
) || (b_start
>= a_end
));
355 is_half(struct ir3_instruction
*instr
)
357 return !!(instr
->regs
[0]->flags
& IR3_REG_HALF
);
361 is_high(struct ir3_instruction
*instr
)
363 return !!(instr
->regs
[0]->flags
& IR3_REG_HIGH
);
367 size_to_class(unsigned sz
, bool half
, bool high
)
370 for (unsigned i
= 0; i
< high_class_count
; i
++)
371 if (high_class_sizes
[i
] >= sz
)
372 return i
+ HIGH_OFFSET
;
374 for (unsigned i
= 0; i
< half_class_count
; i
++)
375 if (half_class_sizes
[i
] >= sz
)
376 return i
+ HALF_OFFSET
;
378 for (unsigned i
= 0; i
< class_count
; i
++)
379 if (class_sizes
[i
] >= sz
)
387 writes_gpr(struct ir3_instruction
*instr
)
391 if (instr
->regs_count
== 0)
393 /* is dest a normal temp register: */
394 struct ir3_register
*reg
= instr
->regs
[0];
395 if (reg
->flags
& (IR3_REG_CONST
| IR3_REG_IMMED
))
397 if ((reg
->num
== regid(REG_A0
, 0)) ||
398 (reg
->num
== regid(REG_P0
, 0)))
404 instr_before(struct ir3_instruction
*a
, struct ir3_instruction
*b
)
406 if (a
->flags
& IR3_INSTR_UNUSED
)
408 return (a
->ip
< b
->ip
);
411 static struct ir3_instruction
*
412 get_definer(struct ir3_ra_ctx
*ctx
, struct ir3_instruction
*instr
,
415 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
416 struct ir3_instruction
*d
= NULL
;
424 if (instr
->opc
== OPC_META_COLLECT
) {
425 /* What about the case where collect is subset of array, we
426 * need to find the distance between where actual array starts
427 * and collect.. that probably doesn't happen currently.
429 struct ir3_register
*src
;
432 /* note: don't use foreach_ssa_src as this gets called once
433 * while assigning regs (which clears SSA flag)
435 foreach_src_n(src
, n
, instr
) {
436 struct ir3_instruction
*dd
;
440 dd
= get_definer(ctx
, src
->instr
, &dsz
, &doff
);
442 if ((!d
) || instr_before(dd
, d
)) {
449 } else if (instr
->cp
.right
|| instr
->cp
.left
) {
450 /* covers also the meta:fo case, which ends up w/ single
451 * scalar instructions for each component:
453 struct ir3_instruction
*f
= ir3_neighbor_first(instr
);
455 /* by definition, the entire sequence forms one linked list
456 * of single scalar register nodes (even if some of them may
457 * be splits from a texture sample (for example) instr. We
458 * just need to walk the list finding the first element of
459 * the group defined (lowest ip)
463 /* need to skip over unused in the group: */
464 while (f
&& (f
->flags
& IR3_INSTR_UNUSED
)) {
470 if ((!d
) || instr_before(f
, d
))
481 /* second case is looking directly at the instruction which
482 * produces multiple values (eg, texture sample), rather
483 * than the split nodes that point back to that instruction.
484 * This isn't quite right, because it may be part of a larger
487 * sam (f32)(xyzw)r0.x, ...
490 * sam (f32)(xyzw)r2.x, r0.w <-- (r0.w, r1.x, r1.y)
492 * need to come up with a better way to handle that case.
494 if (instr
->address
) {
495 *sz
= instr
->regs
[0]->size
;
497 *sz
= util_last_bit(instr
->regs
[0]->wrmask
);
503 if (d
->opc
== OPC_META_SPLIT
) {
504 struct ir3_instruction
*dd
;
507 dd
= get_definer(ctx
, d
->regs
[1]->instr
, &dsz
, &doff
);
509 /* by definition, should come before: */
510 debug_assert(instr_before(dd
, d
));
512 *sz
= MAX2(*sz
, dsz
);
514 if (instr
->opc
== OPC_META_SPLIT
)
515 *off
= MAX2(*off
, instr
->split
.off
);
520 debug_assert(d
->opc
!= OPC_META_SPLIT
);
530 ra_block_find_definers(struct ir3_ra_ctx
*ctx
, struct ir3_block
*block
)
532 list_for_each_entry (struct ir3_instruction
, instr
, &block
->instr_list
, node
) {
533 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
534 if (instr
->regs_count
== 0)
536 /* couple special cases: */
537 if (writes_addr(instr
) || writes_pred(instr
)) {
539 } else if (instr
->regs
[0]->flags
& IR3_REG_ARRAY
) {
540 id
->cls
= total_class_count
;
542 /* and the normal case: */
543 id
->defn
= get_definer(ctx
, instr
, &id
->sz
, &id
->off
);
544 id
->cls
= size_to_class(id
->sz
, is_half(id
->defn
), is_high(id
->defn
));
546 /* this is a bit of duct-tape.. if we have a scenario like:
548 * sam (f32)(x) out.x, ...
549 * sam (f32)(x) out.y, ...
551 * Then the fanout/split meta instructions for the two different
552 * tex instructions end up grouped as left/right neighbors. The
553 * upshot is that in when you get_definer() on one of the meta:fo's
554 * you get definer as the first sam with sz=2, but when you call
555 * get_definer() on the either of the sam's you get itself as the
558 * (We actually avoid this scenario exactly, the neighbor links
559 * prevent one of the output mov's from being eliminated, so this
560 * hack should be enough. But probably we need to rethink how we
561 * find the "defining" instruction.)
563 * TODO how do we figure out offset properly...
565 if (id
->defn
!= instr
) {
566 struct ir3_ra_instr_data
*did
= &ctx
->instrd
[id
->defn
->ip
];
567 if (did
->sz
< id
->sz
) {
576 /* give each instruction a name (and ip), and count up the # of names
580 ra_block_name_instructions(struct ir3_ra_ctx
*ctx
, struct ir3_block
*block
)
582 list_for_each_entry (struct ir3_instruction
, instr
, &block
->instr_list
, node
) {
583 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
591 if (!writes_gpr(instr
))
594 if (id
->defn
!= instr
)
597 /* arrays which don't fit in one of the pre-defined class
598 * sizes are pre-colored:
600 if ((id
->cls
>= 0) && (id
->cls
< total_class_count
)) {
601 instr
->name
= ctx
->class_alloc_count
[id
->cls
]++;
608 ra_init(struct ir3_ra_ctx
*ctx
)
612 ir3_clear_mark(ctx
->ir
);
613 n
= ir3_count_instructions(ctx
->ir
);
615 ctx
->instrd
= rzalloc_array(NULL
, struct ir3_ra_instr_data
, n
);
617 list_for_each_entry (struct ir3_block
, block
, &ctx
->ir
->block_list
, node
) {
618 ra_block_find_definers(ctx
, block
);
621 list_for_each_entry (struct ir3_block
, block
, &ctx
->ir
->block_list
, node
) {
622 ra_block_name_instructions(ctx
, block
);
625 /* figure out the base register name for each class. The
626 * actual ra name is class_base[cls] + instr->name;
628 ctx
->class_base
[0] = 0;
629 for (unsigned i
= 1; i
<= total_class_count
; i
++) {
630 ctx
->class_base
[i
] = ctx
->class_base
[i
-1] +
631 ctx
->class_alloc_count
[i
-1];
634 /* and vreg names for array elements: */
635 base
= ctx
->class_base
[total_class_count
];
636 list_for_each_entry (struct ir3_array
, arr
, &ctx
->ir
->array_list
, node
) {
638 ctx
->class_alloc_count
[total_class_count
] += arr
->length
;
641 ctx
->alloc_count
+= ctx
->class_alloc_count
[total_class_count
];
643 ctx
->g
= ra_alloc_interference_graph(ctx
->set
->regs
, ctx
->alloc_count
);
644 ralloc_steal(ctx
->g
, ctx
->instrd
);
645 ctx
->def
= rzalloc_array(ctx
->g
, unsigned, ctx
->alloc_count
);
646 ctx
->use
= rzalloc_array(ctx
->g
, unsigned, ctx
->alloc_count
);
650 __ra_name(struct ir3_ra_ctx
*ctx
, int cls
, struct ir3_instruction
*defn
)
653 debug_assert(cls
>= 0);
654 debug_assert(cls
< total_class_count
); /* we shouldn't get arrays here.. */
655 name
= ctx
->class_base
[cls
] + defn
->name
;
656 debug_assert(name
< ctx
->alloc_count
);
661 ra_name(struct ir3_ra_ctx
*ctx
, struct ir3_ra_instr_data
*id
)
663 /* TODO handle name mapping for arrays */
664 return __ra_name(ctx
, id
->cls
, id
->defn
);
668 ra_destroy(struct ir3_ra_ctx
*ctx
)
674 ra_block_compute_live_ranges(struct ir3_ra_ctx
*ctx
, struct ir3_block
*block
)
676 struct ir3_ra_block_data
*bd
;
677 unsigned bitset_words
= BITSET_WORDS(ctx
->alloc_count
);
679 #define def(name, instr) \
681 /* defined on first write: */ \
682 if (!ctx->def[name]) \
683 ctx->def[name] = instr->ip; \
684 ctx->use[name] = instr->ip; \
685 BITSET_SET(bd->def, name); \
688 #define use(name, instr) \
690 ctx->use[name] = MAX2(ctx->use[name], instr->ip); \
691 if (!BITSET_TEST(bd->def, name)) \
692 BITSET_SET(bd->use, name); \
695 bd
= rzalloc(ctx
->g
, struct ir3_ra_block_data
);
697 bd
->def
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
698 bd
->use
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
699 bd
->livein
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
700 bd
->liveout
= rzalloc_array(bd
, BITSET_WORD
, bitset_words
);
704 struct ir3_instruction
*first_non_input
= NULL
;
705 list_for_each_entry (struct ir3_instruction
, instr
, &block
->instr_list
, node
) {
706 if (instr
->opc
!= OPC_META_INPUT
) {
707 first_non_input
= instr
;
713 list_for_each_entry (struct ir3_instruction
, instr
, &block
->instr_list
, node
) {
714 struct ir3_instruction
*src
;
715 struct ir3_register
*reg
;
717 /* There are a couple special cases to deal with here:
719 * split: used to split values from a higher class to a lower
720 * class, for example split the results of a texture fetch
721 * into individual scalar values; We skip over these from
722 * a 'def' perspective, and for a 'use' we walk the chain
723 * up to the defining instruction.
725 * collect: used to collect values from lower class and assemble
726 * them together into a higher class, for example arguments
727 * to texture sample instructions; We consider these to be
728 * defined at the earliest collect source.
730 * Most of this is handled in the get_definer() helper.
732 * In either case, we trace the instruction back to the original
733 * definer and consider that as the def/use ip.
736 if (writes_gpr(instr
)) {
737 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
738 struct ir3_register
*dst
= instr
->regs
[0];
740 if (dst
->flags
& IR3_REG_ARRAY
) {
741 struct ir3_array
*arr
=
742 ir3_lookup_array(ctx
->ir
, dst
->array
.id
);
745 arr
->start_ip
= MIN2(arr
->start_ip
, instr
->ip
);
746 arr
->end_ip
= MAX2(arr
->end_ip
, instr
->ip
);
748 /* set the node class now.. in case we don't encounter
749 * this array dst again. From register_alloc algo's
750 * perspective, these are all single/scalar regs:
752 for (i
= 0; i
< arr
->length
; i
++) {
753 unsigned name
= arr
->base
+ i
;
754 ra_set_node_class(ctx
->g
, name
, ctx
->set
->classes
[0]);
757 /* indirect write is treated like a write to all array
758 * elements, since we don't know which one is actually
761 if (dst
->flags
& IR3_REG_RELATIV
) {
762 for (i
= 0; i
< arr
->length
; i
++) {
763 unsigned name
= arr
->base
+ i
;
767 unsigned name
= arr
->base
+ dst
->array
.offset
;
771 } else if (id
->defn
== instr
) {
772 unsigned name
= ra_name(ctx
, id
);
774 /* since we are in SSA at this point: */
775 debug_assert(!BITSET_TEST(bd
->use
, name
));
779 if (instr
->opc
== OPC_META_INPUT
)
780 use(name
, first_non_input
);
782 if (is_high(id
->defn
)) {
783 ra_set_node_class(ctx
->g
, name
,
784 ctx
->set
->high_classes
[id
->cls
- HIGH_OFFSET
]);
785 } else if (is_half(id
->defn
)) {
786 ra_set_node_class(ctx
->g
, name
,
787 ctx
->set
->half_classes
[id
->cls
- HALF_OFFSET
]);
789 ra_set_node_class(ctx
->g
, name
,
790 ctx
->set
->classes
[id
->cls
]);
795 foreach_src(reg
, instr
) {
796 if (reg
->flags
& IR3_REG_ARRAY
) {
797 struct ir3_array
*arr
=
798 ir3_lookup_array(ctx
->ir
, reg
->array
.id
);
799 arr
->start_ip
= MIN2(arr
->start_ip
, instr
->ip
);
800 arr
->end_ip
= MAX2(arr
->end_ip
, instr
->ip
);
802 /* indirect read is treated like a read fromall array
803 * elements, since we don't know which one is actually
806 if (reg
->flags
& IR3_REG_RELATIV
) {
808 for (i
= 0; i
< arr
->length
; i
++) {
809 unsigned name
= arr
->base
+ i
;
813 unsigned name
= arr
->base
+ reg
->array
.offset
;
815 /* NOTE: arrays are not SSA so unconditionally
818 BITSET_SET(bd
->use
, name
);
819 debug_assert(reg
->array
.offset
< arr
->length
);
821 } else if ((src
= ssa(reg
)) && writes_gpr(src
)) {
822 unsigned name
= ra_name(ctx
, &ctx
->instrd
[src
->ip
]);
830 ra_compute_livein_liveout(struct ir3_ra_ctx
*ctx
)
832 unsigned bitset_words
= BITSET_WORDS(ctx
->alloc_count
);
833 bool progress
= false;
835 list_for_each_entry (struct ir3_block
, block
, &ctx
->ir
->block_list
, node
) {
836 struct ir3_ra_block_data
*bd
= block
->data
;
839 for (unsigned i
= 0; i
< bitset_words
; i
++) {
840 BITSET_WORD new_livein
=
841 (bd
->use
[i
] | (bd
->liveout
[i
] & ~bd
->def
[i
]));
843 if (new_livein
& ~bd
->livein
[i
]) {
844 bd
->livein
[i
] |= new_livein
;
849 /* update liveout: */
850 for (unsigned j
= 0; j
< ARRAY_SIZE(block
->successors
); j
++) {
851 struct ir3_block
*succ
= block
->successors
[j
];
852 struct ir3_ra_block_data
*succ_bd
;
857 succ_bd
= succ
->data
;
859 for (unsigned i
= 0; i
< bitset_words
; i
++) {
860 BITSET_WORD new_liveout
=
861 (succ_bd
->livein
[i
] & ~bd
->liveout
[i
]);
864 bd
->liveout
[i
] |= new_liveout
;
875 print_bitset(const char *name
, BITSET_WORD
*bs
, unsigned cnt
)
878 debug_printf(" %s:", name
);
879 for (unsigned i
= 0; i
< cnt
; i
++) {
880 if (BITSET_TEST(bs
, i
)) {
883 debug_printf(" %04u", i
);
891 ra_add_interference(struct ir3_ra_ctx
*ctx
)
893 struct ir3
*ir
= ctx
->ir
;
895 /* initialize array live ranges: */
896 list_for_each_entry (struct ir3_array
, arr
, &ir
->array_list
, node
) {
901 /* compute live ranges (use/def) on a block level, also updating
902 * block's def/use bitmasks (used below to calculate per-block
905 list_for_each_entry (struct ir3_block
, block
, &ir
->block_list
, node
) {
906 ra_block_compute_live_ranges(ctx
, block
);
909 /* update per-block livein/liveout: */
910 while (ra_compute_livein_liveout(ctx
)) {}
912 if (ir3_shader_debug
& IR3_DBG_OPTMSGS
) {
913 debug_printf("AFTER LIVEIN/OUT:\n");
914 list_for_each_entry (struct ir3_block
, block
, &ir
->block_list
, node
) {
915 struct ir3_ra_block_data
*bd
= block
->data
;
916 debug_printf("block%u:\n", block_id(block
));
917 print_bitset(" def", bd
->def
, ctx
->alloc_count
);
918 print_bitset(" use", bd
->use
, ctx
->alloc_count
);
919 print_bitset(" l/i", bd
->livein
, ctx
->alloc_count
);
920 print_bitset(" l/o", bd
->liveout
, ctx
->alloc_count
);
922 list_for_each_entry (struct ir3_array
, arr
, &ir
->array_list
, node
) {
923 debug_printf("array%u:\n", arr
->id
);
924 debug_printf(" length: %u\n", arr
->length
);
925 debug_printf(" start_ip: %u\n", arr
->start_ip
);
926 debug_printf(" end_ip: %u\n", arr
->end_ip
);
930 /* extend start/end ranges based on livein/liveout info from cfg: */
931 list_for_each_entry (struct ir3_block
, block
, &ir
->block_list
, node
) {
932 struct ir3_ra_block_data
*bd
= block
->data
;
934 for (unsigned i
= 0; i
< ctx
->alloc_count
; i
++) {
935 if (BITSET_TEST(bd
->livein
, i
)) {
936 ctx
->def
[i
] = MIN2(ctx
->def
[i
], block
->start_ip
);
937 ctx
->use
[i
] = MAX2(ctx
->use
[i
], block
->start_ip
);
940 if (BITSET_TEST(bd
->liveout
, i
)) {
941 ctx
->def
[i
] = MIN2(ctx
->def
[i
], block
->end_ip
);
942 ctx
->use
[i
] = MAX2(ctx
->use
[i
], block
->end_ip
);
946 list_for_each_entry (struct ir3_array
, arr
, &ctx
->ir
->array_list
, node
) {
947 for (unsigned i
= 0; i
< arr
->length
; i
++) {
948 if (BITSET_TEST(bd
->livein
, i
+ arr
->base
)) {
949 arr
->start_ip
= MIN2(arr
->start_ip
, block
->start_ip
);
951 if (BITSET_TEST(bd
->livein
, i
+ arr
->base
)) {
952 arr
->end_ip
= MAX2(arr
->end_ip
, block
->end_ip
);
958 /* need to fix things up to keep outputs live: */
959 struct ir3_instruction
*out
;
960 foreach_output(out
, ir
) {
961 unsigned name
= ra_name(ctx
, &ctx
->instrd
[out
->ip
]);
962 ctx
->use
[name
] = ctx
->instr_cnt
;
965 for (unsigned i
= 0; i
< ctx
->alloc_count
; i
++) {
966 for (unsigned j
= 0; j
< ctx
->alloc_count
; j
++) {
967 if (intersects(ctx
->def
[i
], ctx
->use
[i
],
968 ctx
->def
[j
], ctx
->use
[j
])) {
969 ra_add_node_interference(ctx
->g
, i
, j
);
975 /* some instructions need fix-up if dst register is half precision: */
976 static void fixup_half_instr_dst(struct ir3_instruction
*instr
)
978 switch (opc_cat(instr
->opc
)) {
979 case 1: /* move instructions */
980 instr
->cat1
.dst_type
= half_type(instr
->cat1
.dst_type
);
983 switch (instr
->opc
) {
985 instr
->opc
= OPC_MAD_F16
;
988 instr
->opc
= OPC_SEL_B16
;
991 instr
->opc
= OPC_SEL_S16
;
994 instr
->opc
= OPC_SEL_F16
;
997 instr
->opc
= OPC_SAD_S16
;
999 /* instructions may already be fixed up: */
1012 instr
->cat5
.type
= half_type(instr
->cat5
.type
);
1016 /* some instructions need fix-up if src register is half precision: */
1017 static void fixup_half_instr_src(struct ir3_instruction
*instr
)
1019 switch (instr
->opc
) {
1021 instr
->cat1
.src_type
= half_type(instr
->cat1
.src_type
);
1028 /* NOTE: instr could be NULL for IR3_REG_ARRAY case, for the first
1029 * array access(es) which do not have any previous access to depend
1030 * on from scheduling point of view
1033 reg_assign(struct ir3_ra_ctx
*ctx
, struct ir3_register
*reg
,
1034 struct ir3_instruction
*instr
)
1036 struct ir3_ra_instr_data
*id
;
1038 if (reg
->flags
& IR3_REG_ARRAY
) {
1039 struct ir3_array
*arr
=
1040 ir3_lookup_array(ctx
->ir
, reg
->array
.id
);
1041 unsigned name
= arr
->base
+ reg
->array
.offset
;
1042 unsigned r
= ra_get_node_reg(ctx
->g
, name
);
1043 unsigned num
= ctx
->set
->ra_reg_to_gpr
[r
];
1045 if (reg
->flags
& IR3_REG_RELATIV
) {
1046 reg
->array
.offset
= num
;
1049 reg
->flags
&= ~IR3_REG_SSA
;
1052 reg
->flags
&= ~IR3_REG_ARRAY
;
1053 } else if ((id
= &ctx
->instrd
[instr
->ip
]) && id
->defn
) {
1054 unsigned name
= ra_name(ctx
, id
);
1055 unsigned r
= ra_get_node_reg(ctx
->g
, name
);
1056 unsigned num
= ctx
->set
->ra_reg_to_gpr
[r
] + id
->off
;
1058 debug_assert(!(reg
->flags
& IR3_REG_RELATIV
));
1060 if (is_high(id
->defn
))
1061 num
+= FIRST_HIGH_REG
;
1064 reg
->flags
&= ~IR3_REG_SSA
;
1066 if (is_half(id
->defn
))
1067 reg
->flags
|= IR3_REG_HALF
;
1072 ra_block_alloc(struct ir3_ra_ctx
*ctx
, struct ir3_block
*block
)
1074 list_for_each_entry (struct ir3_instruction
, instr
, &block
->instr_list
, node
) {
1075 struct ir3_register
*reg
;
1077 if (writes_gpr(instr
)) {
1078 reg_assign(ctx
, instr
->regs
[0], instr
);
1079 if (instr
->regs
[0]->flags
& IR3_REG_HALF
)
1080 fixup_half_instr_dst(instr
);
1083 foreach_src_n(reg
, n
, instr
) {
1084 struct ir3_instruction
*src
= reg
->instr
;
1085 /* Note: reg->instr could be null for IR3_REG_ARRAY */
1086 if (src
|| (reg
->flags
& IR3_REG_ARRAY
))
1087 reg_assign(ctx
, instr
->regs
[n
+1], src
);
1088 if (instr
->regs
[n
+1]->flags
& IR3_REG_HALF
)
1089 fixup_half_instr_src(instr
);
1094 /* handle pre-colored registers. This includes "arrays" (which could be of
1095 * length 1, used for phi webs lowered to registers in nir), as well as
1096 * special shader input values that need to be pinned to certain registers.
1099 ra_precolor(struct ir3_ra_ctx
*ctx
, struct ir3_instruction
**precolor
, unsigned nprecolor
)
1101 unsigned num_precolor
= 0;
1102 for (unsigned i
= 0; i
< nprecolor
; i
++) {
1103 if (precolor
[i
] && !(precolor
[i
]->flags
& IR3_INSTR_UNUSED
)) {
1104 struct ir3_instruction
*instr
= precolor
[i
];
1105 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
1107 debug_assert(!(instr
->regs
[0]->flags
& (IR3_REG_HALF
| IR3_REG_HIGH
)));
1109 /* only consider the first component: */
1113 /* 'base' is in scalar (class 0) but we need to map that
1114 * the conflicting register of the appropriate class (ie.
1115 * input could be vec2/vec3/etc)
1117 * Note that the higher class (larger than scalar) regs
1118 * are setup to conflict with others in the same class,
1119 * so for example, R1 (scalar) is also the first component
1120 * of D1 (vec2/double):
1122 * Single (base) | Double
1123 * --------------+---------------
1130 unsigned regid
= instr
->regs
[0]->num
;
1131 unsigned reg
= ctx
->set
->gpr_to_ra_reg
[id
->cls
][regid
];
1132 unsigned name
= ra_name(ctx
, id
);
1133 ra_set_node_reg(ctx
->g
, name
, reg
);
1134 num_precolor
= MAX2(regid
, num_precolor
);
1138 /* pre-assign array elements:
1140 list_for_each_entry (struct ir3_array
, arr
, &ctx
->ir
->array_list
, node
) {
1143 if (arr
->end_ip
== 0)
1146 /* figure out what else we conflict with which has already
1150 list_for_each_entry (struct ir3_array
, arr2
, &ctx
->ir
->array_list
, node
) {
1153 if (arr2
->end_ip
== 0)
1155 /* if it intersects with liverange AND register range.. */
1156 if (intersects(arr
->start_ip
, arr
->end_ip
,
1157 arr2
->start_ip
, arr2
->end_ip
) &&
1158 intersects(base
, base
+ arr
->length
,
1159 arr2
->reg
, arr2
->reg
+ arr2
->length
)) {
1160 base
= MAX2(base
, arr2
->reg
+ arr2
->length
);
1165 /* also need to not conflict with any pre-assigned inputs: */
1166 for (unsigned i
= 0; i
< nprecolor
; i
++) {
1167 struct ir3_instruction
*instr
= precolor
[i
];
1172 struct ir3_ra_instr_data
*id
= &ctx
->instrd
[instr
->ip
];
1174 /* only consider the first component: */
1178 unsigned name
= ra_name(ctx
, id
);
1179 unsigned regid
= instr
->regs
[0]->num
;
1181 /* Check if array intersects with liverange AND register
1182 * range of the input:
1184 if (intersects(arr
->start_ip
, arr
->end_ip
,
1185 ctx
->def
[name
], ctx
->use
[name
]) &&
1186 intersects(base
, base
+ arr
->length
,
1187 regid
, regid
+ class_sizes
[id
->cls
])) {
1188 base
= MAX2(base
, regid
+ class_sizes
[id
->cls
]);
1195 for (unsigned i
= 0; i
< arr
->length
; i
++) {
1198 name
= arr
->base
+ i
;
1199 reg
= ctx
->set
->gpr_to_ra_reg
[0][base
++];
1201 ra_set_node_reg(ctx
->g
, name
, reg
);
1207 ra_alloc(struct ir3_ra_ctx
*ctx
)
1209 if (!ra_allocate(ctx
->g
))
1212 list_for_each_entry (struct ir3_block
, block
, &ctx
->ir
->block_list
, node
) {
1213 ra_block_alloc(ctx
, block
);
1219 int ir3_ra(struct ir3_shader_variant
*v
, struct ir3_instruction
**precolor
, unsigned nprecolor
)
1221 struct ir3_ra_ctx ctx
= {
1224 .set
= v
->ir
->compiler
->set
,
1229 ra_add_interference(&ctx
);
1230 ra_precolor(&ctx
, precolor
, nprecolor
);
1231 ret
= ra_alloc(&ctx
);