Added peephole to replace LJMP to RET with just a RET instruction
[fw/sdcc] / src / SDCCpeeph.c
1 /*-------------------------------------------------------------------------
2   SDCCpeeph.c - The peep hole optimizer: for interpreting the
3                 peep hole rules
4
5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1999)
6
7    This program is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by the
9    Free Software Foundation; either version 2, or (at your option) any
10    later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program; if not, write to the Free Software
19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20
21    In other words, you are welcome to use, share and improve this program.
22    You are forbidden to forbid anyone else to use, share and improve
23    what you give them.   Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
25
26 #include "common.h"
27
28 static peepRule *rootRules = NULL;
29 static peepRule *currRule = NULL;
30
31 #define HTAB_SIZE 53
32 typedef struct
33   {
34     char name[SDCC_NAME_MAX + 1];
35     int refCount;
36   }
37 labelHashEntry;
38
39 static hTab *labelHash = NULL;
40
41 static struct
42 {
43   allocTrace values;
44   allocTrace labels;
45 } _G;
46
47 static int hashSymbolName (const char *name);
48 static void buildLabelRefCountHash (lineNode * head);
49
50 static bool matchLine (char *, char *, hTab **);
51
52 #define FBYNAME(x) int x (hTab *vars, lineNode *currPl, lineNode *head, \
53         const char *cmdLine)
54
55 #if !OPT_DISABLE_PIC
56 void  peepRules2pCode(peepRule *);
57 #endif
58
59 /*-----------------------------------------------------------------*/
60 /* pcDistance - afinds a label back ward or forward                */
61 /*-----------------------------------------------------------------*/
62 int
63 mcs51_instruction_size(const char *inst)
64 {
65         char *op, op1[256], op2[256];
66         int opsize;
67         const char *p;
68
69         while (*inst && isspace(*inst)) inst++;
70
71         #define ISINST(s) (strncmp(inst, (s), sizeof(s)-1) == 0)
72         if (ISINST("lcall")) return 3;
73         if (ISINST("ret")) return 1;
74         if (ISINST("ljmp")) return 3;
75         if (ISINST("sjmp")) return 2;
76         if (ISINST("rlc")) return 1;
77         if (ISINST("rrc")) return 1;
78         if (ISINST("rl")) return 1;
79         if (ISINST("rr")) return 1;
80         if (ISINST("swap")) return 1;
81         if (ISINST("movx")) return 1;
82         if (ISINST("movc")) return 1;
83         if (ISINST("push")) return 2;
84         if (ISINST("pop")) return 2;
85         if (ISINST("jc")) return 2;
86         if (ISINST("jnc")) return 2;
87         if (ISINST("jb")) return 3;
88         if (ISINST("jnb")) return 3;
89         if (ISINST("jbc")) return 3;
90         if (ISINST("jmp")) return 1;    // always jmp @a+dptr
91         if (ISINST("jz")) return 2;
92         if (ISINST("jnz")) return 2;
93         if (ISINST("cjne")) return 3;
94         if (ISINST("mul")) return 1;
95         if (ISINST("div")) return 1;
96         if (ISINST("da")) return 1;
97         if (ISINST("xchd")) return 1;
98         if (ISINST("reti")) return 1;
99         if (ISINST("nop")) return 1;
100         if (ISINST("acall")) return 1;
101         if (ISINST("ajmp")) return 2;
102
103         p = inst;
104         while (*p && isalnum(*p)) p++;
105         for (op = op1, opsize=0; *p && *p != ',' && opsize < sizeof(op1); p++) {
106                 if (!isspace(*p)) *op++ = *p, opsize++;
107         }
108         *op = '\0';
109         if (*p == ',') p++;
110         for (op = op2, opsize=0; *p && *p != ',' && opsize < sizeof(op2); p++) {
111                 if (!isspace(*p)) *op++ = *p, opsize++;
112         }
113         *op = '\0';
114
115         #define IS_A(s) (*(s) == 'a' && *(s+1) == '\0')
116         #define IS_C(s) (*(s) == 'c' && *(s+1) == '\0')
117         #define IS_Rn(s) (*(s) == 'r' && *(s+1) >= '0' && *(s+1) <= '7')
118         #define IS_atRi(s) (*(s) == '@' && *(s+1) == 'r')
119
120         if (ISINST("mov")) {
121                 if (IS_C(op1) || IS_C(op2)) return 2;
122                 if (IS_A(op1)) {
123                         if (IS_Rn(op2) || IS_atRi(op2)) return 1;
124                         return 2;
125                 }
126                 if (IS_Rn(op1) || IS_atRi(op1)) {
127                         if (IS_A(op2)) return 1;
128                         return 2;
129                 }
130                 if (strcmp(op1, "dptr") == 0) return 3;
131                 if (IS_A(op2) || IS_Rn(op2) || IS_atRi(op2)) return 2;
132                 return 3;
133         }
134         if (ISINST("add") || ISINST("addc") || ISINST("subb") || ISINST("xch")) {
135                 if (IS_Rn(op2) || IS_atRi(op2)) return 1;
136                 return 2;
137         }
138         if (ISINST("inc") || ISINST("dec")) {
139                 if (IS_A(op1) || IS_Rn(op1) || IS_atRi(op1)) return 1;
140                 if (strcmp(op1, "dptr") == 0) return 1;
141                 return 2;
142         }
143         if (ISINST("anl") || ISINST("orl") || ISINST("xrl")) {
144                 if (IS_C(op1)) return 2;
145                 if (IS_A(op1)) {
146                         if (IS_Rn(op2) || IS_atRi(op2)) return 1;
147                         return 2;
148                 } else {
149                         if (IS_A(op2)) return 2;
150                         return 3;
151                 }
152         }
153         if (ISINST("clr") || ISINST("setb") || ISINST("cpl")) {
154                 if (IS_A(op1) || IS_C(op1)) return 1;
155                 return 2;
156         }
157         if (ISINST("djnz")) {
158                 if (IS_Rn(op1)) return 2;
159                 return 3;
160         }
161
162         if (*inst == 'a' && *(inst+1) == 'r' && *(inst+2) >= '0' && *(inst+2) <= '7' && op1[0] == '=') {
163                 /* ignore ar0 = 0x00 type definitions */
164                 return 0;
165         }
166
167         fprintf(stderr, "Warning, peephole unrecognized instruction: %s\n", inst);
168         return 3;
169 }
170
171 int 
172 pcDistance (lineNode * cpos, char *lbl, bool back)
173 {
174   lineNode *pl = cpos;
175   char buff[MAX_PATTERN_LEN];
176   int dist = 0;
177
178   SNPRINTF (buff, sizeof(buff), "%s:", lbl);
179   while (pl)
180     {
181
182       if (pl->line &&
183           *pl->line != ';' &&
184           pl->line[strlen (pl->line) - 1] != ':' &&
185           !pl->isDebug) {
186                 if (strcmp(port->target,"mcs51") == 0) {
187                         dist += mcs51_instruction_size(pl->line);
188                 } else {
189                         dist += 3;
190                 }
191         }
192
193       if (strncmp (pl->line, buff, strlen (buff)) == 0)
194         return dist;
195
196       if (back)
197         pl = pl->prev;
198       else
199         pl = pl->next;
200
201     }
202   return 0;
203 }
204
205 /*-----------------------------------------------------------------*/
206 /* flat24bitModeAndPortDS390 -                                     */
207 /*-----------------------------------------------------------------*/
208 FBYNAME (flat24bitModeAndPortDS390)
209 {
210     return ((strcmp(port->target,"ds390") == 0) && 
211             (options.model == MODEL_FLAT24));
212 }
213
214 /*-----------------------------------------------------------------*/
215 /* portIsDS390 - return true if port is DS390                      */
216 /*-----------------------------------------------------------------*/
217 FBYNAME (portIsDS390)
218 {
219     return (strcmp(port->target,"ds390") == 0);
220 }
221
222 /*-----------------------------------------------------------------*/
223 /* flat24bitMode - will check to see if we are in flat24 mode      */
224 /*-----------------------------------------------------------------*/
225 FBYNAME (flat24bitMode)
226 {
227   return (options.model == MODEL_FLAT24);
228 }
229
230 /*-----------------------------------------------------------------*/
231 /* xramMovcOption - check if using movc to read xram               */
232 /*-----------------------------------------------------------------*/
233 FBYNAME (xramMovcOption)
234 {
235   return (options.xram_movc && (strcmp(port->target,"mcs51") == 0));
236 }
237
238
239
240
241
242
243 /*-----------------------------------------------------------------*/
244 /* labelInRange - will check to see if label %5 is within range    */
245 /*-----------------------------------------------------------------*/
246 FBYNAME (labelInRange)
247 {
248   /* assumes that %5 pattern variable has the label name */
249   char *lbl = hTabItemWithKey (vars, 5);
250   int dist = 0;
251
252   if (!lbl)
253     return FALSE;
254
255   /* if the previous two instructions are "ljmp"s then don't
256      do it since it can be part of a jump table */
257   if (currPl->prev && currPl->prev->prev &&
258       strstr (currPl->prev->line, "ljmp") &&
259       strstr (currPl->prev->prev->line, "ljmp"))
260     return FALSE;
261
262   /* calculate the label distance : the jump for reladdr can be
263      +/- 127 bytes, here Iam assuming that an average 8051
264      instruction is 2 bytes long, so if the label is more than
265      63 intructions away, the label is considered out of range
266      for a relative jump. we could get more precise this will
267      suffice for now since it catches > 90% cases */
268   dist = (pcDistance (currPl, lbl, TRUE) +
269           pcDistance (currPl, lbl, FALSE));
270
271 /*    changed to 127, now that pcDistance return actual number of bytes */
272   if (!dist || dist > 127)
273     return FALSE;
274
275   return TRUE;
276 }
277
278 /*-----------------------------------------------------------------*/
279 /* labelIsReturnOnly - Check if label %5 is followed by RET        */
280 /*-----------------------------------------------------------------*/
281 FBYNAME (labelIsReturnOnly)
282 {
283   /* assumes that %5 pattern variable has the label name */
284   const char *label, *p;
285   const lineNode *pl;
286   int len;
287
288   label = hTabItemWithKey (vars, 5);
289   if (!label) return FALSE;
290   len = strlen(label);
291
292   for(pl = currPl; pl; pl = pl->next) {
293         if (pl->line && !pl->isDebug &&
294           pl->line[strlen(pl->line)-1] == ':') {
295                 if (strncmp(pl->line, label, len) == 0) break; /* Found Label */
296                 if (strlen(pl->line) != 7 || !isdigit(*(pl->line)) ||
297                   !isdigit(*(pl->line+1)) || !isdigit(*(pl->line+2)) ||
298                   !isdigit(*(pl->line+3)) || !isdigit(*(pl->line+4)) ||
299                   *(pl->line+5) != '$') {
300                         return FALSE; /* non-local label encountered */
301                 }
302         }
303   }
304   if (!pl) return FALSE; /* did not find the label */
305   pl = pl->next;
306   if (!pl || !pl->line || pl->isDebug) return FALSE; /* next line not valid */
307   p = pl->line;
308   for (p = pl->line; *p && isspace(*p); p++)
309           ;
310   if (strcmp(p, "ret") == 0) return TRUE;
311   return FALSE;
312 }
313
314
315
316 /*-----------------------------------------------------------------*/
317 /* operandsNotSame - check if %1 & %2 are the same                 */
318 /*-----------------------------------------------------------------*/
319 FBYNAME (operandsNotSame)
320 {
321   char *op1 = hTabItemWithKey (vars, 1);
322   char *op2 = hTabItemWithKey (vars, 2);
323
324   if (strcmp (op1, op2) == 0)
325     return FALSE;
326   else
327     return TRUE;
328 }
329
330 /*-----------------------------------------------------------------*/
331 /* operandsNotSame3- check if any pair of %1,%2,%3 are the same    */
332 /*-----------------------------------------------------------------*/
333 FBYNAME (operandsNotSame3)
334 {
335   char *op1 = hTabItemWithKey (vars, 1);
336   char *op2 = hTabItemWithKey (vars, 2);
337   char *op3 = hTabItemWithKey (vars, 3);
338
339   if ( (strcmp (op1, op2) == 0) ||
340        (strcmp (op1, op3) == 0) ||
341        (strcmp (op2, op3) == 0) )
342     return FALSE;
343   else
344     return TRUE;
345 }
346
347 /*-----------------------------------------------------------------*/
348 /* operandsNotSame4- check if any pair of %1,%2,%3,.. are the same */
349 /*-----------------------------------------------------------------*/
350 FBYNAME (operandsNotSame4)
351 {
352   char *op1 = hTabItemWithKey (vars, 1);
353   char *op2 = hTabItemWithKey (vars, 2);
354   char *op3 = hTabItemWithKey (vars, 3);
355   char *op4 = hTabItemWithKey (vars, 4);
356
357   if ( (strcmp (op1, op2) == 0) ||
358        (strcmp (op1, op3) == 0) ||
359        (strcmp (op1, op4) == 0) ||
360        (strcmp (op2, op3) == 0) ||
361        (strcmp (op2, op4) == 0) ||
362        (strcmp (op3, op4) == 0) )
363     return FALSE;
364   else
365     return TRUE;
366 }
367
368 /*-----------------------------------------------------------------*/
369 /* operandsNotSame5- check if any pair of %1,%2,%3,.. are the same */
370 /*-----------------------------------------------------------------*/
371 FBYNAME (operandsNotSame5)
372 {
373   char *op1 = hTabItemWithKey (vars, 1);
374   char *op2 = hTabItemWithKey (vars, 2);
375   char *op3 = hTabItemWithKey (vars, 3);
376   char *op4 = hTabItemWithKey (vars, 4);
377   char *op5 = hTabItemWithKey (vars, 5);
378
379   if ( (strcmp (op1, op2) == 0) ||
380        (strcmp (op1, op3) == 0) ||
381        (strcmp (op1, op4) == 0) ||
382        (strcmp (op1, op5) == 0) ||
383        (strcmp (op2, op3) == 0) ||
384        (strcmp (op2, op4) == 0) ||
385        (strcmp (op2, op5) == 0) ||
386        (strcmp (op3, op4) == 0) ||
387        (strcmp (op3, op5) == 0) ||
388        (strcmp (op4, op5) == 0) )
389     return FALSE;
390   else
391     return TRUE;
392 }
393
394 /*-----------------------------------------------------------------*/
395 /* operandsNotSame6- check if any pair of %1,%2,%3,.. are the same */
396 /*-----------------------------------------------------------------*/
397 FBYNAME (operandsNotSame6)
398 {
399   char *op1 = hTabItemWithKey (vars, 1);
400   char *op2 = hTabItemWithKey (vars, 2);
401   char *op3 = hTabItemWithKey (vars, 3);
402   char *op4 = hTabItemWithKey (vars, 4);
403   char *op5 = hTabItemWithKey (vars, 5);
404   char *op6 = hTabItemWithKey (vars, 6);
405
406   if ( (strcmp (op1, op2) == 0) ||
407        (strcmp (op1, op3) == 0) ||
408        (strcmp (op1, op4) == 0) ||
409        (strcmp (op1, op5) == 0) ||
410        (strcmp (op1, op6) == 0) ||
411        (strcmp (op2, op3) == 0) ||
412        (strcmp (op2, op4) == 0) ||
413        (strcmp (op2, op5) == 0) ||
414        (strcmp (op2, op6) == 0) ||
415        (strcmp (op3, op4) == 0) ||
416        (strcmp (op3, op5) == 0) ||
417        (strcmp (op3, op6) == 0) ||
418        (strcmp (op4, op5) == 0) ||
419        (strcmp (op4, op6) == 0) ||
420        (strcmp (op5, op6) == 0) )
421     return FALSE;
422   else
423     return TRUE;
424 }
425
426
427 /*-----------------------------------------------------------------*/
428 /* operandsNotSame7- check if any pair of %1,%2,%3,.. are the same */
429 /*-----------------------------------------------------------------*/
430 FBYNAME (operandsNotSame7)
431 {
432   char *op1 = hTabItemWithKey (vars, 1);
433   char *op2 = hTabItemWithKey (vars, 2);
434   char *op3 = hTabItemWithKey (vars, 3);
435   char *op4 = hTabItemWithKey (vars, 4);
436   char *op5 = hTabItemWithKey (vars, 5);
437   char *op6 = hTabItemWithKey (vars, 6);
438   char *op7 = hTabItemWithKey (vars, 7);
439
440   if ( (strcmp (op1, op2) == 0) ||
441        (strcmp (op1, op3) == 0) ||
442        (strcmp (op1, op4) == 0) ||
443        (strcmp (op1, op5) == 0) ||
444        (strcmp (op1, op6) == 0) ||
445        (strcmp (op1, op7) == 0) ||
446        (strcmp (op2, op3) == 0) ||
447        (strcmp (op2, op4) == 0) ||
448        (strcmp (op2, op5) == 0) ||
449        (strcmp (op2, op6) == 0) ||
450        (strcmp (op2, op7) == 0) ||
451        (strcmp (op3, op4) == 0) ||
452        (strcmp (op3, op5) == 0) ||
453        (strcmp (op3, op6) == 0) ||
454        (strcmp (op3, op7) == 0) ||
455        (strcmp (op4, op5) == 0) ||
456        (strcmp (op4, op6) == 0) ||
457        (strcmp (op4, op7) == 0) ||
458        (strcmp (op5, op6) == 0) ||
459        (strcmp (op5, op7) == 0) ||
460        (strcmp (op6, op7) == 0) )
461     return FALSE;
462   else
463     return TRUE;
464 }
465
466 /*-----------------------------------------------------------------*/
467 /* operandsNotSame8- check if any pair of %1,%2,%3,.. are the same */
468 /*-----------------------------------------------------------------*/
469 FBYNAME (operandsNotSame8)
470 {
471   char *op1 = hTabItemWithKey (vars, 1);
472   char *op2 = hTabItemWithKey (vars, 2);
473   char *op3 = hTabItemWithKey (vars, 3);
474   char *op4 = hTabItemWithKey (vars, 4);
475   char *op5 = hTabItemWithKey (vars, 5);
476   char *op6 = hTabItemWithKey (vars, 6);
477   char *op7 = hTabItemWithKey (vars, 7);
478   char *op8 = hTabItemWithKey (vars, 8);
479
480   if ( (strcmp (op1, op2) == 0) ||
481        (strcmp (op1, op3) == 0) ||
482        (strcmp (op1, op4) == 0) ||
483        (strcmp (op1, op5) == 0) ||
484        (strcmp (op1, op6) == 0) ||
485        (strcmp (op1, op7) == 0) ||
486        (strcmp (op1, op8) == 0) ||
487        (strcmp (op2, op3) == 0) ||
488        (strcmp (op2, op4) == 0) ||
489        (strcmp (op2, op5) == 0) ||
490        (strcmp (op2, op6) == 0) ||
491        (strcmp (op2, op7) == 0) ||
492        (strcmp (op2, op8) == 0) ||
493        (strcmp (op3, op4) == 0) ||
494        (strcmp (op3, op5) == 0) ||
495        (strcmp (op3, op6) == 0) ||
496        (strcmp (op3, op7) == 0) ||
497        (strcmp (op3, op8) == 0) ||
498        (strcmp (op4, op5) == 0) ||
499        (strcmp (op4, op6) == 0) ||
500        (strcmp (op4, op7) == 0) ||
501        (strcmp (op4, op8) == 0) ||
502        (strcmp (op5, op6) == 0) ||
503        (strcmp (op5, op7) == 0) ||
504        (strcmp (op5, op8) == 0) ||
505        (strcmp (op6, op7) == 0) ||
506        (strcmp (op6, op8) == 0) ||
507        (strcmp (op7, op8) == 0) )
508     return FALSE;
509   else
510     return TRUE;
511 }
512
513
514 /* labelRefCount:
515
516  * takes two parameters: a variable (bound to a label name)
517  * and an expected reference count.
518  *
519  * Returns TRUE if that label is defined and referenced exactly
520  * the given number of times.
521  */
522 FBYNAME (labelRefCount)
523 {
524   int varNumber, expectedRefCount;
525   bool rc = FALSE;
526
527   /* If we don't have the label hash table yet, build it. */
528   if (!labelHash)
529     {
530       buildLabelRefCountHash (head);
531     }
532
533   if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
534     {
535       char *label = hTabItemWithKey (vars, varNumber);
536
537       if (label)
538         {
539           labelHashEntry *entry;
540
541           entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
542
543           while (entry)
544             {
545               if (!strcmp (label, entry->name))
546                 {
547                   break;
548                 }
549               entry = hTabNextItemWK (labelHash);
550             }
551           if (entry)
552             {
553 #if 0
554               /* debug spew. */
555               fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
556                        label, entry->refCount, expectedRefCount);
557 #endif
558
559               rc = (expectedRefCount == entry->refCount);
560             }
561           else
562             {
563               fprintf (stderr, "*** internal error: no label has entry for"
564                        " %s in labelRefCount peephole.\n",
565                        label);
566             }
567         }
568       else
569         {
570           fprintf (stderr, "*** internal error: var %d not bound"
571                    " in peephole labelRefCount rule.\n",
572                    varNumber);
573         }
574
575     }
576   else
577     {
578       fprintf (stderr,
579                "*** internal error: labelRefCount peephole restriction"
580                " malformed: %s\n", cmdLine);
581     }
582   return rc;
583 }
584
585 /*-----------------------------------------------------------------*/
586 /* callFuncByName - calls a function as defined in the table       */
587 /*-----------------------------------------------------------------*/
588 int 
589 callFuncByName (char *fname,
590                 hTab * vars,
591                 lineNode * currPl,
592                 lineNode * head)
593 {
594   struct ftab
595   {
596     char *fname;
597     int (*func) (hTab *, lineNode *, lineNode *, const char *);
598   }
599   ftab[] =
600   {
601     {
602       "labelInRange", labelInRange
603     }
604     ,
605     {
606       "operandsNotSame", operandsNotSame
607     }
608     ,
609     {
610       "operandsNotSame3", operandsNotSame3
611     }
612     ,
613     {
614       "operandsNotSame4", operandsNotSame4
615     }
616     ,
617     {
618       "operandsNotSame5", operandsNotSame5
619     }
620     ,
621     {
622       "operandsNotSame6", operandsNotSame6
623     }
624     ,
625     {
626       "operandsNotSame7", operandsNotSame7
627     }
628     ,
629     {
630       "operandsNotSame8", operandsNotSame8
631     }
632     ,     
633     {
634       "24bitMode", flat24bitMode
635     }
636     ,
637     {
638       "xramMovcOption", xramMovcOption
639     }
640     ,
641     {
642       "labelRefCount", labelRefCount
643     }
644     ,
645     {
646       "portIsDS390", portIsDS390
647     },
648     {
649       "labelIsReturnOnly", labelIsReturnOnly
650     },
651     {
652       "24bitModeAndPortDS390", flat24bitModeAndPortDS390
653     }
654   };
655   int   i;
656   char  *cmdCopy, *funcName, *funcArgs;
657   int   rc = -1;
658     
659   /* Isolate the function name part (we are passed the full condition 
660    * string including arguments) 
661    */
662   cmdCopy = Safe_strdup(fname);
663   funcName = strtok(cmdCopy, " \t");
664   funcArgs = strtok(NULL, "");
665
666     for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
667     {
668         if (strcmp (ftab[i].fname, funcName) == 0)
669         {
670             rc = (*ftab[i].func) (vars, currPl, head,
671                                   funcArgs);
672         }
673     }
674     
675     Safe_free(cmdCopy);
676     
677     if (rc == -1)
678     {
679         fprintf (stderr, 
680                  "could not find named function \"%s\" in "
681                  "peephole function table\n",
682                  funcName);
683         // If the function couldn't be found, let's assume it's
684         // a bad rule and refuse it.
685         rc = FALSE;
686     }
687     
688   return rc;
689 }
690
691 /*-----------------------------------------------------------------*/
692 /* printLine - prints a line chain into a given file               */
693 /*-----------------------------------------------------------------*/
694 void 
695 printLine (lineNode * head, FILE * of)
696 {
697   if (!of)
698     of = stdout;
699
700   while (head)
701     {
702       /* don't indent comments & labels */
703       if (head->line &&
704           (*head->line == ';' ||
705            head->line[strlen (head->line) - 1] == ':')) {
706         fprintf (of, "%s\n", head->line);
707       } else {
708         if (head->isInline && *head->line=='#') {
709           // comment out preprocessor directives in inline asm
710           fprintf (of, ";");
711         }
712         fprintf (of, "\t%s\n", head->line);
713       }
714       head = head->next;
715     }
716 }
717
718 /*-----------------------------------------------------------------*/
719 /* newPeepRule - creates a new peeprule and attach it to the root  */
720 /*-----------------------------------------------------------------*/
721 peepRule *
722 newPeepRule (lineNode * match,
723              lineNode * replace,
724              char *cond,
725              int restart)
726 {
727   peepRule *pr;
728
729   pr = Safe_alloc ( sizeof (peepRule));
730   pr->match = match;
731   pr->replace = replace;
732   pr->restart = restart;
733
734   if (cond && *cond)
735     {
736       pr->cond = Safe_strdup (cond);
737     }
738   else
739     pr->cond = NULL;
740
741   pr->vars = newHashTable (100);
742
743   /* if root is empty */
744   if (!rootRules)
745     rootRules = currRule = pr;
746   else
747     currRule = currRule->next = pr;
748
749   return pr;
750 }
751
752 /*-----------------------------------------------------------------*/
753 /* newLineNode - creates a new peep line                           */
754 /*-----------------------------------------------------------------*/
755 lineNode *
756 newLineNode (char *line)
757 {
758   lineNode *pl;
759
760   pl = Safe_alloc ( sizeof (lineNode));
761   pl->line = Safe_strdup (line);
762   return pl;
763 }
764
765 /*-----------------------------------------------------------------*/
766 /* connectLine - connects two lines                                */
767 /*-----------------------------------------------------------------*/
768 lineNode *
769 connectLine (lineNode * pl1, lineNode * pl2)
770 {
771   if (!pl1 || !pl2)
772     {
773       fprintf (stderr, "trying to connect null line\n");
774       return NULL;
775     }
776
777   pl2->prev = pl1;
778   pl1->next = pl2;
779
780   return pl2;
781 }
782
783 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
784                          if (!*x) { fprintf(stderr,y); return ; } }
785
786 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ;   \
787                            if (!*x) { fprintf(stderr,z); return ; } }
788 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ;   \
789                            if (!*x) { fprintf(stderr,z); return ; } }
790
791 /*-----------------------------------------------------------------*/
792 /* getPeepLine - parses the peep lines                             */
793 /*-----------------------------------------------------------------*/
794 static void 
795 getPeepLine (lineNode ** head, char **bpp)
796 {
797   char lines[MAX_PATTERN_LEN];
798   char *lp;
799
800   lineNode *currL = NULL;
801   char *bp = *bpp;
802   while (1)
803     {
804
805       if (!*bp)
806         {
807           fprintf (stderr, "unexpected end of match pattern\n");
808           return;
809         }
810
811       if (*bp == '\n')
812         {
813           bp++;
814           while (isspace (*bp) ||
815                  *bp == '\n')
816             bp++;
817         }
818
819       if (*bp == '}')
820         {
821           bp++;
822           break;
823         }
824
825       /* read till end of line */
826       lp = lines;
827       while ((*bp != '\n' && *bp != '}') && *bp)
828         *lp++ = *bp++;
829
830       *lp = '\0';
831       if (!currL)
832         *head = currL = newLineNode (lines);
833       else
834         currL = connectLine (currL, newLineNode (lines));
835     }
836
837   *bpp = bp;
838 }
839
840 /*-----------------------------------------------------------------*/
841 /* readRules - reads the rules from a string buffer                */
842 /*-----------------------------------------------------------------*/
843 static void 
844 readRules (char *bp)
845 {
846   char restart = 0;
847   char lines[MAX_PATTERN_LEN];
848   char *lp;
849   lineNode *match;
850   lineNode *replace;
851   lineNode *currL = NULL;
852
853   if (!bp)
854     return;
855 top:
856   restart = 0;
857   /* look for the token "replace" that is the
858      start of a rule */
859   while (*bp && strncmp (bp, "replace", 7))
860     bp++;
861
862   /* if not found */
863   if (!*bp)
864     return;
865
866   /* then look for either "restart" or '{' */
867   while (strncmp (bp, "restart", 7) &&
868          *bp != '{' && bp)
869     bp++;
870
871   /* not found */
872   if (!*bp)
873     {
874       fprintf (stderr, "expected 'restart' or '{'\n");
875       return;
876     }
877
878   /* if brace */
879   if (*bp == '{')
880     bp++;
881   else
882     {                           /* must be restart */
883       restart++;
884       bp += strlen ("restart");
885       /* look for '{' */
886       EXPECT_CHR (bp, '{', "expected '{'\n");
887       bp++;
888     }
889
890   /* skip thru all the blank space */
891   SKIP_SPACE (bp, "unexpected end of rule\n");
892
893   match = replace = currL = NULL;
894   /* we are the start of a rule */
895   getPeepLine (&match, &bp);
896
897   /* now look for by */
898   EXPECT_STR (bp, "by", "expected 'by'\n");
899
900   /* then look for a '{' */
901   EXPECT_CHR (bp, '{', "expected '{'\n");
902   bp++;
903
904   SKIP_SPACE (bp, "unexpected end of rule\n");
905   getPeepLine (&replace, &bp);
906
907   /* look for a 'if' */
908   while ((isspace (*bp) || *bp == '\n') && *bp)
909     bp++;
910
911   if (strncmp (bp, "if", 2) == 0)
912     {
913       bp += 2;
914       while ((isspace (*bp) || *bp == '\n') && *bp)
915         bp++;
916       if (!*bp)
917         {
918           fprintf (stderr, "expected condition name\n");
919           return;
920         }
921
922       /* look for the condition */
923       lp = lines;
924       while (*bp && (*bp != '\n'))
925         {
926           *lp++ = *bp++;
927         }
928       *lp = '\0';
929
930       newPeepRule (match, replace, lines, restart);
931     }
932   else
933     newPeepRule (match, replace, NULL, restart);
934   goto top;
935
936 }
937
938 /*-----------------------------------------------------------------*/
939 /* keyForVar - returns the numeric key for a var                   */
940 /*-----------------------------------------------------------------*/
941 static int 
942 keyForVar (char *d)
943 {
944   int i = 0;
945
946   while (isdigit (*d))
947     {
948       i *= 10;
949       i += (*d++ - '0');
950     }
951
952   return i;
953 }
954
955 /*-----------------------------------------------------------------*/
956 /* bindVar - binds a value to a variable in the given hashtable    */
957 /*-----------------------------------------------------------------*/
958 static void 
959 bindVar (int key, char **s, hTab ** vtab)
960 {
961   char vval[MAX_PATTERN_LEN];
962   char *vvx;
963   char *vv = vval;
964
965   /* first get the value of the variable */
966   vvx = *s;
967   /* the value is ended by a ',' or space or newline or null or ) */
968   while (*vvx &&
969          *vvx != ',' &&
970          !isspace (*vvx) &&
971          *vvx != '\n' &&
972          *vvx != ':' &&
973          *vvx != ')')
974     {
975       char ubb = 0;
976       /* if we find a '(' then we need to balance it */
977       if (*vvx == '(')
978         {
979           ubb++;
980           while (ubb)
981             {
982               *vv++ = *vvx++;
983               if (*vvx == '(')
984                 ubb++;
985               if (*vvx == ')')
986                 ubb--;
987             }
988           // include the trailing ')'
989           *vv++ = *vvx++;
990         }
991       else
992         *vv++ = *vvx++;
993     }
994   *s = vvx;
995   *vv = '\0';
996   /* got value */
997   vvx = traceAlloc (&_G.values, Safe_strdup(vval));
998
999   hTabAddItem (vtab, key, vvx);
1000 }
1001
1002 /*-----------------------------------------------------------------*/
1003 /* matchLine - matches one line                                    */
1004 /*-----------------------------------------------------------------*/
1005 static bool 
1006 matchLine (char *s, char *d, hTab ** vars)
1007 {
1008
1009   if (!s || !(*s))
1010     return FALSE;
1011
1012   while (*s && *d)
1013     {
1014
1015       /* skip white space in both */
1016       while (isspace (*s))
1017         s++;
1018       while (isspace (*d))
1019         d++;
1020
1021       /* if the destination is a var */
1022       if (*d == '%' && isdigit (*(d + 1)))
1023         {
1024           char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
1025           /* if the variable is already bound
1026              then it MUST match with dest */
1027           if (v)
1028             {
1029               while (*v)
1030                 if (*v++ != *s++)
1031                   return FALSE;
1032             }
1033           else
1034             /* variable not bound we need to
1035                bind it */
1036             bindVar (keyForVar (d + 1), &s, vars);
1037
1038           /* in either case go past the variable */
1039           d++;
1040           while (isdigit (*d))
1041             d++;
1042         }
1043
1044       /* they should be an exact match other wise */
1045       if (*s && *d)
1046         {
1047           while (isspace (*s))
1048             s++;
1049           while (isspace (*d))
1050             d++;
1051           if (*s++ != *d++)
1052             return FALSE;
1053         }
1054
1055     }
1056
1057   /* get rid of the trailing spaces
1058      in both source & destination */
1059   if (*s)
1060     while (isspace (*s))
1061       s++;
1062
1063   if (*d)
1064     while (isspace (*d))
1065       d++;
1066
1067   /* after all this if only one of them
1068      has something left over then no match */
1069   if (*s || *d)
1070     return FALSE;
1071
1072   return TRUE;
1073 }
1074
1075 /*-----------------------------------------------------------------*/
1076 /* matchRule - matches a all the rule lines                        */
1077 /*-----------------------------------------------------------------*/
1078 static bool 
1079 matchRule (lineNode * pl,
1080            lineNode ** mtail,
1081            peepRule * pr,
1082            lineNode * head)
1083 {
1084   lineNode *spl;                /* source pl */
1085   lineNode *rpl;                /* rule peep line */
1086
1087 /*     setToNull((void **) &pr->vars);    */
1088 /*     pr->vars = newHashTable(100); */
1089
1090   /* for all the lines defined in the rule */
1091   rpl = pr->match;
1092   spl = pl;
1093   while (spl && rpl)
1094     {
1095
1096       /* if the source line starts with a ';' then
1097          comment line don't process or the source line
1098          contains == . debugger information skip it */
1099       if (spl->line &&
1100           (*spl->line == ';' || spl->isDebug))
1101         {
1102           spl = spl->next;
1103           continue;
1104         }
1105
1106       if (!matchLine (spl->line, rpl->line, &pr->vars))
1107         return FALSE;
1108
1109       rpl = rpl->next;
1110       if (rpl)
1111         spl = spl->next;
1112     }
1113
1114   /* if rules ended */
1115   if (!rpl)
1116     {
1117       /* if this rule has additional conditions */
1118       if (pr->cond)
1119         {
1120           if (callFuncByName (pr->cond, pr->vars, pl, head))
1121             {
1122               *mtail = spl;
1123               return TRUE;
1124             }
1125           else
1126             return FALSE;
1127         }
1128       else
1129         {
1130           *mtail = spl;
1131           return TRUE;
1132         }
1133     }
1134   else
1135     return FALSE;
1136 }
1137
1138 /*-----------------------------------------------------------------*/
1139 /* replaceRule - does replacement of a matching pattern            */
1140 /*-----------------------------------------------------------------*/
1141 static void 
1142 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
1143 {
1144   lineNode *cl = NULL;
1145   lineNode *pl = NULL, *lhead = NULL;
1146   /* a long function name and long variable name can evaluate to
1147      4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
1148   char lb[MAX_PATTERN_LEN*4];
1149   char *lbp;
1150   lineNode *comment = NULL;
1151
1152   /* collect all the comment lines in the source */
1153   for (cl = *shead; cl != stail; cl = cl->next)
1154     {
1155       if (cl->line && (*cl->line == ';' || cl->isDebug))
1156         {
1157           pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
1158                 (comment = newLineNode (cl->line)));
1159           pl->isDebug = cl->isDebug;
1160         }
1161     }
1162   cl = NULL;
1163
1164   /* for all the lines in the replacement pattern do */
1165   for (pl = pr->replace; pl; pl = pl->next)
1166     {
1167       char *v;
1168       char *l;
1169       lbp = lb;
1170
1171       l = pl->line;
1172
1173       while (*l)
1174         {
1175           /* if the line contains a variable */
1176           if (*l == '%' && isdigit (*(l + 1)))
1177             {
1178               v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
1179               if (!v)
1180                 {
1181                   fprintf (stderr, "used unbound variable in replacement\n");
1182                   l++;
1183                   continue;
1184                 }
1185               while (*v) {
1186                 *lbp++ = *v++;
1187               }
1188               l++;
1189               while (isdigit (*l)) {
1190                 l++;
1191               }
1192               continue;
1193             }
1194           *lbp++ = *l++;
1195         }
1196
1197       *lbp = '\0';
1198       if (cl)
1199         cl = connectLine (cl, newLineNode (lb));
1200       else
1201         lhead = cl = newLineNode (lb);
1202     }
1203
1204   /* add the comments if any to the head of list */
1205   if (comment)
1206     {
1207       lineNode *lc = comment;
1208       while (lc->next)
1209         lc = lc->next;
1210       lc->next = lhead;
1211       if (lhead)
1212         lhead->prev = lc;
1213       lhead = comment;
1214     }
1215
1216   /* now we need to connect / replace the original chain */
1217   /* if there is a prev then change it */
1218   if ((*shead)->prev)
1219     {
1220       (*shead)->prev->next = lhead;
1221       lhead->prev = (*shead)->prev;
1222     }
1223   *shead = lhead;
1224   /* now for the tail */
1225   if (stail && stail->next)
1226     {
1227       stail->next->prev = cl;
1228       if (cl)
1229         cl->next = stail->next;
1230     }
1231 }
1232
1233 /* Returns TRUE if this line is a label definition.
1234
1235  * If so, start will point to the start of the label name,
1236  * and len will be it's length.
1237  */
1238 bool 
1239 isLabelDefinition (const char *line, const char **start, int *len)
1240 {
1241   const char *cp = line;
1242
1243   /* This line is a label if if consists of:
1244    * [optional whitespace] followed by identifier chars
1245    * (alnum | $ | _ ) followed by a colon.
1246    */
1247
1248   while (*cp && isspace (*cp))
1249     {
1250       cp++;
1251     }
1252
1253   if (!*cp)
1254     {
1255       return FALSE;
1256     }
1257
1258   *start = cp;
1259
1260   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
1261     {
1262       cp++;
1263     }
1264
1265   if ((cp == *start) || (*cp != ':'))
1266     {
1267       return FALSE;
1268     }
1269
1270   *len = (cp - (*start));
1271   return TRUE;
1272 }
1273
1274 /* Quick & dirty string hash function. */
1275 static int 
1276 hashSymbolName (const char *name)
1277 {
1278   int hash = 0;
1279
1280   while (*name)
1281     {
1282       hash = (hash << 6) ^ *name;
1283       name++;
1284     }
1285
1286   if (hash < 0)
1287     {
1288       hash = -hash;
1289     }
1290
1291   return hash % HTAB_SIZE;
1292 }
1293
1294 /* Build a hash of all labels in the passed set of lines
1295  * and how many times they are referenced.
1296  */
1297 static void 
1298 buildLabelRefCountHash (lineNode * head)
1299 {
1300   lineNode *line;
1301   const char *label;
1302   int labelLen;
1303   int i;
1304
1305   assert (labelHash == NULL);
1306   labelHash = newHashTable (HTAB_SIZE);
1307
1308   /* First pass: locate all the labels. */
1309   line = head;
1310
1311   while (line)
1312     {
1313       if (isLabelDefinition (line->line, &label, &labelLen)
1314           && labelLen <= SDCC_NAME_MAX)
1315         {
1316           labelHashEntry *entry;
1317
1318           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
1319
1320           memcpy (entry->name, label, labelLen);
1321           entry->name[labelLen] = 0;
1322           entry->refCount = -1;
1323
1324           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
1325         }
1326       line = line->next;
1327     }
1328
1329
1330   /* Second pass: for each line, note all the referenced labels. */
1331   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
1332   line = head;
1333   while (line)
1334     {
1335       for (i = 0; i < HTAB_SIZE; i++)
1336         {
1337           labelHashEntry *thisEntry;
1338
1339           thisEntry = hTabFirstItemWK (labelHash, i);
1340
1341           while (thisEntry)
1342             {
1343               if (strstr (line->line, thisEntry->name))
1344                 {
1345                   thisEntry->refCount++;
1346                 }
1347               thisEntry = hTabNextItemWK (labelHash);
1348             }
1349         }
1350       line = line->next;
1351     }
1352
1353 #if 0
1354   /* Spew the contents of the table. Debugging fun only. */
1355   for (i = 0; i < HTAB_SIZE; i++)
1356     {
1357       labelHashEntry *thisEntry;
1358
1359       thisEntry = hTabFirstItemWK (labelHash, i);
1360
1361       while (thisEntry)
1362         {
1363           fprintf (stderr, "label: %s ref %d\n",
1364                    thisEntry->name, thisEntry->refCount);
1365           thisEntry = hTabNextItemWK (labelHash);
1366         }
1367     }
1368 #endif
1369 }
1370
1371 /* How does this work?
1372    peepHole
1373     For each rule,
1374      For each line,
1375       Try to match
1376       If it matches,
1377        replace and restart.
1378
1379     matchRule
1380      matchLine
1381
1382   Where is stuff allocated?
1383   
1384 */
1385
1386 /*-----------------------------------------------------------------*/
1387 /* peepHole - matches & substitutes rules                          */
1388 /*-----------------------------------------------------------------*/
1389 void 
1390 peepHole (lineNode ** pls)
1391 {
1392   lineNode *spl;
1393   peepRule *pr;
1394   lineNode *mtail = NULL;
1395   bool restart;
1396
1397 #if !OPT_DISABLE_PIC
1398   /* The PIC port uses a different peep hole optimizer based on "pCode" */
1399   if (TARGET_IS_PIC)
1400     return;
1401 #endif
1402
1403   assert(labelHash == NULL);
1404
1405   do
1406     {
1407       restart = FALSE;
1408
1409       /* for all rules */
1410       for (pr = rootRules; pr; pr = pr->next)
1411         {
1412           for (spl = *pls; spl; spl = spl->next)
1413             {
1414               /* if inline assembler then no peep hole */
1415               if (spl->isInline)
1416                 continue;
1417               
1418               mtail = NULL;
1419
1420               /* Tidy up any data stored in the hTab */
1421               
1422               /* if it matches */
1423               if (matchRule (spl, &mtail, pr, *pls))
1424                 {
1425                   
1426                   /* then replace */
1427                   if (spl == *pls)
1428                     replaceRule (pls, mtail, pr);
1429                   else
1430                     replaceRule (&spl, mtail, pr);
1431                   
1432                   /* if restart rule type then
1433                      start at the top again */
1434                   if (pr->restart)
1435                     {
1436                       restart = TRUE;
1437                     }
1438                 }
1439               
1440               if (pr->vars)
1441                 {
1442                   hTabDeleteAll (pr->vars);
1443                   Safe_free (pr->vars);
1444                   pr->vars = NULL;
1445                 }
1446               
1447               freeTrace (&_G.values);
1448             }
1449         }
1450     } while (restart == TRUE);
1451
1452   if (labelHash)
1453     {
1454       hTabDeleteAll (labelHash);
1455       freeTrace (&_G.labels);
1456     }
1457   labelHash = NULL;
1458 }
1459
1460
1461 /*-----------------------------------------------------------------*/
1462 /* readFileIntoBuffer - reads a file into a string buffer          */
1463 /*-----------------------------------------------------------------*/
1464 static char *
1465 readFileIntoBuffer (char *fname)
1466 {
1467   FILE *f;
1468   char *rs = NULL;
1469   int nch = 0;
1470   int ch;
1471   char lb[MAX_PATTERN_LEN];
1472
1473   if (!(f = fopen (fname, "r")))
1474     {
1475       fprintf (stderr, "cannot open peep rule file\n");
1476       return NULL;
1477     }
1478
1479   while ((ch = fgetc (f)) != EOF)
1480     {
1481       lb[nch++] = ch;
1482
1483       /* if we maxed out our local buffer */
1484       if (nch >= (MAX_PATTERN_LEN - 2))
1485         {
1486           lb[nch] = '\0';
1487           /* copy it into allocated buffer */
1488           if (rs)
1489             {
1490               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1491               strncatz (rs, lb,  strlen (rs) + strlen (lb) + 1);
1492             }
1493           else
1494             {
1495               rs = Safe_strdup (lb);
1496             }
1497           nch = 0;
1498         }
1499     }
1500
1501   /* if some charaters left over */
1502   if (nch)
1503     {
1504       lb[nch] = '\0';
1505       /* copy it into allocated buffer */
1506       if (rs)
1507         {
1508           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1509           strncatz (rs, lb, strlen (rs) + strlen (lb) + 1);
1510         }
1511       else
1512         {
1513           rs = Safe_strdup (lb);
1514         }
1515     }
1516   return rs;
1517 }
1518
1519 /*-----------------------------------------------------------------*/
1520 /* initPeepHole - initialises the peep hole optimizer stuff        */
1521 /*-----------------------------------------------------------------*/
1522 void 
1523 initPeepHole ()
1524 {
1525   char *s;
1526
1527   /* read in the default rules */
1528   readRules (port->peep.default_rules);
1529
1530   /* if we have any additional file read it too */
1531   if (options.peep_file)
1532     {
1533       readRules (s = readFileIntoBuffer (options.peep_file));
1534       setToNull ((void **) &s);
1535     }
1536
1537
1538 #if !OPT_DISABLE_PIC
1539   /* Convert the peep rules into pcode.
1540      NOTE: this is only support in the PIC port (at the moment)
1541   */
1542   if (TARGET_IS_PIC) {
1543     peepRules2pCode(rootRules);
1544   }
1545 #endif
1546
1547 }