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