1 /*****************************************************************************/
5 /* Optimize compares */
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 /*****************************************************************************/
46 /*****************************************************************************/
48 /*****************************************************************************/
52 /* Defines for the conditions in a compare */
67 /* Table with the compare suffixes */
68 static const char CmpSuffixTab [][4] = {
69 "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
72 /* Table used to invert a condition, indexed by condition */
73 static const unsigned char CmpInvertTab [] = {
75 CMP_LE, CMP_LT, CMP_GE, CMP_GT,
76 CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
79 /* Table to show which compares are signed (use the N flag) */
80 static const char CmpSignedTab [] = {
81 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
86 /*****************************************************************************/
87 /* Helper functions */
88 /*****************************************************************************/
92 static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
93 /* Search for a compare condition by the given code using the given length */
98 for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
99 if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
111 static cmp_t FindBoolCmpCond (const char* Name)
112 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
114 /* Check for the correct subroutine name */
115 if (strncmp (Name, "bool", 4) == 0) {
116 /* Name is ok, search for the code in the table */
117 return FindCmpCond (Name+4, strlen(Name)-4);
126 static cmp_t FindTosCmpCond (const char* Name)
127 /* Check if this is a call to one of the TOS compare functions (tosgtax).
128 * Return the condition code or CMP_INV on failure.
131 unsigned Len = strlen (Name);
133 /* Check for the correct subroutine name */
134 if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
135 /* Name is ok, search for the code in the table */
136 return FindCmpCond (Name+3, Len-3-2);
145 static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
146 /* Helper function for the replacement of routines that return a boolean
147 * followed by a conditional jump. Instead of the boolean value, the condition
148 * codes are evaluated directly.
149 * I is the index of the conditional branch, the sequence is already checked
157 CodeEntry* E = CS_GetEntry (S, I);
159 /* Replace the conditional branch */
163 CE_ReplaceOPC (E, OP65_JEQ);
167 CE_ReplaceOPC (E, OP65_JNE);
176 if ((N = CS_GetNextEntry (S, I)) == 0) {
178 Internal ("Invalid program flow");
180 L = CS_GenLabel (S, N);
181 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
182 CS_InsertEntry (S, N, I);
183 CE_ReplaceOPC (E, OP65_JPL);
187 CE_ReplaceOPC (E, OP65_JPL);
191 CE_ReplaceOPC (E, OP65_JMI);
199 CE_ReplaceOPC (E, OP65_JMI);
201 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
202 CS_InsertEntry (S, N, I+1);
211 if ((N = CS_GetNextEntry (S, I)) == 0) {
213 Internal ("Invalid program flow");
215 L = CS_GenLabel (S, N);
216 N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI);
217 CS_InsertEntry (S, N, I);
218 CE_ReplaceOPC (E, OP65_JCS);
222 CE_ReplaceOPC (E, OP65_JCS);
226 CE_ReplaceOPC (E, OP65_JCC);
234 CE_ReplaceOPC (E, OP65_JCC);
236 N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI);
237 CS_InsertEntry (S, N, I+1);
241 Internal ("Unknown jump condition: %d", Cond);
249 static int IsImmCmp16 (CodeEntry** L)
250 /* Check if the instructions at L are an immidiate compare of a/x:
255 return (L[0]->OPC == OP65_CPX &&
256 L[0]->AM == AM65_IMM &&
257 (L[0]->Flags & CEF_NUMARG) != 0 &&
258 !CE_HasLabel (L[0]) &&
259 (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) &&
261 !CE_HasLabel (L[1]) &&
262 L[2]->OPC == OP65_CMP &&
263 L[2]->AM == AM65_IMM &&
264 (L[2]->Flags & CEF_NUMARG) != 0 &&
265 (L[3]->Info & OF_CBRA) != 0 &&
267 (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
272 static int GetCmpRegVal (const CodeEntry* E)
273 /* Return the register value for an immediate compare */
276 case OP65_CMP: return E->RI->In.RegA;
277 case OP65_CPX: return E->RI->In.RegX;
278 case OP65_CPY: return E->RI->In.RegY;
279 default: Internal ("Invalid opcode in GetCmpRegVal");
280 return 0; /* Not reached */
286 /*****************************************************************************/
287 /* Remove calls to the bool transformer subroutines */
288 /*****************************************************************************/
292 unsigned OptBoolTrans (CodeSeg* S)
293 /* Try to remove the call to boolean transformer routines where the call is
297 unsigned Changes = 0;
299 /* Walk over the entries */
301 while (I < CS_GetEntryCount (S)) {
307 CodeEntry* E = CS_GetEntry (S, I);
309 /* Check for a boolean transformer */
310 if (E->OPC == OP65_JSR &&
311 (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
312 (N = CS_GetNextEntry (S, I)) != 0 &&
313 (N->Info & OF_ZBRA) != 0) {
315 /* Make the boolean transformer unnecessary by changing the
316 * the conditional jump to evaluate the condition flags that
317 * are set after the compare directly. Note: jeq jumps if
318 * the condition is not met, jne jumps if the condition is met.
319 * Invert the code if we jump on condition not met.
321 if (GetBranchCond (N->OPC) == BC_EQ) {
322 /* Jumps if condition false, invert condition */
323 Cond = CmpInvertTab [Cond];
326 /* Check if we can replace the code by something better */
327 ReplaceCmp (S, I+1, Cond);
329 /* Remove the call to the bool transformer */
332 /* Remember, we had changes */
342 /* Return the number of changes made */
348 /*****************************************************************************/
349 /* Optimizations for compares */
350 /*****************************************************************************/
354 unsigned OptCmp1 (CodeSeg* S)
355 /* Search for the sequence
367 unsigned Changes = 0;
369 /* Walk over the entries */
371 while (I < CS_GetEntryCount (S)) {
376 CodeEntry* E = CS_GetEntry (S, I);
378 /* Check for the sequence */
379 if (E->OPC == OP65_STX &&
380 !CS_RangeHasLabel (S, I+1, 2) &&
381 CS_GetEntries (S, L, I+1, 2) &&
382 L[0]->OPC == OP65_STX &&
383 strcmp (L[0]->Arg, "tmp1") == 0 &&
384 L[1]->OPC == OP65_ORA &&
385 strcmp (L[1]->Arg, "tmp1") == 0) {
387 /* Remove the remaining instructions */
388 CS_DelEntries (S, I+1, 2);
390 /* Insert the ora instead */
391 CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1);
393 /* Remember, we had changes */
403 /* Return the number of changes made */
409 unsigned OptCmp2 (CodeSeg* S)
412 * lda/and/ora/eor ...
416 * lda/and/ora/eor ...
420 * and remove the cmp.
423 unsigned Changes = 0;
425 /* Walk over the entries */
427 while (I < CS_GetEntryCount (S)) {
432 L[0] = CS_GetEntry (S, I);
434 /* Check for the sequence */
435 if ((L[0]->OPC == OP65_ADC ||
436 L[0]->OPC == OP65_AND ||
437 L[0]->OPC == OP65_DEA ||
438 L[0]->OPC == OP65_EOR ||
439 L[0]->OPC == OP65_INA ||
440 L[0]->OPC == OP65_LDA ||
441 L[0]->OPC == OP65_ORA ||
442 L[0]->OPC == OP65_PLA ||
443 L[0]->OPC == OP65_SBC ||
444 L[0]->OPC == OP65_TXA ||
445 L[0]->OPC == OP65_TYA) &&
446 !CS_RangeHasLabel (S, I+1, 2) &&
447 CS_GetEntries (S, L+1, I+1, 2) &&
448 L[1]->OPC == OP65_CMP &&
449 CE_KnownImm (L[1]) &&
452 /* Check for the call to boolxx. We cannot remove the compare if
453 * the carry flag is evaluated later, because the load will not
454 * set the carry flag.
456 if (L[2]->OPC == OP65_JSR) {
457 switch (FindBoolCmpCond (L[2]->Arg)) {
465 /* Remove the compare */
466 CS_DelEntry (S, I+1);
481 /* Check for a branch on conditions that are set by the load.
482 * Beware: The insn may branch to another conditional branch
483 * that evaluates other flags, so check that.
488 if ((E->Info & (OF_CBRA|OF_UBRA)) != 0) {
489 /* A conditional branch. Check if it jumps on a
490 * condition not set by the load.
492 if ((E->Info & (OF_FBRA|OF_UBRA)) == 0) {
495 } else if (E->JumpTo == 0) {
496 /* Jump to external */
500 /* Check target of branch */
501 E = E->JumpTo->Owner;
504 /* Some other insn */
510 /* Delete the compare if we can */
512 CS_DelEntry (S, I+1);
523 /* Return the number of changes made */
529 unsigned OptCmp3 (CodeSeg* S)
539 * If a is zero, we may remove the compare. If a and b are both zero, we may
540 * replace it by the sequence
546 * L1 may be either the label at the branch instruction, or the target label
547 * of this instruction.
550 unsigned Changes = 0;
552 /* Walk over the entries */
554 while (I < CS_GetEntryCount (S)) {
559 CodeEntry* E = CS_GetEntry (S, I);
561 /* Check for the sequence */
562 if (E->OPC == OP65_LDA &&
563 CS_GetEntries (S, L, I+1, 5) &&
564 L[0]->OPC == OP65_LDX &&
565 !CE_HasLabel (L[0]) &&
567 !RegAXUsed (S, I+6)) {
569 if ((L[4]->Info & OF_FBRA) != 0 && L[1]->Num == 0 && L[3]->Num == 0) {
570 /* The value is zero, we may use the simple code version. */
571 CE_ReplaceOPC (L[0], OP65_ORA);
572 CS_DelEntries (S, I+2, 3);
574 /* Move the lda instruction after the first branch. This will
575 * improve speed, since the load is delayed after the first
578 CS_MoveEntry (S, I, I+4);
580 /* We will replace the ldx/cpx by lda/cmp */
581 CE_ReplaceOPC (L[0], OP65_LDA);
582 CE_ReplaceOPC (L[1], OP65_CMP);
584 /* Beware: If the first LDA instruction had a label, we have
585 * to move this label to the top of the sequence again.
587 if (CE_HasLabel (E)) {
588 CS_MoveLabels (S, E, L[0]);
601 /* Return the number of changes made */
607 unsigned OptCmp4 (CodeSeg* S)
608 /* Optimize compares of local variables:
618 unsigned Changes = 0;
620 /* Walk over the entries */
622 while (I < CS_GetEntryCount (S)) {
626 /* Get the next entry */
627 L[0] = CS_GetEntry (S, I);
629 /* Check for the sequence */
630 if (L[0]->OPC == OP65_LDY &&
631 CE_KnownImm (L[0]) &&
632 CS_GetEntries (S, L+1, I+1, 5) &&
633 !CE_HasLabel (L[1]) &&
634 CE_IsCall (L[1], "ldaxysp") &&
637 if ((L[5]->Info & OF_FBRA) != 0 && L[2]->Num == 0 && L[4]->Num == 0) {
642 /* The value is zero, we may use the simple code version:
649 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
650 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
651 CS_InsertEntry (S, X, I+1);
653 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
654 CS_InsertEntry (S, X, I+2);
656 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
657 CS_InsertEntry (S, X, I+3);
659 X = NewCodeEntry (OP65_ORA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
660 CS_InsertEntry (S, X, I+4);
662 CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */
663 CS_DelEntry (S, I); /* ldy */
670 /* Change the code to just use the A register. Move the load
671 * of the low byte after the first branch if possible:
682 sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
683 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
684 CS_InsertEntry (S, X, I+3);
686 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
687 CS_InsertEntry (S, X, I+4);
689 X = NewCodeEntry (OP65_CMP, L[2]->AM, L[2]->Arg, 0, L[2]->LI);
690 CS_InsertEntry (S, X, I+5);
692 X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
693 CS_InsertEntry (S, X, I+7);
695 X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
696 CS_InsertEntry (S, X, I+8);
698 CS_DelEntries (S, I, 3); /* ldy/jsr/cpx */
710 /* Return the number of changes made */
716 unsigned OptCmp5 (CodeSeg* S)
717 /* Search for calls to compare subroutines followed by a conditional branch
718 * and replace them by cheaper versions, since the branch means that the
719 * boolean value returned by these routines is not needed (we may also check
720 * that explicitly, but for the current code generator it is always true).
723 unsigned Changes = 0;
725 /* Walk over the entries */
727 while (I < CS_GetEntryCount (S)) {
733 CodeEntry* E = CS_GetEntry (S, I);
735 /* Check for the sequence */
736 if (E->OPC == OP65_JSR &&
737 (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
738 (N = CS_GetNextEntry (S, I)) != 0 &&
739 (N->Info & OF_ZBRA) != 0 &&
742 /* The tos... functions will return a boolean value in a/x and
743 * the Z flag says if this value is zero or not. We will call
744 * a cheaper subroutine instead, one that does not return a
745 * boolean value but only valid flags. Note: jeq jumps if
746 * the condition is not met, jne jumps if the condition is met.
747 * Invert the code if we jump on condition not met.
749 if (GetBranchCond (N->OPC) == BC_EQ) {
750 /* Jumps if condition false, invert condition */
751 Cond = CmpInvertTab [Cond];
754 /* Replace the subroutine call. */
755 E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp", 0, E->LI);
756 CS_InsertEntry (S, E, I+1);
759 /* Replace the conditional branch */
760 ReplaceCmp (S, I+1, Cond);
762 /* Remember, we had changes */
772 /* Return the number of changes made */
778 unsigned OptCmp6 (CodeSeg* S)
779 /* Search for a sequence ldx/txa/branch and remove the txa if A is not
783 unsigned Changes = 0;
785 /* Walk over the entries */
787 while (I < CS_GetEntryCount (S)) {
792 CodeEntry* E = CS_GetEntry (S, I);
794 /* Check for the sequence */
795 if ((E->OPC == OP65_LDX) &&
796 CS_GetEntries (S, L, I+1, 2) &&
797 L[0]->OPC == OP65_TXA &&
798 !CE_HasLabel (L[0]) &&
799 (L[1]->Info & OF_FBRA) != 0 &&
800 !CE_HasLabel (L[1]) &&
801 !RegAUsed (S, I+3)) {
804 CS_DelEntry (S, I+1);
806 /* Remember, we had changes */
816 /* Return the number of changes made */
822 unsigned OptCmp7 (CodeSeg* S)
823 /* Check for register compares where the contents of the register and therefore
824 * the result of the compare is known.
827 unsigned Changes = 0;
830 /* Generate register info for this step */
833 /* Walk over the entries */
835 while (I < CS_GetEntryCount (S)) {
840 CodeEntry* E = CS_GetEntry (S, I);
842 /* Check for a compare against an immediate value */
843 if ((E->Info & OF_CMP) != 0 &&
844 (RegVal = GetCmpRegVal (E)) >= 0 &&
847 /* We are able to evaluate the compare at compile time. Check if
848 * one or more branches are ahead.
850 unsigned JumpsChanged = 0;
852 while ((N = CS_GetNextEntry (S, I)) != 0 && /* Followed by something.. */
853 (N->Info & OF_CBRA) != 0 && /* ..that is a cond branch.. */
854 !CE_HasLabel (N)) { /* ..and has no label */
856 /* Evaluate the branch condition */
858 switch (GetBranchCond (N->OPC)) {
860 Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num);
864 Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num);
868 Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num);
872 Cond = ((signed char)RegVal) < ((signed char)E->Num);
876 Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num);
880 Cond = ((signed char)RegVal) >= ((signed char)E->Num);
885 /* Not set by the compare operation, bail out (Note:
886 * Just skipping anything here is rather stupid, but
887 * the sequence is never generated by the compiler,
888 * so it's quite safe to skip).
893 Internal ("Unknown branch condition");
897 /* If the condition is false, we may remove the jump. Otherwise
898 * the branch will always be taken, so we may replace it by a
899 * jump (and bail out).
902 CS_DelEntry (S, I+1);
904 CodeLabel* L = N->JumpTo;
905 const char* LabelName = L? L->Name : N->Arg;
906 CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, LabelName, L, N->LI);
907 CS_InsertEntry (S, X, I+2);
908 CS_DelEntry (S, I+1);
911 /* Remember, we had changes */
916 /* If we have made changes above, we may also remove the compare */
929 /* Free register info */
932 /* Return the number of changes made */