X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCCloop.c;h=c3e2f7e86be8960b46c8e8f73a2e6f24ee3db83b;hb=3df17c583bad53f0ee98c8a2464222431584a62b;hp=9bb74e335539b7f6c08b133d4e1bddf5f864729e;hpb=24b38610695ad1df39fb34e5e63be583035e2e21;p=fw%2Fsdcc diff --git a/src/SDCCloop.c b/src/SDCCloop.c index 9bb74e33..c3e2f7e8 100644 --- a/src/SDCCloop.c +++ b/src/SDCCloop.c @@ -1,9 +1,3 @@ -//#define LIVERANGEHUNT -#ifdef LIVERANGEHUNT - #define LRH(x) x -#else - #define LRH(x) -#endif /*------------------------------------------------------------------------- SDCCloop.c - source file for loop detection & optimizations @@ -39,7 +33,7 @@ STACK_DCL (regionStack, eBBlock *, MAX_NEST_LEVEL * 10); /*-----------------------------------------------------------------*/ /* newInduction - creates a new induction variable */ /*-----------------------------------------------------------------*/ -induction * +static induction * newInduction (operand * sym, unsigned int op, long constVal, iCode * ic, operand * asym) { @@ -52,14 +46,14 @@ newInduction (operand * sym, unsigned int op, ip->op = op; ip->cval = constVal; ip->ic = ic; - updateSpillLocation(ic,1); +//updateSpillLocation(ic,1); return ip; } /*-----------------------------------------------------------------*/ /* newRegion - allocate & returns a loop structure */ /*-----------------------------------------------------------------*/ -region * +static region * newRegion () { region *lp; @@ -70,9 +64,11 @@ newRegion () } +#if 0 /*-----------------------------------------------------------------*/ /* pinduction - prints induction */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (pinduction) { induction *ip = item; @@ -89,6 +85,7 @@ DEFSETFUNC (pinduction) /*-----------------------------------------------------------------*/ /* pregion - prints loop information */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (pregion) { region *lp = item; @@ -105,10 +102,12 @@ DEFSETFUNC (pregion) printf ("\n"); return 0; } +#endif /*-----------------------------------------------------------------*/ /* backEdges - returns a list of back edges */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (backEdges) { edge *ep = item; @@ -150,16 +149,14 @@ intersectLoopSucc (set * lexits, eBBlock ** ebbs) return succVect; } - /*-----------------------------------------------------------------*/ /* 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); } @@ -168,6 +165,7 @@ loopInsert (set ** regionSet, eBBlock * block) /*-----------------------------------------------------------------*/ /* insertIntoLoop - insert item into loop */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (insertIntoLoop) { eBBlock *ebp = item; @@ -180,6 +178,7 @@ DEFSETFUNC (insertIntoLoop) /*-----------------------------------------------------------------*/ /* isNotInBlocks - will return 1 if not is blocks */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (isNotInBlocks) { eBBlock *ebp = item; @@ -191,11 +190,12 @@ DEFSETFUNC (isNotInBlocks) return 0; } +#if 0 /*-----------------------------------------------------------------*/ /* hasIncomingDefs - has definitions coming into the loop. i.e. */ /* check to see if the preheaders outDefs has any definitions */ /*-----------------------------------------------------------------*/ -int +static int hasIncomingDefs (region * lreg, operand * op) { eBBlock *preHdr = lreg->entry->preHeader; @@ -209,7 +209,7 @@ hasIncomingDefs (region * lreg, operand * op) /* findLoopEndSeq - will return the sequence number of the last */ /* iCode with the maximum dfNumber in the region */ /*-----------------------------------------------------------------*/ -int +static int findLoopEndSeq (region * lreg) { eBBlock *block; @@ -224,11 +224,13 @@ findLoopEndSeq (region * lreg) return lblock->lSeq; } +#endif /*-----------------------------------------------------------------*/ /* addToExitsMarkDepth - will add the the exitSet all blocks that */ /* have exits, will also update the depth field in the blocks */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (addToExitsMarkDepth) { eBBlock *ebp = item; @@ -236,13 +238,12 @@ DEFSETFUNC (addToExitsMarkDepth) 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->depthdepth = 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) @@ -262,46 +263,21 @@ DEFSETFUNC (addToExitsMarkDepth) /*-----------------------------------------------------------------*/ /* createLoop - will create a set of region */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (createLoop) { 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)) { @@ -311,61 +287,7 @@ DEFSETFUNC (createLoop) 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); @@ -375,6 +297,7 @@ DEFSETFUNC (createLoop) /*-----------------------------------------------------------------*/ /* dominatedBy - will return 1 if item is dominated by block */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (dominatedBy) { eBBlock *ebp = item; @@ -386,22 +309,22 @@ DEFSETFUNC (dominatedBy) /*-----------------------------------------------------------------*/ /* addDefInExprs - adds an expression into the inexpressions */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (addDefInExprs) { 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 +static int assignmentsToSym (set * sset, operand * sym) { eBBlock *ebp; @@ -411,13 +334,11 @@ assignmentsToSym (set * sset, operand * sym) for (ebp = setFirstItem (blocks); ebp; ebp = setNextItem (blocks)) { - /* get all the definitions for this symbol in this block */ bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym)); assigns += bitVectnBitsOn (defs); - setToNull ((void **) &defs); - + setToNull ((void *) &defs); } return assigns; @@ -427,7 +348,7 @@ assignmentsToSym (set * sset, operand * sym) /*-----------------------------------------------------------------*/ /* isOperandInvariant - determines if an operand is an invariant */ /*-----------------------------------------------------------------*/ -int +static int isOperandInvariant (operand * op, region * theLoop, set * lInvars) { int opin = 0; @@ -452,9 +373,6 @@ isOperandInvariant (operand * op, region * theLoop, set * lInvars) !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++; @@ -465,17 +383,34 @@ isOperandInvariant (operand * op, region * theLoop, set * lInvars) /*-----------------------------------------------------------------*/ /* pointerAssigned - will return 1 if pointer set found */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (pointerAssigned) { 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; } /*-----------------------------------------------------------------*/ /* hasNonPtrUse - returns true if operand has non pointer usage */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (hasNonPtrUse) { eBBlock *ebp = item; @@ -492,9 +427,11 @@ DEFSETFUNC (hasNonPtrUse) /*-----------------------------------------------------------------*/ /* loopInvariants - takes loop invariants out of region */ /*-----------------------------------------------------------------*/ -int -loopInvariants (region * theLoop, eBBlock ** ebbs, int count) +static int +loopInvariants (region * theLoop, ebbIndex * ebbi) { + eBBlock ** ebbs = ebbi->dfOrder; + int count = ebbi->count; eBBlock *lBlock; set *lInvars = NULL; @@ -507,8 +444,8 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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)) { @@ -536,7 +473,7 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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 */ @@ -556,6 +493,13 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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) || @@ -568,7 +512,7 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) continue; lin = rin = 0; - + /* special case */ /* if address of then it is an invariant */ if (ic->op == ADDRESS_OF && @@ -582,14 +526,14 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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 @@ -598,18 +542,19 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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) { @@ -636,6 +581,10 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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) @@ -645,12 +594,49 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) } 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; @@ -658,7 +644,9 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) /* 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 */ @@ -668,7 +656,7 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) 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); } } @@ -721,7 +709,7 @@ loopInvariants (region * theLoop, eBBlock ** ebbs, int count) /*-----------------------------------------------------------------*/ /* addressTaken - returns true if the symbol is found in the addrof */ /*-----------------------------------------------------------------*/ -int +static int addressTaken (set * sset, operand * sym) { set *loop; @@ -747,6 +735,7 @@ addressTaken (set * sset, operand * sym) /*-----------------------------------------------------------------*/ /* findInduction :- returns 1 & the item if the induction is found */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (findInduction) { induction *ip = item; @@ -765,7 +754,7 @@ DEFSETFUNC (findInduction) /*-----------------------------------------------------------------*/ /* findDefInRegion - finds the definition within the region */ /*-----------------------------------------------------------------*/ -iCode * +static iCode * findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner) { eBBlock *lBlock; @@ -794,11 +783,191 @@ findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner) return NULL; } +/*-----------------------------------------------------------------*/ +/* addPostLoopBlock - add a ebblock before the successors of the */ +/* loop exits */ +/*-----------------------------------------------------------------*/ +static void +addPostLoopBlock (region *loopReg, ebbIndex *ebbi, iCode *ic) +{ + bitVect *loopSuccs; + int i; + + /* if the number of exits is greater than one then + we use another trick: we will create an intersection + of succesors of the exits, then take those that are not + part of the loop and have dfNumber greater loop entry (eblock), + insert a new predecessor postLoopBlk before them and add + a copy of ic in the new block. The postLoopBlk in between + is necessary, because the old successors of the loop exits can + be successors of other blocks too: see bug-136564. */ + + /* loopSuccs now contains intersection + of all the loops successors */ + loopSuccs = intersectLoopSucc (loopReg->exits, ebbi->dfOrder); + if (!loopSuccs) + return; + + for (i = 0; i < loopSuccs->size; i++) + { + eBBlock *eblock = NULL; + eBBlock *postLoopBlk; + iCode *newic; + int j; + + if (!bitVectBitValue (loopSuccs, i)) + continue; + + /* Need to search for bbnum == i since ebbi->dfOrder is + sorted by dfnum; a direct index won't do. */ + for (j = 0; j < ebbi->count; j++) + if (ebbi->dfOrder[j]->bbnum == i) + { + eblock = ebbi->dfOrder[j]; + break; + } + assert(eblock); + + /* if the successor does not belong to the loop + and will be executed after the loop : then + add a definition to the block */ + if (isinSet (loopReg->regBlocks, eblock)) + continue; + if (eblock->dfnum <= loopReg->entry->dfnum) + continue; + + /* look for an existing loopExitBlock */ + if (strncmp (LOOPEXITLBL, + eblock->entryLabel->name, + sizeof(LOOPEXITLBL) - 1) == 0) + { + /* reuse the existing one */ + postLoopBlk = eblock; + } + else + { + /* create and insert a new eBBlock. + Damn, that's messy ... */ + int i; + set *oldPredList; + eBBlock *ebpi; + + postLoopBlk = neweBBlock(); + + /* create a loopExit-label */ + postLoopBlk->entryLabel = newiTempLoopHeaderLabel (0); + + /* increase bbnum for all blocks after + (and including) eblock */ + for (i = 0; i < ebbi->count; i++) + { + if (ebbi->bbOrder[i]->bbnum >= eblock->bbnum) + ++ebbi->bbOrder[i]->bbnum; + } + /* insert postLoopBlk before bbnum */ + postLoopBlk->bbnum = eblock->bbnum - 1; + + ++ebbi->count; + + /* these arrays need one more block, which ... */ + ebbi->bbOrder = Safe_realloc (ebbi->bbOrder, + (ebbi->count + 1) * sizeof(eBBlock *)); + /* ... must be initialized with 0 */ + ebbi->bbOrder[ebbi->count] = NULL; + /* move the blocks up ... */ + memmove (&ebbi->bbOrder[postLoopBlk->bbnum + 1], + &ebbi->bbOrder[postLoopBlk->bbnum], + (ebbi->count - postLoopBlk->bbnum - 1) * sizeof(eBBlock *)); + /* ... and insert postLoopBlk */ + ebbi->bbOrder[postLoopBlk->bbnum] = postLoopBlk; + + /* just add postLoopBlk at the end of dfOrder, + computeControlFlow() will compute the new dfnum */ + ebbi->dfOrder = Safe_realloc (ebbi->dfOrder, + (ebbi->count + 1) * sizeof(eBBlock *)); + ebbi->dfOrder[ebbi->count] = NULL; + ebbi->dfOrder[ebbi->count - 1] = postLoopBlk; + + /* copy loop information from eblock to postLoopBlk */ + if (eblock->partOfLoop) + { + postLoopBlk->partOfLoop = eblock->partOfLoop; + /* add postLoopBlk to loop region */ + addSetHead (&postLoopBlk->partOfLoop->regBlocks, postLoopBlk); + } + + /* go through loop exits and replace the old exit block eblock + with the new postLoopBlk */ + for (ebpi = setFirstItem (loopReg->exits); + ebpi; + ebpi = setNextItem (loopReg->exits)) + { + /* replace old label with new label */ + replaceLabel (ebpi, eblock->entryLabel, postLoopBlk->entryLabel); + } + + /* now eblock is replaced by postLoopBlk. + It's possible, that eblock has an immediate predecessor + (with ebpi->bbnum + 1 == eblock->bbnum), which isn't part of the + loop. This predecessor must stay predecessor of eblock, not of + postLoopBlk. But now postLoopBlk is in between, therefore a GOTO + from this predecessor to eblock must be appended. + Example: bug-136564.c */ + + /* take all predecessors and subtract the loop exits */ + oldPredList = subtractFromSet (eblock->predList, + loopReg->exits, + THROW_NONE); + for (ebpi = setFirstItem (oldPredList); + ebpi; + ebpi = setNextItem (oldPredList)) + { + /* Is it an immediate predecessor (without GOTO)? + All other predecessors end with a + GOTO, IF, IFX or JUMPTABLE: nothing to to do */ + if (ebpi->bbnum + 1 == postLoopBlk->bbnum) + { + /* insert goto to old predecessor of eblock */ + newic = newiCodeLabelGoto (GOTO, eblock->entryLabel); + addiCodeToeBBlock (ebpi, newic, NULL); + break; /* got it, only one is possible */ + } + } + + /* set the label */ + postLoopBlk->sch = + postLoopBlk->ech = newiCodeLabelGoto (LABEL, postLoopBlk->entryLabel); + } + + /* create the definition in postLoopBlk */ + newic = newiCode ('=', NULL, operandFromOperand (IC_RIGHT (ic))); + IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic)); + /* maintain data flow */ + OP_DEFS(IC_RESULT (newic)) = bitVectSetBit (OP_DEFS (IC_RESULT (newic)), + newic->key); + OP_USES(IC_RIGHT (newic)) = bitVectSetBit (OP_USES (IC_RIGHT (newic)), + newic->key); + + /* and add it */ + addiCodeToeBBlock (postLoopBlk, newic, NULL); + postLoopBlk->sch->lineno = + postLoopBlk->ech->lineno = eblock->sch->lineno; + + /* outDefs is needed by computeControlFlow(), anything + else will be set up by computeControlFlow() */ + postLoopBlk->outDefs = bitVectSetBit (postLoopBlk->outDefs, newic->key); + } /* for (i = 0; i < loopSuccs->size; i++) */ + + /* the postLoopBlk and the induction significantly + changed the control flow, recompute it */ + computeControlFlow (ebbi); +} + /*-----------------------------------------------------------------*/ /* basicInduction - finds the basic induction variables in a loop */ /*-----------------------------------------------------------------*/ -set * -basicInduction (region * loopReg, eBBlock ** ebbs, int count) +static set * +basicInduction (region * loopReg, ebbIndex * ebbi) { eBBlock *lBlock; set *indVars = NULL; @@ -816,13 +985,27 @@ basicInduction (region * loopReg, eBBlock ** ebbs, int count) { 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; @@ -845,6 +1028,15 @@ basicInduction (region * loopReg, eBBlock ** ebbs, int count) 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))) @@ -853,14 +1045,30 @@ basicInduction (region * loopReg, eBBlock ** ebbs, int count) /* 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)) @@ -901,84 +1109,27 @@ basicInduction (region * loopReg, eBBlock ** ebbs, int count) /* replace the inducted variable by the iTemp */ replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic)); - - /* if it has only one exit then remove it from here - and put it in the exit block */ - nexits = elementsInSet (loopReg->exits); - 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) - { - iCode *saveic = ic->prev; - /* remove it */ - remiCodeFromeBBlock (lBlock, ic); - /* clear the definition */ - bitVectUnSetBit (lBlock->defSet, ic->key); - /* add it to the exit */ - addiCodeToeBBlock (exit, ic, NULL); - /* set the definition bit */ - exit->defSet = bitVectSetBit (exit->defSet, ic->key); - ic = saveic; - } - } - - /* if the number of exits is greater than one then - we use another trick ; we will create an intersection - of succesors of the exits, then take those that are not - part of the loop and have dfNumber greater loop entry - and insert a new definition in them */ - if (nexits > 1) - { - - bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs); - - /* loopSuccs now contains intersection - of all the loops successors */ - if (loopSuccs) - { - int i; - for (i = 0; i < loopSuccs->size; i++) - { - if (bitVectBitValue (loopSuccs, i)) - { - - eBBlock *eblock = ebbs[i]; - - /* if the successor does not belong to the loop - and will be executed after the loop : then - add a definition to the block */ - if (!isinSet (loopReg->regBlocks, eblock) && - eblock->dfnum > loopReg->entry->dfnum) - { - /* create the definition */ - iCode *newic = newiCode ('=', NULL, - operandFromOperand (IC_RIGHT (ic))); - IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic)); - OP_DEFS(IC_RESULT (newic))= - bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key); - OP_USES(IC_RIGHT (newic))= - bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key); - /* and add it */ - if (eblock->sch && eblock->sch->op == LABEL) - addiCodeToeBBlock (eblock, newic, eblock->sch->next); - else - addiCodeToeBBlock (eblock, newic, eblock->sch); - /* set the definition bit */ - eblock->defSet = bitVectSetBit (eblock->defSet, ic->key); - } - } - } - } - } - - addSet (&indVars, ip); - } - - } /* end of all blocks for basic induction variables */ + /* ic should now be moved to the exit block(s) */ + + nexits = elementsInSet (loopReg->exits); + if (nexits == 0) + { + /* this is a endless loop without exits: there's + no need to restore the inducted variable */ + iCode *saveic = ic->prev; + + /* ic will be removed by killDeadCode() too, + but it's a nice to see a clean dumploop now. */ + remiCodeFromeBBlock (lBlock, ic); + /* clear the definition */ + bitVectUnSetBit (lBlock->defSet, ic->key); + ic = saveic; + } + else + addPostLoopBlock (loopReg, ebbi, ic); + addSet (&indVars, ip); + } /* for ic */ + } /* end of all blocks for basic induction variables */ return indVars; } @@ -986,11 +1137,11 @@ basicInduction (region * loopReg, eBBlock ** ebbs, int count) /*-----------------------------------------------------------------*/ /* loopInduction - remove induction variables from a loop */ /*-----------------------------------------------------------------*/ -int -loopInduction (region * loopReg, eBBlock ** ebbs, int count) +static int +loopInduction (region * loopReg, ebbIndex * ebbi) { int change = 0; - eBBlock *lBlock, *lastBlock = NULL; + eBBlock *lBlock, *owner, *lastBlock = NULL; set *indVars = NULL; set *basicInd = NULL; @@ -998,7 +1149,7 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) return 0; /* we first determine the basic Induction variables */ - basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count)); + basicInd = setFromSet (indVars = basicInduction (loopReg, ebbi)); /* find other induction variables : by other we mean definitions of */ /* the form x := y (* | / ) .. we will move this one to */ @@ -1009,7 +1160,7 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) lBlock = setNextItem (loopReg->regBlocks)) { - iCode *ic, *indIc; + iCode *ic, *indIc, *dic; induction *ip; /* last block is the one with the highest block @@ -1020,14 +1171,17 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) 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; @@ -1037,9 +1191,19 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) (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 */ @@ -1076,32 +1240,23 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) 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)); + /* 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); - addSet (&indVars, - newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL)); - } } } @@ -1118,7 +1273,6 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) ip; ip = setNextItem (indVars)) { - indVect = bitVectSetBit (indVect, ip->ic->key); ip->ic->lineno = preHdr->ech->lineno; if (!icFirst) @@ -1147,13 +1301,14 @@ loopInduction (region * loopReg, eBBlock ** ebbs, int count) lastBlock->linds = bitVectUnion(lastBlock->linds,indVect); } - setToNull ((void **) &indVars); + setToNull ((void *) &indVars); return change; } /*-----------------------------------------------------------------*/ /* mergeRegions - will merge region with same entry point */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (mergeRegions) { region *theLoop = item; @@ -1175,7 +1330,7 @@ DEFSETFUNC (mergeRegions) if (lp->entry == theLoop->entry) { theLoop->regBlocks = unionSets (theLoop->regBlocks, - lp->regBlocks, THROW_BOTH); + lp->regBlocks, THROW_DEST); lp->merged = 1; } } @@ -1186,6 +1341,7 @@ DEFSETFUNC (mergeRegions) /*-----------------------------------------------------------------*/ /* ifMerged - return 1 if the merge flag is 1 */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (ifMerged) { region *lp = item; @@ -1196,6 +1352,7 @@ DEFSETFUNC (ifMerged) /*-----------------------------------------------------------------*/ /* mergeInnerLoops - will merge into body when entry is present */ /*-----------------------------------------------------------------*/ +static DEFSETFUNC (mergeInnerLoops) { region *theLoop = item; @@ -1230,7 +1387,7 @@ DEFSETFUNC (mergeInnerLoops) /* 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; @@ -1238,26 +1395,13 @@ createLoopRegions (eBBlock ** ebbs, int count) 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 */ @@ -1290,8 +1434,8 @@ createLoopRegions (eBBlock ** ebbs, int count) /*-----------------------------------------------------------------*/ /* 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; @@ -1311,10 +1455,10 @@ loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count) { 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;