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

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 coptind.c                                 */
   4 /*                                                                           */
   5 /*              Environment independent low level optimizations              */
   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 /* cc65 */
  39 #include "codeent.h"
  40 #include "codeinfo.h"
  41 #include "codeopt.h"
  42 #include "error.h"
  43 #include "coptind.h"
  44
  45
  46
  47 /*****************************************************************************/
  48 /*                             Remove dead jumps                             */
  49 /*****************************************************************************/
  50
  51
  52
  53 unsigned OptDeadJumps (CodeSeg* S)
  54 /* Remove dead jumps (jumps to the next instruction) */
  55 {
  56     unsigned Changes = 0;
  57     CodeEntry* E;
  58     unsigned I;
  59
  60     /* Get the number of entries, bail out if we have less than two entries */
  61     unsigned Count = GetCodeEntryCount (S);
  62     if (Count < 2) {
  63         return 0;
  64     }
  65
  66     /* Walk over all entries minus the last one */
  67     I = 0;
  68     while (I < Count-1) {
  69
  70         /* Get the next entry */
  71         E = GetCodeEntry (S, I);
  72
  73         /* Check if it's a branch, if it has a local target, and if the target
  74          * is the next instruction.
  75          */
  76         if (E->AM == AM_BRA && E->JumpTo && E->JumpTo->Owner == GetCodeEntry (S, I+1)) {
  77
  78             /* Delete the dead jump */
  79             DelCodeEntry (S, I);
  80
  81             /* Keep the number of entries updated */
  82             --Count;
  83
  84             /* Remember, we had changes */
  85             ++Changes;
  86
  87         } else {
  88
  89             /* Next entry */
  90             ++I;
  91
  92         }
  93     }
  94
  95     /* Return the number of changes made */
  96     return Changes;
  97 }
  98
  99
 100
 101 /*****************************************************************************/
 102 /*                             Remove dead code                              */
 103 /*****************************************************************************/
 104
 105
 106
 107 unsigned OptDeadCode (CodeSeg* S)
 108 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 109  * and has no label)
 110  */
 111 {
 112     unsigned Changes = 0;
 113     unsigned I;
 114
 115     /* Get the number of entries, bail out if we have less than two entries */
 116     unsigned Count = GetCodeEntryCount (S);
 117     if (Count < 2) {
 118         return 0;
 119     }
 120
 121     /* Walk over all entries minus the last one */
 122     I = 0;
 123     while (I < Count-1) {
 124
 125         /* Get this entry */
 126         CodeEntry* E = GetCodeEntry (S, I);
 127
 128         /* Check if it's an unconditional branch, and if the next entry has
 129          * no labels attached
 130          */
 131         if ((E->Info & OF_DEAD) != 0 && !CodeEntryHasLabel (GetCodeEntry (S, I+1))) {
 132
 133             /* Delete the next entry */
 134             DelCodeEntry (S, I+1);
 135
 136             /* Keep the number of entries updated */
 137             --Count;
 138
 139             /* Remember, we had changes */
 140             ++Changes;
 141
 142         } else {
 143
 144             /* Next entry */
 145             ++I;
 146
 147         }
 148     }
 149
 150     /* Return the number of changes made */
 151     return Changes;
 152 }
 153
 154
 155
 156 /*****************************************************************************/
 157 /*                          Optimize jump cascades                           */
 158 /*****************************************************************************/
 159
 160
 161
 162 unsigned OptJumpCascades (CodeSeg* S)
 163 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 164  * replaced by a jump to the final location. This will in some cases produce
 165  * worse code, because some jump targets are no longer reachable by short
 166  * branches, but this is quite rare, so there are more advantages than
 167  * disadvantages.
 168  */
 169 {
 170     unsigned Changes = 0;
 171     unsigned I;
 172
 173     /* Get the number of entries, bail out if we have no entries */
 174     unsigned Count = GetCodeEntryCount (S);
 175     if (Count == 0) {
 176         return 0;
 177     }
 178
 179     /* Walk over all entries */
 180     I = 0;
 181     while (I < Count) {
 182
 183         /* Get this entry */
 184         CodeEntry* E = GetCodeEntry (S, I);
 185
 186         /* Check if it's a branch, if it has a jump label, and if this jump
 187          * label is not attached to the instruction itself.
 188          */
 189         if ((E->Info & OF_BRA) != 0 && E->JumpTo != 0 && E->JumpTo->Owner != E) {
 190
 191             /* Get the label this insn is branching to */
 192             CodeLabel* OldLabel = E->JumpTo;
 193
 194             /* Get the entry we're branching to */
 195             CodeEntry* N = OldLabel->Owner;
 196
 197             /* If the entry we're branching to is not itself a branch, it is
 198              * not what we're searching for.
 199              */
 200             if ((N->Info & OF_BRA) == 0) {
 201                 goto NextEntry;
 202             }
 203
 204             /* Check if we can use the final target label. This is the case,
 205              * if the target branch is an absolut branch, or if it is a
 206              * conditional branch checking the same condition as the first one.
 207              */
 208             if ((N->Info & OF_UBRA) != 0 ||
 209                 ((E->Info & OF_CBRA) != 0 &&
 210                  GetBranchCond (E->OPC)  == GetBranchCond (N->OPC))) {
 211
 212                 /* This is a jump cascade and we may jump to the final target.
 213                  * If we have a label, move the reference to this label. If
 214                  * we don't have a label, use the argument instead.
 215                  */
 216                 if (N->JumpTo) {
 217                     /* Move the reference to the new insn */
 218                     MoveCodeLabelRef (S, E, N->JumpTo);
 219                 } else {
 220                     /* Remove the reference to the old label */
 221                     RemoveCodeLabelRef (S, E);
 222                 }
 223
 224                 /* Use the new argument */
 225                 CodeEntrySetArg (E, N->Arg);
 226
 227                 /* Use the usage information from the new instruction */
 228                 E->Use = N->Use;
 229                 E->Chg = N->Chg;
 230
 231                 /* Remember, we had changes */
 232                 ++Changes;
 233
 234                 /* Done */
 235                 continue;
 236
 237             }
 238
 239             /* Check if both are conditional branches, and the condition of
 240              * the second is the inverse of that of the first. In this case,
 241              * the second branch will never be taken, and we may jump directly
 242              * to the instruction behind this one.
 243              */
 244             goto NextEntry;
 245
 246         }
 247
 248 NextEntry:
 249         /* Next entry */
 250         ++I;
 251
 252     }
 253
 254     /* Return the number of changes made */
 255     return Changes;
 256 }
 257
 258
 259
 260 /*****************************************************************************/
 261 /*                             Optimize jsr/rts                              */
 262 /*****************************************************************************/
 263
 264
 265
 266 unsigned OptRTS (CodeSeg* S)
 267 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 268  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 269  * label, the dead code elimination should take care of it.
 270  */
 271 {
 272     unsigned Changes = 0;
 273     unsigned I;
 274
 275     /* Get the number of entries, bail out if we have less than 2 entries */
 276     unsigned Count = GetCodeEntryCount (S);
 277     if (Count < 2) {
 278         return 0;
 279     }
 280
 281     /* Walk over all entries minus the last one */
 282     I = 0;
 283     while (I < Count-1) {
 284
 285         /* Get this entry */
 286         CodeEntry* E = GetCodeEntry (S, I);
 287
 288         /* Check if it's a subroutine call and if the following insn is RTS */
 289         if (E->OPC == OPC_JSR && GetCodeEntry(S,I+1)->OPC == OPC_RTS) {
 290
 291             /* Change the jsr to a jmp and use the additional info for a jump */
 292             E->OPC  = OPC_JMP;
 293             E->AM   = AM_BRA;
 294             E->Info = GetOPCInfo (OPC_JMP);
 295
 296             /* Remember, we had changes */
 297             ++Changes;
 298
 299         }
 300
 301         /* Next entry */
 302         ++I;
 303
 304     }
 305
 306     /* Return the number of changes made */
 307     return Changes;
 308 }
 309
 310
 311
 312 /*****************************************************************************/
 313 /*                           Optimize jump targets                           */
 314 /*****************************************************************************/
 315
 316
 317
 318 unsigned OptJumpTarget (CodeSeg* S)
 319 /* If the instruction preceeding an unconditional branch is the same as the
 320  * instruction preceeding the jump target, the jump target may be moved
 321  * one entry back. This is a size optimization, since the instruction before
 322  * the branch gets removed.
 323  */
 324 {
 325     unsigned Changes = 0;
 326     CodeEntry* E1;              /* Entry 1 */
 327     CodeEntry* E2;              /* Entry 2 */
 328     CodeEntry* T1;              /* Jump target entry 1 */
 329     CodeEntry* T2;              /* Jump target entry 2 */
 330     CodeLabel* TL1;             /* Target label 1 */
 331     unsigned TI;                /* Target index */
 332     unsigned I;
 333
 334     /* Get the number of entries, bail out if we have not enough */
 335     unsigned Count = GetCodeEntryCount (S);
 336     if (Count < 3) {
 337         return 0;
 338     }
 339
 340     /* Walk over the entries */
 341     I = 0;
 342     while (I < Count-1) {
 343
 344         /* Get next entry */
 345         E2 = GetCodeEntry (S, I+1);
 346
 347         /* Check if we have a jump or branch, and a matching label */
 348         if ((E2->Info & OF_UBRA) != 0 && E2->JumpTo) {
 349
 350             /* Get the target instruction for the label */
 351             T2 = E2->JumpTo->Owner;
 352
 353             /* Get the entry preceeding this one (if possible) */
 354             TI = GetCodeEntryIndex (S, T2);
 355             if (TI == 0) {
 356                 /* There is no entry before this one */
 357                 goto NextEntry;
 358             }
 359             T1 = GetCodeEntry (S, TI-1);
 360
 361             /* Get the entry preceeding the jump */
 362             E1 = GetCodeEntry (S, I);
 363
 364             /* Check if both preceeding instructions are identical */
 365             if (!CodeEntriesAreEqual (E1, T1)) {
 366                 /* Not equal, try next */
 367                 goto NextEntry;
 368             }
 369
 370             /* Get the label for the instruction preceeding the jump target.
 371              * This routine will create a new label if the instruction does
 372              * not already have one.
 373              */
 374             TL1 = GenCodeLabel (S, T1);
 375
 376             /* Change the jump target to point to this new label */
 377             MoveCodeLabelRef (S, E2, TL1);
 378
 379             /* If the instruction preceeding the jump has labels attached,
 380              * move references to this label to the new label.
 381              */
 382             if (CodeEntryHasLabel (E1)) {
 383                 MoveCodeLabels (S, E1, T1);
 384             }
 385
 386             /* Remove the entry preceeding the jump */
 387             DelCodeEntry (S, I);
 388             --Count;
 389
 390             /* Remember, we had changes */
 391             ++Changes;
 392
 393         }
 394
 395 NextEntry:
 396         /* Next entry */
 397         ++I;
 398
 399     }
 400
 401     /* Return the number of changes made */
 402     return Changes;
 403 }
 404
 405
 406
 407 /*****************************************************************************/
 408 /*                   Remove conditional jumps never taken                    */
 409 /*****************************************************************************/
 410
 411
 412
 413 unsigned OptDeadCondBranches (CodeSeg* S)
 414 /* If an immidiate load of a register is followed by a conditional jump that
 415  * is never taken because the load of the register sets the flags in such a
 416  * manner, remove the conditional branch.
 417  */
 418 {
 419     unsigned Changes = 0;
 420     unsigned I;
 421
 422     /* Get the number of entries, bail out if we have not enough */
 423     unsigned Count = GetCodeEntryCount (S);
 424     if (Count < 2) {
 425         return 0;
 426     }
 427
 428     /* Walk over the entries */
 429     I = 0;
 430     while (I < Count-1) {
 431
 432         /* Get next entry */
 433         CodeEntry* E = GetCodeEntry (S, I);
 434
 435         /* Check if it's a register load */
 436         if ((E->Info & OF_LOAD) != 0 && E->AM == AM_IMM && (E->Flags & CEF_NUMARG) != 0) {
 437
 438             bc_t BC;
 439
 440             /* Immidiate register load, get next instruction */
 441             CodeEntry* N = GetCodeEntry (S, I+1);
 442
 443             /* Check if the following insn is a conditional branch or if it
 444              * has a label attached.
 445              */
 446             if ((N->Info & OF_CBRA) == 0 || CodeEntryHasLabel (E)) {
 447                 /* No conditional jump or label attached, bail out */
 448                 goto NextEntry;
 449             }
 450
 451             /* Get the branch condition */
 452             BC = GetBranchCond (N->OPC);
 453
 454             /* Check the argument against the branch condition */
 455             if ((BC == BC_EQ && E->Num != 0)            ||
 456                 (BC == BC_NE && E->Num == 0)            ||
 457                 (BC == BC_PL && (E->Num & 0x80) != 0)   ||
 458                 (BC == BC_MI && (E->Num & 0x80) == 0)) {
 459
 460                 /* Remove the conditional branch */
 461                 DelCodeEntry (S, I+1);
 462                 --Count;
 463
 464                 /* Remember, we had changes */
 465                 ++Changes;
 466
 467             }
 468         }
 469
 470 NextEntry:
 471         /* Next entry */
 472         ++I;
 473
 474     }
 475
 476     /* Return the number of changes made */
 477     return Changes;
 478 }
 479
 480
 481