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