* src/ds390/gen.c (genFarPointerSet),
[fw/sdcc] / src / mcs51 / peep.c
1 /*-------------------------------------------------------------------------
2   peep.c - source file for peephole optimizer helper functions
3
4   Written By -  Bernhard Held
5
6   This program is free software; you can redistribute it and/or modify it
7   under the terms of the GNU General Public License as published by the
8   Free Software Foundation; either version 2, or (at your option) any
9   later version.
10
11   This program is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program; if not, write to the Free Software
18   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19
20   In other words, you are welcome to use, share and improve this program.
21   You are forbidden to forbid anyone else to use, share and improve
22   what you give them.   Help stamp out software-hoarding!
23 -------------------------------------------------------------------------*/
24
25 #include "common.h"
26 #include "ralloc.h"
27
28 #define D(x) x
29 #define DEADMOVEERROR "SDCC internal error: deadmove in " __FILE__" line %d\n", __LINE__
30
31 typedef enum
32 {
33   S4O_FOUNDOPCODE,
34   S4O_PUSHPOP,
35   S4O_CONDJMP,
36   S4O_WR_OP,
37   S4O_RD_OP,
38   S4O_TERM,
39   S4O_VISITED,
40   S4O_ABORT
41 } S4O_RET;
42
43 static struct
44 {
45   lineNode *head;
46 } _G;
47
48 /*-----------------------------------------------------------------*/
49 /* univisitLines - clear "visited" flag in all lines               */
50 /*-----------------------------------------------------------------*/
51 static void
52 unvisitLines (lineNode *pl)
53 {
54   for (; pl; pl = pl->next)
55     pl->visited = FALSE;
56 }
57
58 /*-----------------------------------------------------------------*/
59 /* cleanLabelRef - clear label jump-counter and pass-flag          */
60 /*-----------------------------------------------------------------*/
61 static void
62 cleanLabelRef (void)
63 {
64   int key;
65   labelHashEntry *entry;
66
67   if (!labelHash)
68     return;
69   for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
70        entry;
71        entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
72     {
73       entry->passedLabel = FALSE;
74       entry->jmpToCount = 0;
75     }
76 }
77
78 /*-----------------------------------------------------------------*/
79 /* checkLabelRef - check all entries in labelHash                  */
80 /* The path from 'pop' to 'push' must be the only possible path.   */
81 /* There must not be any paths in or out of this path.             */
82 /* This is checked by counting the label references.               */
83 /*-----------------------------------------------------------------*/
84 static bool
85 checkLabelRef (void)
86 {
87   int key;
88   labelHashEntry *entry;
89
90   if (!labelHash)
91     {
92       /* no labels at all: no problems ;-) */
93       return TRUE;
94     }
95
96   for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
97        entry;
98        entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
99     {
100
101       /* In our path we passed a label,
102          but we didn't meet all references (jumps) to this label.
103          This means that the code jumps from outside into this path. */
104       if (entry->passedLabel &&
105           entry->jmpToCount != entry->refCount)
106         {
107           return FALSE;
108         }
109
110       /* In our path we jumped to (referenced) a label,
111          but we we didn't pass it.
112          This means that there's a code path into our path. */
113       if (!entry->passedLabel &&
114           entry->jmpToCount != 0)
115         {
116           return FALSE;
117         }
118     }
119   return TRUE;
120 }
121
122 /*-----------------------------------------------------------------*/
123 /* setLabelRefPassedLabel - set flag "passedLabel" in entry        */
124 /* of the list labelHash                                           */
125 /*-----------------------------------------------------------------*/
126 static bool
127 setLabelRefPassedLabel (const char *label)
128 {
129   labelHashEntry *entry;
130
131   entry = getLabelRef (label, _G.head);
132   if (!entry)
133     return FALSE;
134   entry->passedLabel = TRUE;
135   return TRUE;
136 }
137
138 /*-----------------------------------------------------------------*/
139 /* incLabelJmpToCount - increment counter "jmpToCount" in entry    */
140 /* of the list labelHash                                           */
141 /*-----------------------------------------------------------------*/
142 static bool
143 incLabelJmpToCount (const char *label)
144 {
145   labelHashEntry *entry;
146
147   entry = getLabelRef (label, _G.head);
148   if (!entry)
149     return FALSE;
150   entry->jmpToCount++;
151   return TRUE;
152 }
153
154 /*-----------------------------------------------------------------*/
155 /* findLabel -                                                     */
156 /* 1. extracts label in the opcode pl                              */
157 /* 2. increment "label jump-to count" in labelHash                 */
158 /* 3. search lineNode with label definition and return it          */
159 /*-----------------------------------------------------------------*/
160 static lineNode *
161 findLabel (const lineNode *pl)
162 {
163   char *p;
164   lineNode *cpl;
165
166   /* 1. extract label in opcode */
167
168   /* In each mcs51 jumping opcode the label is at the end of the opcode */
169   p = strlen (pl->line) - 1 + pl->line;
170
171   /* scan backward until ',' or '\t' */
172   for (; p > pl->line; p--)
173     if (*p == ',' || *p == '\t')
174       break;
175
176   /* sanity check */
177   if (p == pl->line)
178     {
179       D(fprintf (stderr, DEADMOVEERROR);)
180       return NULL;
181     }
182
183   /* skip ',' resp. '\t' */
184   ++p;
185
186   /* 2. increment "label jump-to count" */
187   if (!incLabelJmpToCount (p))
188     return NULL;
189
190   /* 3. search lineNode with label definition and return it */
191   for (cpl = _G.head; cpl; cpl = cpl->next)
192     {
193       if (   cpl->isLabel
194           && strcmp (p, cpl->line) == 0)
195         {
196           return cpl;
197         }
198     }
199   return NULL;
200 }
201
202 /*-----------------------------------------------------------------*/
203 /* isFunc - returns TRUE if it's a CALL or PCALL (not _gptrget())  */
204 /*-----------------------------------------------------------------*/
205 static bool
206 isFunc (const lineNode *pl)
207 {
208   if (pl && pl->ic)
209     {
210       if (   pl->ic->op == CALL
211           || pl->ic->op == PCALL)
212         return TRUE;
213     }
214   return FALSE;
215 }
216
217 /*-----------------------------------------------------------------*/
218 /* isCallerSaveFunc - returns TRUE if it's a 'normal' function     */
219 /* call and it's a 'caller save' (not 'callee save' or 'naked')    */
220 /*-----------------------------------------------------------------*/
221 static bool
222 isCallerSaveFunc (const lineNode *pl)
223 {
224   sym_link *ftype;
225
226   if (!isFunc (pl))
227     return FALSE;
228   // let's assume calls to literally given locations use the default
229   // most notably :  (*(void (*)()) 0) ();  see bug 1749275
230   if (IS_VALOP (IC_LEFT (pl->ic)))
231     return !options.all_callee_saves;
232
233   ftype = OP_SYM_TYPE(IC_LEFT(pl->ic));
234   if (IS_FUNCPTR (ftype))
235     ftype = ftype->next;
236   if (FUNC_CALLEESAVES(ftype))
237     return FALSE;
238   if (FUNC_ISNAKED(ftype))
239     return FALSE;
240   return TRUE;
241 }
242
243 /*-----------------------------------------------------------------*/
244 /* scan4op - "executes" and examines the assembler opcodes,        */
245 /* follows conditional and un-conditional jumps.                   */
246 /* Moreover it registers all passed labels.                        */
247 /*                                                                 */
248 /* Parameter:                                                      */
249 /*    lineNode **pl                                                */
250 /*       scanning starts from pl;                                  */
251 /*       pl also returns the last scanned line                     */
252 /*    const char *pReg                                             */
253 /*       points to a register (e.g. "ar0"). scan4op() tests for    */
254 /*       read or write operations with this register               */
255 /*    const char *untilOp                                          */
256 /*       points to NULL or a opcode (e.g. "push").                 */
257 /*       scan4op() returns if it hits this opcode.                 */
258 /*    lineNode **plCond                                            */
259 /*       If a conditional branch is met plCond points to the       */
260 /*       lineNode of the conditional branch                        */
261 /*                                                                 */
262 /* Returns:                                                        */
263 /*    S4O_ABORT                                                    */
264 /*       on error                                                  */
265 /*    S4O_VISITED                                                  */
266 /*       hit lineNode with "visited" flag set: scan4op() already   */
267 /*       scanned this opcode.                                      */
268 /*    S4O_FOUNDOPCODE                                              */
269 /*       found opcode and operand, to which untilOp and pReg are   */
270 /*       pointing to.                                              */
271 /*    S4O_RD_OP, S4O_WR_OP                                         */
272 /*       hit an opcode reading or writing from pReg                */
273 /*    S4O_PUSHPOP                                                  */
274 /*       hit a "push" or "pop" opcode                              */
275 /*    S4O_CONDJMP                                                  */
276 /*       hit a conditional jump opcode. pl and plCond return the   */
277 /*       two possible branches.                                    */
278 /*    S4O_TERM                                                     */
279 /*       acall, lcall, ret and reti "terminate" a scan.            */
280 /*-----------------------------------------------------------------*/
281 static S4O_RET
282 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
283          lineNode **plCond)
284 {
285   char *p;
286   int len;
287   bool isConditionalJump;
288
289   /* pReg points to e.g. "ar0"..."ar7" */
290   len = strlen (pReg);
291
292   for (; *pl; *pl = (*pl)->next)
293     {
294       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
295         continue;
296
297       /* don't optimize across inline assembler,
298          e.g. isLabel doesn't work there */
299       if ((*pl)->isInline)
300         return S4O_ABORT;
301
302       if ((*pl)->visited)
303         return S4O_VISITED;
304       (*pl)->visited = TRUE;
305
306       /* found untilOp? */
307       if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
308         {
309           p = (*pl)->line + strlen (untilOp);
310           if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
311             return S4O_FOUNDOPCODE;
312           else
313             {
314               /* found untilOp but without our pReg */
315               return S4O_ABORT;
316             }
317         }
318
319       /* found pReg? */
320       p = strchr ((*pl)->line, '\t');
321       if (p)
322         {
323           /* skip '\t' */
324           p++;
325
326           /* course search */
327           if (strstr (p, pReg + 1))
328             {
329               /* ok, let's have a closer look */
330
331               /* get index into pReg table */
332               int rIdx;
333
334               for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
335                 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
336                   break;
337
338               /* sanity check */
339               if (rIdx >= mcs51_nRegs)
340                 {
341                   D(fprintf (stderr, DEADMOVEERROR);)
342                   return S4O_ABORT;
343                 }
344
345               /* does opcode read from pReg? */
346               if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
347                 return S4O_RD_OP;
348               /* does opcode write to pReg? */
349               if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
350                 return S4O_WR_OP;
351
352               /* we can get here, if the register name is
353                  part of a variable name: ignore it */
354             }
355         }
356
357       /* found label? */
358       if ((*pl)->isLabel)
359         {
360           const char *start;
361           char label[SDCC_NAME_MAX + 1];
362           int len;
363
364           if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
365             return S4O_ABORT;
366           memcpy (label, start, len);
367           label[len] = '\0';
368           /* register passing this label */
369           if (!setLabelRefPassedLabel (label))
370             {
371               D(fprintf (stderr, DEADMOVEERROR);)
372               return S4O_ABORT;
373             }
374           continue;
375         }
376
377       /* branch or terminate? */
378       isConditionalJump = FALSE;
379       switch ((*pl)->line[0])
380         {
381           case 'a':
382             if (strncmp ("acall", (*pl)->line, 5) == 0)
383               {
384                 /* for comments see 'lcall' */
385                 if (isCallerSaveFunc (*pl))
386                   return S4O_TERM;
387                 break;
388               }
389             if (strncmp ("ajmp", (*pl)->line, 4) == 0)
390               {
391                 *pl = findLabel (*pl);
392                 if (!*pl)
393                   return S4O_ABORT;
394               }
395             break;
396           case 'c':
397             if (strncmp ("cjne", (*pl)->line, 4) == 0)
398               {
399                 isConditionalJump = TRUE;
400                 break;
401               }
402             break;
403           case 'd':
404             if (strncmp ("djnz", (*pl)->line, 4) == 0)
405               {
406                 isConditionalJump = TRUE;
407                 break;
408               }
409             break;
410           case 'j':
411             if (strncmp ("jmp", (*pl)->line, 3) == 0)
412               /* "jmp @a+dptr": no chance to trace execution */
413               return S4O_ABORT;
414             if (strncmp ("jc",  (*pl)->line, 2) == 0 ||
415                 strncmp ("jnc", (*pl)->line, 3) == 0 ||
416                 strncmp ("jz",  (*pl)->line, 2) == 0 ||
417                 strncmp ("jnz", (*pl)->line, 3) == 0)
418               {
419                 isConditionalJump = TRUE;
420                 break;
421               }
422             if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
423                 strncmp ("jb",  (*pl)->line, 2) == 0 ||
424                 strncmp ("jnb", (*pl)->line, 3) == 0)
425               {
426                 isConditionalJump = TRUE;
427                 break;
428               }
429             break;
430           case 'l':
431             if (strncmp ("lcall", (*pl)->line, 5) == 0)
432               {
433                 if (isCallerSaveFunc (*pl))
434                   {
435                     /* If it's a 'normal' 'caller save' function call, all
436                        registers have been saved until the 'lcall'. The
437                        'life range' of all registers end at the lcall,
438                        and we can terminate our search.
439                     */
440                     return S4O_TERM;
441                   }
442                 /* If it's a 'callee save' function call, registers are saved
443                    by the callee. We've got no information, if the register
444                    might live beyond the lcall. Therefore we've to continue
445                    the search.
446                 */
447                 break;
448               }
449             if (strncmp ("ljmp", (*pl)->line, 4) == 0)
450               {
451                 *pl = findLabel (*pl);
452                 if (!*pl)
453                   return S4O_ABORT;
454               }
455             break;
456           case 'p':
457             if (strncmp ("pop", (*pl)->line, 3) == 0 ||
458                 strncmp ("push", (*pl)->line, 4) == 0)
459               return S4O_PUSHPOP;
460             break;
461           case 'r':
462             if (strncmp ("reti", (*pl)->line, 4) == 0)
463               return S4O_TERM;
464
465             if (strncmp ("ret", (*pl)->line, 3) == 0)
466               {
467                 /* pcall uses 'ret' */
468                 if (isFunc (*pl))
469                   {
470                     /* for comments see 'lcall' */
471                     if (isCallerSaveFunc (*pl))
472                       return S4O_TERM;
473                     break;
474                   }
475
476                 /* it's a normal function return */
477                 return S4O_TERM;
478               }
479             break;
480           case 's':
481             if (strncmp ("sjmp", (*pl)->line, 4) == 0)
482               {
483                 *pl = findLabel (*pl);
484                 if (!*pl)
485                   return S4O_ABORT;
486               }
487             break;
488           default:
489             break;
490         } /* switch ((*pl)->line[0]) */
491
492       if (isConditionalJump)
493         {
494           *plCond = findLabel (*pl);
495           if (!*plCond)
496             return S4O_ABORT;
497           return S4O_CONDJMP;
498         }
499     } /* for (; *pl; *pl = (*pl)->next) */
500   return S4O_ABORT;
501 }
502
503 /*-----------------------------------------------------------------*/
504 /* doPushScan - scan through area 1. This small wrapper handles:   */
505 /* - action required on different return values                    */
506 /* - recursion in case of conditional branches                     */
507 /*-----------------------------------------------------------------*/
508 static bool
509 doPushScan (lineNode **pl, const char *pReg)
510 {
511   lineNode *plConditional, *pushPl = NULL;
512
513   for (;; *pl = (*pl)->next)
514     {
515       switch (scan4op (pl, pReg, "push", &plConditional))
516         {
517           case S4O_FOUNDOPCODE:
518             /* this is what we're looking for */
519             return TRUE;
520           case S4O_VISITED:
521             if (!pushPl)
522               {
523                 D(fprintf (stderr, DEADMOVEERROR);)
524                 return FALSE;
525               }
526             *pl = pushPl;
527             /* already checked */
528             return TRUE;
529           case S4O_CONDJMP:
530             /* two possible destinations: recurse */
531               {
532                 lineNode *pushPl2 = plConditional;
533
534                 if (!doPushScan (&pushPl2, pReg))
535                   return FALSE;
536                 pushPl = pushPl2;
537               }
538             continue;
539           default:
540             return FALSE;
541         }
542     }
543 }
544
545 /*-----------------------------------------------------------------*/
546 /* doTermScan - scan through area 2. This small wrapper handles:   */
547 /* - action required on different return values                    */
548 /* - recursion in case of conditional branches                     */
549 /*-----------------------------------------------------------------*/
550 static bool
551 doTermScan (lineNode **pl, const char *pReg)
552 {
553   lineNode *plConditional;
554
555   for (;; *pl = (*pl)->next)
556     {
557       switch (scan4op (pl, pReg, NULL, &plConditional))
558         {
559           case S4O_TERM:
560           case S4O_VISITED:
561           case S4O_WR_OP:
562             /* all these are terminating condtions */
563             return TRUE;
564           case S4O_PUSHPOP:
565             /* don't care, go on */
566             continue;
567           case S4O_CONDJMP:
568             /* two possible destinations: recurse */
569               {
570                 lineNode *pl2 = plConditional;
571
572                 if (!doTermScan (&pl2, pReg))
573                   return FALSE;
574               }
575             continue;
576           case S4O_RD_OP:
577           default:
578             /* no go */
579             return FALSE;
580         }
581     }
582 }
583
584 /*-----------------------------------------------------------------*/
585 /* removeDeadPopPush - remove pop/push pair if possible            */
586 /*-----------------------------------------------------------------*/
587 static bool
588 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
589 {
590   lineNode *pushPl, *pl;
591
592   /* A pop/push pair can be removed, if these criteria are met
593      (ar0 is just an example here, ar0...ar7 are possible):
594
595      pop ar0
596
597       ; area 1
598
599       ; There must not be in area 1:
600       ;    - read or write access of ar0
601       ;    - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
602       ;    - "push" opcode, which doesn't push ar0 
603       ;    - inline assembly
604       ;    - a jump in or out of area 1 (see checkLabelRef())
605
606       ; Direct manipulation of sp is not detected. This isn't necessary
607       ; as long as sdcc doesn't emit such code in area 1.
608
609       ; area 1 must be terminated by a:
610      push ar0
611
612       ; area 2
613
614       ; There must not be:
615       ;    - read access of ar0
616       ;    - "jmp @a+dptr" opcode
617       ;    - inline assembly
618       ;    - a jump in or out of area 2 (see checkLabelRef())
619
620       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
621       ; callee save), "reti" or write access of r0 terminate
622       ; the search, and the "mov r0,a" can safely be removed.
623   */
624
625   /* area 1 */
626   pushPl = currPl->next;
627   if (!doPushScan (&pushPl, pReg))
628     return FALSE;
629
630   if (!checkLabelRef())
631     return FALSE;
632
633   /* area 2 */
634   pl = pushPl->next;
635   if (!doTermScan (&pl, pReg))
636     return FALSE;
637   if (!checkLabelRef())
638     return FALSE;
639
640   /* Success! */
641   if (options.noPeepComments)
642     {
643       /* remove pushPl from list */
644       pushPl->prev->next = pushPl->next;
645       pushPl->next->prev = pushPl->prev;
646     }
647   else
648     {
649       /* replace 'push ar0' by comment */
650       #define STR ";\tPeephole\tpush %s removed"
651       int size = sizeof(STR) + 2;
652
653       pushPl->line = Safe_alloc (size);
654       SNPRINTF (pushPl->line, size, STR, pReg);
655       pushPl->isComment = TRUE;
656     }
657
658   /* 'pop ar0' will be removed by peephole framework after returning TRUE */
659   return TRUE;
660 }
661
662 /*-----------------------------------------------------------------*/
663 /* removeDeadMove - remove superflous 'mov r%1,%2'                 */
664 /*-----------------------------------------------------------------*/
665 static bool
666 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
667 {
668   lineNode *pl;
669
670   /* "mov r0,a" can be removed, if these criteria are met
671      (r0 is just an example here, r0...r7 are possible):
672
673       ; There must not be:
674       ;    - read access of r0
675       ;    - "jmp @a+dptr" opcode
676       ;    - inline assembly
677       ;    - a jump in or out of this area (see checkLabelRef())
678
679       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
680       ; callee save), "reti" or write access of r0 terminate
681       ; the search, and the "mov r0,a" can safely be removed.
682   */
683   pl = currPl->next;
684   if (!doTermScan (&pl, pReg))
685     return FALSE;
686
687   if (!checkLabelRef())
688     return FALSE;
689
690   return TRUE;
691 }
692
693 /*-----------------------------------------------------------------*/
694 /* mcs51DeadMove - dispatch condition deadmove between             */
695 /* - remove pop/push                                               */
696 /* - remove mov r%1,%2                                             */
697 /*-----------------------------------------------------------------*/
698 bool
699 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
700 {
701   char pReg[5] = "ar";
702
703   _G.head = head;
704   strcat (pReg, reg);
705
706   unvisitLines (_G.head);
707   cleanLabelRef();
708
709   if (strncmp (currPl->line, "pop", 3) == 0)
710     return removeDeadPopPush (pReg, currPl, head);
711   else if (   strncmp (currPl->line, "mov", 3) == 0
712            && (currPl->line[3] == ' ' || currPl->line[3] == '\t'))
713     return removeDeadMove (pReg, currPl, head);
714   else
715     {
716       fprintf (stderr, "Error: "
717                        "peephole rule with condition deadMove "
718                        "used with unknown opocde:\n"
719                        "\t%s\n", currPl->line);
720       return FALSE;
721     }
722 }