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

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 coptstop.c                                */
   4 /*                                                                           */
   5 /*           Optimize operations that take operands via the stack            */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2001-2009 Ullrich von Bassewitz                                       */
  10 /*               Roemerstrasse 52                                            */
  11 /*               D-70794 Filderstadt                                         */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <stdlib.h>
  37
  38 /* common */
  39 #include "chartype.h"
  40
  41 /* cc65 */
  42 #include "codeent.h"
  43 #include "codeinfo.h"
  44 #include "coptstop.h"
  45
  46
  47
  48 /*****************************************************************************/
  49 /*                            Load tracking data                             */
  50 /*****************************************************************************/
  51
  52
  53
  54 /* LoadRegInfo flags set by DirectOp */
  55 typedef enum {
  56   LI_NONE               = 0x00,
  57   LI_DIRECT             = 0x01,         /* Direct op may be used */
  58   LI_RELOAD_Y           = 0x02,         /* Reload index register Y */
  59   LI_REMOVE             = 0x04,         /* Load may be removed */
  60 } LI_FLAGS;
  61
  62 /* Structure that tells us how to load the lhs values */
  63 typedef struct LoadRegInfo LoadRegInfo;
  64 struct LoadRegInfo {
  65     int                 LoadIndex;      /* Index of load insn, -1 if invalid */
  66     CodeEntry*          LoadEntry;      /* The actual entry, 0 if invalid */
  67     LI_FLAGS            Flags;          /* Tells us how to load */
  68     unsigned char       Offs;           /* Stack offset if data is on stack */
  69 };
  70
  71 /* Now combined for both registers */
  72 typedef struct LoadInfo LoadInfo;
  73 struct LoadInfo {
  74     LoadRegInfo         A;              /* Info for A register */
  75     LoadRegInfo         X;              /* Info for X register */
  76     LoadRegInfo         Y;              /* Info for Y register */
  77 };
  78
  79
  80
  81 /*****************************************************************************/
  82 /*                                   Data                                    */
  83 /*****************************************************************************/
  84
  85
  86
  87 /* Flags for the functions */
  88 typedef enum {
  89     OP_NONE             = 0x00,         /* Nothing special */
  90     OP_A_KNOWN          = 0x01,         /* Value of A must be known */
  91     OP_X_ZERO           = 0x02,         /* X must be zero */
  92     OP_LHS_LOAD         = 0x04,         /* Must have load insns for LHS */
  93     OP_LHS_LOAD_DIRECT  = 0x0C,         /* Must have direct load insn for LHS */
  94     OP_RHS_LOAD         = 0x10,         /* Must have load insns for RHS */
  95     OP_RHS_LOAD_DIRECT  = 0x30,         /* Must have direct load insn for RHS */
  96 } OP_FLAGS;
  97
  98 /* Structure forward decl */
  99 typedef struct StackOpData StackOpData;
 100
 101 /* Structure that describes an optimizer subfunction for a specific op */
 102 typedef unsigned (*OptFunc) (StackOpData* D);
 103 typedef struct OptFuncDesc OptFuncDesc;
 104 struct OptFuncDesc {
 105     const char*         Name;           /* Name of the replaced runtime function */
 106     OptFunc             Func;           /* Function pointer */
 107     unsigned            UnusedRegs;     /* Regs that must not be used later */
 108     OP_FLAGS            Flags;          /* Flags */
 109 };
 110
 111 /* Structure that holds the needed data */
 112 struct StackOpData {
 113     CodeSeg*            Code;           /* Pointer to code segment */
 114     unsigned            Flags;          /* Flags to remember things */
 115
 116     /* Pointer to optimizer subfunction description */
 117     const OptFuncDesc*  OptFunc;
 118
 119     /* ZP register usage inside the sequence */
 120     unsigned            UsedRegs;
 121
 122     /* Register load information for lhs and rhs */
 123     LoadInfo            Lhs;
 124     LoadInfo            Rhs;
 125
 126     /* Several indices of insns in the code segment */
 127     int                 PushIndex;      /* Index of call to pushax in codeseg */
 128     int                 OpIndex;        /* Index of actual operation */
 129
 130     /* Pointers to insns in the code segment */
 131     CodeEntry*          PrevEntry;      /* Entry before the call to pushax */
 132     CodeEntry*          PushEntry;      /* Pointer to entry with call to pushax */
 133     CodeEntry*          OpEntry;        /* Pointer to entry with op */
 134     CodeEntry*          NextEntry;      /* Entry after the op */
 135
 136     const char*         ZPLo;           /* Lo byte of zero page loc to use */
 137     const char*         ZPHi;           /* Hi byte of zero page loc to use */
 138     unsigned            IP;             /* Insertion point used by some routines */
 139 };
 140
 141
 142
 143 /*****************************************************************************/
 144 /*                            Load tracking code                             */
 145 /*****************************************************************************/
 146
 147
 148
 149 static void ClearLoadRegInfo (LoadRegInfo* RI)
 150 /* Clear a LoadRegInfo struct */
 151 {
 152     RI->LoadIndex = -1;
 153 }
 154
 155
 156
 157 static void FinalizeLoadRegInfo (LoadRegInfo* RI, CodeSeg* S)
 158 /* Prepare a LoadRegInfo struct for use */
 159 {
 160     /* Get the entry */
 161     if (RI->LoadIndex >= 0) {
 162         RI->LoadEntry = CS_GetEntry (S, RI->LoadIndex);
 163     } else {
 164         RI->LoadEntry = 0;
 165     }
 166     RI->Flags = LI_NONE;
 167 }
 168
 169
 170
 171 static void ClearLoadInfo (LoadInfo* LI)
 172 /* Clear a LoadInfo struct */
 173 {
 174     ClearLoadRegInfo (&LI->A);
 175     ClearLoadRegInfo (&LI->X);
 176     ClearLoadRegInfo (&LI->Y);
 177 }
 178
 179
 180
 181 static void AdjustLoadRegInfo (LoadRegInfo* RI, int DelIndex, int Change)
 182 /* Adjust a load register info struct after deleting or inserting an entry
 183  * with a given index
 184  */
 185 {
 186     CHECK (abs (Change) == 1);
 187     if (Change < 0) {
 188         /* Deletion */
 189         if (DelIndex < RI->LoadIndex) {
 190             --RI->LoadIndex;
 191         } else if (DelIndex == RI->LoadIndex) {
 192             /* Has been removed */
 193             RI->LoadIndex = -1;
 194             RI->LoadEntry = 0;
 195         }
 196     } else {
 197         /* Insertion */
 198         if (DelIndex <= RI->LoadIndex) {
 199             ++RI->LoadIndex;
 200         }
 201     }
 202 }
 203
 204
 205
 206 static void FinalizeLoadInfo (LoadInfo* LI, CodeSeg* S)
 207 /* Prepare a LoadInfo struct for use */
 208 {
 209     /* Get the entries */
 210     FinalizeLoadRegInfo (&LI->A, S);
 211     FinalizeLoadRegInfo (&LI->X, S);
 212     FinalizeLoadRegInfo (&LI->Y, S);
 213 }
 214
 215
 216
 217 static void AdjustLoadInfo (LoadInfo* LI, int DelIndex, int Change)
 218 /* Adjust a load info struct after deleting entry with a given index */
 219 {
 220     AdjustLoadRegInfo (&LI->A, DelIndex, Change);
 221     AdjustLoadRegInfo (&LI->X, DelIndex, Change);
 222     AdjustLoadRegInfo (&LI->Y, DelIndex, Change);
 223 }
 224
 225
 226
 227 static void TrackLoads (LoadInfo* LI, CodeEntry* E, int I)
 228 /* Track loads for a code entry */
 229 {
 230     if (E->Info & OF_LOAD) {
 231         if (E->Chg & REG_A) {
 232             LI->A.LoadIndex = I;
 233         }
 234         if (E->Chg & REG_X) {
 235             LI->X.LoadIndex = I;
 236         }
 237         if (E->Chg & REG_Y) {
 238             LI->Y.LoadIndex = I;
 239         }
 240     } else if (E->Info & OF_XFR) {
 241         switch (E->OPC) {
 242             case OP65_TAX: LI->X.LoadIndex = LI->A.LoadIndex; break;
 243             case OP65_TAY: LI->Y.LoadIndex = LI->A.LoadIndex; break;
 244             case OP65_TXA: LI->A.LoadIndex = LI->X.LoadIndex; break;
 245             case OP65_TYA: LI->A.LoadIndex = LI->Y.LoadIndex; break;
 246             default:                                          break;
 247         }
 248     } else if (CE_IsCallTo (E, "ldaxysp")) {
 249         /* Both registers set, Y changed */
 250         LI->A.LoadIndex = I;
 251         LI->X.LoadIndex = I;
 252         LI->Y.LoadIndex = -1;
 253     } else {
 254         if (E->Chg & REG_A) {
 255             LI->A.LoadIndex = -1;
 256         }
 257         if (E->Chg & REG_X) {
 258             LI->X.LoadIndex = -1;
 259         }
 260         if (E->Chg & REG_Y) {
 261             LI->Y.LoadIndex = -1;
 262         }
 263     }
 264 }
 265
 266
 267
 268 /*****************************************************************************/
 269 /*                                  Helpers                                  */
 270 /*****************************************************************************/
 271
 272
 273
 274 static void AdjustStackOffset (StackOpData* D, unsigned Offs)
 275 /* Adjust the offset for all stack accesses in the range PushIndex to OpIndex.
 276  * OpIndex is adjusted according to the insertions.
 277  */
 278 {
 279     /* Walk over all entries */
 280     int I = D->PushIndex + 1;
 281     while (I < D->OpIndex) {
 282
 283         CodeEntry* E = CS_GetEntry (D->Code, I);
 284
 285         int NeedCorrection = 0;
 286         if ((E->Use & REG_SP) != 0) {
 287
 288             /* Check for some things that should not happen */
 289             CHECK (E->AM == AM65_ZP_INDY || E->RI->In.RegY >= (short) Offs);
 290             CHECK (strcmp (E->Arg, "sp") == 0);
 291
 292             /* We need to correct this one */
 293             NeedCorrection = 1;
 294
 295         } else if (CE_IsCallTo (E, "ldaxysp")) {
 296
 297             /* We need to correct this one */
 298             NeedCorrection = 1;
 299
 300         }
 301
 302         if (NeedCorrection) {
 303
 304             /* Get the code entry before this one. If it's a LDY, adjust the
 305              * value.
 306              */
 307             CodeEntry* P = CS_GetPrevEntry (D->Code, I);
 308             if (P && P->OPC == OP65_LDY && CE_IsConstImm (P)) {
 309
 310                 /* The Y load is just before the stack access, adjust it */
 311                 CE_SetNumArg (P, P->Num - Offs);
 312
 313             } else {
 314
 315                 /* Insert a new load instruction before the stack access */
 316                 const char* Arg = MakeHexArg (E->RI->In.RegY - Offs);
 317                 CodeEntry* X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 318                 CS_InsertEntry (D->Code, X, I++);
 319
 320                 /* One more inserted entries */
 321                 ++D->OpIndex;
 322
 323             }
 324
 325             /* If we need the value of Y later, be sure to reload it */
 326             if (RegYUsed (D->Code, I+1)) {
 327                 const char* Arg = MakeHexArg (E->RI->In.RegY);
 328                 CodeEntry* X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
 329                 CS_InsertEntry (D->Code, X, I+1);
 330
 331                 /* One more inserted entries */
 332                 ++D->OpIndex;
 333
 334                 /* Skip this instruction in the next round */
 335                 ++I;
 336             }
 337         }
 338
 339         /* Next entry */
 340         ++I;
 341     }
 342 }
 343
 344
 345
 346 static void InsertEntry (StackOpData* D, CodeEntry* E, int Index)
 347 /* Insert a new entry. Depending on Index, D->PushIndex and D->OpIndex will
 348  * be adjusted by this function.
 349  */
 350 {
 351     /* Insert the entry into the code segment */
 352     CS_InsertEntry (D->Code, E, Index);
 353
 354     /* Adjust register loads if necessary */
 355     AdjustLoadInfo (&D->Lhs, Index, 1);
 356     AdjustLoadInfo (&D->Rhs, Index, 1);
 357
 358     /* Adjust the indices if necessary */
 359     if (D->PushEntry && Index <= D->PushIndex) {
 360         ++D->PushIndex;
 361     }
 362     if (D->OpEntry && Index <= D->OpIndex) {
 363         ++D->OpIndex;
 364     }
 365 }
 366
 367
 368
 369 static void DelEntry (StackOpData* D, int Index)
 370 /* Delete an entry. Depending on Index, D->PushIndex and D->OpIndex will be
 371  * adjusted by this function, and PushEntry/OpEntry may get invalidated.
 372  */
 373 {
 374     /* Delete the entry from the code segment */
 375     CS_DelEntry (D->Code, Index);
 376
 377     /* Adjust register loads if necessary */
 378     AdjustLoadInfo (&D->Lhs, Index, -1);
 379     AdjustLoadInfo (&D->Rhs, Index, -1);
 380
 381     /* Adjust the other indices if necessary */
 382     if (Index < D->PushIndex) {
 383         --D->PushIndex;
 384     } else if (Index == D->PushIndex) {
 385         D->PushEntry = 0;
 386     }
 387     if (Index < D->OpIndex) {
 388         --D->OpIndex;
 389     } else if (Index == D->OpIndex) {
 390         D->OpEntry = 0;
 391     }
 392 }
 393
 394
 395
 396 static void CheckOneDirectOp (LoadRegInfo* LI, unsigned char Offs)
 397 /* Check if the given entry is a lda instruction with an addressing mode
 398  * that allows us to replace it by another operation (like ora). If so, we may
 399  * use this location for the or and must not save the value in the zero
 400  * page location.
 401  */
 402 {
 403     /* Get the load entry */
 404     CodeEntry* E = LI->LoadEntry;
 405     if (E == 0) {
 406         /* No load insn */
 407         return;
 408     }
 409
 410     /* Check the load entry */
 411     if (E) {
 412         /* Must check the call first since addressing mode is ABS, so second
 413          * "if" will catch otherwise.
 414          */
 415         if (CE_IsCallTo (E, "ldaxysp")) {
 416             /* Same as single loads from stack. Since we must distinguish
 417              * between A and X here, the necessary offset is passed to the
 418              * function as a parameter.
 419              */
 420             LI->Offs = (unsigned char) E->RI->In.RegY - Offs;
 421             LI->Flags |= (LI_DIRECT | LI_RELOAD_Y);
 422         } else if (E->AM == AM65_IMM || E->AM == AM65_ZP || E->AM == AM65_ABS) {
 423             /* These insns are all ok and replaceable */
 424             LI->Flags |= LI_DIRECT;
 425         } else if (E->AM == AM65_ZP_INDY &&
 426                    RegValIsKnown (E->RI->In.RegY) &&
 427                    strcmp (E->Arg, "sp") == 0) {
 428             /* A load from the stack with known offset is also ok, but in this
 429              * case we must reload the index register later. Please note that
 430              * a load indirect via other zero page locations is not ok, since
 431              * these locations may change between the push and the actual
 432              * operation.
 433              */
 434             LI->Offs  = (unsigned char) E->RI->In.RegY;
 435             LI->Flags |= (LI_DIRECT | LI_RELOAD_Y);
 436         }
 437     }
 438 }
 439
 440
 441
 442 static void CheckDirectOp (StackOpData* D)
 443 /* Check if the given entry is a lda instruction with an addressing mode
 444  * that allows us to replace it by another operation (like ora). If so, we may
 445  * use this location for the or and must not save the value in the zero
 446  * page location.
 447  */
 448 {
 449     /* Check flags for all load instructions */
 450     CheckOneDirectOp (&D->Lhs.A, 1);
 451     CheckOneDirectOp (&D->Lhs.X, 0);
 452     CheckOneDirectOp (&D->Rhs.A, 1);
 453     CheckOneDirectOp (&D->Rhs.X, 0);
 454 }
 455
 456
 457
 458 static void AddStoreA (StackOpData* D)
 459 /* Add a store to zero page after the push insn */
 460 {
 461     CodeEntry* X = NewCodeEntry (OP65_STA, AM65_ZP, D->ZPLo, 0, D->PushEntry->LI);
 462     InsertEntry (D, X, D->PushIndex+1);
 463 }
 464
 465
 466
 467 static void AddStoreX (StackOpData* D)
 468 /* Add a store to zero page after the push insn */
 469 {
 470     CodeEntry* X = NewCodeEntry (OP65_STX, AM65_ZP, D->ZPHi, 0, D->PushEntry->LI);
 471     InsertEntry (D, X, D->PushIndex+1);
 472 }
 473
 474
 475
 476 static void ReplacePushByStore (StackOpData* D)
 477 /* Replace the call to the push subroutine by a store into the zero page
 478  * location (actually, the push is not replaced, because we need it for
 479  * later, but the name is still ok since the push will get removed at the
 480  * end of each routine).
 481  */
 482 {
 483     /* Store the value into the zeropage instead of pushing it. Check high
 484      * byte first so that the store is later in A/X order.
 485      */
 486     if ((D->Lhs.X.Flags & LI_DIRECT) == 0) {
 487         AddStoreX (D);
 488     }
 489     if ((D->Lhs.A.Flags & LI_DIRECT) == 0) {
 490         AddStoreA (D);
 491     }
 492 }
 493
 494
 495
 496 static void AddOpLow (StackOpData* D, opc_t OPC)
 497 /* Add an op for the low byte of an operator. This function honours the
 498  * OP_DIRECT and OP_RELOAD_Y flags and generates the necessary instructions.
 499  * All code is inserted at the current insertion point.
 500  */
 501 {
 502     CodeEntry* X;
 503
 504     if ((D->Lhs.A.Flags & LI_DIRECT) != 0) {
 505         /* Op with a variable location. If the location is on the stack, we
 506          * need to reload the Y register.
 507          */
 508         if ((D->Lhs.A.Flags & LI_RELOAD_Y) == 0) {
 509
 510             /* opc ... */
 511             CodeEntry* LoadA = D->Lhs.A.LoadEntry;
 512             X = NewCodeEntry (OPC, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
 513             InsertEntry (D, X, D->IP++);
 514
 515         } else {
 516
 517             /* ldy #offs */
 518             const char* Arg = MakeHexArg (D->Lhs.A.Offs);
 519             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 520             InsertEntry (D, X, D->IP++);
 521
 522             /* opc (sp),y */
 523             X = NewCodeEntry (OPC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
 524             InsertEntry (D, X, D->IP++);
 525
 526         }
 527
 528         /* In both cases, we can remove the load */
 529         D->Lhs.A.Flags |= LI_REMOVE;
 530
 531     } else {
 532
 533         /* Op with temp storage */
 534         X = NewCodeEntry (OPC, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
 535         InsertEntry (D, X, D->IP++);
 536
 537     }
 538 }
 539
 540
 541
 542 static void AddOpHigh (StackOpData* D, opc_t OPC)
 543 /* Add an op for the high byte of an operator. Special cases (constant values
 544  * or similar) have to be checked separately, the function covers only the
 545  * generic case. Code is inserted at the insertion point.
 546  */
 547 {
 548     CodeEntry* X;
 549
 550     /* pha */
 551     X = NewCodeEntry (OP65_PHA, AM65_IMP, 0, 0, D->OpEntry->LI);
 552     InsertEntry (D, X, D->IP++);
 553
 554     /* txa */
 555     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
 556     InsertEntry (D, X, D->IP++);
 557
 558     if ((D->Lhs.X.Flags & LI_DIRECT) != 0) {
 559
 560         if ((D->Lhs.X.Flags & LI_RELOAD_Y) == 0) {
 561
 562             /* opc xxx */
 563             CodeEntry* LoadX = D->Lhs.X.LoadEntry;
 564             X = NewCodeEntry (OPC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
 565             InsertEntry (D, X, D->IP++);
 566
 567         } else {
 568
 569             /* ldy #const */
 570             const char* Arg = MakeHexArg (D->Lhs.X.Offs);
 571             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 572             InsertEntry (D, X, D->IP++);
 573
 574             /* opc (sp),y */
 575             X = NewCodeEntry (OPC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
 576             InsertEntry (D, X, D->IP++);
 577         }
 578
 579         /* In both cases, we can remove the load */
 580         D->Lhs.X.Flags |= LI_REMOVE;
 581
 582     } else {
 583         /* opc zphi */
 584         X = NewCodeEntry (OPC, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 585         InsertEntry (D, X, D->IP++);
 586     }
 587
 588     /* tax */
 589     X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, D->OpEntry->LI);
 590     InsertEntry (D, X, D->IP++);
 591
 592     /* pla */
 593     X = NewCodeEntry (OP65_PLA, AM65_IMP, 0, 0, D->OpEntry->LI);
 594     InsertEntry (D, X, D->IP++);
 595 }
 596
 597
 598
 599 static void RemoveRegLoads (StackOpData* D, LoadInfo* LI)
 600 /* Remove register load insns */
 601 {
 602     /* Both registers may be loaded with one insn, but DelEntry will in this
 603      * case clear the other one.
 604      */
 605     if (LI->A.LoadIndex >= 0 && (LI->A.Flags & LI_REMOVE)) {
 606         DelEntry (D, LI->A.LoadIndex);
 607     }
 608     if (LI->X.LoadIndex >= 0 && (LI->X.Flags & LI_REMOVE)) {
 609         DelEntry (D, LI->X.LoadIndex);
 610     }
 611 }
 612
 613
 614
 615 static void RemoveRemainders (StackOpData* D)
 616 /* Remove the code that is unnecessary after translation of the sequence */
 617 {
 618     /* Remove the register loads for lhs and rhs */
 619     RemoveRegLoads (D, &D->Lhs);
 620     RemoveRegLoads (D, &D->Rhs);
 621
 622     /* Remove the push and the operator routine */
 623     DelEntry (D, D->OpIndex);
 624     DelEntry (D, D->PushIndex);
 625 }
 626
 627
 628
 629 static int IsRegVar (StackOpData* D)
 630 /* If the value pushed is that of a zeropage variable, replace ZPLo and ZPHi
 631  * in the given StackOpData struct by the variable and return true. Otherwise
 632  * leave D untouched and return false.
 633  */
 634 {
 635     CodeEntry*  LoadA = D->Lhs.A.LoadEntry;
 636     CodeEntry*  LoadX = D->Lhs.X.LoadEntry;
 637     unsigned    Len;
 638
 639     /* Must have both load insns */
 640     if (LoadA == 0 || LoadX == 0) {
 641         return 0;
 642     }
 643
 644     /* Must be loads from zp */
 645     if (LoadA->AM != AM65_ZP || LoadX->AM != AM65_ZP) {
 646         return 0;
 647     }
 648
 649     /* Must be the same zp loc with high byte in X */
 650     Len = strlen (LoadA->Arg);
 651     if (strncmp (LoadA->Arg, LoadX->Arg, Len) != 0      ||
 652         strcmp (LoadX->Arg + Len, "+1") != 0) {
 653         return 0;
 654     }
 655
 656     /* Use the zero page location directly */
 657     D->ZPLo = LoadA->Arg;
 658     D->ZPHi = LoadX->Arg;
 659     return 1;
 660 }
 661
 662
 663
 664 /*****************************************************************************/
 665 /*                       Actual optimization functions                       */
 666 /*****************************************************************************/
 667
 668
 669
 670 static unsigned Opt___bzero (StackOpData* D)
 671 /* Optimize the __bzero sequence if possible */
 672 {
 673     CodeEntry*  X;
 674     const char* Arg;
 675     CodeLabel*  L;
 676
 677     /* Check if we're using a register variable */
 678     if (!IsRegVar (D)) {
 679         /* Store the value into the zeropage instead of pushing it */
 680         AddStoreX (D);
 681         AddStoreA (D);
 682     }
 683
 684     /* If the return value of __bzero is used, we have to add code to reload
 685      * a/x from the pointer variable.
 686      */
 687     if (RegAXUsed (D->Code, D->OpIndex+1)) {
 688         X = NewCodeEntry (OP65_LDA, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
 689         InsertEntry (D, X, D->OpIndex+1);
 690         X = NewCodeEntry (OP65_LDX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 691         InsertEntry (D, X, D->OpIndex+2);
 692     }
 693
 694     /* X is always zero, A contains the size of the data area to zero.
 695      * Note: A may be zero, in which case the operation is null op.
 696      */
 697     if (D->OpEntry->RI->In.RegA != 0) {
 698
 699         /* lda #$00 */
 700         X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
 701         InsertEntry (D, X, D->OpIndex+1);
 702
 703         /* The value of A is known */
 704         if (D->OpEntry->RI->In.RegA <= 0x81) {
 705
 706             /* Loop using the sign bit */
 707
 708             /* ldy #count-1 */
 709             Arg = MakeHexArg (D->OpEntry->RI->In.RegA - 1);
 710             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 711             InsertEntry (D, X, D->OpIndex+2);
 712
 713             /* L: sta (zp),y */
 714             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 715             InsertEntry (D, X, D->OpIndex+3);
 716             L = CS_GenLabel (D->Code, X);
 717
 718             /* dey */
 719             X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, D->OpEntry->LI);
 720             InsertEntry (D, X, D->OpIndex+4);
 721
 722             /* bpl L */
 723             X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, D->OpEntry->LI);
 724             InsertEntry (D, X, D->OpIndex+5);
 725
 726         } else {
 727
 728             /* Loop using an explicit compare */
 729
 730             /* ldy #$00 */
 731             X = NewCodeEntry (OP65_LDY, AM65_IMM, "$00", 0, D->OpEntry->LI);
 732             InsertEntry (D, X, D->OpIndex+2);
 733
 734             /* L: sta (zp),y */
 735             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 736             InsertEntry (D, X, D->OpIndex+3);
 737             L = CS_GenLabel (D->Code, X);
 738
 739             /* iny */
 740             X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, D->OpEntry->LI);
 741             InsertEntry (D, X, D->OpIndex+4);
 742
 743             /* cpy #count */
 744             Arg = MakeHexArg (D->OpEntry->RI->In.RegA);
 745             X = NewCodeEntry (OP65_CPY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 746             InsertEntry (D, X, D->OpIndex+5);
 747
 748             /* bne L */
 749             X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 750             InsertEntry (D, X, D->OpIndex+6);
 751         }
 752
 753     }
 754
 755     /* Remove the push and the call to the __bzero function */
 756     RemoveRemainders (D);
 757
 758     /* We changed the sequence */
 759     return 1;
 760 }
 761
 762
 763
 764 static unsigned Opt_staspidx (StackOpData* D)
 765 /* Optimize the staspidx sequence if possible */
 766 {
 767     CodeEntry* X;
 768
 769     /* Check if we're using a register variable */
 770     if (!IsRegVar (D)) {
 771         /* Store the value into the zeropage instead of pushing it */
 772         AddStoreX (D);
 773         AddStoreA (D);
 774     }
 775
 776     /* Replace the store subroutine call by a direct op */
 777     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 778     InsertEntry (D, X, D->OpIndex+1);
 779
 780     /* Remove the push and the call to the staspidx function */
 781     RemoveRemainders (D);
 782
 783     /* We changed the sequence */
 784     return 1;
 785 }
 786
 787
 788
 789 static unsigned Opt_staxspidx (StackOpData* D)
 790 /* Optimize the staxspidx sequence if possible */
 791 {
 792     CodeEntry* X;
 793
 794     /* Check if we're using a register variable */
 795     if (!IsRegVar (D)) {
 796         /* Store the value into the zeropage instead of pushing it */
 797         AddStoreX (D);
 798         AddStoreA (D);
 799     }
 800
 801     /* Inline the store */
 802
 803     /* sta (zp),y */
 804     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 805     InsertEntry (D, X, D->OpIndex+1);
 806
 807     if (RegValIsKnown (D->OpEntry->RI->In.RegY)) {
 808         /* Value of Y is known */
 809         const char* Arg = MakeHexArg (D->OpEntry->RI->In.RegY + 1);
 810         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 811     } else {
 812         X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, D->OpEntry->LI);
 813     }
 814     InsertEntry (D, X, D->OpIndex+2);
 815
 816     if (RegValIsKnown (D->OpEntry->RI->In.RegX)) {
 817         /* Value of X is known */
 818         const char* Arg = MakeHexArg (D->OpEntry->RI->In.RegX);
 819         X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, D->OpEntry->LI);
 820     } else {
 821         /* Value unknown */
 822         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
 823     }
 824     InsertEntry (D, X, D->OpIndex+3);
 825
 826     /* sta (zp),y */
 827     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 828     InsertEntry (D, X, D->OpIndex+4);
 829
 830     /* If we remove staxspidx, we must restore the Y register to what the
 831      * function would return.
 832      */
 833     X = NewCodeEntry (OP65_LDY, AM65_IMM, "$00", 0, D->OpEntry->LI);
 834     InsertEntry (D, X, D->OpIndex+5);
 835
 836     /* Remove the push and the call to the staxspidx function */
 837     RemoveRemainders (D);
 838
 839     /* We changed the sequence */
 840     return 1;
 841 }
 842
 843
 844
 845 static unsigned Opt_tosaddax (StackOpData* D)
 846 /* Optimize the tosaddax sequence if possible */
 847 {
 848     CodeEntry*  X;
 849     CodeEntry*  N;
 850
 851     /* We need the entry behind the add */
 852     CHECK (D->NextEntry != 0);
 853
 854     /* Check if the X register is known and zero when the add is done, and
 855      * if the add is followed by
 856      *
 857      *  ldy     #$00
 858      *  jsr     ldauidx         ; or ldaidx
 859      *
 860      * If this is true, the addition does actually add an offset to a pointer
 861      * before it is dereferenced. Since both subroutines take an offset in Y,
 862      * we can pass the offset (instead of #$00) and remove the addition
 863      * alltogether.
 864      */
 865     if (D->OpEntry->RI->In.RegX == 0                            &&
 866         D->NextEntry->OPC == OP65_LDY                           &&
 867         CE_IsKnownImm (D->NextEntry, 0)                         &&
 868         !CE_HasLabel (D->NextEntry)                             &&
 869         (N = CS_GetNextEntry (D->Code, D->OpIndex + 1)) != 0    &&
 870         (CE_IsCallTo (N, "ldauidx")                     ||
 871          CE_IsCallTo (N, "ldaidx"))) {
 872
 873         int Signed = (strcmp (N->Arg, "ldaidx") == 0);
 874
 875         /* Store the value into the zeropage instead of pushing it */
 876         AddStoreX (D);
 877         AddStoreA (D);
 878
 879         /* Replace the ldy by a tay. Be sure to create the new entry before
 880          * deleting the ldy, since we will reference the line info from this
 881          * insn.
 882          */
 883         X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, D->NextEntry->LI);
 884         DelEntry (D, D->OpIndex + 1);
 885         InsertEntry (D, X, D->OpIndex + 1);
 886
 887         /* Replace the call to ldaidx/ldauidx. Since X is already zero, and
 888          * the ptr is in the zero page location, we just need to load from
 889          * the pointer, and fix X in case of ldaidx.
 890          */
 891         X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, D->ZPLo, 0, N->LI);
 892         DelEntry (D, D->OpIndex + 2);
 893         InsertEntry (D, X, D->OpIndex + 2);
 894         if (Signed) {
 895
 896             CodeLabel* L;
 897
 898             /* Add sign extension - N is unused now */
 899             N = CS_GetNextEntry (D->Code, D->OpIndex + 2);
 900             CHECK (N != 0);
 901             L = CS_GenLabel (D->Code, N);
 902
 903             X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, X->LI);
 904             InsertEntry (D, X, D->OpIndex + 3);
 905
 906             X = NewCodeEntry (OP65_DEX, AM65_IMP, 0, 0, X->LI);
 907             InsertEntry (D, X, D->OpIndex + 4);
 908         }
 909
 910     } else {
 911
 912         /* Store the value into the zeropage instead of pushing it */
 913         ReplacePushByStore (D);
 914
 915         /* Inline the add */
 916         D->IP = D->OpIndex+1;
 917
 918         /* clc */
 919         X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, D->OpEntry->LI);
 920         InsertEntry (D, X, D->IP++);
 921
 922         /* Low byte */
 923         AddOpLow (D, OP65_ADC);
 924
 925         /* High byte */
 926         if (D->PushEntry->RI->In.RegX == 0) {
 927             /* The high byte is the value in X plus the carry */
 928             CodeLabel* L = CS_GenLabel (D->Code, D->NextEntry);
 929             X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
 930             InsertEntry (D, X, D->IP++);
 931             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
 932             InsertEntry (D, X, D->IP++);
 933         } else if (D->OpEntry->RI->In.RegX == 0) {
 934             /* The high byte is that of the first operand plus carry */
 935             CodeLabel* L;
 936             if (RegValIsKnown (D->PushEntry->RI->In.RegX)) {
 937                 /* Value of first op high byte is known */
 938                 const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX);
 939                 X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
 940             } else {
 941                 /* Value of first op high byte is unknown */
 942                 X = NewCodeEntry (OP65_LDX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 943             }
 944             InsertEntry (D, X, D->IP++);
 945
 946             /* bcc label */
 947             L = CS_GenLabel (D->Code, D->NextEntry);
 948             X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
 949             InsertEntry (D, X, D->IP++);
 950
 951             /* inx */
 952             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
 953             InsertEntry (D, X, D->IP++);
 954         } else {
 955             /* High byte is unknown */
 956             AddOpHigh (D, OP65_ADC);
 957         }
 958     }
 959
 960     /* Remove the push and the call to the tosaddax function */
 961     RemoveRemainders (D);
 962
 963     /* We changed the sequence */
 964     return 1;
 965 }
 966
 967
 968
 969 static unsigned Opt_tosandax (StackOpData* D)
 970 /* Optimize the tosandax sequence if possible */
 971 {
 972     CodeEntry*  X;
 973
 974     /* Store the value into the zeropage instead of pushing it */
 975     ReplacePushByStore (D);
 976
 977     /* Inline the and, low byte */
 978     D->IP = D->OpIndex + 1;
 979     AddOpLow (D, OP65_AND);
 980
 981     /* High byte */
 982     if (D->PushEntry->RI->In.RegX == 0 || D->OpEntry->RI->In.RegX == 0) {
 983         /* The high byte is zero */
 984         X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
 985         InsertEntry (D, X, D->IP++);
 986     } else {
 987         /* High byte is unknown */
 988         AddOpHigh (D, OP65_AND);
 989     }
 990
 991     /* Remove the push and the call to the tosandax function */
 992     RemoveRemainders (D);
 993
 994     /* We changed the sequence */
 995     return 1;
 996 }
 997
 998
 999
