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