536 lines
18 KiB
C
536 lines
18 KiB
C
/*-----------------------------------------------------------------
|
|
SDCClabel.c - label optimizations on iCode (intermediate code)
|
|
|
|
Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
|
|
|
|
This program is free software; you can redistribute it and/or modify it
|
|
under the terms of the GNU General Public License as published by the
|
|
Free Software Foundation; either version 2, or (at your option) any
|
|
later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
|
|
|
|
In other words, you are welcome to use, share and improve this program.
|
|
You are forbidden to forbid anyone else to use, share and improve
|
|
what you give them. Help stamp out software-hoarding!
|
|
-------------------------------------------------------------------------*/
|
|
|
|
#include "common.h"
|
|
|
|
hTab *labelRef = NULL;
|
|
hTab *labelDef = NULL;
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* buildLabelRefTable - creates an hashTable of label references */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
buildLabelRefTable (iCode * ic)
|
|
{
|
|
iCode *lic;
|
|
|
|
setToNull ((void *) &labelRef);
|
|
setToNull ((void *) &labelDef);
|
|
labelRef = newHashTable (labelKey + 1);
|
|
labelDef = newHashTable (labelKey + 1);
|
|
|
|
for (lic = ic; lic; lic = lic->next)
|
|
{
|
|
if (lic->op == GOTO)
|
|
hTabAddItem (&labelRef, (IC_LABEL (lic))->key, lic);
|
|
|
|
if (lic->op == JUMPTABLE)
|
|
{
|
|
symbol *lbl;
|
|
for (lbl = setFirstItem (IC_JTLABELS (lic)); lbl;
|
|
lbl = setNextItem (IC_JTLABELS (lic)))
|
|
{
|
|
hTabAddItem (&labelRef, lbl->key, lic);
|
|
}
|
|
}
|
|
|
|
if (lic->op == IFX)
|
|
{
|
|
if (IC_TRUE (lic))
|
|
hTabAddItem (&labelRef, (IC_TRUE (lic))->key, lic);
|
|
else
|
|
hTabAddItem (&labelRef, (IC_FALSE (lic))->key, lic);
|
|
}
|
|
if (lic->op == LABEL)
|
|
hTabAddItem (&labelDef, (IC_LABEL (lic))->key, lic);
|
|
|
|
}
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* labelGotoNext - kills gotos to next statement */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
labelGotoNext (iCode * ic)
|
|
{
|
|
iCode *loop;
|
|
int change = 0;
|
|
|
|
for (loop = ic; loop; loop = loop->next)
|
|
{
|
|
|
|
if (loop->op == GOTO && /* if this is a goto */
|
|
loop->next && /* and we have a next one */
|
|
loop->next->op == LABEL && /* next one is a label */
|
|
loop->next->label->key == loop->label->key) /* same label */
|
|
{
|
|
loop->prev->next = loop->next; /* get this out of the chain */
|
|
loop->next->prev = loop->prev;
|
|
hTabDeleteItem (&labelRef, (IC_LABEL (loop))->key, loop, DELETE_ITEM, NULL);
|
|
change++;
|
|
}
|
|
}
|
|
|
|
return change;
|
|
}
|
|
|
|
/*-------------------------------------------------------------------*/
|
|
/* deleteIfx - delete an IFX iCode or convert to DUMMY_READ_VOLATILE */
|
|
/*-------------------------------------------------------------------*/
|
|
static void
|
|
deleteIfx (iCode * loop, int key)
|
|
{
|
|
werrorfl (loop->filename, loop->lineno, W_CONTROL_FLOW);
|
|
hTabDeleteItem (&labelRef, key, loop, DELETE_ITEM, NULL);
|
|
|
|
/* If the condition was volatile, convert IFX to */
|
|
/* DUMMY_READ_VOLATILE. Otherwise just delete the */
|
|
/* IFX iCode */
|
|
if (IS_OP_VOLATILE (IC_COND (loop)))
|
|
{
|
|
IC_RIGHT (loop) = IC_COND (loop);
|
|
IC_LEFT (loop) = NULL;
|
|
IC_RESULT (loop) = NULL;
|
|
loop->op = DUMMY_READ_VOLATILE;
|
|
}
|
|
else
|
|
{
|
|
loop->prev->next = loop->next;
|
|
loop->next->prev = loop->prev;
|
|
}
|
|
}
|
|
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* labelIfx - special case Ifx elimination */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
labelIfx (iCode * ic)
|
|
{
|
|
iCode *loop;
|
|
iCode *stat;
|
|
int change = 0;
|
|
|
|
for (loop = ic; loop; loop = loop->next)
|
|
{
|
|
/* if condition goto label */
|
|
/* goto label */
|
|
/* i.e. the flow is going to the same location
|
|
regardless of the condition in this case the
|
|
condition can be eliminated with a WARNING ofcource */
|
|
if (loop->op == IFX &&
|
|
loop->next &&
|
|
loop->next->op == GOTO)
|
|
{
|
|
if (IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key)
|
|
{
|
|
deleteIfx (loop, IC_TRUE (loop)->key);
|
|
change++;
|
|
continue;
|
|
}
|
|
else
|
|
{
|
|
if (IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)
|
|
{
|
|
deleteIfx (loop, IC_FALSE (loop)->key);
|
|
change++;
|
|
continue;
|
|
}
|
|
}
|
|
}
|
|
/* same as above but with a twist */
|
|
/* if condition goto label */
|
|
/* label: */
|
|
if (loop->op == IFX &&
|
|
loop->next &&
|
|
loop->next->op == LABEL &&
|
|
((IC_TRUE (loop) && IC_TRUE (loop)->key == IC_LABEL (loop->next)->key) ||
|
|
(IC_FALSE (loop) && IC_FALSE (loop)->key == IC_LABEL (loop->next)->key)))
|
|
{
|
|
deleteIfx (loop, IC_LABEL (loop->next)->key);
|
|
change++;
|
|
continue;
|
|
}
|
|
|
|
/* we will eliminate certain special case situations */
|
|
/* of the conditional statement :- */
|
|
/* if cond != 0 goto _trueLabel */
|
|
/* goto _falseLabel */
|
|
/* _trueLabel : */
|
|
/* ... */
|
|
/* in these cases we can change it to :- */
|
|
/* if cond == 0 goto _falseLabel */
|
|
/* _trueLabel : */
|
|
/* ... */
|
|
/* similarly if we have a situation like :- */
|
|
/* if cond == 0 goto _falseLabel */
|
|
/* goto _someLabel */
|
|
/* _falseLabel : */
|
|
/* we can change this to */
|
|
/* if cond != 0 goto _someLabel */
|
|
/* _falseLabel : */
|
|
/* ... */
|
|
if (loop->op == IFX && loop->next && loop->next->op == GOTO &&
|
|
loop->next->next && loop->next->next->op == LABEL)
|
|
{
|
|
if (IC_TRUE (loop) && (IC_TRUE (loop))->key != (IC_LABEL (loop->next->next))->key ||
|
|
(IC_FALSE (loop) && (IC_FALSE (loop))->key != (IC_LABEL (loop->next->next))->key))
|
|
continue;
|
|
|
|
/* now make sure that this is the only */
|
|
/* referenece to the _trueLabel */
|
|
if (IC_TRUE (loop) && hTabItemWithKey (labelRef, (IC_TRUE (loop))->key))
|
|
{
|
|
/* we just change the falseLabel */
|
|
/* to the next goto statement */
|
|
/* unreferenced label will take */
|
|
/* care of removing the label */
|
|
/* delete reference to the true label */
|
|
|
|
hTabDeleteItem (&labelRef, (IC_TRUE (loop))->key, loop, DELETE_ITEM, NULL);
|
|
IC_TRUE (loop) = NULL;
|
|
IC_FALSE (loop) = IC_LABEL (loop->next);
|
|
/* add reference to the LABEL */
|
|
hTabAddItem (&labelRef, (IC_FALSE (loop))->key, loop);
|
|
/* next remove the goto */
|
|
hTabDeleteItem (&labelRef,
|
|
(IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
|
|
loop->next = loop->next->next;
|
|
loop->next->prev = loop;
|
|
change++;
|
|
continue;
|
|
}
|
|
|
|
/* now do the same with the false labels */
|
|
if (IC_FALSE (loop) && hTabItemWithKey (labelRef, (IC_FALSE (loop))->key))
|
|
{
|
|
hTabDeleteItem (&labelRef, (IC_FALSE (loop))->key, loop, DELETE_ITEM, NULL);
|
|
IC_FALSE (loop) = NULL;
|
|
IC_TRUE (loop) = IC_LABEL (loop->next);
|
|
hTabAddItem (&labelRef, (IC_TRUE (loop))->key, loop);
|
|
hTabDeleteItem (&labelRef, (IC_LABEL (loop->next))->key, loop->next, DELETE_ITEM, NULL);
|
|
loop->next = loop->next->next;
|
|
loop->next->prev = loop;
|
|
change++;
|
|
continue;
|
|
}
|
|
}
|
|
|
|
/* Optimize hidden jump-to-jump:
|
|
Simplify
|
|
v = 1; stat->prev
|
|
goto l1; stat
|
|
l0:
|
|
v = 0; loop->prev
|
|
l1: loop
|
|
if (v) goto l3; loop->next
|
|
Into
|
|
v = 1;
|
|
goto l3;
|
|
l0:
|
|
v = 0;
|
|
l1: */
|
|
if (loop->op == LABEL &&
|
|
loop->next && loop->next->op == IFX &&
|
|
(stat = hTabFirstItemWK (labelRef, (IC_LABEL (loop))->key)) &&
|
|
!hTabNextItemWK (labelRef) &&
|
|
stat && stat->op == GOTO &&
|
|
stat->prev && stat->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (stat->prev)) &&
|
|
loop->prev && loop->prev->op == '=' && IS_OP_LITERAL (IC_RIGHT (loop->prev)) &&
|
|
IC_RESULT (stat->prev)->key == IC_COND (loop->next)->key &&
|
|
IC_RESULT (loop->prev)->key == IC_COND (loop->next)->key &&
|
|
!IS_OP_VOLATILE (IC_COND (loop->next)) &&
|
|
(!operandLitValue (IC_RIGHT (stat->prev)) ^ !operandLitValue (IC_RIGHT (loop->prev))))
|
|
{
|
|
if (IC_FALSE (loop->next) && !operandLitValue (IC_RIGHT (loop->prev)) ||
|
|
IC_TRUE (loop->next) && operandLitValue (IC_RIGHT (loop->prev)))
|
|
/* Complicated case: Insert goto, remove conditional jump. */
|
|
{
|
|
/* Change IFX to GOTO. */
|
|
stat = loop->next;
|
|
IC_LABEL (stat) = IC_TRUE (stat) ? IC_TRUE (stat) : IC_FALSE (stat);
|
|
stat->op = GOTO;
|
|
|
|
/* Move to desired location. */
|
|
if (loop->next->next)
|
|
loop->next->next->prev = loop;
|
|
loop->next = loop->next->next;
|
|
stat->prev = loop->prev;
|
|
stat->prev->next = stat;
|
|
stat->next = loop;
|
|
loop->prev = stat;
|
|
change++;
|
|
continue;
|
|
}
|
|
else /* Simple case: Redirect goto, remove conditional jump. */
|
|
{
|
|
hTabDeleteItem (&labelRef, (IC_LABEL (stat))->key, stat, DELETE_ITEM, NULL);
|
|
IC_LABEL (stat) = IC_TRUE (loop->next) ? IC_TRUE (loop->next) : IC_FALSE (loop->next);
|
|
hTabAddItem (&labelRef, (IC_LABEL (stat))->key, stat);
|
|
hTabDeleteItem (&labelRef, IC_LABEL (stat)->key, loop->next, DELETE_ITEM, NULL);
|
|
if (loop->next->next)
|
|
loop->next->next->prev = loop;
|
|
loop->next = loop->next->next;
|
|
change++;
|
|
continue;
|
|
}
|
|
}
|
|
}
|
|
|
|
return change;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* replaceGotoGoto - find new target for jump */
|
|
/* if we have a target statement then check if the next */
|
|
/* one is a goto: this means target of goto is a goto */
|
|
/*-----------------------------------------------------------------*/
|
|
static symbol *
|
|
replaceGotoGoto (const iCode *ic, const symbol *sLabel, const iCode *target)
|
|
{
|
|
if (!target || !target->next)
|
|
return 0;
|
|
|
|
if (target->next->op != GOTO && target->next->op != LABEL || target->next == ic)
|
|
return 0;
|
|
|
|
symbol *repLabel = target->next->label;
|
|
|
|
if (repLabel == sLabel)
|
|
return 0;
|
|
|
|
return repLabel;
|
|
}
|
|
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* labelGotoGoto - target of a goto is a goto */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
labelGotoGoto (iCode *ic)
|
|
{
|
|
iCode *loop;
|
|
int change = 0;
|
|
|
|
for (loop = ic; loop; loop = loop->next)
|
|
{
|
|
iCode *stat;
|
|
symbol *sLabel = NULL;
|
|
symbol *repLabel;
|
|
stat = NULL;
|
|
switch (loop->op)
|
|
{
|
|
case GOTO: /* for a goto statement */
|
|
|
|
stat = hTabItemWithKey (labelDef, (sLabel = IC_LABEL (loop))->key);
|
|
|
|
if (repLabel = replaceGotoGoto (loop, sLabel, stat))
|
|
{
|
|
hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
|
|
loop->label = repLabel;
|
|
hTabAddItem (&labelRef, repLabel->key, loop);
|
|
change++;
|
|
}
|
|
break;
|
|
|
|
case IFX: /* for a conditional jump */
|
|
|
|
if (IC_TRUE (loop))
|
|
stat = hTabItemWithKey (labelDef, (sLabel = IC_TRUE (loop))->key);
|
|
else
|
|
stat = hTabItemWithKey (labelDef, (sLabel = IC_FALSE (loop))->key);
|
|
|
|
if (repLabel = replaceGotoGoto (loop, sLabel, stat))
|
|
{
|
|
if (IC_TRUE (loop))
|
|
{
|
|
hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
|
|
IC_TRUE (loop) = repLabel;
|
|
}
|
|
else
|
|
{
|
|
hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
|
|
IC_FALSE (loop) = repLabel;
|
|
}
|
|
hTabAddItem (&labelRef, repLabel->key, loop);
|
|
change++;
|
|
}
|
|
break;
|
|
case JUMPTABLE:
|
|
|
|
for (sLabel = setFirstItem (IC_JTLABELS (loop)); sLabel; sLabel = setNextItem (IC_JTLABELS (loop)))
|
|
if (repLabel = replaceGotoGoto (loop, sLabel, hTabItemWithKey (labelDef, sLabel->key)))
|
|
{
|
|
hTabDeleteItem (&labelRef, sLabel->key, loop, DELETE_ITEM, NULL);
|
|
replaceSetItem (IC_JTLABELS (loop), sLabel, repLabel);
|
|
hTabAddItem (&labelRef, repLabel->key, loop);
|
|
change++;
|
|
}
|
|
}
|
|
}
|
|
|
|
return change;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* labelUnrefLabel - remove unreferenced labels */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
labelUnrefLabel (iCode * ic)
|
|
{
|
|
iCode *loop;
|
|
int change = 0;
|
|
|
|
for (loop = ic; loop; loop = loop->next)
|
|
{
|
|
|
|
/* if this is a label */
|
|
if (loop->op == LABEL)
|
|
{
|
|
if (((IC_LABEL (loop))->key == returnLabel->key) ||
|
|
((IC_LABEL (loop))->key == entryLabel->key))
|
|
continue;
|
|
|
|
if (hTabItemWithKey (labelRef, (IC_LABEL (loop))->key))
|
|
continue;
|
|
|
|
/* else eliminitate this one */
|
|
loop->prev->next = loop->next; /* get this out of the chain */
|
|
loop->next->prev = loop->prev;
|
|
change++;
|
|
}
|
|
}
|
|
|
|
return change;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* labelUnreach - remove unreachable code */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
labelUnreach (iCode * ic)
|
|
{
|
|
iCode *loop;
|
|
iCode *tic;
|
|
int change = 0;
|
|
|
|
/* if we hit a return statement or a goto statement */
|
|
/* remove all statements till we hit the next label */
|
|
for (loop = ic; loop; loop = loop->next)
|
|
{
|
|
iCode *loop2;
|
|
|
|
/* found a goto || return && the next */
|
|
/* statement is not a label */
|
|
if (loop->op == GOTO || loop->op == RETURN ||
|
|
loop->op == CALL && IFFUNC_ISNORETURN (operandType (IC_LEFT (loop))))
|
|
{
|
|
if (loop->next &&
|
|
(loop->next->op == LABEL || loop->next->op == ENDFUNCTION))
|
|
continue;
|
|
|
|
/* loop till we find a label */
|
|
loop2 = loop->next;
|
|
while (loop2 && loop2->op != LABEL)
|
|
loop2 = loop2->next;
|
|
|
|
/* throw away those in between */
|
|
for (tic = loop->next; tic && tic != loop2; tic = tic->next)
|
|
{
|
|
/* remove label references if any */
|
|
switch (tic->op)
|
|
{
|
|
case GOTO:
|
|
hTabDeleteItem (&labelRef, IC_LABEL (tic)->key, tic, DELETE_ITEM, NULL);
|
|
break;
|
|
case IFX:
|
|
werrorfl (tic->filename, tic->lineno, W_CODE_UNREACH);
|
|
if (IC_TRUE (tic))
|
|
hTabDeleteItem (&labelRef, IC_TRUE (tic)->key, tic, DELETE_ITEM, NULL);
|
|
else
|
|
hTabDeleteItem (&labelRef, IC_FALSE (tic)->key, tic, DELETE_ITEM, NULL);
|
|
break;
|
|
default:
|
|
werrorfl (tic->filename, tic->lineno, W_CODE_UNREACH);
|
|
}
|
|
}
|
|
|
|
/* now set up the pointers */
|
|
loop->next = loop2;
|
|
if (loop2)
|
|
loop2->prev = loop;
|
|
change++;
|
|
}
|
|
}
|
|
return change;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* iCodeLabelOptimize - some obvious & general optimizations */
|
|
/*-----------------------------------------------------------------*/
|
|
iCode *
|
|
iCodeLabelOptimize (iCode * ic)
|
|
{
|
|
if (!optimize.label1 &&
|
|
!optimize.label2 &&
|
|
!optimize.label3 &&
|
|
!optimize.label4)
|
|
return ic;
|
|
|
|
/* build labelreferences */
|
|
buildLabelRefTable (ic);
|
|
|
|
/* the following transformations need to ne done */
|
|
/* repeatedly till a fixed point is reached */
|
|
while (1)
|
|
{
|
|
int change;
|
|
change = 0;
|
|
|
|
/* first eliminate any goto statement */
|
|
/* that goes to the next statement */
|
|
if (optimize.label1)
|
|
change += labelGotoNext (ic);
|
|
|
|
if (optimize.label2)
|
|
change += labelIfx (ic);
|
|
|
|
/* target of a goto is a goto then rename this goto */
|
|
if (optimize.label3)
|
|
change += labelGotoGoto (ic);
|
|
|
|
/* remove unreference labels */
|
|
if (optimize.label4)
|
|
change += labelUnrefLabel (ic);
|
|
|
|
/* remove unreachable code */
|
|
change += labelUnreach (ic);
|
|
|
|
if (!change) /* fixed point reached */
|
|
break;
|
|
}
|
|
|
|
return ic;
|
|
}
|