notaz.gp2x.de / pcsx_rearmed.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #644 from pcercuei/update-lightrec-20220409
[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
98fa08a5 6#include "lightrec-config.h"
d16005f8
PC		 7#include "disassembler.h"
8#include "lightrec.h"
9#include "memmanager.h"
10#include "optimizer.h"
11#include "regcache.h"
12
13#include <errno.h>
14#include <stdbool.h>
15#include <stdlib.h>
98fa08a5
PC		 16#include <string.h>
17
18#define IF_OPT(opt, ptr) ((opt) ? (ptr) : NULL)
d16005f8
PC		 19
20struct optimizer_list {
21 void (**optimizers)(struct opcode *);
22 unsigned int nb_optimizers;
23};
24
98fa08a5
PC		 25static bool is_nop(union code op);
26
27bool is_unconditional_jump(union code c)
28{
29 switch (c.i.op) {
30 case OP_SPECIAL:
31 return c.r.op == OP_SPECIAL_JR || c.r.op == OP_SPECIAL_JALR;
32 case OP_J:
33 case OP_JAL:
34 return true;
35 case OP_BEQ:
36 case OP_BLEZ:
37 return c.i.rs == c.i.rt;
38 case OP_REGIMM:
39 return (c.r.rt == OP_REGIMM_BGEZ ||
40 c.r.rt == OP_REGIMM_BGEZAL) && c.i.rs == 0;
41 default:
42 return false;
43 }
44}
45
46bool is_syscall(union code c)
47{
48 return (c.i.op == OP_SPECIAL && c.r.op == OP_SPECIAL_SYSCALL) ||
49 (c.i.op == OP_CP0 && (c.r.rs == OP_CP0_MTC0 ||
50 c.r.rs == OP_CP0_CTC0) &&
51 (c.r.rd == 12 || c.r.rd == 13));
52}
53
54static u64 opcode_read_mask(union code op)
d16005f8
PC		 55{
56 switch (op.i.op) {
57 case OP_SPECIAL:
58 switch (op.r.op) {
59 case OP_SPECIAL_SYSCALL:
60 case OP_SPECIAL_BREAK:
98fa08a5 61 return 0;
d16005f8
PC		 62 case OP_SPECIAL_JR:
63 case OP_SPECIAL_JALR:
64 case OP_SPECIAL_MTHI:
65 case OP_SPECIAL_MTLO:
98fa08a5 66 return BIT(op.r.rs);
d16005f8 67 case OP_SPECIAL_MFHI:
98fa08a5 68 return BIT(REG_HI);
d16005f8 69 case OP_SPECIAL_MFLO:
98fa08a5 70 return BIT(REG_LO);
d16005f8
PC		 71 case OP_SPECIAL_SLL:
72 case OP_SPECIAL_SRL:
73 case OP_SPECIAL_SRA:
98fa08a5 74 return BIT(op.r.rt);
d16005f8 75 default:
98fa08a5 76 return BIT(op.r.rs) | BIT(op.r.rt);
d16005f8
PC		 77 }
78 case OP_CP0:
79 switch (op.r.rs) {
80 case OP_CP0_MTC0:
81 case OP_CP0_CTC0:
98fa08a5 82 return BIT(op.r.rt);
d16005f8 83 default:
98fa08a5 84 return 0;
d16005f8
PC		 85 }
86 case OP_CP2:
87 if (op.r.op == OP_CP2_BASIC) {
88 switch (op.r.rs) {
89 case OP_CP2_BASIC_MTC2:
90 case OP_CP2_BASIC_CTC2:
98fa08a5 91 return BIT(op.r.rt);
d16005f8 92 default:
98fa08a5 93 break;
d16005f8 94 }
d16005f8 95 }
98fa08a5 96 return 0;
d16005f8
PC		 97 case OP_J:
98 case OP_JAL:
99 case OP_LUI:
98fa08a5 100 return 0;
d16005f8
PC		 101 case OP_BEQ:
102 case OP_BNE:
103 case OP_LWL:
104 case OP_LWR:
105 case OP_SB:
106 case OP_SH:
107 case OP_SWL:
108 case OP_SW:
109 case OP_SWR:
98fa08a5 110 return BIT(op.i.rs) | BIT(op.i.rt);
d16005f8 111 default:
98fa08a5 112 return BIT(op.i.rs);
d16005f8
PC		 113 }
114}
115
98fa08a5 116static u64 opcode_write_mask(union code op)
d16005f8 117{
98fa08a5
PC		 118 u64 flags;
119
d16005f8
PC		 120 switch (op.i.op) {
121 case OP_SPECIAL:
122 switch (op.r.op) {
123 case OP_SPECIAL_JR:
d16005f8
PC		 124 case OP_SPECIAL_SYSCALL:
125 case OP_SPECIAL_BREAK:
98fa08a5 126 return 0;
d16005f8
PC		 127 case OP_SPECIAL_MULT:
128 case OP_SPECIAL_MULTU:
129 case OP_SPECIAL_DIV:
130 case OP_SPECIAL_DIVU:
98fa08a5
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 return flags;
d16005f8 143 case OP_SPECIAL_MTHI:
98fa08a5 144 return BIT(REG_HI);
d16005f8 145 case OP_SPECIAL_MTLO:
98fa08a5 146 return BIT(REG_LO);
d16005f8 147 default:
98fa08a5 148 return BIT(op.r.rd);
d16005f8
PC		 149 }
150 case OP_ADDI:
151 case OP_ADDIU:
152 case OP_SLTI:
153 case OP_SLTIU:
154 case OP_ANDI:
155 case OP_ORI:
156 case OP_XORI:
157 case OP_LUI:
158 case OP_LB:
159 case OP_LH:
160 case OP_LWL:
161 case OP_LW:
162 case OP_LBU:
163 case OP_LHU:
164 case OP_LWR:
98fa08a5
PC		 165 return BIT(op.i.rt);
166 case OP_JAL:
167 return BIT(31);
d16005f8
PC		 168 case OP_CP0:
169 switch (op.r.rs) {
170 case OP_CP0_MFC0:
171 case OP_CP0_CFC0:
98fa08a5 172 return BIT(op.i.rt);
d16005f8 173 default:
98fa08a5 174 return 0;
d16005f8
PC		 175 }
176 case OP_CP2:
177 if (op.r.op == OP_CP2_BASIC) {
178 switch (op.r.rs) {
179 case OP_CP2_BASIC_MFC2:
180 case OP_CP2_BASIC_CFC2:
98fa08a5 181 return BIT(op.i.rt);
d16005f8 182 default:
98fa08a5 183 break;
d16005f8 184 }
98fa08a5
PC		 185 }
186 return 0;
187 case OP_REGIMM:
188 switch (op.r.rt) {
189 case OP_REGIMM_BLTZAL:
190 case OP_REGIMM_BGEZAL:
191 return BIT(31);
192 default:
193 return 0;
d16005f8
PC		 194 }
195 case OP_META_MOV:
98fa08a5 196 return BIT(op.r.rd);
d16005f8 197 default:
98fa08a5
PC		 198 return 0;
199 }
200}
201
202bool opcode_reads_register(union code op, u8 reg)
203{
204 return opcode_read_mask(op) & BIT(reg);
205}
206
207bool opcode_writes_register(union code op, u8 reg)
208{
209 return opcode_write_mask(op) & BIT(reg);
210}
211
212static int find_prev_writer(const struct opcode *list, unsigned int offset, u8 reg)
213{
214 union code c;
215 unsigned int i;
216
217 if (list[offset].flags & LIGHTREC_SYNC)
218 return -1;
219
220 for (i = offset; i > 0; i--) {
221 c = list[i - 1].c;
222
223 if (opcode_writes_register(c, reg)) {
224 if (i > 1 && has_delay_slot(list[i - 2].c))
225 break;
226
227 return i - 1;
228 }
229
230 if ((list[i - 1].flags & LIGHTREC_SYNC) ||
231 has_delay_slot(c) ||
232 opcode_reads_register(c, reg))
233 break;
234 }
235
236 return -1;
237}
238
239static int find_next_reader(const struct opcode *list, unsigned int offset, u8 reg)
240{
241 unsigned int i;
242 union code c;
243
244 if (list[offset].flags & LIGHTREC_SYNC)
245 return -1;
246
247 for (i = offset; ; i++) {
248 c = list[i].c;
249
250 if (opcode_reads_register(c, reg)) {
251 if (i > 0 && has_delay_slot(list[i - 1].c))
252 break;
253
254 return i;
255 }
256
257 if ((list[i].flags & LIGHTREC_SYNC) ||
258 has_delay_slot(c) || opcode_writes_register(c, reg))
259 break;
260 }
261
262 return -1;
263}
264
265static bool reg_is_dead(const struct opcode *list, unsigned int offset, u8 reg)
266{
267 unsigned int i;
268
269 if (list[offset].flags & LIGHTREC_SYNC)
d16005f8 270 return false;
98fa08a5
PC		 271
272 for (i = offset + 1; ; i++) {
273 if (opcode_reads_register(list[i].c, reg))
274 return false;
275
276 if (opcode_writes_register(list[i].c, reg))
277 return true;
278
279 if (has_delay_slot(list[i].c)) {
280 if (list[i].flags & LIGHTREC_NO_DS)
281 return false;
282
283 return opcode_writes_register(list[i + 1].c, reg);
284 }
d16005f8
PC		 285 }
286}
287
98fa08a5
PC		 288static bool reg_is_read(const struct opcode *list,
289 unsigned int a, unsigned int b, u8 reg)
290{
291 /* Return true if reg is read in one of the opcodes of the interval
292 * [a, b[ */
293 for (; a < b; a++) {
294 if (!is_nop(list[a].c) && opcode_reads_register(list[a].c, reg))
295 return true;
296 }
297
298 return false;
299}
300
301static bool reg_is_written(const struct opcode *list,
302 unsigned int a, unsigned int b, u8 reg)
303{
304 /* Return true if reg is written in one of the opcodes of the interval
305 * [a, b[ */
306
307 for (; a < b; a++) {
308 if (!is_nop(list[a].c) && opcode_writes_register(list[a].c, reg))
309 return true;
310 }
311
312 return false;
313}
314
315static bool reg_is_read_or_written(const struct opcode *list,
316 unsigned int a, unsigned int b, u8 reg)
317{
318 return reg_is_read(list, a, b, reg) || reg_is_written(list, a, b, reg);
319}
320
321static bool opcode_is_load(union code op)
322{
323 switch (op.i.op) {
324 case OP_LB:
325 case OP_LH:
326 case OP_LWL:
327 case OP_LW:
328 case OP_LBU:
329 case OP_LHU:
330 case OP_LWR:
331 case OP_LWC2:
332 return true;
333 default:
334 return false;
335 }
336}
337
338static bool opcode_is_store(union code op)
339{
340 switch (op.i.op) {
341 case OP_SB:
342 case OP_SH:
343 case OP_SW:
344 case OP_SWL:
345 case OP_SWR:
346 case OP_SWC2:
347 return true;
348 default:
349 return false;
350 }
351}
352
353bool opcode_is_io(union code op)
354{
355 return opcode_is_load(op) || opcode_is_store(op);
356}
357
d16005f8
PC		 358/* TODO: Complete */
359static bool is_nop(union code op)
360{
361 if (opcode_writes_register(op, 0)) {
362 switch (op.i.op) {
363 case OP_CP0:
364 return op.r.rs != OP_CP0_MFC0;
365 case OP_LB:
366 case OP_LH:
367 case OP_LWL:
368 case OP_LW:
369 case OP_LBU:
370 case OP_LHU:
371 case OP_LWR:
372 return false;
373 default:
374 return true;
375 }
376 }
377
378 switch (op.i.op) {
379 case OP_SPECIAL:
380 switch (op.r.op) {
381 case OP_SPECIAL_AND:
382 return op.r.rd == op.r.rt && op.r.rd == op.r.rs;
383 case OP_SPECIAL_ADD:
384 case OP_SPECIAL_ADDU:
385 return (op.r.rd == op.r.rt && op.r.rs == 0) ||
386 (op.r.rd == op.r.rs && op.r.rt == 0);
387 case OP_SPECIAL_SUB:
388 case OP_SPECIAL_SUBU:
389 return op.r.rd == op.r.rs && op.r.rt == 0;
390 case OP_SPECIAL_OR:
391 if (op.r.rd == op.r.rt)
392 return op.r.rd == op.r.rs || op.r.rs == 0;
393 else
394 return (op.r.rd == op.r.rs) && op.r.rt == 0;
395 case OP_SPECIAL_SLL:
396 case OP_SPECIAL_SRA:
397 case OP_SPECIAL_SRL:
398 return op.r.rd == op.r.rt && op.r.imm == 0;
98fa08a5
PC		 399 case OP_SPECIAL_MFHI:
400 case OP_SPECIAL_MFLO:
401 return op.r.rd == 0;
d16005f8
PC		 402 default:
403 return false;
404 }
405 case OP_ORI:
406 case OP_ADDI:
407 case OP_ADDIU:
408 return op.i.rt == op.i.rs && op.i.imm == 0;
409 case OP_BGTZ:
410 return (op.i.rs == 0 || op.i.imm == 1);
411 case OP_REGIMM:
412 return (op.i.op == OP_REGIMM_BLTZ ||
413 op.i.op == OP_REGIMM_BLTZAL) &&
414 (op.i.rs == 0 || op.i.imm == 1);
415 case OP_BNE:
416 return (op.i.rs == op.i.rt || op.i.imm == 1);
417 default:
418 return false;
419 }
420}
421
422bool load_in_delay_slot(union code op)
423{
424 switch (op.i.op) {
425 case OP_CP0:
426 switch (op.r.rs) {
427 case OP_CP0_MFC0:
428 case OP_CP0_CFC0:
429 return true;
430 default:
431 break;
432 }
433
434 break;
435 case OP_CP2:
436 if (op.r.op == OP_CP2_BASIC) {
437 switch (op.r.rs) {
438 case OP_CP2_BASIC_MFC2:
439 case OP_CP2_BASIC_CFC2:
440 return true;
441 default:
442 break;
443 }
444 }
445
446 break;
447 case OP_LB:
448 case OP_LH:
449 case OP_LW:
450 case OP_LWL:
451 case OP_LWR:
452 case OP_LBU:
453 case OP_LHU:
454 return true;
455 default:
456 break;
457 }
458
459 return false;
460}
461
98fa08a5 462static u32 lightrec_propagate_consts(const struct opcode *op, u32 known, u32 *v)
d16005f8 463{
98fa08a5
PC		 464 union code c = op->c;
465
fd58fa32
PC		 466 /* Register $zero is always, well, zero */
467 known |= BIT(0);
468 v[0] = 0;
469
98fa08a5
PC		 470 if (op->flags & LIGHTREC_SYNC)
471 return 0;
472
d16005f8
PC		 473 switch (c.i.op) {
474 case OP_SPECIAL:
475 switch (c.r.op) {
476 case OP_SPECIAL_SLL:
477 if (known & BIT(c.r.rt)) {
478 known |= BIT(c.r.rd);
479 v[c.r.rd] = v[c.r.rt] << c.r.imm;
480 } else {
481 known &= ~BIT(c.r.rd);
482 }
483 break;
484 case OP_SPECIAL_SRL:
485 if (known & BIT(c.r.rt)) {
486 known |= BIT(c.r.rd);
487 v[c.r.rd] = v[c.r.rt] >> c.r.imm;
488 } else {
489 known &= ~BIT(c.r.rd);
490 }
491 break;
492 case OP_SPECIAL_SRA:
493 if (known & BIT(c.r.rt)) {
494 known |= BIT(c.r.rd);
495 v[c.r.rd] = (s32)v[c.r.rt] >> c.r.imm;
496 } else {
497 known &= ~BIT(c.r.rd);
498 }
499 break;
500 case OP_SPECIAL_SLLV:
501 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
502 known |= BIT(c.r.rd);
503 v[c.r.rd] = v[c.r.rt] << (v[c.r.rs] & 0x1f);
504 } else {
505 known &= ~BIT(c.r.rd);
506 }
507 break;
508 case OP_SPECIAL_SRLV:
509 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
510 known |= BIT(c.r.rd);
511 v[c.r.rd] = v[c.r.rt] >> (v[c.r.rs] & 0x1f);
512 } else {
513 known &= ~BIT(c.r.rd);
514 }
515 break;
516 case OP_SPECIAL_SRAV:
517 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
518 known |= BIT(c.r.rd);
519 v[c.r.rd] = (s32)v[c.r.rt]
520 >> (v[c.r.rs] & 0x1f);
521 } else {
522 known &= ~BIT(c.r.rd);
523 }
524 break;
525 case OP_SPECIAL_ADD:
526 case OP_SPECIAL_ADDU:
527 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
528 known |= BIT(c.r.rd);
529 v[c.r.rd] = (s32)v[c.r.rt] + (s32)v[c.r.rs];
530 } else {
531 known &= ~BIT(c.r.rd);
532 }
533 break;
534 case OP_SPECIAL_SUB:
535 case OP_SPECIAL_SUBU:
536 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
537 known |= BIT(c.r.rd);
538 v[c.r.rd] = v[c.r.rt] - v[c.r.rs];
539 } else {
540 known &= ~BIT(c.r.rd);
541 }
542 break;
543 case OP_SPECIAL_AND:
544 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
545 known |= BIT(c.r.rd);
546 v[c.r.rd] = v[c.r.rt] & v[c.r.rs];
547 } else {
548 known &= ~BIT(c.r.rd);
549 }
550 break;
551 case OP_SPECIAL_OR:
552 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
553 known |= BIT(c.r.rd);
554 v[c.r.rd] = v[c.r.rt] | v[c.r.rs];
555 } else {
556 known &= ~BIT(c.r.rd);
557 }
558 break;
559 case OP_SPECIAL_XOR:
560 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
561 known |= BIT(c.r.rd);
562 v[c.r.rd] = v[c.r.rt] ^ v[c.r.rs];
563 } else {
564 known &= ~BIT(c.r.rd);
565 }
566 break;
567 case OP_SPECIAL_NOR:
568 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
569 known |= BIT(c.r.rd);
570 v[c.r.rd] = ~(v[c.r.rt] | v[c.r.rs]);
571 } else {
572 known &= ~BIT(c.r.rd);
573 }
574 break;
575 case OP_SPECIAL_SLT:
576 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
577 known |= BIT(c.r.rd);
578 v[c.r.rd] = (s32)v[c.r.rs] < (s32)v[c.r.rt];
579 } else {
580 known &= ~BIT(c.r.rd);
581 }
582 break;
583 case OP_SPECIAL_SLTU:
584 if (known & BIT(c.r.rt) && known & BIT(c.r.rs)) {
585 known |= BIT(c.r.rd);
586 v[c.r.rd] = v[c.r.rs] < v[c.r.rt];
587 } else {
588 known &= ~BIT(c.r.rd);
589 }
590 break;
591 default:
592 break;
593 }
594 break;
595 case OP_REGIMM:
596 break;
597 case OP_ADDI:
598 case OP_ADDIU:
599 if (known & BIT(c.i.rs)) {
600 known |= BIT(c.i.rt);
601 v[c.i.rt] = v[c.i.rs] + (s32)(s16)c.i.imm;
602 } else {
603 known &= ~BIT(c.i.rt);
604 }
605 break;
606 case OP_SLTI:
607 if (known & BIT(c.i.rs)) {
608 known |= BIT(c.i.rt);
609 v[c.i.rt] = (s32)v[c.i.rs] < (s32)(s16)c.i.imm;
610 } else {
611 known &= ~BIT(c.i.rt);
612 }
613 break;
614 case OP_SLTIU:
615 if (known & BIT(c.i.rs)) {
616 known |= BIT(c.i.rt);
617 v[c.i.rt] = v[c.i.rs] < (u32)(s32)(s16)c.i.imm;
618 } else {
619 known &= ~BIT(c.i.rt);
620 }
621 break;
622 case OP_ANDI:
623 if (known & BIT(c.i.rs)) {
624 known |= BIT(c.i.rt);
625 v[c.i.rt] = v[c.i.rs] & c.i.imm;
626 } else {
627 known &= ~BIT(c.i.rt);
628 }
629 break;
630 case OP_ORI:
631 if (known & BIT(c.i.rs)) {
632 known |= BIT(c.i.rt);
633 v[c.i.rt] = v[c.i.rs] | c.i.imm;
634 } else {
635 known &= ~BIT(c.i.rt);
636 }
637 break;
638 case OP_XORI:
639 if (known & BIT(c.i.rs)) {
640 known |= BIT(c.i.rt);
641 v[c.i.rt] = v[c.i.rs] ^ c.i.imm;
642 } else {
643 known &= ~BIT(c.i.rt);
644 }
645 break;
646 case OP_LUI:
647 known |= BIT(c.i.rt);
648 v[c.i.rt] = c.i.imm << 16;
649 break;
650 case OP_CP0:
651 switch (c.r.rs) {
652 case OP_CP0_MFC0:
653 case OP_CP0_CFC0:
654 known &= ~BIT(c.r.rt);
655 break;
656 }
657 break;
658 case OP_CP2:
659 if (c.r.op == OP_CP2_BASIC) {
660 switch (c.r.rs) {
661 case OP_CP2_BASIC_MFC2:
662 case OP_CP2_BASIC_CFC2:
663 known &= ~BIT(c.r.rt);
664 break;
665 }
666 }
667 break;
668 case OP_LB:
669 case OP_LH:
670 case OP_LWL:
671 case OP_LW:
672 case OP_LBU:
673 case OP_LHU:
674 case OP_LWR:
675 case OP_LWC2:
676 known &= ~BIT(c.i.rt);
677 break;
678 case OP_META_MOV:
679 if (known & BIT(c.r.rs)) {
680 known |= BIT(c.r.rd);
681 v[c.r.rd] = v[c.r.rs];
682 } else {
683 known &= ~BIT(c.r.rd);
684 }
685 break;
686 default:
687 break;
688 }
689
690 return known;
691}
692
98fa08a5 693static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset)
d16005f8 694{
98fa08a5
PC		 695 struct opcode *prev, *prev2 = NULL, *curr = &list[offset];
696 struct opcode *to_change, *to_nop;
697 int idx, idx2;
d16005f8 698
98fa08a5
PC		 699 if (curr->r.imm != 24 && curr->r.imm != 16)
700 return;
701
702 idx = find_prev_writer(list, offset, curr->r.rt);
703 if (idx < 0)
704 return;
705
706 prev = &list[idx];
707
708 if (prev->i.op != OP_SPECIAL || prev->r.op != OP_SPECIAL_SLL ||
709 prev->r.imm != curr->r.imm || prev->r.rd != curr->r.rt)
710 return;
d16005f8 711
98fa08a5
PC		 712 if (prev->r.rd != prev->r.rt && curr->r.rd != curr->r.rt) {
713 /* sll rY, rX, 16
714 * ...
715 * srl rZ, rY, 16 */
d16005f8 716
98fa08a5
PC		 717 if (!reg_is_dead(list, offset, curr->r.rt) ||
718 reg_is_read_or_written(list, idx, offset, curr->r.rd))
719 return;
720
721 /* If rY is dead after the SRL, and rZ is not used after the SLL,
722 * we can change rY to rZ */
723
724 pr_debug("Detected SLL/SRA with middle temp register\n");
725 prev->r.rd = curr->r.rd;
726 curr->r.rt = prev->r.rd;
727 }
728
729 /* We got a SLL/SRA combo. If imm #16, that's a cast to u16.
730 * If imm #24 that's a cast to u8.
731 *
732 * First of all, make sure that the target register of the SLL is not
733 * read before the SRA. */
734
735 if (prev->r.rd == prev->r.rt) {
736 /* sll rX, rX, 16
737 * ...
738 * srl rY, rX, 16 */
739 to_change = curr;
740 to_nop = prev;
741
742 /* rX is used after the SRA - we cannot convert it. */
743 if (prev->r.rd != curr->r.rd && !reg_is_dead(list, offset, prev->r.rd))
744 return;
d16005f8 745 } else {
98fa08a5
PC		 746 /* sll rY, rX, 16
747 * ...
748 * srl rY, rY, 16 */
749 to_change = prev;
750 to_nop = curr;
d16005f8
PC		 751 }
752
98fa08a5
PC		 753 idx2 = find_prev_writer(list, idx, prev->r.rt);
754 if (idx2 >= 0) {
755 /* Note that PSX games sometimes do casts after
756 * a LHU or LBU; in this case we can change the
757 * load opcode to a LH or LB, and the cast can
758 * be changed to a MOV or a simple NOP. */
759
760 prev2 = &list[idx2];
761
762 if (curr->r.rd != prev2->i.rt &&
763 !reg_is_dead(list, offset, prev2->i.rt))
764 prev2 = NULL;
765 else if (curr->r.imm == 16 && prev2->i.op == OP_LHU)
766 prev2->i.op = OP_LH;
767 else if (curr->r.imm == 24 && prev2->i.op == OP_LBU)
768 prev2->i.op = OP_LB;
769 else
770 prev2 = NULL;
771
772 if (prev2) {
773 if (curr->r.rd == prev2->i.rt) {
774 to_change->opcode = 0;
775 } else if (reg_is_dead(list, offset, prev2->i.rt) &&
776 !reg_is_read_or_written(list, idx2 + 1, offset, curr->r.rd)) {
777 /* The target register of the SRA is dead after the
778 * LBU/LHU; we can change the target register of the
779 * LBU/LHU to the one of the SRA. */
780 prev2->i.rt = curr->r.rd;
781 to_change->opcode = 0;
782 } else {
783 to_change->i.op = OP_META_MOV;
784 to_change->r.rd = curr->r.rd;
785 to_change->r.rs = prev2->i.rt;
786 }
d16005f8 787
98fa08a5
PC		 788 if (to_nop->r.imm == 24)
789 pr_debug("Convert LBU+SLL+SRA to LB\n");
790 else
791 pr_debug("Convert LHU+SLL+SRA to LH\n");
792 }
793 }
794
795 if (!prev2) {
796 pr_debug("Convert SLL/SRA #%u to EXT%c\n",
797 prev->r.imm,
798 prev->r.imm == 24 ? 'C' : 'S');
799
800 if (to_change == prev) {
801 to_change->i.rs = prev->r.rt;
802 to_change->i.rt = curr->r.rd;
803 } else {
804 to_change->i.rt = curr->r.rd;
805 to_change->i.rs = prev->r.rt;
806 }
807
808 if (to_nop->r.imm == 24)
809 to_change->i.op = OP_META_EXTC;
810 else
811 to_change->i.op = OP_META_EXTS;
812 }
813
814 to_nop->opcode = 0;
d16005f8
PC		 815}
816
98fa08a5 817static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
d16005f8
PC		 818{
819 struct opcode *list = block->opcode_list;
98fa08a5
PC		 820 struct opcode *op;
821 u32 known = BIT(0);
822 u32 values[32] = { 0 };
823 unsigned int i;
824 int reader;
d16005f8 825
98fa08a5
PC		 826 for (i = 0; i < block->nb_ops; i++) {
827 op = &list[i];
d16005f8
PC		 828
829 /* Transform all opcodes detected as useless to real NOPs
830 * (0x0: SLL r0, r0, #0) */
98fa08a5 831 if (op->opcode != 0 && is_nop(op->c)) {
d16005f8 832 pr_debug("Converting useless opcode 0x%08x to NOP\n",
98fa08a5
PC		 833 op->opcode);
834 op->opcode = 0x0;
d16005f8
PC		 835 }
836
98fa08a5 837 if (!op->opcode)
d16005f8
PC		 838 continue;
839
98fa08a5 840 switch (op->i.op) {
d16005f8 841 case OP_BEQ:
98fa08a5
PC		 842 if (op->i.rs == op->i.rt) {
843 op->i.rs = 0;
844 op->i.rt = 0;
845 } else if (op->i.rs == 0) {
846 op->i.rs = op->i.rt;
847 op->i.rt = 0;
d16005f8
PC		 848 }
849 break;
98fa08a5 850
d16005f8 851 case OP_BNE:
98fa08a5
PC		 852 if (op->i.rs == 0) {
853 op->i.rs = op->i.rt;
854 op->i.rt = 0;
855 }
856 break;
857
858 case OP_LUI:
859 if (!(op->flags & LIGHTREC_SYNC) &&
860 (known & BIT(op->i.rt)) &&
861 values[op->i.rt] == op->i.imm << 16) {
862 pr_debug("Converting duplicated LUI to NOP\n");
863 op->opcode = 0x0;
864 }
865
866 if (op->i.imm != 0 || op->i.rt == 0)
867 break;
868
869 reader = find_next_reader(list, i + 1, op->i.rt);
870 if (reader > 0 &&
871 (opcode_writes_register(list[reader].c, op->i.rt) ||
872 reg_is_dead(list, reader, op->i.rt))) {
873
874 pr_debug("Removing useless LUI 0x0\n");
875
876 if (list[reader].i.rs == op->i.rt)
877 list[reader].i.rs = 0;
878 if (list[reader].i.op == OP_SPECIAL &&
879 list[reader].i.rt == op->i.rt)
880 list[reader].i.rt = 0;
881 op->opcode = 0x0;
d16005f8
PC		 882 }
883 break;
884
885 /* Transform ORI/ADDI/ADDIU with imm #0 or ORR/ADD/ADDU/SUB/SUBU
886 * with register $zero to the MOV meta-opcode */
887 case OP_ORI:
888 case OP_ADDI:
889 case OP_ADDIU:
98fa08a5 890 if (op->i.imm == 0) {
d16005f8 891 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
98fa08a5
PC		 892 op->i.op = OP_META_MOV;
893 op->r.rd = op->i.rt;
d16005f8
PC		 894 }
895 break;
896 case OP_SPECIAL:
98fa08a5 897 switch (op->r.op) {
d16005f8 898 case OP_SPECIAL_SRA:
98fa08a5
PC		 899 if (op->r.imm == 0) {
900 pr_debug("Convert SRA #0 to MOV\n");
901 op->i.op = OP_META_MOV;
902 op->r.rs = op->r.rt;
903 break;
904 }
905
906 lightrec_optimize_sll_sra(block->opcode_list, i);
907 break;
908 case OP_SPECIAL_SLL:
d16005f8 909 case OP_SPECIAL_SRL:
98fa08a5
PC		 910 if (op->r.imm == 0) {
911 pr_debug("Convert SLL/SRL #0 to MOV\n");
912 op->i.op = OP_META_MOV;
913 op->r.rs = op->r.rt;
d16005f8
PC		 914 }
915 break;
916 case OP_SPECIAL_OR:
917 case OP_SPECIAL_ADD:
918 case OP_SPECIAL_ADDU:
98fa08a5 919 if (op->r.rs == 0) {
d16005f8 920 pr_debug("Convert OR/ADD $zero to MOV\n");
98fa08a5
PC		 921 op->i.op = OP_META_MOV;
922 op->r.rs = op->r.rt;
d16005f8
PC		 923 }
924 case OP_SPECIAL_SUB: /* fall-through */
925 case OP_SPECIAL_SUBU:
98fa08a5 926 if (op->r.rt == 0) {
d16005f8 927 pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
98fa08a5 928 op->i.op = OP_META_MOV;
d16005f8
PC		 929 }
930 default: /* fall-through */
931 break;
932 }
933 default: /* fall-through */
934 break;
935 }
98fa08a5
PC		 936
937 known = lightrec_propagate_consts(op, known, values);
d16005f8
PC		 938 }
939
940 return 0;
941}
942
98fa08a5 943static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
d16005f8 944{
98fa08a5
PC		 945 struct opcode *list, *next = &block->opcode_list[0];
946 unsigned int i;
947 union code op, next_op;
d16005f8
PC		 948 u8 flags;
949
98fa08a5
PC		 950 for (i = 0; i < block->nb_ops - 1; i++) {
951 list = next;
952 next = &block->opcode_list[i + 1];
953 next_op = next->c;
954 op = list->c;
d16005f8
PC		 955
956 if (!has_delay_slot(op) ||
957 list->flags & (LIGHTREC_NO_DS | LIGHTREC_EMULATE_BRANCH) ||
98fa08a5
PC		 958 op.opcode == 0 || next_op.opcode == 0)
959 continue;
960
961 if (i && has_delay_slot(block->opcode_list[i - 1].c) &&
962 !(block->opcode_list[i - 1].flags & LIGHTREC_NO_DS))
d16005f8
PC		 963 continue;
964
98fa08a5
PC		 965 if ((list->flags & LIGHTREC_SYNC) ||
966 (next->flags & LIGHTREC_SYNC))
d16005f8
PC		 967 continue;
968
969 switch (list->i.op) {
970 case OP_SPECIAL:
971 switch (op.r.op) {
972 case OP_SPECIAL_JALR:
973 if (opcode_reads_register(next_op, op.r.rd) ||
974 opcode_writes_register(next_op, op.r.rd))
975 continue;
976 case OP_SPECIAL_JR: /* fall-through */
977 if (opcode_writes_register(next_op, op.r.rs))
978 continue;
979 default: /* fall-through */
980 break;
981 }
982 case OP_J: /* fall-through */
983 break;
984 case OP_JAL:
985 if (opcode_reads_register(next_op, 31) ||
986 opcode_writes_register(next_op, 31))
987 continue;
988 else
989 break;
990 case OP_BEQ:
991 case OP_BNE:
992 if (op.i.rt && opcode_writes_register(next_op, op.i.rt))
993 continue;
994 case OP_BLEZ: /* fall-through */
995 case OP_BGTZ:
d16005f8
PC		 996 if (op.i.rs && opcode_writes_register(next_op, op.i.rs))
997 continue;
998 break;
999 case OP_REGIMM:
1000 switch (op.r.rt) {
1001 case OP_REGIMM_BLTZAL:
1002 case OP_REGIMM_BGEZAL:
1003 if (opcode_reads_register(next_op, 31) ||
1004 opcode_writes_register(next_op, 31))
1005 continue;
1006 case OP_REGIMM_BLTZ: /* fall-through */
1007 case OP_REGIMM_BGEZ:
1008 if (op.i.rs &&
1009 opcode_writes_register(next_op, op.i.rs))
1010 continue;
1011 break;
1012 }
1013 default: /* fall-through */
1014 break;
1015 }
1016
1017 pr_debug("Swap branch and delay slot opcodes "
98fa08a5
PC		 1018 "at offsets 0x%x / 0x%x\n",
1019 i << 2, (i + 1) << 2);
d16005f8 1020
98fa08a5 1021 flags = next->flags;
d16005f8 1022 list->c = next_op;
98fa08a5
PC		 1023 next->c = op;
1024 next->flags = list->flags | LIGHTREC_NO_DS;
a59e5536 1025 list->flags = flags | LIGHTREC_NO_DS;
d16005f8
PC		 1026 }
1027
1028 return 0;
1029}
1030
98fa08a5
PC		 1031static int shrink_opcode_list(struct lightrec_state *state, struct block *block, u16 new_size)
1032{
1033 struct opcode *list;
1034
1035 if (new_size >= block->nb_ops) {
1036 pr_err("Invalid shrink size (%u vs %u)\n",
1037 new_size, block->nb_ops);
1038 return -EINVAL;
1039 }
1040
1041
1042 list = lightrec_malloc(state, MEM_FOR_IR,
1043 sizeof(*list) * new_size);
1044 if (!list) {
1045 pr_err("Unable to allocate memory\n");
1046 return -ENOMEM;
1047 }
1048
1049 memcpy(list, block->opcode_list, sizeof(*list) * new_size);
1050
1051 lightrec_free_opcode_list(state, block);
1052 block->opcode_list = list;
1053 block->nb_ops = new_size;
1054
1055 pr_debug("Shrunk opcode list of block PC 0x%08x to %u opcodes\n",
1056 block->pc, new_size);
1057
1058 return 0;
1059}
1060
1061static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1062 struct block *block)
d16005f8 1063{
98fa08a5
PC		 1064 struct opcode *op, *next = &block->opcode_list[0];
1065 unsigned int i;
1066 int ret = 0;
1067
1068 for (i = 0; i < block->nb_ops - 1; i++) {
1069 op = next;
1070 next = &block->opcode_list[i + 1];
d16005f8 1071
d16005f8
PC		 1072 if (!has_delay_slot(op->c) ||
1073 (!load_in_delay_slot(next->c) &&
1074 !has_delay_slot(next->c) &&
1075 !(next->i.op == OP_CP0 && next->r.rs == OP_CP0_RFE)))
1076 continue;
1077
1078 if (op->c.opcode == next->c.opcode) {
1079 /* The delay slot is the exact same opcode as the branch
1080 * opcode: this is effectively a NOP */
1081 next->c.opcode = 0;
1082 continue;
1083 }
1084
98fa08a5
PC		 1085 op->flags |= LIGHTREC_EMULATE_BRANCH;
1086
d16005f8 1087 if (op == block->opcode_list) {
98fa08a5
PC		 1088 pr_debug("First opcode of block PC 0x%08x is an impossible branch\n",
1089 block->pc);
1090
d16005f8
PC		 1091 /* If the first opcode is an 'impossible' branch, we
1092 * only keep the first two opcodes of the block (the
1093 * branch itself + its delay slot) */
98fa08a5
PC		 1094 if (block->nb_ops > 2)
1095 ret = shrink_opcode_list(state, block, 2);
1096 break;
d16005f8 1097 }
d16005f8
PC		 1098 }
1099
98fa08a5 1100 return ret;
d16005f8
PC		 1101}
1102
98fa08a5 1103static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
d16005f8 1104{
98fa08a5
PC		 1105 struct opcode *list;
1106 unsigned int i;
d16005f8 1107 s32 offset;
d16005f8 1108
98fa08a5
PC		 1109 for (i = 0; i < block->nb_ops; i++) {
1110 list = &block->opcode_list[i];
1111
1112 if (should_emulate(list))
d16005f8
PC		 1113 continue;
1114
1115 switch (list->i.op) {
1116 case OP_BEQ:
1117 case OP_BNE:
1118 case OP_BLEZ:
1119 case OP_BGTZ:
1120 case OP_REGIMM:
98fa08a5 1121 offset = i + 1 + (s16)list->i.imm;
d16005f8
PC		 1122 if (offset >= 0 && offset < block->nb_ops)
1123 break;
1124 default: /* fall-through */
1125 continue;
1126 }
1127
1128 pr_debug("Found local branch to offset 0x%x\n", offset << 2);
1129
98fa08a5
PC		 1130 if (should_emulate(&block->opcode_list[offset])) {
1131 pr_debug("Branch target must be emulated - skip\n");
1132 continue;
1133 }
d16005f8 1134
98fa08a5
PC		 1135 if (offset && has_delay_slot(block->opcode_list[offset - 1].c)) {
1136 pr_debug("Branch target is a delay slot - skip\n");
1137 continue;
1138 }
d16005f8 1139
98fa08a5 1140 pr_debug("Adding sync at offset 0x%x\n", offset << 2);
d16005f8 1141
98fa08a5
PC		 1142 block->opcode_list[offset].flags |= LIGHTREC_SYNC;
1143 list->flags |= LIGHTREC_LOCAL_BRANCH;
d16005f8
PC		 1144 }
1145
1146 return 0;
1147}
1148
1149bool has_delay_slot(union code op)
1150{
1151 switch (op.i.op) {
1152 case OP_SPECIAL:
1153 switch (op.r.op) {
1154 case OP_SPECIAL_JR:
1155 case OP_SPECIAL_JALR:
1156 return true;
1157 default:
1158 return false;
1159 }
1160 case OP_J:
1161 case OP_JAL:
1162 case OP_BEQ:
1163 case OP_BNE:
1164 case OP_BLEZ:
1165 case OP_BGTZ:
1166 case OP_REGIMM:
d16005f8
PC		 1167 return true;
1168 default:
1169 return false;
1170 }
1171}
1172
98fa08a5 1173bool should_emulate(const struct opcode *list)
d16005f8 1174{
98fa08a5
PC		 1175 return has_delay_slot(list->c) &&
1176 (list->flags & LIGHTREC_EMULATE_BRANCH);
d16005f8
PC		 1177}
1178
98fa08a5 1179static void lightrec_add_unload(struct opcode *op, u8 reg)
d16005f8 1180{
98fa08a5
PC		 1181 if (op->i.op == OP_SPECIAL && reg == op->r.rd)
1182 op->flags |= LIGHTREC_UNLOAD_RD;
d16005f8 1183
98fa08a5
PC		 1184 if (op->i.rs == reg)
1185 op->flags |= LIGHTREC_UNLOAD_RS;
1186 if (op->i.rt == reg)
1187 op->flags |= LIGHTREC_UNLOAD_RT;
1188}
d16005f8 1189
98fa08a5
PC		 1190static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1191{
1192 unsigned int i, offset;
1193 struct opcode *op;
1194 u8 reg;
d16005f8 1195
98fa08a5
PC		 1196 for (reg = 1; reg < 34; reg++) {
1197 int last_r_id = -1, last_w_id = -1;
1198
1199 for (i = 0; i < block->nb_ops; i++) {
1200 union code c = block->opcode_list[i].c;
1201
1202 if (opcode_reads_register(c, reg))
1203 last_r_id = i;
1204 if (opcode_writes_register(c, reg))
1205 last_w_id = i;
d16005f8
PC		 1206 }
1207
98fa08a5
PC		 1208 if (last_w_id > last_r_id)
1209 offset = (unsigned int)last_w_id;
1210 else if (last_r_id >= 0)
1211 offset = (unsigned int)last_r_id;
1212 else
1213 continue;
d16005f8 1214
98fa08a5 1215 op = &block->opcode_list[offset];
d16005f8 1216
98fa08a5
PC		 1217 if (has_delay_slot(op->c) && (op->flags & LIGHTREC_NO_DS))
1218 offset++;
1219
1220 if (offset == block->nb_ops)
1221 continue;
1222
1223 lightrec_add_unload(&block->opcode_list[offset], reg);
d16005f8
PC		 1224 }
1225
1226 return 0;
1227}
1228
98fa08a5 1229static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
d16005f8 1230{
98fa08a5 1231 const struct lightrec_mem_map *map;
d16005f8
PC		 1232 struct opcode *list;
1233 u32 known = BIT(0);
1234 u32 values[32] = { 0 };
98fa08a5
PC		 1235 unsigned int i;
1236 u32 val;
1237
1238 for (i = 0; i < block->nb_ops; i++) {
1239 list = &block->opcode_list[i];
d16005f8 1240
d16005f8
PC		 1241 switch (list->i.op) {
1242 case OP_SB:
1243 case OP_SH:
1244 case OP_SW:
98fa08a5
PC		 1245 if (OPT_FLAG_STORES) {
1246 /* Mark all store operations that target $sp or $gp
1247 * as not requiring code invalidation. This is based
1248 * on the heuristic that stores using one of these
1249 * registers as address will never hit a code page. */
1250 if (list->i.rs >= 28 && list->i.rs <= 29 &&
1251 !state->maps[PSX_MAP_KERNEL_USER_RAM].ops) {
1252 pr_debug("Flaging opcode 0x%08x as not "
1253 "requiring invalidation\n",
1254 list->opcode);
1255 list->flags |= LIGHTREC_NO_INVALIDATE;
1256 }
1257
1258 /* Detect writes whose destination address is inside the
1259 * current block, using constant propagation. When these
1260 * occur, we mark the blocks as not compilable. */
1261 if ((known & BIT(list->i.rs)) &&
1262 kunseg(values[list->i.rs]) >= kunseg(block->pc) &&
1263 kunseg(values[list->i.rs]) < (kunseg(block->pc) +
1264 block->nb_ops * 4)) {
1265 pr_debug("Self-modifying block detected\n");
1266 block->flags |= BLOCK_NEVER_COMPILE;
1267 list->flags |= LIGHTREC_SMC;
1268 }
1269 }
1270 case OP_SWL: /* fall-through */
1271 case OP_SWR:
1272 case OP_SWC2:
1273 case OP_LB:
1274 case OP_LBU:
1275 case OP_LH:
1276 case OP_LHU:
1277 case OP_LW:
1278 case OP_LWL:
1279 case OP_LWR:
1280 case OP_LWC2:
1281 if (OPT_FLAG_IO && (known & BIT(list->i.rs))) {
1282 val = kunseg(values[list->i.rs] + (s16) list->i.imm);
1283 map = lightrec_get_map(state, NULL, val);
1284
1285 if (!map || map->ops ||
1286 map == &state->maps[PSX_MAP_PARALLEL_PORT]) {
1287 pr_debug("Flagging opcode %u as accessing I/O registers\n",
1288 i);
1289 list->flags |= LIGHTREC_HW_IO;
1290 } else {
1291 pr_debug("Flaging opcode %u as direct memory access\n", i);
1292 list->flags |= LIGHTREC_DIRECT_IO;
1293 }
d16005f8
PC		 1294 }
1295 default: /* fall-through */
1296 break;
1297 }
1298
98fa08a5 1299 known = lightrec_propagate_consts(list, known, values);
d16005f8
PC		 1300 }
1301
1302 return 0;
1303}
1304
98fa08a5
PC		 1305static u8 get_mfhi_mflo_reg(const struct block *block, u16 offset,
1306 const struct opcode *last,
1307 u32 mask, bool sync, bool mflo, bool another)
d16005f8 1308{
98fa08a5
PC		 1309 const struct opcode *op, *next = &block->opcode_list[offset];
1310 u32 old_mask;
1311 u8 reg2, reg = mflo ? REG_LO : REG_HI;
1312 u16 branch_offset;
1313 unsigned int i;
1314
1315 for (i = offset; i < block->nb_ops; i++) {
1316 op = next;
1317 next = &block->opcode_list[i + 1];
1318 old_mask = mask;
1319
1320 /* If any other opcode writes or reads to the register
1321 * we'd use, then we cannot use it anymore. */
1322 mask |= opcode_read_mask(op->c);
1323 mask |= opcode_write_mask(op->c);
1324
1325 if (op->flags & LIGHTREC_SYNC)
1326 sync = true;
d16005f8 1327
d16005f8
PC		 1328 switch (op->i.op) {
1329 case OP_BEQ:
1330 case OP_BNE:
1331 case OP_BLEZ:
1332 case OP_BGTZ:
1333 case OP_REGIMM:
d16005f8 1334 /* TODO: handle backwards branches too */
98fa08a5
PC		 1335 if (!last &&
1336 (op->flags & LIGHTREC_LOCAL_BRANCH) &&
d16005f8 1337 (s16)op->c.i.imm >= 0) {
98fa08a5
PC		 1338 branch_offset = i + 1 + (s16)op->c.i.imm
1339 - !!(OPT_SWITCH_DELAY_SLOTS && (op->flags & LIGHTREC_NO_DS));
1340
1341 reg = get_mfhi_mflo_reg(block, branch_offset, NULL,
1342 mask, sync, mflo, false);
1343 reg2 = get_mfhi_mflo_reg(block, offset + 1, next,
1344 mask, sync, mflo, false);
1345 if (reg > 0 && reg == reg2)
1346 return reg;
1347 if (!reg && !reg2)
1348 return 0;
d16005f8 1349 }
98fa08a5
PC		 1350
1351 return mflo ? REG_LO : REG_HI;
d16005f8
PC		 1352 case OP_SPECIAL:
1353 switch (op->r.op) {
1354 case OP_SPECIAL_MULT:
1355 case OP_SPECIAL_MULTU:
1356 case OP_SPECIAL_DIV:
1357 case OP_SPECIAL_DIVU:
98fa08a5 1358 return 0;
d16005f8 1359 case OP_SPECIAL_MTHI:
98fa08a5
PC		 1360 if (!mflo)
1361 return 0;
1362 continue;
1363 case OP_SPECIAL_MTLO:
1364 if (mflo)
1365 return 0;
1366 continue;
d16005f8 1367 case OP_SPECIAL_JR:
98fa08a5
PC		 1368 if (op->r.rs != 31)
1369 return reg;
1370
1371 if (!sync &&
1372 !(op->flags & LIGHTREC_NO_DS) &&
1373 (next->i.op == OP_SPECIAL) &&
1374 ((!mflo && next->r.op == OP_SPECIAL_MFHI) ||
1375 (mflo && next->r.op == OP_SPECIAL_MFLO)))
1376 return next->r.rd;
1377
1378 return 0;
d16005f8 1379 case OP_SPECIAL_JALR:
98fa08a5 1380 return reg;
d16005f8 1381 case OP_SPECIAL_MFHI:
98fa08a5
PC		 1382 if (!mflo) {
1383 if (another)
1384 return op->r.rd;
1385 /* Must use REG_HI if there is another MFHI target*/
1386 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1387 0, sync, mflo, true);
1388 if (reg2 > 0 && reg2 != REG_HI)
1389 return REG_HI;
1390
1391 if (!sync && !(old_mask & BIT(op->r.rd)))
1392 return op->r.rd;
1393 else
1394 return REG_HI;
1395 }
1396 continue;
1397 case OP_SPECIAL_MFLO:
1398 if (mflo) {
1399 if (another)
1400 return op->r.rd;
1401 /* Must use REG_LO if there is another MFLO target*/
1402 reg2 = get_mfhi_mflo_reg(block, i + 1, next,
1403 0, sync, mflo, true);
1404 if (reg2 > 0 && reg2 != REG_LO)
1405 return REG_LO;
1406
1407 if (!sync && !(old_mask & BIT(op->r.rd)))
1408 return op->r.rd;
1409 else
1410 return REG_LO;
1411 }
d16005f8 1412 continue;
98fa08a5
PC		 1413 default:
1414 break;
d16005f8 1415 }
98fa08a5
PC		 1416
1417 /* fall-through */
d16005f8
PC		 1418 default:
1419 continue;
1420 }
1421 }
1422
98fa08a5
PC		 1423 return reg;
1424}
1425
1426static void lightrec_replace_lo_hi(struct block *block, u16 offset,
1427 u16 last, bool lo)
1428{
1429 unsigned int i;
1430 u32 branch_offset;
1431
1432 /* This function will remove the following MFLO/MFHI. It must be called
1433 * only if get_mfhi_mflo_reg() returned a non-zero value. */
1434
1435 for (i = offset; i < last; i++) {
1436 struct opcode *op = &block->opcode_list[i];
1437
1438 switch (op->i.op) {
1439 case OP_BEQ:
1440 case OP_BNE:
1441 case OP_BLEZ:
1442 case OP_BGTZ:
1443 case OP_REGIMM:
1444 /* TODO: handle backwards branches too */
1445 if ((op->flags & LIGHTREC_LOCAL_BRANCH) &&
1446 (s16)op->c.i.imm >= 0) {
1447 branch_offset = i + 1 + (s16)op->c.i.imm
1448 - !!(OPT_SWITCH_DELAY_SLOTS && (op->flags & LIGHTREC_NO_DS));
1449
1450 lightrec_replace_lo_hi(block, branch_offset, last, lo);
1451 lightrec_replace_lo_hi(block, i + 1, branch_offset, lo);
1452 }
1453 break;
1454
1455 case OP_SPECIAL:
1456 if (lo && op->r.op == OP_SPECIAL_MFLO) {
1457 pr_debug("Removing MFLO opcode at offset 0x%x\n",
1458 i << 2);
1459 op->opcode = 0;
1460 return;
1461 } else if (!lo && op->r.op == OP_SPECIAL_MFHI) {
1462 pr_debug("Removing MFHI opcode at offset 0x%x\n",
1463 i << 2);
1464 op->opcode = 0;
1465 return;
1466 }
1467
1468 /* fall-through */
1469 default:
1470 break;
1471 }
1472 }
d16005f8
PC		 1473}
1474
fd58fa32
PC		 1475static bool lightrec_always_skip_div_check(void)
1476{
1477#ifdef __mips__
1478 return true;
1479#else
1480 return false;
1481#endif
1482}
1483
98fa08a5 1484static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
d16005f8 1485{
98fa08a5
PC		 1486 struct opcode *list;
1487 u8 reg_hi, reg_lo;
1488 unsigned int i;
fd58fa32
PC		 1489 u32 known = BIT(0);
1490 u32 values[32] = { 0 };
98fa08a5
PC		 1491
1492 for (i = 0; i < block->nb_ops - 1; i++) {
1493 list = &block->opcode_list[i];
d16005f8 1494
d16005f8
PC		 1495 if (list->i.op != OP_SPECIAL)
1496 continue;
1497
1498 switch (list->r.op) {
98fa08a5
PC		 1499 case OP_SPECIAL_DIV:
1500 case OP_SPECIAL_DIVU:
fd58fa32
PC		 1501 /* If we are dividing by a non-zero constant, don't
1502 * emit the div-by-zero check. */
1503 if (lightrec_always_skip_div_check() ||
1504 (known & BIT(list->c.r.rt) && values[list->c.r.rt]))
1505 list->flags |= LIGHTREC_NO_DIV_CHECK;
1506 case OP_SPECIAL_MULT: /* fall-through */
1507 case OP_SPECIAL_MULTU:
d16005f8
PC		 1508 break;
1509 default:
fd58fa32 1510 known = lightrec_propagate_consts(list, known, values);
d16005f8
PC		 1511 continue;
1512 }
1513
98fa08a5
PC		 1514 /* Don't support opcodes in delay slots */
1515 if ((i && has_delay_slot(block->opcode_list[i - 1].c)) ||
fd58fa32
PC		 1516 (list->flags & LIGHTREC_NO_DS)) {
1517 known = lightrec_propagate_consts(list, known, values);
d16005f8 1518 continue;
fd58fa32 1519 }
d16005f8 1520
98fa08a5
PC		 1521 reg_lo = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, true, false);
1522 if (reg_lo == 0) {
1523 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1524 " not writing LO\n", i << 2);
1525 list->flags |= LIGHTREC_NO_LO;
1526 }
1527
1528 reg_hi = get_mfhi_mflo_reg(block, i + 1, NULL, 0, false, false, false);
1529 if (reg_hi == 0) {
1530 pr_debug("Mark MULT(U)/DIV(U) opcode at offset 0x%x as"
1531 " not writing HI\n", i << 2);
1532 list->flags |= LIGHTREC_NO_HI;
1533 }
1534
1535 if (!reg_lo && !reg_hi) {
1536 pr_debug("Both LO/HI unused in this block, they will "
1537 "probably be used in parent block - removing "
1538 "flags.\n");
1539 list->flags &= ~(LIGHTREC_NO_LO | LIGHTREC_NO_HI);
1540 }
1541
1542 if (reg_lo > 0 && reg_lo != REG_LO) {
1543 pr_debug("Found register %s to hold LO (rs = %u, rt = %u)\n",
1544 lightrec_reg_name(reg_lo), list->r.rs, list->r.rt);
1545
1546 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, true);
1547 list->r.rd = reg_lo;
1548 } else {
1549 list->r.rd = 0;
1550 }
1551
1552 if (reg_hi > 0 && reg_hi != REG_HI) {
1553 pr_debug("Found register %s to hold HI (rs = %u, rt = %u)\n",
1554 lightrec_reg_name(reg_hi), list->r.rs, list->r.rt);
1555
1556 lightrec_replace_lo_hi(block, i + 1, block->nb_ops, false);
1557 list->r.imm = reg_hi;
1558 } else {
1559 list->r.imm = 0;
1560 }
fd58fa32
PC		 1561
1562 known = lightrec_propagate_consts(list, known, values);
98fa08a5
PC		 1563 }
1564
1565 return 0;
1566}
1567
1568static bool remove_div_sequence(struct block *block, unsigned int offset)
1569{
1570 struct opcode *op;
1571 unsigned int i, found = 0;
1572
1573 /*
1574 * Scan for the zero-checking sequence that GCC automatically introduced
1575 * after most DIV/DIVU opcodes. This sequence checks the value of the
1576 * divisor, and if zero, executes a BREAK opcode, causing the BIOS
1577 * handler to crash the PS1.
1578 *
1579 * For DIV opcodes, this sequence additionally checks that the signed
1580 * operation does not overflow.
1581 *
1582 * With the assumption that the games never crashed the PS1, we can
1583 * therefore assume that the games never divided by zero or overflowed,
1584 * and these sequences can be removed.
1585 */
1586
1587 for (i = offset; i < block->nb_ops; i++) {
1588 op = &block->opcode_list[i];
1589
1590 if (!found) {
1591 if (op->i.op == OP_SPECIAL &&
1592 (op->r.op == OP_SPECIAL_DIV || op->r.op == OP_SPECIAL_DIVU))
1593 break;
1594
1595 if ((op->opcode & 0xfc1fffff) == 0x14000002) {
1596 /* BNE ???, zero, +8 */
1597 found++;
1598 } else {
1599 offset++;
1600 }
1601 } else if (found == 1 && !op->opcode) {
1602 /* NOP */
1603 found++;
1604 } else if (found == 2 && op->opcode == 0x0007000d) {
1605 /* BREAK 0x1c00 */
1606 found++;
1607 } else if (found == 3 && op->opcode == 0x2401ffff) {
1608 /* LI at, -1 */
1609 found++;
1610 } else if (found == 4 && (op->opcode & 0xfc1fffff) == 0x14010004) {
1611 /* BNE ???, at, +16 */
1612 found++;
1613 } else if (found == 5 && op->opcode == 0x3c018000) {
1614 /* LUI at, 0x8000 */
1615 found++;
1616 } else if (found == 6 && (op->opcode & 0x141fffff) == 0x14010002) {
1617 /* BNE ???, at, +16 */
1618 found++;
1619 } else if (found == 7 && !op->opcode) {
1620 /* NOP */
1621 found++;
1622 } else if (found == 8 && op->opcode == 0x0006000d) {
1623 /* BREAK 0x1800 */
1624 found++;
1625 break;
1626 } else {
1627 break;
1628 }
1629 }
1630
1631 if (found >= 3) {
1632 if (found != 9)
1633 found = 3;
1634
1635 pr_debug("Removing DIV%s sequence at offset 0x%x\n",
1636 found == 9 ? "" : "U", offset << 2);
1637
1638 for (i = 0; i < found; i++)
1639 block->opcode_list[offset + i].opcode = 0;
1640
1641 return true;
1642 }
1643
1644 return false;
1645}
1646
1647static int lightrec_remove_div_by_zero_check_sequence(struct lightrec_state *state,
1648 struct block *block)
1649{
1650 struct opcode *op;
1651 unsigned int i;
1652
1653 for (i = 0; i < block->nb_ops; i++) {
1654 op = &block->opcode_list[i];
1655
1656 if (op->i.op == OP_SPECIAL &&
1657 (op->r.op == OP_SPECIAL_DIVU || op->r.op == OP_SPECIAL_DIV) &&
1658 remove_div_sequence(block, i + 1))
1659 op->flags |= LIGHTREC_NO_DIV_CHECK;
1660 }
1661
1662 return 0;
1663}
1664
1665static const u32 memset_code[] = {
1666 0x10a00006, // beqz a1, 2f
1667 0x24a2ffff, // addiu v0,a1,-1
1668 0x2403ffff, // li v1,-1
1669 0xac800000, // 1: sw zero,0(a0)
1670 0x2442ffff, // addiu v0,v0,-1
1671 0x1443fffd, // bne v0,v1, 1b
1672 0x24840004, // addiu a0,a0,4
1673 0x03e00008, // 2: jr ra
1674 0x00000000, // nop
1675};
1676
1677static int lightrec_replace_memset(struct lightrec_state *state, struct block *block)
1678{
1679 unsigned int i;
1680 union code c;
1681
1682 for (i = 0; i < block->nb_ops; i++) {
1683 c = block->opcode_list[i].c;
1684
1685 if (c.opcode != memset_code[i])
1686 return 0;
1687
1688 if (i == ARRAY_SIZE(memset_code) - 1) {
1689 /* success! */
1690 pr_debug("Block at PC 0x%x is a memset\n", block->pc);
1691 block->flags |= BLOCK_IS_MEMSET | BLOCK_NEVER_COMPILE;
1692
1693 /* Return non-zero to skip other optimizers. */
1694 return 1;
d16005f8
PC		 1695 }
1696 }
1697
1698 return 0;
1699}
1700
98fa08a5
PC		 1701static int (*lightrec_optimizers[])(struct lightrec_state *state, struct block *) = {
1702 IF_OPT(OPT_REMOVE_DIV_BY_ZERO_SEQ, &lightrec_remove_div_by_zero_check_sequence),
1703 IF_OPT(OPT_REPLACE_MEMSET, &lightrec_replace_memset),
1704 IF_OPT(OPT_DETECT_IMPOSSIBLE_BRANCHES, &lightrec_detect_impossible_branches),
1705 IF_OPT(OPT_LOCAL_BRANCHES, &lightrec_local_branches),
1706 IF_OPT(OPT_TRANSFORM_OPS, &lightrec_transform_ops),
1707 IF_OPT(OPT_SWITCH_DELAY_SLOTS, &lightrec_switch_delay_slots),
1708 IF_OPT(OPT_FLAG_IO || OPT_FLAG_STORES, &lightrec_flag_io),
1709 IF_OPT(OPT_FLAG_MULT_DIV, &lightrec_flag_mults_divs),
1710 IF_OPT(OPT_EARLY_UNLOAD, &lightrec_early_unload),
d16005f8
PC		 1711};
1712
98fa08a5 1713int lightrec_optimize(struct lightrec_state *state, struct block *block)
d16005f8
PC		 1714{
1715 unsigned int i;
98fa08a5 1716 int ret;
d16005f8
PC		 1717
1718 for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
98fa08a5
PC		 1719 if (lightrec_optimizers[i]) {
1720 ret = (*lightrec_optimizers[i])(state, block);
1721 if (ret)
1722 return ret;
1723 }
d16005f8
PC		 1724 }
1725
1726 return 0;
1727}
ARM optimized PCSX fork