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 static int IsSpLoad (const CodeEntry* E)
 207 /* Return true if this is the load of A from the stack */
 208 {
 209     return E->OPC == OPC_LDA && E->AM == AM_ZP_INDY && strcmp (E->Arg, "sp") == 0;
 210 }
 211
 212
 213
 214 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
 215                           CodeEntry** L, unsigned Count)
 216 /* Check if a 16 bit load of a local variable follows:
 217  *
 218  *      ldy     #$xx
 219  *      lda     (sp),y
 220  *      tax
 221  *      dey
 222  *      lda     (sp),y
 223  *
 224  * If so, read Count entries following the first ldy into L and return true
 225  * if this is possible. Otherwise return false.
 226  */
 227 {
 228     /* Be sure we read enough entries for the check */
 229     CHECK (Count >= 5);
 230
 231     /* Read the first entry */
 232     L[0] = GetCodeEntry (S, Index);
 233
 234     /* Check for the sequence */
 235     return (L[0]->OPC == OPC_LDY                      &&
 236             L[0]->AM == AM_IMM                        &&
 237             (L[0]->Flags & CEF_NUMARG) != 0           &&
 238             GetCodeEntries (S, L+1, Index+1, Count-1) &&
 239             IsSpLoad (L[1])                           &&
 240             !CodeEntryHasLabel (L[1])                 &&
 241             L[2]->OPC == OPC_TAX                      &&
 242             !CodeEntryHasLabel (L[2])                 &&
 243             L[3]->OPC == OPC_DEY                      &&
 244             !CodeEntryHasLabel (L[3])                 &&
 245             IsSpLoad (L[4])                           &&
 246             !CodeEntryHasLabel (L[4]));
 247 }
 248
 249
 250
 251 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
 252 /* Check if the instructions at L are an immidiate compare of a/x:
 253  *
 254  *
 255  */
 256 {
 257     return (L[0]->OPC == OPC_CPX                                             &&
 258             L[0]->AM == AM_IMM                                               &&
 259             (L[0]->Flags & CEF_NUMARG) != 0                                  &&
 260             !CodeEntryHasLabel (L[0])                                        &&
 261             (L[1]->OPC == OPC_JNE || L[1]->OPC == OPC_BNE)                   &&
 262             L[1]->JumpTo != 0                                                &&
 263             !CodeEntryHasLabel (L[1])                                        &&
 264             L[2]->OPC == OPC_CMP                                             &&
 265             L[2]->AM == AM_IMM                                               &&
 266             (L[2]->Flags & CEF_NUMARG) != 0                                  &&
 267             (L[3]->Info & OF_ZBRA) != 0                                      &&
 268             L[3]->JumpTo != 0                                                &&
 269             (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
 270 }
 271
 272
 273
 274 /*****************************************************************************/
 275 /*             Remove calls to the bool transformer subroutines              */
 276 /*****************************************************************************/
 277
 278
 279
 280 static unsigned OptBoolTransforms (CodeSeg* S)
 281 /* Try to remove the call to boolean transformer routines where the call is
 282  * not really needed.
 283  */
 284 {
 285     unsigned Changes = 0;
 286
 287     /* Walk over the entries */
 288     unsigned I = 0;
 289     while (I < GetCodeEntryCount (S)) {
 290
 291         CodeEntry* N;
 292         cmp_t Cond;
 293
 294         /* Get next entry */
 295         CodeEntry* E = GetCodeEntry (S, I);
 296
 297         /* Check for a boolean transformer */
 298         if (E->OPC == OPC_JSR                            &&
 299             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 300             (N = GetNextCodeEntry (S, I)) != 0           &&
 301             (N->Info & OF_ZBRA) != 0) {
 302
 303             CodeEntry* X;
 304             CodeLabel* L;
 305
 306             /* Make the boolean transformer unnecessary by changing the
 307              * the conditional jump to evaluate the condition flags that
 308              * are set after the compare directly. Note: jeq jumps if
 309              * the condition is not met, jne jumps if the condition is met.
 310              * Invert the code if we jump on condition not met.
 311              */
 312             if (GetBranchCond (N->OPC) == BC_EQ) {
 313                 /* Jumps if condition false, invert condition */
 314                 Cond = CmpInvertTab [Cond];
 315             }
 316
 317             /* Check if we can replace the code by something better */
 318             switch (Cond) {
 319
 320                 case CMP_EQ:
 321                     ReplaceOPC (N, OPC_JEQ);
 322                     break;
 323
 324                 case CMP_NE:
 325                     ReplaceOPC (N, OPC_JNE);
 326                     break;
 327
 328                 case CMP_GT:
 329                     /* Replace by
 330                      *     beq @L
 331                      *     jpl Target
 332                      * @L: ...
 333                      */
 334                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 335                         /* No such entry */
 336                         goto NextEntry;
 337                     }
 338                     L = GenCodeLabel (S, X);
 339                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 340                     InsertCodeEntry (S, X, I+1);
 341                     ReplaceOPC (N, OPC_JPL);
 342                     break;
 343
 344                 case CMP_GE:
 345                     ReplaceOPC (N, OPC_JPL);
 346                     break;
 347
 348                 case CMP_LT:
 349                     ReplaceOPC (N, OPC_JMI);
 350                     break;
 351
 352                 case CMP_LE:
 353                     /* Replace by
 354                      *     jmi Target
 355                      *     jeq Target
 356                      */
 357                     ReplaceOPC (N, OPC_JMI);
 358                     L = N->JumpTo;
 359                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 360                     InsertCodeEntry (S, X, I+2);
 361                     break;
 362
 363                 case CMP_UGT:
 364                     /* Replace by
 365                      *     beq @L
 366                      *     jcs Target
 367                      * @L: ...
 368                      */
 369                     if ((X = GetNextCodeEntry (S, I+1)) == 0) {
 370                         /* No such entry */
 371                         goto NextEntry;
 372                     }
 373                     L = GenCodeLabel (S, X);
 374                     X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
 375                     InsertCodeEntry (S, X, I+1);
 376                     ReplaceOPC (N, OPC_JCS);
 377                     break;
 378
 379                 case CMP_UGE:
 380                     ReplaceOPC (N, OPC_JCS);
 381                     break;
 382
 383                 case CMP_ULT:
 384                     ReplaceOPC (N, OPC_JCC);
 385                     break;
 386
 387                 case CMP_ULE:
 388                     /* Replace by
 389                      *     jcc Target
 390                      *     jeq Target
 391                      */
 392                     ReplaceOPC (N, OPC_JCC);
 393                     L = N->JumpTo;
 394                     X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
 395                     InsertCodeEntry (S, X, I+2);
 396                     break;
 397
 398                 default:
 399                     Internal ("Unknown jump condition: %d", Cond);
 400
 401             }
 402
 403             /* Remove the call to the bool transformer */
 404             DelCodeEntry (S, I);
 405
 406             /* Remember, we had changes */
 407             ++Changes;
 408
 409         }
 410
 411 NextEntry:
 412         /* Next entry */
 413         ++I;
 414
 415     }
 416
 417     /* Return the number of changes made */
 418     return Changes;
 419 }
 420
 421
 422
 423 /*****************************************************************************/
 424 /*                           Optimize subtractions                           */
 425 /*****************************************************************************/
 426
 427
 428
 429 static unsigned OptSub1 (CodeSeg* S)
 430 /* Search for the sequence
 431  *
 432  *      sbc     ...
 433  *      bcs     L
 434  *      dex
 435  * L:
 436  *
 437  * and remove the handling of the high byte if X is not used later.
 438  */
 439 {
 440     unsigned Changes = 0;
 441
 442     /* Walk over the entries */
 443     unsigned I = 0;
 444     while (I < GetCodeEntryCount (S)) {
 445
 446         CodeEntry* L[3];
 447
 448         /* Get next entry */
 449         CodeEntry* E = GetCodeEntry (S, I);
 450
 451         /* Check for the sequence */
 452         if (E->OPC == OPC_SBC                              &&
 453             GetCodeEntries (S, L, I+1, 3)                  &&
 454             (L[0]->OPC == OPC_BCS || L[0]->OPC == OPC_JCS) &&
 455             L[0]->JumpTo != 0                              &&
 456             !CodeEntryHasLabel (L[0])                      &&
 457             L[1]->OPC == OPC_DEX                           &&
 458             !CodeEntryHasLabel (L[1])                      &&
 459             L[0]->JumpTo->Owner == L[2]                    &&
 460             !RegXUsed (S, I+3)) {
 461
 462             /* Remove the bcs/dex */
 463             DelCodeEntries (S, I+1, 2);
 464
 465             /* Remember, we had changes */
 466             ++Changes;
 467
 468         }
 469
 470         /* Next entry */
 471         ++I;
 472
 473     }
 474
 475     /* Return the number of changes made */
 476     return Changes;
 477 }
 478
 479
 480
 481 static unsigned OptSub2 (CodeSeg* S)
 482 /* Search for the sequence
 483  *
 484  *      lda     xx
 485  *      sec
 486  *      sta     tmp1
 487  *      lda     yy
 488  *      sbc     tmp1
 489  *      sta     yy
 490  *
 491  * and replace it by
 492  *
 493  *      sec
 494  *      lda     yy
 495  *      sbc     xx
 496  *      sta     yy
 497  */
 498 {
 499     unsigned Changes = 0;
 500
 501     /* Walk over the entries */
 502     unsigned I = 0;
 503     while (I < GetCodeEntryCount (S)) {
 504
 505         CodeEntry* L[5];
 506
 507         /* Get next entry */
 508         CodeEntry* E = GetCodeEntry (S, I);
 509
 510         /* Check for the sequence */
 511         if (E->OPC == OPC_LDA                              &&
 512             GetCodeEntries (S, L, I+1, 5)                  &&
 513             L[0]->OPC == OPC_SEC                           &&
 514             !CodeEntryHasLabel (L[0])                      &&
 515             L[1]->OPC == OPC_STA                           &&
 516             strcmp (L[1]->Arg, "tmp1") == 0                &&
 517             !CodeEntryHasLabel (L[1])                      &&
 518             L[2]->OPC == OPC_LDA                           &&
 519             !CodeEntryHasLabel (L[2])                      &&
 520             L[3]->OPC == OPC_SBC                           &&
 521             strcmp (L[3]->Arg, "tmp1") == 0                &&
 522             !CodeEntryHasLabel (L[3])                      &&
 523             L[4]->OPC == OPC_STA                           &&
 524             strcmp (L[4]->Arg, L[2]->Arg) == 0             &&
 525             !CodeEntryHasLabel (L[4])) {
 526
 527             /* Remove the store to tmp1 */
 528             DelCodeEntry (S, I+2);
 529
 530             /* Remove the subtraction */
 531             DelCodeEntry (S, I+3);
 532
 533             /* Move the lda to the position of the subtraction and change the
 534              * op to SBC.
 535              */
 536             MoveCodeEntry (S, I, I+3);
 537             ReplaceOPC (E, OPC_SBC);
 538
 539             /* Remember, we had changes */
 540             ++Changes;
 541
 542         }
 543
 544         /* Next entry */
 545         ++I;
 546
 547     }
 548
 549     /* Return the number of changes made */
 550     return Changes;
 551 }
 552
 553
 554
 555 /*****************************************************************************/
 556 /*                            Optimize additions                             */
 557 /*****************************************************************************/
 558
 559
 560
 561 static unsigned OptAdd1 (CodeSeg* S)
 562 /* Search for the sequence
 563  *
 564  *      adc     ...
 565  *      bcc     L
 566  *      inx
 567  * L:
 568  *
 569  * and remove the handling of the high byte if X is not used later.
 570  */
 571 {
 572     unsigned Changes = 0;
 573
 574     /* Walk over the entries */
 575     unsigned I = 0;
 576     while (I < GetCodeEntryCount (S)) {
 577
 578         CodeEntry* L[3];
 579
 580         /* Get next entry */
 581         CodeEntry* E = GetCodeEntry (S, I);
 582
 583         /* Check for the sequence */
 584         if (E->OPC == OPC_ADC                              &&
 585             GetCodeEntries (S, L, I+1, 3)                  &&
 586             (L[0]->OPC == OPC_BCC || L[0]->OPC == OPC_JCC) &&
 587             L[0]->JumpTo != 0                              &&
 588             !CodeEntryHasLabel (L[0])                      &&
 589             L[1]->OPC == OPC_INX                           &&
 590             !CodeEntryHasLabel (L[1])                      &&
 591             L[0]->JumpTo->Owner == L[2]                    &&
 592             !RegXUsed (S, I+3)) {
 593
 594             /* Remove the bcs/dex */
 595             DelCodeEntries (S, I+1, 2);
 596
 597             /* Remember, we had changes */
 598             ++Changes;
 599
 600         }
 601
 602         /* Next entry */
 603         ++I;
 604
 605     }
 606
 607     /* Return the number of changes made */
 608     return Changes;
 609 }
 610
 611
 612
 613 /*****************************************************************************/
 614 /*                        Optimizations for compares                         */
 615 /*****************************************************************************/
 616
 617
 618
 619 static unsigned OptCmp1 (CodeSeg* S)
 620 /* Search for the sequence
 621  *
 622  *      stx     xx
 623  *      stx     tmp1
 624  *      ora     tmp1
 625  *
 626  * and replace it by
 627  *
 628  *      stx     xx
 629  *      ora     xx
 630  */
 631 {
 632     unsigned Changes = 0;
 633
 634     /* Walk over the entries */
 635     unsigned I = 0;
 636     while (I < GetCodeEntryCount (S)) {
 637
 638         CodeEntry* L[2];
 639
 640         /* Get next entry */
 641         CodeEntry* E = GetCodeEntry (S, I);
 642
 643         /* Check for the sequence */
 644         if (E->OPC == OPC_STX                   &&
 645             GetCodeEntries (S, L, I+1, 2)       &&
 646             L[0]->OPC == OPC_STX                &&
 647             strcmp (L[0]->Arg, "tmp1") == 0     &&
 648             !CodeEntryHasLabel (L[0])           &&
 649             L[1]->OPC == OPC_ORA                &&
 650             strcmp (L[1]->Arg, "tmp1") == 0     &&
 651             !CodeEntryHasLabel (L[1])) {
 652
 653             /* Remove the remaining instructions */
 654             DelCodeEntries (S, I+1, 2);
 655
 656             /* Insert the ora instead */
 657             InsertCodeEntry (S, NewCodeEntry (OPC_ORA, E->AM, E->Arg, 0), I+1);
 658
 659             /* Remember, we had changes */
 660             ++Changes;
 661
 662         }
 663
 664         /* Next entry */
 665         ++I;
 666
 667     }
 668
 669     /* Return the number of changes made */
 670     return Changes;
 671 }
 672
 673
 674
 675 static unsigned OptCmp2 (CodeSeg* S)
 676 /* Search for
 677  *
 678  *      lda/and/ora/eor ...
 679  *      cmp #$00
 680  *      jeq/jne
 681  *
 682  * and remove the cmp.
 683  */
 684 {
 685     unsigned Changes = 0;
 686
 687     /* Walk over the entries */
 688     unsigned I = 0;
 689     while (I < GetCodeEntryCount (S)) {
 690
 691         CodeEntry* L[2];
 692
 693         /* Get next entry */
 694         CodeEntry* E = GetCodeEntry (S, I);
 695
 696         /* Check for the sequence */
 697         if ((E->OPC == OPC_LDA || IsBitOp (E))    &&
 698             GetCodeEntries (S, L, I+1, 2)         &&
 699             IsCmpToZero (L[0])                    &&
 700             !CodeEntryHasLabel (L[0])             &&
 701             (L[1]->Info & OF_FBRA) != 0           &&
 702             !CodeEntryHasLabel (L[1])) {
 703
 704             /* Remove the compare */
 705             DelCodeEntry (S, I+1);
 706
 707             /* Remember, we had changes */
 708             ++Changes;
 709
 710         }
 711
 712         /* Next entry */
 713         ++I;
 714
 715     }
 716
 717     /* Return the number of changes made */
 718     return Changes;
 719 }
 720
 721
 722
 723 static unsigned OptCmp3 (CodeSeg* S)
 724 /* Search for
 725  *
 726  *      lda     x
 727  *      ldx     y
 728  *      cpx     #a
 729  *      bne     L1
 730  *      cmp     #b
 731  *      jne/jeq L2
 732  *
 733  * If a is zero, we may remove the compare. If a and b are both zero, we may
 734  * replace it by the sequence
 735  *
 736  *      lda     x
 737  *      ora     x+1
 738  *      jne/jeq ...
 739  *
 740  * L1 may be either the label at the branch instruction, or the target label
 741  * of this instruction.
 742  */
 743 {
 744     unsigned Changes = 0;
 745
 746     /* Walk over the entries */
 747     unsigned I = 0;
 748     while (I < GetCodeEntryCount (S)) {
 749
 750         CodeEntry* L[5];
 751
 752         /* Get next entry */
 753         CodeEntry* E = GetCodeEntry (S, I);
 754
 755         /* Check for the sequence */
 756         if (E->OPC == OPC_LDA                                                &&
 757             GetCodeEntries (S, L, I+1, 5)                                    &&
 758             L[0]->OPC == OPC_LDX                                             &&
 759             !CodeEntryHasLabel (L[0])                                        &&
 760             IsImmCmp16 (S, L+1)) {
 761
 762             if (L[1]->Num == 0 && L[3]->Num == 0) {
 763                 /* The value is zero, we may use the simple code version. */
 764                 ReplaceOPC (L[0], OPC_ORA);
 765                 DelCodeEntries (S, I+2, 3);
 766             } else {
 767                 /* Move the lda instruction after the first branch. This will
 768                  * improve speed, since the load is delayed after the first
 769                  * test.
 770                  */
 771                 MoveCodeEntry (S, I, I+4);
 772
 773                 /* We will replace the ldx/cpx by lda/cmp */
 774                 ReplaceOPC (L[0], OPC_LDA);
 775                 ReplaceOPC (L[1], OPC_CMP);
 776
 777             }
 778
 779             ++Changes;
 780         }
 781
 782         /* Next entry */
 783         ++I;
 784
 785     }
 786
 787     /* Return the number of changes made */
 788     return Changes;
 789 }
 790
 791
 792
 793 static unsigned OptCmp4 (CodeSeg* S)
 794 /* Optimize compares of local variables:
 795  *
 796  *      ldy     #o
 797  *      lda     (sp),y
 798  *      tax
 799  *      dey
 800  *      lda     (sp),y
 801  *      cpx     #a
 802  *      bne     L1
 803  *      cmp     #b
 804  *      jne/jeq L2
 805  */
 806 {
 807     unsigned Changes = 0;
 808
 809     /* Walk over the entries */
 810     unsigned I = 0;
 811     while (I < GetCodeEntryCount (S)) {
 812
 813         CodeEntry* L[9];
 814
 815         /* Check for the sequence */
 816         if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
 817
 818             if (L[5]->Num == 0 && L[7]->Num == 0) {
 819
 820                 /* The value is zero, we may use the simple code version:
 821                  *      ldy     #o
 822                  *      lda     (sp),y
 823                  *      dey
 824                  *      ora     (sp),y
 825                  *      jne/jeq ...
 826                  */
 827                 ReplaceOPC (L[4], OPC_ORA);
 828                 DelCodeEntries (S, I+5, 3);   /* cpx/bne/cmp */
 829                 DelCodeEntry (S, I+2);        /* tax */
 830
 831             } else {
 832
 833                 /* Change the code to just use the A register. Move the load
 834                  * of the low byte after the first branch if possible:
 835                  *
 836                  *      ldy     #o
 837                  *      lda     (sp),y
 838                  *      cmp     #a
 839                  *      bne     L1
 840                  *      dey
 841                  *      lda     (sp),y
 842                  *      cmp     #b
 843                  *      jne/jeq ...
 844                  */
 845                 DelCodeEntry (S, I+2);         /* tax */
 846                 ReplaceOPC (L[5], OPC_CMP);    /* cpx -> cmp */
 847                 MoveCodeEntry (S, I+4, I+2);   /* cmp */
 848                 MoveCodeEntry (S, I+5, I+3);   /* bne */
 849
 850             }
 851
 852             ++Changes;
 853         }
 854
 855         /* Next entry */
 856         ++I;
 857
 858     }
 859
 860     /* Return the number of changes made */
 861     return Changes;
 862 }
 863
 864
 865
 866 /*****************************************************************************/
 867 /*                            nega optimizations                             */
 868 /*****************************************************************************/
 869
 870
 871
 872 static unsigned OptNegA1 (CodeSeg* S)
 873 /* Check for
 874  *
 875  *      ldx     #$00
 876  *      lda     ..
 877  *      jsr     bnega
 878  *
 879  * Remove the ldx if the lda does not use it.
 880  */
 881 {
 882     unsigned Changes = 0;
 883
 884     /* Walk over the entries */
 885     unsigned I = 0;
 886     while (I < GetCodeEntryCount (S)) {
 887
 888         CodeEntry* L[2];
 889
 890         /* Get next entry */
 891         CodeEntry* E = GetCodeEntry (S, I);
 892
 893         /* Check for a ldx */
 894         if (E->OPC == OPC_LDX                   &&
 895             E->AM == AM_IMM                     &&
 896             (E->Flags & CEF_NUMARG) != 0        &&
 897             E->Num == 0                         &&
 898             GetCodeEntries (S, L, I+1, 2)       &&
 899             L[0]->OPC == OPC_LDA                &&
 900             (L[0]->Use & REG_X) == 0            &&
 901             L[1]->OPC == OPC_JSR                &&
 902             strcmp (L[1]->Arg, "bnega") == 0) {
 903
 904             /* Remove the ldx instruction */
 905             DelCodeEntry (S, I);
 906
 907             /* Remember, we had changes */
 908             ++Changes;
 909
 910         }
 911
 912         /* Next entry */
 913         ++I;
 914
 915     }
 916
 917     /* Return the number of changes made */
 918     return Changes;
 919 }
 920
 921
 922
 923 static unsigned OptNegA2 (CodeSeg* S)
 924 /* Check for
 925  *
 926  *      lda     ..
 927  *      jsr     bnega
 928  *      jeq/jne ..
 929  *
 930  * Adjust the conditional branch and remove the call to the subroutine.
 931  */
 932 {
 933     unsigned Changes = 0;
 934
 935     /* Walk over the entries */
 936     unsigned I = 0;
 937     while (I < GetCodeEntryCount (S)) {
 938
 939         CodeEntry* L[2];
 940
 941         /* Get next entry */
 942         CodeEntry* E = GetCodeEntry (S, I);
 943
 944         /* Check for the sequence */
 945         if (E->OPC == OPC_LDA                   &&
 946             GetCodeEntries (S, L, I+1, 2)       &&
 947             L[0]->OPC == OPC_JSR                &&
 948             strcmp (L[0]->Arg, "bnega") == 0    &&
 949             !CodeEntryHasLabel (L[0])           &&
 950             (L[1]->Info & OF_ZBRA) != 0) {
 951
 952             /* Invert the branch */
 953             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 954
 955             /* Delete the subroutine call */
 956             DelCodeEntry (S, I+1);
 957
 958             /* Remember, we had changes */
 959             ++Changes;
 960
 961         }
 962
 963         /* Next entry */
 964         ++I;
 965
 966     }
 967
 968     /* Return the number of changes made */
 969     return Changes;
 970 }
 971
 972
 973
 974 /*****************************************************************************/
 975 /*                            negax optimizations                            */
 976 /*****************************************************************************/
 977
 978
 979
 980 static unsigned OptNegAX1 (CodeSeg* S)
 981 /* Search for the sequence:
 982  *
 983  *      lda     (xx),y
 984  *      tax
 985  *      dey
 986  *      lda     (xx),y
 987  *      jsr     bnegax
 988  *      jne/jeq ...
 989  *
 990  * and replace it by
 991  *
 992  *      lda     (xx),y
 993  *      dey
 994  *      ora     (xx),y
 995  *      jeq/jne ...
 996  */
 997 {
 998     unsigned Changes = 0;
 999
1000     /* Walk over the entries */
1001     unsigned I = 0;
1002     while (I < GetCodeEntryCount (S)) {
1003
1004         CodeEntry* L[5];
1005
1006         /* Get next entry */
1007         CodeEntry* E = GetCodeEntry (S, I);
1008
1009         /* Check for the sequence */
1010         if (E->OPC == OPC_LDA                   &&
1011             E->AM == AM_ZP_INDY                 &&
1012             GetCodeEntries (S, L, I+1, 5)       &&
1013             L[0]->OPC == OPC_TAX                &&
1014             L[1]->OPC == OPC_DEY                &&
1015             L[2]->OPC == OPC_LDA                &&
1016             L[2]->AM == AM_ZP_INDY              &&
1017             strcmp (L[2]->Arg, E->Arg) == 0     &&
1018             !CodeEntryHasLabel (L[2])           &&
1019             L[3]->OPC == OPC_JSR                &&
1020             strcmp (L[3]->Arg, "bnegax") == 0   &&
1021             !CodeEntryHasLabel (L[3])           &&
1022             (L[4]->Info & OF_ZBRA) != 0) {
1023
1024             /* lda --> ora */
1025             ReplaceOPC (L[2], OPC_ORA);
1026
1027             /* Invert the branch */
1028             ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1029
1030             /* Delete the entries no longer needed. Beware: Deleting entries
1031              * will change the indices.
1032              */
1033             DelCodeEntry (S, I+4);              /* jsr bnegax */
1034             DelCodeEntry (S, I+1);              /* tax */
1035
1036             /* Remember, we had changes */
1037             ++Changes;
1038
1039         }
1040
1041         /* Next entry */
1042         ++I;
1043
1044     }
1045
1046     /* Return the number of changes made */
1047     return Changes;
1048 }
1049
1050
1051
1052 static unsigned OptNegAX2 (CodeSeg* S)
1053 /* Search for the sequence:
1054  *
1055  *      lda     xx
1056  *      ldx     yy
1057  *      jsr     bnegax
1058  *      jne/jeq ...
1059  *
1060  * and replace it by
1061  *
1062  *      lda     xx
1063  *      ora     xx+1
1064  *      jeq/jne ...
1065  */
1066 {
1067     unsigned Changes = 0;
1068
1069     /* Walk over the entries */
1070     unsigned I = 0;
1071     while (I < GetCodeEntryCount (S)) {
1072
1073         CodeEntry* L[3];
1074
1075         /* Get next entry */
1076         CodeEntry* E = GetCodeEntry (S, I);
1077
1078         /* Check for the sequence */
1079         if (E->OPC == OPC_LDA                   &&
1080             GetCodeEntries (S, L, I+1, 3)       &&
1081             L[0]->OPC == OPC_LDX                &&
1082             !CodeEntryHasLabel (L[0])           &&
1083             L[1]->OPC == OPC_JSR                &&
1084             strcmp (L[1]->Arg, "bnegax") == 0   &&
1085             !CodeEntryHasLabel (L[1])           &&
1086             (L[2]->Info & OF_ZBRA) != 0) {
1087
1088             /* ldx --> ora */
1089             ReplaceOPC (L[0], OPC_ORA);
1090
1091             /* Invert the branch */
1092             ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1093
1094             /* Delete the subroutine call */
1095             DelCodeEntry (S, I+2);
1096
1097             /* Remember, we had changes */
1098             ++Changes;
1099
1100         }
1101
1102         /* Next entry */
1103         ++I;
1104
1105     }
1106
1107     /* Return the number of changes made */
1108     return Changes;
1109 }
1110
1111
1112
1113 static unsigned OptNegAX3 (CodeSeg* S)
1114 /* Search for the sequence:
1115  *
1116  *      jsr     _xxx
1117  *      jsr     bnega(x)
1118  *      jeq/jne ...
1119  *
1120  * and replace it by:
1121  *
1122  *      jsr     _xxx
1123  *      <boolean test>
1124  *      jne/jeq ...
1125  */
1126 {
1127     unsigned Changes = 0;
1128
1129     /* Walk over the entries */
1130     unsigned I = 0;
1131     while (I < GetCodeEntryCount (S)) {
1132
1133         CodeEntry* L[2];
1134
1135         /* Get next entry */
1136         CodeEntry* E = GetCodeEntry (S, I);
1137
1138         /* Check for the sequence */
1139         if (E->OPC == OPC_JSR                   &&
1140             E->Arg[0] == '_'                    &&
1141             GetCodeEntries (S, L, I+1, 2)       &&
1142             L[0]->OPC == OPC_JSR                &&
1143             strncmp (L[0]->Arg,"bnega",5) == 0  &&
1144             !CodeEntryHasLabel (L[0])           &&
1145             (L[1]->Info & OF_ZBRA) != 0) {
1146
1147             /* Check if we're calling bnega or bnegax */
1148             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1149
1150             /* Delete the subroutine call */
1151             DelCodeEntry (S, I+1);
1152
1153             /* Insert apropriate test code */
1154             if (ByteSized) {
1155                 /* Test bytes */
1156                 InsertCodeEntry (S, NewCodeEntry (OPC_TAX, AM_IMP, 0, 0), I+1);
1157             } else {
1158                 /* Test words */
1159                 InsertCodeEntry (S, NewCodeEntry (OPC_STX, AM_ZP, "tmp1", 0), I+1);
1160                 InsertCodeEntry (S, NewCodeEntry (OPC_ORA, AM_ZP, "tmp1", 0), I+2);
1161             }
1162
1163             /* Invert the branch */
1164             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1165
1166             /* Remember, we had changes */
1167             ++Changes;
1168
1169         }
1170
1171         /* Next entry */
1172         ++I;
1173
1174     }
1175
1176     /* Return the number of changes made */
1177     return Changes;
1178 }
1179
1180
1181
1182 /*****************************************************************************/
1183 /*                                   Code                                    */
1184 /*****************************************************************************/
1185
1186
1187
1188 /* Table with all the optimization functions */
1189 typedef struct OptFunc OptFunc;
1190 struct OptFunc {
1191     unsigned (*Func) (CodeSeg*);/* Optimizer function */
1192     const char* Name;           /* Name of optimizer step */
1193     char        Disabled;       /* True if pass disabled */
1194 };
1195
1196
1197
1198 /* Table with optimizer steps -  are called in this order */
1199 static OptFunc OptFuncs [] = {
1200     /* Optimize subtractions */
1201     { OptSub1,              "OptSub1",                  0       },
1202     { OptSub2,              "OptSub2",                  0       },
1203     /* Optimize additions */
1204     { OptAdd1,              "OptAdd1",                  0       },
1205     /* Optimize jump cascades */
1206     { OptJumpCascades,      "OptJumpCascades",          0       },
1207     /* Remove dead jumps */
1208     { OptDeadJumps,         "OptDeadJumps",             0       },
1209     /* Change jsr/rts to jmp */
1210     { OptRTS,               "OptRTS",                   0       },
1211     /* Remove dead code */
1212     { OptDeadCode,          "OptDeadCode",              0       },
1213     /* Optimize jump targets */
1214     { OptJumpTarget,        "OptJumpTarget",            0       },
1215     /* Optimize conditional branches */
1216     { OptCondBranches,      "OptCondBranches",          0       },
1217     /* Replace jumps to RTS by RTS */
1218     { OptRTSJumps,          "OptRTSJumps",              0       },
1219     /* Remove calls to the bool transformer subroutines */
1220     { OptBoolTransforms,    "OptBoolTransforms",        0       },
1221     /* Optimize calls to nega */
1222     { OptNegA1,             "OptNegA1",                 0       },
1223     { OptNegA2,             "OptNegA2",                 0       },
1224     /* Optimize calls to negax */
1225     { OptNegAX1,            "OptNegAX1",                0       },
1226     { OptNegAX2,            "OptNegAX2",                0       },
1227     { OptNegAX3,            "OptNegAX3",                0       },
1228     /* Optimize compares */
1229     { OptCmp1,              "OptCmp1",                  0       },
1230     { OptCmp2,              "OptCmp2",                  0       },
1231     { OptCmp3,              "OptCmp3",                  0       },
1232     { OptCmp4,              "OptCmp4",                  0       },
1233     /* Remove unused loads */
1234     { OptUnusedLoads,       "OptUnusedLoads",           0       },
1235     /* Optimize branch distance */
1236     { OptBranchDist,        "OptBranchDist",            0       },
1237 };
1238
1239
1240
1241 static OptFunc* FindOptStep (const char* Name)
1242 /* Find an optimizer step by name in the table and return a pointer. Print an
1243  * error and call AbEnd if not found.
1244  */
1245 {
1246     unsigned I;
1247
1248     /* Run all optimization steps */
1249     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1250         if (strcmp (OptFuncs[I].Name, Name) == 0) {
1251             /* Found */
1252             return OptFuncs+I;
1253         }
1254     }
1255
1256     /* Not found */
1257     AbEnd ("Optimization step `%s' not found", Name);
1258     return 0;
1259 }
1260
1261
1262
1263 void DisableOpt (const char* Name)
1264 /* Disable the optimization with the given name */
1265 {
1266     OptFunc* F  = FindOptStep (Name);
1267     F->Disabled = 1;
1268 }
1269
1270
1271
1272 void EnableOpt (const char* Name)
1273 /* Enable the optimization with the given name */
1274 {
1275     OptFunc* F  = FindOptStep (Name);
1276     F->Disabled = 0;
1277 }
1278
1279
1280
1281 void RunOpt (CodeSeg* S)
1282 /* Run the optimizer */
1283 {
1284     unsigned I;
1285     unsigned Pass = 0;
1286     unsigned OptChanges;
1287
1288     /* If we shouldn't run the optimizer, bail out */
1289     if (!Optimize) {
1290         return;
1291     }
1292
1293     /* Print the name of the function we are working on */
1294     if (S->Func) {
1295         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1296     } else {
1297         Print (stdout, 1, "Running optimizer for global code segment\n");
1298     }
1299
1300     /* Repeat all steps until there are no more changes */
1301     do {
1302         /* Reset the number of changes */
1303         OptChanges = 0;
1304
1305         /* Keep the user hapy */
1306         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
1307
1308         /* Run all optimization steps */
1309         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1310
1311             /* Print the name of the following optimizer step */
1312             Print (stdout, 1, "    %s:%*s", OptFuncs[I].Name,
1313                    (int) (30-strlen(OptFuncs[I].Name)), "");
1314
1315             /* Check if the step is disabled */
1316             if (OptFuncs[I].Disabled) {
1317                 Print (stdout, 1, "Disabled\n");
1318             } else {
1319                 unsigned Changes = OptFuncs[I].Func (S);
1320                 OptChanges += Changes;
1321                 Print (stdout, 1, "%u Changes\n", Changes);
1322             }
1323         }
1324
1325     } while (OptChanges > 0);
1326 }
1327
1328
1329