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:
76 return BIT(op.r.rs) | BIT(op.r.rt);
87 if (op.r.op == OP_CP2_BASIC) {
89 case OP_CP2_BASIC_MTC2:
90 case OP_CP2_BASIC_CTC2:
110 return BIT(op.i.rs) | BIT(op.i.rt);
116 static u64 opcode_write_mask(union code op)
124 case OP_SPECIAL_SYSCALL:
125 case OP_SPECIAL_BREAK:
127 case OP_SPECIAL_MULT:
128 case OP_SPECIAL_MULTU:
130 case OP_SPECIAL_DIVU:
131 if (!OPT_FLAG_MULT_DIV)
132 return BIT(REG_LO) | BIT(REG_HI);
135 flags = BIT(op.r.rd);
139 flags |= BIT(op.r.imm);
141 flags |= BIT(REG_HI);
143 case OP_SPECIAL_MTHI:
145 case OP_SPECIAL_MTLO:
177 if (op.r.op == OP_CP2_BASIC) {
179 case OP_CP2_BASIC_MFC2:
180 case OP_CP2_BASIC_CFC2:
189 case OP_REGIMM_BLTZAL:
190 case OP_REGIMM_BGEZAL:
202 bool opcode_reads_register(union code op, u8 reg)
204 return opcode_read_mask(op) & BIT(reg);
207 bool opcode_writes_register(union code op, u8 reg)
209 return opcode_write_mask(op) & BIT(reg);
212 static int find_prev_writer(const struct opcode *list, unsigned int offset, u8 reg)
217 if (list[offset].flags & LIGHTREC_SYNC)
220 for (i = offset; i > 0; i--) {
223 if (opcode_writes_register(c, reg)) {
224 if (i > 1 && has_delay_slot(list[i - 2].c))
230 if ((list[i - 1].flags & LIGHTREC_SYNC) ||
232 opcode_reads_register(c, reg))
239 static int find_next_reader(const struct opcode *list, unsigned int offset, u8 reg)
244 if (list[offset].flags & LIGHTREC_SYNC)
247 for (i = offset; ; i++) {
250 if (opcode_reads_register(c, reg)) {
251 if (i > 0 && has_delay_slot(list[i - 1].c))
257 if ((list[i].flags & LIGHTREC_SYNC) ||
258 has_delay_slot(c) || opcode_writes_register(c, reg))
265 static bool reg_is_dead(const struct opcode *list, unsigned int offset, u8 reg)
269 if (list[offset].flags & LIGHTREC_SYNC)
272 for (i = offset + 1; ; i++) {
273 if (opcode_reads_register(list[i].c, reg))
276 if (opcode_writes_register(list[i].c, reg))
279 if (has_delay_slot(list[i].c)) {
280 if (list[i].flags & LIGHTREC_NO_DS)
283 return opcode_writes_register(list[i + 1].c, reg);
288 static bool reg_is_read(const struct opcode *list,
289 unsigned int a, unsigned int b, u8 reg)
291 /* Return true if reg is read in one of the opcodes of the interval
294 if (!is_nop(list[a].c) && opcode_reads_register(list[a].c, reg))
301 static bool reg_is_written(const struct opcode *list,
302 unsigned int a, unsigned int b, u8 reg)
304 /* Return true if reg is written in one of the opcodes of the interval
308 if (!is_nop(list[a].c) && opcode_writes_register(list[a].c, reg))
315 static bool reg_is_read_or_written(const struct opcode *list,
316 unsigned int a, unsigned int b, u8 reg)
318 return reg_is_read(list, a, b, reg) || reg_is_written(list, a, b, reg);
321 static bool opcode_is_load(union code op)
338 static bool opcode_is_store(union code op)
353 bool opcode_is_io(union code op)
355 return opcode_is_load(op) || opcode_is_store(op);
359 static bool is_nop(union code op)
361 if (opcode_writes_register(op, 0)) {
364 return op.r.rs != OP_CP0_MFC0;
382 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
384 case OP_SPECIAL_ADDU:
385 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
386 (op.r.rd == op.r.rs && op.r.rt == 0);
388 case OP_SPECIAL_SUBU:
389 return op.r.rd == op.r.rs && op.r.rt == 0;
391 if (op.r.rd == op.r.rt)
392 return op.r.rd == op.r.rs || op.r.rs == 0;
394 return (op.r.rd == op.r.rs) && op.r.rt == 0;
398 return op.r.rd == op.r.rt && op.r.imm == 0;
399 case OP_SPECIAL_MFHI:
400 case OP_SPECIAL_MFLO:
408 return op.i.rt == op.i.rs && op.i.imm == 0;
410 return (op.i.rs == 0 || op.i.imm == 1);
412 return (op.i.op == OP_REGIMM_BLTZ ||
413 op.i.op == OP_REGIMM_BLTZAL) &&
414 (op.i.rs == 0 || op.i.imm == 1);
416 return (op.i.rs == op.i.rt || op.i.imm == 1);
422 bool load_in_delay_slot(union code op)
436 if (op.r.op == OP_CP2_BASIC) {
438 case OP_CP2_BASIC_MFC2:
439 case OP_CP2_BASIC_CFC2:
462 static u32 lightrec_propagate_consts(const struct opcode *op, u32 known, u32 *v)
464 union code c = op->c;
466 if (op->flags & LIGHTREC_SYNC)
473 if (known & BIT(c.r.rt)) {
474 known |= BIT(c.r.rd);
475 v[c.r.rd] = v[c.r.rt] << c.r.imm;
477 known &= ~BIT(c.r.rd);
481 if (known & BIT(c.r.rt)) {
482 known |= BIT(c.r.rd);
483 v[c.r.rd] = v[c.r.rt] >> c.r.imm;
485 known &= ~BIT(c.r.rd);
489 if (known & BIT(c.r.rt)) {
490 known |= BIT(c.r.rd);
491 v[c.r.rd] = (s32)v[c.r.rt] >> c.r.imm;
493 known &= ~BIT(c.r.rd);
496 case OP_SPECIAL_SLLV:
497 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
498 known |= BIT(c.r.rd);
499 v[c.r.rd] = v[c.r.rt] << (v[c.r.rs] & 0x1f);
501 known &= ~BIT(c.r.rd);
504 case OP_SPECIAL_SRLV:
505 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
506 known |= BIT(c.r.rd);
507 v[c.r.rd] = v[c.r.rt] >> (v[c.r.rs] & 0x1f);
509 known &= ~BIT(c.r.rd);
512 case OP_SPECIAL_SRAV:
513 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
514 known |= BIT(c.r.rd);
515 v[c.r.rd] = (s32)v[c.r.rt]
516 >> (v[c.r.rs] & 0x1f);
518 known &= ~BIT(c.r.rd);
522 case OP_SPECIAL_ADDU:
523 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
524 known |= BIT(c.r.rd);
525 v[c.r.rd] = (s32)v[c.r.rt] + (s32)v[c.r.rs];
527 known &= ~BIT(c.r.rd);
531 case OP_SPECIAL_SUBU:
532 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
533 known |= BIT(c.r.rd);
534 v[c.r.rd] = v[c.r.rt] - v[c.r.rs];
536 known &= ~BIT(c.r.rd);
540 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
541 known |= BIT(c.r.rd);
542 v[c.r.rd] = v[c.r.rt] & v[c.r.rs];
544 known &= ~BIT(c.r.rd);
548 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
549 known |= BIT(c.r.rd);
550 v[c.r.rd] = v[c.r.rt] | v[c.r.rs];
552 known &= ~BIT(c.r.rd);
556 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
557 known |= BIT(c.r.rd);
558 v[c.r.rd] = v[c.r.rt] ^ v[c.r.rs];
560 known &= ~BIT(c.r.rd);
564 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
565 known |= BIT(c.r.rd);
566 v[c.r.rd] = ~(v[c.r.rt] | v[c.r.rs]);
568 known &= ~BIT(c.r.rd);
572 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
573 known |= BIT(c.r.rd);
574 v[c.r.rd] = (s32)v[c.r.rs] < (s32)v[c.r.rt];
576 known &= ~BIT(c.r.rd);
579 case OP_SPECIAL_SLTU:
580 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
581 known |= BIT(c.r.rd);
582 v[c.r.rd] = v[c.r.rs] < v[c.r.rt];
584 known &= ~BIT(c.r.rd);
595 if (known & BIT(c.i.rs)) {
596 known |= BIT(c.i.rt);
597 v[c.i.rt] = v[c.i.rs] + (s32)(s16)c.i.imm;
599 known &= ~BIT(c.i.rt);
603 if (known & BIT(c.i.rs)) {
604 known |= BIT(c.i.rt);
605 v[c.i.rt] = (s32)v[c.i.rs] < (s32)(s16)c.i.imm;
607 known &= ~BIT(c.i.rt);
611 if (known & BIT(c.i.rs)) {
612 known |= BIT(c.i.rt);
613 v[c.i.rt] = v[c.i.rs] < (u32)(s32)(s16)c.i.imm;
615 known &= ~BIT(c.i.rt);
619 if (known & BIT(c.i.rs)) {
620 known |= BIT(c.i.rt);
621 v[c.i.rt] = v[c.i.rs] & c.i.imm;
623 known &= ~BIT(c.i.rt);
627 if (known & BIT(c.i.rs)) {
628 known |= BIT(c.i.rt);
629 v[c.i.rt] = v[c.i.rs] | c.i.imm;
631 known &= ~BIT(c.i.rt);
635 if (known & BIT(c.i.rs)) {
636 known |= BIT(c.i.rt);
637 v[c.i.rt] = v[c.i.rs] ^ c.i.imm;
639 known &= ~BIT(c.i.rt);
643 known |= BIT(c.i.rt);
644 v[c.i.rt] = c.i.imm << 16;
650 known &= ~BIT(c.r.rt);
655 if (c.r.op == OP_CP2_BASIC) {
657 case OP_CP2_BASIC_MFC2:
658 case OP_CP2_BASIC_CFC2:
659 known &= ~BIT(c.r.rt);
672 known &= ~BIT(c.i.rt);
675 if (known & BIT(c.r.rs)) {
676 known |= BIT(c.r.rd);
677 v[c.r.rd] = v[c.r.rs];
679 known &= ~BIT(c.r.rd);
689 static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset)
691 struct opcode *prev, *prev2 = NULL, *curr = &list[offset];
692 struct opcode *to_change, *to_nop;
695 if (curr->r.imm != 24 && curr->r.imm != 16)
698 idx = find_prev_writer(list, offset, curr->r.rt);
704 if (prev->i.op != OP_SPECIAL || prev->r.op != OP_SPECIAL_SLL ||
705 prev->r.imm != curr->r.imm || prev->r.rd != curr->r.rt)
708 if (prev->r.rd != prev->r.rt && curr->r.rd != curr->r.rt) {
713 if (!reg_is_dead(list, offset, curr->r.rt) ||
714 reg_is_read_or_written(list, idx, offset, curr->r.rd))
717 /* If rY is dead after the SRL, and rZ is not used after the SLL,
718 * we can change rY to rZ */
720 pr_debug("Detected SLL/SRA with middle temp register\n");
721 prev->r.rd = curr->r.rd;
722 curr->r.rt = prev->r.rd;
725 /* We got a SLL/SRA combo. If imm #16, that's a cast to u16.
726 * If imm #24 that's a cast to u8.
728 * First of all, make sure that the target register of the SLL is not
729 * read before the SRA. */
731 if (prev->r.rd == prev->r.rt) {
738 /* rX is used after the SRA - we cannot convert it. */
739 if (prev->r.rd != curr->r.rd && !reg_is_dead(list, offset, prev->r.rd))
749 idx2 = find_prev_writer(list, idx, prev->r.rt);
751 /* Note that PSX games sometimes do casts after
752 * a LHU or LBU; in this case we can change the
753 * load opcode to a LH or LB, and the cast can
754 * be changed to a MOV or a simple NOP. */
758 if (curr->r.rd != prev2->i.rt &&
759 !reg_is_dead(list, offset, prev2->i.rt))
761 else if (curr->r.imm == 16 && prev2->i.op == OP_LHU)
763 else if (curr->r.imm == 24 && prev2->i.op == OP_LBU)
769 if (curr->r.rd == prev2->i.rt) {
770 to_change->opcode = 0;
771 } else if (reg_is_dead(list, offset, prev2->i.rt) &&
772 !reg_is_read_or_written(list, idx2 + 1, offset, curr->r.rd)) {
773 /* The target register of the SRA is dead after the
774 * LBU/LHU; we can change the target register of the
775 * LBU/LHU to the one of the SRA. */
776 prev2->i.rt = curr->r.rd;
777 to_change->opcode = 0;
779 to_change->i.op = OP_META_MOV;
780 to_change->r.rd = curr->r.rd;
781 to_change->r.rs = prev2->i.rt;
784 if (to_nop->r.imm == 24)
785 pr_debug("Convert LBU+SLL+SRA to LB\n");
787 pr_debug("Convert LHU+SLL+SRA to LH\n");
792 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
794 prev->r.imm == 24 ? 'C' : 'S');
796 if (to_change == prev) {
797 to_change->i.rs = prev->r.rt;
798 to_change->i.rt = curr->r.rd;
800 to_change->i.rt = curr->r.rd;
801 to_change->i.rs = prev->r.rt;
804 if (to_nop->r.imm == 24)
805 to_change->i.op = OP_META_EXTC;
807 to_change->i.op = OP_META_EXTS;
813 static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
815 struct opcode *list = block->opcode_list;
818 u32 values[32] = { 0 };
822 for (i = 0; i < block->nb_ops; i++) {
825 /* Transform all opcodes detected as useless to real NOPs
826 * (0x0: SLL r0, r0, #0) */
827 if (op->opcode != 0 && is_nop(op->c)) {
828 pr_debug("Converting useless opcode 0x%08x to NOP\n",
836 /* Register $zero is always, well, zero */
842 if (op->i.rs == op->i.rt) {
845 } else if (op->i.rs == 0) {
859 if (!(op->flags & LIGHTREC_SYNC) &&
860 (known & BIT(op->i.rt)) &&
861 values[op->i.rt] == op->i.imm << 16) {
862 pr_debug("Converting duplicated LUI to NOP\n");
866 if (op->i.imm != 0 || op->i.rt == 0)
869 reader = find_next_reader(list, i + 1, op->i.rt);
871 (opcode_writes_register(list[reader].c, op->i.rt) ||
872 reg_is_dead(list, reader, op->i.rt))) {
874 pr_debug("Removing useless LUI 0x0\n");
876 if (list[reader].i.rs == op->i.rt)
877 list[reader].i.rs = 0;
878 if (list[reader].i.op == OP_SPECIAL &&
879 list[reader].i.rt == op->i.rt)
880 list[reader].i.rt = 0;
885 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
886 * with register $zero to the MOV meta-opcode */
890 if (op->i.imm == 0) {
891 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
892 op->i.op = OP_META_MOV;
899 if (op->r.imm == 0) {
900 pr_debug("Convert SRA #0 to MOV\n");
901 op->i.op = OP_META_MOV;
906 lightrec_optimize_sll_sra(block->opcode_list, i);
910 if (op->r.imm == 0) {
911 pr_debug("Convert SLL/SRL #0 to MOV\n");
912 op->i.op = OP_META_MOV;
918 case OP_SPECIAL_ADDU:
920 pr_debug("Convert OR/ADD $zero to MOV\n");
921 op->i.op = OP_META_MOV;
924 case OP_SPECIAL_SUB: /* fall-through */
925 case OP_SPECIAL_SUBU:
927 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
928 op->i.op = OP_META_MOV;
930 default: /* fall-through */
933 default: /* fall-through */
937 known = lightrec_propagate_consts(op, known, values);
943 static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
945 struct opcode *list, *next = &block->opcode_list[0];
947 union code op, next_op;
950 for (i = 0; i < block->nb_ops - 1; i++) {
952 next = &block->opcode_list[i + 1];
956 if (!has_delay_slot(op) ||
957 list->flags & (LIGHTREC_NO_DS | LIGHTREC_EMULATE_BRANCH) ||
958 op.opcode == 0 || next_op.opcode == 0)
961 if (i && has_delay_slot(block->opcode_list[i - 1].c) &&
962 !(block->opcode_list[i - 1].flags & LIGHTREC_NO_DS))
965 if ((list->flags & LIGHTREC_SYNC) ||
966 (next->flags & LIGHTREC_SYNC))
969 switch (list->i.op) {
972 case OP_SPECIAL_JALR:
973 if (opcode_reads_register(next_op, op.r.rd) ||
974 opcode_writes_register(next_op, op.r.rd))
976 case OP_SPECIAL_JR: /* fall-through */
977 if (opcode_writes_register(next_op, op.r.rs))
979 default: /* fall-through */
982 case OP_J: /* fall-through */
985 if (opcode_reads_register(next_op, 31) ||
986 opcode_writes_register(next_op, 31))
992 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
994 case OP_BLEZ: /* fall-through */
996 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1001 case OP_REGIMM_BLTZAL:
1002 case OP_REGIMM_BGEZAL:
1003 if (opcode_reads_register(next_op, 31) ||
1004 opcode_writes_register(next_op, 31))
1006 case OP_REGIMM_BLTZ: /* fall-through */
1007 case OP_REGIMM_BGEZ:
1009 opcode_writes_register(next_op, op.i.rs))
1013 default: /* fall-through */
1017 pr_debug("Swap branch and delay slot opcodes "
1018 "at offsets 0x%x / 0x%x\n",
1019 i << 2, (i + 1) << 2);
1021 flags = next->flags;
1024 next->flags = list->flags | LIGHTREC_NO_DS;
1025 list->flags = flags | LIGHTREC_NO_DS;
1031 static int shrink_opcode_list(struct lightrec_state *state, struct block *block, u16 new_size)
1033 struct opcode *list;
1035 if (new_size >= block->nb_ops) {
1036 pr_err("Invalid shrink size (%u vs %u)\n",
1037 new_size, block->nb_ops);
1042 list = lightrec_malloc(state, MEM_FOR_IR,
1043 sizeof(*list) * new_size);
1045 pr_err("Unable to allocate memory\n");
1049 memcpy(list, block->opcode_list, sizeof(*list) * new_size);
1051 lightrec_free_opcode_list(state, block);
1052 block->opcode_list = list;
1053 block->nb_ops = new_size;
1055 pr_debug("Shrunk opcode list of block PC 0x%08x to %u opcodes\n",
1056 block->pc, new_size);
1061 static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1062 struct block *block)
1064 struct opcode *op, *next = &block->opcode_list[0];
1068 for (i = 0; i < block->nb_ops - 1; i++) {
1070 next = &block->opcode_list[i + 1];
1072 if (!has_delay_slot(op->c) ||
1073 (!load_in_delay_slot(next->c) &&
1074 !has_delay_slot(next->c) &&
1075 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1078 if (op->c.opcode == next->c.opcode) {
1079 /* The delay slot is the exact same opcode as the branch
1080 * opcode: this is effectively a NOP */
1085 op->flags |= LIGHTREC_EMULATE_BRANCH;
1087 if (op == block->opcode_list) {
1088 pr_debug("First opcode of block PC 0x%08x is an impossible branch\n",
1091 /* If the first opcode is an 'impossible' branch, we
1092 * only keep the first two opcodes of the block (the
1093 * branch itself + its delay slot) */
1094 if (block->nb_ops > 2)
1095 ret = shrink_opcode_list(state, block, 2);
1103 static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1105 struct opcode *list;
1109 for (i = 0; i < block->nb_ops; i++) {
1110 list = &block->opcode_list[i];
1112 if (should_emulate(list))
1115 switch (list->i.op) {
1121 offset = i + 1 + (s16)list->i.imm;
1122 if (offset >= 0 && offset < block->nb_ops)
1124 default: /* fall-through */
1128 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1130 if (should_emulate(&block->opcode_list[offset])) {
1131 pr_debug("Branch target must be emulated - skip\n");
1135 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1136 pr_debug("Branch target is a delay slot - skip\n");
1140 pr_debug("Adding sync at offset 0x%x\n", offset << 2);
1142 block->opcode_list[offset].flags |= LIGHTREC_SYNC;
1143 list->flags |= LIGHTREC_LOCAL_BRANCH;
1149 bool has_delay_slot(union code op)
1155 case OP_SPECIAL_JALR:
1173 bool should_emulate(const struct opcode *list)
1175 return has_delay_slot(list->c) &&
1176 (list->flags & LIGHTREC_EMULATE_BRANCH);
1179 static void lightrec_add_unload(struct opcode *op, u8 reg)
1181 if (op->i.op == OP_SPECIAL && reg == op->r.rd)
1182 op->flags |= LIGHTREC_UNLOAD_RD;
1184 if (op->i.rs == reg)
1185 op->flags |= LIGHTREC_UNLOAD_RS;
1186 if (op->i.rt == reg)
1187 op->flags |= LIGHTREC_UNLOAD_RT;
1190 static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1192 unsigned int i, offset;
1196 for (reg = 1; reg < 34; reg++) {
1197 int last_r_id = -1, last_w_id = -1;
1199 for (i = 0; i < block->nb_ops; i++) {
1200 union code c = block->opcode_list[i].c;
1202 if (opcode_reads_register(c, reg))
1204 if (opcode_writes_register(c, reg))
1208 if (last_w_id > last_r_id)
1209 offset = (unsigned int)last_w_id;
1210 else if (last_r_id >= 0)
1211 offset = (unsigned int)last_r_id;
1215 op = &block->opcode_list[offset];
1217 if (has_delay_slot(op->c) && (op->flags & LIGHTREC_NO_DS))
1220 if (offset == block->nb_ops)
1223 lightrec_add_unload(&block->opcode_list[offset], reg);
1229 static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1231 const struct lightrec_mem_map *map;
1232 struct opcode *list;
1234 u32 values[32] = { 0 };
1238 for (i = 0; i < block->nb_ops; i++) {
1239 list = &block->opcode_list[i];
1241 /* Register $zero is always, well, zero */
1245 switch (list->i.op) {
1249 if (OPT_FLAG_STORES) {
1250 /* Mark all store operations that target $sp or $gp
1251 * as not requiring code invalidation. This is based
1252 * on the heuristic that stores using one of these
1253 * registers as address will never hit a code page. */
1254 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1255 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1256 pr_debug("Flaging opcode 0x%08x as not "
1257 "requiring invalidation\n",
1259 list->flags |= LIGHTREC_NO_INVALIDATE;
1262 /* Detect writes whose destination address is inside the
1263 * current block, using constant propagation. When these
1264 * occur, we mark the blocks as not compilable. */
1265 if ((known & BIT(list->i.rs)) &&
1266 kunseg(values[list->i.rs]) >= kunseg(block->pc) &&
1267 kunseg(values[list->i.rs]) < (kunseg(block->pc) +
1268 block->nb_ops * 4)) {
1269 pr_debug("Self-modifying block detected\n");
1270 block->flags |= BLOCK_NEVER_COMPILE;
1271 list->flags |= LIGHTREC_SMC;
1274 case OP_SWL: /* fall-through */
1285 if (OPT_FLAG_IO && (known & BIT(list->i.rs))) {
1286 val = kunseg(values[list->i.rs] + (s16) list->i.imm);
1287 map = lightrec_get_map(state, NULL, val);
1289 if (!map || map->ops ||
1290 map == &state->maps[PSX_MAP_PARALLEL_PORT]) {
1291 pr_debug("Flagging opcode %u as accessing I/O registers\n",
1293 list->flags |= LIGHTREC_HW_IO;
1295 pr_debug("Flaging opcode %u as direct memory access\n", i);
1296 list->flags |= LIGHTREC_DIRECT_IO;
1299 default: /* fall-through */
1303 known = lightrec_propagate_consts(list, known, values);
1309 static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1310 const struct opcode *last,
1311 u32 mask, bool sync, bool mflo, bool another)
1313 const struct opcode *op, *next = &block->opcode_list[offset];
1315 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1319 for (i = offset; i < block->nb_ops; i++) {
1321 next = &block->opcode_list[i + 1];
1324 /* If any other opcode writes or reads to the register
1325 * we'd use, then we cannot use it anymore. */
1326 mask |= opcode_read_mask(op->c);
1327 mask |= opcode_write_mask(op->c);
1329 if (op->flags & LIGHTREC_SYNC)
1338 /* TODO: handle backwards branches too */
1340 (op->flags & LIGHTREC_LOCAL_BRANCH) &&
1341 (s16)op->c.i.imm >= 0) {
1342 branch_offset = i + 1 + (s16)op->c.i.imm
1343 - !!(OPT_SWITCH_DELAY_SLOTS && (op->flags & LIGHTREC_NO_DS));
1345 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1346 mask, sync, mflo, false);
1347 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1348 mask, sync, mflo, false);
1349 if (reg > 0 && reg == reg2)
1355 return mflo ? REG_LO : REG_HI;
1358 case OP_SPECIAL_MULT:
1359 case OP_SPECIAL_MULTU:
1360 case OP_SPECIAL_DIV:
1361 case OP_SPECIAL_DIVU:
1363 case OP_SPECIAL_MTHI:
1367 case OP_SPECIAL_MTLO:
1376 !(op->flags & LIGHTREC_NO_DS) &&
1377 (next->i.op == OP_SPECIAL) &&
1378 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1379 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1383 case OP_SPECIAL_JALR:
1385 case OP_SPECIAL_MFHI:
1389 /* Must use REG_HI if there is another MFHI target*/
1390 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1391 0, sync, mflo, true);
1392 if (reg2 > 0 && reg2 != REG_HI)
1395 if (!sync && !(old_mask & BIT(op->r.rd)))
1401 case OP_SPECIAL_MFLO:
1405 /* Must use REG_LO if there is another MFLO target*/
1406 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1407 0, sync, mflo, true);
1408 if (reg2 > 0 && reg2 != REG_LO)
1411 if (!sync && !(old_mask & BIT(op->r.rd)))
1430 static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1436 /* This function will remove the following MFLO/MFHI. It must be called
1437 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1439 for (i = offset; i < last; i++) {
1440 struct opcode *op = &block->opcode_list[i];
1448 /* TODO: handle backwards branches too */
1449 if ((op->flags & LIGHTREC_LOCAL_BRANCH) &&
1450 (s16)op->c.i.imm >= 0) {
1451 branch_offset = i + 1 + (s16)op->c.i.imm
1452 - !!(OPT_SWITCH_DELAY_SLOTS && (op->flags & LIGHTREC_NO_DS));
1454 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1455 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1460 if (lo && op->r.op == OP_SPECIAL_MFLO) {
1461 pr_debug("Removing MFLO opcode at offset 0x%x\n",
1465 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
1466 pr_debug("Removing MFHI opcode at offset 0x%x\n",
1479 static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
1481 struct opcode *list;
1485 for (i = 0; i < block->nb_ops - 1; i++) {
1486 list = &block->opcode_list[i];
1488 if (list->i.op != OP_SPECIAL)
1491 switch (list->r.op) {
1492 case OP_SPECIAL_MULT:
1493 case OP_SPECIAL_MULTU:
1494 case OP_SPECIAL_DIV:
1495 case OP_SPECIAL_DIVU:
1501 /* Don't support opcodes in delay slots */
1502 if ((i && has_delay_slot(block->opcode_list[i - 1].c)) ||
1503 (list->flags & LIGHTREC_NO_DS))
1506 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
1508 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1509 " not writing LO\n", i << 2);
1510 list->flags |= LIGHTREC_NO_LO;
1513 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
1515 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1516 " not writing HI\n", i << 2);
1517 list->flags |= LIGHTREC_NO_HI;
1520 if (!reg_lo && !reg_hi) {
1521 pr_debug("Both LO/HI unused in this block, they will "
1522 "probably be used in parent block - removing "
1524 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
1527 if (reg_lo > 0 && reg_lo != REG_LO) {
1528 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
1529 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
1531 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
1532 list->r.rd = reg_lo;
1537 if (reg_hi > 0 && reg_hi != REG_HI) {
1538 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
1539 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
1541 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
1542 list->r.imm = reg_hi;
1551 static bool remove_div_sequence(struct block *block, unsigned int offset)
1554 unsigned int i, found = 0;
1557 * Scan for the zero-checking sequence that GCC automatically introduced
1558 * after most DIV/DIVU opcodes. This sequence checks the value of the
1559 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
1560 * handler to crash the PS1.
1562 * For DIV opcodes, this sequence additionally checks that the signed
1563 * operation does not overflow.
1565 * With the assumption that the games never crashed the PS1, we can
1566 * therefore assume that the games never divided by zero or overflowed,
1567 * and these sequences can be removed.
1570 for (i = offset; i < block->nb_ops; i++) {
1571 op = &block->opcode_list[i];
1574 if (op->i.op == OP_SPECIAL &&
1575 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
1578 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
1579 /* BNE ???, zero, +8 */
1584 } else if (found == 1 && !op->opcode) {
1587 } else if (found == 2 && op->opcode == 0x0007000d) {
1590 } else if (found == 3 && op->opcode == 0x2401ffff) {
1593 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
1594 /* BNE ???, at, +16 */
1596 } else if (found == 5 && op->opcode == 0x3c018000) {
1597 /* LUI at, 0x8000 */
1599 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
1600 /* BNE ???, at, +16 */
1602 } else if (found == 7 && !op->opcode) {
1605 } else if (found == 8 && op->opcode == 0x0006000d) {
1618 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
1619 found == 9 ? "" : "U", offset << 2);
1621 for (i = 0; i < found; i++)
1622 block->opcode_list[offset + i].opcode = 0;
1630 static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
1631 struct block *block)
1636 for (i = 0; i < block->nb_ops; i++) {
1637 op = &block->opcode_list[i];
1639 if (op->i.op == OP_SPECIAL &&
1640 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
1641 remove_div_sequence(block, i + 1))
1642 op->flags |= LIGHTREC_NO_DIV_CHECK;
1648 static const u32 memset_code[] = {
1649 0x10a00006, // beqz a1, 2f
1650 0x24a2ffff, // addiu v0,a1,-1
1651 0x2403ffff, // li v1,-1
1652 0xac800000, // 1: sw zero,0(a0)
1653 0x2442ffff, // addiu v0,v0,-1
1654 0x1443fffd, // bne v0,v1, 1b
1655 0x24840004, // addiu a0,a0,4
1656 0x03e00008, // 2: jr ra
1660 static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
1665 for (i = 0; i < block->nb_ops; i++) {
1666 c = block->opcode_list[i].c;
1668 if (c.opcode != memset_code[i])
1671 if (i == ARRAY_SIZE(memset_code) - 1) {
1673 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
1674 block->flags |= BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE;
1676 /* Return non-zero to skip other optimizers. */
1684 static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
1685 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
1686 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
1687 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
1688 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
1689 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
1690 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
1691 IF_OPT(OPT_FLAG_IO || OPT_FLAG_STORES, &lightrec_flag_io),
1692 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
1693 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
1696 int lightrec_optimize(struct lightrec_state *state, struct block *block)
1701 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
1702 if (lightrec_optimizers[i]) {
1703 ret = (*lightrec_optimizers[i])(state, block);