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   else
 840     *shead = lhead;
 841   /* now for the tail */
 842   if (stail && stail->next)
 843     {
 844       stail->next->prev = cl;
 845       if (cl)
 846         cl->next = stail->next;
 847     }
 848 }
 849
 850 /* Returns TRUE if this line is a label definition.
 851
 852  * If so, start will point to the start of the label name,
 853  * and len will be it's length.
 854  */
 855 bool
 856 isLabelDefinition (const char *line, const char **start, int *len)
 857 {
 858   const char *cp = line;
 859
 860   /* This line is a label if if consists of:
 861    * [optional whitespace] followed by identifier chars
 862    * (alnum | $ | _ ) followed by a colon.
 863    */
 864
 865   while (*cp && isspace (*cp))
 866     {
 867       cp++;
 868     }
 869
 870   if (!*cp)
 871     {
 872       return FALSE;
 873     }
 874
 875   *start = cp;
 876
 877   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
 878     {
 879       cp++;
 880     }
 881
 882   if ((cp == *start) || (*cp != ':'))
 883     {
 884       return FALSE;
 885     }
 886
 887   *len = (cp - (*start));
 888   return TRUE;
 889 }
 890
 891 /* Quick & dirty string hash function. */
 892 static int
 893 hashSymbolName (const char *name)
 894 {
 895   int hash = 0;
 896
 897   while (*name)
 898     {
 899       hash = (hash << 6) ^ *name;
 900       name++;
 901     }
 902
 903   if (hash < 0)
 904     {
 905       hash = -hash;
 906     }
 907
 908   return hash % HTAB_SIZE;
 909 }
 910
 911 /* Build a hash of all labels in the passed set of lines
 912  * and how many times they are referenced.
 913  */
 914 static void
 915 buildLabelRefCountHash (lineNode * head)
 916 {
 917   lineNode *line;
 918   const char *label;
 919   int labelLen;
 920   int i;
 921
 922   assert (labelHash == NULL);
 923   labelHash = newHashTable (HTAB_SIZE);
 924
 925   /* First pass: locate all the labels. */
 926   line = head;
 927
 928   while (line)
 929     {
 930       if (isLabelDefinition (line->line, &label, &labelLen)
 931           && labelLen <= SDCC_NAME_MAX)
 932         {
 933           labelHashEntry *entry;
 934
 935           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
 936
 937           memcpy (entry->name, label, labelLen);
 938           entry->name[labelLen] = 0;
 939           entry->refCount = -1;
 940
 941           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
 942         }
 943       line = line->next;
 944     }
 945
 946
 947   /* Second pass: for each line, note all the referenced labels. */
 948   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
 949   line = head;
 950   while (line)
 951     {
 952       for (i = 0; i < HTAB_SIZE; i++)
 953         {
 954           labelHashEntry *thisEntry;
 955
 956           thisEntry = hTabFirstItemWK (labelHash, i);
 957
 958           while (thisEntry)
 959             {
 960               if (strstr (line->line, thisEntry->name))
 961                 {
 962                   thisEntry->refCount++;
 963                 }
 964               thisEntry = hTabNextItemWK (labelHash);
 965             }
 966         }
 967       line = line->next;
 968     }
 969
 970 #if 0
 971   /* Spew the contents of the table. Debugging fun only. */
 972   for (i = 0; i < HTAB_SIZE; i++)
 973     {
 974       labelHashEntry *thisEntry;
 975
 976       thisEntry = hTabFirstItemWK (labelHash, i);
 977
 978       while (thisEntry)
 979         {
 980           fprintf (stderr, "label: %s ref %d\n",
 981                    thisEntry->name, thisEntry->refCount);
 982           thisEntry = hTabNextItemWK (labelHash);
 983         }
 984     }
 985 #endif
 986 }
 987
 988 /* How does this work?
 989    peepHole
 990     For each rule,
 991      For each line,
 992       Try to match
 993       If it matches,
 994        replace and restart.
 995
 996     matchRule
 997      matchLine
 998
 999   Where is stuff allocated?
1000
1001 */
1002
1003 /*-----------------------------------------------------------------*/
1004 /* peepHole - matches & substitutes rules                          */
1005 /*-----------------------------------------------------------------*/
1006 void
1007 peepHole (lineNode ** pls)
1008 {
1009   lineNode *spl;
1010   peepRule *pr;
1011   lineNode *mtail = NULL;
1012   bool restart;
1013
1014   assert(labelHash == NULL);
1015
1016   do
1017     {
1018       restart = FALSE;
1019
1020       /* for all rules */
1021       for (pr = rootRules; pr; pr = pr->next)
1022         {
1023           for (spl = *pls; spl; spl = spl->next)
1024             {
1025               /* if inline assembler then no peep hole */
1026               if (spl->isInline)
1027                 continue;
1028
1029               mtail = NULL;
1030
1031               /* Tidy up any data stored in the hTab */
1032
1033               /* if it matches */
1034               if (matchRule (spl, &mtail, pr, *pls))
1035                 {
1036
1037                   /* then replace */
1038                   if (spl == *pls)
1039                     replaceRule (pls, mtail, pr);
1040                   else
1041                     replaceRule (&spl, mtail, pr);
1042
1043                   /* if restart rule type then
1044                      start at the top again */
1045                   if (pr->restart)
1046                     {
1047                       restart = TRUE;
1048                     }
1049                 }
1050
1051               if (pr->vars)
1052                 {
1053                   hTabDeleteAll (pr->vars);
1054                   Safe_free (pr->vars);
1055                   pr->vars = NULL;
1056                 }
1057
1058               freeTrace (&_G.values);
1059             }
1060         }
1061     } while (restart == TRUE);
1062
1063   if (labelHash)
1064     {
1065       hTabDeleteAll (labelHash);
1066       freeTrace (&_G.labels);
1067     }
1068   labelHash = NULL;
1069 }
1070
1071
1072 /*-----------------------------------------------------------------*/
1073 /* readFileIntoBuffer - reads a file into a string buffer          */
1074 /*-----------------------------------------------------------------*/
1075 static char *
1076 readFileIntoBuffer (char *fname)
1077 {
1078   FILE *f;
1079   char *rs = NULL;
1080   int nch = 0;
1081   int ch;
1082   char lb[MAX_PATTERN_LEN];
1083
1084   if (!(f = fopen (fname, "r")))
1085     {
1086       fprintf (stderr, "cannot open peep rule file\n");
1087       return NULL;
1088     }
1089
1090   while ((ch = fgetc (f)) != EOF)
1091     {
1092       lb[nch++] = ch;
1093
1094       /* if we maxed out our local buffer */
1095       if (nch >= (MAX_PATTERN_LEN - 2))
1096         {
1097           lb[nch] = '\0';
1098           /* copy it into allocated buffer */
1099           if (rs)
1100             {
1101               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1102               strcat (rs, lb);
1103             }
1104           else
1105             {
1106               rs = Safe_alloc ( strlen (lb) + 1);
1107               strcpy (rs, lb);
1108             }
1109           nch = 0;
1110         }
1111     }
1112
1113   /* if some charaters left over */
1114   if (nch)
1115     {
1116       lb[nch] = '\0';
1117       /* copy it into allocated buffer */
1118       if (rs)
1119         {
1120           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1121           strcat (rs, lb);
1122         }
1123       else
1124         {
1125           rs = Safe_alloc ( strlen (lb) + 1);
1126           strcpy (rs, lb);
1127         }
1128     }
1129   return rs;
1130 }
1131
1132 /*-----------------------------------------------------------------*/
1133 /* initPeepHole - initialises the peep hole optimizer stuff        */
1134 /*-----------------------------------------------------------------*/
1135 void
1136 initPeepHole ()
1137 {
1138   char *s;
1139
1140   /* read in the default rules */
1141   readRules (port->peep.default_rules);
1142
1143   /* if we have any additional file read it too */
1144   if (options.peep_file)
1145     {
1146       readRules (s = readFileIntoBuffer (options.peep_file));
1147       setToNull ((void **) &s);
1148     }
1149
1150
1151 #if !OPT_DISABLE_PIC
1152   /* Convert the peep rules into pcode.
1153      NOTE: this is only support in the PIC port (at the moment)
1154   */
1155   if (TARGET_IS_PIC) {
1156     peepRules2pCode(rootRules);
1157   }
1158 #endif
1159
1160 }