/* */
/* */
/* */
-/* (C) 2001 Ullrich von Bassewitz */
-/* Wacholderweg 14 */
-/* D-70597 Stuttgart */
-/* EMail: uz@cc65.org */
+/* (C) 2001-2012, Ullrich von Bassewitz */
+/* Roemerstrasse 52 */
+/* D-70794 Filderstadt */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
-/* Defines for the conditions in a compare */
-typedef enum {
- CMP_INV = -1,
- CMP_EQ,
- CMP_NE,
- CMP_GT,
- CMP_GE,
- CMP_LT,
- CMP_LE,
- CMP_UGT,
- CMP_UGE,
- CMP_ULT,
- CMP_ULE
-} cmp_t;
-
-/* Table with the compare suffixes */
-static const char CmpSuffixTab [][4] = {
- "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
-};
-
/* Table used to invert a condition, indexed by condition */
static const unsigned char CmpInvertTab [] = {
CMP_NE, CMP_EQ,
CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
};
-/* Table to show which compares are signed (use the N flag) */
-static const char CmpSignedTab [] = {
- 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
-};
-
/*****************************************************************************/
-static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
-/* Search for a compare condition by the given code using the given length */
-{
- unsigned I;
-
- /* Linear search */
- for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
- if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
- /* Found */
- return I;
- }
- }
-
- /* Not found */
- return CMP_INV;
-}
-
-
-
-static cmp_t FindBoolCmpCond (const char* Name)
-/* Map a condition suffix to a code. Return the code or CMP_INV on failure */
-{
- /* Check for the correct subroutine name */
- if (strncmp (Name, "bool", 4) == 0) {
- /* Name is ok, search for the code in the table */
- return FindCmpCond (Name+4, strlen(Name)-4);
- } else {
- /* Not found */
- return CMP_INV;
- }
-}
-
-
-
-static cmp_t FindTosCmpCond (const char* Name)
-/* Check if this is a call to one of the TOS compare functions (tosgtax).
- * Return the condition code or CMP_INV on failure.
- */
-{
- unsigned Len = strlen (Name);
-
- /* Check for the correct subroutine name */
- if (strncmp (Name, "tos", 3) == 0 && strcmp (Name+Len-2, "ax") == 0) {
- /* Name is ok, search for the code in the table */
- return FindCmpCond (Name+3, Len-3-2);
- } else {
- /* Not found */
- return CMP_INV;
- }
-}
-
-
-
static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond)
/* Helper function for the replacement of routines that return a boolean
* followed by a conditional jump. Instead of the boolean value, the condition
-static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
+static int IsImmCmp16 (CodeEntry** L)
/* Check if the instructions at L are an immidiate compare of a/x:
*
*
L[2]->OPC == OP65_CMP &&
L[2]->AM == AM65_IMM &&
(L[2]->Flags & CEF_NUMARG) != 0 &&
- (L[3]->Info & OF_ZBRA) != 0 &&
+ (L[3]->Info & OF_CBRA) != 0 &&
L[3]->JumpTo != 0 &&
(L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
}
-static int IsCmpToZero (const CodeEntry* E)
-/* Check if the given instrcuction is a compare to zero instruction */
-{
- return (E->OPC == OP65_CMP &&
- E->AM == AM65_IMM &&
- (E->Flags & CEF_NUMARG) != 0 &&
- E->Num == 0);
-}
-
-
-
-static int IsSpLoad (const CodeEntry* E)
-/* Return true if this is the load of A from the stack */
-{
- return E->OPC == OP65_LDA && E->AM == AM65_ZP_INDY && strcmp (E->Arg, "sp") == 0;
-}
-
-
-
-static int IsLocalLoad16 (CodeSeg* S, unsigned Index,
- CodeEntry** L, unsigned Count)
-/* Check if a 16 bit load of a local variable follows:
- *
- * ldy #$xx
- * lda (sp),y
- * tax
- * dey
- * lda (sp),y
- *
- * If so, read Count entries following the first ldy into L and return true
- * if this is possible. Otherwise return false.
- */
-{
- /* Be sure we read enough entries for the check */
- CHECK (Count >= 5);
-
- /* Read the first entry */
- L[0] = CS_GetEntry (S, Index);
-
- /* Check for the sequence */
- return (L[0]->OPC == OP65_LDY &&
- L[0]->AM == AM65_IMM &&
- (L[0]->Flags & CEF_NUMARG) != 0 &&
- CS_GetEntries (S, L+1, Index+1, Count-1) &&
- IsSpLoad (L[1]) &&
- !CE_HasLabel (L[1]) &&
- L[2]->OPC == OP65_TAX &&
- !CE_HasLabel (L[2]) &&
- L[3]->OPC == OP65_DEY &&
- !CE_HasLabel (L[3]) &&
- IsSpLoad (L[4]) &&
- !CE_HasLabel (L[4]));
-}
-
-
-
/*****************************************************************************/
/* Remove calls to the bool transformer subroutines */
/*****************************************************************************/
/* Check for a boolean transformer */
if (E->OPC == OP65_JSR &&
(Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
- (N = CS_GetNextEntry (S, I)) != 0 &&
+ (N = CS_GetNextEntry (S, I)) != 0 &&
(N->Info & OF_ZBRA) != 0) {
/* Make the boolean transformer unnecessary by changing the
unsigned OptCmp1 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * ldx xx
+ * stx tmp1
+ * ora tmp1
+ *
+ * and replace it by
+ *
+ * ora xx
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < CS_GetEntryCount (S)) {
+
+ CodeEntry* L[3];
+
+ /* Get next entry */
+ L[0] = CS_GetEntry (S, I);
+
+ /* Check for the sequence */
+ if (L[0]->OPC == OP65_LDX &&
+ !CS_RangeHasLabel (S, I+1, 2) &&
+ CS_GetEntries (S, L+1, I+1, 2) &&
+ L[1]->OPC == OP65_STX &&
+ strcmp (L[1]->Arg, "tmp1") == 0 &&
+ L[2]->OPC == OP65_ORA &&
+ strcmp (L[2]->Arg, "tmp1") == 0) {
+
+ CodeEntry* X;
+
+ /* Insert the ora instead */
+ X = NewCodeEntry (OP65_ORA, L[0]->AM, L[0]->Arg, 0, L[0]->LI);
+ CS_InsertEntry (S, X, I);
+
+ /* Remove all other instructions */
+ CS_DelEntries (S, I+1, 3);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+unsigned OptCmp2 (CodeSeg* S)
/* Search for the sequence
*
* stx xx
CodeEntry* E = CS_GetEntry (S, I);
/* Check for the sequence */
- if (E->OPC == OP65_STX &&
+ if (E->OPC == OP65_STX &&
+ !CS_RangeHasLabel (S, I+1, 2) &&
CS_GetEntries (S, L, I+1, 2) &&
- L[0]->OPC == OP65_STX &&
+ L[0]->OPC == OP65_STX &&
strcmp (L[0]->Arg, "tmp1") == 0 &&
- !CE_HasLabel (L[0]) &&
- L[1]->OPC == OP65_ORA &&
- strcmp (L[1]->Arg, "tmp1") == 0 &&
- !CE_HasLabel (L[1])) {
+ L[1]->OPC == OP65_ORA &&
+ strcmp (L[1]->Arg, "tmp1") == 0) {
/* Remove the remaining instructions */
CS_DelEntries (S, I+1, 2);
-unsigned OptCmp2 (CodeSeg* S)
+unsigned OptCmp3 (CodeSeg* S)
/* Search for
*
* lda/and/ora/eor ...
unsigned I = 0;
while (I < CS_GetEntryCount (S)) {
- CodeEntry* L[2];
+ CodeEntry* L[3];
/* Get next entry */
- CodeEntry* E = CS_GetEntry (S, I);
+ L[0] = CS_GetEntry (S, I);
/* Check for the sequence */
- if ((E->OPC == OP65_ADC ||
- E->OPC == OP65_AND ||
- E->OPC == OP65_DEA ||
- E->OPC == OP65_EOR ||
- E->OPC == OP65_INA ||
- E->OPC == OP65_LDA ||
- E->OPC == OP65_ORA ||
- E->OPC == OP65_PLA ||
- E->OPC == OP65_SBC ||
- E->OPC == OP65_TXA ||
- E->OPC == OP65_TYA) &&
- CS_GetEntries (S, L, I+1, 2) &&
- IsCmpToZero (L[0]) &&
- !CE_HasLabel (L[0]) &&
- ((L[1]->Info & OF_FBRA) != 0 ||
- (L[1]->OPC == OP65_JSR &&
- FindBoolCmpCond (L[1]->Arg) != CMP_INV)) &&
- !CE_HasLabel (L[1])) {
-
- /* Remove the compare */
- CS_DelEntry (S, I+1);
-
- /* Remember, we had changes */
- ++Changes;
-
+ if ((L[0]->OPC == OP65_ADC ||
+ L[0]->OPC == OP65_AND ||
+ L[0]->OPC == OP65_ASL ||
+ L[0]->OPC == OP65_DEA ||
+ L[0]->OPC == OP65_EOR ||
+ L[0]->OPC == OP65_INA ||
+ L[0]->OPC == OP65_LDA ||
+ L[0]->OPC == OP65_LSR ||
+ L[0]->OPC == OP65_ORA ||
+ L[0]->OPC == OP65_PLA ||
+ L[0]->OPC == OP65_SBC ||
+ L[0]->OPC == OP65_TXA ||
+ L[0]->OPC == OP65_TYA) &&
+ !CS_RangeHasLabel (S, I+1, 2) &&
+ CS_GetEntries (S, L+1, I+1, 2) &&
+ L[1]->OPC == OP65_CMP &&
+ CE_IsKnownImm (L[1], 0)) {
+
+ int Delete = 0;
+
+ /* Check for the call to boolxx. We only remove the compare if
+ * the carry flag is evaluated later, because the load will not
+ * set the carry flag.
+ */
+ if (L[2]->OPC == OP65_JSR) {
+ switch (FindBoolCmpCond (L[2]->Arg)) {
+
+ case CMP_EQ:
+ case CMP_NE:
+ case CMP_GT:
+ case CMP_GE:
+ case CMP_LT:
+ case CMP_LE:
+ /* Remove the compare */
+ Delete = 1;
+ break;
+
+ case CMP_UGT:
+ case CMP_UGE:
+ case CMP_ULT:
+ case CMP_ULE:
+ case CMP_INV:
+ /* Leave it alone */
+ break;
+ }
+
+ } else if ((L[2]->Info & OF_FBRA) != 0) {
+
+ /* The following insn branches on the condition of a load, so
+ * the compare instruction can be removed.
+ */
+ Delete = 1;
+
+ }
+
+ /* Delete the compare if we can */
+ if (Delete) {
+ CS_DelEntry (S, I+1);
+ ++Changes;
+ }
}
/* Next entry */
-unsigned OptCmp3 (CodeSeg* S)
+unsigned OptCmp4 (CodeSeg* S)
/* Search for
*
* lda x
* cpx #a
* bne L1
* cmp #b
- * jne/jeq L2
+ * L1: jne/jeq L2
*
* If a is zero, we may remove the compare. If a and b are both zero, we may
* replace it by the sequence
/* Check for the sequence */
if (E->OPC == OP65_LDA &&
- CS_GetEntries (S, L, I+1, 5) &&
+ CS_GetEntries (S, L, I+1, 5) &&
L[0]->OPC == OP65_LDX &&
!CE_HasLabel (L[0]) &&
- IsImmCmp16 (S, L+1)) {
+ IsImmCmp16 (L+1) &&
+ !RegAXUsed (S, I+6)) {
- if (L[1]->Num == 0 && L[3]->Num == 0) {
+ if ((L[4]->Info & OF_FBRA) != 0 && L[1]->Num == 0 && L[3]->Num == 0) {
/* The value is zero, we may use the simple code version. */
CE_ReplaceOPC (L[0], OP65_ORA);
CS_DelEntries (S, I+2, 3);
-unsigned OptCmp4 (CodeSeg* S)
+unsigned OptCmp5 (CodeSeg* S)
/* Optimize compares of local variables:
*
* ldy #o
- * lda (sp),y
- * tax
- * dey
- * lda (sp),y
+ * jsr ldaxysp
* cpx #a
* bne L1
* cmp #b
unsigned I = 0;
while (I < CS_GetEntryCount (S)) {
- CodeEntry* L[9];
+ CodeEntry* L[6];
+
+ /* Get the next entry */
+ L[0] = CS_GetEntry (S, I);
/* Check for the sequence */
- if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
+ if (L[0]->OPC == OP65_LDY &&
+ CE_IsConstImm (L[0]) &&
+ CS_GetEntries (S, L+1, I+1, 5) &&
+ !CE_HasLabel (L[1]) &&
+ CE_IsCallTo (L[1], "ldaxysp") &&
+ IsImmCmp16 (L+2)) {
- if (L[5]->Num == 0 && L[7]->Num == 0) {
+ if ((L[5]->Info & OF_FBRA) != 0 && L[2]->Num == 0 && L[4]->Num == 0) {
+
+ CodeEntry* X;
+ char Buf[20];
/* The value is zero, we may use the simple code version:
- * ldy #o
- * lda (sp),y
- * dey
+ * ldy #o-1
+ * lda (sp),y
+ * ldy #o
* ora (sp),y
* jne/jeq ...
*/
- CE_ReplaceOPC (L[4], OP65_ORA);
+ sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
+ X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
+ CS_InsertEntry (S, X, I+1);
+
+ X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
+ CS_InsertEntry (S, X, I+2);
+
+ X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
+ CS_InsertEntry (S, X, I+3);
+
+ X = NewCodeEntry (OP65_ORA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
+ CS_InsertEntry (S, X, I+4);
+
CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */
- CS_DelEntry (S, I+2); /* tax */
+ CS_DelEntry (S, I); /* ldy */
} else {
+ CodeEntry* X;
+ char Buf[20];
+
/* Change the code to just use the A register. Move the load
* of the low byte after the first branch if possible:
*
* lda (sp),y
* cmp #a
* bne L1
- * dey
+ * ldy #o-1
* lda (sp),y
* cmp #b
* jne/jeq ...
*/
- CS_DelEntry (S, I+2); /* tax */
- CE_ReplaceOPC (L[5], OP65_CMP); /* cpx -> cmp */
- CS_MoveEntry (S, I+4, I+2); /* cmp */
- CS_MoveEntry (S, I+5, I+3); /* bne */
+ X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI);
+ CS_InsertEntry (S, X, I+3);
+
+ X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
+ CS_InsertEntry (S, X, I+4);
+
+ X = NewCodeEntry (OP65_CMP, L[2]->AM, L[2]->Arg, 0, L[2]->LI);
+ CS_InsertEntry (S, X, I+5);
+
+ sprintf (Buf, "$%02X", (int)(L[0]->Num-1));
+ X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI);
+ CS_InsertEntry (S, X, I+7);
+
+ X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp", 0, L[1]->LI);
+ CS_InsertEntry (S, X, I+8);
+
+ CS_DelEntries (S, I, 3); /* ldy/jsr/cpx */
}
-unsigned OptCmp5 (CodeSeg* S)
+unsigned OptCmp6 (CodeSeg* S)
/* Search for calls to compare subroutines followed by a conditional branch
* and replace them by cheaper versions, since the branch means that the
* boolean value returned by these routines is not needed (we may also check
CodeEntry* E = CS_GetEntry (S, I);
/* Check for the sequence */
- if (E->OPC == OP65_JSR &&
+ if (E->OPC == OP65_JSR &&
(Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
(N = CS_GetNextEntry (S, I)) != 0 &&
(N->Info & OF_ZBRA) != 0 &&
-unsigned OptCmp6 (CodeSeg* S)
+unsigned OptCmp7 (CodeSeg* S)
/* Search for a sequence ldx/txa/branch and remove the txa if A is not
* used later.
*/
-unsigned OptCmp7 (CodeSeg* S)
+unsigned OptCmp8 (CodeSeg* S)
/* Check for register compares where the contents of the register and therefore
* the result of the compare is known.
*/
unsigned Changes = 0;
unsigned I;
- /* Generate register info for this step */
- CS_GenRegInfo (S);
-
/* Walk over the entries */
I = 0;
while (I < CS_GetEntryCount (S)) {
/* Check for a compare against an immediate value */
if ((E->Info & OF_CMP) != 0 &&
(RegVal = GetCmpRegVal (E)) >= 0 &&
- CE_KnownImm (E)) {
+ CE_IsConstImm (E)) {
/* We are able to evaluate the compare at compile time. Check if
* one or more branches are ahead.
CS_DelEntry (S, I+1);
} else {
CodeLabel* L = N->JumpTo;
- CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, L->Name, L, N->LI);
+ const char* LabelName = L? L->Name : N->Arg;
+ CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, LabelName, L, N->LI);
CS_InsertEntry (S, X, I+2);
CS_DelEntry (S, I+1);
}
}
- /* Free register info */
- CS_FreeRegInfo (S);
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+unsigned OptCmp9 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * sbc xx
+ * bvs/bvc L
+ * eor #$80
+ * L: asl a
+ * bcc/bcs somewhere
+ *
+ * If A is not used later (which should be the case), we can branch on the N
+ * flag instead of the carry flag and remove the asl.
+ */
+{
+ unsigned Changes = 0;
+ unsigned I;
+
+ /* Walk over the entries */
+ I = 0;
+ while (I < CS_GetEntryCount (S)) {
+
+ CodeEntry* L[5];
+
+ /* Get next entry */
+ L[0] = CS_GetEntry (S, I);
+
+ /* Check for the sequence */
+ if (L[0]->OPC == OP65_SBC &&
+ CS_GetEntries (S, L+1, I+1, 4) &&
+ (L[1]->OPC == OP65_BVC ||
+ L[1]->OPC == OP65_BVS) &&
+ L[1]->JumpTo != 0 &&
+ L[1]->JumpTo->Owner == L[3] &&
+ L[2]->OPC == OP65_EOR &&
+ CE_IsKnownImm (L[2], 0x80) &&
+ L[3]->OPC == OP65_ASL &&
+ L[3]->AM == AM65_ACC &&
+ (L[4]->OPC == OP65_BCC ||
+ L[4]->OPC == OP65_BCS ||
+ L[4]->OPC == OP65_JCC ||
+ L[4]->OPC == OP65_JCS) &&
+ !CE_HasLabel (L[4]) &&
+ !RegAUsed (S, I+4)) {
+
+ /* Replace the branch condition */
+ switch (GetBranchCond (L[4]->OPC)) {
+ case BC_CC: CE_ReplaceOPC (L[4], OP65_JPL); break;
+ case BC_CS: CE_ReplaceOPC (L[4], OP65_JMI); break;
+ default: Internal ("Unknown branch condition in OptCmp9");
+ }
+
+ /* Delete the asl insn */
+ CS_DelEntry (S, I+3);
+
+ /* Next sequence is somewhat ahead (if any) */
+ I += 3;
+
+ /* Remember, we had changes */
+ ++Changes;
+ }
+
+ /* Next entry */
+ ++I;
+ }
/* Return the number of changes made */
return Changes;