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 <string.h>
  37
  38 /* common */
  39 #include "abend.h"
  40 #include "print.h"
  41
  42 /* cc65 */
  43 #include "asmlabel.h"
  44 #include "codeent.h"
  45 #include "codeinfo.h"
  46 #include "coptind.h"
  47 #include "error.h"
  48 #include "global.h"
  49 #include "codeopt.h"
  50
  51
  52
  53 /*****************************************************************************/
  54 /*                                   Data                                    */
  55 /*****************************************************************************/
  56
  57
  58
  59 /* Defines for the conditions in a compare */
  60 typedef enum {
  61     CMP_INV = -1,
  62     CMP_EQ,
  63     CMP_NE,
  64     CMP_GT,
  65     CMP_GE,
  66     CMP_LT,
  67     CMP_LE,
  68     CMP_UGT,
  69     CMP_UGE,
  70     CMP_ULT,
  71     CMP_ULE
  72 } cmp_t;
  73
  74 /* Table with the compare suffixes */
  75 static const char CmpSuffixTab [][4] = {
  76     "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
  77 };
  78
  79 /* Table used to invert a condition, indexed by condition */
  80 static const unsigned char CmpInvertTab [] = {
  81     CMP_NE, CMP_EQ,
  82     CMP_LE, CMP_LT, CMP_GE, CMP_GT,
  83     CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
  84 };
  85
  86 /* Table to show which compares are signed (use the N flag) */
  87 static const char CmpSignedTab [] = {
  88     0, 0, 1, 1, 1, 1, 0, 0, 0, 0
  89 };
  90
  91
  92
  93 /*****************************************************************************/
  94 /*                             Helper functions                              */
  95 /*****************************************************************************/
  96
  97
  98
  99 static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
 100 /* Search for a compare condition by the given code using the given length */
 101 {
 102     unsigned I;
 103
 104     /* Linear search */
 105     for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
 106         if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
 107             /* Found */
 108             return I;
 109         }
 110     }
 111
 112     /* Not found */
 113     return CMP_INV;
 114 }
 115
 116
 117
 118 static cmp_t FindBoolCmpCond (const char* Name)
 119 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
 120 {
 121     /* Check for the correct subroutine name */
 122     if (strncmp (Name, "bool", 4) == 0) {
 123         /* Name is ok, search for the code in the table */
 124         return FindCmpCond (Name+4, strlen(Name)-4);
 125     } else {
 126         /* Not found */
 127         return CMP_INV;
 128     }
 129 }
 130
 131
 132
 133 static cmp_t FindTosCmpCond (const char* Name)
 134 /* Check if this is a call to one of the TOS compare functions (tosgtax).
 135  * Return the condition code or CMP_INV on failure.
 136  */
 137 {
 138     unsigned Len = strlen (Name);
 139
 140     /* Check for the correct subroutine name */
 141     if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
 142         /* Name is ok, search for the code in the table */
 143         return FindCmpCond (Name+3, Len-3-2);
 144     } else {
 145         /* Not found */
 146         return CMP_INV;
 147     }
 148 }
 149
 150
 151
 152 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
 153 /* Helper function for the replacement of routines that return a boolean
 154  * followed by a conditional jump. Instead of the boolean value, the condition
 155  * codes are evaluated directly.
 156  * I is the index of the conditional branch, the sequence is already checked
 157  * to be correct.
 158  */
 159 {
 160     CodeEntry* N;
 161     CodeLabel* L;
 162
 163     /* Get the entry */
 164     CodeEntry* E = CS_GetEntry (S, I);
 165
 166     /* Replace the conditional branch */
 167     switch (Cond) {
 168
 169         case CMP_EQ:
 170             CE_ReplaceOPC (E, OP65_JEQ);
 171             break;
 172
 173         case CMP_NE:
 174             CE_ReplaceOPC (E, OP65_JNE);
 175             break;
 176
 177         case CMP_GT:
 178             /* Replace by
 179              *     beq @L
 180              *     jpl Target
 181              * @L: ...
 182              */
 183             if ((N = CS_GetNextEntry (S, I)) == 0) {
 184                 /* No such entry */
 185                 Internal ("Invalid program flow");
 186             }
 187             L = CS_GenLabel (S, N);
 188             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 189             CS_InsertEntry (S, N, I);
 190             CE_ReplaceOPC (E, OP65_JPL);
 191             break;
 192
 193         case CMP_GE:
 194             CE_ReplaceOPC (E, OP65_JPL);
 195             break;
 196
 197         case CMP_LT:
 198             CE_ReplaceOPC (E, OP65_JMI);
 199             break;
 200
 201         case CMP_LE:
 202             /* Replace by
 203              *     jmi Target
 204              *     jeq Target
 205              */
 206             CE_ReplaceOPC (E, OP65_JMI);
 207             L = E->JumpTo;
 208             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 209             CS_InsertEntry (S, N, I+1);
 210             break;
 211
 212         case CMP_UGT:
 213             /* Replace by
 214              *     beq @L
 215              *     jcs Target
 216              * @L: ...
 217              */
 218             if ((N = CS_GetNextEntry (S, I)) == 0) {
 219                 /* No such entry */
 220                 Internal ("Invalid program flow");
 221             }
 222             L = CS_GenLabel (S, N);
 223             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 224             CS_InsertEntry (S, N, I);
 225             CE_ReplaceOPC (E, OP65_JCS);
 226             break;
 227
 228         case CMP_UGE:
 229             CE_ReplaceOPC (E, OP65_JCS);
 230             break;
 231
 232         case CMP_ULT:
 233             CE_ReplaceOPC (E, OP65_JCC);
 234             break;
 235
 236         case CMP_ULE:
 237             /* Replace by
 238              *     jcc Target
 239              *     jeq Target
 240              */
 241             CE_ReplaceOPC (E, OP65_JCC);
 242             L = E->JumpTo;
 243             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 244             CS_InsertEntry (S, N, I+1);
 245             break;
 246
 247         default:
 248             Internal ("Unknown jump condition: %d", Cond);
 249
 250     }
 251
 252 }
 253
 254
 255
 256 static int IsCmpToZero (const CodeEntry* E)
 257 /* Check if the given instrcuction is a compare to zero instruction */
 258 {
 259     return (E->OPC == OP65_CMP            &&
 260             E->AM  == AM65_IMM            &&
 261             (E->Flags & CEF_NUMARG) != 0  &&
 262             E->Num == 0);
 263 }
 264
 265
 266
 267 static int IsSpLoad (const CodeEntry* E)
 268 /* Return true if this is the load of A from the stack */
 269 {
 270     return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
 271 }
 272
 273
 274
 275 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
 276                           CodeEntry** L, unsigned Count)
 277 /* Check if a 16 bit load of a local variable follows:
 278  *
 279  *      ldy     #$xx
 280  *      lda     (sp),y
 281  *      tax
 282  *      dey
 283  *      lda     (sp),y
 284  *
 285  * If so, read Count entries following the first ldy into L and return true
 286  * if this is possible. Otherwise return false.
 287  */
 288 {
 289     /* Be sure we read enough entries for the check */
 290     CHECK (Count >= 5);
 291
 292     /* Read the first entry */
 293     L[0] = CS_GetEntry (S, Index);
 294
 295     /* Check for the sequence */
 296     return (L[0]->OPC == OP65_LDY                        &&
 297             L[0]->AM == AM65_IMM                         &&
 298             (L[0]->Flags & CEF_NUMARG) != 0              &&
 299             CS_GetEntries (S, L+1, Index+1, Count-1)     &&
 300             IsSpLoad (L[1])                              &&
 301             !CE_HasLabel (L[1])                          &&
 302             L[2]->OPC == OP65_TAX                        &&
 303             !CE_HasLabel (L[2])                          &&
 304             L[3]->OPC == OP65_DEY                        &&
 305             !CE_HasLabel (L[3])                          &&
 306             IsSpLoad (L[4])                              &&
 307             !CE_HasLabel (L[4]));
 308 }
 309
 310
 311
 312 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
 313 /* Check if the instructions at L are an immidiate compare of a/x:
 314  *
 315  *
 316  */
 317 {
 318     return (L[0]->OPC == OP65_CPX                              &&
 319             L[0]->AM == AM65_IMM                               &&
 320             (L[0]->Flags & CEF_NUMARG) != 0                    &&
 321             !CE_HasLabel (L[0])                                &&
 322             (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE)   &&
 323             L[1]->JumpTo != 0                                  &&
 324             !CE_HasLabel (L[1])                                &&
 325             L[2]->OPC == OP65_CMP                              &&
 326             L[2]->AM == AM65_IMM                               &&
 327             (L[2]->Flags & CEF_NUMARG) != 0                    &&
 328             (L[3]->Info & OF_ZBRA) != 0                        &&
 329             L[3]->JumpTo != 0                                  &&
 330             (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
 331 }
 332
 333
 334
 335 /*****************************************************************************/
 336 /*             Remove calls to the bool transformer subroutines              */
 337 /*****************************************************************************/
 338
 339
 340
 341 static unsigned OptBoolTransforms (CodeSeg* S)
 342 /* Try to remove the call to boolean transformer routines where the call is
 343  * not really needed.
 344  */
 345 {
 346     unsigned Changes = 0;
 347
 348     /* Walk over the entries */
 349     unsigned I = 0;
 350     while (I < CS_GetEntryCount (S)) {
 351
 352         CodeEntry* N;
 353         cmp_t Cond;
 354
 355         /* Get next entry */
 356         CodeEntry* E = CS_GetEntry (S, I);
 357
 358         /* Check for a boolean transformer */
 359         if (E->OPC == OP65_JSR                           &&
 360             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 361             (N = CS_GetNextEntry (S, I)) != 0        &&
 362             (N->Info & OF_ZBRA) != 0) {
 363
 364             /* Make the boolean transformer unnecessary by changing the
 365              * the conditional jump to evaluate the condition flags that
 366              * are set after the compare directly. Note: jeq jumps if
 367              * the condition is not met, jne jumps if the condition is met.
 368              * Invert the code if we jump on condition not met.
 369              */
 370             if (GetBranchCond (N->OPC) == BC_EQ) {
 371                 /* Jumps if condition false, invert condition */
 372                 Cond = CmpInvertTab [Cond];
 373             }
 374
 375             /* Check if we can replace the code by something better */
 376             ReplaceCmp (S, I+1, Cond);
 377
 378             /* Remove the call to the bool transformer */
 379             CS_DelEntry (S, I);
 380
 381             /* Remember, we had changes */
 382             ++Changes;
 383
 384         }
 385
 386         /* Next entry */
 387         ++I;
 388
 389     }
 390
 391     /* Return the number of changes made */
 392     return Changes;
 393 }
 394
 395
 396
 397 /*****************************************************************************/
 398 /*                           Optimize subtractions                           */
 399 /*****************************************************************************/
 400
 401
 402
 403 static unsigned OptSub1 (CodeSeg* S)
 404 /* Search for the sequence
 405  *
 406  *      sbc     ...
 407  *      bcs     L
 408  *      dex
 409  * L:
 410  *
 411  * and remove the handling of the high byte if X is not used later.
 412  */
 413 {
 414     unsigned Changes = 0;
 415
 416     /* Walk over the entries */
 417     unsigned I = 0;
 418     while (I < CS_GetEntryCount (S)) {
 419
 420         CodeEntry* L[3];
 421
 422         /* Get next entry */
 423         CodeEntry* E = CS_GetEntry (S, I);
 424
 425         /* Check for the sequence */
 426         if (E->OPC == OP65_SBC                               &&
 427             CS_GetEntries (S, L, I+1, 3)                     &&
 428             (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) &&
 429             L[0]->JumpTo != 0                                &&
 430             !CE_HasLabel (L[0])                              &&
 431             L[1]->OPC == OP65_DEX                            &&
 432             !CE_HasLabel (L[1])                              &&
 433             L[0]->JumpTo->Owner == L[2]                      &&
 434             !RegXUsed (S, I+3)) {
 435
 436             /* Remove the bcs/dex */
 437             CS_DelEntries (S, I+1, 2);
 438
 439             /* Remember, we had changes */
 440             ++Changes;
 441
 442         }
 443
 444         /* Next entry */
 445         ++I;
 446
 447     }
 448
 449     /* Return the number of changes made */
 450     return Changes;
 451 }
 452
 453
 454
 455 static unsigned OptSub2 (CodeSeg* S)
 456 /* Search for the sequence
 457  *
 458  *      lda     xx
 459  *      sec
 460  *      sta     tmp1
 461  *      lda     yy
 462  *      sbc     tmp1
 463  *      sta     yy
 464  *
 465  * and replace it by
 466  *
 467  *      sec
 468  *      lda     yy
 469  *      sbc     xx
 470  *      sta     yy
 471  */
 472 {
 473     unsigned Changes = 0;
 474
 475     /* Walk over the entries */
 476     unsigned I = 0;
 477     while (I < CS_GetEntryCount (S)) {
 478
 479         CodeEntry* L[5];
 480
 481         /* Get next entry */
 482         CodeEntry* E = CS_GetEntry (S, I);
 483
 484         /* Check for the sequence */
 485         if (E->OPC == OP65_LDA                             &&
 486             CS_GetEntries (S, L, I+1, 5)                   &&
 487             L[0]->OPC == OP65_SEC                          &&
 488             !CE_HasLabel (L[0])                            &&
 489             L[1]->OPC == OP65_STA                          &&
 490             strcmp (L[1]->Arg, "tmp1") == 0                &&
 491             !CE_HasLabel (L[1])                            &&
 492             L[2]->OPC == OP65_LDA                          &&
 493             !CE_HasLabel (L[2])                            &&
 494             L[3]->OPC == OP65_SBC                          &&
 495             strcmp (L[3]->Arg, "tmp1") == 0                &&
 496             !CE_HasLabel (L[3])                            &&
 497             L[4]->OPC == OP65_STA                          &&
 498             strcmp (L[4]->Arg, L[2]->Arg) == 0             &&
 499             !CE_HasLabel (L[4])) {
 500
 501             /* Remove the store to tmp1 */
 502             CS_DelEntry (S, I+2);
 503
 504             /* Remove the subtraction */
 505             CS_DelEntry (S, I+3);
 506
 507             /* Move the lda to the position of the subtraction and change the
 508              * op to SBC.
 509              */
 510             CS_MoveEntry (S, I, I+3);
 511             CE_ReplaceOPC (E, OP65_SBC);
 512
 513             /* If the sequence head had a label, move this label back to the
 514              * head.
 515              */
 516             if (CE_HasLabel (E)) {
 517                 CS_MoveLabels (S, E, L[0]);
 518             }
 519
 520             /* Remember, we had changes */
 521             ++Changes;
 522
 523         }
 524
 525         /* Next entry */
 526         ++I;
 527
 528     }
 529
 530     /* Return the number of changes made */
 531     return Changes;
 532 }
 533
 534
 535
 536 /*****************************************************************************/
 537 /*                            Optimize additions                             */
 538 /*****************************************************************************/
 539
 540
 541
 542 static unsigned OptAdd1 (CodeSeg* S)
 543 /* Search for the sequence
 544  *
 545  *      jsr     pushax
 546  *      ldy     xxx
 547  *      ldx     #$00
 548  *      lda     (sp),y
 549  *      jsr     tosaddax
 550  *
 551  * and replace it by:
 552  *
 553  *      ldy     xxx
 554  *      clc
 555  *      adc     (sp),y
 556  *      bcc     L
 557  *      inx
 558  * L:
 559  */
 560 {
 561     unsigned Changes = 0;
 562
 563     /* Walk over the entries */
 564     unsigned I = 0;
 565     while (I < CS_GetEntryCount (S)) {
 566
 567         CodeEntry* L[5];
 568
 569         /* Get next entry */
 570         CodeEntry* E = CS_GetEntry (S, I);
 571
 572         /* Check for the sequence */
 573         if (E->OPC == OP65_JSR                               &&
 574             strcmp (E->Arg, "pushax") == 0                   &&
 575             CS_GetEntries (S, L, I+1, 5)                     &&
 576             L[0]->OPC == OP65_LDY                            &&
 577             !CE_HasLabel (L[0])                              &&
 578             L[1]->OPC == OP65_LDX                            &&
 579             CE_KnownImm (L[1])                               &&
 580             L[1]->Num == 0                                   &&
 581             !CE_HasLabel (L[1])                              &&
 582             L[2]->OPC == OP65_LDA                            &&
 583             !CE_HasLabel (L[2])                              &&
 584             L[3]->OPC == OP65_JSR                            &&
 585             strcmp (L[3]->Arg, "tosaddax") == 0              &&
 586             !CE_HasLabel (L[3])) {
 587
 588             CodeEntry* X;
 589             CodeLabel* Label;
 590
 591             /* Remove the call to pushax */
 592             CS_DelEntry (S, I);
 593
 594             /* Add the clc . */
 595             X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, L[3]->LI);
 596             CS_InsertEntry (S, X, I+1);
 597
 598             /* Remove the load */
 599             CS_DelEntry (S, I+3);      /* lda */
 600             CS_DelEntry (S, I+2);      /* ldx */
 601
 602             /* Add the adc */
 603             X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[3]->LI);
 604             CS_InsertEntry (S, X, I+2);
 605
 606             /* Generate the branch label and the branch */
 607             Label = CS_GenLabel (S, L[4]);
 608             X = NewCodeEntry (OP65_BCC, AM65_BRA, Label->Name, Label, L[3]->LI);
 609             CS_InsertEntry (S, X, I+3);
 610
 611             /* Generate the increment of the high byte */
 612             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, L[3]->LI);
 613             CS_InsertEntry (S, X, I+4);
 614
 615             /* Delete the call to tosaddax */
 616             CS_DelEntry (S, I+5);
 617
 618             /* Remember, we had changes */
 619             ++Changes;
 620
 621         }
 622
 623         /* Next entry */
 624         ++I;
 625
 626     }
 627
 628     /* Return the number of changes made */
 629     return Changes;
 630 }
 631
 632
 633
 634 static unsigned OptAdd2 (CodeSeg* S)
 635 /* Search for the sequence
 636  *
 637  *      adc     ...
 638  *      bcc     L
 639  *      inx
 640  * L:
 641  *
 642  * and remove the handling of the high byte if X is not used later.
 643  */
 644 {
 645     unsigned Changes = 0;
 646
 647     /* Walk over the entries */
 648     unsigned I = 0;
 649     while (I < CS_GetEntryCount (S)) {
 650
 651         CodeEntry* L[3];
 652
 653         /* Get next entry */
 654         CodeEntry* E = CS_GetEntry (S, I);
 655
 656         /* Check for the sequence */
 657         if (E->OPC == OP65_ADC                               &&
 658             CS_GetEntries (S, L, I+1, 3)                     &&
 659             (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
 660             L[0]->JumpTo != 0                                &&
 661             !CE_HasLabel (L[0])                              &&
 662             L[1]->OPC == OP65_INX                            &&
 663             !CE_HasLabel (L[1])                              &&
 664             L[0]->JumpTo->Owner == L[2]                      &&
 665             !RegXUsed (S, I+3)) {
 666
 667             /* Remove the bcs/dex */
 668             CS_DelEntries (S, I+1, 2);
 669
 670             /* Remember, we had changes */
 671             ++Changes;
 672
 673         }
 674
 675         /* Next entry */
 676         ++I;
 677
 678     }
 679
 680     /* Return the number of changes made */
 681     return Changes;
 682 }
 683
 684
 685
 686 /*****************************************************************************/
 687 /*                        Optimizations for compares                         */
 688 /*****************************************************************************/
 689
 690
 691
 692 static unsigned OptCmp1 (CodeSeg* S)
 693 /* Search for the sequence
 694  *
 695  *      stx     xx
 696  *      stx     tmp1
 697  *      ora     tmp1
 698  *
 699  * and replace it by
 700  *
 701  *      stx     xx
 702  *      ora     xx
 703  */
 704 {
 705     unsigned Changes = 0;
 706
 707     /* Walk over the entries */
 708     unsigned I = 0;
 709     while (I < CS_GetEntryCount (S)) {
 710
 711         CodeEntry* L[2];
 712
 713         /* Get next entry */
 714         CodeEntry* E = CS_GetEntry (S, I);
 715
 716         /* Check for the sequence */
 717         if (E->OPC == OP65_STX                  &&
 718             CS_GetEntries (S, L, I+1, 2)        &&
 719             L[0]->OPC == OP65_STX               &&
 720             strcmp (L[0]->Arg, "tmp1") == 0     &&
 721             !CE_HasLabel (L[0])                 &&
 722             L[1]->OPC == OP65_ORA               &&
 723             strcmp (L[1]->Arg, "tmp1") == 0     &&
 724             !CE_HasLabel (L[1])) {
 725
 726             /* Remove the remaining instructions */
 727             CS_DelEntries (S, I+1, 2);
 728
 729             /* Insert the ora instead */
 730             CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
 731
 732             /* Remember, we had changes */
 733             ++Changes;
 734
 735         }
 736
 737         /* Next entry */
 738         ++I;
 739
 740     }
 741
 742     /* Return the number of changes made */
 743     return Changes;
 744 }
 745
 746
 747
 748 static unsigned OptCmp2 (CodeSeg* S)
 749 /* Search for
 750  *
 751  *      lda/and/ora/eor ...
 752  *      cmp #$00
 753  *      jeq/jne
 754  *
 755  * and remove the cmp.
 756  */
 757 {
 758     unsigned Changes = 0;
 759
 760     /* Walk over the entries */
 761     unsigned I = 0;
 762     while (I < CS_GetEntryCount (S)) {
 763
 764         CodeEntry* L[2];
 765
 766         /* Get next entry */
 767         CodeEntry* E = CS_GetEntry (S, I);
 768
 769         /* Check for the sequence */
 770         if ((E->OPC == OP65_ADC ||
 771              E->OPC == OP65_AND ||
 772              E->OPC == OP65_DEA ||
 773              E->OPC == OP65_EOR ||
 774              E->OPC == OP65_INA ||
 775              E->OPC == OP65_LDA ||
 776              E->OPC == OP65_ORA ||
 777              E->OPC == OP65_PLA ||
 778              E->OPC == OP65_SBC ||
 779              E->OPC == OP65_TXA ||
 780              E->OPC == OP65_TYA)                  &&
 781             CS_GetEntries (S, L, I+1, 2)          &&
 782             IsCmpToZero (L[0])                    &&
 783             !CE_HasLabel (L[0])                   &&
 784             (L[1]->Info & OF_FBRA) != 0           &&
 785             !CE_HasLabel (L[1])) {
 786
 787             /* Remove the compare */
 788             CS_DelEntry (S, I+1);
 789
 790             /* Remember, we had changes */
 791             ++Changes;
 792
 793         }
 794
 795         /* Next entry */
 796         ++I;
 797
 798     }
 799
 800     /* Return the number of changes made */
 801     return Changes;
 802 }
 803
 804
 805
 806 static unsigned OptCmp3 (CodeSeg* S)
 807 /* Search for
 808  *
 809  *      lda     x
 810  *      ldx     y
 811  *      cpx     #a
 812  *      bne     L1
 813  *      cmp     #b
 814  *      jne/jeq L2
 815  *
 816  * If a is zero, we may remove the compare. If a and b are both zero, we may
 817  * replace it by the sequence
 818  *
 819  *      lda     x
 820  *      ora     x+1
 821  *      jne/jeq ...
 822  *
 823  * L1 may be either the label at the branch instruction, or the target label
 824  * of this instruction.
 825  */
 826 {
 827     unsigned Changes = 0;
 828
 829     /* Walk over the entries */
 830     unsigned I = 0;
 831     while (I < CS_GetEntryCount (S)) {
 832
 833         CodeEntry* L[5];
 834
 835         /* Get next entry */
 836         CodeEntry* E = CS_GetEntry (S, I);
 837
 838         /* Check for the sequence */
 839         if (E->OPC == OP65_LDA               &&
 840             CS_GetEntries (S, L, I+1, 5) &&
 841             L[0]->OPC == OP65_LDX            &&
 842             !CE_HasLabel (L[0])              &&
 843             IsImmCmp16 (S, L+1)) {
 844
 845             if (L[1]->Num == 0 && L[3]->Num == 0) {
 846                 /* The value is zero, we may use the simple code version. */
 847                 CE_ReplaceOPC (L[0], OP65_ORA);
 848                 CS_DelEntries (S, I+2, 3);
 849             } else {
 850                 /* Move the lda instruction after the first branch. This will
 851                  * improve speed, since the load is delayed after the first
 852                  * test.
 853                  */
 854                 CS_MoveEntry (S, I, I+4);
 855
 856                 /* We will replace the ldx/cpx by lda/cmp */
 857                 CE_ReplaceOPC (L[0], OP65_LDA);
 858                 CE_ReplaceOPC (L[1], OP65_CMP);
 859
 860                 /* Beware: If the first LDA instruction had a label, we have
 861                  * to move this label to the top of the sequence again.
 862                  */
 863                 if (CE_HasLabel (E)) {
 864                     CS_MoveLabels (S, E, L[0]);
 865                 }
 866
 867             }
 868
 869             ++Changes;
 870         }
 871
 872         /* Next entry */
 873         ++I;
 874
 875     }
 876
 877     /* Return the number of changes made */
 878     return Changes;
 879 }
 880
 881
 882
 883 static unsigned OptCmp4 (CodeSeg* S)
 884 /* Optimize compares of local variables:
 885  *
 886  *      ldy     #o
 887  *      lda     (sp),y
 888  *      tax
 889  *      dey
 890  *      lda     (sp),y
 891  *      cpx     #a
 892  *      bne     L1
 893  *      cmp     #b
 894  *      jne/jeq L2
 895  */
 896 {
 897     unsigned Changes = 0;
 898
 899     /* Walk over the entries */
 900     unsigned I = 0;
 901     while (I < CS_GetEntryCount (S)) {
 902
 903         CodeEntry* L[9];
 904
 905         /* Check for the sequence */
 906         if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
 907
 908             if (L[5]->Num == 0 && L[7]->Num == 0) {
 909
 910                 /* The value is zero, we may use the simple code version:
 911                  *      ldy     #o
 912                  *      lda     (sp),y
 913                  *      dey
 914                  *      ora     (sp),y
 915                  *      jne/jeq ...
 916                  */
 917                 CE_ReplaceOPC (L[4], OP65_ORA);
 918                 CS_DelEntries (S, I+5, 3);   /* cpx/bne/cmp */
 919                 CS_DelEntry (S, I+2);        /* tax */
 920
 921             } else {
 922
 923                 /* Change the code to just use the A register. Move the load
 924                  * of the low byte after the first branch if possible:
 925                  *
 926                  *      ldy     #o
 927                  *      lda     (sp),y
 928                  *      cmp     #a
 929                  *      bne     L1
 930                  *      dey
 931                  *      lda     (sp),y
 932                  *      cmp     #b
 933                  *      jne/jeq ...
 934                  */
 935                 CS_DelEntry (S, I+2);             /* tax */
 936                 CE_ReplaceOPC (L[5], OP65_CMP);   /* cpx -> cmp */
 937                 CS_MoveEntry (S, I+4, I+2);       /* cmp */
 938                 CS_MoveEntry (S, I+5, I+3);       /* bne */
 939
 940             }
 941
 942             ++Changes;
 943         }
 944
 945         /* Next entry */
 946         ++I;
 947
 948     }
 949
 950     /* Return the number of changes made */
 951     return Changes;
 952 }
 953
 954
 955
 956 static unsigned OptCmp5 (CodeSeg* S)
 957 /* Search for calls to compare subroutines followed by a conditional branch
 958  * and replace them by cheaper versions, since the branch means that the
 959  * boolean value returned by these routines is not needed (we may also check
 960  * that explicitly, but for the current code generator it is always true).
 961  */
 962 {
 963     unsigned Changes = 0;
 964
 965     /* Walk over the entries */
 966     unsigned I = 0;
 967     while (I < CS_GetEntryCount (S)) {
 968
 969         CodeEntry* N;
 970         cmp_t Cond;
 971
 972         /* Get next entry */
 973         CodeEntry* E = CS_GetEntry (S, I);
 974
 975         /* Check for the sequence */
 976         if (E->OPC == OP65_JSR                          &&
 977             (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
 978             (N = CS_GetNextEntry (S, I)) != 0           &&
 979             (N->Info & OF_ZBRA) != 0                    &&
 980             !CE_HasLabel (N)) {
 981
 982             /* The tos... functions will return a boolean value in a/x and
 983              * the Z flag says if this value is zero or not. We will call
 984              * a cheaper subroutine instead, one that does not return a
 985              * boolean value but only valid flags. Note: jeq jumps if
 986              * the condition is not met, jne jumps if the condition is met.
 987              * Invert the code if we jump on condition not met.
 988              */
 989             if (GetBranchCond (N->OPC) == BC_EQ) {
 990                 /* Jumps if condition false, invert condition */
 991                 Cond = CmpInvertTab [Cond];
 992             }
 993
 994             /* Replace the subroutine call. */
 995             E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
 996             CS_InsertEntry (S, E, I+1);
 997             CS_DelEntry (S, I);
 998
 999             /* Replace the conditional branch */
1000             ReplaceCmp (S, I+1, Cond);
1001
1002             /* Remember, we had changes */
1003             ++Changes;
1004
1005         }
1006
1007         /* Next entry */
1008         ++I;
1009
1010     }
1011
1012     /* Return the number of changes made */
1013     return Changes;
1014 }
1015
1016
1017
1018 static unsigned OptCmp6 (CodeSeg* S)
1019 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
1020  * used later.
1021  */
1022 {
1023     unsigned Changes = 0;
1024
1025     /* Walk over the entries */
1026     unsigned I = 0;
1027     while (I < CS_GetEntryCount (S)) {
1028
1029         CodeEntry* L[2];
1030
1031         /* Get next entry */
1032         CodeEntry* E = CS_GetEntry (S, I);
1033
1034         /* Check for the sequence */
1035         if ((E->OPC == OP65_LDX)                        &&
1036             CS_GetEntries (S, L, I+1, 2)                &&
1037             L[0]->OPC == OP65_TXA                       &&
1038             !CE_HasLabel (L[0])                         &&
1039             (L[1]->Info & OF_FBRA) != 0                 &&
1040             !CE_HasLabel (L[1])                         &&
1041             !RegAUsed (S, I+3)) {
1042
1043             /* Remove the txa */
1044             CS_DelEntry (S, I+1);
1045
1046             /* Remember, we had changes */
1047             ++Changes;
1048
1049         }
1050
1051         /* Next entry */
1052         ++I;
1053
1054     }
1055
1056     /* Return the number of changes made */
1057     return Changes;
1058 }
1059
1060
1061
1062 /*****************************************************************************/
1063 /*                              Optimize tests                               */
1064 /*****************************************************************************/
1065
1066
1067
1068 static unsigned OptTest1 (CodeSeg* S)
1069 /* On a sequence
1070  *
1071  *     stx     xxx
1072  *     ora     xxx
1073  *     beq/bne ...
1074  *
1075  * if X is zero, the sequence may be changed to
1076  *
1077  *     cmp     #$00
1078  *     beq/bne ...
1079  *
1080  * which may be optimized further by another step.
1081  *
1082  * If A is zero, the sequence may be changed to
1083  *
1084  *     txa
1085  *     beq/bne ...
1086  *
1087  */
1088 {
1089     unsigned Changes = 0;
1090     unsigned I;
1091
1092     /* Generate register info for this step */
1093     CS_GenRegInfo (S);
1094
1095     /* Walk over the entries */
1096     I = 0;
1097     while (I < CS_GetEntryCount (S)) {
1098
1099         CodeEntry* L[3];
1100
1101         /* Get next entry */
1102         L[0] = CS_GetEntry (S, I);
1103
1104         /* Check if it's the sequence we're searching for */
1105         if (L[0]->OPC == OP65_STX              &&
1106             CS_GetEntries (S, L+1, I+1, 2)     &&
1107             !CE_HasLabel (L[1])                &&
1108             L[1]->OPC == OP65_ORA              &&
1109             strcmp (L[0]->Arg, L[1]->Arg) == 0 &&
1110             !CE_HasLabel (L[2])                &&
1111             (L[2]->Info & OF_ZBRA) != 0) {
1112
1113             /* Check if X is zero */
1114             if (L[0]->RI->In.RegX == 0) {
1115
1116                 /* Insert the compare */
1117                 CodeEntry* N = NewCodeEntry (OP65_CMP, AM65_IMM, "$00", 0, L[0]->LI);
1118                 CS_InsertEntry (S, N, I+2);
1119
1120                 /* Remove the two other insns */
1121                 CS_DelEntry (S, I+1);
1122                 CS_DelEntry (S, I);
1123
1124                 /* We had changes */
1125                 ++Changes;
1126
1127             /* Check if A is zero */
1128             } else if (L[1]->RI->In.RegA == 0) {
1129
1130                 /* Insert the txa */
1131                 CodeEntry* N = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, L[1]->LI);
1132                 CS_InsertEntry (S, N, I+2);
1133
1134                 /* Remove the two other insns */
1135                 CS_DelEntry (S, I+1);
1136                 CS_DelEntry (S, I);
1137
1138                 /* We had changes */
1139                 ++Changes;
1140             }
1141         }
1142
1143         /* Next entry */
1144         ++I;
1145
1146     }
1147
1148     /* Free register info */
1149     CS_FreeRegInfo (S);
1150
1151     /* Return the number of changes made */
1152     return Changes;
1153 }
1154
1155
1156
1157 /*****************************************************************************/
1158 /*                            nega optimizations                             */
1159 /*****************************************************************************/
1160
1161
1162
1163 static unsigned OptNegA1 (CodeSeg* S)
1164 /* Check for
1165  *
1166  *      ldx     #$00
1167  *      lda     ..
1168  *      jsr     bnega
1169  *
1170  * Remove the ldx if the lda does not use it.
1171  */
1172 {
1173     unsigned Changes = 0;
1174
1175     /* Walk over the entries */
1176     unsigned I = 0;
1177     while (I < CS_GetEntryCount (S)) {
1178
1179         CodeEntry* L[2];
1180
1181         /* Get next entry */
1182         CodeEntry* E = CS_GetEntry (S, I);
1183
1184         /* Check for a ldx */
1185         if (E->OPC == OP65_LDX                  &&
1186             E->AM == AM65_IMM                   &&
1187             (E->Flags & CEF_NUMARG) != 0        &&
1188             E->Num == 0                         &&
1189             CS_GetEntries (S, L, I+1, 2)        &&
1190             L[0]->OPC == OP65_LDA               &&
1191             (L[0]->Use & REG_X) == 0            &&
1192             !CE_HasLabel (L[0])                 &&
1193             L[1]->OPC == OP65_JSR               &&
1194             strcmp (L[1]->Arg, "bnega") == 0    &&
1195             !CE_HasLabel (L[1])) {
1196
1197             /* Remove the ldx instruction */
1198             CS_DelEntry (S, I);
1199
1200             /* Remember, we had changes */
1201             ++Changes;
1202
1203         }
1204
1205         /* Next entry */
1206         ++I;
1207
1208     }
1209
1210     /* Return the number of changes made */
1211     return Changes;
1212 }
1213
1214
1215
1216 static unsigned OptNegA2 (CodeSeg* S)
1217 /* Check for
1218  *
1219  *      lda     ..
1220  *      jsr     bnega
1221  *      jeq/jne ..
1222  *
1223  * Adjust the conditional branch and remove the call to the subroutine.
1224  */
1225 {
1226     unsigned Changes = 0;
1227
1228     /* Walk over the entries */
1229     unsigned I = 0;
1230     while (I < CS_GetEntryCount (S)) {
1231
1232         CodeEntry* L[2];
1233
1234         /* Get next entry */
1235         CodeEntry* E = CS_GetEntry (S, I);
1236
1237         /* Check for the sequence */
1238         if ((E->OPC == OP65_ADC ||
1239              E->OPC == OP65_AND ||
1240              E->OPC == OP65_DEA ||
1241              E->OPC == OP65_EOR ||
1242              E->OPC == OP65_INA ||
1243              E->OPC == OP65_LDA ||
1244              E->OPC == OP65_ORA ||
1245              E->OPC == OP65_PLA ||
1246              E->OPC == OP65_SBC ||
1247              E->OPC == OP65_TXA ||
1248              E->OPC == OP65_TYA)                &&
1249             CS_GetEntries (S, L, I+1, 2)        &&
1250             L[0]->OPC == OP65_JSR               &&
1251             strcmp (L[0]->Arg, "bnega") == 0    &&
1252             !CE_HasLabel (L[0])                 &&
1253             (L[1]->Info & OF_ZBRA) != 0         &&
1254             !CE_HasLabel (L[1])) {
1255
1256             /* Invert the branch */
1257             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1258
1259             /* Delete the subroutine call */
1260             CS_DelEntry (S, I+1);
1261
1262             /* Remember, we had changes */
1263             ++Changes;
1264
1265         }
1266
1267         /* Next entry */
1268         ++I;
1269
1270     }
1271
1272     /* Return the number of changes made */
1273     return Changes;
1274 }
1275
1276
1277
1278 /*****************************************************************************/
1279 /*                            negax optimizations                            */
1280 /*****************************************************************************/
1281
1282
1283
1284 static unsigned OptNegAX1 (CodeSeg* S)
1285 /* On a call to bnegax, if X is zero, the result depends only on the value in
1286  * A, so change the call to a call to bnega. This will get further optimized
1287  * later if possible.
1288  */
1289 {
1290     unsigned Changes = 0;
1291     unsigned I;
1292
1293     /* Generate register info for this step */
1294     CS_GenRegInfo (S);
1295
1296     /* Walk over the entries */
1297     I = 0;
1298     while (I < CS_GetEntryCount (S)) {
1299
1300         /* Get next entry */
1301         CodeEntry* E = CS_GetEntry (S, I);
1302
1303         /* Check if this is a call to bnegax, and if X is known and zero */
1304         if (E->OPC == OP65_JSR              &&
1305             E->RI->In.RegX == 0             &&
1306             strcmp (E->Arg, "bnegax") == 0) {
1307
1308             /* We're cheating somewhat here ... */
1309             E->Arg[5] = '\0';
1310             E->Use &= ~REG_X;
1311
1312             /* We had changes */
1313             ++Changes;
1314         }
1315
1316         /* Next entry */
1317         ++I;
1318
1319     }
1320
1321     /* Free register info */
1322     CS_FreeRegInfo (S);
1323
1324     /* Return the number of changes made */
1325     return Changes;
1326 }
1327
1328
1329
1330 static unsigned OptNegAX2 (CodeSeg* S)
1331 /* Search for the sequence:
1332  *
1333  *      lda     (xx),y
1334  *      tax
1335  *      dey
1336  *      lda     (xx),y
1337  *      jsr     bnegax
1338  *      jne/jeq ...
1339  *
1340  * and replace it by
1341  *
1342  *      lda     (xx),y
1343  *      dey
1344  *      ora     (xx),y
1345  *      jeq/jne ...
1346  */
1347 {
1348     unsigned Changes = 0;
1349
1350     /* Walk over the entries */
1351     unsigned I = 0;
1352     while (I < CS_GetEntryCount (S)) {
1353
1354         CodeEntry* L[5];
1355
1356         /* Get next entry */
1357         CodeEntry* E = CS_GetEntry (S, I);
1358
1359         /* Check for the sequence */
1360         if (E->OPC == OP65_LDA                  &&
1361             E->AM == AM65_ZP_INDY               &&
1362             CS_GetEntries (S, L, I+1, 5)        &&
1363             L[0]->OPC == OP65_TAX               &&
1364             L[1]->OPC == OP65_DEY               &&
1365             L[2]->OPC == OP65_LDA               &&
1366             L[2]->AM == AM65_ZP_INDY            &&
1367             strcmp (L[2]->Arg, E->Arg) == 0     &&
1368             !CE_HasLabel (L[2])                 &&
1369             L[3]->OPC == OP65_JSR               &&
1370             strcmp (L[3]->Arg, "bnegax") == 0   &&
1371             !CE_HasLabel (L[3])                 &&
1372             (L[4]->Info & OF_ZBRA) != 0         &&
1373             !CE_HasLabel (L[4])) {
1374
1375             /* lda --> ora */
1376             CE_ReplaceOPC (L[2], OP65_ORA);
1377
1378             /* Invert the branch */
1379             CE_ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1380
1381             /* Delete the entries no longer needed. Beware: Deleting entries
1382              * will change the indices.
1383              */
1384             CS_DelEntry (S, I+4);               /* jsr bnegax */
1385             CS_DelEntry (S, I+1);               /* tax */
1386
1387             /* Remember, we had changes */
1388             ++Changes;
1389
1390         }
1391
1392         /* Next entry */
1393         ++I;
1394
1395     }
1396
1397     /* Return the number of changes made */
1398     return Changes;
1399 }
1400
1401
1402
1403 static unsigned OptNegAX3 (CodeSeg* S)
1404 /* Search for the sequence:
1405  *
1406  *      lda     xx
1407  *      ldx     yy
1408  *      jsr     bnegax
1409  *      jne/jeq ...
1410  *
1411  * and replace it by
1412  *
1413  *      lda     xx
1414  *      ora     xx+1
1415  *      jeq/jne ...
1416  */
1417 {
1418     unsigned Changes = 0;
1419
1420     /* Walk over the entries */
1421     unsigned I = 0;
1422     while (I < CS_GetEntryCount (S)) {
1423
1424         CodeEntry* L[3];
1425
1426         /* Get next entry */
1427         CodeEntry* E = CS_GetEntry (S, I);
1428
1429         /* Check for the sequence */
1430         if (E->OPC == OP65_LDA                  &&
1431             CS_GetEntries (S, L, I+1, 3)        &&
1432             L[0]->OPC == OP65_LDX               &&
1433             !CE_HasLabel (L[0])                 &&
1434             L[1]->OPC == OP65_JSR               &&
1435             strcmp (L[1]->Arg, "bnegax") == 0   &&
1436             !CE_HasLabel (L[1])                 &&
1437             (L[2]->Info & OF_ZBRA) != 0         &&
1438             !CE_HasLabel (L[2])) {
1439
1440             /* ldx --> ora */
1441             CE_ReplaceOPC (L[0], OP65_ORA);
1442
1443             /* Invert the branch */
1444             CE_ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1445
1446             /* Delete the subroutine call */
1447             CS_DelEntry (S, I+2);
1448
1449             /* Remember, we had changes */
1450             ++Changes;
1451
1452         }
1453
1454         /* Next entry */
1455         ++I;
1456
1457     }
1458
1459     /* Return the number of changes made */
1460     return Changes;
1461 }
1462
1463
1464
1465 static unsigned OptNegAX4 (CodeSeg* S)
1466 /* Search for the sequence:
1467  *
1468  *      jsr     xxx
1469  *      jsr     bnega(x)
1470  *      jeq/jne ...
1471  *
1472  * and replace it by:
1473  *
1474  *      jsr     xxx
1475  *      <boolean test>
1476  *      jne/jeq ...
1477  */
1478 {
1479     unsigned Changes = 0;
1480
1481     /* Walk over the entries */
1482     unsigned I = 0;
1483     while (I < CS_GetEntryCount (S)) {
1484
1485         CodeEntry* L[2];
1486
1487         /* Get next entry */
1488         CodeEntry* E = CS_GetEntry (S, I);
1489
1490         /* Check for the sequence */
1491         if (E->OPC == OP65_JSR                  &&
1492             CS_GetEntries (S, L, I+1, 2)        &&
1493             L[0]->OPC == OP65_JSR               &&
1494             strncmp (L[0]->Arg,"bnega",5) == 0  &&
1495             !CE_HasLabel (L[0])                 &&
1496             (L[1]->Info & OF_ZBRA) != 0         &&
1497             !CE_HasLabel (L[1])) {
1498
1499             CodeEntry* X;
1500
1501             /* Check if we're calling bnega or bnegax */
1502             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1503
1504             /* Insert apropriate test code */
1505             if (ByteSized) {
1506                 /* Test bytes */
1507                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
1508                 CS_InsertEntry (S, X, I+2);
1509             } else {
1510                 /* Test words */
1511                 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
1512                 CS_InsertEntry (S, X, I+2);
1513                 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
1514                 CS_InsertEntry (S, X, I+3);
1515             }
1516
1517             /* Delete the subroutine call */
1518             CS_DelEntry (S, I+1);
1519
1520             /* Invert the branch */
1521             CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1522
1523             /* Remember, we had changes */
1524             ++Changes;
1525
1526         }
1527
1528         /* Next entry */
1529         ++I;
1530
1531     }
1532
1533     /* Return the number of changes made */
1534     return Changes;
1535 }
1536
1537
1538
1539 /*****************************************************************************/
1540 /*                     Optimize stores through pointers                      */
1541 /*****************************************************************************/
1542
1543
1544
1545 static unsigned OptPtrStore1Sub (CodeSeg* S, unsigned I, CodeEntry** const L)
1546 /* Check if this is one of the allowed suboperation for OptPtrStore1 */
1547 {
1548     /* Check for a label attached to the entry */
1549     if (CE_HasLabel (L[0])) {
1550         return 0;
1551     }
1552
1553     /* Check for single insn sub ops */
1554     if (L[0]->OPC == OP65_AND                                           ||
1555         L[0]->OPC == OP65_EOR                                           ||
1556         L[0]->OPC == OP65_ORA                                           ||
1557         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shlax", 5) == 0) ||
1558         (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shrax", 5) == 0)) {
1559
1560         /* One insn */
1561         return 1;
1562
1563     } else if (L[0]->OPC == OP65_CLC                      &&
1564                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
1565                L[1]->OPC == OP65_ADC                      &&
1566                !CE_HasLabel (L[1])) {
1567         return 2;
1568     } else if (L[0]->OPC == OP65_SEC                      &&
1569                (L[1] = CS_GetNextEntry (S, I)) != 0       &&
1570                L[1]->OPC == OP65_SBC                      &&
1571                !CE_HasLabel (L[1])) {
1572         return 2;
1573     }
1574
1575
1576
1577     /* Not found */
1578     return 0;
1579 }
1580
1581
1582
1583 static unsigned OptPtrStore1 (CodeSeg* S)
1584 /* Search for the sequence:
1585  *
1586  *      jsr     pushax
1587  *      ldy     xxx
1588  *      jsr     ldauidx
1589  *      subop
1590  *      ldy     yyy
1591  *      jsr     staspidx
1592  *
1593  * and replace it by:
1594  *
1595  *      sta     ptr1
1596  *      stx     ptr1+1
1597  *      ldy     xxx
1598  *      ldx     #$00
1599  *      lda     (ptr1),y
1600  *      subop
1601  *      ldy     yyy
1602  *      sta     (ptr1),y
1603  */
1604 {
1605     unsigned Changes = 0;
1606
1607     /* Walk over the entries */
1608     unsigned I = 0;
1609     while (I < CS_GetEntryCount (S)) {
1610
1611         unsigned K;
1612         CodeEntry* L[10];
1613
1614         /* Get next entry */
1615         L[0] = CS_GetEntry (S, I);
1616
1617         /* Check for the sequence */
1618         if (L[0]->OPC == OP65_JSR                   &&
1619             strcmp (L[0]->Arg, "pushax") == 0       &&
1620             CS_GetEntries (S, L+1, I+1, 3)          &&
1621             L[1]->OPC == OP65_LDY                   &&
1622             CE_KnownImm (L[1])                      &&
1623             !CE_HasLabel (L[1])                     &&
1624             L[2]->OPC == OP65_JSR                   &&
1625             strcmp (L[2]->Arg, "ldauidx") == 0      &&
1626             !CE_HasLabel (L[2])                     &&
1627             (K = OptPtrStore1Sub (S, I+3, L+3)) > 0 &&
1628             CS_GetEntries (S, L+3+K, I+3+K, 2)      &&
1629             L[3+K]->OPC == OP65_LDY                 &&
1630             CE_KnownImm (L[3+K])                    &&
1631             !CE_HasLabel (L[3+K])                   &&
1632             L[4+K]->OPC == OP65_JSR                 &&
1633             strcmp (L[4+K]->Arg, "staspidx") == 0   &&
1634             !CE_HasLabel (L[4+K])) {
1635
1636             CodeEntry* X;
1637
1638             /* Create and insert the stores */
1639             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1640             CS_InsertEntry (S, X, I+1);
1641
1642             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1643             CS_InsertEntry (S, X, I+2);
1644
1645             /* Delete the call to pushax */
1646             CS_DelEntry (S, I);
1647
1648             /* Delete the call to ldauidx */
1649             CS_DelEntry (S, I+3);
1650
1651             /* Insert the load from ptr1 */
1652             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
1653             CS_InsertEntry (S, X, I+3);
1654             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[2]->LI);
1655             CS_InsertEntry (S, X, I+4);
1656
1657             /* Insert the store through ptr1 */
1658             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1659             CS_InsertEntry (S, X, I+6+K);
1660
1661             /* Delete the call to staspidx */
1662             CS_DelEntry (S, I+7+K);
1663
1664             /* Remember, we had changes */
1665             ++Changes;
1666
1667         }
1668
1669         /* Next entry */
1670         ++I;
1671
1672     }
1673
1674     /* Return the number of changes made */
1675     return Changes;
1676 }
1677
1678
1679
1680 static unsigned OptPtrStore2 (CodeSeg* S)
1681 /* Search for the sequence:
1682  *
1683  *      jsr     pushax
1684  *      lda     xxx
1685  *      ldy     yyy
1686  *      jsr     staspidx
1687  *
1688  * and replace it by:
1689  *
1690  *      sta     ptr1
1691  *      stx     ptr1+1
1692  *      lda     xxx
1693  *      ldy     yyy
1694  *      sta     (ptr1),y
1695  */
1696 {
1697     unsigned Changes = 0;
1698
1699     /* Walk over the entries */
1700     unsigned I = 0;
1701     while (I < CS_GetEntryCount (S)) {
1702
1703         CodeEntry* L[4];
1704
1705         /* Get next entry */
1706         L[0] = CS_GetEntry (S, I);
1707
1708         /* Check for the sequence */
1709         if (L[0]->OPC == OP65_JSR               &&
1710             strcmp (L[0]->Arg, "pushax") == 0   &&
1711             CS_GetEntries (S, L+1, I+1, 3)      &&
1712             L[1]->OPC == OP65_LDA               &&
1713             !CE_HasLabel (L[1])                 &&
1714             L[2]->OPC == OP65_LDY               &&
1715             !CE_HasLabel (L[2])                 &&
1716             L[3]->OPC == OP65_JSR               &&
1717             strcmp (L[3]->Arg, "staspidx") == 0 &&
1718             !CE_HasLabel (L[3])) {
1719
1720             CodeEntry* X;
1721
1722             /* Create and insert the stores */
1723             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1724             CS_InsertEntry (S, X, I+1);
1725
1726             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1727             CS_InsertEntry (S, X, I+2);
1728
1729             /* Delete the call to pushax */
1730             CS_DelEntry (S, I);
1731
1732             /* Insert the store through ptr1 */
1733             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1734             CS_InsertEntry (S, X, I+4);
1735
1736             /* Delete the call to staspidx */
1737             CS_DelEntry (S, I+5);
1738
1739             /* Remember, we had changes */
1740             ++Changes;
1741
1742         }
1743
1744         /* Next entry */
1745         ++I;
1746
1747     }
1748
1749     /* Return the number of changes made */
1750     return Changes;
1751 }
1752
1753
1754
1755 /*****************************************************************************/
1756 /*                      Optimize loads through pointers                      */
1757 /*****************************************************************************/
1758
1759
1760
1761 static unsigned OptPtrLoad1 (CodeSeg* S)
1762 /* Search for the sequence:
1763  *
1764  *      tax
1765  *      dey
1766  *      lda     (sp),y             # May be any destination
1767  *      ldy     ...
1768  *      jsr     ldauidx
1769  *
1770  * and replace it by:
1771  *
1772  *      sta     ptr1+1
1773  *      dey
1774  *      lda     (sp),y
1775  *      sta     ptr1
1776  *      ldy     ...
1777  *      ldx     #$00
1778  *      lda     (ptr1),y
1779  */
1780 {
1781     unsigned Changes = 0;
1782
1783     /* Walk over the entries */
1784     unsigned I = 0;
1785     while (I < CS_GetEntryCount (S)) {
1786
1787         CodeEntry* L[5];
1788
1789         /* Get next entry */
1790         L[0] = CS_GetEntry (S, I);
1791
1792         /* Check for the sequence */
1793         if (L[0]->OPC == OP65_TAX               &&
1794             CS_GetEntries (S, L+1, I+1, 4)      &&
1795             L[1]->OPC == OP65_DEY               &&
1796             !CE_HasLabel (L[1])                 &&
1797             L[2]->OPC == OP65_LDA               &&
1798             !CE_HasLabel (L[2])                 &&
1799             L[3]->OPC == OP65_LDY               &&
1800             !CE_HasLabel (L[3])                 &&
1801             L[4]->OPC == OP65_JSR               &&
1802             strcmp (L[4]->Arg, "ldauidx") == 0  &&
1803             !CE_HasLabel (L[4])) {
1804
1805             CodeEntry* X;
1806
1807             /* Store the high byte and remove the TAX instead */
1808             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1809             CS_InsertEntry (S, X, I+1);
1810             CS_DelEntry (S, I);
1811
1812             /* Store the low byte */
1813             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[2]->LI);
1814             CS_InsertEntry (S, X, I+3);
1815
1816             /* Delete the call to ldauidx */
1817             CS_DelEntry (S, I+5);
1818
1819             /* Load high and low byte */
1820             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
1821             CS_InsertEntry (S, X, I+5);
1822             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1823             CS_InsertEntry (S, X, I+6);
1824
1825             /* Remember, we had changes */
1826             ++Changes;
1827
1828         }
1829
1830         /* Next entry */
1831         ++I;
1832
1833     }
1834
1835     /* Return the number of changes made */
1836     return Changes;
1837 }
1838
1839
1840
1841 static unsigned OptPtrLoad2 (CodeSeg* S)
1842 /* Search for the sequence
1843  *
1844  *      ldy     ...
1845  *      jsr     ldauidx
1846  *
1847  * and replace it by:
1848  *
1849  *      ldy     ...
1850  *      stx     ptr1+1
1851  *      sta     ptr1
1852  *      ldx     #$00
1853  *      lda     (ptr1),y
1854  *
1855  * This step must be execute *after* OptPtrLoad1!
1856  */
1857 {
1858     unsigned Changes = 0;
1859
1860     /* Walk over the entries */
1861     unsigned I = 0;
1862     while (I < CS_GetEntryCount (S)) {
1863
1864         CodeEntry* L[2];
1865
1866         /* Get next entry */
1867         L[0] = CS_GetEntry (S, I);
1868
1869         /* Check for the sequence */
1870         if (L[0]->OPC == OP65_LDY               &&
1871             CS_GetEntries (S, L+1, I+1, 1)      &&
1872             L[1]->OPC == OP65_JSR               &&
1873             strcmp (L[1]->Arg, "ldauidx") == 0  &&
1874             !CE_HasLabel (L[1])) {
1875
1876             CodeEntry* X;
1877
1878             /* Store the high byte */
1879             X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1880             CS_InsertEntry (S, X, I+1);
1881
1882             /* Store the low byte */
1883             X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1884             CS_InsertEntry (S, X, I+2);
1885
1886             /* Delete the call to ldauidx */
1887             CS_DelEntry (S, I+3);
1888
1889             /* Load the high and low byte */
1890             X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
1891             CS_InsertEntry (S, X, I+3);
1892             X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
1893             CS_InsertEntry (S, X, I+4);
1894
1895             /* Remember, we had changes */
1896             ++Changes;
1897
1898         }
1899
1900         /* Next entry */
1901         ++I;
1902
1903     }
1904
1905     /* Return the number of changes made */
1906     return Changes;
1907 }
1908
1909
1910
1911 /*****************************************************************************/
1912 /*                                   Code                                    */
1913 /*****************************************************************************/
1914
1915
1916
1917 /* Types of optimization steps */
1918 enum {
1919     optPre,                     /* Repeated once */
1920     optPreMain,                 /* Repeated more than once */
1921     optMain,                    /* dito */
1922     optPostMain,                /* dito */
1923     optPost                     /* Repeated once */
1924 };
1925
1926 /* Table with all the optimization functions */
1927 typedef struct OptFunc OptFunc;
1928 struct OptFunc {
1929     unsigned        (*Func) (CodeSeg*); /* Optimizer function */
1930     const char*     Name;               /* Name of optimizer step */
1931     unsigned char   Type;               /* Type of this step */
1932     char            Disabled;           /* True if pass disabled */
1933 };
1934
1935 /* Macro that builds a table entry */
1936 #define OptEntry(func,type)     { func, #func, type, 0 }
1937
1938 /* Table with optimizer steps */
1939 static OptFunc OptFuncs [] = {
1940     /* Optimizes stores through pointers */
1941     OptEntry (OptPtrStore1, optPre),
1942     OptEntry (OptPtrStore2, optPre),
1943     /* Optimize loads through pointers */
1944     OptEntry (OptPtrLoad1, optMain),
1945     OptEntry (OptPtrLoad2, optMain),
1946     /* Optimize calls to nega */
1947     OptEntry (OptNegA1, optMain),
1948     OptEntry (OptNegA2, optMain),
1949     /* Optimize calls to negax */
1950     OptEntry (OptNegAX1, optPre),
1951     OptEntry (OptNegAX2, optPre),
1952     OptEntry (OptNegAX3, optPre),
1953     OptEntry (OptNegAX4, optPre),
1954     /* Optimize subtractions */
1955     OptEntry (OptSub1, optMain),
1956     OptEntry (OptSub2, optMain),
1957     /* Optimize additions */
1958     OptEntry (OptAdd1, optPre),
1959     OptEntry (OptAdd2, optMain),
1960     /* Optimize jump cascades */
1961     OptEntry (OptJumpCascades, optMain),
1962     /* Remove dead jumps */
1963     OptEntry (OptDeadJumps, optMain),
1964     /* Change jsr/rts to jmp */
1965     OptEntry (OptRTS, optMain),
1966     /* Remove dead code */
1967     OptEntry (OptDeadCode, optMain),
1968     /* Optimize jump targets */
1969     OptEntry (OptJumpTarget, optMain),
1970     /* Optimize conditional branches */
1971     OptEntry (OptCondBranches, optMain),
1972     /* Replace jumps to RTS by RTS */
1973     OptEntry (OptRTSJumps, optMain),
1974     /* Remove calls to the bool transformer subroutines */
1975     OptEntry (OptBoolTransforms, optMain),
1976     /* Optimize compares */
1977     OptEntry (OptCmp1, optMain),
1978     OptEntry (OptCmp2, optMain),
1979     OptEntry (OptCmp3, optMain),
1980     OptEntry (OptCmp4, optMain),
1981     OptEntry (OptCmp5, optMain),
1982     OptEntry (OptCmp6, optMain),
1983     /* Optimize tests */
1984     OptEntry (OptTest1, optMain),
1985     /* Remove unused loads */
1986     OptEntry (OptUnusedLoads, optMain),
1987     OptEntry (OptDuplicateLoads, optMain),
1988     OptEntry (OptStoreLoad, optMain),
1989     OptEntry (OptTransfers, optMain),
1990     /* Optimize branch distance */
1991     OptEntry (OptBranchDist, optPost),
1992 };
1993
1994
1995
1996 static OptFunc* FindOptStep (const char* Name)
1997 /* Find an optimizer step by name in the table and return a pointer. Print an
1998  * error and call AbEnd if not found.
1999  */
2000 {
2001     unsigned I;
2002
2003     /* Run all optimization steps */
2004     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2005         if (strcmp (OptFuncs[I].Name, Name) == 0) {
2006             /* Found */
2007             return OptFuncs+I;
2008         }
2009     }
2010
2011     /* Not found */
2012     AbEnd ("Optimization step `%s' not found", Name);
2013     return 0;
2014 }
2015
2016
2017
2018 void DisableOpt (const char* Name)
2019 /* Disable the optimization with the given name */
2020 {
2021     if (strcmp (Name, "any") == 0) {
2022         unsigned I;
2023         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2024             OptFuncs[I].Disabled = 1;
2025         }
2026     } else {
2027         OptFunc* F = FindOptStep (Name);
2028         F->Disabled = 1;
2029     }
2030 }
2031
2032
2033
2034 void EnableOpt (const char* Name)
2035 /* Enable the optimization with the given name */
2036 {
2037     if (strcmp (Name, "any") == 0) {
2038         unsigned I;
2039         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2040             OptFuncs[I].Disabled = 0;
2041         }
2042     } else {
2043         OptFunc* F = FindOptStep (Name);
2044         F->Disabled = 0;
2045     }
2046 }
2047
2048
2049
2050 void ListOptSteps (FILE* F)
2051 /* List all optimization steps */
2052 {
2053     unsigned I;
2054     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2055         fprintf (F, "%s\n", OptFuncs[I].Name);
2056     }
2057 }
2058
2059
2060
2061 static void RepeatOptStep (CodeSeg* S, unsigned char Type, unsigned Max)
2062 /* Repeat the optimizer step of type Type at may Max times */
2063 {
2064     unsigned I;
2065     unsigned Pass = 0;
2066     unsigned OptChanges;
2067
2068     /* Repeat max times of until there are no more changes */
2069     do {
2070         /* Reset the number of changes */
2071         OptChanges = 0;
2072
2073         /* Keep the user hapy */
2074         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
2075
2076         /* Run all optimization steps */
2077         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2078
2079             /* Get the table entry */
2080             const OptFunc* F = OptFuncs + I;
2081
2082             /* Check if the type matches */
2083             if (F->Type != Type) {
2084                 /* Skip it */
2085                 continue;
2086             }
2087
2088             /* Print the name of the following optimizer step */
2089             Print (stdout, 1, "    %s:%*s", F->Name, (int) (30-strlen(F->Name)), "");
2090
2091             /* Check if the step is disabled */
2092             if (F->Disabled) {
2093                 Print (stdout, 1, "Disabled\n");
2094             } else {
2095                 unsigned Changes = F->Func (S);
2096                 OptChanges += Changes;
2097                 Print (stdout, 1, "%u Changes\n", Changes);
2098             }
2099         }
2100
2101     } while (--Max > 0 && OptChanges > 0);
2102 }
2103
2104
2105
2106 void RunOpt (CodeSeg* S)
2107 /* Run the optimizer */
2108 {
2109
2110     /* If we shouldn't run the optimizer, bail out */
2111     if (!Optimize) {
2112         return;
2113     }
2114
2115     /* Print the name of the function we are working on */
2116     if (S->Func) {
2117         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
2118     } else {
2119         Print (stdout, 1, "Running optimizer for global code segment\n");
2120     }
2121
2122     /* Repeat all steps until there are no more changes */
2123     RepeatOptStep (S, optPre, 1);
2124     RepeatOptStep (S, optPreMain, 0xFFFF);
2125     RepeatOptStep (S, optMain, 0xFFFF);
2126     RepeatOptStep (S, optPostMain, 0xFFFF);
2127     RepeatOptStep (S, optPost, 1);
2128 }
2129
2130
2131