1000 static unsigned Opt_tosgeax (StackOpData* D)
1001 /* Optimize the tosgeax sequence if possible. */
1002 {
1003     CodeEntry*  X;
1004     CodeLabel* L;
1005
1006     /* Inline the sbc */
1007     D->IP = D->OpIndex+1;
1008
1009     /* Must be true because of OP_RHS_LOAD */
1010     CHECK ((D->Rhs.A.Flags & LI_DIRECT) != 0);
1011
1012     /* If the location is on the stack, we need to reload the Y register. */
1013     if ((D->Rhs.A.Flags & LI_RELOAD_Y) == 0) {
1014
1015         /* cmp ... */
1016         CodeEntry* LoadA = D->Rhs.A.LoadEntry;
1017         X = NewCodeEntry (OP65_CMP, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
1018         InsertEntry (D, X, D->IP++);
1019
1020     } else {
1021
1022         /* ldy #offs */
1023         const char* Arg = MakeHexArg (D->Rhs.A.Offs);
1024         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1025         InsertEntry (D, X, D->IP++);
1026
1027         /* cmp (sp),y */
1028         X = NewCodeEntry (OP65_CMP, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1029         InsertEntry (D, X, D->IP++);
1030     }
1031
1032     /* In both cases, we can remove the load */
1033     D->Rhs.A.Flags |= LI_REMOVE;
1034
1035     /* txa */
1036     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
1037     InsertEntry (D, X, D->IP++);
1038
1039     /* Must be true because of OP_RHS_LOAD */
1040     CHECK ((D->Rhs.X.Flags & LI_DIRECT) != 0);
1041
1042     /* If the location is on the stack, we need to reload the Y register. */
1043     if ((D->Rhs.X.Flags & LI_RELOAD_Y) == 0) {
1044
1045         /* sbc ... */
1046         CodeEntry* LoadX = D->Rhs.X.LoadEntry;
1047         X = NewCodeEntry (OP65_SBC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
1048         InsertEntry (D, X, D->IP++);
1049
1050     } else {
1051
1052         /* ldy #offs */
1053         const char* Arg = MakeHexArg (D->Rhs.X.Offs);
1054         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1055         InsertEntry (D, X, D->IP++);
1056
1057         /* sbc (sp),y */
1058         X = NewCodeEntry (OP65_SBC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1059         InsertEntry (D, X, D->IP++);
1060     }
1061
1062     /* In both cases, we can remove the load */
1063     D->Rhs.X.Flags |= LI_REMOVE;
1064
1065     /* eor #$80 */
1066     X = NewCodeEntry (OP65_EOR, AM65_IMM, "$80", 0, D->OpEntry->LI);
1067     InsertEntry (D, X, D->IP++);
1068
1069     /* asl a */
1070     X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, D->OpEntry->LI);
1071     InsertEntry (D, X, D->IP++);
1072     L = CS_GenLabel (D->Code, X);
1073
1074     /* Insert a bvs L before the eor insn */
1075     X = NewCodeEntry (OP65_BVS, AM65_BRA, L->Name, L, D->OpEntry->LI);
1076     InsertEntry (D, X, D->IP - 2);
1077     ++D->IP;
1078
1079     /* lda #$00 */
1080     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1081     InsertEntry (D, X, D->IP++);
1082
1083     /* ldx #$00 */
1084     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1085     InsertEntry (D, X, D->IP++);
1086
1087     /* rol a */
1088     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1089     InsertEntry (D, X, D->IP++);
1090
1091     /* Remove the push and the call to the tosgeax function */
1092     RemoveRemainders (D);
1093
1094     /* We changed the sequence */
1095     return 1;
1096 }
1097
1098
1099
1100 static unsigned Opt_tosltax (StackOpData* D)
1101 /* Optimize the tosltax sequence if possible. */
1102 {
1103     CodeEntry*  X;
1104     CodeLabel* L;
1105
1106
1107     /* Inline the sbc */
1108     D->IP = D->OpIndex+1;
1109
1110     /* Must be true because of OP_RHS_LOAD */
1111     CHECK ((D->Rhs.A.Flags & LI_DIRECT) != 0);
1112
1113     /* If the location is on the stack, we need to reload the Y register. */
1114     if ((D->Rhs.A.Flags & LI_RELOAD_Y) == 0) {
1115
1116         /* cmp ... */
1117         CodeEntry* LoadA = D->Rhs.A.LoadEntry;
1118         X = NewCodeEntry (OP65_CMP, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
1119         InsertEntry (D, X, D->IP++);
1120
1121     } else {
1122
1123         /* ldy #offs */
1124         const char* Arg = MakeHexArg (D->Rhs.A.Offs);
1125         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1126         InsertEntry (D, X, D->IP++);
1127
1128         /* cmp (sp),y */
1129         X = NewCodeEntry (OP65_CMP, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1130         InsertEntry (D, X, D->IP++);
1131     }
1132
1133     /* In both cases, we can remove the load */
1134     D->Rhs.A.Flags |= LI_REMOVE;
1135
1136     /* txa */
1137     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
1138     InsertEntry (D, X, D->IP++);
1139
1140     /* Must be true because of OP_RHS_LOAD */
1141     CHECK ((D->Rhs.X.Flags & LI_DIRECT) != 0);
1142
1143     /* If the location is on the stack, we need to reload the Y register. */
1144     if ((D->Rhs.X.Flags & LI_RELOAD_Y) == 0) {
1145
1146         /* sbc ... */
1147         CodeEntry* LoadX = D->Rhs.X.LoadEntry;
1148         X = NewCodeEntry (OP65_SBC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
1149         InsertEntry (D, X, D->IP++);
1150
1151     } else {
1152
1153         /* ldy #offs */
1154         const char* Arg = MakeHexArg (D->Rhs.X.Offs);
1155         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1156         InsertEntry (D, X, D->IP++);
1157
1158         /* sbc (sp),y */
1159         X = NewCodeEntry (OP65_SBC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1160         InsertEntry (D, X, D->IP++);
1161     }
1162
1163     /* In both cases, we can remove the load */
1164     D->Rhs.X.Flags |= LI_REMOVE;
1165
1166     /* eor #$80 */
1167     X = NewCodeEntry (OP65_EOR, AM65_IMM, "$80", 0, D->OpEntry->LI);
1168     InsertEntry (D, X, D->IP++);
1169
1170     /* asl a */
1171     X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, D->OpEntry->LI);
1172     InsertEntry (D, X, D->IP++);
1173     L = CS_GenLabel (D->Code, X);
1174
1175     /* Insert a bvc L before the eor insn */
1176     X = NewCodeEntry (OP65_BVC, AM65_BRA, L->Name, L, D->OpEntry->LI);
1177     InsertEntry (D, X, D->IP - 2);
1178     ++D->IP;
1179
1180     /* lda #$00 */
1181     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1182     InsertEntry (D, X, D->IP++);
1183
1184     /* ldx #$00 */
1185     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1186     InsertEntry (D, X, D->IP++);
1187
1188     /* rol a */
1189     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1190     InsertEntry (D, X, D->IP++);
1191
1192     /* Remove the push and the call to the tosltax function */
1193     RemoveRemainders (D);
1194
1195     /* We changed the sequence */
1196     return 1;
1197 }
1198
1199
1200
1201 static unsigned Opt_tosorax (StackOpData* D)
1202 /* Optimize the tosorax sequence if possible */
1203 {
1204     CodeEntry*  X;
1205
1206     /* Store the value into the zeropage instead of pushing it */
1207     ReplacePushByStore (D);
1208
1209     /* Inline the or, low byte */
1210     D->IP = D->OpIndex + 1;
1211     AddOpLow (D, OP65_ORA);
1212
1213     /* High byte */
1214     if (RegValIsKnown (D->PushEntry->RI->In.RegX) &&
1215         RegValIsKnown (D->OpEntry->RI->In.RegX)) {
1216         /* Both values known, precalculate the result */
1217         unsigned char Result = D->PushEntry->RI->In.RegX | D->OpEntry->RI->In.RegX;
1218         const char* Arg = MakeHexArg (Result);
1219         X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
1220         InsertEntry (D, X, D->IP++);
1221     } else if (D->PushEntry->RI->In.RegX != 0) {
1222         /* High byte is unknown */
1223         AddOpHigh (D, OP65_ORA);
1224     }
1225
1226     /* Remove the push and the call to the tosorax function */
1227     RemoveRemainders (D);
1228
1229     /* We changed the sequence */
1230     return 1;
1231 }
1232
1233
1234
1235 static unsigned Opt_tossubax (StackOpData* D)
1236 /* Optimize the tossubax sequence if possible. Note: subtraction is not
1237  * commutative!
1238  */
1239 {
1240     CodeEntry*  X;
1241
1242
1243     /* Inline the sbc */
1244     D->IP = D->OpIndex+1;
1245
1246     /* sec */
1247     X = NewCodeEntry (OP65_SEC, AM65_IMP, 0, 0, D->OpEntry->LI);
1248     InsertEntry (D, X, D->IP++);
1249
1250     /* Must be true because of OP_RHS_LOAD */
1251     CHECK ((D->Rhs.A.Flags & LI_DIRECT) != 0);
1252
1253     /* If the location is on the stack, we need to reload the Y register. */
1254     if ((D->Rhs.A.Flags & LI_RELOAD_Y) == 0) {
1255
1256         /* sbc ... */
1257         CodeEntry* LoadA = D->Rhs.A.LoadEntry;
1258         X = NewCodeEntry (OP65_SBC, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
1259         InsertEntry (D, X, D->IP++);
1260
1261     } else {
1262
1263         /* ldy #offs */
1264         const char* Arg = MakeHexArg (D->Rhs.A.Offs);
1265         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1266         InsertEntry (D, X, D->IP++);
1267
1268         /* sbc (sp),y */
1269         X = NewCodeEntry (OP65_SBC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1270         InsertEntry (D, X, D->IP++);
1271     }
1272
1273     /* In both cases, we can remove the load */
1274     D->Rhs.A.Flags |= LI_REMOVE;
1275
1276     /* pha */
1277     X = NewCodeEntry (OP65_PHA, AM65_IMP, 0, 0, D->OpEntry->LI);
1278     InsertEntry (D, X, D->IP++);
1279
1280     /* txa */
1281     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
1282     InsertEntry (D, X, D->IP++);
1283
1284     /* Must be true because of OP_RHS_LOAD */
1285     CHECK ((D->Rhs.X.Flags & LI_DIRECT) != 0);
1286
1287     /* If the location is on the stack, we need to reload the Y register. */
1288     if ((D->Rhs.X.Flags & LI_RELOAD_Y) == 0) {
1289
1290         /* sbc ... */
1291         CodeEntry* LoadX = D->Rhs.X.LoadEntry;
1292         X = NewCodeEntry (OP65_SBC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
1293         InsertEntry (D, X, D->IP++);
1294
1295     } else {
1296
1297         /* ldy #offs */
1298         const char* Arg = MakeHexArg (D->Rhs.X.Offs);
1299         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1300         InsertEntry (D, X, D->IP++);
1301
1302         /* sbc (sp),y */
1303         X = NewCodeEntry (OP65_SBC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1304         InsertEntry (D, X, D->IP++);
1305     }
1306
1307     /* In both cases, we can remove the load */
1308     D->Rhs.X.Flags |= LI_REMOVE;
1309
1310     /* tax */
1311     X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, D->OpEntry->LI);
1312     InsertEntry (D, X, D->IP++);
1313
1314     /* pla */
1315     X = NewCodeEntry (OP65_PLA, AM65_IMP, 0, 0, D->OpEntry->LI);
1316     InsertEntry (D, X, D->IP++);
1317
1318     /* Remove the push and the call to the tossubax function */
1319     RemoveRemainders (D);
1320
1321     /* We changed the sequence */
1322     return 1;
1323 }
1324
1325
1326
1327 static unsigned Opt_tosugeax (StackOpData* D)
1328 /* Optimize the tosugeax sequence if possible. */
1329 {
1330     CodeEntry*  X;
1331
1332
1333     /* Inline the sbc */
1334     D->IP = D->OpIndex+1;
1335
1336     /* Must be true because of OP_RHS_LOAD */
1337     CHECK ((D->Rhs.A.Flags & LI_DIRECT) != 0);
1338
1339     /* If the location is on the stack, we need to reload the Y register. */
1340     if ((D->Rhs.A.Flags & LI_RELOAD_Y) == 0) {
1341
1342         /* cmp ... */
1343         CodeEntry* LoadA = D->Rhs.A.LoadEntry;
1344         X = NewCodeEntry (OP65_CMP, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
1345         InsertEntry (D, X, D->IP++);
1346
1347     } else {
1348
1349         /* ldy #offs */
1350         const char* Arg = MakeHexArg (D->Rhs.A.Offs);
1351         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1352         InsertEntry (D, X, D->IP++);
1353
1354         /* cmp (sp),y */
1355         X = NewCodeEntry (OP65_CMP, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1356         InsertEntry (D, X, D->IP++);
1357     }
1358
1359     /* In both cases, we can remove the load */
1360     D->Rhs.A.Flags |= LI_REMOVE;
1361
1362     /* txa */
1363     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
1364     InsertEntry (D, X, D->IP++);
1365
1366     /* Must be true because of OP_RHS_LOAD */
1367     CHECK ((D->Rhs.X.Flags & LI_DIRECT) != 0);
1368
1369     /* If the location is on the stack, we need to reload the Y register. */
1370     if ((D->Rhs.X.Flags & LI_RELOAD_Y) == 0) {
1371
1372         /* sbc ... */
1373         CodeEntry* LoadX = D->Rhs.X.LoadEntry;
1374         X = NewCodeEntry (OP65_SBC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
1375         InsertEntry (D, X, D->IP++);
1376
1377     } else {
1378
1379         /* ldy #offs */
1380         const char* Arg = MakeHexArg (D->Rhs.X.Offs);
1381         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
1382         InsertEntry (D, X, D->IP++);
1383
1384         /* sbc (sp),y */
1385         X = NewCodeEntry (OP65_SBC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
1386         InsertEntry (D, X, D->IP++);
1387     }
1388
1389     /* In both cases, we can remove the load */
1390     D->Rhs.X.Flags |= LI_REMOVE;
1391
1392     /* lda #$00 */
1393     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1394     InsertEntry (D, X, D->IP++);
1395
1396     /* ldx #$00 */
1397     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1398     InsertEntry (D, X, D->IP++);
1399
1400     /* rol a */
1401     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1402     InsertEntry (D, X, D->IP++);
1403
1404     /* Remove the push and the call to the tosugeax function */
1405     RemoveRemainders (D);
1406
1407     /* We changed the sequence */
1408     return 1;
1409 }
1410
1411
1412
1413 static unsigned Opt_tosxorax (StackOpData* D)
1414 /* Optimize the tosxorax sequence if possible */
1415 {
1416     CodeEntry*  X;
1417
1418
1419     /* Store the value into the zeropage instead of pushing it */
1420     ReplacePushByStore (D);
1421
1422     /* Inline the xor, low byte */
1423     D->IP = D->OpIndex + 1;
1424     AddOpLow (D, OP65_EOR);
1425
1426     /* High byte */
1427     if (RegValIsKnown (D->PushEntry->RI->In.RegX) &&
1428         RegValIsKnown (D->OpEntry->RI->In.RegX)) {
1429         /* Both values known, precalculate the result */
1430         const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX ^ D->OpEntry->RI->In.RegX);
1431         X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
1432         InsertEntry (D, X, D->IP++);
1433     } else if (D->PushEntry->RI->In.RegX != 0) {
1434         /* High byte is unknown */
1435         AddOpHigh (D, OP65_EOR);
1436     }
1437
1438     /* Remove the push and the call to the tosandax function */
1439     RemoveRemainders (D);
1440
1441     /* We changed the sequence */
1442     return 1;
1443 }
1444
1445
1446
1447 /*****************************************************************************/
1448 /*                                   Code                                    */
1449 /*****************************************************************************/
1450
1451
1452
1453 static const OptFuncDesc FuncTable[] = {
1454     { "__bzero",    Opt___bzero,   REG_NONE, OP_X_ZERO | OP_A_KNOWN     },
1455     { "staspidx",   Opt_staspidx,  REG_NONE, OP_NONE                    },
1456     { "staxspidx",  Opt_staxspidx, REG_AX,   OP_NONE                    },
1457     { "tosaddax",   Opt_tosaddax,  REG_NONE, OP_NONE                    },
1458     { "tosandax",   Opt_tosandax,  REG_NONE, OP_NONE                    },
1459     { "tosgeax",    Opt_tosgeax,   REG_NONE, OP_RHS_LOAD_DIRECT         },
1460     { "tosltax",    Opt_tosltax,   REG_NONE, OP_RHS_LOAD_DIRECT         },
1461     { "tosorax",    Opt_tosorax,   REG_NONE, OP_NONE                    },
1462     { "tossubax",   Opt_tossubax,  REG_NONE, OP_RHS_LOAD_DIRECT         },
1463     { "tosugeax",   Opt_tosugeax,  REG_NONE, OP_RHS_LOAD_DIRECT         },
1464     { "tosxorax",   Opt_tosxorax,  REG_NONE, OP_NONE                    },
1465 };
1466 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
1467
1468
1469
1470 static int CmpFunc (const void* Key, const void* Func)
1471 /* Compare function for bsearch */
1472 {
1473     return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
1474 }
1475
1476
1477
1478 static const OptFuncDesc* FindFunc (const char* Name)
1479 /* Find the function with the given name. Return a pointer to the table entry
1480  * or NULL if the function was not found.
1481  */
1482 {
1483     return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
1484 }
1485
1486
1487
1488 static int CmpHarmless (const void* Key, const void* Entry)
1489 /* Compare function for bsearch */
1490 {
1491     return strcmp (Key, *(const char**)Entry);
1492 }
1493
1494
1495
1496 static int HarmlessCall (const char* Name)
1497 /* Check if this is a call to a harmless subroutine that will not interrupt
1498  * the pushax/op sequence when encountered.
1499  */
1500 {
1501     static const char* Tab[] = {
1502         "aslax1",
1503         "aslax2",
1504         "asrax1",
1505         "asrax2",
1506         "bnegax",
1507         "ldaxidx",
1508         "ldaxysp",
1509         "negax",
1510         "shlax1",
1511         "shlax2",
1512         "shrax1",
1513         "shrax2",
1514     };
1515
1516     void* R = bsearch (Name,
1517                        Tab,
1518                        sizeof (Tab) / sizeof (Tab[0]),
1519                        sizeof (Tab[0]),
1520                        CmpHarmless);
1521     return (R != 0);
1522 }
1523
1524
1525
1526 static void ResetStackOpData (StackOpData* Data)
1527 /* Reset the given data structure */
1528 {
1529     Data->OptFunc       = 0;
1530     Data->UsedRegs      = REG_NONE;
1531
1532     ClearLoadInfo (&Data->Lhs);
1533     ClearLoadInfo (&Data->Rhs);
1534
1535     Data->PushIndex     = -1;
1536     Data->OpIndex       = -1;
1537 }
1538
1539
1540
1541 static int PreCondOk (StackOpData* D)
1542 /* Check if the preconditions for a call to the optimizer subfunction are
1543  * satisfied. As a side effect, this function will also choose the zero page
1544  * register to use.
1545  */
1546 {
1547     /* Check the flags */
1548     unsigned UnusedRegs = D->OptFunc->UnusedRegs;
1549     if (UnusedRegs != REG_NONE &&
1550         (GetRegInfo (D->Code, D->OpIndex+1, UnusedRegs) & UnusedRegs) != 0) {
1551         /* Cannot optimize */
1552         return 0;
1553     }
1554     if ((D->OptFunc->Flags & OP_A_KNOWN) != 0 &&
1555         RegValIsUnknown (D->OpEntry->RI->In.RegA)) {
1556         /* Cannot optimize */
1557         return 0;
1558     }
1559     if ((D->OptFunc->Flags & OP_X_ZERO) != 0 &&
1560         D->OpEntry->RI->In.RegX != 0) {
1561         /* Cannot optimize */
1562         return 0;
1563     }
1564     if ((D->OptFunc->Flags & OP_LHS_LOAD) != 0) {
1565         if (D->Lhs.A.LoadIndex < 0 || D->Lhs.X.LoadIndex < 0) {
1566             /* Cannot optimize */
1567             return 0;
1568         } else if ((D->OptFunc->Flags & OP_LHS_LOAD_DIRECT) != 0) {
1569             if ((D->Lhs.A.Flags & D->Lhs.X.Flags & LI_DIRECT) == 0) {
1570                 /* Cannot optimize */
1571                 return 0;
1572             }
1573         }
1574     }
1575     if ((D->OptFunc->Flags & OP_RHS_LOAD) != 0) {
1576         if (D->Rhs.A.LoadIndex < 0 || D->Rhs.X.LoadIndex < 0) {
1577             /* Cannot optimize */
1578             return 0;
1579         } else if ((D->OptFunc->Flags & OP_RHS_LOAD_DIRECT) != 0) {
1580             if ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) == 0) {
1581                 /* Cannot optimize */
1582                 return 0;
1583             }
1584         }
1585     }
1586
1587     /* Determine the zero page locations to use */
1588     if ((D->UsedRegs & REG_PTR1) == REG_NONE) {
1589         D->ZPLo = "ptr1";
1590         D->ZPHi = "ptr1+1";
1591     } else if ((D->UsedRegs & REG_SREG) == REG_NONE) {
1592         D->ZPLo = "sreg";
1593         D->ZPHi = "sreg+1";
1594     } else if ((D->UsedRegs & REG_PTR2) == REG_NONE) {
1595         D->ZPLo = "ptr2";
1596         D->ZPHi = "ptr2+1";
1597     } else {
1598         /* No registers available */
1599         return 0;
1600     }
1601
1602     /* Determine if we have a basic block */
1603     return CS_IsBasicBlock (D->Code, D->PushIndex, D->OpIndex);
1604 }
1605
1606
1607
1608 /*****************************************************************************/
1609 /*                                   Code                                    */
1610 /*****************************************************************************/
1611
1612
1613
1614 unsigned OptStackOps (CodeSeg* S)
1615 /* Optimize operations that take operands via the stack */
1616 {
1617     unsigned            Changes = 0;    /* Number of changes in one run */
1618     StackOpData         Data;
1619     unsigned            I;
1620
1621     enum {
1622         Initialize,
1623         Search,
1624         FoundPush,
1625         FoundOp
1626     } State = Initialize;
1627
1628
1629     /* Generate register info */
1630     CS_GenRegInfo (S);
1631
1632     /* Remember the code segment in the info struct */
1633     Data.Code = S;
1634
1635     /* Look for a call to pushax followed by a call to some other function
1636      * that takes it's first argument on the stack, and the second argument
1637      * in the primary register.
1638      * It depends on the code between the two if we can handle/transform the
1639      * sequence, so check this code for the following list of things:
1640      *
1641      *  - the range must be a basic block (one entry, one exit)
1642      *  - there may not be accesses to local variables with unknown
1643      *    offsets (because we have to adjust these offsets).
1644      *  - no subroutine calls
1645      *  - no jump labels
1646      *
1647      * Since we need a zero page register later, do also check the
1648      * intermediate code for zero page use.
1649      */
1650     I = 0;
1651     while (I < CS_GetEntryCount (S)) {
1652
1653         /* Get the next entry */
1654         CodeEntry* E = CS_GetEntry (S, I);
1655
1656         /* Actions depend on state */
1657         switch (State) {
1658
1659             case Initialize:
1660                 ResetStackOpData (&Data);
1661                 State = Search;
1662                 /* FALLTHROUGH */
1663
1664             case Search:
1665                 /* While searching, track register load insns, so we can tell
1666                  * what is in a register once pushax is encountered.
1667                  */
1668                 if (CE_IsCallTo (E, "pushax")) {
1669                     Data.PushIndex = I;
1670                     State = FoundPush;
1671                 } else {
1672                     /* Track load insns */
1673                     TrackLoads (&Data.Lhs, E, I);
1674                 }
1675                 break;
1676
1677             case FoundPush:
1678                 /* We' found a pushax before. Search for a stack op that may
1679                  * follow and in the meantime, track zeropage usage and check
1680                  * for code that will disable us from translating the sequence.
1681                  */
1682                 if (E->OPC == OP65_JSR) {
1683
1684                     /* Subroutine call: Check if this is one of the functions,
1685                      * we're going to replace.
1686                      */
1687                     Data.OptFunc = FindFunc (E->Arg);
1688                     if (Data.OptFunc) {
1689                         /* Remember the op index and go on */
1690                         Data.OpIndex = I;
1691                         Data.OpEntry = E;
1692                         State = FoundOp;
1693                         break;
1694                     } else if (!HarmlessCall (E->Arg)) {
1695                         /* A call to an unkown subroutine: We need to start
1696                          * over after the last pushax. Note: This will also
1697                          * happen if we encounter a call to pushax!
1698                          */
1699                         I = Data.PushIndex;
1700                         State = Initialize;
1701                         break;
1702                     } else {
1703                         /* Track register usage */
1704                         Data.UsedRegs |= (E->Use | E->Chg);
1705                         TrackLoads (&Data.Rhs, E, I);
1706                     }
1707
1708                 } else if (E->Info & OF_STORE && (E->Chg & REG_ZP) == 0) {
1709
1710                     /* Too dangerous - there may be a change of a variable
1711                      * within the sequence.
1712                      */
1713                     I = Data.PushIndex;
1714                     State = Initialize;
1715                     break;
1716
1717                 } else if ((E->Use & REG_SP) != 0                       &&
1718                            (E->AM != AM65_ZP_INDY               ||
1719                             RegValIsUnknown (E->RI->In.RegY)    ||
1720                             E->RI->In.RegY < 2)) {
1721
1722                     /* If we are using the stack, and we don't have "indirect Y"
1723                      * addressing mode, or the value of Y is unknown, or less
1724                      * than two, we cannot cope with this piece of code. Having
1725                      * an unknown value of Y means that we cannot correct the
1726                      * stack offset, while having an offset less than two means
1727                      * that the code works with the value on stack which is to
1728                      * be removed.
1729                      */
1730                     I = Data.PushIndex;
1731                     State = Initialize;
1732                     break;
1733
1734                 } else {
1735                     /* Other stuff: Track register usage */
1736                     Data.UsedRegs |= (E->Use | E->Chg);
1737                     TrackLoads (&Data.Rhs, E, I);
1738                 }
1739                 break;
1740
1741             case FoundOp:
1742                 /* Track zero page location usage beyond this point */
1743                 Data.UsedRegs |= GetRegInfo (S, I, REG_SREG | REG_PTR1 | REG_PTR2);
1744
1745                 /* Finalize the load info */
1746                 FinalizeLoadInfo (&Data.Lhs, S);
1747                 FinalizeLoadInfo (&Data.Rhs, S);
1748
1749                 /* Set flags for direct operations */
1750                 CheckDirectOp (&Data);
1751
1752                 /* If the Lhs loads do load from zeropage, we have to include
1753                  * them into UsedRegs registers used. The Rhs loads have already
1754                  * been tracked.
1755                  */
1756                 if (Data.Lhs.A.LoadEntry && Data.Lhs.A.LoadEntry->AM == AM65_ZP) {
1757                     Data.UsedRegs |= Data.Lhs.A.LoadEntry->Use;
1758                 }
1759                 if (Data.Lhs.X.LoadEntry && Data.Lhs.X.LoadEntry->AM == AM65_ZP) {
1760                     Data.UsedRegs |= Data.Lhs.X.LoadEntry->Use;
1761                 }
1762
1763                 /* Check the preconditions. If they aren't ok, reset the insn
1764                  * pointer to the pushax and start over. We will loose part of
1765                  * load tracking but at least a/x has probably lost between
1766                  * pushax and here and will be tracked again when restarting.
1767                  */
1768                 if (!PreCondOk (&Data)) {
1769                     I = Data.PushIndex;
1770                     State = Initialize;
1771                     break;
1772                 }
1773
1774                 /* Adjust stack offsets to account for the upcoming removal */
1775                 AdjustStackOffset (&Data, 2);
1776
1777                 /* Regenerate register info, since AdjustStackOffset changed
1778                  * the code
1779                  */
1780                 CS_GenRegInfo (S);
1781
1782                 /* Prepare the remainder of the data structure. */
1783                 Data.PrevEntry = CS_GetPrevEntry (S, Data.PushIndex);
1784                 Data.PushEntry = CS_GetEntry (S, Data.PushIndex);
1785                 Data.OpEntry   = CS_GetEntry (S, Data.OpIndex);
1786                 Data.NextEntry = CS_GetNextEntry (S, Data.OpIndex);
1787
1788                 /* Call the optimizer function */
1789                 Changes += Data.OptFunc->Func (&Data);
1790
1791                 /* Regenerate register info */
1792                 CS_GenRegInfo (S);
1793
1794                 /* Done */
1795                 State = Initialize;
1796                 break;
1797
1798         }
1799
1800         /* Next entry */
1801         ++I;
1802
1803     }
1804
1805     /* Free the register info */
1806     CS_FreeRegInfo (S);
1807
1808     /* Return the number of changes made */
1809     return Changes;
1810 }
1811
1812
1813