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 references */
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->label->key == loop->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 if (!options.lessPedantic) {
125 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
127 loop->prev->next = loop->next;
128 loop->next->prev = loop->prev;
129 hTabDeleteItem (&labelRef,
130 (IC_TRUE (loop))->key,
131 loop, DELETE_ITEM, NULL);
137 if (IC_FALSE (loop) &&
138 IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
140 /* get rid of this if */
141 if (!options.lessPedantic) {
142 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
144 loop->prev->next = loop->next;
145 loop->next->prev = loop->prev;
146 hTabDeleteItem (&labelRef,
147 (IC_FALSE (loop))->key,
148 loop, DELETE_ITEM, NULL);
154 /* same as above but with a twist */
155 /* if condition goto label */
157 if (loop->op == IFX &&
159 loop->next->op == LABEL &&
160 ((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
161 (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
163 if (!options.lessPedantic) {
164 werror (W_CONTROL_FLOW, loop->filename, loop->lineno);
166 loop->prev->next = loop->next;
167 loop->next->prev = loop->prev;
168 hTabDeleteItem (&labelRef,
169 IC_LABEL (loop->next)->key,
170 loop, DELETE_ITEM, NULL);
175 /* we will eliminate certain special case situations */
176 /* of the conditional statement :- */
177 /* if cond != 0 goto _trueLabel */
178 /* goto _falseLabel */
181 /* in these cases , if this is the only reference */
182 /* to the _trueLabel, we can change it to :- */
183 /* if cond == 0 goto _falseLabel */
185 /* similarly if we have a situation like :- */
186 /* if cond == 0 goto _falseLabel */
187 /* goto _someLabel */
189 /* we can change this to */
190 /* if cond != 0 goto _someLabel */
192 if (loop->op == IFX &&
194 loop->next->op == GOTO &&
196 loop->next->next->op == LABEL)
200 /* now check that the last label is the */
201 /* same as the _trueLabel of this */
203 if ((IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key)
206 else if ((IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key)
209 /* now make sure that this is the only */
210 /* referenece to the _trueLabel */
211 if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
214 /* we just change the falseLabel */
215 /* to the next goto statement */
216 /* unreferenced label will take */
217 /* care of removing the label */
218 /* delete reference to the true label */
220 hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
221 IC_TRUE (loop) = NULL;
222 IC_FALSE (loop) = IC_LABEL (loop->next);
223 /* add reference to the LABEL */
224 hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
225 /* next remove the goto */
226 hTabDeleteItem (&labelRef,
227 (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
228 loop->next = loop->next->next;
229 loop->next->prev = loop;
234 /* now do the same with the false labels */
235 if (IC_FALSE (loop) &&
236 hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
239 hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
240 IC_FALSE (loop) = NULL;
241 IC_TRUE (loop) = IC_LABEL (loop->next);
242 hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
243 hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
244 loop->next = loop->next->next;
245 loop->next->prev = loop;
255 /*-----------------------------------------------------------------*/
256 /* labelGotoGoto - target of a goto is a goto */
257 /*-----------------------------------------------------------------*/
259 labelGotoGoto (iCode * ic)
264 for (loop = ic; loop; loop = loop->next)
267 symbol *sLabel = NULL;
271 case GOTO: /* for a goto statement */
272 stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);
274 case IFX: /* for a conditional jump */
276 stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
278 stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);
281 /* if we have a target statement then check if the next */
282 /* one is a goto: this means target of goto is a goto */
283 if (stat && stat->next &&
284 (stat->next->op == GOTO ||
285 stat->next->op == LABEL) &&
289 symbol *repLabel = stat->next->label; /* replace with label */
291 /* if they are the same then continue */
292 if (repLabel->key == sLabel->key)
295 /* replacement depends on the statement type */
299 case GOTO: /* for a goto statement */
301 hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
302 loop->label = repLabel;
303 hTabAddItem (&labelRef, repLabel->key, loop);
306 case IFX: /* for a conditional jump */
310 hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
311 IC_TRUE (loop) = repLabel;
316 hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
317 IC_FALSE (loop) = repLabel;
319 hTabAddItem (&labelRef, repLabel->key, loop);
329 /*-----------------------------------------------------------------*/
330 /* labelUnrefLabel - remove unreferenced labels */
331 /*-----------------------------------------------------------------*/
333 labelUnrefLabel (iCode * ic)
338 for (loop = ic; loop; loop = loop->next)
341 /* if this is a label */
342 if (loop->op == LABEL)
344 if (((IC_LABEL (loop))->key == returnLabel->key) ||
345 ((IC_LABEL (loop))->key == entryLabel->key))
348 if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
351 /* else eliminitate this one */
352 loop->prev->next = loop->next; /* get this out of the chain */
353 loop->next->prev = loop->prev;
361 /*-----------------------------------------------------------------*/
362 /* labelUnreach - remove unreachable code */
363 /*-----------------------------------------------------------------*/
365 labelUnreach (iCode * ic)
371 /* if we hit a return statement or a goto statement */
372 /* remove all statements till we hit the next label */
373 for (loop = ic; loop; loop = loop->next)
377 /* found a goto || return && the next */
378 /* statement is not a label */
379 if (loop->op == GOTO || loop->op == RETURN)
383 (loop->next->op == LABEL ||
384 loop->next->op == ENDFUNCTION))
387 /* loop till we find a label */
389 while (loop2 && loop2->op != LABEL)
392 /* throw away those in between */
393 for (tic = loop->next; tic && tic != loop2; tic = tic->next)
395 /* remove label references if any */
399 hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
403 hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
405 hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
411 /* now set up the pointers */
421 /*-----------------------------------------------------------------*/
422 /* iCodeLabelOptimize - some obvious & general optimizations */
423 /*-----------------------------------------------------------------*/
425 iCodeLabelOptimize (iCode * ic)
427 if (!optimize.label1 &&
433 /* build labelreferences */
434 buildLabelRefTable (ic);
436 /* the following transformations need to ne done */
437 /* repeatedly till a fixed point is reached */
443 /* first eliminate any goto statement */
444 /* that goes to the next statement */
446 change += labelGotoNext (ic);
449 change += labelIfx (ic);
451 /* target of a goto is a goto then rename this goto */
453 change += labelGotoGoto (ic);
455 /* remove unreference labels */
457 change += labelUnrefLabel (ic);
459 /* remove unreachable code */
460 change += labelUnreach (ic);
462 if (!change) /* fixed point reached */