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