git.gag.com Git - fw/sdcc/blob - src/mcs51/peep.c

   1 /*-------------------------------------------------------------------------
   2   peep.c - source file for peephole optimizer helper functions
   3
   4   Written By -  Bernhard Held
   5
   6   This program is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU General Public License as published by the
   8   Free Software Foundation; either version 2, or (at your option) any
   9   later version.
  10
  11   This program is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, write to the Free Software
  18   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20   In other words, you are welcome to use, share and improve this program.
  21   You are forbidden to forbid anyone else to use, share and improve
  22   what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25 #include "common.h"
  26 #include "ralloc.h"
  27
  28 #define D(x) x
  29 #define DEADMOVEERROR "SDCC internal error: deadmove in " __FILE__" line %d\n", __LINE__
  30
  31 typedef enum
  32 {
  33   S4O_FOUNDOPCODE,
  34   S4O_PUSHPOP,
  35   S4O_CONDJMP,
  36   S4O_WR_OP,
  37   S4O_RD_OP,
  38   S4O_TERM,
  39   S4O_VISITED,
  40   S4O_ABORT
  41 } S4O_RET;
  42
  43 static struct
  44 {
  45   lineNode *head;
  46 } _G;
  47
  48 /*-----------------------------------------------------------------*/
  49 /* univisitLines - clear "visited" flag in all lines               */
  50 /*-----------------------------------------------------------------*/
  51 static void
  52 unvisitLines (lineNode *pl)
  53 {
  54   for (; pl; pl = pl->next)
  55     pl->visited = FALSE;
  56 }
  57
  58 /*-----------------------------------------------------------------*/
  59 /* cleanLabelRef - clear label jump-counter and pass-flag          */
  60 /*-----------------------------------------------------------------*/
  61 static void
  62 cleanLabelRef (void)
  63 {
  64   int key;
  65   labelHashEntry *entry;
  66
  67   if (!labelHash)
  68     return;
  69   for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
  70        entry;
  71        entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
  72     {
  73       entry->passedLabel = FALSE;
  74       entry->jmpToCount = 0;
  75     }
  76 }
  77
  78 /*-----------------------------------------------------------------*/
  79 /* checkLabelRef - check all entries in labelHash                  */
  80 /* The path from 'pop' to 'push' must be the only possible path.   */
  81 /* There must not be any paths in or out of this path.             */
  82 /* This is checked by counting the label references.               */
  83 /*-----------------------------------------------------------------*/
  84 static bool
  85 checkLabelRef (void)
  86 {
  87   int key;
  88   labelHashEntry *entry;
  89
  90   if (!labelHash)
  91     {
  92       /* no labels at all: no problems ;-) */
  93       return TRUE;
  94     }
  95
  96   for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
  97        entry;
  98        entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
  99     {
 100
 101       /* In our path we passed a label,
 102          but we didn't meet all references (jumps) to this label.
 103          This means that the code jumps from outside into this path. */
 104       if (entry->passedLabel &&
 105           entry->jmpToCount != entry->refCount)
 106         {
 107           return FALSE;
 108         }
 109
 110       /* In our path we jumped to (referenced) a label,
 111          but we we didn't pass it.
 112          This means that there's a code path into our path. */
 113       if (!entry->passedLabel &&
 114           entry->jmpToCount != 0)
 115         {
 116           return FALSE;
 117         }
 118     }
 119   return TRUE;
 120 }
 121
 122 /*-----------------------------------------------------------------*/
 123 /* setLabelRefPassedLabel - set flag "passedLabel" in entry        */
 124 /* of the list labelHash                                           */
 125 /*-----------------------------------------------------------------*/
 126 static bool
 127 setLabelRefPassedLabel (const char *label)
 128 {
 129   labelHashEntry *entry;
 130
 131   entry = getLabelRef (label, _G.head);
 132   if (!entry)
 133     return FALSE;
 134   entry->passedLabel = TRUE;
 135   return TRUE;
 136 }
 137
 138 /*-----------------------------------------------------------------*/
 139 /* incLabelJmpToCount - increment counter "jmpToCount" in entry    */
 140 /* of the list labelHash                                           */
 141 /*-----------------------------------------------------------------*/
 142 static bool
 143 incLabelJmpToCount (const char *label)
 144 {
 145   labelHashEntry *entry;
 146
 147   entry = getLabelRef (label, _G.head);
 148   if (!entry)
 149     return FALSE;
 150   entry->jmpToCount++;
 151   return TRUE;
 152 }
 153
 154 /*-----------------------------------------------------------------*/
 155 /* findLabel -                                                     */
 156 /* 1. extracts label in the opcode pl                              */
 157 /* 2. increment "label jump-to count" in labelHash                 */
 158 /* 3. search lineNode with label definition and return it          */
 159 /*-----------------------------------------------------------------*/
 160 static lineNode *
 161 findLabel (const lineNode *pl)
 162 {
 163   char *p;
 164   lineNode *cpl;
 165
 166   /* 1. extract label in opcode */
 167
 168   /* In each mcs51 jumping opcode the label is at the end of the opcode */
 169   p = strlen (pl->line) - 1 + pl->line;
 170
 171   /* scan backward until ',' or '\t' */
 172   for (; p > pl->line; p--)
 173     if (*p == ',' || *p == '\t')
 174       break;
 175
 176   /* sanity check */
 177   if (p == pl->line)
 178     {
 179       D(fprintf (stderr, DEADMOVEERROR);)
 180       return NULL;
 181     }
 182
 183   /* skip ',' resp. '\t' */
 184   ++p;
 185
 186   /* 2. increment "label jump-to count" */
 187   if (!incLabelJmpToCount (p))
 188     return NULL;
 189
 190   /* 3. search lineNode with label definition and return it */
 191   for (cpl = _G.head; cpl; cpl = cpl->next)
 192     {
 193       if (   cpl->isLabel
 194           && strcmp (p, cpl->line) == 0)
 195         {
 196           return cpl;
 197         }
 198     }
 199   return NULL;
 200 }
 201
 202 /*-----------------------------------------------------------------*/
 203 /* isFunc - returns TRUE if it's a CALL or PCALL (not _gptrget())  */
 204 /*-----------------------------------------------------------------*/
 205 static bool
 206 isFunc (const lineNode *pl)
 207 {
 208   if (pl && pl->ic)
 209     {
 210       if (   pl->ic->op == CALL
 211           || pl->ic->op == PCALL)
 212         return TRUE;
 213     }
 214   return FALSE;
 215 }
 216
 217 /*-----------------------------------------------------------------*/
 218 /* isCallerSaveFunc - returns TRUE if it's a 'normal' function     */
 219 /* call and it's a 'caller save' (not 'callee save')               */
 220 /*-----------------------------------------------------------------*/
 221 static bool
 222 isCallerSaveFunc (const lineNode *pl)
 223 {
 224   if (!isFunc (pl))
 225     return FALSE;
 226   if (FUNC_CALLEESAVES(OP_SYM_TYPE(IC_LEFT(pl->ic))))
 227     return FALSE;
 228   return TRUE;
 229 }
 230
 231 /*-----------------------------------------------------------------*/
 232 /* scan4op - "executes" and examines the assembler opcodes,        */
 233 /* follows conditional and un-conditional jumps.                   */
 234 /* Moreover it registers all passed labels.                        */
 235 /*                                                                 */
 236 /* Parameter:                                                      */
 237 /*    lineNode **pl                                                */
 238 /*       scanning starts from pl;                                  */
 239 /*       pl also returns the last scanned line                     */
 240 /*    const char *pReg                                             */
 241 /*       points to a register (e.g. "ar0"). scan4op() tests for    */
 242 /*       read or write operations with this register               */
 243 /*    const char *untilOp                                          */
 244 /*       points to NULL or a opcode (e.g. "push").                 */
 245 /*       scan4op() returns if it hits this opcode.                 */
 246 /*    lineNode **plCond                                            */
 247 /*       If a conditional branch is met plCond points to the       */
 248 /*       lineNode of the conditional branch                        */
 249 /*                                                                 */
 250 /* Returns:                                                        */
 251 /*    S4O_ABORT                                                    */
 252 /*       on error                                                  */
 253 /*    S4O_VISITED                                                  */
 254 /*       hit lineNode with "visited" flag set: scan4op() already   */
 255 /*       scanned this opcode.                                      */
 256 /*    S4O_FOUNDOPCODE                                              */
 257 /*       found opcode and operand, to which untilOp and pReg are   */
 258 /*       pointing to.                                              */
 259 /*    S4O_RD_OP, S4O_WR_OP                                         */
 260 /*       hit an opcode reading or writing from pReg                */
 261 /*    S4O_PUSHPOP                                                  */
 262 /*       hit a "push" or "pop" opcode                              */
 263 /*    S4O_CONDJMP                                                  */
 264 /*       hit a conditional jump opcode. pl and plCond return the   */
 265 /*       two possible branches.                                    */
 266 /*    S4O_TERM                                                     */
 267 /*       acall, lcall, ret and reti "terminate" a scan.            */
 268 /*-----------------------------------------------------------------*/
 269 static S4O_RET
 270 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
 271          lineNode **plCond)
 272 {
 273   char *p;
 274   int len;
 275   bool isConditionalJump;
 276
 277   /* pReg points to e.g. "ar0"..."ar7" */
 278   len = strlen (pReg);
 279
 280   for (; *pl; *pl = (*pl)->next)
 281     {
 282       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
 283         continue;
 284
 285       /* don't optimize across inline assembler,
 286          e.g. isLabel doesn't work there */
 287       if ((*pl)->isInline)
 288         return S4O_ABORT;
 289
 290       if ((*pl)->visited)
 291         return S4O_VISITED;
 292       (*pl)->visited = TRUE;
 293
 294       /* found untilOp? */
 295       if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
 296         {
 297           p = (*pl)->line + strlen (untilOp);
 298           if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
 299             return S4O_FOUNDOPCODE;
 300           else
 301             {
 302               /* found untilOp but without our pReg */
 303               return S4O_ABORT;
 304             }
 305         }
 306
 307       /* found pReg? */
 308       p = strchr ((*pl)->line, '\t');
 309       if (p)
 310         {
 311           /* skip '\t' */
 312           p++;
 313
 314           /* course search */
 315           if (strstr (p, pReg + 1))
 316             {
 317               /* ok, let's have a closer look */
 318
 319               /* get index into pReg table */
 320               int rIdx;
 321
 322               for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
 323                 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
 324                   break;
 325
 326               /* sanity check */
 327               if (rIdx >= mcs51_nRegs)
 328                 {
 329                   D(fprintf (stderr, DEADMOVEERROR);)
 330                   return S4O_ABORT;
 331                 }
 332
 333               /* does opcode read from pReg? */
 334               if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
 335                 return S4O_RD_OP;
 336               /* does opcode write to pReg? */
 337               if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
 338                 return S4O_WR_OP;
 339
 340               /* we can get here, if the register name is
 341                  part of a variable name: ignore it */
 342             }
 343         }
 344
 345       /* found label? */
 346       if ((*pl)->isLabel)
 347         {
 348           const char *start;
 349           char label[SDCC_NAME_MAX + 1];
 350           int len;
 351
 352           if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
 353             return S4O_ABORT;
 354           memcpy (label, start, len);
 355           label[len] = '\0';
 356           /* register passing this label */
 357           if (!setLabelRefPassedLabel (label))
 358             {
 359               D(fprintf (stderr, DEADMOVEERROR);)
 360               return S4O_ABORT;
 361             }
 362           continue;
 363         }
 364
 365       /* branch or terminate? */
 366       isConditionalJump = FALSE;
 367       switch ((*pl)->line[0])
 368         {
 369           case 'a':
 370             if (strncmp ("acall", (*pl)->line, 5) == 0)
 371               {
 372                 /* for comments see 'lcall' */
 373                 if (isCallerSaveFunc (*pl))
 374                   return S4O_TERM;
 375                 break;
 376               }
 377             if (strncmp ("ajmp", (*pl)->line, 4) == 0)
 378               {
 379                 *pl = findLabel (*pl);
 380                 if (!*pl)
 381                   return S4O_ABORT;
 382               }
 383             break;
 384           case 'c':
 385             if (strncmp ("cjne", (*pl)->line, 4) == 0)
 386               {
 387                 isConditionalJump = TRUE;
 388                 break;
 389               }
 390             break;
 391           case 'd':
 392             if (strncmp ("djnz", (*pl)->line, 4) == 0)
 393               {
 394                 isConditionalJump = TRUE;
 395                 break;
 396               }
 397             break;
 398           case 'j':
 399             if (strncmp ("jmp", (*pl)->line, 3) == 0)
 400               /* "jmp @a+dptr": no chance to trace execution */
 401               return S4O_ABORT;
 402             if (strncmp ("jc",  (*pl)->line, 2) == 0 ||
 403                 strncmp ("jnc", (*pl)->line, 3) == 0 ||
 404                 strncmp ("jz",  (*pl)->line, 2) == 0 ||
 405                 strncmp ("jnz", (*pl)->line, 3) == 0)
 406               {
 407                 isConditionalJump = TRUE;
 408                 break;
 409               }
 410             if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
 411                 strncmp ("jb",  (*pl)->line, 2) == 0 ||
 412                 strncmp ("jnb", (*pl)->line, 3) == 0)
 413               {
 414                 isConditionalJump = TRUE;
 415                 break;
 416               }
 417             break;
 418           case 'l':
 419             if (strncmp ("lcall", (*pl)->line, 5) == 0)
 420               {
 421                 if (isCallerSaveFunc (*pl))
 422                   {
 423                     /* If it's a 'normal' 'caller save' function call, all
 424                        registers have been saved until the 'lcall'. The
 425                        'life range' of all registers end at the lcall,
 426                        and we can terminate our search.
 427                     */
 428                     return S4O_TERM;
 429                   }
 430                 /* If it's a 'callee save' function call, registers are saved
 431                    by the callee. We've got no information, if the register
 432                    might live beyond the lcall. Therefore we've to continue
 433                    the search.
 434                 */
 435                 break;
 436               }
 437             if (strncmp ("ljmp", (*pl)->line, 4) == 0)
 438               {
 439                 *pl = findLabel (*pl);
 440                 if (!*pl)
 441                   return S4O_ABORT;
 442               }
 443             break;
 444           case 'p':
 445             if (strncmp ("pop", (*pl)->line, 3) == 0 ||
 446                 strncmp ("push", (*pl)->line, 4) == 0)
 447               return S4O_PUSHPOP;
 448             break;
 449           case 'r':
 450             if (strncmp ("reti", (*pl)->line, 4) == 0)
 451               return S4O_TERM;
 452
 453             if (strncmp ("ret", (*pl)->line, 3) == 0)
 454               {
 455                 /* pcall uses 'ret' */
 456                 if (isFunc (*pl))
 457                   {
 458                     /* for comments see 'lcall' */
 459                     if (isCallerSaveFunc (*pl))
 460                       return S4O_TERM;
 461                     break;
 462                   }
 463
 464                 /* it's a normal function return */
 465                 return S4O_TERM;
 466               }
 467             break;
 468           case 's':
 469             if (strncmp ("sjmp", (*pl)->line, 4) == 0)
 470               {
 471                 *pl = findLabel (*pl);
 472                 if (!*pl)
 473                   return S4O_ABORT;
 474               }
 475             break;
 476           default:
 477             break;
 478         } /* switch ((*pl)->line[0]) */
 479
 480       if (isConditionalJump)
 481         {
 482           *plCond = findLabel (*pl);
 483           if (!*plCond)
 484             return S4O_ABORT;
 485           return S4O_CONDJMP;
 486         }
 487     } /* for (; *pl; *pl = (*pl)->next) */
 488   return S4O_ABORT;
 489 }
 490
 491 /*-----------------------------------------------------------------*/
 492 /* doPushScan - scan through area 1. This small wrapper handles:   */
 493 /* - action required on different return values                    */
 494 /* - recursion in case of conditional branches                     */
 495 /*-----------------------------------------------------------------*/
 496 static bool
 497 doPushScan (lineNode **pl, const char *pReg)
 498 {
 499   lineNode *plConditional, *pushPl = NULL;
 500
 501   for (;; *pl = (*pl)->next)
 502     {
 503       switch (scan4op (pl, pReg, "push", &plConditional))
 504         {
 505           case S4O_FOUNDOPCODE:
 506             /* this is what we're looking for */
 507             return TRUE;
 508           case S4O_VISITED:
 509             if (!pushPl)
 510               {
 511                 D(fprintf (stderr, DEADMOVEERROR);)
 512                 return FALSE;
 513               }
 514             *pl = pushPl;
 515             /* already checked */
 516             return TRUE;
 517           case S4O_CONDJMP:
 518             /* two possible destinations: recurse */
 519               {
 520                 lineNode *pushPl2 = plConditional;
 521
 522                 if (!doPushScan (&pushPl2, pReg))
 523                   return FALSE;
 524                 pushPl = pushPl2;
 525               }
 526             continue;
 527           default:
 528             return FALSE;
 529         }
 530     }
 531 }
 532
 533 /*-----------------------------------------------------------------*/
 534 /* doTermScan - scan through area 2. This small wrapper handles:   */
 535 /* - action required on different return values                    */
 536 /* - recursion in case of conditional branches                     */
 537 /*-----------------------------------------------------------------*/
 538 static bool
 539 doTermScan (lineNode **pl, const char *pReg)
 540 {
 541   lineNode *plConditional;
 542
 543   for (;; *pl = (*pl)->next)
 544     {
 545       switch (scan4op (pl, pReg, NULL, &plConditional))
 546         {
 547           case S4O_TERM:
 548           case S4O_VISITED:
 549           case S4O_WR_OP:
 550             /* all these are terminating condtions */
 551             return TRUE;
 552           case S4O_PUSHPOP:
 553             /* don't care, go on */
 554             continue;
 555           case S4O_CONDJMP:
 556             /* two possible destinations: recurse */
 557               {
 558                 lineNode *pl2 = plConditional;
 559
 560                 if (!doTermScan (&pl2, pReg))
 561                   return FALSE;
 562               }
 563             continue;
 564           case S4O_RD_OP:
 565           default:
 566             /* no go */
 567             return FALSE;
 568         }
 569     }
 570 }
 571
 572 /*-----------------------------------------------------------------*/
 573 /* removeDeadPopPush - remove pop/push pair if possible            */
 574 /*-----------------------------------------------------------------*/
 575 static bool
 576 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
 577 {
 578   lineNode *pushPl, *pl;
 579
 580   /* A pop/push pair can be removed, if these criteria are met
 581      (ar0 is just an example here, ar0...ar7 are possible):
 582
 583      pop ar0
 584
 585       ; area 1
 586
 587       ; There must not be in area 1:
 588       ;    - read or write access of ar0
 589       ;    - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
 590       ;    - "push" opcode, which doesn't push ar0
 591       ;    - inline assembly
 592       ;    - a jump in or out of area 1 (see checkLabelRef())
 593
 594       ; Direct manipulation of sp is not detected. This isn't necessary
 595       ; as long as sdcc doesn't emit such code in area 1.
 596
 597       ; area 1 must be terminated by a:
 598      push ar0
 599
 600       ; area 2
 601
 602       ; There must not be:
 603       ;    - read access of ar0
 604       ;    - "jmp @a+dptr" opcode
 605       ;    - inline assembly
 606       ;    - a jump in or out of area 2 (see checkLabelRef())
 607
 608       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
 609       ; callee save), "reti" or write access of r0 terminate
 610       ; the search, and the "mov r0,a" can safely be removed.
 611   */
 612
 613   /* area 1 */
 614   pushPl = currPl->next;
 615   if (!doPushScan (&pushPl, pReg))
 616     return FALSE;
 617
 618   if (!checkLabelRef())
 619     return FALSE;
 620
 621   /* area 2 */
 622   pl = pushPl->next;
 623   if (!doTermScan (&pl, pReg))
 624     return FALSE;
 625   if (!checkLabelRef())
 626     return FALSE;
 627
 628   /* Success! */
 629   if (options.noPeepComments)
 630     {
 631       /* remove pushPl from list */
 632       pushPl->prev->next = pushPl->next;
 633       pushPl->next->prev = pushPl->prev;
 634     }
 635   else
 636     {
 637       /* replace 'push ar0' by comment */
 638       #define STR ";\tPeephole\tpush %s removed"
 639       int size = sizeof(STR) + 2;
 640
 641       pushPl->line = Safe_alloc (size);
 642       SNPRINTF (pushPl->line, size, STR, pReg);
 643       pushPl->isComment = TRUE;
 644     }
 645
 646   /* 'pop ar0' will be removed by peephole framework after returning TRUE */
 647   return TRUE;
 648 }
 649
 650 /*-----------------------------------------------------------------*/
 651 /* removeDeadMove - remove superflous 'mov r%1,%2'                 */
 652 /*-----------------------------------------------------------------*/
 653 static bool
 654 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
 655 {
 656   lineNode *pl;
 657
 658   /* "mov r0,a" can be removed, if these criteria are met
 659      (r0 is just an example here, r0...r7 are possible):
 660
 661       ; There must not be:
 662       ;    - read access of r0
 663       ;    - "jmp @a+dptr" opcode
 664       ;    - inline assembly
 665       ;    - a jump in or out of this area (see checkLabelRef())
 666
 667       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
 668       ; callee save), "reti" or write access of r0 terminate
 669       ; the search, and the "mov r0,a" can safely be removed.
 670   */
 671   pl = currPl->next;
 672   if (!doTermScan (&pl, pReg))
 673     return FALSE;
 674
 675   if (!checkLabelRef())
 676     return FALSE;
 677
 678   return TRUE;
 679 }
 680
 681 /*-----------------------------------------------------------------*/
 682 /* mcs51DeadMove - dispatch condition deadmove between             */
 683 /* - remove pop/push                                               */
 684 /* - remove mov r%1,%2                                             */
 685 /*-----------------------------------------------------------------*/
 686 bool
 687 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
 688 {
 689   char pReg[5] = "ar";
 690
 691   _G.head = head;
 692   strcat (pReg, reg);
 693
 694   unvisitLines (_G.head);
 695   cleanLabelRef();
 696
 697   if (strncmp (currPl->line, "pop", 3) == 0)
 698     return removeDeadPopPush (pReg, currPl, head);
 699   else if (   strncmp (currPl->line, "mov", 3) == 0
 700            && (currPl->line[3] == ' ' || currPl->line[3] == '\t'))
 701     return removeDeadMove (pReg, currPl, head);
 702   else
 703     {
 704       fprintf (stderr, "Error: "
 705                        "peephole rule with condition deadMove "
 706                        "used with unknown opocde:\n"
 707                        "\t%s\n", currPl->line);
 708       return FALSE;
 709     }
 710 }