1 /*-----------------------------------------------------------------
2 SDCClabel.c - label optimizations on iCode (intermediate code)
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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 -------------------------------------------------------------------------*/
27 hTab *labelRef = NULL;
28 hTab *labelDef = NULL;
30 /*-----------------------------------------------------------------*/
31 /* buildLabelRefTable - creates an hashTable of label referneces */
32 /*-----------------------------------------------------------------*/
34 buildLabelRefTable (iCode * ic)
38 setToNull ((void **) &labelRef);
39 setToNull ((void **) &labelDef);
40 labelRef = newHashTable (labelKey + 1);
41 labelDef = newHashTable (labelKey + 1);
43 for (lic = ic; lic; lic = lic->next)
46 hTabAddItem (&labelRef, (IC_LABEL (lic))->key, lic);
48 if (lic->op == JUMPTABLE)
51 for (lbl = setFirstItem (IC_JTLABELS (lic)); lbl;
52 lbl = setNextItem (IC_JTLABELS (lic)))
54 hTabAddItem (&labelRef, lbl->key, lic);
61 hTabAddItem (&labelRef, (IC_TRUE (lic))->key, lic);
63 hTabAddItem (&labelRef, (IC_FALSE (lic))->key, lic);
66 hTabAddItem (&labelDef, (IC_LABEL (lic))->key, lic);
71 /*-----------------------------------------------------------------*/
72 /* labelGotoNext - kills gotos to next statement */
73 /*-----------------------------------------------------------------*/
75 labelGotoNext (iCode * ic)
80 for (loop = ic; loop; loop = loop->next)
83 if (loop->op == GOTO && /* if this is a goto */
84 loop->next && /* and we have a next one */
85 loop->next->op == LABEL && /* next one is a label */
86 loop->next->argLabel.label->key == loop->argLabel.label->key) /* same label */
88 loop->prev->next = loop->next; /* get this out of the chain */
89 loop->next->prev = loop->prev;
90 hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
98 /*-----------------------------------------------------------------*/
99 /* labelIfx - special case Ifx elimination */
100 /*-----------------------------------------------------------------*/
102 labelIfx (iCode * ic)
108 for (loop = ic; loop; loop = loop->next)
110 /* if condition goto label */
112 /* i.e. the flow is going to the same location
113 regardless of the condition in this case the
114 condition can be eliminated with a WARNING ofcource */
115 if (loop->op == IFX &&
117 loop->next->op == GOTO)
119 if (IC_TRUE (loop) &&
120 IC_TRUE (loop)->key == IC_LABEL (loop->next)->key)
123 /* get rid of this if */
124 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
125 loop->prev->next = loop->next;
126 loop->next->prev = loop->prev;
127 hTabDeleteItem (&labelRef,
128 (IC_TRUE (loop))->key,
129 loop, DELETE_ITEM, NULL);
135 if (IC_FALSE (loop) &&
136 IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
138 /* get rid of this if */
139 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
140 loop->prev->next = loop->next;
141 loop->next->prev = loop->prev;
142 hTabDeleteItem (&labelRef,
143 (IC_FALSE (loop))->key,
144 loop, DELETE_ITEM, NULL);
150 /* same as above but with a twist */
151 /* if condition goto label */
153 if (loop->op == IFX &&
155 loop->next->op == LABEL &&
156 ((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
157 (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
160 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
161 loop->prev->next = loop->next;
162 loop->next->prev = loop->prev;
163 hTabDeleteItem (&labelRef,
164 IC_LABEL (loop->next)->key,
165 loop, DELETE_ITEM, NULL);
170 /* we will eliminate certain special case situations */
171 /* of the conditional statement :- */
172 /* if cond != 0 goto _trueLabel */
173 /* goto _falseLabel */
176 /* in these cases , if this is the only reference */
177 /* to the _trueLabel, we can change it to :- */
178 /* if cond == 0 goto _falseLabel */
180 /* similarly if we have a situation like :- */
181 /* if cond == 0 goto _falseLabel */
182 /* goto _someLabel */
184 /* we can change this to */
185 /* if cond != 0 goto _someLabel */
187 if (loop->op == IFX &&
189 loop->next->op == GOTO &&
191 loop->next->next->op == LABEL)
195 /* now check that the last label is the */
196 /* same as the _trueLabel of this */
198 if ((IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key)
201 else if ((IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key)
204 /* now make sure that this is the only */
205 /* referenece to the _trueLabel */
206 if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
209 /* we just change the falseLabel */
210 /* to the next goto statement */
211 /* unreferenced label will take */
212 /* care of removing the label */
213 /* delete reference to the true label */
215 hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
216 IC_TRUE (loop) = NULL;
217 IC_FALSE (loop) = IC_LABEL (loop->next);
218 /* add reference to the LABEL */
219 hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
220 /* next remove the goto */
221 hTabDeleteItem (&labelRef,
222 (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
223 loop->next = loop->next->next;
224 loop->next->prev = loop;
229 /* now do the same with the false labels */
230 if (IC_FALSE (loop) &&
231 hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
234 hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
235 IC_FALSE (loop) = NULL;
236 IC_TRUE (loop) = IC_LABEL (loop->next);
237 hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
238 hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
239 loop->next = loop->next->next;
240 loop->next->prev = loop;
250 /*-----------------------------------------------------------------*/
251 /* labelGotoGoto - target of a goto is a goto */
252 /*-----------------------------------------------------------------*/
254 labelGotoGoto (iCode * ic)
259 for (loop = ic; loop; loop = loop->next)
262 symbol *sLabel = NULL;
266 case GOTO: /* for a goto statement */
267 stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);
269 case IFX: /* for a conditional jump */
271 stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
273 stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);
276 /* if we have a target statement then check if the next */
277 /* one is a goto: this means target of goto is a goto */
278 if (stat && stat->next &&
279 (stat->next->op == GOTO ||
280 stat->next->op == LABEL) &&
284 symbol *repLabel = stat->next->argLabel.label; /* replace with label */
286 /* if they are the same then continue */
287 if (repLabel->key == sLabel->key)
290 /* replacement depends on the statement type */
294 case GOTO: /* for a goto statement */
296 hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
297 loop->argLabel.label = repLabel;
298 hTabAddItem (&labelRef, repLabel->key, loop);
301 case IFX: /* for a conditional jump */
305 hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
306 IC_TRUE (loop) = repLabel;
311 hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
312 IC_FALSE (loop) = repLabel;
314 hTabAddItem (&labelRef, repLabel->key, loop);
324 /*-----------------------------------------------------------------*/
325 /* labelUnrefLabel - remove unreferneced labels */
326 /*-----------------------------------------------------------------*/
328 labelUnrefLabel (iCode * ic)
333 for (loop = ic; loop; loop = loop->next)
336 /* if this is a label */
337 if (loop->op == LABEL)
342 if (((IC_LABEL (loop))->key == returnLabel->key) ||
343 ((IC_LABEL (loop))->key == entryLabel->key))
346 if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
349 /* else eliminitate this one */
350 loop->prev->next = loop->next; /* get this out of the chain */
351 loop->next->prev = loop->prev;
359 /*-----------------------------------------------------------------*/
360 /* labelUnreach - remove unreachable code */
361 /*-----------------------------------------------------------------*/
363 labelUnreach (iCode * ic)
369 /* if we hit a return statement or a goto statement */
370 /* remove all statements till we hit the next label */
371 for (loop = ic; loop; loop = loop->next)
375 /* found a goto || return && the next */
376 /* statement is not a label */
377 if (loop->op == GOTO || loop->op == RETURN)
381 (loop->next->op == LABEL ||
382 loop->next->op == ENDFUNCTION))
385 /* loop till we find a label */
387 while (loop2 && loop2->op != LABEL)
390 /* throw away those in between */
391 for (tic = loop->next; tic && tic != loop2; tic = tic->next)
393 /* remove label references if any */
397 hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
401 hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
403 hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
409 /* now set up the pointers */
419 /*-----------------------------------------------------------------*/
420 /* iCodeLabelOptimize - some obvious & general optimizations */
421 /*-----------------------------------------------------------------*/
423 iCodeLabelOptimize (iCode * ic)
425 if (!optimize.label1 &&
431 /* build labelreferences */
432 buildLabelRefTable (ic);
434 /* the following transformations need to ne done */
435 /* repeatedly till a fixed point is reached */
441 /* first eliminate any goto statement */
442 /* that goes to the next statement */
444 change += labelGotoNext (ic);
447 change += labelIfx (ic);
449 /* target of a goto is a goto then rename this goto */
451 change += labelGotoGoto (ic);
453 /* remove unreference labels */
455 change += labelUnrefLabel (ic);
457 /* remove unreachable code */
458 change += labelUnreach (ic);
460 if (!change) /* fixed point reached */