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-2012, 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 #include <stdarg.h>
  39
  40 /* common */
  41 #include "abend.h"
  42 #include "chartype.h"
  43 #include "cpu.h"
  44 #include "debugflag.h"
  45 #include "print.h"
  46 #include "strbuf.h"
  47 #include "xmalloc.h"
  48 #include "xsprintf.h"
  49
  50 /* cc65 */
  51 #include "asmlabel.h"
  52 #include "codeent.h"
  53 #include "codeinfo.h"
  54 #include "codeopt.h"
  55 #include "coptadd.h"
  56 #include "coptc02.h"
  57 #include "coptcmp.h"
  58 #include "coptind.h"
  59 #include "coptneg.h"
  60 #include "coptptrload.h"
  61 #include "coptptrstore.h"
  62 #include "coptpush.h"
  63 #include "coptshift.h"
  64 #include "coptsize.h"
  65 #include "coptstop.h"
  66 #include "coptstore.h"
  67 #include "coptsub.h"
  68 #include "copttest.h"
  69 #include "error.h"
  70 #include "global.h"
  71 #include "output.h"
  72
  73
  74
  75 /*****************************************************************************/
  76 /*                              Optimize loads                               */
  77 /*****************************************************************************/
  78
  79
  80
  81 static unsigned OptLoad1 (CodeSeg* S)
  82 /* Search for a call to ldaxysp where X is not used later and replace it by
  83  * a load of just the A register.
  84  */
  85 {
  86     unsigned I;
  87     unsigned Changes = 0;
  88
  89     /* Walk over the entries */
  90     I = 0;
  91     while (I < CS_GetEntryCount (S)) {
  92
  93         CodeEntry* E;
  94
  95         /* Get next entry */
  96         E = CS_GetEntry (S, I);
  97
  98         /* Check for the sequence */
  99         if (CE_IsCallTo (E, "ldaxysp")          &&
 100             RegValIsKnown (E->RI->In.RegY)      &&
 101             !RegXUsed (S, I+1)) {
 102
 103             CodeEntry* X;
 104
 105             /* Reload the Y register */
 106             const char* Arg = MakeHexArg (E->RI->In.RegY - 1);
 107             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 108             CS_InsertEntry (S, X, I+1);
 109
 110             /* Load from stack */
 111             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, E->LI);
 112             CS_InsertEntry (S, X, I+2);
 113
 114             /* Now remove the call to the subroutine */
 115             CS_DelEntry (S, I);
 116
 117             /* Remember, we had changes */
 118             ++Changes;
 119
 120         }
 121
 122         /* Next entry */
 123         ++I;
 124
 125     }
 126
 127     /* Return the number of changes made */
 128     return Changes;
 129 }
 130
 131
 132
 133 static unsigned OptLoad2 (CodeSeg* S)
 134 /* Replace calls to ldaxysp by inline code */
 135 {
 136     unsigned I;
 137     unsigned Changes = 0;
 138
 139     /* Walk over the entries */
 140     I = 0;
 141     while (I < CS_GetEntryCount (S)) {
 142
 143         CodeEntry* L[3];
 144
 145         /* Get next entry */
 146         L[0] = CS_GetEntry (S, I);
 147
 148         /* Check for the sequence */
 149         if (CE_IsCallTo (L[0], "ldaxysp")) {
 150
 151             CodeEntry* X;
 152
 153             /* Followed by sta abs/stx abs? */
 154             if (CS_GetEntries (S, L+1, I+1, 2)                  &&
 155                 L[1]->OPC == OP65_STA                           &&
 156                 L[2]->OPC == OP65_STX                           &&
 157                 (L[1]->Arg == 0                         ||
 158                  L[2]->Arg == 0                         ||
 159                  strcmp (L[1]->Arg, L[2]->Arg) != 0)            &&
 160                 !CS_RangeHasLabel (S, I+1, 2)                   &&
 161                 !RegXUsed (S, I+3)) {
 162
 163                 /* A/X are stored into memory somewhere and X is not used
 164                  * later
 165                  */
 166
 167                 /* lda (sp),y */
 168                 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[0]->LI);
 169                 CS_InsertEntry (S, X, I+3);
 170
 171                 /* sta abs */
 172                 X = NewCodeEntry (OP65_STA, L[2]->AM, L[2]->Arg, 0, L[2]->LI);
 173                 CS_InsertEntry (S, X, I+4);
 174
 175                 /* dey */
 176                 X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, L[0]->LI);
 177                 CS_InsertEntry (S, X, I+5);
 178
 179                 /* lda (sp),y */
 180                 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[0]->LI);
 181                 CS_InsertEntry (S, X, I+6);
 182
 183                 /* sta abs */
 184                 X = NewCodeEntry (OP65_STA, L[1]->AM, L[1]->Arg, 0, L[1]->LI);
 185                 CS_InsertEntry (S, X, I+7);
 186
 187                 /* Now remove the call to the subroutine and the sta/stx */
 188                 CS_DelEntries (S, I, 3);
 189
 190             } else {
 191
 192                 /* Standard replacement */
 193
 194                 /* lda (sp),y */
 195                 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[0]->LI);
 196                 CS_InsertEntry (S, X, I+1);
 197
 198                 /* tax */
 199                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
 200                 CS_InsertEntry (S, X, I+2);
 201
 202                 /* dey */
 203                 X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, L[0]->LI);
 204                 CS_InsertEntry (S, X, I+3);
 205
 206                 /* lda (sp),y */
 207                 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[0]->LI);
 208                 CS_InsertEntry (S, X, I+4);
 209
 210                 /* Now remove the call to the subroutine */
 211                 CS_DelEntry (S, I);
 212
 213             }
 214
 215             /* Remember, we had changes */
 216             ++Changes;
 217
 218         }
 219
 220         /* Next entry */
 221         ++I;
 222     }
 223
 224     /* Return the number of changes made */
 225     return Changes;
 226 }
 227
 228
 229
 230 static unsigned OptLoad3 (CodeSeg* S)
 231 /* Remove repeated loads from one and the same memory location */
 232 {
 233     unsigned Changes = 0;
 234     CodeEntry* Load = 0;
 235
 236     /* Walk over the entries */
 237     unsigned I = 0;
 238     while (I < CS_GetEntryCount (S)) {
 239
 240         /* Get next entry */
 241         CodeEntry* E = CS_GetEntry (S, I);
 242
 243         /* Forget a preceeding load if we have a label */
 244         if (Load && CE_HasLabel (E)) {
 245             Load = 0;
 246         }
 247
 248         /* Check if this insn is a load */
 249         if (E->Info & OF_LOAD) {
 250
 251             /* If we had a preceeding load that is identical, remove this one.
 252              * If it is not identical, or we didn't have one, remember it.
 253              */
 254             if (Load != 0                               &&
 255                 E->OPC == Load->OPC                     &&
 256                 E->AM == Load->AM                       &&
 257                 ((E->Arg == 0 && Load->Arg == 0) ||
 258                  strcmp (E->Arg, Load->Arg) == 0)) {
 259
 260                 /* Now remove the call to the subroutine */
 261                 CS_DelEntry (S, I);
 262
 263                 /* Remember, we had changes */
 264                 ++Changes;
 265
 266                 /* Next insn */
 267                 continue;
 268
 269             } else {
 270
 271                 Load = E;
 272
 273             }
 274
 275         } else if ((E->Info & OF_CMP) == 0 && (E->Info & OF_CBRA) == 0) {
 276             /* Forget the first load on occurance of any insn we don't like */
 277             Load = 0;
 278         }
 279
 280         /* Next entry */
 281         ++I;
 282     }
 283
 284     /* Return the number of changes made */
 285     return Changes;
 286 }
 287
 288
 289
 290 /*****************************************************************************/
 291 /*                            Decouple operations                            */
 292 /*****************************************************************************/
 293
 294
 295
 296 static unsigned OptDecouple (CodeSeg* S)
 297 /* Decouple operations, that is, do the following replacements:
 298  *
 299  *   dex        -> ldx #imm
 300  *   inx        -> ldx #imm
 301  *   dey        -> ldy #imm
 302  *   iny        -> ldy #imm
 303  *   tax        -> ldx #imm
 304  *   txa        -> lda #imm
 305  *   tay        -> ldy #imm
 306  *   tya        -> lda #imm
 307  *   lda zp     -> lda #imm
 308  *   ldx zp     -> ldx #imm
 309  *   ldy zp     -> ldy #imm
 310  *
 311  * Provided that the register values are known of course.
 312  */
 313 {
 314     unsigned Changes = 0;
 315     unsigned I;
 316
 317     /* Walk over the entries */
 318     I = 0;
 319     while (I < CS_GetEntryCount (S)) {
 320
 321         const char* Arg;
 322
 323         /* Get next entry and it's input register values */
 324         CodeEntry* E = CS_GetEntry (S, I);
 325         const RegContents* In = &E->RI->In;
 326
 327         /* Assume we have no replacement */
 328         CodeEntry* X = 0;
 329
 330         /* Check the instruction */
 331         switch (E->OPC) {
 332
 333             case OP65_DEA:
 334                 if (RegValIsKnown (In->RegA)) {
 335                     Arg = MakeHexArg ((In->RegA - 1) & 0xFF);
 336                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 337                 }
 338                 break;
 339
 340             case OP65_DEX:
 341                 if (RegValIsKnown (In->RegX)) {
 342                     Arg = MakeHexArg ((In->RegX - 1) & 0xFF);
 343                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 344                 }
 345                 break;
 346
 347             case OP65_DEY:
 348                 if (RegValIsKnown (In->RegY)) {
 349                     Arg = MakeHexArg ((In->RegY - 1) & 0xFF);
 350                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 351                 }
 352                 break;
 353
 354             case OP65_INA:
 355                 if (RegValIsKnown (In->RegA)) {
 356                     Arg = MakeHexArg ((In->RegA + 1) & 0xFF);
 357                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 358                 }
 359                 break;
 360
 361             case OP65_INX:
 362                 if (RegValIsKnown (In->RegX)) {
 363                     Arg = MakeHexArg ((In->RegX + 1) & 0xFF);
 364                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 365                 }
 366                 break;
 367
 368             case OP65_INY:
 369                 if (RegValIsKnown (In->RegY)) {
 370                     Arg = MakeHexArg ((In->RegY + 1) & 0xFF);
 371                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 372                 }
 373                 break;
 374
 375             case OP65_LDA:
 376                 if (E->AM == AM65_ZP) {
 377                     switch (GetKnownReg (E->Use & REG_ZP, In)) {
 378                         case REG_TMP1:
 379                             Arg = MakeHexArg (In->Tmp1);
 380                             X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 381                             break;
 382
 383                         case REG_PTR1_LO:
 384                             Arg = MakeHexArg (In->Ptr1Lo);
 385                             X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 386                             break;
 387
 388                         case REG_PTR1_HI:
 389                             Arg = MakeHexArg (In->Ptr1Hi);
 390                             X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 391                             break;
 392
 393                         case REG_SREG_LO:
 394                             Arg = MakeHexArg (In->SRegLo);
 395                             X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 396                             break;
 397
 398                         case REG_SREG_HI:
 399                             Arg = MakeHexArg (In->SRegHi);
 400                             X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 401                             break;
 402                     }
 403                 }
 404                 break;
 405
 406             case OP65_LDX:
 407                 if (E->AM == AM65_ZP) {
 408                     switch (GetKnownReg (E->Use & REG_ZP, In)) {
 409                         case REG_TMP1:
 410                             Arg = MakeHexArg (In->Tmp1);
 411                             X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 412                             break;
 413
 414                         case REG_PTR1_LO:
 415                             Arg = MakeHexArg (In->Ptr1Lo);
 416                             X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 417                             break;
 418
 419                         case REG_PTR1_HI:
 420                             Arg = MakeHexArg (In->Ptr1Hi);
 421                             X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 422                             break;
 423
 424                         case REG_SREG_LO:
 425                             Arg = MakeHexArg (In->SRegLo);
 426                             X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 427                             break;
 428
 429                         case REG_SREG_HI:
 430                             Arg = MakeHexArg (In->SRegHi);
 431                             X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 432                             break;
 433                     }
 434                 }
 435                 break;
 436
 437             case OP65_LDY:
 438                 if (E->AM == AM65_ZP) {
 439                     switch (GetKnownReg (E->Use, In)) {
 440                         case REG_TMP1:
 441                             Arg = MakeHexArg (In->Tmp1);
 442                             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 443                             break;
 444
 445                         case REG_PTR1_LO:
 446                             Arg = MakeHexArg (In->Ptr1Lo);
 447                             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 448                             break;
 449
 450                         case REG_PTR1_HI:
 451                             Arg = MakeHexArg (In->Ptr1Hi);
 452                             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 453                             break;
 454
 455                         case REG_SREG_LO:
 456                             Arg = MakeHexArg (In->SRegLo);
 457                             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 458                             break;
 459
 460                         case REG_SREG_HI:
 461                             Arg = MakeHexArg (In->SRegHi);
 462                             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 463                             break;
 464                     }
 465                 }
 466                 break;
 467
 468             case OP65_TAX:
 469                 if (E->RI->In.RegA >= 0) {
 470                     Arg = MakeHexArg (In->RegA);
 471                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, E->LI);
 472                 }
 473                 break;
 474
 475             case OP65_TAY:
 476                 if (E->RI->In.RegA >= 0) {
 477                     Arg = MakeHexArg (In->RegA);
 478                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 479                 }
 480                 break;
 481
 482             case OP65_TXA:
 483                 if (E->RI->In.RegX >= 0) {
 484                     Arg = MakeHexArg (In->RegX);
 485                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 486                 }
 487                 break;
 488
 489             case OP65_TYA:
 490                 if (E->RI->In.RegY >= 0) {
 491                     Arg = MakeHexArg (In->RegY);
 492                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
 493                 }
 494                 break;
 495
 496             default:
 497                 /* Avoid gcc warnings */
 498                 break;
 499
 500         }
 501
 502         /* Insert the replacement if we have one */
 503         if (X) {
 504             CS_InsertEntry (S, X, I+1);
 505             CS_DelEntry (S, I);
 506             ++Changes;
 507         }
 508
 509         /* Next entry */
 510         ++I;
 511
 512     }
 513
 514     /* Return the number of changes made */
 515     return Changes;
 516 }
 517
 518
 519
 520 /*****************************************************************************/
 521 /*                        Optimize stack pointer ops                         */
 522 /*****************************************************************************/
 523
 524
 525
 526 static unsigned IsDecSP (const CodeEntry* E)
 527 /* Check if this is an insn that decrements the stack pointer. If so, return
 528  * the decrement. If not, return zero.
 529  * The function expects E to be a subroutine call.
 530  */
 531 {
 532     if (strncmp (E->Arg, "decsp", 5) == 0) {
 533         if (E->Arg[5] >= '1' && E->Arg[5] <= '8') {
 534             return (E->Arg[5] - '0');
 535         }
 536     } else if (strcmp (E->Arg, "subysp") == 0 && RegValIsKnown (E->RI->In.RegY)) {
 537         return E->RI->In.RegY;
 538     }
 539
 540     /* If we come here, it's not a decsp op */
 541     return 0;
 542 }
 543
 544
 545
 546 static unsigned OptStackPtrOps (CodeSeg* S)
 547 /* Merge adjacent calls to decsp into one. NOTE: This function won't merge all
 548  * known cases!
 549  */
 550 {
 551     unsigned Changes = 0;
 552     unsigned I;
 553
 554     /* Walk over the entries */
 555     I = 0;
 556     while (I < CS_GetEntryCount (S)) {
 557
 558         unsigned Dec1;
 559         unsigned Dec2;
 560         const CodeEntry* N;
 561
 562         /* Get the next entry */
 563         const CodeEntry* E = CS_GetEntry (S, I);
 564
 565         /* Check for decspn or subysp */
 566         if (E->OPC == OP65_JSR                          &&
 567             (Dec1 = IsDecSP (E)) > 0                    &&
 568             (N = CS_GetNextEntry (S, I)) != 0           &&
 569             (Dec2 = IsDecSP (N)) > 0                    &&
 570             (Dec1 += Dec2) <= 255                       &&
 571             !CE_HasLabel (N)) {
 572
 573             CodeEntry* X;
 574             char Buf[20];
 575
 576             /* We can combine the two */
 577             if (Dec1 <= 8) {
 578                 /* Insert a call to decsp */
 579                 xsprintf (Buf, sizeof (Buf), "decsp%u", Dec1);
 580                 X = NewCodeEntry (OP65_JSR, AM65_ABS, Buf, 0, N->LI);
 581                 CS_InsertEntry (S, X, I+2);
 582             } else {
 583                 /* Insert a call to subysp */
 584                 const char* Arg = MakeHexArg (Dec1);
 585                 X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, N->LI);
 586                 CS_InsertEntry (S, X, I+2);
 587                 X = NewCodeEntry (OP65_JSR, AM65_ABS, "subysp", 0, N->LI);
 588                 CS_InsertEntry (S, X, I+3);
 589             }
 590
 591             /* Delete the old code */
 592             CS_DelEntries (S, I, 2);
 593
 594             /* Regenerate register info */
 595             CS_GenRegInfo (S);
 596
 597             /* Remember we had changes */
 598             ++Changes;
 599
 600         } else {
 601
 602             /* Next entry */
 603             ++I;
 604         }
 605
 606     }
 607
 608     /* Return the number of changes made */
 609     return Changes;
 610 }
 611
 612
 613
 614 /*****************************************************************************/
 615 /*                              struct OptFunc                               */
 616 /*****************************************************************************/
 617
 618
 619
 620 typedef struct OptFunc OptFunc;
 621 struct OptFunc {
 622     unsigned       (*Func) (CodeSeg*);  /* Optimizer function */
 623     const char*    Name;                /* Name of the function/group */
 624     unsigned       CodeSizeFactor;      /* Code size factor for this opt func */
 625     unsigned long  TotalRuns;           /* Total number of runs */
 626     unsigned long  LastRuns;            /* Last number of runs */
 627     unsigned long  TotalChanges;        /* Total number of changes */
 628     unsigned long  LastChanges;         /* Last number of changes */
 629     char           Disabled;            /* True if function disabled */
 630 };
 631
 632
 633
 634 /*****************************************************************************/
 635 /*                                   Code                                    */
 636 /*****************************************************************************/
 637
 638
 639
 640 /* A list of all the function descriptions */
 641 static OptFunc DOpt65C02BitOps  = { Opt65C02BitOps,  "Opt65C02BitOps",   66, 0, 0, 0, 0, 0 };
 642 static OptFunc DOpt65C02Ind     = { Opt65C02Ind,     "Opt65C02Ind",     100, 0, 0, 0, 0, 0 };
 643 static OptFunc DOpt65C02Stores  = { Opt65C02Stores,  "Opt65C02Stores",  100, 0, 0, 0, 0, 0 };
 644 static OptFunc DOptAdd1         = { OptAdd1,         "OptAdd1",         125, 0, 0, 0, 0, 0 };
 645 static OptFunc DOptAdd2         = { OptAdd2,         "OptAdd2",         200, 0, 0, 0, 0, 0 };
 646 static OptFunc DOptAdd3         = { OptAdd3,         "OptAdd3",          65, 0, 0, 0, 0, 0 };
 647 static OptFunc DOptAdd4         = { OptAdd4,         "OptAdd4",          90, 0, 0, 0, 0, 0 };
 648 static OptFunc DOptAdd5         = { OptAdd5,         "OptAdd5",         100, 0, 0, 0, 0, 0 };
 649 static OptFunc DOptAdd6         = { OptAdd6,         "OptAdd6",          40, 0, 0, 0, 0, 0 };
 650 static OptFunc DOptBNegA1       = { OptBNegA1,       "OptBNegA1",       100, 0, 0, 0, 0, 0 };
 651 static OptFunc DOptBNegA2       = { OptBNegA2,       "OptBNegA2",       100, 0, 0, 0, 0, 0 };
 652 static OptFunc DOptBNegAX1      = { OptBNegAX1,      "OptBNegAX1",      100, 0, 0, 0, 0, 0 };
 653 static OptFunc DOptBNegAX2      = { OptBNegAX2,      "OptBNegAX2",      100, 0, 0, 0, 0, 0 };
 654 static OptFunc DOptBNegAX3      = { OptBNegAX3,      "OptBNegAX3",      100, 0, 0, 0, 0, 0 };
 655 static OptFunc DOptBNegAX4      = { OptBNegAX4,      "OptBNegAX4",      100, 0, 0, 0, 0, 0 };
 656 static OptFunc DOptBoolTrans    = { OptBoolTrans,    "OptBoolTrans",    100, 0, 0, 0, 0, 0 };
 657 static OptFunc DOptBranchDist   = { OptBranchDist,   "OptBranchDist",     0, 0, 0, 0, 0, 0 };
 658 static OptFunc DOptCmp1         = { OptCmp1,         "OptCmp1",          42, 0, 0, 0, 0, 0 };
 659 static OptFunc DOptCmp2         = { OptCmp2,         "OptCmp2",          85, 0, 0, 0, 0, 0 };
 660 static OptFunc DOptCmp3         = { OptCmp3,         "OptCmp3",          75, 0, 0, 0, 0, 0 };
 661 static OptFunc DOptCmp4         = { OptCmp4,         "OptCmp4",          75, 0, 0, 0, 0, 0 };
 662 static OptFunc DOptCmp5         = { OptCmp5,         "OptCmp5",         100, 0, 0, 0, 0, 0 };
 663 static OptFunc DOptCmp6         = { OptCmp6,         "OptCmp6",         100, 0, 0, 0, 0, 0 };
 664 static OptFunc DOptCmp7         = { OptCmp7,         "OptCmp7",          85, 0, 0, 0, 0, 0 };
 665 static OptFunc DOptCmp8         = { OptCmp8,         "OptCmp8",          50, 0, 0, 0, 0, 0 };
 666 static OptFunc DOptCmp9         = { OptCmp9,         "OptCmp9",          85, 0, 0, 0, 0, 0 };
 667 static OptFunc DOptComplAX1     = { OptComplAX1,     "OptComplAX1",      65, 0, 0, 0, 0, 0 };
 668 static OptFunc DOptCondBranches1= { OptCondBranches1,"OptCondBranches1", 80, 0, 0, 0, 0, 0 };
 669 static OptFunc DOptCondBranches2= { OptCondBranches2,"OptCondBranches2",  0, 0, 0, 0, 0, 0 };
 670 static OptFunc DOptDeadCode     = { OptDeadCode,     "OptDeadCode",     100, 0, 0, 0, 0, 0 };
 671 static OptFunc DOptDeadJumps    = { OptDeadJumps,    "OptDeadJumps",    100, 0, 0, 0, 0, 0 };
 672 static OptFunc DOptDecouple     = { OptDecouple,     "OptDecouple",     100, 0, 0, 0, 0, 0 };
 673 static OptFunc DOptDupLoads     = { OptDupLoads,     "OptDupLoads",       0, 0, 0, 0, 0, 0 };
 674 static OptFunc DOptIndLoads1    = { OptIndLoads1,    "OptIndLoads1",      0, 0, 0, 0, 0, 0 };
 675 static OptFunc DOptIndLoads2    = { OptIndLoads2,    "OptIndLoads2",      0, 0, 0, 0, 0, 0 };
 676 static OptFunc DOptJumpCascades = { OptJumpCascades, "OptJumpCascades", 100, 0, 0, 0, 0, 0 };
 677 static OptFunc DOptJumpTarget1  = { OptJumpTarget1,  "OptJumpTarget1",  100, 0, 0, 0, 0, 0 };
 678 static OptFunc DOptJumpTarget2  = { OptJumpTarget2,  "OptJumpTarget2",  100, 0, 0, 0, 0, 0 };
 679 static OptFunc DOptJumpTarget3  = { OptJumpTarget3,  "OptJumpTarget3",  100, 0, 0, 0, 0, 0 };
 680 static OptFunc DOptLoad1        = { OptLoad1,        "OptLoad1",        100, 0, 0, 0, 0, 0 };
 681 static OptFunc DOptLoad2        = { OptLoad2,        "OptLoad2",        200, 0, 0, 0, 0, 0 };
 682 static OptFunc DOptLoad3        = { OptLoad3,        "OptLoad3",          0, 0, 0, 0, 0, 0 };
 683 static OptFunc DOptNegAX1       = { OptNegAX1,       "OptNegAX1",       165, 0, 0, 0, 0, 0 };
 684 static OptFunc DOptNegAX2       = { OptNegAX2,       "OptNegAX2",       200, 0, 0, 0, 0, 0 };
 685 static OptFunc DOptRTS          = { OptRTS,          "OptRTS",          100, 0, 0, 0, 0, 0 };
 686 static OptFunc DOptRTSJumps1    = { OptRTSJumps1,    "OptRTSJumps1",    100, 0, 0, 0, 0, 0 };
 687 static OptFunc DOptRTSJumps2    = { OptRTSJumps2,    "OptRTSJumps2",    100, 0, 0, 0, 0, 0 };
 688 static OptFunc DOptPrecalc      = { OptPrecalc,      "OptPrecalc",      100, 0, 0, 0, 0, 0 };
 689 static OptFunc DOptPtrLoad1     = { OptPtrLoad1,     "OptPtrLoad1",     100, 0, 0, 0, 0, 0 };
 690 static OptFunc DOptPtrLoad2     = { OptPtrLoad2,     "OptPtrLoad2",     100, 0, 0, 0, 0, 0 };
 691 static OptFunc DOptPtrLoad3     = { OptPtrLoad3,     "OptPtrLoad3",     100, 0, 0, 0, 0, 0 };
 692 static OptFunc DOptPtrLoad4     = { OptPtrLoad4,     "OptPtrLoad4",     100, 0, 0, 0, 0, 0 };
 693 static OptFunc DOptPtrLoad5     = { OptPtrLoad5,     "OptPtrLoad5",      50, 0, 0, 0, 0, 0 };
 694 static OptFunc DOptPtrLoad6     = { OptPtrLoad6,     "OptPtrLoad6",      60, 0, 0, 0, 0, 0 };
 695 static OptFunc DOptPtrLoad7     = { OptPtrLoad7,     "OptPtrLoad7",     140, 0, 0, 0, 0, 0 };
 696 static OptFunc DOptPtrLoad11    = { OptPtrLoad11,    "OptPtrLoad11",     92, 0, 0, 0, 0, 0 };
 697 static OptFunc DOptPtrLoad12    = { OptPtrLoad12,    "OptPtrLoad12",     50, 0, 0, 0, 0, 0 };
 698 static OptFunc DOptPtrLoad13    = { OptPtrLoad13,    "OptPtrLoad13",     65, 0, 0, 0, 0, 0 };
 699 static OptFunc DOptPtrLoad14    = { OptPtrLoad14,    "OptPtrLoad14",    108, 0, 0, 0, 0, 0 };
 700 static OptFunc DOptPtrLoad15    = { OptPtrLoad15,    "OptPtrLoad15",     86, 0, 0, 0, 0, 0 };
 701 static OptFunc DOptPtrLoad16    = { OptPtrLoad16,    "OptPtrLoad16",    100, 0, 0, 0, 0, 0 };
 702 static OptFunc DOptPtrLoad17    = { OptPtrLoad17,    "OptPtrLoad17",    190, 0, 0, 0, 0, 0 };
 703 static OptFunc DOptPtrStore1    = { OptPtrStore1,    "OptPtrStore1",     65, 0, 0, 0, 0, 0 };
 704 static OptFunc DOptPtrStore2    = { OptPtrStore2,    "OptPtrStore2",     65, 0, 0, 0, 0, 0 };
 705 static OptFunc DOptPtrStore3    = { OptPtrStore3,    "OptPtrStore3",    100, 0, 0, 0, 0, 0 };
 706 static OptFunc DOptPush1        = { OptPush1,        "OptPush1",         65, 0, 0, 0, 0, 0 };
 707 static OptFunc DOptPush2        = { OptPush2,        "OptPush2",         50, 0, 0, 0, 0, 0 };
 708 static OptFunc DOptPushPop      = { OptPushPop,      "OptPushPop",        0, 0, 0, 0, 0, 0 };
 709 static OptFunc DOptShift1       = { OptShift1,       "OptShift1",       100, 0, 0, 0, 0, 0 };
 710 static OptFunc DOptShift2       = { OptShift2,       "OptShift2",       100, 0, 0, 0, 0, 0 };
 711 static OptFunc DOptShift3       = { OptShift3,       "OptShift3",        17, 0, 0, 0, 0, 0 };
 712 static OptFunc DOptShift4       = { OptShift4,       "OptShift4",       100, 0, 0, 0, 0, 0 };
 713 static OptFunc DOptShift5       = { OptShift5,       "OptShift5",       110, 0, 0, 0, 0, 0 };
 714 static OptFunc DOptShift6       = { OptShift6,       "OptShift6",       200, 0, 0, 0, 0, 0 };
 715 static OptFunc DOptSize1        = { OptSize1,        "OptSize1",        100, 0, 0, 0, 0, 0 };
 716 static OptFunc DOptSize2        = { OptSize2,        "OptSize2",        100, 0, 0, 0, 0, 0 };
 717 static OptFunc DOptStackOps     = { OptStackOps,     "OptStackOps",     100, 0, 0, 0, 0, 0 };
 718 static OptFunc DOptStackPtrOps  = { OptStackPtrOps,  "OptStackPtrOps",   50, 0, 0, 0, 0, 0 };
 719 static OptFunc DOptStore1       = { OptStore1,       "OptStore1",        70, 0, 0, 0, 0, 0 };
 720 static OptFunc DOptStore2       = { OptStore2,       "OptStore2",       115, 0, 0, 0, 0, 0 };
 721 static OptFunc DOptStore3       = { OptStore3,       "OptStore3",       120, 0, 0, 0, 0, 0 };
 722 static OptFunc DOptStore4       = { OptStore4,       "OptStore4",        50, 0, 0, 0, 0, 0 };
 723 static OptFunc DOptStore5       = { OptStore5,       "OptStore5",       100, 0, 0, 0, 0, 0 };
 724 static OptFunc DOptStoreLoad    = { OptStoreLoad,    "OptStoreLoad",      0, 0, 0, 0, 0, 0 };
 725 static OptFunc DOptSub1         = { OptSub1,         "OptSub1",         100, 0, 0, 0, 0, 0 };
 726 static OptFunc DOptSub2         = { OptSub2,         "OptSub2",         100, 0, 0, 0, 0, 0 };
 727 static OptFunc DOptSub3         = { OptSub3,         "OptSub3",         100, 0, 0, 0, 0, 0 };
 728 static OptFunc DOptTest1        = { OptTest1,        "OptTest1",         65, 0, 0, 0, 0, 0 };
 729 static OptFunc DOptTest2        = { OptTest2,        "OptTest2",         50, 0, 0, 0, 0, 0 };
 730 static OptFunc DOptTransfers1   = { OptTransfers1,   "OptTransfers1",     0, 0, 0, 0, 0, 0 };
 731 static OptFunc DOptTransfers2   = { OptTransfers2,   "OptTransfers2",    60, 0, 0, 0, 0, 0 };
 732 static OptFunc DOptTransfers3   = { OptTransfers3,   "OptTransfers3",    65, 0, 0, 0, 0, 0 };
 733 static OptFunc DOptTransfers4   = { OptTransfers4,   "OptTransfers4",    65, 0, 0, 0, 0, 0 };
 734 static OptFunc DOptUnusedLoads  = { OptUnusedLoads,  "OptUnusedLoads",    0, 0, 0, 0, 0, 0 };
 735 static OptFunc DOptUnusedStores = { OptUnusedStores, "OptUnusedStores",   0, 0, 0, 0, 0, 0 };
 736
 737
 738 /* Table containing all the steps in alphabetical order */
 739 static OptFunc* OptFuncs[] = {
 740     &DOpt65C02BitOps,
 741     &DOpt65C02Ind,
 742     &DOpt65C02Stores,
 743     &DOptAdd1,
 744     &DOptAdd2,
 745     &DOptAdd3,
 746     &DOptAdd4,
 747     &DOptAdd5,
 748     &DOptAdd6,
 749     &DOptBNegA1,
 750     &DOptBNegA2,
 751     &DOptBNegAX1,
 752     &DOptBNegAX2,
 753     &DOptBNegAX3,
 754     &DOptBNegAX4,
 755     &DOptBoolTrans,
 756     &DOptBranchDist,
 757     &DOptCmp1,
 758     &DOptCmp2,
 759     &DOptCmp3,
 760     &DOptCmp4,
 761     &DOptCmp5,
 762     &DOptCmp6,
 763     &DOptCmp7,
 764     &DOptCmp8,
 765     &DOptCmp9,
 766     &DOptComplAX1,
 767     &DOptCondBranches1,
 768     &DOptCondBranches2,
 769     &DOptDeadCode,
 770     &DOptDeadJumps,
 771     &DOptDecouple,
 772     &DOptDupLoads,
 773     &DOptIndLoads1,
 774     &DOptIndLoads2,
 775     &DOptJumpCascades,
 776     &DOptJumpTarget1,
 777     &DOptJumpTarget2,
 778     &DOptJumpTarget3,
 779     &DOptLoad1,
 780     &DOptLoad2,
 781     &DOptLoad3,
 782     &DOptNegAX1,
 783     &DOptNegAX2,
 784     &DOptPrecalc,
 785     &DOptPtrLoad1,
 786     &DOptPtrLoad11,
 787     &DOptPtrLoad12,
 788     &DOptPtrLoad13,
 789     &DOptPtrLoad14,
 790     &DOptPtrLoad15,
 791     &DOptPtrLoad16,
 792     &DOptPtrLoad17,
 793     &DOptPtrLoad2,
 794     &DOptPtrLoad3,
 795     &DOptPtrLoad4,
 796     &DOptPtrLoad5,
 797     &DOptPtrLoad6,
 798     &DOptPtrLoad7,
 799     &DOptPtrStore1,
 800     &DOptPtrStore2,
 801     &DOptPtrStore3,
 802     &DOptPush1,
 803     &DOptPush2,
 804     &DOptPushPop,
 805     &DOptRTS,
 806     &DOptRTSJumps1,
 807     &DOptRTSJumps2,
 808     &DOptShift1,
 809     &DOptShift2,
 810     &DOptShift3,
 811     &DOptShift4,
 812     &DOptShift5,
 813     &DOptShift6,
 814     &DOptSize1,
 815     &DOptSize2,
 816     &DOptStackOps,
 817     &DOptStackPtrOps,
 818     &DOptStore1,
 819     &DOptStore2,
 820     &DOptStore3,
 821     &DOptStore4,
 822     &DOptStore5,
 823     &DOptStoreLoad,
 824     &DOptSub1,
 825     &DOptSub2,
 826     &DOptSub3,
 827     &DOptTest1,
 828     &DOptTest2,
 829     &DOptTransfers1,
 830     &DOptTransfers2,
 831     &DOptTransfers3,
 832     &DOptTransfers4,
 833     &DOptUnusedLoads,
 834     &DOptUnusedStores,
 835 };
 836 #define OPTFUNC_COUNT  (sizeof(OptFuncs) / sizeof(OptFuncs[0]))
 837
 838
 839
 840 static int CmpOptStep (const void* Key, const void* Func)
 841 /* Compare function for bsearch */
 842 {
 843     return strcmp (Key, (*(const OptFunc**)Func)->Name);
 844 }
 845
 846
 847
 848 static OptFunc* FindOptFunc (const char* Name)
 849 /* Find an optimizer step by name in the table and return a pointer. Return
 850  * NULL if no such step is found.
 851  */
 852 {
 853     /* Search for the function in the list */
 854     OptFunc** O = bsearch (Name, OptFuncs, OPTFUNC_COUNT, sizeof (OptFuncs[0]), CmpOptStep);
 855     return O? *O : 0;
 856 }
 857
 858
 859
 860 static OptFunc* GetOptFunc (const char* Name)
 861 /* Find an optimizer step by name in the table and return a pointer. Print an
 862  * error and call AbEnd if not found.
 863  */
 864 {
 865     /* Search for the function in the list */
 866     OptFunc* F = FindOptFunc (Name);
 867     if (F == 0) {
 868         /* Not found */
 869         AbEnd ("Optimization step `%s' not found", Name);
 870     }
 871     return F;
 872 }
 873
 874
 875
 876 void DisableOpt (const char* Name)
 877 /* Disable the optimization with the given name */
 878 {
 879     if (strcmp (Name, "any") == 0) {
 880         unsigned I;
 881         for (I = 0; I < OPTFUNC_COUNT; ++I) {
 882             OptFuncs[I]->Disabled = 1;
 883         }
 884     } else {
 885         GetOptFunc(Name)->Disabled = 1;
 886     }
 887 }
 888
 889
 890
 891 void EnableOpt (const char* Name)
 892 /* Enable the optimization with the given name */
 893 {
 894     if (strcmp (Name, "any") == 0) {
 895         unsigned I;
 896         for (I = 0; I < OPTFUNC_COUNT; ++I) {
 897             OptFuncs[I]->Disabled = 0;
 898         }
 899     } else {
 900         GetOptFunc(Name)->Disabled = 0;
 901     }
 902 }
 903
 904
 905
 906 void ListOptSteps (FILE* F)
 907 /* List all optimization steps */
 908 {
 909     unsigned I;
 910     for (I = 0; I < OPTFUNC_COUNT; ++I) {
 911         fprintf (F, "%s\n", OptFuncs[I]->Name);
 912     }
 913 }
 914
 915
 916
 917 static void ReadOptStats (const char* Name)
 918 /* Read the optimizer statistics file */
 919 {
 920     char Buf [256];
 921     unsigned Lines;
 922
 923     /* Try to open the file */
 924     FILE* F = fopen (Name, "r");
 925     if (F == 0) {
 926         /* Ignore the error */
 927         return;
 928     }
 929
 930     /* Read and parse the lines */
 931     Lines = 0;
 932     while (fgets (Buf, sizeof (Buf), F) != 0) {
 933
 934         char* B;
 935         unsigned Len;
 936         OptFunc* Func;
 937
 938         /* Fields */
 939         char Name[32];
 940         unsigned long  TotalRuns;
 941         unsigned long  TotalChanges;
 942
 943         /* Count lines */
 944         ++Lines;
 945
 946         /* Remove trailing white space including the line terminator */
 947         B = Buf;
 948         Len = strlen (B);
 949         while (Len > 0 && IsSpace (B[Len-1])) {
 950             --Len;
 951         }
 952         B[Len] = '\0';
 953
 954         /* Remove leading whitespace */
 955         while (IsSpace (*B)) {
 956             ++B;
 957         }
 958
 959         /* Check for empty and comment lines */
 960         if (*B == '\0' || *B == ';' || *B == '#') {
 961             continue;
 962         }
 963
 964         /* Parse the line */
 965         if (sscanf (B, "%31s %lu %*u %lu %*u", Name, &TotalRuns, &TotalChanges) != 3) {
 966             /* Syntax error */
 967             continue;
 968         }
 969
 970         /* Search for the optimizer step. */
 971         Func = FindOptFunc (Name);
 972         if (Func == 0) {
 973             /* Not found */
 974             continue;
 975         }
 976
 977         /* Found the step, set the fields */
 978         Func->TotalRuns    = TotalRuns;
 979         Func->TotalChanges = TotalChanges;
 980
 981     }
 982
 983     /* Close the file, ignore errors here. */
 984     fclose (F);
 985 }
 986
 987
 988
 989 static void WriteOptStats (const char* Name)
 990 /* Write the optimizer statistics file */
 991 {
 992     unsigned I;
 993
 994     /* Try to open the file */
 995     FILE* F = fopen (Name, "w");
 996     if (F == 0) {
 997         /* Ignore the error */
 998         return;
 999     }
1000
1001     /* Write a header */
1002     fprintf (F,
1003              "; Optimizer               Total      Last       Total      Last\n"
1004              ";   Step                  Runs       Runs        Chg       Chg\n");
1005
1006
1007     /* Write the data */
1008     for (I = 0; I < OPTFUNC_COUNT; ++I) {
1009         const OptFunc* O = OptFuncs[I];
1010         fprintf (F,
1011                  "%-20s %10lu %10lu %10lu %10lu\n",
1012                  O->Name,
1013                  O->TotalRuns,
1014                  O->LastRuns,
1015                  O->TotalChanges,
1016                  O->LastChanges);
1017     }
1018
1019     /* Close the file, ignore errors here. */
1020     fclose (F);
1021 }
1022
1023
1024
1025 static void OpenDebugFile (const CodeSeg* S)
1026 /* Open the debug file for the given segment if the flag is on */
1027 {
1028     if (DebugOptOutput) {
1029         StrBuf Name = AUTO_STRBUF_INITIALIZER;
1030         if (S->Func) {
1031             SB_CopyStr (&Name, S->Func->Name);
1032         } else {
1033             SB_CopyStr (&Name, "global");
1034         }
1035         SB_AppendStr (&Name, ".opt");
1036         SB_Terminate (&Name);
1037         OpenDebugOutputFile (SB_GetConstBuf (&Name));
1038         SB_Done (&Name);
1039     }
1040 }
1041
1042
1043
1044 static void WriteDebugOutput (CodeSeg* S, const char* Step)
1045 /* Write a separator line into the debug file if the flag is on */
1046 {
1047     if (DebugOptOutput) {
1048         /* Output a separator */
1049         WriteOutput ("=========================================================================\n");
1050
1051         /* Output a header line */
1052         if (Step == 0) {
1053             /* Initial output */
1054             WriteOutput ("Initial code for function `%s':\n",
1055                          S->Func? S->Func->Name : "<global>");
1056         } else {
1057             WriteOutput ("Code after applying `%s':\n", Step);
1058         }
1059
1060         /* Output the code segment */
1061         CS_Output (S);
1062     }
1063 }
1064
1065
1066
1067 static unsigned RunOptFunc (CodeSeg* S, OptFunc* F, unsigned Max)
1068 /* Run one optimizer function Max times or until there are no more changes */
1069 {
1070     unsigned Changes, C;
1071
1072     /* Don't run the function if it is disabled or if it is prohibited by the
1073      * code size factor
1074      */
1075     if (F->Disabled || F->CodeSizeFactor > S->CodeSizeFactor) {
1076         return 0;
1077     }
1078
1079     /* Run this until there are no more changes */
1080     Changes = 0;
1081     do {
1082
1083         /* Run the function */
1084         C = F->Func (S);
1085         Changes += C;
1086
1087         /* Do statistics */
1088         ++F->TotalRuns;
1089         ++F->LastRuns;
1090         F->TotalChanges += C;
1091         F->LastChanges  += C;
1092
1093         /* If we had changes, output stuff and regenerate register info */
1094         if (C) {
1095             if (Debug) {
1096                 printf ("Applied %s: %u changes\n", F->Name, C);
1097             }
1098             WriteDebugOutput (S, F->Name);
1099             CS_GenRegInfo (S);
1100         }
1101
1102     } while (--Max && C > 0);
1103
1104     /* Return the number of changes */
1105     return Changes;
1106 }
1107
1108
1109
1110 static unsigned RunOptGroup1 (CodeSeg* S)
1111 /* Run the first group of optimization steps. These steps translate known
1112  * patterns emitted by the code generator into more optimal patterns. Order
1113  * of the steps is important, because some of the steps done earlier cover
1114  * the same patterns as later steps as subpatterns.
1115  */
1116 {
1117     unsigned Changes = 0;
1118
1119     Changes += RunOptFunc (S, &DOptStackPtrOps, 5);
1120     Changes += RunOptFunc (S, &DOptPtrStore1, 1);
1121     Changes += RunOptFunc (S, &DOptPtrStore2, 1);
1122     Changes += RunOptFunc (S, &DOptPtrStore3, 1);
1123     Changes += RunOptFunc (S, &DOptAdd3, 1);    /* Before OptPtrLoad5! */
1124     Changes += RunOptFunc (S, &DOptPtrLoad1, 1);
1125     Changes += RunOptFunc (S, &DOptPtrLoad2, 1);
1126     Changes += RunOptFunc (S, &DOptPtrLoad3, 1);
1127     Changes += RunOptFunc (S, &DOptPtrLoad4, 1);
1128     Changes += RunOptFunc (S, &DOptPtrLoad5, 1);
1129     Changes += RunOptFunc (S, &DOptPtrLoad6, 1);
1130     Changes += RunOptFunc (S, &DOptPtrLoad7, 1);
1131     Changes += RunOptFunc (S, &DOptPtrLoad11, 1);
1132     Changes += RunOptFunc (S, &DOptPtrLoad12, 1);
1133     Changes += RunOptFunc (S, &DOptPtrLoad13, 1);
1134     Changes += RunOptFunc (S, &DOptPtrLoad14, 1);
1135     Changes += RunOptFunc (S, &DOptPtrLoad15, 1);
1136     Changes += RunOptFunc (S, &DOptPtrLoad16, 1);
1137     Changes += RunOptFunc (S, &DOptPtrLoad17, 1);
1138     Changes += RunOptFunc (S, &DOptBNegAX1, 1);
1139     Changes += RunOptFunc (S, &DOptBNegAX2, 1);
1140     Changes += RunOptFunc (S, &DOptBNegAX3, 1);
1141     Changes += RunOptFunc (S, &DOptBNegAX4, 1);
1142     Changes += RunOptFunc (S, &DOptAdd1, 1);
1143     Changes += RunOptFunc (S, &DOptAdd2, 1);
1144     Changes += RunOptFunc (S, &DOptAdd4, 1);
1145     Changes += RunOptFunc (S, &DOptAdd5, 1);
1146     Changes += RunOptFunc (S, &DOptAdd6, 1);
1147     Changes += RunOptFunc (S, &DOptSub1, 1);
1148     Changes += RunOptFunc (S, &DOptSub3, 1);
1149     Changes += RunOptFunc (S, &DOptStore4, 1);
1150     Changes += RunOptFunc (S, &DOptStore5, 1);
1151     Changes += RunOptFunc (S, &DOptShift1, 1);
1152     Changes += RunOptFunc (S, &DOptShift2, 1);
1153     Changes += RunOptFunc (S, &DOptShift5, 1);
1154     Changes += RunOptFunc (S, &DOptShift6, 1);
1155     Changes += RunOptFunc (S, &DOptStore1, 1);
1156     Changes += RunOptFunc (S, &DOptStore2, 5);
1157     Changes += RunOptFunc (S, &DOptStore3, 5);
1158
1159     /* Return the number of changes */
1160     return Changes;
1161 }
1162
1163
1164
1165 static unsigned RunOptGroup2 (CodeSeg* S)
1166 /* Run one group of optimization steps. This step involves just decoupling
1167  * instructions by replacing them by instructions that do not depend on
1168  * previous instructions. This makes it easier to find instructions that
1169  * aren't used.
1170  */
1171 {
1172     unsigned Changes = 0;
1173
1174     Changes += RunOptFunc (S, &DOptDecouple, 1);
1175
1176     /* Return the number of changes */
1177     return Changes;
1178 }
1179
1180
1181
1182 static unsigned RunOptGroup3 (CodeSeg* S)
1183 /* Run one group of optimization steps. These steps depend on each other,
1184  * that means that one step may allow another step to do additional work,
1185  * so we will repeat the steps as long as we see any changes.
1186  */
1187 {
1188     unsigned Changes, C;
1189
1190     Changes = 0;
1191     do {
1192         C = 0;
1193
1194         C += RunOptFunc (S, &DOptBNegA1, 1);
1195         C += RunOptFunc (S, &DOptBNegA2, 1);
1196         C += RunOptFunc (S, &DOptNegAX1, 1);
1197         C += RunOptFunc (S, &DOptNegAX2, 1);
1198         C += RunOptFunc (S, &DOptStackOps, 3);
1199         C += RunOptFunc (S, &DOptShift1, 1);
1200         C += RunOptFunc (S, &DOptShift4, 1);
1201         C += RunOptFunc (S, &DOptComplAX1, 1);
1202         C += RunOptFunc (S, &DOptSub1, 1);
1203         C += RunOptFunc (S, &DOptSub2, 1);
1204         C += RunOptFunc (S, &DOptSub3, 1);
1205         C += RunOptFunc (S, &DOptAdd5, 1);
1206         C += RunOptFunc (S, &DOptAdd6, 1);
1207         C += RunOptFunc (S, &DOptJumpCascades, 1);
1208         C += RunOptFunc (S, &DOptDeadJumps, 1);
1209         C += RunOptFunc (S, &DOptRTS, 1);
1210         C += RunOptFunc (S, &DOptDeadCode, 1);
1211         C += RunOptFunc (S, &DOptBoolTrans, 1);
1212         C += RunOptFunc (S, &DOptJumpTarget1, 1);
1213         C += RunOptFunc (S, &DOptJumpTarget2, 1);
1214         C += RunOptFunc (S, &DOptCondBranches1, 1);
1215         C += RunOptFunc (S, &DOptCondBranches2, 1);
1216         C += RunOptFunc (S, &DOptRTSJumps1, 1);
1217         C += RunOptFunc (S, &DOptCmp1, 1);
1218         C += RunOptFunc (S, &DOptCmp2, 1);
1219         C += RunOptFunc (S, &DOptCmp8, 1);      /* Must run before OptCmp3 */
1220         C += RunOptFunc (S, &DOptCmp3, 1);
1221         C += RunOptFunc (S, &DOptCmp4, 1);
1222         C += RunOptFunc (S, &DOptCmp5, 1);
1223         C += RunOptFunc (S, &DOptCmp6, 1);
1224         C += RunOptFunc (S, &DOptCmp7, 1);
1225         C += RunOptFunc (S, &DOptCmp9, 1);
1226         C += RunOptFunc (S, &DOptTest1, 1);
1227         C += RunOptFunc (S, &DOptLoad1, 1);
1228         C += RunOptFunc (S, &DOptJumpTarget3, 1);       /* After OptCondBranches2 */
1229         C += RunOptFunc (S, &DOptUnusedLoads, 1);
1230         C += RunOptFunc (S, &DOptUnusedStores, 1);
1231         C += RunOptFunc (S, &DOptDupLoads, 1);
1232         C += RunOptFunc (S, &DOptStoreLoad, 1);
1233         C += RunOptFunc (S, &DOptTransfers1, 1);
1234         C += RunOptFunc (S, &DOptTransfers3, 1);
1235         C += RunOptFunc (S, &DOptTransfers4, 1);
1236         C += RunOptFunc (S, &DOptStore1, 1);
1237         C += RunOptFunc (S, &DOptStore5, 1);
1238         C += RunOptFunc (S, &DOptPushPop, 1);
1239         C += RunOptFunc (S, &DOptPrecalc, 1);
1240
1241         Changes += C;
1242
1243     } while (C);
1244
1245     /* Return the number of changes */
1246     return Changes;
1247 }
1248
1249
1250
1251 static unsigned RunOptGroup4 (CodeSeg* S)
1252 /* Run another round of pattern replacements. These are done late, since there
1253  * may be better replacements before.
1254  */
1255 {
1256     unsigned Changes = 0;
1257
1258     /* Repeat some of the steps here */
1259     Changes += RunOptFunc (S, &DOptShift3, 1);
1260     Changes += RunOptFunc (S, &DOptPush1, 1);
1261     Changes += RunOptFunc (S, &DOptPush2, 1);
1262     Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1263     Changes += RunOptFunc (S, &DOptTest2, 1);
1264     Changes += RunOptFunc (S, &DOptTransfers2, 1);
1265     Changes += RunOptFunc (S, &DOptLoad2, 1);
1266     Changes += RunOptFunc (S, &DOptLoad3, 1);
1267     Changes += RunOptFunc (S, &DOptDupLoads, 1);
1268
1269     /* Return the number of changes */
1270     return Changes;
1271 }
1272
1273
1274
1275 static unsigned RunOptGroup5 (CodeSeg* S)
1276 /* 65C02 specific optimizations. */
1277 {
1278     unsigned Changes = 0;
1279
1280     if (CPUIsets[CPU] & CPU_ISET_65SC02) {
1281         Changes += RunOptFunc (S, &DOpt65C02BitOps, 1);
1282         Changes += RunOptFunc (S, &DOpt65C02Ind, 1);
1283         Changes += RunOptFunc (S, &DOpt65C02Stores, 1);
1284         if (Changes) {
1285             /* The 65C02 replacement codes do often make the use of a register
1286              * value unnecessary, so if we have changes, run another load
1287              * removal pass.
1288              */
1289             Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1290         }
1291     }
1292
1293     /* Return the number of changes */
1294     return Changes;
1295 }
1296
1297
1298
1299 static unsigned RunOptGroup6 (CodeSeg* S)
1300 /* This one is quite special. It tries to replace "lda (sp),y" by "lda (sp,x)".
1301  * The latter is ony cycle slower, but if we're able to remove the necessary
1302  * load of the Y register, because X is zero anyway, we gain 1 cycle and
1303  * shorten the code by one (transfer) or two bytes (load). So what we do is
1304  * to replace the insns, remove unused loads, and then change back all insns
1305  * where Y is still zero (meaning that the load has not been removed).
1306  */
1307 {
1308     unsigned Changes = 0;
1309
1310     /* This group will only run for a standard 6502, because the 65C02 has a
1311      * better addressing mode that covers this case.
1312      */
1313     if ((CPUIsets[CPU] & CPU_ISET_65SC02) == 0) {
1314         Changes += RunOptFunc (S, &DOptIndLoads1, 1);
1315         Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1316         Changes += RunOptFunc (S, &DOptIndLoads2, 1);
1317     }
1318
1319     /* Return the number of changes */
1320     return Changes;
1321 }
1322
1323
1324
1325 static unsigned RunOptGroup7 (CodeSeg* S)
1326 /* The last group of optimization steps. Adjust branches, do size optimizations.
1327  */
1328 {
1329     unsigned Changes = 0;
1330     unsigned C;
1331
1332     /* Optimize for size, that is replace operations by shorter ones, even
1333      * if this does hinder further optimizations (no problem since we're
1334      * done soon).
1335      */
1336     C = RunOptFunc (S, &DOptSize1, 1);
1337     if (C) {
1338         Changes += C;
1339         /* Run some optimization passes again, since the size optimizations
1340          * may have opened new oportunities.
1341          */
1342         Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1343         Changes += RunOptFunc (S, &DOptUnusedStores, 1);
1344         Changes += RunOptFunc (S, &DOptJumpTarget1, 5);
1345         Changes += RunOptFunc (S, &DOptStore5, 1);
1346     }
1347
1348     C = RunOptFunc (S, &DOptSize2, 1);
1349     if (C) {
1350         Changes += C;
1351         /* Run some optimization passes again, since the size optimizations
1352          * may have opened new oportunities.
1353          */
1354         Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1355         Changes += RunOptFunc (S, &DOptJumpTarget1, 5);
1356         Changes += RunOptFunc (S, &DOptStore5, 1);
1357         Changes += RunOptFunc (S, &DOptTransfers1, 1);
1358         Changes += RunOptFunc (S, &DOptTransfers3, 1);
1359     }
1360
1361     /* Adjust branch distances */
1362     Changes += RunOptFunc (S, &DOptBranchDist, 3);
1363
1364     /* Replace conditional branches to RTS. If we had changes, we must run dead
1365      * code elimination again, since the change may have introduced dead code.
1366      */
1367     C = RunOptFunc (S, &DOptRTSJumps2, 1);
1368     Changes += C;
1369     if (C) {
1370         Changes += RunOptFunc (S, &DOptDeadCode, 1);
1371     }
1372
1373     /* Return the number of changes */
1374     return Changes;
1375 }
1376
1377
1378
1379 void RunOpt (CodeSeg* S)
1380 /* Run the optimizer */
1381 {
1382     const char* StatFileName;
1383
1384     /* If we shouldn't run the optimizer, bail out */
1385     if (!S->Optimize) {
1386         return;
1387     }
1388
1389     /* Check if we are requested to write optimizer statistics */
1390     StatFileName = getenv ("CC65_OPTSTATS");
1391     if (StatFileName) {
1392         ReadOptStats (StatFileName);
1393     }
1394
1395     /* Print the name of the function we are working on */
1396     if (S->Func) {
1397         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1398     } else {
1399         Print (stdout, 1, "Running optimizer for global code segment\n");
1400     }
1401
1402     /* If requested, open an output file */
1403     OpenDebugFile (S);
1404     WriteDebugOutput (S, 0);
1405
1406     /* Generate register info for all instructions */
1407     CS_GenRegInfo (S);
1408
1409     /* Run groups of optimizations */
1410     RunOptGroup1 (S);
1411     RunOptGroup2 (S);
1412     RunOptGroup3 (S);
1413     RunOptGroup4 (S);
1414     RunOptGroup5 (S);
1415     RunOptGroup6 (S);
1416     RunOptGroup7 (S);
1417
1418     /* Free register info */
1419     CS_FreeRegInfo (S);
1420
1421     /* Close output file if necessary */
1422     if (DebugOptOutput) {
1423         CloseOutputFile ();
1424     }
1425
1426     /* Write statistics */
1427     if (StatFileName) {
1428         WriteOptStats (StatFileName);
1429     }
1430 }
1431
1432
1433