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 "Internal error: deadmove\n"
  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 /* scan4op - "executes" and examines the assembler opcodes,        */
 204 /* follows conditional and un-conditional jumps.                   */
 205 /* Moreover it registers all passed labels.                        */
 206 /*                                                                 */
 207 /* Parameter:                                                      */
 208 /*    lineNode **pl                                                */
 209 /*       scanning starts from pl;                                  */
 210 /*       pl also returns the last scanned line                     */
 211 /*    const char *pReg                                             */
 212 /*       points to a register (e.g. "ar0"). scan4op() tests for    */
 213 /*       read or write operations with this register               */
 214 /*    const char *untilOp                                          */
 215 /*       points to NULL or a opcode (e.g. "push").                 */
 216 /*       scan4op() returns if it hits this opcode.                 */
 217 /*    lineNode **plCond                                            */
 218 /*       If a conditional branch is met plCond points to the       */
 219 /*       lineNode of the conditional branch                        */
 220 /*                                                                 */
 221 /* Returns:                                                        */
 222 /*    S4O_ABORT                                                    */
 223 /*       on error                                                  */
 224 /*    S4O_VISITED                                                  */
 225 /*       hit lineNode with "visited" flag set: scan4op() already   */
 226 /*       scanned this opcode.                                      */
 227 /*    S4O_FOUNDOPCODE                                              */
 228 /*       found opcode and operand, to which untilOp and pReg are   */
 229 /*       pointing to.                                              */
 230 /*    S4O_RD_OP, S4O_WR_OP                                         */
 231 /*       hit an opcode reading or writing from pReg                */
 232 /*    S4O_PUSHPOP                                                  */
 233 /*       hit a "push" or "pop" opcode                              */
 234 /*    S4O_CONDJMP                                                  */
 235 /*       hit a conditional jump opcode. pl and plCond return the   */
 236 /*       two possible branches.                                    */
 237 /*    S4O_TERM                                                     */
 238 /*       acall, lcall, ret and reti "terminate" a scan.            */
 239 /*-----------------------------------------------------------------*/
 240 static S4O_RET
 241 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
 242          lineNode **plCond)
 243 {
 244   char *p;
 245   int len;
 246   bool isConditionalJump;
 247
 248   /* pReg points to e.g. "ar0"..."ar7" */
 249   len = strlen (pReg);
 250
 251   for (; *pl; *pl = (*pl)->next)
 252     {
 253       if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
 254         continue;
 255
 256       /* don't optimize across inline assembler,
 257          e.g. isLabel doesn't work there */
 258       if ((*pl)->isInline)
 259         return S4O_ABORT;
 260
 261       if ((*pl)->visited)
 262         return S4O_VISITED;
 263       (*pl)->visited = TRUE;
 264
 265       /* found untilOp? */
 266       if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
 267         {
 268           p = (*pl)->line + strlen (untilOp);
 269           if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
 270             return S4O_FOUNDOPCODE;
 271           else
 272             {
 273               /* found untilOp but without our pReg */
 274               return S4O_ABORT;
 275             }
 276         }
 277
 278       /* found pReg? */
 279       p = strchr ((*pl)->line, '\t');
 280       if (p)
 281         {
 282           /* skip '\t' */
 283           p++;
 284
 285           /* course search */
 286           if (strstr (p, pReg + 1))
 287             {
 288               /* ok, let's have a closer look */
 289
 290               /* get index into pReg table */
 291               int rIdx;
 292
 293               for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
 294                 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
 295                   break;
 296
 297               /* sanity check */
 298               if (rIdx >= mcs51_nRegs)
 299                 {
 300                   D(fprintf (stderr, DEADMOVEERROR);)
 301                   return S4O_ABORT;
 302                 }
 303
 304               /* does opcode read from pReg? */
 305               if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
 306                 return S4O_RD_OP;
 307               /* does opcode write to pReg? */
 308               if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
 309                 return S4O_WR_OP;
 310
 311               /* should never reach here */
 312               D(fprintf (stderr, DEADMOVEERROR);)
 313               return S4O_ABORT;
 314             }
 315         }
 316
 317       /* found label? */
 318       if ((*pl)->isLabel)
 319         {
 320           const char *start;
 321           char label[SDCC_NAME_MAX + 1];
 322           int len;
 323
 324           if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
 325             return S4O_ABORT;
 326           memcpy (label, start, len);
 327           label[len] = '\0';
 328           /* register passing this label */
 329           if (!setLabelRefPassedLabel (label))
 330             {
 331               D(fprintf (stderr, DEADMOVEERROR);)
 332               return S4O_ABORT;
 333             }
 334           continue;
 335         }
 336
 337       /* branch or terminate? */
 338       isConditionalJump = FALSE;
 339       switch ((*pl)->line[0])
 340         {
 341           case 'a':
 342             if (strncmp ("acall", (*pl)->line, 5) == 0)
 343               return S4O_TERM;
 344             if (strncmp ("ajmp", (*pl)->line, 4) == 0)
 345               {
 346                 *pl = findLabel (*pl);
 347                 if (!*pl)
 348                   return S4O_ABORT;
 349               }
 350             break;
 351           case 'c':
 352             if (strncmp ("cjne", (*pl)->line, 4) == 0)
 353               {
 354                 isConditionalJump = TRUE;
 355                 break;
 356               }
 357             break;
 358           case 'd':
 359             if (strncmp ("djnz", (*pl)->line, 4) == 0)
 360               {
 361                 isConditionalJump = TRUE;
 362                 break;
 363               }
 364             break;
 365           case 'j':
 366             if (strncmp ("jmp", (*pl)->line, 3) == 0)
 367               /* "jmp @a+dptr": no chance to trace execution */
 368               return S4O_ABORT;
 369             if (strncmp ("jc",  (*pl)->line, 2) == 0 ||
 370                 strncmp ("jnc", (*pl)->line, 3) == 0 ||
 371                 strncmp ("jz",  (*pl)->line, 2) == 0 ||
 372                 strncmp ("jnz", (*pl)->line, 3) == 0)
 373               {
 374                 isConditionalJump = TRUE;
 375                 break;
 376               }
 377             if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
 378                 strncmp ("jb",  (*pl)->line, 2) == 0 ||
 379                 strncmp ("jnb", (*pl)->line, 3) == 0)
 380               {
 381                 isConditionalJump = TRUE;
 382                 break;
 383               }
 384             break;
 385           case 'l':
 386             if (strncmp ("lcall", (*pl)->line, 5) == 0)
 387               return S4O_TERM;
 388             if (strncmp ("ljmp", (*pl)->line, 4) == 0)
 389               {
 390                 *pl = findLabel (*pl);
 391                 if (!*pl)
 392                   return S4O_ABORT;
 393               }
 394             break;
 395           case 'p':
 396             if (strncmp ("pop", (*pl)->line, 3) == 0 ||
 397                 strncmp ("push", (*pl)->line, 4) == 0)
 398               return S4O_PUSHPOP;
 399             break;
 400           case 'r':
 401             /* pcall uses ret */
 402             if (strncmp ("ret", (*pl)->line, 3) == 0) /* catches "reti" too */
 403               return S4O_TERM;
 404             break;
 405           case 's':
 406             if (strncmp ("sjmp", (*pl)->line, 4) == 0)
 407               {
 408                 *pl = findLabel (*pl);
 409                 if (!*pl)
 410                   return S4O_ABORT;
 411               }
 412             break;
 413           default:
 414             break;
 415         } /* switch ((*pl)->line[0]) */
 416
 417       if (isConditionalJump)
 418         {
 419           *plCond = findLabel (*pl);
 420           if (!*plCond)
 421             return S4O_ABORT;
 422           return S4O_CONDJMP;
 423         }
 424     } /* for (; *pl; *pl = (*pl)->next) */
 425   return S4O_ABORT;
 426 }
 427
 428 /*-----------------------------------------------------------------*/
 429 /* doPushScan - scan through area 1. This small wrapper handles:   */
 430 /* - action required on different return values                    */
 431 /* - recursion in case of conditional branches                     */
 432 /*-----------------------------------------------------------------*/
 433 static bool
 434 doPushScan (lineNode **pl, const char *pReg)
 435 {
 436   lineNode *plConditional, *pushPl = NULL;
 437
 438   for (;; *pl = (*pl)->next)
 439     {
 440       switch (scan4op (pl, pReg, "push", &plConditional))
 441         {
 442           case S4O_FOUNDOPCODE:
 443             /* this is what we're looking for */
 444             return TRUE;
 445           case S4O_VISITED:
 446             if (!pushPl)
 447               {
 448                 D(fprintf (stderr, DEADMOVEERROR);)
 449                 return FALSE;
 450               }
 451             *pl = pushPl;
 452             /* already checked */
 453             return TRUE;
 454           case S4O_CONDJMP:
 455             /* two possible destinations: recurse */
 456               {
 457                 lineNode *pushPl2 = plConditional;
 458
 459                 if (!doPushScan (&pushPl2, pReg))
 460                   return FALSE;
 461                 pushPl = pushPl2;
 462               }
 463             continue;
 464           default:
 465             return FALSE;
 466         }
 467     }
 468 }
 469
 470 /*-----------------------------------------------------------------*/
 471 /* doTermScan - scan through area 2. This small wrapper handles:   */
 472 /* - action required on different return values                    */
 473 /* - recursion in case of conditional branches                     */
 474 /*-----------------------------------------------------------------*/
 475 static bool
 476 doTermScan (lineNode **pl, const char *pReg)
 477 {
 478   lineNode *plConditional;
 479
 480   for (;; *pl = (*pl)->next)
 481     {
 482       switch (scan4op (pl, pReg, NULL, &plConditional))
 483         {
 484           case S4O_TERM:
 485           case S4O_VISITED:
 486           case S4O_WR_OP:
 487             /* all these are terminating condtions */
 488             return TRUE;
 489           case S4O_PUSHPOP:
 490             /* don't care, go on */
 491             continue;
 492           case S4O_CONDJMP:
 493             /* two possible destinations: recurse */
 494               {
 495                 lineNode *pl2 = plConditional;
 496
 497                 if (!doTermScan (&pl2, pReg))
 498                   return FALSE;
 499               }
 500             continue;
 501           case S4O_RD_OP:
 502           default:
 503             /* no go */
 504             return FALSE;
 505         }
 506     }
 507 }
 508
 509 /*-----------------------------------------------------------------*/
 510 /* -                                                               */
 511 /*-----------------------------------------------------------------*/
 512 bool
 513 mcs51DeadMove (const char *op1, lineNode *currPl, lineNode *head)
 514 {
 515   char pReg[5] = "ar";
 516   lineNode *pushPl, *pl;
 517
 518   /* A pop/push pair can be removed, if these criteria are met
 519      (ar0 is just an example here, ar0...ar7 are possible):
 520
 521      pop ar0
 522
 523       ; area 1
 524
 525       ; There must not be in area 1:
 526       ;    - read or write access of ar0
 527       ;    - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
 528       ;    - "push" opcode, which doesn't push ar0
 529       ;    - inline assembly
 530       ;    - a jump in or out of area 1 (see checkLabelRef())
 531
 532       ; Direct manipulation of sp is not detected. This isn't necessary
 533       ; as long as sdcc doesn't emit such code in area 1.
 534
 535       ; area 1 must be terminated by a:
 536      push ar0
 537
 538       ; area 2
 539
 540       ; There must not be:
 541       ;    - read access of ar0
 542       ;    - "jmp @a+dptr" opcode
 543       ;    - inline assembly
 544       ;    - a jump in or out of area 2 (see checkLabelRef())
 545
 546       ; An "acall", "lcall", "ret", "reti" or write access of ar0 terminate
 547       ; the search, and the pop/push pair can safely be removed.
 548   */
 549
 550   _G.head = head;
 551   strcat (pReg, op1);
 552
 553   unvisitLines (_G.head);
 554   cleanLabelRef();
 555
 556   /* area 1 */
 557   pushPl = currPl->next;
 558   if (!doPushScan (&pushPl, pReg))
 559     return FALSE;
 560
 561   if (!checkLabelRef())
 562     return FALSE;
 563
 564   /* area 2 */
 565   pl = pushPl->next;
 566   if (!doTermScan (&pl, pReg))
 567     return FALSE;
 568   if (!checkLabelRef())
 569     return FALSE;
 570
 571   /* Success! */
 572   if (options.noPeepComments)
 573     {
 574       /* remove pushPl from list */
 575       pushPl->prev->next = pushPl->next;
 576       pushPl->next->prev = pushPl->prev;
 577     }
 578   else
 579     {
 580       /* replace 'push ar0' by comment */
 581       #define STR ";\tPeephole\tpush %s removed"
 582       int size = sizeof(STR) + 2;
 583
 584       pushPl->line = Safe_alloc (size);
 585       SNPRINTF (pushPl->line, size, STR, pReg);
 586       pushPl->isComment = TRUE;
 587     }
 588
 589   /* 'pop ar0' will be removed by peephole framework after returning TRUE */
 590   return TRUE;
 591 }