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