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