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