1 /*****************************************************************************/
9 /* (C) 2001-2012, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
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 /*****************************************************************************/
42 #include "coptshift.h"
46 /*****************************************************************************/
48 /*****************************************************************************/
52 /* Shift types. Shift type is in the first byte, shift count in the second */
57 SHIFT_MASK_COUNT = 0x00FF,
58 SHIFT_MASK_DIR = 0x0F00,
59 SHIFT_MASK_MODE = 0xF000, /* Arithmetic or logical */
60 SHIFT_MASK_TYPE = SHIFT_MASK_DIR | SHIFT_MASK_MODE,
63 SHIFT_COUNT_Y = 0x0000, /* Count is in Y register */
64 SHIFT_COUNT_1 = 0x0001,
65 SHIFT_COUNT_2 = 0x0002,
66 SHIFT_COUNT_3 = 0x0003,
67 SHIFT_COUNT_4 = 0x0004,
68 SHIFT_COUNT_5 = 0x0005,
69 SHIFT_COUNT_6 = 0x0006,
70 SHIFT_COUNT_7 = 0x0007,
72 /* Shift directions */
73 SHIFT_DIR_LEFT = 0x0100,
74 SHIFT_DIR_RIGHT = 0x0200,
77 SHIFT_MODE_ARITH = 0x1000,
78 SHIFT_MODE_LOGICAL = 0x2000,
81 SHIFT_TYPE_ASL = SHIFT_DIR_LEFT | SHIFT_MODE_ARITH,
82 SHIFT_TYPE_ASR = SHIFT_DIR_RIGHT | SHIFT_MODE_ARITH,
83 SHIFT_TYPE_LSL = SHIFT_DIR_LEFT | SHIFT_MODE_LOGICAL,
84 SHIFT_TYPE_LSR = SHIFT_DIR_RIGHT | SHIFT_MODE_LOGICAL,
87 SHIFT_ASL_Y = SHIFT_TYPE_ASL | SHIFT_COUNT_Y,
88 SHIFT_ASR_Y = SHIFT_TYPE_ASR | SHIFT_COUNT_Y,
89 SHIFT_LSL_Y = SHIFT_TYPE_LSL | SHIFT_COUNT_Y,
90 SHIFT_LSR_Y = SHIFT_TYPE_LSR | SHIFT_COUNT_Y,
92 SHIFT_ASL_1 = SHIFT_TYPE_ASL | SHIFT_COUNT_1,
93 SHIFT_ASR_1 = SHIFT_TYPE_ASR | SHIFT_COUNT_1,
94 SHIFT_LSL_1 = SHIFT_TYPE_LSL | SHIFT_COUNT_1,
95 SHIFT_LSR_1 = SHIFT_TYPE_LSR | SHIFT_COUNT_1,
97 SHIFT_ASL_2 = SHIFT_TYPE_ASL | SHIFT_COUNT_2,
98 SHIFT_ASR_2 = SHIFT_TYPE_ASR | SHIFT_COUNT_2,
99 SHIFT_LSL_2 = SHIFT_TYPE_LSL | SHIFT_COUNT_2,
100 SHIFT_LSR_2 = SHIFT_TYPE_LSR | SHIFT_COUNT_2,
102 SHIFT_ASL_3 = SHIFT_TYPE_ASL | SHIFT_COUNT_3,
103 SHIFT_ASR_3 = SHIFT_TYPE_ASR | SHIFT_COUNT_3,
104 SHIFT_LSL_3 = SHIFT_TYPE_LSL | SHIFT_COUNT_3,
105 SHIFT_LSR_3 = SHIFT_TYPE_LSR | SHIFT_COUNT_3,
107 SHIFT_ASL_4 = SHIFT_TYPE_ASL | SHIFT_COUNT_4,
108 SHIFT_ASR_4 = SHIFT_TYPE_ASR | SHIFT_COUNT_4,
109 SHIFT_LSL_4 = SHIFT_TYPE_LSL | SHIFT_COUNT_4,
110 SHIFT_LSR_4 = SHIFT_TYPE_LSR | SHIFT_COUNT_4,
112 SHIFT_ASL_5 = SHIFT_TYPE_ASL | SHIFT_COUNT_5,
113 SHIFT_ASR_5 = SHIFT_TYPE_ASR | SHIFT_COUNT_5,
114 SHIFT_LSL_5 = SHIFT_TYPE_LSL | SHIFT_COUNT_5,
115 SHIFT_LSR_5 = SHIFT_TYPE_LSR | SHIFT_COUNT_5,
117 SHIFT_ASL_6 = SHIFT_TYPE_ASL | SHIFT_COUNT_6,
118 SHIFT_ASR_6 = SHIFT_TYPE_ASR | SHIFT_COUNT_6,
119 SHIFT_LSL_6 = SHIFT_TYPE_LSL | SHIFT_COUNT_6,
120 SHIFT_LSR_6 = SHIFT_TYPE_LSR | SHIFT_COUNT_6,
122 SHIFT_ASL_7 = SHIFT_TYPE_ASL | SHIFT_COUNT_7,
123 SHIFT_ASR_7 = SHIFT_TYPE_ASR | SHIFT_COUNT_7,
124 SHIFT_LSL_7 = SHIFT_TYPE_LSL | SHIFT_COUNT_7,
125 SHIFT_LSR_7 = SHIFT_TYPE_LSR | SHIFT_COUNT_7,
130 /* Macros to extract values from a shift type */
131 #define SHIFT_COUNT(S) ((S) & SHIFT_MASK_COUNT)
132 #define SHIFT_DIR(S) ((S) & SHIFT_MASK_DIR)
133 #define SHIFT_MODE(S) ((S) & SHIFT_MASK_MODE)
134 #define SHIFT_TYPE(S) ((S) & SHIFT_MASK_TYPE)
138 /*****************************************************************************/
139 /* Helper routines */
140 /*****************************************************************************/
144 static unsigned GetShift (const char* Name)
145 /* Determine the shift from the name of the subroutine */
149 if (strncmp (Name, "aslax", 5) == 0) {
150 Type = SHIFT_TYPE_ASL;
151 } else if (strncmp (Name, "asrax", 5) == 0) {
152 Type = SHIFT_TYPE_ASR;
153 } else if (strncmp (Name, "shlax", 5) == 0) {
154 Type = SHIFT_TYPE_LSL;
155 } else if (strncmp (Name, "shrax", 5) == 0) {
156 Type = SHIFT_TYPE_LSR;
158 /* Nothing we know */
164 case 'y': Type |= SHIFT_COUNT_Y; break;
165 case '1': Type |= SHIFT_COUNT_1; break;
166 case '2': Type |= SHIFT_COUNT_2; break;
167 case '3': Type |= SHIFT_COUNT_3; break;
168 case '4': Type |= SHIFT_COUNT_4; break;
169 case '5': Type |= SHIFT_COUNT_5; break;
170 case '6': Type |= SHIFT_COUNT_6; break;
171 case '7': Type |= SHIFT_COUNT_7; break;
172 default: return SHIFT_NONE;
175 /* Make sure nothing follows */
176 if (Name[6] == '\0') {
185 /*****************************************************************************/
186 /* Optimize shifts */
187 /*****************************************************************************/
191 unsigned OptShift1 (CodeSeg* S)
192 /* A call to the shlaxN routine may get replaced by one or more asl insns
193 * if the value of X is not used later. If X is used later, but it is zero
194 * on entry and it's a shift by one, it may get replaced by:
203 unsigned Changes = 0;
206 /* Walk over the entries */
208 while (I < CS_GetEntryCount (S)) {
216 CodeEntry* E = CS_GetEntry (S, I);
218 /* Check for the sequence */
219 if (E->OPC == OP65_JSR &&
220 (Shift = GetShift (E->Arg)) != SHIFT_NONE &&
221 SHIFT_DIR (Shift) == SHIFT_DIR_LEFT) {
224 unsigned Count = SHIFT_COUNT (Shift);
225 if (!RegXUsed (S, I+1)) {
227 if (Count == SHIFT_COUNT_Y) {
231 if (S->CodeSizeFactor < 200) {
244 X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
245 CS_InsertEntry (S, X, I+1);
246 L = CS_GenLabel (S, X);
249 X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, E->LI);
250 CS_InsertEntry (S, X, I+2);
253 X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, E->LI);
254 CS_InsertEntry (S, X, I+3);
257 X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, E->LI);
258 CS_InsertEntry (S, X, I+4);
261 /* Insert shift insns */
263 X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
264 CS_InsertEntry (S, X, I+1);
268 } else if (E->RI->In.RegX == 0 &&
270 (N = CS_GetNextEntry (S, I)) != 0) {
273 X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
274 CS_InsertEntry (S, X, I+1);
277 L = CS_GenLabel (S, N);
278 X = NewCodeEntry (OP65_BCC, AM65_BRA, L->Name, L, E->LI);
279 CS_InsertEntry (S, X, I+2);
282 X = NewCodeEntry (OP65_INX, AM65_IMP, 0, 0, E->LI);
283 CS_InsertEntry (S, X, I+3);
287 /* We won't handle this one */
292 /* Delete the call to shlax */
295 /* Remember, we had changes */
305 /* Return the number of changes made */
311 unsigned OptShift2(CodeSeg* S)
312 /* A call to the asrax1 routines may get replaced by something simpler, if
313 * X is not used later:
320 unsigned Changes = 0;
323 /* Walk over the entries */
325 while (I < CS_GetEntryCount (S)) {
331 CodeEntry* E = CS_GetEntry (S, I);
333 /* Check for the sequence */
334 if (E->OPC == OP65_JSR &&
335 (Shift = GetShift (E->Arg)) != SHIFT_NONE &&
336 SHIFT_TYPE (Shift) == SHIFT_TYPE_ASR &&
337 (Count = SHIFT_COUNT (Shift)) > 0 &&
338 Count * 100 <= S->CodeSizeFactor &&
339 !RegXUsed (S, I+1)) {
344 /* Generate the replacement sequence */
347 X = NewCodeEntry (OP65_CMP, AM65_IMM, "$80", 0, E->LI);
348 CS_InsertEntry (S, X, J++);
351 X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, E->LI);
352 CS_InsertEntry (S, X, J++);
355 /* Delete the call to asrax */
358 /* Remember, we had changes */
367 /* Return the number of changes made */
373 unsigned OptShift3 (CodeSeg* S)
380 * may get replaced by
384 * if X is zero on entry. For shift counts > 1, more
391 unsigned Changes = 0;
394 /* Walk over the entries */
396 while (I < CS_GetEntryCount (S)) {
403 L[0] = CS_GetEntry (S, I);
405 /* Check for the sequence */
406 if ((L[0]->OPC == OP65_BCC || L[0]->OPC == OP65_JCC) &&
408 L[0]->RI->In.RegX == 0 &&
409 CS_GetEntries (S, L+1, I+1, 2) &&
410 L[1]->OPC == OP65_INX &&
411 L[0]->JumpTo->Owner == L[2] &&
412 !CS_RangeHasLabel (S, I, 2) &&
413 L[2]->OPC == OP65_JSR &&
414 (Shift = GetShift (L[2]->Arg)) != SHIFT_NONE &&
415 SHIFT_DIR (Shift) == SHIFT_DIR_RIGHT &&
416 (Count = SHIFT_COUNT (Shift)) > 0) {
418 /* Add the replacement insn instead */
419 CodeEntry* X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, L[2]->LI);
420 CS_InsertEntry (S, X, I+3);
422 X = NewCodeEntry (OP65_LSR, AM65_ACC, "a", 0, L[2]->LI);
423 CS_InsertEntry (S, X, I+4);
426 /* Remove the bcs/dex/jsr */
427 CS_DelEntries (S, I, 3);
429 /* Remember, we had changes */
439 /* Return the number of changes made */
445 unsigned OptShift4 (CodeSeg* S)
446 /* Calls to the asraxN or shraxN routines may get replaced by one or more lsr
447 * insns if the value of X is zero.
450 unsigned Changes = 0;
453 /* Walk over the entries */
455 while (I < CS_GetEntryCount (S)) {
461 CodeEntry* E = CS_GetEntry (S, I);
463 /* Check for the sequence */
464 if (E->OPC == OP65_JSR &&
465 (Shift = GetShift (E->Arg)) != SHIFT_NONE &&
466 SHIFT_DIR (Shift) == SHIFT_DIR_RIGHT &&
467 E->RI->In.RegX == 0) {
471 /* Shift count may be in Y */
472 Count = SHIFT_COUNT (Shift);
473 if (Count == SHIFT_COUNT_Y) {
477 if (S->CodeSizeFactor < 200) {
489 * A negative shift count or one that is greater or equal than
490 * the bit width of the left operand (which is promoted to
491 * integer before the operation) causes undefined behaviour, so
492 * above transformation is safe.
496 X = NewCodeEntry (OP65_LSR, AM65_ACC, "a", 0, E->LI);
497 CS_InsertEntry (S, X, I+1);
498 L = CS_GenLabel (S, X);
501 X = NewCodeEntry (OP65_DEY, AM65_IMP, 0, 0, E->LI);
502 CS_InsertEntry (S, X, I+2);
505 X = NewCodeEntry (OP65_BPL, AM65_BRA, L->Name, L, E->LI);
506 CS_InsertEntry (S, X, I+3);
509 X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, E->LI);
510 CS_InsertEntry (S, X, I+4);
513 /* Insert shift insns */
515 X = NewCodeEntry (OP65_LSR, AM65_ACC, "a", 0, E->LI);
516 CS_InsertEntry (S, X, I+1);
521 /* Delete the call to shrax */
524 /* Remember, we had changes */
535 /* Return the number of changes made */
541 unsigned OptShift5 (CodeSeg* S)
542 /* Search for the sequence
546 * jsr aslax1/asrax1/shlax1/shrax1
559 * or similar, provided that a/x is not used later
562 unsigned Changes = 0;
564 /* Walk over the entries */
566 while (I < CS_GetEntryCount (S)) {
572 L[0] = CS_GetEntry (S, I);
574 /* Check for the sequence */
575 if (L[0]->OPC == OP65_LDA &&
576 (L[0]->AM == AM65_ABS || L[0]->AM == AM65_ZP) &&
577 CS_GetEntries (S, L+1, I+1, 4) &&
578 !CS_RangeHasLabel (S, I+1, 4) &&
579 L[1]->OPC == OP65_LDX &&
580 (L[1]->AM == AM65_ABS || L[1]->AM == AM65_ZP) &&
581 L[2]->OPC == OP65_JSR &&
582 (ShiftType = GetShift (L[2]->Arg)) != SHIFT_NONE &&
583 SHIFT_COUNT(ShiftType) == 1 &&
584 L[3]->OPC == OP65_STA &&
585 (L[3]->AM == AM65_ABS || L[3]->AM == AM65_ZP) &&
586 L[4]->OPC == OP65_STX &&
587 (L[4]->AM == AM65_ABS || L[4]->AM == AM65_ZP) &&
588 !RegAXUsed (S, I+5)) {
592 /* Handle the four shift types differently */
596 X = NewCodeEntry (OP65_LDA, L[1]->AM, L[1]->Arg, 0, L[1]->LI);
597 CS_InsertEntry (S, X, I+5);
598 X = NewCodeEntry (OP65_CMP, AM65_IMM, "$80", 0, L[2]->LI);
599 CS_InsertEntry (S, X, I+6);
600 X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, L[2]->LI);
601 CS_InsertEntry (S, X, I+7);
602 X = NewCodeEntry (OP65_STA, L[4]->AM, L[4]->Arg, 0, L[4]->LI);
603 CS_InsertEntry (S, X, I+8);
604 X = NewCodeEntry (OP65_LDA, L[0]->AM, L[0]->Arg, 0, L[0]->LI);
605 CS_InsertEntry (S, X, I+9);
606 X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, L[2]->LI);
607 CS_InsertEntry (S, X, I+10);
608 X = NewCodeEntry (OP65_STA, L[3]->AM, L[3]->Arg, 0, L[3]->LI);
609 CS_InsertEntry (S, X, I+11);
610 CS_DelEntries (S, I, 5);
614 X = NewCodeEntry (OP65_LDA, L[1]->AM, L[1]->Arg, 0, L[1]->LI);
615 CS_InsertEntry (S, X, I+5);
616 X = NewCodeEntry (OP65_LSR, AM65_ACC, "a", 0, L[2]->LI);
617 CS_InsertEntry (S, X, I+6);
618 X = NewCodeEntry (OP65_STA, L[4]->AM, L[4]->Arg, 0, L[4]->LI);
619 CS_InsertEntry (S, X, I+7);
620 X = NewCodeEntry (OP65_LDA, L[0]->AM, L[0]->Arg, 0, L[0]->LI);
621 CS_InsertEntry (S, X, I+8);
622 X = NewCodeEntry (OP65_ROR, AM65_ACC, "a", 0, L[2]->LI);
623 CS_InsertEntry (S, X, I+9);
624 X = NewCodeEntry (OP65_STA, L[3]->AM, L[3]->Arg, 0, L[3]->LI);
625 CS_InsertEntry (S, X, I+10);
626 CS_DelEntries (S, I, 5);
631 /* These two are identical */
632 X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, L[2]->LI);
633 CS_InsertEntry (S, X, I+1);
634 X = NewCodeEntry (OP65_STA, L[3]->AM, L[3]->Arg, 0, L[3]->LI);
635 CS_InsertEntry (S, X, I+2);
636 X = NewCodeEntry (OP65_LDA, L[1]->AM, L[1]->Arg, 0, L[1]->LI);
637 CS_InsertEntry (S, X, I+3);
638 X = NewCodeEntry (OP65_ROL, AM65_ACC, "a", 0, L[2]->LI);
639 CS_InsertEntry (S, X, I+4);
640 X = NewCodeEntry (OP65_STA, L[4]->AM, L[4]->Arg, 0, L[4]->LI);
641 CS_InsertEntry (S, X, I+5);
642 CS_DelEntries (S, I+6, 4);
647 /* Remember, we had changes */
657 /* Return the number of changes made */
663 unsigned OptShift6 (CodeSeg* S)
664 /* Inline the shift subroutines. */
666 unsigned Changes = 0;
668 /* Walk over the entries */
670 while (I < CS_GetEntryCount (S)) {
678 CodeEntry* E = CS_GetEntry (S, I);
680 /* Check for a call to one of the shift routine */
681 if (E->OPC == OP65_JSR &&
682 (Shift = GetShift (E->Arg)) != SHIFT_NONE &&
683 SHIFT_DIR (Shift) == SHIFT_DIR_LEFT &&
684 (Count = SHIFT_COUNT (Shift)) > 0) {
691 * (repeat ShiftCount-1 times)
694 * which makes 4 + 3 * ShiftCount bytes, compared to the original
695 * 3 bytes for the subroutine call. However, in most cases, the
696 * final load of the X register gets merged with some other insn
697 * and replaces a txa, so for a shift count of 1, we get a factor
698 * of 200, which matches nicely the CodeSizeFactor enabled with -Oi
700 if (Count > 1 || S->CodeSizeFactor > 200) {
701 unsigned Size = 4 + 3 * Count;
702 if ((Size * 100 / 3) > S->CodeSizeFactor) {
708 /* Inline the code. Insertion point is behind the subroutine call */
712 X = NewCodeEntry (OP65_STX, AM65_ZP, "tmp1", 0, E->LI);
713 CS_InsertEntry (S, X, IP++);
717 X = NewCodeEntry (OP65_ASL, AM65_ACC, "a", 0, E->LI);
718 CS_InsertEntry (S, X, IP++);
721 X = NewCodeEntry (OP65_ROL, AM65_ZP, "tmp1", 0, E->LI);
722 CS_InsertEntry (S, X, IP++);
726 X = NewCodeEntry (OP65_LDX, AM65_ZP, "tmp1", 0, E->LI);
727 CS_InsertEntry (S, X, IP++);
729 /* Remove the subroutine call */
732 /* Remember, we had changes */
742 /* Return the number of changes made */