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_calloc (1, sizeof (induction));
53 /*-----------------------------------------------------------------*/
54 /* newRegion - allocate & returns a loop structure */
55 /*-----------------------------------------------------------------*/
61 lp = Safe_calloc (1, 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 */
237 /* put the loop region info in the block */
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, 0, 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);
382 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
385 /*-----------------------------------------------------------------*/
386 /* hasNonPtrUse - returns true if operand has non pointer usage */
387 /*-----------------------------------------------------------------*/
388 DEFSETFUNC (hasNonPtrUse)
391 V_ARG (operand *, op);
392 iCode *ic = usedInRemaining (op, ebp->sch);
394 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
401 /*-----------------------------------------------------------------*/
402 /* loopInvariants - takes loop invariants out of region */
403 /*-----------------------------------------------------------------*/
405 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
412 /* if the preHeader does not exist then do nothing */
413 /* or no exits then do nothing ( have to think about this situation */
414 if (theLoop->entry->preHeader == NULL ||
415 theLoop->exits == NULL)
418 /* we will do the elimination for those blocks */
419 /* in the loop that dominates all exits from the loop */
420 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
421 lBlock = setNextItem (theLoop->regBlocks))
428 /* mark the dominates all exits flag */
429 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
430 elementsInSet (theLoop->exits));
433 /* now we go thru the instructions of this block and */
434 /* collect those instructions with invariant operands */
435 for (ic = lBlock->sch; ic; ic = ic->next)
441 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
444 /* if result is volatile then skip */
445 if (IC_RESULT (ic) &&
446 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
447 IS_OP_PARM (IC_RESULT (ic))))
450 /* if result depends on a volatile then skip */
451 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
452 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
458 /* if address of then it is an invariant */
459 if (ic->op == ADDRESS_OF &&
460 IS_SYMOP (IC_LEFT (ic)) &&
461 IS_AGGREGATE (operandType (IC_LEFT (ic))))
464 /* check if left operand is an invariant */
465 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
466 /* if this is a pointer get then make sure
467 that the pointer set does not exist in
469 if (POINTER_GET (ic) &&
470 (applyToSet (theLoop->regBlocks, pointerAssigned, IC_LEFT (ic))))
473 /* do the same for right */
474 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
476 /* if this is a POINTER_GET then special case, make sure all
477 usages within the loop are POINTER_GET any other usage
478 would mean that this is not an invariant , since the pointer
479 could then be passed as a parameter */
480 if (POINTER_GET (ic) &&
481 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
484 /* if both the left & right are invariants : then check that */
485 /* this definition exists in the out definition of all the */
486 /* blocks, this will ensure that this is not assigned any */
487 /* other value in the loop , and not used in this block */
488 /* prior to this definition which means only this definition */
489 /* is used in this loop */
490 if (lin && rin && IC_RESULT (ic))
493 set *lSet = setFromSet (theLoop->regBlocks);
495 /* if this block does not dominate all exists */
496 /* make sure this defintion is not used anywhere else */
500 if (isOperandGlobal (IC_RESULT (ic)))
502 /* for successors for all exits */
503 for (sBlock = setFirstItem (theLoop->exits); sBlock;
504 sBlock = setNextItem (theLoop->exits))
507 for (i = 0; i < count; ebbs[i++]->visited = 0);
509 if (applyToSet (sBlock->succList, isDefAlive, ic))
513 /* we have found usage */
518 /* now make sure this is the only definition */
519 for (sBlock = setFirstItem (lSet); sBlock;
520 sBlock = setNextItem (lSet))
522 /* if this is the block make sure the definition */
523 /* reaches the end of the block */
524 if (sBlock == lBlock)
526 if (!ifDiCodeIs (sBlock->outExprs, ic))
529 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
534 continue; /* another definition present in the block */
536 /* now check if it exists in the in of this block */
537 /* if not then it was killed before this instruction */
538 if (!bitVectBitValue (lBlock->inDefs, ic->key))
541 /* now we know it is a true invariant */
542 /* remove it from the insts chain & put */
543 /* in the invariant set */
544 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
545 remiCodeFromeBBlock (lBlock, ic);
547 /* maintain the data flow */
548 /* this means removing from definition from the */
549 /* defset of this block and adding it to the */
550 /* inexpressions of all blocks within the loop */
551 bitVectUnSetBit (lBlock->defSet, ic->key);
552 bitVectUnSetBit (lBlock->ldefs, ic->key);
553 ivar = newCseDef (IC_RESULT (ic), ic);
554 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
555 addSet (&lInvars, ivar);
558 } /* for all loop blocks */
560 /* if we have some invariants then */
563 eBBlock *preHdr = theLoop->entry->preHeader;
564 iCode *icFirst = NULL, *icLast = NULL;
567 /* create an iCode chain from it */
568 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
571 /* maintain data flow .. add it to the */
572 /* ldefs defSet & outExprs of the preheader */
573 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
574 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
575 cdp->diCode->lineno = preHdr->ech->lineno;
576 addSetHead (&preHdr->outExprs, cdp);
580 icFirst = cdp->diCode;
583 icLast->next = cdp->diCode;
584 cdp->diCode->prev = icLast;
585 icLast = cdp->diCode;
588 icLast = cdp->diCode;
592 /* add the instruction chain to the end of the
593 preheader for this loop, preheaders will always
594 have atleast a label */
595 preHdr->ech->next = icFirst;
596 icFirst->prev = preHdr->ech;
597 preHdr->ech = icLast;
604 /*-----------------------------------------------------------------*/
605 /* addressTaken - returns true if the symbol is found in the addrof */
606 /*-----------------------------------------------------------------*/
608 addressTaken (set * sset, operand * sym)
614 for (loop = sset; loop; loop = loop->next)
620 if (isOperandEqual ((operand *) loop2->item, sym))
630 /*-----------------------------------------------------------------*/
631 /* findInduction :- returns 1 & the item if the induction is found */
632 /*-----------------------------------------------------------------*/
633 DEFSETFUNC (findInduction)
635 induction *ip = item;
636 V_ARG (operand *, sym);
637 V_ARG (induction **, ipp);
639 if (isOperandEqual (ip->sym, sym))
648 /*-----------------------------------------------------------------*/
649 /* findDefInRegion - finds the definition within the region */
650 /*-----------------------------------------------------------------*/
652 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
656 /* for all blocks in the region */
657 for (lBlock = setFirstItem (regBlocks); lBlock;
658 lBlock = setNextItem (regBlocks))
661 /* if a definition for this exists */
662 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
666 /* go thru the instruction chain to find it */
667 for (ic = lBlock->sch; ic; ic = ic->next)
668 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
680 /*-----------------------------------------------------------------*/
681 /* basicInduction - finds the basic induction variables in a loop */
682 /*-----------------------------------------------------------------*/
684 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
689 /* i.e. all assignments of the form a := a +/- const */
690 /* for all blocks within the loop do */
691 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
692 lBlock = setNextItem (loopReg->regBlocks))
697 /* for all instructions in the blocks do */
698 for (ic = lBlock->sch; ic; ic = ic->next)
702 unsigned long litValue;
705 eBBlock *owner = NULL;
708 /* look for assignments of the form */
709 /* symbolVar := iTempNN */
713 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
714 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
717 if (isOperandGlobal (IC_RESULT (ic)))
720 if (!IS_ITEMP (IC_RIGHT (ic)))
723 /* if it has multiple assignments within the loop then skip */
724 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
727 /* if the address of this was taken inside the loop then continue */
728 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
731 /* find the definition for the result in the block */
732 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
733 IC_RIGHT (ic), &owner)))
736 /* if not +/- continue */
737 if (dic->op != '+' && dic->op != '-')
740 /* make sure definition is of the form a +/- c */
741 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
744 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
745 (litValue = operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
746 (litValue = operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
748 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
749 !isOperandEqual (IC_RIGHT (ic), aSym))
752 /* find the definition for this and check */
753 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
760 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
761 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
765 /* if the right hand side has more than one usage then
766 don't make it an induction (will have to think some more) */
767 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
770 /* if the definition is volatile then it cannot be
771 an induction object */
772 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
773 isOperandVolatile (IC_RESULT (ic), FALSE))
776 /* whew !! that was a lot of work to find the definition */
777 /* create an induction object */
778 indIc = newiCode ('=', NULL, IC_RESULT (ic));
779 indIc->lineno = ic->lineno;
780 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
781 IC_RESULT (indIc)->isaddr = 0;
782 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
783 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
785 /* replace the inducted variable by the iTemp */
786 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
788 /* if it has only one exit then remove it from here
789 and put it in the exit block */
790 nexits = elementsInSet (loopReg->exits);
793 eBBlock *exit = setFirstItem (loopReg->exits);
795 /* if it is the same block then there is no
796 need to move it about */
799 iCode *saveic = ic->prev;
801 remiCodeFromeBBlock (lBlock, ic);
802 /* clear the definition */
803 bitVectUnSetBit (lBlock->defSet, ic->key);
804 /* add it to the exit */
805 addiCodeToeBBlock (exit, ic, NULL);
806 /* set the definition bit */
807 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
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
816 and insert a new definition in them */
820 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
822 /* loopSuccs now contains intersection
823 of all the loops successors */
827 for (i = 0; i < loopSuccs->size; i++)
829 if (bitVectBitValue (loopSuccs, i))
832 eBBlock *eblock = ebbs[i];
834 /* if the successor does not belong to the loop
835 and will be executed after the loop : then
836 add a definition to the block */
837 if (!isinSet (loopReg->regBlocks, eblock) &&
838 eblock->dfnum > loopReg->entry->dfnum)
840 /* create the definition */
841 iCode *newic = newiCode ('=', NULL,
842 operandFromOperand (IC_RIGHT (ic)));
843 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
844 OP_DEFS (IC_RESULT (newic)) =
845 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
846 OP_USES (IC_RIGHT (newic)) =
847 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
849 if (eblock->sch && eblock->sch->op == LABEL)
850 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
852 addiCodeToeBBlock (eblock, newic, eblock->sch);
853 /* set the definition bit */
854 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
861 addSet (&indVars, ip);
864 } /* end of all blocks for basic induction variables */
869 /*-----------------------------------------------------------------*/
870 /* loopInduction - remove induction variables from a loop */
871 /*-----------------------------------------------------------------*/
873 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
876 eBBlock *lBlock, *lastBlock = NULL;
878 set *basicInd = NULL;
880 if (loopReg->entry->preHeader == NULL)
883 /* we first determine the basic Induction variables */
884 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
886 /* find other induction variables : by other we mean definitions of */
887 /* the form x := y (* | / ) <constant> .. we will move this one to */
888 /* beginning of the loop and reduce strength i.e. replace with +/- */
889 /* these expensive expressions: OH! and y must be induction too */
890 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
892 lBlock = setNextItem (loopReg->regBlocks))
898 /* last block is the one with the highest block
900 if (lastBlock->bbnum < lBlock->bbnum)
903 for (ic = lBlock->sch; ic; ic = ic->next)
906 unsigned long litVal;
909 /* consider only * & / */
910 if (ic->op != '*' && ic->op != '/')
913 /* if the result has more definitions then */
914 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
917 /* check if the operands are what we want */
918 /* i.e. one of them an symbol the other a literal */
919 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
920 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
923 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
924 (lr = 1, litVal = operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
925 (litVal = operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
928 /* check if this is an induction variable */
929 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
932 /* ask port for size not worth if native instruction
933 exist for multiply & divide */
934 if (getSize (operandType (IC_LEFT (ic))) <= port->muldiv.native_below ||
935 getSize (operandType (IC_RIGHT (ic))) <= port->muldiv.native_below)
938 /* if this is a division then the remainder should be zero
939 for it to be inducted */
940 if (ic->op == '/' && (ip->cval % litVal))
943 /* create the iCode to be placed in the loop header */
944 /* and create the induction object */
946 /* create an instruction */
947 /* this will be put on the loop header */
948 indIc = newiCode (ic->op,
949 operandFromOperand (aSym),
950 operandFromLit (litVal));
951 indIc->lineno = ic->lineno;
952 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
953 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
955 /* keep track of the inductions */
956 litVal = (ic->op == '*' ? (litVal * ip->cval) :
957 (ip->cval / litVal));
960 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
962 /* now change this instruction */
966 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
967 IC_RIGHT (ic) = operandFromLit (litVal);
971 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
972 IC_LEFT (ic) = operandFromLit (litVal);
975 /* we need somemore initialisation code */
976 /* we subtract the litVal from itself if increment */
979 indIc = newiCode ('-',
980 operandFromOperand (IC_RESULT (ic)),
981 operandFromLit (litVal));
982 indIc->lineno = ic->lineno;
983 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
986 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
991 /* if we have some induction variables then */
994 eBBlock *preHdr = loopReg->entry->preHeader;
995 iCode *icFirst = NULL, *icLast = NULL;
997 bitVect *indVect = NULL;
999 /* create an iCode chain from it */
1000 for (ip = setFirstItem (indVars);
1002 ip = setNextItem (indVars))
1005 indVect = bitVectSetBit (indVect, ip->ic->key);
1006 ip->ic->lineno = preHdr->ech->lineno;
1011 icLast->next = ip->ic;
1012 ip->ic->prev = icLast;
1020 /* add the instruction chain to the end of the */
1021 /* preheader for this loop */
1022 preHdr->ech->next = icFirst;
1023 icFirst->prev = preHdr->ech;
1024 preHdr->ech = icLast;
1025 icLast->next = NULL;
1027 /* add the induction variable vector to the last
1028 block in the loop */
1029 lastBlock->isLastInLoop = 1;
1030 lastBlock->linds = indVect;
1033 setToNull ((void **) &indVars);
1037 /*-----------------------------------------------------------------*/
1038 /* mergeRegions - will merge region with same entry point */
1039 /*-----------------------------------------------------------------*/
1040 DEFSETFUNC (mergeRegions)
1042 region *theLoop = item;
1043 V_ARG (set *, allRegion);
1046 /* if this has already been merged then do nothing */
1047 if (theLoop->merged)
1050 /* go thru all the region and check if any of them have the */
1051 /* entryPoint as the Loop */
1052 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1058 if (lp->entry == theLoop->entry)
1060 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1061 lp->regBlocks, THROW_BOTH);
1069 /*-----------------------------------------------------------------*/
1070 /* ifMerged - return 1 if the merge flag is 1 */
1071 /*-----------------------------------------------------------------*/
1072 DEFSETFUNC (ifMerged)
1079 /*-----------------------------------------------------------------*/
1080 /* mergeInnerLoops - will merge into body when entry is present */
1081 /*-----------------------------------------------------------------*/
1082 DEFSETFUNC (mergeInnerLoops)
1084 region *theLoop = item;
1085 V_ARG (set *, allRegion);
1086 V_ARG (int *, maxDepth);
1089 /* check if the entry point is present in the body of any */
1090 /* loop then put the body of this loop into the outer loop */
1091 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1097 if (isinSet (lp->regBlocks, theLoop->entry))
1099 lp->containsLoops += theLoop->containsLoops + 1;
1100 if (lp->containsLoops > (*maxDepth))
1101 *maxDepth = lp->containsLoops;
1103 lp->regBlocks = unionSets (lp->regBlocks,
1104 theLoop->regBlocks, THROW_DEST);
1112 /*-----------------------------------------------------------------*/
1113 /* createLoopRegions - will detect and create a set of natural loops */
1114 /*-----------------------------------------------------------------*/
1116 createLoopRegions (eBBlock ** ebbs, int count)
1118 set *allRegion = NULL; /* set of all loops */
1119 hTab *orderedLoops = NULL;
1124 /* get all the back edges in the graph */
1125 if (!applyToSet (graphEdges, backEdges, &bEdges))
1126 return 0; /* found no loops */
1128 /* for each of these back edges get the blocks that */
1129 /* constitute the loops */
1130 applyToSet (bEdges, createLoop, &allRegion);
1132 /* now we will create regions from these loops */
1133 /* loops with the same entry points are considered to be the */
1134 /* same loop & they are merged. If the entry point of a loop */
1135 /* is found in the body of another loop then , all the blocks */
1136 /* in that loop are added to the loops containing the header */
1137 applyToSet (allRegion, mergeRegions, allRegion);
1139 /* delete those already merged */
1140 deleteItemIf (&allRegion, ifMerged);
1142 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1144 /* now create all the exits .. also */
1145 /* create an ordered set of loops */
1146 /* i.e. we process loops in the inner to outer order */
1147 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1149 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1150 lp->regBlocks, &lp->exits,
1151 (maxDepth - lp->containsLoops), lp);
1153 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1156 return orderedLoops;
1159 /*-----------------------------------------------------------------*/
1160 /* loopOptimizations - identify region & remove invariants & ind */
1161 /*-----------------------------------------------------------------*/
1163 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1169 /* if no loop optimizations requested */
1170 if (!optimize.loopInvariant &&
1171 !optimize.loopInduction)
1174 /* now we process the loops inner to outer order */
1175 /* this is essential to maintain data flow information */
1176 /* the other choice is an ugly iteration for the depth */
1177 /* of the loops would hate that */
1178 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1179 lp = hTabNextItem (orderedLoops, &k))
1182 if (optimize.loopInvariant)
1183 change += loopInvariants (lp, ebbs, count);
1185 if (optimize.loopInduction)
1186 change += loopInduction (lp, ebbs, count);