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