1 | /*****************************************************************************/ |
2 | /* */ |
3 | /* coptcmp.c */ |
4 | /* */ |
5 | /* Optimize compares */ |
6 | /* */ |
7 | /* */ |
8 | /* */ |
9 | /* (C) 2001-2012, Ullrich von Bassewitz */ |
10 | /* Roemerstrasse 52 */ |
11 | /* D-70794 Filderstadt */ |
12 | /* EMail: uz@cc65.org */ |
13 | /* */ |
14 | /* */ |
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. */ |
18 | /* */ |
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: */ |
22 | /* */ |
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 */ |
30 | /* distribution. */ |
31 | /* */ |
32 | /*****************************************************************************/ |
33 | |
34 | |
35 | |
36 | #include <string.h> |
37 | |
38 | /* cc65 */ |
39 | #include "codeent.h" |
40 | #include "codeinfo.h" |
41 | #include "error.h" |
42 | #include "coptcmp.h" |
43 | |
44 | |
45 | |
46 | /*****************************************************************************/ |
47 | /* Data */ |
48 | /*****************************************************************************/ |
49 | |
50 | |
51 | |
52 | /* Table used to invert a condition, indexed by condition */ |
53 | static const unsigned char CmpInvertTab [] = { |
54 | CMP_NE, CMP_EQ, |
55 | CMP_LE, CMP_LT, CMP_GE, CMP_GT, |
56 | CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT |
57 | }; |
58 | |
59 | |
60 | |
61 | /*****************************************************************************/ |
62 | /* Helper functions */ |
63 | /*****************************************************************************/ |
64 | |
65 | |
66 | |
67 | static void ReplaceCmp (CodeSeg* S, unsigned I, cmp_t Cond) |
68 | /* Helper function for the replacement of routines that return a boolean |
69 | ** followed by a conditional jump. Instead of the boolean value, the condition |
70 | ** codes are evaluated directly. |
71 | ** I is the index of the conditional branch, the sequence is already checked |
72 | ** to be correct. |
73 | */ |
74 | { |
75 | CodeEntry* N; |
76 | CodeLabel* L; |
77 | |
78 | /* Get the entry */ |
79 | CodeEntry* E = CS_GetEntry (S, I); |
80 | |
81 | /* Replace the conditional branch */ |
82 | switch (Cond) { |
83 | |
84 | case CMP_EQ: |
85 | CE_ReplaceOPC (E, OP65_JEQ); |
86 | break; |
87 | |
88 | case CMP_NE: |
89 | CE_ReplaceOPC (E, OP65_JNE); |
90 | break; |
91 | |
92 | case CMP_GT: |
93 | /* Replace by |
94 | ** beq @L |
95 | ** jpl Target |
96 | ** @L: ... |
97 | */ |
98 | if ((N = CS_GetNextEntry (S, I)) == 0) { |
99 | /* No such entry */ |
100 | Internal ("Invalid program flow" ); |
101 | } |
102 | L = CS_GenLabel (S, N); |
103 | N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI); |
104 | CS_InsertEntry (S, N, I); |
105 | CE_ReplaceOPC (E, OP65_JPL); |
106 | break; |
107 | |
108 | case CMP_GE: |
109 | CE_ReplaceOPC (E, OP65_JPL); |
110 | break; |
111 | |
112 | case CMP_LT: |
113 | CE_ReplaceOPC (E, OP65_JMI); |
114 | break; |
115 | |
116 | case CMP_LE: |
117 | /* Replace by |
118 | ** jmi Target |
119 | ** jeq Target |
120 | */ |
121 | CE_ReplaceOPC (E, OP65_JMI); |
122 | L = E->JumpTo; |
123 | N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI); |
124 | CS_InsertEntry (S, N, I+1); |
125 | break; |
126 | |
127 | case CMP_UGT: |
128 | /* Replace by |
129 | ** beq @L |
130 | ** jcs Target |
131 | ** @L: ... |
132 | */ |
133 | if ((N = CS_GetNextEntry (S, I)) == 0) { |
134 | /* No such entry */ |
135 | Internal ("Invalid program flow" ); |
136 | } |
137 | L = CS_GenLabel (S, N); |
138 | N = NewCodeEntry (OP65_BEQ, AM65_BRA, L->Name, L, E->LI); |
139 | CS_InsertEntry (S, N, I); |
140 | CE_ReplaceOPC (E, OP65_JCS); |
141 | break; |
142 | |
143 | case CMP_UGE: |
144 | CE_ReplaceOPC (E, OP65_JCS); |
145 | break; |
146 | |
147 | case CMP_ULT: |
148 | CE_ReplaceOPC (E, OP65_JCC); |
149 | break; |
150 | |
151 | case CMP_ULE: |
152 | /* Replace by |
153 | ** jcc Target |
154 | ** jeq Target |
155 | */ |
156 | CE_ReplaceOPC (E, OP65_JCC); |
157 | L = E->JumpTo; |
158 | N = NewCodeEntry (OP65_JEQ, AM65_BRA, L->Name, L, E->LI); |
159 | CS_InsertEntry (S, N, I+1); |
160 | break; |
161 | |
162 | default: |
163 | Internal ("Unknown jump condition: %d" , Cond); |
164 | |
165 | } |
166 | |
167 | } |
168 | |
169 | |
170 | |
171 | static int IsImmCmp16 (CodeEntry** L) |
172 | /* Check if the instructions at L are an immediate compare of a/x: |
173 | ** |
174 | ** |
175 | */ |
176 | { |
177 | return (L[0]->OPC == OP65_CPX && |
178 | L[0]->AM == AM65_IMM && |
179 | (L[0]->Flags & CEF_NUMARG) != 0 && |
180 | !CE_HasLabel (L[0]) && |
181 | (L[1]->OPC == OP65_JNE || L[1]->OPC == OP65_BNE) && |
182 | L[1]->JumpTo != 0 && |
183 | !CE_HasLabel (L[1]) && |
184 | L[2]->OPC == OP65_CMP && |
185 | L[2]->AM == AM65_IMM && |
186 | (L[2]->Flags & CEF_NUMARG) != 0 && |
187 | (L[3]->Info & OF_CBRA) != 0 && |
188 | L[3]->JumpTo != 0 && |
189 | (L[1]->JumpTo->Owner == L[3] || L[1]->JumpTo == L[3]->JumpTo)); |
190 | } |
191 | |
192 | |
193 | |
194 | static int GetCmpRegVal (const CodeEntry* E) |
195 | /* Return the register value for an immediate compare */ |
196 | { |
197 | switch (E->OPC) { |
198 | case OP65_CMP: return E->RI->In.RegA; |
199 | case OP65_CPX: return E->RI->In.RegX; |
200 | case OP65_CPY: return E->RI->In.RegY; |
201 | default: Internal ("Invalid opcode in GetCmpRegVal" ); |
202 | return 0; /* Not reached */ |
203 | } |
204 | } |
205 | |
206 | |
207 | |
208 | /*****************************************************************************/ |
209 | /* Remove calls to the bool transformer subroutines */ |
210 | /*****************************************************************************/ |
211 | |
212 | |
213 | |
214 | unsigned OptBoolTrans (CodeSeg* S) |
215 | /* Try to remove the call to boolean transformer routines where the call is |
216 | ** not really needed. |
217 | */ |
218 | { |
219 | unsigned Changes = 0; |
220 | |
221 | /* Walk over the entries */ |
222 | unsigned I = 0; |
223 | while (I < CS_GetEntryCount (S)) { |
224 | |
225 | CodeEntry* N; |
226 | cmp_t Cond; |
227 | |
228 | /* Get next entry */ |
229 | CodeEntry* E = CS_GetEntry (S, I); |
230 | |
231 | /* Check for a boolean transformer */ |
232 | if (E->OPC == OP65_JSR && |
233 | (Cond = FindBoolCmpCond (E->Arg)) != CMP_INV && |
234 | (N = CS_GetNextEntry (S, I)) != 0 && |
235 | (N->Info & OF_ZBRA) != 0) { |
236 | |
237 | /* Make the boolean transformer unnecessary by changing the |
238 | ** the conditional jump to evaluate the condition flags that |
239 | ** are set after the compare directly. Note: jeq jumps if |
240 | ** the condition is not met, jne jumps if the condition is met. |
241 | ** Invert the code if we jump on condition not met. |
242 | */ |
243 | if (GetBranchCond (N->OPC) == BC_EQ) { |
244 | /* Jumps if condition false, invert condition */ |
245 | Cond = CmpInvertTab [Cond]; |
246 | } |
247 | |
248 | /* Check if we can replace the code by something better */ |
249 | ReplaceCmp (S, I+1, Cond); |
250 | |
251 | /* Remove the call to the bool transformer */ |
252 | CS_DelEntry (S, I); |
253 | |
254 | /* Remember, we had changes */ |
255 | ++Changes; |
256 | |
257 | } |
258 | |
259 | /* Next entry */ |
260 | ++I; |
261 | |
262 | } |
263 | |
264 | /* Return the number of changes made */ |
265 | return Changes; |
266 | } |
267 | |
268 | |
269 | |
270 | /*****************************************************************************/ |
271 | /* Optimizations for compares */ |
272 | /*****************************************************************************/ |
273 | |
274 | |
275 | |
276 | unsigned OptCmp1 (CodeSeg* S) |
277 | /* Search for the sequence |
278 | ** |
279 | ** ldx xx |
280 | ** stx tmp1 |
281 | ** ora tmp1 |
282 | ** |
283 | ** and replace it by |
284 | ** |
285 | ** ora xx |
286 | */ |
287 | { |
288 | unsigned Changes = 0; |
289 | |
290 | /* Walk over the entries */ |
291 | unsigned I = 0; |
292 | while (I < CS_GetEntryCount (S)) { |
293 | |
294 | CodeEntry* L[3]; |
295 | |
296 | /* Get next entry */ |
297 | L[0] = CS_GetEntry (S, I); |
298 | |
299 | /* Check for the sequence */ |
300 | if (L[0]->OPC == OP65_LDX && |
301 | !CS_RangeHasLabel (S, I+1, 2) && |
302 | CS_GetEntries (S, L+1, I+1, 2) && |
303 | L[1]->OPC == OP65_STX && |
304 | strcmp (L[1]->Arg, "tmp1" ) == 0 && |
305 | L[2]->OPC == OP65_ORA && |
306 | strcmp (L[2]->Arg, "tmp1" ) == 0) { |
307 | |
308 | CodeEntry* X; |
309 | |
310 | /* Insert the ora instead */ |
311 | X = NewCodeEntry (OP65_ORA, L[0]->AM, L[0]->Arg, 0, L[0]->LI); |
312 | CS_InsertEntry (S, X, I); |
313 | |
314 | /* Remove all other instructions */ |
315 | CS_DelEntries (S, I+1, 3); |
316 | |
317 | /* Remember, we had changes */ |
318 | ++Changes; |
319 | |
320 | } |
321 | |
322 | /* Next entry */ |
323 | ++I; |
324 | |
325 | } |
326 | |
327 | /* Return the number of changes made */ |
328 | return Changes; |
329 | } |
330 | |
331 | |
332 | |
333 | unsigned OptCmp2 (CodeSeg* S) |
334 | /* Search for the sequence |
335 | ** |
336 | ** stx xx |
337 | ** stx tmp1 |
338 | ** ora tmp1 |
339 | ** |
340 | ** and replace it by |
341 | ** |
342 | ** stx xx |
343 | ** ora xx |
344 | */ |
345 | { |
346 | unsigned Changes = 0; |
347 | |
348 | /* Walk over the entries */ |
349 | unsigned I = 0; |
350 | while (I < CS_GetEntryCount (S)) { |
351 | |
352 | CodeEntry* L[2]; |
353 | |
354 | /* Get next entry */ |
355 | CodeEntry* E = CS_GetEntry (S, I); |
356 | |
357 | /* Check for the sequence */ |
358 | if (E->OPC == OP65_STX && |
359 | !CS_RangeHasLabel (S, I+1, 2) && |
360 | CS_GetEntries (S, L, I+1, 2) && |
361 | L[0]->OPC == OP65_STX && |
362 | strcmp (L[0]->Arg, "tmp1" ) == 0 && |
363 | L[1]->OPC == OP65_ORA && |
364 | strcmp (L[1]->Arg, "tmp1" ) == 0) { |
365 | |
366 | /* Remove the remaining instructions */ |
367 | CS_DelEntries (S, I+1, 2); |
368 | |
369 | /* Insert the ora instead */ |
370 | CS_InsertEntry (S, NewCodeEntry (OP65_ORA, E->AM, E->Arg, 0, E->LI), I+1); |
371 | |
372 | /* Remember, we had changes */ |
373 | ++Changes; |
374 | |
375 | } |
376 | |
377 | /* Next entry */ |
378 | ++I; |
379 | |
380 | } |
381 | |
382 | /* Return the number of changes made */ |
383 | return Changes; |
384 | } |
385 | |
386 | |
387 | |
388 | unsigned OptCmp3 (CodeSeg* S) |
389 | /* Search for |
390 | ** |
391 | ** lda/and/ora/eor ... |
392 | ** cmp #$00 |
393 | ** jeq/jne |
394 | ** or |
395 | ** lda/and/ora/eor ... |
396 | ** cmp #$00 |
397 | ** jsr boolxx |
398 | ** |
399 | ** and remove the cmp. |
400 | */ |
401 | { |
402 | unsigned Changes = 0; |
403 | |
404 | /* Walk over the entries */ |
405 | unsigned I = 0; |
406 | while (I < CS_GetEntryCount (S)) { |
407 | |
408 | CodeEntry* L[3]; |
409 | |
410 | /* Get next entry */ |
411 | L[0] = CS_GetEntry (S, I); |
412 | |
413 | /* Check for the sequence */ |
414 | if ((L[0]->OPC == OP65_ADC || |
415 | L[0]->OPC == OP65_AND || |
416 | L[0]->OPC == OP65_ASL || |
417 | L[0]->OPC == OP65_DEA || |
418 | L[0]->OPC == OP65_EOR || |
419 | L[0]->OPC == OP65_INA || |
420 | L[0]->OPC == OP65_LDA || |
421 | L[0]->OPC == OP65_LSR || |
422 | L[0]->OPC == OP65_ORA || |
423 | L[0]->OPC == OP65_PLA || |
424 | L[0]->OPC == OP65_SBC || |
425 | L[0]->OPC == OP65_TXA || |
426 | L[0]->OPC == OP65_TYA) && |
427 | !CS_RangeHasLabel (S, I+1, 2) && |
428 | CS_GetEntries (S, L+1, I+1, 2) && |
429 | L[1]->OPC == OP65_CMP && |
430 | CE_IsKnownImm (L[1], 0)) { |
431 | |
432 | int Delete = 0; |
433 | |
434 | /* Check for the call to boolxx. We only remove the compare if |
435 | ** the carry flag is not evaluated later, because the load will |
436 | ** not set the carry flag. |
437 | */ |
438 | if (L[2]->OPC == OP65_JSR) { |
439 | switch (FindBoolCmpCond (L[2]->Arg)) { |
440 | |
441 | case CMP_EQ: |
442 | case CMP_NE: |
443 | case CMP_GT: |
444 | case CMP_GE: |
445 | case CMP_LT: |
446 | case CMP_LE: |
447 | /* Remove the compare */ |
448 | Delete = 1; |
449 | break; |
450 | |
451 | case CMP_UGT: |
452 | case CMP_UGE: |
453 | case CMP_ULT: |
454 | case CMP_ULE: |
455 | case CMP_INV: |
456 | /* Leave it alone */ |
457 | break; |
458 | } |
459 | |
460 | } else if ((L[2]->Info & OF_FBRA) != 0) { |
461 | /* The following insn branches on the condition of the load, |
462 | ** so the compare instruction might be removed. For safety, |
463 | ** do some more checks if the carry isn't used later, since |
464 | ** the compare does set the carry, but the load does not. |
465 | */ |
466 | CodeEntry* E; |
467 | CodeEntry* N; |
468 | if ((E = CS_GetNextEntry (S, I+2)) != 0 && |
469 | L[2]->JumpTo != 0 && |
470 | (N = L[2]->JumpTo->Owner) != 0 && |
471 | N->OPC != OP65_BCC && |
472 | N->OPC != OP65_BCS && |
473 | N->OPC != OP65_JCC && |
474 | N->OPC != OP65_JCS && |
475 | (N->OPC != OP65_JSR || |
476 | FindBoolCmpCond (N->Arg) == CMP_INV)) { |
477 | |
478 | /* The following insn branches on the condition of a load, |
479 | ** and there's no use of the carry flag in sight, so the |
480 | ** compare instruction can be removed. |
481 | */ |
482 | Delete = 1; |
483 | } |
484 | } |
485 | |
486 | /* Delete the compare if we can */ |
487 | if (Delete) { |
488 | CS_DelEntry (S, I+1); |
489 | ++Changes; |
490 | } |
491 | } |
492 | |
493 | /* Next entry */ |
494 | ++I; |
495 | |
496 | } |
497 | |
498 | /* Return the number of changes made */ |
499 | return Changes; |
500 | } |
501 | |
502 | |
503 | |
504 | unsigned OptCmp4 (CodeSeg* S) |
505 | /* Search for |
506 | ** |
507 | ** lda x |
508 | ** ldx y |
509 | ** cpx #a |
510 | ** bne L1 |
511 | ** cmp #b |
512 | ** L1: jne/jeq L2 |
513 | ** |
514 | ** If a is zero, we may remove the compare. If a and b are both zero, we may |
515 | ** replace it by the sequence |
516 | ** |
517 | ** lda x |
518 | ** ora x+1 |
519 | ** jne/jeq ... |
520 | ** |
521 | ** L1 may be either the label at the branch instruction, or the target label |
522 | ** of this instruction. |
523 | */ |
524 | { |
525 | unsigned Changes = 0; |
526 | |
527 | /* Walk over the entries */ |
528 | unsigned I = 0; |
529 | while (I < CS_GetEntryCount (S)) { |
530 | |
531 | CodeEntry* L[5]; |
532 | |
533 | /* Get next entry */ |
534 | CodeEntry* E = CS_GetEntry (S, I); |
535 | |
536 | /* Check for the sequence */ |
537 | if (E->OPC == OP65_LDA && |
538 | CS_GetEntries (S, L, I+1, 5) && |
539 | L[0]->OPC == OP65_LDX && |
540 | !CE_HasLabel (L[0]) && |
541 | IsImmCmp16 (L+1) && |
542 | !RegAXUsed (S, I+6)) { |
543 | |
544 | if ((L[4]->Info & OF_FBRA) != 0 && L[1]->Num == 0 && L[3]->Num == 0) { |
545 | /* The value is zero, we may use the simple code version. */ |
546 | CE_ReplaceOPC (L[0], OP65_ORA); |
547 | CS_DelEntries (S, I+2, 3); |
548 | } else { |
549 | /* Move the lda instruction after the first branch. This will |
550 | ** improve speed, since the load is delayed after the first |
551 | ** test. |
552 | */ |
553 | CS_MoveEntry (S, I, I+4); |
554 | |
555 | /* We will replace the ldx/cpx by lda/cmp */ |
556 | CE_ReplaceOPC (L[0], OP65_LDA); |
557 | CE_ReplaceOPC (L[1], OP65_CMP); |
558 | |
559 | /* Beware: If the first LDA instruction had a label, we have |
560 | ** to move this label to the top of the sequence again. |
561 | */ |
562 | if (CE_HasLabel (E)) { |
563 | CS_MoveLabels (S, E, L[0]); |
564 | } |
565 | |
566 | } |
567 | |
568 | ++Changes; |
569 | } |
570 | |
571 | /* Next entry */ |
572 | ++I; |
573 | |
574 | } |
575 | |
576 | /* Return the number of changes made */ |
577 | return Changes; |
578 | } |
579 | |
580 | |
581 | |
582 | unsigned OptCmp5 (CodeSeg* S) |
583 | /* Optimize compares of local variables: |
584 | ** |
585 | ** ldy #o |
586 | ** jsr ldaxysp |
587 | ** cpx #a |
588 | ** bne L1 |
589 | ** cmp #b |
590 | ** jne/jeq L2 |
591 | */ |
592 | { |
593 | unsigned Changes = 0; |
594 | |
595 | /* Walk over the entries */ |
596 | unsigned I = 0; |
597 | while (I < CS_GetEntryCount (S)) { |
598 | |
599 | CodeEntry* L[6]; |
600 | |
601 | /* Get the next entry */ |
602 | L[0] = CS_GetEntry (S, I); |
603 | |
604 | /* Check for the sequence */ |
605 | if (L[0]->OPC == OP65_LDY && |
606 | CE_IsConstImm (L[0]) && |
607 | CS_GetEntries (S, L+1, I+1, 5) && |
608 | !CE_HasLabel (L[1]) && |
609 | CE_IsCallTo (L[1], "ldaxysp" ) && |
610 | IsImmCmp16 (L+2)) { |
611 | |
612 | if ((L[5]->Info & OF_FBRA) != 0 && L[2]->Num == 0 && L[4]->Num == 0) { |
613 | |
614 | CodeEntry* X; |
615 | char Buf[20]; |
616 | |
617 | /* The value is zero, we may use the simple code version: |
618 | ** ldy #o-1 |
619 | ** lda (sp),y |
620 | ** ldy #o |
621 | ** ora (sp),y |
622 | ** jne/jeq ... |
623 | */ |
624 | sprintf (Buf, "$%02X" , (int)(L[0]->Num-1)); |
625 | X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI); |
626 | CS_InsertEntry (S, X, I+1); |
627 | |
628 | X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp" , 0, L[1]->LI); |
629 | CS_InsertEntry (S, X, I+2); |
630 | |
631 | X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI); |
632 | CS_InsertEntry (S, X, I+3); |
633 | |
634 | X = NewCodeEntry (OP65_ORA, AM65_ZP_INDY, "sp" , 0, L[1]->LI); |
635 | CS_InsertEntry (S, X, I+4); |
636 | |
637 | CS_DelEntries (S, I+5, 3); /* cpx/bne/cmp */ |
638 | CS_DelEntry (S, I); /* ldy */ |
639 | |
640 | } else { |
641 | |
642 | CodeEntry* X; |
643 | char Buf[20]; |
644 | |
645 | /* Change the code to just use the A register. Move the load |
646 | ** of the low byte after the first branch if possible: |
647 | ** |
648 | ** ldy #o |
649 | ** lda (sp),y |
650 | ** cmp #a |
651 | ** bne L1 |
652 | ** ldy #o-1 |
653 | ** lda (sp),y |
654 | ** cmp #b |
655 | ** jne/jeq ... |
656 | */ |
657 | X = NewCodeEntry (OP65_LDY, AM65_IMM, L[0]->Arg, 0, L[0]->LI); |
658 | CS_InsertEntry (S, X, I+3); |
659 | |
660 | X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp" , 0, L[1]->LI); |
661 | CS_InsertEntry (S, X, I+4); |
662 | |
663 | X = NewCodeEntry (OP65_CMP, L[2]->AM, L[2]->Arg, 0, L[2]->LI); |
664 | CS_InsertEntry (S, X, I+5); |
665 | |
666 | sprintf (Buf, "$%02X" , (int)(L[0]->Num-1)); |
667 | X = NewCodeEntry (OP65_LDY, AM65_IMM, Buf, 0, L[0]->LI); |
668 | CS_InsertEntry (S, X, I+7); |
669 | |
670 | X = NewCodeEntry (OP65_LDA, AM65_ZP_INDY, "sp" , 0, L[1]->LI); |
671 | CS_InsertEntry (S, X, I+8); |
672 | |
673 | CS_DelEntries (S, I, 3); /* ldy/jsr/cpx */ |
674 | |
675 | } |
676 | |
677 | ++Changes; |
678 | } |
679 | |
680 | /* Next entry */ |
681 | ++I; |
682 | |
683 | } |
684 | |
685 | /* Return the number of changes made */ |
686 | return Changes; |
687 | } |
688 | |
689 | |
690 | |
691 | unsigned OptCmp6 (CodeSeg* S) |
692 | /* Search for calls to compare subroutines followed by a conditional branch |
693 | ** and replace them by cheaper versions, since the branch means that the |
694 | ** boolean value returned by these routines is not needed (we may also check |
695 | ** that explicitly, but for the current code generator it is always true). |
696 | */ |
697 | { |
698 | unsigned Changes = 0; |
699 | |
700 | /* Walk over the entries */ |
701 | unsigned I = 0; |
702 | while (I < CS_GetEntryCount (S)) { |
703 | |
704 | CodeEntry* N; |
705 | cmp_t Cond; |
706 | |
707 | /* Get next entry */ |
708 | CodeEntry* E = CS_GetEntry (S, I); |
709 | |
710 | /* Check for the sequence */ |
711 | if (E->OPC == OP65_JSR && |
712 | (Cond = FindTosCmpCond (E->Arg)) != CMP_INV && |
713 | (N = CS_GetNextEntry (S, I)) != 0 && |
714 | (N->Info & OF_ZBRA) != 0 && |
715 | !CE_HasLabel (N)) { |
716 | |
717 | /* The tos... functions will return a boolean value in a/x and |
718 | ** the Z flag says if this value is zero or not. We will call |
719 | ** a cheaper subroutine instead, one that does not return a |
720 | ** boolean value but only valid flags. Note: jeq jumps if |
721 | ** the condition is not met, jne jumps if the condition is met. |
722 | ** Invert the code if we jump on condition not met. |
723 | */ |
724 | if (GetBranchCond (N->OPC) == BC_EQ) { |
725 | /* Jumps if condition false, invert condition */ |
726 | Cond = CmpInvertTab [Cond]; |
727 | } |
728 | |
729 | /* Replace the subroutine call. */ |
730 | E = NewCodeEntry (OP65_JSR, AM65_ABS, "tosicmp" , 0, E->LI); |
731 | CS_InsertEntry (S, E, I+1); |
732 | CS_DelEntry (S, I); |
733 | |
734 | /* Replace the conditional branch */ |
735 | ReplaceCmp (S, I+1, Cond); |
736 | |
737 | /* Remember, we had changes */ |
738 | ++Changes; |
739 | |
740 | } |
741 | |
742 | /* Next entry */ |
743 | ++I; |
744 | |
745 | } |
746 | |
747 | /* Return the number of changes made */ |
748 | return Changes; |
749 | } |
750 | |
751 | |
752 | |
753 | unsigned OptCmp7 (CodeSeg* S) |
754 | /* Search for a sequence ldx/txa/branch and remove the txa if A is not |
755 | ** used later. |
756 | */ |
757 | { |
758 | unsigned Changes = 0; |
759 | |
760 | /* Walk over the entries */ |
761 | unsigned I = 0; |
762 | while (I < CS_GetEntryCount (S)) { |
763 | |
764 | CodeEntry* L[2]; |
765 | |
766 | /* Get next entry */ |
767 | CodeEntry* E = CS_GetEntry (S, I); |
768 | |
769 | /* Check for the sequence */ |
770 | if ((E->OPC == OP65_LDX) && |
771 | CS_GetEntries (S, L, I+1, 2) && |
772 | L[0]->OPC == OP65_TXA && |
773 | !CE_HasLabel (L[0]) && |
774 | (L[1]->Info & OF_FBRA) != 0 && |
775 | !CE_HasLabel (L[1]) && |
776 | !RegAUsed (S, I+3)) { |
777 | |
778 | /* Remove the txa */ |
779 | CS_DelEntry (S, I+1); |
780 | |
781 | /* Remember, we had changes */ |
782 | ++Changes; |
783 | |
784 | } |
785 | |
786 | /* Next entry */ |
787 | ++I; |
788 | |
789 | } |
790 | |
791 | /* Return the number of changes made */ |
792 | return Changes; |
793 | } |
794 | |
795 | |
796 | |
797 | unsigned OptCmp8 (CodeSeg* S) |
798 | /* Check for register compares where the contents of the register and therefore |
799 | ** the result of the compare is known. |
800 | */ |
801 | { |
802 | unsigned Changes = 0; |
803 | unsigned I; |
804 | |
805 | /* Walk over the entries */ |
806 | I = 0; |
807 | while (I < CS_GetEntryCount (S)) { |
808 | |
809 | int RegVal; |
810 | |
811 | /* Get next entry */ |
812 | CodeEntry* E = CS_GetEntry (S, I); |
813 | |
814 | /* Check for a compare against an immediate value */ |
815 | if ((E->Info & OF_CMP) != 0 && |
816 | (RegVal = GetCmpRegVal (E)) >= 0 && |
817 | CE_IsConstImm (E)) { |
818 | |
819 | /* We are able to evaluate the compare at compile time. Check if |
820 | ** one or more branches are ahead. |
821 | */ |
822 | unsigned ProtectCompare = 0; |
823 | unsigned JumpsChanged = 0; |
824 | CodeEntry* N; |
825 | while ((N = CS_GetNextEntry (S, I)) != 0 && /* Followed by something.. */ |
826 | (N->Info & OF_CBRA) != 0 && /* ..that is a cond branch.. */ |
827 | !CE_HasLabel (N)) { /* ..and has no label */ |
828 | |
829 | /* Evaluate the branch condition */ |
830 | int Cond; |
831 | switch (GetBranchCond (N->OPC)) { |
832 | case BC_CC: |
833 | Cond = ((unsigned char)RegVal) < ((unsigned char)E->Num); |
834 | break; |
835 | |
836 | case BC_CS: |
837 | Cond = ((unsigned char)RegVal) >= ((unsigned char)E->Num); |
838 | break; |
839 | |
840 | case BC_EQ: |
841 | Cond = ((unsigned char)RegVal) == ((unsigned char)E->Num); |
842 | break; |
843 | |
844 | case BC_MI: |
845 | Cond = ((signed char)RegVal) < ((signed char)E->Num); |
846 | break; |
847 | |
848 | case BC_NE: |
849 | Cond = ((unsigned char)RegVal) != ((unsigned char)E->Num); |
850 | break; |
851 | |
852 | case BC_PL: |
853 | Cond = ((signed char)RegVal) >= ((signed char)E->Num); |
854 | break; |
855 | |
856 | case BC_VC: |
857 | case BC_VS: |
858 | /* Not set by the compare operation, bail out (Note: |
859 | ** Just skipping anything here is rather stupid, but |
860 | ** the sequence is never generated by the compiler, |
861 | ** so it's quite safe to skip). |
862 | */ |
863 | goto NextEntry; |
864 | |
865 | default: |
866 | Internal ("Unknown branch condition" ); |
867 | |
868 | } |
869 | |
870 | /* If the condition is false, we may remove the jump. Otherwise |
871 | ** the branch will always be taken, so we may replace it by a |
872 | ** jump (and bail out). |
873 | */ |
874 | if (!Cond) { |
875 | CS_DelEntry (S, I+1); |
876 | } else { |
877 | CodeLabel* L = N->JumpTo; |
878 | const char* LabelName = L? L->Name : N->Arg; |
879 | CodeEntry* X = NewCodeEntry (OP65_JMP, AM65_BRA, LabelName, L, N->LI); |
880 | CS_InsertEntry (S, X, I+2); |
881 | CS_DelEntry (S, I+1); |
882 | /* Normally we can remove the compare as well, |
883 | ** but some comparisons generate code with a |
884 | ** shared branch operation. This prevents the unsafe |
885 | ** removal of the compare for known problem cases. |
886 | */ |
887 | if ( |
888 | /* Jump to branch that relies on the comparison. */ |
889 | (L->Owner->Info & (OF_CBRA | OF_ZBRA)) || |
890 | /* Jump to boolean transformer that relies on the comparison. */ |
891 | (L->Owner->OPC == OP65_JSR && |
892 | (FindBoolCmpCond (L->Owner->Arg)) != CMP_INV) |
893 | ) |
894 | { |
895 | ++ProtectCompare; |
896 | } |
897 | } |
898 | |
899 | /* Remember, we had changes */ |
900 | ++JumpsChanged; |
901 | ++Changes; |
902 | } |
903 | |
904 | /* Delete the original compare, if safe to do so. */ |
905 | if (JumpsChanged && !ProtectCompare) { |
906 | CS_DelEntry (S, I); |
907 | } |
908 | } |
909 | |
910 | NextEntry: |
911 | /* Next entry */ |
912 | ++I; |
913 | |
914 | } |
915 | |
916 | /* Return the number of changes made */ |
917 | return Changes; |
918 | } |
919 | |
920 | |
921 | |
922 | unsigned OptCmp9 (CodeSeg* S) |
923 | /* Search for the sequence |
924 | ** |
925 | ** sbc xx |
926 | ** bvs/bvc L |
927 | ** eor #$80 |
928 | ** L: asl a |
929 | ** bcc/bcs somewhere |
930 | ** |
931 | ** If A is not used later (which should be the case), we can branch on the N |
932 | ** flag instead of the carry flag and remove the asl. |
933 | */ |
934 | { |
935 | unsigned Changes = 0; |
936 | unsigned I; |
937 | |
938 | /* Walk over the entries */ |
939 | I = 0; |
940 | while (I < CS_GetEntryCount (S)) { |
941 | |
942 | CodeEntry* L[5]; |
943 | |
944 | /* Get next entry */ |
945 | L[0] = CS_GetEntry (S, I); |
946 | |
947 | /* Check for the sequence */ |
948 | if (L[0]->OPC == OP65_SBC && |
949 | CS_GetEntries (S, L+1, I+1, 4) && |
950 | (L[1]->OPC == OP65_BVC || |
951 | L[1]->OPC == OP65_BVS) && |
952 | L[1]->JumpTo != 0 && |
953 | L[1]->JumpTo->Owner == L[3] && |
954 | L[2]->OPC == OP65_EOR && |
955 | CE_IsKnownImm (L[2], 0x80) && |
956 | L[3]->OPC == OP65_ASL && |
957 | L[3]->AM == AM65_ACC && |
958 | (L[4]->OPC == OP65_BCC || |
959 | L[4]->OPC == OP65_BCS || |
960 | L[4]->OPC == OP65_JCC || |
961 | L[4]->OPC == OP65_JCS) && |
962 | !CE_HasLabel (L[4]) && |
963 | !RegAUsed (S, I+4)) { |
964 | |
965 | /* Replace the branch condition */ |
966 | switch (GetBranchCond (L[4]->OPC)) { |
967 | case BC_CC: CE_ReplaceOPC (L[4], OP65_JPL); break; |
968 | case BC_CS: CE_ReplaceOPC (L[4], OP65_JMI); break; |
969 | default: Internal ("Unknown branch condition in OptCmp9" ); |
970 | } |
971 | |
972 | /* Delete the asl insn */ |
973 | CS_DelEntry (S, I+3); |
974 | |
975 | /* Next sequence is somewhat ahead (if any) */ |
976 | I += 3; |
977 | |
978 | /* Remember, we had changes */ |
979 | ++Changes; |
980 | } |
981 | |
982 | /* Next entry */ |
983 | ++I; |
984 | } |
985 | |
986 | /* Return the number of changes made */ |
987 | return Changes; |
988 | } |
989 | |