git.sur5r.net Git - cc65/blob - src/cc65/codeopt.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 codeopt.c                                 */
   4 /*                                                                           */
   5 /*                           Optimizer subroutines                           */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2001      Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <string.h>
  37
  38 /* common */
  39 #include "abend.h"
  40 #include "print.h"
  41
  42 /* cc65 */
  43 #include "asmlabel.h"
  44 #include "codeent.h"
  45 #include "codeinfo.h"
  46 #include "coptind.h"
  47 #include "error.h"
  48 #include "global.h"
  49 #include "codeopt.h"
  50
  51
  52
  53 /*****************************************************************************/
  54 /*                                   Data                                    */
  55 /*****************************************************************************/
  56
  57
  58
  59 /* Defines for the conditions in a compare */
  60 typedef enum {
  61     CMP_INV = -1,
  62     CMP_EQ,
  63     CMP_NE,
  64     CMP_GT,
  65     CMP_GE,
  66     CMP_LT,
  67     CMP_LE,
  68     CMP_UGT,
  69     CMP_UGE,
  70     CMP_ULT,
  71     CMP_ULE
  72 } cmp_t;
  73
  74 /* Table with the compare suffixes */
  75 static const char CmpSuffixTab [][4] = {
  76     "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
  77 };
  78
  79 /* Table used to invert a condition, indexed by condition */
  80 static const unsigned char CmpInvertTab [] = {
  81     CMP_NE, CMP_EQ,
  82     CMP_LE, CMP_LT, CMP_GE, CMP_GT,
  83     CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
  84 };
  85
  86 /* Table to show which compares are signed (use the N flag) */
  87 static const char CmpSignedTab [] = {
  88     0, 0, 1, 1, 1, 1, 0, 0, 0, 0
  89 };
  90
  91
  92
  93 /*****************************************************************************/
  94 /*                             Helper functions                              */
  95 /*****************************************************************************/
  96
  97
  98
  99 static cmp_t FindCmpCond (const char* Suffix)
 100 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
 101 {
 102     int I;
 103
 104     /* Linear search */
 105     for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
 106         if (strcmp (Suffix, CmpSuffixTab [I]) == 0) {
 107             /* Found */
 108             return I;
 109         }
 110     }
 111
 112     /* Not found */
 113     return CMP_INV;
 114 }
 115
 116
 117
 118 /*****************************************************************************/
 119 /*             Remove calls to the bool transformer subroutines              */
 120 /*****************************************************************************/
 121
 122
 123
 124 static unsigned OptBoolTransforms (CodeSeg* S)
 125 /* Try to remove the call to boolean transformer routines where the call is
 126  * not really needed.
 127  */
 128 {
 129     unsigned Changes = 0;
 130
 131     /* Walk over the entries */
 132     unsigned I = 0;
 133     while (I < GetCodeEntryCount (S)) {
 134
 135         CodeEntry* N;
 136         cmp_t Cond;
 137
 138         /* Get next entry */
 139         CodeEntry* E = GetCodeEntry (S, I);
 140
 141         /* Check for a boolean transformer */
 142         if (E->OPC == OPC_JSR                            &&
 143             strncmp (E->Arg, "bool", 4) == 0             &&
 144             (N = GetNextCodeEntry (S, I)) != 0           &&
 145             (N->Info & OF_ZBRA) != 0                     &&
 146             (Cond = FindCmpCond (E->Arg+4)) != CMP_INV) {
 147
 148             CodeEntry* X;
 149             CodeLabel* L;
 150
 151             /* Make the boolean transformer unnecessary by changing the
 152              * the conditional jump to evaluate the condition flags that
 153              * are set after the compare directly. Note: jeq jumps if
 154              * the condition is not met, jne jumps if the condition is met.
 155              * Invert the code if we jump on condition not met.
 156              */
 157             if (GetBranchCond (N->OPC) == BC_EQ) {
 158                 /* Jumps if condition false, invert condition */
 159                 Cond = CmpInvertTab [Cond];
 160             }
 161
 162             /* Check if we can replace the code by something better */
 163             switch (Cond) {
 164
 165                 case CMP_EQ:
 166                     ReplaceOPC (N, OPC_JEQ);
 167                     break;
 168
 169                 case CMP_NE:
 170                     ReplaceOPC (N, OPC_JNE);
 171                     break;
 172
 173                 case CMP_GT:
 174                     /* Replace by
 175                      *     beq @L
 176                      *     jpl Target
 177                      * @L: ...
 178                      */
 179                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 180                         /* No such entry */
 181                         goto NextEntry;
 182                     }
 183                     L = GenCodeLabel (S, X);
 184                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 185                     InsertCodeEntry (S, X, I+1);
 186                     ReplaceOPC (N, OPC_JPL);
 187                     break;
 188
 189                 case CMP_GE:
 190                     ReplaceOPC (N, OPC_JPL);
 191                     break;
 192
 193                 case CMP_LT:
 194                     ReplaceOPC (N, OPC_JMI);
 195                     break;
 196
 197                 case CMP_LE:
 198                     /* Replace by
 199                      *     jmi Target
 200                      *     jeq Target
 201                      */
 202                     ReplaceOPC (N, OPC_JMI);
 203                     L = N->JumpTo;
 204                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 205                     InsertCodeEntry (S, X, I+2);
 206                     break;
 207
 208                 case CMP_UGT:
 209                     /* Replace by
 210                      *     beq @L
 211                      *     jcs Target
 212                      * @L: ...
 213                      */
 214                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 215                         /* No such entry */
 216                         goto NextEntry;
 217                     }
 218                     L = GenCodeLabel (S, X);
 219                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 220                     InsertCodeEntry (S, X, I+1);
 221                     ReplaceOPC (N, OPC_JCS);
 222                     break;
 223
 224                 case CMP_UGE:
 225                     ReplaceOPC (N, OPC_JCS);
 226                     break;
 227
 228                 case CMP_ULT:
 229                     ReplaceOPC (N, OPC_JCC);
 230                     break;
 231
 232                 case CMP_ULE:
 233                     /* Replace by
 234                      *     jcc Target
 235                      *     jeq Target
 236                      */
 237                     ReplaceOPC (N, OPC_JCC);
 238                     L = N->JumpTo;
 239                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 240                     InsertCodeEntry (S, X, I+2);
 241                     break;
 242
 243                 default:
 244                     Internal ("Unknown jump condition: %d", Cond);
 245
 246             }
 247
 248             /* Remove the call to the bool transformer */
 249             DelCodeEntry (S, I);
 250
 251             /* Remember, we had changes */
 252             ++Changes;
 253
 254         }
 255
 256 NextEntry:
 257         /* Next entry */
 258         ++I;
 259
 260     }
 261
 262     /* Return the number of changes made */
 263     return Changes;
 264 }
 265
 266
 267
 268 /*****************************************************************************/
 269 /*                            nega optimizations                             */
 270 /*****************************************************************************/
 271
 272
 273
 274 static unsigned OptNegA1 (CodeSeg* S)
 275 /* Check for
 276  *
 277  *      ldx     #$00
 278  *      lda     ..
 279  *      jsr     bnega
 280  *
 281  * Remove the ldx if the lda does not use it.
 282  */
 283 {
 284     unsigned Changes = 0;
 285
 286     /* Walk over the entries */
 287     unsigned I = 0;
 288     while (I < GetCodeEntryCount (S)) {
 289
 290         CodeEntry* L[2];
 291
 292         /* Get next entry */
 293         CodeEntry* E = GetCodeEntry (S, I);
 294
 295         /* Check for a ldx */
 296         if (E->OPC == OPC_LDX                   &&
 297             E->AM == AM_IMM                     &&
 298             (E->Flags & CEF_NUMARG) != 0        &&
 299             E->Num == 0                         &&
 300             GetCodeEntries (S, L, I+1, 2)       &&
 301             L[0]->OPC == OPC_LDA                &&
 302             (L[0]->Use & REG_X) == 0            &&
 303             L[1]->OPC == OPC_JSR                &&
 304             strcmp (L[1]->Arg, "bnega") == 0) {
 305
 306             /* Remove the ldx instruction */
 307             DelCodeEntry (S, I);
 308
 309             /* Remember, we had changes */
 310             ++Changes;
 311
 312         }
 313
 314         /* Next entry */
 315         ++I;
 316
 317     }
 318
 319     /* Return the number of changes made */
 320     return Changes;
 321 }
 322
 323
 324
 325 static unsigned OptNegA2 (CodeSeg* S)
 326 /* Check for
 327  *
 328  *      lda     ..
 329  *      jsr     bnega
 330  *      jeq/jne ..
 331  *
 332  * Adjust the conditional branch and remove the call to the subroutine.
 333  */
 334 {
 335     unsigned Changes = 0;
 336
 337     /* Walk over the entries */
 338     unsigned I = 0;
 339     while (I < GetCodeEntryCount (S)) {
 340
 341         CodeEntry* L[2];
 342
 343         /* Get next entry */
 344         CodeEntry* E = GetCodeEntry (S, I);
 345
 346         /* Check for the sequence */
 347         if (E->OPC == OPC_LDA                   &&
 348             GetCodeEntries (S, L, I+1, 2)       &&
 349             L[0]->OPC == OPC_JSR                &&
 350             strcmp (L[0]->Arg, "bnega") == 0    &&
 351             !CodeEntryHasLabel (L[0])           &&
 352             (L[1]->Info & OF_ZBRA) != 0) {
 353
 354             /* Invert the branch */
 355             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 356
 357             /* Delete the subroutine call */
 358             DelCodeEntry (S, I+1);
 359
 360             /* Remember, we had changes */
 361             ++Changes;
 362
 363         }
 364
 365         /* Next entry */
 366         ++I;
 367
 368     }
 369
 370     /* Return the number of changes made */
 371     return Changes;
 372 }
 373
 374
 375
 376 /*****************************************************************************/
 377 /*                            negax optimizations                            */
 378 /*****************************************************************************/
 379
 380
 381
 382 static unsigned OptNegAX1 (CodeSeg* S)
 383 /* Search for the sequence:
 384  *
 385  *      lda     (xx),y
 386  *      tax
 387  *      dey
 388  *      lda     (xx),y
 389  *      jsr     bnegax
 390  *      jne/jeq ...
 391  *
 392  * and replace it by
 393  *
 394  *      lda     (xx),y
 395  *      dey
 396  *      ora     (xx),y
 397  *      jeq/jne ...
 398  */
 399 {
 400     unsigned Changes = 0;
 401
 402     /* Walk over the entries */
 403     unsigned I = 0;
 404     while (I < GetCodeEntryCount (S)) {
 405
 406         CodeEntry* L[5];
 407
 408         /* Get next entry */
 409         CodeEntry* E = GetCodeEntry (S, I);
 410
 411         /* Check for the sequence */
 412         if (E->OPC == OPC_LDA                   &&
 413             E->AM == AM_ZP_INDY                 &&
 414             GetCodeEntries (S, L, I+1, 5)       &&
 415             L[0]->OPC == OPC_TAX                &&
 416             L[1]->OPC == OPC_DEY                &&
 417             L[2]->OPC == OPC_LDA                &&
 418             L[2]->AM == AM_ZP_INDY              &&
 419             strcmp (L[2]->Arg, E->Arg) == 0     &&
 420             !CodeEntryHasLabel (L[2])           &&
 421             L[3]->OPC == OPC_JSR                &&
 422             strcmp (L[3]->Arg, "bnegax") == 0   &&
 423             !CodeEntryHasLabel (L[3])           &&
 424             (L[4]->Info & OF_ZBRA) != 0) {
 425
 426             /* lda --> ora */
 427             ReplaceOPC (L[2], OPC_ORA);
 428
 429             /* Invert the branch */
 430             ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
 431
 432             /* Delete the entries no longer needed. Beware: Deleting entries
 433              * will change the indices.
 434              */
 435             DelCodeEntry (S, I+4);              /* jsr bnegax */
 436             DelCodeEntry (S, I+1);              /* tax */
 437
 438             /* Remember, we had changes */
 439             ++Changes;
 440
 441         }
 442
 443         /* Next entry */
 444         ++I;
 445
 446     }
 447
 448     /* Return the number of changes made */
 449     return Changes;
 450 }
 451
 452
 453
 454 static unsigned OptNegAX2 (CodeSeg* S)
 455 /* Search for the sequence:
 456  *
 457  *      lda     xx
 458  *      ldx     yy
 459  *      jsr     bnegax
 460  *      jne/jeq ...
 461  *
 462  * and replace it by
 463  *
 464  *      lda     xx
 465  *      ora     xx+1
 466  *      jeq/jne ...
 467  */
 468 {
 469     unsigned Changes = 0;
 470
 471     /* Walk over the entries */
 472     unsigned I = 0;
 473     while (I < GetCodeEntryCount (S)) {
 474
 475         CodeEntry* L[3];
 476
 477         /* Get next entry */
 478         CodeEntry* E = GetCodeEntry (S, I);
 479
 480         /* Check for the sequence */
 481         if (E->OPC == OPC_LDA                   &&
 482             GetCodeEntries (S, L, I+1, 3)       &&
 483             L[0]->OPC == OPC_LDX                &&
 484             !CodeEntryHasLabel (L[0])           &&
 485             L[1]->OPC == OPC_JSR                &&
 486             strcmp (L[1]->Arg, "bnegax") == 0   &&
 487             !CodeEntryHasLabel (L[1])           &&
 488             (L[2]->Info & OF_ZBRA) != 0) {
 489
 490             /* ldx --> ora */
 491             ReplaceOPC (L[0], OPC_ORA);
 492
 493             /* Invert the branch */
 494             ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
 495
 496             /* Delete the subroutine call */
 497             DelCodeEntry (S, I+2);
 498
 499             /* Remember, we had changes */
 500             ++Changes;
 501
 502         }
 503
 504         /* Next entry */
 505         ++I;
 506
 507     }
 508
 509     /* Return the number of changes made */
 510     return Changes;
 511 }
 512
 513
 514
 515 static unsigned OptNegAX3 (CodeSeg* S)
 516 /* Search for the sequence:
 517  *
 518  *      jsr     _xxx
 519  *      jsr     bnega(x)
 520  *      jeq/jne ...
 521  *
 522  * and replace it by:
 523  *
 524  *      jsr     _xxx
 525  *      <boolean test>
 526  *      jne/jeq ...
 527  */
 528 {
 529     unsigned Changes = 0;
 530
 531     /* Walk over the entries */
 532     unsigned I = 0;
 533     while (I < GetCodeEntryCount (S)) {
 534
 535         CodeEntry* L[2];
 536
 537         /* Get next entry */
 538         CodeEntry* E = GetCodeEntry (S, I);
 539
 540         /* Check for the sequence */
 541         if (E->OPC == OPC_JSR                   &&
 542             E->Arg[0] == '_'                    &&
 543             GetCodeEntries (S, L, I+1, 2)       &&
 544             L[0]->OPC == OPC_JSR                &&
 545             strncmp (L[0]->Arg,"bnega",5) == 0  &&
 546             !CodeEntryHasLabel (L[0])           &&
 547             (L[1]->Info & OF_ZBRA) != 0) {
 548
 549             /* Check if we're calling bnega or bnegax */
 550             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
 551
 552             /* Delete the subroutine call */
 553             DelCodeEntry (S, I+1);
 554
 555             /* Insert apropriate test code */
 556             if (ByteSized) {
 557                 /* Test bytes */
 558                 InsertCodeEntry (S, NewCodeEntry (OPC_TAX, AM_IMP, 0, 0), I+1);
 559             } else {
 560                 /* Test words */
 561                 InsertCodeEntry (S, NewCodeEntry (OPC_STX, AM_ZP, "tmp1", 0), I+1);
 562                 InsertCodeEntry (S, NewCodeEntry (OPC_ORA, AM_ZP, "tmp1", 0), I+2);
 563             }
 564
 565             /* Invert the branch */
 566             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 567
 568             /* Remember, we had changes */
 569             ++Changes;
 570
 571         }
 572
 573         /* Next entry */
 574         ++I;
 575
 576     }
 577
 578     /* Return the number of changes made */
 579     return Changes;
 580 }
 581
 582
 583
 584 /*****************************************************************************/
 585 /*                                   Code                                    */
 586 /*****************************************************************************/
 587
 588
 589
 590 /* Table with all the optimization functions */
 591 typedef struct OptFunc OptFunc;
 592 struct OptFunc {
 593     unsigned (*Func) (CodeSeg*);/* Optimizer function */
 594     const char* Name;           /* Name of optimizer step */
 595     char        Disabled;       /* True if pass disabled */
 596 };
 597
 598
 599
 600 /* Table with optimizer steps -  are called in this order */
 601 static OptFunc OptFuncs [] = {
 602     /* Optimize jump cascades */
 603     { OptJumpCascades,      "OptJumpCascades",          0       },
 604     /* Remove dead jumps */
 605     { OptDeadJumps,         "OptDeadJumps",             0       },
 606     /* Change jsr/rts to jmp */
 607     { OptRTS,               "OptRTS",                   0       },
 608     /* Remove dead code */
 609     { OptDeadCode,          "OptDeadCode",              0       },
 610     /* Optimize jump targets */
 611     { OptJumpTarget,        "OptJumpTarget",            0       },
 612     /* Optimize conditional branches */
 613     { OptCondBranches,      "OptCondBranches",          0       },
 614     /* Replace jumps to RTS by RTS */
 615     { OptRTSJumps,          "OptRTSJumps",              0       },
 616     /* Remove calls to the bool transformer subroutines */
 617     { OptBoolTransforms,    "OptBoolTransforms",        0       },
 618     /* Optimize calls to nega */
 619     { OptNegA1,             "OptNegA1",                 0       },
 620     /* Optimize calls to nega */
 621     { OptNegA2,             "OptNegA2",                 0       },
 622     /* Optimize calls to negax */
 623     { OptNegAX1,            "OptNegAX1",                0       },
 624     /* Optimize calls to negax */
 625     { OptNegAX2,            "OptNegAX2",                0       },
 626     /* Optimize calls to negax */
 627     { OptNegAX3,            "OptNegAX3",                0       },
 628     /* Remove unused loads */
 629     { OptUnusedLoads,       "OptUnusedLoads",           0       },
 630     /* Optimize branch distance */
 631     { OptBranchDist,        "OptBranchDist",            0       },
 632 };
 633
 634
 635
 636 static OptFunc* FindOptStep (const char* Name)
 637 /* Find an optimizer step by name in the table and return a pointer. Print an
 638  * error and call AbEnd if not found.
 639  */
 640 {
 641     unsigned I;
 642
 643     /* Run all optimization steps */
 644     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 645         if (strcmp (OptFuncs[I].Name, Name) == 0) {
 646             /* Found */
 647             return OptFuncs+I;
 648         }
 649     }
 650
 651     /* Not found */
 652     AbEnd ("Optimization step `%s' not found", Name);
 653     return 0;
 654 }
 655
 656
 657
 658 void DisableOpt (const char* Name)
 659 /* Disable the optimization with the given name */
 660 {
 661     OptFunc* F  = FindOptStep (Name);
 662     F->Disabled = 1;
 663 }
 664
 665
 666
 667 void EnableOpt (const char* Name)
 668 /* Enable the optimization with the given name */
 669 {
 670     OptFunc* F  = FindOptStep (Name);
 671     F->Disabled = 0;
 672 }
 673
 674
 675
 676 void RunOpt (CodeSeg* S)
 677 /* Run the optimizer */
 678 {
 679     unsigned I;
 680     unsigned Pass = 0;
 681     unsigned OptChanges;
 682
 683     /* If we shouldn't run the optimizer, bail out */
 684     if (!Optimize) {
 685         return;
 686     }
 687
 688     /* Print the name of the function we are working on */
 689     if (S->Func) {
 690         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
 691     } else {
 692         Print (stdout, 1, "Running optimizer for global code segment\n");
 693     }
 694
 695     /* Repeat all steps until there are no more changes */
 696     do {
 697         /* Reset the number of changes */
 698         OptChanges = 0;
 699
 700         /* Keep the user hapy */
 701         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
 702
 703         /* Run all optimization steps */
 704         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 705
 706             /* Print the name of the following optimizer step */
 707             Print (stdout, 1, "    %s:%*s", OptFuncs[I].Name,
 708                    (int) (30-strlen(OptFuncs[I].Name)), "");
 709
 710             /* Check if the step is disabled */
 711             if (OptFuncs[I].Disabled) {
 712                 Print (stdout, 1, "Disabled\n");
 713             } else {
 714                 unsigned Changes = OptFuncs[I].Func (S);
 715                 OptChanges += Changes;
 716                 Print (stdout, 1, "%u Changes\n", Changes);
 717             }
 718         }
 719
 720     } while (OptChanges > 0);
 721 }
 722
 723
 724