update analog default list
[pcsx_rearmed.git] / deps / lightrec / optimizer.c
... / ...
CommitLineData
1// SPDX-License-Identifier: LGPL-2.1-or-later
2/*
3 * Copyright (C) 2014-2021 Paul Cercueil <paul@crapouillou.net>
4 */
5
6#include "constprop.h"
7#include "lightrec-config.h"
8#include "disassembler.h"
9#include "lightrec.h"
10#include "memmanager.h"
11#include "optimizer.h"
12#include "regcache.h"
13
14#include <errno.h>
15#include <stdbool.h>
16#include <stdlib.h>
17#include <string.h>
18
19#define IF_OPT(opt, ptr) ((opt) ? (ptr) : NULL)
20
21struct optimizer_list {
22 void (**optimizers)(struct opcode *);
23 unsigned int nb_optimizers;
24};
25
26static bool is_nop(union code op);
27
28bool is_unconditional_jump(union code c)
29{
30 switch (c.i.op) {
31 case OP_SPECIAL:
32 return c.r.op == OP_SPECIAL_JR || c.r.op == OP_SPECIAL_JALR;
33 case OP_J:
34 case OP_JAL:
35 return true;
36 case OP_BEQ:
37 case OP_BLEZ:
38 return c.i.rs == c.i.rt;
39 case OP_REGIMM:
40 return (c.r.rt == OP_REGIMM_BGEZ ||
41 c.r.rt == OP_REGIMM_BGEZAL) && c.i.rs == 0;
42 default:
43 return false;
44 }
45}
46
47bool is_syscall(union code c)
48{
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));
53}
54
55static u64 opcode_read_mask(union code op)
56{
57 switch (op.i.op) {
58 case OP_SPECIAL:
59 switch (op.r.op) {
60 case OP_SPECIAL_SYSCALL:
61 case OP_SPECIAL_BREAK:
62 return 0;
63 case OP_SPECIAL_JR:
64 case OP_SPECIAL_JALR:
65 case OP_SPECIAL_MTHI:
66 case OP_SPECIAL_MTLO:
67 return BIT(op.r.rs);
68 case OP_SPECIAL_MFHI:
69 return BIT(REG_HI);
70 case OP_SPECIAL_MFLO:
71 return BIT(REG_LO);
72 case OP_SPECIAL_SLL:
73 if (!op.r.imm)
74 return 0;
75 fallthrough;
76 case OP_SPECIAL_SRL:
77 case OP_SPECIAL_SRA:
78 return BIT(op.r.rt);
79 default:
80 return BIT(op.r.rs) | BIT(op.r.rt);
81 }
82 case OP_CP0:
83 switch (op.r.rs) {
84 case OP_CP0_MTC0:
85 case OP_CP0_CTC0:
86 return BIT(op.r.rt);
87 default:
88 return 0;
89 }
90 case OP_CP2:
91 if (op.r.op == OP_CP2_BASIC) {
92 switch (op.r.rs) {
93 case OP_CP2_BASIC_MTC2:
94 case OP_CP2_BASIC_CTC2:
95 return BIT(op.r.rt);
96 default:
97 break;
98 }
99 }
100 return 0;
101 case OP_J:
102 case OP_JAL:
103 case OP_LUI:
104 return 0;
105 case OP_BEQ:
106 if (op.i.rs == op.i.rt)
107 return 0;
108 fallthrough;
109 case OP_BNE:
110 case OP_LWL:
111 case OP_LWR:
112 case OP_SB:
113 case OP_SH:
114 case OP_SWL:
115 case OP_SW:
116 case OP_SWR:
117 case OP_META_LWU:
118 case OP_META_SWU:
119 return BIT(op.i.rs) | BIT(op.i.rt);
120 case OP_META:
121 return BIT(op.m.rs);
122 default:
123 return BIT(op.i.rs);
124 }
125}
126
127static u64 mult_div_write_mask(union code op)
128{
129 u64 flags;
130
131 if (!OPT_FLAG_MULT_DIV)
132 return BIT(REG_LO) | BIT(REG_HI);
133
134 if (op.r.rd)
135 flags = BIT(op.r.rd);
136 else
137 flags = BIT(REG_LO);
138 if (op.r.imm)
139 flags |= BIT(op.r.imm);
140 else
141 flags |= BIT(REG_HI);
142
143 return flags;
144}
145
146u64 opcode_write_mask(union code op)
147{
148 switch (op.i.op) {
149 case OP_META_MULT2:
150 case OP_META_MULTU2:
151 return mult_div_write_mask(op);
152 case OP_META:
153 return BIT(op.m.rd);
154 case OP_SPECIAL:
155 switch (op.r.op) {
156 case OP_SPECIAL_JR:
157 case OP_SPECIAL_SYSCALL:
158 case OP_SPECIAL_BREAK:
159 return 0;
160 case OP_SPECIAL_MULT:
161 case OP_SPECIAL_MULTU:
162 case OP_SPECIAL_DIV:
163 case OP_SPECIAL_DIVU:
164 return mult_div_write_mask(op);
165 case OP_SPECIAL_MTHI:
166 return BIT(REG_HI);
167 case OP_SPECIAL_MTLO:
168 return BIT(REG_LO);
169 case OP_SPECIAL_SLL:
170 if (!op.r.imm)
171 return 0;
172 fallthrough;
173 default:
174 return BIT(op.r.rd);
175 }
176 case OP_ADDI:
177 case OP_ADDIU:
178 case OP_SLTI:
179 case OP_SLTIU:
180 case OP_ANDI:
181 case OP_ORI:
182 case OP_XORI:
183 case OP_LUI:
184 case OP_LB:
185 case OP_LH:
186 case OP_LWL:
187 case OP_LW:
188 case OP_LBU:
189 case OP_LHU:
190 case OP_LWR:
191 case OP_META_LWU:
192 return BIT(op.i.rt);
193 case OP_JAL:
194 return BIT(31);
195 case OP_CP0:
196 switch (op.r.rs) {
197 case OP_CP0_MFC0:
198 case OP_CP0_CFC0:
199 return BIT(op.i.rt);
200 default:
201 return 0;
202 }
203 case OP_CP2:
204 if (op.r.op == OP_CP2_BASIC) {
205 switch (op.r.rs) {
206 case OP_CP2_BASIC_MFC2:
207 case OP_CP2_BASIC_CFC2:
208 return BIT(op.i.rt);
209 default:
210 break;
211 }
212 }
213 return 0;
214 case OP_REGIMM:
215 switch (op.r.rt) {
216 case OP_REGIMM_BLTZAL:
217 case OP_REGIMM_BGEZAL:
218 return BIT(31);
219 default:
220 return 0;
221 }
222 default:
223 return 0;
224 }
225}
226
227bool opcode_reads_register(union code op, u8 reg)
228{
229 return opcode_read_mask(op) & BIT(reg);
230}
231
232bool opcode_writes_register(union code op, u8 reg)
233{
234 return opcode_write_mask(op) & BIT(reg);
235}
236
237static int find_prev_writer(const struct opcode *list, unsigned int offset, u8 reg)
238{
239 union code c;
240 unsigned int i;
241
242 if (op_flag_sync(list[offset].flags))
243 return -1;
244
245 for (i = offset; i > 0; i--) {
246 c = list[i - 1].c;
247
248 if (opcode_writes_register(c, reg)) {
249 if (i > 1 && has_delay_slot(list[i - 2].c))
250 break;
251
252 return i - 1;
253 }
254
255 if (op_flag_sync(list[i - 1].flags) ||
256 has_delay_slot(c) ||
257 opcode_reads_register(c, reg))
258 break;
259 }
260
261 return -1;
262}
263
264static int find_next_reader(const struct opcode *list, unsigned int offset, u8 reg)
265{
266 unsigned int i;
267 union code c;
268
269 if (op_flag_sync(list[offset].flags))
270 return -1;
271
272 for (i = offset; ; i++) {
273 c = list[i].c;
274
275 if (opcode_reads_register(c, reg))
276 return i;
277
278 if (op_flag_sync(list[i].flags)
279 || (op_flag_no_ds(list[i].flags) && has_delay_slot(c))
280 || is_delay_slot(list, i)
281 || opcode_writes_register(c, reg))
282 break;
283 }
284
285 return -1;
286}
287
288static bool reg_is_dead(const struct opcode *list, unsigned int offset, u8 reg)
289{
290 unsigned int i;
291
292 if (op_flag_sync(list[offset].flags) || is_delay_slot(list, offset))
293 return false;
294
295 for (i = offset + 1; ; i++) {
296 if (opcode_reads_register(list[i].c, reg))
297 return false;
298
299 if (opcode_writes_register(list[i].c, reg))
300 return true;
301
302 if (is_syscall(list[i].c))
303 return false;
304
305 if (has_delay_slot(list[i].c)) {
306 if (op_flag_no_ds(list[i].flags) ||
307 opcode_reads_register(list[i + 1].c, reg))
308 return false;
309
310 return opcode_writes_register(list[i + 1].c, reg);
311 }
312 }
313}
314
315static bool reg_is_read(const struct opcode *list,
316 unsigned int a, unsigned int b, u8 reg)
317{
318 /* Return true if reg is read in one of the opcodes of the interval
319 * [a, b[ */
320 for (; a < b; a++) {
321 if (!is_nop(list[a].c) && opcode_reads_register(list[a].c, reg))
322 return true;
323 }
324
325 return false;
326}
327
328static bool reg_is_written(const struct opcode *list,
329 unsigned int a, unsigned int b, u8 reg)
330{
331 /* Return true if reg is written in one of the opcodes of the interval
332 * [a, b[ */
333
334 for (; a < b; a++) {
335 if (!is_nop(list[a].c) && opcode_writes_register(list[a].c, reg))
336 return true;
337 }
338
339 return false;
340}
341
342static bool reg_is_read_or_written(const struct opcode *list,
343 unsigned int a, unsigned int b, u8 reg)
344{
345 return reg_is_read(list, a, b, reg) || reg_is_written(list, a, b, reg);
346}
347
348bool opcode_is_mfc(union code op)
349{
350 switch (op.i.op) {
351 case OP_CP0:
352 switch (op.r.rs) {
353 case OP_CP0_MFC0:
354 case OP_CP0_CFC0:
355 return true;
356 default:
357 break;
358 }
359
360 break;
361 case OP_CP2:
362 if (op.r.op == OP_CP2_BASIC) {
363 switch (op.r.rs) {
364 case OP_CP2_BASIC_MFC2:
365 case OP_CP2_BASIC_CFC2:
366 return true;
367 default:
368 break;
369 }
370 }
371
372 break;
373 default:
374 break;
375 }
376
377 return false;
378}
379
380bool opcode_is_load(union code op)
381{
382 switch (op.i.op) {
383 case OP_LB:
384 case OP_LH:
385 case OP_LWL:
386 case OP_LW:
387 case OP_LBU:
388 case OP_LHU:
389 case OP_LWR:
390 case OP_LWC2:
391 case OP_META_LWU:
392 return true;
393 default:
394 return false;
395 }
396}
397
398static bool opcode_is_store(union code op)
399{
400 switch (op.i.op) {
401 case OP_SB:
402 case OP_SH:
403 case OP_SW:
404 case OP_SWL:
405 case OP_SWR:
406 case OP_SWC2:
407 case OP_META_SWU:
408 return true;
409 default:
410 return false;
411 }
412}
413
414static u8 opcode_get_io_size(union code op)
415{
416 switch (op.i.op) {
417 case OP_LB:
418 case OP_LBU:
419 case OP_SB:
420 return 8;
421 case OP_LH:
422 case OP_LHU:
423 case OP_SH:
424 return 16;
425 default:
426 return 32;
427 }
428}
429
430bool opcode_is_io(union code op)
431{
432 return opcode_is_load(op) || opcode_is_store(op);
433}
434
435/* TODO: Complete */
436static bool is_nop(union code op)
437{
438 if (opcode_writes_register(op, 0)) {
439 switch (op.i.op) {
440 case OP_CP0:
441 return op.r.rs != OP_CP0_MFC0;
442 case OP_LB:
443 case OP_LH:
444 case OP_LWL:
445 case OP_LW:
446 case OP_LBU:
447 case OP_LHU:
448 case OP_LWR:
449 case OP_META_LWU:
450 return false;
451 default:
452 return true;
453 }
454 }
455
456 switch (op.i.op) {
457 case OP_SPECIAL:
458 switch (op.r.op) {
459 case OP_SPECIAL_AND:
460 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
461 case OP_SPECIAL_ADD:
462 case OP_SPECIAL_ADDU:
463 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
464 (op.r.rd == op.r.rs && op.r.rt == 0);
465 case OP_SPECIAL_SUB:
466 case OP_SPECIAL_SUBU:
467 return op.r.rd == op.r.rs && op.r.rt == 0;
468 case OP_SPECIAL_OR:
469 if (op.r.rd == op.r.rt)
470 return op.r.rd == op.r.rs || op.r.rs == 0;
471 else
472 return (op.r.rd == op.r.rs) && op.r.rt == 0;
473 case OP_SPECIAL_SLL:
474 case OP_SPECIAL_SRA:
475 case OP_SPECIAL_SRL:
476 return op.r.rd == op.r.rt && op.r.imm == 0;
477 case OP_SPECIAL_MFHI:
478 case OP_SPECIAL_MFLO:
479 return op.r.rd == 0;
480 default:
481 return false;
482 }
483 case OP_ORI:
484 case OP_ADDI:
485 case OP_ADDIU:
486 return op.i.rt == op.i.rs && op.i.imm == 0;
487 case OP_BGTZ:
488 return (op.i.rs == 0 || op.i.imm == 1);
489 case OP_REGIMM:
490 return (op.i.op == OP_REGIMM_BLTZ ||
491 op.i.op == OP_REGIMM_BLTZAL) &&
492 (op.i.rs == 0 || op.i.imm == 1);
493 case OP_BNE:
494 return (op.i.rs == op.i.rt || op.i.imm == 1);
495 default:
496 return false;
497 }
498}
499
500static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset,
501 struct constprop_data *v)
502{
503 struct opcode *ldop = NULL, *curr = &list[offset], *next;
504 struct opcode *to_change, *to_nop;
505 int idx, idx2;
506
507 if (curr->r.imm != 24 && curr->r.imm != 16)
508 return;
509
510 if (is_delay_slot(list, offset))
511 return;
512
513 idx = find_next_reader(list, offset + 1, curr->r.rd);
514 if (idx < 0)
515 return;
516
517 next = &list[idx];
518
519 if (next->i.op != OP_SPECIAL || next->r.op != OP_SPECIAL_SRA ||
520 next->r.imm != curr->r.imm || next->r.rt != curr->r.rd)
521 return;
522
523 if (curr->r.rd != curr->r.rt && next->r.rd != next->r.rt) {
524 /* sll rY, rX, 16
525 * ...
526 * sra rZ, rY, 16 */
527
528 if (!reg_is_dead(list, idx, curr->r.rd) ||
529 reg_is_read_or_written(list, offset, idx, next->r.rd))
530 return;
531
532 /* If rY is dead after the SRL, and rZ is not used after the SLL,
533 * we can change rY to rZ */
534
535 pr_debug("Detected SLL/SRA with middle temp register\n");
536 curr->r.rd = next->r.rd;
537 next->r.rt = curr->r.rd;
538 }
539
540 /* We got a SLL/SRA combo. If imm #16, that's a cast to s16.
541 * If imm #24 that's a cast to s8.
542 *
543 * First of all, make sure that the target register of the SLL is not
544 * read after the SRA. */
545
546 if (curr->r.rd == curr->r.rt) {
547 /* sll rX, rX, 16
548 * ...
549 * sra rY, rX, 16 */
550 to_change = next;
551 to_nop = curr;
552
553 /* rX is used after the SRA - we cannot convert it. */
554 if (curr->r.rd != next->r.rd && !reg_is_dead(list, idx, curr->r.rd))
555 return;
556 } else {
557 /* sll rY, rX, 16
558 * ...
559 * sra rY, rY, 16 */
560 to_change = curr;
561 to_nop = next;
562 }
563
564 idx2 = find_prev_writer(list, offset, curr->r.rt);
565 if (idx2 >= 0) {
566 /* Note that PSX games sometimes do casts after
567 * a LHU or LBU; in this case we can change the
568 * load opcode to a LH or LB, and the cast can
569 * be changed to a MOV or a simple NOP. */
570
571 ldop = &list[idx2];
572
573 if (next->r.rd != ldop->i.rt &&
574 !reg_is_dead(list, idx, ldop->i.rt))
575 ldop = NULL;
576 else if (curr->r.imm == 16 && ldop->i.op == OP_LHU)
577 ldop->i.op = OP_LH;
578 else if (curr->r.imm == 24 && ldop->i.op == OP_LBU)
579 ldop->i.op = OP_LB;
580 else
581 ldop = NULL;
582
583 if (ldop) {
584 if (next->r.rd == ldop->i.rt) {
585 to_change->opcode = 0;
586 } else if (reg_is_dead(list, idx, ldop->i.rt) &&
587 !reg_is_read_or_written(list, idx2 + 1, idx, next->r.rd)) {
588 /* The target register of the SRA is dead after the
589 * LBU/LHU; we can change the target register of the
590 * LBU/LHU to the one of the SRA. */
591 v[ldop->i.rt].known = 0;
592 v[ldop->i.rt].sign = 0;
593 ldop->i.rt = next->r.rd;
594 to_change->opcode = 0;
595 } else {
596 to_change->i.op = OP_META;
597 to_change->m.op = OP_META_MOV;
598 to_change->m.rd = next->r.rd;
599 to_change->m.rs = ldop->i.rt;
600 }
601
602 if (to_nop->r.imm == 24)
603 pr_debug("Convert LBU+SLL+SRA to LB\n");
604 else
605 pr_debug("Convert LHU+SLL+SRA to LH\n");
606
607 v[ldop->i.rt].known = 0;
608 v[ldop->i.rt].sign = 0xffffff80 << (24 - curr->r.imm);
609 }
610 }
611
612 if (!ldop) {
613 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
614 curr->r.imm, curr->r.imm == 24 ? 'C' : 'S');
615
616 to_change->m.rs = curr->r.rt;
617 to_change->m.op = to_nop->r.imm == 24 ? OP_META_EXTC : OP_META_EXTS;
618 to_change->i.op = OP_META;
619 }
620
621 to_nop->opcode = 0;
622}
623
624static void
625lightrec_remove_useless_lui(struct block *block, unsigned int offset,
626 const struct constprop_data *v)
627{
628 struct opcode *list = block->opcode_list,
629 *op = &block->opcode_list[offset];
630 int reader;
631
632 if (!op_flag_sync(op->flags) && is_known(v, op->i.rt) &&
633 v[op->i.rt].value == op->i.imm << 16) {
634 pr_debug("Converting duplicated LUI to NOP\n");
635 op->opcode = 0x0;
636 return;
637 }
638
639 if (op->i.imm != 0 || op->i.rt == 0 || offset == block->nb_ops - 1)
640 return;
641
642 reader = find_next_reader(list, offset + 1, op->i.rt);
643 if (reader <= 0)
644 return;
645
646 if (opcode_writes_register(list[reader].c, op->i.rt) ||
647 reg_is_dead(list, reader, op->i.rt)) {
648 pr_debug("Removing useless LUI 0x0\n");
649
650 if (list[reader].i.rs == op->i.rt)
651 list[reader].i.rs = 0;
652 if (list[reader].i.op == OP_SPECIAL &&
653 list[reader].i.rt == op->i.rt)
654 list[reader].i.rt = 0;
655 op->opcode = 0x0;
656 }
657}
658
659static void lightrec_lui_to_movi(struct block *block, unsigned int offset)
660{
661 struct opcode *ori, *lui = &block->opcode_list[offset];
662 int next;
663
664 if (lui->i.op != OP_LUI)
665 return;
666
667 next = find_next_reader(block->opcode_list, offset + 1, lui->i.rt);
668 if (next > 0) {
669 ori = &block->opcode_list[next];
670
671 switch (ori->i.op) {
672 case OP_ORI:
673 case OP_ADDI:
674 case OP_ADDIU:
675 if (ori->i.rs == ori->i.rt && ori->i.imm) {
676 ori->flags |= LIGHTREC_MOVI;
677 lui->flags |= LIGHTREC_MOVI;
678 }
679 break;
680 }
681 }
682}
683
684static void lightrec_modify_lui(struct block *block, unsigned int offset)
685{
686 union code c, *lui = &block->opcode_list[offset].c;
687 bool stop = false, stop_next = false;
688 unsigned int i;
689
690 for (i = offset + 1; !stop && i < block->nb_ops; i++) {
691 c = block->opcode_list[i].c;
692 stop = stop_next;
693
694 if ((opcode_is_store(c) && c.i.rt == lui->i.rt)
695 || (!opcode_is_load(c) && opcode_reads_register(c, lui->i.rt)))
696 break;
697
698 if (opcode_writes_register(c, lui->i.rt)) {
699 if (c.i.op == OP_LWL || c.i.op == OP_LWR) {
700 /* LWL/LWR only partially write their target register;
701 * therefore the LUI should not write a different value. */
702 break;
703 }
704
705 pr_debug("Convert LUI at offset 0x%x to kuseg\n",
706 (i - 1) << 2);
707 lui->i.imm = kunseg(lui->i.imm << 16) >> 16;
708 break;
709 }
710
711 if (has_delay_slot(c))
712 stop_next = true;
713 }
714}
715
716static int lightrec_transform_branches(struct lightrec_state *state,
717 struct block *block)
718{
719 struct opcode *op;
720 unsigned int i;
721 s32 offset;
722
723 for (i = 0; i < block->nb_ops; i++) {
724 op = &block->opcode_list[i];
725
726 switch (op->i.op) {
727 case OP_J:
728 /* Transform J opcode into BEQ $zero, $zero if possible. */
729 offset = (s32)((block->pc & 0xf0000000) >> 2 | op->j.imm)
730 - (s32)(block->pc >> 2) - (s32)i - 1;
731
732 if (offset == (s16)offset) {
733 pr_debug("Transform J into BEQ $zero, $zero\n");
734 op->i.op = OP_BEQ;
735 op->i.rs = 0;
736 op->i.rt = 0;
737 op->i.imm = offset;
738
739 }
740 fallthrough;
741 default:
742 break;
743 }
744 }
745
746 return 0;
747}
748
749static inline bool is_power_of_two(u32 value)
750{
751 return popcount32(value) == 1;
752}
753
754static void lightrec_patch_known_zero(struct opcode *op,
755 const struct constprop_data *v)
756{
757 switch (op->i.op) {
758 case OP_SPECIAL:
759 switch (op->r.op) {
760 case OP_SPECIAL_JR:
761 case OP_SPECIAL_JALR:
762 case OP_SPECIAL_MTHI:
763 case OP_SPECIAL_MTLO:
764 if (is_known_zero(v, op->r.rs))
765 op->r.rs = 0;
766 break;
767 default:
768 if (is_known_zero(v, op->r.rs))
769 op->r.rs = 0;
770 fallthrough;
771 case OP_SPECIAL_SLL:
772 case OP_SPECIAL_SRL:
773 case OP_SPECIAL_SRA:
774 if (is_known_zero(v, op->r.rt))
775 op->r.rt = 0;
776 break;
777 case OP_SPECIAL_SYSCALL:
778 case OP_SPECIAL_BREAK:
779 case OP_SPECIAL_MFHI:
780 case OP_SPECIAL_MFLO:
781 break;
782 }
783 break;
784 case OP_CP0:
785 switch (op->r.rs) {
786 case OP_CP0_MTC0:
787 case OP_CP0_CTC0:
788 if (is_known_zero(v, op->r.rt))
789 op->r.rt = 0;
790 break;
791 default:
792 break;
793 }
794 break;
795 case OP_CP2:
796 if (op->r.op == OP_CP2_BASIC) {
797 switch (op->r.rs) {
798 case OP_CP2_BASIC_MTC2:
799 case OP_CP2_BASIC_CTC2:
800 if (is_known_zero(v, op->r.rt))
801 op->r.rt = 0;
802 break;
803 default:
804 break;
805 }
806 }
807 break;
808 case OP_BEQ:
809 case OP_BNE:
810 if (is_known_zero(v, op->i.rt))
811 op->i.rt = 0;
812 fallthrough;
813 case OP_REGIMM:
814 case OP_BLEZ:
815 case OP_BGTZ:
816 case OP_ADDI:
817 case OP_ADDIU:
818 case OP_SLTI:
819 case OP_SLTIU:
820 case OP_ANDI:
821 case OP_ORI:
822 case OP_XORI:
823 case OP_META_MULT2:
824 case OP_META_MULTU2:
825 case OP_META:
826 if (is_known_zero(v, op->m.rs))
827 op->m.rs = 0;
828 break;
829 case OP_SB:
830 case OP_SH:
831 case OP_SWL:
832 case OP_SW:
833 case OP_SWR:
834 case OP_META_SWU:
835 if (is_known_zero(v, op->i.rt))
836 op->i.rt = 0;
837 fallthrough;
838 case OP_LB:
839 case OP_LH:
840 case OP_LWL:
841 case OP_LW:
842 case OP_LBU:
843 case OP_LHU:
844 case OP_LWR:
845 case OP_LWC2:
846 case OP_SWC2:
847 case OP_META_LWU:
848 if (is_known(v, op->i.rs)
849 && kunseg(v[op->i.rs].value) == 0)
850 op->i.rs = 0;
851 break;
852 default:
853 break;
854 }
855}
856
857static void lightrec_reset_syncs(struct block *block)
858{
859 struct opcode *op, *list = block->opcode_list;
860 unsigned int i;
861 s32 offset;
862
863 for (i = 0; i < block->nb_ops; i++)
864 list[i].flags &= ~LIGHTREC_SYNC;
865
866 for (i = 0; i < block->nb_ops; i++) {
867 op = &list[i];
868
869 if (has_delay_slot(op->c)) {
870 if (op_flag_local_branch(op->flags)) {
871 offset = i + 1 - op_flag_no_ds(op->flags) + (s16)op->i.imm;
872 list[offset].flags |= LIGHTREC_SYNC;
873 }
874
875 if (op_flag_emulate_branch(op->flags) && i + 2 < block->nb_ops)
876 list[i + 2].flags |= LIGHTREC_SYNC;
877 }
878 }
879}
880
881static void maybe_remove_load_delay(struct opcode *op)
882{
883 if (op_flag_load_delay(op->flags) && opcode_is_load(op->c))
884 op->flags &= ~LIGHTREC_LOAD_DELAY;
885}
886
887static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
888{
889 struct opcode *op, *list = block->opcode_list;
890 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
891 unsigned int i;
892 bool local;
893 int idx;
894 u8 tmp;
895
896 for (i = 0; i < block->nb_ops; i++) {
897 op = &list[i];
898
899 lightrec_consts_propagate(block, i, v);
900
901 lightrec_patch_known_zero(op, v);
902
903 /* Transform all opcodes detected as useless to real NOPs
904 * (0x0: SLL r0, r0, #0) */
905 if (op->opcode != 0 && is_nop(op->c)) {
906 pr_debug("Converting useless opcode 0x%08x to NOP\n",
907 op->opcode);
908 op->opcode = 0x0;
909 }
910
911 if (!op->opcode)
912 continue;
913
914 switch (op->i.op) {
915 case OP_BEQ:
916 if (op->i.rs == op->i.rt ||
917 (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
918 v[op->i.rs].value == v[op->i.rt].value)) {
919 if (op->i.rs != op->i.rt)
920 pr_debug("Found always-taken BEQ\n");
921
922 op->i.rs = 0;
923 op->i.rt = 0;
924 } else if (v[op->i.rs].known & v[op->i.rt].known &
925 (v[op->i.rs].value ^ v[op->i.rt].value)) {
926 pr_debug("Found never-taken BEQ\n");
927
928 if (!op_flag_no_ds(op->flags))
929 maybe_remove_load_delay(&list[i + 1]);
930
931 local = op_flag_local_branch(op->flags);
932 op->opcode = 0;
933 op->flags = 0;
934
935 if (local)
936 lightrec_reset_syncs(block);
937 } else if (op->i.rs == 0) {
938 op->i.rs = op->i.rt;
939 op->i.rt = 0;
940 }
941 break;
942
943 case OP_BNE:
944 if (v[op->i.rs].known & v[op->i.rt].known &
945 (v[op->i.rs].value ^ v[op->i.rt].value)) {
946 pr_debug("Found always-taken BNE\n");
947
948 op->i.op = OP_BEQ;
949 op->i.rs = 0;
950 op->i.rt = 0;
951 } else if (is_known(v, op->i.rs) && is_known(v, op->i.rt) &&
952 v[op->i.rs].value == v[op->i.rt].value) {
953 pr_debug("Found never-taken BNE\n");
954
955 if (!op_flag_no_ds(op->flags))
956 maybe_remove_load_delay(&list[i + 1]);
957
958 local = op_flag_local_branch(op->flags);
959 op->opcode = 0;
960 op->flags = 0;
961
962 if (local)
963 lightrec_reset_syncs(block);
964 } else if (op->i.rs == 0) {
965 op->i.rs = op->i.rt;
966 op->i.rt = 0;
967 }
968 break;
969
970 case OP_BLEZ:
971 if (v[op->i.rs].known & BIT(31) &&
972 v[op->i.rs].value & BIT(31)) {
973 pr_debug("Found always-taken BLEZ\n");
974
975 op->i.op = OP_BEQ;
976 op->i.rs = 0;
977 op->i.rt = 0;
978 }
979 break;
980
981 case OP_BGTZ:
982 if (v[op->i.rs].known & BIT(31) &&
983 v[op->i.rs].value & BIT(31)) {
984 pr_debug("Found never-taken BGTZ\n");
985
986 if (!op_flag_no_ds(op->flags))
987 maybe_remove_load_delay(&list[i + 1]);
988
989 local = op_flag_local_branch(op->flags);
990 op->opcode = 0;
991 op->flags = 0;
992
993 if (local)
994 lightrec_reset_syncs(block);
995 }
996 break;
997
998 case OP_LUI:
999 if (i == 0 || !has_delay_slot(list[i - 1].c))
1000 lightrec_modify_lui(block, i);
1001 lightrec_remove_useless_lui(block, i, v);
1002 if (i == 0 || !has_delay_slot(list[i - 1].c))
1003 lightrec_lui_to_movi(block, i);
1004 break;
1005
1006 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
1007 * with register $zero to the MOV meta-opcode */
1008 case OP_ORI:
1009 case OP_ADDI:
1010 case OP_ADDIU:
1011 if (op->i.imm == 0) {
1012 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
1013 op->m.rd = op->i.rt;
1014 op->m.op = OP_META_MOV;
1015 op->i.op = OP_META;
1016 }
1017 break;
1018 case OP_ANDI:
1019 if (bits_are_known_zero(v, op->i.rs, ~op->i.imm)) {
1020 pr_debug("Found useless ANDI 0x%x\n", op->i.imm);
1021
1022 if (op->i.rs == op->i.rt) {
1023 op->opcode = 0;
1024 } else {
1025 op->m.rd = op->i.rt;
1026 op->m.op = OP_META_MOV;
1027 op->i.op = OP_META;
1028 }
1029 }
1030 break;
1031 case OP_LWL:
1032 case OP_LWR:
1033 if (i == 0 || !has_delay_slot(list[i - 1].c)) {
1034 idx = find_next_reader(list, i + 1, op->i.rt);
1035 if (idx > 0 && list[idx].i.op == (op->i.op ^ 0x4)
1036 && list[idx].i.rs == op->i.rs
1037 && list[idx].i.rt == op->i.rt
1038 && abs((s16)op->i.imm - (s16)list[idx].i.imm) == 3) {
1039 /* Replace a LWL/LWR combo with a META_LWU */
1040 if (op->i.op == OP_LWL)
1041 op->i.imm -= 3;
1042 op->i.op = OP_META_LWU;
1043 list[idx].opcode = 0;
1044 pr_debug("Convert LWL/LWR to LWU\n");
1045 }
1046 }
1047 break;
1048 case OP_SWL:
1049 case OP_SWR:
1050 if (i == 0 || !has_delay_slot(list[i - 1].c)) {
1051 idx = find_next_reader(list, i + 1, op->i.rt);
1052 if (idx > 0 && list[idx].i.op == (op->i.op ^ 0x4)
1053 && list[idx].i.rs == op->i.rs
1054 && list[idx].i.rt == op->i.rt
1055 && abs((s16)op->i.imm - (s16)list[idx].i.imm) == 3) {
1056 /* Replace a SWL/SWR combo with a META_SWU */
1057 if (op->i.op == OP_SWL)
1058 op->i.imm -= 3;
1059 op->i.op = OP_META_SWU;
1060 list[idx].opcode = 0;
1061 pr_debug("Convert SWL/SWR to SWU\n");
1062 }
1063 }
1064 break;
1065 case OP_REGIMM:
1066 switch (op->r.rt) {
1067 case OP_REGIMM_BLTZ:
1068 case OP_REGIMM_BGEZ:
1069 if (!(v[op->r.rs].known & BIT(31)))
1070 break;
1071
1072 if (!!(v[op->r.rs].value & BIT(31))
1073 ^ (op->r.rt == OP_REGIMM_BGEZ)) {
1074 pr_debug("Found always-taken BLTZ/BGEZ\n");
1075 op->i.op = OP_BEQ;
1076 op->i.rs = 0;
1077 op->i.rt = 0;
1078 } else {
1079 pr_debug("Found never-taken BLTZ/BGEZ\n");
1080
1081 if (!op_flag_no_ds(op->flags))
1082 maybe_remove_load_delay(&list[i + 1]);
1083
1084 local = op_flag_local_branch(op->flags);
1085 op->opcode = 0;
1086 op->flags = 0;
1087
1088 if (local)
1089 lightrec_reset_syncs(block);
1090 }
1091 break;
1092 case OP_REGIMM_BLTZAL:
1093 case OP_REGIMM_BGEZAL:
1094 /* TODO: Detect always-taken and replace with JAL */
1095 break;
1096 }
1097 break;
1098 case OP_SPECIAL:
1099 switch (op->r.op) {
1100 case OP_SPECIAL_SRAV:
1101 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1102 break;
1103
1104 pr_debug("Convert SRAV to SRA\n");
1105 op->r.imm = v[op->r.rs].value & 0x1f;
1106 op->r.op = OP_SPECIAL_SRA;
1107
1108 fallthrough;
1109 case OP_SPECIAL_SRA:
1110 if (op->r.imm == 0) {
1111 pr_debug("Convert SRA #0 to MOV\n");
1112 op->m.rs = op->r.rt;
1113 op->m.op = OP_META_MOV;
1114 op->i.op = OP_META;
1115 break;
1116 }
1117 break;
1118
1119 case OP_SPECIAL_SLLV:
1120 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1121 break;
1122
1123 pr_debug("Convert SLLV to SLL\n");
1124 op->r.imm = v[op->r.rs].value & 0x1f;
1125 op->r.op = OP_SPECIAL_SLL;
1126
1127 fallthrough;
1128 case OP_SPECIAL_SLL:
1129 if (op->r.imm == 0) {
1130 pr_debug("Convert SLL #0 to MOV\n");
1131 op->m.rs = op->r.rt;
1132 op->m.op = OP_META_MOV;
1133 op->i.op = OP_META;
1134 }
1135
1136 lightrec_optimize_sll_sra(block->opcode_list, i, v);
1137 break;
1138
1139 case OP_SPECIAL_SRLV:
1140 if ((v[op->r.rs].known & 0x1f) != 0x1f)
1141 break;
1142
1143 pr_debug("Convert SRLV to SRL\n");
1144 op->r.imm = v[op->r.rs].value & 0x1f;
1145 op->r.op = OP_SPECIAL_SRL;
1146
1147 fallthrough;
1148 case OP_SPECIAL_SRL:
1149 if (op->r.imm == 0) {
1150 pr_debug("Convert SRL #0 to MOV\n");
1151 op->m.rs = op->r.rt;
1152 op->m.op = OP_META_MOV;
1153 op->i.op = OP_META;
1154 }
1155 break;
1156
1157 case OP_SPECIAL_MULT:
1158 case OP_SPECIAL_MULTU:
1159 if (is_known(v, op->r.rs) &&
1160 is_power_of_two(v[op->r.rs].value)) {
1161 tmp = op->c.i.rs;
1162 op->c.i.rs = op->c.i.rt;
1163 op->c.i.rt = tmp;
1164 } else if (!is_known(v, op->r.rt) ||
1165 !is_power_of_two(v[op->r.rt].value)) {
1166 break;
1167 }
1168
1169 pr_debug("Multiply by power-of-two: %u\n",
1170 v[op->r.rt].value);
1171
1172 if (op->r.op == OP_SPECIAL_MULT)
1173 op->i.op = OP_META_MULT2;
1174 else
1175 op->i.op = OP_META_MULTU2;
1176
1177 op->r.op = ctz32(v[op->r.rt].value);
1178 break;
1179 case OP_SPECIAL_NOR:
1180 if (op->r.rs == 0 || op->r.rt == 0) {
1181 pr_debug("Convert NOR $zero to COM\n");
1182 op->i.op = OP_META;
1183 op->m.op = OP_META_COM;
1184 if (!op->m.rs)
1185 op->m.rs = op->r.rt;
1186 }
1187 break;
1188 case OP_SPECIAL_OR:
1189 case OP_SPECIAL_ADD:
1190 case OP_SPECIAL_ADDU:
1191 if (op->r.rs == 0) {
1192 pr_debug("Convert OR/ADD $zero to MOV\n");
1193 op->m.rs = op->r.rt;
1194 op->m.op = OP_META_MOV;
1195 op->i.op = OP_META;
1196 }
1197 fallthrough;
1198 case OP_SPECIAL_SUB:
1199 case OP_SPECIAL_SUBU:
1200 if (op->r.rt == 0) {
1201 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
1202 op->m.op = OP_META_MOV;
1203 op->i.op = OP_META;
1204 }
1205 fallthrough;
1206 default:
1207 break;
1208 }
1209 fallthrough;
1210 default:
1211 break;
1212 }
1213 }
1214
1215 return 0;
1216}
1217
1218static bool lightrec_can_switch_delay_slot(union code op, union code next_op)
1219{
1220 switch (op.i.op) {
1221 case OP_SPECIAL:
1222 switch (op.r.op) {
1223 case OP_SPECIAL_JALR:
1224 if (opcode_reads_register(next_op, op.r.rd) ||
1225 opcode_writes_register(next_op, op.r.rd))
1226 return false;
1227 fallthrough;
1228 case OP_SPECIAL_JR:
1229 if (opcode_writes_register(next_op, op.r.rs))
1230 return false;
1231 fallthrough;
1232 default:
1233 break;
1234 }
1235 fallthrough;
1236 case OP_J:
1237 break;
1238 case OP_JAL:
1239 if (opcode_reads_register(next_op, 31) ||
1240 opcode_writes_register(next_op, 31))
1241 return false;;
1242
1243 break;
1244 case OP_BEQ:
1245 case OP_BNE:
1246 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
1247 return false;
1248 fallthrough;
1249 case OP_BLEZ:
1250 case OP_BGTZ:
1251 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1252 return false;
1253 break;
1254 case OP_REGIMM:
1255 switch (op.r.rt) {
1256 case OP_REGIMM_BLTZAL:
1257 case OP_REGIMM_BGEZAL:
1258 if (opcode_reads_register(next_op, 31) ||
1259 opcode_writes_register(next_op, 31))
1260 return false;
1261 fallthrough;
1262 case OP_REGIMM_BLTZ:
1263 case OP_REGIMM_BGEZ:
1264 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
1265 return false;
1266 break;
1267 }
1268 fallthrough;
1269 default:
1270 break;
1271 }
1272
1273 return true;
1274}
1275
1276static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
1277{
1278 struct opcode *list, *next = &block->opcode_list[0];
1279 unsigned int i;
1280 union code op, next_op;
1281 u32 flags;
1282
1283 for (i = 0; i < block->nb_ops - 1; i++) {
1284 list = next;
1285 next = &block->opcode_list[i + 1];
1286 next_op = next->c;
1287 op = list->c;
1288
1289 if (!has_delay_slot(op) || op_flag_no_ds(list->flags) ||
1290 op_flag_emulate_branch(list->flags) ||
1291 op.opcode == 0 || next_op.opcode == 0)
1292 continue;
1293
1294 if (is_delay_slot(block->opcode_list, i))
1295 continue;
1296
1297 if (op_flag_sync(next->flags))
1298 continue;
1299
1300 if (op_flag_load_delay(next->flags) && opcode_is_load(next_op))
1301 continue;
1302
1303 if (!lightrec_can_switch_delay_slot(list->c, next_op))
1304 continue;
1305
1306 pr_debug("Swap branch and delay slot opcodes "
1307 "at offsets 0x%x / 0x%x\n",
1308 i << 2, (i + 1) << 2);
1309
1310 flags = next->flags | (list->flags & LIGHTREC_SYNC);
1311 list->c = next_op;
1312 next->c = op;
1313 next->flags = (list->flags | LIGHTREC_NO_DS) & ~LIGHTREC_SYNC;
1314 list->flags = flags | LIGHTREC_NO_DS;
1315 }
1316
1317 return 0;
1318}
1319
1320static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1321 struct block *block)
1322{
1323 struct opcode *op, *list = block->opcode_list, *next = &list[0];
1324 unsigned int i;
1325 int ret = 0;
1326
1327 for (i = 0; i < block->nb_ops - 1; i++) {
1328 op = next;
1329 next = &list[i + 1];
1330
1331 if (!has_delay_slot(op->c) ||
1332 (!has_delay_slot(next->c) &&
1333 !opcode_is_mfc(next->c) &&
1334 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1335 continue;
1336
1337 if (op->c.opcode == next->c.opcode) {
1338 /* The delay slot is the exact same opcode as the branch
1339 * opcode: this is effectively a NOP */
1340 next->c.opcode = 0;
1341 continue;
1342 }
1343
1344 op->flags |= LIGHTREC_EMULATE_BRANCH;
1345
1346 if (OPT_LOCAL_BRANCHES && i + 2 < block->nb_ops) {
1347 /* The interpreter will only emulate the branch, then
1348 * return to the compiled code. Add a SYNC after the
1349 * branch + delay slot in the case where the branch
1350 * was not taken. */
1351 list[i + 2].flags |= LIGHTREC_SYNC;
1352 }
1353 }
1354
1355 return ret;
1356}
1357
1358static bool is_local_branch(const struct block *block, unsigned int idx)
1359{
1360 const struct opcode *op = &block->opcode_list[idx];
1361 s32 offset;
1362
1363 switch (op->c.i.op) {
1364 case OP_BEQ:
1365 case OP_BNE:
1366 case OP_BLEZ:
1367 case OP_BGTZ:
1368 case OP_REGIMM:
1369 offset = idx + 1 + (s16)op->c.i.imm;
1370 if (offset >= 0 && offset < block->nb_ops)
1371 return true;
1372 fallthrough;
1373 default:
1374 return false;
1375 }
1376}
1377
1378static int lightrec_handle_load_delays(struct lightrec_state *state,
1379 struct block *block)
1380{
1381 struct opcode *op, *list = block->opcode_list;
1382 unsigned int i;
1383 s16 imm;
1384
1385 for (i = 0; i < block->nb_ops; i++) {
1386 op = &list[i];
1387
1388 if (!opcode_is_load(op->c) || !op->c.i.rt || op->c.i.op == OP_LWC2)
1389 continue;
1390
1391 if (!is_delay_slot(list, i)) {
1392 /* Only handle load delays in delay slots.
1393 * PSX games never abused load delay slots otherwise. */
1394 continue;
1395 }
1396
1397 if (is_local_branch(block, i - 1)) {
1398 imm = (s16)list[i - 1].c.i.imm;
1399
1400 if (!opcode_reads_register(list[i + imm].c, op->c.i.rt)) {
1401 /* The target opcode of the branch is inside
1402 * the block, and it does not read the register
1403 * written to by the load opcode; we can ignore
1404 * the load delay. */
1405 continue;
1406 }
1407 }
1408
1409 op->flags |= LIGHTREC_LOAD_DELAY;
1410 }
1411
1412 return 0;
1413}
1414
1415static int lightrec_swap_load_delays(struct lightrec_state *state,
1416 struct block *block)
1417{
1418 unsigned int i;
1419 union code c, next;
1420 bool in_ds = false, skip_next = false;
1421 struct opcode op;
1422
1423 if (block->nb_ops < 2)
1424 return 0;
1425
1426 for (i = 0; i < block->nb_ops - 2; i++) {
1427 c = block->opcode_list[i].c;
1428
1429 if (skip_next) {
1430 skip_next = false;
1431 } else if (!in_ds && opcode_is_load(c) && c.i.op != OP_LWC2) {
1432 next = block->opcode_list[i + 1].c;
1433
1434 switch (next.i.op) {
1435 case OP_LWL:
1436 case OP_LWR:
1437 case OP_REGIMM:
1438 case OP_BEQ:
1439 case OP_BNE:
1440 case OP_BLEZ:
1441 case OP_BGTZ:
1442 continue;
1443 }
1444
1445 if (opcode_reads_register(next, c.i.rt)
1446 && !opcode_writes_register(next, c.i.rs)) {
1447 pr_debug("Swapping opcodes at offset 0x%x to "
1448 "respect load delay\n", i << 2);
1449
1450 op = block->opcode_list[i];
1451 block->opcode_list[i] = block->opcode_list[i + 1];
1452 block->opcode_list[i + 1] = op;
1453 skip_next = true;
1454 }
1455 }
1456
1457 in_ds = has_delay_slot(c);
1458 }
1459
1460 return 0;
1461}
1462
1463static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1464{
1465 const struct opcode *ds;
1466 struct opcode *list;
1467 unsigned int i;
1468 s32 offset;
1469
1470 for (i = 0; i < block->nb_ops; i++) {
1471 list = &block->opcode_list[i];
1472
1473 if (should_emulate(list) || !is_local_branch(block, i))
1474 continue;
1475
1476 offset = i + 1 + (s16)list->c.i.imm;
1477
1478 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1479
1480 ds = get_delay_slot(block->opcode_list, i);
1481 if (op_flag_load_delay(ds->flags) && opcode_is_load(ds->c)) {
1482 pr_debug("Branch delay slot has a load delay - skip\n");
1483 continue;
1484 }
1485
1486 if (should_emulate(&block->opcode_list[offset])) {
1487 pr_debug("Branch target must be emulated - skip\n");
1488 continue;
1489 }
1490
1491 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1492 pr_debug("Branch target is a delay slot - skip\n");
1493 continue;
1494 }
1495
1496 list->flags |= LIGHTREC_LOCAL_BRANCH;
1497 }
1498
1499 lightrec_reset_syncs(block);
1500
1501 return 0;
1502}
1503
1504bool has_delay_slot(union code op)
1505{
1506 switch (op.i.op) {
1507 case OP_SPECIAL:
1508 switch (op.r.op) {
1509 case OP_SPECIAL_JR:
1510 case OP_SPECIAL_JALR:
1511 return true;
1512 default:
1513 return false;
1514 }
1515 case OP_J:
1516 case OP_JAL:
1517 case OP_BEQ:
1518 case OP_BNE:
1519 case OP_BLEZ:
1520 case OP_BGTZ:
1521 case OP_REGIMM:
1522 return true;
1523 default:
1524 return false;
1525 }
1526}
1527
1528bool is_delay_slot(const struct opcode *list, unsigned int offset)
1529{
1530 return offset > 0
1531 && !op_flag_no_ds(list[offset - 1].flags)
1532 && has_delay_slot(list[offset - 1].c);
1533}
1534
1535bool should_emulate(const struct opcode *list)
1536{
1537 return op_flag_emulate_branch(list->flags) && has_delay_slot(list->c);
1538}
1539
1540static bool op_writes_rd(union code c)
1541{
1542 switch (c.i.op) {
1543 case OP_SPECIAL:
1544 case OP_META:
1545 return true;
1546 default:
1547 return false;
1548 }
1549}
1550
1551static void lightrec_add_reg_op(struct opcode *op, u8 reg, u32 reg_op)
1552{
1553 if (op_writes_rd(op->c) && reg == op->r.rd)
1554 op->flags |= LIGHTREC_REG_RD(reg_op);
1555 else if (op->i.rs == reg)
1556 op->flags |= LIGHTREC_REG_RS(reg_op);
1557 else if (op->i.rt == reg)
1558 op->flags |= LIGHTREC_REG_RT(reg_op);
1559 else
1560 pr_debug("Cannot add unload/clean/discard flag: "
1561 "opcode does not touch register %s!\n",
1562 lightrec_reg_name(reg));
1563}
1564
1565static void lightrec_add_unload(struct opcode *op, u8 reg)
1566{
1567 lightrec_add_reg_op(op, reg, LIGHTREC_REG_UNLOAD);
1568}
1569
1570static void lightrec_add_discard(struct opcode *op, u8 reg)
1571{
1572 lightrec_add_reg_op(op, reg, LIGHTREC_REG_DISCARD);
1573}
1574
1575static void lightrec_add_clean(struct opcode *op, u8 reg)
1576{
1577 lightrec_add_reg_op(op, reg, LIGHTREC_REG_CLEAN);
1578}
1579
1580static void
1581lightrec_early_unload_sync(struct opcode *list, s16 *last_r, s16 *last_w)
1582{
1583 unsigned int reg;
1584 s16 offset;
1585
1586 for (reg = 0; reg < 34; reg++) {
1587 offset = s16_max(last_w[reg], last_r[reg]);
1588
1589 if (offset >= 0)
1590 lightrec_add_unload(&list[offset], reg);
1591 }
1592
1593 memset(last_r, 0xff, sizeof(*last_r) * 34);
1594 memset(last_w, 0xff, sizeof(*last_w) * 34);
1595}
1596
1597static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1598{
1599 u16 i, offset;
1600 struct opcode *op;
1601 s16 last_r[34], last_w[34], last_sync = 0, next_sync = 0;
1602 u64 mask_r, mask_w, dirty = 0, loaded = 0;
1603 u8 reg, load_delay_reg = 0;
1604
1605 memset(last_r, 0xff, sizeof(last_r));
1606 memset(last_w, 0xff, sizeof(last_w));
1607
1608 /*
1609 * Clean if:
1610 * - the register is dirty, and is read again after a branch opcode
1611 *
1612 * Unload if:
1613 * - the register is dirty or loaded, and is not read again
1614 * - the register is dirty or loaded, and is written again after a branch opcode
1615 * - the next opcode has the SYNC flag set
1616 *
1617 * Discard if:
1618 * - the register is dirty or loaded, and is written again
1619 */
1620
1621 for (i = 0; i < block->nb_ops; i++) {
1622 op = &block->opcode_list[i];
1623
1624 if (OPT_HANDLE_LOAD_DELAYS && load_delay_reg) {
1625 /* Handle delayed register write from load opcodes in
1626 * delay slots */
1627 last_w[load_delay_reg] = i;
1628 load_delay_reg = 0;
1629 }
1630
1631 if (op_flag_sync(op->flags) || should_emulate(op)) {
1632 /* The next opcode has the SYNC flag set, or is a branch
1633 * that should be emulated: unload all registers. */
1634 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1635 dirty = 0;
1636 loaded = 0;
1637 }
1638
1639 if (next_sync == i) {
1640 last_sync = i;
1641 pr_debug("Last sync: 0x%x\n", last_sync << 2);
1642 }
1643
1644 if (has_delay_slot(op->c)) {
1645 next_sync = i + 1 + !op_flag_no_ds(op->flags);
1646 pr_debug("Next sync: 0x%x\n", next_sync << 2);
1647 }
1648
1649 mask_r = opcode_read_mask(op->c);
1650 mask_w = opcode_write_mask(op->c);
1651
1652 if (op_flag_load_delay(op->flags) && opcode_is_load(op->c)) {
1653 /* If we have a load opcode in a delay slot, its target
1654 * register is actually not written there but at a
1655 * later point, in the dispatcher. Prevent the algorithm
1656 * from discarding its previous value. */
1657 load_delay_reg = op->c.i.rt;
1658 mask_w &= ~BIT(op->c.i.rt);
1659 }
1660
1661 for (reg = 0; reg < 34; reg++) {
1662 if (mask_r & BIT(reg)) {
1663 if (dirty & BIT(reg) && last_w[reg] < last_sync) {
1664 /* The register is dirty, and is read
1665 * again after a branch: clean it */
1666
1667 lightrec_add_clean(&block->opcode_list[last_w[reg]], reg);
1668 dirty &= ~BIT(reg);
1669 loaded |= BIT(reg);
1670 }
1671
1672 last_r[reg] = i;
1673 }
1674
1675 if (mask_w & BIT(reg)) {
1676 if ((dirty & BIT(reg) && last_w[reg] < last_sync) ||
1677 (loaded & BIT(reg) && last_r[reg] < last_sync)) {
1678 /* The register is dirty or loaded, and
1679 * is written again after a branch:
1680 * unload it */
1681
1682 offset = s16_max(last_w[reg], last_r[reg]);
1683 lightrec_add_unload(&block->opcode_list[offset], reg);
1684 dirty &= ~BIT(reg);
1685 loaded &= ~BIT(reg);
1686 } else if (!(mask_r & BIT(reg)) &&
1687 ((dirty & BIT(reg) && last_w[reg] > last_sync) ||
1688 (loaded & BIT(reg) && last_r[reg] > last_sync))) {
1689 /* The register is dirty or loaded, and
1690 * is written again: discard it */
1691
1692 offset = s16_max(last_w[reg], last_r[reg]);
1693 lightrec_add_discard(&block->opcode_list[offset], reg);
1694 dirty &= ~BIT(reg);
1695 loaded &= ~BIT(reg);
1696 }
1697
1698 last_w[reg] = i;
1699 }
1700
1701 }
1702
1703 dirty |= mask_w;
1704 loaded |= mask_r;
1705 }
1706
1707 /* Unload all registers that are dirty or loaded at the end of block. */
1708 lightrec_early_unload_sync(block->opcode_list, last_r, last_w);
1709
1710 return 0;
1711}
1712
1713static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1714{
1715 struct opcode *list;
1716 enum psx_map psx_map;
1717 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
1718 unsigned int i;
1719 u32 val, kunseg_val;
1720 bool no_mask;
1721
1722 for (i = 0; i < block->nb_ops; i++) {
1723 list = &block->opcode_list[i];
1724
1725 lightrec_consts_propagate(block, i, v);
1726
1727 switch (list->i.op) {
1728 case OP_SB:
1729 case OP_SH:
1730 case OP_SW:
1731 /* Mark all store operations that target $sp or $gp
1732 * as not requiring code invalidation. This is based
1733 * on the heuristic that stores using one of these
1734 * registers as address will never hit a code page. */
1735 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1736 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1737 pr_debug("Flaging opcode 0x%08x as not requiring invalidation\n",
1738 list->opcode);
1739 list->flags |= LIGHTREC_NO_INVALIDATE;
1740 }
1741
1742 /* Detect writes whose destination address is inside the
1743 * current block, using constant propagation. When these
1744 * occur, we mark the blocks as not compilable. */
1745 if (is_known(v, list->i.rs) &&
1746 kunseg(v[list->i.rs].value) >= kunseg(block->pc) &&
1747 kunseg(v[list->i.rs].value) < (kunseg(block->pc) + block->nb_ops * 4)) {
1748 pr_debug("Self-modifying block detected\n");
1749 block_set_flags(block, BLOCK_NEVER_COMPILE);
1750 list->flags |= LIGHTREC_SMC;
1751 }
1752 fallthrough;
1753 case OP_SWL:
1754 case OP_SWR:
1755 case OP_SWC2:
1756 case OP_LB:
1757 case OP_LBU:
1758 case OP_LH:
1759 case OP_LHU:
1760 case OP_LW:
1761 case OP_LWL:
1762 case OP_LWR:
1763 case OP_LWC2:
1764 if (v[list->i.rs].known | v[list->i.rs].sign) {
1765 psx_map = lightrec_get_constprop_map(state, v,
1766 list->i.rs,
1767 (s16) list->i.imm);
1768
1769 if (psx_map != PSX_MAP_UNKNOWN && !is_known(v, list->i.rs))
1770 pr_debug("Detected map thanks to bit-level const propagation!\n");
1771
1772 list->flags &= ~LIGHTREC_IO_MASK;
1773
1774 val = v[list->i.rs].value + (s16) list->i.imm;
1775 kunseg_val = kunseg(val);
1776
1777 no_mask = (v[list->i.rs].known & ~v[list->i.rs].value
1778 & 0xe0000000) == 0xe0000000;
1779
1780 switch (psx_map) {
1781 case PSX_MAP_KERNEL_USER_RAM:
1782 if (no_mask)
1783 list->flags |= LIGHTREC_NO_MASK;
1784 fallthrough;
1785 case PSX_MAP_MIRROR1:
1786 case PSX_MAP_MIRROR2:
1787 case PSX_MAP_MIRROR3:
1788 pr_debug("Flaging opcode %u as RAM access\n", i);
1789 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_RAM);
1790 if (no_mask && state->mirrors_mapped)
1791 list->flags |= LIGHTREC_NO_MASK;
1792 break;
1793 case PSX_MAP_BIOS:
1794 pr_debug("Flaging opcode %u as BIOS access\n", i);
1795 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_BIOS);
1796 if (no_mask)
1797 list->flags |= LIGHTREC_NO_MASK;
1798 break;
1799 case PSX_MAP_SCRATCH_PAD:
1800 pr_debug("Flaging opcode %u as scratchpad access\n", i);
1801 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_SCRATCH);
1802 if (no_mask)
1803 list->flags |= LIGHTREC_NO_MASK;
1804
1805 /* Consider that we're never going to run code from
1806 * the scratchpad. */
1807 list->flags |= LIGHTREC_NO_INVALIDATE;
1808 break;
1809 case PSX_MAP_HW_REGISTERS:
1810 if (state->ops.hw_direct &&
1811 state->ops.hw_direct(kunseg_val,
1812 opcode_is_store(list->c),
1813 opcode_get_io_size(list->c))) {
1814 pr_debug("Flagging opcode %u as direct I/O access\n",
1815 i);
1816 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT_HW);
1817
1818 if (no_mask)
1819 list->flags |= LIGHTREC_NO_MASK;
1820 } else {
1821 pr_debug("Flagging opcode %u as I/O access\n",
1822 i);
1823 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_HW);
1824 }
1825 break;
1826 default:
1827 break;
1828 }
1829 }
1830
1831 if (!LIGHTREC_FLAGS_GET_IO_MODE(list->flags)
1832 && list->i.rs >= 28 && list->i.rs <= 29
1833 && !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1834 /* Assume that all I/O operations that target
1835 * $sp or $gp will always only target a mapped
1836 * memory (RAM, BIOS, scratchpad). */
1837 if (state->opt_flags & LIGHTREC_OPT_SP_GP_HIT_RAM)
1838 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_RAM);
1839 else
1840 list->flags |= LIGHTREC_IO_MODE(LIGHTREC_IO_DIRECT);
1841 }
1842
1843 fallthrough;
1844 default:
1845 break;
1846 }
1847 }
1848
1849 return 0;
1850}
1851
1852static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1853 const struct opcode *last,
1854 u32 mask, bool sync, bool mflo, bool another)
1855{
1856 const struct opcode *op, *next = &block->opcode_list[offset];
1857 u32 old_mask;
1858 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1859 u16 branch_offset;
1860 unsigned int i;
1861
1862 for (i = offset; i < block->nb_ops; i++) {
1863 op = next;
1864 next = &block->opcode_list[i + 1];
1865 old_mask = mask;
1866
1867 /* If any other opcode writes or reads to the register
1868 * we'd use, then we cannot use it anymore. */
1869 mask |= opcode_read_mask(op->c);
1870 mask |= opcode_write_mask(op->c);
1871
1872 if (op_flag_sync(op->flags))
1873 sync = true;
1874
1875 switch (op->i.op) {
1876 case OP_BEQ:
1877 case OP_BNE:
1878 case OP_BLEZ:
1879 case OP_BGTZ:
1880 case OP_REGIMM:
1881 /* TODO: handle backwards branches too */
1882 if (!last && op_flag_local_branch(op->flags) &&
1883 (s16)op->c.i.imm >= 0) {
1884 branch_offset = i + 1 + (s16)op->c.i.imm
1885 - !!op_flag_no_ds(op->flags);
1886
1887 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1888 mask, sync, mflo, false);
1889 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1890 mask, sync, mflo, false);
1891 if (reg > 0 && reg == reg2)
1892 return reg;
1893 if (!reg && !reg2)
1894 return 0;
1895 }
1896
1897 return mflo ? REG_LO : REG_HI;
1898 case OP_META_MULT2:
1899 case OP_META_MULTU2:
1900 return 0;
1901 case OP_SPECIAL:
1902 switch (op->r.op) {
1903 case OP_SPECIAL_MULT:
1904 case OP_SPECIAL_MULTU:
1905 case OP_SPECIAL_DIV:
1906 case OP_SPECIAL_DIVU:
1907 return 0;
1908 case OP_SPECIAL_MTHI:
1909 if (!mflo)
1910 return 0;
1911 continue;
1912 case OP_SPECIAL_MTLO:
1913 if (mflo)
1914 return 0;
1915 continue;
1916 case OP_SPECIAL_JR:
1917 if (op->r.rs != 31)
1918 return reg;
1919
1920 if (!sync && !op_flag_no_ds(op->flags) &&
1921 (next->i.op == OP_SPECIAL) &&
1922 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1923 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1924 return next->r.rd;
1925
1926 return 0;
1927 case OP_SPECIAL_JALR:
1928 return reg;
1929 case OP_SPECIAL_MFHI:
1930 if (!mflo) {
1931 if (another)
1932 return op->r.rd;
1933 /* Must use REG_HI if there is another MFHI target*/
1934 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1935 0, sync, mflo, true);
1936 if (reg2 > 0 && reg2 != REG_HI)
1937 return REG_HI;
1938
1939 if (!sync && !(old_mask & BIT(op->r.rd)))
1940 return op->r.rd;
1941 else
1942 return REG_HI;
1943 }
1944 continue;
1945 case OP_SPECIAL_MFLO:
1946 if (mflo) {
1947 if (another)
1948 return op->r.rd;
1949 /* Must use REG_LO if there is another MFLO target*/
1950 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1951 0, sync, mflo, true);
1952 if (reg2 > 0 && reg2 != REG_LO)
1953 return REG_LO;
1954
1955 if (!sync && !(old_mask & BIT(op->r.rd)))
1956 return op->r.rd;
1957 else
1958 return REG_LO;
1959 }
1960 continue;
1961 default:
1962 break;
1963 }
1964
1965 fallthrough;
1966 default:
1967 continue;
1968 }
1969 }
1970
1971 return reg;
1972}
1973
1974static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1975 u16 last, bool lo)
1976{
1977 unsigned int i;
1978 u32 branch_offset;
1979
1980 /* This function will remove the following MFLO/MFHI. It must be called
1981 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1982
1983 for (i = offset; i < last; i++) {
1984 struct opcode *op = &block->opcode_list[i];
1985
1986 switch (op->i.op) {
1987 case OP_BEQ:
1988 case OP_BNE:
1989 case OP_BLEZ:
1990 case OP_BGTZ:
1991 case OP_REGIMM:
1992 /* TODO: handle backwards branches too */
1993 if (op_flag_local_branch(op->flags) && (s16)op->c.i.imm >= 0) {
1994 branch_offset = i + 1 + (s16)op->c.i.imm
1995 - !!op_flag_no_ds(op->flags);
1996
1997 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1998 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1999 }
2000 break;
2001
2002 case OP_SPECIAL:
2003 if (lo && op->r.op == OP_SPECIAL_MFLO) {
2004 pr_debug("Removing MFLO opcode at offset 0x%x\n",
2005 i << 2);
2006 op->opcode = 0;
2007 return;
2008 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
2009 pr_debug("Removing MFHI opcode at offset 0x%x\n",
2010 i << 2);
2011 op->opcode = 0;
2012 return;
2013 }
2014
2015 fallthrough;
2016 default:
2017 break;
2018 }
2019 }
2020}
2021
2022static bool lightrec_always_skip_div_check(void)
2023{
2024#ifdef __mips__
2025 return true;
2026#else
2027 return false;
2028#endif
2029}
2030
2031static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
2032{
2033 struct opcode *list = NULL;
2034 struct constprop_data v[32] = LIGHTREC_CONSTPROP_INITIALIZER;
2035 u8 reg_hi, reg_lo;
2036 unsigned int i;
2037
2038 for (i = 0; i < block->nb_ops - 1; i++) {
2039 list = &block->opcode_list[i];
2040
2041 lightrec_consts_propagate(block, i, v);
2042
2043 switch (list->i.op) {
2044 case OP_SPECIAL:
2045 switch (list->r.op) {
2046 case OP_SPECIAL_DIV:
2047 case OP_SPECIAL_DIVU:
2048 /* If we are dividing by a non-zero constant, don't
2049 * emit the div-by-zero check. */
2050 if (lightrec_always_skip_div_check() ||
2051 (v[list->r.rt].known & v[list->r.rt].value)) {
2052 list->flags |= LIGHTREC_NO_DIV_CHECK;
2053 }
2054 fallthrough;
2055 case OP_SPECIAL_MULT:
2056 case OP_SPECIAL_MULTU:
2057 break;
2058 default:
2059 continue;
2060 }
2061 fallthrough;
2062 case OP_META_MULT2:
2063 case OP_META_MULTU2:
2064 break;
2065 default:
2066 continue;
2067 }
2068
2069 /* Don't support opcodes in delay slots */
2070 if (is_delay_slot(block->opcode_list, i) ||
2071 op_flag_no_ds(list->flags)) {
2072 continue;
2073 }
2074
2075 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
2076 if (reg_lo == 0) {
2077 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
2078 " not writing LO\n", i << 2);
2079 list->flags |= LIGHTREC_NO_LO;
2080 }
2081
2082 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
2083 if (reg_hi == 0) {
2084 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
2085 " not writing HI\n", i << 2);
2086 list->flags |= LIGHTREC_NO_HI;
2087 }
2088
2089 if (!reg_lo && !reg_hi) {
2090 pr_debug("Both LO/HI unused in this block, they will "
2091 "probably be used in parent block - removing "
2092 "flags.\n");
2093 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
2094 }
2095
2096 if (reg_lo > 0 && reg_lo != REG_LO) {
2097 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
2098 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
2099
2100 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
2101 list->r.rd = reg_lo;
2102 } else {
2103 list->r.rd = 0;
2104 }
2105
2106 if (reg_hi > 0 && reg_hi != REG_HI) {
2107 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
2108 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
2109
2110 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
2111 list->r.imm = reg_hi;
2112 } else {
2113 list->r.imm = 0;
2114 }
2115 }
2116
2117 return 0;
2118}
2119
2120static bool remove_div_sequence(struct block *block, unsigned int offset)
2121{
2122 struct opcode *op;
2123 unsigned int i, found = 0;
2124
2125 /*
2126 * Scan for the zero-checking sequence that GCC automatically introduced
2127 * after most DIV/DIVU opcodes. This sequence checks the value of the
2128 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
2129 * handler to crash the PS1.
2130 *
2131 * For DIV opcodes, this sequence additionally checks that the signed
2132 * operation does not overflow.
2133 *
2134 * With the assumption that the games never crashed the PS1, we can
2135 * therefore assume that the games never divided by zero or overflowed,
2136 * and these sequences can be removed.
2137 */
2138
2139 for (i = offset; i < block->nb_ops; i++) {
2140 op = &block->opcode_list[i];
2141
2142 if (!found) {
2143 if (op->i.op == OP_SPECIAL &&
2144 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
2145 break;
2146
2147 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
2148 /* BNE ???, zero, +8 */
2149 found++;
2150 } else {
2151 offset++;
2152 }
2153 } else if (found == 1 && !op->opcode) {
2154 /* NOP */
2155 found++;
2156 } else if (found == 2 && op->opcode == 0x0007000d) {
2157 /* BREAK 0x1c00 */
2158 found++;
2159 } else if (found == 3 && op->opcode == 0x2401ffff) {
2160 /* LI at, -1 */
2161 found++;
2162 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
2163 /* BNE ???, at, +16 */
2164 found++;
2165 } else if (found == 5 && op->opcode == 0x3c018000) {
2166 /* LUI at, 0x8000 */
2167 found++;
2168 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
2169 /* BNE ???, at, +16 */
2170 found++;
2171 } else if (found == 7 && !op->opcode) {
2172 /* NOP */
2173 found++;
2174 } else if (found == 8 && op->opcode == 0x0006000d) {
2175 /* BREAK 0x1800 */
2176 found++;
2177 break;
2178 } else {
2179 break;
2180 }
2181 }
2182
2183 if (found >= 3) {
2184 if (found != 9)
2185 found = 3;
2186
2187 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
2188 found == 9 ? "" : "U", offset << 2);
2189
2190 for (i = 0; i < found; i++)
2191 block->opcode_list[offset + i].opcode = 0;
2192
2193 return true;
2194 }
2195
2196 return false;
2197}
2198
2199static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
2200 struct block *block)
2201{
2202 struct opcode *op;
2203 unsigned int i;
2204
2205 for (i = 0; i < block->nb_ops; i++) {
2206 op = &block->opcode_list[i];
2207
2208 if (op->i.op == OP_SPECIAL &&
2209 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
2210 remove_div_sequence(block, i + 1))
2211 op->flags |= LIGHTREC_NO_DIV_CHECK;
2212 }
2213
2214 return 0;
2215}
2216
2217static const u32 memset_code[] = {
2218 0x10a00006, // beqz a1, 2f
2219 0x24a2ffff, // addiu v0,a1,-1
2220 0x2403ffff, // li v1,-1
2221 0xac800000, // 1: sw zero,0(a0)
2222 0x2442ffff, // addiu v0,v0,-1
2223 0x1443fffd, // bne v0,v1, 1b
2224 0x24840004, // addiu a0,a0,4
2225 0x03e00008, // 2: jr ra
2226 0x00000000, // nop
2227};
2228
2229static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
2230{
2231 unsigned int i;
2232 union code c;
2233
2234 for (i = 0; i < block->nb_ops; i++) {
2235 c = block->opcode_list[i].c;
2236
2237 if (c.opcode != memset_code[i])
2238 return 0;
2239
2240 if (i == ARRAY_SIZE(memset_code) - 1) {
2241 /* success! */
2242 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
2243 block_set_flags(block,
2244 BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE);
2245
2246 /* Return non-zero to skip other optimizers. */
2247 return 1;
2248 }
2249 }
2250
2251 return 0;
2252}
2253
2254static int lightrec_test_preload_pc(struct lightrec_state *state, struct block *block)
2255{
2256 unsigned int i;
2257 union code c;
2258 u32 flags;
2259
2260 for (i = 0; i < block->nb_ops; i++) {
2261 c = block->opcode_list[i].c;
2262 flags = block->opcode_list[i].flags;
2263
2264 if (op_flag_sync(flags))
2265 break;
2266
2267 switch (c.i.op) {
2268 case OP_J:
2269 case OP_JAL:
2270 block->flags |= BLOCK_PRELOAD_PC;
2271 return 0;
2272
2273 case OP_REGIMM:
2274 switch (c.r.rt) {
2275 case OP_REGIMM_BLTZAL:
2276 case OP_REGIMM_BGEZAL:
2277 block->flags |= BLOCK_PRELOAD_PC;
2278 return 0;
2279 default:
2280 break;
2281 }
2282 fallthrough;
2283 case OP_BEQ:
2284 case OP_BNE:
2285 case OP_BLEZ:
2286 case OP_BGTZ:
2287 if (!op_flag_local_branch(flags)) {
2288 block->flags |= BLOCK_PRELOAD_PC;
2289 return 0;
2290 }
2291
2292 case OP_SPECIAL:
2293 switch (c.r.op) {
2294 case OP_SPECIAL_JALR:
2295 if (c.r.rd) {
2296 block->flags |= BLOCK_PRELOAD_PC;
2297 return 0;
2298 }
2299 break;
2300 case OP_SPECIAL_SYSCALL:
2301 case OP_SPECIAL_BREAK:
2302 block->flags |= BLOCK_PRELOAD_PC;
2303 return 0;
2304 default:
2305 break;
2306 }
2307 break;
2308 }
2309 }
2310
2311 return 0;
2312}
2313
2314static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
2315 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
2316 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
2317 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
2318 IF_OPT(OPT_HANDLE_LOAD_DELAYS, &lightrec_handle_load_delays),
2319 IF_OPT(OPT_HANDLE_LOAD_DELAYS, &lightrec_swap_load_delays),
2320 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_branches),
2321 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
2322 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
2323 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
2324 IF_OPT(OPT_FLAG_IO, &lightrec_flag_io),
2325 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
2326 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
2327 IF_OPT(OPT_PRELOAD_PC, &lightrec_test_preload_pc),
2328};
2329
2330int lightrec_optimize(struct lightrec_state *state, struct block *block)
2331{
2332 unsigned int i;
2333 int ret;
2334
2335 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
2336 if (lightrec_optimizers[i]) {
2337 ret = (*lightrec_optimizers[i])(state, block);
2338 if (ret)
2339 return ret;
2340 }
2341 }
2342
2343 return 0;
2344}