git.gag.com Git - fw/sdcc/blob - 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 pcDistance (lineNode * cpos, char *lbl, bool back)
  64 {
  65   lineNode *pl = cpos;
  66   char buff[MAX_PATTERN_LEN];
  67   int dist = 0;
  68
  69   sprintf (buff, "%s:", lbl);
  70   while (pl)
  71     {
  72
  73       if (pl->line &&
  74           *pl->line != ';' &&
  75           pl->line[strlen (pl->line) - 1] != ':' &&
  76           !pl->isDebug)
  77
  78         dist++;
  79
  80       if (strncmp (pl->line, buff, strlen (buff)) == 0)
  81         return dist;
  82
  83       if (back)
  84         pl = pl->prev;
  85       else
  86         pl = pl->next;
  87
  88     }
  89   return 0;
  90 }
  91
  92 /*-----------------------------------------------------------------*/
  93 /* flat24bitModeAndPortDS390 -                                     */
  94 /*-----------------------------------------------------------------*/
  95 FBYNAME (flat24bitModeAndPortDS390)
  96 {
  97     return ((strcmp(port->target,"ds390") == 0) &&
  98             (options.model == MODEL_FLAT24));
  99 }
 100
 101 /*-----------------------------------------------------------------*/
 102 /* portIsDS390 - return true if port is DS390                      */
 103 /*-----------------------------------------------------------------*/
 104 FBYNAME (portIsDS390)
 105 {
 106     return (strcmp(port->target,"ds390") == 0);
 107 }
 108
 109 /*-----------------------------------------------------------------*/
 110 /* flat24bitMode - will check to see if we are in flat24 mode      */
 111 /*-----------------------------------------------------------------*/
 112 FBYNAME (flat24bitMode)
 113 {
 114   return (options.model == MODEL_FLAT24);
 115 }
 116
 117 /*-----------------------------------------------------------------*/
 118 /* labelInRange - will check to see if label %5 is within range    */
 119 /*-----------------------------------------------------------------*/
 120 FBYNAME (labelInRange)
 121 {
 122   /* assumes that %5 pattern variable has the label name */
 123   char *lbl = hTabItemWithKey (vars, 5);
 124   int dist = 0;
 125
 126   if (!lbl)
 127     return FALSE;
 128
 129   /* if the previous two instructions are "ljmp"s then don't
 130      do it since it can be part of a jump table */
 131   if (currPl->prev && currPl->prev->prev &&
 132       strstr (currPl->prev->line, "ljmp") &&
 133       strstr (currPl->prev->prev->line, "ljmp"))
 134     return FALSE;
 135
 136   /* calculate the label distance : the jump for reladdr can be
 137      +/- 127 bytes, here Iam assuming that an average 8051
 138      instruction is 2 bytes long, so if the label is more than
 139      63 intructions away, the label is considered out of range
 140      for a relative jump. we could get more precise this will
 141      suffice for now since it catches > 90% cases */
 142   dist = (pcDistance (currPl, lbl, TRUE) +
 143           pcDistance (currPl, lbl, FALSE));
 144
 145 /*    if (!dist || dist > 45) has produced wrong sjmp */
 146   /* 07-Sep-2000 Michael Schmitt */
 147   /* FIX for Peephole 132 */
 148   /* switch with lots of case can lead to a sjmp with a distance */
 149   /* out of the range for sjmp */
 150   if (!dist || dist > 43)
 151     return FALSE;
 152
 153   return TRUE;
 154 }
 155
 156 /*-----------------------------------------------------------------*/
 157 /* operandsNotSame - check if %1 & %2 are the same                 */
 158 /*-----------------------------------------------------------------*/
 159 FBYNAME (operandsNotSame)
 160 {
 161   char *op1 = hTabItemWithKey (vars, 1);
 162   char *op2 = hTabItemWithKey (vars, 2);
 163
 164   if (strcmp (op1, op2) == 0)
 165     return FALSE;
 166   else
 167     return TRUE;
 168 }
 169
 170 /* labelRefCount:
 171
 172  * takes two parameters: a variable (bound to a label name)
 173  * and an expected reference count.
 174  *
 175  * Returns TRUE if that label is defined and referenced exactly
 176  * the given number of times.
 177  */
 178 FBYNAME (labelRefCount)
 179 {
 180   int varNumber, expectedRefCount;
 181   bool rc = FALSE;
 182
 183   /* If we don't have the label hash table yet, build it. */
 184   if (!labelHash)
 185     {
 186       buildLabelRefCountHash (head);
 187     }
 188
 189   if (sscanf (cmdLine, "%*[ \t%]%d %d", &varNumber, &expectedRefCount) == 2)
 190     {
 191       char *label = hTabItemWithKey (vars, varNumber);
 192
 193       if (label)
 194         {
 195           labelHashEntry *entry;
 196
 197           entry = hTabFirstItemWK (labelHash, hashSymbolName (label));
 198
 199           while (entry)
 200             {
 201               if (!strcmp (label, entry->name))
 202                 {
 203                   break;
 204                 }
 205               entry = hTabNextItemWK (labelHash);
 206             }
 207           if (entry)
 208             {
 209 #if 0
 210               /* debug spew. */
 211               fprintf (stderr, "labelRefCount: %s has refCount %d, want %d\n",
 212                        label, entry->refCount, expectedRefCount);
 213 #endif
 214
 215               rc = (expectedRefCount == entry->refCount);
 216             }
 217           else
 218             {
 219               fprintf (stderr, "*** internal error: no label has entry for"
 220                        " %s in labelRefCount peephole.\n",
 221                        label);
 222             }
 223         }
 224       else
 225         {
 226           fprintf (stderr, "*** internal error: var %d not bound"
 227                    " in peephole labelRefCount rule.\n",
 228                    varNumber);
 229         }
 230
 231     }
 232   else
 233     {
 234       fprintf (stderr,
 235                "*** internal error: labelRefCount peephole restriction"
 236                " malformed: %s\n", cmdLine);
 237     }
 238   return rc;
 239 }
 240
 241 /*-----------------------------------------------------------------*/
 242 /* callFuncByName - calls a function as defined in the table       */
 243 /*-----------------------------------------------------------------*/
 244 int
 245 callFuncByName (char *fname,
 246                 hTab * vars,
 247                 lineNode * currPl,
 248                 lineNode * head)
 249 {
 250   struct ftab
 251   {
 252     char *fname;
 253     int (*func) (hTab *, lineNode *, lineNode *, const char *);
 254   }
 255   ftab[] =
 256   {
 257     {
 258       "labelInRange", labelInRange
 259     }
 260     ,
 261     {
 262       "operandsNotSame", operandsNotSame
 263     }
 264     ,
 265     {
 266       "24bitMode", flat24bitMode
 267     }
 268     ,
 269     {
 270       "labelRefCount", labelRefCount
 271     }
 272     ,
 273     {
 274       "portIsDS390", portIsDS390
 275     },
 276     {
 277       "24bitModeAndPortDS390", flat24bitModeAndPortDS390
 278     }
 279   };
 280   int i;
 281
 282   for (i = 0; i < ((sizeof (ftab)) / (sizeof (struct ftab))); i++)
 283     if (strncmp (ftab[i].fname, fname, strlen (ftab[i].fname)) == 0)
 284       {
 285         return (*ftab[i].func) (vars, currPl, head,
 286                                 fname + strlen (ftab[i].fname));
 287       }
 288   fprintf (stderr, "could not find named function in function table\n");
 289   return TRUE;
 290 }
 291
 292 /*-----------------------------------------------------------------*/
 293 /* printLine - prints a line chain into a given file               */
 294 /*-----------------------------------------------------------------*/
 295 void
 296 printLine (lineNode * head, FILE * of)
 297 {
 298   if (!of)
 299     of = stdout;
 300
 301   while (head)
 302     {
 303       /* don't indent comments & labels */
 304       if (head->line &&
 305           (*head->line == ';' ||
 306            head->line[strlen (head->line) - 1] == ':')) {
 307         fprintf (of, "%s\n", head->line);
 308       } else {
 309         if (head->isInline && *head->line=='#') {
 310           // comment out preprocessor directives in inline asm
 311           fprintf (of, ";");
 312         }
 313         fprintf (of, "\t%s\n", head->line);
 314       }
 315       head = head->next;
 316     }
 317 }
 318
 319 /*-----------------------------------------------------------------*/
 320 /* newPeepRule - creates a new peeprule and attach it to the root  */
 321 /*-----------------------------------------------------------------*/
 322 peepRule *
 323 newPeepRule (lineNode * match,
 324              lineNode * replace,
 325              char *cond,
 326              int restart)
 327 {
 328   peepRule *pr;
 329
 330   pr = Safe_alloc ( sizeof (peepRule));
 331   pr->match = match;
 332   pr->replace = replace;
 333   pr->restart = restart;
 334
 335   if (cond && *cond)
 336     {
 337       pr->cond = Safe_alloc ( strlen (cond) + 1);
 338       strcpy (pr->cond, cond);
 339     }
 340   else
 341     pr->cond = NULL;
 342
 343   pr->vars = newHashTable (100);
 344
 345   /* if root is empty */
 346   if (!rootRules)
 347     rootRules = currRule = pr;
 348   else
 349     currRule = currRule->next = pr;
 350
 351   return pr;
 352 }
 353
 354 /*-----------------------------------------------------------------*/
 355 /* newLineNode - creates a new peep line                           */
 356 /*-----------------------------------------------------------------*/
 357 lineNode *
 358 newLineNode (char *line)
 359 {
 360   lineNode *pl;
 361
 362   pl = Safe_alloc ( sizeof (lineNode));
 363   pl->line = Safe_alloc ( strlen (line) + 1);
 364   strcpy (pl->line, line);
 365   return pl;
 366 }
 367
 368 /*-----------------------------------------------------------------*/
 369 /* connectLine - connects two lines                                */
 370 /*-----------------------------------------------------------------*/
 371 lineNode *
 372 connectLine (lineNode * pl1, lineNode * pl2)
 373 {
 374   if (!pl1 || !pl2)
 375     {
 376       fprintf (stderr, "trying to connect null line\n");
 377       return NULL;
 378     }
 379
 380   pl2->prev = pl1;
 381   pl1->next = pl2;
 382
 383   return pl2;
 384 }
 385
 386 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
 387                          if (!*x) { fprintf(stderr,y); return ; } }
 388
 389 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ;   \
 390                            if (!*x) { fprintf(stderr,z); return ; } }
 391 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ;   \
 392                            if (!*x) { fprintf(stderr,z); return ; } }
 393
 394 /*-----------------------------------------------------------------*/
 395 /* getPeepLine - parses the peep lines                             */
 396 /*-----------------------------------------------------------------*/
 397 static void
 398 getPeepLine (lineNode ** head, char **bpp)
 399 {
 400   char lines[MAX_PATTERN_LEN];
 401   char *lp;
 402
 403   lineNode *currL = NULL;
 404   char *bp = *bpp;
 405   while (1)
 406     {
 407
 408       if (!*bp)
 409         {
 410           fprintf (stderr, "unexpected end of match pattern\n");
 411           return;
 412         }
 413
 414       if (*bp == '\n')
 415         {
 416           bp++;
 417           while (isspace (*bp) ||
 418                  *bp == '\n')
 419             bp++;
 420         }
 421
 422       if (*bp == '}')
 423         {
 424           bp++;
 425           break;
 426         }
 427
 428       /* read till end of line */
 429       lp = lines;
 430       while ((*bp != '\n' && *bp != '}') && *bp)
 431         *lp++ = *bp++;
 432
 433       *lp = '\0';
 434       if (!currL)
 435         *head = currL = newLineNode (lines);
 436       else
 437         currL = connectLine (currL, newLineNode (lines));
 438     }
 439
 440   *bpp = bp;
 441 }
 442
 443 /*-----------------------------------------------------------------*/
 444 /* readRules - reads the rules from a string buffer                */
 445 /*-----------------------------------------------------------------*/
 446 static void
 447 readRules (char *bp)
 448 {
 449   char restart = 0;
 450   char lines[MAX_PATTERN_LEN];
 451   char *lp;
 452   lineNode *match;
 453   lineNode *replace;
 454   lineNode *currL = NULL;
 455
 456   if (!bp)
 457     return;
 458 top:
 459   restart = 0;
 460   /* look for the token "replace" that is the
 461      start of a rule */
 462   while (*bp && strncmp (bp, "replace", 7))
 463     bp++;
 464
 465   /* if not found */
 466   if (!*bp)
 467     return;
 468
 469   /* then look for either "restart" or '{' */
 470   while (strncmp (bp, "restart", 7) &&
 471          *bp != '{' && bp)
 472     bp++;
 473
 474   /* not found */
 475   if (!*bp)
 476     {
 477       fprintf (stderr, "expected 'restart' or '{'\n");
 478       return;
 479     }
 480
 481   /* if brace */
 482   if (*bp == '{')
 483     bp++;
 484   else
 485     {                           /* must be restart */
 486       restart++;
 487       bp += strlen ("restart");
 488       /* look for '{' */
 489       EXPECT_CHR (bp, '{', "expected '{'\n");
 490       bp++;
 491     }
 492
 493   /* skip thru all the blank space */
 494   SKIP_SPACE (bp, "unexpected end of rule\n");
 495
 496   match = replace = currL = NULL;
 497   /* we are the start of a rule */
 498   getPeepLine (&match, &bp);
 499
 500   /* now look for by */
 501   EXPECT_STR (bp, "by", "expected 'by'\n");
 502
 503   /* then look for a '{' */
 504   EXPECT_CHR (bp, '{', "expected '{'\n");
 505   bp++;
 506
 507   SKIP_SPACE (bp, "unexpected end of rule\n");
 508   getPeepLine (&replace, &bp);
 509
 510   /* look for a 'if' */
 511   while ((isspace (*bp) || *bp == '\n') && *bp)
 512     bp++;
 513
 514   if (strncmp (bp, "if", 2) == 0)
 515     {
 516       bp += 2;
 517       while ((isspace (*bp) || *bp == '\n') && *bp)
 518         bp++;
 519       if (!*bp)
 520         {
 521           fprintf (stderr, "expected condition name\n");
 522           return;
 523         }
 524
 525       /* look for the condition */
 526       lp = lines;
 527       while (*bp && (*bp != '\n'))
 528         {
 529           *lp++ = *bp++;
 530         }
 531       *lp = '\0';
 532
 533       newPeepRule (match, replace, lines, restart);
 534     }
 535   else
 536     newPeepRule (match, replace, NULL, restart);
 537   goto top;
 538
 539 }
 540
 541 /*-----------------------------------------------------------------*/
 542 /* keyForVar - returns the numeric key for a var                   */
 543 /*-----------------------------------------------------------------*/
 544 static int
 545 keyForVar (char *d)
 546 {
 547   int i = 0;
 548
 549   while (isdigit (*d))
 550     {
 551       i *= 10;
 552       i += (*d++ - '0');
 553     }
 554
 555   return i;
 556 }
 557
 558 /*-----------------------------------------------------------------*/
 559 /* bindVar - binds a value to a variable in the given hashtable    */
 560 /*-----------------------------------------------------------------*/
 561 static void
 562 bindVar (int key, char **s, hTab ** vtab)
 563 {
 564   char vval[MAX_PATTERN_LEN];
 565   char *vvx;
 566   char *vv = vval;
 567
 568   /* first get the value of the variable */
 569   vvx = *s;
 570   /* the value is ended by a ',' or space or newline or null or ) */
 571   while (*vvx &&
 572          *vvx != ',' &&
 573          !isspace (*vvx) &&
 574          *vvx != '\n' &&
 575          *vvx != ':' &&
 576          *vvx != ')')
 577     {
 578       char ubb = 0;
 579       /* if we find a '(' then we need to balance it */
 580       if (*vvx == '(')
 581         {
 582           ubb++;
 583           while (ubb)
 584             {
 585               *vv++ = *vvx++;
 586               if (*vvx == '(')
 587                 ubb++;
 588               if (*vvx == ')')
 589                 ubb--;
 590             }
 591         }
 592       else
 593         *vv++ = *vvx++;
 594     }
 595   *s = vvx;
 596   *vv = '\0';
 597   /* got value */
 598   vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
 599   strcpy (vvx, vval);
 600
 601   hTabAddItem (vtab, key, vvx);
 602 }
 603
 604 /*-----------------------------------------------------------------*/
 605 /* matchLine - matches one line                                    */
 606 /*-----------------------------------------------------------------*/
 607 static bool
 608 matchLine (char *s, char *d, hTab ** vars)
 609 {
 610
 611   if (!s || !(*s))
 612     return FALSE;
 613
 614   while (*s && *d)
 615     {
 616
 617       /* skip white space in both */
 618       while (isspace (*s))
 619         s++;
 620       while (isspace (*d))
 621         d++;
 622
 623       /* if the destination is a var */
 624       if (*d == '%' && isdigit (*(d + 1)))
 625         {
 626           char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
 627           /* if the variable is already bound
 628              then it MUST match with dest */
 629           if (v)
 630             {
 631               while (*v)
 632                 if (*v++ != *s++)
 633                   return FALSE;
 634             }
 635           else
 636             /* variable not bound we need to
 637                bind it */
 638             bindVar (keyForVar (d + 1), &s, vars);
 639
 640           /* in either case go past the variable */
 641           d++;
 642           while (isdigit (*d))
 643             d++;
 644         }
 645
 646       /* they should be an exact match other wise */
 647       if (*s && *d)
 648         {
 649           while (isspace (*s))
 650             s++;
 651           while (isspace (*d))
 652             d++;
 653           if (*s++ != *d++)
 654             return FALSE;
 655         }
 656
 657     }
 658
 659   /* get rid of the trailing spaces
 660      in both source & destination */
 661   if (*s)
 662     while (isspace (*s))
 663       s++;
 664
 665   if (*d)
 666     while (isspace (*d))
 667       d++;
 668
 669   /* after all this if only one of them
 670      has something left over then no match */
 671   if (*s || *d)
 672     return FALSE;
 673
 674   return TRUE;
 675 }
 676
 677 /*-----------------------------------------------------------------*/
 678 /* matchRule - matches a all the rule lines                        */
 679 /*-----------------------------------------------------------------*/
 680 static bool
 681 matchRule (lineNode * pl,
 682            lineNode ** mtail,
 683            peepRule * pr,
 684            lineNode * head)
 685 {
 686   lineNode *spl;                /* source pl */
 687   lineNode *rpl;                /* rule peep line */
 688
 689 /*     setToNull((void **) &pr->vars);    */
 690 /*     pr->vars = newHashTable(100); */
 691
 692   /* for all the lines defined in the rule */
 693   rpl = pr->match;
 694   spl = pl;
 695   while (spl && rpl)
 696     {
 697
 698       /* if the source line starts with a ';' then
 699          comment line don't process or the source line
 700          contains == . debugger information skip it */
 701       if (spl->line &&
 702           (*spl->line == ';' || spl->isDebug))
 703         {
 704           spl = spl->next;
 705           continue;
 706         }
 707
 708       if (!matchLine (spl->line, rpl->line, &pr->vars))
 709         return FALSE;
 710
 711       rpl = rpl->next;
 712       if (rpl)
 713         spl = spl->next;
 714     }
 715
 716   /* if rules ended */
 717   if (!rpl)
 718     {
 719       /* if this rule has additional conditions */
 720       if (pr->cond)
 721         {
 722           if (callFuncByName (pr->cond, pr->vars, pl, head))
 723             {
 724               *mtail = spl;
 725               return TRUE;
 726             }
 727           else
 728             return FALSE;
 729         }
 730       else
 731         {
 732           *mtail = spl;
 733           return TRUE;
 734         }
 735     }
 736   else
 737     return FALSE;
 738 }
 739
 740 /*-----------------------------------------------------------------*/
 741 /* replaceRule - does replacement of a matching pattern            */
 742 /*-----------------------------------------------------------------*/
 743 static void
 744 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
 745 {
 746   lineNode *cl = NULL;
 747   lineNode *pl = NULL, *lhead = NULL;
 748   /* a long function name and long variable name can evaluate to
 749      4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
 750   char lb[MAX_PATTERN_LEN*4];
 751   char *lbp;
 752   lineNode *comment = NULL;
 753
 754   /* collect all the comment lines in the source */
 755   for (cl = *shead; cl != stail; cl = cl->next)
 756     {
 757       if (cl->line && (*cl->line == ';' || cl->isDebug))
 758         {
 759           pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
 760                 (comment = newLineNode (cl->line)));
 761           pl->isDebug = cl->isDebug;
 762         }
 763     }
 764   cl = NULL;
 765
 766   /* for all the lines in the replacement pattern do */
 767   for (pl = pr->replace; pl; pl = pl->next)
 768     {
 769       char *v;
 770       char *l;
 771       lbp = lb;
 772
 773       l = pl->line;
 774
 775       while (*l)
 776         {
 777           /* if the line contains a variable */
 778           if (*l == '%' && isdigit (*(l + 1)))
 779             {
 780               v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
 781               if (!v)
 782                 {
 783                   fprintf (stderr, "used unbound variable in replacement\n");
 784                   l++;
 785                   continue;
 786                 }
 787               while (*v) {
 788                 *lbp++ = *v++;
 789               }
 790               l++;
 791               while (isdigit (*l)) {
 792                 l++;
 793               }
 794               continue;
 795             }
 796           *lbp++ = *l++;
 797         }
 798
 799       *lbp = '\0';
 800       if (cl)
 801         cl = connectLine (cl, newLineNode (lb));
 802       else
 803         lhead = cl = newLineNode (lb);
 804     }
 805
 806   /* add the comments if any to the head of list */
 807   if (comment)
 808     {
 809       lineNode *lc = comment;
 810       while (lc->next)
 811         lc = lc->next;
 812       lc->next = lhead;
 813       if (lhead)
 814         lhead->prev = lc;
 815       lhead = comment;
 816     }
 817
 818   /* now we need to connect / replace the original chain */
 819   /* if there is a prev then change it */
 820   if ((*shead)->prev)
 821     {
 822       (*shead)->prev->next = lhead;
 823       lhead->prev = (*shead)->prev;
 824     }
 825   else
 826     *shead = lhead;
 827   /* now for the tail */
 828   if (stail && stail->next)
 829     {
 830       stail->next->prev = cl;
 831       if (cl)
 832         cl->next = stail->next;
 833     }
 834 }
 835
 836 /* Returns TRUE if this line is a label definition.
 837
 838  * If so, start will point to the start of the label name,
 839  * and len will be it's length.
 840  */
 841 bool
 842 isLabelDefinition (const char *line, const char **start, int *len)
 843 {
 844   const char *cp = line;
 845
 846   /* This line is a label if if consists of:
 847    * [optional whitespace] followed by identifier chars
 848    * (alnum | $ | _ ) followed by a colon.
 849    */
 850
 851   while (*cp && isspace (*cp))
 852     {
 853       cp++;
 854     }
 855
 856   if (!*cp)
 857     {
 858       return FALSE;
 859     }
 860
 861   *start = cp;
 862
 863   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
 864     {
 865       cp++;
 866     }
 867
 868   if ((cp == *start) || (*cp != ':'))
 869     {
 870       return FALSE;
 871     }
 872
 873   *len = (cp - (*start));
 874   return TRUE;
 875 }
 876
 877 /* Quick & dirty string hash function. */
 878 static int
 879 hashSymbolName (const char *name)
 880 {
 881   int hash = 0;
 882
 883   while (*name)
 884     {
 885       hash = (hash << 6) ^ *name;
 886       name++;
 887     }
 888
 889   if (hash < 0)
 890     {
 891       hash = -hash;
 892     }
 893
 894   return hash % HTAB_SIZE;
 895 }
 896
 897 /* Build a hash of all labels in the passed set of lines
 898  * and how many times they are referenced.
 899  */
 900 static void
 901 buildLabelRefCountHash (lineNode * head)
 902 {
 903   lineNode *line;
 904   const char *label;
 905   int labelLen;
 906   int i;
 907
 908   assert (labelHash == NULL);
 909   labelHash = newHashTable (HTAB_SIZE);
 910
 911   /* First pass: locate all the labels. */
 912   line = head;
 913
 914   while (line)
 915     {
 916       if (isLabelDefinition (line->line, &label, &labelLen)
 917           && labelLen <= SDCC_NAME_MAX)
 918         {
 919           labelHashEntry *entry;
 920
 921           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
 922
 923           memcpy (entry->name, label, labelLen);
 924           entry->name[labelLen] = 0;
 925           entry->refCount = -1;
 926
 927           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
 928         }
 929       line = line->next;
 930     }
 931
 932
 933   /* Second pass: for each line, note all the referenced labels. */
 934   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
 935   line = head;
 936   while (line)
 937     {
 938       for (i = 0; i < HTAB_SIZE; i++)
 939         {
 940           labelHashEntry *thisEntry;
 941
 942           thisEntry = hTabFirstItemWK (labelHash, i);
 943
 944           while (thisEntry)
 945             {
 946               if (strstr (line->line, thisEntry->name))
 947                 {
 948                   thisEntry->refCount++;
 949                 }
 950               thisEntry = hTabNextItemWK (labelHash);
 951             }
 952         }
 953       line = line->next;
 954     }
 955
 956 #if 0
 957   /* Spew the contents of the table. Debugging fun only. */
 958   for (i = 0; i < HTAB_SIZE; i++)
 959     {
 960       labelHashEntry *thisEntry;
 961
 962       thisEntry = hTabFirstItemWK (labelHash, i);
 963
 964       while (thisEntry)
 965         {
 966           fprintf (stderr, "label: %s ref %d\n",
 967                    thisEntry->name, thisEntry->refCount);
 968           thisEntry = hTabNextItemWK (labelHash);
 969         }
 970     }
 971 #endif
 972 }
 973
 974 /* How does this work?
 975    peepHole
 976     For each rule,
 977      For each line,
 978       Try to match
 979       If it matches,
 980        replace and restart.
 981
 982     matchRule
 983      matchLine
 984
 985   Where is stuff allocated?
 986
 987 */
 988
 989 /*-----------------------------------------------------------------*/
 990 /* peepHole - matches & substitutes rules                          */
 991 /*-----------------------------------------------------------------*/
 992 void
 993 peepHole (lineNode ** pls)
 994 {
 995   lineNode *spl;
 996   peepRule *pr;
 997   lineNode *mtail = NULL;
 998   bool restart;
 999
1000   assert(labelHash == NULL);
1001
1002   do
1003     {
1004       restart = FALSE;
1005
1006       /* for all rules */
1007       for (pr = rootRules; pr; pr = pr->next)
1008         {
1009           for (spl = *pls; spl; spl = spl->next)
1010             {
1011               /* if inline assembler then no peep hole */
1012               if (spl->isInline)
1013                 continue;
1014
1015               mtail = NULL;
1016
1017               /* Tidy up any data stored in the hTab */
1018
1019               /* if it matches */
1020               if (matchRule (spl, &mtail, pr, *pls))
1021                 {
1022
1023                   /* then replace */
1024                   if (spl == *pls)
1025                     replaceRule (pls, mtail, pr);
1026                   else
1027                     replaceRule (&spl, mtail, pr);
1028
1029                   /* if restart rule type then
1030                      start at the top again */
1031                   if (pr->restart)
1032                     {
1033                       restart = TRUE;
1034                     }
1035                 }
1036
1037               if (pr->vars)
1038                 {
1039                   hTabDeleteAll (pr->vars);
1040                   Safe_free (pr->vars);
1041                   pr->vars = NULL;
1042                 }
1043
1044               freeTrace (&_G.values);
1045             }
1046         }
1047     } while (restart == TRUE);
1048
1049   if (labelHash)
1050     {
1051       hTabDeleteAll (labelHash);
1052       freeTrace (&_G.labels);
1053     }
1054   labelHash = NULL;
1055 }
1056
1057
1058 /*-----------------------------------------------------------------*/
1059 /* readFileIntoBuffer - reads a file into a string buffer          */
1060 /*-----------------------------------------------------------------*/
1061 static char *
1062 readFileIntoBuffer (char *fname)
1063 {
1064   FILE *f;
1065   char *rs = NULL;
1066   int nch = 0;
1067   int ch;
1068   char lb[MAX_PATTERN_LEN];
1069
1070   if (!(f = fopen (fname, "r")))
1071     {
1072       fprintf (stderr, "cannot open peep rule file\n");
1073       return NULL;
1074     }
1075
1076   while ((ch = fgetc (f)) != EOF)
1077     {
1078       lb[nch++] = ch;
1079
1080       /* if we maxed out our local buffer */
1081       if (nch >= (MAX_PATTERN_LEN - 2))
1082         {
1083           lb[nch] = '\0';
1084           /* copy it into allocated buffer */
1085           if (rs)
1086             {
1087               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1088               strcat (rs, lb);
1089             }
1090           else
1091             {
1092               rs = Safe_alloc ( strlen (lb) + 1);
1093               strcpy (rs, lb);
1094             }
1095           nch = 0;
1096         }
1097     }
1098
1099   /* if some charaters left over */
1100   if (nch)
1101     {
1102       lb[nch] = '\0';
1103       /* copy it into allocated buffer */
1104       if (rs)
1105         {
1106           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1107           strcat (rs, lb);
1108         }
1109       else
1110         {
1111           rs = Safe_alloc ( strlen (lb) + 1);
1112           strcpy (rs, lb);
1113         }
1114     }
1115   return rs;
1116 }
1117
1118 /*-----------------------------------------------------------------*/
1119 /* initPeepHole - initialises the peep hole optimizer stuff        */
1120 /*-----------------------------------------------------------------*/
1121 void
1122 initPeepHole ()
1123 {
1124   char *s;
1125
1126   /* read in the default rules */
1127   readRules (port->peep.default_rules);
1128
1129   /* if we have any additional file read it too */
1130   if (options.peep_file)
1131     {
1132       readRules (s = readFileIntoBuffer (options.peep_file));
1133       setToNull ((void **) &s);
1134     }
1135
1136
1137 #if !OPT_DISABLE_PIC
1138   /* Convert the peep rules into pcode.
1139      NOTE: this is only support in the PIC port (at the moment)
1140   */
1141   if (TARGET_IS_PIC) {
1142     peepRules2pCode(rootRules);
1143   }
1144 #endif
1145
1146 }