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;
329 // now also include those blocks that conditionally escape from this loop
330 for (i=1; i<count; i++) {
331 if (ebbs[i]->hasConditionalExit) {
332 for (block=setFirstItem(aloop->regBlocks);
334 block=setNextItem(aloop->regBlocks)) {
335 if (isinSet(block->predList, ebbs[i])) {
336 printf ("%s has a forced exit from %s\n",
337 ebbs[i]->entryLabel->name,
338 block->entryLabel->name);
344 /* set max & min dfNum for loopRegion */
345 for ( block = setFirstItem(aloop->regBlocks); block;
346 block = setNextItem(aloop->regBlocks)) {
347 if (block->dfnum > dfMax) dfMax = block->dfnum;
348 if (block->dfnum < dfMin) dfMin = block->dfnum;
351 /* all blocks that have dfnumbers between dfMin & dfMax are also
353 for (i = 0 ; i < count ; i++) {
354 if (ebbs[i]->dfnum > dfMin &&
355 ebbs[i]->dfnum < dfMax &&
356 !isinSet(aloop->regBlocks,ebbs[i])) {
357 if (!ebbs[i]->partOfLoop) {
358 ebbs[i]->partOfLoop = aloop;
365 printf ("================\n");
366 printf (" loop with entry -- > ");
367 printEntryLabel (aloop->entry, ap);
369 printf (" loop body --> ");
370 applyToSet (aloop->regBlocks, printEntryLabel);
372 printf (" loop exits --> ");
373 applyToSet (aloop->exits, printEntryLabel);
377 /* and if this is a conditional block, the other side of the IFX
378 (if any, that could have a greater dfnum) is too */
380 // just a burp, but I'm getting close :)
384 /* now add it to the set */
385 addSetHead (allRegion, aloop);
389 /*-----------------------------------------------------------------*/
390 /* dominatedBy - will return 1 if item is dominated by block */
391 /*-----------------------------------------------------------------*/
392 DEFSETFUNC (dominatedBy)
395 V_ARG (eBBlock *, block);
397 return bitVectBitValue (ebp->domVect, block->bbnum);
400 /*-----------------------------------------------------------------*/
401 /* addDefInExprs - adds an expression into the inexpressions */
402 /*-----------------------------------------------------------------*/
403 DEFSETFUNC (addDefInExprs)
406 V_ARG (cseDef *, cdp);
407 V_ARG (eBBlock **, ebbs);
410 addSetHead (&ebp->inExprs, cdp);
411 cseBBlock (ebp, 0, ebbs, count);
415 /*-----------------------------------------------------------------*/
416 /* assignmentsToSym - for a set of blocks determine # time assigned */
417 /*-----------------------------------------------------------------*/
419 assignmentsToSym (set * sset, operand * sym)
423 set *blocks = setFromSet (sset);
425 for (ebp = setFirstItem (blocks); ebp;
426 ebp = setNextItem (blocks))
429 /* get all the definitions for this symbol
431 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
432 assigns += bitVectnBitsOn (defs);
433 setToNull ((void **) &defs);
441 /*-----------------------------------------------------------------*/
442 /* isOperandInvariant - determines if an operand is an invariant */
443 /*-----------------------------------------------------------------*/
445 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
448 /* operand is an invariant if it is a */
450 /* b. that have defintions reaching loop entry */
451 /* c. that are already defined as invariant */
452 /* d. has no assignments in the loop */
455 if (IS_OP_LITERAL (op))
457 else if (IS_SYMOP (op) &&
458 OP_SYMBOL (op)->addrtaken)
460 else if (ifDefSymIs (theLoop->entry->inExprs, op))
462 else if (ifDefSymIs (lInvars, op))
464 else if (IS_SYMOP (op) &&
465 !IS_OP_GLOBAL (op) &&
466 !IS_OP_VOLATILE (op) &&
467 assignmentsToSym (theLoop->regBlocks, op) == 0)
469 LRH(if (opin && IS_SYMOP(op)) {
470 printf("isOperandInvariant: %s\n", OP_SYMBOL(op)->name);
479 /*-----------------------------------------------------------------*/
480 /* pointerAssigned - will return 1 if pointer set found */
481 /*-----------------------------------------------------------------*/
482 DEFSETFUNC (pointerAssigned)
485 V_ARG (operand *, op);
487 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
490 /*-----------------------------------------------------------------*/
491 /* hasNonPtrUse - returns true if operand has non pointer usage */
492 /*-----------------------------------------------------------------*/
493 DEFSETFUNC (hasNonPtrUse)
496 V_ARG (operand *, op);
497 iCode *ic = usedInRemaining (op, ebp->sch);
499 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
506 /*-----------------------------------------------------------------*/
507 /* loopInvariants - takes loop invariants out of region */
508 /*-----------------------------------------------------------------*/
510 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
518 /* if the preHeader does not exist then do nothing */
519 /* or no exits then do nothing ( have to think about this situation */
520 if (theLoop->entry->preHeader == NULL ||
521 theLoop->exits == NULL)
524 /* we will do the elimination for those blocks */
525 /* in the loop that dominates all exits from the loop */
526 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
527 lBlock = setNextItem (theLoop->regBlocks))
534 /* mark the dominates all exits flag */
535 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
536 elementsInSet (theLoop->exits));
538 /* find out if we have a function call in this block */
539 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
545 /* now we go thru the instructions of this block and */
546 /* collect those instructions with invariant operands */
547 for (ic = lBlock->sch; ic; ic = ic->next)
553 /* jwk: TODO this is only needed if the call is between
554 here and the definition, but I am too lazy to do that now */
556 /* if there are function calls in this block */
559 /* if this is a pointer get */
560 if (POINTER_GET(ic)) {
564 /* if this is an assignment from a global */
565 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
570 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
573 /* if result is volatile then skip */
574 if (IC_RESULT (ic) &&
575 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
576 IS_OP_PARM (IC_RESULT (ic))))
579 /* if result depends on a volatile then skip */
580 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
581 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
587 /* if address of then it is an invariant */
588 if (ic->op == ADDRESS_OF &&
589 IS_SYMOP (IC_LEFT (ic)) &&
590 IS_AGGREGATE (operandType (IC_LEFT (ic))))
593 /* check if left operand is an invariant */
594 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
595 /* if this is a pointer get then make sure
596 that the pointer set does not exist in
598 if (POINTER_GET (ic) &&
599 (applyToSet (theLoop->regBlocks,
600 pointerAssigned, IC_LEFT (ic))))
604 /* do the same for right */
605 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
607 /* if this is a POINTER_GET then special case, make sure all
608 usages within the loop are POINTER_GET any other usage
609 would mean that this is not an invariant , since the pointer
610 could then be passed as a parameter */
611 if (POINTER_GET (ic) &&
612 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
615 /* if both the left & right are invariants : then check that */
616 /* this definition exists in the out definition of all the */
617 /* blocks, this will ensure that this is not assigned any */
618 /* other value in the loop , and not used in this block */
619 /* prior to this definition which means only this definition */
620 /* is used in this loop */
621 if (lin && rin && IC_RESULT (ic))
624 set *lSet = setFromSet (theLoop->regBlocks);
626 /* if this block does not dominate all exists */
627 /* make sure this defintion is not used anywhere else */
631 if (isOperandGlobal (IC_RESULT (ic)))
633 /* for successors for all exits */
634 for (sBlock = setFirstItem (theLoop->exits); sBlock;
635 sBlock = setNextItem (theLoop->exits))
638 for (i = 0; i < count; ebbs[i++]->visited = 0);
640 if (applyToSet (sBlock->succList, isDefAlive, ic))
644 /* we have found usage */
649 /* now make sure this is the only definition */
650 for (sBlock = setFirstItem (lSet); sBlock;
651 sBlock = setNextItem (lSet))
653 /* if this is the block make sure the definition */
654 /* reaches the end of the block */
655 if (sBlock == lBlock)
657 if (!ifDiCodeIs (sBlock->outExprs, ic))
660 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
665 continue; /* another definition present in the block */
667 /* now check if it exists in the in of this block */
668 /* if not then it was killed before this instruction */
669 if (!bitVectBitValue (lBlock->inDefs, ic->key))
672 /* now we know it is a true invariant */
673 /* remove it from the insts chain & put */
674 /* in the invariant set */
675 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
676 remiCodeFromeBBlock (lBlock, ic);
678 /* maintain the data flow */
679 /* this means removing from definition from the */
680 /* defset of this block and adding it to the */
681 /* inexpressions of all blocks within the loop */
682 bitVectUnSetBit (lBlock->defSet, ic->key);
683 bitVectUnSetBit (lBlock->ldefs, ic->key);
684 ivar = newCseDef (IC_RESULT (ic), ic);
685 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
686 addSet (&lInvars, ivar);
689 } /* for all loop blocks */
691 /* if we have some invariants then */
694 eBBlock *preHdr = theLoop->entry->preHeader;
695 iCode *icFirst = NULL, *icLast = NULL;
698 /* create an iCode chain from it */
699 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
702 /* maintain data flow .. add it to the */
703 /* ldefs defSet & outExprs of the preheader */
704 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
705 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
706 cdp->diCode->lineno = preHdr->ech->lineno;
707 addSetHead (&preHdr->outExprs, cdp);
711 icFirst = cdp->diCode;
714 icLast->next = cdp->diCode;
715 cdp->diCode->prev = icLast;
716 icLast = cdp->diCode;
719 icLast = cdp->diCode;
723 /* add the instruction chain to the end of the
724 preheader for this loop, preheaders will always
725 have atleast a label */
726 preHdr->ech->next = icFirst;
727 icFirst->prev = preHdr->ech;
728 preHdr->ech = icLast;
735 /*-----------------------------------------------------------------*/
736 /* addressTaken - returns true if the symbol is found in the addrof */
737 /*-----------------------------------------------------------------*/
739 addressTaken (set * sset, operand * sym)
745 for (loop = sset; loop; loop = loop->next)
751 if (isOperandEqual ((operand *) loop2->item, sym))
761 /*-----------------------------------------------------------------*/
762 /* findInduction :- returns 1 & the item if the induction is found */
763 /*-----------------------------------------------------------------*/
764 DEFSETFUNC (findInduction)
766 induction *ip = item;
767 V_ARG (operand *, sym);
768 V_ARG (induction **, ipp);
770 if (isOperandEqual (ip->sym, sym))
779 /*-----------------------------------------------------------------*/
780 /* findDefInRegion - finds the definition within the region */
781 /*-----------------------------------------------------------------*/
783 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
787 /* for all blocks in the region */
788 for (lBlock = setFirstItem (regBlocks); lBlock;
789 lBlock = setNextItem (regBlocks))
792 /* if a definition for this exists */
793 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
797 /* go thru the instruction chain to find it */
798 for (ic = lBlock->sch; ic; ic = ic->next)
799 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
811 /*-----------------------------------------------------------------*/
812 /* basicInduction - finds the basic induction variables in a loop */
813 /*-----------------------------------------------------------------*/
815 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
820 /* i.e. all assignments of the form a := a +/- const */
821 /* for all blocks within the loop do */
822 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
823 lBlock = setNextItem (loopReg->regBlocks))
828 /* for all instructions in the blocks do */
829 for (ic = lBlock->sch; ic; ic = ic->next)
833 unsigned long litValue;
836 eBBlock *owner = NULL;
839 /* look for assignments of the form */
840 /* symbolVar := iTempNN */
844 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
845 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
848 if (isOperandGlobal (IC_RESULT (ic)))
851 if (!IS_ITEMP (IC_RIGHT (ic)))
854 /* if it has multiple assignments within the loop then skip */
855 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
858 /* if the address of this was taken inside the loop then continue */
859 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
862 /* find the definition for the result in the block */
863 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
864 IC_RIGHT (ic), &owner)))
867 /* if not +/- continue */
868 if (dic->op != '+' && dic->op != '-')
871 /* make sure definition is of the form a +/- c */
872 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
875 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
876 (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
877 (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
879 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
880 !isOperandEqual (IC_RIGHT (ic), aSym))
883 /* find the definition for this and check */
884 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
891 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
892 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
896 /* if the right hand side has more than one usage then
897 don't make it an induction (will have to think some more) */
898 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
901 /* if the definition is volatile then it cannot be
902 an induction object */
903 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
904 isOperandVolatile (IC_RESULT (ic), FALSE))
907 /* whew !! that was a lot of work to find the definition */
908 /* create an induction object */
909 indIc = newiCode ('=', NULL, IC_RESULT (ic));
910 indIc->lineno = ic->lineno;
911 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
912 IC_RESULT (indIc)->isaddr = 0;
913 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
914 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
916 /* replace the inducted variable by the iTemp */
917 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
919 /* if it has only one exit then remove it from here
920 and put it in the exit block */
921 nexits = elementsInSet (loopReg->exits);
924 eBBlock *exit = setFirstItem (loopReg->exits);
926 /* if it is the same block then there is no
927 need to move it about */
930 iCode *saveic = ic->prev;
932 remiCodeFromeBBlock (lBlock, ic);
933 /* clear the definition */
934 bitVectUnSetBit (lBlock->defSet, ic->key);
935 /* add it to the exit */
936 addiCodeToeBBlock (exit, ic, NULL);
937 /* set the definition bit */
938 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
943 /* if the number of exits is greater than one then
944 we use another trick ; we will create an intersection
945 of succesors of the exits, then take those that are not
946 part of the loop and have dfNumber greater loop entry
947 and insert a new definition in them */
951 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
953 /* loopSuccs now contains intersection
954 of all the loops successors */
958 for (i = 0; i < loopSuccs->size; i++)
960 if (bitVectBitValue (loopSuccs, i))
963 eBBlock *eblock = ebbs[i];
965 /* if the successor does not belong to the loop
966 and will be executed after the loop : then
967 add a definition to the block */
968 if (!isinSet (loopReg->regBlocks, eblock) &&
969 eblock->dfnum > loopReg->entry->dfnum)
971 /* create the definition */
972 iCode *newic = newiCode ('=', NULL,
973 operandFromOperand (IC_RIGHT (ic)));
974 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
975 OP_DEFS(IC_RESULT (newic))=
976 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
977 OP_USES(IC_RIGHT (newic))=
978 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
980 if (eblock->sch && eblock->sch->op == LABEL)
981 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
983 addiCodeToeBBlock (eblock, newic, eblock->sch);
984 /* set the definition bit */
985 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
992 addSet (&indVars, ip);
995 } /* end of all blocks for basic induction variables */
1000 /*-----------------------------------------------------------------*/
1001 /* loopInduction - remove induction variables from a loop */
1002 /*-----------------------------------------------------------------*/
1004 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
1007 eBBlock *lBlock, *lastBlock = NULL;
1008 set *indVars = NULL;
1009 set *basicInd = NULL;
1011 if (loopReg->entry->preHeader == NULL)
1014 /* we first determine the basic Induction variables */
1015 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
1017 /* find other induction variables : by other we mean definitions of */
1018 /* the form x := y (* | / ) <constant> .. we will move this one to */
1019 /* beginning of the loop and reduce strength i.e. replace with +/- */
1020 /* these expensive expressions: OH! and y must be induction too */
1021 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
1023 lBlock = setNextItem (loopReg->regBlocks))
1029 /* last block is the one with the highest block
1031 if (lastBlock->bbnum < lBlock->bbnum)
1034 for (ic = lBlock->sch; ic; ic = ic->next)
1037 unsigned long litVal;
1040 /* consider only * & / */
1041 if (ic->op != '*' && ic->op != '/')
1044 /* if the result has more definitions then */
1045 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
1048 /* check if the operands are what we want */
1049 /* i.e. one of them an symbol the other a literal */
1050 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
1051 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
1054 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
1055 (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
1056 (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
1059 /* check if this is an induction variable */
1060 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
1063 /* ask port for size not worth if native instruction
1064 exist for multiply & divide */
1065 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
1066 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
1069 /* if this is a division then the remainder should be zero
1070 for it to be inducted */
1071 if (ic->op == '/' && (ip->cval % litVal))
1074 /* create the iCode to be placed in the loop header */
1075 /* and create the induction object */
1077 /* create an instruction */
1078 /* this will be put on the loop header */
1079 indIc = newiCode (ic->op,
1080 operandFromOperand (aSym),
1081 operandFromLit (litVal));
1082 indIc->lineno = ic->lineno;
1083 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1084 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1086 /* keep track of the inductions */
1087 litVal = (ic->op == '*' ? (litVal * ip->cval) :
1088 (ip->cval / litVal));
1091 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1093 /* now change this instruction */
1097 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1098 IC_RIGHT (ic) = operandFromLit (litVal);
1102 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1103 IC_LEFT (ic) = operandFromLit (litVal);
1106 /* we need somemore initialisation code */
1107 /* we subtract the litVal from itself if increment */
1110 indIc = newiCode ('-',
1111 operandFromOperand (IC_RESULT (ic)),
1112 operandFromLit (litVal));
1113 indIc->lineno = ic->lineno;
1114 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1117 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1122 /* if we have some induction variables then */
1125 eBBlock *preHdr = loopReg->entry->preHeader;
1126 iCode *icFirst = NULL, *icLast = NULL;
1128 bitVect *indVect = NULL;
1130 /* create an iCode chain from it */
1131 for (ip = setFirstItem (indVars);
1133 ip = setNextItem (indVars))
1136 indVect = bitVectSetBit (indVect, ip->ic->key);
1137 ip->ic->lineno = preHdr->ech->lineno;
1142 icLast->next = ip->ic;
1143 ip->ic->prev = icLast;
1151 /* add the instruction chain to the end of the */
1152 /* preheader for this loop */
1153 preHdr->ech->next = icFirst;
1154 icFirst->prev = preHdr->ech;
1155 preHdr->ech = icLast;
1156 icLast->next = NULL;
1158 /* add the induction variable vector to the last
1159 block in the loop */
1160 lastBlock->isLastInLoop = 1;
1161 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1164 setToNull ((void **) &indVars);
1168 /*-----------------------------------------------------------------*/
1169 /* mergeRegions - will merge region with same entry point */
1170 /*-----------------------------------------------------------------*/
1171 DEFSETFUNC (mergeRegions)
1173 region *theLoop = item;
1174 V_ARG (set *, allRegion);
1177 /* if this has already been merged then do nothing */
1178 if (theLoop->merged)
1181 /* go thru all the region and check if any of them have the */
1182 /* entryPoint as the Loop */
1183 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1189 if (lp->entry == theLoop->entry)
1191 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1192 lp->regBlocks, THROW_DEST);
1200 /*-----------------------------------------------------------------*/
1201 /* ifMerged - return 1 if the merge flag is 1 */
1202 /*-----------------------------------------------------------------*/
1203 DEFSETFUNC (ifMerged)
1210 /*-----------------------------------------------------------------*/
1211 /* mergeInnerLoops - will merge into body when entry is present */
1212 /*-----------------------------------------------------------------*/
1213 DEFSETFUNC (mergeInnerLoops)
1215 region *theLoop = item;
1216 V_ARG (set *, allRegion);
1217 V_ARG (int *, maxDepth);
1220 /* check if the entry point is present in the body of any */
1221 /* loop then put the body of this loop into the outer loop */
1222 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1228 if (isinSet (lp->regBlocks, theLoop->entry))
1230 lp->containsLoops += theLoop->containsLoops + 1;
1231 if (lp->containsLoops > (*maxDepth))
1232 *maxDepth = lp->containsLoops;
1234 lp->regBlocks = unionSets (lp->regBlocks,
1235 theLoop->regBlocks, THROW_DEST);
1243 /*-----------------------------------------------------------------*/
1244 /* createLoopRegions - will detect and create a set of natural loops */
1245 /*-----------------------------------------------------------------*/
1247 createLoopRegions (eBBlock ** ebbs, int count)
1249 set *allRegion = NULL; /* set of all loops */
1250 hTab *orderedLoops = NULL;
1255 LRH(printf ("createLoopRegions: %p\n", ebbs));
1256 /* get all the back edges in the graph */
1257 if (!applyToSet (graphEdges, backEdges, &bEdges))
1258 return 0; /* found no loops */
1260 /* for each of these back edges get the blocks that */
1261 /* constitute the loops */
1262 applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1263 #ifdef LIVERANGEHUNT
1267 lp=setFirstItem(allRegion);
1268 printf ("createLoopRegions: ");
1269 for (ebp=setFirstItem(lp->regBlocks); ebp; ebp=setNextItem(lp->regBlocks)) {
1270 printf ("%s ", ebp->entryLabel->name);
1272 printf (" %d\n", count);
1276 /* now we will create regions from these loops */
1277 /* loops with the same entry points are considered to be the */
1278 /* same loop & they are merged. If the entry point of a loop */
1279 /* is found in the body of another loop then , all the blocks */
1280 /* in that loop are added to the loops containing the header */
1281 applyToSet (allRegion, mergeRegions, allRegion);
1283 /* delete those already merged */
1284 deleteItemIf (&allRegion, ifMerged);
1286 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1289 /* now create all the exits .. also */
1290 /* create an ordered set of loops */
1291 /* i.e. we process loops in the inner to outer order */
1292 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1294 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1295 lp->regBlocks, &lp->exits,
1296 (maxDepth - lp->containsLoops), lp);
1298 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1301 return orderedLoops;
1304 /*-----------------------------------------------------------------*/
1305 /* loopOptimizations - identify region & remove invariants & ind */
1306 /*-----------------------------------------------------------------*/
1308 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1314 /* if no loop optimizations requested */
1315 if (!optimize.loopInvariant &&
1316 !optimize.loopInduction)
1319 /* now we process the loops inner to outer order */
1320 /* this is essential to maintain data flow information */
1321 /* the other choice is an ugly iteration for the depth */
1322 /* of the loops would hate that */
1323 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1324 lp = hTabNextItem (orderedLoops, &k))
1327 if (optimize.loopInvariant)
1328 change += loopInvariants (lp, ebbs, count);
1330 if (optimize.loopInduction)
1331 change += loopInduction (lp, ebbs, count);