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 cmp_t 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 void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
 153 /* Helper function for the replacement of routines that return a boolean
 154  * followed by a conditional jump. Instead of the boolean value, the condition
 155  * codes are evaluated directly.
 156  * I is the index of the conditional branch, the sequence is already checked
 157  * to be correct.
 158  */
 159 {
 160     CodeEntry* N;
 161     CodeLabel* L;
 162
 163     /* Get the entry */
 164     CodeEntry* E = CS_GetEntry (S, I);
 165
 166     /* Replace the conditional branch */
 167     switch (Cond) {
 168
 169         case CMP_EQ:
 170             CE_ReplaceOPC (E, OP65_JEQ);
 171             break;
 172
 173         case CMP_NE:
 174             CE_ReplaceOPC (E, OP65_JNE);
 175             break;
 176
 177         case CMP_GT:
 178             /* Replace by
 179              *     beq @L
 180              *     jpl Target
 181              * @L: ...
 182              */
 183             if ((N = CS_GetNextEntry (S, I)) == 0) {
 184                 /* No such entry */
 185                 Internal ("Invalid program flow");
 186             }
 187             L = CS_GenLabel (S, N);
 188             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 189             CS_InsertEntry (S, N, I);
 190             CE_ReplaceOPC (E, OP65_JPL);
 191             break;
 192
 193         case CMP_GE:
 194             CE_ReplaceOPC (E, OP65_JPL);
 195             break;
 196
 197         case CMP_LT:
 198             CE_ReplaceOPC (E, OP65_JMI);
 199             break;
 200
 201         case CMP_LE:
 202             /* Replace by
 203              *     jmi Target
 204              *     jeq Target
 205              */
 206             CE_ReplaceOPC (E, OP65_JMI);
 207             L = E->JumpTo;
 208             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 209             CS_InsertEntry (S, N, I+1);
 210             break;
 211
 212         case CMP_UGT:
 213             /* Replace by
 214              *     beq @L
 215              *     jcs Target
 216              * @L: ...
 217              */
 218             if ((N = CS_GetNextEntry (S, I)) == 0) {
 219                 /* No such entry */
 220                 Internal ("Invalid program flow");
 221             }
 222             L = CS_GenLabel (S, N);
 223             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 224             CS_InsertEntry (S, N, I);
 225             CE_ReplaceOPC (E, OP65_JCS);
 226             break;
 227
 228         case CMP_UGE:
 229             CE_ReplaceOPC (E, OP65_JCS);
 230             break;
 231
 232         case CMP_ULT:
 233             CE_ReplaceOPC (E, OP65_JCC);
 234             break;
 235
 236         case CMP_ULE:
 237             /* Replace by
 238              *     jcc Target
 239              *     jeq Target
 240              */
 241             CE_ReplaceOPC (E, OP65_JCC);
 242             L = E->JumpTo;
 243             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 244             CS_InsertEntry (S, N, I+1);
 245             break;
 246
 247         default:
 248             Internal ("Unknown jump condition: %d", Cond);
 249
 250     }
 251
 252 }
 253
 254
 255
 256 static int IsCmpToZero (const CodeEntry* E)
 257 /* Check if the given instrcuction is a compare to zero instruction */
 258 {
 259     return (E->OPC == OP65_CMP            &&
 260             E->AM  == AM65_IMM            &&
 261             (E->Flags & CEF_NUMARG) != 0  &&
 262             E->Num == 0);
 263 }
 264
 265
 266
 267 static int IsSpLoad (const CodeEntry* E)
 268 /* Return true if this is the load of A from the stack */
 269 {
 270     return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
 271 }
 272
 273
 274
 275 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
 276                           CodeEntry** L, unsigned Count)
 277 /* Check if a 16 bit load of a local variable follows:
 278  *
 279  *      ldy     #$xx
 280  *      lda     (sp),y
 281  *      tax
 282  *      dey
 283  *      lda     (sp),y
 284  *
 285  * If so, read Count entries following the first ldy into L and return true
 286  * if this is possible. Otherwise return false.
 287  */
 288 {
 289     /* Be sure we read enough entries for the check */
 290     CHECK (Count >= 5);
 291
 292     /* Read the first entry */
 293     L[0] = CS_GetEntry (S, Index);
 294
 295     /* Check for the sequence */
 296     return (L[0]->OPC == OP65_LDY                        &&
 297             L[0]->AM == AM65_IMM                         &&
 298             (L[0]->Flags & CEF_NUMARG) != 0              &&
 299             CS_GetEntries (S, L+1, Index+1, Count-1)     &&
 300             IsSpLoad (L[1])                              &&
 301             !CE_HasLabel (L[1])                          &&
 302             L[2]->OPC == OP65_TAX                        &&
 303             !CE_HasLabel (L[2])                          &&
 304             L[3]->OPC == OP65_DEY                        &&
 305             !CE_HasLabel (L[3])                          &&
 306             IsSpLoad (L[4])                              &&
 307             !CE_HasLabel (L[4]));
 308 }
 309
 310
 311
 312 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
 313 /* Check if the instructions at L are an immidiate compare of a/x:
 314  *
 315  *
 316  */
 317 {
 318     return (L[0]->OPC == OP65_CPX                              &&
 319             L[0]->AM == AM65_IMM                               &&
 320             (L[0]->Flags & CEF_NUMARG) != 0                    &&
 321             !CE_HasLabel (L[0])                                &&
 322             (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE)   &&
 323             L[1]->JumpTo != 0                                  &&
 324             !CE_HasLabel (L[1])                                &&
 325             L[2]->OPC == OP65_CMP                              &&
 326             L[2]->AM == AM65_IMM                               &&
 327             (L[2]->Flags & CEF_NUMARG) != 0                    &&
 328             (L[3]->Info & OF_ZBRA) != 0                        &&
 329             L[3]->JumpTo != 0                                  &&
 330             (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
 331 }
 332
 333
 334
 335 /*****************************************************************************/
 336 /*             Remove calls to the bool transformer subroutines              */
 337 /*****************************************************************************/
 338
 339
 340
 341 static unsigned OptBoolTransforms (CodeSeg* S)
 342 /* Try to remove the call to boolean transformer routines where the call is
 343  * not really needed.
 344  */
 345 {
 346     unsigned Changes = 0;
 347
 348     /* Walk over the entries */
 349     unsigned I = 0;
 350     while (I < CS_GetEntryCount (S)) {
 351
 352         CodeEntry* N;
 353         cmp_t Cond;
 354
 355         /* Get next entry */
 356         CodeEntry* E = CS_GetEntry (S, I);
 357
 358         /* Check for a boolean transformer */
 359         if (E->OPC == OP65_JSR                           &&
 360             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 361             (N = CS_GetNextEntry (S, I)) != 0        &&
 362             (N->Info & OF_ZBRA) != 0) {
 363
 364             /* Make the boolean transformer unnecessary by changing the
 365              * the conditional jump to evaluate the condition flags that
 366              * are set after the compare directly. Note: jeq jumps if
 367              * the condition is not met, jne jumps if the condition is met.
 368              * Invert the code if we jump on condition not met.
 369              */
 370             if (GetBranchCond (N->OPC) == BC_EQ) {
 371                 /* Jumps if condition false, invert condition */
 372                 Cond = CmpInvertTab [Cond];
 373             }
 374
 375             /* Check if we can replace the code by something better */
 376             ReplaceCmp (S, I+1, Cond);
 377
 378             /* Remove the call to the bool transformer */
 379             CS_DelEntry (S, I);
 380
 381             /* Remember, we had changes */
 382             ++Changes;
 383
 384         }
 385
 386         /* Next entry */
 387         ++I;
 388
 389     }
 390
 391     /* Return the number of changes made */
 392     return Changes;
 393 }
 394
 395
 396
 397 /*****************************************************************************/
 398 /*                           Optimize subtractions                           */
 399 /*****************************************************************************/
 400
 401
 402
 403 static unsigned OptSub1 (CodeSeg* S)
 404 /* Search for the sequence
 405  *
 406  *      sbc     ...
 407  *      bcs     L
 408  *      dex
 409  * L:
 410  *
 411  * and remove the handling of the high byte if X is not used later.
 412  */
 413 {
 414     unsigned Changes = 0;
 415
 416     /* Walk over the entries */
 417     unsigned I = 0;
 418     while (I < CS_GetEntryCount (S)) {
 419
 420         CodeEntry* L[3];
 421
 422         /* Get next entry */
 423         CodeEntry* E = CS_GetEntry (S, I);
 424
 425         /* Check for the sequence */
 426         if (E->OPC == OP65_SBC                               &&
 427             CS_GetEntries (S, L, I+1, 3)                     &&
 428             (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) &&
 429             L[0]->JumpTo != 0                                &&
 430             !CE_HasLabel (L[0])                              &&
 431             L[1]->OPC == OP65_DEX                            &&
 432             !CE_HasLabel (L[1])                              &&
 433             L[0]->JumpTo->Owner == L[2]                      &&
 434             !RegXUsed (S, I+3)) {
 435
 436             /* Remove the bcs/dex */
 437             CS_DelEntries (S, I+1, 2);
 438
 439             /* Remember, we had changes */
 440             ++Changes;
 441
 442         }
 443
 444         /* Next entry */
 445         ++I;
 446
 447     }
 448
 449     /* Return the number of changes made */
 450     return Changes;
 451 }
 452
 453
 454
 455 static unsigned OptSub2 (CodeSeg* S)
 456 /* Search for the sequence
 457  *
 458  *      lda     xx
 459  *      sec
 460  *      sta     tmp1
 461  *      lda     yy
 462  *      sbc     tmp1
 463  *      sta     yy
 464  *
 465  * and replace it by
 466  *
 467  *      sec
 468  *      lda     yy
 469  *      sbc     xx
 470  *      sta     yy
 471  */
 472 {
 473     unsigned Changes = 0;
 474
 475     /* Walk over the entries */
 476     unsigned I = 0;
 477     while (I < CS_GetEntryCount (S)) {
 478
 479         CodeEntry* L[5];
 480
 481         /* Get next entry */
 482         CodeEntry* E = CS_GetEntry (S, I);
 483
 484         /* Check for the sequence */
 485         if (E->OPC == OP65_LDA                             &&
 486             CS_GetEntries (S, L, I+1, 5)                   &&
 487             L[0]->OPC == OP65_SEC                          &&
 488             !CE_HasLabel (L[0])                            &&
 489             L[1]->OPC == OP65_STA                          &&
 490             strcmp (L[1]->Arg, "tmp1") == 0                &&
 491             !CE_HasLabel (L[1])                            &&
 492             L[2]->OPC == OP65_LDA                          &&
 493             !CE_HasLabel (L[2])                            &&
 494             L[3]->OPC == OP65_SBC                          &&
 495             strcmp (L[3]->Arg, "tmp1") == 0                &&
 496             !CE_HasLabel (L[3])                            &&
 497             L[4]->OPC == OP65_STA                          &&
 498             strcmp (L[4]->Arg, L[2]->Arg) == 0             &&
 499             !CE_HasLabel (L[4])) {
 500
 501             /* Remove the store to tmp1 */
 502             CS_DelEntry (S, I+2);
 503
 504             /* Remove the subtraction */
 505             CS_DelEntry (S, I+3);
 506
 507             /* Move the lda to the position of the subtraction and change the
 508              * op to SBC.
 509              */
 510             CS_MoveEntry (S, I, I+3);
 511             CE_ReplaceOPC (E, OP65_SBC);
 512
 513             /* If the sequence head had a label, move this label back to the
 514              * head.
 515              */
 516             if (CE_HasLabel (E)) {
 517                 CS_MoveLabels (S, E, L[0]);
 518             }
 519
 520             /* Remember, we had changes */
 521             ++Changes;
 522
 523         }
 524
 525         /* Next entry */
 526         ++I;
 527
 528     }
 529
 530     /* Return the number of changes made */
 531     return Changes;
 532 }
 533
 534
 535
 536 /*****************************************************************************/
 537 /*                            Optimize additions                             */
 538 /*****************************************************************************/
 539
 540
 541
 542 static unsigned OptAdd1 (CodeSeg* S)
 543 /* Search for the sequence
 544  *
 545  *      adc     ...
 546  *      bcc     L
 547  *      inx
 548  * L:
 549  *
 550  * and remove the handling of the high byte if X is not used later.
 551  */
 552 {
 553     unsigned Changes = 0;
 554
 555     /* Walk over the entries */
 556     unsigned I = 0;
 557     while (I < CS_GetEntryCount (S)) {
 558
 559         CodeEntry* L[3];
 560
 561         /* Get next entry */
 562         CodeEntry* E = CS_GetEntry (S, I);
 563
 564         /* Check for the sequence */
 565         if (E->OPC == OP65_ADC                               &&
 566             CS_GetEntries (S, L, I+1, 3)                     &&
 567             (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
 568             L[0]->JumpTo != 0                                &&
 569             !CE_HasLabel (L[0])                              &&
 570             L[1]->OPC == OP65_INX                            &&
 571             !CE_HasLabel (L[1])                              &&
 572             L[0]->JumpTo->Owner == L[2]                      &&
 573             !RegXUsed (S, I+3)) {
 574
 575             /* Remove the bcs/dex */
 576             CS_DelEntries (S, I+1, 2);
 577
 578             /* Remember, we had changes */
 579             ++Changes;
 580
 581         }
 582
 583         /* Next entry */
 584         ++I;
 585
 586     }
 587
 588     /* Return the number of changes made */
 589     return Changes;
 590 }
 591
 592
 593
 594 /*****************************************************************************/
 595 /*                        Optimizations for compares                         */
 596 /*****************************************************************************/
 597
 598
 599
 600 static unsigned OptCmp1 (CodeSeg* S)
 601 /* Search for the sequence
 602  *
 603  *      stx     xx
 604  *      stx     tmp1
 605  *      ora     tmp1
 606  *
 607  * and replace it by
 608  *
 609  *      stx     xx
 610  *      ora     xx
 611  */
 612 {
 613     unsigned Changes = 0;
 614
 615     /* Walk over the entries */
 616     unsigned I = 0;
 617     while (I < CS_GetEntryCount (S)) {
 618
 619         CodeEntry* L[2];
 620
 621         /* Get next entry */
 622         CodeEntry* E = CS_GetEntry (S, I);
 623
 624         /* Check for the sequence */
 625         if (E->OPC == OP65_STX                  &&
 626             CS_GetEntries (S, L, I+1, 2)        &&
 627             L[0]->OPC == OP65_STX               &&
 628             strcmp (L[0]->Arg, "tmp1") == 0     &&
 629             !CE_HasLabel (L[0])                 &&
 630             L[1]->OPC == OP65_ORA               &&
 631             strcmp (L[1]->Arg, "tmp1") == 0     &&
 632             !CE_HasLabel (L[1])) {
 633
 634             /* Remove the remaining instructions */
 635             CS_DelEntries (S, I+1, 2);
 636
 637             /* Insert the ora instead */
 638             CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
 639
 640             /* Remember, we had changes */
 641             ++Changes;
 642
 643         }
 644
 645         /* Next entry */
 646         ++I;
 647
 648     }
 649
 650     /* Return the number of changes made */
 651     return Changes;
 652 }
 653
 654
 655
 656 static unsigned OptCmp2 (CodeSeg* S)
 657 /* Search for
 658  *
 659  *      lda/and/ora/eor ...
 660  *      cmp #$00
 661  *      jeq/jne
 662  *
 663  * and remove the cmp.
 664  */
 665 {
 666     unsigned Changes = 0;
 667
 668     /* Walk over the entries */
 669     unsigned I = 0;
 670     while (I < CS_GetEntryCount (S)) {
 671
 672         CodeEntry* L[2];
 673
 674         /* Get next entry */
 675         CodeEntry* E = CS_GetEntry (S, I);
 676
 677         /* Check for the sequence */
 678         if ((E->OPC == OP65_ADC ||
 679              E->OPC == OP65_AND ||
 680              E->OPC == OP65_DEA ||
 681              E->OPC == OP65_EOR ||
 682              E->OPC == OP65_INA ||
 683              E->OPC == OP65_LDA ||
 684              E->OPC == OP65_ORA ||
 685              E->OPC == OP65_PLA ||
 686              E->OPC == OP65_SBC ||
 687              E->OPC == OP65_TXA ||
 688              E->OPC == OP65_TYA)                  &&
 689             CS_GetEntries (S, L, I+1, 2)          &&
 690             IsCmpToZero (L[0])                    &&
 691             !CE_HasLabel (L[0])                   &&
 692             (L[1]->Info & OF_FBRA) != 0           &&
 693             !CE_HasLabel (L[1])) {
 694
 695             /* Remove the compare */
 696             CS_DelEntry (S, I+1);
 697
 698             /* Remember, we had changes */
 699             ++Changes;
 700
 701         }
 702
 703         /* Next entry */
 704         ++I;
 705
 706     }
 707
 708     /* Return the number of changes made */
 709     return Changes;
 710 }
 711
 712
 713
 714 static unsigned OptCmp3 (CodeSeg* S)
 715 /* Search for
 716  *
 717  *      lda     x
 718  *      ldx     y
 719  *      cpx     #a
 720  *      bne     L1
 721  *      cmp     #b
 722  *      jne/jeq L2
 723  *
 724  * If a is zero, we may remove the compare. If a and b are both zero, we may
 725  * replace it by the sequence
 726  *
 727  *      lda     x
 728  *      ora     x+1
 729  *      jne/jeq ...
 730  *
 731  * L1 may be either the label at the branch instruction, or the target label
 732  * of this instruction.
 733  */
 734 {
 735     unsigned Changes = 0;
 736
 737     /* Walk over the entries */
 738     unsigned I = 0;
 739     while (I < CS_GetEntryCount (S)) {
 740
 741         CodeEntry* L[5];
 742
 743         /* Get next entry */
 744         CodeEntry* E = CS_GetEntry (S, I);
 745
 746         /* Check for the sequence */
 747         if (E->OPC == OP65_LDA               &&
 748             CS_GetEntries (S, L, I+1, 5) &&
 749             L[0]->OPC == OP65_LDX            &&
 750             !CE_HasLabel (L[0])              &&
 751             IsImmCmp16 (S, L+1)) {
 752
 753             if (L[1]->Num == 0 && L[3]->Num == 0) {
 754                 /* The value is zero, we may use the simple code version. */
 755                 CE_ReplaceOPC (L[0], OP65_ORA);
 756                 CS_DelEntries (S, I+2, 3);
 757             } else {
 758                 /* Move the lda instruction after the first branch. This will
 759                  * improve speed, since the load is delayed after the first
 760                  * test.
 761                  */
 762                 CS_MoveEntry (S, I, I+4);
 763
 764                 /* We will replace the ldx/cpx by lda/cmp */
 765                 CE_ReplaceOPC (L[0], OP65_LDA);
 766                 CE_ReplaceOPC (L[1], OP65_CMP);
 767
 768                 /* Beware: If the first LDA instruction had a label, we have
 769                  * to move this label to the top of the sequence again.
 770                  */
 771                 if (CE_HasLabel (E)) {
 772                     CS_MoveLabels (S, E, L[0]);
 773                 }
 774
 775             }
 776
 777             ++Changes;
 778         }
 779
 780         /* Next entry */
 781         ++I;
 782
 783     }
 784
 785     /* Return the number of changes made */
 786     return Changes;
 787 }
 788
 789
 790
 791 static unsigned OptCmp4 (CodeSeg* S)
 792 /* Optimize compares of local variables:
 793  *
 794  *      ldy     #o
 795  *      lda     (sp),y
 796  *      tax
 797  *      dey
 798  *      lda     (sp),y
 799  *      cpx     #a
 800  *      bne     L1
 801  *      cmp     #b
 802  *      jne/jeq L2
 803  */
 804 {
 805     unsigned Changes = 0;
 806
 807     /* Walk over the entries */
 808     unsigned I = 0;
 809     while (I < CS_GetEntryCount (S)) {
 810
 811         CodeEntry* L[9];
 812
 813         /* Check for the sequence */
 814         if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
 815
 816             if (L[5]->Num == 0 && L[7]->Num == 0) {
 817
 818                 /* The value is zero, we may use the simple code version:
 819                  *      ldy     #o
 820                  *      lda     (sp),y
 821                  *      dey
 822                  *      ora     (sp),y
 823                  *      jne/jeq ...
 824                  */
 825                 CE_ReplaceOPC (L[4], OP65_ORA);
 826                 CS_DelEntries (S, I+5, 3);   /* cpx/bne/cmp */
 827                 CS_DelEntry (S, I+2);        /* tax */
 828
 829             } else {
 830
 831                 /* Change the code to just use the A register. Move the load
 832                  * of the low byte after the first branch if possible:
 833                  *
 834                  *      ldy     #o
 835                  *      lda     (sp),y
 836                  *      cmp     #a
 837                  *      bne     L1
 838                  *      dey
 839                  *      lda     (sp),y
 840                  *      cmp     #b
 841                  *      jne/jeq ...
 842                  */
 843                 CS_DelEntry (S, I+2);             /* tax */
 844                 CE_ReplaceOPC (L[5], OP65_CMP);   /* cpx -> cmp */
 845                 CS_MoveEntry (S, I+4, I+2);       /* cmp */
 846                 CS_MoveEntry (S, I+5, I+3);       /* bne */
 847
 848             }
 849
 850             ++Changes;
 851         }
 852
 853         /* Next entry */
 854         ++I;
 855
 856     }
 857
 858     /* Return the number of changes made */
 859     return Changes;
 860 }
 861
 862
 863
 864 static unsigned OptCmp5 (CodeSeg* S)
 865 /* Search for calls to compare subroutines followed by a conditional branch
 866  * and replace them by cheaper versions, since the branch means that the
 867  * boolean value returned by these routines is not needed (we may also check
 868  * that explicitly, but for the current code generator it is always true).
 869  */
 870 {
 871     unsigned Changes = 0;
 872
 873     /* Walk over the entries */
 874     unsigned I = 0;
 875     while (I < CS_GetEntryCount (S)) {
 876
 877         CodeEntry* N;
 878         cmp_t Cond;
 879
 880         /* Get next entry */
 881         CodeEntry* E = CS_GetEntry (S, I);
 882
 883         /* Check for the sequence */
 884         if (E->OPC == OP65_JSR                          &&
 885             (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
 886             (N = CS_GetNextEntry (S, I)) != 0           &&
 887             (N->Info & OF_ZBRA) != 0                    &&
 888             !CE_HasLabel (N)) {
 889
 890             /* The tos... functions will return a boolean value in a/x and
 891              * the Z flag says if this value is zero or not. We will call
 892              * a cheaper subroutine instead, one that does not return a
 893              * boolean value but only valid flags. Note: jeq jumps if
 894              * the condition is not met, jne jumps if the condition is met.
 895              * Invert the code if we jump on condition not met.
 896              */
 897             if (GetBranchCond (N->OPC) == BC_EQ) {
 898                 /* Jumps if condition false, invert condition */
 899                 Cond = CmpInvertTab [Cond];
 900             }
 901
 902             /* Replace the subroutine call. */
 903             E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
 904             CS_InsertEntry (S, E, I+1);
 905             CS_DelEntry (S, I);
 906
 907             /* Replace the conditional branch */
 908             ReplaceCmp (S, I+1, Cond);
 909
 910             /* Remember, we had changes */
 911             ++Changes;
 912
 913         }
 914
 915         /* Next entry */
 916         ++I;
 917
 918     }
 919
 920     /* Return the number of changes made */
 921     return Changes;
 922 }
 923
 924
 925
 926 static unsigned OptCmp6 (CodeSeg* S)
 927 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
 928  * used later.
 929  */
 930 {
 931     unsigned Changes = 0;
 932
 933     /* Walk over the entries */
 934     unsigned I = 0;
 935     while (I < CS_GetEntryCount (S)) {
 936
 937         CodeEntry* L[2];
 938
 939         /* Get next entry */
 940         CodeEntry* E = CS_GetEntry (S, I);
 941
 942         /* Check for the sequence */
 943         if ((E->OPC == OP65_LDX || E->OPC == OP65_TAX)  &&
 944             CS_GetEntries (S, L, I+1, 2)                &&
 945             L[0]->OPC == OP65_TXA                       &&
 946             !CE_HasLabel (L[0])                         &&
 947             (L[1]->Info & OF_FBRA) != 0                 &&
 948             !CE_HasLabel (L[1])                         &&
 949             !RegAUsed (S, I+3)) {
 950
 951             /* Remove the txa */
 952             CS_DelEntry (S, I+1);
 953
 954             /* Remember, we had changes */
 955             ++Changes;
 956
 957         }
 958
 959         /* Next entry */
 960         ++I;
 961
 962     }
 963
 964     /* Return the number of changes made */
 965     return Changes;
 966 }
 967
 968
 969
 970 /*****************************************************************************/
 971 /*                              Optimize tests                               */
 972 /*****************************************************************************/
 973
 974
 975
 976 static unsigned OptTest1 (CodeSeg* S)
 977 /* On a sequence
 978  *
 979  *     stx     xxx
 980  *     ora     xxx
 981  *     beq/bne ...
 982  *
 983  * if X is zero, the sequence may be changed
 984  *
 985  *     cmp     #$00
 986  *     beq/bne ...
 987  *
 988  * which may be optimized further by another step.
 989  */
 990 {
 991     unsigned Changes = 0;
 992     unsigned I;
 993
 994     /* Generate register info for this step */
 995     CS_GenRegInfo (S);
 996
 997     /* Walk over the entries */
 998     I = 0;
 999     while (I < CS_GetEntryCount (S)) {
1000
1001         CodeEntry* L[3];
1002
1003         /* Get next entry */
1004         L[0] = CS_GetEntry (S, I);
1005
1006         /* Check if it's the sequence we're searching for */
1007         if (L[0]->OPC == OP65_STX              &&
1008             L[0]->RI->In.RegX == 0             &&
1009             CS_GetEntries (S, L+1, I+1, 2)     &&
1010             !CE_HasLabel (L[1])                &&
1011             L[1]->OPC == OP65_ORA              &&
1012             strcmp (L[0]->Arg, L[1]->Arg) == 0 &&
1013             !CE_HasLabel (L[2])                &&
1014             (L[2]->Info & OF_ZBRA) != 0) {
1015
1016             /* Insert the compare */
1017             CodeEntry* N = NewCodeEntry (OP65_CMP, AM65_IMM, "$00", 0, L[0]->LI);
1018             CS_InsertEntry (S, N, I+2);
1019
1020             /* Remove the two other insns */
1021             CS_DelEntry (S, I+1);
1022             CS_DelEntry (S, I);
1023
1024             /* We had changes */
1025             ++Changes;
1026         }
1027
1028         /* Next entry */
1029         ++I;
1030
1031     }
1032
1033     /* Free register info */
1034     CS_FreeRegInfo (S);
1035
1036     /* Return the number of changes made */
1037     return Changes;
1038 }
1039
1040
1041
1042
1043
1044
1045
1046 /*****************************************************************************/
1047 /*                            nega optimizations                             */
1048 /*****************************************************************************/
1049
1050
1051
1052 static unsigned OptNegA1 (CodeSeg* S)
1053 /* Check for
1054  *
1055  *      ldx     #$00
1056  *      lda     ..
1057  *      jsr     bnega
1058  *
1059  * Remove the ldx if the lda does not use it.
1060  */
1061 {
1062     unsigned Changes = 0;
1063
1064     /* Walk over the entries */
1065     unsigned I = 0;
1066     while (I < CS_GetEntryCount (S)) {
1067
1068         CodeEntry* L[2];
1069
1070         /* Get next entry */
1071         CodeEntry* E = CS_GetEntry (S, I);
1072
1073         /* Check for a ldx */
1074         if (E->OPC == OP65_LDX                  &&
1075             E->AM == AM65_IMM                   &&
1076             (E->Flags & CEF_NUMARG) != 0        &&
1077             E->Num == 0                         &&
1078             CS_GetEntries (S, L, I+1, 2)        &&
1079             L[0]->OPC == OP65_LDA               &&
1080             (L[0]->Use & REG_X) == 0            &&
1081             !CE_HasLabel (L[0])                 &&
1082             L[1]->OPC == OP65_JSR               &&
1083             strcmp (L[1]->Arg, "bnega") == 0    &&
1084             !CE_HasLabel (L[1])) {
1085
1086             /* Remove the ldx instruction */
1087             CS_DelEntry (S, I);
1088
1089             /* Remember, we had changes */
1090             ++Changes;
1091
1092         }
1093
1094         /* Next entry */
1095         ++I;
1096
1097     }
1098
1099     /* Return the number of changes made */
1100     return Changes;
1101 }
1102
1103
1104
1105 static unsigned OptNegA2 (CodeSeg* S)
1106 /* Check for
1107  *
1108  *      lda     ..
1109  *      jsr     bnega
1110  *      jeq/jne ..
1111  *
1112  * Adjust the conditional branch and remove the call to the subroutine.
1113  */
1114 {
1115     unsigned Changes = 0;
1116
1117     /* Walk over the entries */
1118     unsigned I = 0;
1119     while (I < CS_GetEntryCount (S)) {
1120
1121         CodeEntry* L[2];
1122
1123         /* Get next entry */
1124         CodeEntry* E = CS_GetEntry (S, I);
1125
1126         /* Check for the sequence */
1127         if ((E->OPC == OP65_ADC ||
1128              E->OPC == OP65_AND ||
1129              E->OPC == OP65_DEA ||
1130              E->OPC == OP65_EOR ||
1131              E->OPC == OP65_INA ||
1132              E->OPC == OP65_LDA ||
1133              E->OPC == OP65_ORA ||
1134              E->OPC == OP65_PLA ||
1135              E->OPC == OP65_SBC ||
1136              E->OPC == OP65_TXA ||
1137              E->OPC == OP65_TYA)                &&
1138             CS_GetEntries (S, L, I+1, 2)        &&
1139             L[0]->OPC == OP65_JSR               &&
1140             strcmp (L[0]->Arg, "bnega") == 0    &&
1141             !CE_HasLabel (L[0])                 &&
1142             (L[1]->Info & OF_ZBRA) != 0         &&
1143             !CE_HasLabel (L[1])) {
1144
1145             /* Invert the branch */
1146             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1147
1148             /* Delete the subroutine call */
1149             CS_DelEntry (S, I+1);
1150
1151             /* Remember, we had changes */
1152             ++Changes;
1153
1154         }
1155
1156         /* Next entry */
1157         ++I;
1158
1159     }
1160
1161     /* Return the number of changes made */
1162     return Changes;
1163 }
1164
1165
1166
1167 /*****************************************************************************/
1168 /*                            negax optimizations                            */
1169 /*****************************************************************************/
1170
1171
1172
1173 static unsigned OptNegAX1 (CodeSeg* S)
1174 /* On a call to bnegax, if X is zero, the result depends only on the value in
1175  * A, so change the call to a call to bnega. This will get further optimized
1176  * later if possible.
1177  */
1178 {
1179     unsigned Changes = 0;
1180     unsigned I;
1181
1182     /* Generate register info for this step */
1183     CS_GenRegInfo (S);
1184
1185     /* Walk over the entries */
1186     I = 0;
1187     while (I < CS_GetEntryCount (S)) {
1188
1189         /* Get next entry */
1190         CodeEntry* E = CS_GetEntry (S, I);
1191
1192         /* Check if this is a call to bnegax, and if X is known and zero */
1193         if (E->OPC == OP65_JSR              &&
1194             E->RI->In.RegX == 0             &&
1195             strcmp (E->Arg, "bnegax") == 0) {
1196
1197             /* We're cheating somewhat here ... */
1198             E->Arg[5] = '\0';
1199             E->Use &= ~REG_X;
1200
1201             /* We had changes */
1202             ++Changes;
1203         }
1204
1205         /* Next entry */
1206         ++I;
1207
1208     }
1209
1210     /* Free register info */
1211     CS_FreeRegInfo (S);
1212
1213     /* Return the number of changes made */
1214     return Changes;
1215 }
1216
1217
1218
1219 static unsigned OptNegAX2 (CodeSeg* S)
1220 /* Search for the sequence:
1221  *
1222  *      lda     (xx),y
1223  *      tax
1224  *      dey
1225  *      lda     (xx),y
1226  *      jsr     bnegax
1227  *      jne/jeq ...
1228  *
1229  * and replace it by
1230  *
1231  *      lda     (xx),y
1232  *      dey
1233  *      ora     (xx),y
1234  *      jeq/jne ...
1235  */
1236 {
1237     unsigned Changes = 0;
1238
1239     /* Walk over the entries */
1240     unsigned I = 0;
1241     while (I < CS_GetEntryCount (S)) {
1242
1243         CodeEntry* L[5];
1244
1245         /* Get next entry */
1246         CodeEntry* E = CS_GetEntry (S, I);
1247
1248         /* Check for the sequence */
1249         if (E->OPC == OP65_LDA                  &&
1250             E->AM == AM65_ZP_INDY               &&
1251             CS_GetEntries (S, L, I+1, 5)        &&
1252             L[0]->OPC == OP65_TAX               &&
1253             L[1]->OPC == OP65_DEY               &&
1254             L[2]->OPC == OP65_LDA               &&
1255             L[2]->AM == AM65_ZP_INDY            &&
1256             strcmp (L[2]->Arg, E->Arg) == 0     &&
1257             !CE_HasLabel (L[2])                 &&
1258             L[3]->OPC == OP65_JSR               &&
1259             strcmp (L[3]->Arg, "bnegax") == 0   &&
1260             !CE_HasLabel (L[3])                 &&
1261             (L[4]->Info & OF_ZBRA) != 0         &&
1262             !CE_HasLabel (L[4])) {
1263
1264             /* lda --> ora */
1265             CE_ReplaceOPC (L[2], OP65_ORA);
1266
1267             /* Invert the branch */
1268             CE_ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1269
1270             /* Delete the entries no longer needed. Beware: Deleting entries
1271              * will change the indices.
1272              */
1273             CS_DelEntry (S, I+4);               /* jsr bnegax */
1274             CS_DelEntry (S, I+1);               /* tax */
1275
1276             /* Remember, we had changes */
1277             ++Changes;
1278
1279         }
1280
1281         /* Next entry */
1282         ++I;
1283
1284     }
1285
1286     /* Return the number of changes made */
1287     return Changes;
1288 }
1289
1290
1291
1292 static unsigned OptNegAX3 (CodeSeg* S)
1293 /* Search for the sequence:
1294  *
1295  *      lda     xx
1296  *      ldx     yy
1297  *      jsr     bnegax
1298  *      jne/jeq ...
1299  *
1300  * and replace it by
1301  *
1302  *      lda     xx
1303  *      ora     xx+1
1304  *      jeq/jne ...
1305  */
1306 {
1307     unsigned Changes = 0;
1308
1309     /* Walk over the entries */
1310     unsigned I = 0;
1311     while (I < CS_GetEntryCount (S)) {
1312
1313         CodeEntry* L[3];
1314
1315         /* Get next entry */
1316         CodeEntry* E = CS_GetEntry (S, I);
1317
1318         /* Check for the sequence */
1319         if (E->OPC == OP65_LDA                  &&
1320             CS_GetEntries (S, L, I+1, 3)        &&
1321             L[0]->OPC == OP65_LDX               &&
1322             !CE_HasLabel (L[0])                 &&
1323             L[1]->OPC == OP65_JSR               &&
1324             strcmp (L[1]->Arg, "bnegax") == 0   &&
1325             !CE_HasLabel (L[1])                 &&
1326             (L[2]->Info & OF_ZBRA) != 0         &&
1327             !CE_HasLabel (L[2])) {
1328
1329             /* ldx --> ora */
1330             CE_ReplaceOPC (L[0], OP65_ORA);
1331
1332             /* Invert the branch */
1333             CE_ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1334
1335             /* Delete the subroutine call */
1336             CS_DelEntry (S, I+2);
1337
1338             /* Remember, we had changes */
1339             ++Changes;
1340
1341         }
1342
1343         /* Next entry */
1344         ++I;
1345
1346     }
1347
1348     /* Return the number of changes made */
1349     return Changes;
1350 }
1351
1352
1353
1354 static unsigned OptNegAX4 (CodeSeg* S)
1355 /* Search for the sequence:
1356  *
1357  *      jsr     xxx
1358  *      jsr     bnega(x)
1359  *      jeq/jne ...
1360  *
1361  * and replace it by:
1362  *
1363  *      jsr     xxx
1364  *      <boolean test>
1365  *      jne/jeq ...
1366  */
1367 {
1368     unsigned Changes = 0;
1369
1370     /* Walk over the entries */
1371     unsigned I = 0;
1372     while (I < CS_GetEntryCount (S)) {
1373
1374         CodeEntry* L[2];
1375
1376         /* Get next entry */
1377         CodeEntry* E = CS_GetEntry (S, I);
1378
1379         /* Check for the sequence */
1380         if (E->OPC == OP65_JSR                  &&
1381             CS_GetEntries (S, L, I+1, 2)        &&
1382             L[0]->OPC == OP65_JSR               &&
1383             strncmp (L[0]->Arg,"bnega",5) == 0  &&
1384             !CE_HasLabel (L[0])                 &&
1385             (L[1]->Info & OF_ZBRA) != 0         &&
1386             !CE_HasLabel (L[1])) {
1387
1388             CodeEntry* X;
1389
1390             /* Check if we're calling bnega or bnegax */
1391             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1392
1393             /* Insert apropriate test code */
1394             if (ByteSized) {
1395                 /* Test bytes */
1396                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
1397                 CS_InsertEntry (S, X, I+2);
1398             } else {
1399                 /* Test words */
1400                 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
1401                 CS_InsertEntry (S, X, I+2);
1402                 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
1403                 CS_InsertEntry (S, X, I+3);
1404             }
1405
1406             /* Delete the subroutine call */
1407             CS_DelEntry (S, I+1);
1408
1409             /* Invert the branch */
1410             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1411
1412             /* Remember, we had changes */
1413             ++Changes;
1414
1415         }
1416
1417         /* Next entry */
1418         ++I;
1419
1420     }
1421
1422     /* Return the number of changes made */
1423     return Changes;
1424 }
1425
1426
1427
1428 /*****************************************************************************/
1429 /*                     Optimize stores through pointers                      */
1430 /*****************************************************************************/
1431
1432
1433
1434 static unsigned OptPtrStore1 (CodeSeg* S)
1435 /* Search for the sequence:
1436  *
1437  *      jsr     pushax
1438  *      lda     xxx
1439  *      ldy     yyy
1440  *      jsr     staspidx
1441  *
1442  * and replace it by:
1443  *
1444  *      sta     ptr1
1445  *      stx     ptr1+1
1446  *      lda     xxx
1447  *      ldy     yyy
1448  *      sta     (ptr1),y
1449  */
1450 {
1451     unsigned Changes = 0;
1452
1453     /* Walk over the entries */
1454     unsigned I = 0;
1455     while (I < CS_GetEntryCount (S)) {
1456
1457         CodeEntry* L[4];
1458
1459         /* Get next entry */
1460         L[0] = CS_GetEntry (S, I);
1461
1462         /* Check for the sequence */
1463         if (L[0]->OPC == OP65_JSR               &&
1464             strcmp (L[0]->Arg, "pushax") == 0   &&
1465             CS_GetEntries (S, L+1, I+1, 3)      &&
1466             L[1]->OPC == OP65_LDA               &&
1467             !CE_HasLabel (L[1])                 &&
1468             L[2]->OPC == OP65_LDY               &&
1469             !CE_HasLabel (L[2])                 &&
1470             L[3]->OPC == OP65_JSR               &&
1471             strcmp (L[3]->Arg, "staspidx") == 0 &&
1472             !CE_HasLabel (L[3])) {
1473
1474             CodeEntry* X;
1475
1476             /* Create and insert the stores */
1477             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1478             CS_InsertEntry (S, X, I+1);
1479
1480             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1481             CS_InsertEntry (S, X, I+2);
1482
1483             /* Delete the call to pushax */
1484             CS_DelEntry (S, I);
1485
1486             /* Insert the store through ptr1 */
1487             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1488             CS_InsertEntry (S, X, I+4);
1489
1490             /* Delete the call to staspidx */
1491             CS_DelEntry (S, I+5);
1492
1493             /* Remember, we had changes */
1494             ++Changes;
1495
1496         }
1497
1498         /* Next entry */
1499         ++I;
1500
1501     }
1502
1503     /* Return the number of changes made */
1504     return Changes;
1505 }
1506
1507
1508
1509 /*****************************************************************************/
1510 /*                      Optimize loads through pointers                      */
1511 /*****************************************************************************/
1512
1513
1514
1515 static unsigned OptPtrLoad1 (CodeSeg* S)
1516 /* Search for the sequence:
1517  *
1518  *      tax
1519  *      dey
1520  *      lda     (sp),y             # May be any destination
1521  *      ldy     ...
1522  *      jsr     ldauidx
1523  *
1524  * and replace it by:
1525  *
1526  *      sta     ptr1+1
1527  *      dey
1528  *      lda     (sp),y
1529  *      sta     ptr1
1530  *      ldy     ...
1531  *      ldx     #$00
1532  *      lda     (ptr1),y
1533  */
1534 {
1535     unsigned Changes = 0;
1536
1537     /* Walk over the entries */
1538     unsigned I = 0;
1539     while (I < CS_GetEntryCount (S)) {
1540
1541         CodeEntry* L[5];
1542
1543         /* Get next entry */
1544         L[0] = CS_GetEntry (S, I);
1545
1546         /* Check for the sequence */
1547         if (L[0]->OPC == OP65_TAX               &&
1548             CS_GetEntries (S, L+1, I+1, 4)      &&
1549             L[1]->OPC == OP65_DEY               &&
1550             !CE_HasLabel (L[1])                 &&
1551             L[2]->OPC == OP65_LDA               &&
1552             !CE_HasLabel (L[2])                 &&
1553             L[3]->OPC == OP65_LDY               &&
1554             !CE_HasLabel (L[3])                 &&
1555             L[4]->OPC == OP65_JSR               &&
1556             strcmp (L[4]->Arg, "ldauidx") == 0  &&
1557             !CE_HasLabel (L[4])) {
1558
1559             CodeEntry* X;
1560
1561             /* Store the high byte and remove the TAX instead */
1562             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1563             CS_InsertEntry (S, X, I+1);
1564             CS_DelEntry (S, I);
1565
1566             /* Store the low byte */
1567             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[2]->LI);
1568             CS_InsertEntry (S, X, I+3);
1569
1570             /* Delete the call to ldauidx */
1571             CS_DelEntry (S, I+5);
1572
1573             /* Load high and low byte */
1574             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
1575             CS_InsertEntry (S, X, I+5);
1576             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1577             CS_InsertEntry (S, X, I+6);
1578
1579             /* Remember, we had changes */
1580             ++Changes;
1581
1582         }
1583
1584         /* Next entry */
1585         ++I;
1586
1587     }
1588
1589     /* Return the number of changes made */
1590     return Changes;
1591 }
1592
1593
1594
1595 static unsigned OptPtrLoad2 (CodeSeg* S)
1596 /* Search for the sequence
1597  *
1598  *      ldy     ...
1599  *      jsr     ldauidx
1600  *
1601  * and replace it by:
1602  *
1603  *      ldy     ...
1604  *      stx     ptr1+1
1605  *      sta     ptr1
1606  *      ldx     #$00
1607  *      lda     (ptr1),y
1608  *
1609  * This step must be execute *after* OptPtrLoad1!
1610  */
1611 {
1612     unsigned Changes = 0;
1613
1614     /* Walk over the entries */
1615     unsigned I = 0;
1616     while (I < CS_GetEntryCount (S)) {
1617
1618         CodeEntry* L[2];
1619
1620         /* Get next entry */
1621         L[0] = CS_GetEntry (S, I);
1622
1623         /* Check for the sequence */
1624         if (L[0]->OPC == OP65_LDY               &&
1625             CS_GetEntries (S, L+1, I+1, 1)      &&
1626             L[1]->OPC == OP65_JSR               &&
1627             strcmp (L[1]->Arg, "ldauidx") == 0  &&
1628             !CE_HasLabel (L[1])) {
1629
1630             CodeEntry* X;
1631
1632             /* Store the high byte */
1633             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1634             CS_InsertEntry (S, X, I+1);
1635
1636             /* Store the low byte */
1637             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1638             CS_InsertEntry (S, X, I+2);
1639
1640             /* Delete the call to ldauidx */
1641             CS_DelEntry (S, I+3);
1642
1643             /* Load the high and low byte */
1644             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1645             CS_InsertEntry (S, X, I+3);
1646             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
1647             CS_InsertEntry (S, X, I+4);
1648
1649             /* Remember, we had changes */
1650             ++Changes;
1651
1652         }
1653
1654         /* Next entry */
1655         ++I;
1656
1657     }
1658
1659     /* Return the number of changes made */
1660     return Changes;
1661 }
1662
1663
1664
1665 /*****************************************************************************/
1666 /*                                   Code                                    */
1667 /*****************************************************************************/
1668
1669
1670
1671 /* Types of optimization steps */
1672 enum {
1673     optPre,                     /* Repeated once */
1674     optPreMain,                 /* Repeated more than once */
1675     optMain,                    /* dito */
1676     optPostMain,                /* dito */
1677     optPost                     /* Repeated once */
1678 };
1679
1680 /* Table with all the optimization functions */
1681 typedef struct OptFunc OptFunc;
1682 struct OptFunc {
1683     unsigned        (*Func) (CodeSeg*); /* Optimizer function */
1684     const char*     Name;               /* Name of optimizer step */
1685     unsigned char   Type;               /* Type of this step */
1686     char            Disabled;           /* True if pass disabled */
1687 };
1688
1689 /* Macro that builds a table entry */
1690 #define OptEntry(func,type)     { func, #func, type, 0 }
1691
1692 /* Table with optimizer steps */
1693 static OptFunc OptFuncs [] = {
1694     /* Optimizes stores through pointers */
1695     OptEntry (OptPtrStore1, optPre),
1696     /* Optimize loads through pointers */
1697     OptEntry (OptPtrLoad1, optMain),
1698     OptEntry (OptPtrLoad2, optMain),
1699     /* Optimize calls to nega */
1700     OptEntry (OptNegA1, optPre),
1701     OptEntry (OptNegA2, optPre),
1702     /* Optimize calls to negax */
1703     OptEntry (OptNegAX1, optPre),
1704     OptEntry (OptNegAX2, optPre),
1705     OptEntry (OptNegAX3, optPre),
1706     OptEntry (OptNegAX4, optPre),
1707     /* Optimize subtractions */
1708     OptEntry (OptSub1, optMain),
1709     OptEntry (OptSub2, optMain),
1710     /* Optimize additions */
1711     OptEntry (OptAdd1, optMain),
1712     /* Optimize jump cascades */
1713     OptEntry (OptJumpCascades, optMain),
1714     /* Remove dead jumps */
1715     OptEntry (OptDeadJumps, optMain),
1716     /* Change jsr/rts to jmp */
1717     OptEntry (OptRTS, optMain),
1718     /* Remove dead code */
1719     OptEntry (OptDeadCode, optMain),
1720     /* Optimize jump targets */
1721     OptEntry (OptJumpTarget, optMain),
1722     /* Optimize conditional branches */
1723     OptEntry (OptCondBranches, optMain),
1724     /* Replace jumps to RTS by RTS */
1725     OptEntry (OptRTSJumps, optMain),
1726     /* Remove calls to the bool transformer subroutines */
1727     OptEntry (OptBoolTransforms, optMain),
1728     /* Optimize compares */
1729     OptEntry (OptCmp1, optMain),
1730     OptEntry (OptCmp2, optMain),
1731     OptEntry (OptCmp3, optMain),
1732     OptEntry (OptCmp4, optMain),
1733     OptEntry (OptCmp5, optMain),
1734     OptEntry (OptCmp6, optMain),
1735     /* Optimize tests */
1736     OptEntry (OptTest1, optMain),
1737     /* Remove unused loads */
1738     OptEntry (OptUnusedLoads, optMain),
1739     OptEntry (OptDuplicateLoads, optMain),
1740     OptEntry (OptStoreLoad, optMain),
1741     /* Optimize branch distance */
1742     OptEntry (OptBranchDist, optMain),
1743 };
1744
1745
1746
1747 static OptFunc* FindOptStep (const char* Name)
1748 /* Find an optimizer step by name in the table and return a pointer. Print an
1749  * error and call AbEnd if not found.
1750  */
1751 {
1752     unsigned I;
1753
1754     /* Run all optimization steps */
1755     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1756         if (strcmp (OptFuncs[I].Name, Name) == 0) {
1757             /* Found */
1758             return OptFuncs+I;
1759         }
1760     }
1761
1762     /* Not found */
1763     AbEnd ("Optimization step `%s' not found", Name);
1764     return 0;
1765 }
1766
1767
1768
1769 void DisableOpt (const char* Name)
1770 /* Disable the optimization with the given name */
1771 {
1772     if (strcmp (Name, "any") == 0) {
1773         unsigned I;
1774         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1775             OptFuncs[I].Disabled = 1;
1776         }
1777     } else {
1778         OptFunc* F = FindOptStep (Name);
1779         F->Disabled = 1;
1780     }
1781 }
1782
1783
1784
1785 void EnableOpt (const char* Name)
1786 /* Enable the optimization with the given name */
1787 {
1788     if (strcmp (Name, "any") == 0) {
1789         unsigned I;
1790         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1791             OptFuncs[I].Disabled = 0;
1792         }
1793     } else {
1794         OptFunc* F = FindOptStep (Name);
1795         F->Disabled = 0;
1796     }
1797 }
1798
1799
1800
1801 void ListOptSteps (FILE* F)
1802 /* List all optimization steps */
1803 {
1804     unsigned I;
1805     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1806         fprintf (F, "%s\n", OptFuncs[I].Name);
1807     }
1808 }
1809
1810
1811
1812 static void RepeatOptStep (CodeSeg* S, unsigned char Type, unsigned Max)
1813 /* Repeat the optimizer step of type Type at may Max times */
1814 {
1815     unsigned I;
1816     unsigned Pass = 0;
1817     unsigned OptChanges;
1818
1819     /* Repeat max times of until there are no more changes */
1820     do {
1821         /* Reset the number of changes */
1822         OptChanges = 0;
1823
1824         /* Keep the user hapy */
1825         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
1826
1827         /* Run all optimization steps */
1828         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1829
1830             /* Get the table entry */
1831             const OptFunc* F = OptFuncs + I;
1832
1833             /* Check if the type matches */
1834             if (F->Type != Type) {
1835                 /* Skip it */
1836                 continue;
1837             }
1838
1839             /* Print the name of the following optimizer step */
1840             Print (stdout, 1, "    %s:%*s", F->Name, (int) (30-strlen(F->Name)), "");
1841
1842             /* Check if the step is disabled */
1843             if (F->Disabled) {
1844                 Print (stdout, 1, "Disabled\n");
1845             } else {
1846                 unsigned Changes = F->Func (S);
1847                 OptChanges += Changes;
1848                 Print (stdout, 1, "%u Changes\n", Changes);
1849             }
1850         }
1851
1852     } while (--Max > 0 && OptChanges > 0);
1853 }
1854
1855
1856
1857 void RunOpt (CodeSeg* S)
1858 /* Run the optimizer */
1859 {
1860
1861     /* If we shouldn't run the optimizer, bail out */
1862     if (!Optimize) {
1863         return;
1864     }
1865
1866     /* Print the name of the function we are working on */
1867     if (S->Func) {
1868         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1869     } else {
1870         Print (stdout, 1, "Running optimizer for global code segment\n");
1871     }
1872
1873     /* Repeat all steps until there are no more changes */
1874     RepeatOptStep (S, optPre, 1);
1875     RepeatOptStep (S, optPreMain, 0xFFFF);
1876     RepeatOptStep (S, optMain, 0xFFFF);
1877     RepeatOptStep (S, optPostMain, 0xFFFF);
1878     RepeatOptStep (S, optPost, 1);
1879 }
1880
1881
1882