git.sur5r.net Git - cc65/blob - src/cc65/codeopt.c

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