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 (eBBlock **, ebbs);
308 addSetHead (&ebp->inExprs, cdp);
309 cseBBlock (ebp, optimize.global_cse, ebbs, count);
313 /*-----------------------------------------------------------------*/
314 /* assignmentsToSym - for a set of blocks determine # time assigned */
315 /*-----------------------------------------------------------------*/
317 assignmentsToSym (set * sset, operand * sym)
321 set *blocks = setFromSet (sset);
323 for (ebp = setFirstItem (blocks); ebp;
324 ebp = setNextItem (blocks))
327 /* get all the definitions for this symbol
329 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
330 assigns += bitVectnBitsOn (defs);
331 setToNull ((void *) &defs);
339 /*-----------------------------------------------------------------*/
340 /* isOperandInvariant - determines if an operand is an invariant */
341 /*-----------------------------------------------------------------*/
343 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
346 /* operand is an invariant if it is a */
348 /* b. that have defintions reaching loop entry */
349 /* c. that are already defined as invariant */
350 /* d. has no assignments in the loop */
353 if (IS_OP_LITERAL (op))
355 else if (IS_SYMOP (op) &&
356 OP_SYMBOL (op)->addrtaken)
358 else if (ifDefSymIs (theLoop->entry->inExprs, op))
360 else if (ifDefSymIs (lInvars, op))
362 else if (IS_SYMOP (op) &&
363 !IS_OP_GLOBAL (op) &&
364 !IS_OP_VOLATILE (op) &&
365 assignmentsToSym (theLoop->regBlocks, op) == 0)
374 /*-----------------------------------------------------------------*/
375 /* pointerAssigned - will return 1 if pointer set found */
376 /*-----------------------------------------------------------------*/
377 DEFSETFUNC (pointerAssigned)
380 V_ARG (operand *, op);
385 if (bitVectBitValue (ebp->ptrsSet, op->key))
388 /* Unfortunately, one of the other pointer set operations */
389 /* may be using an alias of this operand, and the above */
390 /* test would miss it. To be thorough, some aliasing */
391 /* analysis should be done here. In the meantime, be */
392 /* conservative and assume any other pointer set operation */
394 if (!bitVectIsZero (ebp->ptrsSet))
400 /*-----------------------------------------------------------------*/
401 /* hasNonPtrUse - returns true if operand has non pointer usage */
402 /*-----------------------------------------------------------------*/
403 DEFSETFUNC (hasNonPtrUse)
406 V_ARG (operand *, op);
407 iCode *ic = usedInRemaining (op, ebp->sch);
409 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
416 /*-----------------------------------------------------------------*/
417 /* loopInvariants - takes loop invariants out of region */
418 /*-----------------------------------------------------------------*/
420 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
428 /* if the preHeader does not exist then do nothing */
429 /* or no exits then do nothing ( have to think about this situation */
430 if (theLoop->entry->preHeader == NULL ||
431 theLoop->exits == NULL)
434 /* we will do the elimination for those blocks */
435 /* in the loop that dominate all exits from the loop */
436 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
437 lBlock = setNextItem (theLoop->regBlocks))
444 /* mark the dominates all exits flag */
445 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
446 elementsInSet (theLoop->exits));
448 /* find out if we have a function call in this block */
449 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
455 /* now we go thru the instructions of this block and */
456 /* collect those instructions with invariant operands */
457 for (ic = lBlock->sch; ic; ic = ic->next)
463 /* TODO this is only needed if the call is between
464 here and the definition, but I am too lazy to do that now */
466 /* if there are function calls in this block */
469 /* if this is a pointer get */
470 if (POINTER_GET(ic)) {
474 /* if this is an assignment from a global */
475 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
480 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
483 /* iTemp assignment from a literal may be invariant, but it
484 will needlessly increase register pressure if the
485 iCode(s) that use this iTemp are not also invariant */
486 if (ic->op=='=' && IS_ITEMP (IC_RESULT (ic))
487 && IS_OP_LITERAL (IC_RIGHT (ic)))
490 /* if result is volatile then skip */
491 if (IC_RESULT (ic) &&
492 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
493 IS_OP_PARM (IC_RESULT (ic))))
496 /* if result depends on a volatile then skip */
497 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
498 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
504 /* if address of then it is an invariant */
505 if (ic->op == ADDRESS_OF &&
506 IS_SYMOP (IC_LEFT (ic)) &&
507 IS_AGGREGATE (operandType (IC_LEFT (ic))))
510 /* check if left operand is an invariant */
511 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
512 /* if this is a pointer get then make sure
513 that the pointer set does not exist in
515 if (POINTER_GET (ic) &&
516 (applyToSet (theLoop->regBlocks,
517 pointerAssigned, IC_LEFT (ic))))
521 /* do the same for right */
522 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
524 /* if this is a POINTER_GET then special case, make sure all
525 usages within the loop are POINTER_GET any other usage
526 would mean that this is not an invariant , since the pointer
527 could then be passed as a parameter */
528 if (POINTER_GET (ic) &&
529 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
533 /* if both the left & right are invariants : then check that */
534 /* this definition exists in the out definition of all the */
535 /* blocks, this will ensure that this is not assigned any */
536 /* other value in the loop, and not used in this block */
537 /* prior to this definition which means only this definition */
538 /* is used in this loop */
539 if (lin && rin && IC_RESULT (ic))
542 set *lSet = setFromSet (theLoop->regBlocks);
544 /* if this block does not dominate all exits */
545 /* make sure this defintion is not used anywhere else */
549 if (isOperandGlobal (IC_RESULT (ic)))
551 /* for successors for all exits */
552 for (sBlock = setFirstItem (theLoop->exits); sBlock;
553 sBlock = setNextItem (theLoop->exits))
556 for (i = 0; i < count; ebbs[i++]->visited = 0);
558 if (applyToSet (sBlock->succList, isDefAlive, ic))
562 /* we have found usage */
567 /* now make sure this is the only definition */
568 for (sBlock = setFirstItem (lSet); sBlock;
569 sBlock = setNextItem (lSet))
571 /* if this is the block make sure the definition */
572 /* reaches the end of the block */
573 if (sBlock == lBlock)
575 if (!ifDiCodeIs (sBlock->outExprs, ic))
578 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
584 /* check that this definition is not assigned */
585 /* any other value in this block */
586 for (ic2 = sBlock->sch; ic2; ic2 = ic2->next)
588 if ((ic != ic2) && (isOperandEqual(IC_RESULT(ic), IC_RESULT(ic2))))
591 if (ic2) /* found another definition */
597 continue; /* another definition present in the block */
599 /* now check if it exists in the in of this block */
600 /* if not then it was killed before this instruction */
601 if (!bitVectBitValue (lBlock->inDefs, ic->key))
604 /* now we know it is a true invariant */
605 /* remove it from the insts chain & put */
606 /* in the invariant set */
608 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
609 SPIL_LOC (IC_RESULT (ic)) = NULL;
610 remiCodeFromeBBlock (lBlock, ic);
612 /* maintain the data flow */
613 /* this means removing from definition from the */
614 /* defset of this block and adding it to the */
615 /* inexpressions of all blocks within the loop */
616 bitVectUnSetBit (lBlock->defSet, ic->key);
617 bitVectUnSetBit (lBlock->ldefs, ic->key);
618 ivar = newCseDef (IC_RESULT (ic), ic);
619 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
620 addSet (&lInvars, ivar);
623 } /* for all loop blocks */
625 /* if we have some invariants then */
628 eBBlock *preHdr = theLoop->entry->preHeader;
629 iCode *icFirst = NULL, *icLast = NULL;
632 /* create an iCode chain from it */
633 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
636 /* maintain data flow .. add it to the */
637 /* ldefs defSet & outExprs of the preheader */
638 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
639 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
640 cdp->diCode->lineno = preHdr->ech->lineno;
641 addSetHead (&preHdr->outExprs, cdp);
645 icFirst = cdp->diCode;
648 icLast->next = cdp->diCode;
649 cdp->diCode->prev = icLast;
650 icLast = cdp->diCode;
653 icLast = cdp->diCode;
657 /* add the instruction chain to the end of the
658 preheader for this loop, preheaders will always
659 have atleast a label */
660 preHdr->ech->next = icFirst;
661 icFirst->prev = preHdr->ech;
662 preHdr->ech = icLast;
669 /*-----------------------------------------------------------------*/
670 /* addressTaken - returns true if the symbol is found in the addrof */
671 /*-----------------------------------------------------------------*/
673 addressTaken (set * sset, operand * sym)
679 for (loop = sset; loop; loop = loop->next)
685 if (isOperandEqual ((operand *) loop2->item, sym))
695 /*-----------------------------------------------------------------*/
696 /* findInduction :- returns 1 & the item if the induction is found */
697 /*-----------------------------------------------------------------*/
698 DEFSETFUNC (findInduction)
700 induction *ip = item;
701 V_ARG (operand *, sym);
702 V_ARG (induction **, ipp);
704 if (isOperandEqual (ip->sym, sym))
713 /*-----------------------------------------------------------------*/
714 /* findDefInRegion - finds the definition within the region */
715 /*-----------------------------------------------------------------*/
717 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
721 /* for all blocks in the region */
722 for (lBlock = setFirstItem (regBlocks); lBlock;
723 lBlock = setNextItem (regBlocks))
726 /* if a definition for this exists */
727 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
731 /* go thru the instruction chain to find it */
732 for (ic = lBlock->sch; ic; ic = ic->next)
733 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
745 /*-----------------------------------------------------------------*/
746 /* basicInduction - finds the basic induction variables in a loop */
747 /*-----------------------------------------------------------------*/
749 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
754 /* i.e. all assignments of the form a := a +/- const */
755 /* for all blocks within the loop do */
756 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
757 lBlock = setNextItem (loopReg->regBlocks))
762 /* for all instructions in the blocks do */
763 for (ic = lBlock->sch; ic; ic = ic->next)
770 eBBlock *owner = NULL;
774 /* To find an induction variable, we need to */
775 /* find within the loop three iCodes in this */
778 /* ddic: iTempB := symbolVar */
779 /* dic: iTempA := iTempB + lit */
780 /* or iTempA := iTempB - lit */
781 /* or iTempA := lit + iTempB */
782 /* ic: symbolVar := iTempA */
784 /* (symbolVar may also be an iTemp if it is */
785 /* register equivalent) */
787 /* look for assignments of the form */
788 /* symbolVar := iTempNN */
792 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
793 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
796 if (isOperandGlobal (IC_RESULT (ic)))
799 if (!IS_ITEMP (IC_RIGHT (ic)))
802 /* if it has multiple assignments within the loop then skip */
803 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
806 /* if the address of this was taken inside the loop then continue */
807 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
810 /* Only consider variables with integral type. */
811 /* (2004/12/06 - EEP - ds390 fails regression tests unless */
812 /* pointers are also considered for induction (due to some */
813 /* register alloctaion bugs). Remove !IS_PTR clause when */
814 /* that gets fixed) */
815 optype = operandType (IC_RIGHT (ic));
816 if (!IS_INTEGRAL (optype) && !IS_PTR (optype))
819 /* find the definition for the result in the block */
820 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
821 IC_RIGHT (ic), &owner)))
824 /* if not +/- continue */
825 if (dic->op != '+' && dic->op != '-')
828 /* make sure definition is of the form a +/- c */
829 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
832 /* make sure the definition found is the only one */
833 if (assignmentsToSym (loopReg->regBlocks, IC_RIGHT (ic)) > 1)
836 if (IS_OP_LITERAL (IC_RIGHT (dic)))
838 aSym = IC_LEFT (dic);
839 litValue = (long) operandLitValue (IC_RIGHT (dic));
843 /* For minus, the literal must not be on the left side. */
844 /* (Actually, this case could be handled, but it's probably */
845 /* not worth the extra code) */
848 aSym = IC_RIGHT (dic);
849 litValue = (long) operandLitValue (IC_LEFT (dic));
852 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
853 !isOperandEqual (IC_RIGHT (ic), aSym))
856 /* find the definition for this and check */
857 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
864 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
865 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
869 /* if the right hand side has more than one usage then
870 don't make it an induction (will have to think some more) */
871 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
874 /* if the definition is volatile then it cannot be
875 an induction object */
876 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
877 isOperandVolatile (IC_RESULT (ic), FALSE))
880 /* whew !! that was a lot of work to find the definition */
881 /* create an induction object */
882 indIc = newiCode ('=', NULL, IC_RESULT (ic));
883 indIc->lineno = ic->lineno;
884 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
885 IC_RESULT (indIc)->isaddr = 0;
886 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
887 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
889 /* replace the inducted variable by the iTemp */
890 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
892 /* if it has only one exit then remove it from here
893 and put it in the exit block */
894 nexits = elementsInSet (loopReg->exits);
897 eBBlock *exit = setFirstItem (loopReg->exits);
898 /* if it is the same block then there is no
899 need to move it about */
902 iCode *saveic = ic->prev;
904 remiCodeFromeBBlock (lBlock, ic);
905 /* clear the definition */
906 bitVectUnSetBit (lBlock->defSet, ic->key);
907 /* add it to the exit */
908 addiCodeToeBBlock (exit, ic, NULL);
909 /* set the definition bit */
910 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
915 /* if the number of exits is greater than one then
916 we use another trick ; we will create an intersection
917 of succesors of the exits, then take those that are not
918 part of the loop and have dfNumber greater loop entry
919 and insert a new definition in them */
923 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
925 /* loopSuccs now contains intersection
926 of all the loops successors */
930 for (i = 0; i < loopSuccs->size; i++)
932 if (bitVectBitValue (loopSuccs, i))
935 eBBlock *eblock = NULL;
938 /* Need to search for bbnum == i since ebbs is */
939 /* sorted by dfnum; a direct index won't do. */
940 for (j=0; j<count; j++)
941 if (ebbs[j]->bbnum == i)
948 /* if the successor does not belong to the loop
949 and will be executed after the loop : then
950 add a definition to the block */
951 if (!isinSet (loopReg->regBlocks, eblock) &&
952 eblock->dfnum > loopReg->entry->dfnum)
954 /* create the definition */
955 iCode *newic = newiCode ('=', NULL,
956 operandFromOperand (IC_RIGHT (ic)));
957 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
958 OP_DEFS(IC_RESULT (newic))=
959 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
960 OP_USES(IC_RIGHT (newic))=
961 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
963 if (eblock->sch && eblock->sch->op == LABEL)
964 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
966 addiCodeToeBBlock (eblock, newic, eblock->sch);
967 /* set the definition bit */
968 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
975 addSet (&indVars, ip);
978 } /* end of all blocks for basic induction variables */
983 /*-----------------------------------------------------------------*/
984 /* loopInduction - remove induction variables from a loop */
985 /*-----------------------------------------------------------------*/
987 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
990 eBBlock *lBlock, *owner, *lastBlock = NULL;
992 set *basicInd = NULL;
994 if (loopReg->entry->preHeader == NULL)
997 /* we first determine the basic Induction variables */
998 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1000 /* find other induction variables : by other we mean definitions of */
1001 /* the form x := y (* | / ) <constant> .. we will move this one to */
1002 /* beginning of the loop and reduce strength i.e. replace with +/- */
1003 /* these expensive expressions: OH! and y must be induction too */
1004 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1006 lBlock = setNextItem (loopReg->regBlocks))
1009 iCode *ic, *indIc, *dic;
1012 /* last block is the one with the highest block
1014 if (lastBlock->bbnum < lBlock->bbnum)
1017 for (ic = lBlock->sch; ic; ic = ic->next)
1022 /* consider only * & / */
1023 if (ic->op != '*' && ic->op != '/')
1026 /* only consider variables with integral type */
1027 if (!IS_INTEGRAL (operandType (IC_RESULT (ic))))
1030 /* if the result has more definitions then */
1031 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1034 /* check if the operands are what we want */
1035 /* i.e. one of them an symbol the other a literal */
1036 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1037 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1040 if (IS_SYMOP (IC_LEFT (ic)))
1042 aSym = IC_LEFT (ic);
1043 litVal = (long) operandLitValue (IC_RIGHT (ic));
1047 /* For division, the literal must not be on the left side */
1050 aSym = IC_RIGHT (ic);
1051 litVal = (long) operandLitValue (IC_LEFT (ic));
1055 /* check if this is an induction variable */
1056 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1059 /* ask port for size not worth if native instruction
1060 exist for multiply & divide */
1061 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1062 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1065 /* if this is a division then the remainder should be zero
1066 for it to be inducted */
1067 if (ic->op == '/' && (ip->cval % litVal))
1070 /* create the iCode to be placed in the loop header */
1071 /* and create the induction object */
1073 /* create an instruction */
1074 /* this will be put on the loop header */
1075 indIc = newiCode (ic->op,
1076 operandFromOperand (aSym),
1077 operandFromLit (litVal));
1078 indIc->lineno = ic->lineno;
1079 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1080 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1082 /* keep track of the inductions */
1083 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1084 (ip->cval / litVal));
1087 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1089 /* Replace mul/div with assignment to self; killDeadCode() will */
1090 /* clean this up since we can't use remiCodeFromeBBlock() here. */
1092 IC_LEFT (ic) = NULL;
1093 IC_RIGHT (ic) = IC_RESULT (ic);
1095 /* Insert an update of the induction variable just before */
1096 /* the update of the basic induction variable. */
1097 indIc = newiCode (ip->op,
1098 operandFromOperand (IC_RESULT (ic)),
1099 operandFromLit (litVal));
1100 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1102 dic = findDefInRegion (setFromSet (loopReg->regBlocks), aSym, &owner);
1104 addiCodeToeBBlock (owner, indIc, dic);
1109 /* if we have some induction variables then */
1112 eBBlock *preHdr = loopReg->entry->preHeader;
1113 iCode *icFirst = NULL, *icLast = NULL;
1115 bitVect *indVect = NULL;
1117 /* create an iCode chain from it */
1118 for (ip = setFirstItem (indVars);
1120 ip = setNextItem (indVars))
1123 indVect = bitVectSetBit (indVect, ip->ic->key);
1124 ip->ic->lineno = preHdr->ech->lineno;
1129 icLast->next = ip->ic;
1130 ip->ic->prev = icLast;
1138 /* add the instruction chain to the end of the */
1139 /* preheader for this loop */
1140 preHdr->ech->next = icFirst;
1141 icFirst->prev = preHdr->ech;
1142 preHdr->ech = icLast;
1143 icLast->next = NULL;
1145 /* add the induction variable vector to the last
1146 block in the loop */
1147 lastBlock->isLastInLoop = 1;
1148 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1151 setToNull ((void *) &indVars);
1155 /*-----------------------------------------------------------------*/
1156 /* mergeRegions - will merge region with same entry point */
1157 /*-----------------------------------------------------------------*/
1158 DEFSETFUNC (mergeRegions)
1160 region *theLoop = item;
1161 V_ARG (set *, allRegion);
1164 /* if this has already been merged then do nothing */
1165 if (theLoop->merged)
1168 /* go thru all the region and check if any of them have the */
1169 /* entryPoint as the Loop */
1170 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1176 if (lp->entry == theLoop->entry)
1178 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1179 lp->regBlocks, THROW_DEST);
1187 /*-----------------------------------------------------------------*/
1188 /* ifMerged - return 1 if the merge flag is 1 */
1189 /*-----------------------------------------------------------------*/
1190 DEFSETFUNC (ifMerged)
1197 /*-----------------------------------------------------------------*/
1198 /* mergeInnerLoops - will merge into body when entry is present */
1199 /*-----------------------------------------------------------------*/
1200 DEFSETFUNC (mergeInnerLoops)
1202 region *theLoop = item;
1203 V_ARG (set *, allRegion);
1204 V_ARG (int *, maxDepth);
1207 /* check if the entry point is present in the body of any */
1208 /* loop then put the body of this loop into the outer loop */
1209 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1215 if (isinSet (lp->regBlocks, theLoop->entry))
1217 lp->containsLoops += theLoop->containsLoops + 1;
1218 if (lp->containsLoops > (*maxDepth))
1219 *maxDepth = lp->containsLoops;
1221 lp->regBlocks = unionSets (lp->regBlocks,
1222 theLoop->regBlocks, THROW_DEST);
1230 /*-----------------------------------------------------------------*/
1231 /* createLoopRegions - will detect and create a set of natural loops */
1232 /*-----------------------------------------------------------------*/
1234 createLoopRegions (eBBlock ** ebbs, int count)
1236 set *allRegion = NULL; /* set of all loops */
1237 hTab *orderedLoops = NULL;
1242 /* get all the back edges in the graph */
1243 if (!applyToSet (graphEdges, backEdges, &bEdges))
1244 return 0; /* found no loops */
1246 /* for each of these back edges get the blocks that */
1247 /* constitute the loops */
1248 applyToSet (bEdges, createLoop, &allRegion);
1250 /* now we will create regions from these loops */
1251 /* loops with the same entry points are considered to be the */
1252 /* same loop & they are merged. If the entry point of a loop */
1253 /* is found in the body of another loop then , all the blocks */
1254 /* in that loop are added to the loops containing the header */
1255 applyToSet (allRegion, mergeRegions, allRegion);
1257 /* delete those already merged */
1258 deleteItemIf (&allRegion, ifMerged);
1260 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1263 /* now create all the exits .. also */
1264 /* create an ordered set of loops */
1265 /* i.e. we process loops in the inner to outer order */
1266 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1268 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1269 lp->regBlocks, &lp->exits,
1270 (maxDepth - lp->containsLoops), lp);
1272 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1275 return orderedLoops;
1278 /*-----------------------------------------------------------------*/
1279 /* loopOptimizations - identify region & remove invariants & ind */
1280 /*-----------------------------------------------------------------*/
1282 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1288 /* if no loop optimizations requested */
1289 if (!optimize.loopInvariant &&
1290 !optimize.loopInduction)
1293 /* now we process the loops inner to outer order */
1294 /* this is essential to maintain data flow information */
1295 /* the other choice is an ugly iteration for the depth */
1296 /* of the loops would hate that */
1297 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1298 lp = hTabNextItem (orderedLoops, &k))
1301 if (optimize.loopInvariant)
1302 change += loopInvariants (lp, ebbs, count);
1304 if (optimize.loopInduction)
1305 change += loopInduction (lp, ebbs, count);