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     /* If we have rhs load insns that load from stack, we'll have to adjust
 344      * the offsets for these also.
 345      */
 346     if (D->Rhs.A.Flags & LI_RELOAD_Y) {
 347         D->Rhs.A.Offs -= Offs;
 348     }
 349     if (D->Rhs.X.Flags & LI_RELOAD_Y) {
 350         D->Rhs.X.Offs -= Offs;
 351     }
 352 }
 353
 354
 355
 356 static void InsertEntry (StackOpData* D, CodeEntry* E, int Index)
 357 /* Insert a new entry. Depending on Index, D->PushIndex and D->OpIndex will
 358  * be adjusted by this function.
 359  */
 360 {
 361     /* Insert the entry into the code segment */
 362     CS_InsertEntry (D->Code, E, Index);
 363
 364     /* Adjust register loads if necessary */
 365     AdjustLoadInfo (&D->Lhs, Index, 1);
 366     AdjustLoadInfo (&D->Rhs, Index, 1);
 367
 368     /* Adjust the indices if necessary */
 369     if (D->PushEntry && Index <= D->PushIndex) {
 370         ++D->PushIndex;
 371     }
 372     if (D->OpEntry && Index <= D->OpIndex) {
 373         ++D->OpIndex;
 374     }
 375 }
 376
 377
 378
 379 static void DelEntry (StackOpData* D, int Index)
 380 /* Delete an entry. Depending on Index, D->PushIndex and D->OpIndex will be
 381  * adjusted by this function, and PushEntry/OpEntry may get invalidated.
 382  */
 383 {
 384     /* Delete the entry from the code segment */
 385     CS_DelEntry (D->Code, Index);
 386
 387     /* Adjust register loads if necessary */
 388     AdjustLoadInfo (&D->Lhs, Index, -1);
 389     AdjustLoadInfo (&D->Rhs, Index, -1);
 390
 391     /* Adjust the other indices if necessary */
 392     if (Index < D->PushIndex) {
 393         --D->PushIndex;
 394     } else if (Index == D->PushIndex) {
 395         D->PushEntry = 0;
 396     }
 397     if (Index < D->OpIndex) {
 398         --D->OpIndex;
 399     } else if (Index == D->OpIndex) {
 400         D->OpEntry = 0;
 401     }
 402 }
 403
 404
 405
 406 static void CheckOneDirectOp (LoadRegInfo* LI, unsigned char Offs)
 407 /* Check if the given entry is a lda instruction with an addressing mode
 408  * that allows us to replace it by another operation (like ora). If so, we may
 409  * use this location for the or and must not save the value in the zero
 410  * page location.
 411  */
 412 {
 413     /* Get the load entry */
 414     CodeEntry* E = LI->LoadEntry;
 415     if (E == 0) {
 416         /* No load insn */
 417         return;
 418     }
 419
 420     /* Check the load entry */
 421     if (E) {
 422         /* Must check the call first since addressing mode is ABS, so second
 423          * "if" will catch otherwise.
 424          */
 425         if (CE_IsCallTo (E, "ldaxysp")) {
 426             /* Same as single loads from stack. Since we must distinguish
 427              * between A and X here, the necessary offset is passed to the
 428              * function as a parameter.
 429              */
 430             LI->Offs = (unsigned char) E->RI->In.RegY - Offs;
 431             LI->Flags |= (LI_DIRECT | LI_RELOAD_Y);
 432         } else if (E->AM == AM65_IMM || E->AM == AM65_ZP || E->AM == AM65_ABS) {
 433             /* These insns are all ok and replaceable */
 434             LI->Flags |= LI_DIRECT;
 435         } else if (E->AM == AM65_ZP_INDY &&
 436                    RegValIsKnown (E->RI->In.RegY) &&
 437                    strcmp (E->Arg, "sp") == 0) {
 438             /* A load from the stack with known offset is also ok, but in this
 439              * case we must reload the index register later. Please note that
 440              * a load indirect via other zero page locations is not ok, since
 441              * these locations may change between the push and the actual
 442              * operation.
 443              */
 444             LI->Offs  = (unsigned char) E->RI->In.RegY;
 445             LI->Flags |= (LI_DIRECT | LI_RELOAD_Y);
 446         }
 447     }
 448 }
 449
 450
 451
 452 static void CheckDirectOp (StackOpData* D)
 453 /* Check if the given entry is a lda instruction with an addressing mode
 454  * that allows us to replace it by another operation (like ora). If so, we may
 455  * use this location for the or and must not save the value in the zero
 456  * page location.
 457  */
 458 {
 459     /* Check flags for all load instructions */
 460     CheckOneDirectOp (&D->Lhs.A, 1);
 461     CheckOneDirectOp (&D->Lhs.X, 0);
 462     CheckOneDirectOp (&D->Rhs.A, 1);
 463     CheckOneDirectOp (&D->Rhs.X, 0);
 464 }
 465
 466
 467
 468 static void AddStoreA (StackOpData* D)
 469 /* Add a store to zero page after the push insn */
 470 {
 471     CodeEntry* X = NewCodeEntry (OP65_STA, AM65_ZP, D->ZPLo, 0, D->PushEntry->LI);
 472     InsertEntry (D, X, D->PushIndex+1);
 473 }
 474
 475
 476
 477 static void AddStoreX (StackOpData* D)
 478 /* Add a store to zero page after the push insn */
 479 {
 480     CodeEntry* X = NewCodeEntry (OP65_STX, AM65_ZP, D->ZPHi, 0, D->PushEntry->LI);
 481     InsertEntry (D, X, D->PushIndex+1);
 482 }
 483
 484
 485
 486 static void ReplacePushByStore (StackOpData* D)
 487 /* Replace the call to the push subroutine by a store into the zero page
 488  * location (actually, the push is not replaced, because we need it for
 489  * later, but the name is still ok since the push will get removed at the
 490  * end of each routine).
 491  */
 492 {
 493     /* Store the value into the zeropage instead of pushing it. Check high
 494      * byte first so that the store is later in A/X order.
 495      */
 496     if ((D->Lhs.X.Flags & LI_DIRECT) == 0) {
 497         AddStoreX (D);
 498     }
 499     if ((D->Lhs.A.Flags & LI_DIRECT) == 0) {
 500         AddStoreA (D);
 501     }
 502 }
 503
 504
 505
 506 static void AddOpLow (StackOpData* D, opc_t OPC, LoadInfo* LI)
 507 /* Add an op for the low byte of an operator. This function honours the
 508  * OP_DIRECT and OP_RELOAD_Y flags and generates the necessary instructions.
 509  * All code is inserted at the current insertion point.
 510  */
 511 {
 512     CodeEntry* X;
 513
 514     if ((LI->A.Flags & LI_DIRECT) != 0) {
 515         /* Op with a variable location. If the location is on the stack, we
 516          * need to reload the Y register.
 517          */
 518         if ((LI->A.Flags & LI_RELOAD_Y) == 0) {
 519
 520             /* opc ... */
 521             CodeEntry* LoadA = LI->A.LoadEntry;
 522             X = NewCodeEntry (OPC, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
 523             InsertEntry (D, X, D->IP++);
 524
 525         } else {
 526
 527             /* ldy #offs */
 528             const char* Arg = MakeHexArg (LI->A.Offs);
 529             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 530             InsertEntry (D, X, D->IP++);
 531
 532             /* opc (sp),y */
 533             X = NewCodeEntry (OPC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
 534             InsertEntry (D, X, D->IP++);
 535
 536         }
 537
 538         /* In both cases, we can remove the load */
 539         LI->A.Flags |= LI_REMOVE;
 540
 541     } else {
 542
 543         /* Op with temp storage */
 544         X = NewCodeEntry (OPC, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
 545         InsertEntry (D, X, D->IP++);
 546
 547     }
 548 }
 549
 550
 551
 552 static void AddOpHigh (StackOpData* D, opc_t OPC, LoadInfo* LI, int KeepResult)
 553 /* Add an op for the high byte of an operator. Special cases (constant values
 554  * or similar) have to be checked separately, the function covers only the
 555  * generic case. Code is inserted at the insertion point.
 556  */
 557 {
 558     CodeEntry* X;
 559
 560     if (KeepResult) {
 561         /* pha */
 562         X = NewCodeEntry (OP65_PHA, AM65_IMP, 0, 0, D->OpEntry->LI);
 563         InsertEntry (D, X, D->IP++);
 564     }
 565
 566     /* txa */
 567     X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
 568     InsertEntry (D, X, D->IP++);
 569
 570     if ((LI->X.Flags & LI_DIRECT) != 0) {
 571
 572         if ((LI->X.Flags & LI_RELOAD_Y) == 0) {
 573
 574             /* opc xxx */
 575             CodeEntry* LoadX = LI->X.LoadEntry;
 576             X = NewCodeEntry (OPC, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
 577             InsertEntry (D, X, D->IP++);
 578
 579         } else {
 580
 581             /* ldy #const */
 582             const char* Arg = MakeHexArg (LI->X.Offs);
 583             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 584             InsertEntry (D, X, D->IP++);
 585
 586             /* opc (sp),y */
 587             X = NewCodeEntry (OPC, AM65_ZP_INDY, "sp", 0, D->OpEntry->LI);
 588             InsertEntry (D, X, D->IP++);
 589         }
 590
 591         /* In both cases, we can remove the load */
 592         LI->X.Flags |= LI_REMOVE;
 593
 594     } else {
 595         /* opc zphi */
 596         X = NewCodeEntry (OPC, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 597         InsertEntry (D, X, D->IP++);
 598     }
 599
 600     if (KeepResult) {
 601         /* tax */
 602         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, D->OpEntry->LI);
 603         InsertEntry (D, X, D->IP++);
 604
 605         /* pla */
 606         X = NewCodeEntry (OP65_PLA, AM65_IMP, 0, 0, D->OpEntry->LI);
 607         InsertEntry (D, X, D->IP++);
 608     }
 609 }
 610
 611
 612
 613 static void RemoveRegLoads (StackOpData* D, LoadInfo* LI)
 614 /* Remove register load insns */
 615 {
 616     /* Both registers may be loaded with one insn, but DelEntry will in this
 617      * case clear the other one.
 618      */
 619     if (LI->A.LoadIndex >= 0 && (LI->A.Flags & LI_REMOVE)) {
 620         DelEntry (D, LI->A.LoadIndex);
 621     }
 622     if (LI->X.LoadIndex >= 0 && (LI->X.Flags & LI_REMOVE)) {
 623         DelEntry (D, LI->X.LoadIndex);
 624     }
 625 }
 626
 627
 628
 629 static void RemoveRemainders (StackOpData* D)
 630 /* Remove the code that is unnecessary after translation of the sequence */
 631 {
 632     /* Remove the register loads for lhs and rhs */
 633     RemoveRegLoads (D, &D->Lhs);
 634     RemoveRegLoads (D, &D->Rhs);
 635
 636     /* Remove the push and the operator routine */
 637     DelEntry (D, D->OpIndex);
 638     DelEntry (D, D->PushIndex);
 639 }
 640
 641
 642
 643 static int IsRegVar (StackOpData* D)
 644 /* If the value pushed is that of a zeropage variable, replace ZPLo and ZPHi
 645  * in the given StackOpData struct by the variable and return true. Otherwise
 646  * leave D untouched and return false.
 647  */
 648 {
 649     CodeEntry*  LoadA = D->Lhs.A.LoadEntry;
 650     CodeEntry*  LoadX = D->Lhs.X.LoadEntry;
 651     unsigned    Len;
 652
 653     /* Must have both load insns */
 654     if (LoadA == 0 || LoadX == 0) {
 655         return 0;
 656     }
 657
 658     /* Must be loads from zp */
 659     if (LoadA->AM != AM65_ZP || LoadX->AM != AM65_ZP) {
 660         return 0;
 661     }
 662
 663     /* Must be the same zp loc with high byte in X */
 664     Len = strlen (LoadA->Arg);
 665     if (strncmp (LoadA->Arg, LoadX->Arg, Len) != 0      ||
 666         strcmp (LoadX->Arg + Len, "+1") != 0) {
 667         return 0;
 668     }
 669
 670     /* Use the zero page location directly */
 671     D->ZPLo = LoadA->Arg;
 672     D->ZPHi = LoadX->Arg;
 673     return 1;
 674 }
 675
 676
 677
 678 /*****************************************************************************/
 679 /*                       Actual optimization functions                       */
 680 /*****************************************************************************/
 681
 682
 683
 684 static unsigned Opt_toseqax_tosneax (StackOpData* D, const char* BoolTransformer)
 685 /* Optimize the toseqax and tosneax sequences. */
 686 {
 687     CodeEntry*  X;
 688     CodeLabel* L;
 689
 690     /* Create a call to the boolean transformer function and a label for this
 691      * insn. This is needed for all variants. Other insns are inserted *before*
 692      * the call.
 693      */
 694     X = NewCodeEntry (OP65_JSR, AM65_ABS, BoolTransformer, 0, D->OpEntry->LI);
 695     InsertEntry (D, X, D->OpIndex + 1);
 696     L = CS_GenLabel (D->Code, X);
 697
 698     /* If the lhs is direct (but not stack relative), encode compares with lhs
 699      * effectively reverting the order (which doesn't matter for ==).
 700      */
 701     if ((D->Lhs.A.Flags & (LI_DIRECT | LI_RELOAD_Y)) == LI_DIRECT &&
 702         (D->Lhs.X.Flags & (LI_DIRECT | LI_RELOAD_Y)) == LI_DIRECT) {
 703
 704         CodeEntry* LoadX = D->Lhs.X.LoadEntry;
 705         CodeEntry* LoadA = D->Lhs.A.LoadEntry;
 706
 707         D->IP = D->OpIndex+1;
 708
 709         /* cpx */
 710         X = NewCodeEntry (OP65_CPX, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
 711         InsertEntry (D, X, D->IP++);
 712
 713         /* bne L */
 714         X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 715         InsertEntry (D, X, D->IP++);
 716
 717         /* cmp */
 718         X = NewCodeEntry (OP65_CMP, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
 719         InsertEntry (D, X, D->IP++);
 720
 721         /* Lhs load entries can be removed */
 722         D->Lhs.X.Flags |= LI_REMOVE;
 723         D->Lhs.A.Flags |= LI_REMOVE;
 724
 725     } else if ((D->Rhs.A.Flags & (LI_DIRECT | LI_RELOAD_Y)) == LI_DIRECT &&
 726                (D->Rhs.X.Flags & (LI_DIRECT | LI_RELOAD_Y)) == LI_DIRECT) {
 727
 728         CodeEntry* LoadX = D->Rhs.X.LoadEntry;
 729         CodeEntry* LoadA = D->Rhs.A.LoadEntry;
 730
 731         D->IP = D->OpIndex+1;
 732
 733         /* cpx */
 734         X = NewCodeEntry (OP65_CPX, LoadX->AM, LoadX->Arg, 0, D->OpEntry->LI);
 735         InsertEntry (D, X, D->IP++);
 736
 737         /* bne L */
 738         X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 739         InsertEntry (D, X, D->IP++);
 740
 741         /* cmp */
 742         X = NewCodeEntry (OP65_CMP, LoadA->AM, LoadA->Arg, 0, D->OpEntry->LI);
 743         InsertEntry (D, X, D->IP++);
 744
 745         /* Rhs load entries can be removed */
 746         D->Rhs.X.Flags |= LI_REMOVE;
 747         D->Rhs.A.Flags |= LI_REMOVE;
 748
 749     } else if ((D->Rhs.A.Flags & LI_DIRECT) != 0 &&
 750                (D->Rhs.X.Flags & LI_DIRECT) != 0) {
 751
 752         D->IP = D->OpIndex+1;
 753
 754         /* Add operand for low byte */
 755         AddOpLow (D, OP65_CMP, &D->Rhs);
 756
 757         /* bne L */
 758         X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 759         InsertEntry (D, X, D->IP++);
 760
 761         /* Add operand for high byte */
 762         AddOpHigh (D, OP65_CMP, &D->Rhs, 0);
 763
 764     } else {
 765
 766         /* Save lhs into zeropage, then compare */
 767         AddStoreX (D);
 768         AddStoreA (D);
 769
 770         D->IP = D->OpIndex+1;
 771
 772         /* cpx */
 773         X = NewCodeEntry (OP65_CPX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 774         InsertEntry (D, X, D->IP++);
 775
 776         /* bne L */
 777         X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 778         InsertEntry (D, X, D->IP++);
 779
 780         /* cmp */
 781         X = NewCodeEntry (OP65_CMP, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
 782         InsertEntry (D, X, D->IP++);
 783
 784     }
 785
 786     /* Remove the push and the call to the tosgeax function */
 787     RemoveRemainders (D);
 788
 789     /* We changed the sequence */
 790     return 1;
 791 }
 792
 793
 794
 795 static unsigned Opt___bzero (StackOpData* D)
 796 /* Optimize the __bzero sequence */
 797 {
 798     CodeEntry*  X;
 799     const char* Arg;
 800     CodeLabel*  L;
 801
 802     /* Check if we're using a register variable */
 803     if (!IsRegVar (D)) {
 804         /* Store the value into the zeropage instead of pushing it */
 805         AddStoreX (D);
 806         AddStoreA (D);
 807     }
 808
 809     /* If the return value of __bzero is used, we have to add code to reload
 810      * a/x from the pointer variable.
 811      */
 812     if (RegAXUsed (D->Code, D->OpIndex+1)) {
 813         X = NewCodeEntry (OP65_LDA, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
 814         InsertEntry (D, X, D->OpIndex+1);
 815         X = NewCodeEntry (OP65_LDX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
 816         InsertEntry (D, X, D->OpIndex+2);
 817     }
 818
 819     /* X is always zero, A contains the size of the data area to zero.
 820      * Note: A may be zero, in which case the operation is null op.
 821      */
 822     if (D->OpEntry->RI->In.RegA != 0) {
 823
 824         /* lda #$00 */
 825         X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
 826         InsertEntry (D, X, D->OpIndex+1);
 827
 828         /* The value of A is known */
 829         if (D->OpEntry->RI->In.RegA <= 0x81) {
 830
 831             /* Loop using the sign bit */
 832
 833             /* ldy #count-1 */
 834             Arg = MakeHexArg (D->OpEntry->RI->In.RegA - 1);
 835             X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 836             InsertEntry (D, X, D->OpIndex+2);
 837
 838             /* L: sta (zp),y */
 839             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 840             InsertEntry (D, X, D->OpIndex+3);
 841             L = CS_GenLabel (D->Code, X);
 842
 843             /* dey */
 844             X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, D->OpEntry->LI);
 845             InsertEntry (D, X, D->OpIndex+4);
 846
 847             /* bpl L */
 848             X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, D->OpEntry->LI);
 849             InsertEntry (D, X, D->OpIndex+5);
 850
 851         } else {
 852
 853             /* Loop using an explicit compare */
 854
 855             /* ldy #$00 */
 856             X = NewCodeEntry (OP65_LDY, AM65_IMM, "$00", 0, D->OpEntry->LI);
 857             InsertEntry (D, X, D->OpIndex+2);
 858
 859             /* L: sta (zp),y */
 860             X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 861             InsertEntry (D, X, D->OpIndex+3);
 862             L = CS_GenLabel (D->Code, X);
 863
 864             /* iny */
 865             X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, D->OpEntry->LI);
 866             InsertEntry (D, X, D->OpIndex+4);
 867
 868             /* cpy #count */
 869             Arg = MakeHexArg (D->OpEntry->RI->In.RegA);
 870             X = NewCodeEntry (OP65_CPY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 871             InsertEntry (D, X, D->OpIndex+5);
 872
 873             /* bne L */
 874             X = NewCodeEntry (OP65_BNE, AM65_BRA, L->Name, L, D->OpEntry->LI);
 875             InsertEntry (D, X, D->OpIndex+6);
 876         }
 877
 878     }
 879
 880     /* Remove the push and the call to the __bzero function */
 881     RemoveRemainders (D);
 882
 883     /* We changed the sequence */
 884     return 1;
 885 }
 886
 887
 888
 889 static unsigned Opt_staspidx (StackOpData* D)
 890 /* Optimize the staspidx sequence */
 891 {
 892     CodeEntry* X;
 893
 894     /* Check if we're using a register variable */
 895     if (!IsRegVar (D)) {
 896         /* Store the value into the zeropage instead of pushing it */
 897         AddStoreX (D);
 898         AddStoreA (D);
 899     }
 900
 901     /* Replace the store subroutine call by a direct op */
 902     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 903     InsertEntry (D, X, D->OpIndex+1);
 904
 905     /* Remove the push and the call to the staspidx function */
 906     RemoveRemainders (D);
 907
 908     /* We changed the sequence */
 909     return 1;
 910 }
 911
 912
 913
 914 static unsigned Opt_staxspidx (StackOpData* D)
 915 /* Optimize the staxspidx sequence */
 916 {
 917     CodeEntry* X;
 918
 919     /* Check if we're using a register variable */
 920     if (!IsRegVar (D)) {
 921         /* Store the value into the zeropage instead of pushing it */
 922         AddStoreX (D);
 923         AddStoreA (D);
 924     }
 925
 926     /* Inline the store */
 927
 928     /* sta (zp),y */
 929     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 930     InsertEntry (D, X, D->OpIndex+1);
 931
 932     if (RegValIsKnown (D->OpEntry->RI->In.RegY)) {
 933         /* Value of Y is known */
 934         const char* Arg = MakeHexArg (D->OpEntry->RI->In.RegY + 1);
 935         X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
 936     } else {
 937         X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, D->OpEntry->LI);
 938     }
 939     InsertEntry (D, X, D->OpIndex+2);
 940
 941     if (RegValIsKnown (D->OpEntry->RI->In.RegX)) {
 942         /* Value of X is known */
 943         const char* Arg = MakeHexArg (D->OpEntry->RI->In.RegX);
 944         X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, D->OpEntry->LI);
 945     } else {
 946         /* Value unknown */
 947         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
 948     }
 949     InsertEntry (D, X, D->OpIndex+3);
 950
 951     /* sta (zp),y */
 952     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
 953     InsertEntry (D, X, D->OpIndex+4);
 954
 955     /* If we remove staxspidx, we must restore the Y register to what the
 956      * function would return.
 957      */
 958     X = NewCodeEntry (OP65_LDY, AM65_IMM, "$00", 0, D->OpEntry->LI);
 959     InsertEntry (D, X, D->OpIndex+5);
 960
 961     /* Remove the push and the call to the staxspidx function */
 962     RemoveRemainders (D);
 963
 964     /* We changed the sequence */
 965     return 1;
 966 }
 967
 968
 969
 970 static unsigned Opt_tosaddax (StackOpData* D)
 971 /* Optimize the tosaddax sequence */
 972 {
 973     CodeEntry*  X;
 974     CodeEntry*  N;
 975
 976     /* We need the entry behind the add */
 977     CHECK (D->NextEntry != 0);
 978
 979     /* Check if the X register is known and zero when the add is done, and
 980      * if the add is followed by
 981      *
 982      *  ldy     #$00
 983      *  jsr     ldauidx         ; or ldaidx
 984      *
 985      * If this is true, the addition does actually add an offset to a pointer
 986      * before it is dereferenced. Since both subroutines take an offset in Y,
 987      * we can pass the offset (instead of #$00) and remove the addition
 988      * alltogether.
 989      */
 990     if (D->OpEntry->RI->In.RegX == 0                            &&
 991         D->NextEntry->OPC == OP65_LDY                           &&
 992         CE_IsKnownImm (D->NextEntry, 0)                         &&
 993         !CE_HasLabel (D->NextEntry)                             &&
 994         (N = CS_GetNextEntry (D->Code, D->OpIndex + 1)) != 0    &&
 995         (CE_IsCallTo (N, "ldauidx")                     ||
 996          CE_IsCallTo (N, "ldaidx"))) {
 997
 998         int Signed = (strcmp (N->Arg, "ldaidx") == 0);
 999
1000         /* Store the value into the zeropage instead of pushing it */
1001         AddStoreX (D);
1002         AddStoreA (D);
1003
1004         /* Replace the ldy by a tay. Be sure to create the new entry before
1005          * deleting the ldy, since we will reference the line info from this
1006          * insn.
1007          */
1008         X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, D->NextEntry->LI);
1009         DelEntry (D, D->OpIndex + 1);
1010         InsertEntry (D, X, D->OpIndex + 1);
1011
1012         /* Replace the call to ldaidx/ldauidx. Since X is already zero, and
1013          * the ptr is in the zero page location, we just need to load from
1014          * the pointer, and fix X in case of ldaidx.
1015          */
1016         X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, D->ZPLo, 0, N->LI);
1017         DelEntry (D, D->OpIndex + 2);
1018         InsertEntry (D, X, D->OpIndex + 2);
1019         if (Signed) {
1020
1021             CodeLabel* L;
1022
1023             /* Add sign extension - N is unused now */
1024             N = CS_GetNextEntry (D->Code, D->OpIndex + 2);
1025             CHECK (N != 0);
1026             L = CS_GenLabel (D->Code, N);
1027
1028             X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, X->LI);
1029             InsertEntry (D, X, D->OpIndex + 3);
1030
1031             X = NewCodeEntry (OP65_DEX, AM65_IMP, 0, 0, X->LI);
1032             InsertEntry (D, X, D->OpIndex + 4);
1033         }
1034
1035     } else {
1036
1037         /* Store the value into the zeropage instead of pushing it */
1038         ReplacePushByStore (D);
1039
1040         /* Inline the add */
1041         D->IP = D->OpIndex+1;
1042
1043         /* clc */
1044         X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, D->OpEntry->LI);
1045         InsertEntry (D, X, D->IP++);
1046
1047         /* Low byte */
1048         AddOpLow (D, OP65_ADC, &D->Lhs);
1049
1050         /* High byte */
1051         if (D->PushEntry->RI->In.RegX == 0) {
1052             /* The high byte is the value in X plus the carry */
1053             CodeLabel* L = CS_GenLabel (D->Code, D->NextEntry);
1054
1055             /* bcc L */
1056             X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
1057             InsertEntry (D, X, D->IP++);
1058
1059             /* inx */
1060             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
1061             InsertEntry (D, X, D->IP++);
1062
1063         } else if (D->OpEntry->RI->In.RegX == 0) {
1064
1065             /* The high byte is that of the first operand plus carry */
1066             CodeLabel* L;
1067             if (RegValIsKnown (D->PushEntry->RI->In.RegX)) {
1068                 /* Value of first op high byte is known */
1069                 const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX);
1070                 X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
1071             } else {
1072                 /* Value of first op high byte is unknown */
1073                 X = NewCodeEntry (OP65_LDX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
1074             }
1075             InsertEntry (D, X, D->IP++);
1076
1077             /* bcc label */
1078             L = CS_GenLabel (D->Code, D->NextEntry);
1079             X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
1080             InsertEntry (D, X, D->IP++);
1081
1082             /* inx */
1083             X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
1084             InsertEntry (D, X, D->IP++);
1085         } else {
1086             /* High byte is unknown */
1087             AddOpHigh (D, OP65_ADC, &D->Lhs, 1);
1088         }
1089     }
1090
1091     /* Remove the push and the call to the tosaddax function */
1092     RemoveRemainders (D);
1093
1094     /* We changed the sequence */
1095     return 1;
1096 }
1097
1098
1099
1100 static unsigned Opt_tosandax (StackOpData* D)
1101 /* Optimize the tosandax sequence */
1102 {
1103     CodeEntry*  X;
1104
1105     /* Store the value into the zeropage instead of pushing it */
1106     ReplacePushByStore (D);
1107
1108     /* Inline the and, low byte */
1109     D->IP = D->OpIndex + 1;
1110     AddOpLow (D, OP65_AND, &D->Lhs);
1111
1112     /* High byte */
1113     if (D->PushEntry->RI->In.RegX == 0 || D->OpEntry->RI->In.RegX == 0) {
1114         /* The high byte is zero */
1115         X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1116         InsertEntry (D, X, D->IP++);
1117     } else {
1118         /* High byte is unknown */
1119         AddOpHigh (D, OP65_AND, &D->Lhs, 1);
1120     }
1121
1122     /* Remove the push and the call to the tosandax function */
1123     RemoveRemainders (D);
1124
1125     /* We changed the sequence */
1126     return 1;
1127 }
1128
1129
1130
1131 static unsigned Opt_toseqax (StackOpData* D)
1132 /* Optimize the toseqax sequence */
1133 {
1134     return Opt_toseqax_tosneax (D, "booleq");
1135 }
1136
1137
1138
1139 static unsigned Opt_tosgeax (StackOpData* D)
1140 /* Optimize the tosgeax sequence */
1141 {
1142     CodeEntry*  X;
1143     CodeLabel* L;
1144
1145     /* Inline the sbc */
1146     D->IP = D->OpIndex+1;
1147
1148     /* Must be true because of OP_RHS_LOAD */
1149     CHECK ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) != 0);
1150
1151     /* Add code for low operand */
1152     AddOpLow (D, OP65_CMP, &D->Rhs);
1153
1154     /* Add code for high operand */
1155     AddOpHigh (D, OP65_SBC, &D->Rhs, 0);
1156
1157     /* eor #$80 */
1158     X = NewCodeEntry (OP65_EOR, AM65_IMM, "$80", 0, D->OpEntry->LI);
1159     InsertEntry (D, X, D->IP++);
1160
1161     /* asl a */
1162     X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, D->OpEntry->LI);
1163     InsertEntry (D, X, D->IP++);
1164     L = CS_GenLabel (D->Code, X);
1165
1166     /* Insert a bvs L before the eor insn */
1167     X = NewCodeEntry (OP65_BVS, AM65_BRA, L->Name, L, D->OpEntry->LI);
1168     InsertEntry (D, X, D->IP - 2);
1169     ++D->IP;
1170
1171     /* lda #$00 */
1172     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1173     InsertEntry (D, X, D->IP++);
1174
1175     /* ldx #$00 */
1176     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1177     InsertEntry (D, X, D->IP++);
1178
1179     /* rol a */
1180     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1181     InsertEntry (D, X, D->IP++);
1182
1183     /* Remove the push and the call to the tosgeax function */
1184     RemoveRemainders (D);
1185
1186     /* We changed the sequence */
1187     return 1;
1188 }
1189
1190
1191
1192 static unsigned Opt_tosltax (StackOpData* D)
1193 /* Optimize the tosltax sequence */
1194 {
1195     CodeEntry*  X;
1196     CodeLabel* L;
1197
1198
1199     /* Inline the sbc */
1200     D->IP = D->OpIndex+1;
1201
1202     /* Must be true because of OP_RHS_LOAD */
1203     CHECK ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) != 0);
1204
1205     /* Add code for low operand */
1206     AddOpLow (D, OP65_CMP, &D->Rhs);
1207
1208     /* Add code for high operand */
1209     AddOpHigh (D, OP65_SBC, &D->Rhs, 0);
1210
1211     /* eor #$80 */
1212     X = NewCodeEntry (OP65_EOR, AM65_IMM, "$80", 0, D->OpEntry->LI);
1213     InsertEntry (D, X, D->IP++);
1214
1215     /* asl a */
1216     X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, D->OpEntry->LI);
1217     InsertEntry (D, X, D->IP++);
1218     L = CS_GenLabel (D->Code, X);
1219
1220     /* Insert a bvc L before the eor insn */
1221     X = NewCodeEntry (OP65_BVC, AM65_BRA, L->Name, L, D->OpEntry->LI);
1222     InsertEntry (D, X, D->IP - 2);
1223     ++D->IP;
1224
1225     /* lda #$00 */
1226     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1227     InsertEntry (D, X, D->IP++);
1228
1229     /* ldx #$00 */
1230     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1231     InsertEntry (D, X, D->IP++);
1232
1233     /* rol a */
1234     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1235     InsertEntry (D, X, D->IP++);
1236
1237     /* Remove the push and the call to the tosltax function */
1238     RemoveRemainders (D);
1239
1240     /* We changed the sequence */
1241     return 1;
1242 }
1243
1244
1245
1246 static unsigned Opt_tosneax (StackOpData* D)
1247 /* Optimize the tosneax sequence */
1248 {
1249     return Opt_toseqax_tosneax (D, "boolne");
1250 }
1251
1252
1253
1254 static unsigned Opt_tosorax (StackOpData* D)
1255 /* Optimize the tosorax sequence */
1256 {
1257     CodeEntry*  X;
1258
1259     /* Store the value into the zeropage instead of pushing it */
1260     ReplacePushByStore (D);
1261
1262     /* Inline the or, low byte */
1263     D->IP = D->OpIndex + 1;
1264     AddOpLow (D, OP65_ORA, &D->Lhs);
1265
1266     /* High byte */
1267     if (RegValIsKnown (D->PushEntry->RI->In.RegX) &&
1268         RegValIsKnown (D->OpEntry->RI->In.RegX)) {
1269         /* Both values known, precalculate the result */
1270         unsigned char Result = D->PushEntry->RI->In.RegX | D->OpEntry->RI->In.RegX;
1271         const char* Arg = MakeHexArg (Result);
1272         X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
1273         InsertEntry (D, X, D->IP++);
1274     } else if (D->PushEntry->RI->In.RegX != 0) {
1275         /* High byte is unknown */
1276         AddOpHigh (D, OP65_ORA, &D->Lhs, 1);
1277     }
1278
1279     /* Remove the push and the call to the tosorax function */
1280     RemoveRemainders (D);
1281
1282     /* We changed the sequence */
1283     return 1;
1284 }
1285
1286
1287
1288 static unsigned Opt_tossubax (StackOpData* D)
1289 /* Optimize the tossubax sequence. Note: subtraction is not commutative! */
1290 {
1291     CodeEntry*  X;
1292
1293
1294     /* Inline the sbc */
1295     D->IP = D->OpIndex+1;
1296
1297     /* sec */
1298     X = NewCodeEntry (OP65_SEC, AM65_IMP, 0, 0, D->OpEntry->LI);
1299     InsertEntry (D, X, D->IP++);
1300
1301     /* Must be true because of OP_RHS_LOAD */
1302     CHECK ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) != 0);
1303
1304     /* Add code for low operand */
1305     AddOpLow (D, OP65_SBC, &D->Rhs);
1306
1307     /* Add code for high operand */
1308     AddOpHigh (D, OP65_SBC, &D->Rhs, 1);
1309
1310     /* Remove the push and the call to the tossubax function */
1311     RemoveRemainders (D);
1312
1313     /* We changed the sequence */
1314     return 1;
1315 }
1316
1317
1318
1319 static unsigned Opt_tosugeax (StackOpData* D)
1320 /* Optimize the tosugeax sequence */
1321 {
1322     CodeEntry*  X;
1323
1324
1325     /* Inline the sbc */
1326     D->IP = D->OpIndex+1;
1327
1328     /* Must be true because of OP_RHS_LOAD */
1329     CHECK ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) != 0);
1330
1331     /* Add code for low operand */
1332     AddOpLow (D, OP65_CMP, &D->Rhs);
1333
1334     /* Add code for high operand */
1335     AddOpHigh (D, OP65_SBC, &D->Rhs, 0);
1336
1337     /* lda #$00 */
1338     X = NewCodeEntry (OP65_LDA, AM65_IMM, "$00", 0, D->OpEntry->LI);
1339     InsertEntry (D, X, D->IP++);
1340
1341     /* ldx #$00 */
1342     X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
1343     InsertEntry (D, X, D->IP++);
1344
1345     /* rol a */
1346     X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, D->OpEntry->LI);
1347     InsertEntry (D, X, D->IP++);
1348
1349     /* Remove the push and the call to the tosugeax function */
1350     RemoveRemainders (D);
1351
1352     /* We changed the sequence */
1353     return 1;
1354 }
1355
1356
1357
1358 static unsigned Opt_tosxorax (StackOpData* D)
1359 /* Optimize the tosxorax sequence */
1360 {
1361     CodeEntry*  X;
1362
1363
1364     /* Store the value into the zeropage instead of pushing it */
1365     ReplacePushByStore (D);
1366
1367     /* Inline the xor, low byte */
1368     D->IP = D->OpIndex + 1;
1369     AddOpLow (D, OP65_EOR, &D->Lhs);
1370
1371     /* High byte */
1372     if (RegValIsKnown (D->PushEntry->RI->In.RegX) &&
1373         RegValIsKnown (D->OpEntry->RI->In.RegX)) {
1374         /* Both values known, precalculate the result */
1375         const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX ^ D->OpEntry->RI->In.RegX);
1376         X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
1377         InsertEntry (D, X, D->IP++);
1378     } else if (D->PushEntry->RI->In.RegX != 0) {
1379         /* High byte is unknown */
1380         AddOpHigh (D, OP65_EOR, &D->Lhs, 1);
1381     }
1382
1383     /* Remove the push and the call to the tosandax function */
1384     RemoveRemainders (D);
1385
1386     /* We changed the sequence */
1387     return 1;
1388 }
1389
1390
1391
1392 /*****************************************************************************/
1393 /*                                   Code                                    */
1394 /*****************************************************************************/
1395
1396
1397
1398 static const OptFuncDesc FuncTable[] = {
1399     { "__bzero",    Opt___bzero,   REG_NONE, OP_X_ZERO | OP_A_KNOWN     },
1400     { "staspidx",   Opt_staspidx,  REG_NONE, OP_NONE                    },
1401     { "staxspidx",  Opt_staxspidx, REG_AX,   OP_NONE                    },
1402     { "tosaddax",   Opt_tosaddax,  REG_NONE, OP_NONE                    },
1403     { "tosandax",   Opt_tosandax,  REG_NONE, OP_NONE                    },
1404     { "toseqax",    Opt_toseqax,   REG_NONE, OP_NONE                    },
1405     { "tosgeax",    Opt_tosgeax,   REG_NONE, OP_RHS_LOAD_DIRECT         },
1406     { "tosltax",    Opt_tosltax,   REG_NONE, OP_RHS_LOAD_DIRECT         },
1407     { "tosneax",    Opt_tosneax,   REG_NONE, OP_NONE                    },
1408     { "tosorax",    Opt_tosorax,   REG_NONE, OP_NONE                    },
1409     { "tossubax",   Opt_tossubax,  REG_NONE, OP_RHS_LOAD_DIRECT         },
1410     { "tosugeax",   Opt_tosugeax,  REG_NONE, OP_RHS_LOAD_DIRECT         },
1411     { "tosxorax",   Opt_tosxorax,  REG_NONE, OP_NONE                    },
1412 };
1413 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
1414
1415
1416
1417 static int CmpFunc (const void* Key, const void* Func)
1418 /* Compare function for bsearch */
1419 {
1420     return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
1421 }
1422
1423
1424
1425 static const OptFuncDesc* FindFunc (const char* Name)
1426 /* Find the function with the given name. Return a pointer to the table entry
1427  * or NULL if the function was not found.
1428  */
1429 {
1430     return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
1431 }
1432
1433
1434
1435 static int CmpHarmless (const void* Key, const void* Entry)
1436 /* Compare function for bsearch */
1437 {
1438     return strcmp (Key, *(const char**)Entry);
1439 }
1440
1441
1442
1443 static int HarmlessCall (const char* Name)
1444 /* Check if this is a call to a harmless subroutine that will not interrupt
1445  * the pushax/op sequence when encountered.
1446  */
1447 {
1448     static const char* Tab[] = {
1449         "aslax1",
1450         "aslax2",
1451         "aslax3",
1452         "aslax4",
1453         "asrax1",
1454         "asrax2",
1455         "asrax3",
1456         "asrax4",
1457         "bnegax",
1458         "ldaxidx",
1459         "ldaxysp",
1460         "negax",
1461         "shlax1",
1462         "shlax2",
1463         "shlax3",
1464         "shlax4",
1465         "shrax1",
1466         "shrax2",
1467         "shrax3",
1468         "shrax4",
1469     };
1470
1471     void* R = bsearch (Name,
1472                        Tab,
1473                        sizeof (Tab) / sizeof (Tab[0]),
1474                        sizeof (Tab[0]),
1475                        CmpHarmless);
1476     return (R != 0);
1477 }
1478
1479
1480
1481 static void ResetStackOpData (StackOpData* Data)
1482 /* Reset the given data structure */
1483 {
1484     Data->OptFunc       = 0;
1485     Data->UsedRegs      = REG_NONE;
1486
1487     ClearLoadInfo (&Data->Lhs);
1488     ClearLoadInfo (&Data->Rhs);
1489
1490     Data->PushIndex     = -1;
1491     Data->OpIndex       = -1;
1492 }
1493
1494
1495
1496 static int PreCondOk (StackOpData* D)
1497 /* Check if the preconditions for a call to the optimizer subfunction are
1498  * satisfied. As a side effect, this function will also choose the zero page
1499  * register to use.
1500  */
1501 {
1502     /* Check the flags */
1503     unsigned UnusedRegs = D->OptFunc->UnusedRegs;
1504     if (UnusedRegs != REG_NONE &&
1505         (GetRegInfo (D->Code, D->OpIndex+1, UnusedRegs) & UnusedRegs) != 0) {
1506         /* Cannot optimize */
1507         return 0;
1508     }
1509     if ((D->OptFunc->Flags & OP_A_KNOWN) != 0 &&
1510         RegValIsUnknown (D->OpEntry->RI->In.RegA)) {
1511         /* Cannot optimize */
1512         return 0;
1513     }
1514     if ((D->OptFunc->Flags & OP_X_ZERO) != 0 &&
1515         D->OpEntry->RI->In.RegX != 0) {
1516         /* Cannot optimize */
1517         return 0;
1518     }
1519     if ((D->OptFunc->Flags & OP_LHS_LOAD) != 0) {
1520         if (D->Lhs.A.LoadIndex < 0 || D->Lhs.X.LoadIndex < 0) {
1521             /* Cannot optimize */
1522             return 0;
1523         } else if ((D->OptFunc->Flags & OP_LHS_LOAD_DIRECT) != 0) {
1524             if ((D->Lhs.A.Flags & D->Lhs.X.Flags & LI_DIRECT) == 0) {
1525                 /* Cannot optimize */
1526                 return 0;
1527             }
1528         }
1529     }
1530     if ((D->OptFunc->Flags & OP_RHS_LOAD) != 0) {
1531         if (D->Rhs.A.LoadIndex < 0 || D->Rhs.X.LoadIndex < 0) {
1532             /* Cannot optimize */
1533             return 0;
1534         } else if ((D->OptFunc->Flags & OP_RHS_LOAD_DIRECT) != 0) {
1535             if ((D->Rhs.A.Flags & D->Rhs.X.Flags & LI_DIRECT) == 0) {
1536                 /* Cannot optimize */
1537                 return 0;
1538             }
1539         }
1540     }
1541
1542     /* Determine the zero page locations to use */
1543     if ((D->UsedRegs & REG_PTR1) == REG_NONE) {
1544         D->ZPLo = "ptr1";
1545         D->ZPHi = "ptr1+1";
1546     } else if ((D->UsedRegs & REG_SREG) == REG_NONE) {
1547         D->ZPLo = "sreg";
1548         D->ZPHi = "sreg+1";
1549     } else if ((D->UsedRegs & REG_PTR2) == REG_NONE) {
1550         D->ZPLo = "ptr2";
1551         D->ZPHi = "ptr2+1";
1552     } else {
1553         /* No registers available */
1554         return 0;
1555     }
1556
1557     /* Determine if we have a basic block */
1558     return CS_IsBasicBlock (D->Code, D->PushIndex, D->OpIndex);
1559 }
1560
1561
1562
1563 /*****************************************************************************/
1564 /*                                   Code                                    */
1565 /*****************************************************************************/
1566
1567
1568
1569 unsigned OptStackOps (CodeSeg* S)
1570 /* Optimize operations that take operands via the stack */
1571 {
1572     unsigned            Changes = 0;    /* Number of changes in one run */
1573     StackOpData         Data;
1574     unsigned            I;
1575
1576     enum {
1577         Initialize,
1578         Search,
1579         FoundPush,
1580         FoundOp
1581     } State = Initialize;
1582
1583
1584     /* Generate register info */
1585     CS_GenRegInfo (S);
1586
1587     /* Remember the code segment in the info struct */
1588     Data.Code = S;
1589
1590     /* Look for a call to pushax followed by a call to some other function
1591      * that takes it's first argument on the stack, and the second argument
1592      * in the primary register.
1593      * It depends on the code between the two if we can handle/transform the
1594      * sequence, so check this code for the following list of things:
1595      *
1596      *  - the range must be a basic block (one entry, one exit)
1597      *  - there may not be accesses to local variables with unknown
1598      *    offsets (because we have to adjust these offsets).
1599      *  - no subroutine calls
1600      *  - no jump labels
1601      *
1602      * Since we need a zero page register later, do also check the
1603      * intermediate code for zero page use.
1604      */
1605     I = 0;
1606     while (I < CS_GetEntryCount (S)) {
1607
1608         /* Get the next entry */
1609         CodeEntry* E = CS_GetEntry (S, I);
1610
1611         /* Actions depend on state */
1612         switch (State) {
1613
1614             case Initialize:
1615                 ResetStackOpData (&Data);
1616                 State = Search;
1617                 /* FALLTHROUGH */
1618
1619             case Search:
1620                 /* While searching, track register load insns, so we can tell
1621                  * what is in a register once pushax is encountered.
1622                  */
1623                 if (CE_IsCallTo (E, "pushax")) {
1624                     Data.PushIndex = I;
1625                     State = FoundPush;
1626                 } else {
1627                     /* Track load insns */
1628                     TrackLoads (&Data.Lhs, E, I);
1629                 }
1630                 break;
1631
1632             case FoundPush:
1633                 /* We' found a pushax before. Search for a stack op that may
1634                  * follow and in the meantime, track zeropage usage and check
1635                  * for code that will disable us from translating the sequence.
1636                  */
1637                 if (E->OPC == OP65_JSR) {
1638
1639                     /* Subroutine call: Check if this is one of the functions,
1640                      * we're going to replace.
1641                      */
1642                     Data.OptFunc = FindFunc (E->Arg);
1643                     if (Data.OptFunc) {
1644                         /* Remember the op index and go on */
1645                         Data.OpIndex = I;
1646                         Data.OpEntry = E;
1647                         State = FoundOp;
1648                         break;
1649                     } else if (!HarmlessCall (E->Arg)) {
1650                         /* A call to an unkown subroutine: We need to start
1651                          * over after the last pushax. Note: This will also
1652                          * happen if we encounter a call to pushax!
1653                          */
1654                         I = Data.PushIndex;
1655                         State = Initialize;
1656                         break;
1657                     } else {
1658                         /* Track register usage */
1659                         Data.UsedRegs |= (E->Use | E->Chg);
1660                         TrackLoads (&Data.Rhs, E, I);
1661                     }
1662
1663                 } else if (E->Info & OF_STORE && (E->Chg & REG_ZP) == 0) {
1664
1665                     /* Too dangerous - there may be a change of a variable
1666                      * within the sequence.
1667                      */
1668                     I = Data.PushIndex;
1669                     State = Initialize;
1670                     break;
1671
1672                 } else if ((E->Use & REG_SP) != 0                       &&
1673                            (E->AM != AM65_ZP_INDY               ||
1674                             RegValIsUnknown (E->RI->In.RegY)    ||
1675                             E->RI->In.RegY < 2)) {
1676
1677                     /* If we are using the stack, and we don't have "indirect Y"
1678                      * addressing mode, or the value of Y is unknown, or less
1679                      * than two, we cannot cope with this piece of code. Having
1680                      * an unknown value of Y means that we cannot correct the
1681                      * stack offset, while having an offset less than two means
1682                      * that the code works with the value on stack which is to
1683                      * be removed.
1684                      */
1685                     I = Data.PushIndex;
1686                     State = Initialize;
1687                     break;
1688
1689                 } else {
1690                     /* Other stuff: Track register usage */
1691                     Data.UsedRegs |= (E->Use | E->Chg);
1692                     TrackLoads (&Data.Rhs, E, I);
1693                 }
1694                 break;
1695
1696             case FoundOp:
1697                 /* Track zero page location usage beyond this point */
1698                 Data.UsedRegs |= GetRegInfo (S, I, REG_SREG | REG_PTR1 | REG_PTR2);
1699
1700                 /* Finalize the load info */
1701                 FinalizeLoadInfo (&Data.Lhs, S);
1702                 FinalizeLoadInfo (&Data.Rhs, S);
1703
1704                 /* Set flags for direct operations */
1705                 CheckDirectOp (&Data);
1706
1707                 /* If the Lhs loads do load from zeropage, we have to include
1708                  * them into UsedRegs registers used. The Rhs loads have already
1709                  * been tracked.
1710                  */
1711                 if (Data.Lhs.A.LoadEntry && Data.Lhs.A.LoadEntry->AM == AM65_ZP) {
1712                     Data.UsedRegs |= Data.Lhs.A.LoadEntry->Use;
1713                 }
1714                 if (Data.Lhs.X.LoadEntry && Data.Lhs.X.LoadEntry->AM == AM65_ZP) {
1715                     Data.UsedRegs |= Data.Lhs.X.LoadEntry->Use;
1716                 }
1717
1718                 /* Check the preconditions. If they aren't ok, reset the insn
1719                  * pointer to the pushax and start over. We will loose part of
1720                  * load tracking but at least a/x has probably lost between
1721                  * pushax and here and will be tracked again when restarting.
1722                  */
1723                 if (!PreCondOk (&Data)) {
1724                     I = Data.PushIndex;
1725                     State = Initialize;
1726                     break;
1727                 }
1728
1729                 /* Adjust stack offsets to account for the upcoming removal */
1730                 AdjustStackOffset (&Data, 2);
1731
1732                 /* Regenerate register info, since AdjustStackOffset changed
1733                  * the code
1734                  */
1735                 CS_GenRegInfo (S);
1736
1737                 /* Prepare the remainder of the data structure. */
1738                 Data.PrevEntry = CS_GetPrevEntry (S, Data.PushIndex);
1739                 Data.PushEntry = CS_GetEntry (S, Data.PushIndex);
1740                 Data.OpEntry   = CS_GetEntry (S, Data.OpIndex);
1741                 Data.NextEntry = CS_GetNextEntry (S, Data.OpIndex);
1742
1743                 /* Call the optimizer function */
1744                 Changes += Data.OptFunc->Func (&Data);
1745
1746                 /* Regenerate register info */
1747                 CS_GenRegInfo (S);
1748
1749                 /* Done */
1750                 State = Initialize;
1751                 break;
1752
1753         }
1754
1755         /* Next entry */
1756         ++I;
1757
1758     }
1759
1760     /* Free the register info */
1761     CS_FreeRegInfo (S);
1762
1763     /* Return the number of changes made */
1764     return Changes;
1765 }
1766
1767
1768