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-2009, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  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 /* common */
  37 #include "cpu.h"
  38
  39 /* cc65 */
  40 #include "codeent.h"
  41 #include "codeinfo.h"
  42 #include "codeopt.h"
  43 #include "error.h"
  44 #include "coptind.h"
  45
  46
  47
  48 /*****************************************************************************/
  49 /*                             Helper functions                              */
  50 /*****************************************************************************/
  51
  52
  53
  54 static int MemAccess (CodeSeg* S, unsigned From, unsigned To, const char* Arg)
  55 /* Checks a range of code entries if there are any memory accesses to Arg.
  56  * Note: This function is not 100% safe, because there is more than one way
  57  * to express a memory location ("foo" and "foo+0" comes to mind) and there
  58  * may be other accesses through pointers. For the code generated by cc65 and
  59  * for the purpose of the caller (OptPushPop) it is assumed to be safe enough
  60  * however.
  61  */
  62 {
  63     /* Walk over all code entries */
  64     while (From <= To) {
  65
  66         /* Get the next entry */
  67         CodeEntry* E = CS_GetEntry (S, From);
  68
  69         /* For simplicity, we just check if there is an argument and if this
  70          * argument equals Arg.
  71          */
  72         if (E->Arg && strcmp (E->Arg, Arg) == 0) {
  73             /* Found an access */
  74             return 1;
  75         }
  76
  77         /* Next entry */
  78         ++From;
  79     }
  80
  81     /* Nothing found */
  82     return 0;
  83 }
  84
  85
  86
  87 static int GetBranchDist (CodeSeg* S, unsigned From, CodeEntry* To)
  88 /* Get the branch distance between the two entries and return it. The distance
  89  * will be negative for backward jumps and positive for forward jumps.
  90  */
  91 {
  92     /* Get the index of the branch target */
  93     unsigned TI = CS_GetEntryIndex (S, To);
  94
  95     /* Determine the branch distance */
  96     int Distance = 0;
  97     if (TI >= From) {
  98         /* Forward branch, do not count the current insn */
  99         unsigned J = From+1;
 100         while (J < TI) {
 101             CodeEntry* N = CS_GetEntry (S, J++);
 102             Distance += N->Size;
 103         }
 104     } else {
 105         /* Backward branch */
 106         unsigned J = TI;
 107         while (J < From) {
 108             CodeEntry* N = CS_GetEntry (S, J++);
 109             Distance -= N->Size;
 110         }
 111     }
 112
 113     /* Return the calculated distance */
 114     return Distance;
 115 }
 116
 117
 118
 119 static int IsShortDist (int Distance)
 120 /* Return true if the given distance is a short branch distance */
 121 {
 122     return (Distance >= -125 && Distance <= 125);
 123 }
 124
 125
 126
 127 static short ZPRegVal (unsigned short Use, const RegContents* RC)
 128 /* Return the contents of the given zeropage register */
 129 {
 130     if ((Use & REG_TMP1) != 0) {
 131         return RC->Tmp1;
 132     } else if ((Use & REG_PTR1_LO) != 0) {
 133         return RC->Ptr1Lo;
 134     } else if ((Use & REG_PTR1_HI) != 0) {
 135         return RC->Ptr1Hi;
 136     } else if ((Use & REG_SREG_LO) != 0) {
 137         return RC->SRegLo;
 138     } else if ((Use & REG_SREG_HI) != 0) {
 139         return RC->SRegHi;
 140     } else {
 141         return UNKNOWN_REGVAL;
 142     }
 143 }
 144
 145
 146
 147 static short RegVal (unsigned short Use, const RegContents* RC)
 148 /* Return the contents of the given register */
 149 {
 150     if ((Use & REG_A) != 0) {
 151         return RC->RegA;
 152     } else if ((Use & REG_X) != 0) {
 153         return RC->RegX;
 154     } else if ((Use & REG_Y) != 0) {
 155         return RC->RegY;
 156     } else {
 157         return ZPRegVal (Use, RC);
 158     }
 159 }
 160
 161
 162
 163 /*****************************************************************************/
 164 /*                        Replace jumps to RTS by RTS                        */
 165 /*****************************************************************************/
 166
 167
 168
 169 unsigned OptRTSJumps1 (CodeSeg* S)
 170 /* Replace jumps to RTS by RTS */
 171 {
 172     unsigned Changes = 0;
 173
 174     /* Walk over all entries minus the last one */
 175     unsigned I = 0;
 176     while (I < CS_GetEntryCount (S)) {
 177
 178         /* Get the next entry */
 179         CodeEntry* E = CS_GetEntry (S, I);
 180
 181         /* Check if it's an unconditional branch to a local target */
 182         if ((E->Info & OF_UBRA) != 0            &&
 183             E->JumpTo != 0                      &&
 184             E->JumpTo->Owner->OPC == OP65_RTS) {
 185
 186             /* Insert an RTS instruction */
 187             CodeEntry* X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->LI);
 188             CS_InsertEntry (S, X, I+1);
 189
 190             /* Delete the jump */
 191             CS_DelEntry (S, I);
 192
 193             /* Remember, we had changes */
 194             ++Changes;
 195
 196         }
 197
 198         /* Next entry */
 199         ++I;
 200
 201     }
 202
 203     /* Return the number of changes made */
 204     return Changes;
 205 }
 206
 207
 208
 209 unsigned OptRTSJumps2 (CodeSeg* S)
 210 /* Replace long conditional jumps to RTS */
 211 {
 212     unsigned Changes = 0;
 213
 214     /* Walk over all entries minus the last one */
 215     unsigned I = 0;
 216     while (I < CS_GetEntryCount (S)) {
 217
 218         CodeEntry* N;
 219
 220         /* Get the next entry */
 221         CodeEntry* E = CS_GetEntry (S, I);
 222
 223         /* Check if it's an unconditional branch to a local target */
 224         if ((E->Info & OF_CBRA) != 0            &&   /* Conditional branch */
 225             (E->Info & OF_LBRA) != 0            &&   /* Long branch */
 226             E->JumpTo != 0                      &&   /* Local label */
 227             E->JumpTo->Owner->OPC == OP65_RTS   &&   /* Target is an RTS */
 228             (N = CS_GetNextEntry (S, I)) != 0) {     /* There is a next entry */
 229
 230             CodeEntry* X;
 231             CodeLabel* LN;
 232             opc_t      NewBranch;
 233
 234             /* We will create a jump around an RTS instead of the long branch */
 235             X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->JumpTo->Owner->LI);
 236             CS_InsertEntry (S, X, I+1);
 237
 238             /* Get the new branch opcode */
 239             NewBranch = MakeShortBranch (GetInverseBranch (E->OPC));
 240
 241             /* Get the label attached to N, create a new one if needed */
 242             LN = CS_GenLabel (S, N);
 243
 244             /* Generate the branch */
 245             X = NewCodeEntry (NewBranch, AM65_BRA, LN->Name, LN, E->LI);
 246             CS_InsertEntry (S, X, I+1);
 247
 248             /* Delete the long branch */
 249             CS_DelEntry (S, I);
 250
 251             /* Remember, we had changes */
 252             ++Changes;
 253
 254         }
 255
 256         /* Next entry */
 257         ++I;
 258
 259     }
 260
 261     /* Return the number of changes made */
 262     return Changes;
 263 }
 264
 265
 266
 267 /*****************************************************************************/
 268 /*                             Remove dead jumps                             */
 269 /*****************************************************************************/
 270
 271
 272
 273 unsigned OptDeadJumps (CodeSeg* S)
 274 /* Remove dead jumps (jumps to the next instruction) */
 275 {
 276     unsigned Changes = 0;
 277
 278     /* Walk over all entries minus the last one */
 279     unsigned I = 0;
 280     while (I < CS_GetEntryCount (S)) {
 281
 282         /* Get the next entry */
 283         CodeEntry* E = CS_GetEntry (S, I);
 284
 285         /* Check if it's a branch, if it has a local target, and if the target
 286          * is the next instruction.
 287          */
 288         if (E->AM == AM65_BRA                               &&
 289             E->JumpTo                                       &&
 290             E->JumpTo->Owner == CS_GetNextEntry (S, I)) {
 291
 292             /* Delete the dead jump */
 293             CS_DelEntry (S, I);
 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 /*                             Remove dead code                              */
 314 /*****************************************************************************/
 315
 316
 317
 318 unsigned OptDeadCode (CodeSeg* S)
 319 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 320  * and has no label)
 321  */
 322 {
 323     unsigned Changes = 0;
 324
 325     /* Walk over all entries */
 326     unsigned I = 0;
 327     while (I < CS_GetEntryCount (S)) {
 328
 329         CodeEntry* N;
 330         CodeLabel* LN;
 331
 332         /* Get this entry */
 333         CodeEntry* E = CS_GetEntry (S, I);
 334
 335         /* Check if it's an unconditional branch, and if the next entry has
 336          * no labels attached, or if the label is just used so that the insn
 337          * can jump to itself.
 338          */
 339         if ((E->Info & OF_DEAD) != 0                     &&     /* Dead code follows */
 340             (N = CS_GetNextEntry (S, I)) != 0            &&     /* Has next entry */
 341             (!CE_HasLabel (N)                        ||         /* Don't has a label */
 342              ((N->Info & OF_UBRA) != 0          &&              /* Uncond branch */
 343               (LN = N->JumpTo) != 0             &&              /* Jumps to known label */
 344               LN->Owner == N                    &&              /* Attached to insn */
 345               CL_GetRefCount (LN) == 1))) {                     /* Only reference */
 346
 347             /* Delete the next entry */
 348             CS_DelEntry (S, I+1);
 349
 350             /* Remember, we had changes */
 351             ++Changes;
 352
 353         } else {
 354
 355             /* Next entry */
 356             ++I;
 357
 358         }
 359     }
 360
 361     /* Return the number of changes made */
 362     return Changes;
 363 }
 364
 365
 366
 367 /*****************************************************************************/
 368 /*                          Optimize jump cascades                           */
 369 /*****************************************************************************/
 370
 371
 372
 373 unsigned OptJumpCascades (CodeSeg* S)
 374 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 375  * replaced by a jump to the final location. This will in some cases produce
 376  * worse code, because some jump targets are no longer reachable by short
 377  * branches, but this is quite rare, so there are more advantages than
 378  * disadvantages.
 379  */
 380 {
 381     unsigned Changes = 0;
 382
 383     /* Walk over all entries */
 384     unsigned I = 0;
 385     while (I < CS_GetEntryCount (S)) {
 386
 387         CodeEntry* N;
 388         CodeLabel* OldLabel;
 389
 390         /* Get this entry */
 391         CodeEntry* E = CS_GetEntry (S, I);
 392
 393         /* Check if it's a branch, if it has a jump label, if this jump
 394          * label is not attached to the instruction itself, and if the
 395          * target instruction is itself a branch.
 396          */
 397         if ((E->Info & OF_BRA) != 0        &&
 398             (OldLabel = E->JumpTo) != 0    &&
 399             (N = OldLabel->Owner) != E     &&
 400             (N->Info & OF_BRA) != 0) {
 401
 402             /* Check if we can use the final target label. This is the case,
 403              * if the target branch is an absolut branch, or if it is a
 404              * conditional branch checking the same condition as the first one.
 405              */
 406             if ((N->Info & OF_UBRA) != 0 ||
 407                 ((E->Info & OF_CBRA) != 0 &&
 408                  GetBranchCond (E->OPC)  == GetBranchCond (N->OPC))) {
 409
 410                 /* This is a jump cascade and we may jump to the final target,
 411                  * provided that the other insn does not jump to itself. If
 412                  * this is the case, we can also jump to ourselves, otherwise
 413                  * insert a jump to the new instruction and remove the old one.
 414                  */
 415                 CodeEntry* X;
 416                 CodeLabel* LN = N->JumpTo;
 417
 418                 if (LN != 0 && LN->Owner == N) {
 419
 420                     /* We found a jump to a jump to itself. Replace our jump
 421                      * by a jump to itself.
 422                      */
 423                     CodeLabel* LE = CS_GenLabel (S, E);
 424                     X = NewCodeEntry (E->OPC, E->AM, LE->Name, LE, E->LI);
 425
 426                 } else {
 427
 428                     /* Jump to the final jump target */
 429                     X = NewCodeEntry (E->OPC, E->AM, N->Arg, N->JumpTo, E->LI);
 430
 431                 }
 432
 433                 /* Insert it behind E */
 434                 CS_InsertEntry (S, X, I+1);
 435
 436                 /* Remove E */
 437                 CS_DelEntry (S, I);
 438
 439                 /* Remember, we had changes */
 440                 ++Changes;
 441
 442             /* Check if both are conditional branches, and the condition of
 443              * the second is the inverse of that of the first. In this case,
 444              * the second branch will never be taken, and we may jump directly
 445              * to the instruction behind this one.
 446              */
 447             } else if ((E->Info & OF_CBRA) != 0 && (N->Info & OF_CBRA) != 0) {
 448
 449                 CodeEntry* X;   /* Instruction behind N */
 450                 CodeLabel* LX;  /* Label attached to X */
 451
 452                 /* Get the branch conditions of both branches */
 453                 bc_t BC1 = GetBranchCond (E->OPC);
 454                 bc_t BC2 = GetBranchCond (N->OPC);
 455
 456                 /* Check the branch conditions */
 457                 if (BC1 != GetInverseCond (BC2)) {
 458                     /* Condition not met */
 459                     goto NextEntry;
 460                 }
 461
 462                 /* We may jump behind this conditional branch. Get the
 463                  * pointer to the next instruction
 464                  */
 465                 if ((X = CS_GetNextEntry (S, CS_GetEntryIndex (S, N))) == 0) {
 466                     /* N is the last entry, bail out */
 467                     goto NextEntry;
 468                 }
 469
 470                 /* Get the label attached to X, create a new one if needed */
 471                 LX = CS_GenLabel (S, X);
 472
 473                 /* Move the reference from E to the new label */
 474                 CS_MoveLabelRef (S, E, LX);
 475
 476                 /* Remember, we had changes */
 477                 ++Changes;
 478             }
 479         }
 480
 481 NextEntry:
 482         /* Next entry */
 483         ++I;
 484
 485     }
 486
 487     /* Return the number of changes made */
 488     return Changes;
 489 }
 490
 491
 492
 493 /*****************************************************************************/
 494 /*                             Optimize jsr/rts                              */
 495 /*****************************************************************************/
 496
 497
 498
 499 unsigned OptRTS (CodeSeg* S)
 500 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 501  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 502  * label, the dead code elimination should take care of it.
 503  */
 504 {
 505     unsigned Changes = 0;
 506
 507     /* Walk over all entries minus the last one */
 508     unsigned I = 0;
 509     while (I < CS_GetEntryCount (S)) {
 510
 511         CodeEntry* N;
 512
 513         /* Get this entry */
 514         CodeEntry* E = CS_GetEntry (S, I);
 515
 516         /* Check if it's a subroutine call and if the following insn is RTS */
 517         if (E->OPC == OP65_JSR                    &&
 518             (N = CS_GetNextEntry (S, I)) != 0 &&
 519             N->OPC == OP65_RTS) {
 520
 521             /* Change the jsr to a jmp and use the additional info for a jump */
 522             E->AM = AM65_BRA;
 523             CE_ReplaceOPC (E, OP65_JMP);
 524
 525             /* Remember, we had changes */
 526             ++Changes;
 527
 528         }
 529
 530         /* Next entry */
 531         ++I;
 532
 533     }
 534
 535     /* Return the number of changes made */
 536     return Changes;
 537 }
 538
 539
 540
 541 /*****************************************************************************/
 542 /*                           Optimize jump targets                           */
 543 /*****************************************************************************/
 544
 545
 546
 547 unsigned OptJumpTarget (CodeSeg* S)
 548 /* If the instruction preceeding an unconditional branch is the same as the
 549  * instruction preceeding the jump target, the jump target may be moved
 550  * one entry back. This is a size optimization, since the instruction before
 551  * the branch gets removed.
 552  */
 553 {
 554     unsigned Changes = 0;
 555     CodeEntry* E1;              /* Entry 1 */
 556     CodeEntry* E2;              /* Entry 2 */
 557     CodeEntry* T1;              /* Jump target entry 1 */
 558     CodeLabel* TL1;             /* Target label 1 */
 559
 560     /* Walk over the entries */
 561     unsigned I = 0;
 562     while (I < CS_GetEntryCount (S)) {
 563
 564         /* Get next entry */
 565         E2 = CS_GetNextEntry (S, I);
 566
 567         /* Check if we have a jump or branch, and a matching label, which
 568          * is not attached to the jump itself
 569          */
 570         if (E2 != 0                     &&
 571             (E2->Info & OF_UBRA) != 0   &&
 572             E2->JumpTo                  &&
 573             E2->JumpTo->Owner != E2) {
 574
 575             /* Get the entry preceeding the branch target */
 576             T1 = CS_GetPrevEntry (S, CS_GetEntryIndex (S, E2->JumpTo->Owner));
 577             if (T1 == 0) {
 578                 /* There is no such entry */
 579                 goto NextEntry;
 580             }
 581
 582             /* Get the entry preceeding the jump */
 583             E1 = CS_GetEntry (S, I);
 584
 585             /* Check if both preceeding instructions are identical */
 586             if (!CodeEntriesAreEqual (E1, T1)) {
 587                 /* Not equal, try next */
 588                 goto NextEntry;
 589             }
 590
 591             /* Get the label for the instruction preceeding the jump target.
 592              * This routine will create a new label if the instruction does
 593              * not already have one.
 594              */
 595             TL1 = CS_GenLabel (S, T1);
 596
 597             /* Change the jump target to point to this new label */
 598             CS_MoveLabelRef (S, E2, TL1);
 599
 600             /* If the instruction preceeding the jump has labels attached,
 601              * move references to this label to the new label.
 602              */
 603             if (CE_HasLabel (E1)) {
 604                 CS_MoveLabels (S, E1, T1);
 605             }
 606
 607             /* Remove the entry preceeding the jump */
 608             CS_DelEntry (S, I);
 609
 610             /* Remember, we had changes */
 611             ++Changes;
 612
 613         } else {
 614 NextEntry:
 615             /* Next entry */
 616             ++I;
 617         }
 618     }
 619
 620     /* Return the number of changes made */
 621     return Changes;
 622 }
 623
 624
 625
 626 /*****************************************************************************/
 627 /*                       Optimize conditional branches                       */
 628 /*****************************************************************************/
 629
 630
 631
 632 unsigned OptCondBranches (CodeSeg* S)
 633 /* Performs several optimization steps:
 634  *
 635  *  - If an immidiate load of a register is followed by a conditional jump that
 636  *    is never taken because the load of the register sets the flags in such a
 637  *    manner, remove the conditional branch.
 638  *  - If the conditional branch is always taken because of the register load,
 639  *    replace it by a jmp.
 640  *  - If a conditional branch jumps around an unconditional branch, remove the
 641  *    conditional branch and make the jump a conditional branch with the
 642  *    inverse condition of the first one.
 643  */
 644 {
 645     unsigned Changes = 0;
 646
 647     /* Walk over the entries */
 648     unsigned I = 0;
 649     while (I < CS_GetEntryCount (S)) {
 650
 651         CodeEntry* N;
 652         CodeLabel* L;
 653
 654         /* Get next entry */
 655         CodeEntry* E = CS_GetEntry (S, I);
 656
 657         /* Check if it's a register load */
 658         if ((E->Info & OF_LOAD) != 0              &&  /* It's a load instruction */
 659             E->AM == AM65_IMM                     &&  /* ..with immidiate addressing */
 660             (E->Flags & CEF_NUMARG) != 0          &&  /* ..and a numeric argument. */
 661             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 662             (N->Info & OF_CBRA) != 0              &&  /* ..which is a conditional branch */
 663             !CE_HasLabel (N)) {               /* ..and does not have a label */
 664
 665             /* Get the branch condition */
 666             bc_t BC = GetBranchCond (N->OPC);
 667
 668             /* Check the argument against the branch condition */
 669             if ((BC == BC_EQ && E->Num != 0)            ||
 670                 (BC == BC_NE && E->Num == 0)            ||
 671                 (BC == BC_PL && (E->Num & 0x80) != 0)   ||
 672                 (BC == BC_MI && (E->Num & 0x80) == 0)) {
 673
 674                 /* Remove the conditional branch */
 675                 CS_DelEntry (S, I+1);
 676
 677                 /* Remember, we had changes */
 678                 ++Changes;
 679
 680             } else if ((BC == BC_EQ && E->Num == 0)             ||
 681                        (BC == BC_NE && E->Num != 0)             ||
 682                        (BC == BC_PL && (E->Num & 0x80) == 0)    ||
 683                        (BC == BC_MI && (E->Num & 0x80) != 0)) {
 684
 685                 /* The branch is always taken, replace it by a jump */
 686                 CE_ReplaceOPC (N, OP65_JMP);
 687
 688                 /* Remember, we had changes */
 689                 ++Changes;
 690             }
 691
 692         }
 693
 694         if ((E->Info & OF_CBRA) != 0              &&  /* It's a conditional branch */
 695             (L = E->JumpTo) != 0                  &&  /* ..referencing a local label */
 696             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 697             (N->Info & OF_UBRA) != 0              &&  /* ..which is an uncond branch, */
 698             !CE_HasLabel (N)                      &&  /* ..has no label attached */
 699             L->Owner == CS_GetNextEntry (S, I+1)) {/* ..and jump target follows */
 700
 701             /* Replace the jump by a conditional branch with the inverse branch
 702              * condition than the branch around it.
 703              */
 704             CE_ReplaceOPC (N, GetInverseBranch (E->OPC));
 705
 706             /* Remove the conditional branch */
 707             CS_DelEntry (S, I);
 708
 709             /* Remember, we had changes */
 710             ++Changes;
 711
 712         }
 713
 714         /* Next entry */
 715         ++I;
 716
 717     }
 718
 719     /* Return the number of changes made */
 720     return Changes;
 721 }
 722
 723
 724
 725 /*****************************************************************************/
 726 /*                      Remove unused loads and stores                       */
 727 /*****************************************************************************/
 728
 729
 730
 731 unsigned OptUnusedLoads (CodeSeg* S)
 732 /* Remove loads of registers where the value loaded is not used later. */
 733 {
 734     unsigned Changes = 0;
 735
 736     /* Walk over the entries */
 737     unsigned I = 0;
 738     while (I < CS_GetEntryCount (S)) {
 739
 740         CodeEntry* N;
 741
 742         /* Get next entry */
 743         CodeEntry* E = CS_GetEntry (S, I);
 744
 745         /* Check if it's a register load or transfer insn */
 746         if ((E->Info & (OF_LOAD | OF_XFR | OF_REG_INCDEC)) != 0         &&
 747             (N = CS_GetNextEntry (S, I)) != 0                           &&
 748             !CE_UseLoadFlags (N)) {
 749
 750             /* Check which sort of load or transfer it is */
 751             unsigned R;
 752             switch (E->OPC) {
 753                 case OP65_DEA:
 754                 case OP65_INA:
 755                 case OP65_LDA:
 756                 case OP65_TXA:
 757                 case OP65_TYA:  R = REG_A;      break;
 758                 case OP65_DEX:
 759                 case OP65_INX:
 760                 case OP65_LDX:
 761                 case OP65_TAX:  R = REG_X;      break;
 762                 case OP65_DEY:
 763                 case OP65_INY:
 764                 case OP65_LDY:
 765                 case OP65_TAY:  R = REG_Y;      break;
 766                 default:        goto NextEntry;         /* OOPS */
 767             }
 768
 769             /* Get register usage and check if the register value is used later */
 770             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 771
 772                 /* Register value is not used, remove the load */
 773                 CS_DelEntry (S, I);
 774
 775                 /* Remember, we had changes. Account the deleted entry in I. */
 776                 ++Changes;
 777                 --I;
 778
 779             }
 780         }
 781
 782 NextEntry:
 783         /* Next entry */
 784         ++I;
 785
 786     }
 787
 788     /* Return the number of changes made */
 789     return Changes;
 790 }
 791
 792
 793
 794 unsigned OptUnusedStores (CodeSeg* S)
 795 /* Remove stores into zero page registers that aren't used later */
 796 {
 797     unsigned Changes = 0;
 798
 799     /* Walk over the entries */
 800     unsigned I = 0;
 801     while (I < CS_GetEntryCount (S)) {
 802
 803         /* Get next entry */
 804         CodeEntry* E = CS_GetEntry (S, I);
 805
 806         /* Check if it's a register load or transfer insn */
 807         if ((E->Info & OF_STORE) != 0    &&
 808             E->AM == AM65_ZP             &&
 809             (E->Chg & REG_ZP) != 0) {
 810
 811             /* Check for the zero page location. We know that there cannot be
 812              * more than one zero page location involved in the store.
 813              */
 814             unsigned R = E->Chg & REG_ZP;
 815
 816             /* Get register usage and check if the register value is used later */
 817             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 818
 819                 /* Register value is not used, remove the load */
 820                 CS_DelEntry (S, I);
 821
 822                 /* Remember, we had changes */
 823                 ++Changes;
 824
 825             }
 826         }
 827
 828         /* Next entry */
 829         ++I;
 830
 831     }
 832
 833     /* Return the number of changes made */
 834     return Changes;
 835 }
 836
 837
 838
 839 unsigned OptDupLoads (CodeSeg* S)
 840 /* Remove loads of registers where the value loaded is already in the register. */
 841 {
 842     unsigned Changes = 0;
 843     unsigned I;
 844
 845     /* Generate register info for this step */
 846     CS_GenRegInfo (S);
 847
 848     /* Walk over the entries */
 849     I = 0;
 850     while (I < CS_GetEntryCount (S)) {
 851
 852         CodeEntry* N;
 853
 854         /* Get next entry */
 855         CodeEntry* E = CS_GetEntry (S, I);
 856
 857         /* Assume we won't delete the entry */
 858         int Delete = 0;
 859
 860         /* Get a pointer to the input registers of the insn */
 861         const RegContents* In  = &E->RI->In;
 862
 863         /* Handle the different instructions */
 864         switch (E->OPC) {
 865
 866             case OP65_LDA:
 867                 if (RegValIsKnown (In->RegA)          && /* Value of A is known */
 868                     CE_IsKnownImm (E, In->RegA)       && /* Value to be loaded is known */
 869                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 870                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 871                     Delete = 1;
 872                 }
 873                 break;
 874
 875             case OP65_LDX:
 876                 if (RegValIsKnown (In->RegX)          && /* Value of X is known */
 877                     CE_IsKnownImm (E, In->RegX)       && /* Value to be loaded is known */
 878                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 879                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 880                     Delete = 1;
 881                 }
 882                 break;
 883
 884             case OP65_LDY:
 885                 if (RegValIsKnown (In->RegY)          && /* Value of Y is known */
 886                     CE_IsKnownImm (E, In->RegY)       && /* Value to be loaded is known */
 887                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 888                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 889                     Delete = 1;
 890                 }
 891                 break;
 892
 893             case OP65_STA:
 894                 /* If we store into a known zero page location, and this
 895                  * location does already contain the value to be stored,
 896                  * remove the store.
 897                  */
 898                 if (RegValIsKnown (In->RegA)          && /* Value of A is known */
 899                     E->AM == AM65_ZP                  && /* Store into zp */
 900                     In->RegA == ZPRegVal (E->Chg, In)) { /* Value identical */
 901
 902                     Delete = 1;
 903                 }
 904                 break;
 905
 906             case OP65_STX:
 907                 /* If we store into a known zero page location, and this
 908                  * location does already contain the value to be stored,
 909                  * remove the store.
 910                  */
 911                 if (RegValIsKnown (In->RegX)          && /* Value of A is known */
 912                     E->AM == AM65_ZP                  && /* Store into zp */
 913                     In->RegX == ZPRegVal (E->Chg, In)) { /* Value identical */
 914
 915                     Delete = 1;
 916
 917                 /* If the value in the X register is known and the same as
 918                  * that in the A register, replace the store by a STA. The
 919                  * optimizer will then remove the load instruction for X
 920                  * later. STX does support the zeropage,y addressing mode,
 921                  * so be sure to check for that.
 922                  */
 923                 } else if (RegValIsKnown (In->RegX)   &&
 924                            In->RegX == In->RegA       &&
 925                            E->AM != AM65_ABSY         &&
 926                            E->AM != AM65_ZPY) {
 927                     /* Use the A register instead */
 928                     CE_ReplaceOPC (E, OP65_STA);
 929                 }
 930                 break;
 931
 932             case OP65_STY:
 933                 /* If we store into a known zero page location, and this
 934                  * location does already contain the value to be stored,
 935                  * remove the store.
 936                  */
 937                 if (RegValIsKnown (In->RegY)          && /* Value of Y is known */
 938                     E->AM == AM65_ZP                  && /* Store into zp */
 939                     In->RegY == ZPRegVal (E->Chg, In)) { /* Value identical */
 940
 941                     Delete = 1;
 942
 943                 /* If the value in the Y register is known and the same as
 944                  * that in the A register, replace the store by a STA. The
 945                  * optimizer will then remove the load instruction for Y
 946                  * later. If replacement by A is not possible try a
 947                  * replacement by X, but check for invalid addressing modes
 948                  * in this case.
 949                  */
 950                 } else if (RegValIsKnown (In->RegY)) {
 951                     if (In->RegY == In->RegA) {
 952                         CE_ReplaceOPC (E, OP65_STA);
 953                     } else if (In->RegY == In->RegX   &&
 954                                E->AM != AM65_ABSX     &&
 955                                E->AM != AM65_ZPX) {
 956                         CE_ReplaceOPC (E, OP65_STX);
 957                     }
 958                 }
 959                 break;
 960
 961             case OP65_STZ:
 962                 /* If we store into a known zero page location, and this
 963                  * location does already contain the value to be stored,
 964                  * remove the store.
 965                  */
 966                 if ((CPUIsets[CPU] & CPU_ISET_65SC02) != 0 && E->AM == AM65_ZP) {
 967                     if (ZPRegVal (E->Chg, In) == 0) {
 968                         Delete = 1;
 969                     }
 970                 }
 971                 break;
 972
 973             case OP65_TAX:
 974                 if (RegValIsKnown (In->RegA)          &&
 975                     In->RegA == In->RegX              &&
 976                     (N = CS_GetNextEntry (S, I)) != 0 &&
 977                     !CE_UseLoadFlags (N)) {
 978                     /* Value is identical and not followed by a branch */
 979                     Delete = 1;
 980                 }
 981                 break;
 982
 983             case OP65_TAY:
 984                 if (RegValIsKnown (In->RegA)            &&
 985                     In->RegA == In->RegY                &&
 986                     (N = CS_GetNextEntry (S, I)) != 0   &&
 987                     !CE_UseLoadFlags (N)) {
 988                     /* Value is identical and not followed by a branch */
 989                     Delete = 1;
 990                 }
 991                 break;
 992
 993             case OP65_TXA:
 994                 if (RegValIsKnown (In->RegX)            &&
 995                     In->RegX == In->RegA                &&
 996                     (N = CS_GetNextEntry (S, I)) != 0   &&
 997                     !CE_UseLoadFlags (N)) {
 998                     /* Value is identical and not followed by a branch */
 999                     Delete = 1;
1000                 }
1001                 break;
1002
1003             case OP65_TYA:
1004                 if (RegValIsKnown (In->RegY)            &&
1005                     In->RegY == In->RegA                &&
1006                     (N = CS_GetNextEntry (S, I)) != 0   &&
1007                     !CE_UseLoadFlags (N)) {
1008                     /* Value is identical and not followed by a branch */
1009                     Delete = 1;
1010                 }
1011                 break;
1012
1013             default:
1014                 break;
1015
1016         }
1017
1018         /* Delete the entry if requested */
1019         if (Delete) {
1020
1021             /* Register value is not used, remove the load */
1022             CS_DelEntry (S, I);
1023
1024             /* Remember, we had changes */
1025             ++Changes;
1026
1027         } else {
1028
1029             /* Next entry */
1030             ++I;
1031
1032         }
1033
1034     }
1035
1036     /* Free register info */
1037     CS_FreeRegInfo (S);
1038
1039     /* Return the number of changes made */
1040     return Changes;
1041 }
1042
1043
1044
1045 unsigned OptStoreLoad (CodeSeg* S)
1046 /* Remove a store followed by a load from the same location. */
1047 {
1048     unsigned Changes = 0;
1049
1050     /* Walk over the entries */
1051     unsigned I = 0;
1052     while (I < CS_GetEntryCount (S)) {
1053
1054         CodeEntry* N;
1055         CodeEntry* X;
1056
1057         /* Get next entry */
1058         CodeEntry* E = CS_GetEntry (S, I);
1059
1060         /* Check if it is a store instruction followed by a load from the
1061          * same address which is itself not followed by a conditional branch.
1062          */
1063         if ((E->Info & OF_STORE) != 0                       &&
1064             (N = CS_GetNextEntry (S, I)) != 0               &&
1065             !CE_HasLabel (N)                                &&
1066             E->AM == N->AM                                  &&
1067             ((E->OPC == OP65_STA && N->OPC == OP65_LDA) ||
1068              (E->OPC == OP65_STX && N->OPC == OP65_LDX) ||
1069              (E->OPC == OP65_STY && N->OPC == OP65_LDY))    &&
1070             strcmp (E->Arg, N->Arg) == 0                    &&
1071             (X = CS_GetNextEntry (S, I+1)) != 0             &&
1072             !CE_UseLoadFlags (X)) {
1073
1074             /* Register has already the correct value, remove the load */
1075             CS_DelEntry (S, I+1);
1076
1077             /* Remember, we had changes */
1078             ++Changes;
1079
1080         }
1081
1082         /* Next entry */
1083         ++I;
1084
1085     }
1086
1087     /* Return the number of changes made */
1088     return Changes;
1089 }
1090
1091
1092
1093 unsigned OptTransfers1 (CodeSeg* S)
1094 /* Remove transfers from one register to another and back */
1095 {
1096     unsigned Changes = 0;
1097
1098     /* Walk over the entries */
1099     unsigned I = 0;
1100     while (I < CS_GetEntryCount (S)) {
1101
1102         CodeEntry* N;
1103         CodeEntry* X;
1104         CodeEntry* P;
1105
1106         /* Get next entry */
1107         CodeEntry* E = CS_GetEntry (S, I);
1108
1109         /* Check if we have two transfer instructions */
1110         if ((E->Info & OF_XFR) != 0                 &&
1111             (N = CS_GetNextEntry (S, I)) != 0       &&
1112             !CE_HasLabel (N)                        &&
1113             (N->Info & OF_XFR) != 0) {
1114
1115             /* Check if it's a transfer and back */
1116             if ((E->OPC == OP65_TAX && N->OPC == OP65_TXA && !RegXUsed (S, I+2)) ||
1117                 (E->OPC == OP65_TAY && N->OPC == OP65_TYA && !RegYUsed (S, I+2)) ||
1118                 (E->OPC == OP65_TXA && N->OPC == OP65_TAX && !RegAUsed (S, I+2)) ||
1119                 (E->OPC == OP65_TYA && N->OPC == OP65_TAY && !RegAUsed (S, I+2))) {
1120
1121                 /* If the next insn is a conditional branch, check if the insn
1122                  * preceeding the first xfr will set the flags right, otherwise we
1123                  * may not remove the sequence.
1124                  */
1125                 if ((X = CS_GetNextEntry (S, I+1)) == 0) {
1126                     goto NextEntry;
1127                 }
1128                 if (CE_UseLoadFlags (X)) {
1129                     if (I == 0) {
1130                         /* No preceeding entry */
1131                         goto NextEntry;
1132                     }
1133                     P = CS_GetEntry (S, I-1);
1134                     if ((P->Info & OF_SETF) == 0) {
1135                         /* Does not set the flags */
1136                         goto NextEntry;
1137                     }
1138                 }
1139
1140                 /* Remove both transfers */
1141                 CS_DelEntry (S, I+1);
1142                 CS_DelEntry (S, I);
1143
1144                 /* Remember, we had changes */
1145                 ++Changes;
1146             }
1147         }
1148
1149 NextEntry:
1150         /* Next entry */
1151         ++I;
1152
1153     }
1154
1155     /* Return the number of changes made */
1156     return Changes;
1157 }
1158
1159
1160
1161 unsigned OptTransfers2 (CodeSeg* S)
1162 /* Replace loads followed by a register transfer by a load with the second
1163  * register if possible.
1164  */
1165 {
1166     unsigned Changes = 0;
1167
1168     /* Walk over the entries */
1169     unsigned I = 0;
1170     while (I < CS_GetEntryCount (S)) {
1171
1172         CodeEntry* N;
1173
1174         /* Get next entry */
1175         CodeEntry* E = CS_GetEntry (S, I);
1176
1177         /* Check if we have a load followed by a transfer where the loaded
1178          * register is not used later.
1179          */
1180         if ((E->Info & OF_LOAD) != 0                &&
1181             (N = CS_GetNextEntry (S, I)) != 0       &&
1182             !CE_HasLabel (N)                        &&
1183             (N->Info & OF_XFR) != 0                 &&
1184             GetRegInfo (S, I+2, E->Chg) != E->Chg) {
1185
1186             CodeEntry* X = 0;
1187
1188             if (E->OPC == OP65_LDA && N->OPC == OP65_TAX) {
1189                 /* LDA/TAX - check for the right addressing modes */
1190                 if (E->AM == AM65_IMM ||
1191                     E->AM == AM65_ZP  ||
1192                     E->AM == AM65_ABS ||
1193                     E->AM == AM65_ABSY) {
1194                     /* Replace */
1195                     X = NewCodeEntry (OP65_LDX, E->AM, E->Arg, 0, N->LI);
1196                 }
1197             } else if (E->OPC == OP65_LDA && N->OPC == OP65_TAY) {
1198                 /* LDA/TAY - check for the right addressing modes */
1199                 if (E->AM == AM65_IMM ||
1200                     E->AM == AM65_ZP  ||
1201                     E->AM == AM65_ZPX ||
1202                     E->AM == AM65_ABS ||
1203                     E->AM == AM65_ABSX) {
1204                     /* Replace */
1205                     X = NewCodeEntry (OP65_LDY, E->AM, E->Arg, 0, N->LI);
1206                 }
1207             } else if (E->OPC == OP65_LDY && N->OPC == OP65_TYA) {
1208                 /* LDY/TYA. LDA supports all addressing modes LDY does */
1209                 X = NewCodeEntry (OP65_LDA, E->AM, E->Arg, 0, N->LI);
1210             } else if (E->OPC == OP65_LDX && N->OPC == OP65_TXA) {
1211                 /* LDX/TXA. LDA doesn't support zp,y, so we must map it to
1212                  * abs,y instead.
1213                  */
1214                 am_t AM = (E->AM == AM65_ZPY)? AM65_ABSY : E->AM;
1215                 X = NewCodeEntry (OP65_LDA, AM, E->Arg, 0, N->LI);
1216             }
1217
1218             /* If we have a load entry, add it and remove the old stuff */
1219             if (X) {
1220                 CS_InsertEntry (S, X, I+2);
1221                 CS_DelEntries (S, I, 2);
1222                 ++Changes;
1223                 --I;    /* Correct for one entry less */
1224             }
1225         }
1226
1227         /* Next entry */
1228         ++I;
1229     }
1230
1231     /* Return the number of changes made */
1232     return Changes;
1233 }
1234
1235
1236
1237 unsigned OptTransfers3 (CodeSeg* S)
1238 /* Replace a register transfer followed by a store of the second register by a
1239  * store of the first register if this is possible.
1240  */
1241 {
1242     unsigned Changes      = 0;
1243     unsigned Xfer         = 0;  /* Index of transfer insn */
1244     unsigned Store        = 0;  /* Index of store insn */
1245     CodeEntry* XferEntry  = 0;  /* Pointer to xfer insn */
1246     CodeEntry* StoreEntry = 0;  /* Pointer to store insn */
1247
1248     enum {
1249         Searching,
1250         FoundXfer,
1251         FoundStore
1252     } State = Searching;
1253
1254     /* Walk over the entries. Look for a xfer instruction that is followed by
1255      * a store later, where the value of the register is not used later.
1256      */
1257     unsigned I = 0;
1258     while (I < CS_GetEntryCount (S)) {
1259
1260         /* Get next entry */
1261         CodeEntry* E = CS_GetEntry (S, I);
1262
1263         switch (State) {
1264
1265             case Searching:
1266                 if (E->Info & OF_XFR) {
1267                     /* Found start of sequence */
1268                     Xfer = I;
1269                     XferEntry = E;
1270                     State = FoundXfer;
1271                 }
1272                 break;
1273
1274             case FoundXfer:
1275                 /* If we find a conditional jump, abort the sequence, since
1276                  * handling them makes things really complicated.
1277                  */
1278                 if (E->Info & OF_CBRA) {
1279
1280                     /* Switch back to searching */
1281                     I = Xfer;
1282                     State = Searching;
1283
1284                 /* Does this insn use the target register of the transfer? */
1285                 } else if ((E->Use & XferEntry->Chg) != 0) {
1286
1287                     /* It it's a store instruction, and the block is a basic
1288                      * block, proceed. Otherwise restart
1289                      */
1290                     if ((E->Info & OF_STORE) != 0       &&
1291                         CS_IsBasicBlock (S, Xfer, I)) {
1292                         Store = I;
1293                         StoreEntry = E;
1294                         State = FoundStore;
1295                     } else {
1296                         I = Xfer;
1297                         State = Searching;
1298                     }
1299
1300                 /* Does this insn change the target register of the transfer? */
1301                 } else if (E->Chg & XferEntry->Chg) {
1302
1303                     /* We *may* add code here to remove the transfer, but I'm
1304                      * currently not sure about the consequences, so I won't
1305                      * do that and bail out instead.
1306                      */
1307                     I = Xfer;
1308                     State = Searching;
1309                 }
1310                 break;
1311
1312             case FoundStore:
1313                 /* We are at the instruction behind the store. If the register
1314                  * isn't used later, and we have an address mode match, we can
1315                  * replace the transfer by a store and remove the store here.
1316                  */
1317                 if ((GetRegInfo (S, I, XferEntry->Chg) & XferEntry->Chg) == 0   &&
1318                     (StoreEntry->AM == AM65_ABS || StoreEntry->AM == AM65_ZP)   &&
1319                     !MemAccess (S, Xfer+1, Store-1, E->Arg)) {
1320
1321                     /* Generate the replacement store insn */
1322                     CodeEntry* X = 0;
1323                     switch (XferEntry->OPC) {
1324
1325                         case OP65_TXA:
1326                             X = NewCodeEntry (OP65_STX,
1327                                               StoreEntry->AM,
1328                                               StoreEntry->Arg,
1329                                               0,
1330                                               StoreEntry->LI);
1331                             break;
1332
1333                         case OP65_TAX:
1334                             X = NewCodeEntry (OP65_STA,
1335                                               StoreEntry->AM,
1336                                               StoreEntry->Arg,
1337                                               0,
1338                                               StoreEntry->LI);
1339                             break;
1340
1341                         case OP65_TYA:
1342                             X = NewCodeEntry (OP65_STY,
1343                                               StoreEntry->AM,
1344                                               StoreEntry->Arg,
1345                                               0,
1346                                               StoreEntry->LI);
1347                             break;
1348
1349                         case OP65_TAY:
1350                             X = NewCodeEntry (OP65_STA,
1351                                               StoreEntry->AM,
1352                                               StoreEntry->Arg,
1353                                               0,
1354                                               StoreEntry->LI);
1355                             break;
1356
1357                         default:
1358                             break;
1359                     }
1360
1361                     /* If we have a replacement store, change the code */
1362                     if (X) {
1363                         /* Insert before the xfer insn */
1364                         CS_InsertEntry (S, X, Xfer);
1365
1366                         /* Remove the xfer instead */
1367                         CS_DelEntry (S, Xfer+1);
1368
1369                         /* Remove the final store */
1370                         CS_DelEntry (S, Store);
1371
1372                         /* Correct I so we continue with the next insn */
1373                         I -= 2;
1374
1375                         /* Remember we had changes */
1376                         ++Changes;
1377                     } else {
1378                         /* Restart after last xfer insn */
1379                         I = Xfer;
1380                     }
1381                 } else {
1382                     /* Restart after last xfer insn */
1383                     I = Xfer;
1384                 }
1385                 State = Searching;
1386                 break;
1387
1388         }
1389
1390         /* Next entry */
1391         ++I;
1392     }
1393
1394     /* Return the number of changes made */
1395     return Changes;
1396 }
1397
1398
1399
1400 unsigned OptTransfers4 (CodeSeg* S)
1401 /* Replace a load of a register followed by a transfer insn of the same register
1402  * by a load of the second register if possible.
1403  */
1404 {
1405     unsigned Changes      = 0;
1406     unsigned Load         = 0;  /* Index of load insn */
1407     unsigned Xfer         = 0;  /* Index of transfer insn */
1408     CodeEntry* LoadEntry  = 0;  /* Pointer to load insn */
1409     CodeEntry* XferEntry  = 0;  /* Pointer to xfer insn */
1410
1411     enum {
1412         Searching,
1413         FoundLoad,
1414         FoundXfer
1415     } State = Searching;
1416
1417     /* Walk over the entries. Look for a load instruction that is followed by
1418      * a load later.
1419      */
1420     unsigned I = 0;
1421     while (I < CS_GetEntryCount (S)) {
1422
1423         /* Get next entry */
1424         CodeEntry* E = CS_GetEntry (S, I);
1425
1426         switch (State) {
1427
1428             case Searching:
1429                 if (E->Info & OF_LOAD) {
1430                     /* Found start of sequence */
1431                     Load = I;
1432                     LoadEntry = E;
1433                     State = FoundLoad;
1434                 }
1435                 break;
1436
1437             case FoundLoad:
1438                 /* If we find a conditional jump, abort the sequence, since
1439                  * handling them makes things really complicated.
1440                  */
1441                 if (E->Info & OF_CBRA) {
1442
1443                     /* Switch back to searching */
1444                     I = Load;
1445                     State = Searching;
1446
1447                 /* Does this insn use the target register of the load? */
1448                 } else if ((E->Use & LoadEntry->Chg) != 0) {
1449
1450                     /* It it's a xfer instruction, and the block is a basic
1451                      * block, proceed. Otherwise restart
1452                      */
1453                     if ((E->Info & OF_XFR) != 0       &&
1454                         CS_IsBasicBlock (S, Load, I)) {
1455                         Xfer = I;
1456                         XferEntry = E;
1457                         State = FoundXfer;
1458                     } else {
1459                         I = Load;
1460                         State = Searching;
1461                     }
1462
1463                 /* Does this insn change the target register of the load? */
1464                 } else if (E->Chg & LoadEntry->Chg) {
1465
1466                     /* We *may* add code here to remove the load, but I'm
1467                      * currently not sure about the consequences, so I won't
1468                      * do that and bail out instead.
1469                      */
1470                     I = Load;
1471                     State = Searching;
1472                 }
1473                 break;
1474
1475             case FoundXfer:
1476                 /* We are at the instruction behind the xfer. If the register
1477                  * isn't used later, and we have an address mode match, we can
1478                  * replace the transfer by a load and remove the initial load.
1479                  */
1480                 if ((GetRegInfo (S, I, LoadEntry->Chg) & LoadEntry->Chg) == 0   &&
1481                     (LoadEntry->AM == AM65_ABS || LoadEntry->AM == AM65_ZP)   &&
1482                     !MemAccess (S, Load+1, Xfer-1, E->Arg)) {
1483
1484                     /* Generate the replacement load insn */
1485                     CodeEntry* X = 0;
1486                     switch (XferEntry->OPC) {
1487
1488                         case OP65_TXA:
1489                         case OP65_TYA:
1490                             X = NewCodeEntry (OP65_LDA,
1491                                               LoadEntry->AM,
1492                                               LoadEntry->Arg,
1493                                               0,
1494                                               LoadEntry->LI);
1495                             break;
1496
1497                         case OP65_TAX:
1498                             X = NewCodeEntry (OP65_LDX,
1499                                               LoadEntry->AM,
1500                                               LoadEntry->Arg,
1501                                               0,
1502                                               LoadEntry->LI);
1503                             break;
1504
1505                         case OP65_TAY:
1506                             X = NewCodeEntry (OP65_LDY,
1507                                               LoadEntry->AM,
1508                                               LoadEntry->Arg,
1509                                               0,
1510                                               LoadEntry->LI);
1511                             break;
1512
1513                         default:
1514                             break;
1515                     }
1516
1517                     /* If we have a replacement load, change the code */
1518                     if (X) {
1519                         /* Insert before the xfer insn */
1520                         CS_InsertEntry (S, X, Xfer);
1521
1522                         /* Remove the xfer instead */
1523                         CS_DelEntry (S, Xfer+1);
1524
1525                         /* Remove the initial load */
1526                         CS_DelEntry (S, Load);
1527
1528                         /* Correct I so we continue with the next insn */
1529                         I -= 2;
1530
1531                         /* Remember we had changes */
1532                         ++Changes;
1533                     } else {
1534                         /* Restart after last xfer insn */
1535                         I = Xfer;
1536                     }
1537                 } else {
1538                     /* Restart after last xfer insn */
1539                     I = Xfer;
1540                 }
1541                 State = Searching;
1542                 break;
1543
1544         }
1545
1546         /* Next entry */
1547         ++I;
1548     }
1549
1550     /* Return the number of changes made */
1551     return Changes;
1552 }
1553
1554
1555
1556 unsigned OptPushPop (CodeSeg* S)
1557 /* Remove a PHA/PLA sequence were A is not used later */
1558 {
1559     unsigned Changes = 0;
1560     unsigned Push    = 0;       /* Index of push insn */
1561     unsigned Pop     = 0;       /* Index of pop insn */
1562     enum {
1563         Searching,
1564         FoundPush,
1565         FoundPop
1566     } State = Searching;
1567
1568     /* Walk over the entries. Look for a push instruction that is followed by
1569      * a pop later, where the pop is not followed by an conditional branch,
1570      * and where the value of the A register is not used later on.
1571      * Look out for the following problems:
1572      *
1573      *  - There may be another PHA/PLA inside the sequence: Restart it.
1574      *  - If the PLA has a label, all jumps to this label must be inside
1575      *    the sequence, otherwise we cannot remove the PHA/PLA.
1576      */
1577     unsigned I = 0;
1578     while (I < CS_GetEntryCount (S)) {
1579
1580         CodeEntry* X;
1581
1582         /* Get next entry */
1583         CodeEntry* E = CS_GetEntry (S, I);
1584
1585         switch (State) {
1586
1587             case Searching:
1588                 if (E->OPC == OP65_PHA) {
1589                     /* Found start of sequence */
1590                     Push  = I;
1591                     State = FoundPush;
1592                 }
1593                 break;
1594
1595             case FoundPush:
1596                 if (E->OPC == OP65_PHA) {
1597                     /* Inner push/pop, restart */
1598                     Push = I;
1599                 } else if (E->OPC == OP65_PLA) {
1600                     /* Found a matching pop */
1601                     Pop = I;
1602                     /* Check that the block between Push and Pop is a basic
1603                      * block (one entry, one exit). Otherwise ignore it.
1604                      */
1605                     if (CS_IsBasicBlock (S, Push, Pop)) {
1606                         State = FoundPop;
1607                     } else {
1608                         /* Go into searching mode again */
1609                         State = Searching;
1610                     }
1611                 }
1612                 break;
1613
1614             case FoundPop:
1615                 /* We're at the instruction after the PLA.
1616                  * Check for the following conditions:
1617                  *   - If this instruction is a store of A, and A is not used
1618                  *     later, we may replace the PHA by the store and remove
1619                  *     pla if several other conditions are met.
1620                  *   - If this instruction is not a conditional branch, and A
1621                  *     is unused later, we may remove PHA and PLA.
1622                  */
1623                 if (E->OPC == OP65_STA                  &&
1624                     !RegAUsed (S, I+1)                  &&
1625                     !MemAccess (S, Push+1, Pop-1, E->Arg)) {
1626
1627                     /* Insert a STA before the PHA */
1628                     X = NewCodeEntry (E->OPC, E->AM, E->Arg, E->JumpTo, E->LI);
1629                     CS_InsertEntry (S, X, Push);
1630
1631                     /* Remove the PHA instead */
1632                     CS_DelEntry (S, Push+1);
1633
1634                     /* Remove the PLA/STA sequence */
1635                     CS_DelEntries (S, Pop, 2);
1636
1637                     /* Correct I so we continue with the next insn */
1638                     I -= 2;
1639
1640                     /* Remember we had changes */
1641                     ++Changes;
1642
1643                 } else if ((E->Info & OF_CBRA) == 0     &&
1644                            !RegAUsed (S, I)) {
1645
1646                     /* We can remove the PHA and PLA instructions */
1647                     CS_DelEntry (S, Pop);
1648                     CS_DelEntry (S, Push);
1649
1650                     /* Correct I so we continue with the next insn */
1651                     I -= 2;
1652
1653                     /* Remember we had changes */
1654                     ++Changes;
1655
1656                 }
1657                 /* Go into search mode again */
1658                 State = Searching;
1659                 break;
1660
1661         }
1662
1663         /* Next entry */
1664         ++I;
1665     }
1666
1667     /* Return the number of changes made */
1668     return Changes;
1669 }
1670
1671
1672
1673 unsigned OptPrecalc (CodeSeg* S)
1674 /* Replace immediate operations with the accu where the current contents are
1675  * known by a load of the final value.
1676  */
1677 {
1678     unsigned Changes = 0;
1679     unsigned I;
1680
1681     /* Generate register info for this step */
1682     CS_GenRegInfo (S);
1683
1684     /* Walk over the entries */
1685     I = 0;
1686     while (I < CS_GetEntryCount (S)) {
1687
1688         /* Get next entry */
1689         CodeEntry* E = CS_GetEntry (S, I);
1690
1691         /* Get a pointer to the output registers of the insn */
1692         const RegContents* Out = &E->RI->Out;
1693
1694         /* Argument for LDn and flag */
1695         const char* Arg = 0;
1696         opc_t OPC = OP65_LDA;
1697
1698         /* Handle the different instructions */
1699         switch (E->OPC) {
1700
1701             case OP65_LDA:
1702                 if (E->AM != AM65_IMM && RegValIsKnown (Out->RegA)) {
1703                     /* Result of load is known */
1704                     Arg = MakeHexArg (Out->RegA);
1705                 }
1706                 break;
1707
1708             case OP65_LDX:
1709                 if (E->AM != AM65_IMM && RegValIsKnown (Out->RegX)) {
1710                     /* Result of load is known but register is X */
1711                     Arg = MakeHexArg (Out->RegX);
1712                     OPC = OP65_LDX;
1713                 }
1714                 break;
1715
1716             case OP65_LDY:
1717                 if (E->AM != AM65_IMM && RegValIsKnown (Out->RegY)) {
1718                     /* Result of load is known but register is Y */
1719                     Arg = MakeHexArg (Out->RegY);
1720                     OPC = OP65_LDY;
1721                 }
1722                 break;
1723
1724             case OP65_ADC:
1725             case OP65_ASL:
1726             case OP65_EOR:
1727             case OP65_LSR:
1728             case OP65_SBC:
1729                 if (RegValIsKnown (Out->RegA)) {
1730                     /* Accu op zp with known contents */
1731                     Arg = MakeHexArg (Out->RegA);
1732                 }
1733                 break;
1734
1735             case OP65_AND:
1736                 if (CE_IsKnownImm (E, 0xFF)) {
1737                     /* AND with 0xFF, remove */
1738                     CS_DelEntry (S, I);
1739                     ++Changes;
1740                 } else if (RegValIsKnown (Out->RegA)) {
1741                     /* Accu AND zp with known contents */
1742                     Arg = MakeHexArg (Out->RegA);
1743                 }
1744                 break;
1745
1746             case OP65_ORA:
1747                 if (CE_IsKnownImm (E, 0x00)) {
1748                     /* ORA with zero, remove */
1749                     CS_DelEntry (S, I);
1750                     ++Changes;
1751                 } else if (RegValIsKnown (Out->RegA)) {
1752                     /* Accu AND zp with known contents */
1753                     Arg = MakeHexArg (Out->RegA);
1754                 }
1755                 break;
1756
1757             default:
1758                 break;
1759
1760         }
1761
1762         /* Check if we have to replace the insn by LDA */
1763         if (Arg) {
1764             CodeEntry* X = NewCodeEntry (OPC, AM65_IMM, Arg, 0, E->LI);
1765             CS_InsertEntry (S, X, I+1);
1766             CS_DelEntry (S, I);
1767             ++Changes;
1768         }
1769
1770         /* Next entry */
1771         ++I;
1772     }
1773
1774     /* Free register info */
1775     CS_FreeRegInfo (S);
1776
1777     /* Return the number of changes made */
1778     return Changes;
1779 }
1780
1781
1782
1783 /*****************************************************************************/
1784 /*                           Optimize branch types                           */
1785 /*****************************************************************************/
1786
1787
1788
1789 unsigned OptBranchDist (CodeSeg* S)
1790 /* Change branches for the distance needed. */
1791 {
1792     unsigned Changes = 0;
1793
1794     /* Walk over the entries */
1795     unsigned I = 0;
1796     while (I < CS_GetEntryCount (S)) {
1797
1798         /* Get next entry */
1799         CodeEntry* E = CS_GetEntry (S, I);
1800
1801         /* Check if it's a conditional branch to a local label. */
1802         if (E->Info & OF_CBRA) {
1803
1804             /* Is this a branch to a local symbol? */
1805             if (E->JumpTo != 0) {
1806
1807                 /* Check if the branch distance is short */
1808                 int IsShort = IsShortDist (GetBranchDist (S, I, E->JumpTo->Owner));
1809
1810                 /* Make the branch short/long according to distance */
1811                 if ((E->Info & OF_LBRA) == 0 && !IsShort) {
1812                     /* Short branch but long distance */
1813                     CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1814                     ++Changes;
1815                 } else if ((E->Info & OF_LBRA) != 0 && IsShort) {
1816                     /* Long branch but short distance */
1817                     CE_ReplaceOPC (E, MakeShortBranch (E->OPC));
1818                     ++Changes;
1819                 }
1820
1821             } else if ((E->Info & OF_LBRA) == 0) {
1822
1823                 /* Short branch to external symbol - make it long */
1824                 CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1825                 ++Changes;
1826
1827             }
1828
1829         } else if ((CPUIsets[CPU] & CPU_ISET_65SC02) != 0 &&
1830                    (E->Info & OF_UBRA) != 0               &&
1831                    E->JumpTo != 0                         &&
1832                    IsShortDist (GetBranchDist (S, I, E->JumpTo->Owner))) {
1833
1834             /* The jump is short and may be replaced by a BRA on the 65C02 CPU */
1835             CE_ReplaceOPC (E, OP65_BRA);
1836             ++Changes;
1837         }
1838
1839         /* Next entry */
1840         ++I;
1841
1842     }
1843
1844     /* Return the number of changes made */
1845     return Changes;
1846 }
1847
1848
1849