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 = GetCodeEntry (S, 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 == GetCodeEntry (S, I+1)) {
  89
  90             /* Delete the dead jump */
  91             DelCodeEntry (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 = GetCodeEntry (S, I);
 135
 136         /* Check if it's an unconditional branch, and if the next entry has
 137          * no labels attached
 138          */
 139         if ((E->Info & OF_DEAD) != 0 && !CodeEntryHasLabel (GetCodeEntry (S, I+1))) {
 140
 141             /* Delete the next entry */
 142             DelCodeEntry (S, I+1);
 143
 144             /* Keep the number of entries updated */
 145             --Count;
 146
 147             /* Remember, we had changes */
 148             ++OptChanges;
 149
 150         } else {
 151
 152             /* Next entry */
 153             ++I;
 154
 155         }
 156     }
 157 }
 158
 159
 160
 161 /*****************************************************************************/
 162 /*                          Optimize jump cascades                           */
 163 /*****************************************************************************/
 164
 165
 166
 167 static void OptJumpCascades (CodeSeg* S)
 168 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 169  * replaced by a jump to the final location. This will in some cases produce
 170  * worse code, because some jump targets are no longer reachable by short
 171  * branches, but this is quite rare, so there are more advantages than
 172  * disadvantages.
 173  */
 174 {
 175     unsigned I;
 176
 177     /* Get the number of entries, bail out if we have no entries */
 178     unsigned Count = CollCount (&S->Entries);
 179     if (Count == 0) {
 180         return;
 181     }
 182
 183     /* Walk over all entries */
 184     I = 0;
 185     while (I < Count) {
 186
 187         CodeLabel* OldLabel;
 188         CodeLabel* NewLabel;
 189
 190         /* Get this entry */
 191         CodeEntry* E = GetCodeEntry (S, I);
 192
 193         /* Check if it's a branch, if it has a label attached, and if the
 194          * instruction at this label is also a branch, and (important) if
 195          * both instructions are not identical.
 196          */
 197         if (E->AM == AM_BRA                             &&      /* It's a branch */
 198             (OldLabel = E->JumpTo) != 0                 &&      /* Label attached */
 199             OldLabel->Owner->AM == AM_BRA               &&      /* Jumps to a branch.. */
 200             (NewLabel = OldLabel->Owner->JumpTo) != 0   &&      /* ..which has a label */
 201             OldLabel->Owner != E) {                             /* And both are distinct */
 202
 203             /* Get the instruction that has the new label attached */
 204             CodeEntry* N = OldLabel->Owner;
 205
 206             /* Remove the reference to our label and delete it if this was
 207              * the last reference.
 208              */
 209             if (RemoveLabelRef (OldLabel, E) == 0) {
 210                 /* Delete it */
 211                 DelCodeLabel (S, OldLabel);
 212             }
 213
 214             /* Use the usage information from the new instruction */
 215             E->Use = N->Use;
 216             E->Chg = N->Chg;
 217
 218             /* Use the new label */
 219             AddLabelRef (NewLabel, E);
 220
 221             /* Remember ,we had changes */
 222             ++OptChanges;
 223
 224         }
 225
 226         /* Next entry */
 227         ++I;
 228
 229     }
 230 }
 231
 232
 233
 234 /*****************************************************************************/
 235 /*                             Optimize jsr/rts                              */
 236 /*****************************************************************************/
 237
 238
 239
 240 static void OptRTS (CodeSeg* S)
 241 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 242  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 243  * label, the dead code elimination should take care of it.
 244  */
 245 {
 246     unsigned I;
 247
 248     /* Get the number of entries, bail out if we have less than 2 entries */
 249     unsigned Count = CollCount (&S->Entries);
 250     if (Count < 2) {
 251         return;
 252     }
 253
 254     /* Walk over all entries minus the last one */
 255     I = 0;
 256     while (I < Count-1) {
 257
 258         /* Get this entry */
 259         CodeEntry* E = GetCodeEntry (S, I);
 260
 261         /* Check if it's a subroutine call and if the following insn is RTS */
 262         if (E->OPC == OPC_JSR && GetCodeEntry(S,I+1)->OPC == OPC_RTS) {
 263
 264             /* Change the jsr to a jmp */
 265             E->OPC = OPC_JMP;
 266
 267             /* Change the opcode info to that of the jump */
 268             E->Info = GetOPCInfo (OPC_JMP);
 269
 270             /* Remember, we had changes */
 271             ++OptChanges;
 272
 273         }
 274
 275         /* Next entry */
 276         ++I;
 277
 278     }
 279 }
 280
 281
 282
 283 /*****************************************************************************/
 284 /*                           Optimize jump targets                           */
 285 /*****************************************************************************/
 286
 287
 288
 289 static void OptJumpTarget (CodeSeg* S)
 290 /* If the instruction preceeding an unconditional branch is the same as the
 291  * instruction preceeding the jump target, the jump target may be moved
 292  * one entry back. This is a size optimization, since the instruction before
 293  * the branch gets removed.
 294  */
 295 {
 296     unsigned I;
 297
 298     /* Get the number of entries, bail out if we have not enough */
 299     unsigned Count = CollCount (&S->Entries);
 300     if (Count < 3) {
 301         return;
 302     }
 303
 304     /* Walk over all entries minus the first one */
 305     I = 1;
 306     while (I < Count) {
 307
 308         /* Get this entry and the entry before this one */
 309         CodeEntry* E = GetCodeEntry (S, I);
 310
 311         /* Check if we have a jump or branch, and a matching label */
 312         if ((E->Info & OF_UBRA) != 0 && E->JumpTo) {
 313
 314             /* Remember, we had changes */
 315             ++OptChanges;
 316
 317         }
 318
 319         /* Next entry */
 320         ++I;
 321
 322     }
 323 }
 324
 325
 326
 327 /*****************************************************************************/
 328 /*                                   Code                                    */
 329 /*****************************************************************************/
 330
 331
 332
 333 void RunOpt (CodeSeg* S)
 334 /* Run the optimizer */
 335 {
 336     typedef void (*OptFunc) (CodeSeg*);
 337
 338     /* Table with optimizer steps -  are called in this order */
 339     static const OptFunc OptFuncs [] = {
 340         OptJumpCascades,        /* Optimize jump cascades */
 341         OptDeadJumps,           /* Remove dead jumps */
 342         OptDeadCode,            /* Remove dead code */
 343         OptRTS,                 /* Change jsr/rts to jmp */
 344     };
 345
 346     /* Repeat all steps until there are no more changes */
 347     do {
 348
 349         unsigned long Flags;
 350         unsigned      I;
 351
 352         /* Reset the number of changes */
 353         OptChanges = 0;
 354
 355         /* Run all optimization steps */
 356         Flags = 1UL;
 357         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 358             if ((OptDisable & Flags) == 0) {
 359                 OptFuncs[I] (S);
 360             } else if (Verbosity > 0 || Debug) {
 361                 printf ("Optimizer pass %u skipped\n", I);
 362             }
 363             Flags <<= 1;
 364         }
 365
 366     } while (OptChanges > 0);
 367 }
 368
 369
 370