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                                 return false;
 282
 283                         return opcode_writes_register(list[i + 1].c, reg);
 284                 }
 285         }
 286 }
 287
 288 static 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
 301 static 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
 315 static 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
 321 static 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
 338 static 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
 353 bool opcode_is_io(union code op)
 354 {
 355         return opcode_is_load(op) || opcode_is_store(op);
 356 }
 357
 358 /* TODO: Complete */
 359 static 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;
 399                 case OP_SPECIAL_MFHI:
 400                 case OP_SPECIAL_MFLO:
 401                         return op.r.rd == 0;
 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
 422 bool 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
 462 static u32 lightrec_propagate_consts(const struct opcode *op, u32 known, u32 *v)
 463 {
 464         union code c = op->c;
 465
 466         /* Register $zero is always, well, zero */
 467         known |= BIT(0);
 468         v[0] = 0;
 469
 470         if (op->flags & LIGHTREC_SYNC)
 471                 return 0;
 472
 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
 693 static void lightrec_optimize_sll_sra(struct opcode *list, unsigned int offset)
 694 {
 695         struct opcode *prev, *prev2 = NULL, *curr = &list[offset];
 696         struct opcode *to_change, *to_nop;
 697         int idx, idx2;
 698
 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;
 711
 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 */
 716
 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;
 745         } else {
 746                 /* sll rY, rX, 16
 747                  * ...
 748                  * srl rY, rY, 16 */
 749                 to_change = prev;
 750                 to_nop = curr;
 751         }
 752
 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                         }
 787
 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;
 815 }
 816
 817 static int lightrec_transform_ops(struct lightrec_state *state, struct block *block)
 818 {
 819         struct opcode *list = block->opcode_list;
 820         struct opcode *op;
 821         u32 known = BIT(0);
 822         u32 values[32] = { 0 };
 823         unsigned int i;
 824         int reader;
 825
 826         for (i = 0; i < block->nb_ops; i++) {
 827                 op = &list[i];
 828
 829                 /* Transform all opcodes detected as useless to real NOPs
 830                  * (0x0: SLL r0, r0, #0) */
 831                 if (op->opcode != 0 && is_nop(op->c)) {
 832                         pr_debug("Converting useless opcode 0x%08x to NOP\n",
 833                                         op->opcode);
 834                         op->opcode = 0x0;
 835                 }
 836
 837                 if (!op->opcode)
 838                         continue;
 839
 840                 switch (op->i.op) {
 841                 case OP_BEQ:
 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;
 848                         }
 849                         break;
 850
 851                 case OP_BNE:
 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;
 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:
 890                         if (op->i.imm == 0) {
 891                                 pr_debug("Convert ORI/ADDI/ADDIU #0 to MOV\n");
 892                                 op->i.op = OP_META_MOV;
 893                                 op->r.rd = op->i.rt;
 894                         }
 895                         break;
 896                 case OP_SPECIAL:
 897                         switch (op->r.op) {
 898                         case OP_SPECIAL_SRA:
 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:
 909                         case OP_SPECIAL_SRL:
 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;
 914                                 }
 915                                 break;
 916                         case OP_SPECIAL_OR:
 917                         case OP_SPECIAL_ADD:
 918                         case OP_SPECIAL_ADDU:
 919                                 if (op->r.rs == 0) {
 920                                         pr_debug("Convert OR/ADD $zero to MOV\n");
 921                                         op->i.op = OP_META_MOV;
 922                                         op->r.rs = op->r.rt;
 923                                 }
 924                         case OP_SPECIAL_SUB: /* fall-through */
 925                         case OP_SPECIAL_SUBU:
 926                                 if (op->r.rt == 0) {
 927                                         pr_debug("Convert OR/ADD/SUB $zero to MOV\n");
 928                                         op->i.op = OP_META_MOV;
 929                                 }
 930                         default: /* fall-through */
 931                                 break;
 932                         }
 933                 default: /* fall-through */
 934                         break;
 935                 }
 936
 937                 known = lightrec_propagate_consts(op, known, values);
 938         }
 939
 940         return 0;
 941 }
 942
 943 static int lightrec_switch_delay_slots(struct lightrec_state *state, struct block *block)
 944 {
 945         struct opcode *list, *next = &block->opcode_list[0];
 946         unsigned int i;
 947         union code op, next_op;
 948         u8 flags;
 949
 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;
 955
 956                 if (!has_delay_slot(op) ||
 957                     list->flags & (LIGHTREC_NO_DS | LIGHTREC_EMULATE_BRANCH) ||
 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))
 963                         continue;
 964
 965                 if ((list->flags & LIGHTREC_SYNC) ||
 966                     (next->flags & LIGHTREC_SYNC))
 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:
 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 "
