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