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