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