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 <stdlib.h>
  37 #include <string.h>
  38
  39 /* common */
  40 #include "abend.h"
  41 #include "chartype.h"
  42 #include "print.h"
  43 #include "xmalloc.h"
  44 #include "xsprintf.h"
  45
  46 /* cc65 */
  47 #include "asmlabel.h"
  48 #include "codeent.h"
  49 #include "codeinfo.h"
  50 #include "coptadd.h"
  51 #include "coptcmp.h"
  52 #include "coptind.h"
  53 #include "coptstop.h"
  54 #include "coptsub.h"
  55 #include "error.h"
  56 #include "global.h"
  57 #include "codeopt.h"
  58
  59
  60
  61 /*****************************************************************************/
  62 /*                              Optimize shifts                              */
  63 /*****************************************************************************/
  64
  65
  66
  67 static unsigned OptShift1 (CodeSeg* S)
  68 /* A call to the shlaxN routine may get replaced by one or more asl insns
  69  * if the value of X is not used later.
  70  */
  71 {
  72     unsigned Changes = 0;
  73
  74     /* Walk over the entries */
  75     unsigned I = 0;
  76     while (I < CS_GetEntryCount (S)) {
  77
  78         /* Get next entry */
  79         CodeEntry* E = CS_GetEntry (S, I);
  80
  81         /* Check for the sequence */
  82         if (E->OPC == OP65_JSR                       &&
  83             (strncmp (E->Arg, "shlax", 5) == 0 ||
  84              strncmp (E->Arg, "aslax", 5) == 0)      &&
  85             strlen (E->Arg) == 6                     &&
  86             IsDigit (E->Arg[5])                      &&
  87             !RegXUsed (S, I+1)) {
  88
  89             /* Insert shift insns */
  90             unsigned Count = E->Arg[5] - '0';
  91             while (Count--) {
  92                 CodeEntry* X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
  93                 CS_InsertEntry (S, X, I+1);
  94             }
  95
  96             /* Delete the call to shlax */
  97             CS_DelEntry (S, I);
  98
  99             /* Remember, we had changes */
 100             ++Changes;
 101
 102         }
 103
 104         /* Next entry */
 105         ++I;
 106
 107     }
 108
 109     /* Return the number of changes made */
 110     return Changes;
 111 }
 112
 113
 114
 115 /*****************************************************************************/
 116 /*                              Optimize tests                               */
 117 /*****************************************************************************/
 118
 119
 120
 121 static unsigned OptTest1 (CodeSeg* S)
 122 /* On a sequence
 123  *
 124  *     stx     xxx
 125  *     ora     xxx
 126  *     beq/bne ...
 127  *
 128  * if X is zero, the sequence may be changed to
 129  *
 130  *     cmp     #$00
 131  *     beq/bne ...
 132  *
 133  * which may be optimized further by another step.
 134  *
 135  * If A is zero, the sequence may be changed to
 136  *
 137  *     txa
 138  *     beq/bne ...
 139  *
 140  */
 141 {
 142     unsigned Changes = 0;
 143     unsigned I;
 144
 145     /* Generate register info for this step */
 146     CS_GenRegInfo (S);
 147
 148     /* Walk over the entries */
 149     I = 0;
 150     while (I < CS_GetEntryCount (S)) {
 151
 152         CodeEntry* L[3];
 153
 154         /* Get next entry */
 155         L[0] = CS_GetEntry (S, I);
 156
 157         /* Check if it's the sequence we're searching for */
 158         if (L[0]->OPC == OP65_STX              &&
 159             CS_GetEntries (S, L+1, I+1, 2)     &&
 160             !CE_HasLabel (L[1])                &&
 161             L[1]->OPC == OP65_ORA              &&
 162             strcmp (L[0]->Arg, L[1]->Arg) == 0 &&
 163             !CE_HasLabel (L[2])                &&
 164             (L[2]->Info & OF_ZBRA) != 0) {
 165
 166             /* Check if X is zero */
 167             if (L[0]->RI->In.RegX == 0) {
 168
 169                 /* Insert the compare */
 170                 CodeEntry* N = NewCodeEntry (OP65_CMP, AM65_IMM, "$00", 0, L[0]->LI);
 171                 CS_InsertEntry (S, N, I+2);
 172
 173                 /* Remove the two other insns */
 174                 CS_DelEntry (S, I+1);
 175                 CS_DelEntry (S, I);
 176
 177                 /* We had changes */
 178                 ++Changes;
 179
 180             /* Check if A is zero */
 181             } else if (L[1]->RI->In.RegA == 0) {
 182
 183                 /* Insert the txa */
 184                 CodeEntry* N = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, L[1]->LI);
 185                 CS_InsertEntry (S, N, I+2);
 186
 187                 /* Remove the two other insns */
 188                 CS_DelEntry (S, I+1);
 189                 CS_DelEntry (S, I);
 190
 191                 /* We had changes */
 192                 ++Changes;
 193             }
 194         }
 195
 196         /* Next entry */
 197         ++I;
 198
 199     }
 200
 201     /* Free register info */
 202     CS_FreeRegInfo (S);
 203
 204     /* Return the number of changes made */
 205     return Changes;
 206 }
 207
 208
 209
 210 /*****************************************************************************/
 211 /*                            nega optimizations                             */
 212 /*****************************************************************************/
 213
 214
 215
 216 static unsigned OptNegA1 (CodeSeg* S)
 217 /* Check for
 218  *
 219  *      ldx     #$00
 220  *      lda     ..
 221  *      jsr     bnega
 222  *
 223  * Remove the ldx if the lda does not use it.
 224  */
 225 {
 226     unsigned Changes = 0;
 227
 228     /* Walk over the entries */
 229     unsigned I = 0;
 230     while (I < CS_GetEntryCount (S)) {
 231
 232         CodeEntry* L[2];
 233
 234         /* Get next entry */
 235         CodeEntry* E = CS_GetEntry (S, I);
 236
 237         /* Check for a ldx */
 238         if (E->OPC == OP65_LDX                  &&
 239             E->AM == AM65_IMM                   &&
 240             (E->Flags & CEF_NUMARG) != 0        &&
 241             E->Num == 0                         &&
 242             CS_GetEntries (S, L, I+1, 2)        &&
 243             L[0]->OPC == OP65_LDA               &&
 244             (L[0]->Use & REG_X) == 0            &&
 245             !CE_HasLabel (L[0])                 &&
 246             L[1]->OPC == OP65_JSR               &&
 247             strcmp (L[1]->Arg, "bnega") == 0    &&
 248             !CE_HasLabel (L[1])) {
 249
 250             /* Remove the ldx instruction */
 251             CS_DelEntry (S, I);
 252
 253             /* Remember, we had changes */
 254             ++Changes;
 255
 256         }
 257
 258         /* Next entry */
 259         ++I;
 260
 261     }
 262
 263     /* Return the number of changes made */
 264     return Changes;
 265 }
 266
 267
 268
 269 static unsigned OptNegA2 (CodeSeg* S)
 270 /* Check for
 271  *
 272  *      lda     ..
 273  *      jsr     bnega
 274  *      jeq/jne ..
 275  *
 276  * Adjust the conditional branch and remove the call to the subroutine.
 277  */
 278 {
 279     unsigned Changes = 0;
 280
 281     /* Walk over the entries */
 282     unsigned I = 0;
 283     while (I < CS_GetEntryCount (S)) {
 284
 285         CodeEntry* L[2];
 286
 287         /* Get next entry */
 288         CodeEntry* E = CS_GetEntry (S, I);
 289
 290         /* Check for the sequence */
 291         if ((E->OPC == OP65_ADC ||
 292              E->OPC == OP65_AND ||
 293              E->OPC == OP65_DEA ||
 294              E->OPC == OP65_EOR ||
 295              E->OPC == OP65_INA ||
 296              E->OPC == OP65_LDA ||
 297              E->OPC == OP65_ORA ||
 298              E->OPC == OP65_PLA ||
 299              E->OPC == OP65_SBC ||
 300              E->OPC == OP65_TXA ||
 301              E->OPC == OP65_TYA)                &&
 302             CS_GetEntries (S, L, I+1, 2)        &&
 303             L[0]->OPC == OP65_JSR               &&
 304             strcmp (L[0]->Arg, "bnega") == 0    &&
 305             !CE_HasLabel (L[0])                 &&
 306             (L[1]->Info & OF_ZBRA) != 0         &&
 307             !CE_HasLabel (L[1])) {
 308
 309             /* Invert the branch */
 310             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 311
 312             /* Delete the subroutine call */
 313             CS_DelEntry (S, I+1);
 314
 315             /* Remember, we had changes */
 316             ++Changes;
 317
 318         }
 319
 320         /* Next entry */
 321         ++I;
 322
 323     }
 324
 325     /* Return the number of changes made */
 326     return Changes;
 327 }
 328
 329
 330
 331 /*****************************************************************************/
 332 /*                            negax optimizations                            */
 333 /*****************************************************************************/
 334
 335
 336
 337 static unsigned OptNegAX1 (CodeSeg* S)
 338 /* On a call to bnegax, if X is zero, the result depends only on the value in
 339  * A, so change the call to a call to bnega. This will get further optimized
 340  * later if possible.
 341  */
 342 {
 343     unsigned Changes = 0;
 344     unsigned I;
 345
 346     /* Generate register info for this step */
 347     CS_GenRegInfo (S);
 348
 349     /* Walk over the entries */
 350     I = 0;
 351     while (I < CS_GetEntryCount (S)) {
 352
 353         /* Get next entry */
 354         CodeEntry* E = CS_GetEntry (S, I);
 355
 356         /* Check if this is a call to bnegax, and if X is known and zero */
 357         if (E->OPC == OP65_JSR              &&
 358             E->RI->In.RegX == 0             &&
 359             strcmp (E->Arg, "bnegax") == 0) {
 360
 361             /* We're cheating somewhat here ... */
 362             E->Arg[5] = '\0';
 363             E->Use &= ~REG_X;
 364
 365             /* We had changes */
 366             ++Changes;
 367         }
 368
 369         /* Next entry */
 370         ++I;
 371
 372     }
 373
 374     /* Free register info */
 375     CS_FreeRegInfo (S);
 376
 377     /* Return the number of changes made */
 378     return Changes;
 379 }
 380
 381
 382
 383 static unsigned OptNegAX2 (CodeSeg* S)
 384 /* Search for the sequence:
 385  *
 386  *      lda     (xx),y
 387  *      tax
 388  *      dey
 389  *      lda     (xx),y
 390  *      jsr     bnegax
 391  *      jne/jeq ...
 392  *
 393  * and replace it by
 394  *
 395  *      lda     (xx),y
 396  *      dey
 397  *      ora     (xx),y
 398  *      jeq/jne ...
 399  */
 400 {
 401     unsigned Changes = 0;
 402
 403     /* Walk over the entries */
 404     unsigned I = 0;
 405     while (I < CS_GetEntryCount (S)) {
 406
 407         CodeEntry* L[5];
 408
 409         /* Get next entry */
 410         CodeEntry* E = CS_GetEntry (S, I);
 411
 412         /* Check for the sequence */
 413         if (E->OPC == OP65_LDA                  &&
 414             E->AM == AM65_ZP_INDY               &&
 415             CS_GetEntries (S, L, I+1, 5)        &&
 416             L[0]->OPC == OP65_TAX               &&
 417             L[1]->OPC == OP65_DEY               &&
 418             L[2]->OPC == OP65_LDA               &&
 419             L[2]->AM == AM65_ZP_INDY            &&
 420             strcmp (L[2]->Arg, E->Arg) == 0     &&
 421             !CE_HasLabel (L[2])                 &&
 422             L[3]->OPC == OP65_JSR               &&
 423             strcmp (L[3]->Arg, "bnegax") == 0   &&
 424             !CE_HasLabel (L[3])                 &&
 425             (L[4]->Info & OF_ZBRA) != 0         &&
 426             !CE_HasLabel (L[4])) {
 427
 428             /* lda --> ora */
 429             CE_ReplaceOPC (L[2], OP65_ORA);
 430
 431             /* Invert the branch */
 432             CE_ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
 433
 434             /* Delete the entries no longer needed. Beware: Deleting entries
 435              * will change the indices.
 436              */
 437             CS_DelEntry (S, I+4);               /* jsr bnegax */
 438             CS_DelEntry (S, I+1);               /* tax */
 439
 440             /* Remember, we had changes */
 441             ++Changes;
 442
 443         }
 444
 445         /* Next entry */
 446         ++I;
 447
 448     }
 449
 450     /* Return the number of changes made */
 451     return Changes;
 452 }
 453
 454
 455
 456 static unsigned OptNegAX3 (CodeSeg* S)
 457 /* Search for the sequence:
 458  *
 459  *      lda     xx
 460  *      ldx     yy
 461  *      jsr     bnegax
 462  *      jne/jeq ...
 463  *
 464  * and replace it by
 465  *
 466  *      lda     xx
 467  *      ora     xx+1
 468  *      jeq/jne ...
 469  */
 470 {
 471     unsigned Changes = 0;
 472
 473     /* Walk over the entries */
 474     unsigned I = 0;
 475     while (I < CS_GetEntryCount (S)) {
 476
 477         CodeEntry* L[3];
 478
 479         /* Get next entry */
 480         CodeEntry* E = CS_GetEntry (S, I);
 481
 482         /* Check for the sequence */
 483         if (E->OPC == OP65_LDA                  &&
 484             CS_GetEntries (S, L, I+1, 3)        &&
 485             L[0]->OPC == OP65_LDX               &&
 486             !CE_HasLabel (L[0])                 &&
 487             L[1]->OPC == OP65_JSR               &&
 488             strcmp (L[1]->Arg, "bnegax") == 0   &&
 489             !CE_HasLabel (L[1])                 &&
 490             (L[2]->Info & OF_ZBRA) != 0         &&
 491             !CE_HasLabel (L[2])) {
 492
 493             /* ldx --> ora */
 494             CE_ReplaceOPC (L[0], OP65_ORA);
 495
 496             /* Invert the branch */
 497             CE_ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
 498
 499             /* Delete the subroutine call */
 500             CS_DelEntry (S, I+2);
 501
 502             /* Remember, we had changes */
 503             ++Changes;
 504
 505         }
 506
 507         /* Next entry */
 508         ++I;
 509
 510     }
 511
 512     /* Return the number of changes made */
 513     return Changes;
 514 }
 515
 516
 517
 518 static unsigned OptNegAX4 (CodeSeg* S)
 519 /* Search for the sequence:
 520  *
 521  *      jsr     xxx
 522  *      jsr     bnega(x)
 523  *      jeq/jne ...
 524  *
 525  * and replace it by:
 526  *
 527  *      jsr     xxx
 528  *      <boolean test>
 529  *      jne/jeq ...
 530  */
 531 {
 532     unsigned Changes = 0;
 533
 534     /* Walk over the entries */
 535     unsigned I = 0;
 536     while (I < CS_GetEntryCount (S)) {
 537
 538         CodeEntry* L[2];
 539
 540         /* Get next entry */
 541         CodeEntry* E = CS_GetEntry (S, I);
 542
 543         /* Check for the sequence */
 544         if (E->OPC == OP65_JSR                  &&
 545             CS_GetEntries (S, L, I+1, 2)        &&
 546             L[0]->OPC == OP65_JSR               &&
 547             strncmp (L[0]->Arg,"bnega",5) == 0  &&
 548             !CE_HasLabel (L[0])                 &&
 549             (L[1]->Info & OF_ZBRA) != 0         &&
 550             !CE_HasLabel (L[1])) {
 551
 552             CodeEntry* X;
 553
 554             /* Check if we're calling bnega or bnegax */
 555             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
 556
 557             /* Insert apropriate test code */
 558             if (ByteSized) {
 559                 /* Test bytes */
 560                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
 561                 CS_InsertEntry (S, X, I+2);
 562             } else {
 563                 /* Test words */
 564                 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
 565                 CS_InsertEntry (S, X, I+2);
 566                 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
 567                 CS_InsertEntry (S, X, I+3);
 568             }
 569
 570             /* Delete the subroutine call */
 571             CS_DelEntry (S, I+1);
 572
 573             /* Invert the branch */
 574             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
 575
 576             /* Remember, we had changes */
 577             ++Changes;
 578
 579         }
 580
 581         /* Next entry */
 582         ++I;
 583
 584     }
 585
 586     /* Return the number of changes made */
 587     return Changes;
 588 }
 589
 590
 591
 592 /*****************************************************************************/
 593 /*                     Optimize stores through pointers                      */
 594 /*****************************************************************************/
 595
 596
 597
 598 static unsigned OptPtrStore1Sub (CodeSeg* S, unsigned I, CodeEntry** const L)
 599 /* Check if this is one of the allowed suboperation for OptPtrStore1 */
 600 {
 601     /* Check for a label attached to the entry */
 602     if (CE_HasLabel (L[0])) {
 603         return 0;
 604     }
 605
 606     /* Check for single insn sub ops */
 607     if (L[0]->OPC == OP65_AND                                           ||
 608         L[0]->OPC == OP65_EOR                                           ||
 609         L[0]->OPC == OP65_ORA                                           ||
 610         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shlax", 5) == 0) ||
 611         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shrax", 5) == 0)) {
 612
 613         /* One insn */
 614         return 1;
 615
 616     } else if (L[0]->OPC == OP65_CLC                      &&
 617                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
 618                L[1]->OPC == OP65_ADC                      &&
 619                !CE_HasLabel (L[1])) {
 620         return 2;
 621     } else if (L[0]->OPC == OP65_SEC                      &&
 622                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
 623                L[1]->OPC == OP65_SBC                      &&
 624                !CE_HasLabel (L[1])) {
 625         return 2;
 626     }
 627
 628
 629
 630     /* Not found */
 631     return 0;
 632 }
 633
 634
 635
 636 static unsigned OptPtrStore1 (CodeSeg* S)
 637 /* Search for the sequence:
 638  *
 639  *      jsr     pushax
 640  *      ldy     xxx
 641  *      jsr     ldauidx
 642  *      subop
 643  *      ldy     yyy
 644  *      jsr     staspidx
 645  *
 646  * and replace it by:
 647  *
 648  *      sta     ptr1
 649  *      stx     ptr1+1
 650  *      ldy     xxx
 651  *      ldx     #$00
 652  *      lda     (ptr1),y
 653  *      subop
 654  *      ldy     yyy
 655  *      sta     (ptr1),y
 656  */
 657 {
 658     unsigned Changes = 0;
 659
 660     /* Walk over the entries */
 661     unsigned I = 0;
 662     while (I < CS_GetEntryCount (S)) {
 663
 664         unsigned K;
 665         CodeEntry* L[10];
 666
 667         /* Get next entry */
 668         L[0] = CS_GetEntry (S, I);
 669
 670         /* Check for the sequence */
 671         if (L[0]->OPC == OP65_JSR                   &&
 672             strcmp (L[0]->Arg, "pushax") == 0       &&
 673             CS_GetEntries (S, L+1, I+1, 3)          &&
 674             L[1]->OPC == OP65_LDY                   &&
 675             CE_KnownImm (L[1])                      &&
 676             !CE_HasLabel (L[1])                     &&
 677             L[2]->OPC == OP65_JSR                   &&
 678             strcmp (L[2]->Arg, "ldauidx") == 0      &&
 679             !CE_HasLabel (L[2])                     &&
 680             (K = OptPtrStore1Sub (S, I+3, L+3)) > 0 &&
 681             CS_GetEntries (S, L+3+K, I+3+K, 2)      &&
 682             L[3+K]->OPC == OP65_LDY                 &&
 683             CE_KnownImm (L[3+K])                    &&
 684             !CE_HasLabel (L[3+K])                   &&
 685             L[4+K]->OPC == OP65_JSR                 &&
 686             strcmp (L[4+K]->Arg, "staspidx") == 0   &&
 687             !CE_HasLabel (L[4+K])) {
 688
 689             CodeEntry* X;
 690
 691             /* Create and insert the stores */
 692             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
 693             CS_InsertEntry (S, X, I+1);
 694
 695             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
 696             CS_InsertEntry (S, X, I+2);
 697
 698             /* Delete the call to pushax */
 699             CS_DelEntry (S, I);
 700
 701             /* Delete the call to ldauidx */
 702             CS_DelEntry (S, I+3);
 703
 704             /* Insert the load from ptr1 */
 705             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
 706             CS_InsertEntry (S, X, I+3);
 707             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[2]->LI);
 708             CS_InsertEntry (S, X, I+4);
 709
 710             /* Insert the store through ptr1 */
 711             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
 712             CS_InsertEntry (S, X, I+6+K);
 713
 714             /* Delete the call to staspidx */
 715             CS_DelEntry (S, I+7+K);
 716
 717             /* Remember, we had changes */
 718             ++Changes;
 719
 720         }
 721
 722         /* Next entry */
 723         ++I;
 724
 725     }
 726
 727     /* Return the number of changes made */
 728     return Changes;
 729 }
 730
 731
 732
 733 static unsigned OptPtrStore2 (CodeSeg* S)
 734 /* Search for the sequence:
 735  *
 736  *      jsr     pushax
 737  *      lda     xxx
 738  *      ldy     yyy
 739  *      jsr     staspidx
 740  *
 741  * and replace it by:
 742  *
 743  *      sta     ptr1
 744  *      stx     ptr1+1
 745  *      lda     xxx
 746  *      ldy     yyy
 747  *      sta     (ptr1),y
 748  */
 749 {
 750     unsigned Changes = 0;
 751
 752     /* Walk over the entries */
 753     unsigned I = 0;
 754     while (I < CS_GetEntryCount (S)) {
 755
 756         CodeEntry* L[4];
 757
 758         /* Get next entry */
 759         L[0] = CS_GetEntry (S, I);
 760
 761         /* Check for the sequence */
 762         if (L[0]->OPC == OP65_JSR               &&
 763             strcmp (L[0]->Arg, "pushax") == 0   &&
 764             CS_GetEntries (S, L+1, I+1, 3)      &&
 765             L[1]->OPC == OP65_LDA               &&
 766             !CE_HasLabel (L[1])                 &&
 767             L[2]->OPC == OP65_LDY               &&
 768             !CE_HasLabel (L[2])                 &&
 769             L[3]->OPC == OP65_JSR               &&
 770             strcmp (L[3]->Arg, "staspidx") == 0 &&
 771             !CE_HasLabel (L[3])) {
 772
 773             CodeEntry* X;
 774
 775             /* Create and insert the stores */
 776             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
 777             CS_InsertEntry (S, X, I+1);
 778
 779             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
 780             CS_InsertEntry (S, X, I+2);
 781
 782             /* Delete the call to pushax */
 783             CS_DelEntry (S, I);
 784
 785             /* Insert the store through ptr1 */
 786             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
 787             CS_InsertEntry (S, X, I+4);
 788
 789             /* Delete the call to staspidx */
 790             CS_DelEntry (S, I+5);
 791
 792             /* Remember, we had changes */
 793             ++Changes;
 794
 795         }
 796
 797         /* Next entry */
 798         ++I;
 799
 800     }
 801
 802     /* Return the number of changes made */
 803     return Changes;
 804 }
 805
 806
 807
 808 /*****************************************************************************/
 809 /*                      Optimize loads through pointers                      */
 810 /*****************************************************************************/
 811
 812
 813
 814 static unsigned OptPtrLoad1 (CodeSeg* S)
 815 /* Search for the sequence:
 816  *
 817  *      tax
 818  *      dey
 819  *      lda     (sp),y             # May be any destination
 820  *      ldy     ...
 821  *      jsr     ldauidx
 822  *
 823  * and replace it by:
 824  *
 825  *      sta     ptr1+1
 826  *      dey
 827  *      lda     (sp),y
 828  *      sta     ptr1
 829  *      ldy     ...
 830  *      ldx     #$00
 831  *      lda     (ptr1),y
 832  */
 833 {
 834     unsigned Changes = 0;
 835
 836     /* Walk over the entries */
 837     unsigned I = 0;
 838     while (I < CS_GetEntryCount (S)) {
 839
 840         CodeEntry* L[5];
 841
 842         /* Get next entry */
 843         L[0] = CS_GetEntry (S, I);
 844
 845         /* Check for the sequence */
 846         if (L[0]->OPC == OP65_TAX               &&
 847             CS_GetEntries (S, L+1, I+1, 4)      &&
 848             L[1]->OPC == OP65_DEY               &&
 849             !CE_HasLabel (L[1])                 &&
 850             L[2]->OPC == OP65_LDA               &&
 851             !CE_HasLabel (L[2])                 &&
 852             L[3]->OPC == OP65_LDY               &&
 853             !CE_HasLabel (L[3])                 &&
 854             L[4]->OPC == OP65_JSR               &&
 855             strcmp (L[4]->Arg, "ldauidx") == 0  &&
 856             !CE_HasLabel (L[4])) {
 857
 858             CodeEntry* X;
 859
 860             /* Store the high byte and remove the TAX instead */
 861             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[0]->LI);
 862             CS_InsertEntry (S, X, I+1);
 863             CS_DelEntry (S, I);
 864
 865             /* Store the low byte */
 866             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[2]->LI);
 867             CS_InsertEntry (S, X, I+3);
 868
 869             /* Delete the call to ldauidx */
 870             CS_DelEntry (S, I+5);
 871
 872             /* Load high and low byte */
 873             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
 874             CS_InsertEntry (S, X, I+5);
 875             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
 876             CS_InsertEntry (S, X, I+6);
 877
 878             /* Remember, we had changes */
 879             ++Changes;
 880
 881         }
 882
 883         /* Next entry */
 884         ++I;
 885
 886     }
 887
 888     /* Return the number of changes made */
 889     return Changes;
 890 }
 891
 892
 893
 894 static unsigned OptPtrLoad2 (CodeSeg* S)
 895 /* Search for the sequence:
 896  *
 897  *      adc     xxx
 898  *      tay
 899  *      txa
 900  *      adc     yyy
 901  *      tax
 902  *      tya
 903  *      ldy
 904  *      jsr     ldauidx
 905  *
 906  * and replace it by:
 907  *
 908  *      adc     xxx
 909  *      sta     ptr1
 910  *      txa
 911  *      adc     yyy
 912  *      sta     ptr1+1
 913  *      ldy
 914  *      ldx     #$00
 915  *      lda     (ptr1),y
 916  */
 917 {
 918     unsigned Changes = 0;
 919
 920     /* Walk over the entries */
 921     unsigned I = 0;
 922     while (I < CS_GetEntryCount (S)) {
 923
 924         CodeEntry* L[8];
 925
 926         /* Get next entry */
 927         L[0] = CS_GetEntry (S, I);
 928
 929         /* Check for the sequence */
 930         if (L[0]->OPC == OP65_ADC               &&
 931             CS_GetEntries (S, L+1, I+1, 7)      &&
 932             L[1]->OPC == OP65_TAY               &&
 933             !CE_HasLabel (L[1])                 &&
 934             L[2]->OPC == OP65_TXA               &&
 935             !CE_HasLabel (L[2])                 &&
 936             L[3]->OPC == OP65_ADC               &&
 937             !CE_HasLabel (L[3])                 &&
 938             L[4]->OPC == OP65_TAX               &&
 939             !CE_HasLabel (L[4])                 &&
 940             L[5]->OPC == OP65_TYA               &&
 941             !CE_HasLabel (L[5])                 &&
 942             L[6]->OPC == OP65_LDY               &&
 943             !CE_HasLabel (L[6])                 &&
 944             L[7]->OPC == OP65_JSR               &&
 945             strcmp (L[7]->Arg, "ldauidx") == 0  &&
 946             !CE_HasLabel (L[7])) {
 947
 948             CodeEntry* X;
 949
 950             /* Store the low byte and remove the TAY instead */
 951             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
 952             CS_InsertEntry (S, X, I+1);
 953             CS_DelEntry (S, I+2);
 954
 955             /* Store the high byte */
 956             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[3]->LI);
 957             CS_InsertEntry (S, X, I+4);
 958
 959             /* Delete more transfer insns */
 960             CS_DelEntry (S, I+6);
 961             CS_DelEntry (S, I+5);
 962
 963             /* Delete the call to ldauidx */
 964             CS_DelEntry (S, I+6);
 965
 966             /* Load high and low byte */
 967             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
 968             CS_InsertEntry (S, X, I+6);
 969             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
 970             CS_InsertEntry (S, X, I+7);
 971
 972             /* Remember, we had changes */
 973             ++Changes;
 974
 975         }
 976
 977         /* Next entry */
 978         ++I;
 979
 980     }
 981
 982     /* Return the number of changes made */
 983     return Changes;
 984 }
 985
 986
 987
 988 static unsigned OptPtrLoad3 (CodeSeg* S)
 989 /* Search for the sequence:
 990  *
 991  *      adc     xxx
 992  *      pha
 993  *      txa
 994  *      iny
 995  *      adc     yyy
 996  *      tax
 997  *      pla
 998  *      ldy
 999  *      jsr     ldauidx
1000  *
1001  * and replace it by:
1002  *
1003  *      adc     xxx
1004  *      sta     ptr1
1005  *      txa
1006  *      iny
1007  *      adc     yyy
1008  *      sta     ptr1+1
1009  *      ldy
1010  *      ldx     #$00
1011  *      lda     (ptr1),y
1012  */
1013 {
1014     unsigned Changes = 0;
1015
1016     /* Walk over the entries */
1017     unsigned I = 0;
1018     while (I < CS_GetEntryCount (S)) {
1019
1020         CodeEntry* L[9];
1021
1022         /* Get next entry */
1023         L[0] = CS_GetEntry (S, I);
1024
1025         /* Check for the sequence */
1026         if (L[0]->OPC == OP65_ADC               &&
1027             CS_GetEntries (S, L+1, I+1, 8)      &&
1028             L[1]->OPC == OP65_PHA               &&
1029             !CE_HasLabel (L[1])                 &&
1030             L[2]->OPC == OP65_TXA               &&
1031             !CE_HasLabel (L[2])                 &&
1032             L[3]->OPC == OP65_INY               &&
1033             !CE_HasLabel (L[3])                 &&
1034             L[4]->OPC == OP65_ADC               &&
1035             !CE_HasLabel (L[4])                 &&
1036             L[5]->OPC == OP65_TAX               &&
1037             !CE_HasLabel (L[5])                 &&
1038             L[6]->OPC == OP65_PLA               &&
1039             !CE_HasLabel (L[6])                 &&
1040             L[7]->OPC == OP65_LDY               &&
1041             !CE_HasLabel (L[7])                 &&
1042             L[8]->OPC == OP65_JSR               &&
1043             strcmp (L[8]->Arg, "ldauidx") == 0  &&
1044             !CE_HasLabel (L[8])) {
1045
1046             CodeEntry* X;
1047
1048             /* Store the low byte and remove the PHA instead */
1049             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1050             CS_InsertEntry (S, X, I+1);
1051             CS_DelEntry (S, I+2);
1052
1053             /* Store the high byte */
1054             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[4]->LI);
1055             CS_InsertEntry (S, X, I+5);
1056
1057             /* Delete more transfer and PLA insns */
1058             CS_DelEntry (S, I+7);
1059             CS_DelEntry (S, I+6);
1060
1061             /* Delete the call to ldauidx */
1062             CS_DelEntry (S, I+7);
1063
1064             /* Load high and low byte */
1065             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
1066             CS_InsertEntry (S, X, I+7);
1067             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
1068             CS_InsertEntry (S, X, I+8);
1069
1070             /* Remember, we had changes */
1071             ++Changes;
1072
1073         }
1074
1075         /* Next entry */
1076         ++I;
1077
1078     }
1079
1080     /* Return the number of changes made */
1081     return Changes;
1082 }
1083
1084
1085
1086 static unsigned OptPtrLoad4 (CodeSeg* S)
1087 /* Search for the sequence:
1088  *
1089  *      lda     #<(label+0)
1090  *      ldx     #>(label+0)
1091  *      clc
1092  *      adc     xxx
1093  *      bcc     L
1094  *      inx
1095  * L:   ldy     #$00
1096  *      jsr     ldauidx
1097  *
1098  * and replace it by:
1099  *
1100  *      ldy     xxx
1101  *      ldx     #$00
1102  *      lda     label,y
1103  */
1104 {
1105     unsigned Changes = 0;
1106
1107     /* Walk over the entries */
1108     unsigned I = 0;
1109     while (I < CS_GetEntryCount (S)) {
1110
1111         CodeEntry* L[8];
1112         unsigned Len;
1113
1114         /* Get next entry */
1115         L[0] = CS_GetEntry (S, I);
1116
1117         /* Check for the sequence */
1118         if (L[0]->OPC == OP65_LDA                            &&
1119             L[0]->AM == AM65_IMM                             &&
1120             CS_GetEntries (S, L+1, I+1, 7)                   &&
1121             L[1]->OPC == OP65_LDX                            &&
1122             L[1]->AM == AM65_IMM                             &&
1123             !CE_HasLabel (L[1])                              &&
1124             L[2]->OPC == OP65_CLC                            &&
1125             !CE_HasLabel (L[2])                              &&
1126             L[3]->OPC == OP65_ADC                            &&
1127             (L[3]->AM == AM65_ABS || L[3]->AM == AM65_ZP)    &&
1128             !CE_HasLabel (L[3])                              &&
1129             (L[4]->OPC == OP65_BCC || L[4]->OPC == OP65_JCC) &&
1130             L[4]->JumpTo != 0                                &&
1131             L[4]->JumpTo->Owner == L[6]                      &&
1132             !CE_HasLabel (L[4])                              &&
1133             L[5]->OPC == OP65_INX                            &&
1134             !CE_HasLabel (L[5])                              &&
1135             L[6]->OPC == OP65_LDY                            &&
1136             CE_KnownImm (L[6])                               &&
1137             L[6]->Num == 0                                   &&
1138             L[7]->OPC == OP65_JSR                            &&
1139             strcmp (L[7]->Arg, "ldauidx") == 0               &&
1140             !CE_HasLabel (L[7])                              &&
1141             /* Check the label last because this is quite costly */
1142             (Len = strlen (L[0]->Arg)) > 3                   &&
1143             L[0]->Arg[0] == '<'                              &&
1144             L[0]->Arg[1] == '('                              &&
1145             strlen (L[1]->Arg) == Len                        &&
1146             L[1]->Arg[0] == '>'                              &&
1147             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
1148
1149             CodeEntry* X;
1150             char* Label;
1151
1152             /* We will create all the new stuff behind the current one so
1153              * we keep the line references.
1154              */
1155             X = NewCodeEntry (OP65_LDY, L[3]->AM, L[3]->Arg, 0, L[0]->LI);
1156             CS_InsertEntry (S, X, I+8);
1157
1158             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1159             CS_InsertEntry (S, X, I+9);
1160
1161             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
1162             Label[Len-3] = '\0';
1163             X = NewCodeEntry (OP65_LDA, AM65_ABSY, Label, 0, L[0]->LI);
1164             CS_InsertEntry (S, X, I+10);
1165             xfree (Label);
1166
1167             /* Remove the old code */
1168             CS_DelEntries (S, I, 8);
1169
1170             /* Remember, we had changes */
1171             ++Changes;
1172
1173         }
1174
1175         /* Next entry */
1176         ++I;
1177
1178     }
1179
1180     /* Return the number of changes made */
1181     return Changes;
1182 }
1183
1184
1185
1186 static unsigned OptPtrLoad5 (CodeSeg* S)
1187 /* Search for the sequence:
1188  *
1189  *      lda     #<(label+0)
1190  *      ldx     #>(label+0)
1191  *      ldy     #$xx
1192  *      clc
1193  *      adc     (sp),y
1194  *      bcc     L
1195  *      inx
1196  * L:   ldy     #$00
1197  *      jsr     ldauidx
1198  *
1199  * and replace it by:
1200  *
1201  *      ldy     #$xx
1202  *      lda     (sp),y
1203  *      tay
1204  *      ldx     #$00
1205  *      lda     label,y
1206  */
1207 {
1208     unsigned Changes = 0;
1209
1210     /* Walk over the entries */
1211     unsigned I = 0;
1212     while (I < CS_GetEntryCount (S)) {
1213
1214         CodeEntry* L[9];
1215         unsigned Len;
1216
1217         /* Get next entry */
1218         L[0] = CS_GetEntry (S, I);
1219
1220         /* Check for the sequence */
1221         if (L[0]->OPC == OP65_LDA                            &&
1222             L[0]->AM == AM65_IMM                             &&
1223             CS_GetEntries (S, L+1, I+1, 8)                   &&
1224             L[1]->OPC == OP65_LDX                            &&
1225             L[1]->AM == AM65_IMM                             &&
1226             !CE_HasLabel (L[1])                              &&
1227             L[2]->OPC == OP65_LDY                            &&
1228             CE_KnownImm (L[2])                               &&
1229             !CE_HasLabel (L[2])                              &&
1230             L[3]->OPC == OP65_CLC                            &&
1231             !CE_HasLabel (L[3])                              &&
1232             L[4]->OPC == OP65_ADC                            &&
1233             L[4]->AM == AM65_ZP_INDY                         &&
1234             !CE_HasLabel (L[4])                              &&
1235             (L[5]->OPC == OP65_BCC || L[5]->OPC == OP65_JCC) &&
1236             L[5]->JumpTo != 0                                &&
1237             L[5]->JumpTo->Owner == L[7]                      &&
1238             !CE_HasLabel (L[5])                              &&
1239             L[6]->OPC == OP65_INX                            &&
1240             !CE_HasLabel (L[6])                              &&
1241             L[7]->OPC == OP65_LDY                            &&
1242             CE_KnownImm (L[7])                               &&
1243             L[7]->Num == 0                                   &&
1244             L[8]->OPC == OP65_JSR                            &&
1245             strcmp (L[8]->Arg, "ldauidx") == 0               &&
1246             !CE_HasLabel (L[8])                              &&
1247             /* Check the label last because this is quite costly */
1248             (Len = strlen (L[0]->Arg)) > 3                   &&
1249             L[0]->Arg[0] == '<'                              &&
1250             L[0]->Arg[1] == '('                              &&
1251             strlen (L[1]->Arg) == Len                        &&
1252             L[1]->Arg[0] == '>'                              &&
1253             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
1254
1255             CodeEntry* X;
1256             char* Label;
1257
1258             /* Add the lda */
1259             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, L[4]->Arg, 0, L[0]->LI);
1260             CS_InsertEntry (S, X, I+3);
1261
1262             /* Add the tay */
1263             X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, L[0]->LI);
1264             CS_InsertEntry (S, X, I+4);
1265
1266             /* Add the ldx */
1267             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1268             CS_InsertEntry (S, X, I+5);
1269
1270             /* Add the lda */
1271             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
1272             Label[Len-3] = '\0';
1273             X = NewCodeEntry (OP65_LDA, AM65_ABSY, Label, 0, L[0]->LI);
1274             CS_InsertEntry (S, X, I+6);
1275             xfree (Label);
1276
1277             /* Remove the old code */
1278             CS_DelEntries (S, I, 2);
1279             CS_DelEntries (S, I+5, 6);
1280
1281             /* Remember, we had changes */
1282             ++Changes;
1283
1284         }
1285
1286         /* Next entry */
1287         ++I;
1288
1289     }
1290
1291     /* Return the number of changes made */
1292     return Changes;
1293 }
1294
1295
1296
1297 static unsigned OptPtrLoad6 (CodeSeg* S)
1298 /* Search for the sequence
1299  *
1300  *      ldy     ...
1301  *      jsr     ldauidx
1302  *
1303  * and replace it by:
1304  *
1305  *      ldy     ...
1306  *      stx     ptr1+1
1307  *      sta     ptr1
1308  *      ldx     #$00
1309  *      lda     (ptr1),y
1310  *
1311  * This step must be execute *after* OptPtrLoad1!
1312  */
1313 {
1314     unsigned Changes = 0;
1315
1316     /* Walk over the entries */
1317     unsigned I = 0;
1318     while (I < CS_GetEntryCount (S)) {
1319
1320         CodeEntry* L[2];
1321
1322         /* Get next entry */
1323         L[0] = CS_GetEntry (S, I);
1324
1325         /* Check for the sequence */
1326         if (L[0]->OPC == OP65_LDY               &&
1327             CS_GetEntries (S, L+1, I+1, 1)      &&
1328             L[1]->OPC == OP65_JSR               &&
1329             strcmp (L[1]->Arg, "ldauidx") == 0  &&
1330             !CE_HasLabel (L[1])) {
1331
1332             CodeEntry* X;
1333
1334             /* Store the high byte */
1335             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1336             CS_InsertEntry (S, X, I+1);
1337
1338             /* Store the low byte */
1339             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1340             CS_InsertEntry (S, X, I+2);
1341
1342             /* Delete the call to ldauidx */
1343             CS_DelEntry (S, I+3);
1344
1345             /* Load the high and low byte */
1346             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1347             CS_InsertEntry (S, X, I+3);
1348             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
1349             CS_InsertEntry (S, X, I+4);
1350
1351             /* Remember, we had changes */
1352             ++Changes;
1353
1354         }
1355
1356         /* Next entry */
1357         ++I;
1358
1359     }
1360
1361     /* Return the number of changes made */
1362     return Changes;
1363 }
1364
1365
1366
1367 /*****************************************************************************/
1368 /*                              struct OptFunc                               */
1369 /*****************************************************************************/
1370
1371
1372
1373 typedef struct OptFunc OptFunc;
1374 struct OptFunc {
1375     unsigned       (*Func) (CodeSeg*);  /* Optimizer function */
1376     const char*    Name;                /* Name of the function/group */
1377     unsigned long  TotalRuns;           /* Total number of runs */
1378     unsigned long  LastRuns;            /* Last number of runs */
1379     unsigned long  TotalChanges;        /* Total number of changes */
1380     unsigned long  LastChanges;         /* Last number of changes */
1381     char           Disabled;            /* True if function disabled */
1382 };
1383
1384
1385
1386 /*****************************************************************************/
1387 /*                                   Code                                    */
1388 /*****************************************************************************/
1389
1390
1391
1392 /* Macro that builds a function description */
1393 #define OptFuncEntry(func) static OptFuncDesc D##func = { func, #func, 0 }
1394
1395 /* A list of all the function descriptions */
1396 static OptFunc DOptPtrStore1    = { OptPtrStore1,    "OptPtrStore1",    0, 0, 0, 0, 0 };
1397 static OptFunc DOptPtrStore2    = { OptPtrStore2,    "OptPtrStore2",    0, 0, 0, 0, 0 };
1398 static OptFunc DOptPtrLoad1     = { OptPtrLoad1,     "OptPtrLoad1",     0, 0, 0, 0, 0 };
1399 static OptFunc DOptPtrLoad2     = { OptPtrLoad2,     "OptPtrLoad2",     0, 0, 0, 0, 0 };
1400 static OptFunc DOptPtrLoad3     = { OptPtrLoad3,     "OptPtrLoad3",     0, 0, 0, 0, 0 };
1401 static OptFunc DOptPtrLoad4     = { OptPtrLoad4,     "OptPtrLoad4",     0, 0, 0, 0, 0 };
1402 static OptFunc DOptPtrLoad5     = { OptPtrLoad5,     "OptPtrLoad5",     0, 0, 0, 0, 0 };
1403 static OptFunc DOptPtrLoad6     = { OptPtrLoad6,     "OptPtrLoad6",     0, 0, 0, 0, 0 };
1404 static OptFunc DOptNegA1        = { OptNegA1,        "OptNegA1",        0, 0, 0, 0, 0 };
1405 static OptFunc DOptNegA2        = { OptNegA2,        "OptNegA2",        0, 0, 0, 0, 0 };
1406 static OptFunc DOptNegAX1       = { OptNegAX1,       "OptNegAX1",       0, 0, 0, 0, 0 };
1407 static OptFunc DOptNegAX2       = { OptNegAX2,       "OptNegAX2",       0, 0, 0, 0, 0 };
1408 static OptFunc DOptNegAX3       = { OptNegAX3,       "OptNegAX3",       0, 0, 0, 0, 0 };
1409 static OptFunc DOptNegAX4       = { OptNegAX4,       "OptNegAX4",       0, 0, 0, 0, 0 };
1410 static OptFunc DOptSub1         = { OptSub1,         "OptSub1",         0, 0, 0, 0, 0 };
1411 static OptFunc DOptSub2         = { OptSub2,         "OptSub2",         0, 0, 0, 0, 0 };
1412 static OptFunc DOptAdd1         = { OptAdd1,         "OptAdd1",         0, 0, 0, 0, 0 };
1413 static OptFunc DOptAdd2         = { OptAdd2,         "OptAdd2",         0, 0, 0, 0, 0 };
1414 static OptFunc DOptAdd3         = { OptAdd3,         "OptAdd3",         0, 0, 0, 0, 0 };
1415 static OptFunc DOptShift1       = { OptShift1,       "OptShift1",       0, 0, 0, 0, 0 };
1416 static OptFunc DOptJumpCascades = { OptJumpCascades, "OptJumpCascades", 0, 0, 0, 0, 0 };
1417 static OptFunc DOptDeadJumps    = { OptDeadJumps,    "OptDeadJumps",    0, 0, 0, 0, 0 };
1418 static OptFunc DOptRTS          = { OptRTS,          "OptRTS",          0, 0, 0, 0, 0 };
1419 static OptFunc DOptDeadCode     = { OptDeadCode,     "OptDeadCode",     0, 0, 0, 0, 0 };
1420 static OptFunc DOptJumpTarget   = { OptJumpTarget,   "OptJumpTarget",   0, 0, 0, 0, 0 };
1421 static OptFunc DOptCondBranches = { OptCondBranches, "OptCondBranches", 0, 0, 0, 0, 0 };
1422 static OptFunc DOptRTSJumps     = { OptRTSJumps,     "OptRTSJumps",     0, 0, 0, 0, 0 };
1423 static OptFunc DOptBoolTrans    = { OptBoolTrans,    "OptBoolTrans",    0, 0, 0, 0, 0 };
1424 static OptFunc DOptCmp1         = { OptCmp1,         "OptCmp1",         0, 0, 0, 0, 0 };
1425 static OptFunc DOptCmp2         = { OptCmp2,         "OptCmp2",         0, 0, 0, 0, 0 };
1426 static OptFunc DOptCmp3         = { OptCmp3,         "OptCmp3",         0, 0, 0, 0, 0 };
1427 static OptFunc DOptCmp4         = { OptCmp4,         "OptCmp4",         0, 0, 0, 0, 0 };
1428 static OptFunc DOptCmp5         = { OptCmp5,         "OptCmp5",         0, 0, 0, 0, 0 };
1429 static OptFunc DOptCmp6         = { OptCmp6,         "OptCmp6",         0, 0, 0, 0, 0 };
1430 static OptFunc DOptCmp7         = { OptCmp7,         "OptCmp7",         0, 0, 0, 0, 0 };
1431 static OptFunc DOptTest1        = { OptTest1,        "OptTest1",        0, 0, 0, 0, 0 };
1432 static OptFunc DOptUnusedLoads  = { OptUnusedLoads,  "OptUnusedLoads",  0, 0, 0, 0, 0 };
1433 static OptFunc DOptUnusedStores = { OptUnusedStores, "OptUnusedStores", 0, 0, 0, 0, 0 };
1434 static OptFunc DOptDupLoads     = { OptDupLoads,     "OptDupLoads",     0, 0, 0, 0, 0 };
1435 static OptFunc DOptStoreLoad    = { OptStoreLoad,    "OptStoreLoad",    0, 0, 0, 0, 0 };
1436 static OptFunc DOptTransfers    = { OptTransfers,    "OptTransfers",    0, 0, 0, 0, 0 };
1437 static OptFunc DOptStackOps     = { OptStackOps,     "OptStackOps",     0, 0, 0, 0, 0 };
1438 static OptFunc DOptBranchDist   = { OptBranchDist,   "OptBranchDist",   0, 0, 0, 0, 0 };
1439
1440 /* Table containing all the steps in alphabetical order */
1441 static OptFunc* OptFuncs[] = {
1442     &DOptAdd1,
1443     &DOptAdd2,
1444     &DOptAdd3,
1445     &DOptBoolTrans,
1446     &DOptBranchDist,
1447     &DOptCmp1,
1448     &DOptCmp2,
1449     &DOptCmp3,
1450     &DOptCmp4,
1451     &DOptCmp5,
1452     &DOptCmp6,
1453     &DOptCmp7,
1454     &DOptCondBranches,
1455     &DOptDeadCode,
1456     &DOptDeadJumps,
1457     &DOptDupLoads,
1458     &DOptJumpCascades,
1459     &DOptJumpTarget,
1460     &DOptNegA1,
1461     &DOptNegA2,
1462     &DOptNegAX1,
1463     &DOptNegAX2,
1464     &DOptNegAX3,
1465     &DOptNegAX4,
1466     &DOptPtrStore1,
1467     &DOptPtrStore2,
1468     &DOptPtrLoad1,
1469     &DOptPtrLoad2,
1470     &DOptPtrLoad3,
1471     &DOptPtrLoad4,
1472     &DOptPtrLoad5,
1473     &DOptPtrLoad6,
1474     &DOptRTS,
1475     &DOptRTSJumps,
1476     &DOptSub1,
1477     &DOptSub2,
1478     &DOptShift1,
1479     &DOptStackOps,
1480     &DOptStoreLoad,
1481     &DOptTest1,
1482     &DOptTransfers,
1483     &DOptUnusedLoads,
1484     &DOptUnusedStores,
1485 };
1486 #define OPTFUNC_COUNT  (sizeof(OptFuncs) / sizeof(OptFuncs[0]))
1487
1488
1489
1490 static int CmpOptStep (const void* Key, const void* Func)
1491 /* Compare function for bsearch */
1492 {
1493     return strcmp (Key, (*(const OptFunc**)Func)->Name);
1494 }
1495
1496
1497
1498 static OptFunc* FindOptFunc (const char* Name)
1499 /* Find an optimizer step by name in the table and return a pointer. Return
1500  * NULL if no such step is found.
1501  */
1502 {
1503     /* Search for the function in the list */
1504     OptFunc** O = bsearch (Name, OptFuncs, OPTFUNC_COUNT, sizeof (OptFuncs[0]), CmpOptStep);
1505     return O? *O : 0;
1506 }
1507
1508
1509
1510 static OptFunc* GetOptFunc (const char* Name)
1511 /* Find an optimizer step by name in the table and return a pointer. Print an
1512  * error and call AbEnd if not found.
1513  */
1514 {
1515     /* Search for the function in the list */
1516     OptFunc* F = FindOptFunc (Name);
1517     if (F == 0) {
1518         /* Not found */
1519         AbEnd ("Optimization step `%s' not found", Name);
1520     }
1521     return F;
1522 }
1523
1524
1525
1526 void DisableOpt (const char* Name)
1527 /* Disable the optimization with the given name */
1528 {
1529     if (strcmp (Name, "any") == 0) {
1530         unsigned I;
1531         for (I = 0; I < OPTFUNC_COUNT; ++I) {
1532             OptFuncs[I]->Disabled = 1;
1533         }
1534     } else {
1535         GetOptFunc(Name)->Disabled = 1;
1536     }
1537 }
1538
1539
1540
1541 void EnableOpt (const char* Name)
1542 /* Enable the optimization with the given name */
1543 {
1544     if (strcmp (Name, "any") == 0) {
1545         unsigned I;
1546         for (I = 0; I < OPTFUNC_COUNT; ++I) {
1547             OptFuncs[I]->Disabled = 0;
1548         }
1549     } else {
1550         GetOptFunc(Name)->Disabled = 0;
1551     }
1552 }
1553
1554
1555
1556 void ListOptSteps (FILE* F)
1557 /* List all optimization steps */
1558 {
1559     unsigned I;
1560     for (I = 0; I < OPTFUNC_COUNT; ++I) {
1561         fprintf (F, "%s\n", OptFuncs[I]->Name);
1562     }
1563 }
1564
1565
1566
1567 static void ReadOptStats (const char* Name)
1568 /* Read the optimizer statistics file */
1569 {
1570     char Buf [256];
1571     unsigned Lines;
1572
1573     /* Try to open the file */
1574     FILE* F = fopen (Name, "r");
1575     if (F == 0) {
1576         /* Ignore the error */
1577         return;
1578     }
1579
1580     /* Read and parse the lines */
1581     Lines = 0;
1582     while (fgets (Buf, sizeof (Buf), F) != 0) {
1583
1584         char* B;
1585         unsigned Len;
1586         OptFunc* Func;
1587
1588         /* Fields */
1589         char Name[32];
1590         unsigned long  TotalRuns;
1591         unsigned long  TotalChanges;
1592
1593         /* Count lines */
1594         ++Lines;
1595
1596         /* Remove trailing white space including the line terminator */
1597         B = Buf;
1598         Len = strlen (B);
1599         while (Len > 0 && IsSpace (B[Len-1])) {
1600             --Len;
1601         }
1602         B[Len] = '\0';
1603
1604         /* Remove leading whitespace */
1605         while (IsSpace (*B)) {
1606             ++B;
1607         }
1608
1609         /* Check for empty and comment lines */
1610         if (*B == '\0' || *B == ';' || *B == '#') {
1611             continue;
1612         }
1613
1614         /* Parse the line */
1615         if (sscanf (B, "%31s %lu %*u %lu %*u", Name, &TotalRuns, &TotalChanges) != 3) {
1616             /* Syntax error */
1617             continue;
1618         }
1619
1620         /* Search for the optimizer step. */
1621         Func = FindOptFunc (Name);
1622         if (Func == 0) {
1623             /* Not found */
1624             continue;
1625         }
1626
1627         /* Found the step, set the fields */
1628         Func->TotalRuns    = TotalRuns;
1629         Func->TotalChanges = TotalChanges;
1630
1631     }
1632
1633     /* Close the file, ignore errors here. */
1634     fclose (F);
1635 }
1636
1637
1638
1639 static void WriteOptStats (const char* Name)
1640 /* Write the optimizer statistics file */
1641 {
1642     unsigned I;
1643
1644     /* Try to open the file */
1645     FILE* F = fopen (Name, "w");
1646     if (F == 0) {
1647         /* Ignore the error */
1648         return;
1649     }
1650
1651     /* Write the file */
1652     for (I = 0; I < OPTFUNC_COUNT; ++I) {
1653         const OptFunc* O = OptFuncs[I];
1654         fprintf (F,
1655                  "%s %lu %lu %lu %lu\n",
1656                  O->Name,
1657                  O->TotalRuns,
1658                  O->LastRuns,
1659                  O->TotalChanges,
1660                  O->LastChanges);
1661     }
1662
1663     /* Close the file, ignore errors here. */
1664     fclose (F);
1665 }
1666
1667
1668
1669 static unsigned RunOptFunc (CodeSeg* S, OptFunc* F, unsigned Max)
1670 /* Run one optimizer function Max times or until there are no more changes */
1671 {
1672     unsigned Changes, C;
1673
1674     /* Don't run the function if it is disabled */
1675     if (F->Disabled) {
1676         return 0;
1677     }
1678
1679     /* Run this until there are no more changes */
1680     Changes = 0;
1681     do {
1682
1683         /* Run the function */
1684         C = F->Func (S);
1685         Changes += C;
1686
1687         /* Do statistics */
1688         ++F->TotalRuns;
1689         ++F->LastRuns;
1690         F->TotalChanges += C;
1691         F->LastChanges  += C;
1692
1693     } while (--Max && C > 0);
1694
1695     /* Return the number of changes */
1696     return Changes;
1697 }
1698
1699
1700
1701 static void RunOptGroup1 (CodeSeg* S)
1702 /* Run the first group of optimization steps. These steps translate known
1703  * patterns emitted by the code generator into more optimal patterns. Order
1704  * of the steps is important, because some of the steps done earlier cover
1705  * the same patterns as later steps as subpatterns.
1706  */
1707 {
1708     RunOptFunc (S, &DOptPtrStore1, 1);
1709     RunOptFunc (S, &DOptPtrStore2, 1);
1710     RunOptFunc (S, &DOptPtrLoad1, 1);
1711     RunOptFunc (S, &DOptPtrLoad2, 1);
1712     RunOptFunc (S, &DOptPtrLoad3, 1);
1713     RunOptFunc (S, &DOptPtrLoad4, 1);
1714     RunOptFunc (S, &DOptPtrLoad5, 1);
1715     RunOptFunc (S, &DOptNegAX1, 1);
1716     RunOptFunc (S, &DOptNegAX2, 1);
1717     RunOptFunc (S, &DOptNegAX3, 1);
1718     RunOptFunc (S, &DOptNegAX4, 1);
1719     RunOptFunc (S, &DOptAdd1, 1);
1720     RunOptFunc (S, &DOptAdd2, 1);
1721     RunOptFunc (S, &DOptShift1, 1);
1722 }
1723
1724
1725
1726 static void RunOptGroup2 (CodeSeg* S)
1727 /* Run one group of optimization steps. These steps depend on each other,
1728  * that means that one step may allow another step to do additional work,
1729  * so we will repeat the steps as long as we see any changes.
1730  */
1731 {
1732     unsigned Changes;
1733
1734     do {
1735         Changes = 0;
1736
1737         Changes += RunOptFunc (S, &DOptPtrLoad6, 1);
1738         Changes += RunOptFunc (S, &DOptNegA1, 1);
1739         Changes += RunOptFunc (S, &DOptNegA2, 1);
1740         Changes += RunOptFunc (S, &DOptSub1, 1);
1741         Changes += RunOptFunc (S, &DOptSub2, 1);
1742         Changes += RunOptFunc (S, &DOptAdd3, 1);
1743         Changes += RunOptFunc (S, &DOptJumpCascades, 1);
1744         Changes += RunOptFunc (S, &DOptDeadJumps, 1);
1745         Changes += RunOptFunc (S, &DOptRTS, 1);
1746         Changes += RunOptFunc (S, &DOptDeadCode, 1);
1747         Changes += RunOptFunc (S, &DOptJumpTarget, 1);
1748         Changes += RunOptFunc (S, &DOptCondBranches, 1);
1749         Changes += RunOptFunc (S, &DOptRTSJumps, 1);
1750         Changes += RunOptFunc (S, &DOptBoolTrans, 1);
1751         Changes += RunOptFunc (S, &DOptCmp1, 1);
1752         Changes += RunOptFunc (S, &DOptCmp2, 1);
1753         Changes += RunOptFunc (S, &DOptCmp3, 1);
1754         Changes += RunOptFunc (S, &DOptCmp4, 1);
1755         Changes += RunOptFunc (S, &DOptCmp5, 1);
1756         Changes += RunOptFunc (S, &DOptCmp6, 1);
1757         Changes += RunOptFunc (S, &DOptCmp7, 1);
1758         Changes += RunOptFunc (S, &DOptTest1, 1);
1759         Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1760         Changes += RunOptFunc (S, &DOptUnusedStores, 1);
1761         Changes += RunOptFunc (S, &DOptDupLoads, 1);
1762         Changes += RunOptFunc (S, &DOptStoreLoad, 1);
1763         Changes += RunOptFunc (S, &DOptTransfers, 1);
1764         Changes += RunOptFunc (S, &DOptStackOps, 1);
1765
1766     } while (Changes);
1767 }
1768
1769
1770
1771 static void RunOptGroup3 (CodeSeg* S)
1772 /* The last group of optimization steps. Adjust branches.
1773  */
1774 {
1775     RunOptFunc (S, &DOptBranchDist, 3);
1776 }
1777
1778
1779
1780 void RunOpt (CodeSeg* S)
1781 /* Run the optimizer */
1782 {
1783     const char* StatFileName;
1784
1785     /* If we shouldn't run the optimizer, bail out */
1786     if (!Optimize) {
1787         return;
1788     }
1789
1790     /* Check if we are requested to write optimizer statistics */
1791     StatFileName = getenv ("CC65_OPTSTATS");
1792     if (StatFileName) {
1793         ReadOptStats (StatFileName);
1794     }
1795
1796     /* Print the name of the function we are working on */
1797     if (S->Func) {
1798         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1799     } else {
1800         Print (stdout, 1, "Running optimizer for global code segment\n");
1801     }
1802
1803     /* Run groups of optimizations */
1804     RunOptGroup1 (S);
1805     RunOptGroup2 (S);
1806     RunOptGroup3 (S);
1807
1808     /* Write statistics */
1809     if (StatFileName) {
1810         WriteOptStats (StatFileName);
1811     }
1812 }
1813
1814
1815