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