1 /*-------------------------------------------------------------------------
2 peep.c - source file for peephole optimizer helper functions
4 Written By - Bernhard Held
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
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.
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.
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 -------------------------------------------------------------------------*/
29 #define DEADMOVEERROR "SDCC internal error: deadmove in " __FILE__" line %d\n", __LINE__
48 /*-----------------------------------------------------------------*/
49 /* univisitLines - clear "visited" flag in all lines */
50 /*-----------------------------------------------------------------*/
52 unvisitLines (lineNode *pl)
54 for (; pl; pl = pl->next)
58 /*-----------------------------------------------------------------*/
59 /* cleanLabelRef - clear label jump-counter and pass-flag */
60 /*-----------------------------------------------------------------*/
65 labelHashEntry *entry;
69 for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
71 entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
73 entry->passedLabel = FALSE;
74 entry->jmpToCount = 0;
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 /*-----------------------------------------------------------------*/
88 labelHashEntry *entry;
92 /* no labels at all: no problems ;-) */
96 for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
98 entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
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)
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)
122 /*-----------------------------------------------------------------*/
123 /* setLabelRefPassedLabel - set flag "passedLabel" in entry */
124 /* of the list labelHash */
125 /*-----------------------------------------------------------------*/
127 setLabelRefPassedLabel (const char *label)
129 labelHashEntry *entry;
131 entry = getLabelRef (label, _G.head);
134 entry->passedLabel = TRUE;
138 /*-----------------------------------------------------------------*/
139 /* incLabelJmpToCount - increment counter "jmpToCount" in entry */
140 /* of the list labelHash */
141 /*-----------------------------------------------------------------*/
143 incLabelJmpToCount (const char *label)
145 labelHashEntry *entry;
147 entry = getLabelRef (label, _G.head);
154 /*-----------------------------------------------------------------*/
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 /*-----------------------------------------------------------------*/
161 findLabel (const lineNode *pl)
166 /* 1. extract label in opcode */
168 /* In each mcs51 jumping opcode the label is at the end of the opcode */
169 p = strlen (pl->line) - 1 + pl->line;
171 /* scan backward until ',' or '\t' */
172 for (; p > pl->line; p--)
173 if (*p == ',' || *p == '\t')
179 D(fprintf (stderr, DEADMOVEERROR);)
183 /* skip ',' resp. '\t' */
186 /* 2. increment "label jump-to count" */
187 if (!incLabelJmpToCount (p))
190 /* 3. search lineNode with label definition and return it */
191 for (cpl = _G.head; cpl; cpl = cpl->next)
194 && strcmp (p, cpl->line) == 0)
202 /*-----------------------------------------------------------------*/
203 /* isFunc - returns TRUE if it's a CALL or PCALL (not _gptrget()) */
204 /*-----------------------------------------------------------------*/
206 isFunc (const lineNode *pl)
210 if ( pl->ic->op == CALL
211 || pl->ic->op == PCALL)
217 /*-----------------------------------------------------------------*/
218 /* isCallerSaveFunc - returns TRUE if it's a 'normal' function */
219 /* call and it's a 'caller save' (not 'callee save') */
220 /*-----------------------------------------------------------------*/
222 isCallerSaveFunc (const lineNode *pl)
226 if (FUNC_CALLEESAVES(OP_SYM_TYPE(IC_LEFT(pl->ic))))
231 /*-----------------------------------------------------------------*/
232 /* scan4op - "executes" and examines the assembler opcodes, */
233 /* follows conditional and un-conditional jumps. */
234 /* Moreover it registers all passed labels. */
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 */
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 */
259 /* S4O_RD_OP, S4O_WR_OP */
260 /* hit an opcode reading or writing from pReg */
262 /* hit a "push" or "pop" opcode */
264 /* hit a conditional jump opcode. pl and plCond return the */
265 /* two possible branches. */
267 /* acall, lcall, ret and reti "terminate" a scan. */
268 /*-----------------------------------------------------------------*/
270 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
275 bool isConditionalJump;
277 /* pReg points to e.g. "ar0"..."ar7" */
280 for (; *pl; *pl = (*pl)->next)
282 if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
285 /* don't optimize across inline assembler,
286 e.g. isLabel doesn't work there */
292 (*pl)->visited = TRUE;
295 if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
297 p = (*pl)->line + strlen (untilOp);
298 if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
299 return S4O_FOUNDOPCODE;
302 /* found untilOp but without our pReg */
308 p = strchr ((*pl)->line, '\t');
315 if (strstr (p, pReg + 1))
317 /* ok, let's have a closer look */
319 /* get index into pReg table */
322 for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
323 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
327 if (rIdx >= mcs51_nRegs)
329 D(fprintf (stderr, DEADMOVEERROR);)
333 /* does opcode read from pReg? */
334 if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
336 /* does opcode write to pReg? */
337 if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
340 /* we can get here, if the register name is
341 part of a variable name: ignore it */
349 char label[SDCC_NAME_MAX + 1];
352 if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
354 memcpy (label, start, len);
356 /* register passing this label */
357 if (!setLabelRefPassedLabel (label))
359 D(fprintf (stderr, DEADMOVEERROR);)
365 /* branch or terminate? */
366 isConditionalJump = FALSE;
367 switch ((*pl)->line[0])
370 if (strncmp ("acall", (*pl)->line, 5) == 0)
372 /* for comments see 'lcall' */
373 if (isCallerSaveFunc (*pl))
377 if (strncmp ("ajmp", (*pl)->line, 4) == 0)
379 *pl = findLabel (*pl);
385 if (strncmp ("cjne", (*pl)->line, 4) == 0)
387 isConditionalJump = TRUE;
392 if (strncmp ("djnz", (*pl)->line, 4) == 0)
394 isConditionalJump = TRUE;
399 if (strncmp ("jmp", (*pl)->line, 3) == 0)
400 /* "jmp @a+dptr": no chance to trace execution */
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)
407 isConditionalJump = TRUE;
410 if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
411 strncmp ("jb", (*pl)->line, 2) == 0 ||
412 strncmp ("jnb", (*pl)->line, 3) == 0)
414 isConditionalJump = TRUE;
419 if (strncmp ("lcall", (*pl)->line, 5) == 0)
421 if (isCallerSaveFunc (*pl))
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.
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
437 if (strncmp ("ljmp", (*pl)->line, 4) == 0)
439 *pl = findLabel (*pl);
445 if (strncmp ("pop", (*pl)->line, 3) == 0 ||
446 strncmp ("push", (*pl)->line, 4) == 0)
450 if (strncmp ("reti", (*pl)->line, 4) == 0)
453 if (strncmp ("ret", (*pl)->line, 3) == 0)
455 /* pcall uses 'ret' */
458 /* for comments see 'lcall' */
459 if (isCallerSaveFunc (*pl))
464 /* it's a normal function return */
469 if (strncmp ("sjmp", (*pl)->line, 4) == 0)
471 *pl = findLabel (*pl);
478 } /* switch ((*pl)->line[0]) */
480 if (isConditionalJump)
482 *plCond = findLabel (*pl);
487 } /* for (; *pl; *pl = (*pl)->next) */
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 /*-----------------------------------------------------------------*/
497 doPushScan (lineNode **pl, const char *pReg)
499 lineNode *plConditional, *pushPl = NULL;
501 for (;; *pl = (*pl)->next)
503 switch (scan4op (pl, pReg, "push", &plConditional))
505 case S4O_FOUNDOPCODE:
506 /* this is what we're looking for */
511 D(fprintf (stderr, DEADMOVEERROR);)
515 /* already checked */
518 /* two possible destinations: recurse */
520 lineNode *pushPl2 = plConditional;
522 if (!doPushScan (&pushPl2, pReg))
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 /*-----------------------------------------------------------------*/
539 doTermScan (lineNode **pl, const char *pReg)
541 lineNode *plConditional;
543 for (;; *pl = (*pl)->next)
545 switch (scan4op (pl, pReg, NULL, &plConditional))
550 /* all these are terminating condtions */
553 /* don't care, go on */
556 /* two possible destinations: recurse */
558 lineNode *pl2 = plConditional;
560 if (!doTermScan (&pl2, pReg))
572 /*-----------------------------------------------------------------*/
573 /* removeDeadPopPush - remove pop/push pair if possible */
574 /*-----------------------------------------------------------------*/
576 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
578 lineNode *pushPl, *pl;
580 /* A pop/push pair can be removed, if these criteria are met
581 (ar0 is just an example here, ar0...ar7 are possible):
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
592 ; - a jump in or out of area 1 (see checkLabelRef())
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.
597 ; area 1 must be terminated by a:
603 ; - read access of ar0
604 ; - "jmp @a+dptr" opcode
606 ; - a jump in or out of area 2 (see checkLabelRef())
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.
614 pushPl = currPl->next;
615 if (!doPushScan (&pushPl, pReg))
618 if (!checkLabelRef())
623 if (!doTermScan (&pl, pReg))
625 if (!checkLabelRef())
629 if (options.noPeepComments)
631 /* remove pushPl from list */
632 pushPl->prev->next = pushPl->next;
633 pushPl->next->prev = pushPl->prev;
637 /* replace 'push ar0' by comment */
638 #define STR ";\tPeephole\tpush %s removed"
639 int size = sizeof(STR) + 2;
641 pushPl->line = Safe_alloc (size);
642 SNPRINTF (pushPl->line, size, STR, pReg);
643 pushPl->isComment = TRUE;
646 /* 'pop ar0' will be removed by peephole framework after returning TRUE */
650 /*-----------------------------------------------------------------*/
651 /* removeDeadMove - remove superflous 'mov r%1,%2' */
652 /*-----------------------------------------------------------------*/
654 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
658 /* "mov r0,a" can be removed, if these criteria are met
659 (r0 is just an example here, r0...r7 are possible):
662 ; - read access of r0
663 ; - "jmp @a+dptr" opcode
665 ; - a jump in or out of this area (see checkLabelRef())
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.
672 if (!doTermScan (&pl, pReg))
675 if (!checkLabelRef())
681 /*-----------------------------------------------------------------*/
682 /* mcs51DeadMove - dispatch condition deadmove between */
683 /* - remove pop/push */
684 /* - remove mov r%1,%2 */
685 /*-----------------------------------------------------------------*/
687 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
694 unvisitLines (_G.head);
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);
704 fprintf (stderr, "Error: "
705 "peephole rule with condition deadMove "
706 "used with unknown opocde:\n"
707 "\t%s\n", currPl->line);