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