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