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             if ((E->Info & OF_CBRA) != 0 && (N->Info & OF_CBRA) != 0) {
 245
 246                 unsigned NI;    /* Index of N */
 247                 CodeEntry* X;   /* Instruction behind N */
 248                 CodeLabel* LX;  /* Label attached to X */
 249
 250                 /* Get the branch conditions of both branches */
 251                 bc_t BC1 = GetBranchCond (E->OPC);
 252                 bc_t BC2 = GetBranchCond (N->OPC);
 253
 254                 /* Check the branch conditions */
 255                 if (BC1 != GetInverseCond (BC2)) {
 256                     /* Condition not met */
 257                     goto NextEntry;
 258                 }
 259
 260                 /* We may jump behind this conditional branch. This means that
 261                  * N may not be the last entry.
 262                  */
 263                 NI = GetCodeEntryIndex (S, N);
 264                 if (NI >= Count-1) {
 265                     /* N is last entry */
 266                     goto NextEntry;
 267                 }
 268
 269                 /* Get the pointer to the next instruction */
 270                 X = GetCodeEntry (S, NI+1);
 271
 272                 /* Get the label attached to X, create a new one if needed */
 273                 LX = GenCodeLabel (S, X);
 274
 275                 /* Move the reference from E to the new label */
 276                 MoveCodeLabelRef (S, E, LX);
 277
 278                 /* Remember, we had changes */
 279                 ++Changes;
 280
 281                 /* Done */
 282                 continue;
 283
 284             }
 285         }
 286
 287 NextEntry:
 288         /* Next entry */
 289         ++I;
 290
 291     }
 292
 293     /* Return the number of changes made */
 294     return Changes;
 295 }
 296
 297
 298
 299 /*****************************************************************************/
 300 /*                             Optimize jsr/rts                              */
 301 /*****************************************************************************/
 302
 303
 304
 305 unsigned OptRTS (CodeSeg* S)
 306 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 307  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 308  * label, the dead code elimination should take care of it.
 309  */
 310 {
 311     unsigned Changes = 0;
 312     unsigned I;
 313
 314     /* Get the number of entries, bail out if we have less than 2 entries */
 315     unsigned Count = GetCodeEntryCount (S);
 316     if (Count < 2) {
 317         return 0;
 318     }
 319
 320     /* Walk over all entries minus the last one */
 321     I = 0;
 322     while (I < Count-1) {
 323
 324         /* Get this entry */
 325         CodeEntry* E = GetCodeEntry (S, I);
 326
 327         /* Check if it's a subroutine call and if the following insn is RTS */
 328         if (E->OPC == OPC_JSR && GetCodeEntry(S,I+1)->OPC == OPC_RTS) {
 329
 330             /* Change the jsr to a jmp and use the additional info for a jump */
 331             E->OPC  = OPC_JMP;
 332             E->AM   = AM_BRA;
 333             E->Info = GetOPCInfo (OPC_JMP);
 334
 335             /* Remember, we had changes */
 336             ++Changes;
 337
 338         }
 339
 340         /* Next entry */
 341         ++I;
 342
 343     }
 344
 345     /* Return the number of changes made */
 346     return Changes;
 347 }
 348
 349
 350
 351 /*****************************************************************************/
 352 /*                           Optimize jump targets                           */
 353 /*****************************************************************************/
 354
 355
 356
 357 unsigned OptJumpTarget (CodeSeg* S)
 358 /* If the instruction preceeding an unconditional branch is the same as the
 359  * instruction preceeding the jump target, the jump target may be moved
 360  * one entry back. This is a size optimization, since the instruction before
 361  * the branch gets removed.
 362  */
 363 {
 364     unsigned Changes = 0;
 365     CodeEntry* E1;              /* Entry 1 */
 366     CodeEntry* E2;              /* Entry 2 */
 367     CodeEntry* T1;              /* Jump target entry 1 */
 368     CodeEntry* T2;              /* Jump target entry 2 */
 369     CodeLabel* TL1;             /* Target label 1 */
 370     unsigned TI;                /* Target index */
 371     unsigned I;
 372
 373     /* Get the number of entries, bail out if we have not enough */
 374     unsigned Count = GetCodeEntryCount (S);
 375     if (Count < 3) {
 376         return 0;
 377     }
 378
 379     /* Walk over the entries */
 380     I = 0;
 381     while (I < Count-1) {
 382
 383         /* Get next entry */
 384         E2 = GetCodeEntry (S, I+1);
 385
 386         /* Check if we have a jump or branch, and a matching label */
 387         if ((E2->Info & OF_UBRA) != 0 && E2->JumpTo) {
 388
 389             /* Get the target instruction for the label */
 390             T2 = E2->JumpTo->Owner;
 391
 392             /* Get the entry preceeding this one (if possible) */
 393             TI = GetCodeEntryIndex (S, T2);
 394             if (TI == 0) {
 395                 /* There is no entry before this one */
 396                 goto NextEntry;
 397             }
 398             T1 = GetCodeEntry (S, TI-1);
 399
 400             /* Get the entry preceeding the jump */
 401             E1 = GetCodeEntry (S, I);
 402
 403             /* Check if both preceeding instructions are identical */
 404             if (!CodeEntriesAreEqual (E1, T1)) {
 405                 /* Not equal, try next */
 406                 goto NextEntry;
 407             }
 408
 409             /* Get the label for the instruction preceeding the jump target.
 410              * This routine will create a new label if the instruction does
 411              * not already have one.
 412              */
 413             TL1 = GenCodeLabel (S, T1);
 414
 415             /* Change the jump target to point to this new label */
 416             MoveCodeLabelRef (S, E2, TL1);
 417
 418             /* If the instruction preceeding the jump has labels attached,
 419              * move references to this label to the new label.
 420              */
 421             if (CodeEntryHasLabel (E1)) {
 422                 MoveCodeLabels (S, E1, T1);
 423             }
 424
 425             /* Remove the entry preceeding the jump */
 426             DelCodeEntry (S, I);
 427             --Count;
 428
 429             /* Remember, we had changes */
 430             ++Changes;
 431
 432         }
 433
 434 NextEntry:
 435         /* Next entry */
 436         ++I;
 437
 438     }
 439
 440     /* Return the number of changes made */
 441     return Changes;
 442 }
 443
 444
 445
 446 /*****************************************************************************/
 447 /*                       Optimize conditional branches                       */
 448 /*****************************************************************************/
 449
 450
 451
 452 unsigned OptCondBranches (CodeSeg* S)
 453 /* Performs several optimization steps:
 454  *
 455  *  - If an immidiate load of a register is followed by a conditional jump that
 456  *    is never taken because the load of the register sets the flags in such a
 457  *    manner, remove the conditional branch.
 458  *  - If the conditional branch is always taken because of the register load,
 459  *    replace it by a jmp.
 460  *  - If a conditional branch jumps around an unconditional branch, remove the
 461  *    conditional branch and make the jump a conditional branch with the
 462  *    inverse condition of the first one.
 463  */
 464 {
 465     unsigned Changes = 0;
 466     unsigned I;
 467
 468     /* Get the number of entries, bail out if we have not enough */
 469     unsigned Count = GetCodeEntryCount (S);
 470     if (Count < 2) {
 471         return 0;
 472     }
 473
 474     /* Walk over the entries */
 475     I = 0;
 476     while (I < Count-1) {
 477
 478         CodeEntry* N;
 479         CodeLabel* L;
 480
 481         /* Get next entry */
 482         CodeEntry* E = GetCodeEntry (S, I);
 483
 484         /* Check if it's a register load */
 485         if ((E->Info & OF_LOAD) != 0            &&  /* It's a load instruction */
 486             E->AM == AM_IMM                     &&  /* ..with immidiate addressing */
 487             (E->Flags & CEF_NUMARG) != 0        &&  /* ..and a numeric argument. */
 488             (N = GetNextCodeEntry (S, I)) != 0  &&  /* There is a following entry */
 489             (N->Info & OF_CBRA) != 0            &&  /* ..which is a conditional branch */
 490             !CodeEntryHasLabel (N)) {               /* ..and does not have a label */
 491
 492             /* Get the branch condition */
 493             bc_t BC = GetBranchCond (N->OPC);
 494
 495             /* Check the argument against the branch condition */
 496             if ((BC == BC_EQ && E->Num != 0)            ||
 497                 (BC == BC_NE && E->Num == 0)            ||
 498                 (BC == BC_PL && (E->Num & 0x80) != 0)   ||
 499                 (BC == BC_MI && (E->Num & 0x80) == 0)) {
 500
 501                 /* Remove the conditional branch */
 502                 DelCodeEntry (S, I+1);
 503                 --Count;
 504
 505                 /* Remember, we had changes */
 506                 ++Changes;
 507
 508             } else if ((BC == BC_EQ && E->Num == 0)             ||
 509                        (BC == BC_NE && E->Num != 0)             ||
 510                        (BC == BC_PL && (E->Num & 0x80) == 0)    ||
 511                        (BC == BC_MI && (E->Num & 0x80) != 0)) {
 512
 513                 /* The branch is always taken, replace it by a jump */
 514                 ReplaceOPC (N, OPC_JMP);
 515
 516                 /* Remember, we had changes */
 517                 ++Changes;
 518             }
 519
 520         }
 521
 522         if ((E->Info & OF_CBRA) != 0            &&  /* It's a conditional branch */
 523             (L = E->JumpTo) != 0                &&  /* ..referencing a local label */
 524             (N = GetNextCodeEntry (S, I)) != 0  &&  /* There is a following entry */
 525             (N->Info & OF_UBRA) != 0            &&  /* ..which is an uncond branch, */
 526             !CodeEntryHasLabel (N)              &&  /* ..has no label attached */
 527             L->Owner == GetNextCodeEntry (S, I+1)) {/* ..and jump target follows */
 528
 529             /* Replace the jump by a conditional branch with the inverse branch
 530              * condition than the branch around it.
 531              */
 532             ReplaceOPC (N, GetInverseBranch (E->OPC));
 533
 534             /* Remove the conditional branch */
 535             DelCodeEntry (S, I);
 536             --Count;
 537
 538             /* Remember, we had changes */
 539             ++Changes;
 540
 541         }
 542
 543         /* Next entry */
 544         ++I;
 545
 546     }
 547
 548     /* Return the number of changes made */
 549     return Changes;
 550 }
 551
 552
 553
 554 /*****************************************************************************/
 555 /*                            Remove unused loads                            */
 556 /*****************************************************************************/
 557
 558
 559
 560 unsigned OptUnusedLoads (CodeSeg* S)
 561 /* Remove loads of registers where the value loaded is not used later. */
 562 {
 563     unsigned Changes = 0;
 564     unsigned I;
 565
 566     /* Get the number of entries, bail out if we have not enough */
 567     unsigned Count = GetCodeEntryCount (S);
 568     if (Count < 2) {
 569         return 0;
 570     }
 571
 572     /* Walk over the entries */
 573     I = 0;
 574     while (I < Count-1) {
 575
 576         /* Get next entry */
 577         CodeEntry* E = GetCodeEntry (S, I);
 578
 579         /* Check if it's a register load */
 580         if ((E->Info & OF_LOAD) != 0) {
 581
 582             unsigned char R;
 583
 584             /* Get the next instruction, it must not be a conditional branch */
 585             CodeEntry* N = GetCodeEntry (S, I+1);
 586             if ((N->Info & OF_CBRA) != 0) {
 587                 goto NextEntry;
 588             }
 589
 590             /* Check which sort of load it is */
 591             switch (E->OPC) {
 592                 case OPC_LDA:   R = REG_A;      break;
 593                 case OPC_LDX:   R = REG_X;      break;
 594                 case OPC_LDY:   R = REG_Y;      break;
 595                 default:        goto NextEntry;         /* OOPS */
 596             }
 597
 598             /* Get register usage and check if the register value is used later */
 599             if ((GetRegInfo (S, I+1) & R) == 0) {
 600
 601                 /* Register value is not used, remove the load */
 602                 DelCodeEntry (S, I);
 603                 --Count;
 604
 605                 /* Remember, we had changes */
 606                 ++Changes;
 607
 608             }
 609         }
 610
 611 NextEntry:
 612         /* Next entry */
 613         ++I;
 614
 615     }
 616
 617     /* Return the number of changes made */
 618     return Changes;
 619 }
 620
 621
 622