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 /* common */
  37 #include "print.h"
  38
  39 /* cc65 */
  40 #include "codeent.h"
  41 #include "codeinfo.h"
  42 #include "global.h"
  43 #include "codeopt.h"
  44
  45
  46
  47 /*****************************************************************************/
  48 /*                                   Data                                    */
  49 /*****************************************************************************/
  50
  51
  52
  53 /* Counter for the number of changes in one run. The optimizer process is
  54  * repeated until there are no more changes.
  55  */
  56 static unsigned OptChanges;
  57
  58
  59
  60 /*****************************************************************************/
  61 /*                             Remove dead jumps                             */
  62 /*****************************************************************************/
  63
  64
  65
  66 static void OptDeadJumps (CodeSeg* S)
  67 /* Remove dead jumps (jumps to the next instruction) */
  68 {
  69     CodeEntry* E;
  70     unsigned I;
  71
  72     /* Get the number of entries, bail out if we have less than two entries */
  73     unsigned Count = CollCount (&S->Entries);
  74     if (Count < 2) {
  75         return;
  76     }
  77
  78     /* Walk over all entries minus the last one */
  79     I = 0;
  80     while (I < Count-1) {
  81
  82         /* Get the next entry */
  83         E = CollAt (&S->Entries, I);
  84
  85         /* Check if it's a branch, if it has a local target, and if the target
  86          * is the next instruction.
  87          */
  88         if (E->AM == AM_BRA && E->JumpTo && E->JumpTo->Owner == CollAt (&S->Entries, I+1)) {
  89
  90             /* Delete the dead jump */
  91             DelCodeSegLine (S, I);
  92
  93             /* Keep the number of entries updated */
  94             --Count;
  95
  96             /* Remember, we had changes */
  97             ++OptChanges;
  98
  99         } else {
 100
 101             /* Next entry */
 102             ++I;
 103
 104         }
 105     }
 106 }
 107
 108
 109
 110 /*****************************************************************************/
 111 /*                             Remove dead code                              */
 112 /*****************************************************************************/
 113
 114
 115
 116 static void OptDeadCode (CodeSeg* S)
 117 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 118  * and has no label)
 119  */
 120 {
 121     unsigned I;
 122
 123     /* Get the number of entries, bail out if we have less than two entries */
 124     unsigned Count = CollCount (&S->Entries);
 125     if (Count < 2) {
 126         return;
 127     }
 128
 129     /* Walk over all entries minus the last one */
 130     I = 0;
 131     while (I < Count-1) {
 132
 133         /* Get this entry */
 134         CodeEntry* E = CollAt (&S->Entries, I);
 135
 136         /* Check if it's an unconditional branch, and if the next entry has
 137          * no labels attached
 138          */
 139         if ((E->OPC == OPC_JMP || E->OPC == OPC_BRA || E->OPC == OPC_RTS || E->OPC == OPC_RTI) &&
 140             !CodeEntryHasLabel (CollAt (&S->Entries, I+1))) {
 141
 142             /* Delete the next entry */
 143             DelCodeSegLine (S, I+1);
 144
 145             /* Keep the number of entries updated */
 146             --Count;
 147
 148             /* Remember, we had changes */
 149             ++OptChanges;
 150
 151         } else {
 152
 153             /* Next entry */
 154             ++I;
 155
 156         }
 157     }
 158 }
 159
 160
 161
 162 /*****************************************************************************/
 163 /*                          Optimize jump cascades                           */
 164 /*****************************************************************************/
 165
 166
 167
 168 static void OptJumpCascades (CodeSeg* S)
 169 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 170  * replaced by a jump to the final location. This will in some cases produce
 171  * worse code, because some jump targets are no longer reachable by short
 172  * branches, but this is quite rare, so there are more advantages than
 173  * disadvantages.
 174  */
 175 {
 176     unsigned I;
 177
 178     /* Get the number of entries, bail out if we have no entries */
 179     unsigned Count = CollCount (&S->Entries);
 180     if (Count == 0) {
 181         return;
 182     }
 183
 184     /* Walk over all entries */
 185     I = 0;
 186     while (I < Count) {
 187
 188         CodeLabel* OldLabel;
 189         CodeLabel* NewLabel;
 190
 191         /* Get this entry */
 192         CodeEntry* E = CollAt (&S->Entries, I);
 193
 194         /* Check if it's a branch, if it has a label attached, and if the
 195          * instruction at this label is also a branch.
 196          */
 197         if (E->AM == AM_BRA                             &&
 198             (OldLabel = E->JumpTo) != 0                 &&
 199             OldLabel->Owner->AM == AM_BRA               &&
 200             (NewLabel = OldLabel->Owner->JumpTo) != 0) {
 201
 202             /* Get the instruction that has the new label attached */
 203             CodeEntry* N = OldLabel->Owner;
 204
 205             /* Remove the reference to our label and delete it if this was
 206              * the last reference.
 207              */
 208             if (RemoveLabelRef (OldLabel, E) == 0) {
 209                 /* Delete it */
 210                 DelCodeLabel (S, OldLabel);
 211             }
 212
 213             /* Remove usage information from the entry and use the usage
 214              * information from the new instruction instead.
 215              */
 216             E->Info &= ~(CI_MASK_USE | CI_MASK_CHG);
 217             E->Info |= N->Info & ~(CI_MASK_USE | CI_MASK_CHG);
 218
 219             /* Use the new label */
 220             AddLabelRef (NewLabel, E);
 221
 222             /* Remember ,we had changes */
 223             ++OptChanges;
 224
 225         }
 226
 227         /* Next entry */
 228         ++I;
 229
 230     }
 231 }
 232
 233
 234
 235 /*****************************************************************************/
 236 /*                                   Code                                    */
 237 /*****************************************************************************/
 238
 239
 240
 241 void RunOpt (CodeSeg* S)
 242 /* Run the optimizer */
 243 {
 244     typedef void (*OptFunc) (CodeSeg*);
 245
 246     /* Table with optimizer steps -  are called in this order */
 247     static const OptFunc OptFuncs [] = {
 248         OptJumpCascades,        /* Optimize jump cascades */
 249         OptDeadJumps,           /* Remove dead jumps */
 250         OptDeadCode,            /* Remove dead code */
 251     };
 252
 253     /* Repeat all steps until there are no more changes */
 254     do {
 255
 256         unsigned long Flags;
 257         unsigned      I;
 258
 259         /* Reset the number of changes */
 260         OptChanges = 0;
 261
 262         /* Run all optimization steps */
 263         Flags = 1UL;
 264         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 265             if ((OptDisable & Flags) == 0) {
 266                 OptFuncs[I] (S);
 267             } else if (Verbosity > 0 || Debug) {
 268                 printf ("Optimizer pass %u skipped\n", I);
 269             }
 270             Flags <<= 1;
 271         }
 272
 273     } while (OptChanges > 0);
 274 }
 275
 276
 277