1 // SPDX-License-Identifier: LGPL-2.1-or-later
3 * Copyright (C) 2014-2021 Paul Cercueil <paul@crapouillou.net>
7 #include "lightrec-config.h"
8 #include "disassembler.h"
10 #include "memmanager.h"
11 #include "optimizer.h"
19 #define IF_OPT(opt, ptr) ((opt) ? (ptr) : NULL)
21 struct optimizer_list {
22 void (**optimizers)(struct opcode *);
23 unsigned int nb_optimizers;
26 static bool is_nop(union code op);
28 bool is_unconditional_jump(union code c)
32 return c.r.op == OP_SPECIAL_JR || c.r.op == OP_SPECIAL_JALR;
38 return c.i.rs == c.i.rt;
40 return (c.r.rt == OP_REGIMM_BGEZ ||
41 c.r.rt == OP_REGIMM_BGEZAL) && c.i.rs == 0;
47 bool is_syscall(union code c)
49 return (c.i.op == OP_SPECIAL && c.r.op == OP_SPECIAL_SYSCALL) ||
50 (c.i.op == OP_CP0 && (c.r.rs == OP_CP0_MTC0 ||
51 c.r.rs == OP_CP0_CTC0) &&
52 (c.r.rd == 12 || c.r.rd == 13));
55 static u64 opcode_read_mask(union code op)
60 case OP_SPECIAL_SYSCALL:
61 case OP_SPECIAL_BREAK:
80 return BIT(op.r.rs) | BIT(op.r.rt);
91 if (op.r.op == OP_CP2_BASIC) {
93 case OP_CP2_BASIC_MTC2:
94 case OP_CP2_BASIC_CTC2:
106 if (op.i.rs == op.i.rt)
117 return BIT(op.i.rs) | BIT(op.i.rt);
125 static u64 mult_div_write_mask(union code op)
129 if (!OPT_FLAG_MULT_DIV)
130 return BIT(REG_LO) | BIT(REG_HI);
133 flags = BIT(op.r.rd);
137 flags |= BIT(op.r.imm);
139 flags |= BIT(REG_HI);
144 u64 opcode_write_mask(union code op)
149 return mult_div_write_mask(op);
155 case OP_SPECIAL_SYSCALL:
156 case OP_SPECIAL_BREAK:
158 case OP_SPECIAL_MULT:
159 case OP_SPECIAL_MULTU:
161 case OP_SPECIAL_DIVU:
162 return mult_div_write_mask(op);
163 case OP_SPECIAL_MTHI:
165 case OP_SPECIAL_MTLO:
201 if (op.r.op == OP_CP2_BASIC) {
203 case OP_CP2_BASIC_MFC2:
204 case OP_CP2_BASIC_CFC2:
213 case OP_REGIMM_BLTZAL:
214 case OP_REGIMM_BGEZAL:
224 bool opcode_reads_register(union code op, u8 reg)
226 return opcode_read_mask(op) & BIT(reg);
229 bool opcode_writes_register(union code op, u8 reg)
231 return opcode_write_mask(op) & BIT(reg);
234 static int find_prev_writer(const struct opcode *list, unsigned int offset, u8 reg)
239 if (op_flag_sync(list[offset].flags))
242 for (i = offset; i > 0; i--) {
245 if (opcode_writes_register(c, reg)) {
246 if (i > 1 && has_delay_slot(list[i - 2].c))
252 if (op_flag_sync(list[i - 1].flags) ||
254 opcode_reads_register(c, reg))
261 static int find_next_reader(const struct opcode *list, unsigned int offset, u8 reg)
266 if (op_flag_sync(list[offset].flags))
269 for (i = offset; ; i++) {
272 if (opcode_reads_register(c, reg))
275 if (op_flag_sync(list[i].flags)
276 || (op_flag_no_ds(list[i].flags) && has_delay_slot(c))
277 || is_delay_slot(list, i)
278 || opcode_writes_register(c, reg))
285 static bool reg_is_dead(const struct opcode *list, unsigned int offset, u8 reg)
289 if (op_flag_sync(list[offset].flags) || is_delay_slot(list, offset))
292 for (i = offset + 1; ; i++) {
293 if (opcode_reads_register(list[i].c, reg))
296 if (opcode_writes_register(list[i].c, reg))
299 if (has_delay_slot(list[i].c)) {
300 if (op_flag_no_ds(list[i].flags) ||
301 opcode_reads_register(list[i + 1].c, reg))
304 return opcode_writes_register(list[i + 1].c, reg);
309 static bool reg_is_read(const struct opcode *list,
310 unsigned int a, unsigned int b, u8 reg)
312 /* Return true if reg is read in one of the opcodes of the interval
315 if (!is_nop(list[a].c) && opcode_reads_register(list[a].c, reg))
322 static bool reg_is_written(const struct opcode *list,
323 unsigned int a, unsigned int b, u8 reg)
325 /* Return true if reg is written in one of the opcodes of the interval
329 if (!is_nop(list[a].c) && opcode_writes_register(list[a].c, reg))
336 static bool reg_is_read_or_written(const struct opcode *list,
337 unsigned int a, unsigned int b, u8 reg)
339 return reg_is_read(list, a, b, reg) || reg_is_written(list, a, b, reg);
342 bool opcode_is_mfc(union code op)
356 if (op.r.op == OP_CP2_BASIC) {
358 case OP_CP2_BASIC_MFC2:
359 case OP_CP2_BASIC_CFC2:
374 bool opcode_is_load(union code op)
391 static bool opcode_is_store(union code op)
406 static u8 opcode_get_io_size(union code op)
422 bool opcode_is_io(union code op)
424 return opcode_is_load(op) || opcode_is_store(op);
428 static bool is_nop(union code op)
430 if (opcode_writes_register(op, 0)) {
433 return op.r.rs != OP_CP0_MFC0;
451 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
453 case OP_SPECIAL_ADDU:
454 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
455 (op.r.rd == op.r.rs && op.r.rt == 0);
457 case OP_SPECIAL_SUBU:
458 return op.r.rd == op.r.rs && op.r.rt == 0;
460 if (op.r.rd == op.r.rt)
461 return op.r.rd == op.r.rs || op.r.rs == 0;
463 return (op.r.rd == op.r.rs) && op.r.rt == 0;
467 return op.r.rd == op.r.rt && op.r.imm == 0;
468 case OP_SPECIAL_MFHI:
469 case OP_SPECIAL_MFLO:
477 return op.i.rt == op.i.rs && op.i.imm == 0;
479 return (op.i.rs == 0 || op.i.imm == 1);
481 return (op.i.op == OP_REGIMM_BLTZ ||
482 op.i.op == OP_REGIMM_BLTZAL) &&
483 (op.i.rs == 0 || op.i.imm == 1);
485 return (op.i.rs == op.i.rt || op.i.imm == 1);
491 static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset,
492 struct constprop_data *v)
494 struct opcode *ldop = NULL, *curr = &list[offset], *next;
495 struct opcode *to_change, *to_nop;
498 if (curr->r.imm != 24 && curr->r.imm != 16)
501 if (is_delay_slot(list, offset))
504 idx = find_next_reader(list, offset + 1, curr->r.rd);
510 if (next->i.op != OP_SPECIAL || next->r.op != OP_SPECIAL_SRA ||
511 next->r.imm != curr->r.imm || next->r.rt != curr->r.rd)
514 if (curr->r.rd != curr->r.rt && next->r.rd != next->r.rt) {
519 if (!reg_is_dead(list, idx, curr->r.rd) ||
520 reg_is_read_or_written(list, offset, idx, next->r.rd))
523 /* If rY is dead after the SRL, and rZ is not used after the SLL,
524 * we can change rY to rZ */
526 pr_debug("Detected SLL/SRA with middle temp register\n");
527 curr->r.rd = next->r.rd;
528 next->r.rt = curr->r.rd;
531 /* We got a SLL/SRA combo. If imm #16, that's a cast to s16.
532 * If imm #24 that's a cast to s8.
534 * First of all, make sure that the target register of the SLL is not
535 * read after the SRA. */
537 if (curr->r.rd == curr->r.rt) {
544 /* rX is used after the SRA - we cannot convert it. */
545 if (curr->r.rd != next->r.rd && !reg_is_dead(list, idx, curr->r.rd))
555 idx2 = find_prev_writer(list, offset, curr->r.rt);
557 /* Note that PSX games sometimes do casts after
558 * a LHU or LBU; in this case we can change the
559 * load opcode to a LH or LB, and the cast can
560 * be changed to a MOV or a simple NOP. */
564 if (next->r.rd != ldop->i.rt &&
565 !reg_is_dead(list, idx, ldop->i.rt))
567 else if (curr->r.imm == 16 && ldop->i.op == OP_LHU)
569 else if (curr->r.imm == 24 && ldop->i.op == OP_LBU)
575 if (next->r.rd == ldop->i.rt) {
576 to_change->opcode = 0;
577 } else if (reg_is_dead(list, idx, ldop->i.rt) &&
578 !reg_is_read_or_written(list, idx2 + 1, idx, next->r.rd)) {
579 /* The target register of the SRA is dead after the
580 * LBU/LHU; we can change the target register of the
581 * LBU/LHU to the one of the SRA. */
582 v[ldop->i.rt].known = 0;
583 v[ldop->i.rt].sign = 0;
584 ldop->i.rt = next->r.rd;
585 to_change->opcode = 0;
587 to_change->i.op = OP_META;
588 to_change->m.op = OP_META_MOV;
589 to_change->m.rd = next->r.rd;
590 to_change->m.rs = ldop->i.rt;
593 if (to_nop->r.imm == 24)
594 pr_debug("Convert LBU+SLL+SRA to LB\n");
596 pr_debug("Convert LHU+SLL+SRA to LH\n");
598 v[ldop->i.rt].known = 0;
599 v[ldop->i.rt].sign = 0xffffff80 << 24 - curr->r.imm;
604 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
605 curr->r.imm, curr->r.imm == 24 ? 'C' : 'S');
607 to_change->m.rs = curr->r.rt;
608 to_change->m.op = to_nop->r.imm == 24 ? OP_META_EXTC : OP_META_EXTS;
609 to_change->i.op = OP_META;
616 lightrec_remove_useless_lui(struct block *block, unsigned int offset,
617 const struct constprop_data *v)
619 struct opcode *list = block->opcode_list,
620 *op = &block->opcode_list[offset];
623 if (!op_flag_sync(op->flags) && is_known(v, op->i.rt) &&
624 v[op->i.rt].value == op->i.imm << 16) {
625 pr_debug("Converting duplicated LUI to NOP\n");
630 if (op->i.imm != 0 || op->i.rt == 0 || offset == block->nb_ops - 1)
633 reader = find_next_reader(list, offset + 1, op->i.rt);
637 if (opcode_writes_register(list[reader].c, op->i.rt) ||
638 reg_is_dead(list, reader, op->i.rt)) {
639 pr_debug("Removing useless LUI 0x0\n");
641 if (list[reader].i.rs == op->i.rt)
642 list[reader].i.rs = 0;
643 if (list[reader].i.op == OP_SPECIAL &&
644 list[reader].i.rt == op->i.rt)
645 list[reader].i.rt = 0;
650 static void lightrec_modify_lui(struct block *block, unsigned int offset)
652 union code c, *lui = &block->opcode_list[offset].c;
653 bool stop = false, stop_next = false;
656 for (i = offset + 1; !stop && i < block->nb_ops; i++) {
657 c = block->opcode_list[i].c;
660 if ((opcode_is_store(c) && c.i.rt == lui->i.rt)
661 || (!opcode_is_load(c) && opcode_reads_register(c, lui->i.rt)))
664 if (opcode_writes_register(c, lui->i.rt)) {
665 if (c.i.op == OP_LWL || c.i.op == OP_LWR) {
666 /* LWL/LWR only partially write their target register;
667 * therefore the LUI should not write a different value. */
671 pr_debug("Convert LUI at offset 0x%x to kuseg\n",
673 lui->i.imm = kunseg(lui->i.imm << 16) >> 16;
677 if (has_delay_slot(c))
682 static int lightrec_transform_branches(struct lightrec_state *state,
689 for (i = 0; i < block->nb_ops; i++) {
690 op = &block->opcode_list[i];
694 /* Transform J opcode into BEQ $zero, $zero if possible. */
695 offset = (s32)((block->pc & 0xf0000000) >> 2 | op->j.imm)
696 - (s32)(block->pc >> 2) - (s32)i - 1;
698 if (offset == (s16)offset) {
699 pr_debug("Transform J into BEQ $zero, $zero\n");
715 static inline bool is_power_of_two(u32 value)
717 return popcount32(value) == 1;
720 static void lightrec_patch_known_zero(struct opcode *op,
721 const struct constprop_data *v)
727 case OP_SPECIAL_JALR:
728 case OP_SPECIAL_MTHI:
729 case OP_SPECIAL_MTLO:
730 if (is_known_zero(v, op->r.rs))
734 if (is_known_zero(v, op->r.rs))
740 if (is_known_zero(v, op->r.rt))
743 case OP_SPECIAL_SYSCALL:
744 case OP_SPECIAL_BREAK:
745 case OP_SPECIAL_MFHI:
746 case OP_SPECIAL_MFLO:
754 if (is_known_zero(v, op->r.rt))
762 if (op->r.op == OP_CP2_BASIC) {
764 case OP_CP2_BASIC_MTC2:
765 case OP_CP2_BASIC_CTC2:
766 if (is_known_zero(v, op->r.rt))
776 if (is_known_zero(v, op->i.rt))
792 if (is_known_zero(v, op->m.rs))
800 if (is_known_zero(v, op->i.rt))
812 if (is_known(v, op->i.rs)
813 && kunseg(v[op->i.rs].value) == 0)
821 static void lightrec_reset_syncs(struct block *block)
823 struct opcode *op, *list = block->opcode_list;
827 for (i = 0; i < block->nb_ops; i++)
828 list[i].flags &= ~LIGHTREC_SYNC;
830 for (i = 0; i < block->nb_ops; i++) {
833 if (has_delay_slot(op->c)) {
834 if (op_flag_local_branch(op->flags)) {
835 offset = i + 1 - op_flag_no_ds(op->flags) + (s16)op->i.imm;
836 list[offset].flags |= LIGHTREC_SYNC;
839 if (op_flag_emulate_branch(op->flags) && i + 2 < block->nb_ops)
840 list[i + 2].flags |= LIGHTREC_SYNC;
845 static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
847 struct opcode *op, *list = block->opcode_list;
848 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
853 for (i = 0; i < block->nb_ops; i++) {
856 lightrec_consts_propagate(block, i, v);
858 lightrec_patch_known_zero(op, v);
860 /* Transform all opcodes detected as useless to real NOPs
861 * (0x0: SLL r0, r0, #0) */
862 if (op->opcode != 0 && is_nop(op->c)) {
863 pr_debug("Converting useless opcode 0x%08x to NOP\n",
873 if (op->i.rs == op->i.rt ||
874 (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
875 v[op->i.rs].value == v[op->i.rt].value)) {
876 if (op->i.rs != op->i.rt)
877 pr_debug("Found always-taken BEQ\n");
881 } else if (v[op->i.rs].known & v[op->i.rt].known &
882 (v[op->i.rs].value ^ v[op->i.rt].value)) {
883 pr_debug("Found never-taken BEQ\n");
885 local = op_flag_local_branch(op->flags);
890 lightrec_reset_syncs(block);
891 } else if (op->i.rs == 0) {
898 if (v[op->i.rs].known & v[op->i.rt].known &
899 (v[op->i.rs].value ^ v[op->i.rt].value)) {
900 pr_debug("Found always-taken BNE\n");
905 } else if (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
906 v[op->i.rs].value == v[op->i.rt].value) {
907 pr_debug("Found never-taken BNE\n");
909 local = op_flag_local_branch(op->flags);
914 lightrec_reset_syncs(block);
915 } else if (op->i.rs == 0) {
922 if (v[op->i.rs].known & BIT(31) &&
923 v[op->i.rs].value & BIT(31)) {
924 pr_debug("Found always-taken BLEZ\n");
933 if (v[op->i.rs].known & BIT(31) &&
934 v[op->i.rs].value & BIT(31)) {
935 pr_debug("Found never-taken BGTZ\n");
937 local = op_flag_local_branch(op->flags);
942 lightrec_reset_syncs(block);
947 if (i == 0 || !has_delay_slot(list[i - 1].c))
948 lightrec_modify_lui(block, i);
949 lightrec_remove_useless_lui(block, i, v);
952 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
953 * with register $zero to the MOV meta-opcode */
957 if (op->i.imm == 0) {
958 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
960 op->m.op = OP_META_MOV;
965 if (bits_are_known_zero(v, op->i.rs, ~op->i.imm)) {
966 pr_debug("Found useless ANDI 0x%x\n", op->i.imm);
968 if (op->i.rs == op->i.rt) {
972 op->m.op = OP_META_MOV;
981 if (!(v[op->r.rs].known & BIT(31)))
984 if (!!(v[op->r.rs].value & BIT(31))
985 ^ (op->r.rt == OP_REGIMM_BGEZ)) {
986 pr_debug("Found always-taken BLTZ/BGEZ\n");
991 pr_debug("Found never-taken BLTZ/BGEZ\n");
993 local = op_flag_local_branch(op->flags);
998 lightrec_reset_syncs(block);
1001 case OP_REGIMM_BLTZAL:
1002 case OP_REGIMM_BGEZAL:
1003 /* TODO: Detect always-taken and replace with JAL */
1009 case OP_SPECIAL_SRAV:
1010 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1013 pr_debug("Convert SRAV to SRA\n");
1014 op->r.imm = v[op->r.rs].value & 0x1f;
1015 op->r.op = OP_SPECIAL_SRA;
1018 case OP_SPECIAL_SRA:
1019 if (op->r.imm == 0) {
1020 pr_debug("Convert SRA #0 to MOV\n");
1021 op->m.rs = op->r.rt;
1022 op->m.op = OP_META_MOV;
1028 case OP_SPECIAL_SLLV:
1029 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1032 pr_debug("Convert SLLV to SLL\n");
1033 op->r.imm = v[op->r.rs].value & 0x1f;
1034 op->r.op = OP_SPECIAL_SLL;
1037 case OP_SPECIAL_SLL:
1038 if (op->r.imm == 0) {
1039 pr_debug("Convert SLL #0 to MOV\n");
1040 op->m.rs = op->r.rt;
1041 op->m.op = OP_META_MOV;
1045 lightrec_optimize_sll_sra(block->opcode_list, i, v);
1048 case OP_SPECIAL_SRLV:
1049 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1052 pr_debug("Convert SRLV to SRL\n");
1053 op->r.imm = v[op->r.rs].value & 0x1f;
1054 op->r.op = OP_SPECIAL_SRL;
1057 case OP_SPECIAL_SRL:
1058 if (op->r.imm == 0) {
1059 pr_debug("Convert SRL #0 to MOV\n");
1060 op->m.rs = op->r.rt;
1061 op->m.op = OP_META_MOV;
1066 case OP_SPECIAL_MULT:
1067 case OP_SPECIAL_MULTU:
1068 if (is_known(v, op->r.rs) &&
1069 is_power_of_two(v[op->r.rs].value)) {
1071 op->c.i.rs = op->c.i.rt;
1073 } else if (!is_known(v, op->r.rt) ||
1074 !is_power_of_two(v[op->r.rt].value)) {
1078 pr_debug("Multiply by power-of-two: %u\n",
1081 if (op->r.op == OP_SPECIAL_MULT)
1082 op->i.op = OP_META_MULT2;
1084 op->i.op = OP_META_MULTU2;
1086 op->r.op = ctz32(v[op->r.rt].value);
1088 case OP_SPECIAL_NOR:
1089 if (op->r.rs == 0 || op->r.rt == 0) {
1090 pr_debug("Convert NOR $zero to COM\n");
1092 op->m.op = OP_META_COM;
1094 op->m.rs = op->r.rt;
1098 case OP_SPECIAL_ADD:
1099 case OP_SPECIAL_ADDU:
1100 if (op->r.rs == 0) {
1101 pr_debug("Convert OR/ADD $zero to MOV\n");
1102 op->m.rs = op->r.rt;
1103 op->m.op = OP_META_MOV;
1107 case OP_SPECIAL_SUB:
1108 case OP_SPECIAL_SUBU:
1109 if (op->r.rt == 0) {
1110 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
1111 op->m.op = OP_META_MOV;
1127 static bool lightrec_can_switch_delay_slot(union code op, union code next_op)
1132 case OP_SPECIAL_JALR:
1133 if (opcode_reads_register(next_op, op.r.rd) ||
1134 opcode_writes_register(next_op, op.r.rd))
1138 if (opcode_writes_register(next_op, op.r.rs))
1148 if (opcode_reads_register(next_op, 31) ||
1149 opcode_writes_register(next_op, 31))
1155 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
1160 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1165 case OP_REGIMM_BLTZAL:
1166 case OP_REGIMM_BGEZAL:
1167 if (opcode_reads_register(next_op, 31) ||
1168 opcode_writes_register(next_op, 31))
1171 case OP_REGIMM_BLTZ:
1172 case OP_REGIMM_BGEZ:
1173 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1185 static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
1187 struct opcode *list, *next = &block->opcode_list[0];
1189 union code op, next_op;
1192 for (i = 0; i < block->nb_ops - 1; i++) {
1194 next = &block->opcode_list[i + 1];
1198 if (!has_delay_slot(op) || op_flag_no_ds(list->flags) ||
1199 op_flag_emulate_branch(list->flags) ||
1200 op.opcode == 0 || next_op.opcode == 0)
1203 if (is_delay_slot(block->opcode_list, i))
1206 if (op_flag_sync(next->flags))
1209 if (op_flag_load_delay(next->flags) && opcode_is_load(next_op))
1212 if (!lightrec_can_switch_delay_slot(list->c, next_op))
1215 pr_debug("Swap branch and delay slot opcodes "
1216 "at offsets 0x%x / 0x%x\n",
1217 i << 2, (i + 1) << 2);
1219 flags = next->flags | (list->flags & LIGHTREC_SYNC);
1222 next->flags = (list->flags | LIGHTREC_NO_DS) & ~LIGHTREC_SYNC;
1223 list->flags = flags | LIGHTREC_NO_DS;
1229 static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1230 struct block *block)
1232 struct opcode *op, *list = block->opcode_list, *next = &list[0];
1236 for (i = 0; i < block->nb_ops - 1; i++) {
1238 next = &list[i + 1];
1240 if (!has_delay_slot(op->c) ||
1241 (!has_delay_slot(next->c) &&
1242 !opcode_is_mfc(next->c) &&
1243 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1246 if (op->c.opcode == next->c.opcode) {
1247 /* The delay slot is the exact same opcode as the branch
1248 * opcode: this is effectively a NOP */
1253 op->flags |= LIGHTREC_EMULATE_BRANCH;
1255 if (OPT_LOCAL_BRANCHES && i + 2 < block->nb_ops) {
1256 /* The interpreter will only emulate the branch, then
1257 * return to the compiled code. Add a SYNC after the
1258 * branch + delay slot in the case where the branch
1260 list[i + 2].flags |= LIGHTREC_SYNC;
1267 static bool is_local_branch(const struct block *block, unsigned int idx)
1269 const struct opcode *op = &block->opcode_list[idx];
1272 switch (op->c.i.op) {
1278 offset = idx + 1 + (s16)op->c.i.imm;
1279 if (offset >= 0 && offset < block->nb_ops)
1287 static int lightrec_handle_load_delays(struct lightrec_state *state,
1288 struct block *block)
1290 struct opcode *op, *list = block->opcode_list;
1294 for (i = 0; i < block->nb_ops; i++) {
1297 if (!opcode_is_load(op->c) || !op->c.i.rt || op->c.i.op == OP_LWC2)
1300 if (!is_delay_slot(list, i)) {
1301 /* Only handle load delays in delay slots.
1302 * PSX games never abused load delay slots otherwise. */
1306 if (is_local_branch(block, i - 1)) {
1307 imm = (s16)list[i - 1].c.i.imm;
1309 if (!opcode_reads_register(list[i + imm].c, op->c.i.rt)) {
1310 /* The target opcode of the branch is inside
1311 * the block, and it does not read the register
1312 * written to by the load opcode; we can ignore
1313 * the load delay. */
1318 op->flags |= LIGHTREC_LOAD_DELAY;
1324 static int lightrec_swap_load_delays(struct lightrec_state *state,
1325 struct block *block)
1329 bool in_ds = false, skip_next = false;
1332 if (block->nb_ops < 2)
1335 for (i = 0; i < block->nb_ops - 2; i++) {
1336 c = block->opcode_list[i].c;
1340 } else if (!in_ds && opcode_is_load(c) && c.i.op != OP_LWC2) {
1341 next = block->opcode_list[i + 1].c;
1343 if (c.i.op == OP_LWL && next.i.op == OP_LWR)
1346 if (opcode_reads_register(next, c.i.rt)
1347 && !opcode_writes_register(next, c.i.rs)) {
1348 pr_debug("Swapping opcodes at offset 0x%x to "
1349 "respect load delay\n", i << 2);
1351 op = block->opcode_list[i];
1352 block->opcode_list[i] = block->opcode_list[i + 1];
1353 block->opcode_list[i + 1] = op;
1358 in_ds = has_delay_slot(c);
1364 static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1366 const struct opcode *ds;
1367 struct opcode *list;
1371 for (i = 0; i < block->nb_ops; i++) {
1372 list = &block->opcode_list[i];
1374 if (should_emulate(list) || !is_local_branch(block, i))
1377 offset = i + 1 + (s16)list->c.i.imm;
1379 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1381 ds = get_delay_slot(block->opcode_list, i);
1382 if (op_flag_load_delay(ds->flags) && opcode_is_load(ds->c)) {
1383 pr_debug("Branch delay slot has a load delay - skip\n");
1387 if (should_emulate(&block->opcode_list[offset])) {
1388 pr_debug("Branch target must be emulated - skip\n");
1392 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1393 pr_debug("Branch target is a delay slot - skip\n");
1397 list->flags |= LIGHTREC_LOCAL_BRANCH;
1400 lightrec_reset_syncs(block);
1405 bool has_delay_slot(union code op)
1411 case OP_SPECIAL_JALR:
1429 bool is_delay_slot(const struct opcode *list, unsigned int offset)
1432 && !op_flag_no_ds(list[offset - 1].flags)
1433 && has_delay_slot(list[offset - 1].c);
1436 bool should_emulate(const struct opcode *list)
1438 return op_flag_emulate_branch(list->flags) && has_delay_slot(list->c);
1441 static bool op_writes_rd(union code c)
1452 static void lightrec_add_reg_op(struct opcode *op, u8 reg, u32 reg_op)
1454 if (op_writes_rd(op->c) && reg == op->r.rd)
1455 op->flags |= LIGHTREC_REG_RD(reg_op);
1456 else if (op->i.rs == reg)
1457 op->flags |= LIGHTREC_REG_RS(reg_op);
1458 else if (op->i.rt == reg)
1459 op->flags |= LIGHTREC_REG_RT(reg_op);
1461 pr_debug("Cannot add unload/clean/discard flag: "
1462 "opcode does not touch register %s!\n",
1463 lightrec_reg_name(reg));
1466 static void lightrec_add_unload(struct opcode *op, u8 reg)
1468 lightrec_add_reg_op(op, reg, LIGHTREC_REG_UNLOAD);
1471 static void lightrec_add_discard(struct opcode *op, u8 reg)
1473 lightrec_add_reg_op(op, reg, LIGHTREC_REG_DISCARD);
1476 static void lightrec_add_clean(struct opcode *op, u8 reg)
1478 lightrec_add_reg_op(op, reg, LIGHTREC_REG_CLEAN);
1482 lightrec_early_unload_sync(struct opcode *list, s16 *last_r, s16 *last_w)
1487 for (reg = 0; reg < 34; reg++) {
1488 offset = s16_max(last_w[reg], last_r[reg]);
1491 lightrec_add_unload(&list[offset], reg);
1494 memset(last_r, 0xff, sizeof(*last_r) * 34);
1495 memset(last_w, 0xff, sizeof(*last_w) * 34);
1498 static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1502 s16 last_r[34], last_w[34], last_sync = 0, next_sync = 0;
1503 u64 mask_r, mask_w, dirty = 0, loaded = 0;
1504 u8 reg, load_delay_reg = 0;
1506 memset(last_r, 0xff, sizeof(last_r));
1507 memset(last_w, 0xff, sizeof(last_w));
1511 * - the register is dirty, and is read again after a branch opcode
1514 * - the register is dirty or loaded, and is not read again
1515 * - the register is dirty or loaded, and is written again after a branch opcode
1516 * - the next opcode has the SYNC flag set
1519 * - the register is dirty or loaded, and is written again
1522 for (i = 0; i < block->nb_ops; i++) {
1523 op = &block->opcode_list[i];
1525 if (OPT_HANDLE_LOAD_DELAYS && load_delay_reg) {
1526 /* Handle delayed register write from load opcodes in
1528 last_w[load_delay_reg] = i;
1532 if (op_flag_sync(op->flags) || should_emulate(op)) {
1533 /* The next opcode has the SYNC flag set, or is a branch
1534 * that should be emulated: unload all registers. */
1535 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1540 if (next_sync == i) {
1542 pr_debug("Last sync: 0x%x\n", last_sync << 2);
1545 if (has_delay_slot(op->c)) {
1546 next_sync = i + 1 + !op_flag_no_ds(op->flags);
1547 pr_debug("Next sync: 0x%x\n", next_sync << 2);
1550 mask_r = opcode_read_mask(op->c);
1551 mask_w = opcode_write_mask(op->c);
1553 if (op_flag_load_delay(op->flags) && opcode_is_load(op->c)) {
1554 /* If we have a load opcode in a delay slot, its target
1555 * register is actually not written there but at a
1556 * later point, in the dispatcher. Prevent the algorithm
1557 * from discarding its previous value. */
1558 load_delay_reg = op->c.i.rt;
1559 mask_w &= ~BIT(op->c.i.rt);
1562 for (reg = 0; reg < 34; reg++) {
1563 if (mask_r & BIT(reg)) {
1564 if (dirty & BIT(reg) && last_w[reg] < last_sync) {
1565 /* The register is dirty, and is read
1566 * again after a branch: clean it */
1568 lightrec_add_clean(&block->opcode_list[last_w[reg]], reg);
1576 if (mask_w & BIT(reg)) {
1577 if ((dirty & BIT(reg) && last_w[reg] < last_sync) ||
1578 (loaded & BIT(reg) && last_r[reg] < last_sync)) {
1579 /* The register is dirty or loaded, and
1580 * is written again after a branch:
1583 offset = s16_max(last_w[reg], last_r[reg]);
1584 lightrec_add_unload(&block->opcode_list[offset], reg);
1586 loaded &= ~BIT(reg);
1587 } else if (!(mask_r & BIT(reg)) &&
1588 ((dirty & BIT(reg) && last_w[reg] > last_sync) ||
1589 (loaded & BIT(reg) && last_r[reg] > last_sync))) {
1590 /* The register is dirty or loaded, and
1591 * is written again: discard it */
1593 offset = s16_max(last_w[reg], last_r[reg]);
1594 lightrec_add_discard(&block->opcode_list[offset], reg);
1596 loaded &= ~BIT(reg);
1608 /* Unload all registers that are dirty or loaded at the end of block. */
1609 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1614 static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1616 struct opcode *list;
1617 enum psx_map psx_map;
1618 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
1620 u32 val, kunseg_val;
1623 for (i = 0; i < block->nb_ops; i++) {
1624 list = &block->opcode_list[i];
1626 lightrec_consts_propagate(block, i, v);
1628 switch (list->i.op) {
1632 /* Mark all store operations that target $sp or $gp
1633 * as not requiring code invalidation. This is based
1634 * on the heuristic that stores using one of these
1635 * registers as address will never hit a code page. */
1636 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1637 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1638 pr_debug("Flaging opcode 0x%08x as not requiring invalidation\n",
1640 list->flags |= LIGHTREC_NO_INVALIDATE;
1643 /* Detect writes whose destination address is inside the
1644 * current block, using constant propagation. When these
1645 * occur, we mark the blocks as not compilable. */
1646 if (is_known(v, list->i.rs) &&
1647 kunseg(v[list->i.rs].value) >= kunseg(block->pc) &&
1648 kunseg(v[list->i.rs].value) < (kunseg(block->pc) + block->nb_ops * 4)) {
1649 pr_debug("Self-modifying block detected\n");
1650 block_set_flags(block, BLOCK_NEVER_COMPILE);
1651 list->flags |= LIGHTREC_SMC;
1665 if (v[list->i.rs].known | v[list->i.rs].sign) {
1666 psx_map = lightrec_get_constprop_map(state, v,
1670 if (psx_map != PSX_MAP_UNKNOWN && !is_known(v, list->i.rs))
1671 pr_debug("Detected map thanks to bit-level const propagation!\n");
1673 list->flags &= ~LIGHTREC_IO_MASK;
1675 val = v[list->i.rs].value + (s16) list->i.imm;
1676 kunseg_val = kunseg(val);
1678 no_mask = (v[list->i.rs].known & ~v[list->i.rs].value
1679 & 0xe0000000) == 0xe0000000;
1682 case PSX_MAP_KERNEL_USER_RAM:
1684 list->flags |= LIGHTREC_NO_MASK;
1686 case PSX_MAP_MIRROR1:
1687 case PSX_MAP_MIRROR2:
1688 case PSX_MAP_MIRROR3:
1689 pr_debug("Flaging opcode %u as RAM access\n", i);
1690 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_RAM);
1691 if (no_mask && state->mirrors_mapped)
1692 list->flags |= LIGHTREC_NO_MASK;
1695 pr_debug("Flaging opcode %u as BIOS access\n", i);
1696 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_BIOS);
1698 list->flags |= LIGHTREC_NO_MASK;
1700 case PSX_MAP_SCRATCH_PAD:
1701 pr_debug("Flaging opcode %u as scratchpad access\n", i);
1702 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_SCRATCH);
1704 list->flags |= LIGHTREC_NO_MASK;
1706 /* Consider that we're never going to run code from
1707 * the scratchpad. */
1708 list->flags |= LIGHTREC_NO_INVALIDATE;
1710 case PSX_MAP_HW_REGISTERS:
1711 if (state->ops.hw_direct &&
1712 state->ops.hw_direct(kunseg_val,
1713 opcode_is_store(list->c),
1714 opcode_get_io_size(list->c))) {
1715 pr_debug("Flagging opcode %u as direct I/O access\n",
1717 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT_HW);
1720 list->flags |= LIGHTREC_NO_MASK;
1722 pr_debug("Flagging opcode %u as I/O access\n",
1724 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_HW);
1732 if (!LIGHTREC_FLAGS_GET_IO_MODE(list->flags)
1733 && list->i.rs >= 28 && list->i.rs <= 29
1734 && !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1735 /* Assume that all I/O operations that target
1736 * $sp or $gp will always only target a mapped
1737 * memory (RAM, BIOS, scratchpad). */
1738 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT);
1750 static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1751 const struct opcode *last,
1752 u32 mask, bool sync, bool mflo, bool another)
1754 const struct opcode *op, *next = &block->opcode_list[offset];
1756 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1760 for (i = offset; i < block->nb_ops; i++) {
1762 next = &block->opcode_list[i + 1];
1765 /* If any other opcode writes or reads to the register
1766 * we'd use, then we cannot use it anymore. */
1767 mask |= opcode_read_mask(op->c);
1768 mask |= opcode_write_mask(op->c);
1770 if (op_flag_sync(op->flags))
1779 /* TODO: handle backwards branches too */
1780 if (!last && op_flag_local_branch(op->flags) &&
1781 (s16)op->c.i.imm >= 0) {
1782 branch_offset = i + 1 + (s16)op->c.i.imm
1783 - !!op_flag_no_ds(op->flags);
1785 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1786 mask, sync, mflo, false);
1787 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1788 mask, sync, mflo, false);
1789 if (reg > 0 && reg == reg2)
1795 return mflo ? REG_LO : REG_HI;
1797 case OP_META_MULTU2:
1801 case OP_SPECIAL_MULT:
1802 case OP_SPECIAL_MULTU:
1803 case OP_SPECIAL_DIV:
1804 case OP_SPECIAL_DIVU:
1806 case OP_SPECIAL_MTHI:
1810 case OP_SPECIAL_MTLO:
1818 if (!sync && !op_flag_no_ds(op->flags) &&
1819 (next->i.op == OP_SPECIAL) &&
1820 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1821 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1825 case OP_SPECIAL_JALR:
1827 case OP_SPECIAL_MFHI:
1831 /* Must use REG_HI if there is another MFHI target*/
1832 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1833 0, sync, mflo, true);
1834 if (reg2 > 0 && reg2 != REG_HI)
1837 if (!sync && !(old_mask & BIT(op->r.rd)))
1843 case OP_SPECIAL_MFLO:
1847 /* Must use REG_LO if there is another MFLO target*/
1848 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1849 0, sync, mflo, true);
1850 if (reg2 > 0 && reg2 != REG_LO)
1853 if (!sync && !(old_mask & BIT(op->r.rd)))
1872 static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1878 /* This function will remove the following MFLO/MFHI. It must be called
1879 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1881 for (i = offset; i < last; i++) {
1882 struct opcode *op = &block->opcode_list[i];
1890 /* TODO: handle backwards branches too */
1891 if (op_flag_local_branch(op->flags) && (s16)op->c.i.imm >= 0) {
1892 branch_offset = i + 1 + (s16)op->c.i.imm
1893 - !!op_flag_no_ds(op->flags);
1895 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1896 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1901 if (lo && op->r.op == OP_SPECIAL_MFLO) {
1902 pr_debug("Removing MFLO opcode at offset 0x%x\n",
1906 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
1907 pr_debug("Removing MFHI opcode at offset 0x%x\n",
1920 static bool lightrec_always_skip_div_check(void)
1929 static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
1931 struct opcode *list = NULL;
1932 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
1936 for (i = 0; i < block->nb_ops - 1; i++) {
1937 list = &block->opcode_list[i];
1939 lightrec_consts_propagate(block, i, v);
1941 switch (list->i.op) {
1943 switch (list->r.op) {
1944 case OP_SPECIAL_DIV:
1945 case OP_SPECIAL_DIVU:
1946 /* If we are dividing by a non-zero constant, don't
1947 * emit the div-by-zero check. */
1948 if (lightrec_always_skip_div_check() ||
1949 (v[list->r.rt].known & v[list->r.rt].value)) {
1950 list->flags |= LIGHTREC_NO_DIV_CHECK;
1953 case OP_SPECIAL_MULT:
1954 case OP_SPECIAL_MULTU:
1961 case OP_META_MULTU2:
1967 /* Don't support opcodes in delay slots */
1968 if (is_delay_slot(block->opcode_list, i) ||
1969 op_flag_no_ds(list->flags)) {
1973 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
1975 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1976 " not writing LO\n", i << 2);
1977 list->flags |= LIGHTREC_NO_LO;
1980 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
1982 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1983 " not writing HI\n", i << 2);
1984 list->flags |= LIGHTREC_NO_HI;
1987 if (!reg_lo && !reg_hi) {
1988 pr_debug("Both LO/HI unused in this block, they will "
1989 "probably be used in parent block - removing "
1991 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
1994 if (reg_lo > 0 && reg_lo != REG_LO) {
1995 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
1996 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
1998 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
1999 list->r.rd = reg_lo;
2004 if (reg_hi > 0 && reg_hi != REG_HI) {
2005 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
2006 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
2008 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
2009 list->r.imm = reg_hi;
2018 static bool remove_div_sequence(struct block *block, unsigned int offset)
2021 unsigned int i, found = 0;
2024 * Scan for the zero-checking sequence that GCC automatically introduced
2025 * after most DIV/DIVU opcodes. This sequence checks the value of the
2026 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
2027 * handler to crash the PS1.
2029 * For DIV opcodes, this sequence additionally checks that the signed
2030 * operation does not overflow.
2032 * With the assumption that the games never crashed the PS1, we can
2033 * therefore assume that the games never divided by zero or overflowed,
2034 * and these sequences can be removed.
2037 for (i = offset; i < block->nb_ops; i++) {
2038 op = &block->opcode_list[i];
2041 if (op->i.op == OP_SPECIAL &&
2042 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
2045 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
2046 /* BNE ???, zero, +8 */
2051 } else if (found == 1 && !op->opcode) {
2054 } else if (found == 2 && op->opcode == 0x0007000d) {
2057 } else if (found == 3 && op->opcode == 0x2401ffff) {
2060 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
2061 /* BNE ???, at, +16 */
2063 } else if (found == 5 && op->opcode == 0x3c018000) {
2064 /* LUI at, 0x8000 */
2066 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
2067 /* BNE ???, at, +16 */
2069 } else if (found == 7 && !op->opcode) {
2072 } else if (found == 8 && op->opcode == 0x0006000d) {
2085 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
2086 found == 9 ? "" : "U", offset << 2);
2088 for (i = 0; i < found; i++)
2089 block->opcode_list[offset + i].opcode = 0;
2097 static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
2098 struct block *block)
2103 for (i = 0; i < block->nb_ops; i++) {
2104 op = &block->opcode_list[i];
2106 if (op->i.op == OP_SPECIAL &&
2107 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
2108 remove_div_sequence(block, i + 1))
2109 op->flags |= LIGHTREC_NO_DIV_CHECK;
2115 static const u32 memset_code[] = {
2116 0x10a00006, // beqz a1, 2f
2117 0x24a2ffff, // addiu v0,a1,-1
2118 0x2403ffff, // li v1,-1
2119 0xac800000, // 1: sw zero,0(a0)
2120 0x2442ffff, // addiu v0,v0,-1
2121 0x1443fffd, // bne v0,v1, 1b
2122 0x24840004, // addiu a0,a0,4
2123 0x03e00008, // 2: jr ra
2127 static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
2132 for (i = 0; i < block->nb_ops; i++) {
2133 c = block->opcode_list[i].c;
2135 if (c.opcode != memset_code[i])
2138 if (i == ARRAY_SIZE(memset_code) - 1) {
2140 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
2141 block_set_flags(block,
2142 BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE);
2144 /* Return non-zero to skip other optimizers. */
2152 static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
2153 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
2154 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
2155 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
2156 IF_OPT(OPT_HANDLE_LOAD_DELAYS, &lightrec_handle_load_delays),
2157 IF_OPT(OPT_HANDLE_LOAD_DELAYS, &lightrec_swap_load_delays),
2158 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_branches),
2159 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
2160 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
2161 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
2162 IF_OPT(OPT_FLAG_IO, &lightrec_flag_io),
2163 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
2164 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
2167 int lightrec_optimize(struct lightrec_state *state, struct block *block)
2172 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
2173 if (lightrec_optimizers[i]) {
2174 ret = (*lightrec_optimizers[i])(state, block);