From cefb4c067d69c9a68754ba965f82c12b96a58d5c Mon Sep 17 00:00:00 2001 From: cuz Date: Wed, 22 Nov 2000 21:39:56 +0000 Subject: [PATCH] Added optimizations for commutative arithmetic ops git-svn-id: svn://svn.cc65.org/cc65/trunk@469 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- src/cc65/optimize.c | 318 ++++++++++++++++++++++++++++---------------- 1 file changed, 207 insertions(+), 111 deletions(-) diff --git a/src/cc65/optimize.c b/src/cc65/optimize.c index c9890a244..e24160658 100644 --- a/src/cc65/optimize.c +++ b/src/cc65/optimize.c @@ -177,6 +177,8 @@ static const struct { { "\tstz\t", 0, REG_NONE, REG_NONE }, { "\ttax", 1, REG_A, REG_X }, { "\ttay", 1, REG_A, REG_Y }, + { "\ttrb\t", 0, REG_A, REG_NONE }, + { "\ttsb\t", 0, REG_A, REG_NONE }, { "\ttsx", 1, REG_NONE, REG_X }, { "\ttxa", 1, REG_X, REG_A }, { "\ttya", 1, REG_Y, REG_A }, @@ -1754,20 +1756,20 @@ static void OptRegLoads (void) /* Search for a load of X and check if the value is used later */ if (LineMatch (L, "\tldx\t") && - !RegXUsed (L) && - !IsCondJump (NextInstruction (L))) { + !RegXUsed (L) && + !IsCondJump (NextInstruction (L))) { - /* Remember to delete this line */ - Delete = 1; + /* Remember to delete this line */ + Delete = 1; } /* Search for a load of A and check if the value is used later */ else if (LineMatch (L, "\tlda\t") && - !RegAUsed (L) && - !IsCondJump (NextInstruction (L))) { + !RegAUsed (L) && + !IsCondJump (NextInstruction (L))) { - /* Remember to delete this line */ - Delete = 1; + /* Remember to delete this line */ + Delete = 1; } /* Search for a load of Y and check if the value is used later */ @@ -1775,16 +1777,16 @@ static void OptRegLoads (void) !RegYUsed (L) && !IsCondJump (NextInstruction (L))) { - /* Remember to delete this line */ - Delete = 1; + /* Remember to delete this line */ + Delete = 1; } /* Go to the next line, delete the current if requested */ Lx = L; L = NextCodeLine (L); if (Delete) { - FreeLine (Lx); - ++Deletions; + FreeLine (Lx); + ++Deletions; } } } while (Deletions > 0); @@ -1932,7 +1934,7 @@ static int OptPtrOps1 (Line** Start) /* Store to pointer */ L = ReplaceLine (L, L3[5]->Line); - L = NewLineAfter (L, "\tldy\t#$00"); + L = NewLineAfter (L, "\tldy\t#$00"); L = NewLineAfter (L, "\tsta\t(%s),y", Reg); L = NewLineAfter (L, "\tinc\t%s", Reg); L = NewLineAfter (L, "\tbne\t*+4"); @@ -2197,7 +2199,7 @@ static int OptPtrOps2 (Line** Start) L = NewLineAfter (L, "\tlda\t(ptr1,x)"); NeedLoad = 0; ++LinesToRemove; - } else if (LineFullMatch (L3[1], "\tsta\tptr1") && + } else if (LineFullMatch (L3[1], "\tsta\tptr1") && GetNextCodeLines (L3[1], &L3[2], 3) && LineFullMatch (L3[2], "\tstx\tptr1+1") && LineFullMatch (L3[3], "\tldx\t#$00") && @@ -2627,7 +2629,7 @@ static void OptPtrOps (void) else if (LineMatch (L, "\tldy\t#$") && GetNextCodeLines (L, L2, 6) && LineFullMatch (L2 [0], "\tlda\t(sp),y") && - LineFullMatch (L2 [1], "\ttax") && + LineFullMatch (L2 [1], "\ttax") && LineFullMatch (L2 [2], "\tdey") && LineFullMatch (L2 [3], "\tlda\t(sp),y") && LineMatch (L2 [4], "\tldy\t#$") && @@ -2782,7 +2784,7 @@ static void OptRegVars (void) * lda regbank+n * ldx regbank+n+1 * ldy #$.. - * jsr ldauidx + * jsr ldauidx * * and replace it by: * @@ -2868,7 +2870,7 @@ static void OptRegVars (void) * * ldy #$mm * lda (sp),y - * ldy #$ll + * ldy #$ll * sta (regbank+n),y * * The source form is not generated by the parser but by the optimizer. @@ -2954,7 +2956,7 @@ static void OptDoubleJumps (void) if ((D = GetJumpDistance (L, FinalTarget)) >= 123) { break; } - } + } /* Make sure the jump does indeed point to another label. * It may happen that this is not the case for some endless @@ -3186,7 +3188,7 @@ static void OptCompares2 (void) * jne/jeq ... */ else if (LineMatch (L, "\tldy\t#$") && - GetNextCodeLines (L, L2, 8) && + GetNextCodeLines (L, L2, 8) && LineFullMatch (L2[0], "\tlda\t(sp),y") && LineFullMatch (L2[1], "\ttax") && LineFullMatch (L2[2], "\tdey") && @@ -3304,7 +3306,7 @@ static void OptTests (void) { Line* L2 [2]; - const char* BitOps [] = { + static const char* BitOps [] = { "\tand\t", "\tora\t", "\teor\t", @@ -3323,7 +3325,7 @@ static void OptTests (void) /* Search for lda/tay/jne or lda/tay/jeq, remove the tay. * Search for - * lda/and/ora/eor + * lda/and/ora/eor * cmp #$00 * jne/jeq ... * Remove the cmp. @@ -3401,6 +3403,127 @@ static void OptTests (void) +static void OptBitOps (void) +/* Optimize bit oeprations */ +{ + Line* L2 [2]; + + /* Walk over the code */ + Line* L = FirstCode; + while (L) { + + /* Search for + * + * lda xxx + * and #$yy ; adc/eor/ora + * sta xxx + * + * and replace it by + * + * lda #$yy + * and xxx + * sta xxx + * + * While this saves nothing here, it transforms the code to contain an + * explicit register load that may be removed by the basic block + * optimization later. As a special optimization for the 65C02, the + * "ora" and "and" ops may be replaced by "trb" and "tsb" resp. if the + * value in A is not used later. + */ + if (LineMatch (L, "\tlda\t") && + L->Line[5] != '#' && + GetNextCodeLines (L, L2, 2) && + LineMatch (L2[1], "\tsta\t") && + strcmp (L->Line+5, L2[1]->Line+5) == 0) { + + if (LineMatch (L2[0], "\tand\t#$")) { + + unsigned Val = GetHexNum (L2[0]->Line+7); + if (Val == 0x00) { + + /* AND with 0x00, remove the mem access */ + FreeLine (L); + FreeLine (L2[1]); + + /* Replace the AND by a load */ + L = ReplaceLine (L2[0], "\tlda\t#$%02X", Val); + + } else if (Val == 0xFF) { + + /* AND with 0xFF, just load the value from memory */ + FreeLines (L2[0], L2[1]); + + } else if (CPU == CPU_65C02 && + !IsXAddrMode (L) && + !IsYAddrMode (L) && + !RegAUsed (L2[1])) { + + /* Replace by trb */ + ReplaceLine (L, "\tlda\t#$%02X", (~Val) & 0xFF); + ReplaceLine (L2[0], "\ttrb\t%s", L2[1]->Line+5); + FreeLine (L2[1]); + L = L2[0]; + + } else { + + /* Just reorder */ + L = ReplaceLine (L, "\tlda\t#$%02X", Val); + ReplaceLine (L2[0], "\tand\t%s", L2[1]->Line+5); + L = L2[1]; + + } + + } else if (LineMatch (L2[0], "\tora\t#$")) { + + unsigned Val = GetHexNum (L2[0]->Line+7); + if (Val == 0x00) { + + /* ORA with 0x00, just load the value from memory */ + FreeLines (L2[0], L2[1]); + + } else if (Val == 0xFF) { + + /* ORA with 0xFF, replace by a store of $FF */ + FreeLine (L); + ReplaceLine (L2[0], "\tlda\t#$FF"); + + } else if (CPU == CPU_65C02 && + !IsXAddrMode (L) && + !IsYAddrMode (L) && + !RegAUsed (L2[1])) { + + /* Replace by trb */ + ReplaceLine (L, "\tlda\t#$%02X", Val); + ReplaceLine (L2[0], "\ttsb\t%s", L2[1]->Line+5); + FreeLine (L2[1]); + L = L2[0]; + + } else { + + /* Just reorder */ + L = ReplaceLine (L, "\tlda\t#$%02X", Val); + ReplaceLine (L2[0], "\tora\t%s", L2[1]->Line+5); + L = L2[1]; + + } + + } else if (LineMatch (L2[0], "\teor\t#$") || + LineMatch (L2[0], "\tadc\t#$")) { + + /* Just reorder */ + L = ReplaceLine (L, "\tlda\t%s", L2[0]->Line+5); + ReplaceLine (L2[0], "\t%.3s\t%s", L2[0]->Line+1, L2[1]->Line+5); + + } + } + + /* Next line */ + L = NextCodeLine (L); + } +} + + + static void OptNeg (void) /* Optimize the "bnegax/jeq" and "bnegax/jne" sequences */ { @@ -3642,7 +3765,7 @@ static Line* OptOneBlock (Line* L) } } else if (LineMatch (L, "\tadc\t")) { if (CPU == CPU_65C02 && Y == 0 && L->Line[5] == '(' && IsYAddrMode(L)) { - L->Line[strlen(L->Line)-2] = '\0'; + L->Line[strlen(L->Line)-2] = '\0'; } A = -1; } else if (LineMatch (L, "\tand\t")) { @@ -3873,7 +3996,7 @@ static Line* OptOneBlock (Line* L) * cycles. */ if (X == 0) { - L = ReplaceLine (L, "\tjsr\tpushax"); + L = ReplaceLine (L, "\tjsr\tpushax"); } X = 0; Y = 1; @@ -3986,7 +4109,7 @@ static Line* OptOneBlock (Line* L) /* lda (zp,x) - if Y and X are both zero, replace by * load indirect y and save one cycle in some cases. */ - if (X == 0 && Y == 0) { + if (X == 0 && Y == 0) { char Buf [256]; const char* S = L->Line + 6; char* T = Buf + 6; @@ -4002,10 +4125,10 @@ static Line* OptOneBlock (Line* L) } } /* In any case invalidate A */ - A = -1; + A = -1; } else if (LineMatch (L, "\tlda\t#$")) { /* Immidiate load into A */ - NewVal = GetHexNum (L->Line + 7); + NewVal = GetHexNum (L->Line + 7); if (NewVal == A) { /* Load has no effect */ Delete = 1; @@ -4045,10 +4168,10 @@ static Line* OptOneBlock (Line* L) } else if (NewVal == A) { /* Requested value is already in A */ L = ReplaceLine (L, "\ttax"); - } else if (X != -1 && NewVal == ((X + 1) & 0xFF)) { + } else if (X != -1 && NewVal == ((X + 1) & 0xFF)) { /* Requested value is one more than current contents */ L = ReplaceLine (L, "\tinx"); - } else if (X != -1 && NewVal == ((X - 1) & 0xFF)) { + } else if (X != -1 && NewVal == ((X - 1) & 0xFF)) { /* Requested value is one less than current contents */ L = ReplaceLine (L, "\tdex"); } @@ -4072,7 +4195,7 @@ static Line* OptOneBlock (Line* L) /* Requested value is already in A */ L = ReplaceLine (L, "\ttay"); } else if (Y != -1 && NewVal == ((Y + 1) & 0xFF)) { - /* Requested value is one more than current contents */ + /* Requested value is one more than current contents */ L = ReplaceLine (L, "\tiny"); } else if (Y != -1 && NewVal == ((Y - 1) & 0xFF)) { /* Requested value is one less than current contents */ @@ -4106,36 +4229,36 @@ static Line* OptOneBlock (Line* L) A = X = Y = -1; } else if (LineMatch (L, "\tsbc\t")) { if (CPU == CPU_65C02 && Y == 0 && L->Line[5] == '(' && IsYAddrMode(L)) { - L->Line[strlen(L->Line)-2] = '\0'; + L->Line[strlen(L->Line)-2] = '\0'; } A = -1; } else if (CPU == CPU_65C02 && LineMatch (L, "\tst")) { /* Try to replace by stz if possible */ if (A == 0 && LineMatch (L, "\tsta\t")) { - /* Not indirect and not Y allowed */ - if (L->Line[5] != '(' && !IsYAddrMode (L)) { - L->Line[3] = 'z'; - } + /* Not indirect and not Y allowed */ + if (L->Line[5] != '(' && !IsYAddrMode (L)) { + L->Line[3] = 'z'; + } } else if (X == 0 && LineMatch (L, "\tstx\t")) { - /* absolute,y not allowed */ - if (!IsYAddrMode (L)) { - L->Line[3] = 'z'; - } + /* absolute,y not allowed */ + if (!IsYAddrMode (L)) { + L->Line[3] = 'z'; + } } else if (Y == 0 && LineMatch (L, "\tsty\t")) { - /* sty and stz share all addressing modes */ - L->Line[3] = 'z'; + /* sty and stz share all addressing modes */ + L->Line[3] = 'z'; } } else if (LineFullMatch (L, "\ttax")) { if (A != -1 && X == A) { - /* Load has no effect */ - Delete = 1; + /* Load has no effect */ + Delete = 1; } else { X = A; } } else if (LineFullMatch (L, "\ttay")) { if (A != -1 && Y == A) { - /* Load has no effect */ - Delete = 1; + /* Load has no effect */ + Delete = 1; } else { Y = A; } @@ -4143,15 +4266,15 @@ static Line* OptOneBlock (Line* L) X = -1; } else if (LineFullMatch (L, "\ttxa")) { if (X != -1 && A == X) { - /* Load has no effect */ - Delete = 1; + /* Load has no effect */ + Delete = 1; } else { A = X; } } else if (LineFullMatch (L, "\ttya")) { if (Y != -1 && A == Y) { - /* Load has no effect */ - Delete = 1; + /* Load has no effect */ + Delete = 1; } else { A = Y; } @@ -4268,21 +4391,37 @@ static void OptRTS (void) -static void OptOnePass (unsigned long Flag, void (*F) (void)) -/* Call one optimizer pass if enabled */ -{ - if ((OptDisable & Flag) == 0) { - F (); - } else if (Verbose || Debug) { - printf ("Optimizer pass %04lX skipped\n", Flag); - } -} - - - void OptDoOpt (void) /* Run the optimizer over the collected stuff */ { + typedef void (*OptFunc)(void); + + /* Table with optimizer steps - are called in this order */ + static const OptFunc OptFuncs [] = { + OptCompares1, /* Optimize compares - first step */ + OptDeadJumps, /* Remove dead jumps */ + OptLoads, /* Remove unnecessary loads */ + OptRegLoads, /* Remove unnecessary register loads */ + OptPtrOps, /* Optimize stores through pointers */ + OptRegVars, /* Optimize use of register variables */ + OptDoubleJumps, /* Remove jump cascades - must be used before OptNeg */ + OptNeg, /* Remove unnecessary boolean negates */ + OptJumpRTS, /* Replace jumps to an RTS by an RTS */ + OptBoolTransforms, /* Optimize boolean transforms */ + OptCompares2, /* Optimize compares */ + OptTests, /* Remove unnecessary tests */ + OptBitOps, /* Optimize bit operations */ + OptTriples, /* Optimize several triples */ + OptBlocks, /* Optimize basic blocks */ + OptRegLoads, /* Remove unnecessary register loads (another pass) */ + OptBlocks, /* Optimize basic blocks */ + OptJumps, /* Optimize jumps */ + OptRTS, /* Optimize jsr/rts sequences */ + }; + + unsigned long Flags; + unsigned I; + /* Find and remember the first line of code */ FindCodeStart (); @@ -4293,57 +4432,14 @@ void OptDoOpt (void) CreateLabelList (); /* Ok, now start the real optimizations */ - - /* Optimize compares - first step */ - OptOnePass (0x0001, OptCompares1); - - /* Remove dead jumps */ - OptOnePass (0x0002, OptDeadJumps); - - /* Remove unnecessary loads */ - OptOnePass (0x0004, OptLoads); - - /* Remove unnecessary register loads */ - OptOnePass (0x0008, OptRegLoads); - - /* Optimize stores through pointers */ - OptOnePass (0x0010, OptPtrOps); - - /* Optimize use of register variables */ - OptOnePass (0x0020, OptRegVars); - - /* Remove jump cascades - must be used before OptNeg */ - OptOnePass (0x0040, OptDoubleJumps); - - /* Remove unnecessary boolean negates */ - OptOnePass (0x0080, OptNeg); - - /* Replace jumps to an RTS by an RTS */ - OptOnePass (0x0100, OptJumpRTS); - - /* Optimize boolean transforms */ - OptOnePass (0x0200, OptBoolTransforms); - - /* Optimize compares */ - OptOnePass (0x0400, OptCompares2); - - /* Remove unnecessary tests */ - OptOnePass (0x0800, OptTests); - - /* Optimize several triples */ - OptOnePass (0x1000, OptTriples); - - /* Optimize basic blocks */ - OptOnePass (0x2000, OptBlocks); - - /* Remove unnecessary register loads (another pass) */ - OptOnePass (0x0008, OptRegLoads); - - /* Optimize jumps */ - OptOnePass (0x4000, OptJumps); - - /* Optimize jsr/rts sequences */ - OptOnePass (0x8000, OptRTS); + Flags = 1UL; + for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) { + if ((OptDisable & Flags) == 0) { + OptFuncs[I] (); + } else if (Verbose || Debug) { + printf ("Optimizer pass %u skipped\n", I); + } + } } -- 2.39.5