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 "chartype.h"
  41 #include "print.h"
  42 #include "xmalloc.h"
  43 #include "xsprintf.h"
  44
  45 /* cc65 */
  46 #include "asmlabel.h"
  47 #include "codeent.h"
  48 #include "codeinfo.h"
  49 #include "coptind.h"
  50 #include "error.h"
  51 #include "global.h"
  52 #include "codeopt.h"
  53
  54
  55
  56 /*****************************************************************************/
  57 /*                                   Data                                    */
  58 /*****************************************************************************/
  59
  60
  61
  62 /* Defines for the conditions in a compare */
  63 typedef enum {
  64     CMP_INV = -1,
  65     CMP_EQ,
  66     CMP_NE,
  67     CMP_GT,
  68     CMP_GE,
  69     CMP_LT,
  70     CMP_LE,
  71     CMP_UGT,
  72     CMP_UGE,
  73     CMP_ULT,
  74     CMP_ULE
  75 } cmp_t;
  76
  77 /* Table with the compare suffixes */
  78 static const char CmpSuffixTab [][4] = {
  79     "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
  80 };
  81
  82 /* Table used to invert a condition, indexed by condition */
  83 static const unsigned char CmpInvertTab [] = {
  84     CMP_NE, CMP_EQ,
  85     CMP_LE, CMP_LT, CMP_GE, CMP_GT,
  86     CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
  87 };
  88
  89 /* Table to show which compares are signed (use the N flag) */
  90 static const char CmpSignedTab [] = {
  91     0, 0, 1, 1, 1, 1, 0, 0, 0, 0
  92 };
  93
  94
  95
  96 /*****************************************************************************/
  97 /*                             Helper functions                              */
  98 /*****************************************************************************/
  99
 100
 101
 102 static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
 103 /* Search for a compare condition by the given code using the given length */
 104 {
 105     unsigned I;
 106
 107     /* Linear search */
 108     for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
 109         if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
 110             /* Found */
 111             return I;
 112         }
 113     }
 114
 115     /* Not found */
 116     return CMP_INV;
 117 }
 118
 119
 120
 121 static cmp_t FindBoolCmpCond (const char* Name)
 122 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
 123 {
 124     /* Check for the correct subroutine name */
 125     if (strncmp (Name, "bool", 4) == 0) {
 126         /* Name is ok, search for the code in the table */
 127         return FindCmpCond (Name+4, strlen(Name)-4);
 128     } else {
 129         /* Not found */
 130         return CMP_INV;
 131     }
 132 }
 133
 134
 135
 136 static cmp_t FindTosCmpCond (const char* Name)
 137 /* Check if this is a call to one of the TOS compare functions (tosgtax).
 138  * Return the condition code or CMP_INV on failure.
 139  */
 140 {
 141     unsigned Len = strlen (Name);
 142
 143     /* Check for the correct subroutine name */
 144     if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
 145         /* Name is ok, search for the code in the table */
 146         return FindCmpCond (Name+3, Len-3-2);
 147     } else {
 148         /* Not found */
 149         return CMP_INV;
 150     }
 151 }
 152
 153
 154
 155 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
 156 /* Helper function for the replacement of routines that return a boolean
 157  * followed by a conditional jump. Instead of the boolean value, the condition
 158  * codes are evaluated directly.
 159  * I is the index of the conditional branch, the sequence is already checked
 160  * to be correct.
 161  */
 162 {
 163     CodeEntry* N;
 164     CodeLabel* L;
 165
 166     /* Get the entry */
 167     CodeEntry* E = CS_GetEntry (S, I);
 168
 169     /* Replace the conditional branch */
 170     switch (Cond) {
 171
 172         case CMP_EQ:
 173             CE_ReplaceOPC (E, OP65_JEQ);
 174             break;
 175
 176         case CMP_NE:
 177             CE_ReplaceOPC (E, OP65_JNE);
 178             break;
 179
 180         case CMP_GT:
 181             /* Replace by
 182              *     beq @L
 183              *     jpl Target
 184              * @L: ...
 185              */
 186             if ((N = CS_GetNextEntry (S, I)) == 0) {
 187                 /* No such entry */
 188                 Internal ("Invalid program flow");
 189             }
 190             L = CS_GenLabel (S, N);
 191             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 192             CS_InsertEntry (S, N, I);
 193             CE_ReplaceOPC (E, OP65_JPL);
 194             break;
 195
 196         case CMP_GE:
 197             CE_ReplaceOPC (E, OP65_JPL);
 198             break;
 199
 200         case CMP_LT:
 201             CE_ReplaceOPC (E, OP65_JMI);
 202             break;
 203
 204         case CMP_LE:
 205             /* Replace by
 206              *     jmi Target
 207              *     jeq Target
 208              */
 209             CE_ReplaceOPC (E, OP65_JMI);
 210             L = E->JumpTo;
 211             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 212             CS_InsertEntry (S, N, I+1);
 213             break;
 214
 215         case CMP_UGT:
 216             /* Replace by
 217              *     beq @L
 218              *     jcs Target
 219              * @L: ...
 220              */
 221             if ((N = CS_GetNextEntry (S, I)) == 0) {
 222                 /* No such entry */
 223                 Internal ("Invalid program flow");
 224             }
 225             L = CS_GenLabel (S, N);
 226             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 227             CS_InsertEntry (S, N, I);
 228             CE_ReplaceOPC (E, OP65_JCS);
 229             break;
 230
 231         case CMP_UGE:
 232             CE_ReplaceOPC (E, OP65_JCS);
 233             break;
 234
 235         case CMP_ULT:
 236             CE_ReplaceOPC (E, OP65_JCC);
 237             break;
 238
 239         case CMP_ULE:
 240             /* Replace by
 241              *     jcc Target
 242              *     jeq Target
 243              */
 244             CE_ReplaceOPC (E, OP65_JCC);
 245             L = E->JumpTo;
 246             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 247             CS_InsertEntry (S, N, I+1);
 248             break;
 249
 250         default:
 251             Internal ("Unknown jump condition: %d", Cond);
 252
 253     }
 254
 255 }
 256
 257
 258
 259 static int GetCmpRegVal (const CodeEntry* E)
 260 /* Return the register value for an immediate compare */
 261 {
 262     switch (E->OPC) {
 263         case OP65_CMP: return E->RI->In.RegA;
 264         case OP65_CPX: return E->RI->In.RegX;
 265         case OP65_CPY: return E->RI->In.RegY;
 266         default:       Internal ("Invalid opcode in GetCmpRegVal");
 267                        return 0;  /* Not reached */
 268     }
 269 }
 270
 271
 272
 273 static int IsCmpToZero (const CodeEntry* E)
 274 /* Check if the given instrcuction is a compare to zero instruction */
 275 {
 276     return (E->OPC == OP65_CMP            &&
 277             E->AM  == AM65_IMM            &&
 278             (E->Flags & CEF_NUMARG) != 0  &&
 279             E->Num == 0);
 280 }
 281
 282
 283
 284 static int IsSpLoad (const CodeEntry* E)
 285 /* Return true if this is the load of A from the stack */
 286 {
 287     return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
 288 }
 289
 290
 291
 292 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
 293                           CodeEntry** L, unsigned Count)
 294 /* Check if a 16 bit load of a local variable follows:
 295  *
 296  *      ldy     #$xx
 297  *      lda     (sp),y
 298  *      tax
 299  *      dey
 300  *      lda     (sp),y
 301  *
 302  * If so, read Count entries following the first ldy into L and return true
 303  * if this is possible. Otherwise return false.
 304  */
 305 {
 306     /* Be sure we read enough entries for the check */
 307     CHECK (Count >= 5);
 308
 309     /* Read the first entry */
 310     L[0] = CS_GetEntry (S, Index);
 311
 312     /* Check for the sequence */
 313     return (L[0]->OPC == OP65_LDY                        &&
 314             L[0]->AM == AM65_IMM                         &&
 315             (L[0]->Flags & CEF_NUMARG) != 0              &&
 316             CS_GetEntries (S, L+1, Index+1, Count-1)     &&
 317             IsSpLoad (L[1])                              &&
 318             !CE_HasLabel (L[1])                          &&
 319             L[2]->OPC == OP65_TAX                        &&
 320             !CE_HasLabel (L[2])                          &&
 321             L[3]->OPC == OP65_DEY                        &&
 322             !CE_HasLabel (L[3])                          &&
 323             IsSpLoad (L[4])                              &&
 324             !CE_HasLabel (L[4]));
 325 }
 326
 327
 328
 329 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
 330 /* Check if the instructions at L are an immidiate compare of a/x:
 331  *
 332  *
 333  */
 334 {
 335     return (L[0]->OPC == OP65_CPX                              &&
 336             L[0]->AM == AM65_IMM                               &&
 337             (L[0]->Flags & CEF_NUMARG) != 0                    &&
 338             !CE_HasLabel (L[0])                                &&
 339             (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE)   &&
 340             L[1]->JumpTo != 0                                  &&
 341             !CE_HasLabel (L[1])                                &&
 342             L[2]->OPC == OP65_CMP                              &&
 343             L[2]->AM == AM65_IMM                               &&
 344             (L[2]->Flags & CEF_NUMARG) != 0                    &&
 345             (L[3]->Info & OF_ZBRA) != 0                        &&
 346             L[3]->JumpTo != 0                                  &&
 347             (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
 348 }
 349
 350
 351
 352 /*****************************************************************************/
 353 /*             Remove calls to the bool transformer subroutines              */
 354 /*****************************************************************************/
 355
 356
 357
 358 static unsigned OptBoolTransforms (CodeSeg* S)
 359 /* Try to remove the call to boolean transformer routines where the call is
 360  * not really needed.
 361  */
 362 {
 363     unsigned Changes = 0;
 364
 365     /* Walk over the entries */
 366     unsigned I = 0;
 367     while (I < CS_GetEntryCount (S)) {
 368
 369         CodeEntry* N;
 370         cmp_t Cond;
 371
 372         /* Get next entry */
 373         CodeEntry* E = CS_GetEntry (S, I);
 374
 375         /* Check for a boolean transformer */
 376         if (E->OPC == OP65_JSR                           &&
 377             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 378             (N = CS_GetNextEntry (S, I)) != 0        &&
 379             (N->Info & OF_ZBRA) != 0) {
 380
 381             /* Make the boolean transformer unnecessary by changing the
 382              * the conditional jump to evaluate the condition flags that
 383              * are set after the compare directly. Note: jeq jumps if
 384              * the condition is not met, jne jumps if the condition is met.
 385              * Invert the code if we jump on condition not met.
 386              */
 387             if (GetBranchCond (N->OPC) == BC_EQ) {
 388                 /* Jumps if condition false, invert condition */
 389                 Cond = CmpInvertTab [Cond];
 390             }
 391
 392             /* Check if we can replace the code by something better */
 393             ReplaceCmp (S, I+1, Cond);
 394
 395             /* Remove the call to the bool transformer */
 396             CS_DelEntry (S, I);
 397
 398             /* Remember, we had changes */
 399             ++Changes;
 400
 401         }
 402
 403         /* Next entry */
 404         ++I;
 405
 406     }
 407
 408     /* Return the number of changes made */
 409     return Changes;
 410 }
 411
 412
 413
 414 /*****************************************************************************/
 415 /*                           Optimize subtractions                           */
 416 /*****************************************************************************/
 417
 418
 419
 420 static unsigned OptSub1 (CodeSeg* S)
 421 /* Search for the sequence
 422  *
 423  *      sbc     ...
 424  *      bcs     L
 425  *      dex
 426  * L:
 427  *
 428  * and remove the handling of the high byte if X is not used later.
 429  */
 430 {
 431     unsigned Changes = 0;
 432
 433     /* Walk over the entries */
 434     unsigned I = 0;
 435     while (I < CS_GetEntryCount (S)) {
 436
 437         CodeEntry* L[3];
 438
 439         /* Get next entry */
 440         CodeEntry* E = CS_GetEntry (S, I);
 441
 442         /* Check for the sequence */
 443         if (E->OPC == OP65_SBC                               &&
 444             CS_GetEntries (S, L, I+1, 3)                     &&
 445             (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) &&
 446             L[0]->JumpTo != 0                                &&
 447             !CE_HasLabel (L[0])                              &&
 448             L[1]->OPC == OP65_DEX                            &&
 449             !CE_HasLabel (L[1])                              &&
 450             L[0]->JumpTo->Owner == L[2]                      &&
 451             !RegXUsed (S, I+3)) {
 452
 453             /* Remove the bcs/dex */
 454             CS_DelEntries (S, I+1, 2);
 455
 456             /* Remember, we had changes */
 457             ++Changes;
 458
 459         }
 460
 461         /* Next entry */
 462         ++I;
 463
 464     }
 465
 466     /* Return the number of changes made */
 467     return Changes;
 468 }
 469
 470
 471
 472 static unsigned OptSub2 (CodeSeg* S)
 473 /* Search for the sequence
 474  *
 475  *      lda     xx
 476  *      sec
 477  *      sta     tmp1
 478  *      lda     yy
 479  *      sbc     tmp1
 480  *      sta     yy
 481  *
 482  * and replace it by
 483  *
 484  *      sec
 485  *      lda     yy
 486  *      sbc     xx
 487  *      sta     yy
 488  */
 489 {
 490     unsigned Changes = 0;
 491
 492     /* Walk over the entries */
 493     unsigned I = 0;
 494     while (I < CS_GetEntryCount (S)) {
 495
 496         CodeEntry* L[5];
 497
 498         /* Get next entry */
 499         CodeEntry* E = CS_GetEntry (S, I);
 500
 501         /* Check for the sequence */
 502         if (E->OPC == OP65_LDA                             &&
 503             CS_GetEntries (S, L, I+1, 5)                   &&
 504             L[0]->OPC == OP65_SEC                          &&
 505             !CE_HasLabel (L[0])                            &&
 506             L[1]->OPC == OP65_STA                          &&
 507             strcmp (L[1]->Arg, "tmp1") == 0                &&
 508             !CE_HasLabel (L[1])                            &&
 509             L[2]->OPC == OP65_LDA                          &&
 510             !CE_HasLabel (L[2])                            &&
 511             L[3]->OPC == OP65_SBC                          &&
 512             strcmp (L[3]->Arg, "tmp1") == 0                &&
 513             !CE_HasLabel (L[3])                            &&
 514             L[4]->OPC == OP65_STA                          &&
 515             strcmp (L[4]->Arg, L[2]->Arg) == 0             &&
 516             !CE_HasLabel (L[4])) {
 517
 518             /* Remove the store to tmp1 */
 519             CS_DelEntry (S, I+2);
 520
 521             /* Remove the subtraction */
 522             CS_DelEntry (S, I+3);
 523
 524             /* Move the lda to the position of the subtraction and change the
 525              * op to SBC.
 526              */
 527             CS_MoveEntry (S, I, I+3);
 528             CE_ReplaceOPC (E, OP65_SBC);
 529
 530             /* If the sequence head had a label, move this label back to the
 531              * head.
 532              */
 533             if (CE_HasLabel (E)) {
 534                 CS_MoveLabels (S, E, L[0]);
 535             }
 536
 537             /* Remember, we had changes */
 538             ++Changes;
 539
 540         }
 541
 542         /* Next entry */
 543         ++I;
 544
 545     }
 546
 547     /* Return the number of changes made */
 548     return Changes;
 549 }
 550
 551
 552
 553 /*****************************************************************************/
 554 /*                            Optimize additions                             */
 555 /*****************************************************************************/
 556
 557
 558
 559 static unsigned OptAdd1 (CodeSeg* S)
 560 /* Search for the sequence
 561  *
 562  *      jsr     pushax
 563  *      ldy     xxx
 564  *      ldx     #$00
 565  *      lda     (sp),y
 566  *      jsr     tosaddax
 567  *
 568  * and replace it by:
 569  *
 570  *      ldy     xxx-2
 571  *      clc
 572  *      adc     (sp),y
 573  *      bcc     L
 574  *      inx
 575  * L:
 576  */
 577 {
 578     unsigned Changes = 0;
 579
 580     /* Walk over the entries */
 581     unsigned I = 0;
 582     while (I < CS_GetEntryCount (S)) {
 583
 584         CodeEntry* L[5];
 585
 586         /* Get next entry */
 587         CodeEntry* E = CS_GetEntry (S, I);
 588
 589         /* Check for the sequence */
 590         if (E->OPC == OP65_JSR                               &&
 591             strcmp (E->Arg, "pushax") == 0                   &&
 592             CS_GetEntries (S, L, I+1, 5)                     &&
 593             L[0]->OPC == OP65_LDY                            &&
 594             CE_KnownImm (L[0])                               &&
 595             !CE_HasLabel (L[0])                              &&
 596             L[1]->OPC == OP65_LDX                            &&
 597             CE_KnownImm (L[1])                               &&
 598             L[1]->Num == 0                                   &&
 599             !CE_HasLabel (L[1])                              &&
 600             L[2]->OPC == OP65_LDA                            &&
 601             !CE_HasLabel (L[2])                              &&
 602             L[3]->OPC == OP65_JSR                            &&
 603             strcmp (L[3]->Arg, "tosaddax") == 0              &&
 604             !CE_HasLabel (L[3])) {
 605
 606             CodeEntry* X;
 607             CodeLabel* Label;
 608
 609             /* Remove the call to pushax */
 610             CS_DelEntry (S, I);
 611
 612             /* Correct the stack offset (needed since pushax was removed) */
 613             CE_SetNumArg (L[0], L[0]->Num - 2);
 614
 615             /* Add the clc . */
 616             X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, L[3]->LI);
 617             CS_InsertEntry (S, X, I+1);
 618
 619             /* Remove the load */
 620             CS_DelEntry (S, I+3);      /* lda */
 621             CS_DelEntry (S, I+2);      /* ldx */
 622
 623             /* Add the adc */
 624             X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[3]->LI);
 625             CS_InsertEntry (S, X, I+2);
 626
 627             /* Generate the branch label and the branch */
 628             Label = CS_GenLabel (S, L[4]);
 629             X = NewCodeEntry (OP65_BCC, AM65_BRA, Label->Name, Label, L[3]->LI);
 630             CS_InsertEntry (S, X, I+3);
 631
 632             /* Generate the increment of the high byte */
 633             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, L[3]->LI);
 634             CS_InsertEntry (S, X, I+4);
 635
 636             /* Delete the call to tosaddax */
 637             CS_DelEntry (S, I+5);
 638
 639             /* Remember, we had changes */
 640             ++Changes;
 641
 642         }
 643
 644         /* Next entry */
 645         ++I;
 646
 647     }
 648
 649     /* Return the number of changes made */
 650     return Changes;
 651 }
 652
 653
 654
 655 static unsigned OptAdd2 (CodeSeg* S)
 656 /* Search for the sequence
 657  *
 658  *      ldy     #xx
 659  *      lda     (sp),y
 660  *      tax
 661  *      dey
 662  *      lda     (sp),y
 663  *      ldy     #$yy
 664  *      jsr     addeqysp
 665  *
 666  * and replace it by:
 667  *
 668  *      ldy     #xx-1
 669  *      lda     (sp),y
 670  *      ldy     #yy
 671  *      clc
 672  *      adc     (sp),y
 673  *      sta     (sp),y
 674  *      ldy     #xx
 675  *      lda     (sp),y
 676  *      ldy     #yy+1
 677  *      adc     (sp),y
 678  *      sta     (sp),y
 679  *
 680  * provided that a/x is not used later.
 681  */
 682 {
 683     unsigned Changes = 0;
 684
 685     /* Walk over the entries */
 686     unsigned I = 0;
 687     while (I < CS_GetEntryCount (S)) {
 688
 689         CodeEntry* L[7];
 690
 691         /* Get next entry */
 692         L[0] = CS_GetEntry (S, I);
 693
 694         /* Check for the sequence */
 695         if (L[0]->OPC == OP65_LDY               &&
 696             CE_KnownImm (L[0])                  &&
 697             CS_GetEntries (S, L+1, I+1, 6)      &&
 698             L[1]->OPC == OP65_LDA               &&
 699             L[1]->AM == AM65_ZP_INDY            &&
 700             !CE_HasLabel (L[1])                 &&
 701             L[2]->OPC == OP65_TAX               &&
 702             !CE_HasLabel (L[2])                 &&
 703             L[3]->OPC == OP65_DEY               &&
 704             !CE_HasLabel (L[3])                 &&
 705             L[4]->OPC == OP65_LDA               &&
 706             L[4]->AM == AM65_ZP_INDY            &&
 707             !CE_HasLabel (L[4])                 &&
 708             L[5]->OPC == OP65_LDY               &&
 709             CE_KnownImm (L[5])                  &&
 710             !CE_HasLabel (L[5])                 &&
 711             L[6]->OPC == OP65_JSR               &&
 712             strcmp (L[6]->Arg, "addeqysp") == 0 &&
 713             !CE_HasLabel (L[6])                 &&
 714             (GetRegInfo (S, I+7, REG_AX) & REG_AX) == 0) {
 715
 716             char Buf [20];
 717             CodeEntry* X;
 718             int Offs;
 719
 720
 721             /* Create a replacement for the first LDY */
 722             Offs = (int) (L[0]->Num - 1);
 723             xsprintf (Buf, sizeof (Buf), "$%02X", Offs);
 724             X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
 725             CS_InsertEntry (S, X, I+1);
 726             CS_DelEntry (S, I);
 727
 728             /* Load Y with the low offset of the target variable */
 729             X = NewCodeEntry (OP65_LDY, AM65_IMM, L[5]->Arg, 0, L[1]->LI);
 730             CS_InsertEntry (S, X, I+2);
 731
 732             /* Add the CLC */
 733             X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, L[1]->LI);
 734             CS_InsertEntry (S, X, I+3);
 735
 736             /* Remove the TAX/DEY sequence */
 737             CS_DelEntry (S, I+5);      /* dey */
 738             CS_DelEntry (S, I+4);      /* tax */
 739
 740             /* Addition of the low byte */
 741             X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[4]->LI);
 742             CS_InsertEntry (S, X, I+4);
 743             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "sp", 0, L[4]->LI);
 744             CS_InsertEntry (S, X, I+5);
 745
 746             /* LDY */
 747             xsprintf (Buf, sizeof (Buf), "$%02X", (Offs+1));
 748             X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[4]->LI);
 749             CS_InsertEntry (S, X, I+6);
 750
 751             /* Addition of the high byte */
 752             xsprintf (Buf, sizeof (Buf), "$%02X", (int)(L[5]->Num+1));
 753             X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[5]->LI);
 754             CS_InsertEntry (S, X, I+8);
 755             X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[6]->LI);
 756             CS_InsertEntry (S, X, I+9);
 757             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "sp", 0, L[6]->LI);
 758             CS_InsertEntry (S, X, I+10);
 759
 760             /* Delete the remaining stuff */
 761             CS_DelEntry (S, I+12);
 762             CS_DelEntry (S, I+11);
 763
 764             /* Remember, we had changes */
 765             ++Changes;
 766
 767         }
 768
 769         /* Next entry */
 770         ++I;
 771
 772     }
 773
 774     /* Return the number of changes made */
 775     return Changes;
 776 }
 777
 778
 779
 780 static unsigned OptAdd3 (CodeSeg* S)
 781 /* Search for the sequence
 782  *
 783  *      adc     ...
 784  *      bcc     L
 785  *      inx
 786  * L:
 787  *
 788  * and remove the handling of the high byte if X is not used later.
 789  */
 790 {
 791     unsigned Changes = 0;
 792
 793     /* Walk over the entries */
 794     unsigned I = 0;
 795     while (I < CS_GetEntryCount (S)) {
 796
 797         CodeEntry* L[3];
 798
 799         /* Get next entry */
 800         CodeEntry* E = CS_GetEntry (S, I);
 801
 802         /* Check for the sequence */
 803         if (E->OPC == OP65_ADC                               &&
 804             CS_GetEntries (S, L, I+1, 3)                     &&
 805             (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
 806             L[0]->JumpTo != 0                                &&
 807             !CE_HasLabel (L[0])                              &&
 808             L[1]->OPC == OP65_INX                            &&
 809             !CE_HasLabel (L[1])                              &&
 810             L[0]->JumpTo->Owner == L[2]                      &&
 811             !RegXUsed (S, I+3)) {
 812
 813             /* Remove the bcs/dex */
 814             CS_DelEntries (S, I+1, 2);
 815
 816             /* Remember, we had changes */
 817             ++Changes;
 818
 819         }
 820
 821         /* Next entry */
 822         ++I;
 823
 824     }
 825
 826     /* Return the number of changes made */
 827     return Changes;
 828 }
 829
 830
 831
 832 /*****************************************************************************/
 833 /*                              Optimize shifts                              */
 834 /*****************************************************************************/
 835
 836
 837
 838 static unsigned OptShift1 (CodeSeg* S)
 839 /* A call to the shlaxN routine may get replaced by one or more asl insns
 840  * if the value of X is not used later.
 841  */
 842 {
 843     unsigned Changes = 0;
 844
 845     /* Walk over the entries */
 846     unsigned I = 0;
 847     while (I < CS_GetEntryCount (S)) {
 848
 849         /* Get next entry */
 850         CodeEntry* E = CS_GetEntry (S, I);
 851
 852         /* Check for the sequence */
 853         if (E->OPC == OP65_JSR                       &&
 854             (strncmp (E->Arg, "shlax", 5) == 0 ||
 855              strncmp (E->Arg, "aslax", 5) == 0)      &&
 856             strlen (E->Arg) == 6                     &&
 857             IsDigit (E->Arg[5])                      &&
 858             !RegXUsed (S, I+1)) {
 859
 860             /* Insert shift insns */
 861             unsigned Count = E->Arg[5] - '0';
 862             while (Count--) {
 863                 CodeEntry* X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
 864                 CS_InsertEntry (S, X, I+1);
 865             }
 866
 867             /* Delete the call to shlax */
 868             CS_DelEntry (S, I);
 869
 870             /* Remember, we had changes */
 871             ++Changes;
 872
 873         }
 874
 875         /* Next entry */
 876         ++I;
 877
 878     }
 879
 880     /* Return the number of changes made */
 881     return Changes;
 882 }
 883
 884
 885
 886 /*****************************************************************************/
 887 /*                        Optimizations for compares                         */
 888 /*****************************************************************************/
 889
 890
 891
 892 static unsigned OptCmp1 (CodeSeg* S)
 893 /* Search for the sequence
 894  *
 895  *      stx     xx
 896  *      stx     tmp1
 897  *      ora     tmp1
 898  *
 899  * and replace it by
 900  *
 901  *      stx     xx
 902  *      ora     xx
 903  */
 904 {
 905     unsigned Changes = 0;
 906
 907     /* Walk over the entries */
 908     unsigned I = 0;
 909     while (I < CS_GetEntryCount (S)) {
 910
 911         CodeEntry* L[2];
 912
 913         /* Get next entry */
 914         CodeEntry* E = CS_GetEntry (S, I);
 915
 916         /* Check for the sequence */
 917         if (E->OPC == OP65_STX                  &&
 918             CS_GetEntries (S, L, I+1, 2)        &&
 919             L[0]->OPC == OP65_STX               &&
 920             strcmp (L[0]->Arg, "tmp1") == 0     &&
 921             !CE_HasLabel (L[0])                 &&
 922             L[1]->OPC == OP65_ORA               &&
 923             strcmp (L[1]->Arg, "tmp1") == 0     &&
 924             !CE_HasLabel (L[1])) {
 925
 926             /* Remove the remaining instructions */
 927             CS_DelEntries (S, I+1, 2);
 928
 929             /* Insert the ora instead */
 930             CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
 931
 932             /* Remember, we had changes */
 933             ++Changes;
 934
 935         }
 936
 937         /* Next entry */
 938         ++I;
 939
 940     }
 941
 942     /* Return the number of changes made */
 943     return Changes;
 944 }
 945
 946
 947
 948 static unsigned OptCmp2 (CodeSeg* S)
 949 /* Search for
 950  *
 951  *      lda/and/ora/eor ...
 952  *      cmp #$00
 953  *      jeq/jne
 954  * or
 955  *      lda/and/ora/eor ...
 956  *      cmp #$00
 957  *      jsr boolxx
 958  *
 959  * and remove the cmp.
 960  */
 961 {
 962     unsigned Changes = 0;
 963
 964     /* Walk over the entries */
 965     unsigned I = 0;
 966     while (I < CS_GetEntryCount (S)) {
 967
 968         CodeEntry* L[2];
 969
 970         /* Get next entry */
 971         CodeEntry* E = CS_GetEntry (S, I);
 972
 973         /* Check for the sequence */
 974         if ((E->OPC == OP65_ADC ||
 975              E->OPC == OP65_AND ||
 976              E->OPC == OP65_DEA ||
 977              E->OPC == OP65_EOR ||
 978              E->OPC == OP65_INA ||
 979              E->OPC == OP65_LDA ||
 980              E->OPC == OP65_ORA ||
 981              E->OPC == OP65_PLA ||
 982              E->OPC == OP65_SBC ||
 983              E->OPC == OP65_TXA ||
 984              E->OPC == OP65_TYA)                       &&
 985             CS_GetEntries (S, L, I+1, 2)               &&
 986             IsCmpToZero (L[0])                         &&
 987             !CE_HasLabel (L[0])                        &&
 988             ((L[1]->Info & OF_FBRA) != 0         ||
 989              (L[1]->OPC == OP65_JSR        &&
 990               FindBoolCmpCond (L[1]->Arg) != CMP_INV)) &&
 991             !CE_HasLabel (L[1])) {
 992
 993             /* Remove the compare */
 994             CS_DelEntry (S, I+1);
 995
 996             /* Remember, we had changes */
 997             ++Changes;
 998
 999         }
1000
1001         /* Next entry */
1002         ++I;
1003
1004     }
1005
1006     /* Return the number of changes made */
1007     return Changes;
1008 }
1009
1010
1011
1012 static unsigned OptCmp3 (CodeSeg* S)
1013 /* Search for
1014  *
1015  *      lda     x
1016  *      ldx     y
1017  *      cpx     #a
1018  *      bne     L1
1019  *      cmp     #b
1020  *      jne/jeq L2
1021  *
1022  * If a is zero, we may remove the compare. If a and b are both zero, we may
1023  * replace it by the sequence
1024  *
1025  *      lda     x
1026  *      ora     x+1
1027  *      jne/jeq ...
1028  *
1029  * L1 may be either the label at the branch instruction, or the target label
1030  * of this instruction.
1031  */
1032 {
1033     unsigned Changes = 0;
1034
1035     /* Walk over the entries */
1036     unsigned I = 0;
1037     while (I < CS_GetEntryCount (S)) {
1038
1039         CodeEntry* L[5];
1040
1041         /* Get next entry */
1042         CodeEntry* E = CS_GetEntry (S, I);
1043
1044         /* Check for the sequence */
1045         if (E->OPC == OP65_LDA               &&
1046             CS_GetEntries (S, L, I+1, 5) &&
1047             L[0]->OPC == OP65_LDX            &&
1048             !CE_HasLabel (L[0])              &&
1049             IsImmCmp16 (S, L+1)) {
1050
1051             if (L[1]->Num == 0 && L[3]->Num == 0) {
1052                 /* The value is zero, we may use the simple code version. */
1053                 CE_ReplaceOPC (L[0], OP65_ORA);
1054                 CS_DelEntries (S, I+2, 3);
1055             } else {
1056                 /* Move the lda instruction after the first branch. This will
1057                  * improve speed, since the load is delayed after the first
1058                  * test.
1059                  */
1060                 CS_MoveEntry (S, I, I+4);
1061
1062                 /* We will replace the ldx/cpx by lda/cmp */
1063                 CE_ReplaceOPC (L[0], OP65_LDA);
1064                 CE_ReplaceOPC (L[1], OP65_CMP);
1065
1066                 /* Beware: If the first LDA instruction had a label, we have
1067                  * to move this label to the top of the sequence again.
1068                  */
1069                 if (CE_HasLabel (E)) {
1070                     CS_MoveLabels (S, E, L[0]);
1071                 }
1072
1073             }
1074
1075             ++Changes;
1076         }
1077
1078         /* Next entry */
1079         ++I;
1080
1081     }
1082
1083     /* Return the number of changes made */
1084     return Changes;
1085 }
1086
1087
1088
1089 static unsigned OptCmp4 (CodeSeg* S)
1090 /* Optimize compares of local variables:
1091  *
1092  *      ldy     #o
1093  *      lda     (sp),y
1094  *      tax
1095  *      dey
1096  *      lda     (sp),y
1097  *      cpx     #a
1098  *      bne     L1
1099  *      cmp     #b
1100  *      jne/jeq L2
1101  */
1102 {
1103     unsigned Changes = 0;
1104
1105     /* Walk over the entries */
1106     unsigned I = 0;
1107     while (I < CS_GetEntryCount (S)) {
1108
1109         CodeEntry* L[9];
1110
1111         /* Check for the sequence */
1112         if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
1113
1114             if (L[5]->Num == 0 && L[7]->Num == 0) {
1115
1116                 /* The value is zero, we may use the simple code version:
1117                  *      ldy     #o
1118                  *      lda     (sp),y
1119                  *      dey
1120                  *      ora     (sp),y
1121                  *      jne/jeq ...
1122                  */
1123                 CE_ReplaceOPC (L[4], OP65_ORA);
1124                 CS_DelEntries (S, I+5, 3);   /* cpx/bne/cmp */
1125                 CS_DelEntry (S, I+2);        /* tax */
1126
1127             } else {
1128
1129                 /* Change the code to just use the A register. Move the load
1130                  * of the low byte after the first branch if possible:
1131                  *
1132                  *      ldy     #o
1133                  *      lda     (sp),y
1134                  *      cmp     #a
1135                  *      bne     L1
1136                  *      dey
1137                  *      lda     (sp),y
1138                  *      cmp     #b
1139                  *      jne/jeq ...
1140                  */
1141                 CS_DelEntry (S, I+2);             /* tax */
1142                 CE_ReplaceOPC (L[5], OP65_CMP);   /* cpx -> cmp */
1143                 CS_MoveEntry (S, I+4, I+2);       /* cmp */
1144                 CS_MoveEntry (S, I+5, I+3);       /* bne */
1145
1146             }
1147
1148             ++Changes;
1149         }
1150
1151         /* Next entry */
1152         ++I;
1153
1154     }
1155
1156     /* Return the number of changes made */
1157     return Changes;
1158 }
1159
1160
1161
1162 static unsigned OptCmp5 (CodeSeg* S)
1163 /* Search for calls to compare subroutines followed by a conditional branch
1164  * and replace them by cheaper versions, since the branch means that the
1165  * boolean value returned by these routines is not needed (we may also check
1166  * that explicitly, but for the current code generator it is always true).
1167  */
1168 {
1169     unsigned Changes = 0;
1170
1171     /* Walk over the entries */
1172     unsigned I = 0;
1173     while (I < CS_GetEntryCount (S)) {
1174
1175         CodeEntry* N;
1176         cmp_t Cond;
1177
1178         /* Get next entry */
1179         CodeEntry* E = CS_GetEntry (S, I);
1180
1181         /* Check for the sequence */
1182         if (E->OPC == OP65_JSR                          &&
1183             (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
1184             (N = CS_GetNextEntry (S, I)) != 0           &&
1185             (N->Info & OF_ZBRA) != 0                    &&
1186             !CE_HasLabel (N)) {
1187
1188             /* The tos... functions will return a boolean value in a/x and
1189              * the Z flag says if this value is zero or not. We will call
1190              * a cheaper subroutine instead, one that does not return a
1191              * boolean value but only valid flags. Note: jeq jumps if
1192              * the condition is not met, jne jumps if the condition is met.
1193              * Invert the code if we jump on condition not met.
1194              */
1195             if (GetBranchCond (N->OPC) == BC_EQ) {
1196                 /* Jumps if condition false, invert condition */
1197                 Cond = CmpInvertTab [Cond];
1198             }
1199
1200             /* Replace the subroutine call. */
1201             E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
1202             CS_InsertEntry (S, E, I+1);
1203             CS_DelEntry (S, I);
1204
1205             /* Replace the conditional branch */
1206             ReplaceCmp (S, I+1, Cond);
1207
1208             /* Remember, we had changes */
1209             ++Changes;
1210
1211         }
1212
1213         /* Next entry */
1214         ++I;
1215
1216     }
1217
1218     /* Return the number of changes made */
1219     return Changes;
1220 }
1221
1222
1223
1224 static unsigned OptCmp6 (CodeSeg* S)
1225 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
1226  * used later.
1227  */
1228 {
1229     unsigned Changes = 0;
1230
1231     /* Walk over the entries */
1232     unsigned I = 0;
1233     while (I < CS_GetEntryCount (S)) {
1234
1235         CodeEntry* L[2];
1236
1237         /* Get next entry */
1238         CodeEntry* E = CS_GetEntry (S, I);
1239
1240         /* Check for the sequence */
1241         if ((E->OPC == OP65_LDX)                        &&
1242             CS_GetEntries (S, L, I+1, 2)                &&
1243             L[0]->OPC == OP65_TXA                       &&
1244             !CE_HasLabel (L[0])                         &&
1245             (L[1]->Info & OF_FBRA) != 0                 &&
1246             !CE_HasLabel (L[1])                         &&
1247             !RegAUsed (S, I+3)) {
1248
1249             /* Remove the txa */
1250             CS_DelEntry (S, I+1);
1251
1252             /* Remember, we had changes */
1253             ++Changes;
1254
1255         }
1256
1257         /* Next entry */
1258         ++I;
1259
1260     }
1261
1262     /* Return the number of changes made */
1263     return Changes;
1264 }
1265
1266
1267
1268 static unsigned OptCmp7 (CodeSeg* S)
1269 /* Check for register compares where the contents of the register and therefore
1270  * the result of the compare is known.
1271  */
1272 {
1273     unsigned Changes = 0;
1274     unsigned I;
1275
1276     /* Generate register info for this step */
1277     CS_GenRegInfo (S);
1278
1279     /* Walk over the entries */
1280     I = 0;
1281     while (I < CS_GetEntryCount (S)) {
1282
1283         int RegVal;
1284
1285         /* Get next entry */
1286         CodeEntry* E = CS_GetEntry (S, I);
1287
1288         /* Check for a compare against an immediate value */
1289         if ((E->Info & OF_CMP) != 0           &&
1290             (RegVal = GetCmpRegVal (E)) >= 0  &&
1291             CE_KnownImm (E)) {
1292
1293             /* We are able to evaluate the compare at compile time. Check if
1294              * one or more branches are ahead.
1295              */
1296             unsigned JumpsChanged = 0;
1297             CodeEntry* N;
1298             while ((N = CS_GetNextEntry (S, I)) != 0 &&   /* Followed by something.. */
1299                    (N->Info & OF_CBRA) != 0          &&   /* ..that is a cond branch.. */
1300                    !CE_HasLabel (N)) {                    /* ..and has no label */
1301
1302                 /* Evaluate the branch condition */
1303                 int Cond;
1304                 switch (GetBranchCond (N->OPC)) {
1305                     case BC_CC:
1306                         Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num);
1307                         break;
1308
1309                     case BC_CS:
1310                         Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num);
1311                         break;
1312
1313                     case BC_EQ:
1314                         Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num);
1315                         break;
1316
1317                     case BC_MI:
1318                         Cond = ((signed char)RegVal) < ((signed char)E->Num);
1319                         break;
1320
1321                     case BC_NE:
1322                         Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num);
1323                         break;
1324
1325                     case BC_PL:
1326                         Cond = ((signed char)RegVal) >= ((signed char)E->Num);
1327                         break;
1328
1329                     case BC_VC:
1330                     case BC_VS:
1331                 }
1332
1333                 /* If the condition is false, we may remove the jump. Otherwise
1334                  * the branch will always be taken, so we may replace it by a
1335                  * jump (and bail out).
1336                  */
1337                 if (!Cond) {
1338                     CS_DelEntry (S, I+1);
1339                 } else {
1340                     CodeLabel* L = N->JumpTo;
1341                     CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, L->Name, L, N->LI);
1342                     CS_InsertEntry (S, X, I+2);
1343                     CS_DelEntry (S, I+1);
1344                 }
1345
1346                 /* Remember, we had changes */
1347                 ++JumpsChanged;
1348                 ++Changes;
1349             }
1350
1351             /* If we have made changes above, we may also remove the compare */
1352             if (JumpsChanged) {
1353                 CS_DelEntry (S, I);
1354             }
1355
1356         }
1357
1358         /* Next entry */
1359         ++I;
1360
1361     }
1362
1363     /* Free register info */
1364     CS_FreeRegInfo (S);
1365
1366     /* Return the number of changes made */
1367     return Changes;
1368 }
1369
1370
1371
1372 /*****************************************************************************/
1373 /*                              Optimize tests                               */
1374 /*****************************************************************************/
1375
1376
1377
1378 static unsigned OptTest1 (CodeSeg* S)
1379 /* On a sequence
1380  *
1381  *     stx     xxx
1382  *     ora     xxx
1383  *     beq/bne ...
1384  *
1385  * if X is zero, the sequence may be changed to
1386  *
1387  *     cmp     #$00
1388  *     beq/bne ...
1389  *
1390  * which may be optimized further by another step.
1391  *
1392  * If A is zero, the sequence may be changed to
1393  *
1394  *     txa
1395  *     beq/bne ...
1396  *
1397  */
1398 {
1399     unsigned Changes = 0;
1400     unsigned I;
1401
1402     /* Generate register info for this step */
1403     CS_GenRegInfo (S);
1404
1405     /* Walk over the entries */
1406     I = 0;
1407     while (I < CS_GetEntryCount (S)) {
1408
1409         CodeEntry* L[3];
1410
1411         /* Get next entry */
1412         L[0] = CS_GetEntry (S, I);
1413
1414         /* Check if it's the sequence we're searching for */
1415         if (L[0]->OPC == OP65_STX              &&
1416             CS_GetEntries (S, L+1, I+1, 2)     &&
1417             !CE_HasLabel (L[1])                &&
1418             L[1]->OPC == OP65_ORA              &&
1419             strcmp (L[0]->Arg, L[1]->Arg) == 0 &&
1420             !CE_HasLabel (L[2])                &&
1421             (L[2]->Info & OF_ZBRA) != 0) {
1422
1423             /* Check if X is zero */
1424             if (L[0]->RI->In.RegX == 0) {
1425
1426                 /* Insert the compare */
1427                 CodeEntry* N = NewCodeEntry (OP65_CMP, AM65_IMM, "$00", 0, L[0]->LI);
1428                 CS_InsertEntry (S, N, I+2);
1429
1430                 /* Remove the two other insns */
1431                 CS_DelEntry (S, I+1);
1432                 CS_DelEntry (S, I);
1433
1434                 /* We had changes */
1435                 ++Changes;
1436
1437             /* Check if A is zero */
1438             } else if (L[1]->RI->In.RegA == 0) {
1439
1440                 /* Insert the txa */
1441                 CodeEntry* N = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, L[1]->LI);
1442                 CS_InsertEntry (S, N, I+2);
1443
1444                 /* Remove the two other insns */
1445                 CS_DelEntry (S, I+1);
1446                 CS_DelEntry (S, I);
1447
1448                 /* We had changes */
1449                 ++Changes;
1450             }
1451         }
1452
1453         /* Next entry */
1454         ++I;
1455
1456     }
1457
1458     /* Free register info */
1459     CS_FreeRegInfo (S);
1460
1461     /* Return the number of changes made */
1462     return Changes;
1463 }
1464
1465
1466
1467 /*****************************************************************************/
1468 /*                            nega optimizations                             */
1469 /*****************************************************************************/
1470
1471
1472
1473 static unsigned OptNegA1 (CodeSeg* S)
1474 /* Check for
1475  *
1476  *      ldx     #$00
1477  *      lda     ..
1478  *      jsr     bnega
1479  *
1480  * Remove the ldx if the lda does not use it.
1481  */
1482 {
1483     unsigned Changes = 0;
1484
1485     /* Walk over the entries */
1486     unsigned I = 0;
1487     while (I < CS_GetEntryCount (S)) {
1488
1489         CodeEntry* L[2];
1490
1491         /* Get next entry */
1492         CodeEntry* E = CS_GetEntry (S, I);
1493
1494         /* Check for a ldx */
1495         if (E->OPC == OP65_LDX                  &&
1496             E->AM == AM65_IMM                   &&
1497             (E->Flags & CEF_NUMARG) != 0        &&
1498             E->Num == 0                         &&
1499             CS_GetEntries (S, L, I+1, 2)        &&
1500             L[0]->OPC == OP65_LDA               &&
1501             (L[0]->Use & REG_X) == 0            &&
1502             !CE_HasLabel (L[0])                 &&
1503             L[1]->OPC == OP65_JSR               &&
1504             strcmp (L[1]->Arg, "bnega") == 0    &&
1505             !CE_HasLabel (L[1])) {
1506
1507             /* Remove the ldx instruction */
1508             CS_DelEntry (S, I);
1509
1510             /* Remember, we had changes */
1511             ++Changes;
1512
1513         }
1514
1515         /* Next entry */
1516         ++I;
1517
1518     }
1519
1520     /* Return the number of changes made */
1521     return Changes;
1522 }
1523
1524
1525
1526 static unsigned OptNegA2 (CodeSeg* S)
1527 /* Check for
1528  *
1529  *      lda     ..
1530  *      jsr     bnega
1531  *      jeq/jne ..
1532  *
1533  * Adjust the conditional branch and remove the call to the subroutine.
1534  */
1535 {
1536     unsigned Changes = 0;
1537
1538     /* Walk over the entries */
1539     unsigned I = 0;
1540     while (I < CS_GetEntryCount (S)) {
1541
1542         CodeEntry* L[2];
1543
1544         /* Get next entry */
1545         CodeEntry* E = CS_GetEntry (S, I);
1546
1547         /* Check for the sequence */
1548         if ((E->OPC == OP65_ADC ||
1549              E->OPC == OP65_AND ||
1550              E->OPC == OP65_DEA ||
1551              E->OPC == OP65_EOR ||
1552              E->OPC == OP65_INA ||
1553              E->OPC == OP65_LDA ||
1554              E->OPC == OP65_ORA ||
1555              E->OPC == OP65_PLA ||
1556              E->OPC == OP65_SBC ||
1557              E->OPC == OP65_TXA ||
1558              E->OPC == OP65_TYA)                &&
1559             CS_GetEntries (S, L, I+1, 2)        &&
1560             L[0]->OPC == OP65_JSR               &&
1561             strcmp (L[0]->Arg, "bnega") == 0    &&
1562             !CE_HasLabel (L[0])                 &&
1563             (L[1]->Info & OF_ZBRA) != 0         &&
1564             !CE_HasLabel (L[1])) {
1565
1566             /* Invert the branch */
1567             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1568
1569             /* Delete the subroutine call */
1570             CS_DelEntry (S, I+1);
1571
1572             /* Remember, we had changes */
1573             ++Changes;
1574
1575         }
1576
1577         /* Next entry */
1578         ++I;
1579
1580     }
1581
1582     /* Return the number of changes made */
1583     return Changes;
1584 }
1585
1586
1587
1588 /*****************************************************************************/
1589 /*                            negax optimizations                            */
1590 /*****************************************************************************/
1591
1592
1593
1594 static unsigned OptNegAX1 (CodeSeg* S)
1595 /* On a call to bnegax, if X is zero, the result depends only on the value in
1596  * A, so change the call to a call to bnega. This will get further optimized
1597  * later if possible.
1598  */
1599 {
1600     unsigned Changes = 0;
1601     unsigned I;
1602
1603     /* Generate register info for this step */
1604     CS_GenRegInfo (S);
1605
1606     /* Walk over the entries */
1607     I = 0;
1608     while (I < CS_GetEntryCount (S)) {
1609
1610         /* Get next entry */
1611         CodeEntry* E = CS_GetEntry (S, I);
1612
1613         /* Check if this is a call to bnegax, and if X is known and zero */
1614         if (E->OPC == OP65_JSR              &&
1615             E->RI->In.RegX == 0             &&
1616             strcmp (E->Arg, "bnegax") == 0) {
1617
1618             /* We're cheating somewhat here ... */
1619             E->Arg[5] = '\0';
1620             E->Use &= ~REG_X;
1621
1622             /* We had changes */
1623             ++Changes;
1624         }
1625
1626         /* Next entry */
1627         ++I;
1628
1629     }
1630
1631     /* Free register info */
1632     CS_FreeRegInfo (S);
1633
1634     /* Return the number of changes made */
1635     return Changes;
1636 }
1637
1638
1639
1640 static unsigned OptNegAX2 (CodeSeg* S)
1641 /* Search for the sequence:
1642  *
1643  *      lda     (xx),y
1644  *      tax
1645  *      dey
1646  *      lda     (xx),y
1647  *      jsr     bnegax
1648  *      jne/jeq ...
1649  *
1650  * and replace it by
1651  *
1652  *      lda     (xx),y
1653  *      dey
1654  *      ora     (xx),y
1655  *      jeq/jne ...
1656  */
1657 {
1658     unsigned Changes = 0;
1659
1660     /* Walk over the entries */
1661     unsigned I = 0;
1662     while (I < CS_GetEntryCount (S)) {
1663
1664         CodeEntry* L[5];
1665
1666         /* Get next entry */
1667         CodeEntry* E = CS_GetEntry (S, I);
1668
1669         /* Check for the sequence */
1670         if (E->OPC == OP65_LDA                  &&
1671             E->AM == AM65_ZP_INDY               &&
1672             CS_GetEntries (S, L, I+1, 5)        &&
1673             L[0]->OPC == OP65_TAX               &&
1674             L[1]->OPC == OP65_DEY               &&
1675             L[2]->OPC == OP65_LDA               &&
1676             L[2]->AM == AM65_ZP_INDY            &&
1677             strcmp (L[2]->Arg, E->Arg) == 0     &&
1678             !CE_HasLabel (L[2])                 &&
1679             L[3]->OPC == OP65_JSR               &&
1680             strcmp (L[3]->Arg, "bnegax") == 0   &&
1681             !CE_HasLabel (L[3])                 &&
1682             (L[4]->Info & OF_ZBRA) != 0         &&
1683             !CE_HasLabel (L[4])) {
1684
1685             /* lda --> ora */
1686             CE_ReplaceOPC (L[2], OP65_ORA);
1687
1688             /* Invert the branch */
1689             CE_ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1690
1691             /* Delete the entries no longer needed. Beware: Deleting entries
1692              * will change the indices.
1693              */
1694             CS_DelEntry (S, I+4);               /* jsr bnegax */
1695             CS_DelEntry (S, I+1);               /* tax */
1696
1697             /* Remember, we had changes */
1698             ++Changes;
1699
1700         }
1701
1702         /* Next entry */
1703         ++I;
1704
1705     }
1706
1707     /* Return the number of changes made */
1708     return Changes;
1709 }
1710
1711
1712
1713 static unsigned OptNegAX3 (CodeSeg* S)
1714 /* Search for the sequence:
1715  *
1716  *      lda     xx
1717  *      ldx     yy
1718  *      jsr     bnegax
1719  *      jne/jeq ...
1720  *
1721  * and replace it by
1722  *
1723  *      lda     xx
1724  *      ora     xx+1
1725  *      jeq/jne ...
1726  */
1727 {
1728     unsigned Changes = 0;
1729
1730     /* Walk over the entries */
1731     unsigned I = 0;
1732     while (I < CS_GetEntryCount (S)) {
1733
1734         CodeEntry* L[3];
1735
1736         /* Get next entry */
1737         CodeEntry* E = CS_GetEntry (S, I);
1738
1739         /* Check for the sequence */
1740         if (E->OPC == OP65_LDA                  &&
1741             CS_GetEntries (S, L, I+1, 3)        &&
1742             L[0]->OPC == OP65_LDX               &&
1743             !CE_HasLabel (L[0])                 &&
1744             L[1]->OPC == OP65_JSR               &&
1745             strcmp (L[1]->Arg, "bnegax") == 0   &&
1746             !CE_HasLabel (L[1])                 &&
1747             (L[2]->Info & OF_ZBRA) != 0         &&
1748             !CE_HasLabel (L[2])) {
1749
1750             /* ldx --> ora */
1751             CE_ReplaceOPC (L[0], OP65_ORA);
1752
1753             /* Invert the branch */
1754             CE_ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1755
1756             /* Delete the subroutine call */
1757             CS_DelEntry (S, I+2);
1758
1759             /* Remember, we had changes */
1760             ++Changes;
1761
1762         }
1763
1764         /* Next entry */
1765         ++I;
1766
1767     }
1768
1769     /* Return the number of changes made */
1770     return Changes;
1771 }
1772
1773
1774
1775 static unsigned OptNegAX4 (CodeSeg* S)
1776 /* Search for the sequence:
1777  *
1778  *      jsr     xxx
1779  *      jsr     bnega(x)
1780  *      jeq/jne ...
1781  *
1782  * and replace it by:
1783  *
1784  *      jsr     xxx
1785  *      <boolean test>
1786  *      jne/jeq ...
1787  */
1788 {
1789     unsigned Changes = 0;
1790
1791     /* Walk over the entries */
1792     unsigned I = 0;
1793     while (I < CS_GetEntryCount (S)) {
1794
1795         CodeEntry* L[2];
1796
1797         /* Get next entry */
1798         CodeEntry* E = CS_GetEntry (S, I);
1799
1800         /* Check for the sequence */
1801         if (E->OPC == OP65_JSR                  &&
1802             CS_GetEntries (S, L, I+1, 2)        &&
1803             L[0]->OPC == OP65_JSR               &&
1804             strncmp (L[0]->Arg,"bnega",5) == 0  &&
1805             !CE_HasLabel (L[0])                 &&
1806             (L[1]->Info & OF_ZBRA) != 0         &&
1807             !CE_HasLabel (L[1])) {
1808
1809             CodeEntry* X;
1810
1811             /* Check if we're calling bnega or bnegax */
1812             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1813
1814             /* Insert apropriate test code */
1815             if (ByteSized) {
1816                 /* Test bytes */
1817                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
1818                 CS_InsertEntry (S, X, I+2);
1819             } else {
1820                 /* Test words */
1821                 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
1822                 CS_InsertEntry (S, X, I+2);
1823                 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
1824                 CS_InsertEntry (S, X, I+3);
1825             }
1826
1827             /* Delete the subroutine call */
1828             CS_DelEntry (S, I+1);
1829
1830             /* Invert the branch */
1831             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1832
1833             /* Remember, we had changes */
1834             ++Changes;
1835
1836         }
1837
1838         /* Next entry */
1839         ++I;
1840
1841     }
1842
1843     /* Return the number of changes made */
1844     return Changes;
1845 }
1846
1847
1848
1849 /*****************************************************************************/
1850 /*                     Optimize stores through pointers                      */
1851 /*****************************************************************************/
1852
1853
1854
1855 static unsigned OptPtrStore1Sub (CodeSeg* S, unsigned I, CodeEntry** const L)
1856 /* Check if this is one of the allowed suboperation for OptPtrStore1 */
1857 {
1858     /* Check for a label attached to the entry */
1859     if (CE_HasLabel (L[0])) {
1860         return 0;
1861     }
1862
1863     /* Check for single insn sub ops */
1864     if (L[0]->OPC == OP65_AND                                           ||
1865         L[0]->OPC == OP65_EOR                                           ||
1866         L[0]->OPC == OP65_ORA                                           ||
1867         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shlax", 5) == 0) ||
1868         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shrax", 5) == 0)) {
1869
1870         /* One insn */
1871         return 1;
1872
1873     } else if (L[0]->OPC == OP65_CLC                      &&
1874                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
1875                L[1]->OPC == OP65_ADC                      &&
1876                !CE_HasLabel (L[1])) {
1877         return 2;
1878     } else if (L[0]->OPC == OP65_SEC                      &&
1879                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
1880                L[1]->OPC == OP65_SBC                      &&
1881                !CE_HasLabel (L[1])) {
1882         return 2;
1883     }
1884
1885
1886
1887     /* Not found */
1888     return 0;
1889 }
1890
1891
1892
1893 static unsigned OptPtrStore1 (CodeSeg* S)
1894 /* Search for the sequence:
1895  *
1896  *      jsr     pushax
1897  *      ldy     xxx
1898  *      jsr     ldauidx
1899  *      subop
1900  *      ldy     yyy
1901  *      jsr     staspidx
1902  *
1903  * and replace it by:
1904  *
1905  *      sta     ptr1
1906  *      stx     ptr1+1
1907  *      ldy     xxx
1908  *      ldx     #$00
1909  *      lda     (ptr1),y
1910  *      subop
1911  *      ldy     yyy
1912  *      sta     (ptr1),y
1913  */
1914 {
1915     unsigned Changes = 0;
1916
1917     /* Walk over the entries */
1918     unsigned I = 0;
1919     while (I < CS_GetEntryCount (S)) {
1920
1921         unsigned K;
1922         CodeEntry* L[10];
1923
1924         /* Get next entry */
1925         L[0] = CS_GetEntry (S, I);
1926
1927         /* Check for the sequence */
1928         if (L[0]->OPC == OP65_JSR                   &&
1929             strcmp (L[0]->Arg, "pushax") == 0       &&
1930             CS_GetEntries (S, L+1, I+1, 3)          &&
1931             L[1]->OPC == OP65_LDY                   &&
1932             CE_KnownImm (L[1])                      &&
1933             !CE_HasLabel (L[1])                     &&
1934             L[2]->OPC == OP65_JSR                   &&
1935             strcmp (L[2]->Arg, "ldauidx") == 0      &&
1936             !CE_HasLabel (L[2])                     &&
1937             (K = OptPtrStore1Sub (S, I+3, L+3)) > 0 &&
1938             CS_GetEntries (S, L+3+K, I+3+K, 2)      &&
1939             L[3+K]->OPC == OP65_LDY                 &&
1940             CE_KnownImm (L[3+K])                    &&
1941             !CE_HasLabel (L[3+K])                   &&
1942             L[4+K]->OPC == OP65_JSR                 &&
1943             strcmp (L[4+K]->Arg, "staspidx") == 0   &&
1944             !CE_HasLabel (L[4+K])) {
1945
1946             CodeEntry* X;
1947
1948             /* Create and insert the stores */
1949             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1950             CS_InsertEntry (S, X, I+1);
1951
1952             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1953             CS_InsertEntry (S, X, I+2);
1954
1955             /* Delete the call to pushax */
1956             CS_DelEntry (S, I);
1957
1958             /* Delete the call to ldauidx */
1959             CS_DelEntry (S, I+3);
1960
1961             /* Insert the load from ptr1 */
1962             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
1963             CS_InsertEntry (S, X, I+3);
1964             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[2]->LI);
1965             CS_InsertEntry (S, X, I+4);
1966
1967             /* Insert the store through ptr1 */
1968             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1969             CS_InsertEntry (S, X, I+6+K);
1970
1971             /* Delete the call to staspidx */
1972             CS_DelEntry (S, I+7+K);
1973
1974             /* Remember, we had changes */
1975             ++Changes;
1976
1977         }
1978
1979         /* Next entry */
1980         ++I;
1981
1982     }
1983
1984     /* Return the number of changes made */
1985     return Changes;
1986 }
1987
1988
1989
1990 static unsigned OptPtrStore2 (CodeSeg* S)
1991 /* Search for the sequence:
1992  *
1993  *      jsr     pushax
1994  *      lda     xxx
1995  *      ldy     yyy
1996  *      jsr     staspidx
1997  *
1998  * and replace it by:
1999  *
2000  *      sta     ptr1
2001  *      stx     ptr1+1
2002  *      lda     xxx
2003  *      ldy     yyy
2004  *      sta     (ptr1),y
2005  */
2006 {
2007     unsigned Changes = 0;
2008
2009     /* Walk over the entries */
2010     unsigned I = 0;
2011     while (I < CS_GetEntryCount (S)) {
2012
2013         CodeEntry* L[4];
2014
2015         /* Get next entry */
2016         L[0] = CS_GetEntry (S, I);
2017
2018         /* Check for the sequence */
2019         if (L[0]->OPC == OP65_JSR               &&
2020             strcmp (L[0]->Arg, "pushax") == 0   &&
2021             CS_GetEntries (S, L+1, I+1, 3)      &&
2022             L[1]->OPC == OP65_LDA               &&
2023             !CE_HasLabel (L[1])                 &&
2024             L[2]->OPC == OP65_LDY               &&
2025             !CE_HasLabel (L[2])                 &&
2026             L[3]->OPC == OP65_JSR               &&
2027             strcmp (L[3]->Arg, "staspidx") == 0 &&
2028             !CE_HasLabel (L[3])) {
2029
2030             CodeEntry* X;
2031
2032             /* Create and insert the stores */
2033             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2034             CS_InsertEntry (S, X, I+1);
2035
2036             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2037             CS_InsertEntry (S, X, I+2);
2038
2039             /* Delete the call to pushax */
2040             CS_DelEntry (S, I);
2041
2042             /* Insert the store through ptr1 */
2043             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
2044             CS_InsertEntry (S, X, I+4);
2045
2046             /* Delete the call to staspidx */
2047             CS_DelEntry (S, I+5);
2048
2049             /* Remember, we had changes */
2050             ++Changes;
2051
2052         }
2053
2054         /* Next entry */
2055         ++I;
2056
2057     }
2058
2059     /* Return the number of changes made */
2060     return Changes;
2061 }
2062
2063
2064
2065 /*****************************************************************************/
2066 /*                      Optimize loads through pointers                      */
2067 /*****************************************************************************/
2068
2069
2070
2071 static unsigned OptPtrLoad1 (CodeSeg* S)
2072 /* Search for the sequence:
2073  *
2074  *      tax
2075  *      dey
2076  *      lda     (sp),y             # May be any destination
2077  *      ldy     ...
2078  *      jsr     ldauidx
2079  *
2080  * and replace it by:
2081  *
2082  *      sta     ptr1+1
2083  *      dey
2084  *      lda     (sp),y
2085  *      sta     ptr1
2086  *      ldy     ...
2087  *      ldx     #$00
2088  *      lda     (ptr1),y
2089  */
2090 {
2091     unsigned Changes = 0;
2092
2093     /* Walk over the entries */
2094     unsigned I = 0;
2095     while (I < CS_GetEntryCount (S)) {
2096
2097         CodeEntry* L[5];
2098
2099         /* Get next entry */
2100         L[0] = CS_GetEntry (S, I);
2101
2102         /* Check for the sequence */
2103         if (L[0]->OPC == OP65_TAX               &&
2104             CS_GetEntries (S, L+1, I+1, 4)      &&
2105             L[1]->OPC == OP65_DEY               &&
2106             !CE_HasLabel (L[1])                 &&
2107             L[2]->OPC == OP65_LDA               &&
2108             !CE_HasLabel (L[2])                 &&
2109             L[3]->OPC == OP65_LDY               &&
2110             !CE_HasLabel (L[3])                 &&
2111             L[4]->OPC == OP65_JSR               &&
2112             strcmp (L[4]->Arg, "ldauidx") == 0  &&
2113             !CE_HasLabel (L[4])) {
2114
2115             CodeEntry* X;
2116
2117             /* Store the high byte and remove the TAX instead */
2118             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2119             CS_InsertEntry (S, X, I+1);
2120             CS_DelEntry (S, I);
2121
2122             /* Store the low byte */
2123             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[2]->LI);
2124             CS_InsertEntry (S, X, I+3);
2125
2126             /* Delete the call to ldauidx */
2127             CS_DelEntry (S, I+5);
2128
2129             /* Load high and low byte */
2130             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
2131             CS_InsertEntry (S, X, I+5);
2132             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
2133             CS_InsertEntry (S, X, I+6);
2134
2135             /* Remember, we had changes */
2136             ++Changes;
2137
2138         }
2139
2140         /* Next entry */
2141         ++I;
2142
2143     }
2144
2145     /* Return the number of changes made */
2146     return Changes;
2147 }
2148
2149
2150
2151 static unsigned OptPtrLoad2 (CodeSeg* S)
2152 /* Search for the sequence:
2153  *
2154  *      adc     xxx
2155  *      tay
2156  *      txa
2157  *      adc     yyy
2158  *      tax
2159  *      tya
2160  *      ldy
2161  *      jsr     ldauidx
2162  *
2163  * and replace it by:
2164  *
2165  *      adc     xxx
2166  *      sta     ptr1
2167  *      txa
2168  *      adc     yyy
2169  *      sta     ptr1+1
2170  *      ldy
2171  *      ldx     #$00
2172  *      lda     (ptr1),y
2173  */
2174 {
2175     unsigned Changes = 0;
2176
2177     /* Walk over the entries */
2178     unsigned I = 0;
2179     while (I < CS_GetEntryCount (S)) {
2180
2181         CodeEntry* L[8];
2182
2183         /* Get next entry */
2184         L[0] = CS_GetEntry (S, I);
2185
2186         /* Check for the sequence */
2187         if (L[0]->OPC == OP65_ADC               &&
2188             CS_GetEntries (S, L+1, I+1, 7)      &&
2189             L[1]->OPC == OP65_TAY               &&
2190             !CE_HasLabel (L[1])                 &&
2191             L[2]->OPC == OP65_TXA               &&
2192             !CE_HasLabel (L[2])                 &&
2193             L[3]->OPC == OP65_ADC               &&
2194             !CE_HasLabel (L[3])                 &&
2195             L[4]->OPC == OP65_TAX               &&
2196             !CE_HasLabel (L[4])                 &&
2197             L[5]->OPC == OP65_TYA               &&
2198             !CE_HasLabel (L[5])                 &&
2199             L[6]->OPC == OP65_LDY               &&
2200             !CE_HasLabel (L[6])                 &&
2201             L[7]->OPC == OP65_JSR               &&
2202             strcmp (L[7]->Arg, "ldauidx") == 0  &&
2203             !CE_HasLabel (L[7])) {
2204
2205             CodeEntry* X;
2206
2207             /* Store the low byte and remove the TAY instead */
2208             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2209             CS_InsertEntry (S, X, I+1);
2210             CS_DelEntry (S, I+2);
2211
2212             /* Store the high byte */
2213             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[3]->LI);
2214             CS_InsertEntry (S, X, I+4);
2215
2216             /* Delete more transfer insns */
2217             CS_DelEntry (S, I+6);
2218             CS_DelEntry (S, I+5);
2219
2220             /* Delete the call to ldauidx */
2221             CS_DelEntry (S, I+6);
2222
2223             /* Load high and low byte */
2224             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
2225             CS_InsertEntry (S, X, I+6);
2226             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
2227             CS_InsertEntry (S, X, I+7);
2228
2229             /* Remember, we had changes */
2230             ++Changes;
2231
2232         }
2233
2234         /* Next entry */
2235         ++I;
2236
2237     }
2238
2239     /* Return the number of changes made */
2240     return Changes;
2241 }
2242
2243
2244
2245 static unsigned OptPtrLoad3 (CodeSeg* S)
2246 /* Search for the sequence:
2247  *
2248  *      adc     xxx
2249  *      pha
2250  *      txa
2251  *      iny
2252  *      adc     yyy
2253  *      tax
2254  *      pla
2255  *      ldy
2256  *      jsr     ldauidx
2257  *
2258  * and replace it by:
2259  *
2260  *      adc     xxx
2261  *      sta     ptr1
2262  *      txa
2263  *      iny
2264  *      adc     yyy
2265  *      sta     ptr1+1
2266  *      ldy
2267  *      ldx     #$00
2268  *      lda     (ptr1),y
2269  */
2270 {
2271     unsigned Changes = 0;
2272
2273     /* Walk over the entries */
2274     unsigned I = 0;
2275     while (I < CS_GetEntryCount (S)) {
2276
2277         CodeEntry* L[9];
2278
2279         /* Get next entry */
2280         L[0] = CS_GetEntry (S, I);
2281
2282         /* Check for the sequence */
2283         if (L[0]->OPC == OP65_ADC               &&
2284             CS_GetEntries (S, L+1, I+1, 8)      &&
2285             L[1]->OPC == OP65_PHA               &&
2286             !CE_HasLabel (L[1])                 &&
2287             L[2]->OPC == OP65_TXA               &&
2288             !CE_HasLabel (L[2])                 &&
2289             L[3]->OPC == OP65_INY               &&
2290             !CE_HasLabel (L[3])                 &&
2291             L[4]->OPC == OP65_ADC               &&
2292             !CE_HasLabel (L[4])                 &&
2293             L[5]->OPC == OP65_TAX               &&
2294             !CE_HasLabel (L[5])                 &&
2295             L[6]->OPC == OP65_PLA               &&
2296             !CE_HasLabel (L[6])                 &&
2297             L[7]->OPC == OP65_LDY               &&
2298             !CE_HasLabel (L[7])                 &&
2299             L[8]->OPC == OP65_JSR               &&
2300             strcmp (L[8]->Arg, "ldauidx") == 0  &&
2301             !CE_HasLabel (L[8])) {
2302
2303             CodeEntry* X;
2304
2305             /* Store the low byte and remove the PHA instead */
2306             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2307             CS_InsertEntry (S, X, I+1);
2308             CS_DelEntry (S, I+2);
2309
2310             /* Store the high byte */
2311             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[4]->LI);
2312             CS_InsertEntry (S, X, I+5);
2313
2314             /* Delete more transfer and PLA insns */
2315             CS_DelEntry (S, I+7);
2316             CS_DelEntry (S, I+6);
2317
2318             /* Delete the call to ldauidx */
2319             CS_DelEntry (S, I+7);
2320
2321             /* Load high and low byte */
2322             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
2323             CS_InsertEntry (S, X, I+7);
2324             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
2325             CS_InsertEntry (S, X, I+8);
2326
2327             /* Remember, we had changes */
2328             ++Changes;
2329
2330         }
2331
2332         /* Next entry */
2333         ++I;
2334
2335     }
2336
2337     /* Return the number of changes made */
2338     return Changes;
2339 }
2340
2341
2342
2343 static unsigned OptPtrLoad4 (CodeSeg* S)
2344 /* Search for the sequence:
2345  *
2346  *      lda     #<(label+0)
2347  *      ldx     #>(label+0)
2348  *      clc
2349  *      adc     xxx
2350  *      bcc     L
2351  *      inx
2352  * L:   ldy     #$00
2353  *      jsr     ldauidx
2354  *
2355  * and replace it by:
2356  *
2357  *      ldx     xxx
2358  *      lda     label,x
2359  *      ldx     #$00
2360  */
2361 {
2362     unsigned Changes = 0;
2363
2364     /* Walk over the entries */
2365     unsigned I = 0;
2366     while (I < CS_GetEntryCount (S)) {
2367
2368         CodeEntry* L[8];
2369         unsigned Len;
2370
2371         /* Get next entry */
2372         L[0] = CS_GetEntry (S, I);
2373
2374         /* Check for the sequence */
2375         if (L[0]->OPC == OP65_LDA                            &&
2376             L[0]->AM == AM65_IMM                             &&
2377             CS_GetEntries (S, L+1, I+1, 7)                   &&
2378             L[1]->OPC == OP65_LDX                            &&
2379             L[1]->AM == AM65_IMM                             &&
2380             !CE_HasLabel (L[1])                              &&
2381             L[2]->OPC == OP65_CLC                            &&
2382             !CE_HasLabel (L[2])                              &&
2383             L[3]->OPC == OP65_ADC                            &&
2384             (L[3]->AM == AM65_ABS || L[3]->AM == AM65_ZP)    &&
2385             !CE_HasLabel (L[3])                              &&
2386             (L[4]->OPC == OP65_BCC || L[4]->OPC == OP65_JCC) &&
2387             L[4]->JumpTo != 0                                &&
2388             L[4]->JumpTo->Owner == L[6]                      &&
2389             !CE_HasLabel (L[4])                              &&
2390             L[5]->OPC == OP65_INX                            &&
2391             !CE_HasLabel (L[5])                              &&
2392             L[6]->OPC == OP65_LDY                            &&
2393             CE_KnownImm (L[6])                               &&
2394             L[6]->Num == 0                                   &&
2395             L[7]->OPC == OP65_JSR                            &&
2396             strcmp (L[7]->Arg, "ldauidx") == 0               &&
2397             !CE_HasLabel (L[7])                              &&
2398             /* Check the label last because this is quite costly */
2399             (Len = strlen (L[0]->Arg)) > 3                   &&
2400             L[0]->Arg[0] == '<'                              &&
2401             L[0]->Arg[1] == '('                              &&
2402             strlen (L[1]->Arg) == Len                        &&
2403             L[1]->Arg[0] == '>'                              &&
2404             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
2405
2406             CodeEntry* X;
2407             char* Label;
2408
2409             /* We will create all the new stuff behind the current one so
2410              * we keep the line references.
2411              */
2412             X = NewCodeEntry (OP65_LDX, L[3]->AM, L[3]->Arg, 0, L[0]->LI);
2413             CS_InsertEntry (S, X, I+8);
2414
2415             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
2416             Label[Len-3] = '\0';
2417             X = NewCodeEntry (OP65_LDA, AM65_ABSX, Label, 0, L[0]->LI);
2418             CS_InsertEntry (S, X, I+9);
2419             xfree (Label);
2420
2421             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2422             CS_InsertEntry (S, X, I+10);
2423
2424             /* Remove the old code */
2425             CS_DelEntries (S, I, 8);
2426
2427             /* Remember, we had changes */
2428             ++Changes;
2429
2430         }
2431
2432         /* Next entry */
2433         ++I;
2434
2435     }
2436
2437     /* Return the number of changes made */
2438     return Changes;
2439 }
2440
2441
2442
2443 static unsigned OptPtrLoad5 (CodeSeg* S)
2444 /* Search for the sequence:
2445  *
2446  *      lda     #<(label+0)
2447  *      ldx     #>(label+0)
2448  *      ldy     #$xx
2449  *      clc
2450  *      adc     (sp),y
2451  *      bcc     L
2452  *      inx
2453  * L:   ldy     #$00
2454  *      jsr     ldauidx
2455  *
2456  * and replace it by:
2457  *
2458  *      ldy     #$xx
2459  *      lda     (sp),y
2460  *      tax
2461  *      lda     label,x
2462  *      ldx     #$00
2463  */
2464 {
2465     unsigned Changes = 0;
2466
2467     /* Walk over the entries */
2468     unsigned I = 0;
2469     while (I < CS_GetEntryCount (S)) {
2470
2471         CodeEntry* L[9];
2472         unsigned Len;
2473
2474         /* Get next entry */
2475         L[0] = CS_GetEntry (S, I);
2476
2477         /* Check for the sequence */
2478         if (L[0]->OPC == OP65_LDA                            &&
2479             L[0]->AM == AM65_IMM                             &&
2480             CS_GetEntries (S, L+1, I+1, 8)                   &&
2481             L[1]->OPC == OP65_LDX                            &&
2482             L[1]->AM == AM65_IMM                             &&
2483             !CE_HasLabel (L[1])                              &&
2484             L[2]->OPC == OP65_LDY                            &&
2485             CE_KnownImm (L[2])                               &&
2486             !CE_HasLabel (L[2])                              &&
2487             L[3]->OPC == OP65_CLC                            &&
2488             !CE_HasLabel (L[3])                              &&
2489             L[4]->OPC == OP65_ADC                            &&
2490             L[4]->AM == AM65_ZP_INDY                         &&
2491             !CE_HasLabel (L[4])                              &&
2492             (L[5]->OPC == OP65_BCC || L[5]->OPC == OP65_JCC) &&
2493             L[5]->JumpTo != 0                                &&
2494             L[5]->JumpTo->Owner == L[7]                      &&
2495             !CE_HasLabel (L[5])                              &&
2496             L[6]->OPC == OP65_INX                            &&
2497             !CE_HasLabel (L[6])                              &&
2498             L[7]->OPC == OP65_LDY                            &&
2499             CE_KnownImm (L[7])                               &&
2500             L[7]->Num == 0                                   &&
2501             L[8]->OPC == OP65_JSR                            &&
2502             strcmp (L[8]->Arg, "ldauidx") == 0               &&
2503             !CE_HasLabel (L[8])                              &&
2504             /* Check the label last because this is quite costly */
2505             (Len = strlen (L[0]->Arg)) > 3                   &&
2506             L[0]->Arg[0] == '<'                              &&
2507             L[0]->Arg[1] == '('                              &&
2508             strlen (L[1]->Arg) == Len                        &&
2509             L[1]->Arg[0] == '>'                              &&
2510             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
2511
2512             CodeEntry* X;
2513             char* Label;
2514
2515             /* Add the lda */
2516             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, L[4]->Arg, 0, L[0]->LI);
2517             CS_InsertEntry (S, X, I+3);
2518
2519             /* Add the tax */
2520             X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
2521             CS_InsertEntry (S, X, I+4);
2522
2523             /* Add the lda */
2524             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
2525             Label[Len-3] = '\0';
2526             X = NewCodeEntry (OP65_LDA, AM65_ABSX, Label, 0, L[0]->LI);
2527             CS_InsertEntry (S, X, I+5);
2528             xfree (Label);
2529
2530             /* Add the ldx */
2531             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2532             CS_InsertEntry (S, X, I+6);
2533
2534             /* Remove the old code */
2535             CS_DelEntries (S, I, 2);
2536             CS_DelEntries (S, I+5, 6);
2537
2538             /* Remember, we had changes */
2539             ++Changes;
2540
2541         }
2542
2543         /* Next entry */
2544         ++I;
2545
2546     }
2547
2548     /* Return the number of changes made */
2549     return Changes;
2550 }
2551
2552
2553
2554 static unsigned OptPtrLoad6 (CodeSeg* S)
2555 /* Search for the sequence
2556  *
2557  *      ldy     ...
2558  *      jsr     ldauidx
2559  *
2560  * and replace it by:
2561  *
2562  *      ldy     ...
2563  *      stx     ptr1+1
2564  *      sta     ptr1
2565  *      ldx     #$00
2566  *      lda     (ptr1),y
2567  *
2568  * This step must be execute *after* OptPtrLoad1!
2569  */
2570 {
2571     unsigned Changes = 0;
2572
2573     /* Walk over the entries */
2574     unsigned I = 0;
2575     while (I < CS_GetEntryCount (S)) {
2576
2577         CodeEntry* L[2];
2578
2579         /* Get next entry */
2580         L[0] = CS_GetEntry (S, I);
2581
2582         /* Check for the sequence */
2583         if (L[0]->OPC == OP65_LDY               &&
2584             CS_GetEntries (S, L+1, I+1, 1)      &&
2585             L[1]->OPC == OP65_JSR               &&
2586             strcmp (L[1]->Arg, "ldauidx") == 0  &&
2587             !CE_HasLabel (L[1])) {
2588
2589             CodeEntry* X;
2590
2591             /* Store the high byte */
2592             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2593             CS_InsertEntry (S, X, I+1);
2594
2595             /* Store the low byte */
2596             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2597             CS_InsertEntry (S, X, I+2);
2598
2599             /* Delete the call to ldauidx */
2600             CS_DelEntry (S, I+3);
2601
2602             /* Load the high and low byte */
2603             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2604             CS_InsertEntry (S, X, I+3);
2605             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
2606             CS_InsertEntry (S, X, I+4);
2607
2608             /* Remember, we had changes */
2609             ++Changes;
2610
2611         }
2612
2613         /* Next entry */
2614         ++I;
2615
2616     }
2617
2618     /* Return the number of changes made */
2619     return Changes;
2620 }
2621
2622
2623
2624 /*****************************************************************************/
2625 /*                                   Code                                    */
2626 /*****************************************************************************/
2627
2628
2629
2630 /* Types of optimization steps */
2631 enum {
2632     optPre,                     /* Repeated once */
2633     optPreMain,                 /* Repeated more than once */
2634     optMain,                    /* dito */
2635     optPostMain,                /* dito */
2636     optPost                     /* Repeated once */
2637 };
2638
2639 /* Table with all the optimization functions */
2640 typedef struct OptFunc OptFunc;
2641 struct OptFunc {
2642     unsigned        (*Func) (CodeSeg*); /* Optimizer function */
2643     const char*     Name;               /* Name of optimizer step */
2644     unsigned char   Type;               /* Type of this step */
2645     char            Disabled;           /* True if pass disabled */
2646 };
2647
2648 /* Macro that builds a table entry */
2649 #define OptEntry(func,type)     { func, #func, type, 0 }
2650
2651 /* Table with optimizer steps */
2652 static OptFunc OptFuncs [] = {
2653     /* Optimizes stores through pointers */
2654     OptEntry (OptPtrStore1, optPre),
2655     OptEntry (OptPtrStore2, optPre),
2656     /* Optimize loads through pointers */
2657     OptEntry (OptPtrLoad1, optPre),
2658     OptEntry (OptPtrLoad2, optPre),
2659     OptEntry (OptPtrLoad3, optPre),
2660     OptEntry (OptPtrLoad4, optPre),
2661     OptEntry (OptPtrLoad5, optPre),
2662     OptEntry (OptPtrLoad6, optMain),
2663     /* Optimize calls to nega */
2664     OptEntry (OptNegA1, optMain),
2665     OptEntry (OptNegA2, optMain),
2666     /* Optimize calls to negax */
2667     OptEntry (OptNegAX1, optPre),
2668     OptEntry (OptNegAX2, optPre),
2669     OptEntry (OptNegAX3, optPre),
2670     OptEntry (OptNegAX4, optPre),
2671     /* Optimize subtractions */
2672     OptEntry (OptSub1, optMain),
2673     OptEntry (OptSub2, optMain),
2674     /* Optimize additions */
2675     OptEntry (OptAdd1, optPre),
2676     OptEntry (OptAdd2, optPre),
2677     OptEntry (OptAdd3, optMain),
2678     /* Optimize shifts */
2679     OptEntry (OptShift1, optPre),
2680     /* Optimize jump cascades */
2681     OptEntry (OptJumpCascades, optMain),
2682     /* Remove dead jumps */
2683     OptEntry (OptDeadJumps, optMain),
2684     /* Change jsr/rts to jmp */
2685     OptEntry (OptRTS, optMain),
2686     /* Remove dead code */
2687     OptEntry (OptDeadCode, optMain),
2688     /* Optimize jump targets */
2689     OptEntry (OptJumpTarget, optMain),
2690     /* Optimize conditional branches */
2691     OptEntry (OptCondBranches, optMain),
2692     /* Replace jumps to RTS by RTS */
2693     OptEntry (OptRTSJumps, optMain),
2694     /* Remove calls to the bool transformer subroutines */
2695     OptEntry (OptBoolTransforms, optMain),
2696     /* Optimize compares */
2697     OptEntry (OptCmp1, optMain),
2698     OptEntry (OptCmp2, optMain),
2699     OptEntry (OptCmp3, optMain),
2700     OptEntry (OptCmp4, optMain),
2701     OptEntry (OptCmp5, optMain),
2702     OptEntry (OptCmp6, optMain),
2703     OptEntry (OptCmp7, optMain),
2704     /* Optimize tests */
2705     OptEntry (OptTest1, optMain),
2706     /* Remove unused loads */
2707     OptEntry (OptUnusedLoads, optMain),
2708     OptEntry (OptUnusedStores, optMain),
2709     OptEntry (OptDuplicateLoads, optMain),
2710     OptEntry (OptStoreLoad, optMain),
2711     OptEntry (OptTransfers, optMain),
2712     /* Optimize branch distance */
2713     OptEntry (OptBranchDist, optPost),
2714 };
2715
2716
2717
2718 static OptFunc* FindOptStep (const char* Name)
2719 /* Find an optimizer step by name in the table and return a pointer. Print an
2720  * error and call AbEnd if not found.
2721  */
2722 {
2723     unsigned I;
2724
2725     /* Run all optimization steps */
2726     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2727         if (strcmp (OptFuncs[I].Name, Name) == 0) {
2728             /* Found */
2729             return OptFuncs+I;
2730         }
2731     }
2732
2733     /* Not found */
2734     AbEnd ("Optimization step `%s' not found", Name);
2735     return 0;
2736 }
2737
2738
2739
2740 void DisableOpt (const char* Name)
2741 /* Disable the optimization with the given name */
2742 {
2743     if (strcmp (Name, "any") == 0) {
2744         unsigned I;
2745         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2746             OptFuncs[I].Disabled = 1;
2747         }
2748     } else {
2749         OptFunc* F = FindOptStep (Name);
2750         F->Disabled = 1;
2751     }
2752 }
2753
2754
2755
2756 void EnableOpt (const char* Name)
2757 /* Enable the optimization with the given name */
2758 {
2759     if (strcmp (Name, "any") == 0) {
2760         unsigned I;
2761         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2762             OptFuncs[I].Disabled = 0;
2763         }
2764     } else {
2765         OptFunc* F = FindOptStep (Name);
2766         F->Disabled = 0;
2767     }
2768 }
2769
2770
2771
2772 void ListOptSteps (FILE* F)
2773 /* List all optimization steps */
2774 {
2775     unsigned I;
2776     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2777         fprintf (F, "%s\n", OptFuncs[I].Name);
2778     }
2779 }
2780
2781
2782
2783 static void RepeatOptStep (CodeSeg* S, unsigned char Type, unsigned Max)
2784 /* Repeat the optimizer step of type Type at may Max times */
2785 {
2786     unsigned I;
2787     unsigned Pass = 0;
2788     unsigned OptChanges;
2789
2790     /* Repeat max times of until there are no more changes */
2791     do {
2792         /* Reset the number of changes */
2793         OptChanges = 0;
2794
2795         /* Keep the user hapy */
2796         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
2797
2798         /* Run all optimization steps */
2799         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2800
2801             /* Get the table entry */
2802             const OptFunc* F = OptFuncs + I;
2803
2804             /* Check if the type matches */
2805             if (F->Type != Type) {
2806                 /* Skip it */
2807                 continue;
2808             }
2809
2810             /* Print the name of the following optimizer step */
2811             Print (stdout, 1, "    %s:%*s", F->Name, (int) (30-strlen(F->Name)), "");
2812
2813             /* Check if the step is disabled */
2814             if (F->Disabled) {
2815                 Print (stdout, 1, "Disabled\n");
2816             } else {
2817                 unsigned Changes = F->Func (S);
2818                 OptChanges += Changes;
2819                 Print (stdout, 1, "%u Changes\n", Changes);
2820             }
2821         }
2822
2823     } while (--Max > 0 && OptChanges > 0);
2824 }
2825
2826
2827
2828 void RunOpt (CodeSeg* S)
2829 /* Run the optimizer */
2830 {
2831
2832     /* If we shouldn't run the optimizer, bail out */
2833     if (!Optimize) {
2834         return;
2835     }
2836
2837     /* Print the name of the function we are working on */
2838     if (S->Func) {
2839         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
2840     } else {
2841         Print (stdout, 1, "Running optimizer for global code segment\n");
2842     }
2843
2844     /* Repeat all steps until there are no more changes */
2845     RepeatOptStep (S, optPre, 1);
2846     RepeatOptStep (S, optPreMain, 0xFFFF);
2847     RepeatOptStep (S, optMain, 0xFFFF);
2848     RepeatOptStep (S, optPostMain, 0xFFFF);
2849     RepeatOptStep (S, optPost, 1);
2850 }
2851
2852
2853