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