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* Code, unsigned CodeLen)
 100 /* Search for a compare condition by the given code using the given length */
 101 {
 102     unsigned I;
 103
 104     /* Linear search */
 105     for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
 106         if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
 107             /* Found */
 108             return I;
 109         }
 110     }
 111
 112     /* Not found */
 113     return CMP_INV;
 114 }
 115
 116
 117
 118 static cmp_t FindBoolCmpCond (const char* Name)
 119 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
 120 {
 121     /* Check for the correct subroutine name */
 122     if (strncmp (Name, "bool", 4) == 0) {
 123         /* Name is ok, search for the code in the table */
 124         return FindCmpCond (Name+4, strlen(Name)-4);
 125     } else {
 126         /* Not found */
 127         return CMP_INV;
 128     }
 129 }
 130
 131
 132
 133 static int FindTosCmpCond (const char* Name)
 134 /* Check if this is a call to one of the TOS compare functions (tosgtax).
 135  * Return the condition code or CMP_INV on failure.
 136  */
 137 {
 138     unsigned Len = strlen (Name);
 139
 140     /* Check for the correct subroutine name */
 141     if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
 142         /* Name is ok, search for the code in the table */
 143         return FindCmpCond (Name+3, Len-3-2);
 144     } else {
 145         /* Not found */
 146         return CMP_INV;
 147     }
 148 }
 149
 150
 151
 152 static int IsUnsignedCmp (int Code)
 153 /* Check if this is an unsigned compare */
 154 {
 155     CHECK (Code >= 0);
 156     return CmpSignedTab [Code] == 0;
 157 }
 158
 159
 160
 161 static const char* MakeBoolCmp (cmp_t Cond)
 162 /* Create the name of a bool transformer subroutine for the given code. The
 163  * result is placed into a static buffer, so beware!
 164  */
 165 {
 166     static char Buffer[20];
 167     CHECK (Cond != CMP_INV);
 168     sprintf (Buffer, "bool%s", CmpSuffixTab[Cond]);
 169     return Buffer;
 170 }
 171
 172
 173
 174 static const char* MakeTosCmp (cmp_t Cond)
 175 /* Create the name of a tos compare subroutine for the given code. The
 176  * result is placed into a static buffer, so beware!
 177  */
 178 {
 179     static char Buffer[20];
 180     CHECK (Cond != CMP_INV);
 181     sprintf (Buffer, "tos%sax", CmpSuffixTab[Cond]);
 182     return Buffer;
 183 }
 184
 185
 186
 187 static int IsBitOp (const CodeEntry* E)
 188 /* Check if E is one of the bit operations (and, or, eor) */
 189 {
 190     return (E->OPC == OPC_AND || E->OPC == OPC_ORA || E->OPC == OPC_EOR);
 191 }
 192
 193
 194
 195 static int IsCmpToZero (const CodeEntry* E)
 196 /* Check if the given instrcuction is a compare to zero instruction */
 197 {
 198     return (E->OPC == OPC_CMP             &&
 199             E->AM  == AM_IMM              &&
 200             (E->Flags & CEF_NUMARG) != 0  &&
 201             E->Num == 0);
 202 }
 203
 204
 205
 206 /*****************************************************************************/
 207 /*             Remove calls to the bool transformer subroutines              */
 208 /*****************************************************************************/
 209
 210
 211
 212 static unsigned OptBoolTransforms (CodeSeg* S)
 213 /* Try to remove the call to boolean transformer routines where the call is
 214  * not really needed.
 215  */
 216 {
 217     unsigned Changes = 0;
 218
 219     /* Walk over the entries */
 220     unsigned I = 0;
 221     while (I < GetCodeEntryCount (S)) {
 222
 223         CodeEntry* N;
 224         cmp_t Cond;
 225
 226         /* Get next entry */
 227         CodeEntry* E = GetCodeEntry (S, I);
 228
 229         /* Check for a boolean transformer */
 230         if (E->OPC == OPC_JSR                            &&
 231             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 232             (N = GetNextCodeEntry (S, I)) != 0           &&
 233             (N->Info & OF_ZBRA) != 0) {
 234
 235             CodeEntry* X;
 236             CodeLabel* L;
 237
 238             /* Make the boolean transformer unnecessary by changing the
 239              * the conditional jump to evaluate the condition flags that
 240              * are set after the compare directly. Note: jeq jumps if
 241              * the condition is not met, jne jumps if the condition is met.
 242              * Invert the code if we jump on condition not met.
 243              */
 244             if (GetBranchCond (N->OPC) == BC_EQ) {
 245                 /* Jumps if condition false, invert condition */
 246                 Cond = CmpInvertTab [Cond];
 247             }
 248
 249             /* Check if we can replace the code by something better */
 250             switch (Cond) {
 251
 252                 case CMP_EQ:
 253                     ReplaceOPC (N, OPC_JEQ);
 254                     break;
 255
 256                 case CMP_NE:
 257                     ReplaceOPC (N, OPC_JNE);
 258                     break;
 259
 260                 case CMP_GT:
 261                     /* Replace by
 262                      *     beq @L
 263                      *     jpl Target
 264                      * @L: ...
 265                      */
 266                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 267                         /* No such entry */
 268                         goto NextEntry;
 269                     }
 270                     L = GenCodeLabel (S, X);
 271                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 272                     InsertCodeEntry (S, X, I+1);
 273                     ReplaceOPC (N, OPC_JPL);
 274                     break;
 275
 276                 case CMP_GE:
 277                     ReplaceOPC (N, OPC_JPL);
 278                     break;
 279
 280                 case CMP_LT:
 281                     ReplaceOPC (N, OPC_JMI);
 282                     break;
 283
 284                 case CMP_LE:
 285                     /* Replace by
 286                      *     jmi Target
 287                      *     jeq Target
 288                      */
 289                     ReplaceOPC (N, OPC_JMI);
 290                     L = N->JumpTo;
 291                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 292                     InsertCodeEntry (S, X, I+2);
 293                     break;
 294
 295                 case CMP_UGT:
 296                     /* Replace by
 297                      *     beq @L
 298                      *     jcs Target
 299                      * @L: ...
 300                      */
 301                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 302                         /* No such entry */
 303                         goto NextEntry;
 304                     }
 305                     L = GenCodeLabel (S, X);
 306                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 307                     InsertCodeEntry (S, X, I+1);
 308                     ReplaceOPC (N, OPC_JCS);
 309                     break;
 310
 311                 case CMP_UGE:
 312                     ReplaceOPC (N, OPC_JCS);
 313                     break;
 314
 315                 case CMP_ULT:
 316                     ReplaceOPC (N, OPC_JCC);
 317                     break;
 318
 319                 case CMP_ULE:
 320                     /* Replace by
 321                      *     jcc Target
 322                      *     jeq Target
 323                      */
 324                     ReplaceOPC (N, OPC_JCC);
 325                     L = N->JumpTo;
 326                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 327                     InsertCodeEntry (S, X, I+2);
 328                     break;
 329
 330                 default:
 331                     Internal ("Unknown jump condition: %d", Cond);
 332
 333             }
 334
 335             /* Remove the call to the bool transformer */
 336             DelCodeEntry (S, I);
 337
 338             /* Remember, we had changes */
 339             ++Changes;
 340
 341         }
 342
 343 NextEntry:
 344         /* Next entry */
 345         ++I;
 346
 347     }
 348
 349     /* Return the number of changes made */
 350     return Changes;
 351 }
 352
 353
 354
 355 /*****************************************************************************/
 356 /*                        Optimizations for compares                         */
 357 /*****************************************************************************/
 358
 359
 360
 361 static unsigned OptCmp1 (CodeSeg* S)
 362 /* Search for the sequence
 363  *
 364  *      stx     xx
 365  *      stx     tmp1
 366  *      ora     tmp1
 367  *
 368  * and replace it by
 369  *
 370  *      stx     xx
 371  *      ora     xx
 372  */
 373 {
 374     unsigned Changes = 0;
 375
 376     /* Walk over the entries */
 377     unsigned I = 0;
 378     while (I < GetCodeEntryCount (S)) {
 379
 380         CodeEntry* L[2];
 381
 382         /* Get next entry */
 383         CodeEntry* E = GetCodeEntry (S, I);
 384
 385         /* Check for the sequence */
 386         if (E->OPC == OPC_STX                   &&
 387             GetCodeEntries (S, L, I+1, 2)       &&
 388             L[0]->OPC == OPC_STX                &&
 389             strcmp (L[0]->Arg, "tmp1") == 0     &&
 390             !CodeEntryHasLabel (L[0])           &&
 391             L[1]->OPC == OPC_ORA                &&
 392             strcmp (L[1]->Arg, "tmp1") == 0     &&
 393             !CodeEntryHasLabel (L[1])) {
 394
 395             /* Remove the remaining instructions */
 396             DelCodeEntries (S, I+1, 2);
 397
 398             /* Insert the ora instead */
 399             InsertCodeEntry (S, NewCodeEntry (OPC_ORA, E->AM, E->Arg, 0), I+1);
 400
 401             /* Remember, we had changes */
 402             ++Changes;
 403
 404         }
 405
 406         /* Next entry */
 407         ++I;
 408
 409     }
 410
 411     /* Return the number of changes made */
 412     return Changes;
 413 }
 414
 415
 416
 417 static unsigned OptCmp2 (CodeSeg* S)
 418 /* Search for
 419  *
 420  *      lda/and/ora/eor ...
 421  *      cmp #$00
 422  *      jeq/jne
 423  *
 424  * and remove the cmp.
 425  */
 426 {
 427     unsigned Changes = 0;
 428
 429     /* Walk over the entries */
 430     unsigned I = 0;
 431     while (I < GetCodeEntryCount (S)) {
 432
 433         CodeEntry* L[2];
 434
 435         /* Get next entry */
 436         CodeEntry* E = GetCodeEntry (S, I);
 437
 438         /* Check for the sequence */
 439         if ((E->OPC == OPC_LDA || IsBitOp (E))    &&
 440             GetCodeEntries (S, L, I+1, 2)         &&
 441             IsCmpToZero (L[0])                    &&
 442             !CodeEntryHasLabel (L[0])             &&
 443             (L[1]->Info & OF_FBRA) != 0           &&
 444             !CodeEntryHasLabel (L[1])) {
 445
 446             /* Remove the compare */
 447             DelCodeEntry (S, I+1);
 448
 449             /* Remember, we had changes */
 450             ++Changes;
 451
 452         }
 453
 454         /* Next entry */
 455         ++I;
 456
 457     }
 458
 459     /* Return the number of changes made */
 460     return Changes;
 461 }
 462
 463
 464
 465 static unsigned OptCmp3 (CodeSeg* S)
 466 /* Search for
 467  *
 468  *      lda     x
 469  *      ldx     y
 470  *      cpx     #a
 471  *      bne     L1
 472  *      cmp     #b
 473  *      jne/jeq L2
 474  *
 475  * If a is zero, we may remove the compare. If a and b are both zero, we may
 476  * replace it by the sequence
 477  *
 478  *      lda     x
 479  *      ora     x+1
 480  *      jne/jeq ...
 481  *
 482  * L1 may be either the label at the branch instruction, or the target label
 483  * of this instruction.
 484  */
 485 {
 486     unsigned Changes = 0;
 487
 488     /* Walk over the entries */
 489     unsigned I = 0;
 490     while (I < GetCodeEntryCount (S)) {
 491
 492         CodeEntry* L[5];
 493
 494         /* Get next entry */
 495         CodeEntry* E = GetCodeEntry (S, I);
 496
 497         /* Check for the sequence */
 498         if (E->OPC == OPC_LDA                                                &&
 499             GetCodeEntries (S, L, I+1, 5)                                    &&
 500             L[0]->OPC == OPC_LDX                                             &&
 501             !CodeEntryHasLabel (L[0])                                        &&
 502             L[1]->OPC == OPC_CPX                                             &&
 503             L[1]->AM == AM_IMM                                               &&
 504             (L[1]->Flags & CEF_NUMARG) != 0                                  &&
 505             !CodeEntryHasLabel (L[1])                                        &&
 506             (L[2]->OPC == OPC_JNE || L[2]->OPC == OPC_BNE)                   &&
 507             L[2]->JumpTo != 0                                                &&
 508             !CodeEntryHasLabel (L[2])                                        &&
 509             L[3]->OPC == OPC_CMP                                             &&
 510             L[3]->AM == AM_IMM                                               &&
 511             (L[3]->Flags & CEF_NUMARG) != 0                                  &&
 512             (L[4]->Info & OF_ZBRA) != 0                                      &&
 513             L[4]->JumpTo != 0                                                &&
 514             (L[2]->JumpTo->Owner == L[4] || L[2]->JumpTo == L[4]->JumpTo)) {
 515
 516             /* Get the compare value */
 517             unsigned Val = ((L[1]->Num & 0xFF) << 8) | (L[3]->Num & 0xFF);
 518
 519             if (Val == 0) {
 520                 /* The value is zero, we may use the simple code version. */
 521                 ReplaceOPC (L[0], OPC_ORA);
 522                 DelCodeEntries (S, I+2, 3);
 523             } else {
 524                 /* Move the lda instruction after the first branch */
 525                 CodeEntry* N = RetrieveCodeEntry (S, I);
 526                 InsertCodeEntry (S, N, I+3);
 527
 528                 /* Replace the ldx/cpx by lda/cmp */
 529                 ReplaceOPC (L[0], OPC_LDA);
 530                 ReplaceOPC (L[1], OPC_CMP);
 531
 532                 /* The high byte is zero, remove the CMP */
 533                 if ((Val & 0xFF00) == 0) {
 534                     DelCodeEntry (S, I+1);
 535                 }
 536             }
 537
 538             ++Changes;
 539         }
 540
 541         /* Next entry */
 542         ++I;
 543
 544     }
 545
 546     /* Return the number of changes made */
 547     return Changes;
 548 }
 549
 550
 551
 552 /*****************************************************************************/
 553 /*                            nega optimizations                             */
 554 /*****************************************************************************/
 555
 556
 557
 558 static unsigned OptNegA1 (CodeSeg* S)
 559 /* Check for
 560  *
 561  *      ldx     #$00
 562  *      lda     ..
 563  *      jsr     bnega
 564  *
 565  * Remove the ldx if the lda does not use it.
 566  */
 567 {
 568     unsigned Changes = 0;
 569
 570     /* Walk over the entries */
 571     unsigned I = 0;
 572     while (I < GetCodeEntryCount (S)) {
 573
 574         CodeEntry* L[2];
 575
 576         /* Get next entry */
 577         CodeEntry* E = GetCodeEntry (S, I);
 578
 579         /* Check for a ldx */
 580         if (E->OPC == OPC_LDX                   &&
 581             E->AM == AM_IMM                     &&
 582             (E->Flags & CEF_NUMARG) != 0        &&
 583             E->Num == 0                         &&
 584             GetCodeEntries (S, L, I+1, 2)       &&
 585             L[0]->OPC == OPC_LDA                &&
 586             (L[0]->Use & REG_X) == 0            &&
 587             L[1]->OPC == OPC_JSR                &&
 588             strcmp (L[1]->Arg, "bnega") == 0) {
 589
 590             /* Remove the ldx instruction */
 591             DelCodeEntry (S, I);
 592
 593             /* Remember, we had changes */
 594             ++Changes;
 595
 596         }
 597
 598         /* Next entry */
 599         ++I;
 600
 601     }
 602
 603     /* Return the number of changes made */
 604     return Changes;
 605 }
 606
 607
 608
 609 static unsigned OptNegA2 (CodeSeg* S)
 610 /* Check for
 611  *
 612  *      lda     ..
 613  *      jsr     bnega
 614  *      jeq/jne ..
 615  *
 616  * Adjust the conditional branch and remove the call to the subroutine.
 617  */
 618 {
 619     unsigned Changes = 0;
 620
 621     /* Walk over the entries */
 622     unsigned I = 0;
 623     while (I < GetCodeEntryCount (S)) {
 624
 625         CodeEntry* L[2];
 626
 627         /* Get next entry */
 628         CodeEntry* E = GetCodeEntry (S, I);
 629
 630         /* Check for the sequence */
 631         if (E->OPC == OPC_LDA                   &&
 632             GetCodeEntries (S, L, I+1, 2)       &&
 633             L[0]->OPC == OPC_JSR                &&
 634             strcmp (L[0]->Arg, "bnega") == 0    &&
 635             !CodeEntryHasLabel (L[0])           &&
 636             (L[1]->Info & OF_ZBRA) != 0) {
 637
 638             /* Invert the branch */
 639             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 640
 641             /* Delete the subroutine call */
 642             DelCodeEntry (S, I+1);
 643
 644             /* Remember, we had changes */
 645             ++Changes;
 646
 647         }
 648
 649         /* Next entry */
 650         ++I;
 651
 652     }
 653
 654     /* Return the number of changes made */
 655     return Changes;
 656 }
 657
 658
 659
 660 /*****************************************************************************/
 661 /*                            negax optimizations                            */
 662 /*****************************************************************************/
 663
 664
 665
 666 static unsigned OptNegAX1 (CodeSeg* S)
 667 /* Search for the sequence:
 668  *
 669  *      lda     (xx),y
 670  *      tax
 671  *      dey
 672  *      lda     (xx),y
 673  *      jsr     bnegax
 674  *      jne/jeq ...
 675  *
 676  * and replace it by
 677  *
 678  *      lda     (xx),y
 679  *      dey
 680  *      ora     (xx),y
 681  *      jeq/jne ...
 682  */
 683 {
 684     unsigned Changes = 0;
 685
 686     /* Walk over the entries */
 687     unsigned I = 0;
 688     while (I < GetCodeEntryCount (S)) {
 689
 690         CodeEntry* L[5];
 691
 692         /* Get next entry */
 693         CodeEntry* E = GetCodeEntry (S, I);
 694
 695         /* Check for the sequence */
 696         if (E->OPC == OPC_LDA                   &&
 697             E->AM == AM_ZP_INDY                 &&
 698             GetCodeEntries (S, L, I+1, 5)       &&
 699             L[0]->OPC == OPC_TAX                &&
 700             L[1]->OPC == OPC_DEY                &&
 701             L[2]->OPC == OPC_LDA                &&
 702             L[2]->AM == AM_ZP_INDY              &&
 703             strcmp (L[2]->Arg, E->Arg) == 0     &&
 704             !CodeEntryHasLabel (L[2])           &&
 705             L[3]->OPC == OPC_JSR                &&
 706             strcmp (L[3]->Arg, "bnegax") == 0   &&
 707             !CodeEntryHasLabel (L[3])           &&
 708             (L[4]->Info & OF_ZBRA) != 0) {
 709
 710             /* lda --> ora */
 711             ReplaceOPC (L[2], OPC_ORA);
 712
 713             /* Invert the branch */
 714             ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
 715
 716             /* Delete the entries no longer needed. Beware: Deleting entries
 717              * will change the indices.
 718              */
 719             DelCodeEntry (S, I+4);              /* jsr bnegax */
 720             DelCodeEntry (S, I+1);              /* tax */
 721
 722             /* Remember, we had changes */
 723             ++Changes;
 724
 725         }
 726
 727         /* Next entry */
 728         ++I;
 729
 730     }
 731
 732     /* Return the number of changes made */
 733     return Changes;
 734 }
 735
 736
 737
 738 static unsigned OptNegAX2 (CodeSeg* S)
 739 /* Search for the sequence:
 740  *
 741  *      lda     xx
 742  *      ldx     yy
 743  *      jsr     bnegax
 744  *      jne/jeq ...
 745  *
 746  * and replace it by
 747  *
 748  *      lda     xx
 749  *      ora     xx+1
 750  *      jeq/jne ...
 751  */
 752 {
 753     unsigned Changes = 0;
 754
 755     /* Walk over the entries */
 756     unsigned I = 0;
 757     while (I < GetCodeEntryCount (S)) {
 758
 759         CodeEntry* L[3];
 760
 761         /* Get next entry */
 762         CodeEntry* E = GetCodeEntry (S, I);
 763
 764         /* Check for the sequence */
 765         if (E->OPC == OPC_LDA                   &&
 766             GetCodeEntries (S, L, I+1, 3)       &&
 767             L[0]->OPC == OPC_LDX                &&
 768             !CodeEntryHasLabel (L[0])           &&
 769             L[1]->OPC == OPC_JSR                &&
 770             strcmp (L[1]->Arg, "bnegax") == 0   &&
 771             !CodeEntryHasLabel (L[1])           &&
 772             (L[2]->Info & OF_ZBRA) != 0) {
 773
 774             /* ldx --> ora */
 775             ReplaceOPC (L[0], OPC_ORA);
 776
 777             /* Invert the branch */
 778             ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
 779
 780             /* Delete the subroutine call */
 781             DelCodeEntry (S, I+2);
 782
 783             /* Remember, we had changes */
 784             ++Changes;
 785
 786         }
 787
 788         /* Next entry */
 789         ++I;
 790
 791     }
 792
 793     /* Return the number of changes made */
 794     return Changes;
 795 }
 796
 797
 798
 799 static unsigned OptNegAX3 (CodeSeg* S)
 800 /* Search for the sequence:
 801  *
 802  *      jsr     _xxx
 803  *      jsr     bnega(x)
 804  *      jeq/jne ...
 805  *
 806  * and replace it by:
 807  *
 808  *      jsr     _xxx
 809  *      <boolean test>
 810  *      jne/jeq ...
 811  */
 812 {
 813     unsigned Changes = 0;
 814
 815     /* Walk over the entries */
 816     unsigned I = 0;
 817     while (I < GetCodeEntryCount (S)) {
 818
 819         CodeEntry* L[2];
 820
 821         /* Get next entry */
 822         CodeEntry* E = GetCodeEntry (S, I);
 823
 824         /* Check for the sequence */
 825         if (E->OPC == OPC_JSR                   &&
 826             E->Arg[0] == '_'                    &&
 827             GetCodeEntries (S, L, I+1, 2)       &&
 828             L[0]->OPC == OPC_JSR                &&
 829             strncmp (L[0]->Arg,"bnega",5) == 0  &&
 830             !CodeEntryHasLabel (L[0])           &&
 831             (L[1]->Info & OF_ZBRA) != 0) {
 832
 833             /* Check if we're calling bnega or bnegax */
 834             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
 835
 836             /* Delete the subroutine call */
 837             DelCodeEntry (S, I+1);
 838
 839             /* Insert apropriate test code */
 840             if (ByteSized) {
 841                 /* Test bytes */
 842                 InsertCodeEntry (S, NewCodeEntry (OPC_TAX, AM_IMP, 0, 0), I+1);
 843             } else {
 844                 /* Test words */
 845                 InsertCodeEntry (S, NewCodeEntry (OPC_STX, AM_ZP, "tmp1", 0), I+1);
 846                 InsertCodeEntry (S, NewCodeEntry (OPC_ORA, AM_ZP, "tmp1", 0), I+2);
 847             }
 848
 849             /* Invert the branch */
 850             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 851
 852             /* Remember, we had changes */
 853             ++Changes;
 854
 855         }
 856
 857         /* Next entry */
 858         ++I;
 859
 860     }
 861
 862     /* Return the number of changes made */
 863     return Changes;
 864 }
 865
 866
 867
 868 /*****************************************************************************/
 869 /*                                   Code                                    */
 870 /*****************************************************************************/
 871
 872
 873
 874 /* Table with all the optimization functions */
 875 typedef struct OptFunc OptFunc;
 876 struct OptFunc {
 877     unsigned (*Func) (CodeSeg*);/* Optimizer function */
 878     const char* Name;           /* Name of optimizer step */
 879     char        Disabled;       /* True if pass disabled */
 880 };
 881
 882
 883
 884 /* Table with optimizer steps -  are called in this order */
 885 static OptFunc OptFuncs [] = {
 886     /* Optimize jump cascades */
 887     { OptJumpCascades,      "OptJumpCascades",          0       },
 888     /* Remove dead jumps */
 889     { OptDeadJumps,         "OptDeadJumps",             0       },
 890     /* Change jsr/rts to jmp */
 891     { OptRTS,               "OptRTS",                   0       },
 892     /* Remove dead code */
 893     { OptDeadCode,          "OptDeadCode",              0       },
 894     /* Optimize jump targets */
 895     { OptJumpTarget,        "OptJumpTarget",            0       },
 896     /* Optimize conditional branches */
 897     { OptCondBranches,      "OptCondBranches",          0       },
 898     /* Replace jumps to RTS by RTS */
 899     { OptRTSJumps,          "OptRTSJumps",              0       },
 900     /* Remove calls to the bool transformer subroutines */
 901     { OptBoolTransforms,    "OptBoolTransforms",        0       },
 902     /* Optimize calls to nega */
 903     { OptNegA1,             "OptNegA1",                 0       },
 904     /* Optimize calls to nega */
 905     { OptNegA2,             "OptNegA2",                 0       },
 906     /* Optimize calls to negax */
 907     { OptNegAX1,            "OptNegAX1",                0       },
 908     /* Optimize calls to negax */
 909     { OptNegAX2,            "OptNegAX2",                0       },
 910     /* Optimize calls to negax */
 911     { OptNegAX3,            "OptNegAX3",                0       },
 912     /* Optimize compares */
 913     { OptCmp1,              "OptCmp1",                  0       },
 914     /* Optimize compares */
 915     { OptCmp2,              "OptCmp2",                  0       },
 916     /* Optimize compares */
 917     { OptCmp3,              "OptCmp3",                  0       },
 918     /* Remove unused loads */
 919     { OptUnusedLoads,       "OptUnusedLoads",           0       },
 920     /* Optimize branch distance */
 921     { OptBranchDist,        "OptBranchDist",            0       },
 922 };
 923
 924
 925
 926 static OptFunc* FindOptStep (const char* Name)
 927 /* Find an optimizer step by name in the table and return a pointer. Print an
 928  * error and call AbEnd if not found.
 929  */
 930 {
 931     unsigned I;
 932
 933     /* Run all optimization steps */
 934     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 935         if (strcmp (OptFuncs[I].Name, Name) == 0) {
 936             /* Found */
 937             return OptFuncs+I;
 938         }
 939     }
 940
 941     /* Not found */
 942     AbEnd ("Optimization step `%s' not found", Name);
 943     return 0;
 944 }
 945
 946
 947
 948 void DisableOpt (const char* Name)
 949 /* Disable the optimization with the given name */
 950 {
 951     OptFunc* F  = FindOptStep (Name);
 952     F->Disabled = 1;
 953 }
 954
 955
 956
 957 void EnableOpt (const char* Name)
 958 /* Enable the optimization with the given name */
 959 {
 960     OptFunc* F  = FindOptStep (Name);
 961     F->Disabled = 0;
 962 }
 963
 964
 965
 966 void RunOpt (CodeSeg* S)
 967 /* Run the optimizer */
 968 {
 969     unsigned I;
 970     unsigned Pass = 0;
 971     unsigned OptChanges;
 972
 973     /* If we shouldn't run the optimizer, bail out */
 974     if (!Optimize) {
 975         return;
 976     }
 977
 978     /* Print the name of the function we are working on */
 979     if (S->Func) {
 980         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
 981     } else {
 982         Print (stdout, 1, "Running optimizer for global code segment\n");
 983     }
 984
 985     /* Repeat all steps until there are no more changes */
 986     do {
 987         /* Reset the number of changes */
 988         OptChanges = 0;
 989
 990         /* Keep the user hapy */
 991         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
 992
 993         /* Run all optimization steps */
 994         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 995
 996             /* Print the name of the following optimizer step */
 997             Print (stdout, 1, "    %s:%*s", OptFuncs[I].Name,
 998                    (int) (30-strlen(OptFuncs[I].Name)), "");
 999
1000             /* Check if the step is disabled */
1001             if (OptFuncs[I].Disabled) {
1002                 Print (stdout, 1, "Disabled\n");
1003             } else {
1004                 unsigned Changes = OptFuncs[I].Func (S);
1005                 OptChanges += Changes;
1006                 Print (stdout, 1, "%u Changes\n", Changes);
1007             }
1008         }
1009
1010     } while (OptChanges > 0);
1011 }
1012
1013
1014