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