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

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 codeopt.c                                 */
   4 /*                                                                           */
   5 /*                           Optimizer subroutines                           */
   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 <string.h>
  37
  38 /* common */
  39 #include "abend.h"
  40 #include "print.h"
  41
  42 /* cc65 */
  43 #include "asmlabel.h"
  44 #include "codeent.h"
  45 #include "codeinfo.h"
  46 #include "coptind.h"
  47 #include "error.h"
  48 #include "global.h"
  49 #include "codeopt.h"
  50
  51
  52
  53 /*****************************************************************************/
  54 /*                                   Data                                    */
  55 /*****************************************************************************/
  56
  57
  58
  59 /* Defines for the conditions in a compare */
  60 typedef enum {
  61     CMP_INV = -1,
  62     CMP_EQ,
  63     CMP_NE,
  64     CMP_GT,
  65     CMP_GE,
  66     CMP_LT,
  67     CMP_LE,
  68     CMP_UGT,
  69     CMP_UGE,
  70     CMP_ULT,
  71     CMP_ULE
  72 } cmp_t;
  73
  74 /* Table with the compare suffixes */
  75 static const char CmpSuffixTab [][4] = {
  76     "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
  77 };
  78
  79 /* Table used to invert a condition, indexed by condition */
  80 static const unsigned char CmpInvertTab [] = {
  81     CMP_NE, CMP_EQ,
  82     CMP_LE, CMP_LT, CMP_GE, CMP_GT,
  83     CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
  84 };
  85
  86 /* Table to show which compares are signed (use the N flag) */
  87 static const char CmpSignedTab [] = {
  88     0, 0, 1, 1, 1, 1, 0, 0, 0, 0
  89 };
  90
  91
  92
  93 /*****************************************************************************/
  94 /*                             Helper functions                              */
  95 /*****************************************************************************/
  96
  97
  98
  99 static cmp_t FindCmpCond (const char* Suffix)
 100 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
 101 {
 102     int I;
 103
 104     /* Linear search */
 105     for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
 106         if (strcmp (Suffix, CmpSuffixTab [I]) == 0) {
 107             /* Found */
 108             return I;
 109         }
 110     }
 111
 112     /* Not found */
 113     return CMP_INV;
 114 }
 115
 116
 117
 118 /*****************************************************************************/
 119 /*             Remove calls to the bool transformer subroutines              */
 120 /*****************************************************************************/
 121
 122
 123
 124 static unsigned OptBoolTransforms (CodeSeg* S)
 125 /* Try to remove the call to boolean transformer routines where the call is
 126  * not really needed.
 127  */
 128 {
 129     unsigned Changes = 0;
 130     unsigned I;
 131
 132     /* Get the number of entries, bail out if we have not enough */
 133     unsigned Count = GetCodeEntryCount (S);
 134     if (Count < 2) {
 135         return 0;
 136     }
 137
 138     /* Walk over the entries */
 139     I = 0;
 140     while (I < Count-1) {
 141
 142         /* Get next entry */
 143         CodeEntry* E = GetCodeEntry (S, I);
 144
 145         /* Check for a boolean transformer */
 146         if (E->OPC == OPC_JSR && strncmp (E->Arg, "bool", 4) == 0) {
 147
 148             cmp_t Cond;
 149
 150             /* Get the next entry */
 151             CodeEntry* N = GetCodeEntry (S, I+1);
 152
 153             /* Check if this is a conditional branch */
 154             if ((N->Info & OF_CBRA) == 0) {
 155                 /* No conditional branch, bail out */
 156                 goto NextEntry;
 157             }
 158
 159             /* Make the boolean transformer unnecessary by changing the
 160              * the conditional jump to evaluate the condition flags that
 161              * are set after the compare directly. Note: jeq jumps if
 162              * the condition is not met, jne jumps if the condition is met.
 163              */
 164             Cond = FindCmpCond (E->Arg + 4);
 165             if (Cond == CMP_INV) {
 166                 /* Unknown function */
 167                 goto NextEntry;
 168             }
 169
 170             /* Invert the code if we jump on condition not met. */
 171             if (GetBranchCond (N->OPC) == BC_EQ) {
 172                 /* Jumps if condition false, invert condition */
 173                 Cond = CmpInvertTab [Cond];
 174             }
 175
 176             /* Check if we can replace the code by something better */
 177             switch (Cond) {
 178
 179                 case CMP_EQ:
 180                     ReplaceOPC (N, OPC_JEQ);
 181                     break;
 182
 183                 case CMP_NE:
 184                     ReplaceOPC (N, OPC_JNE);
 185                     break;
 186
 187                 case CMP_GT:
 188                     /* Not now ### */
 189                     goto NextEntry;
 190
 191                 case CMP_GE:
 192                     ReplaceOPC (N, OPC_JPL);
 193                     break;
 194
 195                 case CMP_LT:
 196                     ReplaceOPC (N, OPC_JMI);
 197                     break;
 198
 199                 case CMP_LE:
 200                     /* Not now ### */
 201                     goto NextEntry;
 202
 203                 case CMP_UGT:
 204                     /* Not now ### */
 205                     goto NextEntry;
 206
 207                 case CMP_UGE:
 208                     ReplaceOPC (N, OPC_JCS);
 209                     break;
 210
 211                 case CMP_ULT:
 212                     ReplaceOPC (N, OPC_JCC);
 213                     break;
 214
 215                 case CMP_ULE:
 216                     /* Not now ### */
 217                     goto NextEntry;
 218
 219                 default:
 220                     Internal ("Unknown jump condition: %d", Cond);
 221
 222             }
 223
 224             /* Remove the call to the bool transformer */
 225             DelCodeEntry (S, I);
 226             --Count;
 227
 228             /* Remember, we had changes */
 229             ++Changes;
 230
 231         }
 232
 233 NextEntry:
 234         /* Next entry */
 235         ++I;
 236
 237     }
 238
 239     /* Return the number of changes made */
 240     return Changes;
 241 }
 242
 243
 244
 245 /*****************************************************************************/
 246 /*                                   Code                                    */
 247 /*****************************************************************************/
 248
 249
 250
 251 /* Table with all the optimization functions */
 252 typedef struct OptFunc OptFunc;
 253 struct OptFunc {
 254     unsigned (*Func) (CodeSeg*);/* Optimizer function */
 255     const char* Name;           /* Name of optimizer step */
 256     char        Disabled;       /* True if pass disabled */
 257 };
 258
 259
 260
 261 /* Table with optimizer steps -  are called in this order */
 262 static OptFunc OptFuncs [] = {
 263     /* Optimize jump cascades */
 264     { OptJumpCascades,      "OptJumpCascades",          0       },
 265     /* Remove dead jumps */
 266     { OptDeadJumps,         "OptDeadJumps",             0       },
 267     /* Change jsr/rts to jmp */
 268     { OptRTS,               "OptRTS",                   0       },
 269     /* Remove dead code */
 270     { OptDeadCode,          "OptDeadCode",              0       },
 271     /* Optimize jump targets */
 272     { OptJumpTarget,        "OptJumpTarget",            0       },
 273     /* Optimize conditional branches */
 274     { OptCondBranches,      "OptCondBranches",          0       },
 275     /* Remove calls to the bool transformer subroutines */
 276     { OptBoolTransforms,    "OptBoolTransforms",        0       },
 277     /* Remove unused loads */
 278     { OptUnusedLoads,       "OptUnusedLoads",           0       },
 279     /* Optimize branch distance */
 280     { OptBranchDist,        "OptBranchDist",            0       },
 281 };
 282
 283
 284
 285 static OptFunc* FindOptStep (const char* Name)
 286 /* Find an optimizer step by name in the table and return a pointer. Print an
 287  * error and call AbEnd if not found.
 288  */
 289 {
 290     unsigned I;
 291
 292     /* Run all optimization steps */
 293     for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 294         if (strcmp (OptFuncs[I].Name, Name) == 0) {
 295             /* Found */
 296             return OptFuncs+I;
 297         }
 298     }
 299
 300     /* Not found */
 301     AbEnd ("Optimization step `%s' not found", Name);
 302     return 0;
 303 }
 304
 305
 306
 307 void DisableOpt (const char* Name)
 308 /* Disable the optimization with the given name */
 309 {
 310     OptFunc* F  = FindOptStep (Name);
 311     F->Disabled = 1;
 312 }
 313
 314
 315
 316 void EnableOpt (const char* Name)
 317 /* Enable the optimization with the given name */
 318 {
 319     OptFunc* F  = FindOptStep (Name);
 320     F->Disabled = 0;
 321 }
 322
 323
 324
 325 void RunOpt (CodeSeg* S)
 326 /* Run the optimizer */
 327 {
 328     unsigned I;
 329     unsigned Pass = 0;
 330     unsigned OptChanges;
 331
 332     /* If we shouldn't run the optimizer, bail out */
 333     if (!Optimize) {
 334         return;
 335     }
 336
 337     /* Print the name of the function we are working on */
 338     if (S->Func) {
 339         Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
 340     } else {
 341         Print (stdout, 1, "Running optimizer for global code segment\n");
 342     }
 343
 344     /* Repeat all steps until there are no more changes */
 345     do {
 346         /* Reset the number of changes */
 347         OptChanges = 0;
 348
 349         /* Keep the user hapy */
 350         Print (stdout, 1, "  Optimizer pass %u:\n", ++Pass);
 351
 352         /* Run all optimization steps */
 353         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 354
 355             /* Print the name of the following optimizer step */
 356             Print (stdout, 1, "    %s:%*s", OptFuncs[I].Name,
 357                    (int) (30-strlen(OptFuncs[I].Name)), "");
 358
 359             /* Check if the step is disabled */
 360             if (OptFuncs[I].Disabled) {
 361                 Print (stdout, 1, "Disabled\n");
 362             } else {
 363                 unsigned Changes = OptFuncs[I].Func (S);
 364                 OptChanges += Changes;
 365                 Print (stdout, 1, "%u Changes\n", Changes);
 366             }
 367         }
 368
 369     } while (OptChanges > 0);
 370 }
 371
 372
 373