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