2 * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
3 * Copyright (C) 2019 Collabora, Ltd.
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 #include "midgard_ops.h"
27 #include "util/u_math.h"
28 #include "util/u_memory.h"
30 #include "midgard_quirks.h"
33 /* Physical register: 0-31 */
36 /* Byte offset into the physical register: 0-15 */
39 /* Number of bytes in a component of this register */
43 /* Shift up by reg_offset and horizontally by dst_offset. */
46 offset_swizzle(unsigned *swizzle
, unsigned reg_offset
, unsigned srcsize
, unsigned dst_offset
)
48 unsigned out
[MIR_VEC_COMPONENTS
];
50 signed reg_comp
= reg_offset
/ srcsize
;
51 signed dst_comp
= dst_offset
/ srcsize
;
53 unsigned max_component
= (16 / srcsize
) - 1;
55 assert(reg_comp
* srcsize
== reg_offset
);
56 assert(dst_comp
* srcsize
== dst_offset
);
58 for (signed c
= 0; c
< MIR_VEC_COMPONENTS
; ++c
) {
59 signed comp
= MAX2(c
- dst_comp
, 0);
60 out
[c
] = MIN2(swizzle
[comp
] + reg_comp
, max_component
);
63 memcpy(swizzle
, out
, sizeof(out
));
66 /* Helper to return the default phys_reg for a given register */
68 static struct phys_reg
69 default_phys_reg(int reg
, midgard_reg_mode size
)
74 .size
= mir_bytes_for_mode(size
)
80 /* Determine which physical register, swizzle, and mask a virtual
81 * register corresponds to */
83 static struct phys_reg
84 index_to_reg(compiler_context
*ctx
, struct lcra_state
*l
, unsigned reg
, midgard_reg_mode size
)
86 /* Check for special cases */
88 return default_phys_reg(REGISTER_UNUSED
, size
);
89 else if (reg
>= SSA_FIXED_MINIMUM
)
90 return default_phys_reg(SSA_REG_FROM_FIXED(reg
), size
);
92 return default_phys_reg(REGISTER_UNUSED
, size
);
95 .reg
= l
->solutions
[reg
] / 16,
96 .offset
= l
->solutions
[reg
] & 0xF,
97 .size
= mir_bytes_for_mode(size
)
100 /* Report that we actually use this register, and return it */
103 ctx
->work_registers
= MAX2(ctx
->work_registers
, r
.reg
);
109 set_class(unsigned *classes
, unsigned node
, unsigned class)
111 if (node
< SSA_FIXED_MINIMUM
&& class != classes
[node
]) {
112 assert(classes
[node
] == REG_CLASS_WORK
);
113 classes
[node
] = class;
117 /* Special register classes impose special constraints on who can read their
118 * values, so check that */
121 check_read_class(unsigned *classes
, unsigned tag
, unsigned node
)
123 /* Non-nodes are implicitly ok */
124 if (node
>= SSA_FIXED_MINIMUM
)
127 switch (classes
[node
]) {
129 return (tag
== TAG_LOAD_STORE_4
);
131 return (tag
== TAG_TEXTURE_4
);
133 return (tag
!= TAG_LOAD_STORE_4
);
137 unreachable("Invalid class");
142 check_write_class(unsigned *classes
, unsigned tag
, unsigned node
)
144 /* Non-nodes are implicitly ok */
145 if (node
>= SSA_FIXED_MINIMUM
)
148 switch (classes
[node
]) {
152 return (tag
== TAG_TEXTURE_4
);
155 return IS_ALU(tag
) || (tag
== TAG_LOAD_STORE_4
);
157 unreachable("Invalid class");
161 /* Prepass before RA to ensure special class restrictions are met. The idea is
162 * to create a bit field of types of instructions that read a particular index.
163 * Later, we'll add moves as appropriate and rewrite to specialize by type. */
166 mark_node_class (unsigned *bitfield
, unsigned node
)
168 if (node
< SSA_FIXED_MINIMUM
)
169 BITSET_SET(bitfield
, node
);
173 mir_lower_special_reads(compiler_context
*ctx
)
175 size_t sz
= BITSET_WORDS(ctx
->temp_count
) * sizeof(BITSET_WORD
);
177 /* Bitfields for the various types of registers we could have. aluw can
178 * be written by either ALU or load/store */
180 unsigned *alur
= calloc(sz
, 1);
181 unsigned *aluw
= calloc(sz
, 1);
182 unsigned *brar
= calloc(sz
, 1);
183 unsigned *ldst
= calloc(sz
, 1);
184 unsigned *texr
= calloc(sz
, 1);
185 unsigned *texw
= calloc(sz
, 1);
187 /* Pass #1 is analysis, a linear scan to fill out the bitfields */
189 mir_foreach_instr_global(ctx
, ins
) {
192 mark_node_class(aluw
, ins
->dest
);
193 mark_node_class(alur
, ins
->src
[0]);
194 mark_node_class(alur
, ins
->src
[1]);
195 mark_node_class(alur
, ins
->src
[2]);
197 if (ins
->compact_branch
&& ins
->writeout
)
198 mark_node_class(brar
, ins
->src
[0]);
202 case TAG_LOAD_STORE_4
:
203 mark_node_class(aluw
, ins
->dest
);
204 mark_node_class(ldst
, ins
->src
[0]);
205 mark_node_class(ldst
, ins
->src
[1]);
206 mark_node_class(ldst
, ins
->src
[2]);
210 mark_node_class(texr
, ins
->src
[0]);
211 mark_node_class(texr
, ins
->src
[1]);
212 mark_node_class(texr
, ins
->src
[2]);
213 mark_node_class(texw
, ins
->dest
);
218 /* Pass #2 is lowering now that we've analyzed all the classes.
219 * Conceptually, if an index is only marked for a single type of use,
220 * there is nothing to lower. If it is marked for different uses, we
221 * split up based on the number of types of uses. To do so, we divide
222 * into N distinct classes of use (where N>1 by definition), emit N-1
223 * moves from the index to copies of the index, and finally rewrite N-1
224 * of the types of uses to use the corresponding move */
226 unsigned spill_idx
= ctx
->temp_count
;
228 for (unsigned i
= 0; i
< ctx
->temp_count
; ++i
) {
229 bool is_alur
= BITSET_TEST(alur
, i
);
230 bool is_aluw
= BITSET_TEST(aluw
, i
);
231 bool is_brar
= BITSET_TEST(brar
, i
);
232 bool is_ldst
= BITSET_TEST(ldst
, i
);
233 bool is_texr
= BITSET_TEST(texr
, i
);
234 bool is_texw
= BITSET_TEST(texw
, i
);
236 /* Analyse to check how many distinct uses there are. ALU ops
237 * (alur) can read the results of the texture pipeline (texw)
238 * but not ldst or texr. Load/store ops (ldst) cannot read
239 * anything but load/store inputs. Texture pipeline cannot read
240 * anything but texture inputs. TODO: Simplify. */
243 (is_alur
&& (is_ldst
|| is_texr
)) ||
244 (is_ldst
&& (is_alur
|| is_texr
|| is_texw
)) ||
245 (is_texr
&& (is_alur
|| is_ldst
|| is_texw
)) ||
246 (is_texw
&& (is_aluw
|| is_ldst
|| is_texr
)) ||
247 (is_brar
&& is_texw
);
252 /* Use the index as-is as the work copy. Emit copies for
255 unsigned classes
[] = { TAG_LOAD_STORE_4
, TAG_TEXTURE_4
, TAG_TEXTURE_4
, TAG_ALU_4
};
256 bool collisions
[] = { is_ldst
, is_texr
, is_texw
&& is_aluw
, is_brar
};
258 for (unsigned j
= 0; j
< ARRAY_SIZE(collisions
); ++j
) {
259 if (!collisions
[j
]) continue;
261 /* When the hazard is from reading, we move and rewrite
262 * sources (typical case). When it's from writing, we
263 * flip the move and rewrite destinations (obscure,
264 * only from control flow -- impossible in SSA) */
266 bool hazard_write
= (j
== 2);
268 unsigned idx
= spill_idx
++;
270 midgard_instruction m
= hazard_write
?
271 v_mov(idx
, i
) : v_mov(i
, idx
);
273 /* Insert move before each read/write, depending on the
274 * hazard we're trying to account for */
276 mir_foreach_instr_global_safe(ctx
, pre_use
) {
277 if (pre_use
->type
!= classes
[j
])
281 if (pre_use
->dest
!= i
)
284 if (!mir_has_arg(pre_use
, i
))
289 midgard_instruction
*use
= mir_next_op(pre_use
);
291 mir_insert_instruction_before(ctx
, use
, m
);
292 mir_rewrite_index_dst_single(pre_use
, i
, idx
);
296 m
.mask
= mir_from_bytemask(mir_bytemask_of_read_components(pre_use
, i
), midgard_reg_mode_32
);
297 mir_insert_instruction_before(ctx
, pre_use
, m
);
298 mir_rewrite_index_src_single(pre_use
, i
, idx
);
312 /* We register allocate after scheduling, so we need to ensure instructions
313 * executing in parallel within a segment of a bundle don't clobber each
314 * other's registers. This is mostly a non-issue thanks to scheduling, but
315 * there are edge cases. In particular, after a register is written in a
316 * segment, it interferes with anything reading. */
319 mir_compute_segment_interference(
320 compiler_context
*ctx
,
321 struct lcra_state
*l
,
326 for (unsigned j
= pivot
; j
< i
; ++j
) {
327 mir_foreach_src(bun
->instructions
[j
], s
) {
328 if (bun
->instructions
[j
]->src
[s
] >= ctx
->temp_count
)
331 for (unsigned q
= pivot
; q
< i
; ++q
) {
332 if (bun
->instructions
[q
]->dest
>= ctx
->temp_count
)
335 /* See dEQP-GLES2.functional.shaders.return.output_write_in_func_dynamic_fragment */
338 if (!(bun
->instructions
[j
]->unit
== UNIT_SMUL
&& bun
->instructions
[q
]->unit
== UNIT_VLUT
))
342 unsigned mask
= mir_bytemask(bun
->instructions
[q
]);
343 unsigned rmask
= mir_bytemask_of_read_components(bun
->instructions
[j
], bun
->instructions
[j
]->src
[s
]);
344 lcra_add_node_interference(l
, bun
->instructions
[q
]->dest
, mask
, bun
->instructions
[j
]->src
[s
], rmask
);
351 mir_compute_bundle_interference(
352 compiler_context
*ctx
,
353 struct lcra_state
*l
,
356 if (!IS_ALU(bun
->tag
))
359 bool old
= bun
->instructions
[0]->unit
>= UNIT_VADD
;
362 for (unsigned i
= 1; i
< bun
->instruction_count
; ++i
) {
363 bool new = bun
->instructions
[i
]->unit
>= UNIT_VADD
;
366 mir_compute_segment_interference(ctx
, l
, bun
, 0, i
);
372 mir_compute_segment_interference(ctx
, l
, bun
, pivot
, bun
->instruction_count
);
376 mir_compute_interference(
377 compiler_context
*ctx
,
378 struct lcra_state
*l
)
380 /* First, we need liveness information to be computed per block */
381 mir_compute_liveness(ctx
);
383 /* Now that every block has live_in/live_out computed, we can determine
384 * interference by walking each block linearly. Take live_out at the
385 * end of each block and walk the block backwards. */
387 mir_foreach_block(ctx
, blk
) {
388 uint16_t *live
= mem_dup(blk
->live_out
, ctx
->temp_count
* sizeof(uint16_t));
390 mir_foreach_instr_in_block_rev(blk
, ins
) {
391 /* Mark all registers live after the instruction as
392 * interfering with the destination */
394 unsigned dest
= ins
->dest
;
396 if (dest
< ctx
->temp_count
) {
397 for (unsigned i
= 0; i
< ctx
->temp_count
; ++i
)
399 unsigned mask
= mir_bytemask(ins
);
400 lcra_add_node_interference(l
, dest
, mask
, i
, live
[i
]);
405 mir_liveness_ins_update(live
, ins
, ctx
->temp_count
);
408 mir_foreach_bundle_in_block(blk
, bun
)
409 mir_compute_bundle_interference(ctx
, l
, bun
);
415 /* This routine performs the actual register allocation. It should be succeeded
416 * by install_registers */
419 allocate_registers(compiler_context
*ctx
, bool *spilled
)
421 /* The number of vec4 work registers available depends on when the
422 * uniforms start, so compute that first */
423 int work_count
= 16 - MAX2((ctx
->uniform_cutoff
- 8), 0);
425 /* No register allocation to do with no SSA */
427 if (!ctx
->temp_count
)
430 struct lcra_state
*l
= lcra_alloc_equations(ctx
->temp_count
, 1, 8, 16, 5);
432 /* Starts of classes, in bytes */
433 l
->class_start
[REG_CLASS_WORK
] = 16 * 0;
434 l
->class_start
[REG_CLASS_LDST
] = 16 * 26;
435 l
->class_start
[REG_CLASS_TEXR
] = 16 * 28;
436 l
->class_start
[REG_CLASS_TEXW
] = 16 * 28;
438 l
->class_size
[REG_CLASS_WORK
] = 16 * work_count
;
439 l
->class_size
[REG_CLASS_LDST
] = 16 * 2;
440 l
->class_size
[REG_CLASS_TEXR
] = 16 * 2;
441 l
->class_size
[REG_CLASS_TEXW
] = 16 * 2;
443 lcra_set_disjoint_class(l
, REG_CLASS_TEXR
, REG_CLASS_TEXW
);
445 /* To save space on T*20, we don't have real texture registers.
446 * Instead, tex inputs reuse the load/store pipeline registers, and
447 * tex outputs use work r0/r1. Note we still use TEXR/TEXW classes,
448 * noting that this handles interferences and sizes correctly. */
450 if (ctx
->quirks
& MIDGARD_INTERPIPE_REG_ALIASING
) {
451 l
->class_start
[REG_CLASS_TEXR
] = l
->class_start
[REG_CLASS_LDST
];
452 l
->class_start
[REG_CLASS_TEXW
] = l
->class_start
[REG_CLASS_WORK
];
455 unsigned *found_class
= calloc(sizeof(unsigned), ctx
->temp_count
);
456 unsigned *min_alignment
= calloc(sizeof(unsigned), ctx
->temp_count
);
458 mir_foreach_instr_global(ctx
, ins
) {
459 if (ins
->dest
>= SSA_FIXED_MINIMUM
) continue;
461 /* 0 for x, 1 for xy, 2 for xyz, 3 for xyzw */
462 int class = util_logbase2(ins
->mask
);
464 /* Use the largest class if there's ambiguity, this
465 * handles partial writes */
467 int dest
= ins
->dest
;
468 found_class
[dest
] = MAX2(found_class
[dest
], class);
470 /* XXX: Ensure swizzles align the right way with more LCRA constraints? */
471 if (ins
->type
== TAG_ALU_4
&& ins
->alu
.reg_mode
!= midgard_reg_mode_32
)
472 min_alignment
[dest
] = 3; /* (1 << 3) = 8 */
474 if (ins
->type
== TAG_LOAD_STORE_4
&& ins
->load_64
)
475 min_alignment
[dest
] = 3;
478 for (unsigned i
= 0; i
< ctx
->temp_count
; ++i
) {
479 lcra_set_alignment(l
, i
, min_alignment
[i
] ? min_alignment
[i
] : 2);
480 lcra_restrict_range(l
, i
, (found_class
[i
] + 1) * 4);
486 /* Next, we'll determine semantic class. We default to zero (work).
487 * But, if we're used with a special operation, that will force us to a
488 * particular class. Each node must be assigned to exactly one class; a
489 * prepass before RA should have lowered what-would-have-been
490 * multiclass nodes into a series of moves to break it up into multiple
493 mir_foreach_instr_global(ctx
, ins
) {
494 /* Check if this operation imposes any classes */
496 if (ins
->type
== TAG_LOAD_STORE_4
) {
497 set_class(l
->class, ins
->src
[0], REG_CLASS_LDST
);
498 set_class(l
->class, ins
->src
[1], REG_CLASS_LDST
);
499 set_class(l
->class, ins
->src
[2], REG_CLASS_LDST
);
501 if (OP_IS_VEC4_ONLY(ins
->load_store
.op
))
502 lcra_restrict_range(l
, ins
->dest
, 16);
503 } else if (ins
->type
== TAG_TEXTURE_4
) {
504 set_class(l
->class, ins
->dest
, REG_CLASS_TEXW
);
505 set_class(l
->class, ins
->src
[0], REG_CLASS_TEXR
);
506 set_class(l
->class, ins
->src
[1], REG_CLASS_TEXR
);
507 set_class(l
->class, ins
->src
[2], REG_CLASS_TEXR
);
511 /* Check that the semantics of the class are respected */
512 mir_foreach_instr_global(ctx
, ins
) {
513 assert(check_write_class(l
->class, ins
->type
, ins
->dest
));
514 assert(check_read_class(l
->class, ins
->type
, ins
->src
[0]));
515 assert(check_read_class(l
->class, ins
->type
, ins
->src
[1]));
516 assert(check_read_class(l
->class, ins
->type
, ins
->src
[2]));
519 /* Mark writeout to r0 */
520 mir_foreach_instr_global(ctx
, ins
) {
521 if (ins
->compact_branch
&& ins
->writeout
&& ins
->src
[0] < ctx
->temp_count
)
522 l
->solutions
[ins
->src
[0]] = 0;
525 mir_compute_interference(ctx
, l
);
527 *spilled
= !lcra_solve(l
);
531 /* Once registers have been decided via register allocation
532 * (allocate_registers), we need to rewrite the MIR to use registers instead of
536 install_registers_instr(
537 compiler_context
*ctx
,
538 struct lcra_state
*l
,
539 midgard_instruction
*ins
)
546 if (ins
->compact_branch
)
549 struct phys_reg src1
= index_to_reg(ctx
, l
, ins
->src
[0], mir_srcsize(ins
, 0));
550 struct phys_reg src2
= index_to_reg(ctx
, l
, ins
->src
[1], mir_srcsize(ins
, 1));
551 struct phys_reg dest
= index_to_reg(ctx
, l
, ins
->dest
, mir_typesize(ins
));
553 mir_set_bytemask(ins
, mir_bytemask(ins
) << dest
.offset
);
555 unsigned dest_offset
=
556 GET_CHANNEL_COUNT(alu_opcode_props
[ins
->alu
.op
].props
) ? 0 :
559 offset_swizzle(ins
->swizzle
[0], src1
.offset
, src1
.size
, dest_offset
);
561 ins
->registers
.src1_reg
= src1
.reg
;
563 ins
->registers
.src2_imm
= ins
->has_inline_constant
;
565 if (ins
->has_inline_constant
) {
566 /* Encode inline 16-bit constant. See disassembler for
567 * where the algorithm is from */
569 ins
->registers
.src2_reg
= ins
->inline_constant
>> 11;
571 int lower_11
= ins
->inline_constant
& ((1 << 12) - 1);
572 uint16_t imm
= ((lower_11
>> 8) & 0x7) |
573 ((lower_11
& 0xFF) << 3);
575 ins
->alu
.src2
= imm
<< 2;
577 midgard_vector_alu_src mod2
=
578 vector_alu_from_unsigned(ins
->alu
.src2
);
579 offset_swizzle(ins
->swizzle
[1], src2
.offset
, src2
.size
, dest_offset
);
580 ins
->alu
.src2
= vector_alu_srco_unsigned(mod2
);
582 ins
->registers
.src2_reg
= src2
.reg
;
585 ins
->registers
.out_reg
= dest
.reg
;
589 case TAG_LOAD_STORE_4
: {
590 /* Which physical register we read off depends on
591 * whether we are loading or storing -- think about the
592 * logical dataflow */
594 bool encodes_src
= OP_IS_STORE(ins
->load_store
.op
);
597 struct phys_reg src
= index_to_reg(ctx
, l
, ins
->src
[0], mir_srcsize(ins
, 0));
598 assert(src
.reg
== 26 || src
.reg
== 27);
600 ins
->load_store
.reg
= src
.reg
- 26;
601 offset_swizzle(ins
->swizzle
[0], src
.offset
, src
.size
, 0);
603 struct phys_reg dst
= index_to_reg(ctx
, l
, ins
->dest
, mir_typesize(ins
));
605 ins
->load_store
.reg
= dst
.reg
;
606 offset_swizzle(ins
->swizzle
[0], 0, 4, dst
.offset
);
607 mir_set_bytemask(ins
, mir_bytemask(ins
) << dst
.offset
);
610 /* We also follow up by actual arguments */
612 unsigned src2
= ins
->src
[1];
613 unsigned src3
= ins
->src
[2];
616 struct phys_reg src
= index_to_reg(ctx
, l
, src2
, mir_srcsize(ins
, 1));
617 unsigned component
= src
.offset
/ src
.size
;
618 assert(component
* src
.size
== src
.offset
);
619 ins
->load_store
.arg_1
|= midgard_ldst_reg(src
.reg
, component
);
623 struct phys_reg src
= index_to_reg(ctx
, l
, src3
, mir_srcsize(ins
, 2));
624 unsigned component
= src
.offset
/ src
.size
;
625 assert(component
* src
.size
== src
.offset
);
626 ins
->load_store
.arg_2
|= midgard_ldst_reg(src
.reg
, component
);
632 case TAG_TEXTURE_4
: {
633 /* Grab RA results */
634 struct phys_reg dest
= index_to_reg(ctx
, l
, ins
->dest
, mir_typesize(ins
));
635 struct phys_reg coord
= index_to_reg(ctx
, l
, ins
->src
[1], mir_srcsize(ins
, 1));
636 struct phys_reg lod
= index_to_reg(ctx
, l
, ins
->src
[2], mir_srcsize(ins
, 2));
638 /* First, install the texture coordinate */
639 ins
->texture
.in_reg_full
= 1;
640 ins
->texture
.in_reg_upper
= 0;
641 ins
->texture
.in_reg_select
= coord
.reg
& 1;
642 offset_swizzle(ins
->swizzle
[1], coord
.offset
, coord
.size
, 0);
644 /* Next, install the destination */
645 ins
->texture
.out_full
= 1;
646 ins
->texture
.out_upper
= 0;
647 ins
->texture
.out_reg_select
= dest
.reg
& 1;
648 offset_swizzle(ins
->swizzle
[0], 0, 4, dest
.offset
);
649 mir_set_bytemask(ins
, mir_bytemask(ins
) << dest
.offset
);
651 /* If there is a register LOD/bias, use it */
652 if (ins
->src
[2] != ~0) {
653 assert(!(lod
.offset
& 3));
654 midgard_tex_register_select sel
= {
657 .component
= lod
.offset
/ 4
661 memcpy(&packed
, &sel
, sizeof(packed
));
662 ins
->texture
.bias
= packed
;
674 install_registers(compiler_context
*ctx
, struct lcra_state
*l
)
676 mir_foreach_instr_global(ctx
, ins
)
677 install_registers_instr(ctx
, l
, ins
);