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 Opt_staspidx (CodeSeg* S, unsigned Push, unsigned Store,
  57                               const char* ZPLo, const char* ZPHi)
  58 /* Optimize the staspidx sequence if possible */
  59 {
  60     CodeEntry* X;
  61     CodeEntry* PushEntry;
  62     CodeEntry* StoreEntry;
  63
  64     /* Generate register info */
  65     CS_GenRegInfo (S);
  66
  67     /* Get the push entry */
  68     PushEntry = CS_GetEntry (S, Push);
  69
  70     /* Store the value into the zeropage instead of pushing it */
  71     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
  72     CS_InsertEntry (S, X, Push+1);
  73     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
  74     CS_InsertEntry (S, X, Push+2);
  75
  76     /* Correct the index of the store and get a pointer to the entry */
  77     Store += 2;
  78     StoreEntry = CS_GetEntry (S, Store);
  79
  80     /* Inline the store */
  81     X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, ZPLo, 0, StoreEntry->LI);
  82     CS_InsertEntry (S, X, Store+1);
  83
  84     /* Remove the push and the call to the staspidx function */
  85     CS_DelEntry (S, Store);
  86     CS_DelEntry (S, Push);
  87
  88     /* Free the register info */
  89     CS_FreeRegInfo (S);
  90
  91     /* We changed the sequence */
  92     return 1;
  93 }
  94
  95
  96
  97 static unsigned Opt_tosaddax (CodeSeg* S, unsigned Push, unsigned Add,
  98                               const char* ZPLo, const char* ZPHi)
  99 /* Optimize the tosaddax sequence if possible */
 100 {
 101     CodeEntry* N;
 102     CodeEntry* X;
 103     CodeEntry* PushEntry;
 104     CodeEntry* AddEntry;
 105
 106     /* We need the entry behind the add */
 107     if ((N = CS_GetNextEntry (S, Add)) == 0) {
 108         /* Unavailable */
 109         return 0;
 110     }
 111
 112     /* Generate register info */
 113     CS_GenRegInfo (S);
 114
 115     /* Get the push entry */
 116     PushEntry = CS_GetEntry (S, Push);
 117
 118     /* Store the value into the zeropage instead of pushing it */
 119     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 120     CS_InsertEntry (S, X, Push+1);
 121     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 122     CS_InsertEntry (S, X, Push+2);
 123
 124     /* Correct the index of the add and get a pointer to the entry */
 125     Add += 2;
 126     AddEntry = CS_GetEntry (S, Add);
 127
 128     /* Inline the add */
 129     X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, AddEntry->LI);
 130     CS_InsertEntry (S, X, Add+1);
 131     X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPLo, 0, AddEntry->LI);
 132     CS_InsertEntry (S, X, Add+2);
 133     if (PushEntry->RI->In.RegX == 0 && AddEntry->RI->In.RegX == 0) {
 134         /* The high byte is zero on entry */
 135         CodeLabel* L = CS_GenLabel (S, N);
 136         X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, AddEntry->LI);
 137         CS_InsertEntry (S, X, Add+3);
 138         X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, AddEntry->LI);
 139         CS_InsertEntry (S, X, Add+4);
 140     } else {
 141         /* High byte is unknown */
 142         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AddEntry->LI);
 143         CS_InsertEntry (S, X, Add+3);
 144         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AddEntry->LI);
 145         CS_InsertEntry (S, X, Add+4);
 146         X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPHi, 0, AddEntry->LI);
 147         CS_InsertEntry (S, X, Add+5);
 148         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AddEntry->LI);
 149         CS_InsertEntry (S, X, Add+6);
 150         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AddEntry->LI);
 151         CS_InsertEntry (S, X, Add+7);
 152     }
 153
 154     /* Remove the push and the call to the tosaddax function */
 155     CS_DelEntry (S, Add);
 156     CS_DelEntry (S, Push);
 157
 158     /* Free the register info */
 159     CS_FreeRegInfo (S);
 160
 161     /* We changed the sequence */
 162     return 1;
 163 }
 164
 165
 166
 167 static unsigned Opt_tosandax (CodeSeg* S, unsigned Push, unsigned And,
 168                               const char* ZPLo, const char* ZPHi)
 169 /* Optimize the tosandax sequence if possible */
 170 {
 171     CodeEntry* X;
 172     CodeEntry* PushEntry;
 173     CodeEntry* AndEntry;
 174
 175     /* Generate register info */
 176     CS_GenRegInfo (S);
 177
 178     /* Get the push entry */
 179     PushEntry = CS_GetEntry (S, Push);
 180
 181     /* Store the value into the zeropage instead of pushing it */
 182     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 183     CS_InsertEntry (S, X, Push+1);
 184     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 185     CS_InsertEntry (S, X, Push+2);
 186
 187     /* Correct the index of the add and get a pointer to the entry */
 188     And += 2;
 189     AndEntry = CS_GetEntry (S, And);
 190
 191     /* Inline the and */
 192     X = NewCodeEntry (OP65_AND, AM65_ZP, ZPLo, 0, AndEntry->LI);
 193     CS_InsertEntry (S, X, And+1);
 194     if (PushEntry->RI->In.RegX == 0 || AndEntry->RI->In.RegX == 0) {
 195         /* The high byte is zero */
 196         X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, AndEntry->LI);
 197         CS_InsertEntry (S, X, And+2);
 198     } else {
 199         /* High byte is unknown */
 200         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AndEntry->LI);
 201         CS_InsertEntry (S, X, And+2);
 202         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AndEntry->LI);
 203         CS_InsertEntry (S, X, And+3);
 204         X = NewCodeEntry (OP65_AND, AM65_ZP, ZPHi, 0, AndEntry->LI);
 205         CS_InsertEntry (S, X, And+4);
 206         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AndEntry->LI);
 207         CS_InsertEntry (S, X, And+5);
 208         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AndEntry->LI);
 209         CS_InsertEntry (S, X, And+6);
 210     }
 211
 212     /* Remove the push and the call to the tosandax function */
 213     CS_DelEntry (S, And);
 214     CS_DelEntry (S, Push);
 215
 216     /* Free the register info */
 217     CS_FreeRegInfo (S);
 218
 219     /* We changed the sequence */
 220     return 1;
 221 }
 222
 223
 224
 225 static unsigned Opt_tosorax (CodeSeg* S, unsigned Push, unsigned Or,
 226                              const char* ZPLo, const char* ZPHi)
 227 /* Optimize the tosorax sequence if possible */
 228 {
 229     CodeEntry* X;
 230     CodeEntry* PushEntry;
 231     CodeEntry* OrEntry;
 232
 233     /* Generate register info */
 234     CS_GenRegInfo (S);
 235
 236     /* Get the push entry */
 237     PushEntry = CS_GetEntry (S, Push);
 238
 239     /* Store the value into the zeropage instead of pushing it */
 240     X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
 241     CS_InsertEntry (S, X, Push+1);
 242     X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
 243     CS_InsertEntry (S, X, Push+2);
 244
 245     /* Correct the index of the add and get a pointer to the entry */
 246     Or += 2;
 247     OrEntry = CS_GetEntry (S, Or);
 248
 249     /* Inline the or */
 250     X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 251     CS_InsertEntry (S, X, Or+1);
 252     if (PushEntry->RI->In.RegX >= 0 && OrEntry->RI->In.RegX == 0) {
 253         /* Value of X will be that of the first operand */
 254         char Buf [16];
 255         xsprintf (Buf, sizeof (Buf), "$%02X", PushEntry->RI->In.RegX);
 256         X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, OrEntry->LI);
 257         CS_InsertEntry (S, X, Or+2);
 258     } else if (PushEntry->RI->In.RegX != 0) {
 259         /* High byte is unknown */
 260         X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 261         CS_InsertEntry (S, X, Or+2);
 262         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, OrEntry->LI);
 263         CS_InsertEntry (S, X, Or+3);
 264         X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPHi, 0, OrEntry->LI);
 265         CS_InsertEntry (S, X, Or+4);
 266         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, OrEntry->LI);
 267         CS_InsertEntry (S, X, Or+5);
 268         X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, OrEntry->LI);
 269         CS_InsertEntry (S, X, Or+6);
 270     }
 271
 272     /* Remove the push and the call to the tosandax function */
 273     CS_DelEntry (S, Or);
 274     CS_DelEntry (S, Push);
 275
 276     /* Free the register info */
 277     CS_FreeRegInfo (S);
 278
 279     /* We changed the sequence */
 280     return 1;
 281 }
 282
 283
 284
 285 /*****************************************************************************/
 286 /*                                   Code                                    */
 287 /*****************************************************************************/
 288
 289
 290
 291 typedef unsigned (*OptFunc) (CodeSeg* S, unsigned Push, unsigned Store,
 292                              const char* ZPLo, const char* ZPHi);
 293 typedef struct OptFuncDesc OptFuncDesc;
 294 struct OptFuncDesc {
 295     const char*         Name;   /* Name of the replaced runtime function */
 296     OptFunc             Func;   /* Function pointer */
 297 };
 298
 299 static const OptFuncDesc FuncTable[] = {
 300     { "staspidx",       Opt_staspidx    },
 301     { "tosaddax",       Opt_tosaddax    },
 302     { "tosandax",       Opt_tosandax    },
 303     { "tosorax",        Opt_tosorax     },
 304 };
 305 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
 306
 307
 308
 309 static int CmpFunc (const void* Key, const void* Func)
 310 /* Compare function for bsearch */
 311 {
 312     return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
 313 }
 314
 315
 316
 317 static const OptFuncDesc* FindFunc (const char* Name)
 318 /* Find the function with the given name. Return a pointer to the table entry
 319  * or NULL if the function was not found.
 320  */
 321 {
 322     return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
 323 }
 324
 325
 326
 327 /*****************************************************************************/
 328 /*                                   Code                                    */
 329 /*****************************************************************************/
 330
 331
 332
 333 unsigned OptStackOps (CodeSeg* S)
 334 /* Optimize operations that take operands via the stack */
 335 {
 336     unsigned Changes = 0;     /* Number of changes in one run */
 337     int      InSeq = 0;       /* Inside a sequence */
 338     unsigned Push = 0;        /* Index of pushax */
 339     unsigned UsedRegs = 0;    /* Zeropage registers used in sequence */
 340
 341
 342     /* Look for a call to pushax followed by a call to some other function
 343      * that takes it's first argument on the stack, and the second argument
 344      * in the primary register.
 345      * It depends on the code between the two if we can handle/transform the
 346      * sequence, so check this code for the following list of things:
 347      *
 348      *  - there must not be a jump or conditional branch (this may
 349      *    get relaxed later).
 350      *  - there may not be accesses to local variables (may also be
 351      *    relaxed later)
 352      *  - no subroutine calls
 353      *  - no jump labels
 354      *
 355      * Since we need a zero page register later, do also check the
 356      * intermediate code for zero page use.
 357      */
 358     unsigned I = 0;
 359     while (I < CS_GetEntryCount (S)) {
 360
 361         /* Get the next entry */
 362         CodeEntry* E = CS_GetEntry (S, I);
 363
 364         /* Handling depends if we're inside a sequence or not */
 365         if (InSeq) {
 366
 367             /* Subroutine call? */
 368             if (E->OPC == OP65_JSR) {
 369
 370                 /* Check if this is one of our functions */
 371                 const OptFuncDesc* F = FindFunc (E->Arg);
 372                 if (F) {
 373
 374                     /* Determine the register to use */
 375                     const char* ZPLo;
 376                     const char* ZPHi;
 377                     UsedRegs |= GetRegInfo (S, I+1, REG_SREG | REG_PTR1 | REG_PTR2);
 378                     if ((UsedRegs & REG_SREG) == REG_NONE) {
 379                         /* SREG is available */
 380                         ZPLo = "sreg";
 381                         ZPHi = "sreg+1";
 382                     } else if ((UsedRegs & REG_PTR1) == REG_NONE) {
 383                         ZPLo = "ptr1";
 384                         ZPHi = "ptr1+1";
 385                     } else if ((UsedRegs & REG_PTR2) == REG_NONE) {
 386                         ZPLo = "ptr2";
 387                         ZPHi = "ptr2+1";
 388                     } else {
 389                         /* No registers available */
 390                         ZPLo = 0;
 391                         ZPHi = 0;
 392                     }
 393
 394                     /* If we have a register, call the optimizer function */
 395                     if (ZPLo && ZPHi) {
 396                         Changes += F->Func (S, Push, I, ZPLo, ZPHi);
 397                     }
 398
 399                     /* End of sequence */
 400                     InSeq = 0;
 401
 402                 } else if (strcmp (E->Arg, "pushax") == 0) {
 403                     /* Restart the sequence */
 404                     Push     = I;
 405                     UsedRegs = REG_NONE;
 406                 } else {
 407                     /* A call to an unkown subroutine ends the sequence */
 408                     InSeq = 0;
 409                 }
 410
 411             } else if ((E->Info & OF_BRA) != 0 ||
 412                        (E->Use & REG_SP) != 0  ||
 413                        CE_HasLabel (E)) {
 414
 415                 /* All this stuff is not allowed in a sequence */
 416                 InSeq = 0;
 417
 418             } else {
 419
 420                 /* Other stuff: Track zeropage register usage */
 421                 UsedRegs |= (E->Use | E->Chg);
 422
 423             }
 424
 425         } else if (CE_IsCall (E, "pushax")) {
 426
 427             /* This starts a sequence */
 428             Push     = I;
 429             UsedRegs = REG_NONE;
 430             InSeq    = 1;
 431
 432         }
 433
 434         /* Next entry */
 435         ++I;
 436
 437     }
 438
 439     /* Return the number of changes made */
 440     return Changes;
 441 }
 442
 443
 444