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