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 /* put the loop region info in the block */
239 if (!isinSet (ebp->partOfLoop, lr))
240 addSetHead (&ebp->partOfLoop, lr);
242 /* if any of the successors go out of the loop then */
243 /* we add this one to the exits */
244 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
246 addSetHead (exits, ebp);
253 /*-----------------------------------------------------------------*/
254 /* createLoop - will create a set of region */
255 /*-----------------------------------------------------------------*/
256 DEFSETFUNC (createLoop)
259 V_ARG (set **, allRegion);
260 region *aloop = newRegion ();
263 /* make sure regionStack is empty */
264 while (!STACK_EMPTY (regionStack))
265 STACK_POP (regionStack);
267 /* add the entryBlock */
268 addSet (&aloop->regBlocks, ep->to);
269 loopInsert (&aloop->regBlocks, ep->from);
271 while (!STACK_EMPTY (regionStack))
273 block = STACK_POP (regionStack);
274 /* if block != entry */
276 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
279 aloop->entry = ep->to;
281 /* now add it to the set */
282 addSetHead (allRegion, aloop);
286 /*-----------------------------------------------------------------*/
287 /* dominatedBy - will return 1 if item is dominated by block */
288 /*-----------------------------------------------------------------*/
289 DEFSETFUNC (dominatedBy)
292 V_ARG (eBBlock *, block);
294 return bitVectBitValue (ebp->domVect, block->bbnum);
297 /*-----------------------------------------------------------------*/
298 /* addDefInExprs - adds an expression into the inexpressions */
299 /*-----------------------------------------------------------------*/
300 DEFSETFUNC (addDefInExprs)
303 V_ARG (cseDef *, cdp);
304 V_ARG (eBBlock **, ebbs);
307 addSetHead (&ebp->inExprs, cdp);
308 cseBBlock (ebp, optimize.global_cse, ebbs, count);
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);
381 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
384 /*-----------------------------------------------------------------*/
385 /* hasNonPtrUse - returns true if operand has non pointer usage */
386 /*-----------------------------------------------------------------*/
387 DEFSETFUNC (hasNonPtrUse)
390 V_ARG (operand *, op);
391 iCode *ic = usedInRemaining (op, ebp->sch);
393 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
400 /*-----------------------------------------------------------------*/
401 /* loopInvariants - takes loop invariants out of region */
402 /*-----------------------------------------------------------------*/
404 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));
432 /* find out if we have a function call in this block */
433 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
439 /* now we go thru the instructions of this block and */
440 /* collect those instructions with invariant operands */
441 for (ic = lBlock->sch; ic; ic = ic->next)
447 /* TODO this is only needed if the call is between
448 here and the definition, but I am too lazy to do that now */
450 /* if there are function calls in this block */
453 /* if this is a pointer get */
454 if (POINTER_GET(ic)) {
458 /* if this is an assignment from a global */
459 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
464 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
467 /* if result is volatile then skip */
468 if (IC_RESULT (ic) &&
469 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
470 IS_OP_PARM (IC_RESULT (ic))))
473 /* if result depends on a volatile then skip */
474 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
475 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
481 /* if address of then it is an invariant */
482 if (ic->op == ADDRESS_OF &&
483 IS_SYMOP (IC_LEFT (ic)) &&
484 IS_AGGREGATE (operandType (IC_LEFT (ic))))
487 /* check if left operand is an invariant */
488 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
489 /* if this is a pointer get then make sure
490 that the pointer set does not exist in
492 if (POINTER_GET (ic) &&
493 (applyToSet (theLoop->regBlocks,
494 pointerAssigned, IC_LEFT (ic))))
498 /* do the same for right */
499 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
501 /* if this is a POINTER_GET then special case, make sure all
502 usages within the loop are POINTER_GET any other usage
503 would mean that this is not an invariant , since the pointer
504 could then be passed as a parameter */
505 if (POINTER_GET (ic) &&
506 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
509 /* if both the left & right are invariants : then check that */
510 /* this definition exists in the out definition of all the */
511 /* blocks, this will ensure that this is not assigned any */
512 /* other value in the loop , and not used in this block */
513 /* prior to this definition which means only this definition */
514 /* is used in this loop */
515 if (lin && rin && IC_RESULT (ic))
518 set *lSet = setFromSet (theLoop->regBlocks);
520 /* if this block does not dominate all exists */
521 /* make sure this defintion is not used anywhere else */
525 if (isOperandGlobal (IC_RESULT (ic)))
527 /* for successors for all exits */
528 for (sBlock = setFirstItem (theLoop->exits); sBlock;
529 sBlock = setNextItem (theLoop->exits))
532 for (i = 0; i < count; ebbs[i++]->visited = 0);
534 if (applyToSet (sBlock->succList, isDefAlive, ic))
538 /* we have found usage */
543 /* now make sure this is the only definition */
544 for (sBlock = setFirstItem (lSet); sBlock;
545 sBlock = setNextItem (lSet))
547 /* if this is the block make sure the definition */
548 /* reaches the end of the block */
549 if (sBlock == lBlock)
551 if (!ifDiCodeIs (sBlock->outExprs, ic))
554 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
559 continue; /* another definition present in the block */
561 /* now check if it exists in the in of this block */
562 /* if not then it was killed before this instruction */
563 if (!bitVectBitValue (lBlock->inDefs, ic->key))
566 /* now we know it is a true invariant */
567 /* remove it from the insts chain & put */
568 /* in the invariant set */
569 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
570 remiCodeFromeBBlock (lBlock, ic);
572 /* maintain the data flow */
573 /* this means removing from definition from the */
574 /* defset of this block and adding it to the */
575 /* inexpressions of all blocks within the loop */
576 bitVectUnSetBit (lBlock->defSet, ic->key);
577 bitVectUnSetBit (lBlock->ldefs, ic->key);
578 ivar = newCseDef (IC_RESULT (ic), ic);
579 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
580 addSet (&lInvars, ivar);
583 } /* for all loop blocks */
585 /* if we have some invariants then */
588 eBBlock *preHdr = theLoop->entry->preHeader;
589 iCode *icFirst = NULL, *icLast = NULL;
592 /* create an iCode chain from it */
593 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
596 /* maintain data flow .. add it to the */
597 /* ldefs defSet & outExprs of the preheader */
598 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
599 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
600 cdp->diCode->lineno = preHdr->ech->lineno;
601 addSetHead (&preHdr->outExprs, cdp);
605 icFirst = cdp->diCode;
608 icLast->next = cdp->diCode;
609 cdp->diCode->prev = icLast;
610 icLast = cdp->diCode;
613 icLast = cdp->diCode;
617 /* add the instruction chain to the end of the
618 preheader for this loop, preheaders will always
619 have atleast a label */
620 preHdr->ech->next = icFirst;
621 icFirst->prev = preHdr->ech;
622 preHdr->ech = icLast;
629 /*-----------------------------------------------------------------*/
630 /* addressTaken - returns true if the symbol is found in the addrof */
631 /*-----------------------------------------------------------------*/
633 addressTaken (set * sset, operand * sym)
639 for (loop = sset; loop; loop = loop->next)
645 if (isOperandEqual ((operand *) loop2->item, sym))
655 /*-----------------------------------------------------------------*/
656 /* findInduction :- returns 1 & the item if the induction is found */
657 /*-----------------------------------------------------------------*/
658 DEFSETFUNC (findInduction)
660 induction *ip = item;
661 V_ARG (operand *, sym);
662 V_ARG (induction **, ipp);
664 if (isOperandEqual (ip->sym, sym))
673 /*-----------------------------------------------------------------*/
674 /* findDefInRegion - finds the definition within the region */
675 /*-----------------------------------------------------------------*/
677 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
681 /* for all blocks in the region */
682 for (lBlock = setFirstItem (regBlocks); lBlock;
683 lBlock = setNextItem (regBlocks))
686 /* if a definition for this exists */
687 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
691 /* go thru the instruction chain to find it */
692 for (ic = lBlock->sch; ic; ic = ic->next)
693 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
705 /*-----------------------------------------------------------------*/
706 /* basicInduction - finds the basic induction variables in a loop */
707 /*-----------------------------------------------------------------*/
709 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
714 /* i.e. all assignments of the form a := a +/- const */
715 /* for all blocks within the loop do */
716 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
717 lBlock = setNextItem (loopReg->regBlocks))
722 /* for all instructions in the blocks do */
723 for (ic = lBlock->sch; ic; ic = ic->next)
727 unsigned long litValue;
730 eBBlock *owner = NULL;
733 /* look for assignments of the form */
734 /* symbolVar := iTempNN */
738 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
739 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
742 if (isOperandGlobal (IC_RESULT (ic)))
745 if (!IS_ITEMP (IC_RIGHT (ic)))
748 /* if it has multiple assignments within the loop then skip */
749 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
752 /* if the address of this was taken inside the loop then continue */
753 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
756 /* find the definition for the result in the block */
757 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
758 IC_RIGHT (ic), &owner)))
761 /* if not +/- continue */
762 if (dic->op != '+' && dic->op != '-')
765 /* make sure definition is of the form a +/- c */
766 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
769 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
770 (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
771 (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
773 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
774 !isOperandEqual (IC_RIGHT (ic), aSym))
777 /* find the definition for this and check */
778 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
785 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
786 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
790 /* if the right hand side has more than one usage then
791 don't make it an induction (will have to think some more) */
792 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
795 /* if the definition is volatile then it cannot be
796 an induction object */
797 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
798 isOperandVolatile (IC_RESULT (ic), FALSE))
801 /* whew !! that was a lot of work to find the definition */
802 /* create an induction object */
803 indIc = newiCode ('=', NULL, IC_RESULT (ic));
804 indIc->lineno = ic->lineno;
805 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
806 IC_RESULT (indIc)->isaddr = 0;
807 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
808 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
810 /* replace the inducted variable by the iTemp */
811 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
813 /* if it has only one exit then remove it from here
814 and put it in the exit block */
815 nexits = elementsInSet (loopReg->exits);
818 eBBlock *exit = setFirstItem (loopReg->exits);
820 /* if it is the same block then there is no
821 need to move it about */
824 iCode *saveic = ic->prev;
826 remiCodeFromeBBlock (lBlock, ic);
827 /* clear the definition */
828 bitVectUnSetBit (lBlock->defSet, ic->key);
829 /* add it to the exit */
830 addiCodeToeBBlock (exit, ic, NULL);
831 /* set the definition bit */
832 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
837 /* if the number of exits is greater than one then
838 we use another trick ; we will create an intersection
839 of succesors of the exits, then take those that are not
840 part of the loop and have dfNumber greater loop entry
841 and insert a new definition in them */
845 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
847 /* loopSuccs now contains intersection
848 of all the loops successors */
852 for (i = 0; i < loopSuccs->size; i++)
854 if (bitVectBitValue (loopSuccs, i))
857 eBBlock *eblock = ebbs[i];
859 /* if the successor does not belong to the loop
860 and will be executed after the loop : then
861 add a definition to the block */
862 if (!isinSet (loopReg->regBlocks, eblock) &&
863 eblock->dfnum > loopReg->entry->dfnum)
865 /* create the definition */
866 iCode *newic = newiCode ('=', NULL,
867 operandFromOperand (IC_RIGHT (ic)));
868 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
869 OP_DEFS(IC_RESULT (newic))=
870 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
871 OP_USES(IC_RIGHT (newic))=
872 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
874 if (eblock->sch && eblock->sch->op == LABEL)
875 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
877 addiCodeToeBBlock (eblock, newic, eblock->sch);
878 /* set the definition bit */
879 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
886 addSet (&indVars, ip);
889 } /* end of all blocks for basic induction variables */
894 /*-----------------------------------------------------------------*/
895 /* loopInduction - remove induction variables from a loop */
896 /*-----------------------------------------------------------------*/
898 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
901 eBBlock *lBlock, *lastBlock = NULL;
903 set *basicInd = NULL;
905 if (loopReg->entry->preHeader == NULL)
908 /* we first determine the basic Induction variables */
909 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
911 /* find other induction variables : by other we mean definitions of */
912 /* the form x := y (* | / ) <constant> .. we will move this one to */
913 /* beginning of the loop and reduce strength i.e. replace with +/- */
914 /* these expensive expressions: OH! and y must be induction too */
915 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
917 lBlock = setNextItem (loopReg->regBlocks))
923 /* last block is the one with the highest block
925 if (lastBlock->bbnum < lBlock->bbnum)
928 for (ic = lBlock->sch; ic; ic = ic->next)
931 unsigned long litVal;
934 /* consider only * & / */
935 if (ic->op != '*' && ic->op != '/')
938 /* if the result has more definitions then */
939 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
942 /* check if the operands are what we want */
943 /* i.e. one of them an symbol the other a literal */
944 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
945 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
948 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
949 (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
950 (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
953 /* check if this is an induction variable */
954 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
957 /* ask port for size not worth if native instruction
958 exist for multiply & divide */
959 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
960 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
963 /* if this is a division then the remainder should be zero
964 for it to be inducted */
965 if (ic->op == '/' && (ip->cval % litVal))
968 /* create the iCode to be placed in the loop header */
969 /* and create the induction object */
971 /* create an instruction */
972 /* this will be put on the loop header */
973 indIc = newiCode (ic->op,
974 operandFromOperand (aSym),
975 operandFromLit (litVal));
976 indIc->lineno = ic->lineno;
977 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
978 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
980 /* keep track of the inductions */
981 litVal = (ic->op == '*' ? (litVal * ip->cval) :
982 (ip->cval / litVal));
985 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
987 /* now change this instruction */
991 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
992 IC_RIGHT (ic) = operandFromLit (litVal);
996 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
997 IC_LEFT (ic) = operandFromLit (litVal);
1000 /* we need somemore initialisation code */
1001 /* we subtract the litVal from itself if increment */
1004 indIc = newiCode ('-',
1005 operandFromOperand (IC_RESULT (ic)),
1006 operandFromLit (litVal));
1007 indIc->lineno = ic->lineno;
1008 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1011 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1016 /* if we have some induction variables then */
1019 eBBlock *preHdr = loopReg->entry->preHeader;
1020 iCode *icFirst = NULL, *icLast = NULL;
1022 bitVect *indVect = NULL;
1024 /* create an iCode chain from it */
1025 for (ip = setFirstItem (indVars);
1027 ip = setNextItem (indVars))
1030 indVect = bitVectSetBit (indVect, ip->ic->key);
1031 ip->ic->lineno = preHdr->ech->lineno;
1036 icLast->next = ip->ic;
1037 ip->ic->prev = icLast;
1045 /* add the instruction chain to the end of the */
1046 /* preheader for this loop */
1047 preHdr->ech->next = icFirst;
1048 icFirst->prev = preHdr->ech;
1049 preHdr->ech = icLast;
1050 icLast->next = NULL;
1052 /* add the induction variable vector to the last
1053 block in the loop */
1054 lastBlock->isLastInLoop = 1;
1055 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1058 setToNull ((void **) &indVars);
1062 /*-----------------------------------------------------------------*/
1063 /* mergeRegions - will merge region with same entry point */
1064 /*-----------------------------------------------------------------*/
1065 DEFSETFUNC (mergeRegions)
1067 region *theLoop = item;
1068 V_ARG (set *, allRegion);
1071 /* if this has already been merged then do nothing */
1072 if (theLoop->merged)
1075 /* go thru all the region and check if any of them have the */
1076 /* entryPoint as the Loop */
1077 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1083 if (lp->entry == theLoop->entry)
1085 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1086 lp->regBlocks, THROW_DEST);
1094 /*-----------------------------------------------------------------*/
1095 /* ifMerged - return 1 if the merge flag is 1 */
1096 /*-----------------------------------------------------------------*/
1097 DEFSETFUNC (ifMerged)
1104 /*-----------------------------------------------------------------*/
1105 /* mergeInnerLoops - will merge into body when entry is present */
1106 /*-----------------------------------------------------------------*/
1107 DEFSETFUNC (mergeInnerLoops)
1109 region *theLoop = item;
1110 V_ARG (set *, allRegion);
1111 V_ARG (int *, maxDepth);
1114 /* check if the entry point is present in the body of any */
1115 /* loop then put the body of this loop into the outer loop */
1116 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1122 if (isinSet (lp->regBlocks, theLoop->entry))
1124 lp->containsLoops += theLoop->containsLoops + 1;
1125 if (lp->containsLoops > (*maxDepth))
1126 *maxDepth = lp->containsLoops;
1128 lp->regBlocks = unionSets (lp->regBlocks,
1129 theLoop->regBlocks, THROW_DEST);
1137 /*-----------------------------------------------------------------*/
1138 /* createLoopRegions - will detect and create a set of natural loops */
1139 /*-----------------------------------------------------------------*/
1141 createLoopRegions (eBBlock ** ebbs, int count)
1143 set *allRegion = NULL; /* set of all loops */
1144 hTab *orderedLoops = NULL;
1149 /* get all the back edges in the graph */
1150 if (!applyToSet (graphEdges, backEdges, &bEdges))
1151 return 0; /* found no loops */
1153 /* for each of these back edges get the blocks that */
1154 /* constitute the loops */
1155 applyToSet (bEdges, createLoop, &allRegion);
1157 /* now we will create regions from these loops */
1158 /* loops with the same entry points are considered to be the */
1159 /* same loop & they are merged. If the entry point of a loop */
1160 /* is found in the body of another loop then , all the blocks */
1161 /* in that loop are added to the loops containing the header */
1162 applyToSet (allRegion, mergeRegions, allRegion);
1164 /* delete those already merged */
1165 deleteItemIf (&allRegion, ifMerged);
1167 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1170 /* now create all the exits .. also */
1171 /* create an ordered set of loops */
1172 /* i.e. we process loops in the inner to outer order */
1173 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1175 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1176 lp->regBlocks, &lp->exits,
1177 (maxDepth - lp->containsLoops), lp);
1179 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1182 return orderedLoops;
1185 /*-----------------------------------------------------------------*/
1186 /* loopOptimizations - identify region & remove invariants & ind */
1187 /*-----------------------------------------------------------------*/
1189 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1195 /* if no loop optimizations requested */
1196 if (!optimize.loopInvariant &&
1197 !optimize.loopInduction)
1200 /* now we process the loops inner to outer order */
1201 /* this is essential to maintain data flow information */
1202 /* the other choice is an ugly iteration for the depth */
1203 /* of the loops would hate that */
1204 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1205 lp = hTabNextItem (orderedLoops, &k))
1208 if (optimize.loopInvariant)
1209 change += loopInvariants (lp, ebbs, count);
1211 if (optimize.loopInduction)
1212 change += loopInduction (lp, ebbs, count);
1218 /*-----------------------------------------------------------------*/
1219 /* addLoopBlocks - will add all blocks inside a loop to this loop */
1220 /* this should fix most of the liverange problems */
1221 /*-----------------------------------------------------------------*/
1223 addLoopBlocks (eBBlock ** ebbs, int count)
1226 struct eBBlock *block;
1230 for (i = 0; i < count; i++)
1232 if (!ebbs[i]->partOfLoop)
1235 /* for all loops this block belongs to */
1236 /* add inner block not already marked as part of this loop */
1237 aloop = setFirstItem (ebbs[i]->partOfLoop);
1238 for (; aloop; aloop = setNextItem (ebbs[i]->partOfLoop))
1246 /* set max & min Seq for loopRegion */
1247 block = setFirstItem (aloop->regBlocks);
1248 seqMax = block->lSeq;
1249 seqMin = block->fSeq;
1250 for (; block; block = setNextItem (aloop->regBlocks))
1252 if (block->lSeq > seqMax)
1253 seqMax = block->lSeq;
1254 if (block->fSeq < seqMin)
1255 seqMin = block->fSeq;
1258 /* add all blocks between seqMin, seqMax to loop */
1259 for (j = 0; j < count; j++)
1261 if (ebbs[j]->fSeq > seqMin && ebbs[j]->lSeq < seqMax &&
1262 !isinSet (aloop->regBlocks, ebbs[j]))
1264 if (!isinSet (ebbs[i]->partOfLoop, aloop))
1265 addSetHead (&ebbs[j]->partOfLoop, aloop);