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 /*-----------------------------------------------------------------*/
 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       "operandsNotSame", operandsNotSame
 455     }
 456     ,
 457     {
 458       "operandsNotSame3", operandsNotSame3
 459     }
 460     ,
 461     {
 462       "operandsNotSame4", operandsNotSame4
 463     }
 464     ,
 465     {
 466       "operandsNotSame5", operandsNotSame5
 467     }
 468     ,
 469     {
 470       "operandsNotSame6", operandsNotSame6
 471     }
 472     ,
 473     {
 474       "operandsNotSame7", operandsNotSame7
 475     }
 476     ,
 477     {
 478       "operandsNotSame8", operandsNotSame8
 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_alloc(strlen (vval) + 1));
 819   strcpy (vvx, vval);
 820
 821   hTabAddItem (vtab, key, vvx);
 822 }
 823
 824 /*-----------------------------------------------------------------*/
 825 /* matchLine - matches one line                                    */
 826 /*-----------------------------------------------------------------*/
 827 static bool
 828 matchLine (char *s, char *d, hTab ** vars)
 829 {
 830
 831   if (!s || !(*s))
 832     return FALSE;
 833
 834   while (*s && *d)
 835     {
 836
 837       /* skip white space in both */
 838       while (isspace (*s))
 839         s++;
 840       while (isspace (*d))
 841         d++;
 842
 843       /* if the destination is a var */
 844       if (*d == '%' && isdigit (*(d + 1)))
 845         {
 846           char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
 847           /* if the variable is already bound
 848              then it MUST match with dest */
 849           if (v)
 850             {
 851               while (*v)
 852                 if (*v++ != *s++)
 853                   return FALSE;
 854             }
 855           else
 856             /* variable not bound we need to
 857                bind it */
 858             bindVar (keyForVar (d + 1), &s, vars);
 859
 860           /* in either case go past the variable */
 861           d++;
 862           while (isdigit (*d))
 863             d++;
 864         }
 865
 866       /* they should be an exact match other wise */
 867       if (*s && *d)
 868         {
 869           while (isspace (*s))
 870             s++;
 871           while (isspace (*d))
 872             d++;
 873           if (*s++ != *d++)
 874             return FALSE;
 875         }
 876
 877     }
 878
 879   /* get rid of the trailing spaces
 880      in both source & destination */
 881   if (*s)
 882     while (isspace (*s))
 883       s++;
 884
 885   if (*d)
 886     while (isspace (*d))
 887       d++;
 888
 889   /* after all this if only one of them
 890      has something left over then no match */
 891   if (*s || *d)
 892     return FALSE;
 893
 894   return TRUE;
 895 }
 896
 897 /*-----------------------------------------------------------------*/
 898 /* matchRule - matches a all the rule lines                        */
 899 /*-----------------------------------------------------------------*/
 900 static bool
 901 matchRule (lineNode * pl,
 902            lineNode ** mtail,
 903            peepRule * pr,
 904            lineNode * head)
 905 {
 906   lineNode *spl;                /* source pl */
 907   lineNode *rpl;                /* rule peep line */
 908
 909 /*     setToNull((void **) &pr->vars);    */
 910 /*     pr->vars = newHashTable(100); */
 911
 912   /* for all the lines defined in the rule */
 913   rpl = pr->match;
 914   spl = pl;
 915   while (spl && rpl)
 916     {
 917
 918       /* if the source line starts with a ';' then
 919          comment line don't process or the source line
 920          contains == . debugger information skip it */
 921       if (spl->line &&
 922           (*spl->line == ';' || spl->isDebug))
 923         {
 924           spl = spl->next;
 925           continue;
 926         }
 927
 928       if (!matchLine (spl->line, rpl->line, &pr->vars))
 929         return FALSE;
 930
 931       rpl = rpl->next;
 932       if (rpl)
 933         spl = spl->next;
 934     }
 935
 936   /* if rules ended */
 937   if (!rpl)
 938     {
 939       /* if this rule has additional conditions */
 940       if (pr->cond)
 941         {
 942           if (callFuncByName (pr->cond, pr->vars, pl, head))
 943             {
 944               *mtail = spl;
 945               return TRUE;
 946             }
 947           else
 948             return FALSE;
 949         }
 950       else
 951         {
 952           *mtail = spl;
 953           return TRUE;
 954         }
 955     }
 956   else
 957     return FALSE;
 958 }
 959
 960 /*-----------------------------------------------------------------*/
 961 /* replaceRule - does replacement of a matching pattern            */
 962 /*-----------------------------------------------------------------*/
 963 static void
 964 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
 965 {
 966   lineNode *cl = NULL;
 967   lineNode *pl = NULL, *lhead = NULL;
 968   /* a long function name and long variable name can evaluate to
 969      4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
 970   char lb[MAX_PATTERN_LEN*4];
 971   char *lbp;
 972   lineNode *comment = NULL;
 973
 974   /* collect all the comment lines in the source */
 975   for (cl = *shead; cl != stail; cl = cl->next)
 976     {
 977       if (cl->line && (*cl->line == ';' || cl->isDebug))
 978         {
 979           pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
 980                 (comment = newLineNode (cl->line)));
 981           pl->isDebug = cl->isDebug;
 982         }
 983     }
 984   cl = NULL;
 985
 986   /* for all the lines in the replacement pattern do */
 987   for (pl = pr->replace; pl; pl = pl->next)
 988     {
 989       char *v;
 990       char *l;
 991       lbp = lb;
 992
 993       l = pl->line;
 994
 995       while (*l)
 996         {
 997           /* if the line contains a variable */
 998           if (*l == '%' && isdigit (*(l + 1)))
 999             {
1000               v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
1001               if (!v)
1002                 {
1003                   fprintf (stderr, "used unbound variable in replacement\n");
1004                   l++;
1005                   continue;
1006                 }
1007               while (*v) {
1008                 *lbp++ = *v++;
1009               }
1010               l++;
1011               while (isdigit (*l)) {
1012                 l++;
1013               }
1014               continue;
1015             }
1016           *lbp++ = *l++;
1017         }
1018
1019       *lbp = '\0';
1020       if (cl)
1021         cl = connectLine (cl, newLineNode (lb));
1022       else
1023         lhead = cl = newLineNode (lb);
1024     }
1025
1026   /* add the comments if any to the head of list */
1027   if (comment)
1028     {
1029       lineNode *lc = comment;
1030       while (lc->next)
1031         lc = lc->next;
1032       lc->next = lhead;
1033       if (lhead)
1034         lhead->prev = lc;
1035       lhead = comment;
1036     }
1037
1038   /* now we need to connect / replace the original chain */
1039   /* if there is a prev then change it */
1040   if ((*shead)->prev)
1041     {
1042       (*shead)->prev->next = lhead;
1043       lhead->prev = (*shead)->prev;
1044     }
1045   *shead = lhead;
1046   /* now for the tail */
1047   if (stail && stail->next)
1048     {
1049       stail->next->prev = cl;
1050       if (cl)
1051         cl->next = stail->next;
1052     }
1053 }
1054
1055 /* Returns TRUE if this line is a label definition.
1056
1057  * If so, start will point to the start of the label name,
1058  * and len will be it's length.
1059  */
1060 bool
1061 isLabelDefinition (const char *line, const char **start, int *len)
1062 {
1063   const char *cp = line;
1064
1065   /* This line is a label if if consists of:
1066    * [optional whitespace] followed by identifier chars
1067    * (alnum | $ | _ ) followed by a colon.
1068    */
1069
1070   while (*cp && isspace (*cp))
1071     {
1072       cp++;
1073     }
1074
1075   if (!*cp)
1076     {
1077       return FALSE;
1078     }
1079
1080   *start = cp;
1081
1082   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
1083     {
1084       cp++;
1085     }
1086
1087   if ((cp == *start) || (*cp != ':'))
1088     {
1089       return FALSE;
1090     }
1091
1092   *len = (cp - (*start));
1093   return TRUE;
1094 }
1095
1096 /* Quick & dirty string hash function. */
1097 static int
1098 hashSymbolName (const char *name)
1099 {
1100   int hash = 0;
1101
1102   while (*name)
1103     {
1104       hash = (hash << 6) ^ *name;
1105       name++;
1106     }
1107
1108   if (hash < 0)
1109     {
1110       hash = -hash;
1111     }
1112
1113   return hash % HTAB_SIZE;
1114 }
1115
1116 /* Build a hash of all labels in the passed set of lines
1117  * and how many times they are referenced.
1118  */
1119 static void
1120 buildLabelRefCountHash (lineNode * head)
1121 {
1122   lineNode *line;
1123   const char *label;
1124   int labelLen;
1125   int i;
1126
1127   assert (labelHash == NULL);
1128   labelHash = newHashTable (HTAB_SIZE);
1129
1130   /* First pass: locate all the labels. */
1131   line = head;
1132
1133   while (line)
1134     {
1135       if (isLabelDefinition (line->line, &label, &labelLen)
1136           && labelLen <= SDCC_NAME_MAX)
1137         {
1138           labelHashEntry *entry;
1139
1140           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
1141
1142           memcpy (entry->name, label, labelLen);
1143           entry->name[labelLen] = 0;
1144           entry->refCount = -1;
1145
1146           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
1147         }
1148       line = line->next;
1149     }
1150
1151
1152   /* Second pass: for each line, note all the referenced labels. */
1153   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
1154   line = head;
1155   while (line)
1156     {
1157       for (i = 0; i < HTAB_SIZE; i++)
1158         {
1159           labelHashEntry *thisEntry;
1160
1161           thisEntry = hTabFirstItemWK (labelHash, i);
1162
1163           while (thisEntry)
1164             {
1165               if (strstr (line->line, thisEntry->name))
1166                 {
1167                   thisEntry->refCount++;
1168                 }
1169               thisEntry = hTabNextItemWK (labelHash);
1170             }
1171         }
1172       line = line->next;
1173     }
1174
1175 #if 0
1176   /* Spew the contents of the table. Debugging fun only. */
1177   for (i = 0; i < HTAB_SIZE; i++)
1178     {
1179       labelHashEntry *thisEntry;
1180
1181       thisEntry = hTabFirstItemWK (labelHash, i);
1182
1183       while (thisEntry)
1184         {
1185           fprintf (stderr, "label: %s ref %d\n",
1186                    thisEntry->name, thisEntry->refCount);
1187           thisEntry = hTabNextItemWK (labelHash);
1188         }
1189     }
1190 #endif
1191 }
1192
1193 /* How does this work?
1194    peepHole
1195     For each rule,
1196      For each line,
1197       Try to match
1198       If it matches,
1199        replace and restart.
1200
1201     matchRule
1202      matchLine
1203
1204   Where is stuff allocated?
1205
1206 */
1207
1208 /*-----------------------------------------------------------------*/
1209 /* peepHole - matches & substitutes rules                          */
1210 /*-----------------------------------------------------------------*/
1211 void
1212 peepHole (lineNode ** pls)
1213 {
1214   lineNode *spl;
1215   peepRule *pr;
1216   lineNode *mtail = NULL;
1217   bool restart;
1218
1219 #if !OPT_DISABLE_PIC
1220   /* The PIC port uses a different peep hole optimizer based on "pCode" */
1221   if (TARGET_IS_PIC)
1222     return;
1223 #endif
1224
1225   assert(labelHash == NULL);
1226
1227   do
1228     {
1229       restart = FALSE;
1230
1231       /* for all rules */
1232       for (pr = rootRules; pr; pr = pr->next)
1233         {
1234           for (spl = *pls; spl; spl = spl->next)
1235             {
1236               /* if inline assembler then no peep hole */
1237               if (spl->isInline)
1238                 continue;
1239
1240               mtail = NULL;
1241
1242               /* Tidy up any data stored in the hTab */
1243
1244               /* if it matches */
1245               if (matchRule (spl, &mtail, pr, *pls))
1246                 {
1247
1248                   /* then replace */
1249                   if (spl == *pls)
1250                     replaceRule (pls, mtail, pr);
1251                   else
1252                     replaceRule (&spl, mtail, pr);
1253
1254                   /* if restart rule type then
1255                      start at the top again */
1256                   if (pr->restart)
1257                     {
1258                       restart = TRUE;
1259                     }
1260                 }
1261
1262               if (pr->vars)
1263                 {
1264                   hTabDeleteAll (pr->vars);
1265                   Safe_free (pr->vars);
1266                   pr->vars = NULL;
1267                 }
1268
1269               freeTrace (&_G.values);
1270             }
1271         }
1272     } while (restart == TRUE);
1273
1274   if (labelHash)
1275     {
1276       hTabDeleteAll (labelHash);
1277       freeTrace (&_G.labels);
1278     }
1279   labelHash = NULL;
1280 }
1281
1282
1283 /*-----------------------------------------------------------------*/
1284 /* readFileIntoBuffer - reads a file into a string buffer          */
1285 /*-----------------------------------------------------------------*/
1286 static char *
1287 readFileIntoBuffer (char *fname)
1288 {
1289   FILE *f;
1290   char *rs = NULL;
1291   int nch = 0;
1292   int ch;
1293   char lb[MAX_PATTERN_LEN];
1294
1295   if (!(f = fopen (fname, "r")))
1296     {
1297       fprintf (stderr, "cannot open peep rule file\n");
1298       return NULL;
1299     }
1300
1301   while ((ch = fgetc (f)) != EOF)
1302     {
1303       lb[nch++] = ch;
1304
1305       /* if we maxed out our local buffer */
1306       if (nch >= (MAX_PATTERN_LEN - 2))
1307         {
1308           lb[nch] = '\0';
1309           /* copy it into allocated buffer */
1310           if (rs)
1311             {
1312               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1313               strcat (rs, lb);
1314             }
1315           else
1316             {
1317               rs = Safe_strdup (lb);
1318             }
1319           nch = 0;
1320         }
1321     }
1322
1323   /* if some charaters left over */
1324   if (nch)
1325     {
1326       lb[nch] = '\0';
1327       /* copy it into allocated buffer */
1328       if (rs)
1329         {
1330           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1331           strcat (rs, lb);
1332         }
1333       else
1334         {
1335           rs = Safe_strdup (lb);
1336         }
1337     }
1338   return rs;
1339 }
1340
1341 /*-----------------------------------------------------------------*/
1342 /* initPeepHole - initialises the peep hole optimizer stuff        */
1343 /*-----------------------------------------------------------------*/
1344 void
1345 initPeepHole ()
1346 {
1347   char *s;
1348
1349   /* read in the default rules */
1350   readRules (port->peep.default_rules);
1351
1352   /* if we have any additional file read it too */
1353   if (options.peep_file)
1354     {
1355       readRules (s = readFileIntoBuffer (options.peep_file));
1356       setToNull ((void **) &s);
1357     }
1358
1359
1360 #if !OPT_DISABLE_PIC
1361   /* Convert the peep rules into pcode.
1362      NOTE: this is only support in the PIC port (at the moment)
1363   */
1364   if (TARGET_IS_PIC) {
1365     peepRules2pCode(rootRules);
1366   }
1367 #endif
1368
1369 }