2 * Copyright 2010 Christoph Bumiller
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 shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 /* #define NV50PC_DEBUG */
26 #include "nv50_program.h"
30 /* returns TRUE if operands 0 and 1 can be swapped */
32 nv_op_commutative(uint opcode
)
50 /* return operand to which the address register applies */
52 nv50_indirect_opnd(struct nv_instruction
*i
)
68 nv50_nvi_can_use_imm(struct nv_instruction
*nvi
, int s
)
70 if (nvi
->flags_src
|| nvi
->flags_def
)
73 switch (nvi
->opcode
) {
81 return (s
== 1) && (nvi
->src
[0]->value
->reg
.file
== NV_FILE_GPR
) &&
82 (nvi
->def
[0]->reg
.file
== NV_FILE_GPR
);
85 return (nvi
->def
[0]->reg
.file
== NV_FILE_GPR
);
92 nv50_nvi_can_load(struct nv_instruction
*nvi
, int s
, struct nv_value
*value
)
96 for (i
= 0; i
< 3 && nvi
->src
[i
]; ++i
)
97 if (nvi
->src
[i
]->value
->reg
.file
== NV_FILE_IMM
)
100 switch (nvi
->opcode
) {
114 if (s
== 0 && (value
->reg
.file
== NV_FILE_MEM_S
||
115 value
->reg
.file
== NV_FILE_MEM_P
))
117 if (value
->reg
.file
< NV_FILE_MEM_C(0) ||
118 value
->reg
.file
> NV_FILE_MEM_C(15))
121 ((s
== 2) && (nvi
->src
[1]->value
->reg
.file
== NV_FILE_GPR
));
124 return /* TRUE */ FALSE
; /* don't turn MOVs into loads */
130 /* Return whether this instruction can be executed conditionally. */
132 nv50_nvi_can_predicate(struct nv_instruction
*nvi
)
138 for (i
= 0; i
< 4 && nvi
->src
[i
]; ++i
)
139 if (nvi
->src
[i
]->value
->reg
.file
== NV_FILE_IMM
)
145 nv50_supported_src_mods(uint opcode
, int s
)
149 return NV_MOD_NEG
| NV_MOD_ABS
; /* obviously */
168 return NV_MOD_ABS
| NV_MOD_NEG
;
174 /* We may want an opcode table. */
176 nv50_op_can_write_flags(uint opcode
)
178 if (nv_is_vector_op(opcode
))
180 switch (opcode
) { /* obvious ones like KIL, CALL, etc. not included */
190 if (opcode
>= NV_OP_RCP
&& opcode
<= NV_OP_PREEX2
)
196 nv_nvi_refcount(struct nv_instruction
*nvi
)
200 rc
= nvi
->flags_def
? nvi
->flags_def
->refc
: 0;
202 for (i
= 0; i
< 4; ++i
) {
205 rc
+= nvi
->def
[i
]->refc
;
211 nvcg_replace_value(struct nv_pc
*pc
, struct nv_value
*old_val
,
212 struct nv_value
*new_val
)
216 if (old_val
== new_val
)
217 return old_val
->refc
;
219 for (i
= 0, n
= 0; i
< pc
->num_refs
; ++i
) {
220 if (pc
->refs
[i
]->value
== old_val
) {
222 nv_reference(pc
, &pc
->refs
[i
], new_val
);
229 nvcg_find_constant(struct nv_ref
*ref
)
231 struct nv_value
*src
;
237 while (src
->insn
&& src
->insn
->opcode
== NV_OP_MOV
) {
238 assert(!src
->insn
->src
[0]->mod
);
239 src
= src
->insn
->src
[0]->value
;
241 if ((src
->reg
.file
== NV_FILE_IMM
) ||
242 (src
->insn
&& src
->insn
->opcode
== NV_OP_LDA
&&
243 src
->insn
->src
[0]->value
->reg
.file
>= NV_FILE_MEM_C(0) &&
244 src
->insn
->src
[0]->value
->reg
.file
<= NV_FILE_MEM_C(15)))
250 nvcg_find_immediate(struct nv_ref
*ref
)
252 struct nv_value
*src
= nvcg_find_constant(ref
);
254 return (src
&& src
->reg
.file
== NV_FILE_IMM
) ? src
: NULL
;
258 nv_pc_free_refs(struct nv_pc
*pc
)
261 for (i
= 0; i
< pc
->num_refs
; i
+= 64)
267 edge_name(ubyte type
)
270 case CFG_EDGE_FORWARD
: return "forward";
271 case CFG_EDGE_BACK
: return "back";
272 case CFG_EDGE_LOOP_ENTER
: return "loop";
273 case CFG_EDGE_LOOP_LEAVE
: return "break";
274 case CFG_EDGE_FAKE
: return "fake";
281 nv_pc_pass_in_order(struct nv_basic_block
*root
, nv_pc_pass_func f
, void *priv
)
283 struct nv_basic_block
*bb
[64], *bbb
[16], *b
;
294 for (j
= 1; j
>= 0; --j
) {
298 switch (b
->out_kind
[j
]) {
301 case CFG_EDGE_FORWARD
:
303 if (++b
->out
[j
]->priv
== b
->out
[j
]->num_in
)
306 case CFG_EDGE_LOOP_ENTER
:
309 case CFG_EDGE_LOOP_LEAVE
:
310 bbb
[pp
++] = b
->out
[j
];
323 bb
[pp
- 1] = bbb
[pp
- 1];
329 nv_do_print_function(void *priv
, struct nv_basic_block
*b
)
331 struct nv_instruction
*i
;
333 debug_printf("=== BB %i ", b
->id
);
335 debug_printf("[%s -> %i] ", edge_name(b
->out_kind
[0]), b
->out
[0]->id
);
337 debug_printf("[%s -> %i] ", edge_name(b
->out_kind
[1]), b
->out
[1]->id
);
338 debug_printf("===\n");
343 for (; i
; i
= i
->next
)
344 nv_print_instruction(i
);
348 nv_print_function(struct nv_basic_block
*root
)
350 if (root
->subroutine
)
351 debug_printf("SUBROUTINE %i\n", root
->subroutine
);
353 debug_printf("MAIN\n");
355 nv_pc_pass_in_order(root
, nv_do_print_function
, root
);
359 nv_print_program(struct nv_pc
*pc
)
362 for (i
= 0; i
< pc
->num_subroutines
+ 1; ++i
)
364 nv_print_function(pc
->root
[i
]);
369 nv_do_print_cfgraph(struct nv_pc
*pc
, FILE *f
, struct nv_basic_block
*b
)
373 b
->pass_seq
= pc
->pass_seq
;
375 fprintf(f
, "\t%i [shape=box]\n", b
->id
);
377 for (i
= 0; i
< 2; ++i
) {
380 switch (b
->out_kind
[i
]) {
381 case CFG_EDGE_FORWARD
:
382 fprintf(f
, "\t%i -> %i;\n", b
->id
, b
->out
[i
]->id
);
384 case CFG_EDGE_LOOP_ENTER
:
385 fprintf(f
, "\t%i -> %i [color=green];\n", b
->id
, b
->out
[i
]->id
);
387 case CFG_EDGE_LOOP_LEAVE
:
388 fprintf(f
, "\t%i -> %i [color=red];\n", b
->id
, b
->out
[i
]->id
);
391 fprintf(f
, "\t%i -> %i;\n", b
->id
, b
->out
[i
]->id
);
394 fprintf(f
, "\t%i -> %i [style=dotted];\n", b
->id
, b
->out
[i
]->id
);
400 if (b
->out
[i
]->pass_seq
< pc
->pass_seq
)
401 nv_do_print_cfgraph(pc
, f
, b
->out
[i
]);
405 /* Print the control flow graph of subroutine @subr (0 == MAIN) to a file. */
407 nv_print_cfgraph(struct nv_pc
*pc
, const char *filepath
, int subr
)
411 f
= fopen(filepath
, "a");
415 fprintf(f
, "digraph G {\n");
419 nv_do_print_cfgraph(pc
, f
, pc
->root
[subr
]);
428 nvcg_show_bincode(struct nv_pc
*pc
)
432 for (i
= 0; i
< pc
->bin_size
/ 4; ++i
) {
433 debug_printf("0x%08x ", pc
->emit
[i
]);
441 nv50_emit_program(struct nv_pc
*pc
)
443 uint32_t *code
= pc
->emit
;
446 NV50_DBGMSG("emitting program: size = %u\n", pc
->bin_size
);
448 for (n
= 0; n
< pc
->num_blocks
; ++n
) {
449 struct nv_instruction
*i
;
450 struct nv_basic_block
*b
= pc
->bb_list
[n
];
452 for (i
= b
->entry
; i
; i
= i
->next
) {
453 nv50_emit_instruction(pc
, i
);
455 pc
->bin_pos
+= 1 + (pc
->emit
[0] & 1);
456 pc
->emit
+= 1 + (pc
->emit
[0] & 1);
459 assert(pc
->emit
== &code
[pc
->bin_size
/ 4]);
461 /* XXX: we can do better than this ... */
463 !(pc
->emit
[-2] & 1) || (pc
->emit
[-2] & 2) || (pc
->emit
[-1] & 3)) {
464 pc
->emit
[0] = 0xf0000001;
465 pc
->emit
[1] = 0xe0000000;
470 code
[pc
->bin_size
/ 4 - 1] |= 1;
473 nvcg_show_bincode(pc
);
480 nv50_generate_code(struct nv50_translation_info
*ti
)
486 pc
= CALLOC_STRUCT(nv_pc
);
490 pc
->root
= CALLOC(ti
->subr_nr
+ 1, sizeof(pc
->root
[0]));
495 pc
->num_subroutines
= ti
->subr_nr
;
497 ret
= nv50_tgsi_to_nc(pc
, ti
);
501 nv_print_program(pc
);
504 pc
->opt_reload_elim
= ti
->store_to_memory
? FALSE
: TRUE
;
507 ret
= nv_pc_exec_pass0(pc
);
511 nv_print_program(pc
);
514 /* register allocation */
515 ret
= nv_pc_exec_pass1(pc
);
519 nv_print_program(pc
);
520 nv_print_cfgraph(pc
, "nv50_shader_cfgraph.dot", 0);
523 /* prepare for emission */
524 ret
= nv_pc_exec_pass2(pc
);
527 assert(!(pc
->bin_size
% 8));
529 pc
->emit
= CALLOC(pc
->bin_size
/ 4 + 2, 4);
534 ret
= nv50_emit_program(pc
);
538 ti
->p
->code_size
= pc
->bin_size
;
539 ti
->p
->code
= pc
->emit
;
541 ti
->p
->immd_size
= pc
->immd_count
* 4;
542 ti
->p
->immd
= pc
->immd_buf
;
544 /* highest 16 bit reg to num of 32 bit regs, limit to >= 4 */
545 ti
->p
->max_gpr
= MAX2(4, (pc
->max_reg
[NV_FILE_GPR
] >> 1) + 1);
547 ti
->p
->fixups
= pc
->fixups
;
548 ti
->p
->num_fixups
= pc
->num_fixups
;
550 ti
->p
->uses_lmem
= ti
->store_to_memory
;
552 NV50_DBGMSG("SHADER TRANSLATION - %s\n", ret
? "failure" : "success");
557 for (i
= 0; i
< pc
->num_blocks
; ++i
)
558 FREE(pc
->bb_list
[i
]);
561 if (ret
) { /* on success, these will be referenced by nv50_program */
574 nvbb_insert_phi(struct nv_basic_block
*b
, struct nv_instruction
*i
)
581 assert(!b
->entry
->prev
&& b
->exit
);
589 if (b
->entry
->opcode
== NV_OP_PHI
) { /* insert after entry */
590 assert(b
->entry
== b
->exit
);
595 } else { /* insert before entry */
596 assert(b
->entry
->prev
&& b
->exit
);
598 i
->prev
= b
->entry
->prev
;
606 nvbb_insert_tail(struct nv_basic_block
*b
, struct nv_instruction
*i
)
608 if (i
->opcode
== NV_OP_PHI
) {
609 nvbb_insert_phi(b
, i
);
618 if (i
->prev
&& i
->prev
->opcode
== NV_OP_PHI
)
623 b
->num_instructions
++;
627 nvi_insert_after(struct nv_instruction
*at
, struct nv_instruction
*ni
)
630 nvbb_insert_tail(at
->bb
, ni
);
640 nv_nvi_delete(struct nv_instruction
*nvi
)
642 struct nv_basic_block
*b
= nvi
->bb
;
645 /* debug_printf("REM: "); nv_print_instruction(nvi); */
647 for (j
= 0; j
< 5; ++j
)
648 nv_reference(NULL
, &nvi
->src
[j
], NULL
);
649 nv_reference(NULL
, &nvi
->flags_src
, NULL
);
652 nvi
->next
->prev
= nvi
->prev
;
654 assert(nvi
== b
->exit
);
659 nvi
->prev
->next
= nvi
->next
;
661 if (nvi
== b
->entry
) {
662 /* PHIs don't get hooked to b->entry */
663 b
->entry
= nvi
->next
;
664 assert(!nvi
->prev
|| nvi
->prev
->opcode
== NV_OP_PHI
);
668 if (nvi
->opcode
!= NV_OP_PHI
)
669 NV50_DBGMSG("NOTE: b->phi points to non-PHI instruction\n");
672 if (!nvi
->next
|| nvi
->next
->opcode
!= NV_OP_PHI
)
680 nv_nvi_permute(struct nv_instruction
*i1
, struct nv_instruction
*i2
)
682 struct nv_basic_block
*b
= i1
->bb
;
684 assert(i1
->opcode
!= NV_OP_PHI
&&
685 i2
->opcode
!= NV_OP_PHI
);
686 assert(i1
->next
== i2
);
706 nvbb_attach_block(struct nv_basic_block
*parent
,
707 struct nv_basic_block
*b
, ubyte edge_kind
)
709 assert(b
->num_in
< 8);
711 if (parent
->out
[0]) {
712 assert(!parent
->out
[1]);
714 parent
->out_kind
[1] = edge_kind
;
717 parent
->out_kind
[0] = edge_kind
;
720 b
->in
[b
->num_in
] = parent
;
721 b
->in_kind
[b
->num_in
++] = edge_kind
;
724 /* NOTE: all BRKs are treated as conditional, so there are 2 outgoing BBs */
727 nvbb_dominated_by(struct nv_basic_block
*b
, struct nv_basic_block
*d
)
734 for (j
= 0; j
< b
->num_in
; ++j
)
735 if ((b
->in_kind
[j
] != CFG_EDGE_BACK
) && !nvbb_dominated_by(b
->in
[j
], d
))
738 return j
? TRUE
: FALSE
;
741 /* check if @bf (future) can be reached from @bp (past), stop at @bt */
743 nvbb_reachable_by(struct nv_basic_block
*bf
, struct nv_basic_block
*bp
,
744 struct nv_basic_block
*bt
)
746 struct nv_basic_block
*q
[NV_PC_MAX_BASIC_BLOCKS
], *b
;
760 assert(n
<= (1024 - 2));
762 for (i
= 0; i
< 2; ++i
) {
763 if (b
->out
[i
] && !IS_WALL_EDGE(b
->out_kind
[i
]) && !b
->out
[i
]->priv
) {
769 for (--n
; n
>= 0; --n
)
775 static struct nv_basic_block
*
776 nvbb_find_dom_frontier(struct nv_basic_block
*b
, struct nv_basic_block
*df
)
778 struct nv_basic_block
*out
;
781 if (!nvbb_dominated_by(df
, b
)) {
782 for (i
= 0; i
< df
->num_in
; ++i
) {
783 if (df
->in_kind
[i
] == CFG_EDGE_BACK
)
785 if (nvbb_dominated_by(df
->in
[i
], b
))
789 for (i
= 0; i
< 2 && df
->out
[i
]; ++i
) {
790 if (df
->out_kind
[i
] == CFG_EDGE_BACK
)
792 if ((out
= nvbb_find_dom_frontier(b
, df
->out
[i
])))
798 struct nv_basic_block
*
799 nvbb_dom_frontier(struct nv_basic_block
*b
)
801 struct nv_basic_block
*df
;
804 for (i
= 0; i
< 2 && b
->out
[i
]; ++i
)
805 if ((df
= nvbb_find_dom_frontier(b
, b
->out
[i
])))