1 /*****************************************************************************/
5 /* Optimizer subroutines */
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 /*****************************************************************************/
57 /*****************************************************************************/
59 /*****************************************************************************/
63 /* Defines for the conditions in a compare */
78 /* Table with the compare suffixes */
79 static const char CmpSuffixTab [][4] = {
80 "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
83 /* Table used to invert a condition, indexed by condition */
84 static const unsigned char CmpInvertTab [] = {
86 CMP_LE, CMP_LT, CMP_GE, CMP_GT,
87 CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
90 /* Table to show which compares are signed (use the N flag) */
91 static const char CmpSignedTab [] = {
92 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
97 /*****************************************************************************/
98 /* Helper functions */
99 /*****************************************************************************/
103 static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
104 /* Search for a compare condition by the given code using the given length */
109 for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
110 if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
122 static cmp_t FindBoolCmpCond (const char* Name)
123 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
125 /* Check for the correct subroutine name */
126 if (strncmp (Name, "bool", 4) == 0) {
127 /* Name is ok, search for the code in the table */
128 return FindCmpCond (Name+4, strlen(Name)-4);
137 static cmp_t FindTosCmpCond (const char* Name)
138 /* Check if this is a call to one of the TOS compare functions (tosgtax).
139 * Return the condition code or CMP_INV on failure.
142 unsigned Len = strlen (Name);
144 /* Check for the correct subroutine name */
145 if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
146 /* Name is ok, search for the code in the table */
147 return FindCmpCond (Name+3, Len-3-2);
156 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
157 /* Helper function for the replacement of routines that return a boolean
158 * followed by a conditional jump. Instead of the boolean value, the condition
159 * codes are evaluated directly.
160 * I is the index of the conditional branch, the sequence is already checked
168 CodeEntry* E = CS_GetEntry (S, I);
170 /* Replace the conditional branch */
174 CE_ReplaceOPC (E, OP65_JEQ);
178 CE_ReplaceOPC (E, OP65_JNE);
187 if ((N = CS_GetNextEntry (S, I)) == 0) {
189 Internal ("Invalid program flow");
191 L = CS_GenLabel (S, N);
192 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
193 CS_InsertEntry (S, N, I);
194 CE_ReplaceOPC (E, OP65_JPL);
198 CE_ReplaceOPC (E, OP65_JPL);
202 CE_ReplaceOPC (E, OP65_JMI);
210 CE_ReplaceOPC (E, OP65_JMI);
212 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
213 CS_InsertEntry (S, N, I+1);
222 if ((N = CS_GetNextEntry (S, I)) == 0) {
224 Internal ("Invalid program flow");
226 L = CS_GenLabel (S, N);
227 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
228 CS_InsertEntry (S, N, I);
229 CE_ReplaceOPC (E, OP65_JCS);
233 CE_ReplaceOPC (E, OP65_JCS);
237 CE_ReplaceOPC (E, OP65_JCC);
245 CE_ReplaceOPC (E, OP65_JCC);
247 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
248 CS_InsertEntry (S, N, I+1);
252 Internal ("Unknown jump condition: %d", Cond);
260 static int GetCmpRegVal (const CodeEntry* E)
261 /* Return the register value for an immediate compare */
264 case OP65_CMP: return E->RI->In.RegA;
265 case OP65_CPX: return E->RI->In.RegX;
266 case OP65_CPY: return E->RI->In.RegY;
267 default: Internal ("Invalid opcode in GetCmpRegVal");
268 return 0; /* Not reached */
274 static int IsCmpToZero (const CodeEntry* E)
275 /* Check if the given instrcuction is a compare to zero instruction */
277 return (E->OPC == OP65_CMP &&
279 (E->Flags & CEF_NUMARG) != 0 &&
285 static int IsSpLoad (const CodeEntry* E)
286 /* Return true if this is the load of A from the stack */
288 return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
293 static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
294 CodeEntry** L, unsigned Count)
295 /* Check if a 16 bit load of a local variable follows:
303 * If so, read Count entries following the first ldy into L and return true
304 * if this is possible. Otherwise return false.
307 /* Be sure we read enough entries for the check */
310 /* Read the first entry */
311 L[0] = CS_GetEntry (S, Index);
313 /* Check for the sequence */
314 return (L[0]->OPC == OP65_LDY &&
315 L[0]->AM == AM65_IMM &&
316 (L[0]->Flags & CEF_NUMARG) != 0 &&
317 CS_GetEntries (S, L+1, Index+1, Count-1) &&
319 !CE_HasLabel (L[1]) &&
320 L[2]->OPC == OP65_TAX &&
321 !CE_HasLabel (L[2]) &&
322 L[3]->OPC == OP65_DEY &&
323 !CE_HasLabel (L[3]) &&
325 !CE_HasLabel (L[4]));
330 static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
331 /* Check if the instructions at L are an immidiate compare of a/x:
336 return (L[0]->OPC == OP65_CPX &&
337 L[0]->AM == AM65_IMM &&
338 (L[0]->Flags & CEF_NUMARG) != 0 &&
339 !CE_HasLabel (L[0]) &&
340 (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) &&
342 !CE_HasLabel (L[1]) &&
343 L[2]->OPC == OP65_CMP &&
344 L[2]->AM == AM65_IMM &&
345 (L[2]->Flags & CEF_NUMARG) != 0 &&
346 (L[3]->Info & OF_ZBRA) != 0 &&
348 (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
353 /*****************************************************************************/
354 /* Remove calls to the bool transformer subroutines */
355 /*****************************************************************************/
359 static unsigned OptBoolTransforms (CodeSeg* S)
360 /* Try to remove the call to boolean transformer routines where the call is
364 unsigned Changes = 0;
366 /* Walk over the entries */
368 while (I < CS_GetEntryCount (S)) {
374 CodeEntry* E = CS_GetEntry (S, I);
376 /* Check for a boolean transformer */
377 if (E->OPC == OP65_JSR &&
378 (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
379 (N = CS_GetNextEntry (S, I)) != 0 &&
380 (N->Info & OF_ZBRA) != 0) {
382 /* Make the boolean transformer unnecessary by changing the
383 * the conditional jump to evaluate the condition flags that
384 * are set after the compare directly. Note: jeq jumps if
385 * the condition is not met, jne jumps if the condition is met.
386 * Invert the code if we jump on condition not met.
388 if (GetBranchCond (N->OPC) == BC_EQ) {
389 /* Jumps if condition false, invert condition */
390 Cond = CmpInvertTab [Cond];
393 /* Check if we can replace the code by something better */
394 ReplaceCmp (S, I+1, Cond);
396 /* Remove the call to the bool transformer */
399 /* Remember, we had changes */
409 /* Return the number of changes made */
415 /*****************************************************************************/
416 /* Optimize subtractions */
417 /*****************************************************************************/
421 static unsigned OptSub1 (CodeSeg* S)
422 /* Search for the sequence
429 * and remove the handling of the high byte if X is not used later.
432 unsigned Changes = 0;
434 /* Walk over the entries */
436 while (I < CS_GetEntryCount (S)) {
441 CodeEntry* E = CS_GetEntry (S, I);
443 /* Check for the sequence */
444 if (E->OPC == OP65_SBC &&
445 CS_GetEntries (S, L, I+1, 3) &&
446 (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) &&
448 !CE_HasLabel (L[0]) &&
449 L[1]->OPC == OP65_DEX &&
450 !CE_HasLabel (L[1]) &&
451 L[0]->JumpTo->Owner == L[2] &&
452 !RegXUsed (S, I+3)) {
454 /* Remove the bcs/dex */
455 CS_DelEntries (S, I+1, 2);
457 /* Remember, we had changes */
467 /* Return the number of changes made */
473 static unsigned OptSub2 (CodeSeg* S)
474 /* Search for the sequence
491 unsigned Changes = 0;
493 /* Walk over the entries */
495 while (I < CS_GetEntryCount (S)) {
500 CodeEntry* E = CS_GetEntry (S, I);
502 /* Check for the sequence */
503 if (E->OPC == OP65_LDA &&
504 CS_GetEntries (S, L, I+1, 5) &&
505 L[0]->OPC == OP65_SEC &&
506 !CE_HasLabel (L[0]) &&
507 L[1]->OPC == OP65_STA &&
508 strcmp (L[1]->Arg, "tmp1") == 0 &&
509 !CE_HasLabel (L[1]) &&
510 L[2]->OPC == OP65_LDA &&
511 !CE_HasLabel (L[2]) &&
512 L[3]->OPC == OP65_SBC &&
513 strcmp (L[3]->Arg, "tmp1") == 0 &&
514 !CE_HasLabel (L[3]) &&
515 L[4]->OPC == OP65_STA &&
516 strcmp (L[4]->Arg, L[2]->Arg) == 0 &&
517 !CE_HasLabel (L[4])) {
519 /* Remove the store to tmp1 */
520 CS_DelEntry (S, I+2);
522 /* Remove the subtraction */
523 CS_DelEntry (S, I+3);
525 /* Move the lda to the position of the subtraction and change the
528 CS_MoveEntry (S, I, I+3);
529 CE_ReplaceOPC (E, OP65_SBC);
531 /* If the sequence head had a label, move this label back to the
534 if (CE_HasLabel (E)) {
535 CS_MoveLabels (S, E, L[0]);
538 /* Remember, we had changes */
548 /* Return the number of changes made */
554 /*****************************************************************************/
555 /* Optimize additions */
556 /*****************************************************************************/
560 static unsigned OptAdd1 (CodeSeg* S)
561 /* Search for the sequence
579 unsigned Changes = 0;
581 /* Walk over the entries */
583 while (I < CS_GetEntryCount (S)) {
588 CodeEntry* E = CS_GetEntry (S, I);
590 /* Check for the sequence */
591 if (E->OPC == OP65_JSR &&
592 strcmp (E->Arg, "pushax") == 0 &&
593 CS_GetEntries (S, L, I+1, 5) &&
594 L[0]->OPC == OP65_LDY &&
595 CE_KnownImm (L[0]) &&
596 !CE_HasLabel (L[0]) &&
597 L[1]->OPC == OP65_LDX &&
598 CE_KnownImm (L[1]) &&
600 !CE_HasLabel (L[1]) &&
601 L[2]->OPC == OP65_LDA &&
602 !CE_HasLabel (L[2]) &&
603 L[3]->OPC == OP65_JSR &&
604 strcmp (L[3]->Arg, "tosaddax") == 0 &&
605 !CE_HasLabel (L[3])) {
610 /* Remove the call to pushax */
613 /* Correct the stack offset (needed since pushax was removed) */
614 CE_SetNumArg (L[0], L[0]->Num - 2);
617 X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, L[3]->LI);
618 CS_InsertEntry (S, X, I+1);
620 /* Remove the load */
621 CS_DelEntry (S, I+3); /* lda */
622 CS_DelEntry (S, I+2); /* ldx */
625 X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[3]->LI);
626 CS_InsertEntry (S, X, I+2);
628 /* Generate the branch label and the branch */
629 Label = CS_GenLabel (S, L[4]);
630 X = NewCodeEntry (OP65_BCC, AM65_BRA, Label->Name, Label, L[3]->LI);
631 CS_InsertEntry (S, X, I+3);
633 /* Generate the increment of the high byte */
634 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, L[3]->LI);
635 CS_InsertEntry (S, X, I+4);
637 /* Delete the call to tosaddax */
638 CS_DelEntry (S, I+5);
640 /* Remember, we had changes */
650 /* Return the number of changes made */
656 static unsigned OptAdd2 (CodeSeg* S)
657 /* Search for the sequence
681 * provided that a/x is not used later.
684 unsigned Changes = 0;
686 /* Walk over the entries */
688 while (I < CS_GetEntryCount (S)) {
693 L[0] = CS_GetEntry (S, I);
695 /* Check for the sequence */
696 if (L[0]->OPC == OP65_LDY &&
697 CE_KnownImm (L[0]) &&
698 CS_GetEntries (S, L+1, I+1, 6) &&
699 L[1]->OPC == OP65_LDA &&
700 L[1]->AM == AM65_ZP_INDY &&
701 !CE_HasLabel (L[1]) &&
702 L[2]->OPC == OP65_TAX &&
703 !CE_HasLabel (L[2]) &&
704 L[3]->OPC == OP65_DEY &&
705 !CE_HasLabel (L[3]) &&
706 L[4]->OPC == OP65_LDA &&
707 L[4]->AM == AM65_ZP_INDY &&
708 !CE_HasLabel (L[4]) &&
709 L[5]->OPC == OP65_LDY &&
710 CE_KnownImm (L[5]) &&
711 !CE_HasLabel (L[5]) &&
712 L[6]->OPC == OP65_JSR &&
713 strcmp (L[6]->Arg, "addeqysp") == 0 &&
714 !CE_HasLabel (L[6]) &&
715 (GetRegInfo (S, I+7, REG_AX) & REG_AX) == 0) {
722 /* Create a replacement for the first LDY */
723 Offs = (int) (L[0]->Num - 1);
724 xsprintf (Buf, sizeof (Buf), "$%02X", Offs);
725 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
726 CS_InsertEntry (S, X, I+1);
729 /* Load Y with the low offset of the target variable */
730 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[5]->Arg, 0, L[1]->LI);
731 CS_InsertEntry (S, X, I+2);
734 X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, L[1]->LI);
735 CS_InsertEntry (S, X, I+3);
737 /* Remove the TAX/DEY sequence */
738 CS_DelEntry (S, I+5); /* dey */
739 CS_DelEntry (S, I+4); /* tax */
741 /* Addition of the low byte */
742 X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[4]->LI);
743 CS_InsertEntry (S, X, I+4);
744 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "sp", 0, L[4]->LI);
745 CS_InsertEntry (S, X, I+5);
748 xsprintf (Buf, sizeof (Buf), "$%02X", (Offs+1));
749 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[4]->LI);
750 CS_InsertEntry (S, X, I+6);
752 /* Addition of the high byte */
753 xsprintf (Buf, sizeof (Buf), "$%02X", (int)(L[5]->Num+1));
754 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[5]->LI);
755 CS_InsertEntry (S, X, I+8);
756 X = NewCodeEntry (OP65_ADC, AM65_ZP_INDY, "sp", 0, L[6]->LI);
757 CS_InsertEntry (S, X, I+9);
758 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "sp", 0, L[6]->LI);
759 CS_InsertEntry (S, X, I+10);
761 /* Delete the remaining stuff */
762 CS_DelEntry (S, I+12);
763 CS_DelEntry (S, I+11);
765 /* Remember, we had changes */
775 /* Return the number of changes made */
781 static unsigned OptAdd3 (CodeSeg* S)
782 /* Search for the sequence
789 * and remove the handling of the high byte if X is not used later.
792 unsigned Changes = 0;
794 /* Walk over the entries */
796 while (I < CS_GetEntryCount (S)) {
801 CodeEntry* E = CS_GetEntry (S, I);
803 /* Check for the sequence */
804 if (E->OPC == OP65_ADC &&
805 CS_GetEntries (S, L, I+1, 3) &&
806 (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
808 !CE_HasLabel (L[0]) &&
809 L[1]->OPC == OP65_INX &&
810 !CE_HasLabel (L[1]) &&
811 L[0]->JumpTo->Owner == L[2] &&
812 !RegXUsed (S, I+3)) {
814 /* Remove the bcs/dex */
815 CS_DelEntries (S, I+1, 2);
817 /* Remember, we had changes */
827 /* Return the number of changes made */
833 /*****************************************************************************/
834 /* Optimize shifts */
835 /*****************************************************************************/
839 static unsigned OptShift1 (CodeSeg* S)
840 /* A call to the shlaxN routine may get replaced by one or more asl insns
841 * if the value of X is not used later.
844 unsigned Changes = 0;
846 /* Walk over the entries */
848 while (I < CS_GetEntryCount (S)) {
851 CodeEntry* E = CS_GetEntry (S, I);
853 /* Check for the sequence */
854 if (E->OPC == OP65_JSR &&
855 (strncmp (E->Arg, "shlax", 5) == 0 ||
856 strncmp (E->Arg, "aslax", 5) == 0) &&
857 strlen (E->Arg) == 6 &&
858 IsDigit (E->Arg[5]) &&
859 !RegXUsed (S, I+1)) {
861 /* Insert shift insns */
862 unsigned Count = E->Arg[5] - '0';
864 CodeEntry* X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
865 CS_InsertEntry (S, X, I+1);
868 /* Delete the call to shlax */
871 /* Remember, we had changes */
881 /* Return the number of changes made */
887 /*****************************************************************************/
888 /* Optimizations for compares */
889 /*****************************************************************************/
893 static unsigned OptCmp1 (CodeSeg* S)
894 /* Search for the sequence
906 unsigned Changes = 0;
908 /* Walk over the entries */
910 while (I < CS_GetEntryCount (S)) {
915 CodeEntry* E = CS_GetEntry (S, I);
917 /* Check for the sequence */
918 if (E->OPC == OP65_STX &&
919 CS_GetEntries (S, L, I+1, 2) &&
920 L[0]->OPC == OP65_STX &&
921 strcmp (L[0]->Arg, "tmp1") == 0 &&
922 !CE_HasLabel (L[0]) &&
923 L[1]->OPC == OP65_ORA &&
924 strcmp (L[1]->Arg, "tmp1") == 0 &&
925 !CE_HasLabel (L[1])) {
927 /* Remove the remaining instructions */
928 CS_DelEntries (S, I+1, 2);
930 /* Insert the ora instead */
931 CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
933 /* Remember, we had changes */
943 /* Return the number of changes made */
949 static unsigned OptCmp2 (CodeSeg* S)
952 * lda/and/ora/eor ...
956 * lda/and/ora/eor ...
960 * and remove the cmp.
963 unsigned Changes = 0;
965 /* Walk over the entries */
967 while (I < CS_GetEntryCount (S)) {
972 CodeEntry* E = CS_GetEntry (S, I);
974 /* Check for the sequence */
975 if ((E->OPC == OP65_ADC ||
976 E->OPC == OP65_AND ||
977 E->OPC == OP65_DEA ||
978 E->OPC == OP65_EOR ||
979 E->OPC == OP65_INA ||
980 E->OPC == OP65_LDA ||
981 E->OPC == OP65_ORA ||
982 E->OPC == OP65_PLA ||
983 E->OPC == OP65_SBC ||
984 E->OPC == OP65_TXA ||
985 E->OPC == OP65_TYA) &&
986 CS_GetEntries (S, L, I+1, 2) &&
987 IsCmpToZero (L[0]) &&
988 !CE_HasLabel (L[0]) &&
989 ((L[1]->Info & OF_FBRA) != 0 ||
990 (L[1]->OPC == OP65_JSR &&
991 FindBoolCmpCond (L[1]->Arg) != CMP_INV)) &&
992 !CE_HasLabel (L[1])) {
994 /* Remove the compare */
995 CS_DelEntry (S, I+1);
997 /* Remember, we had changes */
1007 /* Return the number of changes made */
1013 static unsigned OptCmp3 (CodeSeg* S)
1023 * If a is zero, we may remove the compare. If a and b are both zero, we may
1024 * replace it by the sequence
1030 * L1 may be either the label at the branch instruction, or the target label
1031 * of this instruction.
1034 unsigned Changes = 0;
1036 /* Walk over the entries */
1038 while (I < CS_GetEntryCount (S)) {
1042 /* Get next entry */
1043 CodeEntry* E = CS_GetEntry (S, I);
1045 /* Check for the sequence */
1046 if (E->OPC == OP65_LDA &&
1047 CS_GetEntries (S, L, I+1, 5) &&
1048 L[0]->OPC == OP65_LDX &&
1049 !CE_HasLabel (L[0]) &&
1050 IsImmCmp16 (S, L+1)) {
1052 if (L[1]->Num == 0 && L[3]->Num == 0) {
1053 /* The value is zero, we may use the simple code version. */
1054 CE_ReplaceOPC (L[0], OP65_ORA);
1055 CS_DelEntries (S, I+2, 3);
1057 /* Move the lda instruction after the first branch. This will
1058 * improve speed, since the load is delayed after the first
1061 CS_MoveEntry (S, I, I+4);
1063 /* We will replace the ldx/cpx by lda/cmp */
1064 CE_ReplaceOPC (L[0], OP65_LDA);
1065 CE_ReplaceOPC (L[1], OP65_CMP);
1067 /* Beware: If the first LDA instruction had a label, we have
1068 * to move this label to the top of the sequence again.
1070 if (CE_HasLabel (E)) {
1071 CS_MoveLabels (S, E, L[0]);
1084 /* Return the number of changes made */
1090 static unsigned OptCmp4 (CodeSeg* S)
1091 /* Optimize compares of local variables:
1104 unsigned Changes = 0;
1106 /* Walk over the entries */
1108 while (I < CS_GetEntryCount (S)) {
1112 /* Check for the sequence */
1113 if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
1115 if (L[5]->Num == 0 && L[7]->Num == 0) {
1117 /* The value is zero, we may use the simple code version:
1124 CE_ReplaceOPC (L[4], OP65_ORA);
1125 CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */
1126 CS_DelEntry (S, I+2); /* tax */
1130 /* Change the code to just use the A register. Move the load
1131 * of the low byte after the first branch if possible:
1142 CS_DelEntry (S, I+2); /* tax */
1143 CE_ReplaceOPC (L[5], OP65_CMP); /* cpx -> cmp */
1144 CS_MoveEntry (S, I+4, I+2); /* cmp */
1145 CS_MoveEntry (S, I+5, I+3); /* bne */
1157 /* Return the number of changes made */
1163 static unsigned OptCmp5 (CodeSeg* S)
1164 /* Search for calls to compare subroutines followed by a conditional branch
1165 * and replace them by cheaper versions, since the branch means that the
1166 * boolean value returned by these routines is not needed (we may also check
1167 * that explicitly, but for the current code generator it is always true).
1170 unsigned Changes = 0;
1172 /* Walk over the entries */
1174 while (I < CS_GetEntryCount (S)) {
1179 /* Get next entry */
1180 CodeEntry* E = CS_GetEntry (S, I);
1182 /* Check for the sequence */
1183 if (E->OPC == OP65_JSR &&
1184 (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
1185 (N = CS_GetNextEntry (S, I)) != 0 &&
1186 (N->Info & OF_ZBRA) != 0 &&
1189 /* The tos... functions will return a boolean value in a/x and
1190 * the Z flag says if this value is zero or not. We will call
1191 * a cheaper subroutine instead, one that does not return a
1192 * boolean value but only valid flags. Note: jeq jumps if
1193 * the condition is not met, jne jumps if the condition is met.
1194 * Invert the code if we jump on condition not met.
1196 if (GetBranchCond (N->OPC) == BC_EQ) {
1197 /* Jumps if condition false, invert condition */
1198 Cond = CmpInvertTab [Cond];
1201 /* Replace the subroutine call. */
1202 E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
1203 CS_InsertEntry (S, E, I+1);
1206 /* Replace the conditional branch */
1207 ReplaceCmp (S, I+1, Cond);
1209 /* Remember, we had changes */
1219 /* Return the number of changes made */
1225 static unsigned OptCmp6 (CodeSeg* S)
1226 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
1230 unsigned Changes = 0;
1232 /* Walk over the entries */
1234 while (I < CS_GetEntryCount (S)) {
1238 /* Get next entry */
1239 CodeEntry* E = CS_GetEntry (S, I);
1241 /* Check for the sequence */
1242 if ((E->OPC == OP65_LDX) &&
1243 CS_GetEntries (S, L, I+1, 2) &&
1244 L[0]->OPC == OP65_TXA &&
1245 !CE_HasLabel (L[0]) &&
1246 (L[1]->Info & OF_FBRA) != 0 &&
1247 !CE_HasLabel (L[1]) &&
1248 !RegAUsed (S, I+3)) {
1250 /* Remove the txa */
1251 CS_DelEntry (S, I+1);
1253 /* Remember, we had changes */
1263 /* Return the number of changes made */
1269 static unsigned OptCmp7 (CodeSeg* S)
1270 /* Check for register compares where the contents of the register and therefore
1271 * the result of the compare is known.
1274 unsigned Changes = 0;
1277 /* Generate register info for this step */
1280 /* Walk over the entries */
1282 while (I < CS_GetEntryCount (S)) {
1286 /* Get next entry */
1287 CodeEntry* E = CS_GetEntry (S, I);
1289 /* Check for a compare against an immediate value */
1290 if ((E->Info & OF_CMP) != 0 &&
1291 (RegVal = GetCmpRegVal (E)) >= 0 &&
1294 /* We are able to evaluate the compare at compile time. Check if
1295 * one or more branches are ahead.
1297 unsigned JumpsChanged = 0;
1299 while ((N = CS_GetNextEntry (S, I)) != 0 && /* Followed by something.. */
1300 (N->Info & OF_CBRA) != 0 && /* ..that is a cond branch.. */
1301 !CE_HasLabel (N)) { /* ..and has no label */
1303 /* Evaluate the branch condition */
1305 switch (GetBranchCond (N->OPC)) {
1307 Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num);
1311 Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num);
1315 Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num);
1319 Cond = ((signed char)RegVal) < ((signed char)E->Num);
1323 Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num);
1327 Cond = ((signed char)RegVal) >= ((signed char)E->Num);
1332 /* Not set by the compare operation, bail out (Note:
1333 * Just skipping anything here is rather stupid, but
1334 * the sequence is never generated by the compiler,
1335 * so it's quite safe to skip).
1340 Internal ("Unknown branch condition");
1344 /* If the condition is false, we may remove the jump. Otherwise
1345 * the branch will always be taken, so we may replace it by a
1346 * jump (and bail out).
1349 CS_DelEntry (S, I+1);
1351 CodeLabel* L = N->JumpTo;
1352 CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, L->Name, L, N->LI);
1353 CS_InsertEntry (S, X, I+2);
1354 CS_DelEntry (S, I+1);
1357 /* Remember, we had changes */
1362 /* If we have made changes above, we may also remove the compare */
1375 /* Free register info */
1378 /* Return the number of changes made */
1384 /*****************************************************************************/
1385 /* Optimize tests */
1386 /*****************************************************************************/
1390 static unsigned OptTest1 (CodeSeg* S)
1397 * if X is zero, the sequence may be changed to
1402 * which may be optimized further by another step.
1404 * If A is zero, the sequence may be changed to
1411 unsigned Changes = 0;
1414 /* Generate register info for this step */
1417 /* Walk over the entries */
1419 while (I < CS_GetEntryCount (S)) {
1423 /* Get next entry */
1424 L[0] = CS_GetEntry (S, I);
1426 /* Check if it's the sequence we're searching for */
1427 if (L[0]->OPC == OP65_STX &&
1428 CS_GetEntries (S, L+1, I+1, 2) &&
1429 !CE_HasLabel (L[1]) &&
1430 L[1]->OPC == OP65_ORA &&
1431 strcmp (L[0]->Arg, L[1]->Arg) == 0 &&
1432 !CE_HasLabel (L[2]) &&
1433 (L[2]->Info & OF_ZBRA) != 0) {
1435 /* Check if X is zero */
1436 if (L[0]->RI->In.RegX == 0) {
1438 /* Insert the compare */
1439 CodeEntry* N = NewCodeEntry (OP65_CMP, AM65_IMM, "$00", 0, L[0]->LI);
1440 CS_InsertEntry (S, N, I+2);
1442 /* Remove the two other insns */
1443 CS_DelEntry (S, I+1);
1446 /* We had changes */
1449 /* Check if A is zero */
1450 } else if (L[1]->RI->In.RegA == 0) {
1452 /* Insert the txa */
1453 CodeEntry* N = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, L[1]->LI);
1454 CS_InsertEntry (S, N, I+2);
1456 /* Remove the two other insns */
1457 CS_DelEntry (S, I+1);
1460 /* We had changes */
1470 /* Free register info */
1473 /* Return the number of changes made */
1479 /*****************************************************************************/
1480 /* nega optimizations */
1481 /*****************************************************************************/
1485 static unsigned OptNegA1 (CodeSeg* S)
1492 * Remove the ldx if the lda does not use it.
1495 unsigned Changes = 0;
1497 /* Walk over the entries */
1499 while (I < CS_GetEntryCount (S)) {
1503 /* Get next entry */
1504 CodeEntry* E = CS_GetEntry (S, I);
1506 /* Check for a ldx */
1507 if (E->OPC == OP65_LDX &&
1508 E->AM == AM65_IMM &&
1509 (E->Flags & CEF_NUMARG) != 0 &&
1511 CS_GetEntries (S, L, I+1, 2) &&
1512 L[0]->OPC == OP65_LDA &&
1513 (L[0]->Use & REG_X) == 0 &&
1514 !CE_HasLabel (L[0]) &&
1515 L[1]->OPC == OP65_JSR &&
1516 strcmp (L[1]->Arg, "bnega") == 0 &&
1517 !CE_HasLabel (L[1])) {
1519 /* Remove the ldx instruction */
1522 /* Remember, we had changes */
1532 /* Return the number of changes made */
1538 static unsigned OptNegA2 (CodeSeg* S)
1545 * Adjust the conditional branch and remove the call to the subroutine.
1548 unsigned Changes = 0;
1550 /* Walk over the entries */
1552 while (I < CS_GetEntryCount (S)) {
1556 /* Get next entry */
1557 CodeEntry* E = CS_GetEntry (S, I);
1559 /* Check for the sequence */
1560 if ((E->OPC == OP65_ADC ||
1561 E->OPC == OP65_AND ||
1562 E->OPC == OP65_DEA ||
1563 E->OPC == OP65_EOR ||
1564 E->OPC == OP65_INA ||
1565 E->OPC == OP65_LDA ||
1566 E->OPC == OP65_ORA ||
1567 E->OPC == OP65_PLA ||
1568 E->OPC == OP65_SBC ||
1569 E->OPC == OP65_TXA ||
1570 E->OPC == OP65_TYA) &&
1571 CS_GetEntries (S, L, I+1, 2) &&
1572 L[0]->OPC == OP65_JSR &&
1573 strcmp (L[0]->Arg, "bnega") == 0 &&
1574 !CE_HasLabel (L[0]) &&
1575 (L[1]->Info & OF_ZBRA) != 0 &&
1576 !CE_HasLabel (L[1])) {
1578 /* Invert the branch */
1579 CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1581 /* Delete the subroutine call */
1582 CS_DelEntry (S, I+1);
1584 /* Remember, we had changes */
1594 /* Return the number of changes made */
1600 /*****************************************************************************/
1601 /* negax optimizations */
1602 /*****************************************************************************/
1606 static unsigned OptNegAX1 (CodeSeg* S)
1607 /* On a call to bnegax, if X is zero, the result depends only on the value in
1608 * A, so change the call to a call to bnega. This will get further optimized
1609 * later if possible.
1612 unsigned Changes = 0;
1615 /* Generate register info for this step */
1618 /* Walk over the entries */
1620 while (I < CS_GetEntryCount (S)) {
1622 /* Get next entry */
1623 CodeEntry* E = CS_GetEntry (S, I);
1625 /* Check if this is a call to bnegax, and if X is known and zero */
1626 if (E->OPC == OP65_JSR &&
1627 E->RI->In.RegX == 0 &&
1628 strcmp (E->Arg, "bnegax") == 0) {
1630 /* We're cheating somewhat here ... */
1634 /* We had changes */
1643 /* Free register info */
1646 /* Return the number of changes made */
1652 static unsigned OptNegAX2 (CodeSeg* S)
1653 /* Search for the sequence:
1670 unsigned Changes = 0;
1672 /* Walk over the entries */
1674 while (I < CS_GetEntryCount (S)) {
1678 /* Get next entry */
1679 CodeEntry* E = CS_GetEntry (S, I);
1681 /* Check for the sequence */
1682 if (E->OPC == OP65_LDA &&
1683 E->AM == AM65_ZP_INDY &&
1684 CS_GetEntries (S, L, I+1, 5) &&
1685 L[0]->OPC == OP65_TAX &&
1686 L[1]->OPC == OP65_DEY &&
1687 L[2]->OPC == OP65_LDA &&
1688 L[2]->AM == AM65_ZP_INDY &&
1689 strcmp (L[2]->Arg, E->Arg) == 0 &&
1690 !CE_HasLabel (L[2]) &&
1691 L[3]->OPC == OP65_JSR &&
1692 strcmp (L[3]->Arg, "bnegax") == 0 &&
1693 !CE_HasLabel (L[3]) &&
1694 (L[4]->Info & OF_ZBRA) != 0 &&
1695 !CE_HasLabel (L[4])) {
1698 CE_ReplaceOPC (L[2], OP65_ORA);
1700 /* Invert the branch */
1701 CE_ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
1703 /* Delete the entries no longer needed. Beware: Deleting entries
1704 * will change the indices.
1706 CS_DelEntry (S, I+4); /* jsr bnegax */
1707 CS_DelEntry (S, I+1); /* tax */
1709 /* Remember, we had changes */
1719 /* Return the number of changes made */
1725 static unsigned OptNegAX3 (CodeSeg* S)
1726 /* Search for the sequence:
1740 unsigned Changes = 0;
1742 /* Walk over the entries */
1744 while (I < CS_GetEntryCount (S)) {
1748 /* Get next entry */
1749 CodeEntry* E = CS_GetEntry (S, I);
1751 /* Check for the sequence */
1752 if (E->OPC == OP65_LDA &&
1753 CS_GetEntries (S, L, I+1, 3) &&
1754 L[0]->OPC == OP65_LDX &&
1755 !CE_HasLabel (L[0]) &&
1756 L[1]->OPC == OP65_JSR &&
1757 strcmp (L[1]->Arg, "bnegax") == 0 &&
1758 !CE_HasLabel (L[1]) &&
1759 (L[2]->Info & OF_ZBRA) != 0 &&
1760 !CE_HasLabel (L[2])) {
1763 CE_ReplaceOPC (L[0], OP65_ORA);
1765 /* Invert the branch */
1766 CE_ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
1768 /* Delete the subroutine call */
1769 CS_DelEntry (S, I+2);
1771 /* Remember, we had changes */
1781 /* Return the number of changes made */
1787 static unsigned OptNegAX4 (CodeSeg* S)
1788 /* Search for the sequence:
1794 * and replace it by:
1801 unsigned Changes = 0;
1803 /* Walk over the entries */
1805 while (I < CS_GetEntryCount (S)) {
1809 /* Get next entry */
1810 CodeEntry* E = CS_GetEntry (S, I);
1812 /* Check for the sequence */
1813 if (E->OPC == OP65_JSR &&
1814 CS_GetEntries (S, L, I+1, 2) &&
1815 L[0]->OPC == OP65_JSR &&
1816 strncmp (L[0]->Arg,"bnega",5) == 0 &&
1817 !CE_HasLabel (L[0]) &&
1818 (L[1]->Info & OF_ZBRA) != 0 &&
1819 !CE_HasLabel (L[1])) {
1823 /* Check if we're calling bnega or bnegax */
1824 int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
1826 /* Insert apropriate test code */
1829 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
1830 CS_InsertEntry (S, X, I+2);
1833 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI);
1834 CS_InsertEntry (S, X, I+2);
1835 X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI);
1836 CS_InsertEntry (S, X, I+3);
1839 /* Delete the subroutine call */
1840 CS_DelEntry (S, I+1);
1842 /* Invert the branch */
1843 CE_ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
1845 /* Remember, we had changes */
1855 /* Return the number of changes made */
1861 /*****************************************************************************/
1862 /* Optimize stores through pointers */
1863 /*****************************************************************************/
1867 static unsigned OptPtrStore1Sub (CodeSeg* S, unsigned I, CodeEntry** const L)
1868 /* Check if this is one of the allowed suboperation for OptPtrStore1 */
1870 /* Check for a label attached to the entry */
1871 if (CE_HasLabel (L[0])) {
1875 /* Check for single insn sub ops */
1876 if (L[0]->OPC == OP65_AND ||
1877 L[0]->OPC == OP65_EOR ||
1878 L[0]->OPC == OP65_ORA ||
1879 (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shlax", 5) == 0) ||
1880 (L[0]->OPC == OP65_JSR && strncmp (L[0]->Arg, "shrax", 5) == 0)) {
1885 } else if (L[0]->OPC == OP65_CLC &&
1886 (L[1] = CS_GetNextEntry (S, I)) != 0 &&
1887 L[1]->OPC == OP65_ADC &&
1888 !CE_HasLabel (L[1])) {
1890 } else if (L[0]->OPC == OP65_SEC &&
1891 (L[1] = CS_GetNextEntry (S, I)) != 0 &&
1892 L[1]->OPC == OP65_SBC &&
1893 !CE_HasLabel (L[1])) {
1905 static unsigned OptPtrStore1 (CodeSeg* S)
1906 /* Search for the sequence:
1915 * and replace it by:
1927 unsigned Changes = 0;
1929 /* Walk over the entries */
1931 while (I < CS_GetEntryCount (S)) {
1936 /* Get next entry */
1937 L[0] = CS_GetEntry (S, I);
1939 /* Check for the sequence */
1940 if (L[0]->OPC == OP65_JSR &&
1941 strcmp (L[0]->Arg, "pushax") == 0 &&
1942 CS_GetEntries (S, L+1, I+1, 3) &&
1943 L[1]->OPC == OP65_LDY &&
1944 CE_KnownImm (L[1]) &&
1945 !CE_HasLabel (L[1]) &&
1946 L[2]->OPC == OP65_JSR &&
1947 strcmp (L[2]->Arg, "ldauidx") == 0 &&
1948 !CE_HasLabel (L[2]) &&
1949 (K = OptPtrStore1Sub (S, I+3, L+3)) > 0 &&
1950 CS_GetEntries (S, L+3+K, I+3+K, 2) &&
1951 L[3+K]->OPC == OP65_LDY &&
1952 CE_KnownImm (L[3+K]) &&
1953 !CE_HasLabel (L[3+K]) &&
1954 L[4+K]->OPC == OP65_JSR &&
1955 strcmp (L[4+K]->Arg, "staspidx") == 0 &&
1956 !CE_HasLabel (L[4+K])) {
1960 /* Create and insert the stores */
1961 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
1962 CS_InsertEntry (S, X, I+1);
1964 X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
1965 CS_InsertEntry (S, X, I+2);
1967 /* Delete the call to pushax */
1970 /* Delete the call to ldauidx */
1971 CS_DelEntry (S, I+3);
1973 /* Insert the load from ptr1 */
1974 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
1975 CS_InsertEntry (S, X, I+3);
1976 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[2]->LI);
1977 CS_InsertEntry (S, X, I+4);
1979 /* Insert the store through ptr1 */
1980 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
1981 CS_InsertEntry (S, X, I+6+K);
1983 /* Delete the call to staspidx */
1984 CS_DelEntry (S, I+7+K);
1986 /* Remember, we had changes */
1996 /* Return the number of changes made */
2002 static unsigned OptPtrStore2 (CodeSeg* S)
2003 /* Search for the sequence:
2010 * and replace it by:
2019 unsigned Changes = 0;
2021 /* Walk over the entries */
2023 while (I < CS_GetEntryCount (S)) {
2027 /* Get next entry */
2028 L[0] = CS_GetEntry (S, I);
2030 /* Check for the sequence */
2031 if (L[0]->OPC == OP65_JSR &&
2032 strcmp (L[0]->Arg, "pushax") == 0 &&
2033 CS_GetEntries (S, L+1, I+1, 3) &&
2034 L[1]->OPC == OP65_LDA &&
2035 !CE_HasLabel (L[1]) &&
2036 L[2]->OPC == OP65_LDY &&
2037 !CE_HasLabel (L[2]) &&
2038 L[3]->OPC == OP65_JSR &&
2039 strcmp (L[3]->Arg, "staspidx") == 0 &&
2040 !CE_HasLabel (L[3])) {
2044 /* Create and insert the stores */
2045 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2046 CS_InsertEntry (S, X, I+1);
2048 X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2049 CS_InsertEntry (S, X, I+2);
2051 /* Delete the call to pushax */
2054 /* Insert the store through ptr1 */
2055 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
2056 CS_InsertEntry (S, X, I+4);
2058 /* Delete the call to staspidx */
2059 CS_DelEntry (S, I+5);
2061 /* Remember, we had changes */
2071 /* Return the number of changes made */
2077 /*****************************************************************************/
2078 /* Optimize loads through pointers */
2079 /*****************************************************************************/
2083 static unsigned OptPtrLoad1 (CodeSeg* S)
2084 /* Search for the sequence:
2088 * lda (sp),y # May be any destination
2092 * and replace it by:
2103 unsigned Changes = 0;
2105 /* Walk over the entries */
2107 while (I < CS_GetEntryCount (S)) {
2111 /* Get next entry */
2112 L[0] = CS_GetEntry (S, I);
2114 /* Check for the sequence */
2115 if (L[0]->OPC == OP65_TAX &&
2116 CS_GetEntries (S, L+1, I+1, 4) &&
2117 L[1]->OPC == OP65_DEY &&
2118 !CE_HasLabel (L[1]) &&
2119 L[2]->OPC == OP65_LDA &&
2120 !CE_HasLabel (L[2]) &&
2121 L[3]->OPC == OP65_LDY &&
2122 !CE_HasLabel (L[3]) &&
2123 L[4]->OPC == OP65_JSR &&
2124 strcmp (L[4]->Arg, "ldauidx") == 0 &&
2125 !CE_HasLabel (L[4])) {
2129 /* Store the high byte and remove the TAX instead */
2130 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2131 CS_InsertEntry (S, X, I+1);
2134 /* Store the low byte */
2135 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[2]->LI);
2136 CS_InsertEntry (S, X, I+3);
2138 /* Delete the call to ldauidx */
2139 CS_DelEntry (S, I+5);
2141 /* Load high and low byte */
2142 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[3]->LI);
2143 CS_InsertEntry (S, X, I+5);
2144 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[3]->LI);
2145 CS_InsertEntry (S, X, I+6);
2147 /* Remember, we had changes */
2157 /* Return the number of changes made */
2163 static unsigned OptPtrLoad2 (CodeSeg* S)
2164 /* Search for the sequence:
2175 * and replace it by:
2187 unsigned Changes = 0;
2189 /* Walk over the entries */
2191 while (I < CS_GetEntryCount (S)) {
2195 /* Get next entry */
2196 L[0] = CS_GetEntry (S, I);
2198 /* Check for the sequence */
2199 if (L[0]->OPC == OP65_ADC &&
2200 CS_GetEntries (S, L+1, I+1, 7) &&
2201 L[1]->OPC == OP65_TAY &&
2202 !CE_HasLabel (L[1]) &&
2203 L[2]->OPC == OP65_TXA &&
2204 !CE_HasLabel (L[2]) &&
2205 L[3]->OPC == OP65_ADC &&
2206 !CE_HasLabel (L[3]) &&
2207 L[4]->OPC == OP65_TAX &&
2208 !CE_HasLabel (L[4]) &&
2209 L[5]->OPC == OP65_TYA &&
2210 !CE_HasLabel (L[5]) &&
2211 L[6]->OPC == OP65_LDY &&
2212 !CE_HasLabel (L[6]) &&
2213 L[7]->OPC == OP65_JSR &&
2214 strcmp (L[7]->Arg, "ldauidx") == 0 &&
2215 !CE_HasLabel (L[7])) {
2219 /* Store the low byte and remove the TAY instead */
2220 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2221 CS_InsertEntry (S, X, I+1);
2222 CS_DelEntry (S, I+2);
2224 /* Store the high byte */
2225 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[3]->LI);
2226 CS_InsertEntry (S, X, I+4);
2228 /* Delete more transfer insns */
2229 CS_DelEntry (S, I+6);
2230 CS_DelEntry (S, I+5);
2232 /* Delete the call to ldauidx */
2233 CS_DelEntry (S, I+6);
2235 /* Load high and low byte */
2236 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
2237 CS_InsertEntry (S, X, I+6);
2238 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
2239 CS_InsertEntry (S, X, I+7);
2241 /* Remember, we had changes */
2251 /* Return the number of changes made */
2257 static unsigned OptPtrLoad3 (CodeSeg* S)
2258 /* Search for the sequence:
2270 * and replace it by:
2283 unsigned Changes = 0;
2285 /* Walk over the entries */
2287 while (I < CS_GetEntryCount (S)) {
2291 /* Get next entry */
2292 L[0] = CS_GetEntry (S, I);
2294 /* Check for the sequence */
2295 if (L[0]->OPC == OP65_ADC &&
2296 CS_GetEntries (S, L+1, I+1, 8) &&
2297 L[1]->OPC == OP65_PHA &&
2298 !CE_HasLabel (L[1]) &&
2299 L[2]->OPC == OP65_TXA &&
2300 !CE_HasLabel (L[2]) &&
2301 L[3]->OPC == OP65_INY &&
2302 !CE_HasLabel (L[3]) &&
2303 L[4]->OPC == OP65_ADC &&
2304 !CE_HasLabel (L[4]) &&
2305 L[5]->OPC == OP65_TAX &&
2306 !CE_HasLabel (L[5]) &&
2307 L[6]->OPC == OP65_PLA &&
2308 !CE_HasLabel (L[6]) &&
2309 L[7]->OPC == OP65_LDY &&
2310 !CE_HasLabel (L[7]) &&
2311 L[8]->OPC == OP65_JSR &&
2312 strcmp (L[8]->Arg, "ldauidx") == 0 &&
2313 !CE_HasLabel (L[8])) {
2317 /* Store the low byte and remove the PHA instead */
2318 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2319 CS_InsertEntry (S, X, I+1);
2320 CS_DelEntry (S, I+2);
2322 /* Store the high byte */
2323 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1+1", 0, L[4]->LI);
2324 CS_InsertEntry (S, X, I+5);
2326 /* Delete more transfer and PLA insns */
2327 CS_DelEntry (S, I+7);
2328 CS_DelEntry (S, I+6);
2330 /* Delete the call to ldauidx */
2331 CS_DelEntry (S, I+7);
2333 /* Load high and low byte */
2334 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[6]->LI);
2335 CS_InsertEntry (S, X, I+7);
2336 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[6]->LI);
2337 CS_InsertEntry (S, X, I+8);
2339 /* Remember, we had changes */
2349 /* Return the number of changes made */
2355 static unsigned OptPtrLoad4 (CodeSeg* S)
2356 /* Search for the sequence:
2367 * and replace it by:
2374 unsigned Changes = 0;
2376 /* Walk over the entries */
2378 while (I < CS_GetEntryCount (S)) {
2383 /* Get next entry */
2384 L[0] = CS_GetEntry (S, I);
2386 /* Check for the sequence */
2387 if (L[0]->OPC == OP65_LDA &&
2388 L[0]->AM == AM65_IMM &&
2389 CS_GetEntries (S, L+1, I+1, 7) &&
2390 L[1]->OPC == OP65_LDX &&
2391 L[1]->AM == AM65_IMM &&
2392 !CE_HasLabel (L[1]) &&
2393 L[2]->OPC == OP65_CLC &&
2394 !CE_HasLabel (L[2]) &&
2395 L[3]->OPC == OP65_ADC &&
2396 (L[3]->AM == AM65_ABS || L[3]->AM == AM65_ZP) &&
2397 !CE_HasLabel (L[3]) &&
2398 (L[4]->OPC == OP65_BCC || L[4]->OPC == OP65_JCC) &&
2399 L[4]->JumpTo != 0 &&
2400 L[4]->JumpTo->Owner == L[6] &&
2401 !CE_HasLabel (L[4]) &&
2402 L[5]->OPC == OP65_INX &&
2403 !CE_HasLabel (L[5]) &&
2404 L[6]->OPC == OP65_LDY &&
2405 CE_KnownImm (L[6]) &&
2407 L[7]->OPC == OP65_JSR &&
2408 strcmp (L[7]->Arg, "ldauidx") == 0 &&
2409 !CE_HasLabel (L[7]) &&
2410 /* Check the label last because this is quite costly */
2411 (Len = strlen (L[0]->Arg)) > 3 &&
2412 L[0]->Arg[0] == '<' &&
2413 L[0]->Arg[1] == '(' &&
2414 strlen (L[1]->Arg) == Len &&
2415 L[1]->Arg[0] == '>' &&
2416 memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
2421 /* We will create all the new stuff behind the current one so
2422 * we keep the line references.
2424 X = NewCodeEntry (OP65_LDX, L[3]->AM, L[3]->Arg, 0, L[0]->LI);
2425 CS_InsertEntry (S, X, I+8);
2427 Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
2428 Label[Len-3] = '\0';
2429 X = NewCodeEntry (OP65_LDA, AM65_ABSX, Label, 0, L[0]->LI);
2430 CS_InsertEntry (S, X, I+9);
2433 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2434 CS_InsertEntry (S, X, I+10);
2436 /* Remove the old code */
2437 CS_DelEntries (S, I, 8);
2439 /* Remember, we had changes */
2449 /* Return the number of changes made */
2455 static unsigned OptPtrLoad5 (CodeSeg* S)
2456 /* Search for the sequence:
2468 * and replace it by:
2477 unsigned Changes = 0;
2479 /* Walk over the entries */
2481 while (I < CS_GetEntryCount (S)) {
2486 /* Get next entry */
2487 L[0] = CS_GetEntry (S, I);
2489 /* Check for the sequence */
2490 if (L[0]->OPC == OP65_LDA &&
2491 L[0]->AM == AM65_IMM &&
2492 CS_GetEntries (S, L+1, I+1, 8) &&
2493 L[1]->OPC == OP65_LDX &&
2494 L[1]->AM == AM65_IMM &&
2495 !CE_HasLabel (L[1]) &&
2496 L[2]->OPC == OP65_LDY &&
2497 CE_KnownImm (L[2]) &&
2498 !CE_HasLabel (L[2]) &&
2499 L[3]->OPC == OP65_CLC &&
2500 !CE_HasLabel (L[3]) &&
2501 L[4]->OPC == OP65_ADC &&
2502 L[4]->AM == AM65_ZP_INDY &&
2503 !CE_HasLabel (L[4]) &&
2504 (L[5]->OPC == OP65_BCC || L[5]->OPC == OP65_JCC) &&
2505 L[5]->JumpTo != 0 &&
2506 L[5]->JumpTo->Owner == L[7] &&
2507 !CE_HasLabel (L[5]) &&
2508 L[6]->OPC == OP65_INX &&
2509 !CE_HasLabel (L[6]) &&
2510 L[7]->OPC == OP65_LDY &&
2511 CE_KnownImm (L[7]) &&
2513 L[8]->OPC == OP65_JSR &&
2514 strcmp (L[8]->Arg, "ldauidx") == 0 &&
2515 !CE_HasLabel (L[8]) &&
2516 /* Check the label last because this is quite costly */
2517 (Len = strlen (L[0]->Arg)) > 3 &&
2518 L[0]->Arg[0] == '<' &&
2519 L[0]->Arg[1] == '(' &&
2520 strlen (L[1]->Arg) == Len &&
2521 L[1]->Arg[0] == '>' &&
2522 memcmp (L[0]->Arg+1, L[1]->Arg+1, Len-1) == 0) {
2528 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, L[4]->Arg, 0, L[0]->LI);
2529 CS_InsertEntry (S, X, I+3);
2532 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI);
2533 CS_InsertEntry (S, X, I+4);
2536 Label = memcpy (xmalloc (Len-2), L[0]->Arg+2, Len-3);
2537 Label[Len-3] = '\0';
2538 X = NewCodeEntry (OP65_LDA, AM65_ABSX, Label, 0, L[0]->LI);
2539 CS_InsertEntry (S, X, I+5);
2543 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2544 CS_InsertEntry (S, X, I+6);
2546 /* Remove the old code */
2547 CS_DelEntries (S, I, 2);
2548 CS_DelEntries (S, I+5, 6);
2550 /* Remember, we had changes */
2560 /* Return the number of changes made */
2566 static unsigned OptPtrLoad6 (CodeSeg* S)
2567 /* Search for the sequence
2572 * and replace it by:
2580 * This step must be execute *after* OptPtrLoad1!
2583 unsigned Changes = 0;
2585 /* Walk over the entries */
2587 while (I < CS_GetEntryCount (S)) {
2591 /* Get next entry */
2592 L[0] = CS_GetEntry (S, I);
2594 /* Check for the sequence */
2595 if (L[0]->OPC == OP65_LDY &&
2596 CS_GetEntries (S, L+1, I+1, 1) &&
2597 L[1]->OPC == OP65_JSR &&
2598 strcmp (L[1]->Arg, "ldauidx") == 0 &&
2599 !CE_HasLabel (L[1])) {
2603 /* Store the high byte */
2604 X = NewCodeEntry (OP65_STA, AM65_ZP, "ptr1", 0, L[0]->LI);
2605 CS_InsertEntry (S, X, I+1);
2607 /* Store the low byte */
2608 X = NewCodeEntry (OP65_STX, AM65_ZP, "ptr1+1", 0, L[0]->LI);
2609 CS_InsertEntry (S, X, I+2);
2611 /* Delete the call to ldauidx */
2612 CS_DelEntry (S, I+3);
2614 /* Load the high and low byte */
2615 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, L[0]->LI);
2616 CS_InsertEntry (S, X, I+3);
2617 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "ptr1", 0, L[0]->LI);
2618 CS_InsertEntry (S, X, I+4);
2620 /* Remember, we had changes */
2630 /* Return the number of changes made */
2636 /*****************************************************************************/
2638 /*****************************************************************************/
2642 /* Types of optimization steps */
2644 optPre, /* Repeated once */
2645 optPreMain, /* Repeated more than once */
2647 optPostMain, /* dito */
2648 optPost /* Repeated once */
2651 /* Table with all the optimization functions */
2652 typedef struct OptFunc OptFunc;
2654 unsigned (*Func) (CodeSeg*); /* Optimizer function */
2655 const char* Name; /* Name of optimizer step */
2656 unsigned char Type; /* Type of this step */
2657 char Disabled; /* True if pass disabled */
2660 /* Macro that builds a table entry */
2661 #define OptEntry(func,type) { func, #func, type, 0 }
2663 /* Table with optimizer steps */
2664 static OptFunc OptFuncs [] = {
2665 /* Optimizes stores through pointers */
2666 OptEntry (OptPtrStore1, optPre),
2667 OptEntry (OptPtrStore2, optPre),
2668 /* Optimize loads through pointers */
2669 OptEntry (OptPtrLoad1, optPre),
2670 OptEntry (OptPtrLoad2, optPre),
2671 OptEntry (OptPtrLoad3, optPre),
2672 OptEntry (OptPtrLoad4, optPre),
2673 OptEntry (OptPtrLoad5, optPre),
2674 OptEntry (OptPtrLoad6, optMain),
2675 /* Optimize calls to nega */
2676 OptEntry (OptNegA1, optMain),
2677 OptEntry (OptNegA2, optMain),
2678 /* Optimize calls to negax */
2679 OptEntry (OptNegAX1, optPre),
2680 OptEntry (OptNegAX2, optPre),
2681 OptEntry (OptNegAX3, optPre),
2682 OptEntry (OptNegAX4, optPre),
2683 /* Optimize subtractions */
2684 OptEntry (OptSub1, optMain),
2685 OptEntry (OptSub2, optMain),
2686 /* Optimize additions */
2687 OptEntry (OptAdd1, optPre),
2688 OptEntry (OptAdd2, optPre),
2689 OptEntry (OptAdd3, optMain),
2690 /* Optimize shifts */
2691 OptEntry (OptShift1, optPre),
2692 /* Optimize jump cascades */
2693 OptEntry (OptJumpCascades, optMain),
2694 /* Remove dead jumps */
2695 OptEntry (OptDeadJumps, optMain),
2696 /* Change jsr/rts to jmp */
2697 OptEntry (OptRTS, optMain),
2698 /* Remove dead code */
2699 OptEntry (OptDeadCode, optMain),
2700 /* Optimize jump targets */
2701 OptEntry (OptJumpTarget, optMain),
2702 /* Optimize conditional branches */
2703 OptEntry (OptCondBranches, optMain),
2704 /* Replace jumps to RTS by RTS */
2705 OptEntry (OptRTSJumps, optMain),
2706 /* Remove calls to the bool transformer subroutines */
2707 OptEntry (OptBoolTransforms, optMain),
2708 /* Optimize compares */
2709 OptEntry (OptCmp1, optMain),
2710 OptEntry (OptCmp2, optMain),
2711 OptEntry (OptCmp3, optMain),
2712 OptEntry (OptCmp4, optMain),
2713 OptEntry (OptCmp5, optMain),
2714 OptEntry (OptCmp6, optMain),
2715 OptEntry (OptCmp7, optMain),
2716 /* Optimize tests */
2717 OptEntry (OptTest1, optMain),
2718 /* Remove unused loads */
2719 OptEntry (OptUnusedLoads, optMain),
2720 OptEntry (OptUnusedStores, optMain),
2721 OptEntry (OptDuplicateLoads, optMain),
2722 OptEntry (OptStoreLoad, optMain),
2723 OptEntry (OptTransfers, optMain),
2724 /* Optimize operations that use the stack to pass operands */
2725 OptEntry (OptStackOps, optMain),
2726 /* Optimize branch distance */
2727 OptEntry (OptBranchDist, optPost),
2732 static OptFunc* FindOptStep (const char* Name)
2733 /* Find an optimizer step by name in the table and return a pointer. Print an
2734 * error and call AbEnd if not found.
2739 /* Run all optimization steps */
2740 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2741 if (strcmp (OptFuncs[I].Name, Name) == 0) {
2748 AbEnd ("Optimization step `%s' not found", Name);
2754 void DisableOpt (const char* Name)
2755 /* Disable the optimization with the given name */
2757 if (strcmp (Name, "any") == 0) {
2759 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2760 OptFuncs[I].Disabled = 1;
2763 OptFunc* F = FindOptStep (Name);
2770 void EnableOpt (const char* Name)
2771 /* Enable the optimization with the given name */
2773 if (strcmp (Name, "any") == 0) {
2775 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2776 OptFuncs[I].Disabled = 0;
2779 OptFunc* F = FindOptStep (Name);
2786 void ListOptSteps (FILE* F)
2787 /* List all optimization steps */
2790 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2791 fprintf (F, "%s\n", OptFuncs[I].Name);
2797 static void RepeatOptStep (CodeSeg* S, unsigned char Type, unsigned Max)
2798 /* Repeat the optimizer step of type Type at may Max times */
2802 unsigned OptChanges;
2804 /* Repeat max times of until there are no more changes */
2806 /* Reset the number of changes */
2809 /* Keep the user hapy */
2810 Print (stdout, 1, " Optimizer pass %u:\n", ++Pass);
2812 /* Run all optimization steps */
2813 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
2815 /* Get the table entry */
2816 const OptFunc* F = OptFuncs + I;
2818 /* Check if the type matches */
2819 if (F->Type != Type) {
2824 /* Print the name of the following optimizer step */
2825 Print (stdout, 1, " %s:%*s", F->Name, (int) (30-strlen(F->Name)), "");
2827 /* Check if the step is disabled */
2829 Print (stdout, 1, "Disabled\n");
2831 unsigned Changes = F->Func (S);
2832 OptChanges += Changes;
2833 Print (stdout, 1, "%u Changes\n", Changes);
2837 } while (--Max > 0 && OptChanges > 0);
2842 void RunOpt (CodeSeg* S)
2843 /* Run the optimizer */
2846 /* If we shouldn't run the optimizer, bail out */
2851 /* Print the name of the function we are working on */
2853 Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
2855 Print (stdout, 1, "Running optimizer for global code segment\n");
2858 /* Repeat all steps until there are no more changes */
2859 RepeatOptStep (S, optPre, 1);
2860 RepeatOptStep (S, optPreMain, 0xFFFF);
2861 RepeatOptStep (S, optMain, 0xFFFF);
2862 RepeatOptStep (S, optPostMain, 0xFFFF);
2863 RepeatOptStep (S, optPost, 1);