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 /*                        Replace jumps to RTS by RTS                        */
  49 /*****************************************************************************/
  50
  51
  52
  53 unsigned OptRTSJumps (CodeSeg* S)
  54 /* Replace jumps to RTS by RTS */
  55 {
  56     unsigned Changes = 0;
  57
  58     /* Walk over all entries minus the last one */
  59     unsigned I = 0;
  60     while (I < CS_GetEntryCount (S)) {
  61
  62         /* Get the next entry */
  63         CodeEntry* E = CS_GetEntry (S, I);
  64
  65         /* Check if it's an unconditional branch to a local target */
  66         if ((E->Info & OF_UBRA) != 0            &&
  67             E->JumpTo != 0                      &&
  68             E->JumpTo->Owner->OPC == OP65_RTS) {
  69
  70             /* Insert an RTS instruction */
  71             CodeEntry* X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->LI);
  72             CS_InsertEntry (S, X, I+1);
  73
  74             /* Delete the jump */
  75             CS_DelEntry (S, I);
  76
  77             /* Remember, we had changes */
  78             ++Changes;
  79
  80         }
  81
  82         /* Next entry */
  83         ++I;
  84
  85     }
  86
  87     /* Return the number of changes made */
  88     return Changes;
  89 }
  90
  91
  92
  93 /*****************************************************************************/
  94 /*                             Remove dead jumps                             */
  95 /*****************************************************************************/
  96
  97
  98
  99 unsigned OptDeadJumps (CodeSeg* S)
 100 /* Remove dead jumps (jumps to the next instruction) */
 101 {
 102     unsigned Changes = 0;
 103     CodeEntry* E;
 104     unsigned I;
 105
 106     /* Get the number of entries, bail out if we have less than two entries */
 107     unsigned Count = CS_GetEntryCount (S);
 108     if (Count < 2) {
 109         return 0;
 110     }
 111
 112     /* Walk over all entries minus the last one */
 113     I = 0;
 114     while (I < Count-1) {
 115
 116         /* Get the next entry */
 117         E = CS_GetEntry (S, I);
 118
 119         /* Check if it's a branch, if it has a local target, and if the target
 120          * is the next instruction.
 121          */
 122         if (E->AM == AM65_BRA && E->JumpTo && E->JumpTo->Owner == CS_GetEntry (S, I+1)) {
 123
 124             /* Delete the dead jump */
 125             CS_DelEntry (S, I);
 126
 127             /* Keep the number of entries updated */
 128             --Count;
 129
 130             /* Remember, we had changes */
 131             ++Changes;
 132
 133         } else {
 134
 135             /* Next entry */
 136             ++I;
 137
 138         }
 139     }
 140
 141     /* Return the number of changes made */
 142     return Changes;
 143 }
 144
 145
 146
 147 /*****************************************************************************/
 148 /*                             Remove dead code                              */
 149 /*****************************************************************************/
 150
 151
 152
 153 unsigned OptDeadCode (CodeSeg* S)
 154 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 155  * and has no label)
 156  */
 157 {
 158     unsigned Changes = 0;
 159     unsigned I;
 160
 161     /* Get the number of entries, bail out if we have less than two entries */
 162     unsigned Count = CS_GetEntryCount (S);
 163     if (Count < 2) {
 164         return 0;
 165     }
 166
 167     /* Walk over all entries */
 168     I = 0;
 169     while (I < Count) {
 170
 171         CodeEntry* N;
 172
 173         /* Get this entry */
 174         CodeEntry* E = CS_GetEntry (S, I);
 175
 176         /* Check if it's an unconditional branch, and if the next entry has
 177          * no labels attached
 178          */
 179         if ((E->Info & OF_DEAD) != 0           &&
 180             (N = CS_GetNextEntry (S, I)) != 0  &&
 181             !CE_HasLabel (N)) {
 182
 183             /* Delete the next entry */
 184             CS_DelEntry (S, I+1);
 185
 186             /* Keep the number of entries updated */
 187             --Count;
 188
 189             /* Remember, we had changes */
 190             ++Changes;
 191
 192         } else {
 193
 194             /* Next entry */
 195             ++I;
 196
 197         }
 198     }
 199
 200     /* Return the number of changes made */
 201     return Changes;
 202 }
 203
 204
 205
 206 /*****************************************************************************/
 207 /*                          Optimize jump cascades                           */
 208 /*****************************************************************************/
 209
 210
 211
 212 unsigned OptJumpCascades (CodeSeg* S)
 213 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 214  * replaced by a jump to the final location. This will in some cases produce
 215  * worse code, because some jump targets are no longer reachable by short
 216  * branches, but this is quite rare, so there are more advantages than
 217  * disadvantages.
 218  */
 219 {
 220     unsigned Changes = 0;
 221
 222     /* Walk over all entries */
 223     unsigned I = 0;
 224     while (I < CS_GetEntryCount (S)) {
 225
 226         CodeEntry* N;
 227         CodeLabel* OldLabel;
 228
 229         /* Get this entry */
 230         CodeEntry* E = CS_GetEntry (S, I);
 231
 232         /* Check if it's a branch, if it has a jump label, if this jump
 233          * label is not attached to the instruction itself, and if the
 234          * target instruction is itself a branch.
 235          */
 236         if ((E->Info & OF_BRA) != 0        &&
 237             (OldLabel = E->JumpTo) != 0    &&
 238             (N = OldLabel->Owner) != E     &&
 239             (N->Info & OF_BRA) != 0) {
 240
 241             /* Check if we can use the final target label. This is the case,
 242              * if the target branch is an absolut branch, or if it is a
 243              * conditional branch checking the same condition as the first one.
 244              */
 245             if ((N->Info & OF_UBRA) != 0 ||
 246                 ((E->Info & OF_CBRA) != 0 &&
 247                  GetBranchCond (E->OPC)  == GetBranchCond (N->OPC))) {
 248
 249                 /* This is a jump cascade and we may jump to the final target.
 250                  * Insert a new instruction, then remove the old one
 251                  */
 252                 CodeEntry* X = NewCodeEntry (E->OPC, E->AM, N->Arg, N->JumpTo, E->LI);
 253
 254                 /* Insert it behind E */
 255                 CS_InsertEntry (S, X, I+1);
 256
 257                 /* Remove E */
 258                 CS_DelEntry (S, I);
 259
 260                 /* Remember, we had changes */
 261                 ++Changes;
 262
 263                 /* Done */
 264                 continue;
 265
 266             }
 267
 268             /* Check if both are conditional branches, and the condition of
 269              * the second is the inverse of that of the first. In this case,
 270              * the second branch will never be taken, and we may jump directly
 271              * to the instruction behind this one.
 272              */
 273             if ((E->Info & OF_CBRA) != 0 && (N->Info & OF_CBRA) != 0) {
 274
 275                 CodeEntry* X;   /* Instruction behind N */
 276                 CodeLabel* LX;  /* Label attached to X */
 277
 278                 /* Get the branch conditions of both branches */
 279                 bc_t BC1 = GetBranchCond (E->OPC);
 280                 bc_t BC2 = GetBranchCond (N->OPC);
 281
 282                 /* Check the branch conditions */
 283                 if (BC1 != GetInverseCond (BC2)) {
 284                     /* Condition not met */
 285                     goto NextEntry;
 286                 }
 287
 288                 /* We may jump behind this conditional branch. Get the
 289                  * pointer to the next instruction
 290                  */
 291                 if ((X = CS_GetNextEntry (S, CS_GetEntryIndex (S, N))) == 0) {
 292                     /* N is the last entry, bail out */
 293                     goto NextEntry;
 294                 }
 295
 296                 /* Get the label attached to X, create a new one if needed */
 297                 LX = CS_GenLabel (S, X);
 298
 299                 /* Move the reference from E to the new label */
 300                 CS_MoveLabelRef (S, E, LX);
 301
 302                 /* Remember, we had changes */
 303                 ++Changes;
 304
 305                 /* Done */
 306                 continue;
 307
 308             }
 309         }
 310
 311 NextEntry:
 312         /* Next entry */
 313         ++I;
 314
 315     }
 316
 317     /* Return the number of changes made */
 318     return Changes;
 319 }
 320
 321
 322
 323 /*****************************************************************************/
 324 /*                             Optimize jsr/rts                              */
 325 /*****************************************************************************/
 326
 327
 328
 329 unsigned OptRTS (CodeSeg* S)
 330 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 331  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 332  * label, the dead code elimination should take care of it.
 333  */
 334 {
 335     unsigned Changes = 0;
 336     unsigned I;
 337
 338     /* Get the number of entries, bail out if we have less than 2 entries */
 339     unsigned Count = CS_GetEntryCount (S);
 340     if (Count < 2) {
 341         return 0;
 342     }
 343
 344     /* Walk over all entries minus the last one */
 345     I = 0;
 346     while (I < Count-1) {
 347
 348         CodeEntry* N;
 349
 350         /* Get this entry */
 351         CodeEntry* E = CS_GetEntry (S, I);
 352
 353         /* Check if it's a subroutine call and if the following insn is RTS */
 354         if (E->OPC == OP65_JSR                    &&
 355             (N = CS_GetNextEntry (S, I)) != 0 &&
 356             N->OPC == OP65_RTS) {
 357
 358             /* Change the jsr to a jmp and use the additional info for a jump */
 359             E->AM = AM65_BRA;
 360             CE_ReplaceOPC (E, OP65_JMP);
 361
 362             /* Remember, we had changes */
 363             ++Changes;
 364
 365         }
 366
 367         /* Next entry */
 368         ++I;
 369
 370     }
 371
 372     /* Return the number of changes made */
 373     return Changes;
 374 }
 375
 376
 377
 378 /*****************************************************************************/
 379 /*                           Optimize jump targets                           */
 380 /*****************************************************************************/
 381
 382
 383
 384 unsigned OptJumpTarget (CodeSeg* S)
 385 /* If the instruction preceeding an unconditional branch is the same as the
 386  * instruction preceeding the jump target, the jump target may be moved
 387  * one entry back. This is a size optimization, since the instruction before
 388  * the branch gets removed.
 389  */
 390 {
 391     unsigned Changes = 0;
 392     CodeEntry* E1;              /* Entry 1 */
 393     CodeEntry* E2;              /* Entry 2 */
 394     CodeEntry* T1;              /* Jump target entry 1 */
 395     CodeEntry* T2;              /* Jump target entry 2 */
 396     CodeLabel* TL1;             /* Target label 1 */
 397     unsigned TI;                /* Target index */
 398     unsigned I;
 399
 400     /* Get the number of entries, bail out if we have not enough */
 401     unsigned Count = CS_GetEntryCount (S);
 402     if (Count < 3) {
 403         return 0;
 404     }
 405
 406     /* Walk over the entries */
 407     I = 0;
 408     while (I < Count-1) {
 409
 410         /* Get next entry */
 411         E2 = CS_GetEntry (S, I+1);
 412
 413         /* Check if we have a jump or branch, and a matching label */
 414         if ((E2->Info & OF_UBRA) != 0 && E2->JumpTo) {
 415
 416             /* Get the target instruction for the label */
 417             T2 = E2->JumpTo->Owner;
 418
 419             /* Get the entry preceeding this one (if possible) */
 420             TI = CS_GetEntryIndex (S, T2);
 421             if (TI == 0) {
 422                 /* There is no entry before this one */
 423                 goto NextEntry;
 424             }
 425             T1 = CS_GetEntry (S, TI-1);
 426
 427             /* Get the entry preceeding the jump */
 428             E1 = CS_GetEntry (S, I);
 429
 430             /* Check if both preceeding instructions are identical */
 431             if (!CodeEntriesAreEqual (E1, T1)) {
 432                 /* Not equal, try next */
 433                 goto NextEntry;
 434             }
 435
 436             /* Get the label for the instruction preceeding the jump target.
 437              * This routine will create a new label if the instruction does
 438              * not already have one.
 439              */
 440             TL1 = CS_GenLabel (S, T1);
 441
 442             /* Change the jump target to point to this new label */
 443             CS_MoveLabelRef (S, E2, TL1);
 444
 445             /* If the instruction preceeding the jump has labels attached,
 446              * move references to this label to the new label.
 447              */
 448             if (CE_HasLabel (E1)) {
 449                 CS_MoveLabels (S, E1, T1);
 450             }
 451
 452             /* Remove the entry preceeding the jump */
 453             CS_DelEntry (S, I);
 454             --Count;
 455
 456             /* Remember, we had changes */
 457             ++Changes;
 458
 459         }
 460
 461 NextEntry:
 462         /* Next entry */
 463         ++I;
 464
 465     }
 466
 467     /* Return the number of changes made */
 468     return Changes;
 469 }
 470
 471
 472
 473 /*****************************************************************************/
 474 /*                       Optimize conditional branches                       */
 475 /*****************************************************************************/
 476
 477
 478
 479 unsigned OptCondBranches (CodeSeg* S)
 480 /* Performs several optimization steps:
 481  *
 482  *  - If an immidiate load of a register is followed by a conditional jump that
 483  *    is never taken because the load of the register sets the flags in such a
 484  *    manner, remove the conditional branch.
 485  *  - If the conditional branch is always taken because of the register load,
 486  *    replace it by a jmp.
 487  *  - If a conditional branch jumps around an unconditional branch, remove the
 488  *    conditional branch and make the jump a conditional branch with the
 489  *    inverse condition of the first one.
 490  */
 491 {
 492     unsigned Changes = 0;
 493     unsigned I;
 494
 495     /* Get the number of entries, bail out if we have not enough */
 496     unsigned Count = CS_GetEntryCount (S);
 497     if (Count < 2) {
 498         return 0;
 499     }
 500
 501     /* Walk over the entries */
 502     I = 0;
 503     while (I < Count-1) {
 504
 505         CodeEntry* N;
 506         CodeLabel* L;
 507
 508         /* Get next entry */
 509         CodeEntry* E = CS_GetEntry (S, I);
 510
 511         /* Check if it's a register load */
 512         if ((E->Info & OF_LOAD) != 0              &&  /* It's a load instruction */
 513             E->AM == AM65_IMM                     &&  /* ..with immidiate addressing */
 514             (E->Flags & CEF_NUMARG) != 0          &&  /* ..and a numeric argument. */
 515             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 516             (N->Info & OF_CBRA) != 0              &&  /* ..which is a conditional branch */
 517             !CE_HasLabel (N)) {               /* ..and does not have a label */
 518
 519             /* Get the branch condition */
 520             bc_t BC = GetBranchCond (N->OPC);
 521
 522             /* Check the argument against the branch condition */
 523             if ((BC == BC_EQ && E->Num != 0)            ||
 524                 (BC == BC_NE && E->Num == 0)            ||
 525                 (BC == BC_PL && (E->Num & 0x80) != 0)   ||
 526                 (BC == BC_MI && (E->Num & 0x80) == 0)) {
 527
 528                 /* Remove the conditional branch */
 529                 CS_DelEntry (S, I+1);
 530                 --Count;
 531
 532                 /* Remember, we had changes */
 533                 ++Changes;
 534
 535             } else if ((BC == BC_EQ && E->Num == 0)             ||
 536                        (BC == BC_NE && E->Num != 0)             ||
 537                        (BC == BC_PL && (E->Num & 0x80) == 0)    ||
 538                        (BC == BC_MI && (E->Num & 0x80) != 0)) {
 539
 540                 /* The branch is always taken, replace it by a jump */
 541                 CE_ReplaceOPC (N, OP65_JMP);
 542
 543                 /* Remember, we had changes */
 544                 ++Changes;
 545             }
 546
 547         }
 548
 549         if ((E->Info & OF_CBRA) != 0              &&  /* It's a conditional branch */
 550             (L = E->JumpTo) != 0                  &&  /* ..referencing a local label */
 551             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 552             (N->Info & OF_UBRA) != 0              &&  /* ..which is an uncond branch, */
 553             !CE_HasLabel (N)                      &&  /* ..has no label attached */
 554             L->Owner == CS_GetNextEntry (S, I+1)) {/* ..and jump target follows */
 555
 556             /* Replace the jump by a conditional branch with the inverse branch
 557              * condition than the branch around it.
 558              */
 559             CE_ReplaceOPC (N, GetInverseBranch (E->OPC));
 560
 561             /* Remove the conditional branch */
 562             CS_DelEntry (S, I);
 563             --Count;
 564
 565             /* Remember, we had changes */
 566             ++Changes;
 567
 568         }
 569
 570         /* Next entry */
 571         ++I;
 572
 573     }
 574
 575     /* Return the number of changes made */
 576     return Changes;
 577 }
 578
 579
 580
 581 /*****************************************************************************/
 582 /*                      Remove unused loads and stores                       */
 583 /*****************************************************************************/
 584
 585
 586
 587 unsigned OptUnusedLoads (CodeSeg* S)
 588 /* Remove loads of registers where the value loaded is not used later. */
 589 {
 590     unsigned Changes = 0;
 591
 592     /* Walk over the entries */
 593     unsigned I = 0;
 594     while (I < CS_GetEntryCount (S)) {
 595
 596         CodeEntry* N;
 597
 598         /* Get next entry */
 599         CodeEntry* E = CS_GetEntry (S, I);
 600
 601         /* Check if it's a register load or transfer insn */
 602         if ((E->Info & (OF_LOAD | OF_XFR | OF_REG_INCDEC)) != 0  &&
 603             (N = CS_GetNextEntry (S, I)) != 0                    &&
 604             (N->Info & OF_FBRA) == 0) {
 605
 606             /* Check which sort of load or transfer it is */
 607             unsigned R;
 608             switch (E->OPC) {
 609                 case OP65_DEA:
 610                 case OP65_INA:
 611                 case OP65_LDA:
 612                 case OP65_TXA:
 613                 case OP65_TYA:  R = REG_A;      break;
 614                 case OP65_DEX:
 615                 case OP65_INX:
 616                 case OP65_LDX:
 617                 case OP65_TAX:  R = REG_X;      break;
 618                 case OP65_DEY:
 619                 case OP65_INY:
 620                 case OP65_LDY:
 621                 case OP65_TAY:  R = REG_Y;      break;
 622                 default:        goto NextEntry;         /* OOPS */
 623             }
 624
 625             /* Get register usage and check if the register value is used later */
 626             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 627
 628                 /* Register value is not used, remove the load */
 629                 CS_DelEntry (S, I);
 630
 631                 /* Remember, we had changes */
 632                 ++Changes;
 633
 634             }
 635         }
 636
 637 NextEntry:
 638         /* Next entry */
 639         ++I;
 640
 641     }
 642
 643     /* Return the number of changes made */
 644     return Changes;
 645 }
 646
 647
 648
 649 unsigned OptUnusedStores (CodeSeg* S)
 650 /* Remove stores into zero page registers that aren't used later */
 651 {
 652     unsigned Changes = 0;
 653
 654     /* Walk over the entries */
 655     unsigned I = 0;
 656     while (I < CS_GetEntryCount (S)) {
 657
 658         /* Get next entry */
 659         CodeEntry* E = CS_GetEntry (S, I);
 660
 661         /* Check if it's a register load or transfer insn */
 662         if ((E->Info & OF_STORE) != 0    &&
 663             E->AM == AM65_ZP             &&
 664             (E->Chg & REG_ZP) != 0) {
 665
 666             /* Check for the zero page location. We know that there cannot be
 667              * more than one zero page location involved in the store.
 668              */
 669             unsigned R = E->Chg & REG_ZP;
 670
 671             /* Get register usage and check if the register value is used later */
 672             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 673
 674                 /* Register value is not used, remove the load */
 675                 CS_DelEntry (S, I);
 676
 677                 /* Remember, we had changes */
 678                 ++Changes;
 679
 680             }
 681         }
 682
 683         /* Next entry */
 684         ++I;
 685
 686     }
 687
 688     /* Return the number of changes made */
 689     return Changes;
 690 }
 691
 692
 693
 694 unsigned OptDuplicateLoads (CodeSeg* S)
 695 /* Remove loads of registers where the value loaded is already in the register. */
 696 {
 697     unsigned Changes = 0;
 698     unsigned I;
 699
 700     /* Generate register info for this step */
 701     CS_GenRegInfo (S);
 702
 703     /* Walk over the entries */
 704     I = 0;
 705     while (I < CS_GetEntryCount (S)) {
 706
 707         CodeEntry* N;
 708
 709         /* Get next entry */
 710         CodeEntry* E = CS_GetEntry (S, I);
 711
 712         /* Assume we won't delete the entry */
 713         int Delete = 0;
 714
 715         /* Get a pointer to the input registers of the insn */
 716         const RegContents* In  = &E->RI->In;
 717
 718         /* Handle the different instructions */
 719         switch (E->OPC) {
 720
 721             case OP65_LDA:
 722                 if (In->RegA >= 0                     && /* Value of A is known */
 723                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 724                     In->RegA == (long) E->Num         && /* Both are equal */
 725                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 726                     (N->Info & OF_FBRA) == 0) {          /* Which is not a cond branch */
 727                     Delete = 1;
 728                 }
 729                 break;
 730
 731             case OP65_LDX:
 732                 if (In->RegX >= 0                     && /* Value of X is known */
 733                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 734                     In->RegX == (long) E->Num         && /* Both are equal */
 735                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 736                     (N->Info & OF_FBRA) == 0) {          /* Which is not a cond branch */
 737                     Delete = 1;
 738                 }
 739                 break;
 740
 741             case OP65_LDY:
 742                 if (In->RegY >= 0                     && /* Value of Y is known */
 743                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 744                     In->RegY == (long) E->Num         && /* Both are equal */
 745                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 746                     (N->Info & OF_FBRA) == 0) {          /* Which is not a cond branch */
 747                     Delete = 1;
 748                 }
 749                 break;
 750
 751             case OP65_STA:
 752                 /* If we store into a known zero page location, and this
 753                  * location does already contain the value to be stored,
 754                  * remove the store.
 755                  */
 756                 if (In->RegA >= 0                     && /* Value of A is known */
 757                     E->AM == AM65_ZP                  && /* Store into zp */
 758                     (((E->Chg & REG_SREG_LO) != 0 &&     /* Store into sreg */
 759                       In->RegA == In->SRegLo)       ||   /* Value identical */
 760                      ((E->Chg & REG_SREG_HI) != 0 &&     /* Store into sreg+1 */
 761                       In->RegA == In->SRegHi))) {        /* Value identical */
 762                     Delete = 1;
 763                 }
 764                 break;
 765
 766             case OP65_STX:
 767                 /* If we store into a known zero page location, and this
 768                  * location does already contain the value to be stored,
 769                  * remove the store.
 770                  */
 771                 if (In->RegX >= 0                     && /* Value of A is known */
 772                     E->AM == AM65_ZP                  && /* Store into zp */
 773                     (((E->Chg & REG_SREG_LO) != 0 &&     /* Store into sreg */
 774                       In->RegX == In->SRegLo)       ||   /* Value identical */
 775                      ((E->Chg & REG_SREG_HI) != 0 &&     /* Store into sreg+1 */
 776                       In->RegX == In->SRegHi))) {        /* Value identical */
 777                     Delete = 1;
 778
 779                 /* If the value in the X register is known and the same as
 780                  * that in the A register, replace the store by a STA. The
 781                  * optimizer will then remove the load instruction for X
 782                  * later. STX does support the zeropage,y addressing mode,
 783                  * so be sure to check for that.
 784                  */
 785                 } else if (In->RegX >= 0              &&
 786                            In->RegX == In->RegA       &&
 787                            E->AM != AM65_ABSY         &&
 788                            E->AM != AM65_ZPY) {
 789                     /* Use the A register instead */
 790                     CE_ReplaceOPC (E, OP65_STA);
 791                 }
 792                 break;
 793
 794             case OP65_STY:
 795                 /* If we store into a known zero page location, and this
 796                  * location does already contain the value to be stored,
 797                  * remove the store.
 798                  */
 799                 if (In->RegX >= 0                     && /* Value of A is known */
 800                     E->AM == AM65_ZP                  && /* Store into zp */
 801                     (((E->Chg & REG_SREG_LO) != 0 &&     /* Store into sreg */
 802                       In->RegX == In->SRegLo)       ||   /* Value identical */
 803                      ((E->Chg & REG_SREG_HI) != 0 &&     /* Store into sreg+1 */
 804                       In->RegX == In->SRegHi))) {        /* Value identical */
 805                     Delete = 1;
 806                 /* If the value in the Y register is known and the same as
 807                  * that in the A register, replace the store by a STA. The
 808                  * optimizer will then remove the load instruction for Y
 809                  * later. If replacement by A is not possible try a
 810                  * replacement by X, but check for invalid addressing modes
 811                  * in this case.
 812                  */
 813                 } else if (In->RegY >= 0) {
 814                     if (In->RegY == In->RegA) {
 815                         CE_ReplaceOPC (E, OP65_STA);
 816                     } else if (In->RegY == In->RegX   &&
 817                                E->AM != AM65_ABSX     &&
 818                                E->AM != AM65_ZPX) {
 819                         CE_ReplaceOPC (E, OP65_STX);
 820                     }
 821                 }
 822                 break;
 823
 824             case OP65_TAX:
 825                 if (In->RegA >= 0                     &&
 826                     In->RegA == In->RegX              &&
 827                     (N = CS_GetNextEntry (S, I)) != 0 &&
 828                     (N->Info & OF_FBRA) == 0) {
 829                     /* Value is identical and not followed by a branch */
 830                     Delete = 1;
 831                 }
 832                 break;
 833
 834             case OP65_TAY:
 835                 if (In->RegA >= 0                 &&
 836                     In->RegA == In->RegY    &&
 837                     (N = CS_GetNextEntry (S, I)) != 0   &&
 838                     (N->Info & OF_FBRA) == 0) {
 839                     /* Value is identical and not followed by a branch */
 840                     Delete = 1;
 841                 }
 842                 break;
 843
 844             case OP65_TXA:
 845                 if (In->RegX >= 0                 &&
 846                     In->RegX == In->RegA    &&
 847                     (N = CS_GetNextEntry (S, I)) != 0   &&
 848                     (N->Info & OF_FBRA) == 0) {
 849                     /* Value is identical and not followed by a branch */
 850                     Delete = 1;
 851                 }
 852                 break;
 853
 854             case OP65_TYA:
 855                 if (In->RegY >= 0                 &&
 856                     In->RegY == In->RegA    &&
 857                     (N = CS_GetNextEntry (S, I)) != 0   &&
 858                     (N->Info & OF_FBRA) == 0) {
 859                     /* Value is identical and not followed by a branch */
 860                     Delete = 1;
 861                 }
 862                 break;
 863
 864             default:
 865                 break;
 866
 867         }
 868
 869         /* Delete the entry if requested */
 870         if (Delete) {
 871
 872             /* Register value is not used, remove the load */
 873             CS_DelEntry (S, I);
 874
 875             /* Remember, we had changes */
 876             ++Changes;
 877
 878         } else {
 879
 880             /* Next entry */
 881             ++I;
 882
 883         }
 884
 885     }
 886
 887     /* Free register info */
 888     CS_FreeRegInfo (S);
 889
 890     /* Return the number of changes made */
 891     return Changes;
 892 }
 893
 894
 895
 896 unsigned OptStoreLoad (CodeSeg* S)
 897 /* Remove a store followed by a load from the same location. */
 898 {
 899     unsigned Changes = 0;
 900
 901     /* Walk over the entries */
 902     unsigned I = 0;
 903     while (I < CS_GetEntryCount (S)) {
 904
 905         CodeEntry* N;
 906         CodeEntry* X;
 907
 908         /* Get next entry */
 909         CodeEntry* E = CS_GetEntry (S, I);
 910
 911         /* Check if it is a store instruction followed by a load from the
 912          * same address which is itself not followed by a conditional branch.
 913          */
 914         if ((E->Info & OF_STORE) != 0                 &&
 915             (N = CS_GetNextEntry (S, I)) != 0         &&
 916             !CE_HasLabel (N)                          &&
 917             (N->Info & OF_LOAD) != 0                  &&
 918             strcmp (E->Arg, N->Arg) == 0              &&
 919             (X = CS_GetNextEntry (S, I+1)) != 0       &&
 920             (X->Info & OF_FBRA) == 0) {
 921
 922             /* Register value is not used, remove the load */
 923             CS_DelEntry (S, I+1);
 924
 925             /* Remember, we had changes */
 926             ++Changes;
 927
 928         }
 929
 930         /* Next entry */
 931         ++I;
 932
 933     }
 934
 935     /* Return the number of changes made */
 936     return Changes;
 937 }
 938
 939
 940
 941 unsigned OptTransfers (CodeSeg* S)
 942 /* Remove transfers from one register to another and back */
 943 {
 944     unsigned Changes = 0;
 945
 946     /* Walk over the entries */
 947     unsigned I = 0;
 948     while (I < CS_GetEntryCount (S)) {
 949
 950         CodeEntry* N;
 951         CodeEntry* X;
 952         CodeEntry* P;
 953
 954         /* Get next entry */
 955         CodeEntry* E = CS_GetEntry (S, I);
 956
 957         /* Check if it is a store instruction followed by a load from the
 958          * same address which is itself not followed by a conditional branch.
 959          */
 960         if ((E->Info & OF_XFR) != 0                 &&
 961             (N = CS_GetNextEntry (S, I)) != 0       &&
 962             !CE_HasLabel (N)                        &&
 963             (N->Info & OF_XFR) != 0) {
 964
 965             /* Check if it's a transfer and back */
 966             if ((E->OPC == OP65_TAX && N->OPC == OP65_TXA && !RegXUsed (S, I+2)) ||
 967                 (E->OPC == OP65_TAY && N->OPC == OP65_TYA && !RegYUsed (S, I+2)) ||
 968                 (E->OPC == OP65_TXA && N->OPC == OP65_TAX && !RegAUsed (S, I+2)) ||
 969                 (E->OPC == OP65_TYA && N->OPC == OP65_TAY && !RegAUsed (S, I+1))) {
 970
 971                 /* If the next insn is a conditional branch, check if the insn
 972                  * preceeding the first xfr will set the flags right, otherwise we
 973                  * may not remove the sequence.
 974                  */
 975                 if ((X = CS_GetNextEntry (S, I+1)) == 0) {
 976                     goto NextEntry;
 977                 }
 978                 if ((X->Info & OF_FBRA) != 0) {
 979                     if (I == 0) {
 980                         /* No preceeding entry */
 981                         goto NextEntry;
 982                     }
 983                     P = CS_GetEntry (S, I-1);
 984                     if ((P->Info & OF_SETF) == 0) {
 985                         /* Does not set the flags */
 986                         goto NextEntry;
 987                     }
 988                 }
 989
 990                 /* Remove both transfers */
 991                 CS_DelEntry (S, I+1);
 992                 CS_DelEntry (S, I);
 993
 994                 /* Remember, we had changes */
 995                 ++Changes;
 996             }
 997         }
 998
 999 NextEntry:
1000         /* Next entry */
1001         ++I;
1002
1003     }
1004
1005     /* Return the number of changes made */
1006     return Changes;
1007 }
1008
1009
1010
1011 /*****************************************************************************/
1012 /*                           Optimize branch types                           */
1013 /*****************************************************************************/
1014
1015
1016
1017 unsigned OptBranchDist (CodeSeg* S)
1018 /* Change branches for the distance needed. */
1019 {
1020     unsigned Changes = 0;
1021     unsigned I;
1022
1023     /* Get the number of entries, bail out if we have not enough */
1024     unsigned Count = CS_GetEntryCount (S);
1025
1026     /* Walk over the entries */
1027     I = 0;
1028     while (I < Count) {
1029
1030         /* Get next entry */
1031         CodeEntry* E = CS_GetEntry (S, I);
1032
1033         /* Check if it's a conditional branch to a local label. */
1034         if ((E->Info & OF_CBRA) != 0) {
1035
1036             /* Is this a branch to a local symbol? */
1037             if (E->JumpTo != 0) {
1038
1039                 /* Get the index of the branch target */
1040                 unsigned TI = CS_GetEntryIndex (S, E->JumpTo->Owner);
1041
1042                 /* Determine the branch distance */
1043                 int Distance = 0;
1044                 if (TI >= I) {
1045                     /* Forward branch */
1046                     unsigned J = I;
1047                     while (J < TI) {
1048                         CodeEntry* N = CS_GetEntry (S, J++);
1049                         Distance += N->Size;
1050                     }
1051                 } else {
1052                     /* Backward branch */
1053                     unsigned J = TI;
1054                     while (J < I) {
1055                         CodeEntry* N = CS_GetEntry (S, J++);
1056                         Distance += N->Size;
1057                     }
1058                 }
1059
1060                 /* Make the branch short/long according to distance */
1061                 if ((E->Info & OF_LBRA) == 0 && Distance > 120) {
1062                     /* Short branch but long distance */
1063                     CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1064                     ++Changes;
1065                 } else if ((E->Info & OF_LBRA) != 0 && Distance < 120) {
1066                     /* Long branch but short distance */
1067                     CE_ReplaceOPC (E, MakeShortBranch (E->OPC));
1068                     ++Changes;
1069                 }
1070
1071             } else if ((E->Info & OF_LBRA) == 0) {
1072
1073                 /* Short branch to external symbol - make it long */
1074                 CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1075                 ++Changes;
1076
1077             }
1078         }
1079
1080         /* Next entry */
1081         ++I;
1082
1083     }
1084
1085     /* Return the number of changes made */
1086     return Changes;
1087 }
1088
1089
1090