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' or 'naked') */
220 /*-----------------------------------------------------------------*/
222 isCallerSaveFunc (const lineNode *pl)
226 if (FUNC_CALLEESAVES(OP_SYM_TYPE(IC_LEFT(pl->ic))))
228 if (FUNC_ISNAKED(OP_SYM_TYPE(IC_LEFT(pl->ic))))
233 /*-----------------------------------------------------------------*/
234 /* scan4op - "executes" and examines the assembler opcodes, */
235 /* follows conditional and un-conditional jumps. */
236 /* Moreover it registers all passed labels. */
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 */
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 */
261 /* S4O_RD_OP, S4O_WR_OP */
262 /* hit an opcode reading or writing from pReg */
264 /* hit a "push" or "pop" opcode */
266 /* hit a conditional jump opcode. pl and plCond return the */
267 /* two possible branches. */
269 /* acall, lcall, ret and reti "terminate" a scan. */
270 /*-----------------------------------------------------------------*/
272 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
277 bool isConditionalJump;
279 /* pReg points to e.g. "ar0"..."ar7" */
282 for (; *pl; *pl = (*pl)->next)
284 if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
287 /* don't optimize across inline assembler,
288 e.g. isLabel doesn't work there */
294 (*pl)->visited = TRUE;
297 if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
299 p = (*pl)->line + strlen (untilOp);
300 if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
301 return S4O_FOUNDOPCODE;
304 /* found untilOp but without our pReg */
310 p = strchr ((*pl)->line, '\t');
317 if (strstr (p, pReg + 1))
319 /* ok, let's have a closer look */
321 /* get index into pReg table */
324 for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
325 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
329 if (rIdx >= mcs51_nRegs)
331 D(fprintf (stderr, DEADMOVEERROR);)
335 /* does opcode read from pReg? */
336 if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
338 /* does opcode write to pReg? */
339 if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
342 /* we can get here, if the register name is
343 part of a variable name: ignore it */
351 char label[SDCC_NAME_MAX + 1];
354 if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
356 memcpy (label, start, len);
358 /* register passing this label */
359 if (!setLabelRefPassedLabel (label))
361 D(fprintf (stderr, DEADMOVEERROR);)
367 /* branch or terminate? */
368 isConditionalJump = FALSE;
369 switch ((*pl)->line[0])
372 if (strncmp ("acall", (*pl)->line, 5) == 0)
374 /* for comments see 'lcall' */
375 if (isCallerSaveFunc (*pl))
379 if (strncmp ("ajmp", (*pl)->line, 4) == 0)
381 *pl = findLabel (*pl);
387 if (strncmp ("cjne", (*pl)->line, 4) == 0)
389 isConditionalJump = TRUE;
394 if (strncmp ("djnz", (*pl)->line, 4) == 0)
396 isConditionalJump = TRUE;
401 if (strncmp ("jmp", (*pl)->line, 3) == 0)
402 /* "jmp @a+dptr": no chance to trace execution */
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)
409 isConditionalJump = TRUE;
412 if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
413 strncmp ("jb", (*pl)->line, 2) == 0 ||
414 strncmp ("jnb", (*pl)->line, 3) == 0)
416 isConditionalJump = TRUE;
421 if (strncmp ("lcall", (*pl)->line, 5) == 0)
423 if (isCallerSaveFunc (*pl))
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.
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
439 if (strncmp ("ljmp", (*pl)->line, 4) == 0)
441 *pl = findLabel (*pl);
447 if (strncmp ("pop", (*pl)->line, 3) == 0 ||
448 strncmp ("push", (*pl)->line, 4) == 0)
452 if (strncmp ("reti", (*pl)->line, 4) == 0)
455 if (strncmp ("ret", (*pl)->line, 3) == 0)
457 /* pcall uses 'ret' */
460 /* for comments see 'lcall' */
461 if (isCallerSaveFunc (*pl))
466 /* it's a normal function return */
471 if (strncmp ("sjmp", (*pl)->line, 4) == 0)
473 *pl = findLabel (*pl);
480 } /* switch ((*pl)->line[0]) */
482 if (isConditionalJump)
484 *plCond = findLabel (*pl);
489 } /* for (; *pl; *pl = (*pl)->next) */
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 /*-----------------------------------------------------------------*/
499 doPushScan (lineNode **pl, const char *pReg)
501 lineNode *plConditional, *pushPl = NULL;
503 for (;; *pl = (*pl)->next)
505 switch (scan4op (pl, pReg, "push", &plConditional))
507 case S4O_FOUNDOPCODE:
508 /* this is what we're looking for */
513 D(fprintf (stderr, DEADMOVEERROR);)
517 /* already checked */
520 /* two possible destinations: recurse */
522 lineNode *pushPl2 = plConditional;
524 if (!doPushScan (&pushPl2, pReg))
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 /*-----------------------------------------------------------------*/
541 doTermScan (lineNode **pl, const char *pReg)
543 lineNode *plConditional;
545 for (;; *pl = (*pl)->next)
547 switch (scan4op (pl, pReg, NULL, &plConditional))
552 /* all these are terminating condtions */
555 /* don't care, go on */
558 /* two possible destinations: recurse */
560 lineNode *pl2 = plConditional;
562 if (!doTermScan (&pl2, pReg))
574 /*-----------------------------------------------------------------*/
575 /* removeDeadPopPush - remove pop/push pair if possible */
576 /*-----------------------------------------------------------------*/
578 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
580 lineNode *pushPl, *pl;
582 /* A pop/push pair can be removed, if these criteria are met
583 (ar0 is just an example here, ar0...ar7 are possible):
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
594 ; - a jump in or out of area 1 (see checkLabelRef())
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.
599 ; area 1 must be terminated by a:
605 ; - read access of ar0
606 ; - "jmp @a+dptr" opcode
608 ; - a jump in or out of area 2 (see checkLabelRef())
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.
616 pushPl = currPl->next;
617 if (!doPushScan (&pushPl, pReg))
620 if (!checkLabelRef())
625 if (!doTermScan (&pl, pReg))
627 if (!checkLabelRef())
631 if (options.noPeepComments)
633 /* remove pushPl from list */
634 pushPl->prev->next = pushPl->next;
635 pushPl->next->prev = pushPl->prev;
639 /* replace 'push ar0' by comment */
640 #define STR ";\tPeephole\tpush %s removed"
641 int size = sizeof(STR) + 2;
643 pushPl->line = Safe_alloc (size);
644 SNPRINTF (pushPl->line, size, STR, pReg);
645 pushPl->isComment = TRUE;
648 /* 'pop ar0' will be removed by peephole framework after returning TRUE */
652 /*-----------------------------------------------------------------*/
653 /* removeDeadMove - remove superflous 'mov r%1,%2' */
654 /*-----------------------------------------------------------------*/
656 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
660 /* "mov r0,a" can be removed, if these criteria are met
661 (r0 is just an example here, r0...r7 are possible):
664 ; - read access of r0
665 ; - "jmp @a+dptr" opcode
667 ; - a jump in or out of this area (see checkLabelRef())
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.
674 if (!doTermScan (&pl, pReg))
677 if (!checkLabelRef())
683 /*-----------------------------------------------------------------*/
684 /* mcs51DeadMove - dispatch condition deadmove between */
685 /* - remove pop/push */
686 /* - remove mov r%1,%2 */
687 /*-----------------------------------------------------------------*/
689 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
696 unvisitLines (_G.head);
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);
706 fprintf (stderr, "Error: "
707 "peephole rule with condition deadMove "
708 "used with unknown opocde:\n"
709 "\t%s\n", currPl->line);