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