1 // SPDX-License-Identifier: LGPL-2.1-or-later
3 * Copyright (C) 2014-2021 Paul Cercueil <paul@crapouillou.net>
6 #include "lightrec-config.h"
7 #include "disassembler.h"
9 #include "memmanager.h"
10 #include "optimizer.h"
18 #define IF_OPT(opt, ptr) ((opt) ? (ptr) : NULL)
20 struct optimizer_list {
21 void (**optimizers)(struct opcode *);
22 unsigned int nb_optimizers;
25 static bool is_nop(union code op);
27 bool is_unconditional_jump(union code c)
31 return c.r.op == OP_SPECIAL_JR || c.r.op == OP_SPECIAL_JALR;
37 return c.i.rs == c.i.rt;
39 return (c.r.rt == OP_REGIMM_BGEZ ||
40 c.r.rt == OP_REGIMM_BGEZAL) && c.i.rs == 0;
46 bool is_syscall(union code c)
48 return (c.i.op == OP_SPECIAL && c.r.op == OP_SPECIAL_SYSCALL) ||
49 (c.i.op == OP_CP0 && (c.r.rs == OP_CP0_MTC0 ||
50 c.r.rs == OP_CP0_CTC0) &&
51 (c.r.rd == 12 || c.r.rd == 13));
54 static u64 opcode_read_mask(union code op)
59 case OP_SPECIAL_SYSCALL:
60 case OP_SPECIAL_BREAK:
79 return BIT(op.r.rs) | BIT(op.r.rt);
90 if (op.r.op == OP_CP2_BASIC) {
92 case OP_CP2_BASIC_MTC2:
93 case OP_CP2_BASIC_CTC2:
105 if (op.i.rs == op.i.rt)
116 return BIT(op.i.rs) | BIT(op.i.rt);
122 static u64 mult_div_write_mask(union code op)
126 if (!OPT_FLAG_MULT_DIV)
127 return BIT(REG_LO) | BIT(REG_HI);
130 flags = BIT(op.r.rd);
134 flags |= BIT(op.r.imm);
136 flags |= BIT(REG_HI);
141 static u64 opcode_write_mask(union code op)
146 return mult_div_write_mask(op);
150 case OP_SPECIAL_SYSCALL:
151 case OP_SPECIAL_BREAK:
153 case OP_SPECIAL_MULT:
154 case OP_SPECIAL_MULTU:
156 case OP_SPECIAL_DIVU:
157 return mult_div_write_mask(op);
158 case OP_SPECIAL_MTHI:
160 case OP_SPECIAL_MTLO:
198 if (op.r.op == OP_CP2_BASIC) {
200 case OP_CP2_BASIC_MFC2:
201 case OP_CP2_BASIC_CFC2:
210 case OP_REGIMM_BLTZAL:
211 case OP_REGIMM_BGEZAL:
223 bool opcode_reads_register(union code op, u8 reg)
225 return opcode_read_mask(op) & BIT(reg);
228 bool opcode_writes_register(union code op, u8 reg)
230 return opcode_write_mask(op) & BIT(reg);
233 static int find_prev_writer(const struct opcode *list, unsigned int offset, u8 reg)
238 if (op_flag_sync(list[offset].flags))
241 for (i = offset; i > 0; i--) {
244 if (opcode_writes_register(c, reg)) {
245 if (i > 1 && has_delay_slot(list[i - 2].c))
251 if (op_flag_sync(list[i - 1].flags) ||
253 opcode_reads_register(c, reg))
260 static int find_next_reader(const struct opcode *list, unsigned int offset, u8 reg)
265 if (op_flag_sync(list[offset].flags))
268 for (i = offset; ; i++) {
271 if (opcode_reads_register(c, reg)) {
272 if (i > 0 && has_delay_slot(list[i - 1].c))
278 if (op_flag_sync(list[i].flags) ||
279 has_delay_slot(c) || opcode_writes_register(c, reg))
286 static bool reg_is_dead(const struct opcode *list, unsigned int offset, u8 reg)
290 if (op_flag_sync(list[offset].flags))
293 for (i = offset + 1; ; i++) {
294 if (opcode_reads_register(list[i].c, reg))
297 if (opcode_writes_register(list[i].c, reg))
300 if (has_delay_slot(list[i].c)) {
301 if (op_flag_no_ds(list[i].flags) ||
302 opcode_reads_register(list[i + 1].c, reg))
305 return opcode_writes_register(list[i + 1].c, reg);
310 static bool reg_is_read(const struct opcode *list,
311 unsigned int a, unsigned int b, u8 reg)
313 /* Return true if reg is read in one of the opcodes of the interval
316 if (!is_nop(list[a].c) && opcode_reads_register(list[a].c, reg))
323 static bool reg_is_written(const struct opcode *list,
324 unsigned int a, unsigned int b, u8 reg)
326 /* Return true if reg is written in one of the opcodes of the interval
330 if (!is_nop(list[a].c) && opcode_writes_register(list[a].c, reg))
337 static bool reg_is_read_or_written(const struct opcode *list,
338 unsigned int a, unsigned int b, u8 reg)
340 return reg_is_read(list, a, b, reg) || reg_is_written(list, a, b, reg);
343 static bool opcode_is_load(union code op)
360 static bool opcode_is_store(union code op)
375 static u8 opcode_get_io_size(union code op)
391 bool opcode_is_io(union code op)
393 return opcode_is_load(op) || opcode_is_store(op);
397 static bool is_nop(union code op)
399 if (opcode_writes_register(op, 0)) {
402 return op.r.rs != OP_CP0_MFC0;
420 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
422 case OP_SPECIAL_ADDU:
423 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
424 (op.r.rd == op.r.rs && op.r.rt == 0);
426 case OP_SPECIAL_SUBU:
427 return op.r.rd == op.r.rs && op.r.rt == 0;
429 if (op.r.rd == op.r.rt)
430 return op.r.rd == op.r.rs || op.r.rs == 0;
432 return (op.r.rd == op.r.rs) && op.r.rt == 0;
436 return op.r.rd == op.r.rt && op.r.imm == 0;
437 case OP_SPECIAL_MFHI:
438 case OP_SPECIAL_MFLO:
446 return op.i.rt == op.i.rs && op.i.imm == 0;
448 return (op.i.rs == 0 || op.i.imm == 1);
450 return (op.i.op == OP_REGIMM_BLTZ ||
451 op.i.op == OP_REGIMM_BLTZAL) &&
452 (op.i.rs == 0 || op.i.imm == 1);
454 return (op.i.rs == op.i.rt || op.i.imm == 1);
460 bool load_in_delay_slot(union code op)
474 if (op.r.op == OP_CP2_BASIC) {
476 case OP_CP2_BASIC_MFC2:
477 case OP_CP2_BASIC_CFC2:
500 static u32 lightrec_propagate_consts(const struct opcode *op,
501 const struct opcode *prev,
504 union code c = prev->c;
506 /* Register $zero is always, well, zero */
510 if (op_flag_sync(op->flags))
517 if (known & BIT(c.r.rt)) {
518 known |= BIT(c.r.rd);
519 v[c.r.rd] = v[c.r.rt] << c.r.imm;
521 known &= ~BIT(c.r.rd);
525 if (known & BIT(c.r.rt)) {
526 known |= BIT(c.r.rd);
527 v[c.r.rd] = v[c.r.rt] >> c.r.imm;
529 known &= ~BIT(c.r.rd);
533 if (known & BIT(c.r.rt)) {
534 known |= BIT(c.r.rd);
535 v[c.r.rd] = (s32)v[c.r.rt] >> c.r.imm;
537 known &= ~BIT(c.r.rd);
540 case OP_SPECIAL_SLLV:
541 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
542 known |= BIT(c.r.rd);
543 v[c.r.rd] = v[c.r.rt] << (v[c.r.rs] & 0x1f);
545 known &= ~BIT(c.r.rd);
548 case OP_SPECIAL_SRLV:
549 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
550 known |= BIT(c.r.rd);
551 v[c.r.rd] = v[c.r.rt] >> (v[c.r.rs] & 0x1f);
553 known &= ~BIT(c.r.rd);
556 case OP_SPECIAL_SRAV:
557 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
558 known |= BIT(c.r.rd);
559 v[c.r.rd] = (s32)v[c.r.rt]
560 >> (v[c.r.rs] & 0x1f);
562 known &= ~BIT(c.r.rd);
566 case OP_SPECIAL_ADDU:
567 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
568 known |= BIT(c.r.rd);
569 v[c.r.rd] = (s32)v[c.r.rt] + (s32)v[c.r.rs];
571 known &= ~BIT(c.r.rd);
575 case OP_SPECIAL_SUBU:
576 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
577 known |= BIT(c.r.rd);
578 v[c.r.rd] = v[c.r.rt] - v[c.r.rs];
580 known &= ~BIT(c.r.rd);
584 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
585 known |= BIT(c.r.rd);
586 v[c.r.rd] = v[c.r.rt] & v[c.r.rs];
588 known &= ~BIT(c.r.rd);
592 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
593 known |= BIT(c.r.rd);
594 v[c.r.rd] = v[c.r.rt] | v[c.r.rs];
596 known &= ~BIT(c.r.rd);
600 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
601 known |= BIT(c.r.rd);
602 v[c.r.rd] = v[c.r.rt] ^ v[c.r.rs];
604 known &= ~BIT(c.r.rd);
608 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
609 known |= BIT(c.r.rd);
610 v[c.r.rd] = ~(v[c.r.rt] | v[c.r.rs]);
612 known &= ~BIT(c.r.rd);
616 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
617 known |= BIT(c.r.rd);
618 v[c.r.rd] = (s32)v[c.r.rs] < (s32)v[c.r.rt];
620 known &= ~BIT(c.r.rd);
623 case OP_SPECIAL_SLTU:
624 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
625 known |= BIT(c.r.rd);
626 v[c.r.rd] = v[c.r.rs] < v[c.r.rt];
628 known &= ~BIT(c.r.rd);
631 case OP_SPECIAL_MULT:
632 case OP_SPECIAL_MULTU:
634 case OP_SPECIAL_DIVU:
635 if (OPT_FLAG_MULT_DIV && c.r.rd)
636 known &= ~BIT(c.r.rd);
637 if (OPT_FLAG_MULT_DIV && c.r.imm)
638 known &= ~BIT(c.r.imm);
640 case OP_SPECIAL_MFLO:
641 case OP_SPECIAL_MFHI:
642 known &= ~BIT(c.r.rd);
650 if (OPT_FLAG_MULT_DIV && (known & BIT(c.r.rs))) {
652 known |= BIT(c.r.rd);
655 v[c.r.rd] = v[c.r.rs] << c.r.op;
661 known |= BIT(c.r.imm);
664 v[c.r.imm] = v[c.r.rs] << (c.r.op - 32);
665 else if (c.i.op == OP_META_MULT2)
666 v[c.r.imm] = (s32) v[c.r.rs] >> (32 - c.r.op);
668 v[c.r.imm] = v[c.r.rs] >> (32 - c.r.op);
671 if (OPT_FLAG_MULT_DIV && c.r.rd)
672 known &= ~BIT(c.r.rd);
673 if (OPT_FLAG_MULT_DIV && c.r.imm)
674 known &= ~BIT(c.r.imm);
681 if (known & BIT(c.i.rs)) {
682 known |= BIT(c.i.rt);
683 v[c.i.rt] = v[c.i.rs] + (s32)(s16)c.i.imm;
685 known &= ~BIT(c.i.rt);
689 if (known & BIT(c.i.rs)) {
690 known |= BIT(c.i.rt);
691 v[c.i.rt] = (s32)v[c.i.rs] < (s32)(s16)c.i.imm;
693 known &= ~BIT(c.i.rt);
697 if (known & BIT(c.i.rs)) {
698 known |= BIT(c.i.rt);
699 v[c.i.rt] = v[c.i.rs] < (u32)(s32)(s16)c.i.imm;
701 known &= ~BIT(c.i.rt);
705 if (known & BIT(c.i.rs)) {
706 known |= BIT(c.i.rt);
707 v[c.i.rt] = v[c.i.rs] & c.i.imm;
709 known &= ~BIT(c.i.rt);
713 if (known & BIT(c.i.rs)) {
714 known |= BIT(c.i.rt);
715 v[c.i.rt] = v[c.i.rs] | c.i.imm;
717 known &= ~BIT(c.i.rt);
721 if (known & BIT(c.i.rs)) {
722 known |= BIT(c.i.rt);
723 v[c.i.rt] = v[c.i.rs] ^ c.i.imm;
725 known &= ~BIT(c.i.rt);
729 known |= BIT(c.i.rt);
730 v[c.i.rt] = c.i.imm << 16;
736 known &= ~BIT(c.r.rt);
741 if (c.r.op == OP_CP2_BASIC) {
743 case OP_CP2_BASIC_MFC2:
744 case OP_CP2_BASIC_CFC2:
745 known &= ~BIT(c.r.rt);
758 known &= ~BIT(c.i.rt);
761 if (known & BIT(c.r.rs)) {
762 known |= BIT(c.r.rd);
763 v[c.r.rd] = v[c.r.rs];
765 known &= ~BIT(c.r.rd);
769 if (known & BIT(c.i.rs)) {
770 known |= BIT(c.i.rt);
771 v[c.i.rt] = (s32)(s8)v[c.i.rs];
773 known &= ~BIT(c.i.rt);
777 if (known & BIT(c.i.rs)) {
778 known |= BIT(c.i.rt);
779 v[c.i.rt] = (s32)(s16)v[c.i.rs];
781 known &= ~BIT(c.i.rt);
791 static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset)
793 struct opcode *prev, *prev2 = NULL, *curr = &list[offset];
794 struct opcode *to_change, *to_nop;
797 if (curr->r.imm != 24 && curr->r.imm != 16)
800 idx = find_prev_writer(list, offset, curr->r.rt);
806 if (prev->i.op != OP_SPECIAL || prev->r.op != OP_SPECIAL_SLL ||
807 prev->r.imm != curr->r.imm || prev->r.rd != curr->r.rt)
810 if (prev->r.rd != prev->r.rt && curr->r.rd != curr->r.rt) {
815 if (!reg_is_dead(list, offset, curr->r.rt) ||
816 reg_is_read_or_written(list, idx, offset, curr->r.rd))
819 /* If rY is dead after the SRL, and rZ is not used after the SLL,
820 * we can change rY to rZ */
822 pr_debug("Detected SLL/SRA with middle temp register\n");
823 prev->r.rd = curr->r.rd;
824 curr->r.rt = prev->r.rd;
827 /* We got a SLL/SRA combo. If imm #16, that's a cast to u16.
828 * If imm #24 that's a cast to u8.
830 * First of all, make sure that the target register of the SLL is not
831 * read before the SRA. */
833 if (prev->r.rd == prev->r.rt) {
840 /* rX is used after the SRA - we cannot convert it. */
841 if (prev->r.rd != curr->r.rd && !reg_is_dead(list, offset, prev->r.rd))
851 idx2 = find_prev_writer(list, idx, prev->r.rt);
853 /* Note that PSX games sometimes do casts after
854 * a LHU or LBU; in this case we can change the
855 * load opcode to a LH or LB, and the cast can
856 * be changed to a MOV or a simple NOP. */
860 if (curr->r.rd != prev2->i.rt &&
861 !reg_is_dead(list, offset, prev2->i.rt))
863 else if (curr->r.imm == 16 && prev2->i.op == OP_LHU)
865 else if (curr->r.imm == 24 && prev2->i.op == OP_LBU)
871 if (curr->r.rd == prev2->i.rt) {
872 to_change->opcode = 0;
873 } else if (reg_is_dead(list, offset, prev2->i.rt) &&
874 !reg_is_read_or_written(list, idx2 + 1, offset, curr->r.rd)) {
875 /* The target register of the SRA is dead after the
876 * LBU/LHU; we can change the target register of the
877 * LBU/LHU to the one of the SRA. */
878 prev2->i.rt = curr->r.rd;
879 to_change->opcode = 0;
881 to_change->i.op = OP_META_MOV;
882 to_change->r.rd = curr->r.rd;
883 to_change->r.rs = prev2->i.rt;
886 if (to_nop->r.imm == 24)
887 pr_debug("Convert LBU+SLL+SRA to LB\n");
889 pr_debug("Convert LHU+SLL+SRA to LH\n");
894 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
896 prev->r.imm == 24 ? 'C' : 'S');
898 if (to_change == prev) {
899 to_change->i.rs = prev->r.rt;
900 to_change->i.rt = curr->r.rd;
902 to_change->i.rt = curr->r.rd;
903 to_change->i.rs = prev->r.rt;
906 if (to_nop->r.imm == 24)
907 to_change->i.op = OP_META_EXTC;
909 to_change->i.op = OP_META_EXTS;
915 static void lightrec_remove_useless_lui(struct block *block, unsigned int offset,
916 u32 known, u32 *values)
918 struct opcode *list = block->opcode_list,
919 *op = &block->opcode_list[offset];
922 if (!op_flag_sync(op->flags) && (known & BIT(op->i.rt)) &&
923 values[op->i.rt] == op->i.imm << 16) {
924 pr_debug("Converting duplicated LUI to NOP\n");
929 if (op->i.imm != 0 || op->i.rt == 0)
932 reader = find_next_reader(list, offset + 1, op->i.rt);
936 if (opcode_writes_register(list[reader].c, op->i.rt) ||
937 reg_is_dead(list, reader, op->i.rt)) {
938 pr_debug("Removing useless LUI 0x0\n");
940 if (list[reader].i.rs == op->i.rt)
941 list[reader].i.rs = 0;
942 if (list[reader].i.op == OP_SPECIAL &&
943 list[reader].i.rt == op->i.rt)
944 list[reader].i.rt = 0;
949 static void lightrec_modify_lui(struct block *block, unsigned int offset)
951 union code c, *lui = &block->opcode_list[offset].c;
952 bool stop = false, stop_next = false;
955 for (i = offset + 1; !stop && i < block->nb_ops; i++) {
956 c = block->opcode_list[i].c;
959 if ((opcode_is_store(c) && c.i.rt == lui->i.rt)
960 || (!opcode_is_load(c) && opcode_reads_register(c, lui->i.rt)))
963 if (opcode_writes_register(c, lui->i.rt)) {
964 pr_debug("Convert LUI at offset 0x%x to kuseg\n",
966 lui->i.imm = kunseg(lui->i.imm << 16) >> 16;
970 if (has_delay_slot(c))
975 static int lightrec_transform_branches(struct lightrec_state *state,
982 for (i = 0; i < block->nb_ops; i++) {
983 op = &block->opcode_list[i];
987 /* Transform J opcode into BEQ $zero, $zero if possible. */
988 offset = (s32)((block->pc & 0xf0000000) >> 2 | op->j.imm)
989 - (s32)(block->pc >> 2) - (s32)i - 1;
991 if (offset == (s16)offset) {
992 pr_debug("Transform J into BEQ $zero, $zero\n");
1008 static inline bool is_power_of_two(u32 value)
1010 return popcount32(value) == 1;
1013 static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
1015 struct opcode *list = block->opcode_list;
1016 struct opcode *prev, *op = NULL;
1018 u32 values[32] = { 0 };
1022 for (i = 0; i < block->nb_ops; i++) {
1027 known = lightrec_propagate_consts(op, prev, known, values);
1029 /* Transform all opcodes detected as useless to real NOPs
1030 * (0x0: SLL r0, r0, #0) */
1031 if (op->opcode != 0 && is_nop(op->c)) {
1032 pr_debug("Converting useless opcode 0x%08x to NOP\n",
1042 if (op->i.rs == op->i.rt) {
1045 } else if (op->i.rs == 0) {
1046 op->i.rs = op->i.rt;
1052 if (op->i.rs == 0) {
1053 op->i.rs = op->i.rt;
1059 if (!prev || !has_delay_slot(prev->c))
1060 lightrec_modify_lui(block, i);
1061 lightrec_remove_useless_lui(block, i, known, values);
1064 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
1065 * with register $zero to the MOV meta-opcode */
1069 if (op->i.imm == 0) {
1070 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
1071 op->i.op = OP_META_MOV;
1072 op->r.rd = op->i.rt;
1077 case OP_SPECIAL_SRA:
1078 if (op->r.imm == 0) {
1079 pr_debug("Convert SRA #0 to MOV\n");
1080 op->i.op = OP_META_MOV;
1081 op->r.rs = op->r.rt;
1085 lightrec_optimize_sll_sra(block->opcode_list, i);
1087 case OP_SPECIAL_SLL:
1088 case OP_SPECIAL_SRL:
1089 if (op->r.imm == 0) {
1090 pr_debug("Convert SLL/SRL #0 to MOV\n");
1091 op->i.op = OP_META_MOV;
1092 op->r.rs = op->r.rt;
1095 case OP_SPECIAL_MULT:
1096 case OP_SPECIAL_MULTU:
1097 if ((known & BIT(op->r.rs)) &&
1098 is_power_of_two(values[op->r.rs])) {
1100 op->c.i.rs = op->c.i.rt;
1102 } else if (!(known & BIT(op->r.rt)) ||
1103 !is_power_of_two(values[op->r.rt])) {
1107 pr_debug("Multiply by power-of-two: %u\n",
1110 if (op->r.op == OP_SPECIAL_MULT)
1111 op->i.op = OP_META_MULT2;
1113 op->i.op = OP_META_MULTU2;
1115 op->r.op = ffs32(values[op->r.rt]);
1118 case OP_SPECIAL_ADD:
1119 case OP_SPECIAL_ADDU:
1120 if (op->r.rs == 0) {
1121 pr_debug("Convert OR/ADD $zero to MOV\n");
1122 op->i.op = OP_META_MOV;
1123 op->r.rs = op->r.rt;
1126 case OP_SPECIAL_SUB:
1127 case OP_SPECIAL_SUBU:
1128 if (op->r.rt == 0) {
1129 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
1130 op->i.op = OP_META_MOV;
1145 static bool lightrec_can_switch_delay_slot(union code op, union code next_op)
1150 case OP_SPECIAL_JALR:
1151 if (opcode_reads_register(next_op, op.r.rd) ||
1152 opcode_writes_register(next_op, op.r.rd))
1156 if (opcode_writes_register(next_op, op.r.rs))
1166 if (opcode_reads_register(next_op, 31) ||
1167 opcode_writes_register(next_op, 31))
1173 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
1178 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1183 case OP_REGIMM_BLTZAL:
1184 case OP_REGIMM_BGEZAL:
1185 if (opcode_reads_register(next_op, 31) ||
1186 opcode_writes_register(next_op, 31))
1189 case OP_REGIMM_BLTZ:
1190 case OP_REGIMM_BGEZ:
1191 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1203 static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
1205 struct opcode *list, *next = &block->opcode_list[0];
1207 union code op, next_op;
1210 for (i = 0; i < block->nb_ops - 1; i++) {
1212 next = &block->opcode_list[i + 1];
1216 if (!has_delay_slot(op) || op_flag_no_ds(list->flags) ||
1217 op_flag_emulate_branch(list->flags) ||
1218 op.opcode == 0 || next_op.opcode == 0)
1221 if (i && has_delay_slot(block->opcode_list[i - 1].c) &&
1222 !op_flag_no_ds(block->opcode_list[i - 1].flags))
1225 if (op_flag_sync(next->flags))
1228 if (!lightrec_can_switch_delay_slot(list->c, next_op))
1231 pr_debug("Swap branch and delay slot opcodes "
1232 "at offsets 0x%x / 0x%x\n",
1233 i << 2, (i + 1) << 2);
1235 flags = next->flags | (list->flags & LIGHTREC_SYNC);
1238 next->flags = (list->flags | LIGHTREC_NO_DS) & ~LIGHTREC_SYNC;
1239 list->flags = flags | LIGHTREC_NO_DS;
1245 static int shrink_opcode_list(struct lightrec_state *state, struct block *block, u16 new_size)
1247 struct opcode_list *list, *old_list;
1249 if (new_size >= block->nb_ops) {
1250 pr_err("Invalid shrink size (%u vs %u)\n",
1251 new_size, block->nb_ops);
1255 list = lightrec_malloc(state, MEM_FOR_IR,
1256 sizeof(*list) + sizeof(struct opcode) * new_size);
1258 pr_err("Unable to allocate memory\n");
1262 old_list = container_of(block->opcode_list, struct opcode_list, ops);
1263 memcpy(list->ops, old_list->ops, sizeof(struct opcode) * new_size);
1265 lightrec_free_opcode_list(state, block->opcode_list);
1266 list->nb_ops = new_size;
1267 block->nb_ops = new_size;
1268 block->opcode_list = list->ops;
1270 pr_debug("Shrunk opcode list of block PC 0x%08x to %u opcodes\n",
1271 block->pc, new_size);
1276 static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1277 struct block *block)
1279 struct opcode *op, *list = block->opcode_list, *next = &list[0];
1284 for (i = 0; i < block->nb_ops - 1; i++) {
1286 next = &list[i + 1];
1288 if (!has_delay_slot(op->c) ||
1289 (!load_in_delay_slot(next->c) &&
1290 !has_delay_slot(next->c) &&
1291 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1294 if (op->c.opcode == next->c.opcode) {
1295 /* The delay slot is the exact same opcode as the branch
1296 * opcode: this is effectively a NOP */
1301 offset = i + 1 + (s16)op->i.imm;
1302 if (load_in_delay_slot(next->c) &&
1303 (offset >= 0 && offset < block->nb_ops) &&
1304 !opcode_reads_register(list[offset].c, next->c.i.rt)) {
1305 /* The 'impossible' branch is a local branch - we can
1306 * verify here that the first opcode of the target does
1307 * not use the target register of the delay slot */
1309 pr_debug("Branch at offset 0x%x has load delay slot, "
1310 "but is local and dest opcode does not read "
1311 "dest register\n", i << 2);
1315 op->flags |= LIGHTREC_EMULATE_BRANCH;
1318 pr_debug("First opcode of block PC 0x%08x is an impossible branch\n",
1321 /* If the first opcode is an 'impossible' branch, we
1322 * only keep the first two opcodes of the block (the
1323 * branch itself + its delay slot) */
1324 if (block->nb_ops > 2)
1325 ret = shrink_opcode_list(state, block, 2);
1333 static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1335 struct opcode *list;
1339 for (i = 0; i < block->nb_ops; i++) {
1340 list = &block->opcode_list[i];
1342 if (should_emulate(list))
1345 switch (list->i.op) {
1351 offset = i + 1 + (s16)list->i.imm;
1352 if (offset >= 0 && offset < block->nb_ops)
1359 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1361 if (should_emulate(&block->opcode_list[offset])) {
1362 pr_debug("Branch target must be emulated - skip\n");
1366 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1367 pr_debug("Branch target is a delay slot - skip\n");
1371 pr_debug("Adding sync at offset 0x%x\n", offset << 2);
1373 block->opcode_list[offset].flags |= LIGHTREC_SYNC;
1374 list->flags |= LIGHTREC_LOCAL_BRANCH;
1380 bool has_delay_slot(union code op)
1386 case OP_SPECIAL_JALR:
1404 bool should_emulate(const struct opcode *list)
1406 return op_flag_emulate_branch(list->flags) && has_delay_slot(list->c);
1409 static bool op_writes_rd(union code c)
1420 static void lightrec_add_reg_op(struct opcode *op, u8 reg, u32 reg_op)
1422 if (op_writes_rd(op->c) && reg == op->r.rd)
1423 op->flags |= LIGHTREC_REG_RD(reg_op);
1424 else if (op->i.rs == reg)
1425 op->flags |= LIGHTREC_REG_RS(reg_op);
1426 else if (op->i.rt == reg)
1427 op->flags |= LIGHTREC_REG_RT(reg_op);
1429 pr_debug("Cannot add unload/clean/discard flag: "
1430 "opcode does not touch register %s!\n",
1431 lightrec_reg_name(reg));
1434 static void lightrec_add_unload(struct opcode *op, u8 reg)
1436 lightrec_add_reg_op(op, reg, LIGHTREC_REG_UNLOAD);
1439 static void lightrec_add_discard(struct opcode *op, u8 reg)
1441 lightrec_add_reg_op(op, reg, LIGHTREC_REG_DISCARD);
1444 static void lightrec_add_clean(struct opcode *op, u8 reg)
1446 lightrec_add_reg_op(op, reg, LIGHTREC_REG_CLEAN);
1450 lightrec_early_unload_sync(struct opcode *list, s16 *last_r, s16 *last_w)
1455 for (reg = 0; reg < 34; reg++) {
1456 offset = s16_max(last_w[reg], last_r[reg]);
1459 lightrec_add_unload(&list[offset], reg);
1462 memset(last_r, 0xff, sizeof(*last_r) * 34);
1463 memset(last_w, 0xff, sizeof(*last_w) * 34);
1466 static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1470 s16 last_r[34], last_w[34], last_sync = 0, next_sync = 0;
1471 u64 mask_r, mask_w, dirty = 0, loaded = 0;
1474 memset(last_r, 0xff, sizeof(last_r));
1475 memset(last_w, 0xff, sizeof(last_w));
1479 * - the register is dirty, and is read again after a branch opcode
1482 * - the register is dirty or loaded, and is not read again
1483 * - the register is dirty or loaded, and is written again after a branch opcode
1484 * - the next opcode has the SYNC flag set
1487 * - the register is dirty or loaded, and is written again
1490 for (i = 0; i < block->nb_ops; i++) {
1491 op = &block->opcode_list[i];
1493 if (op_flag_sync(op->flags) || should_emulate(op)) {
1494 /* The next opcode has the SYNC flag set, or is a branch
1495 * that should be emulated: unload all registers. */
1496 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1501 if (next_sync == i) {
1503 pr_debug("Last sync: 0x%x\n", last_sync << 2);
1506 if (has_delay_slot(op->c)) {
1507 next_sync = i + 1 + !op_flag_no_ds(op->flags);
1508 pr_debug("Next sync: 0x%x\n", next_sync << 2);
1511 mask_r = opcode_read_mask(op->c);
1512 mask_w = opcode_write_mask(op->c);
1514 for (reg = 0; reg < 34; reg++) {
1515 if (mask_r & BIT(reg)) {
1516 if (dirty & BIT(reg) && last_w[reg] < last_sync) {
1517 /* The register is dirty, and is read
1518 * again after a branch: clean it */
1520 lightrec_add_clean(&block->opcode_list[last_w[reg]], reg);
1528 if (mask_w & BIT(reg)) {
1529 if ((dirty & BIT(reg) && last_w[reg] < last_sync) ||
1530 (loaded & BIT(reg) && last_r[reg] < last_sync)) {
1531 /* The register is dirty or loaded, and
1532 * is written again after a branch:
1535 offset = s16_max(last_w[reg], last_r[reg]);
1536 lightrec_add_unload(&block->opcode_list[offset], reg);
1538 loaded &= ~BIT(reg);
1539 } else if (!(mask_r & BIT(reg)) &&
1540 ((dirty & BIT(reg) && last_w[reg] > last_sync) ||
1541 (loaded & BIT(reg) && last_r[reg] > last_sync))) {
1542 /* The register is dirty or loaded, and
1543 * is written again: discard it */
1545 offset = s16_max(last_w[reg], last_r[reg]);
1546 lightrec_add_discard(&block->opcode_list[offset], reg);
1548 loaded &= ~BIT(reg);
1560 /* Unload all registers that are dirty or loaded at the end of block. */
1561 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1566 static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1568 struct opcode *prev = NULL, *list = NULL;
1569 enum psx_map psx_map;
1571 u32 values[32] = { 0 };
1573 u32 val, kunseg_val;
1576 for (i = 0; i < block->nb_ops; i++) {
1578 list = &block->opcode_list[i];
1581 known = lightrec_propagate_consts(list, prev, known, values);
1583 switch (list->i.op) {
1587 if (OPT_FLAG_STORES) {
1588 /* Mark all store operations that target $sp or $gp
1589 * as not requiring code invalidation. This is based
1590 * on the heuristic that stores using one of these
1591 * registers as address will never hit a code page. */
1592 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1593 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1594 pr_debug("Flaging opcode 0x%08x as not "
1595 "requiring invalidation\n",
1597 list->flags |= LIGHTREC_NO_INVALIDATE;
1598 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT);
1601 /* Detect writes whose destination address is inside the
1602 * current block, using constant propagation. When these
1603 * occur, we mark the blocks as not compilable. */
1604 if ((known & BIT(list->i.rs)) &&
1605 kunseg(values[list->i.rs]) >= kunseg(block->pc) &&
1606 kunseg(values[list->i.rs]) < (kunseg(block->pc) +
1607 block->nb_ops * 4)) {
1608 pr_debug("Self-modifying block detected\n");
1609 block_set_flags(block, BLOCK_NEVER_COMPILE);
1610 list->flags |= LIGHTREC_SMC;
1625 if (OPT_FLAG_IO && (known & BIT(list->i.rs))) {
1626 val = values[list->i.rs] + (s16) list->i.imm;
1627 kunseg_val = kunseg(val);
1628 psx_map = lightrec_get_map_idx(state, kunseg_val);
1630 list->flags &= ~LIGHTREC_IO_MASK;
1631 no_mask = val == kunseg_val;
1634 case PSX_MAP_KERNEL_USER_RAM:
1636 list->flags |= LIGHTREC_NO_MASK;
1638 case PSX_MAP_MIRROR1:
1639 case PSX_MAP_MIRROR2:
1640 case PSX_MAP_MIRROR3:
1641 pr_debug("Flaging opcode %u as RAM access\n", i);
1642 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_RAM);
1643 if (no_mask && state->mirrors_mapped)
1644 list->flags |= LIGHTREC_NO_MASK;
1647 pr_debug("Flaging opcode %u as BIOS access\n", i);
1648 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_BIOS);
1650 list->flags |= LIGHTREC_NO_MASK;
1652 case PSX_MAP_SCRATCH_PAD:
1653 pr_debug("Flaging opcode %u as scratchpad access\n", i);
1654 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_SCRATCH);
1656 list->flags |= LIGHTREC_NO_MASK;
1658 /* Consider that we're never going to run code from
1659 * the scratchpad. */
1660 list->flags |= LIGHTREC_NO_INVALIDATE;
1662 case PSX_MAP_HW_REGISTERS:
1663 if (state->ops.hw_direct &&
1664 state->ops.hw_direct(kunseg_val,
1665 opcode_is_store(list->c),
1666 opcode_get_io_size(list->c))) {
1667 pr_debug("Flagging opcode %u as direct I/O access\n",
1669 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT_HW);
1672 list->flags |= LIGHTREC_NO_MASK;
1677 pr_debug("Flagging opcode %u as I/O access\n",
1679 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_HW);
1692 static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1693 const struct opcode *last,
1694 u32 mask, bool sync, bool mflo, bool another)
1696 const struct opcode *op, *next = &block->opcode_list[offset];
1698 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1702 for (i = offset; i < block->nb_ops; i++) {
1704 next = &block->opcode_list[i + 1];
1707 /* If any other opcode writes or reads to the register
1708 * we'd use, then we cannot use it anymore. */
1709 mask |= opcode_read_mask(op->c);
1710 mask |= opcode_write_mask(op->c);
1712 if (op_flag_sync(op->flags))
1721 /* TODO: handle backwards branches too */
1722 if (!last && op_flag_local_branch(op->flags) &&
1723 (s16)op->c.i.imm >= 0) {
1724 branch_offset = i + 1 + (s16)op->c.i.imm
1725 - !!op_flag_no_ds(op->flags);
1727 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1728 mask, sync, mflo, false);
1729 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1730 mask, sync, mflo, false);
1731 if (reg > 0 && reg == reg2)
1737 return mflo ? REG_LO : REG_HI;
1739 case OP_META_MULTU2:
1743 case OP_SPECIAL_MULT:
1744 case OP_SPECIAL_MULTU:
1745 case OP_SPECIAL_DIV:
1746 case OP_SPECIAL_DIVU:
1748 case OP_SPECIAL_MTHI:
1752 case OP_SPECIAL_MTLO:
1760 if (!sync && !op_flag_no_ds(op->flags) &&
1761 (next->i.op == OP_SPECIAL) &&
1762 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1763 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1767 case OP_SPECIAL_JALR:
1769 case OP_SPECIAL_MFHI:
1773 /* Must use REG_HI if there is another MFHI target*/
1774 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1775 0, sync, mflo, true);
1776 if (reg2 > 0 && reg2 != REG_HI)
1779 if (!sync && !(old_mask & BIT(op->r.rd)))
1785 case OP_SPECIAL_MFLO:
1789 /* Must use REG_LO if there is another MFLO target*/
1790 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1791 0, sync, mflo, true);
1792 if (reg2 > 0 && reg2 != REG_LO)
1795 if (!sync && !(old_mask & BIT(op->r.rd)))
1814 static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1820 /* This function will remove the following MFLO/MFHI. It must be called
1821 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1823 for (i = offset; i < last; i++) {
1824 struct opcode *op = &block->opcode_list[i];
1832 /* TODO: handle backwards branches too */
1833 if (op_flag_local_branch(op->flags) && (s16)op->c.i.imm >= 0) {
1834 branch_offset = i + 1 + (s16)op->c.i.imm
1835 - !!op_flag_no_ds(op->flags);
1837 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1838 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1843 if (lo && op->r.op == OP_SPECIAL_MFLO) {
1844 pr_debug("Removing MFLO opcode at offset 0x%x\n",
1848 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
1849 pr_debug("Removing MFHI opcode at offset 0x%x\n",
1862 static bool lightrec_always_skip_div_check(void)
1871 static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
1873 struct opcode *prev, *list = NULL;
1877 u32 values[32] = { 0 };
1879 for (i = 0; i < block->nb_ops - 1; i++) {
1881 list = &block->opcode_list[i];
1884 known = lightrec_propagate_consts(list, prev, known, values);
1886 switch (list->i.op) {
1888 switch (list->r.op) {
1889 case OP_SPECIAL_DIV:
1890 case OP_SPECIAL_DIVU:
1891 /* If we are dividing by a non-zero constant, don't
1892 * emit the div-by-zero check. */
1893 if (lightrec_always_skip_div_check() ||
1894 ((known & BIT(list->c.r.rt)) && values[list->c.r.rt]))
1895 list->flags |= LIGHTREC_NO_DIV_CHECK;
1897 case OP_SPECIAL_MULT:
1898 case OP_SPECIAL_MULTU:
1905 case OP_META_MULTU2:
1911 /* Don't support opcodes in delay slots */
1912 if ((i && has_delay_slot(block->opcode_list[i - 1].c)) ||
1913 op_flag_no_ds(list->flags)) {
1917 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
1919 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1920 " not writing LO\n", i << 2);
1921 list->flags |= LIGHTREC_NO_LO;
1924 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
1926 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1927 " not writing HI\n", i << 2);
1928 list->flags |= LIGHTREC_NO_HI;
1931 if (!reg_lo && !reg_hi) {
1932 pr_debug("Both LO/HI unused in this block, they will "
1933 "probably be used in parent block - removing "
1935 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
1938 if (reg_lo > 0 && reg_lo != REG_LO) {
1939 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
1940 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
1942 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
1943 list->r.rd = reg_lo;
1948 if (reg_hi > 0 && reg_hi != REG_HI) {
1949 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
1950 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
1952 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
1953 list->r.imm = reg_hi;
1962 static bool remove_div_sequence(struct block *block, unsigned int offset)
1965 unsigned int i, found = 0;
1968 * Scan for the zero-checking sequence that GCC automatically introduced
1969 * after most DIV/DIVU opcodes. This sequence checks the value of the
1970 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
1971 * handler to crash the PS1.
1973 * For DIV opcodes, this sequence additionally checks that the signed
1974 * operation does not overflow.
1976 * With the assumption that the games never crashed the PS1, we can
1977 * therefore assume that the games never divided by zero or overflowed,
1978 * and these sequences can be removed.
1981 for (i = offset; i < block->nb_ops; i++) {
1982 op = &block->opcode_list[i];
1985 if (op->i.op == OP_SPECIAL &&
1986 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
1989 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
1990 /* BNE ???, zero, +8 */
1995 } else if (found == 1 && !op->opcode) {
1998 } else if (found == 2 && op->opcode == 0x0007000d) {
2001 } else if (found == 3 && op->opcode == 0x2401ffff) {
2004 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
2005 /* BNE ???, at, +16 */
2007 } else if (found == 5 && op->opcode == 0x3c018000) {
2008 /* LUI at, 0x8000 */
2010 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
2011 /* BNE ???, at, +16 */
2013 } else if (found == 7 && !op->opcode) {
2016 } else if (found == 8 && op->opcode == 0x0006000d) {
2029 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
2030 found == 9 ? "" : "U", offset << 2);
2032 for (i = 0; i < found; i++)
2033 block->opcode_list[offset + i].opcode = 0;
2041 static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
2042 struct block *block)
2047 for (i = 0; i < block->nb_ops; i++) {
2048 op = &block->opcode_list[i];
2050 if (op->i.op == OP_SPECIAL &&
2051 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
2052 remove_div_sequence(block, i + 1))
2053 op->flags |= LIGHTREC_NO_DIV_CHECK;
2059 static const u32 memset_code[] = {
2060 0x10a00006, // beqz a1, 2f
2061 0x24a2ffff, // addiu v0,a1,-1
2062 0x2403ffff, // li v1,-1
2063 0xac800000, // 1: sw zero,0(a0)
2064 0x2442ffff, // addiu v0,v0,-1
2065 0x1443fffd, // bne v0,v1, 1b
2066 0x24840004, // addiu a0,a0,4
2067 0x03e00008, // 2: jr ra
2071 static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
2076 for (i = 0; i < block->nb_ops; i++) {
2077 c = block->opcode_list[i].c;
2079 if (c.opcode != memset_code[i])
2082 if (i == ARRAY_SIZE(memset_code) - 1) {
2084 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
2085 block_set_flags(block,
2086 BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE);
2088 /* Return non-zero to skip other optimizers. */
2096 static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
2097 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
2098 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
2099 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
2100 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_branches),
2101 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
2102 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
2103 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
2104 IF_OPT(OPT_FLAG_IO || OPT_FLAG_STORES, &lightrec_flag_io),
2105 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
2106 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
2109 int lightrec_optimize(struct lightrec_state *state, struct block *block)
2114 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
2115 if (lightrec_optimizers[i]) {
2116 ret = (*lightrec_optimizers[i])(state, block);