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