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      Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <stdlib.h>
  37
  38 /* common */
  39 #include "xsprintf.h"
  40
  41 /* cc65 */
  42 #include "codeent.h"
  43 #include "codeinfo.h"
  44 #include "codeopt.h"
  45 #include "error.h"
  46 #include "coptstop.h"
  47
  48
  49
  50 /*****************************************************************************/
  51 /*                                  Helpers                                  */
  52 /*****************************************************************************/
  53
  54
  55
  56 static unsigned AdjustStackOffset (CodeSeg* S, unsigned Start, unsigned Stop,
  57                                    unsigned Offs)
  58 /* Adjust the offset for all stack accesses in the range Start to Stop, both
  59  * inclusive. The function returns the number of instructions that have been
  60  * inserted.
  61  */
  62 {
  63     /* Number of inserted instructions */
  64     unsigned Inserted = 0;
  65
  66     /* Walk over all entries */
  67     unsigned I = Start;
  68     while (I <= Stop) {
  69
  70         CodeEntry* E = CS_GetEntry (S, I);
  71
  72         if (E->Use & REG_SP) {
  73
  74             CodeEntry* P;
  75
  76             /* Check for some things that should not happen */
  77             CHECK (E->AM == AM65_ZP_INDY || E->RI->In.RegY >= (short) Offs);
  78             CHECK (strcmp (E->Arg, "sp") == 0);
  79
  80             /* Get the code entry before this one. If it's a LDY, adjust the
  81              * value.
  82              */
  83             P = CS_GetPrevEntry (S, I);
  84             if (P && P->OPC == OP65_LDY && CE_KnownImm (P)) {
  85
  86                 /* The Y load is just before the stack access, adjust it */
  87                 CE_SetNumArg (P, P->Num - Offs);
  88
  89             } else {
  90
  91                 /* Insert a new load instruction before the stack access */
  92                 char Buf [16];
  93                 CodeEntry* X;
  94                 xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegY - Offs);
  95                 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, E->LI);
  96                 CS_InsertEntry (S, X, I);
  97
  98                 /* One more inserted entries */
  99                 ++Inserted;
 100                 ++Stop;
 101
 102                 /* Be sure to skip the stack access for the next round */
 103                 ++I;
 104
 105             }
 106
 107         }
 108
 109         /* Next entry */
 110         ++I;
 111     }
 112
 113     /* Return the number of inserted entries */
 114     return Inserted;
 115 }
 116
 117
 118
 119 /*****************************************************************************/
 120 /*                       Actual optimization functions                       */
 121 /*****************************************************************************/
 122
 123
 124
 125 static unsigned Opt_staspidx (CodeSeg* S, unsigned Push, unsigned Store,
 126                               const char* ZPLo, const char* ZPHi)
 127 /* Optimize the staspidx sequence if possible */
 128 {
 129     CodeEntry* X;
 130     CodeEntry* PushEntry;
 131     CodeEntry* StoreEntry;
 132
 133     /* Get the push entry */
 134     PushEntry = CS_GetEntry (S, Push);
 135
 136     /* Store the value into the zeropage instead of pushing it */
 137     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 138     CS_InsertEntry (S, X, Push+1);
 139     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 140     CS_InsertEntry (S, X, Push+2);
 141
 142     /* Correct the index of the store and get a pointer to the entry */
 143     Store += 2;
 144     StoreEntry = CS_GetEntry (S, Store);
 145
 146     /* Inline the store */
 147     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, ZPLo, 0, StoreEntry->LI);
 148     CS_InsertEntry (S, X, Store+1);
 149
 150     /* Remove the push and the call to the staspidx function */
 151     CS_DelEntry (S, Store);
 152     CS_DelEntry (S, Push);
 153
 154     /* We changed the sequence */
 155     return 1;
 156 }
 157
 158
 159
 160 static unsigned Opt_tosaddax (CodeSeg* S, unsigned Push, unsigned Add,
 161                               const char* ZPLo, const char* ZPHi)
 162 /* Optimize the tosaddax sequence if possible */
 163 {
 164     CodeEntry* N;
 165     CodeEntry* X;
 166     CodeEntry* PushEntry;
 167     CodeEntry* AddEntry;
 168
 169     /* We need the entry behind the add */
 170     CHECK ((N = CS_GetNextEntry (S, Add)) != 0);
 171
 172     /* Get the push entry */
 173     PushEntry = CS_GetEntry (S, Push);
 174
 175     /* Store the value into the zeropage instead of pushing it */
 176     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 177     CS_InsertEntry (S, X, Push+1);
 178     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 179     CS_InsertEntry (S, X, Push+2);
 180
 181     /* Correct the index of the add and get a pointer to the entry */
 182     Add += 2;
 183     AddEntry = CS_GetEntry (S, Add);
 184
 185     /* Inline the add */
 186     X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, AddEntry->LI);
 187     CS_InsertEntry (S, X, Add+1);
 188     X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPLo, 0, AddEntry->LI);
 189     CS_InsertEntry (S, X, Add+2);
 190     if (PushEntry->RI->In.RegX == 0) {
 191         /* The high byte is the value in X plus the carry */
 192         CodeLabel* L = CS_GenLabel (S, N);
 193         X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, AddEntry->LI);
 194         CS_InsertEntry (S, X, Add+3);
 195         X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, AddEntry->LI);
 196         CS_InsertEntry (S, X, Add+4);
 197     } else if (AddEntry->RI->In.RegX == 0) {
 198         /* The high byte is that of the first operand plus carry */
 199         CodeLabel* L;
 200         if (PushEntry->RI->In.RegX >= 0) {
 201             /* Value of first op high byte is known */
 202             char Buf [16];
 203             xsprintf (Buf, sizeof (Buf), "$%02X", PushEntry->RI->In.RegX);
 204             X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, AddEntry->LI);
 205         } else {
 206             /* Value of first op high byte is unknown */
 207             X = NewCodeEntry (OP65_LDX, AM65_ZP, ZPHi, 0, AddEntry->LI);
 208         }
 209         CS_InsertEntry (S, X, Add+3);
 210         L = CS_GenLabel (S, N);
 211         X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, AddEntry->LI);
 212         CS_InsertEntry (S, X, Add+4);
 213         X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, AddEntry->LI);
 214         CS_InsertEntry (S, X, Add+5);
 215     } else {
 216         /* High byte is unknown */
 217         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AddEntry->LI);
 218         CS_InsertEntry (S, X, Add+3);
 219         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AddEntry->LI);
 220         CS_InsertEntry (S, X, Add+4);
 221         X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPHi, 0, AddEntry->LI);
 222         CS_InsertEntry (S, X, Add+5);
 223         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AddEntry->LI);
 224         CS_InsertEntry (S, X, Add+6);
 225         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AddEntry->LI);
 226         CS_InsertEntry (S, X, Add+7);
 227     }
 228
 229     /* Remove the push and the call to the tosaddax function */
 230     CS_DelEntry (S, Add);
 231     CS_DelEntry (S, Push);
 232
 233     /* We changed the sequence */
 234     return 1;
 235 }
 236
 237
 238
 239 static unsigned Opt_tosandax (CodeSeg* S, unsigned Push, unsigned And,
 240                               const char* ZPLo, const char* ZPHi)
 241 /* Optimize the tosandax sequence if possible */
 242 {
 243     CodeEntry* X;
 244     CodeEntry* PushEntry;
 245     CodeEntry* AndEntry;
 246
 247     /* Get the push entry */
 248     PushEntry = CS_GetEntry (S, Push);
 249
 250     /* Store the value into the zeropage instead of pushing it */
 251     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 252     CS_InsertEntry (S, X, Push+1);
 253     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 254     CS_InsertEntry (S, X, Push+2);
 255
 256     /* Correct the index of the add and get a pointer to the entry */
 257     And += 2;
 258     AndEntry = CS_GetEntry (S, And);
 259
 260     /* Inline the and */
 261     X = NewCodeEntry (OP65_AND, AM65_ZP, ZPLo, 0, AndEntry->LI);
 262     CS_InsertEntry (S, X, And+1);
 263     if (PushEntry->RI->In.RegX == 0 || AndEntry->RI->In.RegX == 0) {
 264         /* The high byte is zero */
 265         X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, AndEntry->LI);
 266         CS_InsertEntry (S, X, And+2);
 267     } else {
 268         /* High byte is unknown */
 269         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AndEntry->LI);
 270         CS_InsertEntry (S, X, And+2);
 271         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AndEntry->LI);
 272         CS_InsertEntry (S, X, And+3);
 273         X = NewCodeEntry (OP65_AND, AM65_ZP, ZPHi, 0, AndEntry->LI);
 274         CS_InsertEntry (S, X, And+4);
 275         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AndEntry->LI);
 276         CS_InsertEntry (S, X, And+5);
 277         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AndEntry->LI);
 278         CS_InsertEntry (S, X, And+6);
 279     }
 280
 281     /* Remove the push and the call to the tosandax function */
 282     CS_DelEntry (S, And);
 283     CS_DelEntry (S, Push);
 284
 285     /* We changed the sequence */
 286     return 1;
 287 }
 288
 289
 290
 291 static unsigned Opt_tosorax (CodeSeg* S, unsigned Push, unsigned Or,
 292                              const char* ZPLo, const char* ZPHi)
 293 /* Optimize the tosorax sequence if possible */
 294 {
 295     CodeEntry* X;
 296     CodeEntry* PushEntry;
 297     CodeEntry* OrEntry;
 298
 299     /* Get the push entry */
 300     PushEntry = CS_GetEntry (S, Push);
 301
 302     /* Store the value into the zeropage instead of pushing it */
 303     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 304     CS_InsertEntry (S, X, Push+1);
 305     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 306     CS_InsertEntry (S, X, Push+2);
 307
 308     /* Correct the index of the add and get a pointer to the entry */
 309     Or += 2;
 310     OrEntry = CS_GetEntry (S, Or);
 311
 312     /* Inline the or */
 313     X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 314     CS_InsertEntry (S, X, Or+1);
 315     if (PushEntry->RI->In.RegX >= 0 && OrEntry->RI->In.RegX >= 0) {
 316         /* Both values known, precalculate the result */
 317         char Buf [16];
 318         int Val = (PushEntry->RI->In.RegX | OrEntry->RI->In.RegX);
 319         xsprintf (Buf, sizeof (Buf), "$%02X", Val);
 320         X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, OrEntry->LI);
 321         CS_InsertEntry (S, X, Or+2);
 322     } else if (PushEntry->RI->In.RegX != 0) {
 323         /* High byte is unknown */
 324         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 325         CS_InsertEntry (S, X, Or+2);
 326         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, OrEntry->LI);
 327         CS_InsertEntry (S, X, Or+3);
 328         X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPHi, 0, OrEntry->LI);
 329         CS_InsertEntry (S, X, Or+4);
 330         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, OrEntry->LI);
 331         CS_InsertEntry (S, X, Or+5);
 332         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 333         CS_InsertEntry (S, X, Or+6);
 334     }
 335
 336     /* Remove the push and the call to the tosandax function */
 337     CS_DelEntry (S, Or);
 338     CS_DelEntry (S, Push);
 339
 340     /* We changed the sequence */
 341     return 1;
 342 }
 343
 344
 345
 346 static unsigned Opt_tosxorax (CodeSeg* S, unsigned Push, unsigned Xor,
 347                               const char* ZPLo, const char* ZPHi)
 348 /* Optimize the tosorax sequence if possible */
 349 {
 350     CodeEntry* X;
 351     CodeEntry* PushEntry;
 352     CodeEntry* XorEntry;
 353
 354     /* Get the push entry */
 355     PushEntry = CS_GetEntry (S, Push);
 356
 357     /* Store the value into the zeropage instead of pushing it */
 358     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 359     CS_InsertEntry (S, X, Push+1);
 360     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 361     CS_InsertEntry (S, X, Push+2);
 362
 363     /* Correct the index of the add and get a pointer to the entry */
 364     Xor += 2;
 365     XorEntry = CS_GetEntry (S, Xor);
 366
 367     /* Inline the or */
 368     X = NewCodeEntry (OP65_EOR, AM65_ZP, ZPLo, 0, XorEntry->LI);
 369     CS_InsertEntry (S, X, Xor+1);
 370     if (PushEntry->RI->In.RegX >= 0 && XorEntry->RI->In.RegX >= 0) {
 371         /* Both values known, precalculate the result */
 372         char Buf [16];
 373         int Val = (PushEntry->RI->In.RegX ^ XorEntry->RI->In.RegX);
 374         xsprintf (Buf, sizeof (Buf), "$%02X", Val);
 375         X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, XorEntry->LI);
 376         CS_InsertEntry (S, X, Xor+2);
 377     } else if (PushEntry->RI->In.RegX != 0) {
 378         /* High byte is unknown */
 379         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, XorEntry->LI);
 380         CS_InsertEntry (S, X, Xor+2);
 381         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, XorEntry->LI);
 382         CS_InsertEntry (S, X, Xor+3);
 383         X = NewCodeEntry (OP65_EOR, AM65_ZP, ZPHi, 0, XorEntry->LI);
 384         CS_InsertEntry (S, X, Xor+4);
 385         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, XorEntry->LI);
 386         CS_InsertEntry (S, X, Xor+5);
 387         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, XorEntry->LI);
 388         CS_InsertEntry (S, X, Xor+6);
 389     }
 390
 391     /* Remove the push and the call to the tosandax function */
 392     CS_DelEntry (S, Xor);
 393     CS_DelEntry (S, Push);
 394
 395     /* We changed the sequence */
 396     return 1;
 397 }
 398
 399
 400
 401 /*****************************************************************************/
 402 /*                                   Code                                    */
 403 /*****************************************************************************/
 404
 405
 406
 407 typedef unsigned (*OptFunc) (CodeSeg* S, unsigned Push, unsigned Store,
 408                              const char* ZPLo, const char* ZPHi);
 409 typedef struct OptFuncDesc OptFuncDesc;
 410 struct OptFuncDesc {
 411     const char*         Name;   /* Name of the replaced runtime function */
 412     OptFunc             Func;   /* Function pointer */
 413 };
 414
 415 static const OptFuncDesc FuncTable[] = {
 416     { "staspidx",       Opt_staspidx    },
 417     { "tosaddax",       Opt_tosaddax    },
 418     { "tosandax",       Opt_tosandax    },
 419     { "tosorax",        Opt_tosorax     },
 420     { "tosxorax",       Opt_tosxorax    },
 421 };
 422 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
 423
 424
 425
 426 static int CmpFunc (const void* Key, const void* Func)
 427 /* Compare function for bsearch */
 428 {
 429     return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
 430 }
 431
 432
 433
 434 static const OptFuncDesc* FindFunc (const char* Name)
 435 /* Find the function with the given name. Return a pointer to the table entry
 436  * or NULL if the function was not found.
 437  */
 438 {
 439     return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
 440 }
 441
 442
 443
 444 /*****************************************************************************/
 445 /*                                   Code                                    */
 446 /*****************************************************************************/
 447
 448
 449
 450 unsigned OptStackOps (CodeSeg* S)
 451 /* Optimize operations that take operands via the stack */
 452 {
 453     unsigned Changes = 0;     /* Number of changes in one run */
 454     int      InSeq = 0;       /* Inside a sequence */
 455     unsigned Push = 0;        /* Index of pushax */
 456     unsigned UsedRegs = 0;    /* Zeropage registers used in sequence */
 457     unsigned I;
 458
 459     /* Generate register info */
 460     CS_GenRegInfo (S);
 461
 462     /* Look for a call to pushax followed by a call to some other function
 463      * that takes it's first argument on the stack, and the second argument
 464      * in the primary register.
 465      * It depends on the code between the two if we can handle/transform the
 466      * sequence, so check this code for the following list of things:
 467      *
 468      *  - there must not be a jump or conditional branch (this may
 469      *    get relaxed later).
 470      *  - there may not be accesses to local variables with unknown
 471      *    offsets (because we have to adjust these offsets).
 472      *  - no subroutine calls
 473      *  - no jump labels
 474      *
 475      * Since we need a zero page register later, do also check the
 476      * intermediate code for zero page use.
 477      */
 478     I = 0;
 479     while (I < CS_GetEntryCount (S)) {
 480
 481         /* Get the next entry */
 482         CodeEntry* E = CS_GetEntry (S, I);
 483
 484         /* Handling depends if we're inside a sequence or not */
 485         if (InSeq) {
 486
 487             if ((E->Info & OF_BRA) != 0                              ||
 488                 ((E->Use & REG_SP) != 0                         &&
 489                  (E->AM != AM65_ZP_INDY || E->RI->In.RegY < 0))      ||
 490                 CE_HasLabel (E)) {
 491
 492                 /* All this stuff is not allowed in a sequence */
 493                 InSeq = 0;
 494
 495             } else if (E->OPC == OP65_JSR) {
 496
 497                 /* Subroutine call: Check if this is one of our functions */
 498                 const OptFuncDesc* F = FindFunc (E->Arg);
 499                 if (F) {
 500
 501                     /* Determine the register to use */
 502                     const char* ZPLo;
 503                     const char* ZPHi;
 504                     UsedRegs |= GetRegInfo (S, I+1, REG_SREG | REG_PTR1 | REG_PTR2);
 505                     if ((UsedRegs & REG_SREG) == REG_NONE) {
 506                         /* SREG is available */
 507                         ZPLo = "sreg";
 508                         ZPHi = "sreg+1";
 509                     } else if ((UsedRegs & REG_PTR1) == REG_NONE) {
 510                         ZPLo = "ptr1";
 511                         ZPHi = "ptr1+1";
 512                     } else if ((UsedRegs & REG_PTR2) == REG_NONE) {
 513                         ZPLo = "ptr2";
 514                         ZPHi = "ptr2+1";
 515                     } else {
 516                         /* No registers available */
 517                         ZPLo = 0;
 518                         ZPHi = 0;
 519                     }
 520
 521                     /* If we have a register, call the optimizer function */
 522                     if (ZPLo && ZPHi) {
 523
 524                         /* Adjust stack offsets */
 525                         unsigned Op = I + AdjustStackOffset (S, Push, I, 2);
 526
 527                         /* Call the optimizer function */
 528                         Changes += F->Func (S, Push, Op, ZPLo, ZPHi);
 529
 530                         /* Regenerate register info */
 531                         CS_GenRegInfo (S);
 532                     }
 533
 534                     /* End of sequence */
 535                     InSeq = 0;
 536
 537                 } else if (strcmp (E->Arg, "pushax") == 0) {
 538                     /* Restart the sequence */
 539                     Push     = I;
 540                     UsedRegs = REG_NONE;
 541                 } else {
 542                     /* A call to an unkown subroutine ends the sequence */
 543                     InSeq = 0;
 544                 }
 545
 546             } else {
 547
 548                 /* Other stuff: Track zeropage register usage */
 549                 UsedRegs |= (E->Use | E->Chg);
 550
 551             }
 552
 553         } else if (CE_IsCall (E, "pushax")) {
 554
 555             /* This starts a sequence */
 556             Push     = I;
 557             UsedRegs = REG_NONE;
 558             InSeq    = 1;
 559
 560         }
 561
 562         /* Next entry */
 563         ++I;
 564
 565     }
 566
 567     /* Free the register info */
 568     CS_FreeRegInfo (S);
 569
 570     /* Return the number of changes made */
 571     return Changes;
 572 }
 573
 574
 575