- int loopInvariants( region *theLoop , eBBlock **ebbs, int count)
-{
- eBBlock *lBlock ;
- set *lInvars = NULL ;
-
- int change = 0 ;
-
- /* if the preHeader does not exist then do nothing */
- /* or no exits then do nothing ( have to think about this situation */
- if (theLoop->entry->preHeader == NULL ||
- theLoop->exits == NULL )
- return 0;
-
- /* we will do the elimination for those blocks */
- /* in the loop that dominates all exits from the loop */
- for (lBlock = setFirstItem(theLoop->regBlocks); lBlock;
- lBlock = setNextItem(theLoop->regBlocks)) {
-
- iCode *ic;
- int domsAllExits ;
- int i ;
-
- /* mark the dominates all exits flag */
- domsAllExits = ( applyToSet (theLoop->exits,dominatedBy,lBlock) ==
- elementsInSet (theLoop->exits));
-
-
- /* now we go thru the instructions of this block and */
- /* collect those instructions with invariant operands*/
- for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
-
- int lin , rin ;
- cseDef *ivar ;
-
- if (SKIP_IC(ic) || POINTER_SET(ic) || ic->op == IFX)
- continue ;
-
- /* if result is volatile then skip */
- if (IC_RESULT(ic) &&
- ( isOperandVolatile(IC_RESULT(ic),TRUE) ||
- IS_OP_PARM(IC_RESULT(ic))))
- continue ;
-
- lin = rin = 0 ;
-
- /* special case */
- /* if address of then it is an invariant */
- if (ic->op == ADDRESS_OF &&
- IS_SYMOP(IC_LEFT(ic)) &&
- IS_AGGREGATE(operandType(IC_LEFT(ic))))
- lin++;
- else
- /* check if left operand is an invariant */
- if ( (lin = isOperandInvariant (IC_LEFT(ic),theLoop,lInvars)))
- /* if this is a pointer get then make sure
- that the pointer set does not exist in
- any of the blocks */
- if (POINTER_GET(ic) &&
- ( 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
- could then be passed as a parameter */
- if (POINTER_GET(ic) &&
- 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 */
- /* prior to this definition which means only this definition*/
- /* 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 */
- /* make sure this defintion is not used anywhere else */
- if (!domsAllExits) {
-
- if (isOperandGlobal(IC_RESULT(ic)))
- continue;
- /* for successors for all exits */
- for ( sBlock = setFirstItem(theLoop->exits); sBlock;
- sBlock = setNextItem(theLoop->exits)) {
-
- for(i=0; i < count; ebbs[i++]->visited = 0);
- lBlock->visited = 1;
- if ( applyToSet (sBlock->succList,isDefAlive,ic))
- break ;
- }
-
- /* we have found usage */
- if (sBlock )
- continue ;
- }
-
- /* now make sure this is the only definition */
- for (sBlock = setFirstItem(lSet); sBlock ;
- sBlock = setNextItem (lSet)) {
- /* if this is the block make sure the definition */
- /* reaches the end of the block */
- if (sBlock == lBlock ) {
- if (! ifDiCodeIs (sBlock->outExprs,ic))
- break;
- }
- else
- if (bitVectBitsInCommon (sBlock->defSet,OP_DEFS(IC_RESULT(ic))))
- break;
- }
-
- if (sBlock)
- continue ; /* another definition present in the 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;
- remiCodeFromeBBlock (lBlock,ic);
-
- /* maintain the data flow */
- /* this means removing from definition from the */
- /* defset of this block and adding it to the */
- /* inexpressions of all blocks within the loop */
- bitVectUnSetBit (lBlock->defSet,ic->key);
- bitVectUnSetBit (lBlock->ldefs,ic->key);
- ivar = newCseDef(IC_RESULT(ic),ic);
- applyToSet (theLoop->regBlocks, addDefInExprs, ivar,ebbs,count);
- addSet(&lInvars,ivar);
- }
- }
- } /* for all loop blocks */
-
- /* if we have some invariants then */
- if (lInvars) {
- eBBlock *preHdr= theLoop->entry->preHeader ;
- iCode *icFirst = NULL , *icLast = NULL ;
- cseDef *cdp;
-
- /* create an iCode chain from it */
- for (cdp = setFirstItem(lInvars); cdp ; cdp = setNextItem(lInvars)) {
-
- /* maintain data flow .. add it to the */
- /* defSet & outExprs of the preheader */
- preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
- cdp->diCode->lineno = preHdr->ech->lineno;
- addSetHead (&preHdr->outExprs,cdp);
-
-
- if (!icFirst)
- icFirst = cdp->diCode;
- if (icLast) {
- icLast->next = cdp->diCode;
- cdp->diCode->prev = icLast;
- icLast = cdp->diCode ;
- } else
- icLast = cdp->diCode;
- change++ ;
- }
-
- /* add the instruction chain to the end of the
- preheader for this loop, preheaders will always
- have atleast a label */
- preHdr->ech->next = icFirst ;
- icFirst->prev = preHdr->ech ;
- preHdr->ech = icLast;
- icLast->next = NULL;
-
+static int
+loopInvariants (region * theLoop, ebbIndex * ebbi)
+{
+ eBBlock ** ebbs = ebbi->dfOrder;
+ int count = ebbi->count;
+ eBBlock *lBlock;
+ set *lInvars = NULL;
+
+ int change = 0;
+ int fCallsInBlock;
+
+ /* if the preHeader does not exist then do nothing */
+ /* or no exits then do nothing ( have to think about this situation */
+ if (theLoop->entry->preHeader == NULL ||
+ theLoop->exits == NULL)
+ return 0;
+
+ /* 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))
+ {
+
+ iCode *ic;
+ int domsAllExits;
+ int i;
+
+ /* mark the dominates all exits flag */
+ domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
+ elementsInSet (theLoop->exits));
+
+ /* find out if we have a function call in this block */
+ for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next)
+ {
+ if (SKIP_IC(ic))
+ {
+ fCallsInBlock++;
+ }
+ }
+
+ /* now we go thru the instructions of this block and */
+ /* collect those instructions with invariant operands */
+ for (ic = lBlock->sch; ic; ic = ic->next)
+ {
+
+ int lin, rin;
+ cseDef *ivar;
+
+ /* 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 (fCallsInBlock)
+ {
+ /* if this is a pointer get */
+ if (POINTER_GET(ic))
+ {
+ continue;
+ }
+
+ /* if this is an assignment from a global */
+ if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic)))
+ {
+ continue;
+ }
+
+ /* Bug 1717943,
+ * if this is an assignment to a global */
+ if (ic->op=='=' && isOperandGlobal(IC_RESULT(ic)))
+ {
+ continue;
+ }
+ }
+
+ 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) ||
+ IS_OP_PARM (IC_RESULT (ic))))
+ continue;
+
+ /* if result depends on a volatile then skip */
+ if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
+ (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
+ continue;
+
+ lin = rin = 0;
+
+ /* special case */
+ /* if address of then it is an invariant */
+ if (ic->op == ADDRESS_OF &&
+ IS_SYMOP (IC_LEFT (ic)) &&
+ IS_AGGREGATE (operandType (IC_LEFT (ic))))
+ {
+ lin++;
+ }
+ else
+ {
+ /* check if left operand is an invariant */
+ if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)) &&
+ /* if this is a pointer get then make sure
+ that the pointer set does not exist in
+ any of the blocks */
+ POINTER_GET (ic) &&
+ 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
+ could then be passed as a parameter */
+ if (POINTER_GET (ic) &&
+ 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 */
+ /* prior to this definition which means only this definition */
+ /* 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 exits */
+ /* make sure this defintion is not used anywhere else */
+ if (!domsAllExits)
+ {
+
+ if (isOperandGlobal (IC_RESULT (ic)))
+ continue;
+ /* for successors for all exits */
+ for (sBlock = setFirstItem (theLoop->exits); sBlock;
+ sBlock = setNextItem (theLoop->exits))
+ {
+
+ for (i = 0; i < count; ebbs[i++]->visited = 0);
+ lBlock->visited = 1;
+ if (applyToSet (sBlock->succList, isDefAlive, ic))
+ break;
+ }
+
+ /* we have found usage */
+ if (sBlock)
+ continue;
+ }
+
+ /* now make sure this is the only definition */
+ 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)
+ {
+ if (!ifDiCodeIs (sBlock->outExprs, ic))
+ break;
+ }
+ 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 */
+ /* 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;
+ SPIL_LOC (IC_RESULT (ic)) = NULL;
+ remiCodeFromeBBlock (lBlock, ic);
+
+ /* maintain the data flow */
+ /* this means removing from definition from the */
+ /* defset of this block and adding it to the */
+ /* inexpressions of all blocks within the loop */
+ bitVectUnSetBit (lBlock->defSet, ic->key);
+ bitVectUnSetBit (lBlock->ldefs, ic->key);
+ ivar = newCseDef (IC_RESULT (ic), ic);
+ applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
+ addSet (&lInvars, ivar);
+ }
+ }
+ } /* for all loop blocks */
+
+ /* if we have some invariants then */
+ if (lInvars)
+ {
+ eBBlock *preHdr = theLoop->entry->preHeader;
+ iCode *icFirst = NULL, *icLast = NULL;
+ cseDef *cdp;
+
+ /* create an iCode chain from it */
+ for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
+ {
+
+ /* maintain data flow .. add it to the */
+ /* ldefs defSet & outExprs of the preheader */
+ preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
+ preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
+ cdp->diCode->filename = preHdr->ech->filename;
+ cdp->diCode->lineno = preHdr->ech->lineno;
+ addSetHead (&preHdr->outExprs, cdp);
+
+
+ if (!icFirst)
+ icFirst = cdp->diCode;
+ if (icLast)
+ {
+ icLast->next = cdp->diCode;
+ cdp->diCode->prev = icLast;
+ icLast = cdp->diCode;
+ }
+ else
+ icLast = cdp->diCode;
+ change++;
+ }
+
+ /* add the instruction chain to the end of the
+ preheader for this loop, preheaders will always
+ have atleast a label */
+ preHdr->ech->next = icFirst;
+ icFirst->prev = preHdr->ech;
+ preHdr->ech = icLast;
+ icLast->next = NULL;
+
projects / fw / sdcc / blobdiff