git.sur5r.net Git - cc65/blob - src/cc65/codeopt.c

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