1 //#define LIVERANGEHUNT
7 /*-------------------------------------------------------------------------
9 SDCCloop.c - source file for loop detection & optimizations
11 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
13 This program is free software; you can redistribute it and/or modify it
14 under the terms of the GNU General Public License as published by the
15 Free Software Foundation; either version 2, or (at your option) any
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 In other words, you are welcome to use, share and improve this program.
28 You are forbidden to forbid anyone else to use, share and improve
29 what you give them. Help stamp out software-hoarding!
30 -------------------------------------------------------------------------*/
35 DEFSETFUNC (isDefAlive);
37 STACK_DCL (regionStack, eBBlock *, MAX_NEST_LEVEL * 10);
39 /*-----------------------------------------------------------------*/
40 /* newInduction - creates a new induction variable */
41 /*-----------------------------------------------------------------*/
43 newInduction (operand * sym, unsigned int op,
44 long constVal, iCode * ic, operand * asym)
48 ip = Safe_alloc ( sizeof (induction));
55 updateSpillLocation(ic,1);
59 /*-----------------------------------------------------------------*/
60 /* newRegion - allocate & returns a loop structure */
61 /*-----------------------------------------------------------------*/
67 lp = Safe_alloc ( sizeof (region));
73 /*-----------------------------------------------------------------*/
74 /* pinduction - prints induction */
75 /*-----------------------------------------------------------------*/
76 DEFSETFUNC (pinduction)
81 fprintf (stdout, "\t");
82 printOperand (ip->sym, stdout);
83 icTab = getTableEntry (ip->ic->op);
84 icTab->iCodePrint (stdout, ip->ic, icTab->printName);
85 fprintf (stdout, " %04d\n", (int) ip->cval);
89 /*-----------------------------------------------------------------*/
90 /* pregion - prints loop information */
91 /*-----------------------------------------------------------------*/
96 printf ("================\n");
97 printf (" loop with entry -- > ");
98 printEntryLabel (lp->entry, ap);
100 printf (" loop body --> ");
101 applyToSet (lp->regBlocks, printEntryLabel);
103 printf (" loop exits --> ");
104 applyToSet (lp->exits, printEntryLabel);
109 /*-----------------------------------------------------------------*/
110 /* backEdges - returns a list of back edges */
111 /*-----------------------------------------------------------------*/
112 DEFSETFUNC (backEdges)
115 V_ARG (set **, bEdges);
117 /* if this is a back edge ; to determine this we check */
118 /* to see if the 'to' is in the dominator list of the */
119 /* 'from' if yes then this is a back edge */
120 if (bitVectBitValue (ep->from->domVect, ep->to->bbnum))
122 addSetHead (bEdges, ep);
129 /*-----------------------------------------------------------------*/
130 /* intersectLoopSucc - returns intersection of loop Successors */
131 /*-----------------------------------------------------------------*/
133 intersectLoopSucc (set * lexits, eBBlock ** ebbs)
135 bitVect *succVect = NULL;
136 eBBlock *exit = setFirstItem (lexits);
141 succVect = bitVectCopy (exit->succVect);
143 for (exit = setNextItem (lexits); exit;
144 exit = setNextItem (lexits))
146 succVect = bitVectIntersect (succVect,
154 /*-----------------------------------------------------------------*/
155 /* loopInsert will insert a block into the loop set */
156 /*-----------------------------------------------------------------*/
158 loopInsert (set ** regionSet, eBBlock * block)
160 if (!isinSet (*regionSet, block))
162 LRH(printf ("loopInsert: %s\n", block->entryLabel->name));
163 addSetHead (regionSet, block);
164 STACK_PUSH (regionStack, block);
168 /*-----------------------------------------------------------------*/
169 /* insertIntoLoop - insert item into loop */
170 /*-----------------------------------------------------------------*/
171 DEFSETFUNC (insertIntoLoop)
174 V_ARG (set **, regionSet);
176 loopInsert (regionSet, ebp);
180 /*-----------------------------------------------------------------*/
181 /* isNotInBlocks - will return 1 if not is blocks */
182 /*-----------------------------------------------------------------*/
183 DEFSETFUNC (isNotInBlocks)
186 V_ARG (set *, blocks);
188 if (!isinSet (blocks, ebp))
194 /*-----------------------------------------------------------------*/
195 /* hasIncomingDefs - has definitions coming into the loop. i.e. */
196 /* check to see if the preheaders outDefs has any definitions */
197 /*-----------------------------------------------------------------*/
199 hasIncomingDefs (region * lreg, operand * op)
201 eBBlock *preHdr = lreg->entry->preHeader;
203 if (preHdr && bitVectBitsInCommon (preHdr->outDefs, OP_DEFS (op)))
208 /*-----------------------------------------------------------------*/
209 /* findLoopEndSeq - will return the sequence number of the last */
210 /* iCode with the maximum dfNumber in the region */
211 /*-----------------------------------------------------------------*/
213 findLoopEndSeq (region * lreg)
218 for (block = lblock = setFirstItem (lreg->regBlocks); block;
219 block = setNextItem (lreg->regBlocks))
221 if (block != lblock && block->lSeq > lblock->lSeq)
228 /*-----------------------------------------------------------------*/
229 /* addToExitsMarkDepth - will add the the exitSet all blocks that */
230 /* have exits, will also update the depth field in the blocks */
231 /*-----------------------------------------------------------------*/
232 DEFSETFUNC (addToExitsMarkDepth)
235 V_ARG (set *, loopBlocks);
236 V_ARG (set **, exits);
238 V_ARG (region *, lr);
239 LRH(printf ("addToExitsMarkDepth: %s %d\n", ebp->entryLabel->name, depth));
240 /* mark the loop depth of this block */
242 if (ebp->depth<depth)
245 /* put the loop region info in the block */
246 /* NOTE: here we will update only the inner most loop
247 that it is a part of */
248 if (!ebp->partOfLoop)
249 ebp->partOfLoop = lr;
251 /* if any of the successors go out of the loop then */
252 /* we add this one to the exits */
253 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
255 addSetHead (exits, ebp);
262 /*-----------------------------------------------------------------*/
263 /* createLoop - will create a set of region */
264 /*-----------------------------------------------------------------*/
265 DEFSETFUNC (createLoop)
268 V_ARG (set **, allRegion);
269 V_ARG (eBBlock **,ebbs);
271 region *aloop = newRegion ();
273 int dfMin = count ,dfMax =0, i;
275 LRH(printf("CreateLoop\n"));
276 /* make sure regionStack is empty */
277 while (!STACK_EMPTY (regionStack))
278 STACK_POP (regionStack);
280 /* add the entryBlock */
281 addSet (&aloop->regBlocks, ep->to);
283 // print regBlocks jwk
287 for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
288 printf ("cl1 %s ", ebp->entryLabel->name);
290 printf (" %d\n", count);
293 loopInsert (&aloop->regBlocks, ep->from);
295 // print regBlocks jwk
299 for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
300 printf ("cl2 %s ", ebp->entryLabel->name);
302 printf (" %d\n", count);
306 while (!STACK_EMPTY (regionStack))
308 block = STACK_POP (regionStack);
309 /* if block != entry */
311 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
315 // print regBlocks jwk
319 for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
320 printf ("cl3 %s ", ebp->entryLabel->name);
322 printf (" %d\n", count);
326 aloop->entry = ep->to;
327 /* set max & min dfNum for loopRegion */
328 for ( block = setFirstItem(aloop->regBlocks); block;
329 block = setNextItem(aloop->regBlocks)) {
330 if (block->dfnum > dfMax) dfMax = block->dfnum;
331 if (block->dfnum < dfMin) dfMin = block->dfnum;
334 /* all blocks that have dfnumbers between dfMin & dfMax are also
336 for (i = 0 ; i < count ; i++) {
337 if (ebbs[i]->dfnum > dfMin &&
338 ebbs[i]->dfnum < dfMax &&
339 !isinSet(aloop->regBlocks,ebbs[i])) {
340 if (!ebbs[i]->partOfLoop) {
341 #if !defined(LIVERANGEHUNT)
342 ebbs[i]->partOfLoop = aloop;
344 loopInsert(&aloop->regBlocks,ebbs[i]);
351 printf ("================\n");
352 printf (" loop with entry -- > ");
353 printEntryLabel (aloop->entry, ap);
355 printf (" loop body --> ");
356 applyToSet (aloop->regBlocks, printEntryLabel);
358 printf (" loop exits --> ");
359 applyToSet (aloop->exits, printEntryLabel);
363 /* and if this is a conditional block, the other side of the IFX
364 (if any, that could have a greater dfnum) is too */
366 // just a burp, but I'm getting close :)
370 /* now add it to the set */
371 addSetHead (allRegion, aloop);
375 /*-----------------------------------------------------------------*/
376 /* dominatedBy - will return 1 if item is dominated by block */
377 /*-----------------------------------------------------------------*/
378 DEFSETFUNC (dominatedBy)
381 V_ARG (eBBlock *, block);
383 return bitVectBitValue (ebp->domVect, block->bbnum);
386 /*-----------------------------------------------------------------*/
387 /* addDefInExprs - adds an expression into the inexpressions */
388 /*-----------------------------------------------------------------*/
389 DEFSETFUNC (addDefInExprs)
392 V_ARG (cseDef *, cdp);
393 V_ARG (eBBlock **, ebbs);
396 addSetHead (&ebp->inExprs, cdp);
397 cseBBlock (ebp, 0, ebbs, count);
401 /*-----------------------------------------------------------------*/
402 /* assignmentsToSym - for a set of blocks determine # time assigned */
403 /*-----------------------------------------------------------------*/
405 assignmentsToSym (set * sset, operand * sym)
409 set *blocks = setFromSet (sset);
411 for (ebp = setFirstItem (blocks); ebp;
412 ebp = setNextItem (blocks))
415 /* get all the definitions for this symbol
417 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
418 assigns += bitVectnBitsOn (defs);
419 setToNull ((void **) &defs);
427 /*-----------------------------------------------------------------*/
428 /* isOperandInvariant - determines if an operand is an invariant */
429 /*-----------------------------------------------------------------*/
431 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
434 /* operand is an invariant if it is a */
436 /* b. that have defintions reaching loop entry */
437 /* c. that are already defined as invariant */
438 /* d. has no assignments in the loop */
441 if (IS_OP_LITERAL (op))
443 else if (IS_SYMOP (op) &&
444 OP_SYMBOL (op)->addrtaken)
446 else if (ifDefSymIs (theLoop->entry->inExprs, op))
448 else if (ifDefSymIs (lInvars, op))
450 else if (IS_SYMOP (op) &&
451 !IS_OP_GLOBAL (op) &&
452 !IS_OP_VOLATILE (op) &&
453 assignmentsToSym (theLoop->regBlocks, op) == 0)
455 LRH(if (opin && IS_SYMOP(op)) {
456 printf("isOperandInvariant: %s\n", OP_SYMBOL(op)->name);
465 /*-----------------------------------------------------------------*/
466 /* pointerAssigned - will return 1 if pointer set found */
467 /*-----------------------------------------------------------------*/
468 DEFSETFUNC (pointerAssigned)
471 V_ARG (operand *, op);
473 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
476 /*-----------------------------------------------------------------*/
477 /* hasNonPtrUse - returns true if operand has non pointer usage */
478 /*-----------------------------------------------------------------*/
479 DEFSETFUNC (hasNonPtrUse)
482 V_ARG (operand *, op);
483 iCode *ic = usedInRemaining (op, ebp->sch);
485 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
492 /*-----------------------------------------------------------------*/
493 /* loopInvariants - takes loop invariants out of region */
494 /*-----------------------------------------------------------------*/
496 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
504 /* if the preHeader does not exist then do nothing */
505 /* or no exits then do nothing ( have to think about this situation */
506 if (theLoop->entry->preHeader == NULL ||
507 theLoop->exits == NULL)
510 /* we will do the elimination for those blocks */
511 /* in the loop that dominates all exits from the loop */
512 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
513 lBlock = setNextItem (theLoop->regBlocks))
520 /* mark the dominates all exits flag */
521 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
522 elementsInSet (theLoop->exits));
524 /* find out if we have a function call in this block */
525 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
531 /* now we go thru the instructions of this block and */
532 /* collect those instructions with invariant operands */
533 for (ic = lBlock->sch; ic; ic = ic->next)
539 /* jwk: TODO this is only needed if the call is between
540 here and the definition, but I am too lazy to do that now */
542 /* if there are function calls in this block */
545 /* if this is a pointer get */
546 if (POINTER_GET(ic)) {
550 /* if this is an assignment from a global */
551 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
556 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
559 /* if result is volatile then skip */
560 if (IC_RESULT (ic) &&
561 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
562 IS_OP_PARM (IC_RESULT (ic))))
565 /* if result depends on a volatile then skip */
566 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
567 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
573 /* if address of then it is an invariant */
574 if (ic->op == ADDRESS_OF &&
575 IS_SYMOP (IC_LEFT (ic)) &&
576 IS_AGGREGATE (operandType (IC_LEFT (ic))))
579 /* check if left operand is an invariant */
580 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
581 /* if this is a pointer get then make sure
582 that the pointer set does not exist in
584 if (POINTER_GET (ic) &&
585 (applyToSet (theLoop->regBlocks,
586 pointerAssigned, IC_LEFT (ic))))
590 /* do the same for right */
591 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
593 /* if this is a POINTER_GET then special case, make sure all
594 usages within the loop are POINTER_GET any other usage
595 would mean that this is not an invariant , since the pointer
596 could then be passed as a parameter */
597 if (POINTER_GET (ic) &&
598 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
601 /* if both the left & right are invariants : then check that */
602 /* this definition exists in the out definition of all the */
603 /* blocks, this will ensure that this is not assigned any */
604 /* other value in the loop , and not used in this block */
605 /* prior to this definition which means only this definition */
606 /* is used in this loop */
607 if (lin && rin && IC_RESULT (ic))
610 set *lSet = setFromSet (theLoop->regBlocks);
612 /* if this block does not dominate all exists */
613 /* make sure this defintion is not used anywhere else */
617 if (isOperandGlobal (IC_RESULT (ic)))
619 /* for successors for all exits */
620 for (sBlock = setFirstItem (theLoop->exits); sBlock;
621 sBlock = setNextItem (theLoop->exits))
624 for (i = 0; i < count; ebbs[i++]->visited = 0);
626 if (applyToSet (sBlock->succList, isDefAlive, ic))
630 /* we have found usage */
635 /* now make sure this is the only definition */
636 for (sBlock = setFirstItem (lSet); sBlock;
637 sBlock = setNextItem (lSet))
639 /* if this is the block make sure the definition */
640 /* reaches the end of the block */
641 if (sBlock == lBlock)
643 if (!ifDiCodeIs (sBlock->outExprs, ic))
646 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
651 continue; /* another definition present in the block */
653 /* now check if it exists in the in of this block */
654 /* if not then it was killed before this instruction */
655 if (!bitVectBitValue (lBlock->inDefs, ic->key))
658 /* now we know it is a true invariant */
659 /* remove it from the insts chain & put */
660 /* in the invariant set */
661 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
662 remiCodeFromeBBlock (lBlock, ic);
664 /* maintain the data flow */
665 /* this means removing from definition from the */
666 /* defset of this block and adding it to the */
667 /* inexpressions of all blocks within the loop */
668 bitVectUnSetBit (lBlock->defSet, ic->key);
669 bitVectUnSetBit (lBlock->ldefs, ic->key);
670 ivar = newCseDef (IC_RESULT (ic), ic);
671 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
672 addSet (&lInvars, ivar);
675 } /* for all loop blocks */
677 /* if we have some invariants then */
680 eBBlock *preHdr = theLoop->entry->preHeader;
681 iCode *icFirst = NULL, *icLast = NULL;
684 /* create an iCode chain from it */
685 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
688 /* maintain data flow .. add it to the */
689 /* ldefs defSet & outExprs of the preheader */
690 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
691 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
692 cdp->diCode->lineno = preHdr->ech->lineno;
693 addSetHead (&preHdr->outExprs, cdp);
697 icFirst = cdp->diCode;
700 icLast->next = cdp->diCode;
701 cdp->diCode->prev = icLast;
702 icLast = cdp->diCode;
705 icLast = cdp->diCode;
709 /* add the instruction chain to the end of the
710 preheader for this loop, preheaders will always
711 have atleast a label */
712 preHdr->ech->next = icFirst;
713 icFirst->prev = preHdr->ech;
714 preHdr->ech = icLast;
721 /*-----------------------------------------------------------------*/
722 /* addressTaken - returns true if the symbol is found in the addrof */
723 /*-----------------------------------------------------------------*/
725 addressTaken (set * sset, operand * sym)
731 for (loop = sset; loop; loop = loop->next)
737 if (isOperandEqual ((operand *) loop2->item, sym))
747 /*-----------------------------------------------------------------*/
748 /* findInduction :- returns 1 & the item if the induction is found */
749 /*-----------------------------------------------------------------*/
750 DEFSETFUNC (findInduction)
752 induction *ip = item;
753 V_ARG (operand *, sym);
754 V_ARG (induction **, ipp);
756 if (isOperandEqual (ip->sym, sym))
765 /*-----------------------------------------------------------------*/
766 /* findDefInRegion - finds the definition within the region */
767 /*-----------------------------------------------------------------*/
769 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
773 /* for all blocks in the region */
774 for (lBlock = setFirstItem (regBlocks); lBlock;
775 lBlock = setNextItem (regBlocks))
778 /* if a definition for this exists */
779 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
783 /* go thru the instruction chain to find it */
784 for (ic = lBlock->sch; ic; ic = ic->next)
785 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
797 /*-----------------------------------------------------------------*/
798 /* basicInduction - finds the basic induction variables in a loop */
799 /*-----------------------------------------------------------------*/
801 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
806 /* i.e. all assignments of the form a := a +/- const */
807 /* for all blocks within the loop do */
808 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
809 lBlock = setNextItem (loopReg->regBlocks))
814 /* for all instructions in the blocks do */
815 for (ic = lBlock->sch; ic; ic = ic->next)
819 unsigned long litValue;
822 eBBlock *owner = NULL;
825 /* look for assignments of the form */
826 /* symbolVar := iTempNN */
830 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
831 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
834 if (isOperandGlobal (IC_RESULT (ic)))
837 if (!IS_ITEMP (IC_RIGHT (ic)))
840 /* if it has multiple assignments within the loop then skip */
841 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
844 /* if the address of this was taken inside the loop then continue */
845 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
848 /* find the definition for the result in the block */
849 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
850 IC_RIGHT (ic), &owner)))
853 /* if not +/- continue */
854 if (dic->op != '+' && dic->op != '-')
857 /* make sure definition is of the form a +/- c */
858 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
861 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
862 (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
863 (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
865 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
866 !isOperandEqual (IC_RIGHT (ic), aSym))
869 /* find the definition for this and check */
870 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
877 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
878 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
882 /* if the right hand side has more than one usage then
883 don't make it an induction (will have to think some more) */
884 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
887 /* if the definition is volatile then it cannot be
888 an induction object */
889 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
890 isOperandVolatile (IC_RESULT (ic), FALSE))
893 /* whew !! that was a lot of work to find the definition */
894 /* create an induction object */
895 indIc = newiCode ('=', NULL, IC_RESULT (ic));
896 indIc->lineno = ic->lineno;
897 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
898 IC_RESULT (indIc)->isaddr = 0;
899 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
900 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
902 /* replace the inducted variable by the iTemp */
903 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
905 /* if it has only one exit then remove it from here
906 and put it in the exit block */
907 nexits = elementsInSet (loopReg->exits);
910 eBBlock *exit = setFirstItem (loopReg->exits);
912 /* if it is the same block then there is no
913 need to move it about */
916 iCode *saveic = ic->prev;
918 remiCodeFromeBBlock (lBlock, ic);
919 /* clear the definition */
920 bitVectUnSetBit (lBlock->defSet, ic->key);
921 /* add it to the exit */
922 addiCodeToeBBlock (exit, ic, NULL);
923 /* set the definition bit */
924 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
929 /* if the number of exits is greater than one then
930 we use another trick ; we will create an intersection
931 of succesors of the exits, then take those that are not
932 part of the loop and have dfNumber greater loop entry
933 and insert a new definition in them */
937 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
939 /* loopSuccs now contains intersection
940 of all the loops successors */
944 for (i = 0; i < loopSuccs->size; i++)
946 if (bitVectBitValue (loopSuccs, i))
949 eBBlock *eblock = ebbs[i];
951 /* if the successor does not belong to the loop
952 and will be executed after the loop : then
953 add a definition to the block */
954 if (!isinSet (loopReg->regBlocks, eblock) &&
955 eblock->dfnum > loopReg->entry->dfnum)
957 /* create the definition */
958 iCode *newic = newiCode ('=', NULL,
959 operandFromOperand (IC_RIGHT (ic)));
960 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
961 OP_DEFS(IC_RESULT (newic))=
962 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
963 OP_USES(IC_RIGHT (newic))=
964 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
966 if (eblock->sch && eblock->sch->op == LABEL)
967 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
969 addiCodeToeBBlock (eblock, newic, eblock->sch);
970 /* set the definition bit */
971 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
978 addSet (&indVars, ip);
981 } /* end of all blocks for basic induction variables */
986 /*-----------------------------------------------------------------*/
987 /* loopInduction - remove induction variables from a loop */
988 /*-----------------------------------------------------------------*/
990 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
993 eBBlock *lBlock, *lastBlock = NULL;
995 set *basicInd = NULL;
997 if (loopReg->entry->preHeader == NULL)
1000 /* we first determine the basic Induction variables */
1001 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1003 /* find other induction variables : by other we mean definitions of */
1004 /* the form x := y (* | / ) <constant> .. we will move this one to */
1005 /* beginning of the loop and reduce strength i.e. replace with +/- */
1006 /* these expensive expressions: OH! and y must be induction too */
1007 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1009 lBlock = setNextItem (loopReg->regBlocks))
1015 /* last block is the one with the highest block
1017 if (lastBlock->bbnum < lBlock->bbnum)
1020 for (ic = lBlock->sch; ic; ic = ic->next)
1023 unsigned long litVal;
1026 /* consider only * & / */
1027 if (ic->op != '*' && ic->op != '/')
1030 /* if the result has more definitions then */
1031 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1034 /* check if the operands are what we want */
1035 /* i.e. one of them an symbol the other a literal */
1036 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1037 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1040 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
1041 (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
1042 (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
1045 /* check if this is an induction variable */
1046 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1049 /* ask port for size not worth if native instruction
1050 exist for multiply & divide */
1051 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1052 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1055 /* if this is a division then the remainder should be zero
1056 for it to be inducted */
1057 if (ic->op == '/' && (ip->cval % litVal))
1060 /* create the iCode to be placed in the loop header */
1061 /* and create the induction object */
1063 /* create an instruction */
1064 /* this will be put on the loop header */
1065 indIc = newiCode (ic->op,
1066 operandFromOperand (aSym),
1067 operandFromLit (litVal));
1068 indIc->lineno = ic->lineno;
1069 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1070 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1072 /* keep track of the inductions */
1073 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1074 (ip->cval / litVal));
1077 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1079 /* now change this instruction */
1083 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1084 IC_RIGHT (ic) = operandFromLit (litVal);
1088 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1089 IC_LEFT (ic) = operandFromLit (litVal);
1092 /* we need somemore initialisation code */
1093 /* we subtract the litVal from itself if increment */
1096 indIc = newiCode ('-',
1097 operandFromOperand (IC_RESULT (ic)),
1098 operandFromLit (litVal));
1099 indIc->lineno = ic->lineno;
1100 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1103 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1108 /* if we have some induction variables then */
1111 eBBlock *preHdr = loopReg->entry->preHeader;
1112 iCode *icFirst = NULL, *icLast = NULL;
1114 bitVect *indVect = NULL;
1116 /* create an iCode chain from it */
1117 for (ip = setFirstItem (indVars);
1119 ip = setNextItem (indVars))
1122 indVect = bitVectSetBit (indVect, ip->ic->key);
1123 ip->ic->lineno = preHdr->ech->lineno;
1128 icLast->next = ip->ic;
1129 ip->ic->prev = icLast;
1137 /* add the instruction chain to the end of the */
1138 /* preheader for this loop */
1139 preHdr->ech->next = icFirst;
1140 icFirst->prev = preHdr->ech;
1141 preHdr->ech = icLast;
1142 icLast->next = NULL;
1144 /* add the induction variable vector to the last
1145 block in the loop */
1146 lastBlock->isLastInLoop = 1;
1147 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1150 setToNull ((void **) &indVars);
1154 /*-----------------------------------------------------------------*/
1155 /* mergeRegions - will merge region with same entry point */
1156 /*-----------------------------------------------------------------*/
1157 DEFSETFUNC (mergeRegions)
1159 region *theLoop = item;
1160 V_ARG (set *, allRegion);
1163 /* if this has already been merged then do nothing */
1164 if (theLoop->merged)
1167 /* go thru all the region and check if any of them have the */
1168 /* entryPoint as the Loop */
1169 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1175 if (lp->entry == theLoop->entry)
1177 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1178 lp->regBlocks, THROW_DEST);
1186 /*-----------------------------------------------------------------*/
1187 /* ifMerged - return 1 if the merge flag is 1 */
1188 /*-----------------------------------------------------------------*/
1189 DEFSETFUNC (ifMerged)
1196 /*-----------------------------------------------------------------*/
1197 /* mergeInnerLoops - will merge into body when entry is present */
1198 /*-----------------------------------------------------------------*/
1199 DEFSETFUNC (mergeInnerLoops)
1201 region *theLoop = item;
1202 V_ARG (set *, allRegion);
1203 V_ARG (int *, maxDepth);
1206 /* check if the entry point is present in the body of any */
1207 /* loop then put the body of this loop into the outer loop */
1208 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1214 if (isinSet (lp->regBlocks, theLoop->entry))
1216 lp->containsLoops += theLoop->containsLoops + 1;
1217 if (lp->containsLoops > (*maxDepth))
1218 *maxDepth = lp->containsLoops;
1220 lp->regBlocks = unionSets (lp->regBlocks,
1221 theLoop->regBlocks, THROW_DEST);
1229 /*-----------------------------------------------------------------*/
1230 /* createLoopRegions - will detect and create a set of natural loops */
1231 /*-----------------------------------------------------------------*/
1233 createLoopRegions (eBBlock ** ebbs, int count)
1235 set *allRegion = NULL; /* set of all loops */
1236 hTab *orderedLoops = NULL;
1241 LRH(printf ("createLoopRegions: %p\n", ebbs));
1242 /* get all the back edges in the graph */
1243 if (!applyToSet (graphEdges, backEdges, &bEdges))
1244 return 0; /* found no loops */
1246 /* for each of these back edges get the blocks that */
1247 /* constitute the loops */
1248 applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1249 #ifdef LIVERANGEHUNT
1253 lp=setFirstItem(allRegion);
1254 printf ("createLoopRegions: ");
1255 for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
1256 printf ("%s ", ebp->entryLabel->name);
1258 printf (" %d\n", count);
1262 /* now we will create regions from these loops */
1263 /* loops with the same entry points are considered to be the */
1264 /* same loop & they are merged. If the entry point of a loop */
1265 /* is found in the body of another loop then , all the blocks */
1266 /* in that loop are added to the loops containing the header */
1267 applyToSet (allRegion, mergeRegions, allRegion);
1269 /* delete those already merged */
1270 deleteItemIf (&allRegion, ifMerged);
1272 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1275 /* now create all the exits .. also */
1276 /* create an ordered set of loops */
1277 /* i.e. we process loops in the inner to outer order */
1278 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1280 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1281 lp->regBlocks, &lp->exits,
1282 (maxDepth - lp->containsLoops), lp);
1284 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1287 return orderedLoops;
1290 /*-----------------------------------------------------------------*/
1291 /* loopOptimizations - identify region & remove invariants & ind */
1292 /*-----------------------------------------------------------------*/
1294 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1300 /* if no loop optimizations requested */
1301 if (!optimize.loopInvariant &&
1302 !optimize.loopInduction)
1305 /* now we process the loops inner to outer order */
1306 /* this is essential to maintain data flow information */
1307 /* the other choice is an ugly iteration for the depth */
1308 /* of the loops would hate that */
1309 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1310 lp = hTabNextItem (orderedLoops, &k))
1313 if (optimize.loopInvariant)
1314 change += loopInvariants (lp, ebbs, count);
1316 if (optimize.loopInduction)
1317 change += loopInduction (lp, ebbs, count);