git.sur5r.net Git - cc65/blob - src/cc65/coptind.c

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