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           // include the trailing ')'
 604           *vv++ = *vvx++;
 605         }
 606       else
 607         *vv++ = *vvx++;
 608     }
 609   *s = vvx;
 610   *vv = '\0';
 611   /* got value */
 612   vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
 613   strcpy (vvx, vval);
 614
 615   hTabAddItem (vtab, key, vvx);
 616 }
 617
 618 /*-----------------------------------------------------------------*/
 619 /* matchLine - matches one line                                    */
 620 /*-----------------------------------------------------------------*/
 621 static bool
 622 matchLine (char *s, char *d, hTab ** vars)
 623 {
 624
 625   if (!s || !(*s))
 626     return FALSE;
 627
 628   while (*s && *d)
 629     {
 630
 631       /* skip white space in both */
 632       while (isspace (*s))
 633         s++;
 634       while (isspace (*d))
 635         d++;
 636
 637       /* if the destination is a var */
 638       if (*d == '%' && isdigit (*(d + 1)))
 639         {
 640           char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
 641           /* if the variable is already bound
 642              then it MUST match with dest */
 643           if (v)
 644             {
 645               while (*v)
 646                 if (*v++ != *s++)
 647                   return FALSE;
 648             }
 649           else
 650             /* variable not bound we need to
 651                bind it */
 652             bindVar (keyForVar (d + 1), &s, vars);
 653
 654           /* in either case go past the variable */
 655           d++;
 656           while (isdigit (*d))
 657             d++;
 658         }
 659
 660       /* they should be an exact match other wise */
 661       if (*s && *d)
 662         {
 663           while (isspace (*s))
 664             s++;
 665           while (isspace (*d))
 666             d++;
 667           if (*s++ != *d++)
 668             return FALSE;
 669         }
 670
 671     }
 672
 673   /* get rid of the trailing spaces
 674      in both source & destination */
 675   if (*s)
 676     while (isspace (*s))
 677       s++;
 678
 679   if (*d)
 680     while (isspace (*d))
 681       d++;
 682
 683   /* after all this if only one of them
 684      has something left over then no match */
 685   if (*s || *d)
 686     return FALSE;
 687
 688   return TRUE;
 689 }
 690
 691 /*-----------------------------------------------------------------*/
 692 /* matchRule - matches a all the rule lines                        */
 693 /*-----------------------------------------------------------------*/
 694 static bool
 695 matchRule (lineNode * pl,
 696            lineNode ** mtail,
 697            peepRule * pr,
 698            lineNode * head)
 699 {
 700   lineNode *spl;                /* source pl */
 701   lineNode *rpl;                /* rule peep line */
 702
 703 /*     setToNull((void **) &pr->vars);    */
 704 /*     pr->vars = newHashTable(100); */
 705
 706   /* for all the lines defined in the rule */
 707   rpl = pr->match;
 708   spl = pl;
 709   while (spl && rpl)
 710     {
 711
 712       /* if the source line starts with a ';' then
 713          comment line don't process or the source line
 714          contains == . debugger information skip it */
 715       if (spl->line &&
 716           (*spl->line == ';' || spl->isDebug))
 717         {
 718           spl = spl->next;
 719           continue;
 720         }
 721
 722       if (!matchLine (spl->line, rpl->line, &pr->vars))
 723         return FALSE;
 724
 725       rpl = rpl->next;
 726       if (rpl)
 727         spl = spl->next;
 728     }
 729
 730   /* if rules ended */
 731   if (!rpl)
 732     {
 733       /* if this rule has additional conditions */
 734       if (pr->cond)
 735         {
 736           if (callFuncByName (pr->cond, pr->vars, pl, head))
 737             {
 738               *mtail = spl;
 739               return TRUE;
 740             }
 741           else
 742             return FALSE;
 743         }
 744       else
 745         {
 746           *mtail = spl;
 747           return TRUE;
 748         }
 749     }
 750   else
 751     return FALSE;
 752 }
 753
 754 /*-----------------------------------------------------------------*/
 755 /* replaceRule - does replacement of a matching pattern            */
 756 /*-----------------------------------------------------------------*/
 757 static void
 758 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
 759 {
 760   lineNode *cl = NULL;
 761   lineNode *pl = NULL, *lhead = NULL;
 762   /* a long function name and long variable name can evaluate to
 763      4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
 764   char lb[MAX_PATTERN_LEN*4];
 765   char *lbp;
 766   lineNode *comment = NULL;
 767
 768   /* collect all the comment lines in the source */
 769   for (cl = *shead; cl != stail; cl = cl->next)
 770     {
 771       if (cl->line && (*cl->line == ';' || cl->isDebug))
 772         {
 773           pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
 774                 (comment = newLineNode (cl->line)));
 775           pl->isDebug = cl->isDebug;
 776         }
 777     }
 778   cl = NULL;
 779
 780   /* for all the lines in the replacement pattern do */
 781   for (pl = pr->replace; pl; pl = pl->next)
 782     {
 783       char *v;
 784       char *l;
 785       lbp = lb;
 786
 787       l = pl->line;
 788
 789       while (*l)
 790         {
 791           /* if the line contains a variable */
 792           if (*l == '%' && isdigit (*(l + 1)))
 793             {
 794               v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
 795               if (!v)
 796                 {
 797                   fprintf (stderr, "used unbound variable in replacement\n");
 798                   l++;
 799                   continue;
 800                 }
 801               while (*v) {
 802                 *lbp++ = *v++;
 803               }
 804               l++;
 805               while (isdigit (*l)) {
 806                 l++;
 807               }
 808               continue;
 809             }
 810           *lbp++ = *l++;
 811         }
 812
 813       *lbp = '\0';
 814       if (cl)
 815         cl = connectLine (cl, newLineNode (lb));
 816       else
 817         lhead = cl = newLineNode (lb);
 818     }
 819
 820   /* add the comments if any to the head of list */
 821   if (comment)
 822     {
 823       lineNode *lc = comment;
 824       while (lc->next)
 825         lc = lc->next;
 826       lc->next = lhead;
 827       if (lhead)
 828         lhead->prev = lc;
 829       lhead = comment;
 830     }
 831
 832   /* now we need to connect / replace the original chain */
 833   /* if there is a prev then change it */
 834   if ((*shead)->prev)
 835     {
 836       (*shead)->prev->next = lhead;
 837       lhead->prev = (*shead)->prev;
 838     }
 839   *shead = lhead;
 840   /* now for the tail */
 841   if (stail && stail->next)
 842     {
 843       stail->next->prev = cl;
 844       if (cl)
 845         cl->next = stail->next;
 846     }
 847 }
 848
 849 /* Returns TRUE if this line is a label definition.
 850
 851  * If so, start will point to the start of the label name,
 852  * and len will be it's length.
 853  */
 854 bool
 855 isLabelDefinition (const char *line, const char **start, int *len)
 856 {
 857   const char *cp = line;
 858
 859   /* This line is a label if if consists of:
 860    * [optional whitespace] followed by identifier chars
 861    * (alnum | $ | _ ) followed by a colon.
 862    */
 863
 864   while (*cp && isspace (*cp))
 865     {
 866       cp++;
 867     }
 868
 869   if (!*cp)
 870     {
 871       return FALSE;
 872     }
 873
 874   *start = cp;
 875
 876   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
 877     {
 878       cp++;
 879     }
 880
 881   if ((cp == *start) || (*cp != ':'))
 882     {
 883       return FALSE;
 884     }
 885
 886   *len = (cp - (*start));
 887   return TRUE;
 888 }
 889
 890 /* Quick & dirty string hash function. */
 891 static int
 892 hashSymbolName (const char *name)
 893 {
 894   int hash = 0;
 895
 896   while (*name)
 897     {
 898       hash = (hash << 6) ^ *name;
 899       name++;
 900     }
 901
 902   if (hash < 0)
 903     {
 904       hash = -hash;
 905     }
 906
 907   return hash % HTAB_SIZE;
 908 }
 909
 910 /* Build a hash of all labels in the passed set of lines
 911  * and how many times they are referenced.
 912  */
 913 static void
 914 buildLabelRefCountHash (lineNode * head)
 915 {
 916   lineNode *line;
 917   const char *label;
 918   int labelLen;
 919   int i;
 920
 921   assert (labelHash == NULL);
 922   labelHash = newHashTable (HTAB_SIZE);
 923
 924   /* First pass: locate all the labels. */
 925   line = head;
 926
 927   while (line)
 928     {
 929       if (isLabelDefinition (line->line, &label, &labelLen)
 930           && labelLen <= SDCC_NAME_MAX)
 931         {
 932           labelHashEntry *entry;
 933
 934           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
 935
 936           memcpy (entry->name, label, labelLen);
 937           entry->name[labelLen] = 0;
 938           entry->refCount = -1;
 939
 940           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
 941         }
 942       line = line->next;
 943     }
 944
 945
 946   /* Second pass: for each line, note all the referenced labels. */
 947   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
 948   line = head;
 949   while (line)
 950     {
 951       for (i = 0; i < HTAB_SIZE; i++)
 952         {
 953           labelHashEntry *thisEntry;
 954
 955           thisEntry = hTabFirstItemWK (labelHash, i);
 956
 957           while (thisEntry)
 958             {
 959               if (strstr (line->line, thisEntry->name))
 960                 {
 961                   thisEntry->refCount++;
 962                 }
 963               thisEntry = hTabNextItemWK (labelHash);
 964             }
 965         }
 966       line = line->next;
 967     }
 968
 969 #if 0
 970   /* Spew the contents of the table. Debugging fun only. */
 971   for (i = 0; i < HTAB_SIZE; i++)
 972     {
 973       labelHashEntry *thisEntry;
 974
 975       thisEntry = hTabFirstItemWK (labelHash, i);
 976
 977       while (thisEntry)
 978         {
 979           fprintf (stderr, "label: %s ref %d\n",
 980                    thisEntry->name, thisEntry->refCount);
 981           thisEntry = hTabNextItemWK (labelHash);
 982         }
 983     }
 984 #endif
 985 }
 986
 987 /* How does this work?
 988    peepHole
 989     For each rule,
 990      For each line,
 991       Try to match
 992       If it matches,
 993        replace and restart.
 994
 995     matchRule
 996      matchLine
 997
 998   Where is stuff allocated?
 999
1000 */
1001
1002 /*-----------------------------------------------------------------*/
1003 /* peepHole - matches & substitutes rules                          */
1004 /*-----------------------------------------------------------------*/
1005 void
1006 peepHole (lineNode ** pls)
1007 {
1008   lineNode *spl;
1009   peepRule *pr;
1010   lineNode *mtail = NULL;
1011   bool restart;
1012
1013 #if !OPT_DISABLE_PIC
1014   /* The PIC port uses a different peep hole optimizer based on "pCode" */
1015   if (TARGET_IS_PIC)
1016     return;
1017 #endif
1018
1019   assert(labelHash == NULL);
1020
1021   do
1022     {
1023       restart = FALSE;
1024
1025       /* for all rules */
1026       for (pr = rootRules; pr; pr = pr->next)
1027         {
1028           for (spl = *pls; spl; spl = spl->next)
1029             {
1030               /* if inline assembler then no peep hole */
1031               if (spl->isInline)
1032                 continue;
1033
1034               mtail = NULL;
1035
1036               /* Tidy up any data stored in the hTab */
1037
1038               /* if it matches */
1039               if (matchRule (spl, &mtail, pr, *pls))
1040                 {
1041
1042                   /* then replace */
1043                   if (spl == *pls)
1044                     replaceRule (pls, mtail, pr);
1045                   else
1046                     replaceRule (&spl, mtail, pr);
1047
1048                   /* if restart rule type then
1049                      start at the top again */
1050                   if (pr->restart)
1051                     {
1052                       restart = TRUE;
1053                     }
1054                 }
1055
1056               if (pr->vars)
1057                 {
1058                   hTabDeleteAll (pr->vars);
1059                   Safe_free (pr->vars);
1060                   pr->vars = NULL;
1061                 }
1062
1063               freeTrace (&_G.values);
1064             }
1065         }
1066     } while (restart == TRUE);
1067
1068   if (labelHash)
1069     {
1070       hTabDeleteAll (labelHash);
1071       freeTrace (&_G.labels);
1072     }
1073   labelHash = NULL;
1074 }
1075
1076
1077 /*-----------------------------------------------------------------*/
1078 /* readFileIntoBuffer - reads a file into a string buffer          */
1079 /*-----------------------------------------------------------------*/
1080 static char *
1081 readFileIntoBuffer (char *fname)
1082 {
1083   FILE *f;
1084   char *rs = NULL;
1085   int nch = 0;
1086   int ch;
1087   char lb[MAX_PATTERN_LEN];
1088
1089   if (!(f = fopen (fname, "r")))
1090     {
1091       fprintf (stderr, "cannot open peep rule file\n");
1092       return NULL;
1093     }
1094
1095   while ((ch = fgetc (f)) != EOF)
1096     {
1097       lb[nch++] = ch;
1098
1099       /* if we maxed out our local buffer */
1100       if (nch >= (MAX_PATTERN_LEN - 2))
1101         {
1102           lb[nch] = '\0';
1103           /* copy it into allocated buffer */
1104           if (rs)
1105             {
1106               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1107               strcat (rs, lb);
1108             }
1109           else
1110             {
1111               rs = Safe_alloc ( strlen (lb) + 1);
1112               strcpy (rs, lb);
1113             }
1114           nch = 0;
1115         }
1116     }
1117
1118   /* if some charaters left over */
1119   if (nch)
1120     {
1121       lb[nch] = '\0';
1122       /* copy it into allocated buffer */
1123       if (rs)
1124         {
1125           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1126           strcat (rs, lb);
1127         }
1128       else
1129         {
1130           rs = Safe_alloc ( strlen (lb) + 1);
1131           strcpy (rs, lb);
1132         }
1133     }
1134   return rs;
1135 }
1136
1137 /*-----------------------------------------------------------------*/
1138 /* initPeepHole - initialises the peep hole optimizer stuff        */
1139 /*-----------------------------------------------------------------*/
1140 void
1141 initPeepHole ()
1142 {
1143   char *s;
1144
1145   /* read in the default rules */
1146   readRules (port->peep.default_rules);
1147
1148   /* if we have any additional file read it too */
1149   if (options.peep_file)
1150     {
1151       readRules (s = readFileIntoBuffer (options.peep_file));
1152       setToNull ((void **) &s);
1153     }
1154
1155
1156 #if !OPT_DISABLE_PIC
1157   /* Convert the peep rules into pcode.
1158      NOTE: this is only support in the PIC port (at the moment)
1159   */
1160   if (TARGET_IS_PIC) {
1161     peepRules2pCode(rootRules);
1162   }
1163 #endif
1164
1165 }