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