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_alloc ( strlen (cond) + 1);
 558       strcpy (pr->cond, cond);
 559     }
 560   else
 561     pr->cond = NULL;
 562
 563   pr->vars = newHashTable (100);
 564
 565   /* if root is empty */
 566   if (!rootRules)
 567     rootRules = currRule = pr;
 568   else
 569     currRule = currRule->next = pr;
 570
 571   return pr;
 572 }
 573
 574 /*-----------------------------------------------------------------*/
 575 /* newLineNode - creates a new peep line                           */
 576 /*-----------------------------------------------------------------*/
 577 lineNode *
 578 newLineNode (char *line)
 579 {
 580   lineNode *pl;
 581
 582   pl = Safe_alloc ( sizeof (lineNode));
 583   pl->line = Safe_alloc ( strlen (line) + 1);
 584   strcpy (pl->line, line);
 585   return pl;
 586 }
 587
 588 /*-----------------------------------------------------------------*/
 589 /* connectLine - connects two lines                                */
 590 /*-----------------------------------------------------------------*/
 591 lineNode *
 592 connectLine (lineNode * pl1, lineNode * pl2)
 593 {
 594   if (!pl1 || !pl2)
 595     {
 596       fprintf (stderr, "trying to connect null line\n");
 597       return NULL;
 598     }
 599
 600   pl2->prev = pl1;
 601   pl1->next = pl2;
 602
 603   return pl2;
 604 }
 605
 606 #define SKIP_SPACE(x,y) { while (*x && (isspace(*x) || *x == '\n')) x++; \
 607                          if (!*x) { fprintf(stderr,y); return ; } }
 608
 609 #define EXPECT_STR(x,y,z) { while (*x && strncmp(x,y,strlen(y))) x++ ;   \
 610                            if (!*x) { fprintf(stderr,z); return ; } }
 611 #define EXPECT_CHR(x,y,z) { while (*x && *x != y) x++ ;   \
 612                            if (!*x) { fprintf(stderr,z); return ; } }
 613
 614 /*-----------------------------------------------------------------*/
 615 /* getPeepLine - parses the peep lines                             */
 616 /*-----------------------------------------------------------------*/
 617 static void
 618 getPeepLine (lineNode ** head, char **bpp)
 619 {
 620   char lines[MAX_PATTERN_LEN];
 621   char *lp;
 622
 623   lineNode *currL = NULL;
 624   char *bp = *bpp;
 625   while (1)
 626     {
 627
 628       if (!*bp)
 629         {
 630           fprintf (stderr, "unexpected end of match pattern\n");
 631           return;
 632         }
 633
 634       if (*bp == '\n')
 635         {
 636           bp++;
 637           while (isspace (*bp) ||
 638                  *bp == '\n')
 639             bp++;
 640         }
 641
 642       if (*bp == '}')
 643         {
 644           bp++;
 645           break;
 646         }
 647
 648       /* read till end of line */
 649       lp = lines;
 650       while ((*bp != '\n' && *bp != '}') && *bp)
 651         *lp++ = *bp++;
 652
 653       *lp = '\0';
 654       if (!currL)
 655         *head = currL = newLineNode (lines);
 656       else
 657         currL = connectLine (currL, newLineNode (lines));
 658     }
 659
 660   *bpp = bp;
 661 }
 662
 663 /*-----------------------------------------------------------------*/
 664 /* readRules - reads the rules from a string buffer                */
 665 /*-----------------------------------------------------------------*/
 666 static void
 667 readRules (char *bp)
 668 {
 669   char restart = 0;
 670   char lines[MAX_PATTERN_LEN];
 671   char *lp;
 672   lineNode *match;
 673   lineNode *replace;
 674   lineNode *currL = NULL;
 675
 676   if (!bp)
 677     return;
 678 top:
 679   restart = 0;
 680   /* look for the token "replace" that is the
 681      start of a rule */
 682   while (*bp && strncmp (bp, "replace", 7))
 683     bp++;
 684
 685   /* if not found */
 686   if (!*bp)
 687     return;
 688
 689   /* then look for either "restart" or '{' */
 690   while (strncmp (bp, "restart", 7) &&
 691          *bp != '{' && bp)
 692     bp++;
 693
 694   /* not found */
 695   if (!*bp)
 696     {
 697       fprintf (stderr, "expected 'restart' or '{'\n");
 698       return;
 699     }
 700
 701   /* if brace */
 702   if (*bp == '{')
 703     bp++;
 704   else
 705     {                           /* must be restart */
 706       restart++;
 707       bp += strlen ("restart");
 708       /* look for '{' */
 709       EXPECT_CHR (bp, '{', "expected '{'\n");
 710       bp++;
 711     }
 712
 713   /* skip thru all the blank space */
 714   SKIP_SPACE (bp, "unexpected end of rule\n");
 715
 716   match = replace = currL = NULL;
 717   /* we are the start of a rule */
 718   getPeepLine (&match, &bp);
 719
 720   /* now look for by */
 721   EXPECT_STR (bp, "by", "expected 'by'\n");
 722
 723   /* then look for a '{' */
 724   EXPECT_CHR (bp, '{', "expected '{'\n");
 725   bp++;
 726
 727   SKIP_SPACE (bp, "unexpected end of rule\n");
 728   getPeepLine (&replace, &bp);
 729
 730   /* look for a 'if' */
 731   while ((isspace (*bp) || *bp == '\n') && *bp)
 732     bp++;
 733
 734   if (strncmp (bp, "if", 2) == 0)
 735     {
 736       bp += 2;
 737       while ((isspace (*bp) || *bp == '\n') && *bp)
 738         bp++;
 739       if (!*bp)
 740         {
 741           fprintf (stderr, "expected condition name\n");
 742           return;
 743         }
 744
 745       /* look for the condition */
 746       lp = lines;
 747       while (*bp && (*bp != '\n'))
 748         {
 749           *lp++ = *bp++;
 750         }
 751       *lp = '\0';
 752
 753       newPeepRule (match, replace, lines, restart);
 754     }
 755   else
 756     newPeepRule (match, replace, NULL, restart);
 757   goto top;
 758
 759 }
 760
 761 /*-----------------------------------------------------------------*/
 762 /* keyForVar - returns the numeric key for a var                   */
 763 /*-----------------------------------------------------------------*/
 764 static int
 765 keyForVar (char *d)
 766 {
 767   int i = 0;
 768
 769   while (isdigit (*d))
 770     {
 771       i *= 10;
 772       i += (*d++ - '0');
 773     }
 774
 775   return i;
 776 }
 777
 778 /*-----------------------------------------------------------------*/
 779 /* bindVar - binds a value to a variable in the given hashtable    */
 780 /*-----------------------------------------------------------------*/
 781 static void
 782 bindVar (int key, char **s, hTab ** vtab)
 783 {
 784   char vval[MAX_PATTERN_LEN];
 785   char *vvx;
 786   char *vv = vval;
 787
 788   /* first get the value of the variable */
 789   vvx = *s;
 790   /* the value is ended by a ',' or space or newline or null or ) */
 791   while (*vvx &&
 792          *vvx != ',' &&
 793          !isspace (*vvx) &&
 794          *vvx != '\n' &&
 795          *vvx != ':' &&
 796          *vvx != ')')
 797     {
 798       char ubb = 0;
 799       /* if we find a '(' then we need to balance it */
 800       if (*vvx == '(')
 801         {
 802           ubb++;
 803           while (ubb)
 804             {
 805               *vv++ = *vvx++;
 806               if (*vvx == '(')
 807                 ubb++;
 808               if (*vvx == ')')
 809                 ubb--;
 810             }
 811           // include the trailing ')'
 812           *vv++ = *vvx++;
 813         }
 814       else
 815         *vv++ = *vvx++;
 816     }
 817   *s = vvx;
 818   *vv = '\0';
 819   /* got value */
 820   vvx = traceAlloc (&_G.values, Safe_alloc(strlen (vval) + 1));
 821   strcpy (vvx, vval);
 822
 823   hTabAddItem (vtab, key, vvx);
 824 }
 825
 826 /*-----------------------------------------------------------------*/
 827 /* matchLine - matches one line                                    */
 828 /*-----------------------------------------------------------------*/
 829 static bool
 830 matchLine (char *s, char *d, hTab ** vars)
 831 {
 832
 833   if (!s || !(*s))
 834     return FALSE;
 835
 836   while (*s && *d)
 837     {
 838
 839       /* skip white space in both */
 840       while (isspace (*s))
 841         s++;
 842       while (isspace (*d))
 843         d++;
 844
 845       /* if the destination is a var */
 846       if (*d == '%' && isdigit (*(d + 1)))
 847         {
 848           char *v = hTabItemWithKey (*vars, keyForVar (d + 1));
 849           /* if the variable is already bound
 850              then it MUST match with dest */
 851           if (v)
 852             {
 853               while (*v)
 854                 if (*v++ != *s++)
 855                   return FALSE;
 856             }
 857           else
 858             /* variable not bound we need to
 859                bind it */
 860             bindVar (keyForVar (d + 1), &s, vars);
 861
 862           /* in either case go past the variable */
 863           d++;
 864           while (isdigit (*d))
 865             d++;
 866         }
 867
 868       /* they should be an exact match other wise */
 869       if (*s && *d)
 870         {
 871           while (isspace (*s))
 872             s++;
 873           while (isspace (*d))
 874             d++;
 875           if (*s++ != *d++)
 876             return FALSE;
 877         }
 878
 879     }
 880
 881   /* get rid of the trailing spaces
 882      in both source & destination */
 883   if (*s)
 884     while (isspace (*s))
 885       s++;
 886
 887   if (*d)
 888     while (isspace (*d))
 889       d++;
 890
 891   /* after all this if only one of them
 892      has something left over then no match */
 893   if (*s || *d)
 894     return FALSE;
 895
 896   return TRUE;
 897 }
 898
 899 /*-----------------------------------------------------------------*/
 900 /* matchRule - matches a all the rule lines                        */
 901 /*-----------------------------------------------------------------*/
 902 static bool
 903 matchRule (lineNode * pl,
 904            lineNode ** mtail,
 905            peepRule * pr,
 906            lineNode * head)
 907 {
 908   lineNode *spl;                /* source pl */
 909   lineNode *rpl;                /* rule peep line */
 910
 911 /*     setToNull((void **) &pr->vars);    */
 912 /*     pr->vars = newHashTable(100); */
 913
 914   /* for all the lines defined in the rule */
 915   rpl = pr->match;
 916   spl = pl;
 917   while (spl && rpl)
 918     {
 919
 920       /* if the source line starts with a ';' then
 921          comment line don't process or the source line
 922          contains == . debugger information skip it */
 923       if (spl->line &&
 924           (*spl->line == ';' || spl->isDebug))
 925         {
 926           spl = spl->next;
 927           continue;
 928         }
 929
 930       if (!matchLine (spl->line, rpl->line, &pr->vars))
 931         return FALSE;
 932
 933       rpl = rpl->next;
 934       if (rpl)
 935         spl = spl->next;
 936     }
 937
 938   /* if rules ended */
 939   if (!rpl)
 940     {
 941       /* if this rule has additional conditions */
 942       if (pr->cond)
 943         {
 944           if (callFuncByName (pr->cond, pr->vars, pl, head))
 945             {
 946               *mtail = spl;
 947               return TRUE;
 948             }
 949           else
 950             return FALSE;
 951         }
 952       else
 953         {
 954           *mtail = spl;
 955           return TRUE;
 956         }
 957     }
 958   else
 959     return FALSE;
 960 }
 961
 962 /*-----------------------------------------------------------------*/
 963 /* replaceRule - does replacement of a matching pattern            */
 964 /*-----------------------------------------------------------------*/
 965 static void
 966 replaceRule (lineNode ** shead, lineNode * stail, peepRule * pr)
 967 {
 968   lineNode *cl = NULL;
 969   lineNode *pl = NULL, *lhead = NULL;
 970   /* a long function name and long variable name can evaluate to
 971      4x max pattern length e.g. "mov dptr,((fie_var>>8)<<8)+fie_var" */
 972   char lb[MAX_PATTERN_LEN*4];
 973   char *lbp;
 974   lineNode *comment = NULL;
 975
 976   /* collect all the comment lines in the source */
 977   for (cl = *shead; cl != stail; cl = cl->next)
 978     {
 979       if (cl->line && (*cl->line == ';' || cl->isDebug))
 980         {
 981           pl = (pl ? connectLine (pl, newLineNode (cl->line)) :
 982                 (comment = newLineNode (cl->line)));
 983           pl->isDebug = cl->isDebug;
 984         }
 985     }
 986   cl = NULL;
 987
 988   /* for all the lines in the replacement pattern do */
 989   for (pl = pr->replace; pl; pl = pl->next)
 990     {
 991       char *v;
 992       char *l;
 993       lbp = lb;
 994
 995       l = pl->line;
 996
 997       while (*l)
 998         {
 999           /* if the line contains a variable */
1000           if (*l == '%' && isdigit (*(l + 1)))
1001             {
1002               v = hTabItemWithKey (pr->vars, keyForVar (l + 1));
1003               if (!v)
1004                 {
1005                   fprintf (stderr, "used unbound variable in replacement\n");
1006                   l++;
1007                   continue;
1008                 }
1009               while (*v) {
1010                 *lbp++ = *v++;
1011               }
1012               l++;
1013               while (isdigit (*l)) {
1014                 l++;
1015               }
1016               continue;
1017             }
1018           *lbp++ = *l++;
1019         }
1020
1021       *lbp = '\0';
1022       if (cl)
1023         cl = connectLine (cl, newLineNode (lb));
1024       else
1025         lhead = cl = newLineNode (lb);
1026     }
1027
1028   /* add the comments if any to the head of list */
1029   if (comment)
1030     {
1031       lineNode *lc = comment;
1032       while (lc->next)
1033         lc = lc->next;
1034       lc->next = lhead;
1035       if (lhead)
1036         lhead->prev = lc;
1037       lhead = comment;
1038     }
1039
1040   /* now we need to connect / replace the original chain */
1041   /* if there is a prev then change it */
1042   if ((*shead)->prev)
1043     {
1044       (*shead)->prev->next = lhead;
1045       lhead->prev = (*shead)->prev;
1046     }
1047   *shead = lhead;
1048   /* now for the tail */
1049   if (stail && stail->next)
1050     {
1051       stail->next->prev = cl;
1052       if (cl)
1053         cl->next = stail->next;
1054     }
1055 }
1056
1057 /* Returns TRUE if this line is a label definition.
1058
1059  * If so, start will point to the start of the label name,
1060  * and len will be it's length.
1061  */
1062 bool
1063 isLabelDefinition (const char *line, const char **start, int *len)
1064 {
1065   const char *cp = line;
1066
1067   /* This line is a label if if consists of:
1068    * [optional whitespace] followed by identifier chars
1069    * (alnum | $ | _ ) followed by a colon.
1070    */
1071
1072   while (*cp && isspace (*cp))
1073     {
1074       cp++;
1075     }
1076
1077   if (!*cp)
1078     {
1079       return FALSE;
1080     }
1081
1082   *start = cp;
1083
1084   while (isalnum (*cp) || (*cp == '$') || (*cp == '_'))
1085     {
1086       cp++;
1087     }
1088
1089   if ((cp == *start) || (*cp != ':'))
1090     {
1091       return FALSE;
1092     }
1093
1094   *len = (cp - (*start));
1095   return TRUE;
1096 }
1097
1098 /* Quick & dirty string hash function. */
1099 static int
1100 hashSymbolName (const char *name)
1101 {
1102   int hash = 0;
1103
1104   while (*name)
1105     {
1106       hash = (hash << 6) ^ *name;
1107       name++;
1108     }
1109
1110   if (hash < 0)
1111     {
1112       hash = -hash;
1113     }
1114
1115   return hash % HTAB_SIZE;
1116 }
1117
1118 /* Build a hash of all labels in the passed set of lines
1119  * and how many times they are referenced.
1120  */
1121 static void
1122 buildLabelRefCountHash (lineNode * head)
1123 {
1124   lineNode *line;
1125   const char *label;
1126   int labelLen;
1127   int i;
1128
1129   assert (labelHash == NULL);
1130   labelHash = newHashTable (HTAB_SIZE);
1131
1132   /* First pass: locate all the labels. */
1133   line = head;
1134
1135   while (line)
1136     {
1137       if (isLabelDefinition (line->line, &label, &labelLen)
1138           && labelLen <= SDCC_NAME_MAX)
1139         {
1140           labelHashEntry *entry;
1141
1142           entry = traceAlloc (&_G.labels, Safe_alloc(sizeof (labelHashEntry)));
1143
1144           memcpy (entry->name, label, labelLen);
1145           entry->name[labelLen] = 0;
1146           entry->refCount = -1;
1147
1148           hTabAddItem (&labelHash, hashSymbolName (entry->name), entry);
1149         }
1150       line = line->next;
1151     }
1152
1153
1154   /* Second pass: for each line, note all the referenced labels. */
1155   /* This is ugly, O(N^2) stuff. Optimizations welcome... */
1156   line = head;
1157   while (line)
1158     {
1159       for (i = 0; i < HTAB_SIZE; i++)
1160         {
1161           labelHashEntry *thisEntry;
1162
1163           thisEntry = hTabFirstItemWK (labelHash, i);
1164
1165           while (thisEntry)
1166             {
1167               if (strstr (line->line, thisEntry->name))
1168                 {
1169                   thisEntry->refCount++;
1170                 }
1171               thisEntry = hTabNextItemWK (labelHash);
1172             }
1173         }
1174       line = line->next;
1175     }
1176
1177 #if 0
1178   /* Spew the contents of the table. Debugging fun only. */
1179   for (i = 0; i < HTAB_SIZE; i++)
1180     {
1181       labelHashEntry *thisEntry;
1182
1183       thisEntry = hTabFirstItemWK (labelHash, i);
1184
1185       while (thisEntry)
1186         {
1187           fprintf (stderr, "label: %s ref %d\n",
1188                    thisEntry->name, thisEntry->refCount);
1189           thisEntry = hTabNextItemWK (labelHash);
1190         }
1191     }
1192 #endif
1193 }
1194
1195 /* How does this work?
1196    peepHole
1197     For each rule,
1198      For each line,
1199       Try to match
1200       If it matches,
1201        replace and restart.
1202
1203     matchRule
1204      matchLine
1205
1206   Where is stuff allocated?
1207
1208 */
1209
1210 /*-----------------------------------------------------------------*/
1211 /* peepHole - matches & substitutes rules                          */
1212 /*-----------------------------------------------------------------*/
1213 void
1214 peepHole (lineNode ** pls)
1215 {
1216   lineNode *spl;
1217   peepRule *pr;
1218   lineNode *mtail = NULL;
1219   bool restart;
1220
1221 #if !OPT_DISABLE_PIC
1222   /* The PIC port uses a different peep hole optimizer based on "pCode" */
1223   if (TARGET_IS_PIC)
1224     return;
1225 #endif
1226
1227   assert(labelHash == NULL);
1228
1229   do
1230     {
1231       restart = FALSE;
1232
1233       /* for all rules */
1234       for (pr = rootRules; pr; pr = pr->next)
1235         {
1236           for (spl = *pls; spl; spl = spl->next)
1237             {
1238               /* if inline assembler then no peep hole */
1239               if (spl->isInline)
1240                 continue;
1241
1242               mtail = NULL;
1243
1244               /* Tidy up any data stored in the hTab */
1245
1246               /* if it matches */
1247               if (matchRule (spl, &mtail, pr, *pls))
1248                 {
1249
1250                   /* then replace */
1251                   if (spl == *pls)
1252                     replaceRule (pls, mtail, pr);
1253                   else
1254                     replaceRule (&spl, mtail, pr);
1255
1256                   /* if restart rule type then
1257                      start at the top again */
1258                   if (pr->restart)
1259                     {
1260                       restart = TRUE;
1261                     }
1262                 }
1263
1264               if (pr->vars)
1265                 {
1266                   hTabDeleteAll (pr->vars);
1267                   Safe_free (pr->vars);
1268                   pr->vars = NULL;
1269                 }
1270
1271               freeTrace (&_G.values);
1272             }
1273         }
1274     } while (restart == TRUE);
1275
1276   if (labelHash)
1277     {
1278       hTabDeleteAll (labelHash);
1279       freeTrace (&_G.labels);
1280     }
1281   labelHash = NULL;
1282 }
1283
1284
1285 /*-----------------------------------------------------------------*/
1286 /* readFileIntoBuffer - reads a file into a string buffer          */
1287 /*-----------------------------------------------------------------*/
1288 static char *
1289 readFileIntoBuffer (char *fname)
1290 {
1291   FILE *f;
1292   char *rs = NULL;
1293   int nch = 0;
1294   int ch;
1295   char lb[MAX_PATTERN_LEN];
1296
1297   if (!(f = fopen (fname, "r")))
1298     {
1299       fprintf (stderr, "cannot open peep rule file\n");
1300       return NULL;
1301     }
1302
1303   while ((ch = fgetc (f)) != EOF)
1304     {
1305       lb[nch++] = ch;
1306
1307       /* if we maxed out our local buffer */
1308       if (nch >= (MAX_PATTERN_LEN - 2))
1309         {
1310           lb[nch] = '\0';
1311           /* copy it into allocated buffer */
1312           if (rs)
1313             {
1314               rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1315               strcat (rs, lb);
1316             }
1317           else
1318             {
1319               rs = Safe_alloc ( strlen (lb) + 1);
1320               strcpy (rs, lb);
1321             }
1322           nch = 0;
1323         }
1324     }
1325
1326   /* if some charaters left over */
1327   if (nch)
1328     {
1329       lb[nch] = '\0';
1330       /* copy it into allocated buffer */
1331       if (rs)
1332         {
1333           rs = Safe_realloc (rs, strlen (rs) + strlen (lb) + 1);
1334           strcat (rs, lb);
1335         }
1336       else
1337         {
1338           rs = Safe_alloc ( strlen (lb) + 1);
1339           strcpy (rs, lb);
1340         }
1341     }
1342   return rs;
1343 }
1344
1345 /*-----------------------------------------------------------------*/
1346 /* initPeepHole - initialises the peep hole optimizer stuff        */
1347 /*-----------------------------------------------------------------*/
1348 void
1349 initPeepHole ()
1350 {
1351   char *s;
1352
1353   /* read in the default rules */
1354   readRules (port->peep.default_rules);
1355
1356   /* if we have any additional file read it too */
1357   if (options.peep_file)
1358     {
1359       readRules (s = readFileIntoBuffer (options.peep_file));
1360       setToNull ((void **) &s);
1361     }
1362
1363
1364 #if !OPT_DISABLE_PIC
1365   /* Convert the peep rules into pcode.
1366      NOTE: this is only support in the PIC port (at the moment)
1367   */
1368   if (TARGET_IS_PIC) {
1369     peepRules2pCode(rootRules);
1370   }
1371 #endif
1372
1373 }