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