1 /*****************************************************************************/
5 /* Environment independent low level optimizations */
9 /* (C) 2001 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
47 /*****************************************************************************/
49 /*****************************************************************************/
53 /* Macro to increment and decrement register contents if they're valid */
54 #define INC(reg,val) if ((reg) >= 0) (reg) = ((reg) + val) & 0xFF
55 #define DEC(reg,val) if ((reg) >= 0) (reg) = ((reg) - val) & 0xFF
59 /*****************************************************************************/
60 /* Replace jumps to RTS by RTS */
61 /*****************************************************************************/
65 unsigned OptRTSJumps (CodeSeg* S)
66 /* Replace jumps to RTS by RTS */
70 /* Walk over all entries minus the last one */
72 while (I < CS_GetEntryCount (S)) {
74 /* Get the next entry */
75 CodeEntry* E = CS_GetEntry (S, I);
77 /* Check if it's an unconditional branch to a local target */
78 if ((E->Info & OF_UBRA) != 0 &&
80 E->JumpTo->Owner->OPC == OP65_RTS) {
82 /* Insert an RTS instruction */
83 CodeEntry* X = NewCodeEntry (OP65_RTS, AM65_IMP, 0, 0, E->LI);
84 CS_InsertEntry (S, X, I+1);
89 /* Remember, we had changes */
99 /* Return the number of changes made */
105 /*****************************************************************************/
106 /* Remove dead jumps */
107 /*****************************************************************************/
111 unsigned OptDeadJumps (CodeSeg* S)
112 /* Remove dead jumps (jumps to the next instruction) */
114 unsigned Changes = 0;
118 /* Get the number of entries, bail out if we have less than two entries */
119 unsigned Count = CS_GetEntryCount (S);
124 /* Walk over all entries minus the last one */
126 while (I < Count-1) {
128 /* Get the next entry */
129 E = CS_GetEntry (S, I);
131 /* Check if it's a branch, if it has a local target, and if the target
132 * is the next instruction.
134 if (E->AM == AM65_BRA && E->JumpTo && E->JumpTo->Owner == CS_GetEntry (S, I+1)) {
136 /* Delete the dead jump */
139 /* Keep the number of entries updated */
142 /* Remember, we had changes */
153 /* Return the number of changes made */
159 /*****************************************************************************/
160 /* Remove dead code */
161 /*****************************************************************************/
165 unsigned OptDeadCode (CodeSeg* S)
166 /* Remove dead code (code that follows an unconditional jump or an rts/rti
170 unsigned Changes = 0;
173 /* Get the number of entries, bail out if we have less than two entries */
174 unsigned Count = CS_GetEntryCount (S);
179 /* Walk over all entries */
186 CodeEntry* E = CS_GetEntry (S, I);
188 /* Check if it's an unconditional branch, and if the next entry has
191 if ((E->Info & OF_DEAD) != 0 &&
192 (N = CS_GetNextEntry (S, I)) != 0 &&
195 /* Delete the next entry */
196 CS_DelEntry (S, I+1);
198 /* Keep the number of entries updated */
201 /* Remember, we had changes */
212 /* Return the number of changes made */
218 /*****************************************************************************/
219 /* Optimize jump cascades */
220 /*****************************************************************************/
224 unsigned OptJumpCascades (CodeSeg* S)
225 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
226 * replaced by a jump to the final location. This will in some cases produce
227 * worse code, because some jump targets are no longer reachable by short
228 * branches, but this is quite rare, so there are more advantages than
232 unsigned Changes = 0;
234 /* Walk over all entries */
236 while (I < CS_GetEntryCount (S)) {
242 CodeEntry* E = CS_GetEntry (S, I);
244 /* Check if it's a branch, if it has a jump label, if this jump
245 * label is not attached to the instruction itself, and if the
246 * target instruction is itself a branch.
248 if ((E->Info & OF_BRA) != 0 &&
249 (OldLabel = E->JumpTo) != 0 &&
250 (N = OldLabel->Owner) != E &&
251 (N->Info & OF_BRA) != 0) {
253 /* Check if we can use the final target label. This is the case,
254 * if the target branch is an absolut branch, or if it is a
255 * conditional branch checking the same condition as the first one.
257 if ((N->Info & OF_UBRA) != 0 ||
258 ((E->Info & OF_CBRA) != 0 &&
259 GetBranchCond (E->OPC) == GetBranchCond (N->OPC))) {
261 /* This is a jump cascade and we may jump to the final target.
262 * Insert a new instruction, then remove the old one
264 CodeEntry* X = NewCodeEntry (E->OPC, E->AM, N->Arg, N->JumpTo, E->LI);
266 /* Insert it behind E */
267 CS_InsertEntry (S, X, I+1);
272 /* Remember, we had changes */
280 /* Check if both are conditional branches, and the condition of
281 * the second is the inverse of that of the first. In this case,
282 * the second branch will never be taken, and we may jump directly
283 * to the instruction behind this one.
285 if ((E->Info & OF_CBRA) != 0 && (N->Info & OF_CBRA) != 0) {
287 CodeEntry* X; /* Instruction behind N */
288 CodeLabel* LX; /* Label attached to X */
290 /* Get the branch conditions of both branches */
291 bc_t BC1 = GetBranchCond (E->OPC);
292 bc_t BC2 = GetBranchCond (N->OPC);
294 /* Check the branch conditions */
295 if (BC1 != GetInverseCond (BC2)) {
296 /* Condition not met */
300 /* We may jump behind this conditional branch. Get the
301 * pointer to the next instruction
303 if ((X = CS_GetNextEntry (S, CS_GetEntryIndex (S, N))) == 0) {
304 /* N is the last entry, bail out */
308 /* Get the label attached to X, create a new one if needed */
309 LX = CS_GenLabel (S, X);
311 /* Move the reference from E to the new label */
312 CS_MoveLabelRef (S, E, LX);
314 /* Remember, we had changes */
329 /* Return the number of changes made */
335 /*****************************************************************************/
336 /* Optimize jsr/rts */
337 /*****************************************************************************/
341 unsigned OptRTS (CodeSeg* S)
342 /* Optimize subroutine calls followed by an RTS. The subroutine call will get
343 * replaced by a jump. Don't bother to delete the RTS if it does not have a
344 * label, the dead code elimination should take care of it.
347 unsigned Changes = 0;
350 /* Get the number of entries, bail out if we have less than 2 entries */
351 unsigned Count = CS_GetEntryCount (S);
356 /* Walk over all entries minus the last one */
358 while (I < Count-1) {
363 CodeEntry* E = CS_GetEntry (S, I);
365 /* Check if it's a subroutine call and if the following insn is RTS */
366 if (E->OPC == OP65_JSR &&
367 (N = CS_GetNextEntry (S, I)) != 0 &&
368 N->OPC == OP65_RTS) {
370 /* Change the jsr to a jmp and use the additional info for a jump */
372 CE_ReplaceOPC (E, OP65_JMP);
374 /* Remember, we had changes */
384 /* Return the number of changes made */
390 /*****************************************************************************/
391 /* Optimize jump targets */
392 /*****************************************************************************/
396 unsigned OptJumpTarget (CodeSeg* S)
397 /* If the instruction preceeding an unconditional branch is the same as the
398 * instruction preceeding the jump target, the jump target may be moved
399 * one entry back. This is a size optimization, since the instruction before
400 * the branch gets removed.
403 unsigned Changes = 0;
404 CodeEntry* E1; /* Entry 1 */
405 CodeEntry* E2; /* Entry 2 */
406 CodeEntry* T1; /* Jump target entry 1 */
407 CodeEntry* T2; /* Jump target entry 2 */
408 CodeLabel* TL1; /* Target label 1 */
409 unsigned TI; /* Target index */
412 /* Get the number of entries, bail out if we have not enough */
413 unsigned Count = CS_GetEntryCount (S);
418 /* Walk over the entries */
420 while (I < Count-1) {
423 E2 = CS_GetEntry (S, I+1);
425 /* Check if we have a jump or branch, and a matching label */
426 if ((E2->Info & OF_UBRA) != 0 && E2->JumpTo) {
428 /* Get the target instruction for the label */
429 T2 = E2->JumpTo->Owner;
431 /* Get the entry preceeding this one (if possible) */
432 TI = CS_GetEntryIndex (S, T2);
434 /* There is no entry before this one */
437 T1 = CS_GetEntry (S, TI-1);
439 /* Get the entry preceeding the jump */
440 E1 = CS_GetEntry (S, I);
442 /* Check if both preceeding instructions are identical */
443 if (!CodeEntriesAreEqual (E1, T1)) {
444 /* Not equal, try next */
448 /* Get the label for the instruction preceeding the jump target.
449 * This routine will create a new label if the instruction does
450 * not already have one.
452 TL1 = CS_GenLabel (S, T1);
454 /* Change the jump target to point to this new label */
455 CS_MoveLabelRef (S, E2, TL1);
457 /* If the instruction preceeding the jump has labels attached,
458 * move references to this label to the new label.
460 if (CE_HasLabel (E1)) {
461 CS_MoveLabels (S, E1, T1);
464 /* Remove the entry preceeding the jump */
468 /* Remember, we had changes */
479 /* Return the number of changes made */
485 /*****************************************************************************/
486 /* Optimize conditional branches */
487 /*****************************************************************************/
491 unsigned OptCondBranches (CodeSeg* S)
492 /* Performs several optimization steps:
494 * - If an immidiate load of a register is followed by a conditional jump that
495 * is never taken because the load of the register sets the flags in such a
496 * manner, remove the conditional branch.
497 * - If the conditional branch is always taken because of the register load,
498 * replace it by a jmp.
499 * - If a conditional branch jumps around an unconditional branch, remove the
500 * conditional branch and make the jump a conditional branch with the
501 * inverse condition of the first one.
504 unsigned Changes = 0;
507 /* Get the number of entries, bail out if we have not enough */
508 unsigned Count = CS_GetEntryCount (S);
513 /* Walk over the entries */
515 while (I < Count-1) {
521 CodeEntry* E = CS_GetEntry (S, I);
523 /* Check if it's a register load */
524 if ((E->Info & OF_LOAD) != 0 && /* It's a load instruction */
525 E->AM == AM65_IMM && /* ..with immidiate addressing */
526 (E->Flags & CEF_NUMARG) != 0 && /* ..and a numeric argument. */
527 (N = CS_GetNextEntry (S, I)) != 0 && /* There is a following entry */
528 (N->Info & OF_CBRA) != 0 && /* ..which is a conditional branch */
529 !CE_HasLabel (N)) { /* ..and does not have a label */
531 /* Get the branch condition */
532 bc_t BC = GetBranchCond (N->OPC);
534 /* Check the argument against the branch condition */
535 if ((BC == BC_EQ && E->Num != 0) ||
536 (BC == BC_NE && E->Num == 0) ||
537 (BC == BC_PL && (E->Num & 0x80) != 0) ||
538 (BC == BC_MI && (E->Num & 0x80) == 0)) {
540 /* Remove the conditional branch */
541 CS_DelEntry (S, I+1);
544 /* Remember, we had changes */
547 } else if ((BC == BC_EQ && E->Num == 0) ||
548 (BC == BC_NE && E->Num != 0) ||
549 (BC == BC_PL && (E->Num & 0x80) == 0) ||
550 (BC == BC_MI && (E->Num & 0x80) != 0)) {
552 /* The branch is always taken, replace it by a jump */
553 CE_ReplaceOPC (N, OP65_JMP);
555 /* Remember, we had changes */
561 if ((E->Info & OF_CBRA) != 0 && /* It's a conditional branch */
562 (L = E->JumpTo) != 0 && /* ..referencing a local label */
563 (N = CS_GetNextEntry (S, I)) != 0 && /* There is a following entry */
564 (N->Info & OF_UBRA) != 0 && /* ..which is an uncond branch, */
565 !CE_HasLabel (N) && /* ..has no label attached */
566 L->Owner == CS_GetNextEntry (S, I+1)) {/* ..and jump target follows */
568 /* Replace the jump by a conditional branch with the inverse branch
569 * condition than the branch around it.
571 CE_ReplaceOPC (N, GetInverseBranch (E->OPC));
573 /* Remove the conditional branch */
577 /* Remember, we had changes */
587 /* Return the number of changes made */
593 /*****************************************************************************/
594 /* Remove unused loads */
595 /*****************************************************************************/
599 unsigned OptUnusedLoads (CodeSeg* S)
600 /* Remove loads of registers where the value loaded is not used later. */
602 unsigned Changes = 0;
604 /* Walk over the entries */
606 while (I < CS_GetEntryCount (S)) {
611 CodeEntry* E = CS_GetEntry (S, I);
613 /* Check if it's a register load or transfer insn */
614 if ((E->Info & (OF_LOAD | OF_XFR)) != 0 &&
615 (N = CS_GetNextEntry (S, I)) != 0 &&
616 (N->Info & OF_FBRA) == 0) {
618 /* Check which sort of load or transfer it is */
623 case OP65_LDA: R = REG_A; break;
625 case OP65_LDX: R = REG_X; break;
627 case OP65_LDY: R = REG_Y; break;
628 default: goto NextEntry; /* OOPS */
631 /* Get register usage and check if the register value is used later */
632 if ((GetRegInfo (S, I+1) & R) == 0) {
634 /* Register value is not used, remove the load */
637 /* Remember, we had changes */
649 /* Return the number of changes made */
655 unsigned OptDuplicateLoads (CodeSeg* S)
656 /* Remove loads of registers where the value loaded is already in the register. */
658 unsigned Changes = 0;
661 /* Generate register info for this step */
664 /* Walk over the entries */
666 while (I < CS_GetEntryCount (S)) {
671 CodeEntry* E = CS_GetEntry (S, I);
673 /* Assume we won't delete the entry */
676 /* Handle the different instructions */
680 if (E->RI->In.RegA >= 0 && /* Value of A is known */
681 CE_KnownImm (E) && /* Value to be loaded is known */
682 E->RI->In.RegA == E->Num && /* Both are equal */
683 (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
684 (N->Info & OF_FBRA) == 0) { /* Which is not a cond branch */
690 if (E->RI->In.RegX >= 0 && /* Value of X is known */
691 CE_KnownImm (E) && /* Value to be loaded is known */
692 E->RI->In.RegX == E->Num && /* Both are equal */
693 (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
694 (N->Info & OF_FBRA) == 0) { /* Which is not a cond branch */
700 if (E->RI->In.RegY >= 0 && /* Value of Y is known */
701 CE_KnownImm (E) && /* Value to be loaded is known */
702 E->RI->In.RegY == E->Num && /* Both are equal */
703 (N = CS_GetNextEntry (S, I)) != 0 && /* There is a next entry */
704 (N->Info & OF_FBRA) == 0) { /* Which is not a cond branch */
710 /* If the value in the X register is known and the same as
711 * that in the A register, replace the store by a STA. The
712 * optimizer will then remove the load instruction for X
713 * later. STX does support the zeropage,y addressing mode,
714 * so be sure to check for that.
716 if (E->RI->In.RegX >= 0 &&
717 E->RI->In.RegX == E->RI->In.RegA &&
718 E->AM != AM65_ABSY &&
720 /* Use the A register instead */
721 CE_ReplaceOPC (E, OP65_STA);
726 /* If the value in the Y register is known and the same as
727 * that in the A register, replace the store by a STA. The
728 * optimizer will then remove the load instruction for Y
729 * later. If replacement by A is not possible try a
730 * replacement by X, but check for invalid addressing modes
733 if (E->RI->In.RegY >= 0) {
734 if (E->RI->In.RegY == E->RI->In.RegA) {
735 CE_ReplaceOPC (E, OP65_STA);
736 } else if (E->RI->In.RegY == E->RI->In.RegX &&
737 E->AM != AM65_ABSX &&
739 CE_ReplaceOPC (E, OP65_STX);
745 if (E->RI->In.RegA >= 0 &&
746 E->RI->In.RegA == E->RI->In.RegX &&
747 (N = CS_GetNextEntry (S, I)) != 0 &&
748 (N->Info & OF_FBRA) == 0) {
749 /* Value is identical and not followed by a branch */
755 if (E->RI->In.RegA >= 0 &&
756 E->RI->In.RegA == E->RI->In.RegY &&
757 (N = CS_GetNextEntry (S, I)) != 0 &&
758 (N->Info & OF_FBRA) == 0) {
759 /* Value is identical and not followed by a branch */
765 if (E->RI->In.RegX >= 0 &&
766 E->RI->In.RegX == E->RI->In.RegA &&
767 (N = CS_GetNextEntry (S, I)) != 0 &&
768 (N->Info & OF_FBRA) == 0) {
769 /* Value is identical and not followed by a branch */
775 if (E->RI->In.RegY >= 0 &&
776 E->RI->In.RegY == E->RI->In.RegA &&
777 (N = CS_GetNextEntry (S, I)) != 0 &&
778 (N->Info & OF_FBRA) == 0) {
779 /* Value is identical and not followed by a branch */
789 /* Delete the entry if requested */
792 /* Register value is not used, remove the load */
795 /* Remember, we had changes */
807 /* Free register info */
810 /* Return the number of changes made */
816 unsigned OptStoreLoad (CodeSeg* S)
817 /* Remove a store followed by a load from the same location. */
819 unsigned Changes = 0;
821 /* Walk over the entries */
823 while (I < CS_GetEntryCount (S)) {
829 CodeEntry* E = CS_GetEntry (S, I);
831 /* Check if it is a store instruction followed by a load from the
832 * same address which is itself not followed by a conditional branch.
834 if ((E->Info & OF_STORE) != 0 &&
835 (N = CS_GetNextEntry (S, I)) != 0 &&
836 (N->Info & OF_LOAD) != 0 &&
837 strcmp (E->Arg, N->Arg) == 0 &&
838 (X = CS_GetNextEntry (S, I+1)) != 0 &&
839 (X->Info & OF_FBRA) == 0) {
841 /* Register value is not used, remove the load */
842 CS_DelEntry (S, I+1);
844 /* Remember, we had changes */
854 /* Return the number of changes made */
860 /*****************************************************************************/
861 /* Optimize branch types */
862 /*****************************************************************************/
866 unsigned OptBranchDist (CodeSeg* S)
867 /* Change branches for the distance needed. */
869 unsigned Changes = 0;
872 /* Get the number of entries, bail out if we have not enough */
873 unsigned Count = CS_GetEntryCount (S);
875 /* Walk over the entries */
880 CodeEntry* E = CS_GetEntry (S, I);
882 /* Check if it's a conditional branch to a local label. */
883 if ((E->Info & OF_CBRA) != 0) {
885 /* Is this a branch to a local symbol? */
886 if (E->JumpTo != 0) {
888 /* Get the index of the branch target */
889 unsigned TI = CS_GetEntryIndex (S, E->JumpTo->Owner);
891 /* Determine the branch distance */
897 CodeEntry* N = CS_GetEntry (S, J++);
901 /* Backward branch */
904 CodeEntry* N = CS_GetEntry (S, J++);
909 /* Make the branch short/long according to distance */
910 if ((E->Info & OF_LBRA) == 0 && Distance > 120) {
911 /* Short branch but long distance */
912 CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
914 } else if ((E->Info & OF_LBRA) != 0 && Distance < 120) {
915 /* Long branch but short distance */
916 CE_ReplaceOPC (E, MakeShortBranch (E->OPC));
920 } else if ((E->Info & OF_LBRA) == 0) {
922 /* Short branch to external symbol - make it long */
923 CE_ReplaceOPC (E, MakeLongBranch (E->OPC));
934 /* Return the number of changes made */