1 /*****************************************************************************/
5 /* Optimize compares */
9 /* (C) 2001-2009, 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
59 /* Table to show which compares are signed (use the N flag) */
60 static const char CmpSignedTab [] = {
61 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
66 /*****************************************************************************/
67 /* Helper functions */
68 /*****************************************************************************/
72 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
73 /* Helper function for the replacement of routines that return a boolean
74 * followed by a conditional jump. Instead of the boolean value, the condition
75 * codes are evaluated directly.
76 * I is the index of the conditional branch, the sequence is already checked
84 CodeEntry* E = CS_GetEntry (S, I);
86 /* Replace the conditional branch */
90 CE_ReplaceOPC (E, OP65_JEQ);
94 CE_ReplaceOPC (E, OP65_JNE);
103 if ((N = CS_GetNextEntry (S, I)) == 0) {
105 Internal ("Invalid program flow");
107 L = CS_GenLabel (S, N);
108 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
109 CS_InsertEntry (S, N, I);
110 CE_ReplaceOPC (E, OP65_JPL);
114 CE_ReplaceOPC (E, OP65_JPL);
118 CE_ReplaceOPC (E, OP65_JMI);
126 CE_ReplaceOPC (E, OP65_JMI);
128 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
129 CS_InsertEntry (S, N, I+1);
138 if ((N = CS_GetNextEntry (S, I)) == 0) {
140 Internal ("Invalid program flow");
142 L = CS_GenLabel (S, N);
143 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
144 CS_InsertEntry (S, N, I);
145 CE_ReplaceOPC (E, OP65_JCS);
149 CE_ReplaceOPC (E, OP65_JCS);
153 CE_ReplaceOPC (E, OP65_JCC);
161 CE_ReplaceOPC (E, OP65_JCC);
163 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
164 CS_InsertEntry (S, N, I+1);
168 Internal ("Unknown jump condition: %d", Cond);
176 static int IsImmCmp16 (CodeEntry** L)
177 /* Check if the instructions at L are an immidiate compare of a/x:
182 return (L[0]->OPC == OP65_CPX &&
183 L[0]->AM == AM65_IMM &&
184 (L[0]->Flags & CEF_NUMARG) != 0 &&
185 !CE_HasLabel (L[0]) &&
186 (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) &&
188 !CE_HasLabel (L[1]) &&
189 L[2]->OPC == OP65_CMP &&
190 L[2]->AM == AM65_IMM &&
191 (L[2]->Flags & CEF_NUMARG) != 0 &&
192 (L[3]->Info & OF_CBRA) != 0 &&
194 (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
199 static int GetCmpRegVal (const CodeEntry* E)
200 /* Return the register value for an immediate compare */
203 case OP65_CMP: return E->RI->In.RegA;
204 case OP65_CPX: return E->RI->In.RegX;
205 case OP65_CPY: return E->RI->In.RegY;
206 default: Internal ("Invalid opcode in GetCmpRegVal");
207 return 0; /* Not reached */
213 /*****************************************************************************/
214 /* Remove calls to the bool transformer subroutines */
215 /*****************************************************************************/
219 unsigned OptBoolTrans (CodeSeg* S)
220 /* Try to remove the call to boolean transformer routines where the call is
224 unsigned Changes = 0;
226 /* Walk over the entries */
228 while (I < CS_GetEntryCount (S)) {
234 CodeEntry* E = CS_GetEntry (S, I);
236 /* Check for a boolean transformer */
237 if (E->OPC == OP65_JSR &&
238 (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
239 (N = CS_GetNextEntry (S, I)) != 0 &&
240 (N->Info & OF_ZBRA) != 0) {
242 /* Make the boolean transformer unnecessary by changing the
243 * the conditional jump to evaluate the condition flags that
244 * are set after the compare directly. Note: jeq jumps if
245 * the condition is not met, jne jumps if the condition is met.
246 * Invert the code if we jump on condition not met.
248 if (GetBranchCond (N->OPC) == BC_EQ) {
249 /* Jumps if condition false, invert condition */
250 Cond = CmpInvertTab [Cond];
253 /* Check if we can replace the code by something better */
254 ReplaceCmp (S, I+1, Cond);
256 /* Remove the call to the bool transformer */
259 /* Remember, we had changes */
269 /* Return the number of changes made */
275 /*****************************************************************************/
276 /* Optimizations for compares */
277 /*****************************************************************************/
281 unsigned OptCmp1 (CodeSeg* S)
282 /* Search for the sequence
293 unsigned Changes = 0;
295 /* Walk over the entries */
297 while (I < CS_GetEntryCount (S)) {
302 L[0] = CS_GetEntry (S, I);
304 /* Check for the sequence */
305 if (L[0]->OPC == OP65_LDX &&
306 !CS_RangeHasLabel (S, I+1, 2) &&
307 CS_GetEntries (S, L+1, I+1, 2) &&
308 L[1]->OPC == OP65_STX &&
309 strcmp (L[1]->Arg, "tmp1") == 0 &&
310 L[2]->OPC == OP65_ORA &&
311 strcmp (L[2]->Arg, "tmp1") == 0) {
315 /* Insert the ora instead */
316 X = NewCodeEntry (OP65_ORA, L[0]->AM, L[0]->Arg, 0, L[0]->LI);
317 CS_InsertEntry (S, X, I);
319 /* Remove all other instructions */
320 CS_DelEntries (S, I+1, 3);
322 /* Remember, we had changes */
332 /* Return the number of changes made */
338 unsigned OptCmp2 (CodeSeg* S)
339 /* Search for the sequence
351 unsigned Changes = 0;
353 /* Walk over the entries */
355 while (I < CS_GetEntryCount (S)) {
360 CodeEntry* E = CS_GetEntry (S, I);
362 /* Check for the sequence */
363 if (E->OPC == OP65_STX &&
364 !CS_RangeHasLabel (S, I+1, 2) &&
365 CS_GetEntries (S, L, I+1, 2) &&
366 L[0]->OPC == OP65_STX &&
367 strcmp (L[0]->Arg, "tmp1") == 0 &&
368 L[1]->OPC == OP65_ORA &&
369 strcmp (L[1]->Arg, "tmp1") == 0) {
371 /* Remove the remaining instructions */
372 CS_DelEntries (S, I+1, 2);
374 /* Insert the ora instead */
375 CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
377 /* Remember, we had changes */
387 /* Return the number of changes made */
393 unsigned OptCmp3 (CodeSeg* S)
396 * lda/and/ora/eor ...
400 * lda/and/ora/eor ...
404 * and remove the cmp.
407 unsigned Changes = 0;
409 /* Walk over the entries */
411 while (I < CS_GetEntryCount (S)) {
416 L[0] = CS_GetEntry (S, I);
418 /* Check for the sequence */
419 if ((L[0]->OPC == OP65_ADC ||
420 L[0]->OPC == OP65_AND ||
421 L[0]->OPC == OP65_ASL ||
422 L[0]->OPC == OP65_DEA ||
423 L[0]->OPC == OP65_EOR ||
424 L[0]->OPC == OP65_INA ||
425 L[0]->OPC == OP65_LDA ||
426 L[0]->OPC == OP65_LSR ||
427 L[0]->OPC == OP65_ORA ||
428 L[0]->OPC == OP65_PLA ||
429 L[0]->OPC == OP65_SBC ||
430 L[0]->OPC == OP65_TXA ||
431 L[0]->OPC == OP65_TYA) &&
432 !CS_RangeHasLabel (S, I+1, 2) &&
433 CS_GetEntries (S, L+1, I+1, 2) &&
434 L[1]->OPC == OP65_CMP &&
435 CE_IsKnownImm (L[1], 0)) {
439 /* Check for the call to boolxx. We only remove the compare if
440 * the carry flag is evaluated later, because the load will not
441 * set the carry flag.
443 if (L[2]->OPC == OP65_JSR) {
444 switch (FindBoolCmpCond (L[2]->Arg)) {
452 /* Remove the compare */
465 } else if ((L[2]->Info & OF_FBRA) != 0) {
467 /* The following insn branches on the condition of a load, so
468 * the compare instruction can be removed.
474 /* Delete the compare if we can */
476 CS_DelEntry (S, I+1);
486 /* Return the number of changes made */
492 unsigned OptCmp4 (CodeSeg* S)
502 * If a is zero, we may remove the compare. If a and b are both zero, we may
503 * replace it by the sequence
509 * L1 may be either the label at the branch instruction, or the target label
510 * of this instruction.
513 unsigned Changes = 0;
515 /* Walk over the entries */
517 while (I < CS_GetEntryCount (S)) {
522 CodeEntry* E = CS_GetEntry (S, I);
524 /* Check for the sequence */
525 if (E->OPC == OP65_LDA &&
526 CS_GetEntries (S, L, I+1, 5) &&
527 L[0]->OPC == OP65_LDX &&
528 !CE_HasLabel (L[0]) &&
530 !RegAXUsed (S, I+6)) {
532 if ((L[4]->Info & OF_FBRA) != 0 && L[1]->Num == 0 && L[3]->Num == 0) {
533 /* The value is zero, we may use the simple code version. */
534 CE_ReplaceOPC (L[0], OP65_ORA);
535 CS_DelEntries (S, I+2, 3);
537 /* Move the lda instruction after the first branch. This will
538 * improve speed, since the load is delayed after the first
541 CS_MoveEntry (S, I, I+4);
543 /* We will replace the ldx/cpx by lda/cmp */
544 CE_ReplaceOPC (L[0], OP65_LDA);
545 CE_ReplaceOPC (L[1], OP65_CMP);
547 /* Beware: If the first LDA instruction had a label, we have
548 * to move this label to the top of the sequence again.
550 if (CE_HasLabel (E)) {
551 CS_MoveLabels (S, E, L[0]);
564 /* Return the number of changes made */
570 unsigned OptCmp5 (CodeSeg* S)
571 /* Optimize compares of local variables:
581 unsigned Changes = 0;
583 /* Walk over the entries */
585 while (I < CS_GetEntryCount (S)) {
589 /* Get the next entry */
590 L[0] = CS_GetEntry (S, I);
592 /* Check for the sequence */
593 if (L[0]->OPC == OP65_LDY &&
594 CE_IsConstImm (L[0]) &&
595 CS_GetEntries (S, L+1, I+1, 5) &&
596 !CE_HasLabel (L[1]) &&
597 CE_IsCallTo (L[1], "ldaxysp") &&
600 if ((L[5]->Info & OF_FBRA) != 0 && L[2]->Num == 0 && L[4]->Num == 0) {
605 /* The value is zero, we may use the simple code version:
612 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
613 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
614 CS_InsertEntry (S, X, I+1);
616 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
617 CS_InsertEntry (S, X, I+2);
619 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
620 CS_InsertEntry (S, X, I+3);
622 X = NewCodeEntry (OP65_ORA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
623 CS_InsertEntry (S, X, I+4);
625 CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */
626 CS_DelEntry (S, I); /* ldy */
633 /* Change the code to just use the A register. Move the load
634 * of the low byte after the first branch if possible:
645 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
646 CS_InsertEntry (S, X, I+3);
648 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
649 CS_InsertEntry (S, X, I+4);
651 X = NewCodeEntry (OP65_CMP, L[2]->AM, L[2]->Arg, 0, L[2]->LI);
652 CS_InsertEntry (S, X, I+5);
654 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
655 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
656 CS_InsertEntry (S, X, I+7);
658 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
659 CS_InsertEntry (S, X, I+8);
661 CS_DelEntries (S, I, 3); /* ldy/jsr/cpx */
673 /* Return the number of changes made */
679 unsigned OptCmp6 (CodeSeg* S)
680 /* Search for calls to compare subroutines followed by a conditional branch
681 * and replace them by cheaper versions, since the branch means that the
682 * boolean value returned by these routines is not needed (we may also check
683 * that explicitly, but for the current code generator it is always true).
686 unsigned Changes = 0;
688 /* Walk over the entries */
690 while (I < CS_GetEntryCount (S)) {
696 CodeEntry* E = CS_GetEntry (S, I);
698 /* Check for the sequence */
699 if (E->OPC == OP65_JSR &&
700 (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
701 (N = CS_GetNextEntry (S, I)) != 0 &&
702 (N->Info & OF_ZBRA) != 0 &&
705 /* The tos... functions will return a boolean value in a/x and
706 * the Z flag says if this value is zero or not. We will call
707 * a cheaper subroutine instead, one that does not return a
708 * boolean value but only valid flags. Note: jeq jumps if
709 * the condition is not met, jne jumps if the condition is met.
710 * Invert the code if we jump on condition not met.
712 if (GetBranchCond (N->OPC) == BC_EQ) {
713 /* Jumps if condition false, invert condition */
714 Cond = CmpInvertTab [Cond];
717 /* Replace the subroutine call. */
718 E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
719 CS_InsertEntry (S, E, I+1);
722 /* Replace the conditional branch */
723 ReplaceCmp (S, I+1, Cond);
725 /* Remember, we had changes */
735 /* Return the number of changes made */
741 unsigned OptCmp7 (CodeSeg* S)
742 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
746 unsigned Changes = 0;
748 /* Walk over the entries */
750 while (I < CS_GetEntryCount (S)) {
755 CodeEntry* E = CS_GetEntry (S, I);
757 /* Check for the sequence */
758 if ((E->OPC == OP65_LDX) &&
759 CS_GetEntries (S, L, I+1, 2) &&
760 L[0]->OPC == OP65_TXA &&
761 !CE_HasLabel (L[0]) &&
762 (L[1]->Info & OF_FBRA) != 0 &&
763 !CE_HasLabel (L[1]) &&
764 !RegAUsed (S, I+3)) {
767 CS_DelEntry (S, I+1);
769 /* Remember, we had changes */
779 /* Return the number of changes made */
785 unsigned OptCmp8 (CodeSeg* S)
786 /* Check for register compares where the contents of the register and therefore
787 * the result of the compare is known.
790 unsigned Changes = 0;
793 /* Generate register info for this step */
796 /* Walk over the entries */
798 while (I < CS_GetEntryCount (S)) {
803 CodeEntry* E = CS_GetEntry (S, I);
805 /* Check for a compare against an immediate value */
806 if ((E->Info & OF_CMP) != 0 &&
807 (RegVal = GetCmpRegVal (E)) >= 0 &&
810 /* We are able to evaluate the compare at compile time. Check if
811 * one or more branches are ahead.
813 unsigned JumpsChanged = 0;
815 while ((N = CS_GetNextEntry (S, I)) != 0 && /* Followed by something.. */
816 (N->Info & OF_CBRA) != 0 && /* ..that is a cond branch.. */
817 !CE_HasLabel (N)) { /* ..and has no label */
819 /* Evaluate the branch condition */
821 switch (GetBranchCond (N->OPC)) {
823 Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num);
827 Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num);
831 Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num);
835 Cond = ((signed char)RegVal) < ((signed char)E->Num);
839 Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num);
843 Cond = ((signed char)RegVal) >= ((signed char)E->Num);
848 /* Not set by the compare operation, bail out (Note:
849 * Just skipping anything here is rather stupid, but
850 * the sequence is never generated by the compiler,
851 * so it's quite safe to skip).
856 Internal ("Unknown branch condition");
860 /* If the condition is false, we may remove the jump. Otherwise
861 * the branch will always be taken, so we may replace it by a
862 * jump (and bail out).
865 CS_DelEntry (S, I+1);
867 CodeLabel* L = N->JumpTo;
868 const char* LabelName = L? L->Name : N->Arg;
869 CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, LabelName, L, N->LI);
870 CS_InsertEntry (S, X, I+2);
871 CS_DelEntry (S, I+1);
874 /* Remember, we had changes */
879 /* If we have made changes above, we may also remove the compare */
892 /* Free register info */
895 /* Return the number of changes made */
901 unsigned OptCmp9 (CodeSeg* S)
902 /* Search for the sequence
910 * If A is not used later (which should be the case), we can branch on the N
911 * flag instead of the carry flag and remove the asl.
914 unsigned Changes = 0;
917 /* Walk over the entries */
919 while (I < CS_GetEntryCount (S)) {
924 L[0] = CS_GetEntry (S, I);
926 /* Check for the sequence */
927 if (L[0]->OPC == OP65_SBC &&
928 CS_GetEntries (S, L+1, I+1, 4) &&
929 (L[1]->OPC == OP65_BVC ||
930 L[1]->OPC == OP65_BVS) &&
932 L[1]->JumpTo->Owner == L[3] &&
933 L[2]->OPC == OP65_EOR &&
934 CE_IsKnownImm (L[2], 0x80) &&
935 L[3]->OPC == OP65_ASL &&
936 L[3]->AM == AM65_ACC &&
937 (L[4]->OPC == OP65_BCC ||
938 L[4]->OPC == OP65_BCS ||
939 L[4]->OPC == OP65_JCC ||
940 L[4]->OPC == OP65_JCS) &&
941 !CE_HasLabel (L[4]) &&
942 !RegAUsed (S, I+4)) {
944 /* Replace the branch condition */
945 switch (GetBranchCond (L[4]->OPC)) {
946 case BC_CC: CE_ReplaceOPC (L[4], OP65_JPL); break;
947 case BC_CS: CE_ReplaceOPC (L[4], OP65_JMI); break;
948 default: Internal ("Unknown branch condition in OptCmp9");
951 /* Delete the asl insn */
952 CS_DelEntry (S, I+3);
954 /* Next sequence is somewhat ahead (if any) */
957 /* Remember, we had changes */
965 /* Return the number of changes made */