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 /* NOTE: here we will update only the inner most loop
240 that it is a part of */
241 if (!ebp->partOfLoop)
242 ebp->partOfLoop = lr;
244 /* if any of the successors go out of the loop then */
245 /* we add this one to the exits */
246 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
248 addSetHead (exits, ebp);
255 /*-----------------------------------------------------------------*/
256 /* createLoop - will create a set of region */
257 /*-----------------------------------------------------------------*/
258 DEFSETFUNC (createLoop)
261 V_ARG (set **, allRegion);
262 V_ARG (eBBlock **,ebbs);
264 region *aloop = newRegion ();
266 int dfMin = count ,dfMax =0, i;
268 /* make sure regionStack is empty */
269 while (!STACK_EMPTY (regionStack))
270 STACK_POP (regionStack);
272 /* add the entryBlock */
273 addSet (&aloop->regBlocks, ep->to);
274 loopInsert (&aloop->regBlocks, ep->from);
276 while (!STACK_EMPTY (regionStack))
278 block = STACK_POP (regionStack);
279 /* if block != entry */
281 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
284 aloop->entry = ep->to;
286 /* set max & min dfNum for loopRegion */
287 for ( block = setFirstItem(aloop->regBlocks); block;
288 block = setNextItem(aloop->regBlocks)) {
289 if (block->dfnum > dfMax) dfMax = block->dfnum;
290 if (block->dfnum < dfMin) dfMin = block->dfnum;
293 /* all blocks that have dfnumbers between dfMin & dfMax are also
295 for (i = 0 ; i < count ; i++) {
296 if (ebbs[i]->dfnum > dfMin &&
297 ebbs[i]->dfnum < dfMax &&
298 !isinSet(aloop->regBlocks,ebbs[i])) {
299 if (!ebbs[i]->partOfLoop) {
300 ebbs[i]->partOfLoop = aloop;
305 /* and if this is a conditional block, the other side of the IFX
306 (if any, that could have a greater dfnum) is too */
308 // just a burp, but I'm getting close :)
312 /* now add it to the set */
313 addSetHead (allRegion, aloop);
317 /*-----------------------------------------------------------------*/
318 /* dominatedBy - will return 1 if item is dominated by block */
319 /*-----------------------------------------------------------------*/
320 DEFSETFUNC (dominatedBy)
323 V_ARG (eBBlock *, block);
325 return bitVectBitValue (ebp->domVect, block->bbnum);
328 /*-----------------------------------------------------------------*/
329 /* addDefInExprs - adds an expression into the inexpressions */
330 /*-----------------------------------------------------------------*/
331 DEFSETFUNC (addDefInExprs)
334 V_ARG (cseDef *, cdp);
335 V_ARG (eBBlock **, ebbs);
338 addSetHead (&ebp->inExprs, cdp);
339 cseBBlock (ebp, 0, ebbs, count);
343 /*-----------------------------------------------------------------*/
344 /* assignmentsToSym - for a set of blocks determine # time assigned */
345 /*-----------------------------------------------------------------*/
347 assignmentsToSym (set * sset, operand * sym)
351 set *blocks = setFromSet (sset);
353 for (ebp = setFirstItem (blocks); ebp;
354 ebp = setNextItem (blocks))
357 /* get all the definitions for this symbol
359 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
360 assigns += bitVectnBitsOn (defs);
361 setToNull ((void **) &defs);
369 /*-----------------------------------------------------------------*/
370 /* isOperandInvariant - determines if an operand is an invariant */
371 /*-----------------------------------------------------------------*/
373 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
376 /* operand is an invariant if it is a */
378 /* b. that have defintions reaching loop entry */
379 /* c. that are already defined as invariant */
380 /* d. has no assignments in the loop */
383 if (IS_OP_LITERAL (op))
385 else if (IS_SYMOP (op) &&
386 OP_SYMBOL (op)->addrtaken)
388 else if (ifDefSymIs (theLoop->entry->inExprs, op))
390 else if (ifDefSymIs (lInvars, op))
392 else if (IS_SYMOP (op) &&
393 !IS_OP_GLOBAL (op) &&
394 !IS_OP_VOLATILE (op) &&
395 assignmentsToSym (theLoop->regBlocks, op) == 0)
404 /*-----------------------------------------------------------------*/
405 /* pointerAssigned - will return 1 if pointer set found */
406 /*-----------------------------------------------------------------*/
407 DEFSETFUNC (pointerAssigned)
410 V_ARG (operand *, op);
412 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
415 /*-----------------------------------------------------------------*/
416 /* hasNonPtrUse - returns true if operand has non pointer usage */
417 /*-----------------------------------------------------------------*/
418 DEFSETFUNC (hasNonPtrUse)
421 V_ARG (operand *, op);
422 iCode *ic = usedInRemaining (op, ebp->sch);
424 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
431 /*-----------------------------------------------------------------*/
432 /* loopInvariants - takes loop invariants out of region */
433 /*-----------------------------------------------------------------*/
435 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
443 /* if the preHeader does not exist then do nothing */
444 /* or no exits then do nothing ( have to think about this situation */
445 if (theLoop->entry->preHeader == NULL ||
446 theLoop->exits == NULL)
449 /* we will do the elimination for those blocks */
450 /* in the loop that dominates all exits from the loop */
451 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
452 lBlock = setNextItem (theLoop->regBlocks))
459 /* mark the dominates all exits flag */
460 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
461 elementsInSet (theLoop->exits));
463 /* find out if we have a function call in this block */
464 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
470 /* now we go thru the instructions of this block and */
471 /* collect those instructions with invariant operands */
472 for (ic = lBlock->sch; ic; ic = ic->next)
478 /* TODO this is only needed if the call is between
479 here and the definition, but I am too lazy to do that now */
481 /* if there are function calls in this block */
484 /* if this is a pointer get */
485 if (POINTER_GET(ic)) {
489 /* if this is an assignment from a global */
490 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
495 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
498 /* if result is volatile then skip */
499 if (IC_RESULT (ic) &&
500 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
501 IS_OP_PARM (IC_RESULT (ic))))
504 /* if result depends on a volatile then skip */
505 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
506 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
512 /* if address of then it is an invariant */
513 if (ic->op == ADDRESS_OF &&
514 IS_SYMOP (IC_LEFT (ic)) &&
515 IS_AGGREGATE (operandType (IC_LEFT (ic))))
518 /* check if left operand is an invariant */
519 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
520 /* if this is a pointer get then make sure
521 that the pointer set does not exist in
523 if (POINTER_GET (ic) &&
524 (applyToSet (theLoop->regBlocks,
525 pointerAssigned, IC_LEFT (ic))))
529 /* do the same for right */
530 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
532 /* if this is a POINTER_GET then special case, make sure all
533 usages within the loop are POINTER_GET any other usage
534 would mean that this is not an invariant , since the pointer
535 could then be passed as a parameter */
536 if (POINTER_GET (ic) &&
537 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
540 /* if both the left & right are invariants : then check that */
541 /* this definition exists in the out definition of all the */
542 /* blocks, this will ensure that this is not assigned any */
543 /* other value in the loop , and not used in this block */
544 /* prior to this definition which means only this definition */
545 /* is used in this loop */
546 if (lin && rin && IC_RESULT (ic))
549 set *lSet = setFromSet (theLoop->regBlocks);
551 /* if this block does not dominate all exists */
552 /* make sure this defintion is not used anywhere else */
556 if (isOperandGlobal (IC_RESULT (ic)))
558 /* for successors for all exits */
559 for (sBlock = setFirstItem (theLoop->exits); sBlock;
560 sBlock = setNextItem (theLoop->exits))
563 for (i = 0; i < count; ebbs[i++]->visited = 0);
565 if (applyToSet (sBlock->succList, isDefAlive, ic))
569 /* we have found usage */
574 /* now make sure this is the only definition */
575 for (sBlock = setFirstItem (lSet); sBlock;
576 sBlock = setNextItem (lSet))
578 /* if this is the block make sure the definition */
579 /* reaches the end of the block */
580 if (sBlock == lBlock)
582 if (!ifDiCodeIs (sBlock->outExprs, ic))
585 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
590 continue; /* another definition present in the block */
592 /* now check if it exists in the in of this block */
593 /* if not then it was killed before this instruction */
594 if (!bitVectBitValue (lBlock->inDefs, ic->key))
597 /* now we know it is a true invariant */
598 /* remove it from the insts chain & put */
599 /* in the invariant set */
600 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
601 remiCodeFromeBBlock (lBlock, ic);
603 /* maintain the data flow */
604 /* this means removing from definition from the */
605 /* defset of this block and adding it to the */
606 /* inexpressions of all blocks within the loop */
607 bitVectUnSetBit (lBlock->defSet, ic->key);
608 bitVectUnSetBit (lBlock->ldefs, ic->key);
609 ivar = newCseDef (IC_RESULT (ic), ic);
610 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
611 addSet (&lInvars, ivar);
614 } /* for all loop blocks */
616 /* if we have some invariants then */
619 eBBlock *preHdr = theLoop->entry->preHeader;
620 iCode *icFirst = NULL, *icLast = NULL;
623 /* create an iCode chain from it */
624 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
627 /* maintain data flow .. add it to the */
628 /* ldefs defSet & outExprs of the preheader */
629 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
630 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
631 cdp->diCode->lineno = preHdr->ech->lineno;
632 addSetHead (&preHdr->outExprs, cdp);
636 icFirst = cdp->diCode;
639 icLast->next = cdp->diCode;
640 cdp->diCode->prev = icLast;
641 icLast = cdp->diCode;
644 icLast = cdp->diCode;
648 /* add the instruction chain to the end of the
649 preheader for this loop, preheaders will always
650 have atleast a label */
651 preHdr->ech->next = icFirst;
652 icFirst->prev = preHdr->ech;
653 preHdr->ech = icLast;
660 /*-----------------------------------------------------------------*/
661 /* addressTaken - returns true if the symbol is found in the addrof */
662 /*-----------------------------------------------------------------*/
664 addressTaken (set * sset, operand * sym)
670 for (loop = sset; loop; loop = loop->next)
676 if (isOperandEqual ((operand *) loop2->item, sym))
686 /*-----------------------------------------------------------------*/
687 /* findInduction :- returns 1 & the item if the induction is found */
688 /*-----------------------------------------------------------------*/
689 DEFSETFUNC (findInduction)
691 induction *ip = item;
692 V_ARG (operand *, sym);
693 V_ARG (induction **, ipp);
695 if (isOperandEqual (ip->sym, sym))
704 /*-----------------------------------------------------------------*/
705 /* findDefInRegion - finds the definition within the region */
706 /*-----------------------------------------------------------------*/
708 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
712 /* for all blocks in the region */
713 for (lBlock = setFirstItem (regBlocks); lBlock;
714 lBlock = setNextItem (regBlocks))
717 /* if a definition for this exists */
718 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
722 /* go thru the instruction chain to find it */
723 for (ic = lBlock->sch; ic; ic = ic->next)
724 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
736 /*-----------------------------------------------------------------*/
737 /* basicInduction - finds the basic induction variables in a loop */
738 /*-----------------------------------------------------------------*/
740 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
745 /* i.e. all assignments of the form a := a +/- const */
746 /* for all blocks within the loop do */
747 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
748 lBlock = setNextItem (loopReg->regBlocks))
753 /* for all instructions in the blocks do */
754 for (ic = lBlock->sch; ic; ic = ic->next)
758 unsigned long litValue;
761 eBBlock *owner = NULL;
764 /* look for assignments of the form */
765 /* symbolVar := iTempNN */
769 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
770 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
773 if (isOperandGlobal (IC_RESULT (ic)))
776 if (!IS_ITEMP (IC_RIGHT (ic)))
779 /* if it has multiple assignments within the loop then skip */
780 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
783 /* if the address of this was taken inside the loop then continue */
784 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
787 /* find the definition for the result in the block */
788 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
789 IC_RIGHT (ic), &owner)))
792 /* if not +/- continue */
793 if (dic->op != '+' && dic->op != '-')
796 /* make sure definition is of the form a +/- c */
797 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
800 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
801 (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
802 (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
804 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
805 !isOperandEqual (IC_RIGHT (ic), aSym))
808 /* find the definition for this and check */
809 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
816 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
817 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
821 /* if the right hand side has more than one usage then
822 don't make it an induction (will have to think some more) */
823 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
826 /* if the definition is volatile then it cannot be
827 an induction object */
828 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
829 isOperandVolatile (IC_RESULT (ic), FALSE))
832 /* whew !! that was a lot of work to find the definition */
833 /* create an induction object */
834 indIc = newiCode ('=', NULL, IC_RESULT (ic));
835 indIc->lineno = ic->lineno;
836 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
837 IC_RESULT (indIc)->isaddr = 0;
838 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
839 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
841 /* replace the inducted variable by the iTemp */
842 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
844 /* if it has only one exit then remove it from here
845 and put it in the exit block */
846 nexits = elementsInSet (loopReg->exits);
849 eBBlock *exit = setFirstItem (loopReg->exits);
851 /* if it is the same block then there is no
852 need to move it about */
855 iCode *saveic = ic->prev;
857 remiCodeFromeBBlock (lBlock, ic);
858 /* clear the definition */
859 bitVectUnSetBit (lBlock->defSet, ic->key);
860 /* add it to the exit */
861 addiCodeToeBBlock (exit, ic, NULL);
862 /* set the definition bit */
863 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
868 /* if the number of exits is greater than one then
869 we use another trick ; we will create an intersection
870 of succesors of the exits, then take those that are not
871 part of the loop and have dfNumber greater loop entry
872 and insert a new definition in them */
876 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
878 /* loopSuccs now contains intersection
879 of all the loops successors */
883 for (i = 0; i < loopSuccs->size; i++)
885 if (bitVectBitValue (loopSuccs, i))
888 eBBlock *eblock = ebbs[i];
890 /* if the successor does not belong to the loop
891 and will be executed after the loop : then
892 add a definition to the block */
893 if (!isinSet (loopReg->regBlocks, eblock) &&
894 eblock->dfnum > loopReg->entry->dfnum)
896 /* create the definition */
897 iCode *newic = newiCode ('=', NULL,
898 operandFromOperand (IC_RIGHT (ic)));
899 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
900 OP_DEFS(IC_RESULT (newic))=
901 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
902 OP_USES(IC_RIGHT (newic))=
903 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
905 if (eblock->sch && eblock->sch->op == LABEL)
906 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
908 addiCodeToeBBlock (eblock, newic, eblock->sch);
909 /* set the definition bit */
910 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
917 addSet (&indVars, ip);
920 } /* end of all blocks for basic induction variables */
925 /*-----------------------------------------------------------------*/
926 /* loopInduction - remove induction variables from a loop */
927 /*-----------------------------------------------------------------*/
929 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
932 eBBlock *lBlock, *lastBlock = NULL;
934 set *basicInd = NULL;
936 if (loopReg->entry->preHeader == NULL)
939 /* we first determine the basic Induction variables */
940 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
942 /* find other induction variables : by other we mean definitions of */
943 /* the form x := y (* | / ) <constant> .. we will move this one to */
944 /* beginning of the loop and reduce strength i.e. replace with +/- */
945 /* these expensive expressions: OH! and y must be induction too */
946 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
948 lBlock = setNextItem (loopReg->regBlocks))
954 /* last block is the one with the highest block
956 if (lastBlock->bbnum < lBlock->bbnum)
959 for (ic = lBlock->sch; ic; ic = ic->next)
962 unsigned long litVal;
965 /* consider only * & / */
966 if (ic->op != '*' && ic->op != '/')
969 /* if the result has more definitions then */
970 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
973 /* check if the operands are what we want */
974 /* i.e. one of them an symbol the other a literal */
975 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
976 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
979 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
980 (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
981 (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
984 /* check if this is an induction variable */
985 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
988 /* ask port for size not worth if native instruction
989 exist for multiply & divide */
990 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
991 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
994 /* if this is a division then the remainder should be zero
995 for it to be inducted */
996 if (ic->op == '/' && (ip->cval % litVal))
999 /* create the iCode to be placed in the loop header */
1000 /* and create the induction object */
1002 /* create an instruction */
1003 /* this will be put on the loop header */
1004 indIc = newiCode (ic->op,
1005 operandFromOperand (aSym),
1006 operandFromLit (litVal));
1007 indIc->lineno = ic->lineno;
1008 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1009 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1011 /* keep track of the inductions */
1012 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1013 (ip->cval / litVal));
1016 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1018 /* now change this instruction */
1022 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1023 IC_RIGHT (ic) = operandFromLit (litVal);
1027 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1028 IC_LEFT (ic) = operandFromLit (litVal);
1031 /* we need somemore initialisation code */
1032 /* we subtract the litVal from itself if increment */
1035 indIc = newiCode ('-',
1036 operandFromOperand (IC_RESULT (ic)),
1037 operandFromLit (litVal));
1038 indIc->lineno = ic->lineno;
1039 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1042 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1047 /* if we have some induction variables then */
1050 eBBlock *preHdr = loopReg->entry->preHeader;
1051 iCode *icFirst = NULL, *icLast = NULL;
1053 bitVect *indVect = NULL;
1055 /* create an iCode chain from it */
1056 for (ip = setFirstItem (indVars);
1058 ip = setNextItem (indVars))
1061 indVect = bitVectSetBit (indVect, ip->ic->key);
1062 ip->ic->lineno = preHdr->ech->lineno;
1067 icLast->next = ip->ic;
1068 ip->ic->prev = icLast;
1076 /* add the instruction chain to the end of the */
1077 /* preheader for this loop */
1078 preHdr->ech->next = icFirst;
1079 icFirst->prev = preHdr->ech;
1080 preHdr->ech = icLast;
1081 icLast->next = NULL;
1083 /* add the induction variable vector to the last
1084 block in the loop */
1085 lastBlock->isLastInLoop = 1;
1086 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1089 setToNull ((void **) &indVars);
1093 /*-----------------------------------------------------------------*/
1094 /* mergeRegions - will merge region with same entry point */
1095 /*-----------------------------------------------------------------*/
1096 DEFSETFUNC (mergeRegions)
1098 region *theLoop = item;
1099 V_ARG (set *, allRegion);
1102 /* if this has already been merged then do nothing */
1103 if (theLoop->merged)
1106 /* go thru all the region and check if any of them have the */
1107 /* entryPoint as the Loop */
1108 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1114 if (lp->entry == theLoop->entry)
1116 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1117 lp->regBlocks, THROW_DEST);
1125 /*-----------------------------------------------------------------*/
1126 /* ifMerged - return 1 if the merge flag is 1 */
1127 /*-----------------------------------------------------------------*/
1128 DEFSETFUNC (ifMerged)
1135 /*-----------------------------------------------------------------*/
1136 /* mergeInnerLoops - will merge into body when entry is present */
1137 /*-----------------------------------------------------------------*/
1138 DEFSETFUNC (mergeInnerLoops)
1140 region *theLoop = item;
1141 V_ARG (set *, allRegion);
1142 V_ARG (int *, maxDepth);
1145 /* check if the entry point is present in the body of any */
1146 /* loop then put the body of this loop into the outer loop */
1147 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1153 if (isinSet (lp->regBlocks, theLoop->entry))
1155 lp->containsLoops += theLoop->containsLoops + 1;
1156 if (lp->containsLoops > (*maxDepth))
1157 *maxDepth = lp->containsLoops;
1159 lp->regBlocks = unionSets (lp->regBlocks,
1160 theLoop->regBlocks, THROW_DEST);
1168 /*-----------------------------------------------------------------*/
1169 /* createLoopRegions - will detect and create a set of natural loops */
1170 /*-----------------------------------------------------------------*/
1172 createLoopRegions (eBBlock ** ebbs, int count)
1174 set *allRegion = NULL; /* set of all loops */
1175 hTab *orderedLoops = NULL;
1180 /* get all the back edges in the graph */
1181 if (!applyToSet (graphEdges, backEdges, &bEdges))
1182 return 0; /* found no loops */
1184 /* for each of these back edges get the blocks that */
1185 /* constitute the loops */
1186 applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1188 /* now we will create regions from these loops */
1189 /* loops with the same entry points are considered to be the */
1190 /* same loop & they are merged. If the entry point of a loop */
1191 /* is found in the body of another loop then , all the blocks */
1192 /* in that loop are added to the loops containing the header */
1193 applyToSet (allRegion, mergeRegions, allRegion);
1195 /* delete those already merged */
1196 deleteItemIf (&allRegion, ifMerged);
1198 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1201 /* now create all the exits .. also */
1202 /* create an ordered set of loops */
1203 /* i.e. we process loops in the inner to outer order */
1204 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1206 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1207 lp->regBlocks, &lp->exits,
1208 (maxDepth - lp->containsLoops), lp);
1210 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1213 return orderedLoops;
1216 /*-----------------------------------------------------------------*/
1217 /* loopOptimizations - identify region & remove invariants & ind */
1218 /*-----------------------------------------------------------------*/
1220 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1226 /* if no loop optimizations requested */
1227 if (!optimize.loopInvariant &&
1228 !optimize.loopInduction)
1231 /* now we process the loops inner to outer order */
1232 /* this is essential to maintain data flow information */
1233 /* the other choice is an ugly iteration for the depth */
1234 /* of the loops would hate that */
1235 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1236 lp = hTabNextItem (orderedLoops, &k))
1239 if (optimize.loopInvariant)
1240 change += loopInvariants (lp, ebbs, count);
1242 if (optimize.loopInduction)
1243 change += loopInduction (lp, ebbs, count);