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