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