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