-//#define LIVERANGEHUNT
-#ifdef LIVERANGEHUNT
- #define LRH(x) x
-#else
- #define LRH(x)
-#endif
/*-------------------------------------------------------------------------
SDCCloop.c - source file for loop detection & optimizations
ip->op = op;
ip->cval = constVal;
ip->ic = ic;
- updateSpillLocation(ic,1);
+//updateSpillLocation(ic,1);
return ip;
}
/*-----------------------------------------------------------------*/
/* loopInsert will insert a block into the loop set */
/*-----------------------------------------------------------------*/
-static void
+static void
loopInsert (set ** regionSet, eBBlock * block)
{
if (!isinSet (*regionSet, block))
{
- LRH(printf ("loopInsert: %s\n", block->entryLabel->name));
addSetHead (regionSet, block);
STACK_PUSH (regionStack, block);
}
/* hasIncomingDefs - has definitions coming into the loop. i.e. */
/* check to see if the preheaders outDefs has any definitions */
/*-----------------------------------------------------------------*/
-int
+int
hasIncomingDefs (region * lreg, operand * op)
{
eBBlock *preHdr = lreg->entry->preHeader;
/* findLoopEndSeq - will return the sequence number of the last */
/* iCode with the maximum dfNumber in the region */
/*-----------------------------------------------------------------*/
-int
+int
findLoopEndSeq (region * lreg)
{
eBBlock *block;
V_ARG (set **, exits);
V_ARG (int, depth);
V_ARG (region *, lr);
- LRH(printf ("addToExitsMarkDepth: %s %d\n", ebp->entryLabel->name, depth));
+
/* mark the loop depth of this block */
//if (!ebp->depth)
if (ebp->depth<depth)
ebp->depth = depth;
- /* put the loop region info in the block */
/* NOTE: here we will update only the inner most loop
that it is a part of */
if (!ebp->partOfLoop)
{
edge *ep = item;
V_ARG (set **, allRegion);
- V_ARG (eBBlock **,ebbs);
- V_ARG (int,count);
region *aloop = newRegion ();
eBBlock *block;
- int dfMin = count ,dfMax =0, i;
- LRH(printf("CreateLoop\n"));
/* make sure regionStack is empty */
while (!STACK_EMPTY (regionStack))
STACK_POP (regionStack);
/* add the entryBlock */
addSet (&aloop->regBlocks, ep->to);
-#ifdef LIVERANGEHUNT
- // print regBlocks jwk
- {
- eBBlock *ebp;
- region *lp=aloop;
- for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
- printf ("cl1 %s ", ebp->entryLabel->name);
- }
- printf (" %d\n", count);
- }
-#endif
loopInsert (&aloop->regBlocks, ep->from);
-#ifdef LIVERANGEHUNT
- // print regBlocks jwk
- {
- eBBlock *ebp;
- region *lp=aloop;
- for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
- printf ("cl2 %s ", ebp->entryLabel->name);
- }
- printf (" %d\n", count);
- }
-#endif
while (!STACK_EMPTY (regionStack))
{
applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
}
-#ifdef LIVERANGEHUNT
- // print regBlocks jwk
- {
- eBBlock *ebp;
- region *lp=aloop;
- for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
- printf ("cl3 %s ", ebp->entryLabel->name);
- }
- printf (" %d\n", count);
- }
-#endif
-
aloop->entry = ep->to;
- /* set max & min dfNum for loopRegion */
- for ( block = setFirstItem(aloop->regBlocks); block;
- block = setNextItem(aloop->regBlocks)) {
- if (block->dfnum > dfMax) dfMax = block->dfnum;
- if (block->dfnum < dfMin) dfMin = block->dfnum;
- }
-
- /* all blocks that have dfnumbers between dfMin & dfMax are also
- part of loop */
- for (i = 0 ; i < count ; i++) {
- if (ebbs[i]->dfnum > dfMin &&
- ebbs[i]->dfnum < dfMax &&
- !isinSet(aloop->regBlocks,ebbs[i])) {
- if (!ebbs[i]->partOfLoop) {
-#if !defined(LIVERANGEHUNT)
- ebbs[i]->partOfLoop = aloop;
-#else
- loopInsert(&aloop->regBlocks,ebbs[i]);
-#endif
- }
- }
- }
-
-#ifdef LIVERANGEHUNT
- printf ("================\n");
- printf (" loop with entry -- > ");
- printEntryLabel (aloop->entry, ap);
- printf ("\n");
- printf (" loop body --> ");
- applyToSet (aloop->regBlocks, printEntryLabel);
- printf ("\n");
- printf (" loop exits --> ");
- applyToSet (aloop->exits, printEntryLabel);
- printf ("\n");
-#endif
-
- /* and if this is a conditional block, the other side of the IFX
- (if any, that could have a greater dfnum) is too */
- {
- // just a burp, but I'm getting close :)
- }
-
/* now add it to the set */
addSetHead (allRegion, aloop);
{
eBBlock *ebp = item;
V_ARG (cseDef *, cdp);
- V_ARG (eBBlock **, ebbs);
- V_ARG (int, count);
+ V_ARG (ebbIndex *, ebbi);
addSetHead (&ebp->inExprs, cdp);
- cseBBlock (ebp, 0, ebbs, count);
+ cseBBlock (ebp, optimize.global_cse, ebbi);
return 0;
}
/*-----------------------------------------------------------------*/
/* assignmentsToSym - for a set of blocks determine # time assigned */
/*-----------------------------------------------------------------*/
-int
+int
assignmentsToSym (set * sset, operand * sym)
{
eBBlock *ebp;
in this block */
bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
assigns += bitVectnBitsOn (defs);
- setToNull ((void **) &defs);
+ setToNull ((void *) &defs);
}
/*-----------------------------------------------------------------*/
/* isOperandInvariant - determines if an operand is an invariant */
/*-----------------------------------------------------------------*/
-int
+int
isOperandInvariant (operand * op, region * theLoop, set * lInvars)
{
int opin = 0;
!IS_OP_VOLATILE (op) &&
assignmentsToSym (theLoop->regBlocks, op) == 0)
opin = 1;
- LRH(if (opin && IS_SYMOP(op)) {
- printf("isOperandInvariant: %s\n", OP_SYMBOL(op)->name);
- });
}
else
opin++;
eBBlock *ebp = item;
V_ARG (operand *, op);
- return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
+ if (ebp->hasFcall)
+ return 1;
+
+ if (bitVectBitValue (ebp->ptrsSet, op->key))
+ return 1;
+
+ /* Unfortunately, one of the other pointer set operations */
+ /* may be using an alias of this operand, and the above */
+ /* test would miss it. To be thorough, some aliasing */
+ /* analysis should be done here. In the meantime, be */
+ /* conservative and assume any other pointer set operation */
+ /* is dangerous */
+ if (!bitVectIsZero (ebp->ptrsSet))
+ return 1;
+
+ return 0;
}
/*-----------------------------------------------------------------*/
/*-----------------------------------------------------------------*/
/* loopInvariants - takes loop invariants out of region */
/*-----------------------------------------------------------------*/
-int
-loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
+int
+loopInvariants (region * theLoop, ebbIndex * ebbi)
{
+ eBBlock ** ebbs = ebbi->dfOrder;
+ int count = ebbi->count;
eBBlock *lBlock;
set *lInvars = NULL;
theLoop->exits == NULL)
return 0;
- /* we will do the elimination for those blocks */
- /* in the loop that dominates all exits from the loop */
+ /* we will do the elimination for those blocks */
+ /* in the loop that dominate all exits from the loop */
for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
lBlock = setNextItem (theLoop->regBlocks))
{
int lin, rin;
cseDef *ivar;
- /* jwk: TODO this is only needed if the call is between
+ /* TODO this is only needed if the call is between
here and the definition, but I am too lazy to do that now */
/* if there are function calls in this block */
if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
continue;
+ /* iTemp assignment from a literal may be invariant, but it
+ will needlessly increase register pressure if the
+ iCode(s) that use this iTemp are not also invariant */
+ if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
+ && IS_OP_LITERAL (IC_RIGHT (ic)))
+ continue;
+
/* if result is volatile then skip */
if (IC_RESULT (ic) &&
(isOperandVolatile (IC_RESULT (ic), TRUE) ||
continue;
lin = rin = 0;
-
+
/* special case */
/* if address of then it is an invariant */
if (ic->op == ADDRESS_OF &&
that the pointer set does not exist in
any of the blocks */
if (POINTER_GET (ic) &&
- (applyToSet (theLoop->regBlocks,
+ (applyToSet (theLoop->regBlocks,
pointerAssigned, IC_LEFT (ic))))
lin = 0;
}
-
+
/* do the same for right */
rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
-
+
/* if this is a POINTER_GET then special case, make sure all
usages within the loop are POINTER_GET any other usage
would mean that this is not an invariant , since the pointer
applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
continue;
- /* if both the left & right are invariants : then check that */
- /* this definition exists in the out definition of all the */
- /* blocks, this will ensure that this is not assigned any */
- /* other value in the loop , and not used in this block */
+
+ /* if both the left & right are invariants : then check that */
+ /* this definition exists in the out definition of all the */
+ /* blocks, this will ensure that this is not assigned any */
+ /* other value in the loop, and not used in this block */
/* prior to this definition which means only this definition */
- /* is used in this loop */
+ /* is used in this loop */
if (lin && rin && IC_RESULT (ic))
{
eBBlock *sBlock;
set *lSet = setFromSet (theLoop->regBlocks);
- /* if this block does not dominate all exists */
+ /* if this block does not dominate all exits */
/* make sure this defintion is not used anywhere else */
if (!domsAllExits)
{
for (sBlock = setFirstItem (lSet); sBlock;
sBlock = setNextItem (lSet))
{
+ iCode *ic2;
+ int used;
+ int defDominates;
+
/* if this is the block make sure the definition */
/* reaches the end of the block */
if (sBlock == lBlock)
}
else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
break;
+
+ /* Check that this definition is not assigned */
+ /* any other value in this block. Also check */
+ /* that any usage in the block is dominated by */
+ /* by this definition. */
+ defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
+ used = 0;
+ for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
+ {
+ if (ic2->op == IFX)
+ {
+ if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
+ used = 1;
+ }
+ else if (ic2->op == JUMPTABLE)
+ {
+ if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
+ used = 1;
+ }
+ else
+ {
+ if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
+ used = 1;
+ if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
+ used = 1;
+ if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
+ break;
+ /* If used before this definition, might not be invariant */
+ if ((ic == ic2) && used)
+ break;
+ }
+ if (used && !defDominates)
+ break;
+ }
+ if (ic2) /* found another definition or a usage before the definition */
+ break;
}
if (sBlock)
continue; /* another definition present in the block */
+
- /* now check if it exists in the in of this block */
+ /* now check if it exists in the in of this block */
/* if not then it was killed before this instruction */
if (!bitVectBitValue (lBlock->inDefs, ic->key))
continue;
/* now we know it is a true invariant */
/* remove it from the insts chain & put */
/* in the invariant set */
- OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
+
+ OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
+ SPIL_LOC (IC_RESULT (ic)) = NULL;
remiCodeFromeBBlock (lBlock, ic);
/* maintain the data flow */
bitVectUnSetBit (lBlock->defSet, ic->key);
bitVectUnSetBit (lBlock->ldefs, ic->key);
ivar = newCseDef (IC_RESULT (ic), ic);
- applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
+ applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
addSet (&lInvars, ivar);
}
}
/*-----------------------------------------------------------------*/
/* addressTaken - returns true if the symbol is found in the addrof */
/*-----------------------------------------------------------------*/
-int
+int
addressTaken (set * sset, operand * sym)
{
set *loop;
{
operand *aSym;
- unsigned long litValue;
+ long litValue;
induction *ip;
iCode *indIc;
eBBlock *owner = NULL;
int nexits;
-
- /* look for assignments of the form */
+ sym_link *optype;
+
+ /* To find an induction variable, we need to */
+ /* find within the loop three iCodes in this */
+ /* general form: */
+ /* */
+ /* ddic: iTempB := symbolVar */
+ /* dic: iTempA := iTempB + lit */
+ /* or iTempA := iTempB - lit */
+ /* or iTempA := lit + iTempB */
+ /* ic: symbolVar := iTempA */
+ /* */
+ /* (symbolVar may also be an iTemp if it is */
+ /* register equivalent) */
+
+ /* look for assignments of the form */
/* symbolVar := iTempNN */
if (ic->op != '=')
continue;
if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
continue;
+ /* Only consider variables with integral type. */
+ /* (2004/12/06 - EEP - ds390 fails regression tests unless */
+ /* pointers are also considered for induction (due to some */
+ /* register alloctaion bugs). Remove !IS_PTR clause when */
+ /* that gets fixed) */
+ optype = operandType (IC_RIGHT (ic));
+ if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
+ continue;
+
/* find the definition for the result in the block */
if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
IC_RIGHT (ic), &owner)))
/* if not +/- continue */
if (dic->op != '+' && dic->op != '-')
continue;
-
+
/* make sure definition is of the form a +/- c */
if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
continue;
+
+ /* make sure the definition found is the only one */
+ if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
+ continue;
- aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
- (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
- (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
+ if (IS_OP_LITERAL (IC_RIGHT (dic)))
+ {
+ aSym = IC_LEFT (dic);
+ litValue = (long) operandLitValue (IC_RIGHT (dic));
+ }
+ else
+ {
+ /* For minus, the literal must not be on the left side. */
+ /* (Actually, this case could be handled, but it's probably */
+ /* not worth the extra code) */
+ if (dic->op == '-')
+ continue;
+ aSym = IC_RIGHT (dic);
+ litValue = (long) operandLitValue (IC_LEFT (dic));
+ }
if (!isOperandEqual (IC_RESULT (ic), aSym) &&
!isOperandEqual (IC_RIGHT (ic), aSym))
if (nexits == 1)
{
eBBlock *exit = setFirstItem (loopReg->exits);
-
/* if it is the same block then there is no
need to move it about */
if (exit != lBlock)
if (bitVectBitValue (loopSuccs, i))
{
- eBBlock *eblock = ebbs[i];
+ eBBlock *eblock = NULL;
+ int j;
+
+ /* Need to search for bbnum == i since ebbs is */
+ /* sorted by dfnum; a direct index won't do. */
+ for (j=0; j<count; j++)
+ if (ebbs[j]->bbnum == i)
+ {
+ eblock = ebbs[j];
+ break;
+ }
+ assert(eblock);
/* if the successor does not belong to the loop
and will be executed after the loop : then
/*-----------------------------------------------------------------*/
/* loopInduction - remove induction variables from a loop */
/*-----------------------------------------------------------------*/
-int
-loopInduction (region * loopReg, eBBlock ** ebbs, int count)
+int
+loopInduction (region * loopReg, ebbIndex * ebbi)
{
+ eBBlock ** ebbs = ebbi->dfOrder;
+ int count = ebbi->count;
int change = 0;
- eBBlock *lBlock, *lastBlock = NULL;
+ eBBlock *lBlock, *owner, *lastBlock = NULL;
set *indVars = NULL;
set *basicInd = NULL;
lBlock = setNextItem (loopReg->regBlocks))
{
- iCode *ic, *indIc;
+ iCode *ic, *indIc, *dic;
induction *ip;
/* last block is the one with the highest block
for (ic = lBlock->sch; ic; ic = ic->next)
{
operand *aSym;
- unsigned long litVal;
- int lr = 0;
+ long litVal;
/* consider only * & / */
if (ic->op != '*' && ic->op != '/')
continue;
- /* if the result has more definitions then */
+ /* only consider variables with integral type */
+ if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
+ continue;
+
+ /* if the result has more definitions then */
if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
continue;
(IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
continue;
- aSym = (IS_SYMOP (IC_LEFT (ic)) ?
- (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
- (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
+ if (IS_SYMOP (IC_LEFT (ic)))
+ {
+ aSym = IC_LEFT (ic);
+ litVal = (long) operandLitValue (IC_RIGHT (ic));
+ }
+ else
+ {
+ /* For division, the literal must not be on the left side */
+ if (ic->op == '/')
+ continue;
+ aSym = IC_RIGHT (ic);
+ litVal = (long) operandLitValue (IC_LEFT (ic));
+ }
ip = NULL;
/* check if this is an induction variable */
addSet (&indVars,
newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
- /* now change this instruction */
- ic->op = ip->op;
- if (lr)
- {
- IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
- IC_RIGHT (ic) = operandFromLit (litVal);
- }
- else
- {
- IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
- IC_LEFT (ic) = operandFromLit (litVal);
- }
-
- /* we need somemore initialisation code */
- /* we subtract the litVal from itself if increment */
- if (ic->op == '+')
- {
- indIc = newiCode ('-',
- operandFromOperand (IC_RESULT (ic)),
- operandFromLit (litVal));
- indIc->lineno = ic->lineno;
- IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
-
- addSet (&indVars,
- newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
- }
+ /* Replace mul/div with assignment to self; killDeadCode() will */
+ /* clean this up since we can't use remiCodeFromeBBlock() here. */
+ ic->op = '=';
+ IC_LEFT (ic) = NULL;
+ IC_RIGHT (ic) = IC_RESULT (ic);
+
+ /* Insert an update of the induction variable just before */
+ /* the update of the basic induction variable. */
+ indIc = newiCode (ip->op,
+ operandFromOperand (IC_RESULT (ic)),
+ operandFromLit (litVal));
+ IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
+ owner = NULL;
+ dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
+ assert (dic);
+ addiCodeToeBBlock (owner, indIc, dic);
+
}
}
lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
}
- setToNull ((void **) &indVars);
+ setToNull ((void *) &indVars);
return change;
}
if (lp->entry == theLoop->entry)
{
theLoop->regBlocks = unionSets (theLoop->regBlocks,
- lp->regBlocks, THROW_BOTH);
+ lp->regBlocks, THROW_DEST);
lp->merged = 1;
}
}
/* createLoopRegions - will detect and create a set of natural loops */
/*-----------------------------------------------------------------*/
hTab *
-createLoopRegions (eBBlock ** ebbs, int count)
+createLoopRegions (ebbIndex * ebbi)
{
set *allRegion = NULL; /* set of all loops */
hTab *orderedLoops = NULL;
int maxDepth = 0;
region *lp;
- LRH(printf ("createLoopRegions: %p\n", ebbs));
/* get all the back edges in the graph */
if (!applyToSet (graphEdges, backEdges, &bEdges))
return 0; /* found no loops */
/* for each of these back edges get the blocks that */
/* constitute the loops */
- applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
-#ifdef LIVERANGEHUNT
- // print regBlocks
- {
- eBBlock *ebp;
- lp=setFirstItem(allRegion);
- printf ("createLoopRegions: ");
- for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
- printf ("%s ", ebp->entryLabel->name);
- }
- printf (" %d\n", count);
- }
-#endif
+ applyToSet (bEdges, createLoop, &allRegion);
/* now we will create regions from these loops */
/* loops with the same entry points are considered to be the */
/*-----------------------------------------------------------------*/
/* loopOptimizations - identify region & remove invariants & ind */
/*-----------------------------------------------------------------*/
-int
-loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
+int
+loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
{
region *lp;
int change = 0;
{
if (optimize.loopInvariant)
- change += loopInvariants (lp, ebbs, count);
+ change += loopInvariants (lp, ebbi);
if (optimize.loopInduction)
- change += loopInduction (lp, ebbs, count);
+ change += loopInduction (lp, ebbi);
}
return change;
projects / fw / sdcc / blobdiff