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

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 coptsize.c                                */
   4 /*                                                                           */
   5 /*                              Size optimizations                           */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2002-2005, Ullrich von Bassewitz                                      */
  10 /*                Römerstraße 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 "cpu.h"
  40
  41 /* cc65 */
  42 #include "codeent.h"
  43 #include "codeinfo.h"
  44 #include "coptsize.h"
  45 #include "reginfo.h"
  46
  47
  48
  49 /*****************************************************************************/
  50 /*                                   Data                                    */
  51 /*****************************************************************************/
  52
  53
  54
  55 typedef struct CallDesc CallDesc;
  56 struct CallDesc {
  57     const char*     LongFunc;       /* Long function name */
  58     short           A, X, Y;        /* Register contents */
  59     const char*     ShortFunc;      /* Short function name */
  60 };
  61
  62 /* Note: The table is sorted. If there is more than one entry with the same
  63  * name, entries are sorted best match first, so when searching linear for
  64  * a match, the first one can be used because it is also the best one (or
  65  * at least none of the following ones are better).
  66  */
  67 static const CallDesc CallTable [] = {
  68     /* Name          A register      X register     Y register     replacement */
  69     { "addeqysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "addeq0sp"  },
  70     { "laddeqysp", UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "laddeq0sp" },
  71     { "ldaxidx",   UNKNOWN_REGVAL, UNKNOWN_REGVAL,              1, "ldaxi"     },
  72     { "ldaxysp",   UNKNOWN_REGVAL, UNKNOWN_REGVAL,              1, "ldax0sp"   },
  73     { "ldeaxidx",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              3, "ldeaxi"    },
  74     { "ldeaxysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              3, "ldeax0sp"  },
  75     { "pusha",                  0, UNKNOWN_REGVAL, UNKNOWN_REGVAL, "pushc0"    },
  76     { "pusha",                  1, UNKNOWN_REGVAL, UNKNOWN_REGVAL, "pushc1"    },
  77     { "pusha",                  2, UNKNOWN_REGVAL, UNKNOWN_REGVAL, "pushc2"    },
  78     { "pushax",                 0,              0, UNKNOWN_REGVAL, "push0"     },
  79     { "pushax",                 1,              0, UNKNOWN_REGVAL, "push1"     },
  80     { "pushax",                 2,              0, UNKNOWN_REGVAL, "push2"     },
  81     { "pushax",                 3,              0, UNKNOWN_REGVAL, "push3"     },
  82     { "pushax",                 4,              0, UNKNOWN_REGVAL, "push4"     },
  83     { "pushax",                 5,              0, UNKNOWN_REGVAL, "push5"     },
  84     { "pushax",                 6,              0, UNKNOWN_REGVAL, "push6"     },
  85     { "pushax",                 7,              0, UNKNOWN_REGVAL, "push7"     },
  86     { "pushax",    UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "pusha0"    },
  87     { "pushax",    UNKNOWN_REGVAL,           0xFF, UNKNOWN_REGVAL, "pushaFF"   },
  88     { "pushaysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "pusha0sp"  },
  89     { "pushwidx",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              1, "pushw"     },
  90     { "pushwysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              3, "pushw0sp"  },
  91     { "staxysp",   UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "stax0sp"   },
  92     { "tosaddax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosadda0"  },
  93     { "tosandax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosanda0"  },
  94     { "tosdivax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosdiva0"  },
  95     { "toseqax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "toseqa0"   },
  96     { "tosgeax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosgea0"   },
  97     { "tosgtax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosgta0"   },
  98     { "tosleax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "toslea0"   },
  99     { "tosorax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosora0"   },
 100     { "lsubeqysp", UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "lsubeq0sp" },
 101     { "steaxysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "steax0sp"  },
 102     { "subeqysp",  UNKNOWN_REGVAL, UNKNOWN_REGVAL,              0, "subeq0sp"  },
 103     { "tosltax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "toslta0"   },
 104     { "tosmodax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosmoda0"  },
 105     { "tosmulax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosmula0"  },
 106     { "tosneax",   UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosnea0"   },
 107     { "tosrsubax", UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosrsuba0" },
 108     { "tossubax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tossuba0"  },
 109     { "tosudivax", UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosudiva0" },
 110     { "tosugeax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosugea0"  },
 111     { "tosugtax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosugta0"  },
 112     { "tosuleax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosulea0"  },
 113     { "tosultax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosulta0"  },
 114     { "tosumodax", UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosumoda0" },
 115     { "tosumulax", UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosumula0" },
 116     { "tosxorax",  UNKNOWN_REGVAL,              0, UNKNOWN_REGVAL, "tosxora0"  },
 117
 118 #if 0
 119     "tosadd0ax",         /* tosaddeax, sreg = 0 */
 120     "laddeqa",           /* laddeq, sreg = 0, x = 0 */
 121     "laddeq1",           /* laddeq, sreg = 0, x = 0, a = 1 */
 122     "tosand0ax",         /* tosandeax, sreg = 0 */
 123     "tosdiv0ax",         /* tosdiveax, sreg = 0 */
 124     "tosmod0ax",         /* tosmodeax, sreg = 0 */
 125     "tosmul0ax",         /* tosmuleax, sreg = 0 */
 126     "tosumul0ax",        /* tosumuleax, sreg = 0 */
 127     "tosor0ax",          /* tosoreax, sreg = 0 */
 128     "push0ax",           /* pusheax, sreg = 0 */
 129     "tosrsub0ax",        /* tosrsubeax, sreg = 0 */
 130     "tosshl0ax",         /* tosshleax, sreg = 0 */
 131     "tosasl0ax",         /* tosasleax, sreg = 0 */
 132     "tosshr0ax",         /* tosshreax, sreg = 0 */
 133     "tosasr0ax",         /* tosasreax, sreg = 0 */
 134     "tossub0ax",         /* tossubeax, sreg = 0 */
 135     "lsubeqa",           /* lsubeq, sreg = 0, x = 0 */
 136     "lsubeq1",           /* lsubeq, sreg = 0, x = 0, a = 1 */
 137     "tosudiv0ax",        /* tosudiveax, sreg = 0 */
 138     "tosumod0ax",        /* tosumodeax, sreg = 0 */
 139     "tosxor0ax",         /* tosxoreax, sreg = 0 */
 140 #endif
 141 };
 142 #define CALL_COUNT (sizeof(CallTable) / sizeof(CallTable[0]))
 143
 144
 145
 146 /*****************************************************************************/
 147 /*                                  Helpers                                  */
 148 /*****************************************************************************/
 149
 150
 151
 152 static const CallDesc* FindCall (const char* Name)
 153 /* Find the function with the given name. Return a pointer to the table entry
 154  * or NULL if the function was not found.
 155  */
 156 {
 157     /* Do a binary search */
 158     int First = 0;
 159     int Last = CALL_COUNT - 1;
 160     int Found = 0;
 161
 162     while (First <= Last) {
 163
 164         /* Set current to mid of range */
 165         int Current = (Last + First) / 2;
 166
 167         /* Do a compare */
 168         int Result = strcmp (CallTable[Current].LongFunc, Name);
 169         if (Result < 0) {
 170             First = Current + 1;
 171         } else {
 172             Last = Current - 1;
 173             if (Result == 0) {
 174                 /* Found. Repeat the procedure until the first of all entries
 175                  * with the same name is found.
 176                  */
 177                 Found = 1;
 178             }
 179         }
 180     }
 181
 182     /* Return the first entry if found, or NULL otherwise */
 183     return Found? &CallTable[First] : 0;
 184 }
 185
 186
 187
 188 /*****************************************************************************/
 189 /*                                   Code                                    */
 190 /*****************************************************************************/
 191
 192
 193
 194 unsigned OptSize1 (CodeSeg* S)
 195 /* Do size optimization by calling special subroutines that preload registers.
 196  * This routine does not work standalone, it needs a following register load
 197  * removal pass.
 198  */
 199 {
 200     CodeEntry* E;
 201     unsigned Changes = 0;
 202     unsigned I;
 203
 204     /* Generate register info for the following step */
 205     CS_GenRegInfo (S);
 206
 207     /* Walk over the entries */
 208     I = 0;
 209     while (I < CS_GetEntryCount (S)) {
 210
 211         const CallDesc* D;
 212
 213         /* Get next entry */
 214         E = CS_GetEntry (S, I);
 215
 216         /* Check if it's a subroutine call */
 217         if (E->OPC == OP65_JSR && (D = FindCall (E->Arg)) != 0) {
 218
 219             /* Check for any of the known functions. */
 220             while (1) {
 221
 222                 /* Check the registers */
 223                 if ((D->A < 0 || D->A == E->RI->In.RegA) &&
 224                     (D->X < 0 || D->X == E->RI->In.RegX) &&
 225                     (D->Y < 0 || D->Y == E->RI->In.RegY)) {
 226
 227                     /* Ok, match for all registers */
 228                     CodeEntry* X;
 229                     X = NewCodeEntry (E->OPC, E->AM, D->ShortFunc, 0, E->LI);
 230                     CS_InsertEntry (S, X, I+1);
 231                     CS_DelEntry (S, I);
 232
 233                     /* Remember that we had changes */
 234                     ++Changes;
 235
 236                     /* Done */
 237                     break;
 238                 }
 239
 240                 /* Next table entry, bail out if next entry not valid */
 241                 if (++D >= CallTable + CALL_COUNT ||
 242                     strcmp (D->LongFunc, E->Arg) != 0) {
 243                     /* End of table or entries reached */
 244                     break;
 245                 }
 246             }
 247         }
 248
 249         /* Next entry */
 250         ++I;
 251
 252     }
 253
 254     /* Free register info */
 255     CS_FreeRegInfo (S);
 256
 257     /* Return the number of changes made */
 258     return Changes;
 259 }
 260
 261
 262
 263 unsigned OptSize2 (CodeSeg* S)
 264 /* Do size optimization by using shorter code sequences, even if this
 265  * introduces relations between instructions. This step must be one of the
 266  * last steps, because it makes further work much more difficult.
 267  */
 268 {
 269     unsigned Changes = 0;
 270     unsigned I;
 271
 272     /* Generate register info for the following step */
 273     CS_GenRegInfo (S);
 274
 275     /* Walk over the entries */
 276     I = 0;
 277     while (I < CS_GetEntryCount (S)) {
 278
 279         /* Get next entry */
 280         CodeEntry* E = CS_GetEntry (S, I);
 281
 282         /* Get the input registers */
 283         const RegContents* In = &E->RI->In;
 284
 285         /* Assume we have no replacement */
 286         CodeEntry* X = 0;
 287
 288         /* Check the instruction */
 289         switch (E->OPC) {
 290
 291             case OP65_LDA:
 292                 if (CE_IsConstImm (E)) {
 293                     short Val = (short) E->Num;
 294                     if (Val == In->RegX) {
 295                         X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, E->LI);
 296                     } else if (Val == In->RegY) {
 297                         X = NewCodeEntry (OP65_TYA, AM65_IMP, 0, 0, E->LI);
 298                     } else if (RegValIsKnown (In->RegA) && (CPUIsets[CPU] & CPU_ISET_65SC02) != 0) {
 299                         if (Val == ((In->RegA - 1) & 0xFF)) {
 300                             X = NewCodeEntry (OP65_DEA, AM65_IMP, 0, 0, E->LI);
 301                         } else if (Val == ((In->RegA + 1) & 0xFF)) {
 302                             X = NewCodeEntry (OP65_INA, AM65_IMP, 0, 0, E->LI);
 303                         }
 304                     }
 305                 }
 306                 break;
 307
 308             case OP65_LDX:
 309                 if (CE_IsConstImm (E)) {
 310                     short Val = (short) E->Num;
 311                     if (RegValIsKnown (In->RegX) && Val == ((In->RegX - 1) & 0xFF)) {
 312                         X = NewCodeEntry (OP65_DEX, AM65_IMP, 0, 0, E->LI);
 313                     } else if (RegValIsKnown (In->RegX) && Val == ((In->RegX + 1) & 0xFF)) {
 314                         X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, E->LI);
 315                     } else if (Val == In->RegA) {
 316                         X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, E->LI);
 317                     }
 318                 }
 319                 break;
 320
 321             case OP65_LDY:
 322                 if (CE_IsConstImm (E)) {
 323                     short Val = (short) E->Num;
 324                     if (RegValIsKnown (In->RegY) && Val == ((In->RegY - 1) & 0xFF)) {
 325                         X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, E->LI);
 326                     } else if (RegValIsKnown (In->RegY) && Val == ((In->RegY + 1) & 0xFF)) {
 327                         X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, E->LI);
 328                     } else if (Val == In->RegA) {
 329                         X = NewCodeEntry (OP65_TAY, AM65_IMP, 0, 0, E->LI);
 330                     }
 331                 }
 332                 break;
 333
 334             default:
 335                 /* Avoid gcc warnings */
 336                 break;
 337
 338         }
 339
 340         /* Insert the replacement if we have one */
 341         if (X) {
 342             CS_InsertEntry (S, X, I+1);
 343             CS_DelEntry (S, I);
 344             ++Changes;
 345         }
 346
 347         /* Next entry */
 348         ++I;
 349
 350     }
 351
 352     /* Free register info */
 353     CS_FreeRegInfo (S);
 354
 355     /* Return the number of changes made */
 356     return Changes;
 357 }
 358
 359
 360