1 /*****************************************************************************/
5 /* Optimize operations that take operands via the stack */
9 /* (C) 2001-2002 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 /*****************************************************************************/
47 /*****************************************************************************/
49 /*****************************************************************************/
53 /* Structure that holds the needed data */
54 typedef struct StackOpData StackOpData;
56 CodeSeg* Code; /* Pointer to code segment */
57 unsigned Flags; /* Flags to remember things */
58 unsigned PushIndex; /* Index of call to pushax in codeseg */
59 unsigned OpIndex; /* Index of actual operation */
60 CodeEntry* PrevEntry; /* Entry before the call to pushax */
61 CodeEntry* PushEntry; /* Pointer to entry with call to pushax */
62 CodeEntry* OpEntry; /* Pointer to entry with op */
63 CodeEntry* NextEntry; /* Entry after the op */
64 const char* ZPLo; /* Lo byte of zero page loc to use */
65 const char* ZPHi; /* Hi byte of zero page loc to use */
66 unsigned IP; /* Insertion point used by some routines */
69 /* Flags returned by DirectOp */
70 #define OP_DIRECT 0x01 /* Direct op may be used */
71 #define OP_ONSTACK 0x02 /* Operand is on stack */
75 /*****************************************************************************/
77 /*****************************************************************************/
81 static unsigned AdjustStackOffset (CodeSeg* S, unsigned Start, unsigned Stop,
83 /* Adjust the offset for all stack accesses in the range Start to Stop, both
84 * inclusive. The function returns the number of instructions that have been
88 /* Number of inserted instructions */
89 unsigned Inserted = 0;
91 /* Walk over all entries */
95 CodeEntry* E = CS_GetEntry (S, I);
97 if (E->Use & REG_SP) {
101 /* Check for some things that should not happen */
102 CHECK (E->AM == AM65_ZP_INDY || E->RI->In.RegY >= (short) Offs);
103 CHECK (strcmp (E->Arg, "sp") == 0);
105 /* Get the code entry before this one. If it's a LDY, adjust the
108 P = CS_GetPrevEntry (S, I);
109 if (P && P->OPC == OP65_LDY && CE_KnownImm (P)) {
111 /* The Y load is just before the stack access, adjust it */
112 CE_SetNumArg (P, P->Num - Offs);
116 /* Insert a new load instruction before the stack access */
117 const char* Arg = MakeHexArg (E->RI->In.RegY - Offs);
118 CodeEntry* X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, E->LI);
119 CS_InsertEntry (S, X, I);
121 /* One more inserted entries */
125 /* Be sure to skip the stack access for the next round */
136 /* Return the number of inserted entries */
142 static void InsertEntry (StackOpData* D, CodeEntry* E, unsigned Index)
143 /* Insert a new entry. Depending on Index, D->PushIndex and D->OpIndex will
144 * be adjusted by this function.
147 /* Insert the entry into the code segment */
148 CS_InsertEntry (D->Code, E, Index);
150 /* Adjust the indices if necessary */
151 if (D->PushEntry && Index <= D->PushIndex) {
154 if (D->OpEntry && Index <= D->OpIndex) {
161 static void DelEntry (StackOpData* D, unsigned Index)
162 /* Delete an entry. Depending on Index, D->PushIndex and D->OpIndex will be
163 * adjusted by this function, and PushEntry/OpEntry may get invalidated.
166 /* Delete the entry from the code segment */
167 CS_DelEntry (D->Code, Index);
169 /* Adjust the indices if necessary */
170 if (Index < D->PushIndex) {
172 } else if (Index == D->PushIndex) {
175 if (Index < D->OpIndex) {
177 } else if (Index == D->OpIndex) {
184 static void CheckDirectOp (StackOpData* D)
185 /* Check if the given entry is a lda instruction with an addressing mode
186 * that allows us to replace it by another operation (like ora). If so, we may
187 * use this location for the or and must not save the value in the zero
191 /* We need the entry before the push */
193 CHECK ((E = D->PrevEntry) != 0);
195 if (E->OPC == OP65_LDA) {
196 if (E->AM == AM65_IMM || E->AM == AM65_ZP || E->AM == AM65_ABS) {
197 /* These insns are all ok and replaceable */
198 D->Flags |= OP_DIRECT;
199 } else if (E->AM == AM65_ZP_INDY &&
200 E->RI->In.RegY >= 0 &&
201 (E->Use & REG_SP) != 0) {
202 /* Load from stack with known offset is also ok */
203 D->Flags |= (OP_DIRECT | OP_ONSTACK);
210 static void ReplacePushByStore (StackOpData* D)
211 /* Replace the call to the push subroutine by a store into the zero page
212 * location (actually, the push is not replaced, because we need it for
213 * later, but the name is still ok since the push will get removed at the
214 * end of each routine.
219 /* Store the value into the zeropage instead of pushing it */
220 X = NewCodeEntry (OP65_STX, AM65_ZP, D->ZPHi, 0, D->PushEntry->LI);
221 InsertEntry (D, X, D->PushIndex+1);
222 if ((D->Flags & OP_DIRECT) == 0) {
223 X = NewCodeEntry (OP65_STA, AM65_ZP, D->ZPLo, 0, D->PushEntry->LI);
224 InsertEntry (D, X, D->PushIndex+1);
230 static void AddOpLow (StackOpData* D, opc_t OPC)
231 /* Add an op for the low byte of an operator. This function honours the
232 * OP_DIRECT and OP_ONSTACK flags and generates the necessary instructions.
233 * All code is inserted at the current insertion point.
238 if ((D->Flags & OP_DIRECT) != 0) {
239 /* Op with a variable location. If the location is on the stack, we
240 * need to reload the Y register.
242 if ((D->Flags & OP_ONSTACK) != 0) {
243 const char* Arg = MakeHexArg (D->PrevEntry->RI->In.RegY);
244 X = NewCodeEntry (OP65_LDY, AM65_IMM, Arg, 0, D->OpEntry->LI);
245 InsertEntry (D, X, D->IP++);
247 X = NewCodeEntry (OPC, D->PrevEntry->AM, D->PrevEntry->Arg, 0, D->OpEntry->LI);
249 /* Op with temp storage */
250 X = NewCodeEntry (OPC, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
252 InsertEntry (D, X, D->IP++);
257 static void AddOpHigh (StackOpData* D, opc_t OPC)
258 /* Add an op for the high byte of an operator. Special cases (constant values
259 * or similar have to be checked separately, the function covers only the
260 * generic case. Code is inserted at the insertion point.
265 /* High byte is unknown */
266 X = NewCodeEntry (OP65_STA, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
267 InsertEntry (D, X, D->IP++);
268 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
269 InsertEntry (D, X, D->IP++);
270 X = NewCodeEntry (OPC, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
271 InsertEntry (D, X, D->IP++);
272 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, D->OpEntry->LI);
273 InsertEntry (D, X, D->IP++);
274 X = NewCodeEntry (OP65_LDA, AM65_ZP, D->ZPLo, 0, D->OpEntry->LI);
275 InsertEntry (D, X, D->IP++);
280 static void RemovePushAndOp (StackOpData* D)
281 /* Remove the call to pushax and the call to the operator subroutine */
283 DelEntry (D, D->OpIndex);
284 DelEntry (D, D->PushIndex);
289 /*****************************************************************************/
290 /* Actual optimization functions */
291 /*****************************************************************************/
295 static unsigned Opt_staspidx (StackOpData* D)
296 /* Optimize the staspidx sequence if possible */
300 /* Store the value into the zeropage instead of pushing it */
301 ReplacePushByStore (D);
303 /* Replace the store subroutine call by a direct op */
304 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
305 InsertEntry (D, X, D->OpIndex+1);
307 /* Remove the push and the call to the staspidx function */
310 /* We changed the sequence */
316 static unsigned Opt_staxspidx (StackOpData* D)
317 /* Optimize the staxspidx sequence if possible */
321 /* Store the value into the zeropage instead of pushing it */
322 ReplacePushByStore (D);
324 /* Inline the store */
325 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
326 InsertEntry (D, X, D->OpIndex+1);
327 X = NewCodeEntry (OP65_INY, AM65_IMP, 0, 0, D->OpEntry->LI);
328 InsertEntry (D, X, D->OpIndex+2);
329 if (D->OpEntry->RI->In.RegX >= 0) {
330 /* Value of X is known */
331 const char* Arg = MakeHexArg (D->OpEntry->RI->In.RegX);
332 X = NewCodeEntry (OP65_LDA, AM65_IMM, Arg, 0, D->OpEntry->LI);
335 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, D->OpEntry->LI);
337 InsertEntry (D, X, D->OpIndex+3);
338 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, D->ZPLo, 0, D->OpEntry->LI);
339 InsertEntry (D, X, D->OpIndex+4);
341 /* Remove the push and the call to the staspidx function */
344 /* We changed the sequence */
350 static unsigned Opt_tosaddax (StackOpData* D)
351 /* Optimize the tosaddax sequence if possible */
356 /* We need the entry behind the add */
357 CHECK (D->NextEntry != 0);
359 /* Check the entry before the push. If it's a lda instruction with an
360 * addressing mode that allows us to replace it, we may use this
361 * location for the op and must not save the value in the zero page
366 /* Store the value into the zeropage instead of pushing it */
367 ReplacePushByStore (D);
370 D->IP = D->OpIndex+1;
371 X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, D->OpEntry->LI);
372 InsertEntry (D, X, D->IP++);
375 AddOpLow (D, OP65_ADC);
378 if (D->PushEntry->RI->In.RegX == 0) {
379 /* The high byte is the value in X plus the carry */
380 CodeLabel* L = CS_GenLabel (D->Code, D->NextEntry);
381 X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
382 InsertEntry (D, X, D->IP++);
383 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
384 InsertEntry (D, X, D->IP++);
385 } else if (D->OpEntry->RI->In.RegX == 0) {
386 /* The high byte is that of the first operand plus carry */
388 if (D->PushEntry->RI->In.RegX >= 0) {
389 /* Value of first op high byte is known */
390 const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX);
391 X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
393 /* Value of first op high byte is unknown */
394 X = NewCodeEntry (OP65_LDX, AM65_ZP, D->ZPHi, 0, D->OpEntry->LI);
396 InsertEntry (D, X, D->IP++);
397 L = CS_GenLabel (D->Code, D->NextEntry);
398 X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, D->OpEntry->LI);
399 InsertEntry (D, X, D->IP++);
400 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, D->OpEntry->LI);
401 InsertEntry (D, X, D->IP++);
403 /* High byte is unknown */
404 AddOpHigh (D, OP65_ADC);
407 /* Remove the push and the call to the tosaddax function */
410 /* We changed the sequence */
416 static unsigned Opt_tosandax (StackOpData* D)
417 /* Optimize the tosandax sequence if possible */
421 /* Check the entry before the push. If it's a lda instruction with an
422 * addressing mode that allows us to replace it, we may use this
423 * location for the op and must not save the value in the zero page
428 /* Store the value into the zeropage instead of pushing it */
429 ReplacePushByStore (D);
431 /* Inline the and, low byte */
432 D->IP = D->OpIndex + 1;
433 AddOpLow (D, OP65_AND);
436 if (D->PushEntry->RI->In.RegX == 0 || D->OpEntry->RI->In.RegX == 0) {
437 /* The high byte is zero */
438 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, D->OpEntry->LI);
439 InsertEntry (D, X, D->IP++);
441 /* High byte is unknown */
442 AddOpHigh (D, OP65_AND);
445 /* Remove the push and the call to the tosandax function */
448 /* We changed the sequence */
454 static unsigned Opt_tosorax (StackOpData* D)
455 /* Optimize the tosorax sequence if possible */
459 /* Check the entry before the push. If it's a lda instruction with an
460 * addressing mode that allows us to replace it, we may use this
461 * location for the op and must not save the value in the zero page
466 /* Store the value into the zeropage instead of pushing it */
467 ReplacePushByStore (D);
469 /* Inline the or, low byte */
470 D->IP = D->OpIndex + 1;
471 AddOpLow (D, OP65_ORA);
474 if (D->PushEntry->RI->In.RegX >= 0 && D->OpEntry->RI->In.RegX >= 0) {
475 /* Both values known, precalculate the result */
476 const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX | D->OpEntry->RI->In.RegX);
477 X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
478 InsertEntry (D, X, D->IP++);
479 } else if (D->PushEntry->RI->In.RegX != 0) {
480 /* High byte is unknown */
481 AddOpHigh (D, OP65_ORA);
484 /* Remove the push and the call to the tosorax function */
487 /* We changed the sequence */
493 static unsigned Opt_tosxorax (StackOpData* D)
494 /* Optimize the tosxorax sequence if possible */
498 /* Check the entry before the push. If it's a lda instruction with an
499 * addressing mode that allows us to replace it, we may use this
500 * location for the op and must not save the value in the zero page
505 /* Store the value into the zeropage instead of pushing it */
506 ReplacePushByStore (D);
508 /* Inline the xor, low byte */
509 D->IP = D->OpIndex + 1;
510 AddOpLow (D, OP65_EOR);
513 if (D->PushEntry->RI->In.RegX >= 0 && D->OpEntry->RI->In.RegX >= 0) {
514 /* Both values known, precalculate the result */
515 const char* Arg = MakeHexArg (D->PushEntry->RI->In.RegX ^ D->OpEntry->RI->In.RegX);
516 X = NewCodeEntry (OP65_LDX, AM65_IMM, Arg, 0, D->OpEntry->LI);
517 InsertEntry (D, X, D->IP++);
518 } else if (D->PushEntry->RI->In.RegX != 0) {
519 /* High byte is unknown */
520 AddOpHigh (D, OP65_EOR);
523 /* Remove the push and the call to the tosandax function */
526 /* We changed the sequence */
532 /*****************************************************************************/
534 /*****************************************************************************/
538 /* Flags for the functions */
540 STOP_NONE, /* Nothing special */
541 STOP_A_UNUSED /* Call only if a unused later */
545 typedef unsigned (*OptFunc) (StackOpData* D);
546 typedef struct OptFuncDesc OptFuncDesc;
548 const char* Name; /* Name of the replaced runtime function */
549 OptFunc Func; /* Function pointer */
550 STOP_FLAGS Flags; /* Flags */
553 static const OptFuncDesc FuncTable[] = {
554 { "staspidx", Opt_staspidx, STOP_NONE },
555 { "staxspidx", Opt_staxspidx, STOP_A_UNUSED },
556 { "tosaddax", Opt_tosaddax, STOP_NONE },
557 { "tosandax", Opt_tosandax, STOP_NONE },
558 { "tosorax", Opt_tosorax, STOP_NONE },
559 { "tosxorax", Opt_tosxorax, STOP_NONE },
561 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
565 static int CmpFunc (const void* Key, const void* Func)
566 /* Compare function for bsearch */
568 return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
573 static const OptFuncDesc* FindFunc (const char* Name)
574 /* Find the function with the given name. Return a pointer to the table entry
575 * or NULL if the function was not found.
578 return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
583 static int CmpHarmless (const void* Key, const void* Entry)
584 /* Compare function for bsearch */
586 return strcmp (Key, *(const char**)Entry);
591 static int HarmlessCall (const char* Name)
592 /* Check if this is a call to a harmless subroutine that will not interrupt
593 * the pushax/op sequence when encountered.
596 static const char* Tab[] = {
600 void* R = bsearch (Name,
602 sizeof (Tab) / sizeof (Tab[0]),
610 /*****************************************************************************/
612 /*****************************************************************************/
616 unsigned OptStackOps (CodeSeg* S)
617 /* Optimize operations that take operands via the stack */
619 unsigned Changes = 0; /* Number of changes in one run */
620 int InSeq = 0; /* Inside a sequence */
621 unsigned Push = 0; /* Index of pushax */
622 unsigned UsedRegs = 0; /* Zeropage registers used in sequence */
626 /* Generate register info */
629 /* Look for a call to pushax followed by a call to some other function
630 * that takes it's first argument on the stack, and the second argument
631 * in the primary register.
632 * It depends on the code between the two if we can handle/transform the
633 * sequence, so check this code for the following list of things:
635 * - there must not be a jump or conditional branch (this may
636 * get relaxed later).
637 * - there may not be accesses to local variables with unknown
638 * offsets (because we have to adjust these offsets).
639 * - no subroutine calls
642 * Since we need a zero page register later, do also check the
643 * intermediate code for zero page use.
646 while (I < CS_GetEntryCount (S)) {
648 /* Get the next entry */
649 CodeEntry* E = CS_GetEntry (S, I);
651 /* Handling depends if we're inside a sequence or not */
654 if ((E->Info & OF_BRA) != 0 ||
655 ((E->Use & REG_SP) != 0 &&
656 (E->AM != AM65_ZP_INDY || E->RI->In.RegY < 0)) ||
659 /* All this stuff is not allowed in a sequence */
662 } else if (E->OPC == OP65_JSR) {
664 /* Subroutine call: Check if this is one of our functions */
665 const OptFuncDesc* F = FindFunc (E->Arg);
671 /* Check the flags */
672 if (F->Flags & STOP_A_UNUSED) {
673 /* a must be unused later */
674 if (RegAUsed (S, I+1)) {
675 /* Cannot optimize */
680 /* Determine the zero page locations to use */
682 UsedRegs |= GetRegInfo (S, I+1, REG_SREG | REG_PTR1 | REG_PTR2);
683 if ((UsedRegs & REG_SREG) == REG_NONE) {
684 /* SREG is available */
686 Data.ZPHi = "sreg+1";
687 } else if ((UsedRegs & REG_PTR1) == REG_NONE) {
689 Data.ZPHi = "ptr1+1";
690 } else if ((UsedRegs & REG_PTR2) == REG_NONE) {
692 Data.ZPHi = "ptr2+1";
694 /* No registers available */
699 /* If preconditions are ok, call the optimizer function */
702 /* Adjust stack offsets */
703 Data.OpIndex = I + AdjustStackOffset (S, Push, I, 2);
705 /* Prepare the remainder of the data structure */
708 Data.PushIndex = Push;
709 Data.PrevEntry = CS_GetPrevEntry (S, Data.PushIndex);
710 Data.PushEntry = CS_GetEntry (S, Data.PushIndex);
712 Data.NextEntry = CS_GetNextEntry (S, Data.OpIndex);
714 /* Call the optimizer function */
715 Changes += F->Func (&Data);
717 /* Regenerate register info */
721 /* End of sequence */
724 } else if (strcmp (E->Arg, "pushax") == 0) {
725 /* Restart the sequence */
728 } else if (!HarmlessCall (E->Arg)) {
729 /* A call to an unkown subroutine ends the sequence */
735 /* Other stuff: Track zeropage register usage */
736 UsedRegs |= (E->Use | E->Chg);
740 } else if (CE_IsCall (E, "pushax")) {
742 /* This starts a sequence */
754 /* Free the register info */
757 /* Return the number of changes made */