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)
470 /* now we go thru the instructions of this block and */
471 /* collect those instructions with invariant operands */
472 for (ic = lBlock->sch; ic; ic = ic->next)
478 /* TODO this is only needed if the call is between
479 here and the definition, but I am too lazy to do that now */
481 /* if there are function calls in this block */
484 /* if this is a pointer get */
490 /* if this is an assignment from a global */
491 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic)))
497 * if this is an assignment to a global */
498 if (ic->op=='=' && isOperandGlobal(IC_RESULT(ic)))
504 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
507 /* iTemp assignment from a literal may be invariant, but it
508 will needlessly increase register pressure if the
509 iCode(s) that use this iTemp are not also invariant */
510 if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
511 && IS_OP_LITERAL (IC_RIGHT (ic)))
514 /* if result is volatile then skip */
515 if (IC_RESULT (ic) &&
516 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
517 IS_OP_PARM (IC_RESULT (ic))))
520 /* if result depends on a volatile then skip */
521 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
522 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
528 /* if address of then it is an invariant */
529 if (ic->op == ADDRESS_OF &&
530 IS_SYMOP (IC_LEFT (ic)) &&
531 IS_AGGREGATE (operandType (IC_LEFT (ic))))
537 /* check if left operand is an invariant */
538 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)) &&
539 /* if this is a pointer get then make sure
540 that the pointer set does not exist in
543 applyToSet (theLoop->regBlocks, pointerAssigned, IC_LEFT (ic)))
549 /* do the same for right */
550 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
552 /* if this is a POINTER_GET then special case, make sure all
553 usages within the loop are POINTER_GET any other usage
554 would mean that this is not an invariant , since the pointer
555 could then be passed as a parameter */
556 if (POINTER_GET (ic) &&
557 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
561 /* if both the left & right are invariants : then check that */
562 /* this definition exists in the out definition of all the */
563 /* blocks, this will ensure that this is not assigned any */
564 /* other value in the loop, and not used in this block */
565 /* prior to this definition which means only this definition */
566 /* is used in this loop */
567 if (lin && rin && IC_RESULT (ic))
570 set *lSet = setFromSet (theLoop->regBlocks);
572 /* if this block does not dominate all exits */
573 /* make sure this defintion is not used anywhere else */
577 if (isOperandGlobal (IC_RESULT (ic)))
579 /* for successors for all exits */
580 for (sBlock = setFirstItem (theLoop->exits); sBlock;
581 sBlock = setNextItem (theLoop->exits))
584 for (i = 0; i < count; ebbs[i++]->visited = 0);
586 if (applyToSet (sBlock->succList, isDefAlive, ic))
590 /* we have found usage */
595 /* now make sure this is the only definition */
596 for (sBlock = setFirstItem (lSet); sBlock;
597 sBlock = setNextItem (lSet))
603 /* if this is the block make sure the definition */
604 /* reaches the end of the block */
605 if (sBlock == lBlock)
607 if (!ifDiCodeIs (sBlock->outExprs, ic))
610 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
613 /* Check that this definition is not assigned */
614 /* any other value in this block. Also check */
615 /* that any usage in the block is dominated by */
616 /* by this definition. */
617 defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
619 for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
623 if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
626 else if (ic2->op == JUMPTABLE)
628 if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
633 if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
635 if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
637 if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
639 /* If used before this definition, might not be invariant */
640 if ((ic == ic2) && used)
643 if (used && !defDominates)
646 if (ic2) /* found another definition or a usage before the definition */
651 continue; /* another definition present in the block */
654 /* now check if it exists in the in of this block */
655 /* if not then it was killed before this instruction */
656 if (!bitVectBitValue (lBlock->inDefs, ic->key))
659 /* now we know it is a true invariant */
660 /* remove it from the insts chain & put */
661 /* in the invariant set */
663 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
664 SPIL_LOC (IC_RESULT (ic)) = NULL;
665 remiCodeFromeBBlock (lBlock, ic);
667 /* maintain the data flow */
668 /* this means removing from definition from the */
669 /* defset of this block and adding it to the */
670 /* inexpressions of all blocks within the loop */
671 bitVectUnSetBit (lBlock->defSet, ic->key);
672 bitVectUnSetBit (lBlock->ldefs, ic->key);
673 ivar = newCseDef (IC_RESULT (ic), ic);
674 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
675 addSet (&lInvars, ivar);
678 } /* for all loop blocks */
680 /* if we have some invariants then */
683 eBBlock *preHdr = theLoop->entry->preHeader;
684 iCode *icFirst = NULL, *icLast = NULL;
687 /* create an iCode chain from it */
688 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
691 /* maintain data flow .. add it to the */
692 /* ldefs defSet & outExprs of the preheader */
693 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
694 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
695 cdp->diCode->filename = preHdr->ech->filename;
696 cdp->diCode->lineno = preHdr->ech->lineno;
697 addSetHead (&preHdr->outExprs, cdp);
701 icFirst = cdp->diCode;
704 icLast->next = cdp->diCode;
705 cdp->diCode->prev = icLast;
706 icLast = cdp->diCode;
709 icLast = cdp->diCode;
713 /* add the instruction chain to the end of the
714 preheader for this loop, preheaders will always
715 have atleast a label */
716 preHdr->ech->next = icFirst;
717 icFirst->prev = preHdr->ech;
718 preHdr->ech = icLast;
725 /*-----------------------------------------------------------------*/
726 /* addressTaken - returns true if the symbol is found in the addrof */
727 /*-----------------------------------------------------------------*/
729 addressTaken (set * sset, operand * sym)
735 for (loop = sset; loop; loop = loop->next)
741 if (isOperandEqual ((operand *) loop2->item, sym))
751 /*-----------------------------------------------------------------*/
752 /* findInduction :- returns 1 & the item if the induction is found */
753 /*-----------------------------------------------------------------*/
755 DEFSETFUNC (findInduction)
757 induction *ip = item;
758 V_ARG (operand *, sym);
759 V_ARG (induction **, ipp);
761 if (isOperandEqual (ip->sym, sym))
770 /*-----------------------------------------------------------------*/
771 /* findDefInRegion - finds the definition within the region */
772 /*-----------------------------------------------------------------*/
774 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
778 /* for all blocks in the region */
779 for (lBlock = setFirstItem (regBlocks); lBlock;
780 lBlock = setNextItem (regBlocks))
783 /* if a definition for this exists */
784 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
788 /* go thru the instruction chain to find it */
789 for (ic = lBlock->sch; ic; ic = ic->next)
790 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
802 /*-----------------------------------------------------------------*/
803 /* addPostLoopBlock - add a ebblock before the successors of the */
805 /*-----------------------------------------------------------------*/
807 addPostLoopBlock (region *loopReg, ebbIndex *ebbi, iCode *ic)
812 /* if the number of exits is greater than one then
813 we use another trick: we will create an intersection
814 of succesors of the exits, then take those that are not
815 part of the loop and have dfNumber greater loop entry (eblock),
816 insert a new predecessor postLoopBlk before them and add
817 a copy of ic in the new block. The postLoopBlk in between
818 is necessary, because the old successors of the loop exits can
819 be successors of other blocks too: see bug-136564. */
821 /* loopSuccs now contains intersection
822 of all the loops successors */
823 loopSuccs = intersectLoopSucc (loopReg->exits, ebbi->dfOrder);
827 for (i = 0; i < loopSuccs->size; i++)
829 eBBlock *eblock = NULL;
830 eBBlock *postLoopBlk;
834 if (!bitVectBitValue (loopSuccs, i))
837 /* Need to search for bbnum == i since ebbi->dfOrder is
838 sorted by dfnum; a direct index won't do. */
839 for (j = 0; j < ebbi->count; j++)
840 if (ebbi->dfOrder[j]->bbnum == i)
842 eblock = ebbi->dfOrder[j];
847 /* if the successor does not belong to the loop
848 and will be executed after the loop : then
849 add a definition to the block */
850 if (isinSet (loopReg->regBlocks, eblock))
852 if (eblock->dfnum <= loopReg->entry->dfnum)
855 /* look for an existing loopExitBlock */
856 if (strncmp (LOOPEXITLBL,
857 eblock->entryLabel->name,
858 sizeof(LOOPEXITLBL) - 1) == 0)
860 /* reuse the existing one */
861 postLoopBlk = eblock;
865 /* create and insert a new eBBlock.
866 Damn, that's messy ... */
871 postLoopBlk = neweBBlock();
873 /* create a loopExit-label */
874 postLoopBlk->entryLabel = newiTempLoopHeaderLabel (0);
876 /* increase bbnum for all blocks after
877 (and including) eblock */
878 for (i = 0; i < ebbi->count; i++)
880 if (ebbi->bbOrder[i]->bbnum >= eblock->bbnum)
881 ++ebbi->bbOrder[i]->bbnum;
883 /* insert postLoopBlk before bbnum */
884 postLoopBlk->bbnum = eblock->bbnum - 1;
888 /* these arrays need one more block, which ... */
889 ebbi->bbOrder = Safe_realloc (ebbi->bbOrder,
890 (ebbi->count + 1) * sizeof(eBBlock *));
891 /* ... must be initialized with 0 */
892 ebbi->bbOrder[ebbi->count] = NULL;
893 /* move the blocks up ... */
894 memmove (&ebbi->bbOrder[postLoopBlk->bbnum + 1],
895 &ebbi->bbOrder[postLoopBlk->bbnum],
896 (ebbi->count - postLoopBlk->bbnum - 1) * sizeof(eBBlock *));
897 /* ... and insert postLoopBlk */
898 ebbi->bbOrder[postLoopBlk->bbnum] = postLoopBlk;
900 /* just add postLoopBlk at the end of dfOrder,
901 computeControlFlow() will compute the new dfnum */
902 ebbi->dfOrder = Safe_realloc (ebbi->dfOrder,
903 (ebbi->count + 1) * sizeof(eBBlock *));
904 ebbi->dfOrder[ebbi->count] = NULL;
905 ebbi->dfOrder[ebbi->count - 1] = postLoopBlk;
907 /* copy loop information from eblock to postLoopBlk */
908 if (eblock->partOfLoop)
910 postLoopBlk->partOfLoop = eblock->partOfLoop;
911 /* add postLoopBlk to loop region */
912 addSetHead (&postLoopBlk->partOfLoop->regBlocks, postLoopBlk);
915 /* go through loop exits and replace the old exit block eblock
916 with the new postLoopBlk */
917 for (ebpi = setFirstItem (loopReg->exits);
919 ebpi = setNextItem (loopReg->exits))
921 /* replace old label with new label */
922 replaceLabel (ebpi, eblock->entryLabel, postLoopBlk->entryLabel);
925 /* now eblock is replaced by postLoopBlk.
926 It's possible, that eblock has an immediate predecessor
927 (with ebpi->bbnum + 1 == eblock->bbnum), which isn't part of the
928 loop. This predecessor must stay predecessor of eblock, not of
929 postLoopBlk. But now postLoopBlk is in between, therefore a GOTO
930 from this predecessor to eblock must be appended.
931 Example: bug-136564.c */
933 /* take all predecessors and subtract the loop exits */
934 oldPredList = subtractFromSet (eblock->predList,
937 for (ebpi = setFirstItem (oldPredList);
939 ebpi = setNextItem (oldPredList))
941 /* Is it an immediate predecessor (without GOTO)?
942 All other predecessors end with a
943 GOTO, IF, IFX or JUMPTABLE: nothing to to do */
944 if (ebpi->bbnum + 1 == postLoopBlk->bbnum)
946 /* insert goto to old predecessor of eblock */
947 newic = newiCodeLabelGoto (GOTO, eblock->entryLabel);
948 addiCodeToeBBlock (ebpi, newic, NULL);
949 break; /* got it, only one is possible */
955 postLoopBlk->ech = newiCodeLabelGoto (LABEL, postLoopBlk->entryLabel);
958 /* create the definition in postLoopBlk */
959 newic = newiCode ('=', NULL, operandFromOperand (IC_RIGHT (ic)));
960 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
961 /* maintain data flow */
962 OP_DEFS(IC_RESULT (newic)) = bitVectSetBit (OP_DEFS (IC_RESULT (newic)),
964 OP_USES(IC_RIGHT (newic)) = bitVectSetBit (OP_USES (IC_RIGHT (newic)),
968 addiCodeToeBBlock (postLoopBlk, newic, NULL);
969 postLoopBlk->sch->filename =
970 postLoopBlk->ech->filename = eblock->sch->filename;
971 postLoopBlk->sch->lineno =
972 postLoopBlk->ech->lineno = eblock->sch->lineno;
974 /* outDefs is needed by computeControlFlow(), anything
975 else will be set up by computeControlFlow() */
976 postLoopBlk->outDefs = bitVectSetBit (postLoopBlk->outDefs, newic->key);
977 } /* for (i = 0; i < loopSuccs->size; i++) */
979 /* the postLoopBlk and the induction significantly
980 changed the control flow, recompute it */
981 computeControlFlow (ebbi);
984 /*-----------------------------------------------------------------*/
985 /* basicInduction - finds the basic induction variables in a loop */
986 /*-----------------------------------------------------------------*/
988 basicInduction (region * loopReg, ebbIndex * ebbi)
993 /* i.e. all assignments of the form a := a +/- const */
994 /* for all blocks within the loop do */
995 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
996 lBlock = setNextItem (loopReg->regBlocks))
1001 /* for all instructions in the blocks do */
1002 for (ic = lBlock->sch; ic; ic = ic->next)
1009 eBBlock *owner = NULL;
1013 /* To find an induction variable, we need to */
1014 /* find within the loop three iCodes in this */
1017 /* ddic: iTempB := symbolVar */
1018 /* dic: iTempA := iTempB + lit */
1019 /* or iTempA := iTempB - lit */
1020 /* or iTempA := lit + iTempB */
1021 /* ic: symbolVar := iTempA */
1023 /* (symbolVar may also be an iTemp if it is */
1024 /* register equivalent) */
1026 /* look for assignments of the form */
1027 /* symbolVar := iTempNN */
1031 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
1032 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
1035 if (isOperandGlobal (IC_RESULT (ic)))
1038 if (!IS_ITEMP (IC_RIGHT (ic)))
1041 /* if it has multiple assignments within the loop then skip */
1042 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1045 /* if the address of this was taken inside the loop then continue */
1046 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
1049 /* Only consider variables with integral type. */
1050 /* (2004/12/06 - EEP - ds390 fails regression tests unless */
1051 /* pointers are also considered for induction (due to some */
1052 /* register alloctaion bugs). Remove !IS_PTR clause when */
1053 /* that gets fixed) */
1054 optype = operandType (IC_RIGHT (ic));
1055 if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
1058 /* find the definition for the result in the block */
1059 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
1060 IC_RIGHT (ic), &owner)))
1063 /* if not +/- continue */
1064 if (dic->op != '+' && dic->op != '-')
1067 /* make sure definition is of the form a +/- c */
1068 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
1071 /* make sure the definition found is the only one */
1072 if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
1075 if (IS_OP_LITERAL (IC_RIGHT (dic)))
1077 aSym = IC_LEFT (dic);
1078 litValue = (long) operandLitValue (IC_RIGHT (dic));
1082 /* For minus, the literal must not be on the left side. */
1083 /* (Actually, this case could be handled, but it's probably */
1084 /* not worth the extra code) */
1087 aSym = IC_RIGHT (dic);
1088 litValue = (long) operandLitValue (IC_LEFT (dic));
1091 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
1092 !isOperandEqual (IC_RIGHT (ic), aSym))
1095 /* find the definition for this and check */
1096 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
1100 if (ddic->op != '=')
1103 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
1104 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
1108 /* if the right hand side has more than one usage then
1109 don't make it an induction (will have to think some more) */
1110 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
1113 /* if the definition is volatile then it cannot be
1114 an induction object */
1115 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
1116 isOperandVolatile (IC_RESULT (ic), FALSE))
1119 /* whew !! that was a lot of work to find the definition */
1120 /* create an induction object */
1121 indIc = newiCode ('=', NULL, IC_RESULT (ic));
1122 indIc->filename = ic->filename;
1123 indIc->lineno = ic->lineno;
1124 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
1125 IC_RESULT (indIc)->isaddr = 0;
1126 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1127 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
1129 /* replace the inducted variable by the iTemp */
1130 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
1131 /* ic should now be moved to the exit block(s) */
1133 nexits = elementsInSet (loopReg->exits);
1136 /* this is a endless loop without exits: there's
1137 no need to restore the inducted variable */
1138 iCode *saveic = ic->prev;
1140 /* ic will be removed by killDeadCode() too,
1141 but it's a nice to see a clean dumploop now. */
1142 remiCodeFromeBBlock (lBlock, ic);
1143 /* clear the definition */
1144 bitVectUnSetBit (lBlock->defSet, ic->key);
1148 addPostLoopBlock (loopReg, ebbi, ic);
1149 addSet (&indVars, ip);
1151 } /* end of all blocks for basic induction variables */
1156 /*-----------------------------------------------------------------*/
1157 /* loopInduction - remove induction variables from a loop */
1158 /*-----------------------------------------------------------------*/
1160 loopInduction (region * loopReg, ebbIndex * ebbi)
1163 eBBlock *lBlock, *owner, *lastBlock = NULL;
1164 set *indVars = NULL;
1165 set *basicInd = NULL;
1167 if (loopReg->entry->preHeader == NULL)
1170 /* we first determine the basic Induction variables */
1171 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbi));
1173 /* find other induction variables : by other we mean definitions of */
1174 /* the form x := y (* | / ) <constant> .. we will move this one to */
1175 /* beginning of the loop and reduce strength i.e. replace with +/- */
1176 /* these expensive expressions: OH! and y must be induction too */
1177 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1179 lBlock = setNextItem (loopReg->regBlocks))
1182 iCode *ic, *indIc, *dic;
1185 /* last block is the one with the highest block
1187 if (lastBlock->bbnum < lBlock->bbnum)
1190 for (ic = lBlock->sch; ic; ic = ic->next)
1195 /* consider only * & / */
1196 if (ic->op != '*' && ic->op != '/')
1199 /* only consider variables with integral type */
1200 if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1203 /* if the result has more definitions then */
1204 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1207 /* check if the operands are what we want */
1208 /* i.e. one of them an symbol the other a literal */
1209 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1210 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1213 if (IS_SYMOP (IC_LEFT (ic)))
1215 aSym = IC_LEFT (ic);
1216 litVal = (long) operandLitValue (IC_RIGHT (ic));
1220 /* For division, the literal must not be on the left side */
1223 aSym = IC_RIGHT (ic);
1224 litVal = (long) operandLitValue (IC_LEFT (ic));
1228 /* check if this is an induction variable */
1229 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1232 /* ask port for size not worth if native instruction
1233 exist for multiply & divide */
1234 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1235 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1238 /* if this is a division then the remainder should be zero
1239 for it to be inducted */
1240 if (ic->op == '/' && (ip->cval % litVal))
1243 /* create the iCode to be placed in the loop header */
1244 /* and create the induction object */
1246 /* create an instruction */
1247 /* this will be put on the loop header */
1248 indIc = newiCode (ic->op,
1249 operandFromOperand (aSym),
1250 operandFromLit (litVal));
1251 indIc->filename = ic->filename;
1252 indIc->lineno = ic->lineno;
1253 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1254 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1256 /* keep track of the inductions */
1257 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1258 (ip->cval / litVal));
1261 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1263 /* Replace mul/div with assignment to self; killDeadCode() will */
1264 /* clean this up since we can't use remiCodeFromeBBlock() here. */
1266 IC_LEFT (ic) = NULL;
1267 IC_RIGHT (ic) = IC_RESULT (ic);
1269 /* Insert an update of the induction variable just before */
1270 /* the update of the basic induction variable. */
1271 indIc = newiCode (ip->op,
1272 operandFromOperand (IC_RESULT (ic)),
1273 operandFromLit (litVal));
1274 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1276 dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1278 addiCodeToeBBlock (owner, indIc, dic);
1283 /* if we have some induction variables then */
1286 eBBlock *preHdr = loopReg->entry->preHeader;
1287 iCode *icFirst = NULL, *icLast = NULL;
1289 bitVect *indVect = NULL;
1291 /* create an iCode chain from it */
1292 for (ip = setFirstItem (indVars);
1294 ip = setNextItem (indVars))
1296 indVect = bitVectSetBit (indVect, ip->ic->key);
1297 ip->ic->filename = preHdr->ech->filename;
1298 ip->ic->lineno = preHdr->ech->lineno;
1303 icLast->next = ip->ic;
1304 ip->ic->prev = icLast;
1312 /* add the instruction chain to the end of the */
1313 /* preheader for this loop */
1314 preHdr->ech->next = icFirst;
1315 icFirst->prev = preHdr->ech;
1316 preHdr->ech = icLast;
1317 icLast->next = NULL;
1319 /* add the induction variable vector to the last
1320 block in the loop */
1321 lastBlock->isLastInLoop = 1;
1322 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1325 setToNull ((void *) &indVars);
1329 /*-----------------------------------------------------------------*/
1330 /* mergeRegions - will merge region with same entry point */
1331 /*-----------------------------------------------------------------*/
1333 DEFSETFUNC (mergeRegions)
1335 region *theLoop = item;
1336 V_ARG (set *, allRegion);
1339 /* if this has already been merged then do nothing */
1340 if (theLoop->merged)
1343 /* go thru all the region and check if any of them have the */
1344 /* entryPoint as the Loop */
1345 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1351 if (lp->entry == theLoop->entry)
1353 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1354 lp->regBlocks, THROW_DEST);
1362 /*-----------------------------------------------------------------*/
1363 /* ifMerged - return 1 if the merge flag is 1 */
1364 /*-----------------------------------------------------------------*/
1366 DEFSETFUNC (ifMerged)
1373 /*-----------------------------------------------------------------*/
1374 /* mergeInnerLoops - will merge into body when entry is present */
1375 /*-----------------------------------------------------------------*/
1377 DEFSETFUNC (mergeInnerLoops)
1379 region *theLoop = item;
1380 V_ARG (set *, allRegion);
1381 V_ARG (int *, maxDepth);
1384 /* check if the entry point is present in the body of any */
1385 /* loop then put the body of this loop into the outer loop */
1386 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1392 if (isinSet (lp->regBlocks, theLoop->entry))
1394 lp->containsLoops += theLoop->containsLoops + 1;
1395 if (lp->containsLoops > (*maxDepth))
1396 *maxDepth = lp->containsLoops;
1398 lp->regBlocks = unionSets (lp->regBlocks,
1399 theLoop->regBlocks, THROW_DEST);
1407 /*-----------------------------------------------------------------*/
1408 /* createLoopRegions - will detect and create a set of natural loops */
1409 /*-----------------------------------------------------------------*/
1411 createLoopRegions (ebbIndex * ebbi)
1413 set *allRegion = NULL; /* set of all loops */
1414 hTab *orderedLoops = NULL;
1419 /* get all the back edges in the graph */
1420 if (!applyToSet (graphEdges, backEdges, &bEdges))
1421 return 0; /* found no loops */
1423 /* for each of these back edges get the blocks that */
1424 /* constitute the loops */
1425 applyToSet (bEdges, createLoop, &allRegion);
1427 /* now we will create regions from these loops */
1428 /* loops with the same entry points are considered to be the */
1429 /* same loop & they are merged. If the entry point of a loop */
1430 /* is found in the body of another loop then , all the blocks */
1431 /* in that loop are added to the loops containing the header */
1432 applyToSet (allRegion, mergeRegions, allRegion);
1434 /* delete those already merged */
1435 deleteItemIf (&allRegion, ifMerged);
1437 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1440 /* now create all the exits .. also */
1441 /* create an ordered set of loops */
1442 /* i.e. we process loops in the inner to outer order */
1443 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1445 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1446 lp->regBlocks, &lp->exits,
1447 (maxDepth - lp->containsLoops), lp);
1449 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1452 return orderedLoops;
1455 /*-----------------------------------------------------------------*/
1456 /* loopOptimizations - identify region & remove invariants & ind */
1457 /*-----------------------------------------------------------------*/
1459 loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
1465 /* if no loop optimizations requested */
1466 if (!optimize.loopInvariant &&
1467 !optimize.loopInduction)
1470 /* now we process the loops inner to outer order */
1471 /* this is essential to maintain data flow information */
1472 /* the other choice is an ugly iteration for the depth */
1473 /* of the loops would hate that */
1474 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1475 lp = hTabNextItem (orderedLoops, &k))
1478 if (optimize.loopInvariant)
1479 change += loopInvariants (lp, ebbi);
1481 if (optimize.loopInduction)
1482 change += loopInduction (lp, ebbi);