X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=src%2Fcc65%2Fcodeopt.c;h=0946a008e5560aeb5ed0296134c8f4b43c973027;hb=9ce1e413e4d5a9f48a57b3ce357e71d62281c7c8;hp=384a414559b0d8360b32e626750bfc6c72ffc687;hpb=1fbf554c6370e8d4c50393e3b78cdae9c32129f9;p=cc65 diff --git a/src/cc65/codeopt.c b/src/cc65/codeopt.c index 384a41455..0946a008e 100644 --- a/src/cc65/codeopt.c +++ b/src/cc65/codeopt.c @@ -33,15 +33,19 @@ +#include + /* common */ +#include "abend.h" #include "print.h" /* cc65 */ -#include "global.h" - -/* b6502 */ +#include "asmlabel.h" #include "codeent.h" #include "codeinfo.h" +#include "coptind.h" +#include "error.h" +#include "global.h" #include "codeopt.h" @@ -52,177 +56,1178 @@ -/* 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 = CollAt (&S->Entries, 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 == CollAt (&S->Entries, I+1)) { - /* Delete the dead jump */ - DelCodeSegLine (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; +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, OP65_JEQ); + break; + + case CMP_NE: + ReplaceOPC (E, OP65_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 (OP65_BEQ, AM65_BRA, L->Name, L, E->LI); + InsertCodeEntry (S, N, I); + ReplaceOPC (E, OP65_JPL); + break; + + case CMP_GE: + ReplaceOPC (E, OP65_JPL); + break; + + case CMP_LT: + ReplaceOPC (E, OP65_JMI); + break; + + case CMP_LE: + /* Replace by + * jmi Target + * jeq Target + */ + ReplaceOPC (E, OP65_JMI); + L = E->JumpTo; + N = NewCodeEntry (OP65_JEQ, AM65_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 (OP65_BEQ, AM65_BRA, L->Name, L, E->LI); + InsertCodeEntry (S, N, I); + ReplaceOPC (E, OP65_JCS); + break; + + case CMP_UGE: + ReplaceOPC (E, OP65_JCS); + break; + + case CMP_ULT: + ReplaceOPC (E, OP65_JCC); + break; + + case CMP_ULE: + /* Replace by + * jcc Target + * jeq Target + */ + ReplaceOPC (E, OP65_JCC); + L = E->JumpTo; + N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI); + InsertCodeEntry (S, N, I+1); + break; + + default: + Internal ("Unknown jump condition: %d", Cond); + + } + +} + + + +static int IsBitOp (const CodeEntry* E) +/* Check if E is one of the bit operations (and, or, eor) */ +{ + return (E->OPC == OP65_AND || E->OPC == OP65_ORA || E->OPC == OP65_EOR); +} + + + +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] = GetCodeEntry (S, Index); + + /* Check for the sequence */ + return (L[0]->OPC == OP65_LDY && + L[0]->AM == AM65_IMM && + (L[0]->Flags & CEF_NUMARG) != 0 && + GetCodeEntries (S, L+1, Index+1, Count-1) && + IsSpLoad (L[1]) && + !CodeEntryHasLabel (L[1]) && + L[2]->OPC == OP65_TAX && + !CodeEntryHasLabel (L[2]) && + L[3]->OPC == OP65_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 == OP65_CPX && + L[0]->AM == AM65_IMM && + (L[0]->Flags & CEF_NUMARG) != 0 && + !CodeEntryHasLabel (L[0]) && + (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) && + L[1]->JumpTo != 0 && + !CodeEntryHasLabel (L[1]) && + L[2]->OPC == OP65_CMP && + L[2]->AM == AM65_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 == OP65_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); /* Remember, we had changes */ - ++OptChanges; + ++Changes; - } else { + } - /* Next entry */ - ++I; + /* Next entry */ + ++I; + + } + + /* Return the number of changes made */ + return Changes; +} + + + +/*****************************************************************************/ +/* Optimize subtractions */ +/*****************************************************************************/ + + + +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 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 == OP65_SBC && + GetCodeEntries (S, L, I+1, 3) && + (L[0]->OPC == OP65_BCS || L[0]->OPC == OP65_JCS) && + L[0]->JumpTo != 0 && + !CodeEntryHasLabel (L[0]) && + L[1]->OPC == OP65_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 == OP65_LDA && + GetCodeEntries (S, L, I+1, 5) && + L[0]->OPC == OP65_SEC && + !CodeEntryHasLabel (L[0]) && + L[1]->OPC == OP65_STA && + strcmp (L[1]->Arg, "tmp1") == 0 && + !CodeEntryHasLabel (L[1]) && + L[2]->OPC == OP65_LDA && + !CodeEntryHasLabel (L[2]) && + L[3]->OPC == OP65_SBC && + strcmp (L[3]->Arg, "tmp1") == 0 && + !CodeEntryHasLabel (L[3]) && + L[4]->OPC == OP65_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, OP65_SBC); + + /* If the sequence head had a label, move this label back to the + * head. + */ + if (CodeEntryHasLabel (E)) { + MoveCodeLabels (S, E, L[0]); + } + + /* Remember, we had changes */ + ++Changes; + + } + + /* Next entry */ + ++I; + + } + + /* Return the number of changes made */ + return Changes; +} + + + +/*****************************************************************************/ +/* 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; + + /* 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 == OP65_ADC && + GetCodeEntries (S, L, I+1, 3) && + (L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) && + L[0]->JumpTo != 0 && + !CodeEntryHasLabel (L[0]) && + L[1]->OPC == OP65_INX && + !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; } /*****************************************************************************/ -/* Remove dead code */ +/* Optimizations for compares */ /*****************************************************************************/ -static void OptDeadCode (CodeSeg* S) -/* Remove dead code (code that follows an unconditional jump or an rts/rti - * and has no label) +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 == OP65_STX && + GetCodeEntries (S, L, I+1, 2) && + L[0]->OPC == OP65_STX && + strcmp (L[0]->Arg, "tmp1") == 0 && + !CodeEntryHasLabel (L[0]) && + L[1]->OPC == OP65_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 (OP65_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 == OP65_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 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 = CollAt (&S->Entries, I); - /* Check if it's an unconditional branch, and if the next entry has - * no labels attached - */ - if ((E->OPC == OPC_JMP || E->OPC == OPC_BRA || E->OPC == OPC_RTS || E->OPC == OPC_RTI) && - !CodeEntryHasLabel (CollAt (&S->Entries, I+1))) { - /* Delete the next entry */ - DelCodeSegLine (S, I+1); +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 == OP65_LDA && + GetCodeEntries (S, L, I+1, 5) && + L[0]->OPC == OP65_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], OP65_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], OP65_LDA); + ReplaceOPC (L[1], OP65_CMP); + + /* Beware: If the first LDA instruction had a label, we have + * to move this label to the top of the sequence again. + */ + if (CodeEntryHasLabel (E)) { + MoveCodeLabels (S, E, L[0]); + } - /* Keep the number of entries updated */ - --Count; + } - /* Remember, we had changes */ - ++OptChanges; + ++Changes; + } - } else { + /* 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], OP65_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], OP65_CMP); /* cpx -> cmp */ + MoveCodeEntry (S, I+4, I+2); /* cmp */ + MoveCodeEntry (S, I+5, I+3); /* bne */ - /* Next entry */ - ++I; + } + + ++Changes; + } + + /* Next entry */ + ++I; - } } + + /* Return the number of changes made */ + return Changes; +} + + + +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 == OP65_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 (OP65_JSR, AM65_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 */ + ++Changes; + + } + + /* Next entry */ + ++I; + + } + + /* Return the number of changes made */ + return Changes; } /*****************************************************************************/ -/* Optimize jump cascades */ +/* nega optimizations */ /*****************************************************************************/ -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 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 == OP65_LDX && + E->AM == AM65_IMM && + (E->Flags & CEF_NUMARG) != 0 && + E->Num == 0 && + GetCodeEntries (S, L, I+1, 2) && + L[0]->OPC == OP65_LDA && + (L[0]->Use & REG_X) == 0 && + L[1]->OPC == OP65_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 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; +} + + + +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]; - CodeLabel* OldLabel; - CodeLabel* NewLabel; + /* Get next entry */ + CodeEntry* E = GetCodeEntry (S, I); - /* Get this entry */ - CodeEntry* E = CollAt (&S->Entries, I); + /* Check for the sequence */ + if (E->OPC == OP65_LDA && + GetCodeEntries (S, L, I+1, 2) && + L[0]->OPC == OP65_JSR && + strcmp (L[0]->Arg, "bnega") == 0 && + !CodeEntryHasLabel (L[0]) && + (L[1]->Info & OF_ZBRA) != 0) { - /* Check if it's a branch, if it has a label attached, and if the - * instruction at this label is also a branch. - */ - if (E->AM == AM_BRA && - (OldLabel = E->JumpTo) != 0 && - OldLabel->Owner->AM == AM_BRA && - (NewLabel = OldLabel->Owner->JumpTo) != 0) { + /* Invert the branch */ + ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC)); - /* Get the instruction that has the new label attached */ - CodeEntry* N = OldLabel->Owner; + /* Delete the subroutine call */ + DelCodeEntry (S, I+1); - /* Remove the reference to our label and delete it if this was - * the last reference. + /* Remember, we had changes */ + ++Changes; + + } + + /* Next entry */ + ++I; + + } + + /* Return the number of changes made */ + return Changes; +} + + + +/*****************************************************************************/ +/* negax optimizations */ +/*****************************************************************************/ + + + +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 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 == OP65_LDA && + E->AM == AM65_ZP_INDY && + GetCodeEntries (S, L, I+1, 5) && + L[0]->OPC == OP65_TAX && + L[1]->OPC == OP65_DEY && + L[2]->OPC == OP65_LDA && + L[2]->AM == AM65_ZP_INDY && + strcmp (L[2]->Arg, E->Arg) == 0 && + !CodeEntryHasLabel (L[2]) && + L[3]->OPC == OP65_JSR && + strcmp (L[3]->Arg, "bnegax") == 0 && + !CodeEntryHasLabel (L[3]) && + (L[4]->Info & OF_ZBRA) != 0) { + + /* lda --> ora */ + ReplaceOPC (L[2], OP65_ORA); + + /* Invert the branch */ + ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC)); + + /* Delete the entries no longer needed. Beware: Deleting entries + * will change the indices. */ - if (RemoveLabelRef (OldLabel, E) == 0) { - /* Delete it */ - DelCodeLabel (S, OldLabel); + DelCodeEntry (S, I+4); /* jsr bnegax */ + DelCodeEntry (S, I+1); /* tax */ + + /* Remember, we had changes */ + ++Changes; + + } + + /* Next entry */ + ++I; + + } + + /* 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 == OP65_LDA && + GetCodeEntries (S, L, I+1, 3) && + L[0]->OPC == OP65_LDX && + !CodeEntryHasLabel (L[0]) && + L[1]->OPC == OP65_JSR && + strcmp (L[1]->Arg, "bnegax") == 0 && + !CodeEntryHasLabel (L[1]) && + (L[2]->Info & OF_ZBRA) != 0) { + + /* ldx --> ora */ + ReplaceOPC (L[0], OP65_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 + * + * 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 == OP65_JSR && + E->Arg[0] == '_' && + GetCodeEntries (S, L, I+1, 2) && + L[0]->OPC == OP65_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 (OP65_TAX, AM65_IMP, 0, 0, L[0]->LI); + InsertCodeEntry (S, X, I+2); + } else { + /* Test words */ + X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, L[0]->LI); + InsertCodeEntry (S, X, I+2); + X = NewCodeEntry (OP65_ORA, AM65_ZP, "tmp1", 0, L[0]->LI); + InsertCodeEntry (S, X, I+3); } - /* Remove usage information from the entry and use the usage - * information from the new instruction instead. - */ - E->Info &= ~(CI_MASK_USE | CI_MASK_CHG); - E->Info |= N->Info & ~(CI_MASK_USE | CI_MASK_CHG); + /* Delete the subroutine call */ + DelCodeEntry (S, I+1); - /* Use the new label */ - AddLabelRef (NewLabel, E); + /* Invert the branch */ + ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC)); - /* Remember ,we had changes */ - ++OptChanges; + /* Remember, we had changes */ + ++Changes; } @@ -230,46 +1235,169 @@ static void OptJumpCascades (CodeSeg* S) ++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 */ - }; + /* 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);