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() do {werror(E_INTERNAL_ERROR, __FILE__, __LINE__, "error in deadmove");} while(0)
49 /*-----------------------------------------------------------------*/
50 /* univisitLines - clear "visited" flag in all lines */
51 /*-----------------------------------------------------------------*/
53 unvisitLines (lineNode *pl)
55 for (; pl; pl = pl->next)
59 /*-----------------------------------------------------------------*/
60 /* cleanLabelRef - clear label jump-counter and pass-flag */
61 /*-----------------------------------------------------------------*/
66 labelHashEntry *entry;
70 for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
72 entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
74 entry->passedLabel = FALSE;
75 entry->jmpToCount = 0;
79 /*-----------------------------------------------------------------*/
80 /* checkLabelRef - check all entries in labelHash */
81 /* The path from 'pop' to 'push' must be the only possible path. */
82 /* There must not be any paths in or out of this path. */
83 /* This is checked by counting the label references. */
84 /*-----------------------------------------------------------------*/
89 labelHashEntry *entry;
93 /* no labels at all: no problems ;-) */
97 for (entry = (labelHashEntry *) hTabFirstItem (labelHash, &key);
99 entry = (labelHashEntry *) hTabNextItem (labelHash, &key))
102 /* In our path we passed a label,
103 but we didn't meet all references (jumps) to this label.
104 This means that the code jumps from outside into this path. */
105 if (entry->passedLabel &&
106 entry->jmpToCount != entry->refCount)
111 /* In our path we jumped to (referenced) a label,
112 but we we didn't pass it.
113 This means that there's a code path into our path. */
114 if (!entry->passedLabel &&
115 entry->jmpToCount != 0)
123 /*-----------------------------------------------------------------*/
124 /* setLabelRefPassedLabel - set flag "passedLabel" in entry */
125 /* of the list labelHash */
126 /*-----------------------------------------------------------------*/
128 setLabelRefPassedLabel (const char *label)
130 labelHashEntry *entry;
132 entry = getLabelRef (label, _G.head);
135 entry->passedLabel = TRUE;
139 /*-----------------------------------------------------------------*/
140 /* incLabelJmpToCount - increment counter "jmpToCount" in entry */
141 /* of the list labelHash */
142 /*-----------------------------------------------------------------*/
144 incLabelJmpToCount (const char *label)
146 labelHashEntry *entry;
148 entry = getLabelRef (label, _G.head);
155 /*-----------------------------------------------------------------*/
157 /* 1. extracts label in the opcode pl */
158 /* 2. increment "label jump-to count" in labelHash */
159 /* 3. search lineNode with label definition and return it */
160 /*-----------------------------------------------------------------*/
162 findLabel (const lineNode *pl)
167 /* 1. extract label in opcode */
169 /* In each mcs51 jumping opcode the label is at the end of the opcode */
170 p = strlen (pl->line) - 1 + pl->line;
172 /* scan backward until ',' or '\t' */
173 for (; p > pl->line; p--)
174 if (*p == ',' || *p == '\t')
184 /* skip ',' resp. '\t' */
187 /* 2. increment "label jump-to count" */
188 if (!incLabelJmpToCount (p))
191 /* 3. search lineNode with label definition and return it */
192 for (cpl = _G.head; cpl; cpl = cpl->next)
195 && strcmp (p, cpl->line) == 0)
203 /*-----------------------------------------------------------------*/
204 /* isFunc - returns TRUE if it's a CALL or PCALL (not _gptrget()) */
205 /*-----------------------------------------------------------------*/
207 isFunc (const lineNode *pl)
211 if ( pl->ic->op == CALL
212 || pl->ic->op == PCALL)
218 /*-----------------------------------------------------------------*/
219 /* termScanAtFunc - returns S4O_TERM if it's a 'normal' function */
220 /* call and it's a 'caller save'. returns S4O_CONTINUE if it's */
221 /* 'callee save' or 'naked'. returns S4O_ABORT if it's 'banked' */
222 /* uses the register for the destination. */
223 /*-----------------------------------------------------------------*/
225 termScanAtFunc (const lineNode *pl, int rIdx)
231 // let's assume calls to literally given locations use the default
232 // most notably : (*(void (*)()) 0) (); see bug 1749275
233 if (IS_VALOP (IC_LEFT (pl->ic)))
234 return !options.all_callee_saves;
236 ftype = OP_SYM_TYPE(IC_LEFT(pl->ic));
237 if (IS_FUNCPTR (ftype))
239 if (FUNC_CALLEESAVES(ftype))
241 if (FUNC_ISNAKED(ftype))
243 if (FUNC_BANKED(ftype) &&
244 ((rIdx == R0_IDX) || (rIdx == R1_IDX) || (rIdx == R2_IDX)))
249 /*-----------------------------------------------------------------*/
250 /* scan4op - "executes" and examines the assembler opcodes, */
251 /* follows conditional and un-conditional jumps. */
252 /* Moreover it registers all passed labels. */
256 /* scanning starts from pl; */
257 /* pl also returns the last scanned line */
258 /* const char *pReg */
259 /* points to a register (e.g. "ar0"). scan4op() tests for */
260 /* read or write operations with this register */
261 /* const char *untilOp */
262 /* points to NULL or a opcode (e.g. "push"). */
263 /* scan4op() returns if it hits this opcode. */
264 /* lineNode **plCond */
265 /* If a conditional branch is met plCond points to the */
266 /* lineNode of the conditional branch */
272 /* hit lineNode with "visited" flag set: scan4op() already */
273 /* scanned this opcode. */
274 /* S4O_FOUNDOPCODE */
275 /* found opcode and operand, to which untilOp and pReg are */
277 /* S4O_RD_OP, S4O_WR_OP */
278 /* hit an opcode reading or writing from pReg */
280 /* hit a "push" or "pop" opcode */
282 /* hit a conditional jump opcode. pl and plCond return the */
283 /* two possible branches. */
285 /* acall, lcall, ret and reti "terminate" a scan. */
286 /*-----------------------------------------------------------------*/
288 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
293 bool isConditionalJump;
297 /* pReg points to e.g. "ar0"..."ar7" */
300 /* get index into pReg table */
301 for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
302 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
306 if (rIdx >= mcs51_nRegs)
312 for (; *pl; *pl = (*pl)->next)
314 if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
317 /* don't optimize across inline assembler,
318 e.g. isLabel doesn't work there */
324 (*pl)->visited = TRUE;
327 if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
329 p = (*pl)->line + strlen (untilOp);
330 if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
331 return S4O_FOUNDOPCODE;
334 /* found untilOp but without our pReg */
340 p = strchr ((*pl)->line, '\t');
347 if (strstr (p, pReg + 1))
349 /* ok, let's have a closer look */
351 /* does opcode read from pReg? */
352 if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
354 /* does opcode write to pReg? */
355 if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
358 /* we can get here, if the register name is
359 part of a variable name: ignore it */
367 char label[SDCC_NAME_MAX + 1];
370 if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
372 memcpy (label, start, len);
374 /* register passing this label */
375 if (!setLabelRefPassedLabel (label))
383 /* branch or terminate? */
384 isConditionalJump = FALSE;
385 switch ((*pl)->line[0])
388 if (strncmp ("acall", (*pl)->line, 5) == 0)
390 /* for comments see 'lcall' */
391 ret = termScanAtFunc (*pl, rIdx);
392 if (ret != S4O_CONTINUE)
396 if (strncmp ("ajmp", (*pl)->line, 4) == 0)
398 *pl = findLabel (*pl);
404 if (strncmp ("cjne", (*pl)->line, 4) == 0)
406 isConditionalJump = TRUE;
411 if (strncmp ("djnz", (*pl)->line, 4) == 0)
413 isConditionalJump = TRUE;
418 if (strncmp ("jmp", (*pl)->line, 3) == 0)
419 /* "jmp @a+dptr": no chance to trace execution */
421 if (strncmp ("jc", (*pl)->line, 2) == 0 ||
422 strncmp ("jnc", (*pl)->line, 3) == 0 ||
423 strncmp ("jz", (*pl)->line, 2) == 0 ||
424 strncmp ("jnz", (*pl)->line, 3) == 0)
426 isConditionalJump = TRUE;
429 if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
430 strncmp ("jb", (*pl)->line, 2) == 0 ||
431 strncmp ("jnb", (*pl)->line, 3) == 0)
433 isConditionalJump = TRUE;
438 if (strncmp ("lcall", (*pl)->line, 5) == 0)
440 ret = termScanAtFunc (*pl, rIdx);
441 /* If it's a 'normal' 'caller save' function call, all
442 registers have been saved until the 'lcall'. The
443 'life range' of all registers end at the lcall,
444 and we can terminate our search.
445 * If the function is 'banked', the registers r0, r1 and r2
446 are used to tell the trampoline the destination. After
447 that their 'life range' ends just like the other registers.
448 * If it's a 'callee save' function call, registers are saved
449 by the callee. We've got no information, if the register
450 might live beyond the lcall. Therefore we've to continue
453 if (ret != S4O_CONTINUE)
457 if (strncmp ("ljmp", (*pl)->line, 4) == 0)
459 *pl = findLabel (*pl);
465 if (strncmp ("pop", (*pl)->line, 3) == 0 ||
466 strncmp ("push", (*pl)->line, 4) == 0)
470 if (strncmp ("reti", (*pl)->line, 4) == 0)
473 if (strncmp ("ret", (*pl)->line, 3) == 0)
475 /* pcall uses 'ret' */
478 /* for comments see 'lcall' */
479 ret = termScanAtFunc (*pl, rIdx);
480 if (ret != S4O_CONTINUE)
485 /* it's a normal function return */
490 if (strncmp ("sjmp", (*pl)->line, 4) == 0)
492 *pl = findLabel (*pl);
499 } /* switch ((*pl)->line[0]) */
501 if (isConditionalJump)
503 *plCond = findLabel (*pl);
508 } /* for (; *pl; *pl = (*pl)->next) */
512 /*-----------------------------------------------------------------*/
513 /* doPushScan - scan through area 1. This small wrapper handles: */
514 /* - action required on different return values */
515 /* - recursion in case of conditional branches */
516 /*-----------------------------------------------------------------*/
518 doPushScan (lineNode **pl, const char *pReg)
520 lineNode *plConditional, *pushPl = NULL;
522 for (;; *pl = (*pl)->next)
524 switch (scan4op (pl, pReg, "push", &plConditional))
526 case S4O_FOUNDOPCODE:
527 /* this is what we're looking for */
536 /* already checked */
539 /* two possible destinations: recurse */
541 lineNode *pushPl2 = plConditional;
543 if (!doPushScan (&pushPl2, pReg))
554 /*-----------------------------------------------------------------*/
555 /* doTermScan - scan through area 2. This small wrapper handles: */
556 /* - action required on different return values */
557 /* - recursion in case of conditional branches */
558 /*-----------------------------------------------------------------*/
560 doTermScan (lineNode **pl, const char *pReg)
562 lineNode *plConditional;
564 for (;; *pl = (*pl)->next)
566 switch (scan4op (pl, pReg, NULL, &plConditional))
571 /* all these are terminating condtions */
574 /* don't care, go on */
577 /* two possible destinations: recurse */
579 lineNode *pl2 = plConditional;
581 if (!doTermScan (&pl2, pReg))
593 /*-----------------------------------------------------------------*/
594 /* removeDeadPopPush - remove pop/push pair if possible */
595 /*-----------------------------------------------------------------*/
597 removeDeadPopPush (const char *pReg, lineNode *currPl, lineNode *head)
599 lineNode *pushPl, *pl;
601 /* A pop/push pair can be removed, if these criteria are met
602 (ar0 is just an example here, ar0...ar7 are possible):
608 ; There must not be in area 1:
609 ; - read or write access of ar0
610 ; - "acall", "lcall", "pop", "ret", "reti" or "jmp @a+dptr" opcodes
611 ; - "push" opcode, which doesn't push ar0
613 ; - a jump in or out of area 1 (see checkLabelRef())
615 ; Direct manipulation of sp is not detected. This isn't necessary
616 ; as long as sdcc doesn't emit such code in area 1.
618 ; area 1 must be terminated by a:
624 ; - read access of ar0
625 ; - "jmp @a+dptr" opcode
627 ; - a jump in or out of area 2 (see checkLabelRef())
629 ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
630 ; callee save), "reti" or write access of r0 terminate
631 ; the search, and the "mov r0,a" can safely be removed.
635 pushPl = currPl->next;
636 if (!doPushScan (&pushPl, pReg))
639 if (!checkLabelRef())
644 if (!doTermScan (&pl, pReg))
646 if (!checkLabelRef())
650 if (options.noPeepComments)
652 /* remove pushPl from list */
653 pushPl->prev->next = pushPl->next;
654 pushPl->next->prev = pushPl->prev;
658 /* replace 'push ar0' by comment */
659 #define STR ";\tPeephole\tpush %s removed"
660 int size = sizeof(STR) + 2;
662 pushPl->line = Safe_alloc (size);
663 SNPRINTF (pushPl->line, size, STR, pReg);
664 pushPl->isComment = TRUE;
667 /* 'pop ar0' will be removed by peephole framework after returning TRUE */
671 /*-----------------------------------------------------------------*/
672 /* removeDeadMove - remove superflous 'mov r%1,%2' */
673 /*-----------------------------------------------------------------*/
675 removeDeadMove (const char *pReg, lineNode *currPl, lineNode *head)
679 /* "mov r0,a" can be removed, if these criteria are met
680 (r0 is just an example here, r0...r7 are possible):
683 ; - read access of r0
684 ; - "jmp @a+dptr" opcode
686 ; - a jump in or out of this area (see checkLabelRef())
688 ; An "acall", "lcall" (not callee save), "ret" (not PCALL with
689 ; callee save), "reti" or write access of r0 terminate
690 ; the search, and the "mov r0,a" can safely be removed.
693 if (!doTermScan (&pl, pReg))
696 if (!checkLabelRef())
702 /*-----------------------------------------------------------------*/
703 /* mcs51DeadMove - dispatch condition deadmove between */
704 /* - remove pop/push */
705 /* - remove mov r%1,%2 */
706 /*-----------------------------------------------------------------*/
708 mcs51DeadMove (const char *reg, lineNode *currPl, lineNode *head)
715 unvisitLines (_G.head);
718 if (strncmp (currPl->line, "pop", 3) == 0)
719 return removeDeadPopPush (pReg, currPl, head);
720 else if ( strncmp (currPl->line, "mov", 3) == 0
721 && (currPl->line[3] == ' ' || currPl->line[3] == '\t'))
722 return removeDeadMove (pReg, currPl, head);
725 fprintf (stderr, "Error: "
726 "peephole rule with condition deadMove "
727 "used with unknown opocde:\n"
728 "\t%s\n", currPl->line);