int iCodeSeq = 0;
hTab *liveRanges = NULL;
hTab *iCodehTab = NULL;
+hTab *iCodeSeqhTab = NULL;
/*-----------------------------------------------------------------*/
/* sequenceiCode - creates a sequence number for the iCode & add */
ic->seq = ++iCodeSeq;
ic->depth = ebbs[i]->depth;
hTabAddItem (&iCodehTab, ic->key, ic);
+ hTabAddItem (&iCodeSeqhTab, ic->seq, ic);
}
ebbs[i]->lSeq = iCodeSeq;
}
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;
+ if (getenv ("SDCC_LRKLAUS"))
+ {
+ /* if not then check any of the following blocks use it */
+ for (i = 0; i < count; i++)
+ {
+ if (ebbs[i]->fSeq <= ebp->fSeq)
+ continue;
+ if (usedInRemaining (op, ebbs[i]->sch))
+ return 0;
+ }
+ }
+ else
+ {
+ /* 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;
OP_SYMBOL (op)->name,
ic->filename, ic->lineno);
}
+#if 0 // this will create a segfault: bug #498971
OP_SYMBOL (op)->isspilt = 1;
+#endif
}
}
(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
+
+ /* if this is a SEND then the toRange should be extended
+ to the call */
+ if (ic->op == SEND)
+ {
+ iCode *lic ;
+ for (lic = ic->next ; lic ; lic = lic->next)
+ {
+ if (lic->op == CALL || lic->op == PCALL)
+ break;
+ }
+ /* found it : mark */
+ if (lic)
+ torange = lic->prev->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);
+ if (getenv ("SDCC_LRKLAUS"))
+ {
+ if (ebp->KpartOfLoop)
+ {
+ region *aloop;
+
+ aloop = setFirstItem (ebp->KpartOfLoop);
+ for (; aloop; aloop = setNextItem (ebp->KpartOfLoop))
+ {
+ if (hasIncomingDefs (aloop, op))
+ torange = findLoopEndSeq (aloop);
+ }
+ }
}
+ else
+ {
+ if (ebp->partOfLoop
+ && hasIncomingDefs (ebp->partOfLoop, op))
+ {
+ torange = findLoopEndSeq (ebp->partOfLoop);
+ }
+ }
+
op = operandFromOperand (op);
setToRange (op, torange, FALSE);
}
!IS_STATIC (etype))
{
- if (bitVectIsZero (op->usesDefs))
+ if (bitVectIsZero (op->usesDefs) && OP_SYMBOL(op)->ival==NULL)
{
OP_SYMBOL (op)->isspilt = 1;
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 (bitVectBitValue (defsNotUsed, i) &&
(dic = hTabItemWithKey (iCodehTab, i)))
{
-
setToRange (IC_RESULT (dic), (ebp->fSeq - 1), TRUE);
}
}
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 */
- }
- }
+ 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 |= ((lrange->liveFrom < ic->seq) &&
+ (ic->op == CALL || ic->op == PCALL || ic->op == SEND));
+ if (ic->op == CALL && lrange->liveFrom == ic->seq) continue;
+ ic->rlive = bitVectSetBit (ic->rlive, lrange->key);
+ }
+ }
+#if 0
+ /* 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 */
}
+ }
+#endif
+ }
+ }
+}
+
+/*-----------------------------------------------------------------*/
+/* computeClash - find out which live ranges collide with others */
+/*-----------------------------------------------------------------*/
+static void computeClash ()
+{
+ hTab *lRangeCopy = newHashTable(hTabMaxKey(liveRanges));
+ void *item;
+ symbol *outer, *inner;
+ int key, key1;
+
+ /* have to make a copy of the liveRanges hashTable :: UGHH .*/
+ for (item = hTabFirstItem(liveRanges,&key); item ;
+ item = hTabNextItem(liveRanges,&key)) {
+ hTabAddItem(&lRangeCopy,key,item);
+ }
+
+ /* outerloop : for each liverange do */
+ for (outer = hTabFirstItem(liveRanges,&key); outer ;
+ outer = hTabNextItem(liveRanges,&key)) {
+
+ /* if the liveFrom & To are the same then skip,
+ could happen for unused return values from functions */
+ if (outer->liveFrom == outer->liveTo) continue;
+
+ /* innerloop : for the inner loop we can start from the
+ item after the outer loop */
+ inner = hTabFirstItemWK (lRangeCopy,outer->key);
+ inner = hTabNextItem (lRangeCopy,&key1 );
+ for (; inner ; inner = hTabNextItem( lRangeCopy ,&key1)) {
+
+ if (inner->liveFrom == inner->liveTo) continue;
+ if (inner->liveTo < outer->liveFrom) continue;
+ if (inner->liveFrom > outer->liveTo) continue;
+
+ /* if one of them are being defined where the other
+ one end , then no overlap (i.e. they can goto same registers */
+ if (inner->liveFrom == outer->liveTo ||
+ outer->liveFrom == inner->liveTo) continue;
+
+ /* so they overlap : set both their clashes */
+ inner->clashes = bitVectSetBit(inner->clashes,outer->key);
+ outer->clashes = bitVectSetBit(outer->clashes,inner->key);
+
+ /* check if they share the same spillocation */
+ if (SYM_SPIL_LOC(inner) && SYM_SPIL_LOC(outer) &&
+ SYM_SPIL_LOC(inner) == SYM_SPIL_LOC(outer)) {
+ if (inner->reqv && !outer->reqv) SYM_SPIL_LOC(outer)=NULL;
+ else if (outer->reqv && !inner->reqv) SYM_SPIL_LOC(inner)=NULL;
+ else if (inner->used > outer->used) SYM_SPIL_LOC(outer)=NULL;
+ else SYM_SPIL_LOC(inner)=NULL;
+ }
+
}
+ }
+}
+
+/*-----------------------------------------------------------------*/
+/* allDefsOutOfRange - all definitions are out of a range */
+/*-----------------------------------------------------------------*/
+bool
+allDefsOutOfRange (bitVect * defs, int fseq, int toseq)
+{
+ int i;
+
+ if (!defs)
+ return TRUE;
+
+ for (i = 0; i < defs->size; i++)
+ {
+ iCode *ic;
+
+ if (bitVectBitValue (defs, i) &&
+ (ic = hTabItemWithKey (iCodehTab, i)) &&
+ (ic->seq >= fseq && ic->seq <= toseq))
+
+ return FALSE;
+
+ }
+
+ return TRUE;
+}
+
+/*-----------------------------------------------------------------*/
+/* notUsedInBlock - not used in this block */
+/*-----------------------------------------------------------------*/
+int
+notUsedInBlock (symbol * sym, eBBlock * ebp, iCode *ic)
+{
+ return (!bitVectBitsInCommon (sym->defs, ebp->usesDefs) &&
+ allDefsOutOfRange (sym->defs, ebp->fSeq, ebp->lSeq) &&
+ allDefsOutOfRange (sym->uses, ebp->fSeq, ebp->lSeq));
}
/*-----------------------------------------------------------------*/
/* computeLiveRanges - computes the live ranges for variables */
/*-----------------------------------------------------------------*/
-void
+void
computeLiveRanges (eBBlock ** ebbs, int count)
{
int i = 0;
- /* sequence the code the live ranges are computed
- in terms of this sequence additionally the
+ /* 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);
+ setToNull ((void *) &iCodehTab);
iCodehTab = newHashTable (iCodeKey);
+ setToNull ((void *) &iCodeSeqhTab);
+ iCodeSeqhTab = newHashTable (iCodeKey);
sequenceiCode (ebbs, count);
+ if (getenv ("SDCC_LRKLAUS"))
+ {
+ /* add blocks between loop blocks as part of that loop */
+ addLoopBlocks (ebbs, count);
+ }
+
/* call routine to mark the from & to live ranges for
variables used */
- setToNull ((void **) &liveRanges);
+ setToNull ((void *) &liveRanges);
for (i = 0; i < count; i++)
markLiveRanges (ebbs[i], ebbs, count);
/* mark the ranges live for each point */
rlivePoint (ebbs, count);
+
+ /* compute which overlaps with what */
+ computeClash();
}
+