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