2 * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
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
25 #include "midgard_ops.h"
26 #include "util/u_memory.h"
27 #include "util/register_allocate.h"
29 /* Scheduling for Midgard is complicated, to say the least. ALU instructions
30 * must be grouped into VLIW bundles according to following model:
33 * [VADD] [SMUL] [VLUT]
35 * A given instruction can execute on some subset of the units (or a few can
36 * execute on all). Instructions can be either vector or scalar; only scalar
37 * instructions can execute on SADD/SMUL units. Units on a given line execute
38 * in parallel. Subsequent lines execute separately and can pass results
39 * directly via pipeline registers r24/r25, bypassing the register file.
41 * A bundle can optionally have 128-bits of embedded constants, shared across
42 * all of the instructions within a bundle.
44 * Instructions consuming conditionals (branches and conditional selects)
45 * require their condition to be written into the conditional register (r31)
46 * within the same bundle they are consumed.
48 * Fragment writeout requires its argument to be written in full within the
49 * same bundle as the branch, with no hanging dependencies.
51 * Load/store instructions are also in bundles of simply two instructions, and
52 * texture instructions have no bundling.
54 * -------------------------------------------------------------------------
58 /* We create the dependency graph with per-component granularity */
60 #define COMPONENT_COUNT 8
63 add_dependency(struct util_dynarray
*table
, unsigned index
, unsigned mask
, midgard_instruction
**instructions
, unsigned child
)
65 for (unsigned i
= 0; i
< COMPONENT_COUNT
; ++i
) {
66 if (!(mask
& (1 << i
)))
69 struct util_dynarray
*parents
= &table
[(COMPONENT_COUNT
* index
) + i
];
71 util_dynarray_foreach(parents
, unsigned, parent
) {
72 BITSET_WORD
*dependents
= instructions
[*parent
]->dependents
;
74 /* Already have the dependency */
75 if (BITSET_TEST(dependents
, child
))
78 BITSET_SET(dependents
, child
);
79 instructions
[child
]->nr_dependencies
++;
85 mark_access(struct util_dynarray
*table
, unsigned index
, unsigned mask
, unsigned parent
)
87 for (unsigned i
= 0; i
< COMPONENT_COUNT
; ++i
) {
88 if (!(mask
& (1 << i
)))
91 util_dynarray_append(&table
[(COMPONENT_COUNT
* index
) + i
], unsigned, parent
);
96 mir_create_dependency_graph(midgard_instruction
**instructions
, unsigned count
, unsigned node_count
)
98 size_t sz
= node_count
* COMPONENT_COUNT
;
100 struct util_dynarray
*last_read
= calloc(sizeof(struct util_dynarray
), sz
);
101 struct util_dynarray
*last_write
= calloc(sizeof(struct util_dynarray
), sz
);
103 for (unsigned i
= 0; i
< sz
; ++i
) {
104 util_dynarray_init(&last_read
[i
], NULL
);
105 util_dynarray_init(&last_write
[i
], NULL
);
108 /* Initialize dependency graph */
109 for (unsigned i
= 0; i
< count
; ++i
) {
110 instructions
[i
]->dependents
=
111 calloc(BITSET_WORDS(count
), sizeof(BITSET_WORD
));
113 instructions
[i
]->nr_dependencies
= 0;
116 /* Populate dependency graph */
117 for (signed i
= count
- 1; i
>= 0; --i
) {
118 if (instructions
[i
]->compact_branch
)
121 unsigned dest
= instructions
[i
]->dest
;
122 unsigned mask
= instructions
[i
]->mask
;
124 mir_foreach_src((*instructions
), s
) {
125 unsigned src
= instructions
[i
]->src
[s
];
127 if (src
< node_count
) {
128 unsigned readmask
= mir_mask_of_read_components(instructions
[i
], src
);
129 add_dependency(last_write
, src
, readmask
, instructions
, i
);
133 if (dest
< node_count
) {
134 add_dependency(last_read
, dest
, mask
, instructions
, i
);
135 add_dependency(last_write
, dest
, mask
, instructions
, i
);
136 mark_access(last_write
, dest
, mask
, i
);
139 mir_foreach_src((*instructions
), s
) {
140 unsigned src
= instructions
[i
]->src
[s
];
142 if (src
< node_count
) {
143 unsigned readmask
= mir_mask_of_read_components(instructions
[i
], src
);
144 mark_access(last_read
, src
, readmask
, i
);
149 /* If there is a branch, all instructions depend on it, as interblock
150 * execution must be purely in-order */
152 if (instructions
[count
- 1]->compact_branch
) {
153 BITSET_WORD
*dependents
= instructions
[count
- 1]->dependents
;
155 for (signed i
= count
- 2; i
>= 0; --i
) {
156 if (BITSET_TEST(dependents
, i
))
159 BITSET_SET(dependents
, i
);
160 instructions
[i
]->nr_dependencies
++;
164 /* Free the intermediate structures */
165 for (unsigned i
= 0; i
< sz
; ++i
) {
166 util_dynarray_fini(&last_read
[i
]);
167 util_dynarray_fini(&last_write
[i
]);
171 /* Does the mask cover more than a scalar? */
174 is_single_component_mask(unsigned mask
)
178 for (int c
= 0; c
< 8; ++c
) {
183 return components
== 1;
186 /* Helpers for scheudling */
189 mir_is_scalar(midgard_instruction
*ains
)
191 /* Do we try to use it as a vector op? */
192 if (!is_single_component_mask(ains
->mask
))
195 /* Otherwise, check mode hazards */
196 bool could_scalar
= true;
198 /* Only 16/32-bit can run on a scalar unit */
199 could_scalar
&= ains
->alu
.reg_mode
!= midgard_reg_mode_8
;
200 could_scalar
&= ains
->alu
.reg_mode
!= midgard_reg_mode_64
;
201 could_scalar
&= ains
->alu
.dest_override
== midgard_dest_override_none
;
203 if (ains
->alu
.reg_mode
== midgard_reg_mode_16
) {
204 /* If we're running in 16-bit mode, we
205 * can't have any 8-bit sources on the
206 * scalar unit (since the scalar unit
207 * doesn't understand 8-bit) */
209 midgard_vector_alu_src s1
=
210 vector_alu_from_unsigned(ains
->alu
.src1
);
212 could_scalar
&= !s1
.half
;
214 midgard_vector_alu_src s2
=
215 vector_alu_from_unsigned(ains
->alu
.src2
);
217 could_scalar
&= !s2
.half
;
223 /* How many bytes does this ALU instruction add to the bundle? */
226 bytes_for_instruction(midgard_instruction
*ains
)
228 if (ains
->unit
& UNITS_ANY_VECTOR
)
229 return sizeof(midgard_reg_info
) + sizeof(midgard_vector_alu
);
230 else if (ains
->unit
== ALU_ENAB_BRANCH
)
231 return sizeof(midgard_branch_extended
);
232 else if (ains
->compact_branch
)
233 return sizeof(ains
->br_compact
);
235 return sizeof(midgard_reg_info
) + sizeof(midgard_scalar_alu
);
238 /* We would like to flatten the linked list of midgard_instructions in a bundle
239 * to an array of pointers on the heap for easy indexing */
241 static midgard_instruction
**
242 flatten_mir(midgard_block
*block
, unsigned *len
)
244 *len
= list_length(&block
->instructions
);
249 midgard_instruction
**instructions
=
250 calloc(sizeof(midgard_instruction
*), *len
);
254 mir_foreach_instr_in_block(block
, ins
)
255 instructions
[i
++] = ins
;
260 /* The worklist is the set of instructions that can be scheduled now; that is,
261 * the set of instructions with no remaining dependencies */
264 mir_initialize_worklist(BITSET_WORD
*worklist
, midgard_instruction
**instructions
, unsigned count
)
266 for (unsigned i
= 0; i
< count
; ++i
) {
267 if (instructions
[i
]->nr_dependencies
== 0)
268 BITSET_SET(worklist
, i
);
272 /* Update the worklist after an instruction terminates. Remove its edges from
273 * the graph and if that causes any node to have no dependencies, add it to the
278 BITSET_WORD
*worklist
, unsigned count
,
279 midgard_instruction
**instructions
, midgard_instruction
*done
)
281 /* Sanity check: if no instruction terminated, there is nothing to do.
282 * If the instruction that terminated had dependencies, that makes no
283 * sense and means we messed up the worklist. Finally, as the purpose
284 * of this routine is to update dependents, we abort early if there are
285 * no dependents defined. */
290 assert(done
->nr_dependencies
== 0);
292 if (!done
->dependents
)
295 /* We have an instruction with dependents. Iterate each dependent to
296 * remove one dependency (`done`), adding dependents to the worklist
301 BITSET_FOREACH_SET(i
, tmp
, done
->dependents
, count
) {
302 assert(instructions
[i
]->nr_dependencies
);
304 if (!(--instructions
[i
]->nr_dependencies
))
305 BITSET_SET(worklist
, i
);
308 free(done
->dependents
);
311 /* While scheduling, we need to choose instructions satisfying certain
312 * criteria. As we schedule backwards, we choose the *last* instruction in the
313 * worklist to simulate in-order scheduling. Chosen instructions must satisfy a
314 * given predicate. */
316 struct midgard_predicate
{
317 /* TAG or ~0 for dont-care */
320 /* True if we want to pop off the chosen instruction */
323 /* For ALU, choose only this unit */
326 /* State for bundle constants. constants is the actual constants
327 * for the bundle. constant_count is the number of bytes (up to
328 * 16) currently in use for constants. When picking in destructive
329 * mode, the constants array will be updated, and the instruction
330 * will be adjusted to index into the constants array */
333 unsigned constant_count
;
336 /* Exclude this destination (if not ~0) */
340 /* For an instruction that can fit, adjust it to fit and update the constants
341 * array, in destructive mode. Returns whether the fitting was successful. */
344 mir_adjust_constants(midgard_instruction
*ins
,
345 struct midgard_predicate
*pred
,
348 /* Blend constants dominate */
349 if (ins
->has_blend_constant
) {
350 if (pred
->constant_count
)
352 else if (destructive
) {
353 pred
->blend_constant
= true;
354 pred
->constant_count
= 16;
359 /* No constant, nothing to adjust */
360 if (!ins
->has_constants
)
363 /* TODO: Deduplicate; permit multiple constants within a bundle */
365 if (destructive
&& !pred
->constant_count
) {
366 if (ins
->alu
.reg_mode
== midgard_reg_mode_16
) {
367 /* TODO: Fix packing XXX */
368 uint16_t *bundles
= (uint16_t *) pred
->constants
;
369 uint32_t *constants
= (uint32_t *) ins
->constants
;
371 /* Copy them wholesale */
372 for (unsigned i
= 0; i
< 4; ++i
)
373 bundles
[i
] = constants
[i
];
375 memcpy(pred
->constants
, ins
->constants
, 16);
378 pred
->constant_count
= 16;
382 return !pred
->constant_count
;
385 static midgard_instruction
*
386 mir_choose_instruction(
387 midgard_instruction
**instructions
,
388 BITSET_WORD
*worklist
, unsigned count
,
389 struct midgard_predicate
*predicate
)
391 /* Parse the predicate */
392 unsigned tag
= predicate
->tag
;
393 bool alu
= tag
== TAG_ALU_4
;
394 unsigned unit
= predicate
->unit
;
395 bool branch
= alu
&& (unit
== ALU_ENAB_BR_COMPACT
);
397 /* Iterate to find the best instruction satisfying the predicate */
401 signed best_index
= -1;
403 /* Enforce a simple metric limiting distance to keep down register
404 * pressure. TOOD: replace with liveness tracking for much better
407 unsigned max_active
= 0;
408 unsigned max_distance
= 6;
410 BITSET_FOREACH_SET(i
, tmp
, worklist
, count
) {
411 max_active
= MAX2(max_active
, i
);
414 BITSET_FOREACH_SET(i
, tmp
, worklist
, count
) {
415 if ((max_active
- i
) >= max_distance
)
418 if (tag
!= ~0 && instructions
[i
]->type
!= tag
)
421 if (predicate
->exclude
!= ~0 && instructions
[i
]->dest
== predicate
->exclude
)
424 if (alu
&& !branch
&& !(alu_opcode_props
[instructions
[i
]->alu
.op
].props
& unit
))
427 if (branch
&& !instructions
[i
]->compact_branch
)
430 if (alu
&& !mir_adjust_constants(instructions
[i
], predicate
, false))
433 /* Simulate in-order scheduling */
434 if ((signed) i
< best_index
)
441 /* Did we find anything? */
446 /* If we found something, remove it from the worklist */
447 assert(best_index
< count
);
449 if (predicate
->destructive
) {
450 BITSET_CLEAR(worklist
, best_index
);
453 mir_adjust_constants(instructions
[best_index
], predicate
, true);
456 return instructions
[best_index
];
459 /* Still, we don't choose instructions in a vacuum. We need a way to choose the
460 * best bundle type (ALU, load/store, texture). Nondestructive. */
464 midgard_instruction
**instructions
,
465 BITSET_WORD
*worklist
, unsigned count
)
467 /* At the moment, our algorithm is very simple - use the bundle of the
468 * best instruction, regardless of what else could be scheduled
469 * alongside it. This is not optimal but it works okay for in-order */
471 struct midgard_predicate predicate
= {
473 .destructive
= false,
477 midgard_instruction
*chosen
= mir_choose_instruction(instructions
, worklist
, count
, &predicate
);
485 /* We want to choose an ALU instruction filling a given unit */
487 mir_choose_alu(midgard_instruction
**slot
,
488 midgard_instruction
**instructions
,
489 BITSET_WORD
*worklist
, unsigned len
,
490 struct midgard_predicate
*predicate
,
493 /* Did we already schedule to this slot? */
497 /* Try to schedule something, if not */
498 predicate
->unit
= unit
;
499 *slot
= mir_choose_instruction(instructions
, worklist
, len
, predicate
);
501 /* Store unit upon scheduling */
502 if (*slot
&& !((*slot
)->compact_branch
))
503 (*slot
)->unit
= unit
;
506 /* When we are scheduling a branch/csel, we need the consumed condition in the
507 * same block as a pipeline register. There are two options to enable this:
509 * - Move the conditional into the bundle. Preferred, but only works if the
510 * conditional is used only once and is from this block.
511 * - Copy the conditional.
513 * We search for the conditional. If it's in this block, single-use, and
514 * without embedded constants, we schedule it immediately. Otherwise, we
515 * schedule a move for it.
517 * mir_comparison_mobile is a helper to find the moveable condition.
521 mir_comparison_mobile(
522 compiler_context
*ctx
,
523 midgard_instruction
**instructions
,
527 if (!mir_single_use(ctx
, cond
))
532 for (unsigned i
= 0; i
< count
; ++i
) {
533 if (instructions
[i
]->dest
!= cond
)
536 /* Must fit in an ALU bundle */
537 if (instructions
[i
]->type
!= TAG_ALU_4
)
540 /* We'll need to rewrite to .w but that doesn't work for vector
541 * ops that don't replicate (ball/bany), so bail there */
543 if (GET_CHANNEL_COUNT(alu_opcode_props
[instructions
[i
]->alu
.op
].props
))
546 /* TODO: moving conditionals with constants */
548 if (instructions
[i
]->has_constants
)
551 /* Ensure it is written only once */
562 /* Using the information about the moveable conditional itself, we either pop
563 * that condition off the worklist for use now, or create a move to
564 * artificially schedule instead as a fallback */
566 static midgard_instruction
*
567 mir_schedule_comparison(
568 compiler_context
*ctx
,
569 midgard_instruction
**instructions
,
570 BITSET_WORD
*worklist
, unsigned count
,
571 unsigned cond
, bool vector
, unsigned swizzle
,
572 midgard_instruction
*user
)
574 /* TODO: swizzle when scheduling */
576 (!vector
&& (swizzle
== 0)) ?
577 mir_comparison_mobile(ctx
, instructions
, count
, cond
) : ~0;
579 /* If we can, schedule the condition immediately */
580 if ((comp_i
!= ~0) && BITSET_TEST(worklist
, comp_i
)) {
581 assert(comp_i
< count
);
582 BITSET_CLEAR(worklist
, comp_i
);
583 return instructions
[comp_i
];
586 /* Otherwise, we insert a move */
587 midgard_vector_alu_src csel
= {
591 midgard_instruction mov
= v_mov(cond
, csel
, cond
);
592 mov
.mask
= vector
? 0xF : 0x1;
594 return mir_insert_instruction_before(ctx
, user
, mov
);
597 /* Most generally, we need instructions writing to r31 in the appropriate
600 static midgard_instruction
*
601 mir_schedule_condition(compiler_context
*ctx
,
602 struct midgard_predicate
*predicate
,
603 BITSET_WORD
*worklist
, unsigned count
,
604 midgard_instruction
**instructions
,
605 midgard_instruction
*last
)
607 /* For a branch, the condition is the only argument; for csel, third */
608 bool branch
= last
->compact_branch
;
609 unsigned condition_index
= branch
? 0 : 2;
611 /* csel_v is vector; otherwise, conditions are scalar */
612 bool vector
= !branch
&& OP_IS_CSEL_V(last
->alu
.op
);
614 /* Grab the conditional instruction */
616 midgard_instruction
*cond
= mir_schedule_comparison(
617 ctx
, instructions
, worklist
, count
, last
->src
[condition_index
],
618 vector
, last
->cond_swizzle
, last
);
620 /* We have exclusive reign over this (possibly move) conditional
621 * instruction. We can rewrite into a pipeline conditional register */
623 predicate
->exclude
= cond
->dest
;
624 cond
->dest
= SSA_FIXED_REGISTER(31);
627 cond
->mask
= (1 << COMPONENT_W
);
629 mir_foreach_src(cond
, s
) {
630 if (cond
->src
[s
] == ~0)
633 mir_set_swizzle(cond
, s
, (mir_get_swizzle(cond
, s
) << (2*3)) & 0xFF);
637 /* Schedule the unit: csel is always in the latter pipeline, so a csel
638 * condition must be in the former pipeline stage (vmul/sadd),
639 * depending on scalar/vector of the instruction itself. A branch must
640 * be written from the latter pipeline stage and a branch condition is
641 * always scalar, so it is always in smul (exception: ball/bany, which
645 cond
->unit
= UNIT_SMUL
;
647 cond
->unit
= vector
? UNIT_VMUL
: UNIT_SADD
;
652 /* Schedules a single bundle of the given type */
654 static midgard_bundle
655 mir_schedule_texture(
656 midgard_instruction
**instructions
,
657 BITSET_WORD
*worklist
, unsigned len
)
659 struct midgard_predicate predicate
= {
660 .tag
= TAG_TEXTURE_4
,
665 midgard_instruction
*ins
=
666 mir_choose_instruction(instructions
, worklist
, len
, &predicate
);
668 mir_update_worklist(worklist
, len
, instructions
, ins
);
670 struct midgard_bundle out
= {
671 .tag
= TAG_TEXTURE_4
,
672 .instruction_count
= 1,
673 .instructions
= { ins
}
679 static midgard_bundle
681 midgard_instruction
**instructions
,
682 BITSET_WORD
*worklist
, unsigned len
)
684 struct midgard_predicate predicate
= {
685 .tag
= TAG_LOAD_STORE_4
,
690 /* Try to pick two load/store ops. Second not gauranteed to exist */
692 midgard_instruction
*ins
=
693 mir_choose_instruction(instructions
, worklist
, len
, &predicate
);
695 midgard_instruction
*pair
=
696 mir_choose_instruction(instructions
, worklist
, len
, &predicate
);
698 struct midgard_bundle out
= {
699 .tag
= TAG_LOAD_STORE_4
,
700 .instruction_count
= pair
? 2 : 1,
701 .instructions
= { ins
, pair
}
704 /* We have to update the worklist atomically, since the two
705 * instructions run concurrently (TODO: verify it's not pipelined) */
707 mir_update_worklist(worklist
, len
, instructions
, ins
);
708 mir_update_worklist(worklist
, len
, instructions
, pair
);
713 static midgard_bundle
715 compiler_context
*ctx
,
716 midgard_instruction
**instructions
,
717 BITSET_WORD
*worklist
, unsigned len
)
719 struct midgard_bundle bundle
= {};
721 unsigned bytes_emitted
= sizeof(bundle
.control
);
723 struct midgard_predicate predicate
= {
727 .constants
= (uint8_t *) bundle
.constants
730 midgard_instruction
*vmul
= NULL
;
731 midgard_instruction
*vadd
= NULL
;
732 midgard_instruction
*vlut
= NULL
;
733 midgard_instruction
*smul
= NULL
;
734 midgard_instruction
*sadd
= NULL
;
735 midgard_instruction
*branch
= NULL
;
737 mir_choose_alu(&branch
, instructions
, worklist
, len
, &predicate
, ALU_ENAB_BR_COMPACT
);
738 mir_update_worklist(worklist
, len
, instructions
, branch
);
739 bool writeout
= branch
&& branch
->writeout
;
741 if (branch
&& !branch
->prepacked_branch
&& branch
->branch
.conditional
) {
742 midgard_instruction
*cond
= mir_schedule_condition(ctx
, &predicate
, worklist
, len
, instructions
, branch
);
744 if (cond
->unit
== UNIT_VADD
)
746 else if (cond
->unit
== UNIT_SMUL
)
749 unreachable("Bad condition");
753 mir_choose_alu(&vlut
, instructions
, worklist
, len
, &predicate
, UNIT_VLUT
);
755 mir_choose_alu(&vadd
, instructions
, worklist
, len
, &predicate
, UNIT_VADD
);
757 mir_update_worklist(worklist
, len
, instructions
, vlut
);
758 mir_update_worklist(worklist
, len
, instructions
, vadd
);
759 mir_update_worklist(worklist
, len
, instructions
, smul
);
761 bool vadd_csel
= vadd
&& OP_IS_CSEL(vadd
->alu
.op
);
762 bool smul_csel
= smul
&& OP_IS_CSEL(smul
->alu
.op
);
764 if (vadd_csel
|| smul_csel
) {
765 midgard_instruction
*ins
= vadd_csel
? vadd
: smul
;
766 midgard_instruction
*cond
= mir_schedule_condition(ctx
, &predicate
, worklist
, len
, instructions
, ins
);
768 if (cond
->unit
== UNIT_VMUL
)
770 else if (cond
->unit
== UNIT_SADD
)
773 unreachable("Bad condition");
776 /* Check if writeout reads its own register */
777 bool bad_writeout
= false;
779 if (branch
&& branch
->writeout
) {
780 midgard_instruction
*stages
[] = { sadd
, vadd
, smul
};
781 unsigned src
= (branch
->src
[0] == ~0) ? SSA_FIXED_REGISTER(0) : branch
->src
[0];
782 unsigned writeout_mask
= 0x0;
784 for (unsigned i
= 0; i
< ARRAY_SIZE(stages
); ++i
) {
788 if (stages
[i
]->dest
!= src
)
791 writeout_mask
|= stages
[i
]->mask
;
792 bad_writeout
|= mir_has_arg(stages
[i
], branch
->src
[0]);
795 /* Add a move if necessary */
796 if (bad_writeout
|| writeout_mask
!= 0xF) {
797 unsigned temp
= (branch
->src
[0] == ~0) ? SSA_FIXED_REGISTER(0) : make_compiler_temp(ctx
);
798 midgard_instruction mov
= v_mov(src
, blank_alu_src
, temp
);
799 vmul
= mem_dup(&mov
, sizeof(midgard_instruction
));
800 vmul
->unit
= UNIT_VMUL
;
801 vmul
->mask
= 0xF ^ writeout_mask
;
802 /* TODO: Don't leak */
804 /* Rewrite to use our temp */
806 for (unsigned i
= 0; i
< ARRAY_SIZE(stages
); ++i
) {
808 mir_rewrite_index_dst_single(stages
[i
], src
, temp
);
811 mir_rewrite_index_src_single(branch
, src
, temp
);
815 mir_choose_alu(&vmul
, instructions
, worklist
, len
, &predicate
, UNIT_VMUL
);
817 mir_update_worklist(worklist
, len
, instructions
, vmul
);
818 mir_update_worklist(worklist
, len
, instructions
, sadd
);
820 bundle
.has_blend_constant
= predicate
.blend_constant
;
821 bundle
.has_embedded_constants
= predicate
.constant_count
> 0;
823 unsigned padding
= 0;
825 /* Now that we have finished scheduling, build up the bundle */
826 midgard_instruction
*stages
[] = { vmul
, sadd
, vadd
, smul
, vlut
, branch
};
828 for (unsigned i
= 0; i
< ARRAY_SIZE(stages
); ++i
) {
830 bundle
.control
|= stages
[i
]->unit
;
831 bytes_emitted
+= bytes_for_instruction(stages
[i
]);
832 bundle
.instructions
[bundle
.instruction_count
++] = stages
[i
];
836 /* Pad ALU op to nearest word */
838 if (bytes_emitted
& 15) {
839 padding
= 16 - (bytes_emitted
& 15);
840 bytes_emitted
+= padding
;
843 /* Constants must always be quadwords */
844 if (bundle
.has_embedded_constants
)
847 /* Size ALU instruction for tag */
848 bundle
.tag
= (TAG_ALU_4
) + (bytes_emitted
/ 16) - 1;
849 bundle
.padding
= padding
;
850 bundle
.control
|= bundle
.tag
;
855 /* Schedule a single block by iterating its instruction to create bundles.
856 * While we go, tally about the bundle sizes to compute the block size. */
860 schedule_block(compiler_context
*ctx
, midgard_block
*block
)
862 /* Copy list to dynamic array */
864 midgard_instruction
**instructions
= flatten_mir(block
, &len
);
869 /* Calculate dependencies and initial worklist */
870 unsigned node_count
= ctx
->temp_count
+ 1;
871 mir_create_dependency_graph(instructions
, len
, node_count
);
873 /* Allocate the worklist */
874 size_t sz
= BITSET_WORDS(len
) * sizeof(BITSET_WORD
);
875 BITSET_WORD
*worklist
= calloc(sz
, 1);
876 mir_initialize_worklist(worklist
, instructions
, len
);
878 struct util_dynarray bundles
;
879 util_dynarray_init(&bundles
, NULL
);
881 block
->quadword_count
= 0;
882 unsigned blend_offset
= 0;
885 unsigned tag
= mir_choose_bundle(instructions
, worklist
, len
);
886 midgard_bundle bundle
;
888 if (tag
== TAG_TEXTURE_4
)
889 bundle
= mir_schedule_texture(instructions
, worklist
, len
);
890 else if (tag
== TAG_LOAD_STORE_4
)
891 bundle
= mir_schedule_ldst(instructions
, worklist
, len
);
892 else if (tag
== TAG_ALU_4
)
893 bundle
= mir_schedule_alu(ctx
, instructions
, worklist
, len
);
897 util_dynarray_append(&bundles
, midgard_bundle
, bundle
);
899 if (bundle
.has_blend_constant
)
900 blend_offset
= block
->quadword_count
;
902 block
->quadword_count
+= quadword_size(bundle
.tag
);
905 /* We emitted bundles backwards; copy into the block in reverse-order */
907 util_dynarray_init(&block
->bundles
, NULL
);
908 util_dynarray_foreach_reverse(&bundles
, midgard_bundle
, bundle
) {
909 util_dynarray_append(&block
->bundles
, midgard_bundle
, *bundle
);
912 /* Blend constant was backwards as well. blend_offset if set is
913 * strictly positive, as an offset of zero would imply constants before
914 * any instructions which is invalid in Midgard */
917 ctx
->blend_constant_offset
= ((ctx
->quadword_count
+ block
->quadword_count
) - blend_offset
- 1) * 0x10;
919 block
->is_scheduled
= true;
920 ctx
->quadword_count
+= block
->quadword_count
;
922 /* Reorder instructions to match bundled. First remove existing
923 * instructions and then recreate the list */
925 mir_foreach_instr_in_block_safe(block
, ins
) {
926 list_del(&ins
->link
);
929 mir_foreach_instr_in_block_scheduled_rev(block
, ins
) {
930 list_add(&ins
->link
, &block
->instructions
);
934 /* When we're 'squeezing down' the values in the IR, we maintain a hash
938 find_or_allocate_temp(compiler_context
*ctx
, unsigned hash
)
940 if (hash
>= SSA_FIXED_MINIMUM
)
943 unsigned temp
= (uintptr_t) _mesa_hash_table_u64_search(
944 ctx
->hash_to_temp
, hash
+ 1);
949 /* If no temp is find, allocate one */
950 temp
= ctx
->temp_count
++;
951 ctx
->max_hash
= MAX2(ctx
->max_hash
, hash
);
953 _mesa_hash_table_u64_insert(ctx
->hash_to_temp
,
954 hash
+ 1, (void *) ((uintptr_t) temp
+ 1));
959 /* Reassigns numbering to get rid of gaps in the indices */
962 mir_squeeze_index(compiler_context
*ctx
)
966 /* TODO don't leak old hash_to_temp */
967 ctx
->hash_to_temp
= _mesa_hash_table_u64_create(NULL
);
969 mir_foreach_instr_global(ctx
, ins
) {
970 ins
->dest
= find_or_allocate_temp(ctx
, ins
->dest
);
972 for (unsigned i
= 0; i
< ARRAY_SIZE(ins
->src
); ++i
)
973 ins
->src
[i
] = find_or_allocate_temp(ctx
, ins
->src
[i
]);
977 static midgard_instruction
978 v_load_store_scratch(
984 /* We index by 32-bit vec4s */
985 unsigned byte
= (index
* 4 * 4);
987 midgard_instruction ins
= {
988 .type
= TAG_LOAD_STORE_4
,
991 .src
= { ~0, ~0, ~0 },
993 .op
= is_store
? midgard_op_st_int4
: midgard_op_ld_int4
,
994 .swizzle
= SWIZZLE_XYZW
,
996 /* For register spilling - to thread local storage */
1000 /* Splattered across, TODO combine logically */
1001 .varying_parameters
= (byte
& 0x1FF) << 1,
1002 .address
= (byte
>> 9)
1005 /* If we spill an unspill, RA goes into an infinite loop */
1010 /* r0 = r26, r1 = r27 */
1011 assert(srcdest
== SSA_FIXED_REGISTER(26) || srcdest
== SSA_FIXED_REGISTER(27));
1012 ins
.src
[0] = srcdest
;
1020 /* If register allocation fails, find the best spill node and spill it to fix
1021 * whatever the issue was. This spill node could be a work register (spilling
1022 * to thread local storage), but it could also simply be a special register
1023 * that needs to spill to become a work register. */
1025 static void mir_spill_register(
1026 compiler_context
*ctx
,
1028 unsigned *spill_count
)
1030 unsigned spill_index
= ctx
->temp_count
;
1032 /* Our first step is to calculate spill cost to figure out the best
1033 * spill node. All nodes are equal in spill cost, but we can't spill
1034 * nodes written to from an unspill */
1036 for (unsigned i
= 0; i
< ctx
->temp_count
; ++i
) {
1037 ra_set_node_spill_cost(g
, i
, 1.0);
1040 /* We can't spill any bundles that contain unspills. This could be
1041 * optimized to allow use of r27 to spill twice per bundle, but if
1042 * you're at the point of optimizing spilling, it's too late. */
1044 mir_foreach_block(ctx
, block
) {
1045 mir_foreach_bundle_in_block(block
, bun
) {
1046 bool no_spill
= false;
1048 for (unsigned i
= 0; i
< bun
->instruction_count
; ++i
)
1049 no_spill
|= bun
->instructions
[i
]->no_spill
;
1054 for (unsigned i
= 0; i
< bun
->instruction_count
; ++i
) {
1055 unsigned dest
= bun
->instructions
[i
]->dest
;
1056 if (dest
< ctx
->temp_count
)
1057 ra_set_node_spill_cost(g
, dest
, -1.0);
1062 int spill_node
= ra_get_best_spill_node(g
);
1064 if (spill_node
< 0) {
1065 mir_print_shader(ctx
);
1069 /* We have a spill node, so check the class. Work registers
1070 * legitimately spill to TLS, but special registers just spill to work
1073 unsigned class = ra_get_node_class(g
, spill_node
);
1074 bool is_special
= (class >> 2) != REG_CLASS_WORK
;
1075 bool is_special_w
= (class >> 2) == REG_CLASS_TEXW
;
1077 /* Allocate TLS slot (maybe) */
1078 unsigned spill_slot
= !is_special
? (*spill_count
)++ : 0;
1080 /* For TLS, replace all stores to the spilled node. For
1081 * special reads, just keep as-is; the class will be demoted
1082 * implicitly. For special writes, spill to a work register */
1084 if (!is_special
|| is_special_w
) {
1086 spill_slot
= spill_index
++;
1088 mir_foreach_block(ctx
, block
) {
1089 mir_foreach_instr_in_block_safe(block
, ins
) {
1090 if (ins
->dest
!= spill_node
) continue;
1092 midgard_instruction st
;
1095 st
= v_mov(spill_node
, blank_alu_src
, spill_slot
);
1098 ins
->dest
= SSA_FIXED_REGISTER(26);
1099 ins
->no_spill
= true;
1100 st
= v_load_store_scratch(ins
->dest
, spill_slot
, true, ins
->mask
);
1103 /* Hint: don't rewrite this node */
1106 mir_insert_instruction_after_scheduled(ctx
, block
, ins
, st
);
1114 /* For special reads, figure out how many components we need */
1115 unsigned read_mask
= 0;
1117 mir_foreach_instr_global_safe(ctx
, ins
) {
1118 read_mask
|= mir_mask_of_read_components(ins
, spill_node
);
1121 /* Insert a load from TLS before the first consecutive
1122 * use of the node, rewriting to use spilled indices to
1123 * break up the live range. Or, for special, insert a
1124 * move. Ironically the latter *increases* register
1125 * pressure, but the two uses of the spilling mechanism
1126 * are somewhat orthogonal. (special spilling is to use
1127 * work registers to back special registers; TLS
1128 * spilling is to use memory to back work registers) */
1130 mir_foreach_block(ctx
, block
) {
1131 bool consecutive_skip
= false;
1132 unsigned consecutive_index
= 0;
1134 mir_foreach_instr_in_block(block
, ins
) {
1135 /* We can't rewrite the moves used to spill in the
1136 * first place. These moves are hinted. */
1137 if (ins
->hint
) continue;
1139 if (!mir_has_arg(ins
, spill_node
)) {
1140 consecutive_skip
= false;
1144 if (consecutive_skip
) {
1146 mir_rewrite_index_src_single(ins
, spill_node
, consecutive_index
);
1150 if (!is_special_w
) {
1151 consecutive_index
= ++spill_index
;
1153 midgard_instruction
*before
= ins
;
1155 /* For a csel, go back one more not to break up the bundle */
1156 if (ins
->type
== TAG_ALU_4
&& OP_IS_CSEL(ins
->alu
.op
))
1157 before
= mir_prev_op(before
);
1159 midgard_instruction st
;
1163 st
= v_mov(spill_node
, blank_alu_src
, consecutive_index
);
1167 st
= v_load_store_scratch(consecutive_index
, spill_slot
, false, 0xF);
1170 /* Mask the load based on the component count
1171 * actually needed to prvent RA loops */
1173 st
.mask
= read_mask
;
1175 mir_insert_instruction_before_scheduled(ctx
, block
, before
, st
);
1176 // consecutive_skip = true;
1178 /* Special writes already have their move spilled in */
1179 consecutive_index
= spill_slot
;
1183 /* Rewrite to use */
1184 mir_rewrite_index_src_single(ins
, spill_node
, consecutive_index
);
1193 mir_foreach_instr_global(ctx
, ins
) {
1199 schedule_program(compiler_context
*ctx
)
1201 struct ra_graph
*g
= NULL
;
1202 bool spilled
= false;
1203 int iter_count
= 1000; /* max iterations */
1205 /* Number of 128-bit slots in memory we've spilled into */
1206 unsigned spill_count
= 0;
1208 midgard_promote_uniforms(ctx
, 16);
1210 /* Must be lowered right before RA */
1211 mir_squeeze_index(ctx
);
1212 mir_lower_special_reads(ctx
);
1213 mir_squeeze_index(ctx
);
1215 /* Lowering can introduce some dead moves */
1217 mir_foreach_block(ctx
, block
) {
1218 midgard_opt_dead_move_eliminate(ctx
, block
);
1219 schedule_block(ctx
, block
);
1222 mir_create_pipeline_registers(ctx
);
1226 mir_spill_register(ctx
, g
, &spill_count
);
1228 mir_squeeze_index(ctx
);
1231 g
= allocate_registers(ctx
, &spilled
);
1232 } while(spilled
&& ((iter_count
--) > 0));
1234 if (iter_count
<= 0) {
1235 fprintf(stderr
, "panfrost: Gave up allocating registers, rendering will be incomplete\n");
1239 /* Report spilling information. spill_count is in 128-bit slots (vec4 x
1240 * fp32), but tls_size is in bytes, so multiply by 16 */
1242 ctx
->tls_size
= spill_count
* 16;
1244 install_registers(ctx
, g
);