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' or 'naked')    */
 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   if (FUNC_ISNAKED(OP_SYM_TYPE(IC_LEFT(pl->ic))))
 229     return FALSE;
 230   return TRUE;
 231 }
 232
 233 /*-----------------------------------------------------------------*/
 234 /* scan4op - "executes" and examines the assembler opcodes,        */
 235 /* follows conditional and un-conditional jumps.                   */
 236 /* Moreover it registers all passed labels.                        */
 237 /*                                                                 */
 238 /* Parameter:                                                      */
 239 /*    lineNode **pl                                                */
 240 /*       scanning starts from pl;                                  */
 241 /*       pl also returns the last scanned line                     */
 242 /*    const char *pReg                                             */
 243 /*       points to a register (e.g. "ar0"). scan4op() tests for    */
 244 /*       read or write operations with this register               */
 245 /*    const char *untilOp                                          */
 246 /*       points to NULL or a opcode (e.g. "push").                 */
 247 /*       scan4op() returns if it hits this opcode.                 */
 248 /*    lineNode **plCond                                            */
 249 /*       If a conditional branch is met plCond points to the       */
 250 /*       lineNode of the conditional branch                        */
 251 /*                                                                 */
 252 /* Returns:                                                        */
 253 /*    S4O_ABORT                                                    */
 254 /*       on error                                                  */
 255 /*    S4O_VISITED                                                  */
 256 /*       hit lineNode with "visited" flag set: scan4op() already   */
 257 /*       scanned this opcode.                                      */
 258 /*    S4O_FOUNDOPCODE                                              */
 259 /*       found opcode and operand, to which untilOp and pReg are   */
 260 /*       pointing to.                                              */
 261 /*    S4O_RD_OP, S4O_WR_OP                                         */
 262 /*       hit an opcode reading or writing from pReg                */
 263 /*    S4O_PUSHPOP                                                  */
 264 /*       hit a "push" or "pop" opcode                              */
 265 /*    S4O_CONDJMP                                                  */
 266 /*       hit a conditional jump opcode. pl and plCond return the   */
 267 /*       two possible branches.                                    */
 268 /*    S4O_TERM                                                     */
 269 /*       acall, lcall, ret and reti "terminate" a scan.            */
 270 /*-----------------------------------------------------------------*/
 271 static S4O_RET
 272 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
 273          lineNode **plCond)
 274 {
 275   char *p;
 276   int len;
 277   bool isConditionalJump;
 278
 279   /* pReg points to e.g. "ar0"..."ar7" */
 280   len = strlen (pReg);
 281
 282   for (; *pl; *pl = (*pl)->next)
 283     {
 284       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
 285         continue;
 286
 287       /* don't optimize across inline assembler,
 288          e.g. isLabel doesn't work there */
 289       if ((*pl)->isInline)
 290         return S4O_ABORT;
 291
 292       if ((*pl)->visited)
 293         return S4O_VISITED;
 294       (*pl)->visited = TRUE;
 295
 296       /* found untilOp? */
 297       if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
 298         {
 299           p = (*pl)->line + strlen (untilOp);
 300           if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
 301             return S4O_FOUNDOPCODE;
 302           else
 303             {
 304               /* found untilOp but without our pReg */
 305               return S4O_ABORT;
 306             }
 307         }
 308
 309       /* found pReg? */
 310       p = strchr ((*pl)->line, '\t');
 311       if (p)
 312         {
 313           /* skip '\t' */
 314           p++;
 315
 316           /* course search */
 317           if (strstr (p, pReg + 1))
 318             {
 319               /* ok, let's have a closer look */
 320
 321               /* get index into pReg table */
 322               int rIdx;
 323
 324               for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
 325                 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
 326                   break;
 327
 328               /* sanity check */
 329               if (rIdx >= mcs51_nRegs)
 330                 {
 331                   D(fprintf (stderr, DEADMOVEERROR);)
 332                   return S4O_ABORT;
 333                 }
 334
 335               /* does opcode read from pReg? */
 336               if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
 337                 return S4O_RD_OP;
 338               /* does opcode write to pReg? */
 339               if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
 340                 return S4O_WR_OP;
 341
 342               /* we can get here, if the register name is
 343                  part of a variable name: ignore it */
 344             }
 345         }
 346
 347       /* found label? */
 348       if ((*pl)->isLabel)
 349         {
 350           const char *start;
 351           char label[SDCC_NAME_MAX + 1];
 352           int len;
 353
 354           if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
 355             return S4O_ABORT;
 356           memcpy (label, start, len);
 357           label[len] = '\0';
 358           /* register passing this label */
 359           if (!setLabelRefPassedLabel (label))
 360             {
 361               D(fprintf (stderr, DEADMOVEERROR);)
 362               return S4O_ABORT;
 363             }
 364           continue;
 365         }
 366
 367       /* branch or terminate? */
 368       isConditionalJump = FALSE;
 369       switch ((*pl)->line[0])
 370         {
 371           case 'a':
 372             if (strncmp ("acall", (*pl)->line, 5) == 0)
 373               {
 374                 /* for comments see 'lcall' */
 375                 if (isCallerSaveFunc (*pl))
 376                   return S4O_TERM;
 377                 break;
 378               }
 379             if (strncmp ("ajmp", (*pl)->line, 4) == 0)
 380               {
 381                 *pl = findLabel (*pl);
 382                 if (!*pl)
 383                   return S4O_ABORT;
 384               }
 385             break;
 386           case 'c':
 387             if (strncmp ("cjne", (*pl)->line, 4) == 0)
 388               {
 389                 isConditionalJump = TRUE;
 390                 break;
 391               }
 392             break;
 393           case 'd':
 394             if (strncmp ("djnz", (*pl)->line, 4) == 0)
 395               {
 396                 isConditionalJump = TRUE;
 397                 break;
 398               }
 399             break;
 400           case 'j':
 401             if (strncmp ("jmp", (*pl)->line, 3) == 0)
 402               /* "jmp @a+dptr": no chance to trace execution */
 403               return S4O_ABORT;
 404             if (strncmp ("jc",  (*pl)->line, 2) == 0 ||
 405                 strncmp ("jnc", (*pl)->line, 3) == 0 ||
 406                 strncmp ("jz",  (*pl)->line, 2) == 0 ||
 407                 strncmp ("jnz", (*pl)->line, 3) == 0)
 408               {
 409                 isConditionalJump = TRUE;
 410                 break;
 411               }
 412             if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
 413                 strncmp ("jb",  (*pl)->line, 2) == 0 ||
 414                 strncmp ("jnb", (*pl)->line, 3) == 0)
 415               {
 416                 isConditionalJump = TRUE;
 417                 break;
 418               }
 419             break;
 420           case 'l':
 421             if (strncmp ("lcall", (*pl)->line, 5) == 0)
 422               {
 423                 if (isCallerSaveFunc (*pl))
 424                   {
 425                     /* If it's a 'normal' 'caller save' function call, all
 426                        registers have been saved until the 'lcall'. The
 427                        'life range' of all registers end at the lcall,
 428                        and we can terminate our search.
 429                     */
 430                     return S4O_TERM;
 431                   }
 432                 /* If it's a 'callee save' function call, registers are saved
 433                    by the callee. We've got no information, if the register
 434                    might live beyond the lcall. Therefore we've to continue
 435                    the search.
 436                 */
 437                 break;
 438               }
 439             if (strncmp ("ljmp", (*pl)->line, 4) == 0)
 440               {
 441                 *pl = findLabel (*pl);
 442                 if (!*pl)
 443                   return S4O_ABORT;
 444               }
 445             break;
 446           case 'p':
 447             if (strncmp ("pop", (*pl)->line, 3) == 0 ||
 448                 strncmp ("push", (*pl)->line, 4) == 0)
 449               return S4O_PUSHPOP;
 450             break;
 451           case 'r':
 452             if (strncmp ("reti", (*pl)->line, 4) == 0)
 453               return S4O_TERM;
 454
 455             if (strncmp ("ret", (*pl)->line, 3) == 0)
 456               {
 457                 /* pcall uses 'ret' */
 458                 if (isFunc (*pl))
 459                   {
 460                     /* for comments see 'lcall' */
 461                     if (isCallerSaveFunc (*pl))
 462                       return S4O_TERM;
 463                     break;
 464                   }
 465
 466                 /* it's a normal function return */
 467                 return S4O_TERM;
 468               }
 469             break;
 470           case 's':
 471             if (strncmp ("sjmp", (*pl)->line, 4) == 0)
 472               {
 473                 *pl = findLabel (*pl);
 474                 if (!*pl)
 475                   return S4O_ABORT;
 476               }
 477             break;
 478           default:
 479             break;
 480         } /* switch ((*pl)->line[0]) */
 481
 482       if (isConditionalJump)
 483         {
 484           *plCond = findLabel (*pl);
 485           if (!*plCond)
 486             return S4O_ABORT;
 487           return S4O_CONDJMP;
 488         }
 489     } /* for (; *pl; *pl = (*pl)->next) */
 490   return S4O_ABORT;
 491 }
 492
 493 /*-----------------------------------------------------------------*/
 494 /* doPushScan - scan through area 1. This small wrapper handles:   */
 495 /* - action required on different return values                    */
 496 /* - recursion in case of conditional branches                     */
 497 /*-----------------------------------------------------------------*/
 498 static bool
 499 doPushScan (lineNode **pl, const char *pReg)
 500 {
 501   lineNode *plConditional, *pushPl = NULL;
 502
 503   for (;; *pl = (*pl)->next)
 504     {
 505       switch (scan4op (pl, pReg, "push", &plConditional))
 506         {
 507           case S4O_FOUNDOPCODE:
 508             /* this is what we're looking for */
 509             return TRUE;
 510           case S4O_VISITED:
 511             if (!pushPl)
 512               {
 513                 D(fprintf (stderr, DEADMOVEERROR);)
 514                 return FALSE;
 515               }
 516             *pl = pushPl;
 517             /* already checked */
 518             return TRUE;
 519           case S4O_CONDJMP:
 520             /* two possible destinations: recurse */
 521               {
 522                 lineNode *pushPl2 = plConditional;
 523
 524                 if (!doPushScan (&pushPl2, pReg))
 525                   return FALSE;
 526                 pushPl = pushPl2;
 527               }
 528             continue;
 529           default:
 530             return FALSE;
 531         }
 532     }
 533 }
 534
 535 /*-----------------------------------------------------------------*/
 536 /* doTermScan - scan through area 2. This small wrapper handles:   */
 537 /* - action required on different return values                    */
 538 /* - recursion in case of conditional branches                     */
 539 /*-----------------------------------------------------------------*/
 540 static bool
 541 doTermScan (lineNode **pl, const char *pReg)
 542 {
 543   lineNode *plConditional;
 544
 545   for (;; *pl = (*pl)->next)
 546     {
 547       switch (scan4op (pl, pReg, NULL, &plConditional))
 548         {
 549           case S4O_TERM:
 550           case S4O_VISITED:
 551           case S4O_WR_OP:
 552             /* all these are terminating condtions */
 553             return TRUE;
 554           case S4O_PUSHPOP:
 555             /* don't care, go on */
 556             continue;
 557           case S4O_CONDJMP:
 558             /* two possible destinations: recurse */
 559               {
 560                 lineNode *pl2 = plConditional;
 561
 562                 if (!doTermScan (&pl2, pReg))
 563                   return FALSE;
 564               }
 565             continue;
 566           case S4O_RD_OP:
 567           default:
 568             /* no go */
 569             return FALSE;
 570         }
 571     }
 572 }
 573
 574 /*-----------------------------------------------------------------*/
 575 /* removeDeadPopPush - remove pop/push pair if possible            */
 576 /*-----------------------------------------------------------------*/
 577 static bool
 578 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
 579 {
 580   lineNode *pushPl, *pl;
 581
 582   /* A pop/push pair can be removed, if these criteria are met
 583      (ar0 is just an example here, ar0...ar7 are possible):
 584
 585      pop ar0
 586
 587       ; area 1
 588
 589       ; There must not be in area 1:
 590       ;    - read or write access of ar0
 591       ;    - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
 592       ;    - "push" opcode, which doesn't push ar0
 593       ;    - inline assembly
 594       ;    - a jump in or out of area 1 (see checkLabelRef())
 595
 596       ; Direct manipulation of sp is not detected. This isn't necessary
 597       ; as long as sdcc doesn't emit such code in area 1.
 598
 599       ; area 1 must be terminated by a:
 600      push ar0
 601
 602       ; area 2
 603
 604       ; There must not be:
 605       ;    - read access of ar0
 606       ;    - "jmp @a+dptr" opcode
 607       ;    - inline assembly
 608       ;    - a jump in or out of area 2 (see checkLabelRef())
 609
 610       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
 611       ; callee save), "reti" or write access of r0 terminate
 612       ; the search, and the "mov r0,a" can safely be removed.
 613   */
 614
 615   /* area 1 */
 616   pushPl = currPl->next;
 617   if (!doPushScan (&pushPl, pReg))
 618     return FALSE;
 619
 620   if (!checkLabelRef())
 621     return FALSE;
 622
 623   /* area 2 */
 624   pl = pushPl->next;
 625   if (!doTermScan (&pl, pReg))
 626     return FALSE;
 627   if (!checkLabelRef())
 628     return FALSE;
 629
 630   /* Success! */
 631   if (options.noPeepComments)
 632     {
 633       /* remove pushPl from list */
 634       pushPl->prev->next = pushPl->next;
 635       pushPl->next->prev = pushPl->prev;
 636     }
 637   else
 638     {
 639       /* replace 'push ar0' by comment */
 640       #define STR ";\tPeephole\tpush %s removed"
 641       int size = sizeof(STR) + 2;
 642
 643       pushPl->line = Safe_alloc (size);
 644       SNPRINTF (pushPl->line, size, STR, pReg);
 645       pushPl->isComment = TRUE;
 646     }
 647
 648   /* 'pop ar0' will be removed by peephole framework after returning TRUE */
 649   return TRUE;
 650 }
 651
 652 /*-----------------------------------------------------------------*/
 653 /* removeDeadMove - remove superflous 'mov r%1,%2'                 */
 654 /*-----------------------------------------------------------------*/
 655 static bool
 656 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
 657 {
 658   lineNode *pl;
 659
 660   /* "mov r0,a" can be removed, if these criteria are met
 661      (r0 is just an example here, r0...r7 are possible):
 662
 663       ; There must not be:
 664       ;    - read access of r0
 665       ;    - "jmp @a+dptr" opcode
 666       ;    - inline assembly
 667       ;    - a jump in or out of this area (see checkLabelRef())
 668
 669       ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
 670       ; callee save), "reti" or write access of r0 terminate
 671       ; the search, and the "mov r0,a" can safely be removed.
 672   */
 673   pl = currPl->next;
 674   if (!doTermScan (&pl, pReg))
 675     return FALSE;
 676
 677   if (!checkLabelRef())
 678     return FALSE;
 679
 680   return TRUE;
 681 }
 682
 683 /*-----------------------------------------------------------------*/
 684 /* mcs51DeadMove - dispatch condition deadmove between             */
 685 /* - remove pop/push                                               */
 686 /* - remove mov r%1,%2                                             */
 687 /*-----------------------------------------------------------------*/
 688 bool
 689 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
 690 {
 691   char pReg[5] = "ar";
 692
 693   _G.head = head;
 694   strcat (pReg, reg);
 695
 696   unvisitLines (_G.head);
 697   cleanLabelRef();
 698
 699   if (strncmp (currPl->line, "pop", 3) == 0)
 700     return removeDeadPopPush (pReg, currPl, head);
 701   else if (   strncmp (currPl->line, "mov", 3) == 0
 702            && (currPl->line[3] == ' ' || currPl->line[3] == '\t'))
 703     return removeDeadMove (pReg, currPl, head);
 704   else
 705     {
 706       fprintf (stderr, "Error: "
 707                        "peephole rule with condition deadMove "
 708                        "used with unknown opocde:\n"
 709                        "\t%s\n", currPl->line);
 710       return FALSE;
 711     }
 712 }