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