+#include <string.h>
+
/* common */
+#include "abend.h"
#include "print.h"
/* cc65 */
+#include "asmlabel.h"
#include "codeent.h"
#include "codeinfo.h"
+#include "coptind.h"
+#include "error.h"
#include "global.h"
#include "codeopt.h"
-/* Counter for the number of changes in one run. The optimizer process is
- * repeated until there are no more changes.
- */
-static unsigned OptChanges;
+/* 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_LE, CMP_LT, CMP_GE, CMP_GT,
+ 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
+};
/*****************************************************************************/
-/* Remove dead jumps */
+/* Helper functions */
/*****************************************************************************/
-static void OptDeadJumps (CodeSeg* S)
-/* Remove dead jumps (jumps to the next instruction) */
+static cmp_t FindCmpCond (const char* Code, unsigned CodeLen)
+/* Search for a compare condition by the given code using the given length */
{
- CodeEntry* E;
unsigned I;
- /* Get the number of entries, bail out if we have less than two entries */
- unsigned Count = CollCount (&S->Entries);
- if (Count < 2) {
- return;
+ /* Linear search */
+ for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
+ if (strncmp (Code, CmpSuffixTab [I], CodeLen) == 0) {
+ /* Found */
+ return I;
+ }
}
- /* Walk over all entries minus the last one */
- I = 0;
- while (I < Count-1) {
+ /* Not found */
+ return CMP_INV;
+}
- /* Get the next entry */
- E = GetCodeEntry (S, I);
- /* Check if it's a branch, if it has a local target, and if the target
- * is the next instruction.
- */
- if (E->AM == AM_BRA && E->JumpTo && E->JumpTo->Owner == GetCodeEntry (S, I+1)) {
- /* Delete the dead jump */
- DelCodeEntry (S, I);
+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;
+ }
+}
- /* Keep the number of entries updated */
- --Count;
- /* Remember, we had changes */
- ++OptChanges;
- } else {
+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
+ * codes are evaluated directly.
+ * I is the index of the conditional branch, the sequence is already checked
+ * to be correct.
+ */
+{
+ CodeEntry* N;
+ CodeLabel* L;
+
+ /* Get the entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Replace the conditional branch */
+ switch (Cond) {
+
+ case CMP_EQ:
+ ReplaceOPC (E, OPC_JEQ);
+ break;
+
+ case CMP_NE:
+ ReplaceOPC (E, OPC_JNE);
+ break;
+
+ case CMP_GT:
+ /* Replace by
+ * beq @L
+ * jpl Target
+ * @L: ...
+ */
+ if ((N = GetNextCodeEntry (S, I)) == 0) {
+ /* No such entry */
+ Internal ("Invalid program flow");
+ }
+ L = GenCodeLabel (S, N);
+ N = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L, E->LI);
+ InsertCodeEntry (S, N, I);
+ ReplaceOPC (E, OPC_JPL);
+ break;
+
+ case CMP_GE:
+ ReplaceOPC (E, OPC_JPL);
+ break;
+
+ case CMP_LT:
+ ReplaceOPC (E, OPC_JMI);
+ break;
+
+ case CMP_LE:
+ /* Replace by
+ * jmi Target
+ * jeq Target
+ */
+ ReplaceOPC (E, OPC_JMI);
+ L = E->JumpTo;
+ N = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L, E->LI);
+ InsertCodeEntry (S, N, I+1);
+ break;
+
+ case CMP_UGT:
+ /* Replace by
+ * beq @L
+ * jcs Target
+ * @L: ...
+ */
+ if ((N = GetNextCodeEntry (S, I)) == 0) {
+ /* No such entry */
+ Internal ("Invalid program flow");
+ }
+ L = GenCodeLabel (S, N);
+ N = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L, E->LI);
+ InsertCodeEntry (S, N, I);
+ ReplaceOPC (E, OPC_JCS);
+ break;
+
+ case CMP_UGE:
+ ReplaceOPC (E, OPC_JCS);
+ break;
+
+ case CMP_ULT:
+ ReplaceOPC (E, OPC_JCC);
+ break;
+
+ case CMP_ULE:
+ /* Replace by
+ * jcc Target
+ * jeq Target
+ */
+ ReplaceOPC (E, OPC_JCC);
+ L = E->JumpTo;
+ N = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L, E->LI);
+ InsertCodeEntry (S, N, I+1);
+ break;
+
+ default:
+ Internal ("Unknown jump condition: %d", Cond);
+
+ }
+
+}
+
+
+
+static int IsUnsignedCmp (int Code)
+/* Check if this is an unsigned compare */
+{
+ CHECK (Code >= 0);
+ return CmpSignedTab [Code] == 0;
+}
+
+
+
+static int IsBitOp (const CodeEntry* E)
+/* Check if E is one of the bit operations (and, or, eor) */
+{
+ return (E->OPC == OPC_AND || E->OPC == OPC_ORA || E->OPC == OPC_EOR);
+}
+
+
+
+static int IsCmpToZero (const CodeEntry* E)
+/* Check if the given instrcuction is a compare to zero instruction */
+{
+ return (E->OPC == OPC_CMP &&
+ E->AM == AM_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 == OPC_LDA && E->AM == AM_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] = GetCodeEntry (S, Index);
+
+ /* Check for the sequence */
+ return (L[0]->OPC == OPC_LDY &&
+ L[0]->AM == AM_IMM &&
+ (L[0]->Flags & CEF_NUMARG) != 0 &&
+ GetCodeEntries (S, L+1, Index+1, Count-1) &&
+ IsSpLoad (L[1]) &&
+ !CodeEntryHasLabel (L[1]) &&
+ L[2]->OPC == OPC_TAX &&
+ !CodeEntryHasLabel (L[2]) &&
+ L[3]->OPC == OPC_DEY &&
+ !CodeEntryHasLabel (L[3]) &&
+ IsSpLoad (L[4]) &&
+ !CodeEntryHasLabel (L[4]));
+}
+
+
+
+static int IsImmCmp16 (CodeSeg* S, CodeEntry** L)
+/* Check if the instructions at L are an immidiate compare of a/x:
+ *
+ *
+ */
+{
+ return (L[0]->OPC == OPC_CPX &&
+ L[0]->AM == AM_IMM &&
+ (L[0]->Flags & CEF_NUMARG) != 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ (L[1]->OPC == OPC_JNE || L[1]->OPC == OPC_BNE) &&
+ L[1]->JumpTo != 0 &&
+ !CodeEntryHasLabel (L[1]) &&
+ L[2]->OPC == OPC_CMP &&
+ L[2]->AM == AM_IMM &&
+ (L[2]->Flags & CEF_NUMARG) != 0 &&
+ (L[3]->Info & OF_ZBRA) != 0 &&
+ L[3]->JumpTo != 0 &&
+ (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo));
+}
+
+
+
+/*****************************************************************************/
+/* Remove calls to the bool transformer subroutines */
+/*****************************************************************************/
+
+
+
+static unsigned OptBoolTransforms (CodeSeg* S)
+/* Try to remove the call to boolean transformer routines where the call is
+ * not really needed.
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* N;
+ cmp_t Cond;
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for a boolean transformer */
+ if (E->OPC == OPC_JSR &&
+ (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV &&
+ (N = GetNextCodeEntry (S, I)) != 0 &&
+ (N->Info & OF_ZBRA) != 0) {
+
+ /* Make the boolean transformer unnecessary by changing the
+ * the conditional jump to evaluate the condition flags that
+ * are set after the compare directly. Note: jeq jumps if
+ * the condition is not met, jne jumps if the condition is met.
+ * Invert the code if we jump on condition not met.
+ */
+ if (GetBranchCond (N->OPC) == BC_EQ) {
+ /* Jumps if condition false, invert condition */
+ Cond = CmpInvertTab [Cond];
+ }
+
+ /* Check if we can replace the code by something better */
+ ReplaceCmp (S, I+1, Cond);
+
+ /* Remove the call to the bool transformer */
+ DelCodeEntry (S, I);
- /* Next entry */
- ++I;
+ /* Remember, we had changes */
+ ++Changes;
}
+
+ /* Next entry */
+ ++I;
+
}
+
+ /* Return the number of changes made */
+ return Changes;
}
/*****************************************************************************/
-/* Remove dead code */
+/* Optimize subtractions */
/*****************************************************************************/
-static void OptDeadCode (CodeSeg* S)
-/* Remove dead code (code that follows an unconditional jump or an rts/rti
- * and has no label)
+static unsigned OptSub1 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * sbc ...
+ * bcs L
+ * dex
+ * L:
+ *
+ * and remove the handling of the high byte if X is not used later.
*/
{
- unsigned I;
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[3];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_SBC &&
+ GetCodeEntries (S, L, I+1, 3) &&
+ (L[0]->OPC == OPC_BCS || L[0]->OPC == OPC_JCS) &&
+ L[0]->JumpTo != 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ L[1]->OPC == OPC_DEX &&
+ !CodeEntryHasLabel (L[1]) &&
+ L[0]->JumpTo->Owner == L[2] &&
+ !RegXUsed (S, I+3)) {
+
+ /* Remove the bcs/dex */
+ DelCodeEntries (S, I+1, 2);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptSub2 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * lda xx
+ * sec
+ * sta tmp1
+ * lda yy
+ * sbc tmp1
+ * sta yy
+ *
+ * and replace it by
+ *
+ * sec
+ * lda yy
+ * sbc xx
+ * sta yy
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[5];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_LDA &&
+ GetCodeEntries (S, L, I+1, 5) &&
+ L[0]->OPC == OPC_SEC &&
+ !CodeEntryHasLabel (L[0]) &&
+ L[1]->OPC == OPC_STA &&
+ strcmp (L[1]->Arg, "tmp1") == 0 &&
+ !CodeEntryHasLabel (L[1]) &&
+ L[2]->OPC == OPC_LDA &&
+ !CodeEntryHasLabel (L[2]) &&
+ L[3]->OPC == OPC_SBC &&
+ strcmp (L[3]->Arg, "tmp1") == 0 &&
+ !CodeEntryHasLabel (L[3]) &&
+ L[4]->OPC == OPC_STA &&
+ strcmp (L[4]->Arg, L[2]->Arg) == 0 &&
+ !CodeEntryHasLabel (L[4])) {
+
+ /* Remove the store to tmp1 */
+ DelCodeEntry (S, I+2);
+
+ /* Remove the subtraction */
+ DelCodeEntry (S, I+3);
+
+ /* Move the lda to the position of the subtraction and change the
+ * op to SBC.
+ */
+ MoveCodeEntry (S, I, I+3);
+ ReplaceOPC (E, OPC_SBC);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
- /* Get the number of entries, bail out if we have less than two entries */
- unsigned Count = CollCount (&S->Entries);
- if (Count < 2) {
- return;
}
- /* Walk over all entries minus the last one */
- I = 0;
- while (I < Count-1) {
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
- /* Get this entry */
- CodeEntry* E = GetCodeEntry (S, I);
+/*****************************************************************************/
+/* Optimize additions */
+/*****************************************************************************/
+
+
+
+static unsigned OptAdd1 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * adc ...
+ * bcc L
+ * inx
+ * L:
+ *
+ * and remove the handling of the high byte if X is not used later.
+ */
+{
+ unsigned Changes = 0;
- /* Check if it's an unconditional branch, and if the next entry has
- * no labels attached
- */
- if ((E->Info & OF_DEAD) != 0 && !CodeEntryHasLabel (GetCodeEntry (S, I+1))) {
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
- /* Delete the next entry */
- DelCodeEntry (S, I+1);
+ CodeEntry* L[3];
- /* Keep the number of entries updated */
- --Count;
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
- /* Remember, we had changes */
- ++OptChanges;
+ /* Check for the sequence */
+ if (E->OPC == OPC_ADC &&
+ GetCodeEntries (S, L, I+1, 3) &&
+ (L[0]->OPC == OPC_BCC || L[0]->OPC == OPC_JCC) &&
+ L[0]->JumpTo != 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ L[1]->OPC == OPC_INX &&
+ !CodeEntryHasLabel (L[1]) &&
+ L[0]->JumpTo->Owner == L[2] &&
+ !RegXUsed (S, I+3)) {
- } else {
+ /* Remove the bcs/dex */
+ DelCodeEntries (S, I+1, 2);
- /* Next entry */
- ++I;
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
- }
}
+
+ /* Return the number of changes made */
+ return Changes;
}
/*****************************************************************************/
-/* Optimize jump cascades */
+/* Optimizations for compares */
/*****************************************************************************/
-static void OptJumpCascades (CodeSeg* S)
-/* Optimize jump cascades (jumps to jumps). In such a case, the jump is
- * replaced by a jump to the final location. This will in some cases produce
- * worse code, because some jump targets are no longer reachable by short
- * branches, but this is quite rare, so there are more advantages than
- * disadvantages.
+static unsigned OptCmp1 (CodeSeg* S)
+/* Search for the sequence
+ *
+ * stx xx
+ * stx tmp1
+ * ora tmp1
+ *
+ * and replace it by
+ *
+ * stx xx
+ * ora xx
*/
{
- unsigned I;
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[2];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_STX &&
+ GetCodeEntries (S, L, I+1, 2) &&
+ L[0]->OPC == OPC_STX &&
+ strcmp (L[0]->Arg, "tmp1") == 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ L[1]->OPC == OPC_ORA &&
+ strcmp (L[1]->Arg, "tmp1") == 0 &&
+ !CodeEntryHasLabel (L[1])) {
+
+ /* Remove the remaining instructions */
+ DelCodeEntries (S, I+1, 2);
+
+ /* Insert the ora instead */
+ InsertCodeEntry (S, NewCodeEntry (OPC_ORA, E->AM, E->Arg, 0, E->LI), I+1);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptCmp2 (CodeSeg* S)
+/* Search for
+ *
+ * lda/and/ora/eor ...
+ * cmp #$00
+ * jeq/jne
+ *
+ * and remove the cmp.
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[2];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if ((E->OPC == OPC_LDA || IsBitOp (E)) &&
+ GetCodeEntries (S, L, I+1, 2) &&
+ IsCmpToZero (L[0]) &&
+ !CodeEntryHasLabel (L[0]) &&
+ (L[1]->Info & OF_FBRA) != 0 &&
+ !CodeEntryHasLabel (L[1])) {
+
+ /* Remove the compare */
+ DelCodeEntry (S, I+1);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
- /* Get the number of entries, bail out if we have no entries */
- unsigned Count = CollCount (&S->Entries);
- if (Count == 0) {
- return;
}
- /* Walk over all entries */
- I = 0;
- while (I < Count) {
+ /* Return the number of changes made */
+ return Changes;
+}
- CodeLabel* OldLabel;
- CodeLabel* NewLabel;
- /* Get this entry */
- CodeEntry* E = GetCodeEntry (S, I);
- /* Check if it's a branch, if it has a label attached, and if the
- * instruction at this label is also a branch, and (important) if
- * both instructions are not identical.
- */
- if (E->AM == AM_BRA && /* It's a branch */
- (OldLabel = E->JumpTo) != 0 && /* Label attached */
- OldLabel->Owner->AM == AM_BRA && /* Jumps to a branch.. */
- (NewLabel = OldLabel->Owner->JumpTo) != 0 && /* ..which has a label */
- OldLabel->Owner != E) { /* And both are distinct */
+static unsigned OptCmp3 (CodeSeg* S)
+/* Search for
+ *
+ * lda x
+ * ldx y
+ * cpx #a
+ * bne L1
+ * cmp #b
+ * 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
+ *
+ * lda x
+ * ora x+1
+ * jne/jeq ...
+ *
+ * L1 may be either the label at the branch instruction, or the target label
+ * of this instruction.
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[5];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_LDA &&
+ GetCodeEntries (S, L, I+1, 5) &&
+ L[0]->OPC == OPC_LDX &&
+ !CodeEntryHasLabel (L[0]) &&
+ IsImmCmp16 (S, L+1)) {
+
+ if (L[1]->Num == 0 && L[3]->Num == 0) {
+ /* The value is zero, we may use the simple code version. */
+ ReplaceOPC (L[0], OPC_ORA);
+ DelCodeEntries (S, I+2, 3);
+ } else {
+ /* Move the lda instruction after the first branch. This will
+ * improve speed, since the load is delayed after the first
+ * test.
+ */
+ MoveCodeEntry (S, I, I+4);
+
+ /* We will replace the ldx/cpx by lda/cmp */
+ ReplaceOPC (L[0], OPC_LDA);
+ ReplaceOPC (L[1], OPC_CMP);
- /* Get the instruction that has the new label attached */
- CodeEntry* N = OldLabel->Owner;
+ }
+
+ ++Changes;
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptCmp4 (CodeSeg* S)
+/* Optimize compares of local variables:
+ *
+ * ldy #o
+ * lda (sp),y
+ * tax
+ * dey
+ * lda (sp),y
+ * cpx #a
+ * bne L1
+ * cmp #b
+ * jne/jeq L2
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[9];
+
+ /* Check for the sequence */
+ if (IsLocalLoad16 (S, I, L, 9) && IsImmCmp16 (S, L+5)) {
+
+ if (L[5]->Num == 0 && L[7]->Num == 0) {
+
+ /* The value is zero, we may use the simple code version:
+ * ldy #o
+ * lda (sp),y
+ * dey
+ * ora (sp),y
+ * jne/jeq ...
+ */
+ ReplaceOPC (L[4], OPC_ORA);
+ DelCodeEntries (S, I+5, 3); /* cpx/bne/cmp */
+ DelCodeEntry (S, I+2); /* tax */
+
+ } else {
+
+ /* Change the code to just use the A register. Move the load
+ * of the low byte after the first branch if possible:
+ *
+ * ldy #o
+ * lda (sp),y
+ * cmp #a
+ * bne L1
+ * dey
+ * lda (sp),y
+ * cmp #b
+ * jne/jeq ...
+ */
+ DelCodeEntry (S, I+2); /* tax */
+ ReplaceOPC (L[5], OPC_CMP); /* cpx -> cmp */
+ MoveCodeEntry (S, I+4, I+2); /* cmp */
+ MoveCodeEntry (S, I+5, I+3); /* bne */
- /* Remove the reference to our label and delete it if this was
- * the last reference.
- */
- if (RemoveLabelRef (OldLabel, E) == 0) {
- /* Delete it */
- DelCodeLabel (S, OldLabel);
}
- /* Use the usage information from the new instruction */
- E->Use = N->Use;
- E->Chg = N->Chg;
+ ++Changes;
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
- /* Use the new label */
- AddLabelRef (NewLabel, E);
+static unsigned OptCmp5 (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
+ * that explicitly, but for the current code generator it is always true).
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* N;
+ cmp_t Cond;
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_JSR &&
+ (Cond = FindTosCmpCond (E->Arg)) != CMP_INV &&
+ (N = GetNextCodeEntry (S, I)) != 0 &&
+ (N->Info & OF_ZBRA) != 0 &&
+ !CodeEntryHasLabel (N)) {
+
+ /* The tos... functions will return a boolean value in a/x and
+ * the Z flag says if this value is zero or not. We will call
+ * a cheaper subroutine instead, one that does not return a
+ * boolean value but only valid flags. Note: jeq jumps if
+ * the condition is not met, jne jumps if the condition is met.
+ * Invert the code if we jump on condition not met.
+ */
+ if (GetBranchCond (N->OPC) == BC_EQ) {
+ /* Jumps if condition false, invert condition */
+ Cond = CmpInvertTab [Cond];
+ }
+
+ /* Replace the subroutine call. */
+ E = NewCodeEntry (OPC_JSR, AM_ABS, "tosicmp", 0, E->LI);
+ InsertCodeEntry (S, E, I+1);
+ DelCodeEntry (S, I);
+
+ /* Replace the conditional branch */
+ ReplaceCmp (S, I+1, Cond);
- /* Remember ,we had changes */
- ++OptChanges;
+ /* Remember, we had changes */
+ ++Changes;
}
++I;
}
+
+ /* Return the number of changes made */
+ return Changes;
}
/*****************************************************************************/
-/* Optimize jsr/rts */
+/* nega optimizations */
/*****************************************************************************/
-static void OptRTS (CodeSeg* S)
-/* Optimize subroutine calls followed by an RTS. The subroutine call will get
- * replaced by a jump. Don't bother to delete the RTS if it does not have a
- * label, the dead code elimination should take care of it.
+static unsigned OptNegA1 (CodeSeg* S)
+/* Check for
+ *
+ * ldx #$00
+ * lda ..
+ * jsr bnega
+ *
+ * Remove the ldx if the lda does not use it.
*/
{
- unsigned I;
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[2];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for a ldx */
+ if (E->OPC == OPC_LDX &&
+ E->AM == AM_IMM &&
+ (E->Flags & CEF_NUMARG) != 0 &&
+ E->Num == 0 &&
+ GetCodeEntries (S, L, I+1, 2) &&
+ L[0]->OPC == OPC_LDA &&
+ (L[0]->Use & REG_X) == 0 &&
+ L[1]->OPC == OPC_JSR &&
+ strcmp (L[1]->Arg, "bnega") == 0) {
+
+ /* Remove the ldx instruction */
+ DelCodeEntry (S, I);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
- /* Get the number of entries, bail out if we have less than 2 entries */
- unsigned Count = CollCount (&S->Entries);
- if (Count < 2) {
- return;
}
- /* Walk over all entries minus the last one */
- I = 0;
- while (I < Count-1) {
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptNegA2 (CodeSeg* S)
+/* Check for
+ *
+ * lda ..
+ * jsr bnega
+ * jeq/jne ..
+ *
+ * Adjust the conditional branch and remove the call to the subroutine.
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[2];
- /* Get this entry */
- CodeEntry* E = GetCodeEntry (S, I);
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
- /* Check if it's a subroutine call and if the following insn is RTS */
- if (E->OPC == OPC_JSR && GetCodeEntry(S,I+1)->OPC == OPC_RTS) {
+ /* Check for the sequence */
+ if (E->OPC == OPC_LDA &&
+ GetCodeEntries (S, L, I+1, 2) &&
+ L[0]->OPC == OPC_JSR &&
+ strcmp (L[0]->Arg, "bnega") == 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ (L[1]->Info & OF_ZBRA) != 0) {
- /* Change the jsr to a jmp */
- E->OPC = OPC_JMP;
+ /* Invert the branch */
+ ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
- /* Change the opcode info to that of the jump */
- E->Info = GetOPCInfo (OPC_JMP);
-
- /* Remember, we had changes */
- ++OptChanges;
+ /* Delete the subroutine call */
+ DelCodeEntry (S, I+1);
+
+ /* Remember, we had changes */
+ ++Changes;
}
++I;
}
+
+ /* Return the number of changes made */
+ return Changes;
}
/*****************************************************************************/
-/* Optimize jump targets */
+/* negax optimizations */
/*****************************************************************************/
-static void OptJumpTarget (CodeSeg* S)
-/* If the instruction preceeding an unconditional branch is the same as the
- * instruction preceeding the jump target, the jump target may be moved
- * one entry back. This is a size optimization, since the instruction before
- * the branch gets removed.
+static unsigned OptNegAX1 (CodeSeg* S)
+/* Search for the sequence:
+ *
+ * lda (xx),y
+ * tax
+ * dey
+ * lda (xx),y
+ * jsr bnegax
+ * jne/jeq ...
+ *
+ * and replace it by
+ *
+ * lda (xx),y
+ * dey
+ * ora (xx),y
+ * jeq/jne ...
*/
{
- unsigned I;
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[5];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_LDA &&
+ E->AM == AM_ZP_INDY &&
+ GetCodeEntries (S, L, I+1, 5) &&
+ L[0]->OPC == OPC_TAX &&
+ L[1]->OPC == OPC_DEY &&
+ L[2]->OPC == OPC_LDA &&
+ L[2]->AM == AM_ZP_INDY &&
+ strcmp (L[2]->Arg, E->Arg) == 0 &&
+ !CodeEntryHasLabel (L[2]) &&
+ L[3]->OPC == OPC_JSR &&
+ strcmp (L[3]->Arg, "bnegax") == 0 &&
+ !CodeEntryHasLabel (L[3]) &&
+ (L[4]->Info & OF_ZBRA) != 0) {
+
+ /* lda --> ora */
+ ReplaceOPC (L[2], OPC_ORA);
+
+ /* Invert the branch */
+ ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
+
+ /* Delete the entries no longer needed. Beware: Deleting entries
+ * will change the indices.
+ */
+ DelCodeEntry (S, I+4); /* jsr bnegax */
+ DelCodeEntry (S, I+1); /* tax */
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
- /* Get the number of entries, bail out if we have not enough */
- unsigned Count = CollCount (&S->Entries);
- if (Count < 3) {
- return;
}
- /* Walk over all entries minus the first one */
- I = 1;
- while (I < Count) {
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptNegAX2 (CodeSeg* S)
+/* Search for the sequence:
+ *
+ * lda xx
+ * ldx yy
+ * jsr bnegax
+ * jne/jeq ...
+ *
+ * and replace it by
+ *
+ * lda xx
+ * ora xx+1
+ * jeq/jne ...
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[3];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_LDA &&
+ GetCodeEntries (S, L, I+1, 3) &&
+ L[0]->OPC == OPC_LDX &&
+ !CodeEntryHasLabel (L[0]) &&
+ L[1]->OPC == OPC_JSR &&
+ strcmp (L[1]->Arg, "bnegax") == 0 &&
+ !CodeEntryHasLabel (L[1]) &&
+ (L[2]->Info & OF_ZBRA) != 0) {
+
+ /* ldx --> ora */
+ ReplaceOPC (L[0], OPC_ORA);
+
+ /* Invert the branch */
+ ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
+
+ /* Delete the subroutine call */
+ DelCodeEntry (S, I+2);
+
+ /* Remember, we had changes */
+ ++Changes;
+
+ }
+
+ /* Next entry */
+ ++I;
+
+ }
+
+ /* Return the number of changes made */
+ return Changes;
+}
+
+
+
+static unsigned OptNegAX3 (CodeSeg* S)
+/* Search for the sequence:
+ *
+ * jsr _xxx
+ * jsr bnega(x)
+ * jeq/jne ...
+ *
+ * and replace it by:
+ *
+ * jsr _xxx
+ * <boolean test>
+ * jne/jeq ...
+ */
+{
+ unsigned Changes = 0;
+
+ /* Walk over the entries */
+ unsigned I = 0;
+ while (I < GetCodeEntryCount (S)) {
+
+ CodeEntry* L[2];
+
+ /* Get next entry */
+ CodeEntry* E = GetCodeEntry (S, I);
+
+ /* Check for the sequence */
+ if (E->OPC == OPC_JSR &&
+ E->Arg[0] == '_' &&
+ GetCodeEntries (S, L, I+1, 2) &&
+ L[0]->OPC == OPC_JSR &&
+ strncmp (L[0]->Arg,"bnega",5) == 0 &&
+ !CodeEntryHasLabel (L[0]) &&
+ (L[1]->Info & OF_ZBRA) != 0) {
+
+ CodeEntry* X;
+
+ /* Check if we're calling bnega or bnegax */
+ int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
+
+ /* Insert apropriate test code */
+ if (ByteSized) {
+ /* Test bytes */
+ X = NewCodeEntry (OPC_TAX, AM_IMP, 0, 0, L[0]->LI);
+ InsertCodeEntry (S, X, I+2);
+ } else {
+ /* Test words */
+ X = NewCodeEntry (OPC_STX, AM_ZP, "tmp1", 0, L[0]->LI);
+ InsertCodeEntry (S, X, I+2);
+ X = NewCodeEntry (OPC_ORA, AM_ZP, "tmp1", 0, L[0]->LI);
+ InsertCodeEntry (S, X, I+3);
+ }
- /* Get this entry and the entry before this one */
- CodeEntry* E = GetCodeEntry (S, I);
+ /* Delete the subroutine call */
+ DelCodeEntry (S, I+1);
- /* Check if we have a jump or branch, and a matching label */
- if ((E->Info & OF_UBRA) != 0 && E->JumpTo) {
+ /* Invert the branch */
+ ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
- /* Remember, we had changes */
- ++OptChanges;
+ /* Remember, we had changes */
+ ++Changes;
}
++I;
}
+
+ /* Return the number of changes made */
+ return Changes;
}
/*****************************************************************************/
-/* Code */
+/* Code */
/*****************************************************************************/
+/* Table with all the optimization functions */
+typedef struct OptFunc OptFunc;
+struct OptFunc {
+ unsigned (*Func) (CodeSeg*);/* Optimizer function */
+ const char* Name; /* Name of optimizer step */
+ char Disabled; /* True if pass disabled */
+};
+
+
+
+/* Table with optimizer steps - are called in this order */
+static OptFunc OptFuncs [] = {
+ /* Optimize subtractions */
+ { OptSub1, "OptSub1", 0 },
+ { OptSub2, "OptSub2", 0 },
+ /* Optimize additions */
+ { OptAdd1, "OptAdd1", 0 },
+ /* Optimize jump cascades */
+ { OptJumpCascades, "OptJumpCascades", 0 },
+ /* Remove dead jumps */
+ { OptDeadJumps, "OptDeadJumps", 0 },
+ /* Change jsr/rts to jmp */
+ { OptRTS, "OptRTS", 0 },
+ /* Remove dead code */
+ { OptDeadCode, "OptDeadCode", 0 },
+ /* Optimize jump targets */
+ { OptJumpTarget, "OptJumpTarget", 0 },
+ /* Optimize conditional branches */
+ { OptCondBranches, "OptCondBranches", 0 },
+ /* Replace jumps to RTS by RTS */
+ { OptRTSJumps, "OptRTSJumps", 0 },
+ /* Remove calls to the bool transformer subroutines */
+ { OptBoolTransforms, "OptBoolTransforms", 0 },
+ /* Optimize calls to nega */
+ { OptNegA1, "OptNegA1", 0 },
+ { OptNegA2, "OptNegA2", 0 },
+ /* Optimize calls to negax */
+ { OptNegAX1, "OptNegAX1", 0 },
+ { OptNegAX2, "OptNegAX2", 0 },
+ { OptNegAX3, "OptNegAX3", 0 },
+ /* Optimize compares */
+ { OptCmp1, "OptCmp1", 0 },
+ { OptCmp2, "OptCmp2", 0 },
+ { OptCmp3, "OptCmp3", 0 },
+ { OptCmp4, "OptCmp4", 0 },
+ { OptCmp5, "OptCmp5", 0 },
+ /* Remove unused loads */
+ { OptUnusedLoads, "OptUnusedLoads", 0 },
+ /* Optimize branch distance */
+ { OptBranchDist, "OptBranchDist", 0 },
+};
+
+
+
+static OptFunc* FindOptStep (const char* Name)
+/* Find an optimizer step by name in the table and return a pointer. Print an
+ * error and call AbEnd if not found.
+ */
+{
+ unsigned I;
+
+ /* Run all optimization steps */
+ for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
+ if (strcmp (OptFuncs[I].Name, Name) == 0) {
+ /* Found */
+ return OptFuncs+I;
+ }
+ }
+
+ /* Not found */
+ AbEnd ("Optimization step `%s' not found", Name);
+ return 0;
+}
+
+
+
+void DisableOpt (const char* Name)
+/* Disable the optimization with the given name */
+{
+ if (strcmp (Name, "any") == 0) {
+ unsigned I;
+ for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
+ OptFuncs[I].Disabled = 1;
+ }
+ } else {
+ OptFunc* F = FindOptStep (Name);
+ F->Disabled = 1;
+ }
+}
+
+
+
+void EnableOpt (const char* Name)
+/* Enable the optimization with the given name */
+{
+ if (strcmp (Name, "any") == 0) {
+ unsigned I;
+ for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
+ OptFuncs[I].Disabled = 0;
+ }
+ } else {
+ OptFunc* F = FindOptStep (Name);
+ F->Disabled = 0;
+ }
+}
+
+
+
void RunOpt (CodeSeg* S)
/* Run the optimizer */
{
- typedef void (*OptFunc) (CodeSeg*);
+ unsigned I;
+ unsigned Pass = 0;
+ unsigned OptChanges;
- /* Table with optimizer steps - are called in this order */
- static const OptFunc OptFuncs [] = {
- OptJumpCascades, /* Optimize jump cascades */
- OptDeadJumps, /* Remove dead jumps */
- OptDeadCode, /* Remove dead code */
- OptRTS, /* Change jsr/rts to jmp */
- };
+ /* If we shouldn't run the optimizer, bail out */
+ if (!Optimize) {
+ return;
+ }
+
+ /* Print the name of the function we are working on */
+ if (S->Func) {
+ Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
+ } else {
+ Print (stdout, 1, "Running optimizer for global code segment\n");
+ }
/* Repeat all steps until there are no more changes */
do {
-
- unsigned long Flags;
- unsigned I;
-
/* Reset the number of changes */
OptChanges = 0;
+ /* Keep the user hapy */
+ Print (stdout, 1, " Optimizer pass %u:\n", ++Pass);
+
/* Run all optimization steps */
- Flags = 1UL;
for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
- if ((OptDisable & Flags) == 0) {
- OptFuncs[I] (S);
- } else if (Verbosity > 0 || Debug) {
- printf ("Optimizer pass %u skipped\n", I);
+
+ /* Print the name of the following optimizer step */
+ Print (stdout, 1, " %s:%*s", OptFuncs[I].Name,
+ (int) (30-strlen(OptFuncs[I].Name)), "");
+
+ /* Check if the step is disabled */
+ if (OptFuncs[I].Disabled) {
+ Print (stdout, 1, "Disabled\n");
+ } else {
+ unsigned Changes = OptFuncs[I].Func (S);
+ OptChanges += Changes;
+ Print (stdout, 1, "%u Changes\n", Changes);
}
- Flags <<= 1;
}
} while (OptChanges > 0);
projects / cc65 / blobdiff