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