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