611 lines
17 KiB
C
611 lines
17 KiB
C
/*-------------------------------------------------------------------------
|
|
|
|
SDCClrange.c - source file for live range computations
|
|
|
|
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"
|
|
#include "limits.h"
|
|
|
|
int iCodeSeq = 0;
|
|
hTab *liveRanges = NULL;
|
|
hTab *iCodehTab = NULL;
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* sequenceiCode - creates a sequence number for the iCode & add */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
sequenceiCode (eBBlock ** ebbs, int count)
|
|
{
|
|
int i;
|
|
|
|
for (i = 0; i < count; i++)
|
|
{
|
|
|
|
iCode *ic;
|
|
ebbs[i]->fSeq = iCodeSeq + 1;
|
|
for (ic = ebbs[i]->sch; ic; ic = ic->next)
|
|
{
|
|
ic->seq = ++iCodeSeq;
|
|
ic->depth = ebbs[i]->depth;
|
|
hTabAddItem (&iCodehTab, ic->key, ic);
|
|
}
|
|
ebbs[i]->lSeq = iCodeSeq;
|
|
}
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* markVisited - will set the visited flag for the given Block */
|
|
/*-----------------------------------------------------------------*/
|
|
DEFSETFUNC (markVisited)
|
|
{
|
|
eBBlock *ebp = item;
|
|
|
|
if (ebp->visited)
|
|
return 0;
|
|
ebp->visited = 1;
|
|
applyToSet (ebp->succList, markVisited);
|
|
return 0;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* isOpAlive - checks to see if the usage in this block is the */
|
|
/* uses the same definitions as this one */
|
|
/*-----------------------------------------------------------------*/
|
|
DEFSETFUNC (isOpAlive)
|
|
{
|
|
eBBlock *ebp = item;
|
|
V_ARG (operand *, op);
|
|
V_ARG (eBBlock *, orig);
|
|
V_ARG (iCode *, ic);
|
|
|
|
if (ebp->visited)
|
|
return 0;
|
|
|
|
ebp->visited = 1;
|
|
|
|
/* if we have reached the originating block */
|
|
/* or this block has some definiton for it */
|
|
/* then check if it is used between start & */
|
|
/* this point */
|
|
if (ebp == orig ||
|
|
bitVectBitsInCommon (OP_DEFS (op), ebp->defSet))
|
|
if (usedBetweenPoints (op, ebp->sch, ic))
|
|
return 1;
|
|
else
|
|
{
|
|
applyToSet (ebp->succList, markVisited);
|
|
return 0;
|
|
}
|
|
else
|
|
/* choosing this more expensive one since
|
|
killDeadCode will take away some definitions
|
|
but there is not way right now to take away
|
|
the usage information for the corresponding
|
|
usages, this will lead to longer live ranges */
|
|
if (usedInRemaining (op, ebp->sch))
|
|
return 1;
|
|
|
|
|
|
return (applyToSet (ebp->succList, isOpAlive, op, orig, ic));
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* isLastUse - return TRUE if no usage of this operand after this */
|
|
/*-----------------------------------------------------------------*/
|
|
int
|
|
isLastUse (operand * op, eBBlock * ebp, iCode * ic,
|
|
eBBlock ** ebbs, int count)
|
|
{
|
|
int i;
|
|
|
|
/* if this is used in the remaining */
|
|
if (usedInRemaining (op, ic))
|
|
return 0;
|
|
|
|
/* if not then check any of the successor blocks use it */
|
|
for (i = 0; i < count; ebbs[i++]->visited = 0);
|
|
if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic))
|
|
return 0;
|
|
|
|
/* this is the last use */
|
|
return 1;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* unionDefsUsed - unions the defsUsed in a block */
|
|
/*-----------------------------------------------------------------*/
|
|
DEFSETFUNC (unionDefsUsed)
|
|
{
|
|
eBBlock *ebp = item;
|
|
V_ARG (bitVect **, bvp);
|
|
|
|
if (ebp->visited)
|
|
return 0;
|
|
|
|
ebp->visited = 1;
|
|
|
|
*bvp = bitVectUnion (*bvp, ebp->usesDefs);
|
|
applyToSet (ebp->succList, unionDefsUsed, bvp);
|
|
return 0;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* setFromRange - sets the from range of a given operand */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
setFromRange (operand * op, int from)
|
|
{
|
|
/* only for compiler defined temporaries */
|
|
if (!IS_ITEMP (op))
|
|
return;
|
|
|
|
hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
|
|
|
|
if (op->isaddr)
|
|
OP_SYMBOL (op)->isptr = 1;
|
|
|
|
if (!OP_LIVEFROM (op) ||
|
|
OP_LIVEFROM (op) > from)
|
|
OP_LIVEFROM (op) = from;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* setToRange - set the range to for an operand */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
setToRange (operand * op, int to, bool check)
|
|
{
|
|
/* only for compiler defined temps */
|
|
if (!IS_ITEMP (op))
|
|
return;
|
|
|
|
OP_SYMBOL (op)->key = op->key;
|
|
hTabAddItemIfNotP (&liveRanges, op->key, OP_SYMBOL (op));
|
|
|
|
if (op->isaddr)
|
|
OP_SYMBOL (op)->isptr = 1;
|
|
|
|
if (check)
|
|
if (!OP_LIVETO (op))
|
|
OP_LIVETO (op) = to;
|
|
else;
|
|
else
|
|
OP_LIVETO (op) = to;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* firstDeOf - finds the first definition in seq for op */
|
|
/*-----------------------------------------------------------------*/
|
|
static iCode *
|
|
firstDefOf (operand * op)
|
|
{
|
|
int i;
|
|
iCode *ric = NULL, *lic = NULL;
|
|
int fSeq = INT_MAX;
|
|
|
|
if (!OP_DEFS (op))
|
|
return NULL;
|
|
|
|
for (i = 0; i < OP_DEFS (op)->size; i++)
|
|
{
|
|
if (bitVectBitValue (OP_DEFS (op), i) &&
|
|
(lic = hTabItemWithKey (iCodehTab, i)) &&
|
|
lic->seq < fSeq)
|
|
{
|
|
|
|
fSeq = lic->seq;
|
|
ric = lic;
|
|
}
|
|
}
|
|
return ric;
|
|
}
|
|
/*-----------------------------------------------------------------*/
|
|
/* useDefLoopCheck - check for uses before init inside loops */
|
|
/*-----------------------------------------------------------------*/
|
|
static void
|
|
useDefLoopCheck (operand * op, iCode * ic)
|
|
{
|
|
/* this is for situations like the following
|
|
int a,b;
|
|
|
|
while (...) {
|
|
a = ... ;
|
|
...
|
|
_some_usage_of_b_;
|
|
...
|
|
b = ... ;
|
|
}
|
|
in this case the definition of 'b' will flow to the usages
|
|
but register allocator cannot handle these situations.so
|
|
will mark as spilt */
|
|
|
|
int i = 0, fdSeq;
|
|
int er = 0;
|
|
iCode *tic;
|
|
|
|
/* get the first definition */
|
|
if (!(tic = firstDefOf (op)))
|
|
return;
|
|
|
|
fdSeq = tic->seq;
|
|
/* now go thru the usages & make sure they follow
|
|
the first definition */
|
|
for (i = 0; i <= OP_USES (op)->size; i++)
|
|
{
|
|
if (bitVectBitValue (OP_USES (op), i) &&
|
|
(tic = hTabItemWithKey (iCodehTab, i)) &&
|
|
tic->seq < fdSeq)
|
|
{
|
|
er = 1;
|
|
break;
|
|
}
|
|
}
|
|
|
|
/* found a usage without definition */
|
|
if (er)
|
|
{
|
|
if (OP_SYMBOL (op)->isreqv && SPIL_LOC (op))
|
|
{
|
|
|
|
werror (W_LOCAL_NOINIT,
|
|
SPIL_LOC (op)->name,
|
|
ic->filename, ic->lineno);
|
|
}
|
|
else
|
|
{
|
|
|
|
werror (W_LOCAL_NOINIT,
|
|
OP_SYMBOL (op)->name,
|
|
ic->filename, ic->lineno);
|
|
}
|
|
OP_SYMBOL (op)->isspilt = 1;
|
|
}
|
|
}
|
|
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* operandLUse - check and set the last use for a given operand */
|
|
/*-----------------------------------------------------------------*/
|
|
operand *
|
|
operandLUse (operand * op, eBBlock ** ebbs,
|
|
int count, iCode * ic, eBBlock * ebp)
|
|
{
|
|
setFromRange (op, ic->seq);
|
|
if (ic->depth)
|
|
OP_SYMBOL (op)->used += (((unsigned int) 1 << ic->depth) + 1);
|
|
else
|
|
OP_SYMBOL (op)->used += 1;
|
|
|
|
if (isLastUse (op, ebp, ic->next, ebbs, count) ||
|
|
(OP_LIVETO (op) && OP_LIVETO (op) < ic->seq))
|
|
{
|
|
int torange = ic->seq;
|
|
/* if this is the last use then if this block belongs
|
|
to a loop & some definition comes into the loop
|
|
then extend the live range to the end of the loop */
|
|
if (ebp->partOfLoop
|
|
&& hasIncomingDefs (ebp->partOfLoop, op))
|
|
{
|
|
torange = findLoopEndSeq (ebp->partOfLoop);
|
|
}
|
|
op = operandFromOperand (op);
|
|
setToRange (op, torange, FALSE);
|
|
}
|
|
ic->uses = bitVectSetBit (ic->uses, op->key);
|
|
|
|
if (!OP_SYMBOL (op)->udChked)
|
|
{
|
|
sym_link *type = operandType (op);
|
|
sym_link *etype = getSpec (type);
|
|
|
|
OP_SYMBOL (op)->udChked = 1;
|
|
/* good place to check if unintialised */
|
|
if ((IS_TRUE_SYMOP (op) || OP_SYMBOL (op)->isreqv) &&
|
|
OP_SYMBOL (op)->islocal &&
|
|
!IS_AGGREGATE (type) &&
|
|
!IS_FUNC (type) &&
|
|
ic->op != ADDRESS_OF &&
|
|
!IS_STATIC (etype))
|
|
{
|
|
|
|
if (bitVectIsZero (op->usesDefs))
|
|
{
|
|
OP_SYMBOL (op)->isspilt = 1;
|
|
|
|
if (OP_SYMBOL (op)->isreqv &&
|
|
!OP_SYMBOL (op)->_isparm && SPIL_LOC (op))
|
|
{
|
|
|
|
werror (W_LOCAL_NOINIT,
|
|
SPIL_LOC (op)->name,
|
|
ic->filename, ic->lineno);
|
|
}
|
|
else
|
|
{
|
|
|
|
werror (W_LOCAL_NOINIT,
|
|
OP_SYMBOL (op)->name,
|
|
ic->filename, ic->lineno);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (ebp->depth && op->usesDefs &&
|
|
!OP_SYMBOL (op)->_isparm)
|
|
{
|
|
/* check non-inits inside loops */
|
|
useDefLoopCheck (op, ic);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return op;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* killAllAlive - mark all the definitions living with this seq */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
killAllAlive (int seq)
|
|
{
|
|
symbol *sym;
|
|
int k;
|
|
|
|
for (sym = hTabFirstItem (liveRanges, &k); sym;
|
|
sym = hTabNextItem (liveRanges, &k))
|
|
if (!sym->liveTo || (sym->liveTo < sym->liveFrom))
|
|
sym->liveTo = seq;
|
|
}
|
|
/*-----------------------------------------------------------------*/
|
|
/* defUsedAfterLoop - all definitions & usages before sequence num */
|
|
/*-----------------------------------------------------------------*/
|
|
bool
|
|
defUsedAfterLoop (operand * op, int seq)
|
|
{
|
|
int i;
|
|
iCode *ic;
|
|
|
|
/* check for the usages first */
|
|
if (OP_SYMBOL (op)->uses && !bitVectIsZero (OP_SYMBOL (op)->uses))
|
|
{
|
|
for (i = 0; i < OP_SYMBOL (op)->uses->size; i++)
|
|
{
|
|
|
|
if (bitVectBitValue (OP_SYMBOL (op)->uses, i) && /* usage found */
|
|
(ic = hTabItemWithKey (iCodehTab, i)) && /* "" */
|
|
ic->seq > seq) /* & is after the seq */
|
|
return TRUE;
|
|
}
|
|
}
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* markLiveRanges - for each operand mark the liveFrom & liveTo */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
markLiveRanges (eBBlock * ebp, eBBlock ** ebbs, int count)
|
|
{
|
|
iCode *ic;
|
|
bitVect *defsUsed = NULL;
|
|
bitVect *defsNotUsed = NULL;
|
|
int i;
|
|
/* for all the instructions */
|
|
for (ic = ebp->sch; ic; ic = ic->next)
|
|
{
|
|
|
|
if (ic->op == CALL || ic->op == PCALL)
|
|
{
|
|
setFromRange (IC_RESULT (ic), ic->seq);
|
|
/* if the result has no usage then
|
|
mark this as the end of its life too
|
|
and take it away from the defs for the block */
|
|
if (bitVectIsZero (OP_SYMBOL (IC_RESULT (ic))->uses))
|
|
{
|
|
setToRange (IC_RESULT (ic), ic->seq, FALSE);
|
|
bitVectUnSetBit (ebp->defSet, ic->key);
|
|
}
|
|
}
|
|
|
|
if (SKIP_IC2 (ic))
|
|
continue;
|
|
|
|
/* take care of the special icodes first */
|
|
if (ic->op == JUMPTABLE && IS_SYMOP (IC_JTCOND (ic)))
|
|
{
|
|
operandLUse (IC_JTCOND (ic), ebbs, count, ic, ebp);
|
|
continue;
|
|
}
|
|
|
|
if (ic->op == IFX && IS_SYMOP (IC_COND (ic)))
|
|
{
|
|
operandLUse (IC_COND (ic), ebbs, count, ic, ebp);
|
|
continue;
|
|
}
|
|
|
|
if (IS_SYMOP (IC_LEFT (ic)))
|
|
operandLUse (IC_LEFT (ic), ebbs, count, ic, ebp);
|
|
|
|
if (IS_SYMOP (IC_RIGHT (ic)))
|
|
operandLUse (IC_RIGHT (ic), ebbs, count, ic, ebp);
|
|
|
|
if (POINTER_SET (ic))
|
|
operandLUse (IC_RESULT (ic), ebbs, count, ic, ebp);
|
|
else if (IC_RESULT (ic))
|
|
ic->defKey = IC_RESULT (ic)->key;
|
|
}
|
|
|
|
|
|
/* for all the definitions in the block */
|
|
/* compute and set the live from */
|
|
if (ebp->ldefs && !bitVectIsZero (ebp->ldefs))
|
|
{
|
|
for (i = 0; i < ebp->ldefs->size; i++)
|
|
{
|
|
iCode *dic;
|
|
|
|
if (bitVectBitValue (ebp->ldefs, i) &&
|
|
(dic = hTabItemWithKey (iCodehTab, i)))
|
|
{
|
|
|
|
/* if the definition has a from & it is greater */
|
|
/* than the defininng iCode->seq then change it */
|
|
setFromRange (IC_RESULT (dic), dic->seq);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* special case for lastBlock in a loop: here we
|
|
mark the end of all the induction variables for the
|
|
loop */
|
|
if (ebp->isLastInLoop && !bitVectIsZero (ebp->linds))
|
|
{
|
|
for (i = 0; i <= ebp->linds->size; i++)
|
|
{
|
|
iCode *dic;
|
|
|
|
if (bitVectBitValue (ebp->linds, i) &&
|
|
(dic = hTabItemWithKey (iCodehTab, i)))
|
|
{
|
|
|
|
/* if this is a register equvalent make sure
|
|
it is not defined or used anywhere after the loop */
|
|
if (OP_SYMBOL (IC_RESULT (dic))->isreqv &&
|
|
defUsedAfterLoop (IC_RESULT (dic), ebp->lSeq))
|
|
continue;
|
|
|
|
setToRange (IC_RESULT (dic), (ebp->lSeq), FALSE);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* for defnitions coming into the block if they */
|
|
/* not used by itself & any of its successors */
|
|
/* they are dead */
|
|
/* first union the definitions used in all successors
|
|
and itself */
|
|
for (i = 0; i < count; ebbs[i++]->visited = 0);
|
|
applyToSet (ebp->succList, unionDefsUsed, &defsUsed);
|
|
defsUsed = bitVectUnion (defsUsed, ebp->usesDefs);
|
|
|
|
/* now subract the result of these unions from */
|
|
/* the incoming definitions this will give the */
|
|
/* definitions that are never used in the future */
|
|
defsNotUsed = bitVectCplAnd (bitVectCopy (ebp->inDefs),
|
|
defsUsed);
|
|
|
|
/* mark the end of the defintions */
|
|
if (!bitVectIsZero (defsNotUsed) && ebp->sch)
|
|
{
|
|
for (i = 0; i < defsNotUsed->size; i++)
|
|
{
|
|
iCode *dic;
|
|
|
|
if (bitVectBitValue (defsNotUsed, i) &&
|
|
(dic = hTabItemWithKey (iCodehTab, i)))
|
|
{
|
|
|
|
setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/* if we reach a lock with noPath to it then kill all
|
|
the live ranges alive at this point */
|
|
/* if (ebp->noPath || ebp->entryLabel == returnLabel) */
|
|
if (ebp->entryLabel == returnLabel)
|
|
killAllAlive (ebp->fSeq);
|
|
}
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* rlivePoint - for each point compute the ranges that are alive */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
rlivePoint (eBBlock ** ebbs, int count)
|
|
{
|
|
int i;
|
|
|
|
/* for all blocks do */
|
|
for (i = 0; i < count; i++) {
|
|
iCode *ic;
|
|
|
|
/* for all instruction in the block do */
|
|
for (ic = ebbs[i]->sch; ic; ic = ic->next) {
|
|
symbol *lrange;
|
|
int k;
|
|
|
|
ic->rlive = newBitVect (operandKey);
|
|
/* for all symbols in the liverange table */
|
|
for (lrange = hTabFirstItem (liveRanges, &k); lrange;
|
|
lrange = hTabNextItem (liveRanges, &k)) {
|
|
|
|
/* if it is live then add the lrange to ic->rlive */
|
|
if (lrange->liveFrom <= ic->seq &&
|
|
lrange->liveTo >= ic->seq) {
|
|
lrange->isLiveFcall |= (ic->op == CALL || ic->op == PCALL || ic->op == SEND);
|
|
ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
|
|
}
|
|
}
|
|
/* overlapping live ranges should be eliminated */
|
|
if (ASSIGN_ITEMP_TO_ITEMP (ic)) {
|
|
|
|
if (SPIL_LOC(IC_RIGHT(ic)) == SPIL_LOC(IC_RESULT(ic)) && /* left & right share the same spil location */
|
|
OP_SYMBOL(IC_RESULT(ic))->isreqv && /* left of assign is a register requivalent */
|
|
!OP_SYMBOL(IC_RIGHT(ic))->isreqv && /* right side is not */
|
|
OP_SYMBOL(IC_RIGHT(ic))->liveTo > ic->key && /* right side live beyond this point */
|
|
bitVectnBitsOn(OP_DEFS(IC_RESULT(ic))) > 1 ) { /* left has multiple definitions */
|
|
SPIL_LOC(IC_RIGHT(ic)) = NULL; /* then cannot share */
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/*-----------------------------------------------------------------*/
|
|
/* computeLiveRanges - computes the live ranges for variables */
|
|
/*-----------------------------------------------------------------*/
|
|
void
|
|
computeLiveRanges (eBBlock ** ebbs, int count)
|
|
{
|
|
int i = 0;
|
|
/* sequence the code the live ranges are computed
|
|
in terms of this sequence additionally the
|
|
routine will also create a hashtable of instructions */
|
|
iCodeSeq = 0;
|
|
setToNull ((void **) &iCodehTab);
|
|
iCodehTab = newHashTable (iCodeKey);
|
|
sequenceiCode (ebbs, count);
|
|
|
|
/* call routine to mark the from & to live ranges for
|
|
variables used */
|
|
setToNull ((void **) &liveRanges);
|
|
for (i = 0; i < count; i++)
|
|
markLiveRanges (ebbs[i], ebbs, count);
|
|
|
|
/* mark the ranges live for each point */
|
|
rlivePoint (ebbs, count);
|
|
}
|