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 /*-----------------------------------------------------------------*/
33 void buildLabelRefTable (iCode *ic)
37 setToNull ((void **)&labelRef);
38 setToNull ((void **)&labelDef);
39 labelRef = newHashTable(labelKey + 1);
40 labelDef = newHashTable(labelKey + 1);
42 for (lic = ic ; lic ; lic = lic->next ) {
43 if ( lic->op == GOTO )
44 hTabAddItem (&labelRef, (IC_LABEL(lic))->key, lic);
46 if ( lic->op == JUMPTABLE ) {
48 for (lbl = setFirstItem(IC_JTLABELS(lic)); lbl;
49 lbl = setNextItem(IC_JTLABELS(lic))) {
50 hTabAddItem(&labelRef,lbl->key,lic);
54 if (lic->op == IFX ) {
56 hTabAddItem(&labelRef,(IC_TRUE(lic))->key, lic);
58 hTabAddItem(&labelRef,(IC_FALSE(lic))->key, lic);
60 if ( lic->op == LABEL )
61 hTabAddItem (&labelDef,(IC_LABEL(lic))->key, lic);
66 /*-----------------------------------------------------------------*/
67 /* labelGotoNext - kills gotos to next statement */
68 /*-----------------------------------------------------------------*/
69 int labelGotoNext (iCode *ic)
74 for ( loop = ic ; loop ; loop = loop->next) {
76 if (loop->op == GOTO && /* if this is a goto */
77 loop->next && /* and we have a next one */
78 loop->next->op == LABEL && /* next one is a label */
79 loop->next->argLabel.label->key == loop->argLabel.label->key) /* same label */
81 loop->prev->next = loop->next ; /* get this out of the chain */
82 loop->next->prev = loop->prev ;
83 hTabDeleteItem (&labelRef,(IC_LABEL(loop))->key, loop, DELETE_ITEM, NULL);
91 /*-----------------------------------------------------------------*/
92 /* labelIfx - special case Ifx elimination */
93 /*-----------------------------------------------------------------*/
94 int labelIfx ( iCode *ic)
100 for ( loop = ic ; loop ; loop = loop->next ) {
101 /* if condition goto label */
103 /* i.e. the flow is going to the same location
104 regardless of the condition in this case the
105 condition can be eliminated with a WARNING ofcource */
106 if ( loop->op == IFX &&
108 loop->next->op == GOTO ) {
110 IC_TRUE(loop)->key == IC_LABEL(loop->next)->key) {
112 /* get rid of this if */
113 werror(W_CONTROL_FLOW,loop->filename,loop->lineno);
114 loop->prev->next = loop->next;
115 loop->next->prev = loop->prev;
116 hTabDeleteItem(&labelRef,
117 (IC_TRUE(loop))->key,
118 loop, DELETE_ITEM,NULL);
123 if (IC_FALSE(loop) &&
124 IC_FALSE(loop)->key == IC_LABEL(loop->next)->key){
125 /* get rid of this if */
126 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_FALSE(loop))->key,
131 loop, DELETE_ITEM,NULL);
137 /* same as above but with a twist */
138 /* if condition goto label */
140 if (loop->op == IFX &&
142 loop->next->op == LABEL &&
143 ((IC_TRUE(loop) && IC_TRUE(loop)->key == IC_LABEL(loop->next)->key) ||
144 (IC_FALSE(loop) && IC_FALSE(loop)->key == IC_LABEL(loop->next)->key))) {
146 werror(W_CONTROL_FLOW,loop->filename,loop->lineno);
147 loop->prev->next = loop->next;
148 loop->next->prev = loop->prev;
149 hTabDeleteItem(&labelRef,
150 IC_LABEL(loop->next)->key,
151 loop, DELETE_ITEM,NULL);
156 /* we will eliminate certain special case situations*/
157 /* of the conditional statement :- */
158 /* if cond != 0 goto _trueLabel */
159 /* goto _falseLabel */
162 /* in these cases , if this is the only reference */
163 /* to the _trueLabel, we can change it to :- */
164 /* if cond == 0 goto _falseLabel */
166 /* similarly if we have a situation like :- */
167 /* if cond == 0 goto _falseLabel */
168 /* goto _someLabel */
170 /* we can change this to */
171 /* if cond != 0 goto _someLabel */
173 if (loop->op == IFX &&
175 loop->next->op == GOTO &&
177 loop->next->next->op == LABEL ) {
180 /* now check that the last label is the */
181 /* same as the _trueLabel of this */
183 if ( (IC_TRUE(loop))->key != (IC_LABEL(loop->next->next))->key )
187 if ( (IC_FALSE(loop))->key != (IC_LABEL(loop->next->next))->key )
190 /* now make sure that this is the only */
191 /* referenece to the _trueLabel */
192 if ( IC_TRUE(loop) && hTabItemWithKey(labelRef,(IC_TRUE(loop))->key) ) {
194 /* we just change the falseLabel */
195 /* to the next goto statement */
196 /* unreferenced label will take */
197 /* care of removing the label */
198 /* delete reference to the true label */
200 hTabDeleteItem(&labelRef, (IC_TRUE(loop))->key, loop, DELETE_ITEM,NULL);
201 IC_TRUE(loop) = NULL ;
202 IC_FALSE(loop) = IC_LABEL(loop->next);
203 /* add reference to the LABEL */
204 hTabAddItem (&labelRef,(IC_FALSE(loop))->key,loop);
205 /* next remove the goto */
206 hTabDeleteItem(&labelRef,
207 (IC_LABEL(loop->next))->key,loop->next,DELETE_ITEM,NULL);
208 loop->next = loop->next->next ;
209 loop->next->prev = loop ;
214 /* now do the same with the false labels */
215 if (IC_FALSE(loop) &&
216 hTabItemWithKey(labelRef,(IC_FALSE(loop))->key)) {
218 hTabDeleteItem(&labelRef, (IC_FALSE(loop))->key, loop, DELETE_ITEM,NULL);
219 IC_FALSE(loop) = NULL ;
220 IC_TRUE(loop) = IC_LABEL(loop->next);
221 hTabAddItem (&labelRef,(IC_TRUE(loop))->key,loop);
222 hTabDeleteItem(&labelRef,(IC_LABEL(loop->next))->key,loop->next,DELETE_ITEM,NULL);
223 loop->next = loop->next->next ;
224 loop->next->prev = loop ;
234 /*-----------------------------------------------------------------*/
235 /* labelGotoGoto - target of a goto is a goto */
236 /*-----------------------------------------------------------------*/
237 int labelGotoGoto (iCode *ic)
242 for ( loop = ic ; loop ; loop = loop->next ) {
244 symbol *sLabel = NULL;
247 case GOTO: /* for a goto statement */
248 stat = hTabItemWithKey(labelDef,(sLabel = IC_LABEL(loop))->key) ;
250 case IFX : /* for a conditional jump */
252 stat = hTabItemWithKey(labelDef,(sLabel = IC_TRUE(loop))->key);
254 stat = hTabItemWithKey (labelDef,(sLabel = IC_FALSE(loop))->key);
257 /* if we have a target statement then check if the next */
258 /* one is a goto: this means target of goto is a goto */
259 if ( stat && stat->next &&
260 ( stat->next->op == GOTO ||
261 stat->next->op == LABEL) &&
262 stat->next != loop ) {
264 symbol *repLabel = stat->next->argLabel.label ; /* replace with label */
266 /* if they are the same then continue */
267 if (repLabel->key == sLabel->key)
270 /* replacement depends on the statement type */
273 case GOTO: /* for a goto statement */
275 hTabDeleteItem (&labelRef, (IC_LABEL(loop))->key, loop,DELETE_ITEM,NULL);
276 loop->argLabel.label = repLabel ;
277 hTabAddItem (&labelRef, repLabel->key, loop);
280 case IFX : /* for a conditional jump */
283 hTabDeleteItem (&labelRef, (IC_TRUE(loop))->key, loop,DELETE_ITEM,NULL);
284 IC_TRUE(loop) = repLabel ;
288 hTabDeleteItem (&labelRef, (IC_FALSE(loop))->key, loop,DELETE_ITEM,NULL);
289 IC_FALSE(loop) = repLabel;
291 hTabAddItem (&labelRef, repLabel->key, loop);
301 /*-----------------------------------------------------------------*/
302 /* labelUnrefLabel - remove unreferneced labels */
303 /*-----------------------------------------------------------------*/
304 int labelUnrefLabel (iCode *ic)
309 for ( loop = ic ; loop ; loop = loop->next) {
311 /* if this is a label */
312 if (loop->op == LABEL) {
316 if ( ( (IC_LABEL(loop))->key == returnLabel->key ) ||
317 ( (IC_LABEL(loop))->key == entryLabel->key ) )
320 if (hTabItemWithKey(labelRef,(IC_LABEL(loop))->key) )
323 /* else eliminitate this one */
324 loop->prev->next = loop->next ; /* get this out of the chain */
325 loop->next->prev = loop->prev ;
333 /*-----------------------------------------------------------------*/
334 /* labelUnreach - remove unreachable code */
335 /*-----------------------------------------------------------------*/
336 int labelUnreach (iCode *ic)
342 /* if we hit a return statement or a goto statement */
343 /* remove all statements till we hit the next label */
344 for (loop = ic ; loop ; loop = loop->next) {
347 /* found a goto || return && the next */
348 /* statement is not a label */
349 if (loop->op == GOTO || loop->op == RETURN ) {
352 (loop->next->op == LABEL ||
353 loop->next->op == ENDFUNCTION ))
356 /* loop till we find a label */
358 while (loop2 && loop2->op != LABEL)
361 /* throw away those in between */
362 for (tic = loop->next ; tic && tic != loop2 ; tic=tic->next) {
363 /* remove label references if any */
366 hTabDeleteItem (&labelRef,IC_LABEL(tic)->key,tic,DELETE_ITEM,NULL);
370 hTabDeleteItem (&labelRef,IC_TRUE(tic)->key,tic,DELETE_ITEM,NULL);
372 hTabDeleteItem (&labelRef,IC_FALSE(tic)->key,tic,DELETE_ITEM,NULL);
378 /* now set up the pointers */
388 /*-----------------------------------------------------------------*/
389 /* iCodeLabelOptimize - some obvious & general optimizations */
390 /*-----------------------------------------------------------------*/
391 iCode *iCodeLabelOptimize (iCode *ic)
393 if (!optimize.label1 &&
399 /* build labelreferences */
400 buildLabelRefTable (ic);
402 /* the following transformations need to ne done */
403 /* repeatedly till a fixed point is reached */
408 /* first eliminate any goto statement */
409 /* that goes to the next statement */
411 change += labelGotoNext (ic);
413 if ( optimize.label2 )
414 change += labelIfx (ic);
416 /* target of a goto is a goto then rename this goto */
417 if (optimize.label3 )
418 change += labelGotoGoto (ic);
420 /* remove unreference labels */
422 change += labelUnrefLabel (ic);
424 /* remove unreachable code */
425 change += labelUnreach (ic);
427 if (!change) /* fixed point reached */