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 "asmlabel.h"
  41 #include "codeent.h"
  42 #include "codeinfo.h"
  43 #include "global.h"
  44 #include "codeopt.h"
  45
  46
  47
  48 /*****************************************************************************/
  49 /*                                   Data                                    */
  50 /*****************************************************************************/
  51
  52
  53
  54 /* Counter for the number of changes in one run. The optimizer process is
  55  * repeated until there are no more changes.
  56  */
  57 static unsigned OptChanges;
  58
  59
  60
  61 /*****************************************************************************/
  62 /*                             Remove dead jumps                             */
  63 /*****************************************************************************/
  64
  65
  66
  67 static void OptDeadJumps (CodeSeg* S)
  68 /* Remove dead jumps (jumps to the next instruction) */
  69 {
  70     CodeEntry* E;
  71     unsigned I;
  72
  73     /* Get the number of entries, bail out if we have less than two entries */
  74     unsigned Count = GetCodeEntryCount (S);
  75     if (Count < 2) {
  76         return;
  77     }
  78
  79     /* Walk over all entries minus the last one */
  80     I = 0;
  81     while (I < Count-1) {
  82
  83         /* Get the next entry */
  84         E = GetCodeEntry (S, I);
  85
  86         /* Check if it's a branch, if it has a local target, and if the target
  87          * is the next instruction.
  88          */
  89         if (E->AM == AM_BRA && E->JumpTo && E->JumpTo->Owner == GetCodeEntry (S, I+1)) {
  90
  91             /* Delete the dead jump */
  92             DelCodeEntry (S, I);
  93
  94             /* Keep the number of entries updated */
  95             --Count;
  96
  97             /* Remember, we had changes */
  98             ++OptChanges;
  99
 100         } else {
 101
 102             /* Next entry */
 103             ++I;
 104
 105         }
 106     }
 107 }
 108
 109
 110
 111 /*****************************************************************************/
 112 /*                             Remove dead code                              */
 113 /*****************************************************************************/
 114
 115
 116
 117 static void OptDeadCode (CodeSeg* S)
 118 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 119  * and has no label)
 120  */
 121 {
 122     unsigned I;
 123
 124     /* Get the number of entries, bail out if we have less than two entries */
 125     unsigned Count = GetCodeEntryCount (S);
 126     if (Count < 2) {
 127         return;
 128     }
 129
 130     /* Walk over all entries minus the last one */
 131     I = 0;
 132     while (I < Count-1) {
 133
 134         /* Get this entry */
 135         CodeEntry* E = GetCodeEntry (S, I);
 136
 137         /* Check if it's an unconditional branch, and if the next entry has
 138          * no labels attached
 139          */
 140         if ((E->Info & OF_DEAD) != 0 && !CodeEntryHasLabel (GetCodeEntry (S, I+1))) {
 141
 142             /* Delete the next entry */
 143             DelCodeEntry (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 = GetCodeEntryCount (S);
 180     if (Count == 0) {
 181         return;
 182     }
 183
 184     /* Walk over all entries */
 185     I = 0;
 186     while (I < Count) {
 187
 188         /* Get this entry */
 189         CodeEntry* E = GetCodeEntry (S, I);
 190
 191         /* Check if it's a branch, if it has a jump label, and if this jump
 192          * label is not attached to the instruction itself.
 193          */
 194         if ((E->Info & OF_BRA) != 0 && E->JumpTo != 0 && E->JumpTo->Owner != E) {
 195
 196             /* Get the label this insn is branching to */
 197             CodeLabel* OldLabel = E->JumpTo;
 198
 199             /* Get the entry we're branching to */
 200             CodeEntry* N = OldLabel->Owner;
 201
 202             /* If the entry we're branching to is not itself a branch, it is
 203              * not what we're searching for.
 204              */
 205             if ((N->Info & OF_BRA) == 0) {
 206                 goto NextEntry;
 207             }
 208
 209             /* Check if we can use the final target label. This is the case,
 210              * if the target branch is an absolut branch, or if it is a
 211              * conditional branch checking the same condition as the first one.
 212              */
 213             if ((N->Info & OF_UBRA) != 0 ||
 214                 ((E->Info & OF_CBRA) != 0 &&
 215                  GetBranchCond (E->OPC)  == GetBranchCond (N->OPC))) {
 216
 217                 /* This is a jump cascade and we may jump to the final target.
 218                  * If we have a label, move the reference to this label. If
 219                  * we don't have a label, use the argument instead.
 220                  */
 221                 if (N->JumpTo) {
 222                     /* Move the reference to the new insn */
 223                     MoveCodeLabelRef (S, E, N->JumpTo);
 224                 } else {
 225                     /* Remove the reference to the old label */
 226                     RemoveCodeLabelRef (S, E);
 227                 }
 228
 229                 /* Use the new argument */
 230                 CodeEntrySetArg (E, N->Arg);
 231
 232                 /* Use the usage information from the new instruction */
 233                 E->Use = N->Use;
 234                 E->Chg = N->Chg;
 235
 236                 /* Remember, we had changes */
 237                 ++OptChanges;
 238
 239                 /* Done */
 240                 goto NextEntry;
 241
 242             }
 243
 244             /* Check if both are conditional branches, and the condition of
 245              * the second is the inverse of that of the first. In this case,
 246              * the second branch will never be taken, and we may jump directly
 247              * to the instruction behind this one.
 248              */
 249             goto NextEntry;
 250
 251         }
 252
 253 NextEntry:
 254         /* Next entry */
 255         ++I;
 256
 257     }
 258 }
 259
 260
 261
 262 /*****************************************************************************/
 263 /*                             Optimize jsr/rts                              */
 264 /*****************************************************************************/
 265
 266
 267
 268 static void OptRTS (CodeSeg* S)
 269 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 270  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 271  * label, the dead code elimination should take care of it.
 272  */
 273 {
 274     unsigned I;
 275
 276     /* Get the number of entries, bail out if we have less than 2 entries */
 277     unsigned Count = GetCodeEntryCount (S);
 278     if (Count < 2) {
 279         return;
 280     }
 281
 282     /* Walk over all entries minus the last one */
 283     I = 0;
 284     while (I < Count-1) {
 285
 286         /* Get this entry */
 287         CodeEntry* E = GetCodeEntry (S, I);
 288
 289         /* Check if it's a subroutine call and if the following insn is RTS */
 290         if (E->OPC == OPC_JSR && GetCodeEntry(S,I+1)->OPC == OPC_RTS) {
 291
 292             /* Change the jsr to a jmp and use the additional info for a jump */
 293             E->OPC  = OPC_JMP;
 294             E->AM   = AM_BRA;
 295             E->Info = GetOPCInfo (OPC_JMP);
 296
 297             /* Remember, we had changes */
 298             ++OptChanges;
 299
 300         }
 301
 302         /* Next entry */
 303         ++I;
 304
 305     }
 306 }
 307
 308
 309
 310 /*****************************************************************************/
 311 /*                           Optimize jump targets                           */
 312 /*****************************************************************************/
 313
 314
 315
 316 static void OptJumpTarget (CodeSeg* S)
 317 /* If the instruction preceeding an unconditional branch is the same as the
 318  * instruction preceeding the jump target, the jump target may be moved
 319  * one entry back. This is a size optimization, since the instruction before
 320  * the branch gets removed.
 321  */
 322 {
 323     CodeEntry* E1;      /* Entry 1 */
 324     CodeEntry* E2;      /* Entry 2 */
 325     CodeEntry* T1;      /* Jump target entry 1 */
 326     CodeEntry* T2;      /* Jump target entry 2 */
 327     CodeLabel* TL1;     /* Target label 1 */
 328     unsigned TI;        /* Target index */
 329     unsigned I;
 330
 331     /* Get the number of entries, bail out if we have not enough */
 332     unsigned Count = GetCodeEntryCount (S);
 333     if (Count < 3) {
 334         return;
 335     }
 336
 337     /* Walk over the entries */
 338     I = 0;
 339     while (I < Count-1) {
 340
 341         /* Get next entry */
 342         E2 = GetCodeEntry (S, I+1);
 343
 344         /* Check if we have a jump or branch, and a matching label */
 345         if ((E2->Info & OF_UBRA) != 0 && E2->JumpTo) {
 346
 347             /* Get the target instruction for the label */
 348             T2 = E2->JumpTo->Owner;
 349
 350             /* Get the entry preceeding this one (if possible) */
 351             TI = GetCodeEntryIndex (S, T2);
 352             if (TI == 0) {
 353                 /* There is no entry before this one */
 354                 goto NextEntry;
 355             }
 356             T1 = GetCodeEntry (S, TI-1);
 357
 358             /* Get the entry preceeding the jump */
 359             E1 = GetCodeEntry (S, I);
 360
 361             /* Check if both preceeding instructions are identical */
 362             if (!CodeEntriesAreEqual (E1, T1)) {
 363                 /* Not equal, try next */
 364                 goto NextEntry;
 365             }
 366
 367             /* Get the label for the instruction preceeding the jump target.
 368              * This routine will create a new label if the instruction does
 369              * not already have one.
 370              */
 371             TL1 = GenCodeLabel (S, T1);
 372
 373             /* Change the jump target to point to this new label */
 374             MoveCodeLabelRef (S, E2, TL1);
 375
 376             /* If the instruction preceeding the jump has labels attached,
 377              * move references to this label to the new label.
 378              */
 379             if (CodeEntryHasLabel (E1)) {
 380                 MoveCodeLabels (S, E1, T1);
 381             }
 382
 383             /* Remove the entry preceeding the jump */
 384             DelCodeEntry (S, I);
 385             --Count;
 386
 387             /* Remember, we had changes */
 388             ++OptChanges;
 389
 390         }
 391
 392 NextEntry:
 393         /* Next entry */
 394         ++I;
 395
 396     }
 397 }
 398
 399
 400
 401 /*****************************************************************************/
 402 /*                                   Code                                    */
 403 /*****************************************************************************/
 404
 405
 406
 407 void RunOpt (CodeSeg* S)
 408 /* Run the optimizer */
 409 {
 410     typedef void (*OptFunc) (CodeSeg*);
 411
 412     /* Table with optimizer steps -  are called in this order */
 413     static const OptFunc OptFuncs [] = {
 414         OptJumpCascades,        /* Optimize jump cascades */
 415         OptDeadJumps,           /* Remove dead jumps */
 416         OptDeadCode,            /* Remove dead code */
 417         OptRTS,                 /* Change jsr/rts to jmp */
 418         OptJumpTarget,          /* Optimize jump targets */
 419     };
 420
 421     /* Repeat all steps until there are no more changes */
 422     do {
 423
 424         unsigned long Flags;
 425         unsigned      I;
 426
 427         /* Reset the number of changes */
 428         OptChanges = 0;
 429
 430         /* Run all optimization steps */
 431         Flags = 1UL;
 432         for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
 433             if ((OptDisable & Flags) == 0) {
 434                 OptFuncs[I] (S);
 435             } else if (Verbosity > 0 || Debug) {
 436                 printf ("Optimizer pass %u skipped\n", I);
 437             }
 438             Flags <<= 1;
 439         }
 440
 441     } while (OptChanges > 0);
 442 }
 443
 444
 445