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