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