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