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-2003 Ullrich von Bassewitz                                       */
  10 /*               Römerstrasse 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 GetBranchDist (CodeSeg* S, unsigned From, CodeEntry* To)
  55 /* Get the branch distance between the two entries and return it. The distance
  56  * will be negative for backward jumps and positive for forward jumps.
  57  */
  58 {
  59     /* Get the index of the branch target */
  60     unsigned TI = CS_GetEntryIndex (S, To);
  61
  62     /* Determine the branch distance */
  63     int Distance = 0;
  64     if (TI >= From) {
  65         /* Forward branch, do not count the current insn */
  66         unsigned J = From+1;
  67         while (J < TI) {
  68             CodeEntry* N = CS_GetEntry (S, J++);
  69             Distance += N->Size;
  70         }
  71     } else {
  72         /* Backward branch */
  73         unsigned J = TI;
  74         while (J < From) {
  75             CodeEntry* N = CS_GetEntry (S, J++);
  76             Distance -= N->Size;
  77         }
  78     }
  79
  80     /* Return the calculated distance */
  81     return Distance;
  82 }
  83
  84
  85
  86 static int IsShortDist (int Distance)
  87 /* Return true if the given distance is a short branch distance */
  88 {
  89     return (Distance >= -125 && Distance <= 125);
  90 }
  91
  92
  93
  94 static short ZPRegVal (unsigned short Use, const RegContents* RC)
  95 /* Return the contents of the given zeropage register */
  96 {
  97     if ((Use & REG_TMP1) != 0) {
  98         return RC->Tmp1;
  99     } else if ((Use & REG_PTR1_LO) != 0) {
 100         return RC->Ptr1Lo;
 101     } else if ((Use & REG_PTR1_HI) != 0) {
 102         return RC->Ptr1Hi;
 103     } else if ((Use & REG_SREG_LO) != 0) {
 104         return RC->SRegLo;
 105     } else if ((Use & REG_SREG_HI) != 0) {
 106         return RC->SRegHi;
 107     } else {
 108         return UNKNOWN_REGVAL;
 109     }
 110 }
 111
 112
 113
 114 static short RegVal (unsigned short Use, const RegContents* RC)
 115 /* Return the contents of the given register */
 116 {
 117     if ((Use & REG_A) != 0) {
 118         return RC->RegA;
 119     } else if ((Use & REG_X) != 0) {
 120         return RC->RegX;
 121     } else if ((Use & REG_Y) != 0) {
 122         return RC->RegY;
 123     } else {
 124         return ZPRegVal (Use, RC);
 125     }
 126 }
 127
 128
 129
 130 /*****************************************************************************/
 131 /*                        Replace jumps to RTS by RTS                        */
 132 /*****************************************************************************/
 133
 134
 135
 136 unsigned OptRTSJumps1 (CodeSeg* S)
 137 /* Replace jumps to RTS by RTS */
 138 {
 139     unsigned Changes = 0;
 140
 141     /* Walk over all entries minus the last one */
 142     unsigned I = 0;
 143     while (I < CS_GetEntryCount (S)) {
 144
 145         /* Get the next entry */
 146         CodeEntry* E = CS_GetEntry (S, I);
 147
 148         /* Check if it's an unconditional branch to a local target */
 149         if ((E->Info & OF_UBRA) != 0            &&
 150             E->JumpTo != 0                      &&
 151             E->JumpTo->Owner->OPC == OP65_RTS) {
 152
 153             /* Insert an RTS instruction */
 154             CodeEntry* X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->LI);
 155             CS_InsertEntry (S, X, I+1);
 156
 157             /* Delete the jump */
 158             CS_DelEntry (S, I);
 159
 160             /* Remember, we had changes */
 161             ++Changes;
 162
 163         }
 164
 165         /* Next entry */
 166         ++I;
 167
 168     }
 169
 170     /* Return the number of changes made */
 171     return Changes;
 172 }
 173
 174
 175
 176 unsigned OptRTSJumps2 (CodeSeg* S)
 177 /* Replace long conditional jumps to RTS */
 178 {
 179     unsigned Changes = 0;
 180
 181     /* Walk over all entries minus the last one */
 182     unsigned I = 0;
 183     while (I < CS_GetEntryCount (S)) {
 184
 185         CodeEntry* N;
 186
 187         /* Get the next entry */
 188         CodeEntry* E = CS_GetEntry (S, I);
 189
 190         /* Check if it's an unconditional branch to a local target */
 191         if ((E->Info & OF_CBRA) != 0            &&   /* Conditional branch */
 192             (E->Info & OF_LBRA) != 0            &&   /* Long branch */
 193             E->JumpTo != 0                      &&   /* Local label */
 194             E->JumpTo->Owner->OPC == OP65_RTS   &&   /* Target is an RTS */
 195             (N = CS_GetNextEntry (S, I)) != 0) {     /* There is a next entry */
 196
 197             CodeEntry* X;
 198             CodeLabel* LN;
 199             opc_t      NewBranch;
 200
 201             /* We will create a jump around an RTS instead of the long branch */
 202             X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->JumpTo->Owner->LI);
 203             CS_InsertEntry (S, X, I+1);
 204
 205             /* Get the new branch opcode */
 206             NewBranch = MakeShortBranch (GetInverseBranch (E->OPC));
 207
 208             /* Get the label attached to N, create a new one if needed */
 209             LN = CS_GenLabel (S, N);
 210
 211             /* Generate the branch */
 212             X = NewCodeEntry (NewBranch, AM65_BRA, LN->Name, LN, E->LI);
 213             CS_InsertEntry (S, X, I+1);
 214
 215             /* Delete the long branch */
 216             CS_DelEntry (S, I);
 217
 218             /* Remember, we had changes */
 219             ++Changes;
 220
 221         }
 222
 223         /* Next entry */
 224         ++I;
 225
 226     }
 227
 228     /* Return the number of changes made */
 229     return Changes;
 230 }
 231
 232
 233
 234 /*****************************************************************************/
 235 /*                             Remove dead jumps                             */
 236 /*****************************************************************************/
 237
 238
 239
 240 unsigned OptDeadJumps (CodeSeg* S)
 241 /* Remove dead jumps (jumps to the next instruction) */
 242 {
 243     unsigned Changes = 0;
 244
 245     /* Walk over all entries minus the last one */
 246     unsigned I = 0;
 247     while (I < CS_GetEntryCount (S)) {
 248
 249         /* Get the next entry */
 250         CodeEntry* E = CS_GetEntry (S, I);
 251
 252         /* Check if it's a branch, if it has a local target, and if the target
 253          * is the next instruction.
 254          */
 255         if (E->AM == AM65_BRA                               &&
 256             E->JumpTo                                       &&
 257             E->JumpTo->Owner == CS_GetNextEntry (S, I)) {
 258
 259             /* Delete the dead jump */
 260             CS_DelEntry (S, I);
 261
 262             /* Remember, we had changes */
 263             ++Changes;
 264
 265         } else {
 266
 267             /* Next entry */
 268             ++I;
 269
 270         }
 271     }
 272
 273     /* Return the number of changes made */
 274     return Changes;
 275 }
 276
 277
 278
 279 /*****************************************************************************/
 280 /*                             Remove dead code                              */
 281 /*****************************************************************************/
 282
 283
 284
 285 unsigned OptDeadCode (CodeSeg* S)
 286 /* Remove dead code (code that follows an unconditional jump or an rts/rti
 287  * and has no label)
 288  */
 289 {
 290     unsigned Changes = 0;
 291
 292     /* Walk over all entries */
 293     unsigned I = 0;
 294     while (I < CS_GetEntryCount (S)) {
 295
 296         CodeEntry* N;
 297         CodeLabel* LN;
 298
 299         /* Get this entry */
 300         CodeEntry* E = CS_GetEntry (S, I);
 301
 302         /* Check if it's an unconditional branch, and if the next entry has
 303          * no labels attached, or if the label is just used so that the insn
 304          * can jump to itself.
 305          */
 306         if ((E->Info & OF_DEAD) != 0                     &&     /* Dead code follows */
 307             (N = CS_GetNextEntry (S, I)) != 0            &&     /* Has next entry */
 308             (!CE_HasLabel (N)                        ||         /* Don't has a label */
 309              ((N->Info & OF_UBRA) != 0          &&              /* Uncond branch */
 310               (LN = N->JumpTo) != 0             &&              /* Jumps to known label */
 311               LN->Owner == N                    &&              /* Attached to insn */
 312               CL_GetRefCount (LN) == 1))) {                     /* Only reference */
 313
 314             /* Delete the next entry */
 315             CS_DelEntry (S, I+1);
 316
 317             /* Remember, we had changes */
 318             ++Changes;
 319
 320         } else {
 321
 322             /* Next entry */
 323             ++I;
 324
 325         }
 326     }
 327
 328     /* Return the number of changes made */
 329     return Changes;
 330 }
 331
 332
 333
 334 /*****************************************************************************/
 335 /*                          Optimize jump cascades                           */
 336 /*****************************************************************************/
 337
 338
 339
 340 unsigned OptJumpCascades (CodeSeg* S)
 341 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
 342  * replaced by a jump to the final location. This will in some cases produce
 343  * worse code, because some jump targets are no longer reachable by short
 344  * branches, but this is quite rare, so there are more advantages than
 345  * disadvantages.
 346  */
 347 {
 348     unsigned Changes = 0;
 349
 350     /* Walk over all entries */
 351     unsigned I = 0;
 352     while (I < CS_GetEntryCount (S)) {
 353
 354         CodeEntry* N;
 355         CodeLabel* OldLabel;
 356
 357         /* Get this entry */
 358         CodeEntry* E = CS_GetEntry (S, I);
 359
 360         /* Check if it's a branch, if it has a jump label, if this jump
 361          * label is not attached to the instruction itself, and if the
 362          * target instruction is itself a branch.
 363          */
 364         if ((E->Info & OF_BRA) != 0        &&
 365             (OldLabel = E->JumpTo) != 0    &&
 366             (N = OldLabel->Owner) != E     &&
 367             (N->Info & OF_BRA) != 0) {
 368
 369             /* Check if we can use the final target label. This is the case,
 370              * if the target branch is an absolut branch, or if it is a
 371              * conditional branch checking the same condition as the first one.
 372              */
 373             if ((N->Info & OF_UBRA) != 0 ||
 374                 ((E->Info & OF_CBRA) != 0 &&
 375                  GetBranchCond (E->OPC)  == GetBranchCond (N->OPC))) {
 376
 377                 /* This is a jump cascade and we may jump to the final target,
 378                  * provided that the other insn does not jump to itself. If
 379                  * this is the case, we can also jump to ourselves, otherwise
 380                  * insert a jump to the new instruction and remove the old one.
 381                  */
 382                 CodeEntry* X;
 383                 CodeLabel* LN = N->JumpTo;
 384
 385                 if (LN != 0 && LN->Owner == N) {
 386
 387                     /* We found a jump to a jump to itself. Replace our jump
 388                      * by a jump to itself.
 389                      */
 390                     CodeLabel* LE = CS_GenLabel (S, E);
 391                     X = NewCodeEntry (E->OPC, E->AM, LE->Name, LE, E->LI);
 392
 393                 } else {
 394
 395                     /* Jump to the final jump target */
 396                     X = NewCodeEntry (E->OPC, E->AM, N->Arg, N->JumpTo, E->LI);
 397
 398                 }
 399
 400                 /* Insert it behind E */
 401                 CS_InsertEntry (S, X, I+1);
 402
 403                 /* Remove E */
 404                 CS_DelEntry (S, I);
 405
 406                 /* Remember, we had changes */
 407                 ++Changes;
 408
 409                 /* Done */
 410                 continue;
 411
 412             }
 413
 414             /* Check if both are conditional branches, and the condition of
 415              * the second is the inverse of that of the first. In this case,
 416              * the second branch will never be taken, and we may jump directly
 417              * to the instruction behind this one.
 418              */
 419             if ((E->Info & OF_CBRA) != 0 && (N->Info & OF_CBRA) != 0) {
 420
 421                 CodeEntry* X;   /* Instruction behind N */
 422                 CodeLabel* LX;  /* Label attached to X */
 423
 424                 /* Get the branch conditions of both branches */
 425                 bc_t BC1 = GetBranchCond (E->OPC);
 426                 bc_t BC2 = GetBranchCond (N->OPC);
 427
 428                 /* Check the branch conditions */
 429                 if (BC1 != GetInverseCond (BC2)) {
 430                     /* Condition not met */
 431                     goto NextEntry;
 432                 }
 433
 434                 /* We may jump behind this conditional branch. Get the
 435                  * pointer to the next instruction
 436                  */
 437                 if ((X = CS_GetNextEntry (S, CS_GetEntryIndex (S, N))) == 0) {
 438                     /* N is the last entry, bail out */
 439                     goto NextEntry;
 440                 }
 441
 442                 /* Get the label attached to X, create a new one if needed */
 443                 LX = CS_GenLabel (S, X);
 444
 445                 /* Move the reference from E to the new label */
 446                 CS_MoveLabelRef (S, E, LX);
 447
 448                 /* Remember, we had changes */
 449                 ++Changes;
 450
 451                 /* Done */
 452                 continue;
 453
 454             }
 455         }
 456
 457 NextEntry:
 458         /* Next entry */
 459         ++I;
 460
 461     }
 462
 463     /* Return the number of changes made */
 464     return Changes;
 465 }
 466
 467
 468
 469 /*****************************************************************************/
 470 /*                             Optimize jsr/rts                              */
 471 /*****************************************************************************/
 472
 473
 474
 475 unsigned OptRTS (CodeSeg* S)
 476 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
 477  * replaced by a jump. Don't bother to delete the RTS if it does not have a
 478  * label, the dead code elimination should take care of it.
 479  */
 480 {
 481     unsigned Changes = 0;
 482
 483     /* Walk over all entries minus the last one */
 484     unsigned I = 0;
 485     while (I < CS_GetEntryCount (S)) {
 486
 487         CodeEntry* N;
 488
 489         /* Get this entry */
 490         CodeEntry* E = CS_GetEntry (S, I);
 491
 492         /* Check if it's a subroutine call and if the following insn is RTS */
 493         if (E->OPC == OP65_JSR                    &&
 494             (N = CS_GetNextEntry (S, I)) != 0 &&
 495             N->OPC == OP65_RTS) {
 496
 497             /* Change the jsr to a jmp and use the additional info for a jump */
 498             E->AM = AM65_BRA;
 499             CE_ReplaceOPC (E, OP65_JMP);
 500
 501             /* Remember, we had changes */
 502             ++Changes;
 503
 504         }
 505
 506         /* Next entry */
 507         ++I;
 508
 509     }
 510
 511     /* Return the number of changes made */
 512     return Changes;
 513 }
 514
 515
 516
 517 /*****************************************************************************/
 518 /*                           Optimize jump targets                           */
 519 /*****************************************************************************/
 520
 521
 522
 523 unsigned OptJumpTarget (CodeSeg* S)
 524 /* If the instruction preceeding an unconditional branch is the same as the
 525  * instruction preceeding the jump target, the jump target may be moved
 526  * one entry back. This is a size optimization, since the instruction before
 527  * the branch gets removed.
 528  */
 529 {
 530     unsigned Changes = 0;
 531     CodeEntry* E1;              /* Entry 1 */
 532     CodeEntry* E2;              /* Entry 2 */
 533     CodeEntry* T1;              /* Jump target entry 1 */
 534     CodeLabel* TL1;             /* Target label 1 */
 535
 536     /* Walk over the entries */
 537     unsigned I = 0;
 538     while (I < CS_GetEntryCount (S)) {
 539
 540         /* Get next entry */
 541         E2 = CS_GetNextEntry (S, I);
 542
 543         /* Check if we have a jump or branch, and a matching label, which
 544          * is not attached to the jump itself
 545          */
 546         if (E2 != 0                     &&
 547             (E2->Info & OF_UBRA) != 0   &&
 548             E2->JumpTo                  &&
 549             E2->JumpTo->Owner != E2) {
 550
 551             /* Get the entry preceeding the branch target */
 552             T1 = CS_GetPrevEntry (S, CS_GetEntryIndex (S, E2->JumpTo->Owner));
 553             if (T1 == 0) {
 554                 /* There is no such entry */
 555                 goto NextEntry;
 556             }
 557
 558             /* Get the entry preceeding the jump */
 559             E1 = CS_GetEntry (S, I);
 560
 561             /* Check if both preceeding instructions are identical */
 562             if (!CodeEntriesAreEqual (E1, T1)) {
 563                 /* Not equal, try next */
 564                 goto NextEntry;
 565             }
 566
 567             /* Get the label for the instruction preceeding the jump target.
 568              * This routine will create a new label if the instruction does
 569              * not already have one.
 570              */
 571             TL1 = CS_GenLabel (S, T1);
 572
 573             /* Change the jump target to point to this new label */
 574             CS_MoveLabelRef (S, E2, TL1);
 575
 576             /* If the instruction preceeding the jump has labels attached,
 577              * move references to this label to the new label.
 578              */
 579             if (CE_HasLabel (E1)) {
 580                 CS_MoveLabels (S, E1, T1);
 581             }
 582
 583             /* Remove the entry preceeding the jump */
 584             CS_DelEntry (S, I);
 585
 586             /* Remember, we had changes */
 587             ++Changes;
 588
 589         }
 590
 591 NextEntry:
 592         /* Next entry */
 593         ++I;
 594
 595     }
 596
 597     /* Return the number of changes made */
 598     return Changes;
 599 }
 600
 601
 602
 603 /*****************************************************************************/
 604 /*                       Optimize conditional branches                       */
 605 /*****************************************************************************/
 606
 607
 608
 609 unsigned OptCondBranches (CodeSeg* S)
 610 /* Performs several optimization steps:
 611  *
 612  *  - If an immidiate load of a register is followed by a conditional jump that
 613  *    is never taken because the load of the register sets the flags in such a
 614  *    manner, remove the conditional branch.
 615  *  - If the conditional branch is always taken because of the register load,
 616  *    replace it by a jmp.
 617  *  - If a conditional branch jumps around an unconditional branch, remove the
 618  *    conditional branch and make the jump a conditional branch with the
 619  *    inverse condition of the first one.
 620  */
 621 {
 622     unsigned Changes = 0;
 623
 624     /* Walk over the entries */
 625     unsigned I = 0;
 626     while (I < CS_GetEntryCount (S)) {
 627
 628         CodeEntry* N;
 629         CodeLabel* L;
 630
 631         /* Get next entry */
 632         CodeEntry* E = CS_GetEntry (S, I);
 633
 634         /* Check if it's a register load */
 635         if ((E->Info & OF_LOAD) != 0              &&  /* It's a load instruction */
 636             E->AM == AM65_IMM                     &&  /* ..with immidiate addressing */
 637             (E->Flags & CEF_NUMARG) != 0          &&  /* ..and a numeric argument. */
 638             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 639             (N->Info & OF_CBRA) != 0              &&  /* ..which is a conditional branch */
 640             !CE_HasLabel (N)) {               /* ..and does not have a label */
 641
 642             /* Get the branch condition */
 643             bc_t BC = GetBranchCond (N->OPC);
 644
 645             /* Check the argument against the branch condition */
 646             if ((BC == BC_EQ && E->Num != 0)            ||
 647                 (BC == BC_NE && E->Num == 0)            ||
 648                 (BC == BC_PL && (E->Num & 0x80) != 0)   ||
 649                 (BC == BC_MI && (E->Num & 0x80) == 0)) {
 650
 651                 /* Remove the conditional branch */
 652                 CS_DelEntry (S, I+1);
 653
 654                 /* Remember, we had changes */
 655                 ++Changes;
 656
 657             } else if ((BC == BC_EQ && E->Num == 0)             ||
 658                        (BC == BC_NE && E->Num != 0)             ||
 659                        (BC == BC_PL && (E->Num & 0x80) == 0)    ||
 660                        (BC == BC_MI && (E->Num & 0x80) != 0)) {
 661
 662                 /* The branch is always taken, replace it by a jump */
 663                 CE_ReplaceOPC (N, OP65_JMP);
 664
 665                 /* Remember, we had changes */
 666                 ++Changes;
 667             }
 668
 669         }
 670
 671         if ((E->Info & OF_CBRA) != 0              &&  /* It's a conditional branch */
 672             (L = E->JumpTo) != 0                  &&  /* ..referencing a local label */
 673             (N = CS_GetNextEntry (S, I)) != 0     &&  /* There is a following entry */
 674             (N->Info & OF_UBRA) != 0              &&  /* ..which is an uncond branch, */
 675             !CE_HasLabel (N)                      &&  /* ..has no label attached */
 676             L->Owner == CS_GetNextEntry (S, I+1)) {/* ..and jump target follows */
 677
 678             /* Replace the jump by a conditional branch with the inverse branch
 679              * condition than the branch around it.
 680              */
 681             CE_ReplaceOPC (N, GetInverseBranch (E->OPC));
 682
 683             /* Remove the conditional branch */
 684             CS_DelEntry (S, I);
 685
 686             /* Remember, we had changes */
 687             ++Changes;
 688
 689         }
 690
 691         /* Next entry */
 692         ++I;
 693
 694     }
 695
 696     /* Return the number of changes made */
 697     return Changes;
 698 }
 699
 700
 701
 702 /*****************************************************************************/
 703 /*                      Remove unused loads and stores                       */
 704 /*****************************************************************************/
 705
 706
 707
 708 unsigned OptUnusedLoads (CodeSeg* S)
 709 /* Remove loads of registers where the value loaded is not used later. */
 710 {
 711     unsigned Changes = 0;
 712
 713     /* Walk over the entries */
 714     unsigned I = 0;
 715     while (I < CS_GetEntryCount (S)) {
 716
 717         CodeEntry* N;
 718
 719         /* Get next entry */
 720         CodeEntry* E = CS_GetEntry (S, I);
 721
 722         /* Check if it's a register load or transfer insn */
 723         if ((E->Info & (OF_LOAD | OF_XFR | OF_REG_INCDEC)) != 0         &&
 724             (N = CS_GetNextEntry (S, I)) != 0                           &&
 725             !CE_UseLoadFlags (N)) {
 726
 727             /* Check which sort of load or transfer it is */
 728             unsigned R;
 729             switch (E->OPC) {
 730                 case OP65_DEA:
 731                 case OP65_INA:
 732                 case OP65_LDA:
 733                 case OP65_TXA:
 734                 case OP65_TYA:  R = REG_A;      break;
 735                 case OP65_DEX:
 736                 case OP65_INX:
 737                 case OP65_LDX:
 738                 case OP65_TAX:  R = REG_X;      break;
 739                 case OP65_DEY:
 740                 case OP65_INY:
 741                 case OP65_LDY:
 742                 case OP65_TAY:  R = REG_Y;      break;
 743                 default:        goto NextEntry;         /* OOPS */
 744             }
 745
 746             /* Get register usage and check if the register value is used later */
 747             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 748
 749                 /* Register value is not used, remove the load */
 750                 CS_DelEntry (S, I);
 751
 752                 /* Remember, we had changes */
 753                 ++Changes;
 754
 755             }
 756         }
 757
 758 NextEntry:
 759         /* Next entry */
 760         ++I;
 761
 762     }
 763
 764     /* Return the number of changes made */
 765     return Changes;
 766 }
 767
 768
 769
 770 unsigned OptUnusedStores (CodeSeg* S)
 771 /* Remove stores into zero page registers that aren't used later */
 772 {
 773     unsigned Changes = 0;
 774
 775     /* Walk over the entries */
 776     unsigned I = 0;
 777     while (I < CS_GetEntryCount (S)) {
 778
 779         /* Get next entry */
 780         CodeEntry* E = CS_GetEntry (S, I);
 781
 782         /* Check if it's a register load or transfer insn */
 783         if ((E->Info & OF_STORE) != 0    &&
 784             E->AM == AM65_ZP             &&
 785             (E->Chg & REG_ZP) != 0) {
 786
 787             /* Check for the zero page location. We know that there cannot be
 788              * more than one zero page location involved in the store.
 789              */
 790             unsigned R = E->Chg & REG_ZP;
 791
 792             /* Get register usage and check if the register value is used later */
 793             if ((GetRegInfo (S, I+1, R) & R) == 0) {
 794
 795                 /* Register value is not used, remove the load */
 796                 CS_DelEntry (S, I);
 797
 798                 /* Remember, we had changes */
 799                 ++Changes;
 800
 801             }
 802         }
 803
 804         /* Next entry */
 805         ++I;
 806
 807     }
 808
 809     /* Return the number of changes made */
 810     return Changes;
 811 }
 812
 813
 814
 815 unsigned OptDupLoads (CodeSeg* S)
 816 /* Remove loads of registers where the value loaded is already in the register. */
 817 {
 818     unsigned Changes = 0;
 819     unsigned I;
 820
 821     /* Generate register info for this step */
 822     CS_GenRegInfo (S);
 823
 824     /* Walk over the entries */
 825     I = 0;
 826     while (I < CS_GetEntryCount (S)) {
 827
 828         CodeEntry* N;
 829
 830         /* Get next entry */
 831         CodeEntry* E = CS_GetEntry (S, I);
 832
 833         /* Assume we won't delete the entry */
 834         int Delete = 0;
 835
 836         /* Get a pointer to the input registers of the insn */
 837         const RegContents* In  = &E->RI->In;
 838
 839         /* Handle the different instructions */
 840         switch (E->OPC) {
 841
 842             case OP65_LDA:
 843                 if (RegValIsKnown (In->RegA)          && /* Value of A is known */
 844                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 845                     In->RegA == (long) E->Num         && /* Both are equal */
 846                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 847                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 848                     Delete = 1;
 849                 }
 850                 break;
 851
 852             case OP65_LDX:
 853                 if (RegValIsKnown (In->RegX)          && /* Value of X is known */
 854                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 855                     In->RegX == (long) E->Num         && /* Both are equal */
 856                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 857                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 858                     Delete = 1;
 859                 }
 860                 break;
 861
 862             case OP65_LDY:
 863                 if (RegValIsKnown (In->RegY)          && /* Value of Y is known */
 864                     CE_KnownImm (E)                   && /* Value to be loaded is known */
 865                     In->RegY == (long) E->Num         && /* Both are equal */
 866                     (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
 867                     !CE_UseLoadFlags (N)) {              /* Which does not use the flags */
 868                     Delete = 1;
 869                 }
 870                 break;
 871
 872             case OP65_STA:
 873                 /* If we store into a known zero page location, and this
 874                  * location does already contain the value to be stored,
 875                  * remove the store.
 876                  */
 877                 if (RegValIsKnown (In->RegA)          && /* Value of A is known */
 878                     E->AM == AM65_ZP                  && /* Store into zp */
 879                     In->RegA == ZPRegVal (E->Chg, In)) { /* Value identical */
 880
 881                     Delete = 1;
 882                 }
 883                 break;
 884
 885             case OP65_STX:
 886                 /* If we store into a known zero page location, and this
 887                  * location does already contain the value to be stored,
 888                  * remove the store.
 889                  */
 890                 if (RegValIsKnown (In->RegX)          && /* Value of A is known */
 891                     E->AM == AM65_ZP                  && /* Store into zp */
 892                     In->RegX == ZPRegVal (E->Chg, In)) { /* Value identical */
 893
 894                     Delete = 1;
 895
 896                 /* If the value in the X register is known and the same as
 897                  * that in the A register, replace the store by a STA. The
 898                  * optimizer will then remove the load instruction for X
 899                  * later. STX does support the zeropage,y addressing mode,
 900                  * so be sure to check for that.
 901                  */
 902                 } else if (RegValIsKnown (In->RegX)   &&
 903                            In->RegX == In->RegA       &&
 904                            E->AM != AM65_ABSY         &&
 905                            E->AM != AM65_ZPY) {
 906                     /* Use the A register instead */
 907                     CE_ReplaceOPC (E, OP65_STA);
 908                 }
 909                 break;
 910
 911             case OP65_STY:
 912                 /* If we store into a known zero page location, and this
 913                  * location does already contain the value to be stored,
 914                  * remove the store.
 915                  */
 916                 if (RegValIsKnown (In->RegY)          && /* Value of Y is known */
 917                     E->AM == AM65_ZP                  && /* Store into zp */
 918                     In->RegY == ZPRegVal (E->Chg, In)) { /* Value identical */
 919
 920                     Delete = 1;
 921
 922                 /* If the value in the Y register is known and the same as
 923                  * that in the A register, replace the store by a STA. The
 924                  * optimizer will then remove the load instruction for Y
 925                  * later. If replacement by A is not possible try a
 926                  * replacement by X, but check for invalid addressing modes
 927                  * in this case.
 928                  */
 929                 } else if (RegValIsKnown (In->RegY)) {
 930                     if (In->RegY == In->RegA) {
 931                         CE_ReplaceOPC (E, OP65_STA);
 932                     } else if (In->RegY == In->RegX   &&
 933                                E->AM != AM65_ABSX     &&
 934                                E->AM != AM65_ZPX) {
 935                         CE_ReplaceOPC (E, OP65_STX);
 936                     }
 937                 }
 938                 break;
 939
 940             case OP65_STZ:
 941                 /* If we store into a known zero page location, and this
 942                  * location does already contain the value to be stored,
 943                  * remove the store.
 944                  */
 945                 if (CPU >= CPU_65C02 && E->AM == AM65_ZP) {
 946                     if (ZPRegVal (E->Chg, In) == 0) {
 947                         Delete = 1;
 948                     }
 949                 }
 950                 break;
 951
 952             case OP65_TAX:
 953                 if (RegValIsKnown (In->RegA)          &&
 954                     In->RegA == In->RegX              &&
 955                     (N = CS_GetNextEntry (S, I)) != 0 &&
 956                     !CE_UseLoadFlags (N)) {
 957                     /* Value is identical and not followed by a branch */
 958                     Delete = 1;
 959                 }
 960                 break;
 961
 962             case OP65_TAY:
 963                 if (RegValIsKnown (In->RegA)            &&
 964                     In->RegA == In->RegY                &&
 965                     (N = CS_GetNextEntry (S, I)) != 0   &&
 966                     !CE_UseLoadFlags (N)) {
 967                     /* Value is identical and not followed by a branch */
 968                     Delete = 1;
 969                 }
 970                 break;
 971
 972             case OP65_TXA:
 973                 if (RegValIsKnown (In->RegX)            &&
 974                     In->RegX == In->RegA                &&
 975                     (N = CS_GetNextEntry (S, I)) != 0   &&
 976                     !CE_UseLoadFlags (N)) {
 977                     /* Value is identical and not followed by a branch */
 978                     Delete = 1;
 979                 }
 980                 break;
 981
 982             case OP65_TYA:
 983                 if (RegValIsKnown (In->RegY)            &&
 984                     In->RegY == In->RegA                &&
 985                     (N = CS_GetNextEntry (S, I)) != 0   &&
 986                     !CE_UseLoadFlags (N)) {
 987                     /* Value is identical and not followed by a branch */
 988                     Delete = 1;
 989                 }
 990                 break;
 991
 992             default:
 993                 break;
 994
 995         }
 996
 997         /* Delete the entry if requested */
 998         if (Delete) {
 999
1000             /* Register value is not used, remove the load */
1001             CS_DelEntry (S, I);
1002
1003             /* Remember, we had changes */
1004             ++Changes;
1005
1006         } else {
1007
1008             /* Next entry */
1009             ++I;
1010
1011         }
1012
1013     }
1014
1015     /* Free register info */
1016     CS_FreeRegInfo (S);
1017
1018     /* Return the number of changes made */
1019     return Changes;
1020 }
1021
1022
1023
1024 unsigned OptStoreLoad (CodeSeg* S)
1025 /* Remove a store followed by a load from the same location. */
1026 {
1027     unsigned Changes = 0;
1028
1029     /* Walk over the entries */
1030     unsigned I = 0;
1031     while (I < CS_GetEntryCount (S)) {
1032
1033         CodeEntry* N;
1034         CodeEntry* X;
1035
1036         /* Get next entry */
1037         CodeEntry* E = CS_GetEntry (S, I);
1038
1039         /* Check if it is a store instruction followed by a load from the
1040          * same address which is itself not followed by a conditional branch.
1041          */
1042         if ((E->Info & OF_STORE) != 0                       &&
1043             (N = CS_GetNextEntry (S, I)) != 0               &&
1044             !CE_HasLabel (N)                                &&
1045             E->AM == N->AM                                  &&
1046             ((E->OPC == OP65_STA && N->OPC == OP65_LDA) ||
1047              (E->OPC == OP65_STX && N->OPC == OP65_LDX) ||
1048              (E->OPC == OP65_STY && N->OPC == OP65_LDY))    &&
1049             strcmp (E->Arg, N->Arg) == 0                    &&
1050             (X = CS_GetNextEntry (S, I+1)) != 0             &&
1051             !CE_UseLoadFlags (X)) {
1052
1053             /* Register has already the correct value, remove the load */
1054             CS_DelEntry (S, I+1);
1055
1056             /* Remember, we had changes */
1057             ++Changes;
1058
1059         }
1060
1061         /* Next entry */
1062         ++I;
1063
1064     }
1065
1066     /* Return the number of changes made */
1067     return Changes;
1068 }
1069
1070
1071
1072 unsigned OptTransfers1 (CodeSeg* S)
1073 /* Remove transfers from one register to another and back */
1074 {
1075     unsigned Changes = 0;
1076
1077     /* Walk over the entries */
1078     unsigned I = 0;
1079     while (I < CS_GetEntryCount (S)) {
1080
1081         CodeEntry* N;
1082         CodeEntry* X;
1083         CodeEntry* P;
1084
1085         /* Get next entry */
1086         CodeEntry* E = CS_GetEntry (S, I);
1087
1088         /* Check if we have two transfer instructions */
1089         if ((E->Info & OF_XFR) != 0                 &&
1090             (N = CS_GetNextEntry (S, I)) != 0       &&
1091             !CE_HasLabel (N)                        &&
1092             (N->Info & OF_XFR) != 0) {
1093
1094             /* Check if it's a transfer and back */
1095             if ((E->OPC == OP65_TAX && N->OPC == OP65_TXA && !RegXUsed (S, I+2)) ||
1096                 (E->OPC == OP65_TAY && N->OPC == OP65_TYA && !RegYUsed (S, I+2)) ||
1097                 (E->OPC == OP65_TXA && N->OPC == OP65_TAX && !RegAUsed (S, I+2)) ||
1098                 (E->OPC == OP65_TYA && N->OPC == OP65_TAY && !RegAUsed (S, I+2))) {
1099
1100                 /* If the next insn is a conditional branch, check if the insn
1101                  * preceeding the first xfr will set the flags right, otherwise we
1102                  * may not remove the sequence.
1103                  */
1104                 if ((X = CS_GetNextEntry (S, I+1)) == 0) {
1105                     goto NextEntry;
1106                 }
1107                 if (CE_UseLoadFlags (X)) {
1108                     if (I == 0) {
1109                         /* No preceeding entry */
1110                         goto NextEntry;
1111                     }
1112                     P = CS_GetEntry (S, I-1);
1113                     if ((P->Info & OF_SETF) == 0) {
1114                         /* Does not set the flags */
1115                         goto NextEntry;
1116                     }
1117                 }
1118
1119                 /* Remove both transfers */
1120                 CS_DelEntry (S, I+1);
1121                 CS_DelEntry (S, I);
1122
1123                 /* Remember, we had changes */
1124                 ++Changes;
1125             }
1126         }
1127
1128 NextEntry:
1129         /* Next entry */
1130         ++I;
1131
1132     }
1133
1134     /* Return the number of changes made */
1135     return Changes;
1136 }
1137
1138
1139
1140 unsigned OptTransfers2 (CodeSeg* S)
1141 /* Replace loads followed by a register transfer by a load with the second
1142  * register if possible.
1143  */
1144 {
1145     unsigned Changes = 0;
1146
1147     /* Walk over the entries */
1148     unsigned I = 0;
1149     while (I < CS_GetEntryCount (S)) {
1150
1151         CodeEntry* N;
1152
1153         /* Get next entry */
1154         CodeEntry* E = CS_GetEntry (S, I);
1155
1156         /* Check if we have a load followed by a transfer where the loaded
1157          * register is not used later.
1158          */
1159         if ((E->Info & OF_LOAD) != 0                &&
1160             (N = CS_GetNextEntry (S, I)) != 0       &&
1161             !CE_HasLabel (N)                        &&
1162             (N->Info & OF_XFR) != 0                 &&
1163             GetRegInfo (S, I+2, E->Chg) != E->Chg) {
1164
1165             CodeEntry* X = 0;
1166
1167             if (E->OPC == OP65_LDA && N->OPC == OP65_TAX) {
1168                 /* LDA/TAX - check for the right addressing modes */
1169                 if (E->AM == AM65_IMM ||
1170                     E->AM == AM65_ZP  ||
1171                     E->AM == AM65_ABS ||
1172                     E->AM == AM65_ABSY) {
1173                     /* Replace */
1174                     X = NewCodeEntry (OP65_LDX, E->AM, E->Arg, 0, N->LI);
1175                 }
1176             } else if (E->OPC == OP65_LDA && N->OPC == OP65_TAY) {
1177                 /* LDA/TAY - check for the right addressing modes */
1178                 if (E->AM == AM65_IMM ||
1179                     E->AM == AM65_ZP  ||
1180                     E->AM == AM65_ZPX ||
1181                     E->AM == AM65_ABS ||
1182                     E->AM == AM65_ABSX) {
1183                     /* Replace */
1184                     X = NewCodeEntry (OP65_LDY, E->AM, E->Arg, 0, N->LI);
1185                 }
1186             } else if (E->OPC == OP65_LDY && N->OPC == OP65_TYA) {
1187                 /* LDY/TYA. LDA supports all addressing modes LDY does */
1188                 X = NewCodeEntry (OP65_LDA, E->AM, E->Arg, 0, N->LI);
1189             } else if (E->OPC == OP65_LDX && N->OPC == OP65_TXA) {
1190                 /* LDX/TXA. LDA doesn't support zp,y, so we must map it to
1191                  * abs,y instead.
1192                  */
1193                 am_t AM = (E->AM == AM65_ZPY)? AM65_ABSY : E->AM;
1194                 X = NewCodeEntry (OP65_LDA, AM, E->Arg, 0, N->LI);
1195             }
1196
1197             /* If we have a load entry, add it and remove the old stuff */
1198             if (X) {
1199                 CS_InsertEntry (S, X, I+2);
1200                 CS_DelEntries (S, I, 2);
1201                 ++Changes;
1202                 --I;    /* Correct for one entry less */
1203             }
1204         }
1205
1206         /* Next entry */
1207         ++I;
1208     }
1209
1210     /* Return the number of changes made */
1211     return Changes;
1212 }
1213
1214
1215
1216 unsigned OptPushPop (CodeSeg* S)
1217 /* Remove a PHA/PLA sequence were A is not used later */
1218 {
1219     unsigned Changes = 0;
1220     unsigned Push    = 0;       /* Index of push insn */
1221     unsigned Pop     = 0;       /* Index of pop insn */
1222     enum {
1223         Searching,
1224         FoundPush,
1225         FoundPop
1226     } State = Searching;
1227
1228     /* Walk over the entries. Look for a push instruction that is followed by
1229      * a pop later, where the pop is not followed by an conditional branch,
1230      * and where the value of the A register is not used later on.
1231      * Look out for the following problems:
1232      *
1233      *  - There may be another PHA/PLA inside the sequence: Restart it.
1234      *  - If the PLA has a label, all jumps to this label must be inside
1235      *    the sequence, otherwise we cannot remove the PHA/PLA.
1236      */
1237     unsigned I = 0;
1238     while (I < CS_GetEntryCount (S)) {
1239
1240         /* Get next entry */
1241         CodeEntry* E = CS_GetEntry (S, I);
1242
1243         switch (State) {
1244
1245             case Searching:
1246                 if (E->OPC == OP65_PHA) {
1247                     /* Found start of sequence */
1248                     Push  = I;
1249                     State = FoundPush;
1250                 }
1251                 break;
1252
1253             case FoundPush:
1254                 if (E->OPC == OP65_PHA) {
1255                     /* Inner push/pop, restart */
1256                     Push = I;
1257                 } else if (E->OPC == OP65_PLA) {
1258                     /* Found a matching pop */
1259                     Pop = I;
1260                     State = FoundPop;
1261                 }
1262                 break;
1263
1264             case FoundPop:
1265                 /* Next insn, just check if it is no conditional branch and
1266                  * that A is not used later. Check also that the range we have
1267                  * found now is a basic block, which means that the PHA is the
1268                  * only entrance and the PLA the only exit.
1269                  */
1270                 if ((E->Info & OF_CBRA) == 0    &&
1271                     !RegAUsed (S, I)            &&
1272                     CS_IsBasicBlock (S, Push, Pop)) {
1273                     /* We can remove the PHA and PLA instructions */
1274                     CS_DelEntry (S, Pop);
1275                     CS_DelEntry (S, Push);
1276                     /* Correct I so we continue with the next insn */
1277                     I -= 2;
1278                     /* Remember we had changes */
1279                     ++Changes;
1280                 }
1281                 /* Go into search mode again */
1282                 State = Searching;
1283                 break;
1284
1285         }
1286
1287         /* Next entry */
1288         ++I;
1289     }
1290
1291     /* Return the number of changes made */
1292     return Changes;
1293 }
1294
1295
1296
1297 unsigned OptPrecalc (CodeSeg* S)
1298 /* Replace immediate operations with the accu where the current contents are
1299  * known by a load of the final value.
1300  */
1301 {
1302     unsigned Changes = 0;
1303     unsigned I;
1304
1305     /* Generate register info for this step */
1306     CS_GenRegInfo (S);
1307
1308     /* Walk over the entries */
1309     I = 0;
1310     while (I < CS_GetEntryCount (S)) {
1311
1312         /* Get next entry */
1313         CodeEntry* E = CS_GetEntry (S, I);
1314
1315         /* Get a pointer to the output registers of the insn */
1316         const RegContents* Out = &E->RI->Out;
1317
1318         /* Handle the different instructions */
1319         switch (E->OPC) {
1320
1321             case OP65_ADC:
1322             case OP65_AND:
1323             case OP65_ASL:
1324             case OP65_EOR:
1325             case OP65_LSR:
1326             case OP65_ORA:
1327             case OP65_SBC:
1328                 if (RegValIsKnown (Out->RegA)) {
1329                     /* Accu AND zp with known contents */
1330                     const char* Arg = MakeHexArg (Out->RegA);
1331                     CodeEntry* X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, E->LI);
1332                     CS_InsertEntry (S, X, I+1);
1333                     CS_DelEntry (S, I);
1334                     ++Changes;
1335                 }
1336                 break;
1337
1338             default:
1339                 break;
1340
1341         }
1342
1343         /* Next entry */
1344         ++I;
1345     }
1346
1347     /* Free register info */
1348     CS_FreeRegInfo (S);
1349
1350     /* Return the number of changes made */
1351     return Changes;
1352 }
1353
1354
1355
1356 /*****************************************************************************/
1357 /*                           Optimize branch types                           */
1358 /*****************************************************************************/
1359
1360
1361
1362 unsigned OptBranchDist (CodeSeg* S)
1363 /* Change branches for the distance needed. */
1364 {
1365     unsigned Changes = 0;
1366
1367     /* Walk over the entries */
1368     unsigned I = 0;
1369     while (I < CS_GetEntryCount (S)) {
1370
1371         /* Get next entry */
1372         CodeEntry* E = CS_GetEntry (S, I);
1373
1374         /* Check if it's a conditional branch to a local label. */
1375         if (E->Info & OF_CBRA) {
1376
1377             /* Is this a branch to a local symbol? */
1378             if (E->JumpTo != 0) {
1379
1380                 /* Check if the branch distance is short */
1381                 int IsShort = IsShortDist (GetBranchDist (S, I, E->JumpTo->Owner));
1382
1383                 /* Make the branch short/long according to distance */
1384                 if ((E->Info & OF_LBRA) == 0 && !IsShort) {
1385                     /* Short branch but long distance */
1386                     CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1387                     ++Changes;
1388                 } else if ((E->Info & OF_LBRA) != 0 && IsShort) {
1389                     /* Long branch but short distance */
1390                     CE_ReplaceOPC (E, MakeShortBranch (E->OPC));
1391                     ++Changes;
1392                 }
1393
1394             } else if ((E->Info & OF_LBRA) == 0) {
1395
1396                 /* Short branch to external symbol - make it long */
1397                 CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
1398                 ++Changes;
1399
1400             }
1401
1402         } else if (CPU == CPU_65C02                                      &&
1403                    (E->Info & OF_UBRA) != 0                              &&
1404                    E->JumpTo != 0                                        &&
1405                    IsShortDist (GetBranchDist (S, I, E->JumpTo->Owner))) {
1406
1407             /* The jump is short and may be replaced by a BRA on the 65C02 CPU */
1408             CE_ReplaceOPC (E, OP65_BRA);
1409             ++Changes;
1410         }
1411
1412         /* Next entry */
1413         ++I;
1414
1415     }
1416
1417     /* Return the number of changes made */
1418     return Changes;
1419 }
1420
1421
1422