deps/lightrec/optimizer.c

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