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  *      clc
 794  *      adc     xxx
 795  *      tay
 796  *      txa
 797  *      adc     yyy
 798  *      tax
 799  *      tya
 800  *      ldy
 801  *      jsr     ldauidx
 802  *
 803  * and replace it by:
 804  *
 805  *      clc
 806  *      adc     xxx
 807  *      sta     ptr1
 808  *      txa
 809  *      adc     yyy
 810  *      sta     ptr1+1
 811  *      ldy
 812  *      ldx     #$00
 813  *      lda     (ptr1),y
 814  */
 815 {
 816     unsigned Changes = 0;
 817
 818     /* Walk over the entries */
 819     unsigned I = 0;
 820     while (I < CS_GetEntryCount (S)) {
 821
 822         CodeEntry* L[9];
 823
 824         /* Get next entry */
 825         L[0] = CS_GetEntry (S, I);
 826
 827         /* Check for the sequence */
 828         if (L[0]->OPC == OP65_CLC               &&
 829             CS_GetEntries (S, L+1, I+1, 8)      &&
 830             L[1]->OPC == OP65_ADC               &&
 831             !CE_HasLabel (L[1])                 &&
 832             L[2]->OPC == OP65_TAY               &&
 833             !CE_HasLabel (L[2])                 &&
 834             L[3]->OPC == OP65_TXA               &&
 835             !CE_HasLabel (L[3])                 &&
 836             L[4]->OPC == OP65_ADC               &&
 837             !CE_HasLabel (L[4])                 &&
 838             L[5]->OPC == OP65_TAX               &&
 839             !CE_HasLabel (L[5])                 &&
 840             L[6]->OPC == OP65_TYA               &&
 841             !CE_HasLabel (L[6])                 &&
 842             L[7]->OPC == OP65_LDY               &&
 843             !CE_HasLabel (L[7])                 &&
 844             CE_IsCall (L[8], "ldauidx")         &&
 845             !CE_HasLabel (L[8])) {
 846
 847             CodeEntry* X;
 848             CodeEntry* P;
 849
 850             /* Store the low byte and remove the TAY instead */
 851             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[1]->LI);
 852             CS_InsertEntry (S, X, I+2);
 853             CS_DelEntry (S, I+3);
 854
 855             /* Store the high byte */
 856             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[4]->LI);
 857             CS_InsertEntry (S, X, I+5);
 858
 859             /* If the instruction before the adc is a ldx, replace the
 860              * txa by and lda with the same location of the ldx.
 861              */
 862             if ((P = CS_GetPrevEntry (S, I)) != 0 &&
 863                 P->OPC == OP65_LDX                &&
 864                 !CE_HasLabel (P)) {
 865
 866                 X = NewCodeEntry (OP65_LDA, P->AM, P->Arg, 0, P->LI);
 867                 CS_InsertEntry (S, X, I+4);
 868                 CS_DelEntry (S, I+3);
 869             }
 870
 871             /* Delete more transfer insns */
 872             CS_DelEntry (S, I+7);
 873             CS_DelEntry (S, I+6);
 874
 875             /* Delete the call to ldauidx */
 876             CS_DelEntry (S, I+7);
 877
 878             /* Load high and low byte */
 879             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[7]->LI);
 880             CS_InsertEntry (S, X, I+7);
 881             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[7]->LI);
 882             CS_InsertEntry (S, X, I+8);
 883
 884             /* Remember, we had changes */
 885             ++Changes;
 886
 887         }
 888
 889         /* Next entry */
 890         ++I;
 891
 892     }
 893
 894     /* Return the number of changes made */
 895     return Changes;
 896 }
 897
 898
 899
 900 static unsigned OptPtrLoad3 (CodeSeg* S)
 901 /* Search for the sequence:
 902  *
 903  *      adc     xxx
 904  *      pha
 905  *      txa
 906  *      iny
 907  *      adc     yyy
 908  *      tax
 909  *      pla
 910  *      ldy
 911  *      jsr     ldauidx
 912  *
 913  * and replace it by:
 914  *
 915  *      adc     xxx
 916  *      sta     ptr1
 917  *      txa
 918  *      iny
 919  *      adc     yyy
 920  *      sta     ptr1+1
 921  *      ldy
 922  *      ldx     #$00
 923  *      lda     (ptr1),y
 924  */
 925 {
 926     unsigned Changes = 0;
 927
 928     /* Walk over the entries */
 929     unsigned I = 0;
 930     while (I < CS_GetEntryCount (S)) {
 931
 932         CodeEntry* L[9];
 933
 934         /* Get next entry */
 935         L[0] = CS_GetEntry (S, I);
 936
 937         /* Check for the sequence */
 938         if (L[0]->OPC == OP65_ADC               &&
 939             CS_GetEntries (S, L+1, I+1, 8)      &&
 940             L[1]->OPC == OP65_PHA               &&
 941             !CE_HasLabel (L[1])                 &&
 942             L[2]->OPC == OP65_TXA               &&
 943             !CE_HasLabel (L[2])                 &&
 944             L[3]->OPC == OP65_INY               &&
 945             !CE_HasLabel (L[3])                 &&
 946             L[4]->OPC == OP65_ADC               &&
 947             !CE_HasLabel (L[4])                 &&
 948             L[5]->OPC == OP65_TAX               &&
 949             !CE_HasLabel (L[5])                 &&
 950             L[6]->OPC == OP65_PLA               &&
 951             !CE_HasLabel (L[6])                 &&
 952             L[7]->OPC == OP65_LDY               &&
 953             !CE_HasLabel (L[7])                 &&
 954             CE_IsCall (L[8], "ldauidx")         &&
 955             !CE_HasLabel (L[8])) {
 956
 957             CodeEntry* X;
 958
 959             /* Store the low byte and remove the PHA instead */
 960             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
 961             CS_InsertEntry (S, X, I+1);
 962             CS_DelEntry (S, I+2);
 963
 964             /* Store the high byte */
 965             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[4]->LI);
 966             CS_InsertEntry (S, X, I+5);
 967
 968             /* Delete more transfer and PLA insns */
 969             CS_DelEntry (S, I+7);
 970             CS_DelEntry (S, I+6);
 971
 972             /* Delete the call to ldauidx */
 973             CS_DelEntry (S, I+7);
 974
 975             /* Load high and low byte */
 976             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
 977             CS_InsertEntry (S, X, I+7);
 978             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
 979             CS_InsertEntry (S, X, I+8);
 980
 981             /* Remember, we had changes */
 982             ++Changes;
 983
 984         }
 985
 986         /* Next entry */
 987         ++I;
 988
 989     }
 990
 991     /* Return the number of changes made */
 992     return Changes;
 993 }
 994
 995
 996
 997 static unsigned OptPtrLoad4 (CodeSeg* S)
 998 /* Search for the sequence:
 999  *
1000  *      lda     #<(label+0)
1001  *      ldx     #>(label+0)
1002  *      clc
1003  *      adc     xxx
1004  *      bcc     L
1005  *      inx
1006  * L:   ldy     #$00
1007  *      jsr     ldauidx
1008  *
1009  * and replace it by:
1010  *
1011  *      ldy     xxx
1012  *      ldx     #$00
1013  *      lda     label,y
1014  */
1015 {
1016     unsigned Changes = 0;
1017
1018     /* Walk over the entries */
1019     unsigned I = 0;
1020     while (I < CS_GetEntryCount (S)) {
1021
1022         CodeEntry* L[8];
1023         unsigned Len;
1024
1025         /* Get next entry */
1026         L[0] = CS_GetEntry (S, I);
1027
1028         /* Check for the sequence */
1029         if (L[0]->OPC == OP65_LDA                            &&
1030             L[0]->AM == AM65_IMM                             &&
1031             CS_GetEntries (S, L+1, I+1, 7)                   &&
1032             L[1]->OPC == OP65_LDX                            &&
1033             L[1]->AM == AM65_IMM                             &&
1034             !CE_HasLabel (L[1])                              &&
1035             L[2]->OPC == OP65_CLC                            &&
1036             !CE_HasLabel (L[2])                              &&
1037             L[3]->OPC == OP65_ADC                            &&
1038             (L[3]->AM == AM65_ABS || L[3]->AM == AM65_ZP)    &&
1039             !CE_HasLabel (L[3])                              &&
1040             (L[4]->OPC == OP65_BCC || L[4]->OPC == OP65_JCC) &&
1041             L[4]->JumpTo != 0                                &&
1042             L[4]->JumpTo->Owner == L[6]                      &&
1043             !CE_HasLabel (L[4])                              &&
1044             L[5]->OPC == OP65_INX                            &&
1045             !CE_HasLabel (L[5])                              &&
1046             L[6]->OPC == OP65_LDY                            &&
1047             CE_KnownImm (L[6])                               &&
1048             L[6]->Num == 0                                   &&
1049             CE_IsCall (L[7], "ldauidx")                      &&
1050             !CE_HasLabel (L[7])                              &&
1051             /* Check the label last because this is quite costly */
1052             (Len = strlen (L[0]->Arg)) > 3                   &&
1053             L[0]->Arg[0] == '<'                              &&
1054             L[0]->Arg[1] == '('                              &&
1055             strlen (L[1]->Arg) == Len                        &&
1056             L[1]->Arg[0] == '>'                              &&
1057             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
1058
1059             CodeEntry* X;
1060             char* Label;
1061
1062             /* We will create all the new stuff behind the current one so
1063              * we keep the line references.
1064              */
1065             X = NewCodeEntry (OP65_LDY, L[3]->AM, L[3]->Arg, 0, L[0]->LI);
1066             CS_InsertEntry (S, X, I+8);
1067
1068             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1069             CS_InsertEntry (S, X, I+9);
1070
1071             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
1072             Label[Len-3] = '\0';
1073             X = NewCodeEntry (OP65_LDA, AM65_ABSY, Label, 0, L[0]->LI);
1074             CS_InsertEntry (S, X, I+10);
1075             xfree (Label);
1076
1077             /* Remove the old code */
1078             CS_DelEntries (S, I, 8);
1079
1080             /* Remember, we had changes */
1081             ++Changes;
1082
1083         }
1084
1085         /* Next entry */
1086         ++I;
1087
1088     }
1089
1090     /* Return the number of changes made */
1091     return Changes;
1092 }
1093
1094
1095
1096 static unsigned OptPtrLoad5 (CodeSeg* S)
1097 /* Search for the sequence:
1098  *
1099  *      lda     #<(label+0)
1100  *      ldx     #>(label+0)
1101  *      ldy     #$xx
1102  *      clc
1103  *      adc     (sp),y
1104  *      bcc     L
1105  *      inx
1106  * L:   ldy     #$00
1107  *      jsr     ldauidx
1108  *
1109  * and replace it by:
1110  *
1111  *      ldy     #$xx
1112  *      lda     (sp),y
1113  *      tay
1114  *      ldx     #$00
1115  *      lda     label,y
1116  */
1117 {
1118     unsigned Changes = 0;
1119
1120     /* Walk over the entries */
1121     unsigned I = 0;
1122     while (I < CS_GetEntryCount (S)) {
1123
1124         CodeEntry* L[9];
1125         unsigned Len;
1126
1127         /* Get next entry */
1128         L[0] = CS_GetEntry (S, I);
1129
1130         /* Check for the sequence */
1131         if (L[0]->OPC == OP65_LDA                            &&
1132             L[0]->AM == AM65_IMM                             &&
1133             CS_GetEntries (S, L+1, I+1, 8)                   &&
1134             L[1]->OPC == OP65_LDX                            &&
1135             L[1]->AM == AM65_IMM                             &&
1136             !CE_HasLabel (L[1])                              &&
1137             L[2]->OPC == OP65_LDY                            &&
1138             CE_KnownImm (L[2])                               &&
1139             !CE_HasLabel (L[2])                              &&
1140             L[3]->OPC == OP65_CLC                            &&
1141             !CE_HasLabel (L[3])                              &&
1142             L[4]->OPC == OP65_ADC                            &&
1143             L[4]->AM == AM65_ZP_INDY                         &&
1144             !CE_HasLabel (L[4])                              &&
1145             (L[5]->OPC == OP65_BCC || L[5]->OPC == OP65_JCC) &&
1146             L[5]->JumpTo != 0                                &&
1147             L[5]->JumpTo->Owner == L[7]                      &&
1148             !CE_HasLabel (L[5])                              &&
1149             L[6]->OPC == OP65_INX                            &&
1150             !CE_HasLabel (L[6])                              &&
1151             L[7]->OPC == OP65_LDY                            &&
1152             CE_KnownImm (L[7])                               &&
1153             L[7]->Num == 0                                   &&
1154             CE_IsCall (L[8], "ldauidx")                      &&
1155             !CE_HasLabel (L[8])                              &&
1156             /* Check the label last because this is quite costly */
1157             (Len = strlen (L[0]->Arg)) > 3                   &&
1158             L[0]->Arg[0] == '<'                              &&
1159             L[0]->Arg[1] == '('                              &&
1160             strlen (L[1]->Arg) == Len                        &&
1161             L[1]->Arg[0] == '>'                              &&
1162             memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
1163
1164             CodeEntry* X;
1165             char* Label;
1166
1167             /* Add the lda */
1168             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, L[4]->Arg, 0, L[0]->LI);
1169             CS_InsertEntry (S, X, I+3);
1170
1171             /* Add the tay */
1172             X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, L[0]->LI);
1173             CS_InsertEntry (S, X, I+4);
1174
1175             /* Add the ldx */
1176             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1177             CS_InsertEntry (S, X, I+5);
1178
1179             /* Add the lda */
1180             Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
1181             Label[Len-3] = '\0';
1182             X = NewCodeEntry (OP65_LDA, AM65_ABSY, Label, 0, L[0]->LI);
1183             CS_InsertEntry (S, X, I+6);
1184             xfree (Label);
1185
1186             /* Remove the old code */
1187             CS_DelEntries (S, I, 2);
1188             CS_DelEntries (S, I+5, 6);
1189
1190             /* Remember, we had changes */
1191             ++Changes;
1192
1193         }
1194
1195         /* Next entry */
1196         ++I;
1197
1198     }
1199
1200     /* Return the number of changes made */
1201     return Changes;
1202 }
1203
1204
1205
1206 static unsigned OptPtrLoad6 (CodeSeg* S)
1207 /* Search for the sequence
1208  *
1209  *      ldy     ...
1210  *      jsr     ldauidx
1211  *
1212  * and replace it by:
1213  *
1214  *      ldy     ...
1215  *      stx     ptr1+1
1216  *      sta     ptr1
1217  *      ldx     #$00
1218  *      lda     (ptr1),y
1219  *
1220  * This step must be execute *after* OptPtrLoad1!
1221  */
1222 {
1223     unsigned Changes = 0;
1224
1225     /* Walk over the entries */
1226     unsigned I = 0;
1227     while (I < CS_GetEntryCount (S)) {
1228
1229         CodeEntry* L[2];
1230
1231         /* Get next entry */
1232         L[0] = CS_GetEntry (S, I);
1233
1234         /* Check for the sequence */
1235         if (L[0]->OPC == OP65_LDY               &&
1236             CS_GetEntries (S, L+1, I+1, 1)      &&
1237             CE_IsCall (L[1], "ldauidx")         &&
1238             !CE_HasLabel (L[1])) {
1239
1240             CodeEntry* X;
1241
1242             /* Store the high byte */
1243             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1244             CS_InsertEntry (S, X, I+1);
1245
1246             /* Store the low byte */
1247             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1248             CS_InsertEntry (S, X, I+2);
1249
1250             /* Delete the call to ldauidx */
1251             CS_DelEntry (S, I+3);
1252
1253             /* Load the high and low byte */
1254             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1255             CS_InsertEntry (S, X, I+3);
1256             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
1257             CS_InsertEntry (S, X, I+4);
1258
1259             /* Remember, we had changes */
1260             ++Changes;
1261
1262         }
1263
1264         /* Next entry */
1265         ++I;
1266
1267     }
1268
1269     /* Return the number of changes made */
1270     return Changes;
1271 }
1272
1273
1274
1275 /*****************************************************************************/
1276 /*                            Decouple operations                            */
1277 /*****************************************************************************/
1278
1279
1280
1281 static unsigned OptDecouple (CodeSeg* S)
1282 /* Decouple operations, that is, do the following replacements:
1283  *
1284  *   dex  -> ldx
1285  *   inx  -> ldx
1286  *   dey  -> ldy
1287  *   iny  -> ldy
1288  *   tax  -> ldx
1289  *   txa  -> lda
1290  *   tay  -> ldy
1291  *   tya  -> lda
1292  *
1293  * Provided that the register values are known of course.
1294  */
1295 {
1296     unsigned Changes = 0;
1297     unsigned I;
1298
1299     /* Generate register info for the following step */
1300     CS_GenRegInfo (S);
1301
1302     /* Walk over the entries */
1303     I = 0;
1304     while (I < CS_GetEntryCount (S)) {
1305
1306         char Buf [16];
1307
1308         /* Get next entry */
1309         CodeEntry* E = CS_GetEntry (S, I);
1310
1311         /* Assume we have no replacement */
1312         CodeEntry* X = 0;
1313
1314         /* Check the instruction */
1315         switch (E->OPC) {
1316
1317             case OP65_DEX:
1318                 if (E->RI->In.RegX >= 0) {
1319                     xsprintf (Buf, sizeof (Buf), "$%02X", (E->RI->In.RegX - 1) & 0xFF);
1320                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, E->LI);
1321                 }
1322                 break;
1323
1324             case OP65_DEY:
1325                 if (E->RI->In.RegY >= 0) {
1326                     xsprintf (Buf, sizeof (Buf), "$%02X", (E->RI->In.RegY - 1) & 0xFF);
1327                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, E->LI);
1328                 }
1329                 break;
1330
1331             case OP65_INX:
1332                 if (E->RI->In.RegX >= 0) {
1333                     xsprintf (Buf, sizeof (Buf), "$%02X", (E->RI->In.RegX + 1) & 0xFF);
1334                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, E->LI);
1335                 }
1336                 break;
1337
1338             case OP65_INY:
1339                 if (E->RI->In.RegY >= 0) {
1340                     xsprintf (Buf, sizeof (Buf), "$%02X", (E->RI->In.RegY + 1) & 0xFF);
1341                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, E->LI);
1342                 }
1343                 break;
1344
1345             case OP65_TAX:
1346                 if (E->RI->In.RegA >= 0) {
1347                     xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegA);
1348                     X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, E->LI);
1349                 }
1350                 break;
1351
1352             case OP65_TAY:
1353                 if (E->RI->In.RegA >= 0) {
1354                     xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegA);
1355                     X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, E->LI);
1356                 }
1357                 break;
1358
1359             case OP65_TXA:
1360                 if (E->RI->In.RegX >= 0) {
1361                     xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegX);
1362                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Buf, 0, E->LI);
1363                 }
1364                 break;
1365
1366             case OP65_TYA:
1367                 if (E->RI->In.RegY >= 0) {
1368                     xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegY);
1369                     X = NewCodeEntry (OP65_LDA, AM65_IMM, Buf, 0, E->LI);
1370                 }
1371                 break;
1372
1373             default:
1374                 /* Avoid gcc warnings */
1375                 break;
1376
1377         }
1378
1379         /* Insert the replacement if we have one */
1380         if (X) {
1381             CS_InsertEntry (S, X, I+1);
1382             CS_DelEntry (S, I);
1383             ++Changes;
1384         }
1385
1386         /* Next entry */
1387         ++I;
1388
1389     }
1390
1391     /* Free register info */
1392     CS_FreeRegInfo (S);
1393
1394     /* Return the number of changes made */
1395     return Changes;
1396 }
1397
1398
1399
1400 /*****************************************************************************/
1401 /*                             Size optimization                             */
1402 /*****************************************************************************/
1403
1404
1405
1406 static unsigned OptSize (CodeSeg* S)
1407 /* Do size optimization by using shorter code sequences, even if this
1408  * introduces relations between instructions. This step must be one of the
1409  * last steps, because it makes further work much more difficult.
1410  */
1411 {
1412     unsigned Changes = 0;
1413     unsigned I;
1414
1415     /* Generate register info for the following step */
1416     CS_GenRegInfo (S);
1417
1418     /* Walk over the entries */
1419     I = 0;
1420     while (I < CS_GetEntryCount (S)) {
1421
1422
1423         /* Get next entry */
1424         CodeEntry* E = CS_GetEntry (S, I);
1425
1426         /* Assume we have no replacement */
1427         CodeEntry* X = 0;
1428
1429         /* Check the instruction */
1430         switch (E->OPC) {
1431
1432             case OP65_LDA:
1433                 if (CE_KnownImm (E)) {
1434                     short Val = (short) E->Num;
1435                     if (Val == E->RI->In.RegX) {
1436                         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, E->LI);
1437                     } else if (Val == E->RI->In.RegY) {
1438                         X = NewCodeEntry (OP65_TYA, AM65_IMP, 0, 0, E->LI);
1439                     } else if (E->RI->In.RegA >= 0 && CPU >= CPU_65C02) {
1440                         if (Val == ((E->RI->In.RegA - 1) & 0xFF)) {
1441                             X = NewCodeEntry (OP65_DEA, AM65_IMP, 0, 0, E->LI);
1442                         } else if (Val == ((E->RI->In.RegA + 1) & 0xFF)) {
1443                             X = NewCodeEntry (OP65_INA, AM65_IMP, 0, 0, E->LI);
1444                         }
1445                     }
1446                 }
1447                 break;
1448
1449             case OP65_LDX:
1450                 if (CE_KnownImm (E)) {
1451                     short Val = (short) E->Num;
1452                     if (E->RI->In.RegX >= 0 && Val == ((E->RI->In.RegX - 1) & 0xFF)) {
1453                         X = NewCodeEntry (OP65_DEX, AM65_IMP, 0, 0, E->LI);
1454                     } else if (E->RI->In.RegX >= 0 && Val == ((E->RI->In.RegX + 1) & 0xFF)) {
1455                         X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, E->LI);
1456                     } else if (Val == E->RI->In.RegA) {
1457                         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, E->LI);
1458                     }
1459                 }
1460                 break;
1461
1462             case OP65_LDY:
1463                 if (CE_KnownImm (E)) {
1464                     short Val = (short) E->Num;
1465                     if (E->RI->In.RegY >= 0 && Val == ((E->RI->In.RegY - 1) & 0xFF)) {
1466                         X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, E->LI);
1467                     } else if (E->RI->In.RegY >= 0 && Val == ((E->RI->In.RegY + 1) & 0xFF)) {
1468                         X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, E->LI);
1469                     } else if (Val == E->RI->In.RegA) {
1470                         X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, E->LI);
1471                     }
1472                 }
1473                 break;
1474
1475             default:
1476                 /* Avoid gcc warnings */
1477                 break;
1478
1479         }
1480
1481         /* Insert the replacement if we have one */
1482         if (X) {
1483             CS_InsertEntry (S, X, I+1);
1484             CS_DelEntry (S, I);
1485             ++Changes;
1486         }
1487
1488         /* Next entry */
1489         ++I;
1490
1491     }
1492
1493     /* Free register info */
1494     CS_FreeRegInfo (S);
1495
1496     /* Return the number of changes made */
1497     return Changes;
1498 }
1499
1500
1501
1502 /*****************************************************************************/
1503 /*                              struct OptFunc                               */
1504 /*****************************************************************************/
1505
1506
1507
1508 typedef struct OptFunc OptFunc;
1509 struct OptFunc {
1510     unsigned       (*Func) (CodeSeg*);  /* Optimizer function */
1511     const char*    Name;                /* Name of the function/group */
1512     unsigned long  TotalRuns;           /* Total number of runs */
1513     unsigned long  LastRuns;            /* Last number of runs */
1514     unsigned long  TotalChanges;        /* Total number of changes */
1515     unsigned long  LastChanges;         /* Last number of changes */
1516     char           Disabled;            /* True if function disabled */
1517 };
1518
1519
1520
1521 /*****************************************************************************/
1522 /*                                   Code                                    */
1523 /*****************************************************************************/
1524
1525
1526
1527 /* Macro that builds a function description */
1528 #define OptFuncEntry(func) static OptFuncDesc D##func = { func, #func, 0 }
1529
1530 /* A list of all the function descriptions */
1531 static OptFunc DOptAdd1         = { OptAdd1,         "OptAdd1",         0, 0, 0, 0, 0 };
1532 static OptFunc DOptAdd2         = { OptAdd2,         "OptAdd2",         0, 0, 0, 0, 0 };
1533 static OptFunc DOptAdd3         = { OptAdd3,         "OptAdd3",         0, 0, 0, 0, 0 };
1534 static OptFunc DOptBoolTrans    = { OptBoolTrans,    "OptBoolTrans",    0, 0, 0, 0, 0 };
1535 static OptFunc DOptBranchDist   = { OptBranchDist,   "OptBranchDist",   0, 0, 0, 0, 0 };
1536 static OptFunc DOptCmp1         = { OptCmp1,         "OptCmp1",         0, 0, 0, 0, 0 };
1537 static OptFunc DOptCmp2         = { OptCmp2,         "OptCmp2",         0, 0, 0, 0, 0 };
1538 static OptFunc DOptCmp3         = { OptCmp3,         "OptCmp3",         0, 0, 0, 0, 0 };
1539 static OptFunc DOptCmp4         = { OptCmp4,         "OptCmp4",         0, 0, 0, 0, 0 };
1540 static OptFunc DOptCmp5         = { OptCmp5,         "OptCmp5",         0, 0, 0, 0, 0 };
1541 static OptFunc DOptCmp6         = { OptCmp6,         "OptCmp6",         0, 0, 0, 0, 0 };
1542 static OptFunc DOptCmp7         = { OptCmp7,         "OptCmp7",         0, 0, 0, 0, 0 };
1543 static OptFunc DOptCondBranches = { OptCondBranches, "OptCondBranches", 0, 0, 0, 0, 0 };
1544 static OptFunc DOptDeadCode     = { OptDeadCode,     "OptDeadCode",     0, 0, 0, 0, 0 };
1545 static OptFunc DOptDeadJumps    = { OptDeadJumps,    "OptDeadJumps",    0, 0, 0, 0, 0 };
1546 static OptFunc DOptDecouple     = { OptDecouple,     "OptDecouple",     0, 0, 0, 0, 0 };
1547 static OptFunc DOptDupLoads     = { OptDupLoads,     "OptDupLoads",     0, 0, 0, 0, 0 };
1548 static OptFunc DOptJumpCascades = { OptJumpCascades, "OptJumpCascades", 0, 0, 0, 0, 0 };
1549 static OptFunc DOptJumpTarget   = { OptJumpTarget,   "OptJumpTarget",   0, 0, 0, 0, 0 };
1550 static OptFunc DOptRTS          = { OptRTS,          "OptRTS",          0, 0, 0, 0, 0 };
1551 static OptFunc DOptRTSJumps     = { OptRTSJumps,     "OptRTSJumps",     0, 0, 0, 0, 0 };
1552 static OptFunc DOptNegA1        = { OptNegA1,        "OptNegA1",        0, 0, 0, 0, 0 };
1553 static OptFunc DOptNegA2        = { OptNegA2,        "OptNegA2",        0, 0, 0, 0, 0 };
1554 static OptFunc DOptNegAX1       = { OptNegAX1,       "OptNegAX1",       0, 0, 0, 0, 0 };
1555 static OptFunc DOptNegAX2       = { OptNegAX2,       "OptNegAX2",       0, 0, 0, 0, 0 };
1556 static OptFunc DOptNegAX3       = { OptNegAX3,       "OptNegAX3",       0, 0, 0, 0, 0 };
1557 static OptFunc DOptNegAX4       = { OptNegAX4,       "OptNegAX4",       0, 0, 0, 0, 0 };
1558 static OptFunc DOptPtrLoad1     = { OptPtrLoad1,     "OptPtrLoad1",     0, 0, 0, 0, 0 };
1559 static OptFunc DOptPtrLoad2     = { OptPtrLoad2,     "OptPtrLoad2",     0, 0, 0, 0, 0 };
1560 static OptFunc DOptPtrLoad3     = { OptPtrLoad3,     "OptPtrLoad3",     0, 0, 0, 0, 0 };
1561 static OptFunc DOptPtrLoad4     = { OptPtrLoad4,     "OptPtrLoad4",     0, 0, 0, 0, 0 };
1562 static OptFunc DOptPtrLoad5     = { OptPtrLoad5,     "OptPtrLoad5",     0, 0, 0, 0, 0 };
1563 static OptFunc DOptPtrLoad6     = { OptPtrLoad6,     "OptPtrLoad6",     0, 0, 0, 0, 0 };
1564 static OptFunc DOptPtrStore1    = { OptPtrStore1,    "OptPtrStore1",    0, 0, 0, 0, 0 };
1565 static OptFunc DOptPtrStore2    = { OptPtrStore2,    "OptPtrStore2",    0, 0, 0, 0, 0 };
1566 static OptFunc DOptShift1       = { OptShift1,       "OptShift1",       0, 0, 0, 0, 0 };
1567 static OptFunc DOptSize         = { OptSize,         "OptSize",         0, 0, 0, 0, 0 };
1568 static OptFunc DOptStackOps     = { OptStackOps,     "OptStackOps",     0, 0, 0, 0, 0 };
1569 static OptFunc DOptStoreLoad    = { OptStoreLoad,    "OptStoreLoad",    0, 0, 0, 0, 0 };
1570 static OptFunc DOptSub1         = { OptSub1,         "OptSub1",         0, 0, 0, 0, 0 };
1571 static OptFunc DOptSub2         = { OptSub2,         "OptSub2",         0, 0, 0, 0, 0 };
1572 static OptFunc DOptTest1        = { OptTest1,        "OptTest1",        0, 0, 0, 0, 0 };
1573 static OptFunc DOptTransfers    = { OptTransfers,    "OptTransfers",    0, 0, 0, 0, 0 };
1574 static OptFunc DOptUnusedLoads  = { OptUnusedLoads,  "OptUnusedLoads",  0, 0, 0, 0, 0 };
1575 static OptFunc DOptUnusedStores = { OptUnusedStores, "OptUnusedStores", 0, 0, 0, 0, 0 };
1576
1577
1578 /* Table containing all the steps in alphabetical order */
1579 static OptFunc* OptFuncs[] = {
1580     &DOptAdd1,
1581     &DOptAdd2,
1582     &DOptAdd3,
1583     &DOptBoolTrans,
1584     &DOptBranchDist,
1585     &DOptCmp1,
1586     &DOptCmp2,
1587     &DOptCmp3,
1588     &DOptCmp4,
1589     &DOptCmp5,
1590     &DOptCmp6,
1591     &DOptCmp7,
1592     &DOptCondBranches,
1593     &DOptDeadCode,
1594     &DOptDeadJumps,
1595     &DOptDecouple,
1596     &DOptDupLoads,
1597     &DOptJumpCascades,
1598     &DOptJumpTarget,
1599     &DOptNegA1,
1600     &DOptNegA2,
1601     &DOptNegAX1,
1602     &DOptNegAX2,
1603     &DOptNegAX3,
1604     &DOptNegAX4,
1605     &DOptPtrStore1,
1606     &DOptPtrStore2,
1607     &DOptPtrLoad1,
1608     &DOptPtrLoad2,
1609     &DOptPtrLoad3,
1610     &DOptPtrLoad4,
1611     &DOptPtrLoad5,
1612     &DOptPtrLoad6,
1613     &DOptRTS,
1614     &DOptRTSJumps,
1615     &DOptShift1,
1616     &DOptSize,
1617     &DOptSub1,
1618     &DOptSub2,
1619     &DOptStackOps,
1620     &DOptStoreLoad,
1621     &DOptTest1,
1622     &DOptTransfers,
1623     &DOptUnusedLoads,
1624     &DOptUnusedStores,
1625 };
1626 #define OPTFUNC_COUNT  (sizeof(OptFuncs) / sizeof(OptFuncs[0]))
1627
1628
1629
1630 static int CmpOptStep (const void* Key, const void* Func)
1631 /* Compare function for bsearch */
1632 {
1633     return strcmp (Key, (*(const OptFunc**)Func)->Name);
1634 }
1635
1636
1637
1638 static OptFunc* FindOptFunc (const char* Name)
1639 /* Find an optimizer step by name in the table and return a pointer. Return
1640  * NULL if no such step is found.
1641  */
1642 {
1643     /* Search for the function in the list */
1644     OptFunc** O = bsearch (Name, OptFuncs, OPTFUNC_COUNT, sizeof (OptFuncs[0]), CmpOptStep);
1645     return O? *O : 0;
1646 }
1647
1648
1649
1650 static OptFunc* GetOptFunc (const char* Name)
1651 /* Find an optimizer step by name in the table and return a pointer. Print an
1652  * error and call AbEnd if not found.
1653  */
1654 {
1655     /* Search for the function in the list */
1656     OptFunc* F = FindOptFunc (Name);
1657     if (F == 0) {
1658         /* Not found */
1659         AbEnd ("Optimization step `%s' not found", Name);
1660     }
1661     return F;
1662 }
1663
1664
1665
1666 void DisableOpt (const char* Name)
1667 /* Disable the optimization with the given name */
1668 {
1669     if (strcmp (Name, "any") == 0) {
1670         unsigned I;
1671         for (I = 0; I < OPTFUNC_COUNT; ++I) {
1672             OptFuncs[I]->Disabled = 1;
1673         }
1674     } else {
1675         GetOptFunc(Name)->Disabled = 1;
1676     }
1677 }
1678
1679
1680
1681 void EnableOpt (const char* Name)
1682 /* Enable the optimization with the given name */
1683 {
1684     if (strcmp (Name, "any") == 0) {
1685         unsigned I;
1686         for (I = 0; I < OPTFUNC_COUNT; ++I) {
1687             OptFuncs[I]->Disabled = 0;
1688         }
1689     } else {
1690         GetOptFunc(Name)->Disabled = 0;
1691     }
1692 }
1693
1694
1695
1696 void ListOptSteps (FILE* F)
1697 /* List all optimization steps */
1698 {
1699     unsigned I;
1700     for (I = 0; I < OPTFUNC_COUNT; ++I) {
1701         fprintf (F, "%s\n", OptFuncs[I]->Name);
1702     }
1703 }
1704
1705
1706
1707 static void ReadOptStats (const char* Name)
1708 /* Read the optimizer statistics file */
1709 {
1710     char Buf [256];
1711     unsigned Lines;
1712
1713     /* Try to open the file */
1714     FILE* F = fopen (Name, "r");
1715     if (F == 0) {
1716         /* Ignore the error */
1717         return;
1718     }
1719
1720     /* Read and parse the lines */
1721     Lines = 0;
1722     while (fgets (Buf, sizeof (Buf), F) != 0) {
1723
1724         char* B;
1725         unsigned Len;
1726         OptFunc* Func;
1727
1728         /* Fields */
1729         char Name[32];
1730         unsigned long  TotalRuns;
1731         unsigned long  TotalChanges;
1732
1733         /* Count lines */
1734         ++Lines;
1735
1736         /* Remove trailing white space including the line terminator */
1737         B = Buf;
1738         Len = strlen (B);
1739         while (Len > 0 && IsSpace (B[Len-1])) {
1740             --Len;
1741         }
1742         B[Len] = '\0';
1743
1744         /* Remove leading whitespace */
1745         while (IsSpace (*B)) {
1746             ++B;
1747         }
1748
1749         /* Check for empty and comment lines */
1750         if (*B == '\0' || *B == ';' || *B == '#') {
1751             continue;
1752         }
1753
1754         /* Parse the line */
1755         if (sscanf (B, "%31s %lu %*u %lu %*u", Name, &TotalRuns, &TotalChanges) != 3) {
1756             /* Syntax error */
1757             continue;
1758         }
1759
1760         /* Search for the optimizer step. */
1761         Func = FindOptFunc (Name);
1762         if (Func == 0) {
1763             /* Not found */
1764             continue;
1765         }
1766
1767         /* Found the step, set the fields */
1768         Func->TotalRuns    = TotalRuns;
1769         Func->TotalChanges = TotalChanges;
1770
1771     }
1772
1773     /* Close the file, ignore errors here. */
1774     fclose (F);
1775 }
1776
1777
1778
1779 static void WriteOptStats (const char* Name)
1780 /* Write the optimizer statistics file */
1781 {
1782     unsigned I;
1783
1784     /* Try to open the file */
1785     FILE* F = fopen (Name, "w");
1786     if (F == 0) {
1787         /* Ignore the error */
1788         return;
1789     }
1790
1791     /* Write the file */
1792     for (I = 0; I < OPTFUNC_COUNT; ++I) {
1793         const OptFunc* O = OptFuncs[I];
1794         fprintf (F,
1795                  "%-20s %6lu %6lu %6lu %6lu\n",
1796                  O->Name,
1797                  O->TotalRuns,
1798                  O->LastRuns,
1799                  O->TotalChanges,
1800                  O->LastChanges);
1801     }
1802
1803     /* Close the file, ignore errors here. */
1804     fclose (F);
1805 }
1806
1807
1808
1809 static unsigned RunOptFunc (CodeSeg* S, OptFunc* F, unsigned Max)
1810 /* Run one optimizer function Max times or until there are no more changes */
1811 {
1812     unsigned Changes, C;
1813
1814     /* Don't run the function if it is disabled */
1815     if (F->Disabled) {
1816         return 0;
1817     }
1818
1819     /* Run this until there are no more changes */
1820     Changes = 0;
1821     do {
1822
1823         /* Run the function */
1824         C = F->Func (S);
1825         Changes += C;
1826
1827         /* Do statistics */
1828         ++F->TotalRuns;
1829         ++F->LastRuns;
1830         F->TotalChanges += C;
1831         F->LastChanges  += C;
1832
1833     } while (--Max && C > 0);
1834
1835     /* Return the number of changes */
1836     return Changes;
1837 }
1838
1839
1840
1841 static void RunOptGroup1 (CodeSeg* S)
1842 /* Run the first group of optimization steps. These steps translate known
1843  * patterns emitted by the code generator into more optimal patterns. Order
1844  * of the steps is important, because some of the steps done earlier cover
1845  * the same patterns as later steps as subpatterns.
1846  */
1847 {
1848     RunOptFunc (S, &DOptPtrStore1, 1);
1849     RunOptFunc (S, &DOptPtrStore2, 1);
1850     RunOptFunc (S, &DOptPtrLoad1, 1);
1851     RunOptFunc (S, &DOptPtrLoad2, 1);
1852     RunOptFunc (S, &DOptPtrLoad3, 1);
1853     RunOptFunc (S, &DOptPtrLoad4, 1);
1854     RunOptFunc (S, &DOptPtrLoad5, 1);
1855     RunOptFunc (S, &DOptNegAX1, 1);
1856     RunOptFunc (S, &DOptNegAX2, 1);
1857     RunOptFunc (S, &DOptNegAX3, 1);
1858     RunOptFunc (S, &DOptNegAX4, 1);
1859     RunOptFunc (S, &DOptAdd1, 1);
1860     RunOptFunc (S, &DOptAdd2, 1);
1861     RunOptFunc (S, &DOptShift1, 1);
1862 }
1863
1864
1865
1866 static void RunOptGroup2 (CodeSeg* S)
1867 /* Run one group of optimization steps. This step involves just decoupling
1868  * instructions by replacing them by instructions that do not depend on
1869  * previous instructions. This makes it easier to find instructions that
1870  * aren't used.
1871  */
1872 {
1873     RunOptFunc (S, &DOptDecouple, 1);
1874 }
1875
1876
1877
1878
1879 static void RunOptGroup3 (CodeSeg* S)
1880 /* Run one group of optimization steps. These steps depend on each other,
1881  * that means that one step may allow another step to do additional work,
1882  * so we will repeat the steps as long as we see any changes.
1883  */
1884 {
1885     unsigned Changes;
1886
1887     do {
1888         Changes = 0;
1889
1890         Changes += RunOptFunc (S, &DOptPtrLoad6, 1);
1891         Changes += RunOptFunc (S, &DOptNegA1, 1);
1892         Changes += RunOptFunc (S, &DOptNegA2, 1);
1893         Changes += RunOptFunc (S, &DOptSub1, 1);
1894         Changes += RunOptFunc (S, &DOptSub2, 1);
1895         Changes += RunOptFunc (S, &DOptAdd3, 1);
1896         Changes += RunOptFunc (S, &DOptJumpCascades, 1);
1897         Changes += RunOptFunc (S, &DOptDeadJumps, 1);
1898         Changes += RunOptFunc (S, &DOptRTS, 1);
1899         Changes += RunOptFunc (S, &DOptDeadCode, 1);
1900         Changes += RunOptFunc (S, &DOptJumpTarget, 1);
1901         Changes += RunOptFunc (S, &DOptCondBranches, 1);
1902         Changes += RunOptFunc (S, &DOptRTSJumps, 1);
1903         Changes += RunOptFunc (S, &DOptBoolTrans, 1);
1904         Changes += RunOptFunc (S, &DOptCmp1, 1);
1905         Changes += RunOptFunc (S, &DOptCmp2, 1);
1906         Changes += RunOptFunc (S, &DOptCmp3, 1);
1907         Changes += RunOptFunc (S, &DOptCmp4, 1);
1908         Changes += RunOptFunc (S, &DOptCmp5, 1);
1909         Changes += RunOptFunc (S, &DOptCmp6, 1);
1910         Changes += RunOptFunc (S, &DOptCmp7, 1);
1911         Changes += RunOptFunc (S, &DOptTest1, 1);
1912         Changes += RunOptFunc (S, &DOptUnusedLoads, 1);
1913         Changes += RunOptFunc (S, &DOptUnusedStores, 1);
1914         Changes += RunOptFunc (S, &DOptDupLoads, 1);
1915         Changes += RunOptFunc (S, &DOptStoreLoad, 1);
1916         Changes += RunOptFunc (S, &DOptTransfers, 1);
1917         Changes += RunOptFunc (S, &DOptStackOps, 1);
1918
1919     } while (Changes);
1920 }
1921
1922
1923
1924 static void RunOptGroup4 (CodeSeg* S)
1925 /* The last group of optimization steps. Adjust branches.
1926  */
1927 {
1928     /* Optimize for size, that is replace operations by shorter ones, even
1929      * if this does hinder further optimizations (no problem since we're
1930      * done soon).
1931      */
1932     RunOptFunc (S, &DOptSize, 1);
1933
1934     /* Run the jump target optimization again, since the size optimization
1935      * above may have opened new oportunities.
1936      */
1937     RunOptFunc (S, &DOptJumpTarget, 5);
1938
1939     /* Finally, adjust branch distances */
1940     RunOptFunc (S, &DOptBranchDist, 3);
1941 }
1942
1943
1944
1945 void RunOpt (CodeSeg* S)
1946 /* Run the optimizer */
1947 {
1948     const char* StatFileName;
1949
1950     /* If we shouldn't run the optimizer, bail out */
1951     if (!Optimize) {
1952         return;
1953     }
1954
1955     /* Check if we are requested to write optimizer statistics */
1956     StatFileName = getenv ("CC65_OPTSTATS");
1957     if (StatFileName) {
1958         ReadOptStats (StatFileName);
1959     }
1960
1961     /* Print the name of the function we are working on */
1962     if (S->Func) {
1963         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1964     } else {
1965         Print (stdout, 1, "Running optimizer for global code segment\n");
1966     }
1967
1968     /* Run groups of optimizations */
1969     RunOptGroup1 (S);
1970     RunOptGroup2 (S);
1971     RunOptGroup3 (S);
1972     RunOptGroup4 (S);
1973
1974     /* Write statistics */
1975     if (StatFileName) {
1976         WriteOptStats (StatFileName);
1977     }
1978 }
1979
1980
1981