1018                          "at offsets 0x%x / 0x%x\n",
1019                          i << 2, (i + 1) << 2);
1020
1021                 flags = next->flags;
1022                 list->c = next_op;
1023                 next->c = op;
1024                 next->flags = list->flags | LIGHTREC_NO_DS;
1025                 list->flags = flags | LIGHTREC_NO_DS;
1026         }
1027
1028         return 0;
1029 }
1030
1031 static 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
1061 static int lightrec_detect_impossible_branches(struct lightrec_state *state,
1062                                                struct block *block)
1063 {
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];
1071
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
1085                 op->flags |= LIGHTREC_EMULATE_BRANCH;
1086
1087                 if (op == block->opcode_list) {
1088                         pr_debug("First opcode of block PC 0x%08x is an impossible branch\n",
1089                                  block->pc);
1090
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) */
1094                         if (block->nb_ops > 2)
1095                                 ret = shrink_opcode_list(state, block, 2);
1096                         break;
1097                 }
1098         }
1099
1100         return ret;
1101 }
1102
1103 static int lightrec_local_branches(struct lightrec_state *state, struct block *block)
1104 {
1105         struct opcode *list;
1106         unsigned int i;
1107         s32 offset;
1108
1109         for (i = 0; i < block->nb_ops; i++) {
1110                 list = &block->opcode_list[i];
1111
1112                 if (should_emulate(list))
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:
1121                         offset = i + 1 + (s16)list->i.imm;
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
1130                 if (should_emulate(&block->opcode_list[offset])) {
1131                         pr_debug("Branch target must be emulated - skip\n");
1132                         continue;
1133                 }
1134
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                 }
1139
1140                 pr_debug("Adding sync at offset 0x%x\n", offset << 2);
1141
1142                 block->opcode_list[offset].flags |= LIGHTREC_SYNC;
1143                 list->flags |= LIGHTREC_LOCAL_BRANCH;
1144         }
1145
1146         return 0;
1147 }
1148
1149 bool 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:
1167                 return true;
1168         default:
1169                 return false;
1170         }
1171 }
1172
1173 bool should_emulate(const struct opcode *list)
1174 {
1175         return has_delay_slot(list->c) &&
1176                 (list->flags & LIGHTREC_EMULATE_BRANCH);
1177 }
1178
1179 static void lightrec_add_unload(struct opcode *op, u8 reg)
1180 {
1181         if (op->i.op == OP_SPECIAL && reg == op->r.rd)
1182                 op->flags |= LIGHTREC_UNLOAD_RD;
1183
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 }
1189
1190 static int lightrec_early_unload(struct lightrec_state *state, struct block *block)
1191 {
1192         unsigned int i, offset;
1193         struct opcode *op;
1194         u8 reg;
1195
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;
1206                 }
1207
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;
1214
1215                 op = &block->opcode_list[offset];
1216
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);
1224         }
1225
1226         return 0;
1227 }
1228
1229 static int lightrec_flag_io(struct lightrec_state *state, struct block *block)
1230 {
1231         const struct lightrec_mem_map *map;
1232         struct opcode *list;
1233         u32 known = BIT(0);
1234         u32 values[32] = { 0 };
1235         unsigned int i;
1236         u32 val;
1237
1238         for (i = 0; i < block->nb_ops; i++) {
1239                 list = &block->opcode_list[i];
1240
1241                 switch (list->i.op) {
1242                 case OP_SB:
1243                 case OP_SH:
1244                 case OP_SW:
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                                 }
1294                         }
1295                 default: /* fall-through */
1296                         break;
1297                 }
1298
1299                 known = lightrec_propagate_consts(list, known, values);
1300         }
1301
1302         return 0;
1303 }
1304
1305 static 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)
1308 {
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;
1327
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:
1334                         /* TODO: handle backwards branches too */
1335                         if (!last &&
1336                             (op->flags & LIGHTREC_LOCAL_BRANCH) &&
1337                             (s16)op->c.i.imm >= 0) {
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;
1349                         }
1350
1351                         return mflo ? REG_LO : REG_HI;
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:
1358                                 return 0;
1359                         case OP_SPECIAL_MTHI:
1360                                 if (!mflo)
1361                                         return 0;
1362                                 continue;
1363                         case OP_SPECIAL_MTLO:
1364                                 if (mflo)
1365                                         return 0;
1366                                 continue;
1367                         case OP_SPECIAL_JR:
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;
1379                         case OP_SPECIAL_JALR:
1380                                 return reg;
1381                         case OP_SPECIAL_MFHI:
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                                 }
1412                                 continue;
1413                         default:
1414                                 break;
1415                         }
1416
1417                         /* fall-through */
1418                 default:
1419                         continue;
1420                 }
1421         }
1422
1423         return reg;
1424 }
1425
1426 static 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         }
1473 }
1474
1475 static bool lightrec_always_skip_div_check(void)
1476 {
1477 #ifdef __mips__
1478         return true;
1479 #else
1480         return false;
1481 #endif
1482 }
1483
1484 static int lightrec_flag_mults_divs(struct lightrec_state *state, struct block *block)
1485 {
1486         struct opcode *list;
1487         u8 reg_hi, reg_lo;
1488         unsigned int i;
1489         u32 known = BIT(0);
1490         u32 values[32] = { 0 };
1491
1492         for (i = 0; i < block->nb_ops - 1; i++) {
1493                 list = &block->opcode_list[i];
1494
1495                 if (list->i.op != OP_SPECIAL)
1496                         continue;
1497
1498                 switch (list->r.op) {
1499                 case OP_SPECIAL_DIV:
1500                 case OP_SPECIAL_DIVU:
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:
1508                         break;
1509                 default:
1510                         known = lightrec_propagate_consts(list, known, values);
1511                         continue;
1512                 }
1513
1514                 /* Don't support opcodes in delay slots */
1515                 if ((i && has_delay_slot(block->opcode_list[i - 1].c)) ||
1516                     (list->flags & LIGHTREC_NO_DS)) {
1517                         known = lightrec_propagate_consts(list, known, values);
1518                         continue;
1519                 }
1520
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                 }
1561
1562                 known = lightrec_propagate_consts(list, known, values);
1563         }
1564
1565         return 0;
1566 }
1567
1568 static 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
1647 static 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
1665 static 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
1677 static 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;
1695                 }
1696         }
1697
1698         return 0;
1699 }
1700
1701 static 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),
1711 };
1712
1713 int lightrec_optimize(struct lightrec_state *state, struct block *block)
1714 {
1715         unsigned int i;
1716         int ret;
1717
1718         for (i = 0; i < ARRAY_SIZE(lightrec_optimizers); i++) {
1719                 if (lightrec_optimizers[i]) {
1720                         ret = (*lightrec_optimizers[i])(state, block);
1721                         if (ret)
1722                                 return ret;
1723                 }
1724         }
1725
1726         return 0;
1727 }