1 /*-------------------------------------------------------------------------
3 SDCCloop.c - source file for loop detection & optimizations
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
29 DEFSETFUNC (isDefAlive);
31 STACK_DCL (regionStack, eBBlock *, MAX_NEST_LEVEL * 10);
33 /*-----------------------------------------------------------------*/
34 /* newInduction - creates a new induction variable */
35 /*-----------------------------------------------------------------*/
37 newInduction (operand * sym, unsigned int op,
38 long constVal, iCode * ic, operand * asym)
42 ip = Safe_alloc ( sizeof (induction));
49 //updateSpillLocation(ic,1);
53 /*-----------------------------------------------------------------*/
54 /* newRegion - allocate & returns a loop structure */
55 /*-----------------------------------------------------------------*/
61 lp = Safe_alloc ( sizeof (region));
68 /*-----------------------------------------------------------------*/
69 /* pinduction - prints induction */
70 /*-----------------------------------------------------------------*/
72 DEFSETFUNC (pinduction)
77 fprintf (stdout, "\t");
78 printOperand (ip->sym, stdout);
79 icTab = getTableEntry (ip->ic->op);
80 icTab->iCodePrint (stdout, ip->ic, icTab->printName);
81 fprintf (stdout, " %04d\n", (int) ip->cval);
85 /*-----------------------------------------------------------------*/
86 /* pregion - prints loop information */
87 /*-----------------------------------------------------------------*/
93 printf ("================\n");
94 printf (" loop with entry -- > ");
95 printEntryLabel (lp->entry, ap);
97 printf (" loop body --> ");
98 applyToSet (lp->regBlocks, printEntryLabel);
100 printf (" loop exits --> ");
101 applyToSet (lp->exits, printEntryLabel);
107 /*-----------------------------------------------------------------*/
108 /* backEdges - returns a list of back edges */
109 /*-----------------------------------------------------------------*/
111 DEFSETFUNC (backEdges)
114 V_ARG (set **, bEdges);
116 /* if this is a back edge ; to determine this we check */
117 /* to see if the 'to' is in the dominator list of the */
118 /* 'from' if yes then this is a back edge */
119 if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
121 addSetHead (bEdges, ep);
128 /*-----------------------------------------------------------------*/
129 /* intersectLoopSucc - returns intersection of loop Successors */
130 /*-----------------------------------------------------------------*/
132 intersectLoopSucc (set * lexits, eBBlock ** ebbs)
134 bitVect *succVect = NULL;
135 eBBlock *exit = setFirstItem (lexits);
140 succVect = bitVectCopy (exit->succVect);
142 for (exit = setNextItem (lexits); exit;
143 exit = setNextItem (lexits))
145 succVect = bitVectIntersect (succVect,
152 /*-----------------------------------------------------------------*/
153 /* loopInsert will insert a block into the loop set */
154 /*-----------------------------------------------------------------*/
156 loopInsert (set ** regionSet, eBBlock * block)
158 if (!isinSet (*regionSet, block))
160 addSetHead (regionSet, block);
161 STACK_PUSH (regionStack, block);
165 /*-----------------------------------------------------------------*/
166 /* insertIntoLoop - insert item into loop */
167 /*-----------------------------------------------------------------*/
169 DEFSETFUNC (insertIntoLoop)
172 V_ARG (set **, regionSet);
174 loopInsert (regionSet, ebp);
178 /*-----------------------------------------------------------------*/
179 /* isNotInBlocks - will return 1 if not is blocks */
180 /*-----------------------------------------------------------------*/
182 DEFSETFUNC (isNotInBlocks)
185 V_ARG (set *, blocks);
187 if (!isinSet (blocks, ebp))
194 /*-----------------------------------------------------------------*/
195 /* hasIncomingDefs - has definitions coming into the loop. i.e. */
196 /* check to see if the preheaders outDefs has any definitions */
197 /*-----------------------------------------------------------------*/
199 hasIncomingDefs (region * lreg, operand * op)
201 eBBlock *preHdr = lreg->entry->preHeader;
203 if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
208 /*-----------------------------------------------------------------*/
209 /* findLoopEndSeq - will return the sequence number of the last */
210 /* iCode with the maximum dfNumber in the region */
211 /*-----------------------------------------------------------------*/
213 findLoopEndSeq (region * lreg)
218 for (block = lblock = setFirstItem (lreg->regBlocks); block;
219 block = setNextItem (lreg->regBlocks))
221 if (block != lblock && block->lSeq > lblock->lSeq)
229 /*-----------------------------------------------------------------*/
230 /* addToExitsMarkDepth - will add the the exitSet all blocks that */
231 /* have exits, will also update the depth field in the blocks */
232 /*-----------------------------------------------------------------*/
234 DEFSETFUNC (addToExitsMarkDepth)
237 V_ARG (set *, loopBlocks);
238 V_ARG (set **, exits);
240 V_ARG (region *, lr);
242 /* mark the loop depth of this block */
244 if (ebp->depth<depth)
247 /* NOTE: here we will update only the inner most loop
248 that it is a part of */
249 if (!ebp->partOfLoop)
250 ebp->partOfLoop = lr;
252 /* if any of the successors go out of the loop then */
253 /* we add this one to the exits */
254 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
256 addSetHead (exits, ebp);
263 /*-----------------------------------------------------------------*/
264 /* createLoop - will create a set of region */
265 /*-----------------------------------------------------------------*/
267 DEFSETFUNC (createLoop)
270 V_ARG (set **, allRegion);
271 region *aloop = newRegion ();
274 /* make sure regionStack is empty */
275 while (!STACK_EMPTY (regionStack))
276 STACK_POP (regionStack);
278 /* add the entryBlock */
279 addSet (&aloop->regBlocks, ep->to);
280 loopInsert (&aloop->regBlocks, ep->from);
282 while (!STACK_EMPTY (regionStack))
284 block = STACK_POP (regionStack);
285 /* if block != entry */
287 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
290 aloop->entry = ep->to;
292 /* now add it to the set */
293 addSetHead (allRegion, aloop);
297 /*-----------------------------------------------------------------*/
298 /* dominatedBy - will return 1 if item is dominated by block */
299 /*-----------------------------------------------------------------*/
301 DEFSETFUNC (dominatedBy)
304 V_ARG (eBBlock *, block);
306 return bitVectBitValue (ebp->domVect, block->bbnum);
309 /*-----------------------------------------------------------------*/
310 /* addDefInExprs - adds an expression into the inexpressions */
311 /*-----------------------------------------------------------------*/
313 DEFSETFUNC (addDefInExprs)
316 V_ARG (cseDef *, cdp);
317 V_ARG (ebbIndex *, ebbi);
319 addSetHead (&ebp->inExprs, cdp);
320 cseBBlock (ebp, optimize.global_cse, ebbi);
324 /*-----------------------------------------------------------------*/
325 /* assignmentsToSym - for a set of blocks determine # time assigned */
326 /*-----------------------------------------------------------------*/
328 assignmentsToSym (set * sset, operand * sym)
332 set *blocks = setFromSet (sset);
334 for (ebp = setFirstItem (blocks); ebp;
335 ebp = setNextItem (blocks))
337 /* get all the definitions for this symbol
339 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
340 assigns += bitVectnBitsOn (defs);
341 setToNull ((void *) &defs);
348 /*-----------------------------------------------------------------*/
349 /* isOperandInvariant - determines if an operand is an invariant */
350 /*-----------------------------------------------------------------*/
352 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
355 /* operand is an invariant if it is a */
357 /* b. that have defintions reaching loop entry */
358 /* c. that are already defined as invariant */
359 /* d. has no assignments in the loop */
362 if (IS_OP_LITERAL (op))
364 else if (IS_SYMOP (op) &&
365 OP_SYMBOL (op)->addrtaken)
367 else if (ifDefSymIs (theLoop->entry->inExprs, op))
369 else if (ifDefSymIs (lInvars, op))
371 else if (IS_SYMOP (op) &&
372 !IS_OP_GLOBAL (op) &&
373 !IS_OP_VOLATILE (op) &&
374 assignmentsToSym (theLoop->regBlocks, op) == 0)
383 /*-----------------------------------------------------------------*/
384 /* pointerAssigned - will return 1 if pointer set found */
385 /*-----------------------------------------------------------------*/
387 DEFSETFUNC (pointerAssigned)
390 V_ARG (operand *, op);
395 if (bitVectBitValue (ebp->ptrsSet, op->key))
398 /* Unfortunately, one of the other pointer set operations */
399 /* may be using an alias of this operand, and the above */
400 /* test would miss it. To be thorough, some aliasing */
401 /* analysis should be done here. In the meantime, be */
402 /* conservative and assume any other pointer set operation */
404 if (!bitVectIsZero (ebp->ptrsSet))
410 /*-----------------------------------------------------------------*/
411 /* hasNonPtrUse - returns true if operand has non pointer usage */
412 /*-----------------------------------------------------------------*/
414 DEFSETFUNC (hasNonPtrUse)
417 V_ARG (operand *, op);
418 iCode *ic = usedInRemaining (op, ebp->sch);
420 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
427 /*-----------------------------------------------------------------*/
428 /* loopInvariants - takes loop invariants out of region */
429 /*-----------------------------------------------------------------*/
431 loopInvariants (region * theLoop, ebbIndex * ebbi)
433 eBBlock ** ebbs = ebbi->dfOrder;
434 int count = ebbi->count;
441 /* if the preHeader does not exist then do nothing */
442 /* or no exits then do nothing ( have to think about this situation */
443 if (theLoop->entry->preHeader == NULL ||
444 theLoop->exits == NULL)
447 /* we will do the elimination for those blocks */
448 /* in the loop that dominate all exits from the loop */
449 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
450 lBlock = setNextItem (theLoop->regBlocks))
457 /* mark the dominates all exits flag */
458 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
459 elementsInSet (theLoop->exits));
461 /* find out if we have a function call in this block */
462 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
468 /* now we go thru the instructions of this block and */
469 /* collect those instructions with invariant operands */
470 for (ic = lBlock->sch; ic; ic = ic->next)
476 /* TODO this is only needed if the call is between
477 here and the definition, but I am too lazy to do that now */
479 /* if there are function calls in this block */
482 /* if this is a pointer get */
483 if (POINTER_GET(ic)) {
487 /* if this is an assignment from a global */
488 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
493 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
496 /* iTemp assignment from a literal may be invariant, but it
497 will needlessly increase register pressure if the
498 iCode(s) that use this iTemp are not also invariant */
499 if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
500 && IS_OP_LITERAL (IC_RIGHT (ic)))
503 /* if result is volatile then skip */
504 if (IC_RESULT (ic) &&
505 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
506 IS_OP_PARM (IC_RESULT (ic))))
509 /* if result depends on a volatile then skip */
510 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
511 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
517 /* if address of then it is an invariant */
518 if (ic->op == ADDRESS_OF &&
519 IS_SYMOP (IC_LEFT (ic)) &&
520 IS_AGGREGATE (operandType (IC_LEFT (ic))))
523 /* check if left operand is an invariant */
524 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
525 /* if this is a pointer get then make sure
526 that the pointer set does not exist in
528 if (POINTER_GET (ic) &&
529 (applyToSet (theLoop->regBlocks,
530 pointerAssigned, IC_LEFT (ic))))
534 /* do the same for right */
535 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
537 /* if this is a POINTER_GET then special case, make sure all
538 usages within the loop are POINTER_GET any other usage
539 would mean that this is not an invariant , since the pointer
540 could then be passed as a parameter */
541 if (POINTER_GET (ic) &&
542 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
546 /* if both the left & right are invariants : then check that */
547 /* this definition exists in the out definition of all the */
548 /* blocks, this will ensure that this is not assigned any */
549 /* other value in the loop, and not used in this block */
550 /* prior to this definition which means only this definition */
551 /* is used in this loop */
552 if (lin && rin && IC_RESULT (ic))
555 set *lSet = setFromSet (theLoop->regBlocks);
557 /* if this block does not dominate all exits */
558 /* make sure this defintion is not used anywhere else */
562 if (isOperandGlobal (IC_RESULT (ic)))
564 /* for successors for all exits */
565 for (sBlock = setFirstItem (theLoop->exits); sBlock;
566 sBlock = setNextItem (theLoop->exits))
569 for (i = 0; i < count; ebbs[i++]->visited = 0);
571 if (applyToSet (sBlock->succList, isDefAlive, ic))
575 /* we have found usage */
580 /* now make sure this is the only definition */
581 for (sBlock = setFirstItem (lSet); sBlock;
582 sBlock = setNextItem (lSet))
588 /* if this is the block make sure the definition */
589 /* reaches the end of the block */
590 if (sBlock == lBlock)
592 if (!ifDiCodeIs (sBlock->outExprs, ic))
595 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
598 /* Check that this definition is not assigned */
599 /* any other value in this block. Also check */
600 /* that any usage in the block is dominated by */
601 /* by this definition. */
602 defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
604 for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
608 if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
611 else if (ic2->op == JUMPTABLE)
613 if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
618 if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
620 if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
622 if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
624 /* If used before this definition, might not be invariant */
625 if ((ic == ic2) && used)
628 if (used && !defDominates)
631 if (ic2) /* found another definition or a usage before the definition */
636 continue; /* another definition present in the block */
639 /* now check if it exists in the in of this block */
640 /* if not then it was killed before this instruction */
641 if (!bitVectBitValue (lBlock->inDefs, ic->key))
644 /* now we know it is a true invariant */
645 /* remove it from the insts chain & put */
646 /* in the invariant set */
648 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
649 SPIL_LOC (IC_RESULT (ic)) = NULL;
650 remiCodeFromeBBlock (lBlock, ic);
652 /* maintain the data flow */
653 /* this means removing from definition from the */
654 /* defset of this block and adding it to the */
655 /* inexpressions of all blocks within the loop */
656 bitVectUnSetBit (lBlock->defSet, ic->key);
657 bitVectUnSetBit (lBlock->ldefs, ic->key);
658 ivar = newCseDef (IC_RESULT (ic), ic);
659 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
660 addSet (&lInvars, ivar);
663 } /* for all loop blocks */
665 /* if we have some invariants then */
668 eBBlock *preHdr = theLoop->entry->preHeader;
669 iCode *icFirst = NULL, *icLast = NULL;
672 /* create an iCode chain from it */
673 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
676 /* maintain data flow .. add it to the */
677 /* ldefs defSet & outExprs of the preheader */
678 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
679 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
680 cdp->diCode->filename = preHdr->ech->filename;
681 cdp->diCode->lineno = preHdr->ech->lineno;
682 addSetHead (&preHdr->outExprs, cdp);
686 icFirst = cdp->diCode;
689 icLast->next = cdp->diCode;
690 cdp->diCode->prev = icLast;
691 icLast = cdp->diCode;
694 icLast = cdp->diCode;
698 /* add the instruction chain to the end of the
699 preheader for this loop, preheaders will always
700 have atleast a label */
701 preHdr->ech->next = icFirst;
702 icFirst->prev = preHdr->ech;
703 preHdr->ech = icLast;
710 /*-----------------------------------------------------------------*/
711 /* addressTaken - returns true if the symbol is found in the addrof */
712 /*-----------------------------------------------------------------*/
714 addressTaken (set * sset, operand * sym)
720 for (loop = sset; loop; loop = loop->next)
726 if (isOperandEqual ((operand *) loop2->item, sym))
736 /*-----------------------------------------------------------------*/
737 /* findInduction :- returns 1 & the item if the induction is found */
738 /*-----------------------------------------------------------------*/
740 DEFSETFUNC (findInduction)
742 induction *ip = item;
743 V_ARG (operand *, sym);
744 V_ARG (induction **, ipp);
746 if (isOperandEqual (ip->sym, sym))
755 /*-----------------------------------------------------------------*/
756 /* findDefInRegion - finds the definition within the region */
757 /*-----------------------------------------------------------------*/
759 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
763 /* for all blocks in the region */
764 for (lBlock = setFirstItem (regBlocks); lBlock;
765 lBlock = setNextItem (regBlocks))
768 /* if a definition for this exists */
769 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
773 /* go thru the instruction chain to find it */
774 for (ic = lBlock->sch; ic; ic = ic->next)
775 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
787 /*-----------------------------------------------------------------*/
788 /* addPostLoopBlock - add a ebblock before the successors of the */
790 /*-----------------------------------------------------------------*/
792 addPostLoopBlock (region *loopReg, ebbIndex *ebbi, iCode *ic)
797 /* if the number of exits is greater than one then
798 we use another trick: we will create an intersection
799 of succesors of the exits, then take those that are not
800 part of the loop and have dfNumber greater loop entry (eblock),
801 insert a new predecessor postLoopBlk before them and add
802 a copy of ic in the new block. The postLoopBlk in between
803 is necessary, because the old successors of the loop exits can
804 be successors of other blocks too: see bug-136564. */
806 /* loopSuccs now contains intersection
807 of all the loops successors */
808 loopSuccs = intersectLoopSucc (loopReg->exits, ebbi->dfOrder);
812 for (i = 0; i < loopSuccs->size; i++)
814 eBBlock *eblock = NULL;
815 eBBlock *postLoopBlk;
819 if (!bitVectBitValue (loopSuccs, i))
822 /* Need to search for bbnum == i since ebbi->dfOrder is
823 sorted by dfnum; a direct index won't do. */
824 for (j = 0; j < ebbi->count; j++)
825 if (ebbi->dfOrder[j]->bbnum == i)
827 eblock = ebbi->dfOrder[j];
832 /* if the successor does not belong to the loop
833 and will be executed after the loop : then
834 add a definition to the block */
835 if (isinSet (loopReg->regBlocks, eblock))
837 if (eblock->dfnum <= loopReg->entry->dfnum)
840 /* look for an existing loopExitBlock */
841 if (strncmp (LOOPEXITLBL,
842 eblock->entryLabel->name,
843 sizeof(LOOPEXITLBL) - 1) == 0)
845 /* reuse the existing one */
846 postLoopBlk = eblock;
850 /* create and insert a new eBBlock.
851 Damn, that's messy ... */
856 postLoopBlk = neweBBlock();
858 /* create a loopExit-label */
859 postLoopBlk->entryLabel = newiTempLoopHeaderLabel (0);
861 /* increase bbnum for all blocks after
862 (and including) eblock */
863 for (i = 0; i < ebbi->count; i++)
865 if (ebbi->bbOrder[i]->bbnum >= eblock->bbnum)
866 ++ebbi->bbOrder[i]->bbnum;
868 /* insert postLoopBlk before bbnum */
869 postLoopBlk->bbnum = eblock->bbnum - 1;
873 /* these arrays need one more block, which ... */
874 ebbi->bbOrder = Safe_realloc (ebbi->bbOrder,
875 (ebbi->count + 1) * sizeof(eBBlock *));
876 /* ... must be initialized with 0 */
877 ebbi->bbOrder[ebbi->count] = NULL;
878 /* move the blocks up ... */
879 memmove (&ebbi->bbOrder[postLoopBlk->bbnum + 1],
880 &ebbi->bbOrder[postLoopBlk->bbnum],
881 (ebbi->count - postLoopBlk->bbnum - 1) * sizeof(eBBlock *));
882 /* ... and insert postLoopBlk */
883 ebbi->bbOrder[postLoopBlk->bbnum] = postLoopBlk;
885 /* just add postLoopBlk at the end of dfOrder,
886 computeControlFlow() will compute the new dfnum */
887 ebbi->dfOrder = Safe_realloc (ebbi->dfOrder,
888 (ebbi->count + 1) * sizeof(eBBlock *));
889 ebbi->dfOrder[ebbi->count] = NULL;
890 ebbi->dfOrder[ebbi->count - 1] = postLoopBlk;
892 /* copy loop information from eblock to postLoopBlk */
893 if (eblock->partOfLoop)
895 postLoopBlk->partOfLoop = eblock->partOfLoop;
896 /* add postLoopBlk to loop region */
897 addSetHead (&postLoopBlk->partOfLoop->regBlocks, postLoopBlk);
900 /* go through loop exits and replace the old exit block eblock
901 with the new postLoopBlk */
902 for (ebpi = setFirstItem (loopReg->exits);
904 ebpi = setNextItem (loopReg->exits))
906 /* replace old label with new label */
907 replaceLabel (ebpi, eblock->entryLabel, postLoopBlk->entryLabel);
910 /* now eblock is replaced by postLoopBlk.
911 It's possible, that eblock has an immediate predecessor
912 (with ebpi->bbnum + 1 == eblock->bbnum), which isn't part of the
913 loop. This predecessor must stay predecessor of eblock, not of
914 postLoopBlk. But now postLoopBlk is in between, therefore a GOTO
915 from this predecessor to eblock must be appended.
916 Example: bug-136564.c */
918 /* take all predecessors and subtract the loop exits */
919 oldPredList = subtractFromSet (eblock->predList,
922 for (ebpi = setFirstItem (oldPredList);
924 ebpi = setNextItem (oldPredList))
926 /* Is it an immediate predecessor (without GOTO)?
927 All other predecessors end with a
928 GOTO, IF, IFX or JUMPTABLE: nothing to to do */
929 if (ebpi->bbnum + 1 == postLoopBlk->bbnum)
931 /* insert goto to old predecessor of eblock */
932 newic = newiCodeLabelGoto (GOTO, eblock->entryLabel);
933 addiCodeToeBBlock (ebpi, newic, NULL);
934 break; /* got it, only one is possible */
940 postLoopBlk->ech = newiCodeLabelGoto (LABEL, postLoopBlk->entryLabel);
943 /* create the definition in postLoopBlk */
944 newic = newiCode ('=', NULL, operandFromOperand (IC_RIGHT (ic)));
945 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
946 /* maintain data flow */
947 OP_DEFS(IC_RESULT (newic)) = bitVectSetBit (OP_DEFS (IC_RESULT (newic)),
949 OP_USES(IC_RIGHT (newic)) = bitVectSetBit (OP_USES (IC_RIGHT (newic)),
953 addiCodeToeBBlock (postLoopBlk, newic, NULL);
954 postLoopBlk->sch->filename =
955 postLoopBlk->ech->filename = eblock->sch->filename;
956 postLoopBlk->sch->lineno =
957 postLoopBlk->ech->lineno = eblock->sch->lineno;
959 /* outDefs is needed by computeControlFlow(), anything
960 else will be set up by computeControlFlow() */
961 postLoopBlk->outDefs = bitVectSetBit (postLoopBlk->outDefs, newic->key);
962 } /* for (i = 0; i < loopSuccs->size; i++) */
964 /* the postLoopBlk and the induction significantly
965 changed the control flow, recompute it */
966 computeControlFlow (ebbi);
969 /*-----------------------------------------------------------------*/
970 /* basicInduction - finds the basic induction variables in a loop */
971 /*-----------------------------------------------------------------*/
973 basicInduction (region * loopReg, ebbIndex * ebbi)
978 /* i.e. all assignments of the form a := a +/- const */
979 /* for all blocks within the loop do */
980 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
981 lBlock = setNextItem (loopReg->regBlocks))
986 /* for all instructions in the blocks do */
987 for (ic = lBlock->sch; ic; ic = ic->next)
994 eBBlock *owner = NULL;
998 /* To find an induction variable, we need to */
999 /* find within the loop three iCodes in this */
1002 /* ddic: iTempB := symbolVar */
1003 /* dic: iTempA := iTempB + lit */
1004 /* or iTempA := iTempB - lit */
1005 /* or iTempA := lit + iTempB */
1006 /* ic: symbolVar := iTempA */
1008 /* (symbolVar may also be an iTemp if it is */
1009 /* register equivalent) */
1011 /* look for assignments of the form */
1012 /* symbolVar := iTempNN */
1016 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
1017 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
1020 if (isOperandGlobal (IC_RESULT (ic)))
1023 if (!IS_ITEMP (IC_RIGHT (ic)))
1026 /* if it has multiple assignments within the loop then skip */
1027 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1030 /* if the address of this was taken inside the loop then continue */
1031 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
1034 /* Only consider variables with integral type. */
1035 /* (2004/12/06 - EEP - ds390 fails regression tests unless */
1036 /* pointers are also considered for induction (due to some */
1037 /* register alloctaion bugs). Remove !IS_PTR clause when */
1038 /* that gets fixed) */
1039 optype = operandType (IC_RIGHT (ic));
1040 if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
1043 /* find the definition for the result in the block */
1044 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
1045 IC_RIGHT (ic), &owner)))
1048 /* if not +/- continue */
1049 if (dic->op != '+' && dic->op != '-')
1052 /* make sure definition is of the form a +/- c */
1053 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
1056 /* make sure the definition found is the only one */
1057 if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
1060 if (IS_OP_LITERAL (IC_RIGHT (dic)))
1062 aSym = IC_LEFT (dic);
1063 litValue = (long) operandLitValue (IC_RIGHT (dic));
1067 /* For minus, the literal must not be on the left side. */
1068 /* (Actually, this case could be handled, but it's probably */
1069 /* not worth the extra code) */
1072 aSym = IC_RIGHT (dic);
1073 litValue = (long) operandLitValue (IC_LEFT (dic));
1076 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
1077 !isOperandEqual (IC_RIGHT (ic), aSym))
1080 /* find the definition for this and check */
1081 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
1085 if (ddic->op != '=')
1088 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
1089 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
1093 /* if the right hand side has more than one usage then
1094 don't make it an induction (will have to think some more) */
1095 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
1098 /* if the definition is volatile then it cannot be
1099 an induction object */
1100 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
1101 isOperandVolatile (IC_RESULT (ic), FALSE))
1104 /* whew !! that was a lot of work to find the definition */
1105 /* create an induction object */
1106 indIc = newiCode ('=', NULL, IC_RESULT (ic));
1107 indIc->filename = ic->filename;
1108 indIc->lineno = ic->lineno;
1109 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
1110 IC_RESULT (indIc)->isaddr = 0;
1111 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1112 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
1114 /* replace the inducted variable by the iTemp */
1115 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
1116 /* ic should now be moved to the exit block(s) */
1118 nexits = elementsInSet (loopReg->exits);
1121 /* this is a endless loop without exits: there's
1122 no need to restore the inducted variable */
1123 iCode *saveic = ic->prev;
1125 /* ic will be removed by killDeadCode() too,
1126 but it's a nice to see a clean dumploop now. */
1127 remiCodeFromeBBlock (lBlock, ic);
1128 /* clear the definition */
1129 bitVectUnSetBit (lBlock->defSet, ic->key);
1133 addPostLoopBlock (loopReg, ebbi, ic);
1134 addSet (&indVars, ip);
1136 } /* end of all blocks for basic induction variables */
1141 /*-----------------------------------------------------------------*/
1142 /* loopInduction - remove induction variables from a loop */
1143 /*-----------------------------------------------------------------*/
1145 loopInduction (region * loopReg, ebbIndex * ebbi)
1148 eBBlock *lBlock, *owner, *lastBlock = NULL;
1149 set *indVars = NULL;
1150 set *basicInd = NULL;
1152 if (loopReg->entry->preHeader == NULL)
1155 /* we first determine the basic Induction variables */
1156 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbi));
1158 /* find other induction variables : by other we mean definitions of */
1159 /* the form x := y (* | / ) <constant> .. we will move this one to */
1160 /* beginning of the loop and reduce strength i.e. replace with +/- */
1161 /* these expensive expressions: OH! and y must be induction too */
1162 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1164 lBlock = setNextItem (loopReg->regBlocks))
1167 iCode *ic, *indIc, *dic;
1170 /* last block is the one with the highest block
1172 if (lastBlock->bbnum < lBlock->bbnum)
1175 for (ic = lBlock->sch; ic; ic = ic->next)
1180 /* consider only * & / */
1181 if (ic->op != '*' && ic->op != '/')
1184 /* only consider variables with integral type */
1185 if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1188 /* if the result has more definitions then */
1189 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1192 /* check if the operands are what we want */
1193 /* i.e. one of them an symbol the other a literal */
1194 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1195 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1198 if (IS_SYMOP (IC_LEFT (ic)))
1200 aSym = IC_LEFT (ic);
1201 litVal = (long) operandLitValue (IC_RIGHT (ic));
1205 /* For division, the literal must not be on the left side */
1208 aSym = IC_RIGHT (ic);
1209 litVal = (long) operandLitValue (IC_LEFT (ic));
1213 /* check if this is an induction variable */
1214 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1217 /* ask port for size not worth if native instruction
1218 exist for multiply & divide */
1219 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1220 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1223 /* if this is a division then the remainder should be zero
1224 for it to be inducted */
1225 if (ic->op == '/' && (ip->cval % litVal))
1228 /* create the iCode to be placed in the loop header */
1229 /* and create the induction object */
1231 /* create an instruction */
1232 /* this will be put on the loop header */
1233 indIc = newiCode (ic->op,
1234 operandFromOperand (aSym),
1235 operandFromLit (litVal));
1236 indIc->filename = ic->filename;
1237 indIc->lineno = ic->lineno;
1238 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1239 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1241 /* keep track of the inductions */
1242 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1243 (ip->cval / litVal));
1246 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1248 /* Replace mul/div with assignment to self; killDeadCode() will */
1249 /* clean this up since we can't use remiCodeFromeBBlock() here. */
1251 IC_LEFT (ic) = NULL;
1252 IC_RIGHT (ic) = IC_RESULT (ic);
1254 /* Insert an update of the induction variable just before */
1255 /* the update of the basic induction variable. */
1256 indIc = newiCode (ip->op,
1257 operandFromOperand (IC_RESULT (ic)),
1258 operandFromLit (litVal));
1259 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1261 dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1263 addiCodeToeBBlock (owner, indIc, dic);
1268 /* if we have some induction variables then */
1271 eBBlock *preHdr = loopReg->entry->preHeader;
1272 iCode *icFirst = NULL, *icLast = NULL;
1274 bitVect *indVect = NULL;
1276 /* create an iCode chain from it */
1277 for (ip = setFirstItem (indVars);
1279 ip = setNextItem (indVars))
1281 indVect = bitVectSetBit (indVect, ip->ic->key);
1282 ip->ic->filename = preHdr->ech->filename;
1283 ip->ic->lineno = preHdr->ech->lineno;
1288 icLast->next = ip->ic;
1289 ip->ic->prev = icLast;
1297 /* add the instruction chain to the end of the */
1298 /* preheader for this loop */
1299 preHdr->ech->next = icFirst;
1300 icFirst->prev = preHdr->ech;
1301 preHdr->ech = icLast;
1302 icLast->next = NULL;
1304 /* add the induction variable vector to the last
1305 block in the loop */
1306 lastBlock->isLastInLoop = 1;
1307 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1310 setToNull ((void *) &indVars);
1314 /*-----------------------------------------------------------------*/
1315 /* mergeRegions - will merge region with same entry point */
1316 /*-----------------------------------------------------------------*/
1318 DEFSETFUNC (mergeRegions)
1320 region *theLoop = item;
1321 V_ARG (set *, allRegion);
1324 /* if this has already been merged then do nothing */
1325 if (theLoop->merged)
1328 /* go thru all the region and check if any of them have the */
1329 /* entryPoint as the Loop */
1330 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1336 if (lp->entry == theLoop->entry)
1338 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1339 lp->regBlocks, THROW_DEST);
1347 /*-----------------------------------------------------------------*/
1348 /* ifMerged - return 1 if the merge flag is 1 */
1349 /*-----------------------------------------------------------------*/
1351 DEFSETFUNC (ifMerged)
1358 /*-----------------------------------------------------------------*/
1359 /* mergeInnerLoops - will merge into body when entry is present */
1360 /*-----------------------------------------------------------------*/
1362 DEFSETFUNC (mergeInnerLoops)
1364 region *theLoop = item;
1365 V_ARG (set *, allRegion);
1366 V_ARG (int *, maxDepth);
1369 /* check if the entry point is present in the body of any */
1370 /* loop then put the body of this loop into the outer loop */
1371 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1377 if (isinSet (lp->regBlocks, theLoop->entry))
1379 lp->containsLoops += theLoop->containsLoops + 1;
1380 if (lp->containsLoops > (*maxDepth))
1381 *maxDepth = lp->containsLoops;
1383 lp->regBlocks = unionSets (lp->regBlocks,
1384 theLoop->regBlocks, THROW_DEST);
1392 /*-----------------------------------------------------------------*/
1393 /* createLoopRegions - will detect and create a set of natural loops */
1394 /*-----------------------------------------------------------------*/
1396 createLoopRegions (ebbIndex * ebbi)
1398 set *allRegion = NULL; /* set of all loops */
1399 hTab *orderedLoops = NULL;
1404 /* get all the back edges in the graph */
1405 if (!applyToSet (graphEdges, backEdges, &bEdges))
1406 return 0; /* found no loops */
1408 /* for each of these back edges get the blocks that */
1409 /* constitute the loops */
1410 applyToSet (bEdges, createLoop, &allRegion);
1412 /* now we will create regions from these loops */
1413 /* loops with the same entry points are considered to be the */
1414 /* same loop & they are merged. If the entry point of a loop */
1415 /* is found in the body of another loop then , all the blocks */
1416 /* in that loop are added to the loops containing the header */
1417 applyToSet (allRegion, mergeRegions, allRegion);
1419 /* delete those already merged */
1420 deleteItemIf (&allRegion, ifMerged);
1422 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1425 /* now create all the exits .. also */
1426 /* create an ordered set of loops */
1427 /* i.e. we process loops in the inner to outer order */
1428 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1430 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1431 lp->regBlocks, &lp->exits,
1432 (maxDepth - lp->containsLoops), lp);
1434 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1437 return orderedLoops;
1440 /*-----------------------------------------------------------------*/
1441 /* loopOptimizations - identify region & remove invariants & ind */
1442 /*-----------------------------------------------------------------*/
1444 loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
1450 /* if no loop optimizations requested */
1451 if (!optimize.loopInvariant &&
1452 !optimize.loopInduction)
1455 /* now we process the loops inner to outer order */
1456 /* this is essential to maintain data flow information */
1457 /* the other choice is an ugly iteration for the depth */
1458 /* of the loops would hate that */
1459 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1460 lp = hTabNextItem (orderedLoops, &k))
1463 if (optimize.loopInvariant)
1464 change += loopInvariants (lp, ebbi);
1466 if (optimize.loopInduction)
1467 change += loopInduction (lp, ebbi);