1 /*****************************************************************************/
5 /* Optimize operations that take operands via the stack */
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 /*****************************************************************************/
50 /*****************************************************************************/
52 /*****************************************************************************/
56 static unsigned AdjustStackOffset (CodeSeg* S, unsigned Start, unsigned Stop,
58 /* Adjust the offset for all stack accesses in the range Start to Stop, both
59 * inclusive. The function returns the number of instructions that have been
63 /* Number of inserted instructions */
64 unsigned Inserted = 0;
66 /* Walk over all entries */
70 CodeEntry* E = CS_GetEntry (S, I);
72 if (E->Use & REG_SP) {
76 /* Check for some things that should not happen */
77 CHECK (E->AM == AM65_ZP_INDY || E->RI->In.RegY >= (short) Offs);
78 CHECK (strcmp (E->Arg, "sp") == 0);
80 /* Get the code entry before this one. If it's a LDY, adjust the
83 P = CS_GetPrevEntry (S, I);
84 if (P && P->OPC == OP65_LDY && CE_KnownImm (P)) {
86 /* The Y load is just before the stack access, adjust it */
87 CE_SetNumArg (P, P->Num - Offs);
91 /* Insert a new load instruction before the stack access */
94 xsprintf (Buf, sizeof (Buf), "$%02X", E->RI->In.RegY - Offs);
95 X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, E->LI);
96 CS_InsertEntry (S, X, I);
98 /* One more inserted entries */
102 /* Be sure to skip the stack access for the next round */
113 /* Return the number of inserted entries */
119 /*****************************************************************************/
120 /* Actual optimization functions */
121 /*****************************************************************************/
125 static unsigned Opt_staspidx (CodeSeg* S, unsigned Push, unsigned Store,
126 const char* ZPLo, const char* ZPHi)
127 /* Optimize the staspidx sequence if possible */
130 CodeEntry* PushEntry;
131 CodeEntry* StoreEntry;
133 /* Get the push entry */
134 PushEntry = CS_GetEntry (S, Push);
136 /* Store the value into the zeropage instead of pushing it */
137 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
138 CS_InsertEntry (S, X, Push+1);
139 X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
140 CS_InsertEntry (S, X, Push+2);
142 /* Correct the index of the store and get a pointer to the entry */
144 StoreEntry = CS_GetEntry (S, Store);
146 /* Inline the store */
147 X = NewCodeEntry (OP65_STA, AM65_ZP_INDY, ZPLo, 0, StoreEntry->LI);
148 CS_InsertEntry (S, X, Store+1);
150 /* Remove the push and the call to the staspidx function */
151 CS_DelEntry (S, Store);
152 CS_DelEntry (S, Push);
154 /* We changed the sequence */
160 static unsigned Opt_tosaddax (CodeSeg* S, unsigned Push, unsigned Add,
161 const char* ZPLo, const char* ZPHi)
162 /* Optimize the tosaddax sequence if possible */
166 CodeEntry* PushEntry;
169 /* We need the entry behind the add */
170 CHECK ((N = CS_GetNextEntry (S, Add)) != 0);
172 /* Get the push entry */
173 PushEntry = CS_GetEntry (S, Push);
175 /* Store the value into the zeropage instead of pushing it */
176 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
177 CS_InsertEntry (S, X, Push+1);
178 X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
179 CS_InsertEntry (S, X, Push+2);
181 /* Correct the index of the add and get a pointer to the entry */
183 AddEntry = CS_GetEntry (S, Add);
186 X = NewCodeEntry (OP65_CLC, AM65_IMP, 0, 0, AddEntry->LI);
187 CS_InsertEntry (S, X, Add+1);
188 X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPLo, 0, AddEntry->LI);
189 CS_InsertEntry (S, X, Add+2);
190 if (PushEntry->RI->In.RegX == 0) {
191 /* The high byte is the value in X plus the carry */
192 CodeLabel* L = CS_GenLabel (S, N);
193 X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, AddEntry->LI);
194 CS_InsertEntry (S, X, Add+3);
195 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, AddEntry->LI);
196 CS_InsertEntry (S, X, Add+4);
197 } else if (AddEntry->RI->In.RegX == 0) {
198 /* The high byte is that of the first operand plus carry */
200 if (PushEntry->RI->In.RegX >= 0) {
201 /* Value of first op high byte is known */
203 xsprintf (Buf, sizeof (Buf), "$%02X", PushEntry->RI->In.RegX);
204 X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, AddEntry->LI);
206 /* Value of first op high byte is unknown */
207 X = NewCodeEntry (OP65_LDX, AM65_ZP, ZPHi, 0, AddEntry->LI);
209 CS_InsertEntry (S, X, Add+3);
210 L = CS_GenLabel (S, N);
211 X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, AddEntry->LI);
212 CS_InsertEntry (S, X, Add+4);
213 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, AddEntry->LI);
214 CS_InsertEntry (S, X, Add+5);
216 /* High byte is unknown */
217 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AddEntry->LI);
218 CS_InsertEntry (S, X, Add+3);
219 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AddEntry->LI);
220 CS_InsertEntry (S, X, Add+4);
221 X = NewCodeEntry (OP65_ADC, AM65_ZP, ZPHi, 0, AddEntry->LI);
222 CS_InsertEntry (S, X, Add+5);
223 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AddEntry->LI);
224 CS_InsertEntry (S, X, Add+6);
225 X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AddEntry->LI);
226 CS_InsertEntry (S, X, Add+7);
229 /* Remove the push and the call to the tosaddax function */
230 CS_DelEntry (S, Add);
231 CS_DelEntry (S, Push);
233 /* We changed the sequence */
239 static unsigned Opt_tosandax (CodeSeg* S, unsigned Push, unsigned And,
240 const char* ZPLo, const char* ZPHi)
241 /* Optimize the tosandax sequence if possible */
244 CodeEntry* PushEntry;
247 /* Get the push entry */
248 PushEntry = CS_GetEntry (S, Push);
250 /* Store the value into the zeropage instead of pushing it */
251 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
252 CS_InsertEntry (S, X, Push+1);
253 X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
254 CS_InsertEntry (S, X, Push+2);
256 /* Correct the index of the add and get a pointer to the entry */
258 AndEntry = CS_GetEntry (S, And);
261 X = NewCodeEntry (OP65_AND, AM65_ZP, ZPLo, 0, AndEntry->LI);
262 CS_InsertEntry (S, X, And+1);
263 if (PushEntry->RI->In.RegX == 0 || AndEntry->RI->In.RegX == 0) {
264 /* The high byte is zero */
265 X = NewCodeEntry (OP65_LDX, AM65_IMM, "$00", 0, AndEntry->LI);
266 CS_InsertEntry (S, X, And+2);
268 /* High byte is unknown */
269 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, AndEntry->LI);
270 CS_InsertEntry (S, X, And+2);
271 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, AndEntry->LI);
272 CS_InsertEntry (S, X, And+3);
273 X = NewCodeEntry (OP65_AND, AM65_ZP, ZPHi, 0, AndEntry->LI);
274 CS_InsertEntry (S, X, And+4);
275 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, AndEntry->LI);
276 CS_InsertEntry (S, X, And+5);
277 X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, AndEntry->LI);
278 CS_InsertEntry (S, X, And+6);
281 /* Remove the push and the call to the tosandax function */
282 CS_DelEntry (S, And);
283 CS_DelEntry (S, Push);
285 /* We changed the sequence */
291 static unsigned Opt_tosorax (CodeSeg* S, unsigned Push, unsigned Or,
292 const char* ZPLo, const char* ZPHi)
293 /* Optimize the tosorax sequence if possible */
296 CodeEntry* PushEntry;
299 /* Get the push entry */
300 PushEntry = CS_GetEntry (S, Push);
302 /* Store the value into the zeropage instead of pushing it */
303 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
304 CS_InsertEntry (S, X, Push+1);
305 X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
306 CS_InsertEntry (S, X, Push+2);
308 /* Correct the index of the add and get a pointer to the entry */
310 OrEntry = CS_GetEntry (S, Or);
313 X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPLo, 0, OrEntry->LI);
314 CS_InsertEntry (S, X, Or+1);
315 if (PushEntry->RI->In.RegX >= 0 && OrEntry->RI->In.RegX >= 0) {
316 /* Both values known, precalculate the result */
318 int Val = (PushEntry->RI->In.RegX | OrEntry->RI->In.RegX);
319 xsprintf (Buf, sizeof (Buf), "$%02X", Val);
320 X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, OrEntry->LI);
321 CS_InsertEntry (S, X, Or+2);
322 } else if (PushEntry->RI->In.RegX != 0) {
323 /* High byte is unknown */
324 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, OrEntry->LI);
325 CS_InsertEntry (S, X, Or+2);
326 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, OrEntry->LI);
327 CS_InsertEntry (S, X, Or+3);
328 X = NewCodeEntry (OP65_ORA, AM65_ZP, ZPHi, 0, OrEntry->LI);
329 CS_InsertEntry (S, X, Or+4);
330 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, OrEntry->LI);
331 CS_InsertEntry (S, X, Or+5);
332 X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, OrEntry->LI);
333 CS_InsertEntry (S, X, Or+6);
336 /* Remove the push and the call to the tosandax function */
338 CS_DelEntry (S, Push);
340 /* We changed the sequence */
346 static unsigned Opt_tosxorax (CodeSeg* S, unsigned Push, unsigned Xor,
347 const char* ZPLo, const char* ZPHi)
348 /* Optimize the tosorax sequence if possible */
351 CodeEntry* PushEntry;
354 /* Get the push entry */
355 PushEntry = CS_GetEntry (S, Push);
357 /* Store the value into the zeropage instead of pushing it */
358 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, PushEntry->LI);
359 CS_InsertEntry (S, X, Push+1);
360 X = NewCodeEntry (OP65_STX, AM65_ZP, ZPHi, 0, PushEntry->LI);
361 CS_InsertEntry (S, X, Push+2);
363 /* Correct the index of the add and get a pointer to the entry */
365 XorEntry = CS_GetEntry (S, Xor);
368 X = NewCodeEntry (OP65_EOR, AM65_ZP, ZPLo, 0, XorEntry->LI);
369 CS_InsertEntry (S, X, Xor+1);
370 if (PushEntry->RI->In.RegX >= 0 && XorEntry->RI->In.RegX >= 0) {
371 /* Both values known, precalculate the result */
373 int Val = (PushEntry->RI->In.RegX ^ XorEntry->RI->In.RegX);
374 xsprintf (Buf, sizeof (Buf), "$%02X", Val);
375 X = NewCodeEntry (OP65_LDX, AM65_IMM, Buf, 0, XorEntry->LI);
376 CS_InsertEntry (S, X, Xor+2);
377 } else if (PushEntry->RI->In.RegX != 0) {
378 /* High byte is unknown */
379 X = NewCodeEntry (OP65_STA, AM65_ZP, ZPLo, 0, XorEntry->LI);
380 CS_InsertEntry (S, X, Xor+2);
381 X = NewCodeEntry (OP65_TXA, AM65_IMP, 0, 0, XorEntry->LI);
382 CS_InsertEntry (S, X, Xor+3);
383 X = NewCodeEntry (OP65_EOR, AM65_ZP, ZPHi, 0, XorEntry->LI);
384 CS_InsertEntry (S, X, Xor+4);
385 X = NewCodeEntry (OP65_TAX, AM65_IMP, 0, 0, XorEntry->LI);
386 CS_InsertEntry (S, X, Xor+5);
387 X = NewCodeEntry (OP65_LDA, AM65_ZP, ZPLo, 0, XorEntry->LI);
388 CS_InsertEntry (S, X, Xor+6);
391 /* Remove the push and the call to the tosandax function */
392 CS_DelEntry (S, Xor);
393 CS_DelEntry (S, Push);
395 /* We changed the sequence */
401 /*****************************************************************************/
403 /*****************************************************************************/
407 typedef unsigned (*OptFunc) (CodeSeg* S, unsigned Push, unsigned Store,
408 const char* ZPLo, const char* ZPHi);
409 typedef struct OptFuncDesc OptFuncDesc;
411 const char* Name; /* Name of the replaced runtime function */
412 OptFunc Func; /* Function pointer */
415 static const OptFuncDesc FuncTable[] = {
416 { "staspidx", Opt_staspidx },
417 { "tosaddax", Opt_tosaddax },
418 { "tosandax", Opt_tosandax },
419 { "tosorax", Opt_tosorax },
420 { "tosxorax", Opt_tosxorax },
422 #define FUNC_COUNT (sizeof(FuncTable) / sizeof(FuncTable[0]))
426 static int CmpFunc (const void* Key, const void* Func)
427 /* Compare function for bsearch */
429 return strcmp (Key, ((const OptFuncDesc*) Func)->Name);
434 static const OptFuncDesc* FindFunc (const char* Name)
435 /* Find the function with the given name. Return a pointer to the table entry
436 * or NULL if the function was not found.
439 return bsearch (Name, FuncTable, FUNC_COUNT, sizeof(OptFuncDesc), CmpFunc);
444 /*****************************************************************************/
446 /*****************************************************************************/
450 unsigned OptStackOps (CodeSeg* S)
451 /* Optimize operations that take operands via the stack */
453 unsigned Changes = 0; /* Number of changes in one run */
454 int InSeq = 0; /* Inside a sequence */
455 unsigned Push = 0; /* Index of pushax */
456 unsigned UsedRegs = 0; /* Zeropage registers used in sequence */
459 /* Generate register info */
462 /* Look for a call to pushax followed by a call to some other function
463 * that takes it's first argument on the stack, and the second argument
464 * in the primary register.
465 * It depends on the code between the two if we can handle/transform the
466 * sequence, so check this code for the following list of things:
468 * - there must not be a jump or conditional branch (this may
469 * get relaxed later).
470 * - there may not be accesses to local variables with unknown
471 * offsets (because we have to adjust these offsets).
472 * - no subroutine calls
475 * Since we need a zero page register later, do also check the
476 * intermediate code for zero page use.
479 while (I < CS_GetEntryCount (S)) {
481 /* Get the next entry */
482 CodeEntry* E = CS_GetEntry (S, I);
484 /* Handling depends if we're inside a sequence or not */
487 if ((E->Info & OF_BRA) != 0 ||
488 ((E->Use & REG_SP) != 0 &&
489 (E->AM != AM65_ZP_INDY || E->RI->In.RegY < 0)) ||
492 /* All this stuff is not allowed in a sequence */
495 } else if (E->OPC == OP65_JSR) {
497 /* Subroutine call: Check if this is one of our functions */
498 const OptFuncDesc* F = FindFunc (E->Arg);
501 /* Determine the register to use */
504 UsedRegs |= GetRegInfo (S, I+1, REG_SREG | REG_PTR1 | REG_PTR2);
505 if ((UsedRegs & REG_SREG) == REG_NONE) {
506 /* SREG is available */
509 } else if ((UsedRegs & REG_PTR1) == REG_NONE) {
512 } else if ((UsedRegs & REG_PTR2) == REG_NONE) {
516 /* No registers available */
521 /* If we have a register, call the optimizer function */
524 /* Adjust stack offsets */
525 unsigned Op = I + AdjustStackOffset (S, Push, I, 2);
527 /* Call the optimizer function */
528 Changes += F->Func (S, Push, Op, ZPLo, ZPHi);
530 /* Regenerate register info */
534 /* End of sequence */
537 } else if (strcmp (E->Arg, "pushax") == 0) {
538 /* Restart the sequence */
542 /* A call to an unkown subroutine ends the sequence */
548 /* Other stuff: Track zeropage register usage */
549 UsedRegs |= (E->Use | E->Chg);
553 } else if (CE_IsCall (E, "pushax")) {
555 /* This starts a sequence */
567 /* Free the register info */
570 /* Return the number of changes made */