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);
123 static u64 mult_div_write_mask(union code op)
127 if (!OPT_FLAG_MULT_DIV)
128 return BIT(REG_LO) | BIT(REG_HI);
131 flags = BIT(op.r.rd);
135 flags |= BIT(op.r.imm);
137 flags |= BIT(REG_HI);
142 static u64 opcode_write_mask(union code op)
147 return mult_div_write_mask(op);
151 case OP_SPECIAL_SYSCALL:
152 case OP_SPECIAL_BREAK:
154 case OP_SPECIAL_MULT:
155 case OP_SPECIAL_MULTU:
157 case OP_SPECIAL_DIVU:
158 return mult_div_write_mask(op);
159 case OP_SPECIAL_MTHI:
161 case OP_SPECIAL_MTLO:
199 if (op.r.op == OP_CP2_BASIC) {
201 case OP_CP2_BASIC_MFC2:
202 case OP_CP2_BASIC_CFC2:
211 case OP_REGIMM_BLTZAL:
212 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 static bool opcode_is_load(union code op)
359 static bool opcode_is_store(union code op)
374 static u8 opcode_get_io_size(union code op)
390 bool opcode_is_io(union code op)
392 return opcode_is_load(op) || opcode_is_store(op);
396 static bool is_nop(union code op)
398 if (opcode_writes_register(op, 0)) {
401 return op.r.rs != OP_CP0_MFC0;
419 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
421 case OP_SPECIAL_ADDU:
422 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
423 (op.r.rd == op.r.rs && op.r.rt == 0);
425 case OP_SPECIAL_SUBU:
426 return op.r.rd == op.r.rs && op.r.rt == 0;
428 if (op.r.rd == op.r.rt)
429 return op.r.rd == op.r.rs || op.r.rs == 0;
431 return (op.r.rd == op.r.rs) && op.r.rt == 0;
435 return op.r.rd == op.r.rt && op.r.imm == 0;
436 case OP_SPECIAL_MFHI:
437 case OP_SPECIAL_MFLO:
445 return op.i.rt == op.i.rs && op.i.imm == 0;
447 return (op.i.rs == 0 || op.i.imm == 1);
449 return (op.i.op == OP_REGIMM_BLTZ ||
450 op.i.op == OP_REGIMM_BLTZAL) &&
451 (op.i.rs == 0 || op.i.imm == 1);
453 return (op.i.rs == op.i.rt || op.i.imm == 1);
459 bool load_in_delay_slot(union code op)
473 if (op.r.op == OP_CP2_BASIC) {
475 case OP_CP2_BASIC_MFC2:
476 case OP_CP2_BASIC_CFC2:
499 static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset,
500 struct constprop_data *v)
502 struct opcode *ldop = NULL, *curr = &list[offset], *next;
503 struct opcode *to_change, *to_nop;
506 if (curr->r.imm != 24 && curr->r.imm != 16)
509 if (is_delay_slot(list, offset))
512 idx = find_next_reader(list, offset + 1, curr->r.rd);
518 if (next->i.op != OP_SPECIAL || next->r.op != OP_SPECIAL_SRA ||
519 next->r.imm != curr->r.imm || next->r.rt != curr->r.rd)
522 if (curr->r.rd != curr->r.rt && next->r.rd != next->r.rt) {
527 if (!reg_is_dead(list, idx, curr->r.rd) ||
528 reg_is_read_or_written(list, offset, idx, next->r.rd))
531 /* If rY is dead after the SRL, and rZ is not used after the SLL,
532 * we can change rY to rZ */
534 pr_debug("Detected SLL/SRA with middle temp register\n");
535 curr->r.rd = next->r.rd;
536 next->r.rt = curr->r.rd;
539 /* We got a SLL/SRA combo. If imm #16, that's a cast to s16.
540 * If imm #24 that's a cast to s8.
542 * First of all, make sure that the target register of the SLL is not
543 * read after the SRA. */
545 if (curr->r.rd == curr->r.rt) {
552 /* rX is used after the SRA - we cannot convert it. */
553 if (curr->r.rd != next->r.rd && !reg_is_dead(list, idx, curr->r.rd))
563 idx2 = find_prev_writer(list, offset, curr->r.rt);
565 /* Note that PSX games sometimes do casts after
566 * a LHU or LBU; in this case we can change the
567 * load opcode to a LH or LB, and the cast can
568 * be changed to a MOV or a simple NOP. */
572 if (next->r.rd != ldop->i.rt &&
573 !reg_is_dead(list, idx, ldop->i.rt))
575 else if (curr->r.imm == 16 && ldop->i.op == OP_LHU)
577 else if (curr->r.imm == 24 && ldop->i.op == OP_LBU)
583 if (next->r.rd == ldop->i.rt) {
584 to_change->opcode = 0;
585 } else if (reg_is_dead(list, idx, ldop->i.rt) &&
586 !reg_is_read_or_written(list, idx2 + 1, idx, next->r.rd)) {
587 /* The target register of the SRA is dead after the
588 * LBU/LHU; we can change the target register of the
589 * LBU/LHU to the one of the SRA. */
590 v[ldop->i.rt].known = 0;
591 v[ldop->i.rt].sign = 0;
592 ldop->i.rt = next->r.rd;
593 to_change->opcode = 0;
595 to_change->i.op = OP_META_MOV;
596 to_change->r.rd = next->r.rd;
597 to_change->r.rs = ldop->i.rt;
600 if (to_nop->r.imm == 24)
601 pr_debug("Convert LBU+SLL+SRA to LB\n");
603 pr_debug("Convert LHU+SLL+SRA to LH\n");
605 v[ldop->i.rt].known = 0;
606 v[ldop->i.rt].sign = 0xffffff80 << 24 - curr->r.imm;
611 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
612 curr->r.imm, curr->r.imm == 24 ? 'C' : 'S');
614 if (to_change == curr) {
615 to_change->i.rs = curr->r.rt;
616 to_change->i.rt = next->r.rd;
618 to_change->i.rt = next->r.rd;
619 to_change->i.rs = curr->r.rt;
622 if (to_nop->r.imm == 24)
623 to_change->i.op = OP_META_EXTC;
625 to_change->i.op = OP_META_EXTS;
632 lightrec_remove_useless_lui(struct block *block, unsigned int offset,
633 const struct constprop_data *v)
635 struct opcode *list = block->opcode_list,
636 *op = &block->opcode_list[offset];
639 if (!op_flag_sync(op->flags) && is_known(v, op->i.rt) &&
640 v[op->i.rt].value == op->i.imm << 16) {
641 pr_debug("Converting duplicated LUI to NOP\n");
646 if (op->i.imm != 0 || op->i.rt == 0 || offset == block->nb_ops - 1)
649 reader = find_next_reader(list, offset + 1, op->i.rt);
653 if (opcode_writes_register(list[reader].c, op->i.rt) ||
654 reg_is_dead(list, reader, op->i.rt)) {
655 pr_debug("Removing useless LUI 0x0\n");
657 if (list[reader].i.rs == op->i.rt)
658 list[reader].i.rs = 0;
659 if (list[reader].i.op == OP_SPECIAL &&
660 list[reader].i.rt == op->i.rt)
661 list[reader].i.rt = 0;
666 static void lightrec_modify_lui(struct block *block, unsigned int offset)
668 union code c, *lui = &block->opcode_list[offset].c;
669 bool stop = false, stop_next = false;
672 for (i = offset + 1; !stop && i < block->nb_ops; i++) {
673 c = block->opcode_list[i].c;
676 if ((opcode_is_store(c) && c.i.rt == lui->i.rt)
677 || (!opcode_is_load(c) && opcode_reads_register(c, lui->i.rt)))
680 if (opcode_writes_register(c, lui->i.rt)) {
681 pr_debug("Convert LUI at offset 0x%x to kuseg\n",
683 lui->i.imm = kunseg(lui->i.imm << 16) >> 16;
687 if (has_delay_slot(c))
692 static int lightrec_transform_branches(struct lightrec_state *state,
699 for (i = 0; i < block->nb_ops; i++) {
700 op = &block->opcode_list[i];
704 /* Transform J opcode into BEQ $zero, $zero if possible. */
705 offset = (s32)((block->pc & 0xf0000000) >> 2 | op->j.imm)
706 - (s32)(block->pc >> 2) - (s32)i - 1;
708 if (offset == (s16)offset) {
709 pr_debug("Transform J into BEQ $zero, $zero\n");
725 static inline bool is_power_of_two(u32 value)
727 return popcount32(value) == 1;
730 static void lightrec_patch_known_zero(struct opcode *op,
731 const struct constprop_data *v)
737 case OP_SPECIAL_JALR:
738 case OP_SPECIAL_MTHI:
739 case OP_SPECIAL_MTLO:
740 if (is_known_zero(v, op->r.rs))
744 if (is_known_zero(v, op->r.rs))
750 if (is_known_zero(v, op->r.rt))
753 case OP_SPECIAL_SYSCALL:
754 case OP_SPECIAL_BREAK:
755 case OP_SPECIAL_MFHI:
756 case OP_SPECIAL_MFLO:
764 if (is_known_zero(v, op->r.rt))
772 if (op->r.op == OP_CP2_BASIC) {
774 case OP_CP2_BASIC_MTC2:
775 case OP_CP2_BASIC_CTC2:
776 if (is_known_zero(v, op->r.rt))
786 if (is_known_zero(v, op->i.rt))
804 if (is_known_zero(v, op->i.rs))
812 if (is_known_zero(v, op->i.rt))
824 if (is_known(v, op->i.rs)
825 && kunseg(v[op->i.rs].value) == 0)
833 static void lightrec_reset_syncs(struct block *block)
835 struct opcode *op, *list = block->opcode_list;
839 for (i = 0; i < block->nb_ops; i++)
840 list[i].flags &= ~LIGHTREC_SYNC;
842 for (i = 0; i < block->nb_ops; i++) {
845 if (op_flag_local_branch(op->flags) && has_delay_slot(op->c)) {
846 offset = i + 1 + (s16)op->i.imm;
847 list[offset].flags |= LIGHTREC_SYNC;
852 static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
854 struct opcode *op, *list = block->opcode_list;
855 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
860 for (i = 0; i < block->nb_ops; i++) {
863 lightrec_consts_propagate(list, i, v);
865 lightrec_patch_known_zero(op, v);
867 /* Transform all opcodes detected as useless to real NOPs
868 * (0x0: SLL r0, r0, #0) */
869 if (op->opcode != 0 && is_nop(op->c)) {
870 pr_debug("Converting useless opcode 0x%08x to NOP\n",
880 if (op->i.rs == op->i.rt ||
881 (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
882 v[op->i.rs].value == v[op->i.rt].value)) {
883 if (op->i.rs != op->i.rt)
884 pr_debug("Found always-taken BEQ\n");
888 } else if (v[op->i.rs].known & v[op->i.rt].known &
889 (v[op->i.rs].value ^ v[op->i.rt].value)) {
890 pr_debug("Found never-taken BEQ\n");
892 local = op_flag_local_branch(op->flags);
897 lightrec_reset_syncs(block);
898 } else if (op->i.rs == 0) {
905 if (v[op->i.rs].known & v[op->i.rt].known &
906 (v[op->i.rs].value ^ v[op->i.rt].value)) {
907 pr_debug("Found always-taken BNE\n");
912 } else if (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
913 v[op->i.rs].value == v[op->i.rt].value) {
914 pr_debug("Found never-taken BNE\n");
916 local = op_flag_local_branch(op->flags);
921 lightrec_reset_syncs(block);
922 } else if (op->i.rs == 0) {
929 if (v[op->i.rs].known & BIT(31) &&
930 v[op->i.rs].value & BIT(31)) {
931 pr_debug("Found always-taken BLEZ\n");
940 if (v[op->i.rs].known & BIT(31) &&
941 v[op->i.rs].value & BIT(31)) {
942 pr_debug("Found never-taken BGTZ\n");
944 local = op_flag_local_branch(op->flags);
949 lightrec_reset_syncs(block);
954 if (i == 0 || !has_delay_slot(list[i - 1].c))
955 lightrec_modify_lui(block, i);
956 lightrec_remove_useless_lui(block, i, v);
959 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
960 * with register $zero to the MOV meta-opcode */
964 if (op->i.imm == 0) {
965 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
966 op->i.op = OP_META_MOV;
971 if (bits_are_known_zero(v, op->i.rs, ~op->i.imm)) {
972 pr_debug("Found useless ANDI 0x%x\n", op->i.imm);
974 if (op->i.rs == op->i.rt) {
977 op->i.op = OP_META_MOV;
986 if (!(v[op->r.rs].known & BIT(31)))
989 if (!!(v[op->r.rs].value & BIT(31))
990 ^ (op->r.rt == OP_REGIMM_BGEZ)) {
991 pr_debug("Found always-taken BLTZ/BGEZ\n");
996 pr_debug("Found never-taken BLTZ/BGEZ\n");
998 local = op_flag_local_branch(op->flags);
1003 lightrec_reset_syncs(block);
1006 case OP_REGIMM_BLTZAL:
1007 case OP_REGIMM_BGEZAL:
1008 /* TODO: Detect always-taken and replace with JAL */
1014 case OP_SPECIAL_SRAV:
1015 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1018 pr_debug("Convert SRAV to SRA\n");
1019 op->r.imm = v[op->r.rs].value & 0x1f;
1020 op->r.op = OP_SPECIAL_SRA;
1023 case OP_SPECIAL_SRA:
1024 if (op->r.imm == 0) {
1025 pr_debug("Convert SRA #0 to MOV\n");
1026 op->i.op = OP_META_MOV;
1027 op->r.rs = op->r.rt;
1032 case OP_SPECIAL_SLLV:
1033 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1036 pr_debug("Convert SLLV to SLL\n");
1037 op->r.imm = v[op->r.rs].value & 0x1f;
1038 op->r.op = OP_SPECIAL_SLL;
1041 case OP_SPECIAL_SLL:
1042 if (op->r.imm == 0) {
1043 pr_debug("Convert SLL #0 to MOV\n");
1044 op->i.op = OP_META_MOV;
1045 op->r.rs = op->r.rt;
1048 lightrec_optimize_sll_sra(block->opcode_list, i, v);
1051 case OP_SPECIAL_SRLV:
1052 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1055 pr_debug("Convert SRLV to SRL\n");
1056 op->r.imm = v[op->r.rs].value & 0x1f;
1057 op->r.op = OP_SPECIAL_SRL;
1060 case OP_SPECIAL_SRL:
1061 if (op->r.imm == 0) {
1062 pr_debug("Convert SRL #0 to MOV\n");
1063 op->i.op = OP_META_MOV;
1064 op->r.rs = op->r.rt;
1068 case OP_SPECIAL_MULT:
1069 case OP_SPECIAL_MULTU:
1070 if (is_known(v, op->r.rs) &&
1071 is_power_of_two(v[op->r.rs].value)) {
1073 op->c.i.rs = op->c.i.rt;
1075 } else if (!is_known(v, op->r.rt) ||
1076 !is_power_of_two(v[op->r.rt].value)) {
1080 pr_debug("Multiply by power-of-two: %u\n",
1083 if (op->r.op == OP_SPECIAL_MULT)
1084 op->i.op = OP_META_MULT2;
1086 op->i.op = OP_META_MULTU2;
1088 op->r.op = ctz32(v[op->r.rt].value);
1091 case OP_SPECIAL_ADD:
1092 case OP_SPECIAL_ADDU:
1093 if (op->r.rs == 0) {
1094 pr_debug("Convert OR/ADD $zero to MOV\n");
1095 op->i.op = OP_META_MOV;
1096 op->r.rs = op->r.rt;
1099 case OP_SPECIAL_SUB:
1100 case OP_SPECIAL_SUBU:
1101 if (op->r.rt == 0) {
1102 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
1103 op->i.op = OP_META_MOV;
1118 static bool lightrec_can_switch_delay_slot(union code op, union code next_op)
1123 case OP_SPECIAL_JALR:
1124 if (opcode_reads_register(next_op, op.r.rd) ||
1125 opcode_writes_register(next_op, op.r.rd))
1129 if (opcode_writes_register(next_op, op.r.rs))
1139 if (opcode_reads_register(next_op, 31) ||
1140 opcode_writes_register(next_op, 31))
1146 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
1151 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1156 case OP_REGIMM_BLTZAL:
1157 case OP_REGIMM_BGEZAL:
1158 if (opcode_reads_register(next_op, 31) ||
1159 opcode_writes_register(next_op, 31))
1162 case OP_REGIMM_BLTZ:
1163 case OP_REGIMM_BGEZ:
1164 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1176 static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
1178 struct opcode *list, *next = &block->opcode_list[0];
1180 union code op, next_op;
1183 for (i = 0; i < block->nb_ops - 1; i++) {
1185 next = &block->opcode_list[i + 1];
1189 if (!has_delay_slot(op) || op_flag_no_ds(list->flags) ||
1190 op_flag_emulate_branch(list->flags) ||
1191 op.opcode == 0 || next_op.opcode == 0)
1194 if (is_delay_slot(block->opcode_list, i))
1197 if (op_flag_sync(next->flags))
1200 if (!lightrec_can_switch_delay_slot(list->c, next_op))
1203 pr_debug("Swap branch and delay slot opcodes "
1204 "at offsets 0x%x / 0x%x\n",
1205 i << 2, (i + 1) << 2);
1207 flags = next->flags | (list->flags & LIGHTREC_SYNC);
1210 next->flags = (list->flags | LIGHTREC_NO_DS) & ~LIGHTREC_SYNC;
1211 list->flags = flags | LIGHTREC_NO_DS;
1217 static int shrink_opcode_list(struct lightrec_state *state, struct block *block, u16 new_size)
1219 struct opcode_list *list, *old_list;
1221 if (new_size >= block->nb_ops) {
1222 pr_err("Invalid shrink size (%u vs %u)\n",
1223 new_size, block->nb_ops);
1227 list = lightrec_malloc(state, MEM_FOR_IR,
1228 sizeof(*list) + sizeof(struct opcode) * new_size);
1230 pr_err("Unable to allocate memory\n");
1234 old_list = container_of(block->opcode_list, struct opcode_list, ops);
1235 memcpy(list->ops, old_list->ops, sizeof(struct opcode) * new_size);
1237 lightrec_free_opcode_list(state, block->opcode_list);
1238 list->nb_ops = new_size;
1239 block->nb_ops = new_size;
1240 block->opcode_list = list->ops;
1242 pr_debug("Shrunk opcode list of block PC 0x%08x to %u opcodes\n",
1243 block->pc, new_size);
1248 static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1249 struct block *block)
1251 struct opcode *op, *list = block->opcode_list, *next = &list[0];
1256 for (i = 0; i < block->nb_ops - 1; i++) {
1258 next = &list[i + 1];
1260 if (!has_delay_slot(op->c) ||
1261 (!load_in_delay_slot(next->c) &&
1262 !has_delay_slot(next->c) &&
1263 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1266 if (op->c.opcode == next->c.opcode) {
1267 /* The delay slot is the exact same opcode as the branch
1268 * opcode: this is effectively a NOP */
1273 offset = i + 1 + (s16)op->i.imm;
1274 if (load_in_delay_slot(next->c) &&
1275 (offset >= 0 && offset < block->nb_ops) &&
1276 !opcode_reads_register(list[offset].c, next->c.i.rt)) {
1277 /* The 'impossible' branch is a local branch - we can
1278 * verify here that the first opcode of the target does
1279 * not use the target register of the delay slot */
1281 pr_debug("Branch at offset 0x%x has load delay slot, "
1282 "but is local and dest opcode does not read "
1283 "dest register\n", i << 2);
1287 op->flags |= LIGHTREC_EMULATE_BRANCH;
1290 pr_debug("First opcode of block PC 0x%08x is an impossible branch\n",
1293 /* If the first opcode is an 'impossible' branch, we
1294 * only keep the first two opcodes of the block (the
1295 * branch itself + its delay slot) */
1296 if (block->nb_ops > 2)
1297 ret = shrink_opcode_list(state, block, 2);
1305 static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1307 struct opcode *list;
1311 for (i = 0; i < block->nb_ops; i++) {
1312 list = &block->opcode_list[i];
1314 if (should_emulate(list))
1317 switch (list->i.op) {
1323 offset = i + 1 + (s16)list->i.imm;
1324 if (offset >= 0 && offset < block->nb_ops)
1331 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1333 if (should_emulate(&block->opcode_list[offset])) {
1334 pr_debug("Branch target must be emulated - skip\n");
1338 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1339 pr_debug("Branch target is a delay slot - skip\n");
1343 list->flags |= LIGHTREC_LOCAL_BRANCH;
1346 lightrec_reset_syncs(block);
1351 bool has_delay_slot(union code op)
1357 case OP_SPECIAL_JALR:
1375 bool is_delay_slot(const struct opcode *list, unsigned int offset)
1378 && !op_flag_no_ds(list[offset - 1].flags)
1379 && has_delay_slot(list[offset - 1].c);
1382 bool should_emulate(const struct opcode *list)
1384 return op_flag_emulate_branch(list->flags) && has_delay_slot(list->c);
1387 static bool op_writes_rd(union code c)
1398 static void lightrec_add_reg_op(struct opcode *op, u8 reg, u32 reg_op)
1400 if (op_writes_rd(op->c) && reg == op->r.rd)
1401 op->flags |= LIGHTREC_REG_RD(reg_op);
1402 else if (op->i.rs == reg)
1403 op->flags |= LIGHTREC_REG_RS(reg_op);
1404 else if (op->i.rt == reg)
1405 op->flags |= LIGHTREC_REG_RT(reg_op);
1407 pr_debug("Cannot add unload/clean/discard flag: "
1408 "opcode does not touch register %s!\n",
1409 lightrec_reg_name(reg));
1412 static void lightrec_add_unload(struct opcode *op, u8 reg)
1414 lightrec_add_reg_op(op, reg, LIGHTREC_REG_UNLOAD);
1417 static void lightrec_add_discard(struct opcode *op, u8 reg)
1419 lightrec_add_reg_op(op, reg, LIGHTREC_REG_DISCARD);
1422 static void lightrec_add_clean(struct opcode *op, u8 reg)
1424 lightrec_add_reg_op(op, reg, LIGHTREC_REG_CLEAN);
1428 lightrec_early_unload_sync(struct opcode *list, s16 *last_r, s16 *last_w)
1433 for (reg = 0; reg < 34; reg++) {
1434 offset = s16_max(last_w[reg], last_r[reg]);
1437 lightrec_add_unload(&list[offset], reg);
1440 memset(last_r, 0xff, sizeof(*last_r) * 34);
1441 memset(last_w, 0xff, sizeof(*last_w) * 34);
1444 static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1448 s16 last_r[34], last_w[34], last_sync = 0, next_sync = 0;
1449 u64 mask_r, mask_w, dirty = 0, loaded = 0;
1452 memset(last_r, 0xff, sizeof(last_r));
1453 memset(last_w, 0xff, sizeof(last_w));
1457 * - the register is dirty, and is read again after a branch opcode
1460 * - the register is dirty or loaded, and is not read again
1461 * - the register is dirty or loaded, and is written again after a branch opcode
1462 * - the next opcode has the SYNC flag set
1465 * - the register is dirty or loaded, and is written again
1468 for (i = 0; i < block->nb_ops; i++) {
1469 op = &block->opcode_list[i];
1471 if (op_flag_sync(op->flags) || should_emulate(op)) {
1472 /* The next opcode has the SYNC flag set, or is a branch
1473 * that should be emulated: unload all registers. */
1474 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1479 if (next_sync == i) {
1481 pr_debug("Last sync: 0x%x\n", last_sync << 2);
1484 if (has_delay_slot(op->c)) {
1485 next_sync = i + 1 + !op_flag_no_ds(op->flags);
1486 pr_debug("Next sync: 0x%x\n", next_sync << 2);
1489 mask_r = opcode_read_mask(op->c);
1490 mask_w = opcode_write_mask(op->c);
1492 for (reg = 0; reg < 34; reg++) {
1493 if (mask_r & BIT(reg)) {
1494 if (dirty & BIT(reg) && last_w[reg] < last_sync) {
1495 /* The register is dirty, and is read
1496 * again after a branch: clean it */
1498 lightrec_add_clean(&block->opcode_list[last_w[reg]], reg);
1506 if (mask_w & BIT(reg)) {
1507 if ((dirty & BIT(reg) && last_w[reg] < last_sync) ||
1508 (loaded & BIT(reg) && last_r[reg] < last_sync)) {
1509 /* The register is dirty or loaded, and
1510 * is written again after a branch:
1513 offset = s16_max(last_w[reg], last_r[reg]);
1514 lightrec_add_unload(&block->opcode_list[offset], reg);
1516 loaded &= ~BIT(reg);
1517 } else if (!(mask_r & BIT(reg)) &&
1518 ((dirty & BIT(reg) && last_w[reg] > last_sync) ||
1519 (loaded & BIT(reg) && last_r[reg] > last_sync))) {
1520 /* The register is dirty or loaded, and
1521 * is written again: discard it */
1523 offset = s16_max(last_w[reg], last_r[reg]);
1524 lightrec_add_discard(&block->opcode_list[offset], reg);
1526 loaded &= ~BIT(reg);
1538 /* Unload all registers that are dirty or loaded at the end of block. */
1539 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1544 static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1546 struct opcode *list;
1547 enum psx_map psx_map;
1548 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
1550 u32 val, kunseg_val;
1553 for (i = 0; i < block->nb_ops; i++) {
1554 list = &block->opcode_list[i];
1556 lightrec_consts_propagate(block->opcode_list, i, v);
1558 switch (list->i.op) {
1562 if (OPT_FLAG_STORES) {
1563 /* Mark all store operations that target $sp or $gp
1564 * as not requiring code invalidation. This is based
1565 * on the heuristic that stores using one of these
1566 * registers as address will never hit a code page. */
1567 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1568 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1569 pr_debug("Flaging opcode 0x%08x as not "
1570 "requiring invalidation\n",
1572 list->flags |= LIGHTREC_NO_INVALIDATE;
1573 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT);
1576 /* Detect writes whose destination address is inside the
1577 * current block, using constant propagation. When these
1578 * occur, we mark the blocks as not compilable. */
1579 if (is_known(v, list->i.rs) &&
1580 kunseg(v[list->i.rs].value) >= kunseg(block->pc) &&
1581 kunseg(v[list->i.rs].value) < (kunseg(block->pc) +
1582 block->nb_ops * 4)) {
1583 pr_debug("Self-modifying block detected\n");
1584 block_set_flags(block, BLOCK_NEVER_COMPILE);
1585 list->flags |= LIGHTREC_SMC;
1601 (v[list->i.rs].known | v[list->i.rs].sign)) {
1602 psx_map = lightrec_get_constprop_map(state, v,
1606 if (psx_map != PSX_MAP_UNKNOWN && !is_known(v, list->i.rs))
1607 pr_debug("Detected map thanks to bit-level const propagation!\n");
1609 list->flags &= ~LIGHTREC_IO_MASK;
1611 val = v[list->i.rs].value + (s16) list->i.imm;
1612 kunseg_val = kunseg(val);
1614 no_mask = (v[list->i.rs].known & ~v[list->i.rs].value
1615 & 0xe0000000) == 0xe0000000;
1618 case PSX_MAP_KERNEL_USER_RAM:
1620 list->flags |= LIGHTREC_NO_MASK;
1622 case PSX_MAP_MIRROR1:
1623 case PSX_MAP_MIRROR2:
1624 case PSX_MAP_MIRROR3:
1625 pr_debug("Flaging opcode %u as RAM access\n", i);
1626 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_RAM);
1627 if (no_mask && state->mirrors_mapped)
1628 list->flags |= LIGHTREC_NO_MASK;
1631 pr_debug("Flaging opcode %u as BIOS access\n", i);
1632 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_BIOS);
1634 list->flags |= LIGHTREC_NO_MASK;
1636 case PSX_MAP_SCRATCH_PAD:
1637 pr_debug("Flaging opcode %u as scratchpad access\n", i);
1638 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_SCRATCH);
1640 list->flags |= LIGHTREC_NO_MASK;
1642 /* Consider that we're never going to run code from
1643 * the scratchpad. */
1644 list->flags |= LIGHTREC_NO_INVALIDATE;
1646 case PSX_MAP_HW_REGISTERS:
1647 if (state->ops.hw_direct &&
1648 state->ops.hw_direct(kunseg_val,
1649 opcode_is_store(list->c),
1650 opcode_get_io_size(list->c))) {
1651 pr_debug("Flagging opcode %u as direct I/O access\n",
1653 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT_HW);
1656 list->flags |= LIGHTREC_NO_MASK;
1658 pr_debug("Flagging opcode %u as I/O access\n",
1660 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_HW);
1676 static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1677 const struct opcode *last,
1678 u32 mask, bool sync, bool mflo, bool another)
1680 const struct opcode *op, *next = &block->opcode_list[offset];
1682 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1686 for (i = offset; i < block->nb_ops; i++) {
1688 next = &block->opcode_list[i + 1];
1691 /* If any other opcode writes or reads to the register
1692 * we'd use, then we cannot use it anymore. */
1693 mask |= opcode_read_mask(op->c);
1694 mask |= opcode_write_mask(op->c);
1696 if (op_flag_sync(op->flags))
1705 /* TODO: handle backwards branches too */
1706 if (!last && op_flag_local_branch(op->flags) &&
1707 (s16)op->c.i.imm >= 0) {
1708 branch_offset = i + 1 + (s16)op->c.i.imm
1709 - !!op_flag_no_ds(op->flags);
1711 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1712 mask, sync, mflo, false);
1713 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1714 mask, sync, mflo, false);
1715 if (reg > 0 && reg == reg2)
1721 return mflo ? REG_LO : REG_HI;
1723 case OP_META_MULTU2:
1727 case OP_SPECIAL_MULT:
1728 case OP_SPECIAL_MULTU:
1729 case OP_SPECIAL_DIV:
1730 case OP_SPECIAL_DIVU:
1732 case OP_SPECIAL_MTHI:
1736 case OP_SPECIAL_MTLO:
1744 if (!sync && !op_flag_no_ds(op->flags) &&
1745 (next->i.op == OP_SPECIAL) &&
1746 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1747 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1751 case OP_SPECIAL_JALR:
1753 case OP_SPECIAL_MFHI:
1757 /* Must use REG_HI if there is another MFHI target*/
1758 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1759 0, sync, mflo, true);
1760 if (reg2 > 0 && reg2 != REG_HI)
1763 if (!sync && !(old_mask & BIT(op->r.rd)))
1769 case OP_SPECIAL_MFLO:
1773 /* Must use REG_LO if there is another MFLO target*/
1774 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1775 0, sync, mflo, true);
1776 if (reg2 > 0 && reg2 != REG_LO)
1779 if (!sync && !(old_mask & BIT(op->r.rd)))
1798 static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1804 /* This function will remove the following MFLO/MFHI. It must be called
1805 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1807 for (i = offset; i < last; i++) {
1808 struct opcode *op = &block->opcode_list[i];
1816 /* TODO: handle backwards branches too */
1817 if (op_flag_local_branch(op->flags) && (s16)op->c.i.imm >= 0) {
1818 branch_offset = i + 1 + (s16)op->c.i.imm
1819 - !!op_flag_no_ds(op->flags);
1821 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1822 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1827 if (lo && op->r.op == OP_SPECIAL_MFLO) {
1828 pr_debug("Removing MFLO opcode at offset 0x%x\n",
1832 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
1833 pr_debug("Removing MFHI opcode at offset 0x%x\n",
1846 static bool lightrec_always_skip_div_check(void)
1855 static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
1857 struct opcode *list = NULL;
1858 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
1862 for (i = 0; i < block->nb_ops - 1; i++) {
1863 list = &block->opcode_list[i];
1865 lightrec_consts_propagate(block->opcode_list, i, v);
1867 switch (list->i.op) {
1869 switch (list->r.op) {
1870 case OP_SPECIAL_DIV:
1871 case OP_SPECIAL_DIVU:
1872 /* If we are dividing by a non-zero constant, don't
1873 * emit the div-by-zero check. */
1874 if (lightrec_always_skip_div_check() ||
1875 (v[list->r.rt].known & v[list->r.rt].value)) {
1876 list->flags |= LIGHTREC_NO_DIV_CHECK;
1879 case OP_SPECIAL_MULT:
1880 case OP_SPECIAL_MULTU:
1887 case OP_META_MULTU2:
1893 /* Don't support opcodes in delay slots */
1894 if (is_delay_slot(block->opcode_list, i) ||
1895 op_flag_no_ds(list->flags)) {
1899 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
1901 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1902 " not writing LO\n", i << 2);
1903 list->flags |= LIGHTREC_NO_LO;
1906 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
1908 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1909 " not writing HI\n", i << 2);
1910 list->flags |= LIGHTREC_NO_HI;
1913 if (!reg_lo && !reg_hi) {
1914 pr_debug("Both LO/HI unused in this block, they will "
1915 "probably be used in parent block - removing "
1917 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
1920 if (reg_lo > 0 && reg_lo != REG_LO) {
1921 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
1922 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
1924 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
1925 list->r.rd = reg_lo;
1930 if (reg_hi > 0 && reg_hi != REG_HI) {
1931 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
1932 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
1934 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
1935 list->r.imm = reg_hi;
1944 static bool remove_div_sequence(struct block *block, unsigned int offset)
1947 unsigned int i, found = 0;
1950 * Scan for the zero-checking sequence that GCC automatically introduced
1951 * after most DIV/DIVU opcodes. This sequence checks the value of the
1952 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
1953 * handler to crash the PS1.
1955 * For DIV opcodes, this sequence additionally checks that the signed
1956 * operation does not overflow.
1958 * With the assumption that the games never crashed the PS1, we can
1959 * therefore assume that the games never divided by zero or overflowed,
1960 * and these sequences can be removed.
1963 for (i = offset; i < block->nb_ops; i++) {
1964 op = &block->opcode_list[i];
1967 if (op->i.op == OP_SPECIAL &&
1968 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
1971 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
1972 /* BNE ???, zero, +8 */
1977 } else if (found == 1 && !op->opcode) {
1980 } else if (found == 2 && op->opcode == 0x0007000d) {
1983 } else if (found == 3 && op->opcode == 0x2401ffff) {
1986 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
1987 /* BNE ???, at, +16 */
1989 } else if (found == 5 && op->opcode == 0x3c018000) {
1990 /* LUI at, 0x8000 */
1992 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
1993 /* BNE ???, at, +16 */
1995 } else if (found == 7 && !op->opcode) {
1998 } else if (found == 8 && op->opcode == 0x0006000d) {
2011 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
2012 found == 9 ? "" : "U", offset << 2);
2014 for (i = 0; i < found; i++)
2015 block->opcode_list[offset + i].opcode = 0;
2023 static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
2024 struct block *block)
2029 for (i = 0; i < block->nb_ops; i++) {
2030 op = &block->opcode_list[i];
2032 if (op->i.op == OP_SPECIAL &&
2033 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
2034 remove_div_sequence(block, i + 1))
2035 op->flags |= LIGHTREC_NO_DIV_CHECK;
2041 static const u32 memset_code[] = {
2042 0x10a00006, // beqz a1, 2f
2043 0x24a2ffff, // addiu v0,a1,-1
2044 0x2403ffff, // li v1,-1
2045 0xac800000, // 1: sw zero,0(a0)
2046 0x2442ffff, // addiu v0,v0,-1
2047 0x1443fffd, // bne v0,v1, 1b
2048 0x24840004, // addiu a0,a0,4
2049 0x03e00008, // 2: jr ra
2053 static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
2058 for (i = 0; i < block->nb_ops; i++) {
2059 c = block->opcode_list[i].c;
2061 if (c.opcode != memset_code[i])
2064 if (i == ARRAY_SIZE(memset_code) - 1) {
2066 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
2067 block_set_flags(block,
2068 BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE);
2070 /* Return non-zero to skip other optimizers. */
2078 static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
2079 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
2080 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
2081 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
2082 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_branches),
2083 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
2084 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
2085 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
2086 IF_OPT(OPT_FLAG_IO || OPT_FLAG_STORES, &lightrec_flag_io),
2087 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
2088 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
2091 int lightrec_optimize(struct lightrec_state *state, struct block *block)
2096 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
2097 if (lightrec_optimizers[i]) {
2098 ret = (*lightrec_optimizers[i])(state, block);