1 /*****************************************************************************/
5 /* Optimize compares */
9 /* (C) 2001-2012, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
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 /*****************************************************************************/
46 /*****************************************************************************/
48 /*****************************************************************************/
52 /* Table used to invert a condition, indexed by condition */
53 static const unsigned char CmpInvertTab [] = {
55 CMP_LE, CMP_LT, CMP_GE, CMP_GT,
56 CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
61 /*****************************************************************************/
62 /* Helper functions */
63 /*****************************************************************************/
67 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
68 /* Helper function for the replacement of routines that return a boolean
69 * followed by a conditional jump. Instead of the boolean value, the condition
70 * codes are evaluated directly.
71 * I is the index of the conditional branch, the sequence is already checked
79 CodeEntry* E = CS_GetEntry (S, I);
81 /* Replace the conditional branch */
85 CE_ReplaceOPC (E, OP65_JEQ);
89 CE_ReplaceOPC (E, OP65_JNE);
98 if ((N = CS_GetNextEntry (S, I)) == 0) {
100 Internal ("Invalid program flow");
102 L = CS_GenLabel (S, N);
103 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
104 CS_InsertEntry (S, N, I);
105 CE_ReplaceOPC (E, OP65_JPL);
109 CE_ReplaceOPC (E, OP65_JPL);
113 CE_ReplaceOPC (E, OP65_JMI);
121 CE_ReplaceOPC (E, OP65_JMI);
123 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
124 CS_InsertEntry (S, N, I+1);
133 if ((N = CS_GetNextEntry (S, I)) == 0) {
135 Internal ("Invalid program flow");
137 L = CS_GenLabel (S, N);
138 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
139 CS_InsertEntry (S, N, I);
140 CE_ReplaceOPC (E, OP65_JCS);
144 CE_ReplaceOPC (E, OP65_JCS);
148 CE_ReplaceOPC (E, OP65_JCC);
156 CE_ReplaceOPC (E, OP65_JCC);
158 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
159 CS_InsertEntry (S, N, I+1);
163 Internal ("Unknown jump condition: %d", Cond);
171 static int IsImmCmp16 (CodeEntry** L)
172 /* Check if the instructions at L are an immidiate compare of a/x:
177 return (L[0]->OPC == OP65_CPX &&
178 L[0]->AM == AM65_IMM &&
179 (L[0]->Flags & CEF_NUMARG) != 0 &&
180 !CE_HasLabel (L[0]) &&
181 (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) &&
183 !CE_HasLabel (L[1]) &&
184 L[2]->OPC == OP65_CMP &&
185 L[2]->AM == AM65_IMM &&
186 (L[2]->Flags & CEF_NUMARG) != 0 &&
187 (L[3]->Info & OF_CBRA) != 0 &&
189 (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
194 static int GetCmpRegVal (const CodeEntry* E)
195 /* Return the register value for an immediate compare */
198 case OP65_CMP: return E->RI->In.RegA;
199 case OP65_CPX: return E->RI->In.RegX;
200 case OP65_CPY: return E->RI->In.RegY;
201 default: Internal ("Invalid opcode in GetCmpRegVal");
202 return 0; /* Not reached */
208 /*****************************************************************************/
209 /* Remove calls to the bool transformer subroutines */
210 /*****************************************************************************/
214 unsigned OptBoolTrans (CodeSeg* S)
215 /* Try to remove the call to boolean transformer routines where the call is
219 unsigned Changes = 0;
221 /* Walk over the entries */
223 while (I < CS_GetEntryCount (S)) {
229 CodeEntry* E = CS_GetEntry (S, I);
231 /* Check for a boolean transformer */
232 if (E->OPC == OP65_JSR &&
233 (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
234 (N = CS_GetNextEntry (S, I)) != 0 &&
235 (N->Info & OF_ZBRA) != 0) {
237 /* Make the boolean transformer unnecessary by changing the
238 * the conditional jump to evaluate the condition flags that
239 * are set after the compare directly. Note: jeq jumps if
240 * the condition is not met, jne jumps if the condition is met.
241 * Invert the code if we jump on condition not met.
243 if (GetBranchCond (N->OPC) == BC_EQ) {
244 /* Jumps if condition false, invert condition */
245 Cond = CmpInvertTab [Cond];
248 /* Check if we can replace the code by something better */
249 ReplaceCmp (S, I+1, Cond);
251 /* Remove the call to the bool transformer */
254 /* Remember, we had changes */
264 /* Return the number of changes made */
270 /*****************************************************************************/
271 /* Optimizations for compares */
272 /*****************************************************************************/
276 unsigned OptCmp1 (CodeSeg* S)
277 /* Search for the sequence
288 unsigned Changes = 0;
290 /* Walk over the entries */
292 while (I < CS_GetEntryCount (S)) {
297 L[0] = CS_GetEntry (S, I);
299 /* Check for the sequence */
300 if (L[0]->OPC == OP65_LDX &&
301 !CS_RangeHasLabel (S, I+1, 2) &&
302 CS_GetEntries (S, L+1, I+1, 2) &&
303 L[1]->OPC == OP65_STX &&
304 strcmp (L[1]->Arg, "tmp1") == 0 &&
305 L[2]->OPC == OP65_ORA &&
306 strcmp (L[2]->Arg, "tmp1") == 0) {
310 /* Insert the ora instead */
311 X = NewCodeEntry (OP65_ORA, L[0]->AM, L[0]->Arg, 0, L[0]->LI);
312 CS_InsertEntry (S, X, I);
314 /* Remove all other instructions */
315 CS_DelEntries (S, I+1, 3);
317 /* Remember, we had changes */
327 /* Return the number of changes made */
333 unsigned OptCmp2 (CodeSeg* S)
334 /* Search for the sequence
346 unsigned Changes = 0;
348 /* Walk over the entries */
350 while (I < CS_GetEntryCount (S)) {
355 CodeEntry* E = CS_GetEntry (S, I);
357 /* Check for the sequence */
358 if (E->OPC == OP65_STX &&
359 !CS_RangeHasLabel (S, I+1, 2) &&
360 CS_GetEntries (S, L, I+1, 2) &&
361 L[0]->OPC == OP65_STX &&
362 strcmp (L[0]->Arg, "tmp1") == 0 &&
363 L[1]->OPC == OP65_ORA &&
364 strcmp (L[1]->Arg, "tmp1") == 0) {
366 /* Remove the remaining instructions */
367 CS_DelEntries (S, I+1, 2);
369 /* Insert the ora instead */
370 CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
372 /* Remember, we had changes */
382 /* Return the number of changes made */
388 unsigned OptCmp3 (CodeSeg* S)
391 * lda/and/ora/eor ...
395 * lda/and/ora/eor ...
399 * and remove the cmp.
402 unsigned Changes = 0;
404 /* Walk over the entries */
406 while (I < CS_GetEntryCount (S)) {
411 L[0] = CS_GetEntry (S, I);
413 /* Check for the sequence */
414 if ((L[0]->OPC == OP65_ADC ||
415 L[0]->OPC == OP65_AND ||
416 L[0]->OPC == OP65_ASL ||
417 L[0]->OPC == OP65_DEA ||
418 L[0]->OPC == OP65_EOR ||
419 L[0]->OPC == OP65_INA ||
420 L[0]->OPC == OP65_LDA ||
421 L[0]->OPC == OP65_LSR ||
422 L[0]->OPC == OP65_ORA ||
423 L[0]->OPC == OP65_PLA ||
424 L[0]->OPC == OP65_SBC ||
425 L[0]->OPC == OP65_TXA ||
426 L[0]->OPC == OP65_TYA) &&
427 !CS_RangeHasLabel (S, I+1, 2) &&
428 CS_GetEntries (S, L+1, I+1, 2) &&
429 L[1]->OPC == OP65_CMP &&
430 CE_IsKnownImm (L[1], 0)) {
434 /* Check for the call to boolxx. We only remove the compare if
435 * the carry flag is not evaluated later, because the load will
436 * not set the carry flag.
438 if (L[2]->OPC == OP65_JSR) {
439 switch (FindBoolCmpCond (L[2]->Arg)) {
447 /* Remove the compare */
460 } else if ((L[2]->Info & OF_FBRA) != 0) {
461 /* The following insn branches on the condition of the load,
462 * so the compare instruction might be removed. For safety,
463 * do some more checks if the carry isn't used later, since
464 * the compare does set the carry, but the load does not.
468 if ((E = CS_GetNextEntry (S, I+2)) != 0 &&
470 (N = L[2]->JumpTo->Owner) != 0 &&
471 N->OPC != OP65_BCC &&
472 N->OPC != OP65_BCS &&
473 N->OPC != OP65_JCC &&
474 N->OPC != OP65_JCS &&
475 (N->OPC != OP65_JSR ||
476 FindBoolCmpCond (N->Arg) == CMP_INV)) {
478 /* The following insn branches on the condition of a load,
479 * and there's no use of the carry flag in sight, so the
480 * compare instruction can be removed.
486 /* Delete the compare if we can */
488 CS_DelEntry (S, I+1);
498 /* Return the number of changes made */
504 unsigned OptCmp4 (CodeSeg* S)
514 * If a is zero, we may remove the compare. If a and b are both zero, we may
515 * replace it by the sequence
521 * L1 may be either the label at the branch instruction, or the target label
522 * of this instruction.
525 unsigned Changes = 0;
527 /* Walk over the entries */
529 while (I < CS_GetEntryCount (S)) {
534 CodeEntry* E = CS_GetEntry (S, I);
536 /* Check for the sequence */
537 if (E->OPC == OP65_LDA &&
538 CS_GetEntries (S, L, I+1, 5) &&
539 L[0]->OPC == OP65_LDX &&
540 !CE_HasLabel (L[0]) &&
542 !RegAXUsed (S, I+6)) {
544 if ((L[4]->Info & OF_FBRA) != 0 && L[1]->Num == 0 && L[3]->Num == 0) {
545 /* The value is zero, we may use the simple code version. */
546 CE_ReplaceOPC (L[0], OP65_ORA);
547 CS_DelEntries (S, I+2, 3);
549 /* Move the lda instruction after the first branch. This will
550 * improve speed, since the load is delayed after the first
553 CS_MoveEntry (S, I, I+4);
555 /* We will replace the ldx/cpx by lda/cmp */
556 CE_ReplaceOPC (L[0], OP65_LDA);
557 CE_ReplaceOPC (L[1], OP65_CMP);
559 /* Beware: If the first LDA instruction had a label, we have
560 * to move this label to the top of the sequence again.
562 if (CE_HasLabel (E)) {
563 CS_MoveLabels (S, E, L[0]);
576 /* Return the number of changes made */
582 unsigned OptCmp5 (CodeSeg* S)
583 /* Optimize compares of local variables:
593 unsigned Changes = 0;
595 /* Walk over the entries */
597 while (I < CS_GetEntryCount (S)) {
601 /* Get the next entry */
602 L[0] = CS_GetEntry (S, I);
604 /* Check for the sequence */
605 if (L[0]->OPC == OP65_LDY &&
606 CE_IsConstImm (L[0]) &&
607 CS_GetEntries (S, L+1, I+1, 5) &&
608 !CE_HasLabel (L[1]) &&
609 CE_IsCallTo (L[1], "ldaxysp") &&
612 if ((L[5]->Info & OF_FBRA) != 0 && L[2]->Num == 0 && L[4]->Num == 0) {
617 /* The value is zero, we may use the simple code version:
624 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
625 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
626 CS_InsertEntry (S, X, I+1);
628 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
629 CS_InsertEntry (S, X, I+2);
631 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
632 CS_InsertEntry (S, X, I+3);
634 X = NewCodeEntry (OP65_ORA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
635 CS_InsertEntry (S, X, I+4);
637 CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */
638 CS_DelEntry (S, I); /* ldy */
645 /* Change the code to just use the A register. Move the load
646 * of the low byte after the first branch if possible:
657 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
658 CS_InsertEntry (S, X, I+3);
660 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
661 CS_InsertEntry (S, X, I+4);
663 X = NewCodeEntry (OP65_CMP, L[2]->AM, L[2]->Arg, 0, L[2]->LI);
664 CS_InsertEntry (S, X, I+5);
666 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
667 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
668 CS_InsertEntry (S, X, I+7);
670 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
671 CS_InsertEntry (S, X, I+8);
673 CS_DelEntries (S, I, 3); /* ldy/jsr/cpx */
685 /* Return the number of changes made */
691 unsigned OptCmp6 (CodeSeg* S)
692 /* Search for calls to compare subroutines followed by a conditional branch
693 * and replace them by cheaper versions, since the branch means that the
694 * boolean value returned by these routines is not needed (we may also check
695 * that explicitly, but for the current code generator it is always true).
698 unsigned Changes = 0;
700 /* Walk over the entries */
702 while (I < CS_GetEntryCount (S)) {
708 CodeEntry* E = CS_GetEntry (S, I);
710 /* Check for the sequence */
711 if (E->OPC == OP65_JSR &&
712 (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
713 (N = CS_GetNextEntry (S, I)) != 0 &&
714 (N->Info & OF_ZBRA) != 0 &&
717 /* The tos... functions will return a boolean value in a/x and
718 * the Z flag says if this value is zero or not. We will call
719 * a cheaper subroutine instead, one that does not return a
720 * boolean value but only valid flags. Note: jeq jumps if
721 * the condition is not met, jne jumps if the condition is met.
722 * Invert the code if we jump on condition not met.
724 if (GetBranchCond (N->OPC) == BC_EQ) {
725 /* Jumps if condition false, invert condition */
726 Cond = CmpInvertTab [Cond];
729 /* Replace the subroutine call. */
730 E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
731 CS_InsertEntry (S, E, I+1);
734 /* Replace the conditional branch */
735 ReplaceCmp (S, I+1, Cond);
737 /* Remember, we had changes */
747 /* Return the number of changes made */
753 unsigned OptCmp7 (CodeSeg* S)
754 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
758 unsigned Changes = 0;
760 /* Walk over the entries */
762 while (I < CS_GetEntryCount (S)) {
767 CodeEntry* E = CS_GetEntry (S, I);
769 /* Check for the sequence */
770 if ((E->OPC == OP65_LDX) &&
771 CS_GetEntries (S, L, I+1, 2) &&
772 L[0]->OPC == OP65_TXA &&
773 !CE_HasLabel (L[0]) &&
774 (L[1]->Info & OF_FBRA) != 0 &&
775 !CE_HasLabel (L[1]) &&
776 !RegAUsed (S, I+3)) {
779 CS_DelEntry (S, I+1);
781 /* Remember, we had changes */
791 /* Return the number of changes made */
797 unsigned OptCmp8 (CodeSeg* S)
798 /* Check for register compares where the contents of the register and therefore
799 * the result of the compare is known.
802 unsigned Changes = 0;
805 /* Walk over the entries */
807 while (I < CS_GetEntryCount (S)) {
812 CodeEntry* E = CS_GetEntry (S, I);
814 /* Check for a compare against an immediate value */
815 if ((E->Info & OF_CMP) != 0 &&
816 (RegVal = GetCmpRegVal (E)) >= 0 &&
819 /* We are able to evaluate the compare at compile time. Check if
820 * one or more branches are ahead.
822 unsigned JumpsChanged = 0;
824 while ((N = CS_GetNextEntry (S, I)) != 0 && /* Followed by something.. */
825 (N->Info & OF_CBRA) != 0 && /* ..that is a cond branch.. */
826 !CE_HasLabel (N)) { /* ..and has no label */
828 /* Evaluate the branch condition */
830 switch (GetBranchCond (N->OPC)) {
832 Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num);
836 Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num);
840 Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num);
844 Cond = ((signed char)RegVal) < ((signed char)E->Num);
848 Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num);
852 Cond = ((signed char)RegVal) >= ((signed char)E->Num);
857 /* Not set by the compare operation, bail out (Note:
858 * Just skipping anything here is rather stupid, but
859 * the sequence is never generated by the compiler,
860 * so it's quite safe to skip).
865 Internal ("Unknown branch condition");
869 /* If the condition is false, we may remove the jump. Otherwise
870 * the branch will always be taken, so we may replace it by a
871 * jump (and bail out).
874 CS_DelEntry (S, I+1);
876 CodeLabel* L = N->JumpTo;
877 const char* LabelName = L? L->Name : N->Arg;
878 CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, LabelName, L, N->LI);
879 CS_InsertEntry (S, X, I+2);
880 CS_DelEntry (S, I+1);
883 /* Remember, we had changes */
888 /* If we have made changes above, we may also remove the compare */
901 /* Return the number of changes made */
907 unsigned OptCmp9 (CodeSeg* S)
908 /* Search for the sequence
916 * If A is not used later (which should be the case), we can branch on the N
917 * flag instead of the carry flag and remove the asl.
920 unsigned Changes = 0;
923 /* Walk over the entries */
925 while (I < CS_GetEntryCount (S)) {
930 L[0] = CS_GetEntry (S, I);
932 /* Check for the sequence */
933 if (L[0]->OPC == OP65_SBC &&
934 CS_GetEntries (S, L+1, I+1, 4) &&
935 (L[1]->OPC == OP65_BVC ||
936 L[1]->OPC == OP65_BVS) &&
938 L[1]->JumpTo->Owner == L[3] &&
939 L[2]->OPC == OP65_EOR &&
940 CE_IsKnownImm (L[2], 0x80) &&
941 L[3]->OPC == OP65_ASL &&
942 L[3]->AM == AM65_ACC &&
943 (L[4]->OPC == OP65_BCC ||
944 L[4]->OPC == OP65_BCS ||
945 L[4]->OPC == OP65_JCC ||
946 L[4]->OPC == OP65_JCS) &&
947 !CE_HasLabel (L[4]) &&
948 !RegAUsed (S, I+4)) {
950 /* Replace the branch condition */
951 switch (GetBranchCond (L[4]->OPC)) {
952 case BC_CC: CE_ReplaceOPC (L[4], OP65_JPL); break;
953 case BC_CS: CE_ReplaceOPC (L[4], OP65_JMI); break;
954 default: Internal ("Unknown branch condition in OptCmp9");
957 /* Delete the asl insn */
958 CS_DelEntry (S, I+3);
960 /* Next sequence is somewhat ahead (if any) */
963 /* Remember, we had changes */
971 /* Return the number of changes made */