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 if (getenv ("SDCC_LRKLAUS"))
240 /* put the loop region info in the block */
241 if (!isinSet (ebp->KpartOfLoop, lr))
242 addSetHead (&ebp->KpartOfLoop, lr);
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;
252 /* if any of the successors go out of the loop then */
253 /* we add this one to the exits */
254 if (applyToSet (ebp->succList, isNotInBlocks, loopBlocks))
256 addSetHead (exits, ebp);
263 /*-----------------------------------------------------------------*/
264 /* createLoop - will create a set of region */
265 /*-----------------------------------------------------------------*/
266 DEFSETFUNC (createLoop)
269 V_ARG (set **, allRegion);
270 region *aloop = newRegion ();
273 /* make sure regionStack is empty */
274 while (!STACK_EMPTY (regionStack))
275 STACK_POP (regionStack);
277 /* add the entryBlock */
278 addSet (&aloop->regBlocks, ep->to);
279 loopInsert (&aloop->regBlocks, ep->from);
281 while (!STACK_EMPTY (regionStack))
283 block = STACK_POP (regionStack);
284 /* if block != entry */
286 applyToSet (block->predList, insertIntoLoop, &aloop->regBlocks);
289 aloop->entry = ep->to;
291 /* now add it to the set */
292 addSetHead (allRegion, aloop);
296 /*-----------------------------------------------------------------*/
297 /* dominatedBy - will return 1 if item is dominated by block */
298 /*-----------------------------------------------------------------*/
299 DEFSETFUNC (dominatedBy)
302 V_ARG (eBBlock *, block);
304 return bitVectBitValue (ebp->domVect, block->bbnum);
307 /*-----------------------------------------------------------------*/
308 /* addDefInExprs - adds an expression into the inexpressions */
309 /*-----------------------------------------------------------------*/
310 DEFSETFUNC (addDefInExprs)
313 V_ARG (cseDef *, cdp);
314 V_ARG (eBBlock **, ebbs);
317 addSetHead (&ebp->inExprs, cdp);
318 cseBBlock (ebp, optimize.global_cse, ebbs, count);
322 /*-----------------------------------------------------------------*/
323 /* assignmentsToSym - for a set of blocks determine # time assigned */
324 /*-----------------------------------------------------------------*/
326 assignmentsToSym (set * sset, operand * sym)
330 set *blocks = setFromSet (sset);
332 for (ebp = setFirstItem (blocks); ebp;
333 ebp = setNextItem (blocks))
336 /* get all the definitions for this symbol
338 bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
339 assigns += bitVectnBitsOn (defs);
340 setToNull ((void *) &defs);
348 /*-----------------------------------------------------------------*/
349 /* isOperandInvariant - determines if an operand is an invariant */
350 /*-----------------------------------------------------------------*/
352 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
355 /* operand is an invariant if it is a */
357 /* b. that have defintions reaching loop entry */
358 /* c. that are already defined as invariant */
359 /* d. has no assignments in the loop */
362 if (IS_OP_LITERAL (op))
364 else if (IS_SYMOP (op) &&
365 OP_SYMBOL (op)->addrtaken)
367 else if (ifDefSymIs (theLoop->entry->inExprs, op))
369 else if (ifDefSymIs (lInvars, op))
371 else if (IS_SYMOP (op) &&
372 !IS_OP_GLOBAL (op) &&
373 !IS_OP_VOLATILE (op) &&
374 assignmentsToSym (theLoop->regBlocks, op) == 0)
383 /*-----------------------------------------------------------------*/
384 /* pointerAssigned - will return 1 if pointer set found */
385 /*-----------------------------------------------------------------*/
386 DEFSETFUNC (pointerAssigned)
389 V_ARG (operand *, op);
391 return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
394 /*-----------------------------------------------------------------*/
395 /* hasNonPtrUse - returns true if operand has non pointer usage */
396 /*-----------------------------------------------------------------*/
397 DEFSETFUNC (hasNonPtrUse)
400 V_ARG (operand *, op);
401 iCode *ic = usedInRemaining (op, ebp->sch);
403 if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
410 /*-----------------------------------------------------------------*/
411 /* loopInvariants - takes loop invariants out of region */
412 /*-----------------------------------------------------------------*/
414 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
422 /* if the preHeader does not exist then do nothing */
423 /* or no exits then do nothing ( have to think about this situation */
424 if (theLoop->entry->preHeader == NULL ||
425 theLoop->exits == NULL)
428 /* we will do the elimination for those blocks */
429 /* in the loop that dominates all exits from the loop */
430 for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
431 lBlock = setNextItem (theLoop->regBlocks))
438 /* mark the dominates all exits flag */
439 domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
440 elementsInSet (theLoop->exits));
442 /* find out if we have a function call in this block */
443 for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
449 /* now we go thru the instructions of this block and */
450 /* collect those instructions with invariant operands */
451 for (ic = lBlock->sch; ic; ic = ic->next)
457 /* TODO this is only needed if the call is between
458 here and the definition, but I am too lazy to do that now */
460 /* if there are function calls in this block */
463 /* if this is a pointer get */
464 if (POINTER_GET(ic)) {
468 /* if this is an assignment from a global */
469 if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
474 if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
477 /* if result is volatile then skip */
478 if (IC_RESULT (ic) &&
479 (isOperandVolatile (IC_RESULT (ic), TRUE) ||
480 IS_OP_PARM (IC_RESULT (ic))))
483 /* if result depends on a volatile then skip */
484 if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
485 (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
491 /* if address of then it is an invariant */
492 if (ic->op == ADDRESS_OF &&
493 IS_SYMOP (IC_LEFT (ic)) &&
494 IS_AGGREGATE (operandType (IC_LEFT (ic))))
497 /* check if left operand is an invariant */
498 if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
499 /* if this is a pointer get then make sure
500 that the pointer set does not exist in
502 if (POINTER_GET (ic) &&
503 (applyToSet (theLoop->regBlocks,
504 pointerAssigned, IC_LEFT (ic))))
508 /* do the same for right */
509 rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
511 /* if this is a POINTER_GET then special case, make sure all
512 usages within the loop are POINTER_GET any other usage
513 would mean that this is not an invariant , since the pointer
514 could then be passed as a parameter */
515 if (POINTER_GET (ic) &&
516 applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
519 /* if both the left & right are invariants : then check that */
520 /* this definition exists in the out definition of all the */
521 /* blocks, this will ensure that this is not assigned any */
522 /* other value in the loop , and not used in this block */
523 /* prior to this definition which means only this definition */
524 /* is used in this loop */
525 if (lin && rin && IC_RESULT (ic))
528 set *lSet = setFromSet (theLoop->regBlocks);
530 /* if this block does not dominate all exists */
531 /* make sure this defintion is not used anywhere else */
535 if (isOperandGlobal (IC_RESULT (ic)))
537 /* for successors for all exits */
538 for (sBlock = setFirstItem (theLoop->exits); sBlock;
539 sBlock = setNextItem (theLoop->exits))
542 for (i = 0; i < count; ebbs[i++]->visited = 0);
544 if (applyToSet (sBlock->succList, isDefAlive, ic))
548 /* we have found usage */
553 /* now make sure this is the only definition */
554 for (sBlock = setFirstItem (lSet); sBlock;
555 sBlock = setNextItem (lSet))
557 /* if this is the block make sure the definition */
558 /* reaches the end of the block */
559 if (sBlock == lBlock)
561 if (!ifDiCodeIs (sBlock->outExprs, ic))
564 else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
569 continue; /* another definition present in the block */
571 /* now check if it exists in the in of this block */
572 /* if not then it was killed before this instruction */
573 if (!bitVectBitValue (lBlock->inDefs, ic->key))
576 /* now we know it is a true invariant */
577 /* remove it from the insts chain & put */
578 /* in the invariant set */
579 OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
580 remiCodeFromeBBlock (lBlock, ic);
582 /* maintain the data flow */
583 /* this means removing from definition from the */
584 /* defset of this block and adding it to the */
585 /* inexpressions of all blocks within the loop */
586 bitVectUnSetBit (lBlock->defSet, ic->key);
587 bitVectUnSetBit (lBlock->ldefs, ic->key);
588 ivar = newCseDef (IC_RESULT (ic), ic);
589 applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
590 addSet (&lInvars, ivar);
593 } /* for all loop blocks */
595 /* if we have some invariants then */
598 eBBlock *preHdr = theLoop->entry->preHeader;
599 iCode *icFirst = NULL, *icLast = NULL;
602 /* create an iCode chain from it */
603 for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
606 /* maintain data flow .. add it to the */
607 /* ldefs defSet & outExprs of the preheader */
608 preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
609 preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
610 cdp->diCode->lineno = preHdr->ech->lineno;
611 addSetHead (&preHdr->outExprs, cdp);
615 icFirst = cdp->diCode;
618 icLast->next = cdp->diCode;
619 cdp->diCode->prev = icLast;
620 icLast = cdp->diCode;
623 icLast = cdp->diCode;
627 /* add the instruction chain to the end of the
628 preheader for this loop, preheaders will always
629 have atleast a label */
630 preHdr->ech->next = icFirst;
631 icFirst->prev = preHdr->ech;
632 preHdr->ech = icLast;
639 /*-----------------------------------------------------------------*/
640 /* addressTaken - returns true if the symbol is found in the addrof */
641 /*-----------------------------------------------------------------*/
643 addressTaken (set * sset, operand * sym)
649 for (loop = sset; loop; loop = loop->next)
655 if (isOperandEqual ((operand *) loop2->item, sym))
665 /*-----------------------------------------------------------------*/
666 /* findInduction :- returns 1 & the item if the induction is found */
667 /*-----------------------------------------------------------------*/
668 DEFSETFUNC (findInduction)
670 induction *ip = item;
671 V_ARG (operand *, sym);
672 V_ARG (induction **, ipp);
674 if (isOperandEqual (ip->sym, sym))
683 /*-----------------------------------------------------------------*/
684 /* findDefInRegion - finds the definition within the region */
685 /*-----------------------------------------------------------------*/
687 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
691 /* for all blocks in the region */
692 for (lBlock = setFirstItem (regBlocks); lBlock;
693 lBlock = setNextItem (regBlocks))
696 /* if a definition for this exists */
697 if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
701 /* go thru the instruction chain to find it */
702 for (ic = lBlock->sch; ic; ic = ic->next)
703 if (bitVectBitValue (OP_DEFS (defOp), ic->key))
715 /*-----------------------------------------------------------------*/
716 /* basicInduction - finds the basic induction variables in a loop */
717 /*-----------------------------------------------------------------*/
719 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
724 /* i.e. all assignments of the form a := a +/- const */
725 /* for all blocks within the loop do */
726 for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
727 lBlock = setNextItem (loopReg->regBlocks))
732 /* for all instructions in the blocks do */
733 for (ic = lBlock->sch; ic; ic = ic->next)
737 unsigned long litValue;
740 eBBlock *owner = NULL;
743 /* look for assignments of the form */
744 /* symbolVar := iTempNN */
748 if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
749 !OP_SYMBOL (IC_RESULT (ic))->isreqv)
752 if (isOperandGlobal (IC_RESULT (ic)))
755 if (!IS_ITEMP (IC_RIGHT (ic)))
758 /* if it has multiple assignments within the loop then skip */
759 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
762 /* if the address of this was taken inside the loop then continue */
763 if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
766 /* find the definition for the result in the block */
767 if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
768 IC_RIGHT (ic), &owner)))
771 /* if not +/- continue */
772 if (dic->op != '+' && dic->op != '-')
775 /* make sure definition is of the form a +/- c */
776 if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
779 aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
780 (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
781 (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
783 if (!isOperandEqual (IC_RESULT (ic), aSym) &&
784 !isOperandEqual (IC_RIGHT (ic), aSym))
787 /* find the definition for this and check */
788 if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
795 if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
796 !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
800 /* if the right hand side has more than one usage then
801 don't make it an induction (will have to think some more) */
802 if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
805 /* if the definition is volatile then it cannot be
806 an induction object */
807 if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
808 isOperandVolatile (IC_RESULT (ic), FALSE))
811 /* whew !! that was a lot of work to find the definition */
812 /* create an induction object */
813 indIc = newiCode ('=', NULL, IC_RESULT (ic));
814 indIc->lineno = ic->lineno;
815 IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
816 IC_RESULT (indIc)->isaddr = 0;
817 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
818 ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
820 /* replace the inducted variable by the iTemp */
821 replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
823 /* if it has only one exit then remove it from here
824 and put it in the exit block */
825 nexits = elementsInSet (loopReg->exits);
828 eBBlock *exit = setFirstItem (loopReg->exits);
830 /* if it is the same block then there is no
831 need to move it about */
834 iCode *saveic = ic->prev;
836 remiCodeFromeBBlock (lBlock, ic);
837 /* clear the definition */
838 bitVectUnSetBit (lBlock->defSet, ic->key);
839 /* add it to the exit */
840 addiCodeToeBBlock (exit, ic, NULL);
841 /* set the definition bit */
842 exit->defSet = bitVectSetBit (exit->defSet, ic->key);
847 /* if the number of exits is greater than one then
848 we use another trick ; we will create an intersection
849 of succesors of the exits, then take those that are not
850 part of the loop and have dfNumber greater loop entry
851 and insert a new definition in them */
855 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
857 /* loopSuccs now contains intersection
858 of all the loops successors */
862 for (i = 0; i < loopSuccs->size; i++)
864 if (bitVectBitValue (loopSuccs, i))
867 eBBlock *eblock = ebbs[i];
869 /* if the successor does not belong to the loop
870 and will be executed after the loop : then
871 add a definition to the block */
872 if (!isinSet (loopReg->regBlocks, eblock) &&
873 eblock->dfnum > loopReg->entry->dfnum)
875 /* create the definition */
876 iCode *newic = newiCode ('=', NULL,
877 operandFromOperand (IC_RIGHT (ic)));
878 IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
879 OP_DEFS(IC_RESULT (newic))=
880 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key);
881 OP_USES(IC_RIGHT (newic))=
882 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key);
884 if (eblock->sch && eblock->sch->op == LABEL)
885 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
887 addiCodeToeBBlock (eblock, newic, eblock->sch);
888 /* set the definition bit */
889 eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
896 addSet (&indVars, ip);
899 } /* end of all blocks for basic induction variables */
904 /*-----------------------------------------------------------------*/
905 /* loopInduction - remove induction variables from a loop */
906 /*-----------------------------------------------------------------*/
908 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
911 eBBlock *lBlock, *lastBlock = NULL;
913 set *basicInd = NULL;
915 if (loopReg->entry->preHeader == NULL)
918 /* we first determine the basic Induction variables */
919 basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
921 /* find other induction variables : by other we mean definitions of */
922 /* the form x := y (* | / ) <constant> .. we will move this one to */
923 /* beginning of the loop and reduce strength i.e. replace with +/- */
924 /* these expensive expressions: OH! and y must be induction too */
925 for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
927 lBlock = setNextItem (loopReg->regBlocks))
933 /* last block is the one with the highest block
935 if (lastBlock->bbnum < lBlock->bbnum)
938 for (ic = lBlock->sch; ic; ic = ic->next)
941 unsigned long litVal;
944 /* consider only * & / */
945 if (ic->op != '*' && ic->op != '/')
948 /* if the result has more definitions then */
949 if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
952 /* check if the operands are what we want */
953 /* i.e. one of them an symbol the other a literal */
954 if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
955 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
958 aSym = (IS_SYMOP (IC_LEFT (ic)) ?
959 (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
960 (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
963 /* check if this is an induction variable */
964 if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
967 /* ask port for size not worth if native instruction
968 exist for multiply & divide */
969 if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
970 getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
973 /* if this is a division then the remainder should be zero
974 for it to be inducted */
975 if (ic->op == '/' && (ip->cval % litVal))
978 /* create the iCode to be placed in the loop header */
979 /* and create the induction object */
981 /* create an instruction */
982 /* this will be put on the loop header */
983 indIc = newiCode (ic->op,
984 operandFromOperand (aSym),
985 operandFromLit (litVal));
986 indIc->lineno = ic->lineno;
987 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
988 OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
990 /* keep track of the inductions */
991 litVal = (ic->op == '*' ? (litVal * ip->cval) :
992 (ip->cval / litVal));
995 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
997 /* now change this instruction */
1001 IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1002 IC_RIGHT (ic) = operandFromLit (litVal);
1006 IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1007 IC_LEFT (ic) = operandFromLit (litVal);
1010 /* we need somemore initialisation code */
1011 /* we subtract the litVal from itself if increment */
1014 indIc = newiCode ('-',
1015 operandFromOperand (IC_RESULT (ic)),
1016 operandFromLit (litVal));
1017 indIc->lineno = ic->lineno;
1018 IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1021 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1026 /* if we have some induction variables then */
1029 eBBlock *preHdr = loopReg->entry->preHeader;
1030 iCode *icFirst = NULL, *icLast = NULL;
1032 bitVect *indVect = NULL;
1034 /* create an iCode chain from it */
1035 for (ip = setFirstItem (indVars);
1037 ip = setNextItem (indVars))
1040 indVect = bitVectSetBit (indVect, ip->ic->key);
1041 ip->ic->lineno = preHdr->ech->lineno;
1046 icLast->next = ip->ic;
1047 ip->ic->prev = icLast;
1055 /* add the instruction chain to the end of the */
1056 /* preheader for this loop */
1057 preHdr->ech->next = icFirst;
1058 icFirst->prev = preHdr->ech;
1059 preHdr->ech = icLast;
1060 icLast->next = NULL;
1062 /* add the induction variable vector to the last
1063 block in the loop */
1064 lastBlock->isLastInLoop = 1;
1065 lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1068 setToNull ((void *) &indVars);
1072 /*-----------------------------------------------------------------*/
1073 /* mergeRegions - will merge region with same entry point */
1074 /*-----------------------------------------------------------------*/
1075 DEFSETFUNC (mergeRegions)
1077 region *theLoop = item;
1078 V_ARG (set *, allRegion);
1081 /* if this has already been merged then do nothing */
1082 if (theLoop->merged)
1085 /* go thru all the region and check if any of them have the */
1086 /* entryPoint as the Loop */
1087 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1093 if (lp->entry == theLoop->entry)
1095 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1096 lp->regBlocks, THROW_DEST);
1104 /*-----------------------------------------------------------------*/
1105 /* ifMerged - return 1 if the merge flag is 1 */
1106 /*-----------------------------------------------------------------*/
1107 DEFSETFUNC (ifMerged)
1114 /*-----------------------------------------------------------------*/
1115 /* mergeInnerLoops - will merge into body when entry is present */
1116 /*-----------------------------------------------------------------*/
1117 DEFSETFUNC (mergeInnerLoops)
1119 region *theLoop = item;
1120 V_ARG (set *, allRegion);
1121 V_ARG (int *, maxDepth);
1124 /* check if the entry point is present in the body of any */
1125 /* loop then put the body of this loop into the outer loop */
1126 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1132 if (isinSet (lp->regBlocks, theLoop->entry))
1134 lp->containsLoops += theLoop->containsLoops + 1;
1135 if (lp->containsLoops > (*maxDepth))
1136 *maxDepth = lp->containsLoops;
1138 lp->regBlocks = unionSets (lp->regBlocks,
1139 theLoop->regBlocks, THROW_DEST);
1147 /*-----------------------------------------------------------------*/
1148 /* createLoopRegions - will detect and create a set of natural loops */
1149 /*-----------------------------------------------------------------*/
1151 createLoopRegions (eBBlock ** ebbs, int count)
1153 set *allRegion = NULL; /* set of all loops */
1154 hTab *orderedLoops = NULL;
1159 /* get all the back edges in the graph */
1160 if (!applyToSet (graphEdges, backEdges, &bEdges))
1161 return 0; /* found no loops */
1163 /* for each of these back edges get the blocks that */
1164 /* constitute the loops */
1165 applyToSet (bEdges, createLoop, &allRegion);
1167 /* now we will create regions from these loops */
1168 /* loops with the same entry points are considered to be the */
1169 /* same loop & they are merged. If the entry point of a loop */
1170 /* is found in the body of another loop then , all the blocks */
1171 /* in that loop are added to the loops containing the header */
1172 applyToSet (allRegion, mergeRegions, allRegion);
1174 /* delete those already merged */
1175 deleteItemIf (&allRegion, ifMerged);
1177 applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1180 /* now create all the exits .. also */
1181 /* create an ordered set of loops */
1182 /* i.e. we process loops in the inner to outer order */
1183 for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1185 applyToSet (lp->regBlocks, addToExitsMarkDepth,
1186 lp->regBlocks, &lp->exits,
1187 (maxDepth - lp->containsLoops), lp);
1189 hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1192 return orderedLoops;
1195 /*-----------------------------------------------------------------*/
1196 /* loopOptimizations - identify region & remove invariants & ind */
1197 /*-----------------------------------------------------------------*/
1199 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1205 /* if no loop optimizations requested */
1206 if (!optimize.loopInvariant &&
1207 !optimize.loopInduction)
1210 /* now we process the loops inner to outer order */
1211 /* this is essential to maintain data flow information */
1212 /* the other choice is an ugly iteration for the depth */
1213 /* of the loops would hate that */
1214 for (lp = hTabFirstItem (orderedLoops, &k); lp;
1215 lp = hTabNextItem (orderedLoops, &k))
1218 if (optimize.loopInvariant)
1219 change += loopInvariants (lp, ebbs, count);
1221 if (optimize.loopInduction)
1222 change += loopInduction (lp, ebbs, count);
1228 /*-----------------------------------------------------------------*/
1229 /* addLoopBlocks - will add all blocks inside a loop to this loop */
1230 /* this should fix most of the liverange problems */
1231 /*-----------------------------------------------------------------*/
1233 addLoopBlocks (eBBlock ** ebbs, int count)
1236 struct eBBlock *block;
1240 for (i = 0; i < count; i++)
1242 if (!ebbs[i]->KpartOfLoop)
1245 /* for all loops this block belongs to */
1246 /* add inner block not already marked as part of this loop */
1247 aloop = setFirstItem (ebbs[i]->KpartOfLoop);
1248 for (; aloop; aloop = setNextItem (ebbs[i]->KpartOfLoop))
1256 /* set max & min Seq for loopRegion */
1257 block = setFirstItem (aloop->regBlocks);
1258 seqMax = block->lSeq;
1259 seqMin = block->fSeq;
1260 for (; block; block = setNextItem (aloop->regBlocks))
1262 if (block->lSeq > seqMax)
1263 seqMax = block->lSeq;
1264 if (block->fSeq < seqMin)
1265 seqMin = block->fSeq;
1268 /* add all blocks between seqMin, seqMax to loop */
1269 for (j = 0; j < count; j++)
1271 if (ebbs[j]->fSeq > seqMin && ebbs[j]->lSeq < seqMax &&
1272 !isinSet (aloop->regBlocks, ebbs[j]))
1274 if (!isinSet (ebbs[j]->KpartOfLoop, aloop))
1275 addSetHead (&ebbs[j]->KpartOfLoop, aloop);