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 "Internal error: deadmove\n"
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 /* scan4op - "executes" and examines the assembler opcodes, */
204 /* follows conditional and un-conditional jumps. */
205 /* Moreover it registers all passed labels. */
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 */
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 */
230 /* S4O_RD_OP, S4O_WR_OP */
231 /* hit an opcode reading or writing from pReg */
233 /* hit a "push" or "pop" opcode */
235 /* hit a conditional jump opcode. pl and plCond return the */
236 /* two possible branches. */
238 /* acall, lcall, ret and reti "terminate" a scan. */
239 /*-----------------------------------------------------------------*/
241 scan4op (lineNode **pl, const char *pReg, const char *untilOp,
246 bool isConditionalJump;
248 /* pReg points to e.g. "ar0"..."ar7" */
251 for (; *pl; *pl = (*pl)->next)
253 if (!(*pl)->line || (*pl)->isDebug || (*pl)->isComment)
256 /* don't optimize across inline assembler,
257 e.g. isLabel doesn't work there */
263 (*pl)->visited = TRUE;
266 if (untilOp && strncmp ((*pl)->line, untilOp, strlen (untilOp)) == 0)
268 p = (*pl)->line + strlen (untilOp);
269 if (*p == '\t' && strncmp (p + 1, pReg, len) == 0)
270 return S4O_FOUNDOPCODE;
273 /* found untilOp but without our pReg */
279 p = strchr ((*pl)->line, '\t');
286 if (strstr (p, pReg + 1))
288 /* ok, let's have a closer look */
290 /* get index into pReg table */
293 for (rIdx = 0; rIdx < mcs51_nRegs; ++rIdx)
294 if (strcmp (regs8051[rIdx].name, pReg + 1) == 0)
298 if (rIdx >= mcs51_nRegs)
300 D(fprintf (stderr, DEADMOVEERROR);)
304 /* does opcode read from pReg? */
305 if (bitVectBitValue (port->peep.getRegsRead ((*pl)), rIdx))
307 /* does opcode write to pReg? */
308 if (bitVectBitValue (port->peep.getRegsWritten ((*pl)), rIdx))
311 /* should never reach here */
312 D(fprintf (stderr, DEADMOVEERROR);)
321 char label[SDCC_NAME_MAX + 1];
324 if (!isLabelDefinition ((*pl)->line, &start, &len, FALSE))
326 memcpy (label, start, len);
328 /* register passing this label */
329 if (!setLabelRefPassedLabel (label))
331 D(fprintf (stderr, DEADMOVEERROR);)
337 /* branch or terminate? */
338 isConditionalJump = FALSE;
339 switch ((*pl)->line[0])
342 if (strncmp ("acall", (*pl)->line, 5) == 0)
344 if (strncmp ("ajmp", (*pl)->line, 4) == 0)
346 *pl = findLabel (*pl);
352 if (strncmp ("cjne", (*pl)->line, 4) == 0)
354 isConditionalJump = TRUE;
359 if (strncmp ("djnz", (*pl)->line, 4) == 0)
361 isConditionalJump = TRUE;
366 if (strncmp ("jmp", (*pl)->line, 3) == 0)
367 /* "jmp @a+dptr": no chance to trace execution */
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)
374 isConditionalJump = TRUE;
377 if (strncmp ("jbc", (*pl)->line, 3) == 0 ||
378 strncmp ("jb", (*pl)->line, 2) == 0 ||
379 strncmp ("jnb", (*pl)->line, 3) == 0)
381 isConditionalJump = TRUE;
386 if (strncmp ("lcall", (*pl)->line, 5) == 0)
388 if (strncmp ("ljmp", (*pl)->line, 4) == 0)
390 *pl = findLabel (*pl);
396 if (strncmp ("pop", (*pl)->line, 3) == 0 ||
397 strncmp ("push", (*pl)->line, 4) == 0)
402 if (strncmp ("ret", (*pl)->line, 3) == 0) /* catches "reti" too */
406 if (strncmp ("sjmp", (*pl)->line, 4) == 0)
408 *pl = findLabel (*pl);
415 } /* switch ((*pl)->line[0]) */
417 if (isConditionalJump)
419 *plCond = findLabel (*pl);
424 } /* for (; *pl; *pl = (*pl)->next) */
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 /*-----------------------------------------------------------------*/
434 doPushScan (lineNode **pl, const char *pReg)
436 lineNode *plConditional, *pushPl = NULL;
438 for (;; *pl = (*pl)->next)
440 switch (scan4op (pl, pReg, "push", &plConditional))
442 case S4O_FOUNDOPCODE:
443 /* this is what we're looking for */
448 D(fprintf (stderr, DEADMOVEERROR);)
452 /* already checked */
455 /* two possible destinations: recurse */
457 lineNode *pushPl2 = plConditional;
459 if (!doPushScan (&pushPl2, pReg))
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 /*-----------------------------------------------------------------*/
476 doTermScan (lineNode **pl, const char *pReg)
478 lineNode *plConditional;
480 for (;; *pl = (*pl)->next)
482 switch (scan4op (pl, pReg, NULL, &plConditional))
487 /* all these are terminating condtions */
490 /* don't care, go on */
493 /* two possible destinations: recurse */
495 lineNode *pl2 = plConditional;
497 if (!doTermScan (&pl2, pReg))
509 /*-----------------------------------------------------------------*/
511 /*-----------------------------------------------------------------*/
513 mcs51DeadMove (const char *op1, lineNode *currPl, lineNode *head)
516 lineNode *pushPl, *pl;
518 /* A pop/push pair can be removed, if these criteria are met
519 (ar0 is just an example here, ar0...ar7 are possible):
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
530 ; - a jump in or out of area 1 (see checkLabelRef())
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.
535 ; area 1 must be terminated by a:
541 ; - read access of ar0
542 ; - "jmp @a+dptr" opcode
544 ; - a jump in or out of area 2 (see checkLabelRef())
546 ; An "acall", "lcall", "ret", "reti" or write access of ar0 terminate
547 ; the search, and the pop/push pair can safely be removed.
553 unvisitLines (_G.head);
557 pushPl = currPl->next;
558 if (!doPushScan (&pushPl, pReg))
561 if (!checkLabelRef())
566 if (!doTermScan (&pl, pReg))
568 if (!checkLabelRef())
572 if (options.noPeepComments)
574 /* remove pushPl from list */
575 pushPl->prev->next = pushPl->next;
576 pushPl->next->prev = pushPl->prev;
580 /* replace 'push ar0' by comment */
581 #define STR ";\tPeephole\tpush %s removed"
582 int size = sizeof(STR) + 2;
584 pushPl->line = Safe_alloc (size);
585 SNPRINTF (pushPl->line, size, STR, pReg);
586 pushPl->isComment = TRUE;
589 /* 'pop ar0' will be removed by peephole framework after returning TRUE */