1 /*****************************************************************************/
5 /* Optimizer subroutines */
9 /* (C) 2001 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
53 /*****************************************************************************/
55 /*****************************************************************************/
59 /* Defines for the conditions in a compare */
74 /* Table with the compare suffixes */
75 static const char CmpSuffixTab [][4] = {
76 "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
79 /* Table used to invert a condition, indexed by condition */
80 static const unsigned char CmpInvertTab [] = {
82 CMP_LE, CMP_LT, CMP_GE, CMP_GT,
83 CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
86 /* Table to show which compares are signed (use the N flag) */
87 static const char CmpSignedTab [] = {
88 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
93 /*****************************************************************************/
94 /* Helper functions */
95 /*****************************************************************************/
99 static cmp_t FindCmpCond (const char* Suffix)
100 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
105 for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
106 if (strcmp (Suffix, CmpSuffixTab [I]) == 0) {
118 /*****************************************************************************/
119 /* Remove calls to the bool transformer subroutines */
120 /*****************************************************************************/
124 static unsigned OptBoolTransforms (CodeSeg* S)
125 /* Try to remove the call to boolean transformer routines where the call is
129 unsigned Changes = 0;
131 /* Walk over the entries */
133 while (I < GetCodeEntryCount (S)) {
139 CodeEntry* E = GetCodeEntry (S, I);
141 /* Check for a boolean transformer */
142 if (E->OPC == OPC_JSR &&
143 strncmp (E->Arg, "bool", 4) == 0 &&
144 (N = GetNextCodeEntry (S, I)) != 0 &&
145 (N->Info & OF_ZBRA) != 0 &&
146 (Cond = FindCmpCond (E->Arg+4)) != CMP_INV) {
151 /* Make the boolean transformer unnecessary by changing the
152 * the conditional jump to evaluate the condition flags that
153 * are set after the compare directly. Note: jeq jumps if
154 * the condition is not met, jne jumps if the condition is met.
155 * Invert the code if we jump on condition not met.
157 if (GetBranchCond (N->OPC) == BC_EQ) {
158 /* Jumps if condition false, invert condition */
159 Cond = CmpInvertTab [Cond];
162 /* Check if we can replace the code by something better */
166 ReplaceOPC (N, OPC_JEQ);
170 ReplaceOPC (N, OPC_JNE);
179 if ((X = GetNextCodeEntry (S, I+1)) == 0) {
183 L = GenCodeLabel (S, X);
184 X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
185 InsertCodeEntry (S, X, I+1);
186 ReplaceOPC (N, OPC_JPL);
190 ReplaceOPC (N, OPC_JPL);
194 ReplaceOPC (N, OPC_JMI);
202 ReplaceOPC (N, OPC_JMI);
204 X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
205 InsertCodeEntry (S, X, I+2);
214 if ((X = GetNextCodeEntry (S, I+1)) == 0) {
218 L = GenCodeLabel (S, X);
219 X = NewCodeEntry (OPC_BEQ, AM_BRA, L->Name, L);
220 InsertCodeEntry (S, X, I+1);
221 ReplaceOPC (N, OPC_JCS);
225 ReplaceOPC (N, OPC_JCS);
229 ReplaceOPC (N, OPC_JCC);
237 ReplaceOPC (N, OPC_JCC);
239 X = NewCodeEntry (OPC_JEQ, AM_BRA, L->Name, L);
240 InsertCodeEntry (S, X, I+2);
244 Internal ("Unknown jump condition: %d", Cond);
248 /* Remove the call to the bool transformer */
251 /* Remember, we had changes */
262 /* Return the number of changes made */
268 /*****************************************************************************/
269 /* nega optimizations */
270 /*****************************************************************************/
274 static unsigned OptNegA1 (CodeSeg* S)
281 * Remove the ldx if the lda does not use it.
284 unsigned Changes = 0;
286 /* Walk over the entries */
288 while (I < GetCodeEntryCount (S)) {
293 CodeEntry* E = GetCodeEntry (S, I);
295 /* Check for a ldx */
296 if (E->OPC == OPC_LDX &&
298 (E->Flags & CEF_NUMARG) != 0 &&
300 GetCodeEntries (S, L, I+1, 2) &&
301 L[0]->OPC == OPC_LDA &&
302 (L[0]->Use & REG_X) == 0 &&
303 L[1]->OPC == OPC_JSR &&
304 strcmp (L[1]->Arg, "bnega") == 0) {
306 /* Remove the ldx instruction */
309 /* Remember, we had changes */
319 /* Return the number of changes made */
325 static unsigned OptNegA2 (CodeSeg* S)
332 * Adjust the conditional branch and remove the call to the subroutine.
335 unsigned Changes = 0;
337 /* Walk over the entries */
339 while (I < GetCodeEntryCount (S)) {
344 CodeEntry* E = GetCodeEntry (S, I);
346 /* Check for the sequence */
347 if (E->OPC == OPC_LDA &&
348 GetCodeEntries (S, L, I+1, 2) &&
349 L[0]->OPC == OPC_JSR &&
350 strcmp (L[0]->Arg, "bnega") == 0 &&
351 !CodeEntryHasLabel (L[0]) &&
352 (L[1]->Info & OF_ZBRA) != 0) {
354 /* Invert the branch */
355 ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
357 /* Delete the subroutine call */
358 DelCodeEntry (S, I+1);
360 /* Remember, we had changes */
370 /* Return the number of changes made */
376 /*****************************************************************************/
377 /* negax optimizations */
378 /*****************************************************************************/
382 static unsigned OptNegAX1 (CodeSeg* S)
383 /* Search for the sequence:
400 unsigned Changes = 0;
402 /* Walk over the entries */
404 while (I < GetCodeEntryCount (S)) {
409 CodeEntry* E = GetCodeEntry (S, I);
411 /* Check for the sequence */
412 if (E->OPC == OPC_LDA &&
413 E->AM == AM_ZP_INDY &&
414 GetCodeEntries (S, L, I+1, 5) &&
415 L[0]->OPC == OPC_TAX &&
416 L[1]->OPC == OPC_DEY &&
417 L[2]->OPC == OPC_LDA &&
418 L[2]->AM == AM_ZP_INDY &&
419 strcmp (L[2]->Arg, E->Arg) == 0 &&
420 !CodeEntryHasLabel (L[2]) &&
421 L[3]->OPC == OPC_JSR &&
422 strcmp (L[3]->Arg, "bnegax") == 0 &&
423 !CodeEntryHasLabel (L[3]) &&
424 (L[4]->Info & OF_ZBRA) != 0) {
427 ReplaceOPC (L[2], OPC_ORA);
429 /* Invert the branch */
430 ReplaceOPC (L[4], GetInverseBranch (L[4]->OPC));
432 /* Delete the entries no longer needed. Beware: Deleting entries
433 * will change the indices.
435 DelCodeEntry (S, I+4); /* jsr bnegax */
436 DelCodeEntry (S, I+1); /* tax */
438 /* Remember, we had changes */
448 /* Return the number of changes made */
454 static unsigned OptNegAX2 (CodeSeg* S)
455 /* Search for the sequence:
469 unsigned Changes = 0;
471 /* Walk over the entries */
473 while (I < GetCodeEntryCount (S)) {
478 CodeEntry* E = GetCodeEntry (S, I);
480 /* Check for the sequence */
481 if (E->OPC == OPC_LDA &&
482 GetCodeEntries (S, L, I+1, 3) &&
483 L[0]->OPC == OPC_LDX &&
484 !CodeEntryHasLabel (L[0]) &&
485 L[1]->OPC == OPC_JSR &&
486 strcmp (L[1]->Arg, "bnegax") == 0 &&
487 !CodeEntryHasLabel (L[1]) &&
488 (L[2]->Info & OF_ZBRA) != 0) {
491 ReplaceOPC (L[0], OPC_ORA);
493 /* Invert the branch */
494 ReplaceOPC (L[2], GetInverseBranch (L[2]->OPC));
496 /* Delete the subroutine call */
497 DelCodeEntry (S, I+2);
499 /* Remember, we had changes */
509 /* Return the number of changes made */
515 static unsigned OptNegAX3 (CodeSeg* S)
516 /* Search for the sequence:
529 unsigned Changes = 0;
531 /* Walk over the entries */
533 while (I < GetCodeEntryCount (S)) {
538 CodeEntry* E = GetCodeEntry (S, I);
540 /* Check for the sequence */
541 if (E->OPC == OPC_JSR &&
543 GetCodeEntries (S, L, I+1, 2) &&
544 L[0]->OPC == OPC_JSR &&
545 strncmp (L[0]->Arg,"bnega",5) == 0 &&
546 !CodeEntryHasLabel (L[0]) &&
547 (L[1]->Info & OF_ZBRA) != 0) {
549 /* Check if we're calling bnega or bnegax */
550 int ByteSized = (strcmp (L[0]->Arg, "bnega") == 0);
552 /* Delete the subroutine call */
553 DelCodeEntry (S, I+1);
555 /* Insert apropriate test code */
558 InsertCodeEntry (S, NewCodeEntry (OPC_TAX, AM_IMP, 0, 0), I+1);
561 InsertCodeEntry (S, NewCodeEntry (OPC_STX, AM_ZP, "tmp1", 0), I+1);
562 InsertCodeEntry (S, NewCodeEntry (OPC_ORA, AM_ZP, "tmp1", 0), I+2);
565 /* Invert the branch */
566 ReplaceOPC (L[1], GetInverseBranch (L[1]->OPC));
568 /* Remember, we had changes */
578 /* Return the number of changes made */
584 /*****************************************************************************/
586 /*****************************************************************************/
590 /* Table with all the optimization functions */
591 typedef struct OptFunc OptFunc;
593 unsigned (*Func) (CodeSeg*);/* Optimizer function */
594 const char* Name; /* Name of optimizer step */
595 char Disabled; /* True if pass disabled */
600 /* Table with optimizer steps - are called in this order */
601 static OptFunc OptFuncs [] = {
602 /* Optimize jump cascades */
603 { OptJumpCascades, "OptJumpCascades", 0 },
604 /* Remove dead jumps */
605 { OptDeadJumps, "OptDeadJumps", 0 },
606 /* Change jsr/rts to jmp */
607 { OptRTS, "OptRTS", 0 },
608 /* Remove dead code */
609 { OptDeadCode, "OptDeadCode", 0 },
610 /* Optimize jump targets */
611 { OptJumpTarget, "OptJumpTarget", 0 },
612 /* Optimize conditional branches */
613 { OptCondBranches, "OptCondBranches", 0 },
614 /* Replace jumps to RTS by RTS */
615 { OptRTSJumps, "OptRTSJumps", 0 },
616 /* Remove calls to the bool transformer subroutines */
617 { OptBoolTransforms, "OptBoolTransforms", 0 },
618 /* Optimize calls to nega */
619 { OptNegA1, "OptNegA1", 0 },
620 /* Optimize calls to nega */
621 { OptNegA2, "OptNegA2", 0 },
622 /* Optimize calls to negax */
623 { OptNegAX1, "OptNegAX1", 0 },
624 /* Optimize calls to negax */
625 { OptNegAX2, "OptNegAX2", 0 },
626 /* Optimize calls to negax */
627 { OptNegAX3, "OptNegAX3", 0 },
628 /* Remove unused loads */
629 { OptUnusedLoads, "OptUnusedLoads", 0 },
630 /* Optimize branch distance */
631 { OptBranchDist, "OptBranchDist", 0 },
636 static OptFunc* FindOptStep (const char* Name)
637 /* Find an optimizer step by name in the table and return a pointer. Print an
638 * error and call AbEnd if not found.
643 /* Run all optimization steps */
644 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
645 if (strcmp (OptFuncs[I].Name, Name) == 0) {
652 AbEnd ("Optimization step `%s' not found", Name);
658 void DisableOpt (const char* Name)
659 /* Disable the optimization with the given name */
661 OptFunc* F = FindOptStep (Name);
667 void EnableOpt (const char* Name)
668 /* Enable the optimization with the given name */
670 OptFunc* F = FindOptStep (Name);
676 void RunOpt (CodeSeg* S)
677 /* Run the optimizer */
683 /* If we shouldn't run the optimizer, bail out */
688 /* Print the name of the function we are working on */
690 Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
692 Print (stdout, 1, "Running optimizer for global code segment\n");
695 /* Repeat all steps until there are no more changes */
697 /* Reset the number of changes */
700 /* Keep the user hapy */
701 Print (stdout, 1, " Optimizer pass %u:\n", ++Pass);
703 /* Run all optimization steps */
704 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
706 /* Print the name of the following optimizer step */
707 Print (stdout, 1, " %s:%*s", OptFuncs[I].Name,
708 (int) (30-strlen(OptFuncs[I].Name)), "");
710 /* Check if the step is disabled */
711 if (OptFuncs[I].Disabled) {
712 Print (stdout, 1, "Disabled\n");
714 unsigned Changes = OptFuncs[I].Func (S);
715 OptChanges += Changes;
716 Print (stdout, 1, "%u Changes\n", Changes);
720 } while (OptChanges > 0);