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 = GetCodeEntry (S, I);
 165
 166     /* Replace the conditional branch */
 167     switch (Cond) {
 168
 169         case CMP_EQ:
 170             ReplaceOPC (E, OP65_JEQ);
 171             break;
 172
 173         case CMP_NE:
 174             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 = GetNextCodeEntry (S, I)) == 0) {
 184                 /* No such entry */
 185                 Internal ("Invalid program flow");
 186             }
 187             L = GenCodeLabel (S, N);
 188             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 189             InsertCodeEntry (S, N, I);
 190             ReplaceOPC (E, OP65_JPL);
 191             break;
 192
 193         case CMP_GE:
 194             ReplaceOPC (E, OP65_JPL);
 195             break;
 196
 197         case CMP_LT:
 198             ReplaceOPC (E, OP65_JMI);
 199             break;
 200
 201         case CMP_LE:
 202             /* Replace by
 203              *     jmi Target
 204              *     jeq Target
 205              */
 206             ReplaceOPC (E, OP65_JMI);
 207             L = E->JumpTo;
 208             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 209             InsertCodeEntry (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 = GetNextCodeEntry (S, I)) == 0) {
 219                 /* No such entry */
 220                 Internal ("Invalid program flow");
 221             }
 222             L = GenCodeLabel (S, N);
 223             N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
 224             InsertCodeEntry (S, N, I);
 225             ReplaceOPC (E, OP65_JCS);
 226             break;
 227
 228         case CMP_UGE:
 229             ReplaceOPC (E, OP65_JCS);
 230             break;
 231
 232         case CMP_ULT:
 233             ReplaceOPC (E, OP65_JCC);
 234             break;
 235
 236         case CMP_ULE:
 237             /* Replace by
 238              *     jcc Target
 239              *     jeq Target
 240              */
 241             ReplaceOPC (E, OP65_JCC);
 242             L = E->JumpTo;
 243             N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
 244             InsertCodeEntry (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 IsBitOp (const CodeEntry* E)
 257 /* Check if E is one of the bit operations (and, or, eor) */
 258 {
 259     return (E->OPC == OP65_AND || E->OPC == OP65_ORA || E->OPC == OP65_EOR);
 260 }
 261
 262
 263
 264 static int IsCmpToZero (const CodeEntry* E)
 265 /* Check if the given instrcuction is a compare to zero instruction */
 266 {
 267     return (E->OPC == OP65_CMP            &&
 268             E->AM  == AM65_IMM            &&
 269             (E->Flags & CEF_NUMARG) != 0  &&
 270             E->Num == 0);
 271 }
 272
 273
 274
 275 static int IsSpLoad (const CodeEntry* E)
 276 /* Return true if this is the load of A from the stack */
 277 {
 278     return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
 279 }
 280
 281
 282
 283 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
 284                           CodeEntry** L, unsigned Count)
 285 /* Check if a 16 bit load of a local variable follows:
 286  *
 287  *      ldy     #$xx
 288  *      lda     (sp),y
 289  *      tax
 290  *      dey
 291  *      lda     (sp),y
 292  *
 293  * If so, read Count entries following the first ldy into L and return true
 294  * if this is possible. Otherwise return false.
 295  */
 296 {
 297     /* Be sure we read enough entries for the check */
 298     CHECK (Count >= 5);
 299
 300     /* Read the first entry */
 301     L[0] = GetCodeEntry (S, Index);
 302
 303     /* Check for the sequence */
 304     return (L[0]->OPC == OP65_LDY                     &&
 305             L[0]->AM == AM65_IMM                      &&
 306             (L[0]->Flags & CEF_NUMARG) != 0           &&
 307             GetCodeEntries (S, L+1, Index+1, Count-1) &&
 308             IsSpLoad (L[1])                           &&
 309             !CodeEntryHasLabel (L[1])                 &&
 310             L[2]->OPC == OP65_TAX                     &&
 311             !CodeEntryHasLabel (L[2])                 &&
 312             L[3]->OPC == OP65_DEY                     &&
 313             !CodeEntryHasLabel (L[3])                 &&
 314             IsSpLoad (L[4])                           &&
 315             !CodeEntryHasLabel (L[4]));
 316 }
 317
 318
 319
 320 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
 321 /* Check if the instructions at L are an immidiate compare of a/x:
 322  *
 323  *
 324  */
 325 {
 326     return (L[0]->OPC == OP65_CPX                              &&
 327             L[0]->AM == AM65_IMM                               &&
 328             (L[0]->Flags & CEF_NUMARG) != 0                    &&
 329             !CodeEntryHasLabel (L[0])                          &&
 330             (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE)   &&
 331             L[1]->JumpTo != 0                                  &&
 332             !CodeEntryHasLabel (L[1])                          &&
 333             L[2]->OPC == OP65_CMP                              &&
 334             L[2]->AM == AM65_IMM                                 &&
 335             (L[2]->Flags & CEF_NUMARG) != 0                    &&
 336             (L[3]->Info & OF_ZBRA) != 0                        &&
 337             L[3]->JumpTo != 0                                  &&
 338             (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
 339 }
 340
 341
 342
 343 /*****************************************************************************/
 344 /*             Remove calls to the bool transformer subroutines              */
 345 /*****************************************************************************/
 346
 347
 348
 349 static unsigned OptBoolTransforms (CodeSeg* S)
 350 /* Try to remove the call to boolean transformer routines where the call is
 351  * not really needed.
 352  */
 353 {
 354     unsigned Changes = 0;
 355
 356     /* Walk over the entries */
 357     unsigned I = 0;
 358     while (I < GetCodeEntryCount (S)) {
 359
 360         CodeEntry* N;
 361         cmp_t Cond;
 362
 363         /* Get next entry */
 364         CodeEntry* E = GetCodeEntry (S, I);
 365
 366         /* Check for a boolean transformer */
 367         if (E->OPC == OP65_JSR                           &&
 368             (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
 369             (N = GetNextCodeEntry (S, I)) != 0           &&
 370             (N->Info & OF_ZBRA) != 0) {
 371
 372             /* Make the boolean transformer unnecessary by changing the
 373              * the conditional jump to evaluate the condition flags that
 374              * are set after the compare directly. Note: jeq jumps if
 375              * the condition is not met, jne jumps if the condition is met.
 376              * Invert the code if we jump on condition not met.
 377              */
 378             if (GetBranchCond (N->OPC) == BC_EQ) {
 379                 /* Jumps if condition false, invert condition */
 380                 Cond = CmpInvertTab [Cond];
 381             }
 382
 383             /* Check if we can replace the code by something better */
 384             ReplaceCmp (S, I+1, Cond);
 385
 386             /* Remove the call to the bool transformer */
 387             DelCodeEntry (S, I);
 388
 389             /* Remember, we had changes */
 390             ++Changes;
 391
 392         }
 393
 394         /* Next entry */
 395         ++I;
 396
 397     }
 398
 399     /* Return the number of changes made */
 400     return Changes;
 401 }
 402
 403
 404
 405 /*****************************************************************************/
 406 /*                           Optimize subtractions                           */
 407 /*****************************************************************************/
 408
 409
 410
 411 static unsigned OptSub1 (CodeSeg* S)
 412 /* Search for the sequence
 413  *
 414  *      sbc     ...
 415  *      bcs     L
 416  *      dex
 417  * L:
 418  *
 419  * and remove the handling of the high byte if X is not used later.
 420  */
 421 {
 422     unsigned Changes = 0;
 423
 424     /* Walk over the entries */
 425     unsigned I = 0;
 426     while (I < GetCodeEntryCount (S)) {
 427
 428         CodeEntry* L[3];
 429
 430         /* Get next entry */
 431         CodeEntry* E = GetCodeEntry (S, I);
 432
 433         /* Check for the sequence */
 434         if (E->OPC == OP65_SBC                               &&
 435             GetCodeEntries (S, L, I+1, 3)                    &&
 436             (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) &&
 437             L[0]->JumpTo != 0                                &&
 438             !CodeEntryHasLabel (L[0])                        &&
 439             L[1]->OPC == OP65_DEX                            &&
 440             !CodeEntryHasLabel (L[1])                        &&
 441             L[0]->JumpTo->Owner == L[2]                      &&
 442             !RegXUsed (S, I+3)) {
 443
 444             /* Remove the bcs/dex */
 445             DelCodeEntries (S, I+1, 2);
 446
 447             /* Remember, we had changes */
 448             ++Changes;
 449
 450         }
 451
 452         /* Next entry */
 453         ++I;
 454
 455     }
 456
 457     /* Return the number of changes made */
 458     return Changes;
 459 }
 460
 461
 462
 463 static unsigned OptSub2 (CodeSeg* S)
 464 /* Search for the sequence
 465  *
 466  *      lda     xx
 467  *      sec
 468  *      sta     tmp1
 469  *      lda     yy
 470  *      sbc     tmp1
 471  *      sta     yy
 472  *
 473  * and replace it by
 474  *
 475  *      sec
 476  *      lda     yy
 477  *      sbc     xx
 478  *      sta     yy
 479  */
 480 {
 481     unsigned Changes = 0;
 482
 483     /* Walk over the entries */
 484     unsigned I = 0;
 485     while (I < GetCodeEntryCount (S)) {
 486
 487         CodeEntry* L[5];
 488
 489         /* Get next entry */
 490         CodeEntry* E = GetCodeEntry (S, I);
 491
 492         /* Check for the sequence */
 493         if (E->OPC == OP65_LDA                             &&
 494             GetCodeEntries (S, L, I+1, 5)                  &&
 495             L[0]->OPC == OP65_SEC                          &&
 496             !CodeEntryHasLabel (L[0])                      &&
 497             L[1]->OPC == OP65_STA                          &&
 498             strcmp (L[1]->Arg, "tmp1") == 0                &&
 499             !CodeEntryHasLabel (L[1])                      &&
 500             L[2]->OPC == OP65_LDA                          &&
 501             !CodeEntryHasLabel (L[2])                      &&
 502             L[3]->OPC == OP65_SBC                          &&
 503             strcmp (L[3]->Arg, "tmp1") == 0                &&
 504             !CodeEntryHasLabel (L[3])                      &&
 505             L[4]->OPC == OP65_STA                          &&
 506             strcmp (L[4]->Arg, L[2]->Arg) == 0             &&
 507             !CodeEntryHasLabel (L[4])) {
 508
 509             /* Remove the store to tmp1 */
 510             DelCodeEntry (S, I+2);
 511
 512             /* Remove the subtraction */
 513             DelCodeEntry (S, I+3);
 514
 515             /* Move the lda to the position of the subtraction and change the
 516              * op to SBC.
 517              */
 518             MoveCodeEntry (S, I, I+3);
 519             ReplaceOPC (E, OP65_SBC);
 520
 521             /* If the sequence head had a label, move this label back to the
 522              * head.
 523              */
 524             if (CodeEntryHasLabel (E)) {
 525                 MoveCodeLabels (S, E, L[0]);
 526             }
 527
 528             /* Remember, we had changes */
 529             ++Changes;
 530
 531         }
 532
 533         /* Next entry */
 534         ++I;
 535
 536     }
 537
 538     /* Return the number of changes made */
 539     return Changes;
 540 }
 541
 542
 543
 544 /*****************************************************************************/
 545 /*                            Optimize additions                             */
 546 /*****************************************************************************/
 547
 548
 549
 550 static unsigned OptAdd1 (CodeSeg* S)
 551 /* Search for the sequence
 552  *
 553  *      adc     ...
 554  *      bcc     L
 555  *      inx
 556  * L:
 557  *
 558  * and remove the handling of the high byte if X is not used later.
 559  */
 560 {
 561     unsigned Changes = 0;
 562
 563     /* Walk over the entries */
 564     unsigned I = 0;
 565     while (I < GetCodeEntryCount (S)) {
 566
 567         CodeEntry* L[3];
 568
 569         /* Get next entry */
 570         CodeEntry* E = GetCodeEntry (S, I);
 571
 572         /* Check for the sequence */
 573         if (E->OPC == OP65_ADC                               &&
 574             GetCodeEntries (S, L, I+1, 3)                    &&
 575             (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
 576             L[0]->JumpTo != 0                                &&
 577             !CodeEntryHasLabel (L[0])                        &&
 578             L[1]->OPC == OP65_INX                            &&
 579             !CodeEntryHasLabel (L[1])                        &&
 580             L[0]->JumpTo->Owner == L[2]                      &&
 581             !RegXUsed (S, I+3)) {
 582
 583             /* Remove the bcs/dex */
 584             DelCodeEntries (S, I+1, 2);
 585
 586             /* Remember, we had changes */
 587             ++Changes;
 588
 589         }
 590
 591         /* Next entry */
 592         ++I;
 593
 594     }
 595
 596     /* Return the number of changes made */
 597     return Changes;
 598 }
 599
 600
 601
 602 /*****************************************************************************/
 603 /*                        Optimizations for compares                         */
 604 /*****************************************************************************/
 605
 606
 607
 608 static unsigned OptCmp1 (CodeSeg* S)
 609 /* Search for the sequence
 610  *
 611  *      stx     xx
 612  *      stx     tmp1
 613  *      ora     tmp1
 614  *
 615  * and replace it by
 616  *
 617  *      stx     xx
 618  *      ora     xx
 619  */
 620 {
 621     unsigned Changes = 0;
 622
 623     /* Walk over the entries */
 624     unsigned I = 0;
 625     while (I < GetCodeEntryCount (S)) {
 626
 627         CodeEntry* L[2];
 628
 629         /* Get next entry */
 630         CodeEntry* E = GetCodeEntry (S, I);
 631
 632         /* Check for the sequence */
 633         if (E->OPC == OP65_STX                  &&
 634             GetCodeEntries (S, L, I+1, 2)       &&
 635             L[0]->OPC == OP65_STX               &&
 636             strcmp (L[0]->Arg, "tmp1") == 0     &&
 637             !CodeEntryHasLabel (L[0])           &&
 638             L[1]->OPC == OP65_ORA               &&
 639             strcmp (L[1]->Arg, "tmp1") == 0     &&
 640             !CodeEntryHasLabel (L[1])) {
 641
 642             /* Remove the remaining instructions */
 643             DelCodeEntries (S, I+1, 2);
 644
 645             /* Insert the ora instead */
 646             InsertCodeEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
 647
 648             /* Remember, we had changes */
 649             ++Changes;
 650
 651         }
 652
 653         /* Next entry */
 654         ++I;
 655
 656     }
 657
 658     /* Return the number of changes made */
 659     return Changes;
 660 }
 661
 662
 663
 664 static unsigned OptCmp2 (CodeSeg* S)
 665 /* Search for
 666  *
 667  *      lda/and/ora/eor ...
 668  *      cmp #$00
 669  *      jeq/jne
 670  *
 671  * and remove the cmp.
 672  */
 673 {
 674     unsigned Changes = 0;
 675
 676     /* Walk over the entries */
 677     unsigned I = 0;
 678     while (I < GetCodeEntryCount (S)) {
 679
 680         CodeEntry* L[2];
 681
 682         /* Get next entry */
 683         CodeEntry* E = GetCodeEntry (S, I);
 684
 685         /* Check for the sequence */
 686         if ((E->OPC == OP65_LDA || IsBitOp (E))   &&
 687             GetCodeEntries (S, L, I+1, 2)         &&
 688             IsCmpToZero (L[0])                    &&
 689             !CodeEntryHasLabel (L[0])             &&
 690             (L[1]->Info & OF_FBRA) != 0           &&
 691             !CodeEntryHasLabel (L[1])) {
 692
 693             /* Remove the compare */
 694             DelCodeEntry (S, I+1);
 695
 696             /* Remember, we had changes */
 697             ++Changes;
 698
 699         }
 700
 701         /* Next entry */
 702         ++I;
 703
 704     }
 705
 706     /* Return the number of changes made */
 707     return Changes;
 708 }
 709
 710
 711
 712 static unsigned OptCmp3 (CodeSeg* S)
 713 /* Search for
 714  *
 715  *      lda     x
 716  *      ldx     y
 717  *      cpx     #a
 718  *      bne     L1
 719  *      cmp     #b
 720  *      jne/jeq L2
 721  *
 722  * If a is zero, we may remove the compare. If a and b are both zero, we may
 723  * replace it by the sequence
 724  *
 725  *      lda     x
 726  *      ora     x+1
 727  *      jne/jeq ...
 728  *
 729  * L1 may be either the label at the branch instruction, or the target label
 730  * of this instruction.
 731  */
 732 {
 733     unsigned Changes = 0;
 734
 735     /* Walk over the entries */
 736     unsigned I = 0;
 737     while (I < GetCodeEntryCount (S)) {
 738
 739         CodeEntry* L[5];
 740
 741         /* Get next entry */
 742         CodeEntry* E = GetCodeEntry (S, I);
 743
 744         /* Check for the sequence */
 745         if (E->OPC == OP65_LDA               &&
 746             GetCodeEntries (S, L, I+1, 5)    &&
 747             L[0]->OPC == OP65_LDX            &&
 748             !CodeEntryHasLabel (L[0])        &&
 749             IsImmCmp16 (S, L+1)) {
 750
 751             if (L[1]->Num == 0 && L[3]->Num == 0) {
 752                 /* The value is zero, we may use the simple code version. */
 753                 ReplaceOPC (L[0], OP65_ORA);
 754                 DelCodeEntries (S, I+2, 3);
 755             } else {
 756                 /* Move the lda instruction after the first branch. This will
 757                  * improve speed, since the load is delayed after the first
 758                  * test.
 759                  */
 760                 MoveCodeEntry (S, I, I+4);
 761
 762                 /* We will replace the ldx/cpx by lda/cmp */
 763                 ReplaceOPC (L[0], OP65_LDA);
 764                 ReplaceOPC (L[1], OP65_CMP);
 765
 766                 /* Beware: If the first LDA instruction had a label, we have
 767                  * to move this label to the top of the sequence again.
 768                  */
 769                 if (CodeEntryHasLabel (E)) {
 770                     MoveCodeLabels (S, E, L[0]);
 771                 }
 772
 773             }
 774
 775             ++Changes;
 776         }
 777
 778         /* Next entry */
 779         ++I;
 780
 781     }
 782
 783     /* Return the number of changes made */
 784     return Changes;
 785 }
 786
 787
 788
 789 static unsigned OptCmp4 (CodeSeg* S)
 790 /* Optimize compares of local variables:
 791  *
 792  *      ldy     #o
 793  *      lda     (sp),y
 794  *      tax
 795  *      dey
 796  *      lda     (sp),y
 797  *      cpx     #a
 798  *      bne     L1
 799  *      cmp     #b
 800  *      jne/jeq L2
 801  */
 802 {
 803     unsigned Changes = 0;
 804
 805     /* Walk over the entries */
 806     unsigned I = 0;
 807     while (I < GetCodeEntryCount (S)) {
 808
 809         CodeEntry* L[9];
 810
 811         /* Check for the sequence */
 812         if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
 813
 814             if (L[5]->Num == 0 && L[7]->Num == 0) {
 815
 816                 /* The value is zero, we may use the simple code version:
 817                  *      ldy     #o
 818                  *      lda     (sp),y
 819                  *      dey
 820                  *      ora     (sp),y
 821                  *      jne/jeq ...
 822                  */
 823                 ReplaceOPC (L[4], OP65_ORA);
 824                 DelCodeEntries (S, I+5, 3);   /* cpx/bne/cmp */
 825                 DelCodeEntry (S, I+2);        /* tax */
 826
 827             } else {
 828
 829                 /* Change the code to just use the A register. Move the load
 830                  * of the low byte after the first branch if possible:
 831                  *
 832                  *      ldy     #o
 833                  *      lda     (sp),y
 834                  *      cmp     #a
 835                  *      bne     L1
 836                  *      dey
 837                  *      lda     (sp),y
 838                  *      cmp     #b
 839                  *      jne/jeq ...
 840                  */
 841                 DelCodeEntry (S, I+2);         /* tax */
 842                 ReplaceOPC (L[5], OP65_CMP);   /* cpx -> cmp */
 843                 MoveCodeEntry (S, I+4, I+2);   /* cmp */
 844                 MoveCodeEntry (S, I+5, I+3);   /* bne */
 845
 846             }
 847
 848             ++Changes;
 849         }
 850
 851         /* Next entry */
 852         ++I;
 853
 854     }
 855
 856     /* Return the number of changes made */
 857     return Changes;
 858 }
 859
 860
 861
 862 static unsigned OptCmp5 (CodeSeg* S)
 863 /* Search for calls to compare subroutines followed by a conditional branch
 864  * and replace them by cheaper versions, since the branch means that the
 865  * boolean value returned by these routines is not needed (we may also check
 866  * that explicitly, but for the current code generator it is always true).
 867  */
 868 {
 869     unsigned Changes = 0;
 870
 871     /* Walk over the entries */
 872     unsigned I = 0;
 873     while (I < GetCodeEntryCount (S)) {
 874
 875         CodeEntry* N;
 876         cmp_t Cond;
 877
 878         /* Get next entry */
 879         CodeEntry* E = GetCodeEntry (S, I);
 880
 881         /* Check for the sequence */
 882         if (E->OPC == OP65_JSR                          &&
 883             (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
 884             (N = GetNextCodeEntry (S, I)) != 0          &&
 885             (N->Info & OF_ZBRA) != 0                    &&
 886             !CodeEntryHasLabel (N)) {
 887
 888             /* The tos... functions will return a boolean value in a/x and
 889              * the Z flag says if this value is zero or not. We will call
 890              * a cheaper subroutine instead, one that does not return a
 891              * boolean value but only valid flags. Note: jeq jumps if
 892              * the condition is not met, jne jumps if the condition is met.
 893              * Invert the code if we jump on condition not met.
 894              */
 895             if (GetBranchCond (N->OPC) == BC_EQ) {
 896                 /* Jumps if condition false, invert condition */
 897                 Cond = CmpInvertTab [Cond];
 898             }
 899
 900             /* Replace the subroutine call. */
 901             E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
 902             InsertCodeEntry (S, E, I+1);
 903             DelCodeEntry (S, I);
 904
 905             /* Replace the conditional branch */
 906             ReplaceCmp (S, I+1, Cond);
 907
 908             /* Remember, we had changes */
 909             ++Changes;
 910
 911         }
 912
 913         /* Next entry */
 914         ++I;
 915
 916     }
 917
 918     /* Return the number of changes made */
 919     return Changes;
 920 }
 921
 922
 923
 924 /*****************************************************************************/
 925 /*                            nega optimizations                             */
 926 /*****************************************************************************/
 927
 928
 929
 930 static unsigned OptNegA1 (CodeSeg* S)
 931 /* Check for
 932  *
 933  *      ldx     #$00
 934  *      lda     ..
 935  *      jsr     bnega
 936  *
 937  * Remove the ldx if the lda does not use it.
 938  */
 939 {
 940     unsigned Changes = 0;
 941
 942     /* Walk over the entries */
 943     unsigned I = 0;
 944     while (I < GetCodeEntryCount (S)) {
 945
 946         CodeEntry* L[2];
 947
 948         /* Get next entry */
 949         CodeEntry* E = GetCodeEntry (S, I);
 950
 951         /* Check for a ldx */
 952         if (E->OPC == OP65_LDX                  &&
 953             E->AM == AM65_IMM                   &&
 954             (E->Flags & CEF_NUMARG) != 0        &&
 955             E->Num == 0                         &&
 956             GetCodeEntries (S, L, I+1, 2)       &&
 957             L[0]->OPC == OP65_LDA               &&
 958             (L[0]->Use & REG_X) == 0            &&
 959             L[1]->OPC == OP65_JSR               &&
 960             strcmp (L[1]->Arg, "bnega") == 0) {
 961
 962             /* Remove the ldx instruction */
 963             DelCodeEntry (S, I);
 964
 965             /* Remember, we had changes */
 966             ++Changes;
 967
 968         }
 969
 970         /* Next entry */
 971         ++I;
 972
 973     }
 974
 975     /* Return the number of changes made */
 976     return Changes;
 977 }
 978
 979
 980
 981 static unsigned OptNegA2 (CodeSeg* S)
 982 /* Check for
 983  *
 984  *      lda     ..
 985  *      jsr     bnega
 986  *      jeq/jne ..
 987  *
 988  * Adjust the conditional branch and remove the call to the subroutine.
 989  */
 990 {
 991     unsigned Changes = 0;
 992
 993     /* Walk over the entries */
 994     unsigned I = 0;
 995     while (I < GetCodeEntryCount (S)) {
 996
 997         CodeEntry* L[2];
 998
 999         /* Get next entry */
1000         CodeEntry* E = GetCodeEntry (S, I);
1001
1002         /* Check for the sequence */
1003         if (E->OPC == OP65_LDA                  &&
1004             GetCodeEntries (S, L, I+1, 2)       &&
1005             L[0]->OPC == OP65_JSR               &&
1006             strcmp (L[0]->Arg, "bnega") == 0    &&
1007             !CodeEntryHasLabel (L[0])           &&
1008             (L[1]->Info & OF_ZBRA) != 0) {
1009
1010             /* Invert the branch */
1011             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1012
1013             /* Delete the subroutine call */
1014             DelCodeEntry (S, I+1);
1015
1016             /* Remember, we had changes */
1017             ++Changes;
1018
1019         }
1020
1021         /* Next entry */
1022         ++I;
1023
1024     }
1025
1026     /* Return the number of changes made */
1027     return Changes;
1028 }
1029
1030
1031
1032 /*****************************************************************************/
1033 /*                            negax optimizations                            */
1034 /*****************************************************************************/
1035
1036
1037
1038 static unsigned OptNegAX1 (CodeSeg* S)
1039 /* Search for the sequence:
1040  *
1041  *      lda     (xx),y
1042  *      tax
1043  *      dey
1044  *      lda     (xx),y
1045  *      jsr     bnegax
1046  *      jne/jeq ...
1047  *
1048  * and replace it by
1049  *
1050  *      lda     (xx),y
1051  *      dey
1052  *      ora     (xx),y
1053  *      jeq/jne ...
1054  */
1055 {
1056     unsigned Changes = 0;
1057
1058     /* Walk over the entries */
1059     unsigned I = 0;
1060     while (I < GetCodeEntryCount (S)) {
1061
1062         CodeEntry* L[5];
1063
1064         /* Get next entry */
1065         CodeEntry* E = GetCodeEntry (S, I);
1066
1067         /* Check for the sequence */
1068         if (E->OPC == OP65_LDA                  &&
1069             E->AM == AM65_ZP_INDY               &&
1070             GetCodeEntries (S, L, I+1, 5)       &&
1071             L[0]->OPC == OP65_TAX               &&
1072             L[1]->OPC == OP65_DEY               &&
1073             L[2]->OPC == OP65_LDA               &&
1074             L[2]->AM == AM65_ZP_INDY            &&
1075             strcmp (L[2]->Arg, E->Arg) == 0     &&
1076             !CodeEntryHasLabel (L[2])           &&
1077             L[3]->OPC == OP65_JSR               &&
1078             strcmp (L[3]->Arg, "bnegax") == 0   &&
1079             !CodeEntryHasLabel (L[3])           &&
1080             (L[4]->Info & OF_ZBRA) != 0) {
1081
1082             /* lda --> ora */
1083             ReplaceOPC (L[2], OP65_ORA);
1084
1085             /* Invert the branch */
1086             ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1087
1088             /* Delete the entries no longer needed. Beware: Deleting entries
1089              * will change the indices.
1090              */
1091             DelCodeEntry (S, I+4);              /* jsr bnegax */
1092             DelCodeEntry (S, I+1);              /* tax */
1093
1094             /* Remember, we had changes */
1095             ++Changes;
1096
1097         }
1098
1099         /* Next entry */
1100         ++I;
1101
1102     }
1103
1104     /* Return the number of changes made */
1105     return Changes;
1106 }
1107
1108
1109
1110 static unsigned OptNegAX2 (CodeSeg* S)
1111 /* Search for the sequence:
1112  *
1113  *      lda     xx
1114  *      ldx     yy
1115  *      jsr     bnegax
1116  *      jne/jeq ...
1117  *
1118  * and replace it by
1119  *
1120  *      lda     xx
1121  *      ora     xx+1
1122  *      jeq/jne ...
1123  */
1124 {
1125     unsigned Changes = 0;
1126
1127     /* Walk over the entries */
1128     unsigned I = 0;
1129     while (I < GetCodeEntryCount (S)) {
1130
1131         CodeEntry* L[3];
1132
1133         /* Get next entry */
1134         CodeEntry* E = GetCodeEntry (S, I);
1135
1136         /* Check for the sequence */
1137         if (E->OPC == OP65_LDA                  &&
1138             GetCodeEntries (S, L, I+1, 3)       &&
1139             L[0]->OPC == OP65_LDX               &&
1140             !CodeEntryHasLabel (L[0])           &&
1141             L[1]->OPC == OP65_JSR               &&
1142             strcmp (L[1]->Arg, "bnegax") == 0   &&
1143             !CodeEntryHasLabel (L[1])           &&
1144             (L[2]->Info & OF_ZBRA) != 0) {
1145
1146             /* ldx --> ora */
1147             ReplaceOPC (L[0], OP65_ORA);
1148
1149             /* Invert the branch */
1150             ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1151
1152             /* Delete the subroutine call */
1153             DelCodeEntry (S, I+2);
1154
1155             /* Remember, we had changes */
1156             ++Changes;
1157
1158         }
1159
1160         /* Next entry */
1161         ++I;
1162
1163     }
1164
1165     /* Return the number of changes made */
1166     return Changes;
1167 }
1168
1169
1170
1171 static unsigned OptNegAX3 (CodeSeg* S)
1172 /* Search for the sequence:
1173  *
1174  *      jsr     _xxx
1175  *      jsr     bnega(x)
1176  *      jeq/jne ...
1177  *
1178  * and replace it by:
1179  *
1180  *      jsr     _xxx
1181  *      <boolean test>
1182  *      jne/jeq ...
1183  */
1184 {
1185     unsigned Changes = 0;
1186
1187     /* Walk over the entries */
1188     unsigned I = 0;
1189     while (I < GetCodeEntryCount (S)) {
1190
1191         CodeEntry* L[2];
1192
1193         /* Get next entry */
1194         CodeEntry* E = GetCodeEntry (S, I);
1195
1196         /* Check for the sequence */
1197         if (E->OPC == OP65_JSR                  &&
1198             E->Arg[0] == '_'                    &&
1199             GetCodeEntries (S, L, I+1, 2)       &&
1200             L[0]->OPC == OP65_JSR               &&
1201             strncmp (L[0]->Arg,"bnega",5) == 0  &&
1202             !CodeEntryHasLabel (L[0])           &&
1203             (L[1]->Info & OF_ZBRA) != 0) {
1204
1205             CodeEntry* X;
1206
1207             /* Check if we're calling bnega or bnegax */
1208             int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1209
1210             /* Insert apropriate test code */
1211             if (ByteSized) {
1212                 /* Test bytes */
1213                 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
1214                 InsertCodeEntry (S, X, I+2);
1215             } else {
1216                 /* Test words */
1217                 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
1218                 InsertCodeEntry (S, X, I+2);
1219                 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
1220                 InsertCodeEntry (S, X, I+3);
1221             }
1222
1223             /* Delete the subroutine call */
1224             DelCodeEntry (S, I+1);
1225
1226             /* Invert the branch */
1227             ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1228
1229             /* Remember, we had changes */
1230             ++Changes;
1231
1232         }
1233
1234         /* Next entry */
1235         ++I;
1236
1237     }
1238
1239     /* Return the number of changes made */
1240     return Changes;
1241 }
1242
1243
1244
1245 /*****************************************************************************/
1246 /*                                   Code                                    */
1247 /*****************************************************************************/
1248
1249
1250
1251 /* Table with all the optimization functions */
1252 typedef struct OptFunc OptFunc;
1253 struct OptFunc {
1254     unsigned (*Func) (CodeSeg*);/* Optimizer function */
1255     const char* Name;           /* Name of optimizer step */
1256     char        Disabled;       /* True if pass disabled */
1257 };
1258
1259
1260
1261 /* Table with optimizer steps -  are called in this order */
1262 static OptFunc OptFuncs [] = {
1263     /* Optimize subtractions */
1264     { OptSub1,              "OptSub1",                  0       },
1265     { OptSub2,              "OptSub2",                  0       },
1266     /* Optimize additions */
1267     { OptAdd1,              "OptAdd1",                  0       },
1268     /* Optimize jump cascades */
1269     { OptJumpCascades,      "OptJumpCascades",          0       },
1270     /* Remove dead jumps */
1271     { OptDeadJumps,         "OptDeadJumps",             0       },
1272     /* Change jsr/rts to jmp */
1273     { OptRTS,               "OptRTS",                   0       },
1274     /* Remove dead code */
1275     { OptDeadCode,          "OptDeadCode",              0       },
1276     /* Optimize jump targets */
1277     { OptJumpTarget,        "OptJumpTarget",            0       },
1278     /* Optimize conditional branches */
1279     { OptCondBranches,      "OptCondBranches",          0       },
1280     /* Replace jumps to RTS by RTS */
1281     { OptRTSJumps,          "OptRTSJumps",              0       },
1282     /* Remove calls to the bool transformer subroutines */
1283     { OptBoolTransforms,    "OptBoolTransforms",        0       },
1284     /* Optimize calls to nega */
1285     { OptNegA1,             "OptNegA1",                 0       },
1286     { OptNegA2,             "OptNegA2",                 0       },
1287     /* Optimize calls to negax */
1288     { OptNegAX1,            "OptNegAX1",                0       },
1289     { OptNegAX2,            "OptNegAX2",                0       },
1290     { OptNegAX3,            "OptNegAX3",                0       },
1291     /* Optimize compares */
1292     { OptCmp1,              "OptCmp1",                  0       },
1293     { OptCmp2,              "OptCmp2",                  0       },
1294     { OptCmp3,              "OptCmp3",                  0       },
1295     { OptCmp4,              "OptCmp4",                  0       },
1296     { OptCmp5,              "OptCmp5",                  0       },
1297     /* Remove unused loads */
1298     { OptUnusedLoads,       "OptUnusedLoads",           0       },
1299     /* Optimize branch distance */
1300     { OptBranchDist,        "OptBranchDist",            0       },
1301 };
1302
1303
1304
1305 static OptFunc* FindOptStep (const char* Name)
1306 /* Find an optimizer step by name in the table and return a pointer. Print an
1307  * error and call AbEnd if not found.
1308  */
1309 {
1310     unsigned I;
1311
1312     /* Run all optimization steps */
1313     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1314         if (strcmp (OptFuncs[I].Name, Name) == 0) {
1315             /* Found */
1316             return OptFuncs+I;
1317         }
1318     }
1319
1320     /* Not found */
1321     AbEnd ("Optimization step `%s' not found", Name);
1322     return 0;
1323 }
1324
1325
1326
1327 void DisableOpt (const char* Name)
1328 /* Disable the optimization with the given name */
1329 {
1330     if (strcmp (Name, "any") == 0) {
1331         unsigned I;
1332         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1333             OptFuncs[I].Disabled = 1;
1334         }
1335     } else {
1336         OptFunc* F = FindOptStep (Name);
1337         F->Disabled = 1;
1338     }
1339 }
1340
1341
1342
1343 void EnableOpt (const char* Name)
1344 /* Enable the optimization with the given name */
1345 {
1346     if (strcmp (Name, "any") == 0) {
1347         unsigned I;
1348         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1349             OptFuncs[I].Disabled = 0;
1350         }
1351     } else {
1352         OptFunc* F = FindOptStep (Name);
1353         F->Disabled = 0;
1354     }
1355 }
1356
1357
1358
1359 void RunOpt (CodeSeg* S)
1360 /* Run the optimizer */
1361 {
1362     unsigned I;
1363     unsigned Pass = 0;
1364     unsigned OptChanges;
1365
1366     /* If we shouldn't run the optimizer, bail out */
1367     if (!Optimize) {
1368         return;
1369     }
1370
1371     /* Print the name of the function we are working on */
1372     if (S->Func) {
1373         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
1374     } else {
1375         Print (stdout, 1, "Running optimizer for global code segment\n");
1376     }
1377
1378     /* Repeat all steps until there are no more changes */
1379     do {
1380         /* Reset the number of changes */
1381         OptChanges = 0;
1382
1383         /* Keep the user hapy */
1384         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
1385
1386         /* Run all optimization steps */
1387         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
1388
1389             /* Print the name of the following optimizer step */
1390             Print (stdout, 1, "    %s:%*s", OptFuncs[I].Name,
1391                    (int) (30-strlen(OptFuncs[I].Name)), "");
1392
1393             /* Check if the step is disabled */
1394             if (OptFuncs[I].Disabled) {
1395                 Print (stdout, 1, "Disabled\n");
1396             } else {
1397                 unsigned Changes = OptFuncs[I].Func (S);
1398                 OptChanges += Changes;
1399                 Print (stdout, 1, "%u Changes\n", Changes);
1400             }
1401         }
1402
1403     } while (OptChanges > 0);
1404 }
1405
1406
1407