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));
67 /*-----------------------------------------------------------------*/
68 /* pinduction - prints induction */
69 /*-----------------------------------------------------------------*/
70 DEFSETFUNC (pinduction)
75 fprintf (stdout, "\t");
76 printOperand (ip->sym, stdout);
77 icTab = getTableEntry (ip->ic->op);
78 icTab->iCodePrint (stdout, ip->ic, icTab->printName);
79 fprintf (stdout, " %04d\n", (int) ip->cval);
83 /*-----------------------------------------------------------------*/
84 /* pregion - prints loop information */
85 /*-----------------------------------------------------------------*/
90 printf ("================\n");
91 printf (" loop with entry -- > ");
92 printEntryLabel (lp->entry, ap);
94 printf (" loop body --> ");
95 applyToSet (lp->regBlocks, printEntryLabel);
97 printf (" loop exits --> ");
98 applyToSet (lp->exits, printEntryLabel);
103 /*-----------------------------------------------------------------*/
104 /* backEdges - returns a list of back edges */
105 /*-----------------------------------------------------------------*/
106 DEFSETFUNC (backEdges)
109 V_ARG (set **, bEdges);
111 /* if this is a back edge ; to determine this we check */
112 /* to see if the 'to' is in the dominator list of the */
113 /* 'from' if yes then this is a back edge */
114 if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
116 addSetHead (bEdges, ep);
123 /*-----------------------------------------------------------------*/
124 /* intersectLoopSucc - returns intersection of loop Successors */
125 /*-----------------------------------------------------------------*/
127 intersectLoopSucc (set * lexits, eBBlock ** ebbs)
129 bitVect *succVect = NULL;
130 eBBlock *exit = setFirstItem (lexits);
135 succVect = bitVectCopy (exit->succVect);
137 for (exit = setNextItem (lexits); exit;
138 exit = setNextItem (lexits))
140 succVect = bitVectIntersect (succVect,
148 /*-----------------------------------------------------------------*/
149 /* loopInsert will insert a block into the loop set */
150 /*-----------------------------------------------------------------*/
152 loopInsert (set ** regionSet, eBBlock * block)
154 if (!isinSet (*regionSet, block))
156 addSetHead (regionSet, block);
157 STACK_PUSH (regionStack, block);
161 /*-----------------------------------------------------------------*/
162 /* insertIntoLoop - insert item into loop */
163 /*-----------------------------------------------------------------*/
164 DEFSETFUNC (insertIntoLoop)
167 V_ARG (set **, regionSet);
169 loopInsert (regionSet, ebp);
173 /*-----------------------------------------------------------------*/
174 /* isNotInBlocks - will return 1 if not is blocks */
175 /*-----------------------------------------------------------------*/
176 DEFSETFUNC (isNotInBlocks)
179 V_ARG (set *, blocks);
181 if (!isinSet (blocks, ebp))
187 /*-----------------------------------------------------------------*/
188 /* hasIncomingDefs - has definitions coming into the loop. i.e. */
189 /* check to see if the preheaders outDefs has any definitions */
190 /*-----------------------------------------------------------------*/
192 hasIncomingDefs (region * lreg, operand * op)
194 eBBlock *preHdr = lreg->entry->preHeader;
196 if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
201 /*-----------------------------------------------------------------*/
202 /* findLoopEndSeq - will return the sequence number of the last */
203 /* iCode with the maximum dfNumber in the region */
204 /*-----------------------------------------------------------------*/
206 findLoopEndSeq (region * lreg)
211 for (block = lblock = setFirstItem (lreg->regBlocks); block;
212 block = setNextItem (lreg->regBlocks))
214 if (block != lblock && block->lSeq > lblock->lSeq)
221 /*-----------------------------------------------------------------*/
222 /* addToExitsMarkDepth - will add the the exitSet all blocks that */
223 /* have exits, will also update the depth field in the blocks */
224 /*-----------------------------------------------------------------*/
225 DEFSETFUNC (addToExitsMarkDepth)
228 V_ARG (set *, loopBlocks);
229 V_ARG (set **, exits);
231 V_ARG (region *, lr);
233 /* mark the loop depth of this block */
235 if (ebp->depth<depth)
238 /* NOTE: here we will update only the inner most loop
239 that it is a part of */
240 if (!ebp->partOfLoop)
241 ebp->partOfLoop = lr;
243 /* if any of the successors go out of the loop then */
244 /* we add this one to the exits */
245 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
247 addSetHead (exits, ebp);
254 /*-----------------------------------------------------------------*/
255 /* createLoop - will create a set of region */
256 /*-----------------------------------------------------------------*/
257 DEFSETFUNC (createLoop)
260 V_ARG (set **, allRegion);
261 region *aloop = newRegion ();
264 /* make sure regionStack is empty */
265 while (!STACK_EMPTY (regionStack))
266 STACK_POP (regionStack);
268 /* add the entryBlock */
269 addSet (&aloop->regBlocks, ep->to);
270 loopInsert (&aloop->regBlocks, ep->from);
272 while (!STACK_EMPTY (regionStack))
274 block = STACK_POP (regionStack);
275 /* if block != entry */
277 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
280 aloop->entry = ep->to;
282 /* now add it to the set */
283 addSetHead (allRegion, aloop);
287 /*-----------------------------------------------------------------*/
288 /* dominatedBy - will return 1 if item is dominated by block */
289 /*-----------------------------------------------------------------*/
290 DEFSETFUNC (dominatedBy)
293 V_ARG (eBBlock *, block);
295 return bitVectBitValue (ebp->domVect, block->bbnum);
298 /*-----------------------------------------------------------------*/
299 /* addDefInExprs - adds an expression into the inexpressions */
300 /*-----------------------------------------------------------------*/
301 DEFSETFUNC (addDefInExprs)
304 V_ARG (cseDef *, cdp);
305 V_ARG (ebbIndex *, ebbi);
307 addSetHead (&ebp->inExprs, cdp);
308 cseBBlock (ebp, optimize.global_cse, ebbi);
312 /*-----------------------------------------------------------------*/
313 /* assignmentsToSym - for a set of blocks determine # time assigned */
314 /*-----------------------------------------------------------------*/
316 assignmentsToSym (set * sset, operand * sym)
320 set *blocks = setFromSet (sset);
322 for (ebp = setFirstItem (blocks); ebp;
323 ebp = setNextItem (blocks))
326 /* get all the definitions for this symbol
328 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
329 assigns += bitVectnBitsOn (defs);
330 setToNull ((void *) &defs);
338 /*-----------------------------------------------------------------*/
339 /* isOperandInvariant - determines if an operand is an invariant */
340 /*-----------------------------------------------------------------*/
342 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
345 /* operand is an invariant if it is a */
347 /* b. that have defintions reaching loop entry */
348 /* c. that are already defined as invariant */
349 /* d. has no assignments in the loop */
352 if (IS_OP_LITERAL (op))
354 else if (IS_SYMOP (op) &&
355 OP_SYMBOL (op)->addrtaken)
357 else if (ifDefSymIs (theLoop->entry->inExprs, op))
359 else if (ifDefSymIs (lInvars, op))
361 else if (IS_SYMOP (op) &&
362 !IS_OP_GLOBAL (op) &&
363 !IS_OP_VOLATILE (op) &&
364 assignmentsToSym (theLoop->regBlocks, op) == 0)
373 /*-----------------------------------------------------------------*/
374 /* pointerAssigned - will return 1 if pointer set found */
375 /*-----------------------------------------------------------------*/
376 DEFSETFUNC (pointerAssigned)
379 V_ARG (operand *, op);
384 if (bitVectBitValue (ebp->ptrsSet, op->key))
387 /* Unfortunately, one of the other pointer set operations */
388 /* may be using an alias of this operand, and the above */
389 /* test would miss it. To be thorough, some aliasing */
390 /* analysis should be done here. In the meantime, be */
391 /* conservative and assume any other pointer set operation */
393 if (!bitVectIsZero (ebp->ptrsSet))
399 /*-----------------------------------------------------------------*/
400 /* hasNonPtrUse - returns true if operand has non pointer usage */
401 /*-----------------------------------------------------------------*/
402 DEFSETFUNC (hasNonPtrUse)
405 V_ARG (operand *, op);
406 iCode *ic = usedInRemaining (op, ebp->sch);
408 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
415 /*-----------------------------------------------------------------*/
416 /* loopInvariants - takes loop invariants out of region */
417 /*-----------------------------------------------------------------*/
419 loopInvariants (region * theLoop, ebbIndex * ebbi)
421 eBBlock ** ebbs = ebbi->dfOrder;
422 int count = ebbi->count;
429 /* if the preHeader does not exist then do nothing */
430 /* or no exits then do nothing ( have to think about this situation */
431 if (theLoop->entry->preHeader == NULL ||
432 theLoop->exits == NULL)
435 /* we will do the elimination for those blocks */
436 /* in the loop that dominate all exits from the loop */
437 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
438 lBlock = setNextItem (theLoop->regBlocks))
445 /* mark the dominates all exits flag */
446 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
447 elementsInSet (theLoop->exits));
449 /* find out if we have a function call in this block */
450 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
456 /* now we go thru the instructions of this block and */
457 /* collect those instructions with invariant operands */
458 for (ic = lBlock->sch; ic; ic = ic->next)
464 /* TODO this is only needed if the call is between
465 here and the definition, but I am too lazy to do that now */
467 /* if there are function calls in this block */
470 /* if this is a pointer get */
471 if (POINTER_GET(ic)) {
475 /* if this is an assignment from a global */
476 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
481 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
484 /* iTemp assignment from a literal may be invariant, but it
485 will needlessly increase register pressure if the
486 iCode(s) that use this iTemp are not also invariant */
487 if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
488 && IS_OP_LITERAL (IC_RIGHT (ic)))
491 /* if result is volatile then skip */
492 if (IC_RESULT (ic) &&
493 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
494 IS_OP_PARM (IC_RESULT (ic))))
497 /* if result depends on a volatile then skip */
498 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
499 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
505 /* if address of then it is an invariant */
506 if (ic->op == ADDRESS_OF &&
507 IS_SYMOP (IC_LEFT (ic)) &&
508 IS_AGGREGATE (operandType (IC_LEFT (ic))))
511 /* check if left operand is an invariant */
512 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
513 /* if this is a pointer get then make sure
514 that the pointer set does not exist in
516 if (POINTER_GET (ic) &&
517 (applyToSet (theLoop->regBlocks,
518 pointerAssigned, IC_LEFT (ic))))
522 /* do the same for right */
523 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
525 /* if this is a POINTER_GET then special case, make sure all
526 usages within the loop are POINTER_GET any other usage
527 would mean that this is not an invariant , since the pointer
528 could then be passed as a parameter */
529 if (POINTER_GET (ic) &&
530 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
534 /* if both the left & right are invariants : then check that */
535 /* this definition exists in the out definition of all the */
536 /* blocks, this will ensure that this is not assigned any */
537 /* other value in the loop, and not used in this block */
538 /* prior to this definition which means only this definition */
539 /* is used in this loop */
540 if (lin && rin && IC_RESULT (ic))
543 set *lSet = setFromSet (theLoop->regBlocks);
545 /* if this block does not dominate all exits */
546 /* make sure this defintion is not used anywhere else */
550 if (isOperandGlobal (IC_RESULT (ic)))
552 /* for successors for all exits */
553 for (sBlock = setFirstItem (theLoop->exits); sBlock;
554 sBlock = setNextItem (theLoop->exits))
557 for (i = 0; i < count; ebbs[i++]->visited = 0);
559 if (applyToSet (sBlock->succList, isDefAlive, ic))
563 /* we have found usage */
568 /* now make sure this is the only definition */
569 for (sBlock = setFirstItem (lSet); sBlock;
570 sBlock = setNextItem (lSet))
576 /* if this is the block make sure the definition */
577 /* reaches the end of the block */
578 if (sBlock == lBlock)
580 if (!ifDiCodeIs (sBlock->outExprs, ic))
583 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
586 /* Check that this definition is not assigned */
587 /* any other value in this block. Also check */
588 /* that any usage in the block is dominated by */
589 /* by this definition. */
590 defDominates = bitVectBitValue (sBlock->domVect, lBlock->bbnum);
592 for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
596 if (isOperandEqual (IC_RESULT (ic), IC_COND (ic2)))
599 else if (ic2->op == JUMPTABLE)
601 if (isOperandEqual (IC_RESULT (ic), IC_JTCOND (ic2)))
606 if (IC_LEFT (ic2) && isOperandEqual (IC_RESULT (ic), IC_LEFT (ic2)))
608 if (IC_RIGHT (ic2) && isOperandEqual (IC_RESULT (ic), IC_RIGHT (ic2)))
610 if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
612 /* If used before this definition, might not be invariant */
613 if ((ic == ic2) && used)
616 if (used && !defDominates)
619 if (ic2) /* found another definition or a usage before the definition */
624 continue; /* another definition present in the block */
627 /* now check if it exists in the in of this block */
628 /* if not then it was killed before this instruction */
629 if (!bitVectBitValue (lBlock->inDefs, ic->key))
632 /* now we know it is a true invariant */
633 /* remove it from the insts chain & put */
634 /* in the invariant set */
636 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
637 SPIL_LOC (IC_RESULT (ic)) = NULL;
638 remiCodeFromeBBlock (lBlock, ic);
640 /* maintain the data flow */
641 /* this means removing from definition from the */
642 /* defset of this block and adding it to the */
643 /* inexpressions of all blocks within the loop */
644 bitVectUnSetBit (lBlock->defSet, ic->key);
645 bitVectUnSetBit (lBlock->ldefs, ic->key);
646 ivar = newCseDef (IC_RESULT (ic), ic);
647 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbi);
648 addSet (&lInvars, ivar);
651 } /* for all loop blocks */
653 /* if we have some invariants then */
656 eBBlock *preHdr = theLoop->entry->preHeader;
657 iCode *icFirst = NULL, *icLast = NULL;
660 /* create an iCode chain from it */
661 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
664 /* maintain data flow .. add it to the */
665 /* ldefs defSet & outExprs of the preheader */
666 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
667 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
668 cdp->diCode->lineno = preHdr->ech->lineno;
669 addSetHead (&preHdr->outExprs, cdp);
673 icFirst = cdp->diCode;
676 icLast->next = cdp->diCode;
677 cdp->diCode->prev = icLast;
678 icLast = cdp->diCode;
681 icLast = cdp->diCode;
685 /* add the instruction chain to the end of the
686 preheader for this loop, preheaders will always
687 have atleast a label */
688 preHdr->ech->next = icFirst;
689 icFirst->prev = preHdr->ech;
690 preHdr->ech = icLast;
697 /*-----------------------------------------------------------------*/
698 /* addressTaken - returns true if the symbol is found in the addrof */
699 /*-----------------------------------------------------------------*/
701 addressTaken (set * sset, operand * sym)
707 for (loop = sset; loop; loop = loop->next)
713 if (isOperandEqual ((operand *) loop2->item, sym))
723 /*-----------------------------------------------------------------*/
724 /* findInduction :- returns 1 & the item if the induction is found */
725 /*-----------------------------------------------------------------*/
726 DEFSETFUNC (findInduction)
728 induction *ip = item;
729 V_ARG (operand *, sym);
730 V_ARG (induction **, ipp);
732 if (isOperandEqual (ip->sym, sym))
741 /*-----------------------------------------------------------------*/
742 /* findDefInRegion - finds the definition within the region */
743 /*-----------------------------------------------------------------*/
745 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
749 /* for all blocks in the region */
750 for (lBlock = setFirstItem (regBlocks); lBlock;
751 lBlock = setNextItem (regBlocks))
754 /* if a definition for this exists */
755 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
759 /* go thru the instruction chain to find it */
760 for (ic = lBlock->sch; ic; ic = ic->next)
761 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
773 /*-----------------------------------------------------------------*/
774 /* basicInduction - finds the basic induction variables in a loop */
775 /*-----------------------------------------------------------------*/
777 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
782 /* i.e. all assignments of the form a := a +/- const */
783 /* for all blocks within the loop do */
784 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
785 lBlock = setNextItem (loopReg->regBlocks))
790 /* for all instructions in the blocks do */
791 for (ic = lBlock->sch; ic; ic = ic->next)
798 eBBlock *owner = NULL;
802 /* To find an induction variable, we need to */
803 /* find within the loop three iCodes in this */
806 /* ddic: iTempB := symbolVar */
807 /* dic: iTempA := iTempB + lit */
808 /* or iTempA := iTempB - lit */
809 /* or iTempA := lit + iTempB */
810 /* ic: symbolVar := iTempA */
812 /* (symbolVar may also be an iTemp if it is */
813 /* register equivalent) */
815 /* look for assignments of the form */
816 /* symbolVar := iTempNN */
820 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
821 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
824 if (isOperandGlobal (IC_RESULT (ic)))
827 if (!IS_ITEMP (IC_RIGHT (ic)))
830 /* if it has multiple assignments within the loop then skip */
831 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
834 /* if the address of this was taken inside the loop then continue */
835 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
838 /* Only consider variables with integral type. */
839 /* (2004/12/06 - EEP - ds390 fails regression tests unless */
840 /* pointers are also considered for induction (due to some */
841 /* register alloctaion bugs). Remove !IS_PTR clause when */
842 /* that gets fixed) */
843 optype = operandType (IC_RIGHT (ic));
844 if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
847 /* find the definition for the result in the block */
848 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
849 IC_RIGHT (ic), &owner)))
852 /* if not +/- continue */
853 if (dic->op != '+' && dic->op != '-')
856 /* make sure definition is of the form a +/- c */
857 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
860 /* make sure the definition found is the only one */
861 if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
864 if (IS_OP_LITERAL (IC_RIGHT (dic)))
866 aSym = IC_LEFT (dic);
867 litValue = (long) operandLitValue (IC_RIGHT (dic));
871 /* For minus, the literal must not be on the left side. */
872 /* (Actually, this case could be handled, but it's probably */
873 /* not worth the extra code) */
876 aSym = IC_RIGHT (dic);
877 litValue = (long) operandLitValue (IC_LEFT (dic));
880 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
881 !isOperandEqual (IC_RIGHT (ic), aSym))
884 /* find the definition for this and check */
885 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
892 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
893 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
897 /* if the right hand side has more than one usage then
898 don't make it an induction (will have to think some more) */
899 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
902 /* if the definition is volatile then it cannot be
903 an induction object */
904 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
905 isOperandVolatile (IC_RESULT (ic), FALSE))
908 /* whew !! that was a lot of work to find the definition */
909 /* create an induction object */
910 indIc = newiCode ('=', NULL, IC_RESULT (ic));
911 indIc->lineno = ic->lineno;
912 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
913 IC_RESULT (indIc)->isaddr = 0;
914 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
915 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
917 /* replace the inducted variable by the iTemp */
918 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
920 /* if it has only one exit then remove it from here
921 and put it in the exit block */
922 nexits = elementsInSet (loopReg->exits);
925 eBBlock *exit = setFirstItem (loopReg->exits);
926 /* if it is the same block then there is no
927 need to move it about */
930 iCode *saveic = ic->prev;
932 remiCodeFromeBBlock (lBlock, ic);
933 /* clear the definition */
934 bitVectUnSetBit (lBlock->defSet, ic->key);
935 /* add it to the exit */
936 addiCodeToeBBlock (exit, ic, NULL);
937 /* set the definition bit */
938 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
943 /* if the number of exits is greater than one then
944 we use another trick ; we will create an intersection
945 of succesors of the exits, then take those that are not
946 part of the loop and have dfNumber greater loop entry
947 and insert a new definition in them */
951 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
953 /* loopSuccs now contains intersection
954 of all the loops successors */
958 for (i = 0; i < loopSuccs->size; i++)
960 if (bitVectBitValue (loopSuccs, i))
963 eBBlock *eblock = NULL;
966 /* Need to search for bbnum == i since ebbs is */
967 /* sorted by dfnum; a direct index won't do. */
968 for (j=0; j<count; j++)
969 if (ebbs[j]->bbnum == i)
976 /* if the successor does not belong to the loop
977 and will be executed after the loop : then
978 add a definition to the block */
979 if (!isinSet (loopReg->regBlocks, eblock) &&
980 eblock->dfnum > loopReg->entry->dfnum)
982 /* create the definition */
983 iCode *newic = newiCode ('=', NULL,
984 operandFromOperand (IC_RIGHT (ic)));
985 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
986 OP_DEFS(IC_RESULT (newic))=
987 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
988 OP_USES(IC_RIGHT (newic))=
989 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
991 if (eblock->sch && eblock->sch->op == LABEL)
992 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
994 addiCodeToeBBlock (eblock, newic, eblock->sch);
995 /* set the definition bit */
996 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
1003 addSet (&indVars, ip);
1006 } /* end of all blocks for basic induction variables */
1011 /*-----------------------------------------------------------------*/
1012 /* loopInduction - remove induction variables from a loop */
1013 /*-----------------------------------------------------------------*/
1015 loopInduction (region * loopReg, ebbIndex * ebbi)
1017 eBBlock ** ebbs = ebbi->dfOrder;
1018 int count = ebbi->count;
1020 eBBlock *lBlock, *owner, *lastBlock = NULL;
1021 set *indVars = NULL;
1022 set *basicInd = NULL;
1024 if (loopReg->entry->preHeader == NULL)
1027 /* we first determine the basic Induction variables */
1028 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1030 /* find other induction variables : by other we mean definitions of */
1031 /* the form x := y (* | / ) <constant> .. we will move this one to */
1032 /* beginning of the loop and reduce strength i.e. replace with +/- */
1033 /* these expensive expressions: OH! and y must be induction too */
1034 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1036 lBlock = setNextItem (loopReg->regBlocks))
1039 iCode *ic, *indIc, *dic;
1042 /* last block is the one with the highest block
1044 if (lastBlock->bbnum < lBlock->bbnum)
1047 for (ic = lBlock->sch; ic; ic = ic->next)
1052 /* consider only * & / */
1053 if (ic->op != '*' && ic->op != '/')
1056 /* only consider variables with integral type */
1057 if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1060 /* if the result has more definitions then */
1061 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1064 /* check if the operands are what we want */
1065 /* i.e. one of them an symbol the other a literal */
1066 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1067 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1070 if (IS_SYMOP (IC_LEFT (ic)))
1072 aSym = IC_LEFT (ic);
1073 litVal = (long) operandLitValue (IC_RIGHT (ic));
1077 /* For division, the literal must not be on the left side */
1080 aSym = IC_RIGHT (ic);
1081 litVal = (long) operandLitValue (IC_LEFT (ic));
1085 /* check if this is an induction variable */
1086 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1089 /* ask port for size not worth if native instruction
1090 exist for multiply & divide */
1091 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1092 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1095 /* if this is a division then the remainder should be zero
1096 for it to be inducted */
1097 if (ic->op == '/' && (ip->cval % litVal))
1100 /* create the iCode to be placed in the loop header */
1101 /* and create the induction object */
1103 /* create an instruction */
1104 /* this will be put on the loop header */
1105 indIc = newiCode (ic->op,
1106 operandFromOperand (aSym),
1107 operandFromLit (litVal));
1108 indIc->lineno = ic->lineno;
1109 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1110 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1112 /* keep track of the inductions */
1113 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1114 (ip->cval / litVal));
1117 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1119 /* Replace mul/div with assignment to self; killDeadCode() will */
1120 /* clean this up since we can't use remiCodeFromeBBlock() here. */
1122 IC_LEFT (ic) = NULL;
1123 IC_RIGHT (ic) = IC_RESULT (ic);
1125 /* Insert an update of the induction variable just before */
1126 /* the update of the basic induction variable. */
1127 indIc = newiCode (ip->op,
1128 operandFromOperand (IC_RESULT (ic)),
1129 operandFromLit (litVal));
1130 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1132 dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1134 addiCodeToeBBlock (owner, indIc, dic);
1139 /* if we have some induction variables then */
1142 eBBlock *preHdr = loopReg->entry->preHeader;
1143 iCode *icFirst = NULL, *icLast = NULL;
1145 bitVect *indVect = NULL;
1147 /* create an iCode chain from it */
1148 for (ip = setFirstItem (indVars);
1150 ip = setNextItem (indVars))
1153 indVect = bitVectSetBit (indVect, ip->ic->key);
1154 ip->ic->lineno = preHdr->ech->lineno;
1159 icLast->next = ip->ic;
1160 ip->ic->prev = icLast;
1168 /* add the instruction chain to the end of the */
1169 /* preheader for this loop */
1170 preHdr->ech->next = icFirst;
1171 icFirst->prev = preHdr->ech;
1172 preHdr->ech = icLast;
1173 icLast->next = NULL;
1175 /* add the induction variable vector to the last
1176 block in the loop */
1177 lastBlock->isLastInLoop = 1;
1178 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1181 setToNull ((void *) &indVars);
1185 /*-----------------------------------------------------------------*/
1186 /* mergeRegions - will merge region with same entry point */
1187 /*-----------------------------------------------------------------*/
1188 DEFSETFUNC (mergeRegions)
1190 region *theLoop = item;
1191 V_ARG (set *, allRegion);
1194 /* if this has already been merged then do nothing */
1195 if (theLoop->merged)
1198 /* go thru all the region and check if any of them have the */
1199 /* entryPoint as the Loop */
1200 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1206 if (lp->entry == theLoop->entry)
1208 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1209 lp->regBlocks, THROW_DEST);
1217 /*-----------------------------------------------------------------*/
1218 /* ifMerged - return 1 if the merge flag is 1 */
1219 /*-----------------------------------------------------------------*/
1220 DEFSETFUNC (ifMerged)
1227 /*-----------------------------------------------------------------*/
1228 /* mergeInnerLoops - will merge into body when entry is present */
1229 /*-----------------------------------------------------------------*/
1230 DEFSETFUNC (mergeInnerLoops)
1232 region *theLoop = item;
1233 V_ARG (set *, allRegion);
1234 V_ARG (int *, maxDepth);
1237 /* check if the entry point is present in the body of any */
1238 /* loop then put the body of this loop into the outer loop */
1239 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1245 if (isinSet (lp->regBlocks, theLoop->entry))
1247 lp->containsLoops += theLoop->containsLoops + 1;
1248 if (lp->containsLoops > (*maxDepth))
1249 *maxDepth = lp->containsLoops;
1251 lp->regBlocks = unionSets (lp->regBlocks,
1252 theLoop->regBlocks, THROW_DEST);
1260 /*-----------------------------------------------------------------*/
1261 /* createLoopRegions - will detect and create a set of natural loops */
1262 /*-----------------------------------------------------------------*/
1264 createLoopRegions (ebbIndex * ebbi)
1266 set *allRegion = NULL; /* set of all loops */
1267 hTab *orderedLoops = NULL;
1272 /* get all the back edges in the graph */
1273 if (!applyToSet (graphEdges, backEdges, &bEdges))
1274 return 0; /* found no loops */
1276 /* for each of these back edges get the blocks that */
1277 /* constitute the loops */
1278 applyToSet (bEdges, createLoop, &allRegion);
1280 /* now we will create regions from these loops */
1281 /* loops with the same entry points are considered to be the */
1282 /* same loop & they are merged. If the entry point of a loop */
1283 /* is found in the body of another loop then , all the blocks */
1284 /* in that loop are added to the loops containing the header */
1285 applyToSet (allRegion, mergeRegions, allRegion);
1287 /* delete those already merged */
1288 deleteItemIf (&allRegion, ifMerged);
1290 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1293 /* now create all the exits .. also */
1294 /* create an ordered set of loops */
1295 /* i.e. we process loops in the inner to outer order */
1296 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1298 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1299 lp->regBlocks, &lp->exits,
1300 (maxDepth - lp->containsLoops), lp);
1302 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1305 return orderedLoops;
1308 /*-----------------------------------------------------------------*/
1309 /* loopOptimizations - identify region & remove invariants & ind */
1310 /*-----------------------------------------------------------------*/
1312 loopOptimizations (hTab * orderedLoops, ebbIndex * ebbi)
1318 /* if no loop optimizations requested */
1319 if (!optimize.loopInvariant &&
1320 !optimize.loopInduction)
1323 /* now we process the loops inner to outer order */
1324 /* this is essential to maintain data flow information */
1325 /* the other choice is an ugly iteration for the depth */
1326 /* of the loops would hate that */
1327 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1328 lp = hTabNextItem (orderedLoops, &k))
1331 if (optimize.loopInvariant)
1332 change += loopInvariants (lp, ebbi);
1334 if (optimize.loopInduction)
1335 change += loopInduction (lp, ebbi);