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)
228 // let's assume calls to literally given locations use the default
229 // most notably : (*(void (*)()) 0) (); see bug 1749275
230 if (IS_VALOP (IC_LEFT (pl->ic)))
231 return !options.all_callee_saves;
233 ftype = OP_SYM_TYPE(IC_LEFT(pl->ic));
234 if (IS_FUNCPTR (ftype))
236 if (FUNC_CALLEESAVES(ftype))
238 if (FUNC_ISNAKED(ftype))
243 /*-----------------------------------------------------------------*/
244 /* scan4op - "executes" and examines the assembler opcodes, */
245 /* follows conditional and un-conditional jumps. */
246 /* Moreover it registers all passed labels. */
250 /* scanning starts from pl; */
251 /* pl also returns the last scanned line */
252 /* const char *pReg */
253 /* points to a register (e.g. "ar0"). scan4op() tests for */
254 /* read or write operations with this register */
255 /* const char *untilOp */
256 /* points to NULL or a opcode (e.g. "push"). */
257 /* scan4op() returns if it hits this opcode. */
258 /* lineNode **plCond */
259 /* If a conditional branch is met plCond points to the */
260 /* lineNode of the conditional branch */
266 /* hit lineNode with "visited" flag set: scan4op() already */
267 /* scanned this opcode. */
268 /* S4O_FOUNDOPCODE */
269 /* found opcode and operand, to which untilOp and pReg are */
271 /* S4O_RD_OP, S4O_WR_OP */
272 /* hit an opcode reading or writing from pReg */
274 /* hit a "push" or "pop" opcode */
276 /* hit a conditional jump opcode. pl and plCond return the */
277 /* two possible branches. */
279 /* acall, lcall, ret and reti "terminate" a scan. */
280 /*-----------------------------------------------------------------*/
282 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
287 bool isConditionalJump;
289 /* pReg points to e.g. "ar0"..."ar7" */
292 for (; *pl; *pl = (*pl)->next)
294 if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
297 /* don't optimize across inline assembler,
298 e.g. isLabel doesn't work there */
304 (*pl)->visited = TRUE;
307 if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
309 p = (*pl)->line + strlen (untilOp);
310 if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
311 return S4O_FOUNDOPCODE;
314 /* found untilOp but without our pReg */
320 p = strchr ((*pl)->line, '\t');
327 if (strstr (p, pReg + 1))
329 /* ok, let's have a closer look */
331 /* get index into pReg table */
334 for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
335 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
339 if (rIdx >= mcs51_nRegs)
341 D(fprintf (stderr, DEADMOVEERROR);)
345 /* does opcode read from pReg? */
346 if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
348 /* does opcode write to pReg? */
349 if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
352 /* we can get here, if the register name is
353 part of a variable name: ignore it */
361 char label[SDCC_NAME_MAX + 1];
364 if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
366 memcpy (label, start, len);
368 /* register passing this label */
369 if (!setLabelRefPassedLabel (label))
371 D(fprintf (stderr, DEADMOVEERROR);)
377 /* branch or terminate? */
378 isConditionalJump = FALSE;
379 switch ((*pl)->line[0])
382 if (strncmp ("acall", (*pl)->line, 5) == 0)
384 /* for comments see 'lcall' */
385 if (isCallerSaveFunc (*pl))
389 if (strncmp ("ajmp", (*pl)->line, 4) == 0)
391 *pl = findLabel (*pl);
397 if (strncmp ("cjne", (*pl)->line, 4) == 0)
399 isConditionalJump = TRUE;
404 if (strncmp ("djnz", (*pl)->line, 4) == 0)
406 isConditionalJump = TRUE;
411 if (strncmp ("jmp", (*pl)->line, 3) == 0)
412 /* "jmp @a+dptr": no chance to trace execution */
414 if (strncmp ("jc", (*pl)->line, 2) == 0 ||
415 strncmp ("jnc", (*pl)->line, 3) == 0 ||
416 strncmp ("jz", (*pl)->line, 2) == 0 ||
417 strncmp ("jnz", (*pl)->line, 3) == 0)
419 isConditionalJump = TRUE;
422 if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
423 strncmp ("jb", (*pl)->line, 2) == 0 ||
424 strncmp ("jnb", (*pl)->line, 3) == 0)
426 isConditionalJump = TRUE;
431 if (strncmp ("lcall", (*pl)->line, 5) == 0)
433 if (isCallerSaveFunc (*pl))
435 /* If it's a 'normal' 'caller save' function call, all
436 registers have been saved until the 'lcall'. The
437 'life range' of all registers end at the lcall,
438 and we can terminate our search.
442 /* If it's a 'callee save' function call, registers are saved
443 by the callee. We've got no information, if the register
444 might live beyond the lcall. Therefore we've to continue
449 if (strncmp ("ljmp", (*pl)->line, 4) == 0)
451 *pl = findLabel (*pl);
457 if (strncmp ("pop", (*pl)->line, 3) == 0 ||
458 strncmp ("push", (*pl)->line, 4) == 0)
462 if (strncmp ("reti", (*pl)->line, 4) == 0)
465 if (strncmp ("ret", (*pl)->line, 3) == 0)
467 /* pcall uses 'ret' */
470 /* for comments see 'lcall' */
471 if (isCallerSaveFunc (*pl))
476 /* it's a normal function return */
481 if (strncmp ("sjmp", (*pl)->line, 4) == 0)
483 *pl = findLabel (*pl);
490 } /* switch ((*pl)->line[0]) */
492 if (isConditionalJump)
494 *plCond = findLabel (*pl);
499 } /* for (; *pl; *pl = (*pl)->next) */
503 /*-----------------------------------------------------------------*/
504 /* doPushScan - scan through area 1. This small wrapper handles: */
505 /* - action required on different return values */
506 /* - recursion in case of conditional branches */
507 /*-----------------------------------------------------------------*/
509 doPushScan (lineNode **pl, const char *pReg)
511 lineNode *plConditional, *pushPl = NULL;
513 for (;; *pl = (*pl)->next)
515 switch (scan4op (pl, pReg, "push", &plConditional))
517 case S4O_FOUNDOPCODE:
518 /* this is what we're looking for */
523 D(fprintf (stderr, DEADMOVEERROR);)
527 /* already checked */
530 /* two possible destinations: recurse */
532 lineNode *pushPl2 = plConditional;
534 if (!doPushScan (&pushPl2, pReg))
545 /*-----------------------------------------------------------------*/
546 /* doTermScan - scan through area 2. This small wrapper handles: */
547 /* - action required on different return values */
548 /* - recursion in case of conditional branches */
549 /*-----------------------------------------------------------------*/
551 doTermScan (lineNode **pl, const char *pReg)
553 lineNode *plConditional;
555 for (;; *pl = (*pl)->next)
557 switch (scan4op (pl, pReg, NULL, &plConditional))
562 /* all these are terminating condtions */
565 /* don't care, go on */
568 /* two possible destinations: recurse */
570 lineNode *pl2 = plConditional;
572 if (!doTermScan (&pl2, pReg))
584 /*-----------------------------------------------------------------*/
585 /* removeDeadPopPush - remove pop/push pair if possible */
586 /*-----------------------------------------------------------------*/
588 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
590 lineNode *pushPl, *pl;
592 /* A pop/push pair can be removed, if these criteria are met
593 (ar0 is just an example here, ar0...ar7 are possible):
599 ; There must not be in area 1:
600 ; - read or write access of ar0
601 ; - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
602 ; - "push" opcode, which doesn't push ar0
604 ; - a jump in or out of area 1 (see checkLabelRef())
606 ; Direct manipulation of sp is not detected. This isn't necessary
607 ; as long as sdcc doesn't emit such code in area 1.
609 ; area 1 must be terminated by a:
615 ; - read access of ar0
616 ; - "jmp @a+dptr" opcode
618 ; - a jump in or out of area 2 (see checkLabelRef())
620 ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
621 ; callee save), "reti" or write access of r0 terminate
622 ; the search, and the "mov r0,a" can safely be removed.
626 pushPl = currPl->next;
627 if (!doPushScan (&pushPl, pReg))
630 if (!checkLabelRef())
635 if (!doTermScan (&pl, pReg))
637 if (!checkLabelRef())
641 if (options.noPeepComments)
643 /* remove pushPl from list */
644 pushPl->prev->next = pushPl->next;
645 pushPl->next->prev = pushPl->prev;
649 /* replace 'push ar0' by comment */
650 #define STR ";\tPeephole\tpush %s removed"
651 int size = sizeof(STR) + 2;
653 pushPl->line = Safe_alloc (size);
654 SNPRINTF (pushPl->line, size, STR, pReg);
655 pushPl->isComment = TRUE;
658 /* 'pop ar0' will be removed by peephole framework after returning TRUE */
662 /*-----------------------------------------------------------------*/
663 /* removeDeadMove - remove superflous 'mov r%1,%2' */
664 /*-----------------------------------------------------------------*/
666 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
670 /* "mov r0,a" can be removed, if these criteria are met
671 (r0 is just an example here, r0...r7 are possible):
674 ; - read access of r0
675 ; - "jmp @a+dptr" opcode
677 ; - a jump in or out of this area (see checkLabelRef())
679 ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
680 ; callee save), "reti" or write access of r0 terminate
681 ; the search, and the "mov r0,a" can safely be removed.
684 if (!doTermScan (&pl, pReg))
687 if (!checkLabelRef())
693 /*-----------------------------------------------------------------*/
694 /* mcs51DeadMove - dispatch condition deadmove between */
695 /* - remove pop/push */
696 /* - remove mov r%1,%2 */
697 /*-----------------------------------------------------------------*/
699 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
706 unvisitLines (_G.head);
709 if (strncmp (currPl->line, "pop", 3) == 0)
710 return removeDeadPopPush (pReg, currPl, head);
711 else if ( strncmp (currPl->line, "mov", 3) == 0
712 && (currPl->line[3] == ' ' || currPl->line[3] == '\t'))
713 return removeDeadMove (pReg, currPl, head);
716 fprintf (stderr, "Error: "
717 "peephole rule with condition deadMove "
718 "used with unknown opocde:\n"
719 "\t%s\n", currPl->line);