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 -------------------------------------------------------------------------*/
28 DEFSETFUNC(isDefAlive);
30 STACK_DCL(regionStack,eBBlock *, MAX_NEST_LEVEL * 10);
32 /*-----------------------------------------------------------------*/
33 /* newInduction - creates a new induction variable */
34 /*-----------------------------------------------------------------*/
35 induction *newInduction (operand *sym, unsigned int op,
36 long constVal, iCode *ic, operand *asym)
40 ALLOC(ip,sizeof(induction));
51 /*-----------------------------------------------------------------*/
52 /* newRegion - allocate & returns a loop structure */
53 /*-----------------------------------------------------------------*/
58 ALLOC(lp,sizeof(region));
64 /*-----------------------------------------------------------------*/
65 /* pinduction - prints induction */
66 /*-----------------------------------------------------------------*/
67 DEFSETFUNC(pinduction)
73 printOperand(ip->sym,stdout);
74 icTab = getTableEntry(ip->ic->op);
75 icTab->iCodePrint(stdout,ip->ic,icTab->printName);
76 fprintf(stdout," %04d\n",(int)ip->cval);
80 /*-----------------------------------------------------------------*/
81 /* pregion - prints loop information */
82 /*-----------------------------------------------------------------*/
87 printf("================\n");
88 printf(" loop with entry -- > "); printEntryLabel(lp->entry,ap);
90 printf(" loop body --> "); applyToSet(lp->regBlocks,printEntryLabel);
92 printf(" loop exits --> "); applyToSet(lp->exits,printEntryLabel);
97 /*-----------------------------------------------------------------*/
98 /* backEdges - returns a list of back edges */
99 /*-----------------------------------------------------------------*/
100 DEFSETFUNC(backEdges)
103 V_ARG(set **,bEdges);
105 /* if this is a back edge ; to determine this we check */
106 /* to see if the 'to' is in the dominator list of the */
107 /* 'from' if yes then this is a back edge */
108 if (bitVectBitValue (ep->from->domVect,ep->to->bbnum)) {
109 addSetHead (bEdges,ep);
116 /*-----------------------------------------------------------------*/
117 /* intersectLoopSucc - returns intersection of loop Successors */
118 /*-----------------------------------------------------------------*/
119 static bitVect *intersectLoopSucc ( set *lexits, eBBlock **ebbs)
121 bitVect *succVect = NULL;
122 eBBlock *exit = setFirstItem(lexits);
127 succVect = bitVectCopy(exit->succVect);
129 for (exit = setNextItem(lexits); exit ;
130 exit = setNextItem(lexits)) {
131 succVect = bitVectIntersect(succVect,
139 /*-----------------------------------------------------------------*/
140 /* loopInsert will insert a block into the loop set */
141 /*-----------------------------------------------------------------*/
142 static void loopInsert (set **regionSet, eBBlock *block)
144 if (!isinSet (*regionSet,block)) {
145 addSetHead (regionSet,block);
146 STACK_PUSH(regionStack,block);
150 /*-----------------------------------------------------------------*/
151 /* insertIntoLoop - insert item into loop */
152 /*-----------------------------------------------------------------*/
153 DEFSETFUNC(insertIntoLoop)
155 eBBlock *ebp = item ;
156 V_ARG(set **,regionSet);
158 loopInsert (regionSet,ebp);
162 /*-----------------------------------------------------------------*/
163 /* isNotInBlocks - will return 1 if not is blocks */
164 /*-----------------------------------------------------------------*/
165 DEFSETFUNC(isNotInBlocks)
170 if (! isinSet (blocks,ebp))
176 /*-----------------------------------------------------------------*/
177 /* hasIncomingDefs - has definitions coming into the loop. i.e. */
178 /* check to see if the preheaders outDefs has any definitions */
179 /*-----------------------------------------------------------------*/
180 int hasIncomingDefs (region *lreg, operand *op)
182 eBBlock *preHdr = lreg->entry->preHeader;
184 if (preHdr && bitVectBitsInCommon(preHdr->outDefs,OP_DEFS(op)))
189 /*-----------------------------------------------------------------*/
190 /* findLoopEndSeq - will return the sequence number of the last */
191 /* iCode with the maximum dfNumber in the region */
192 /*-----------------------------------------------------------------*/
193 int findLoopEndSeq (region *lreg)
198 for (block = lblock =setFirstItem(lreg->regBlocks); block;
199 block = setNextItem(lreg->regBlocks)) {
200 if (block != lblock && block->lSeq > lblock->lSeq)
207 /*-----------------------------------------------------------------*/
208 /* addToExitsMarkDepth - will add the the exitSet all blocks that */
209 /* have exits, will also update the depth field in the blocks */
210 /*-----------------------------------------------------------------*/
211 DEFSETFUNC(addToExitsMarkDepth)
213 eBBlock *ebp = item ;
214 V_ARG(set *,loopBlocks);
219 /* mark the loop depth of this block */
223 /* put the loop region info in the block */
224 /* NOTE: here we will update only the inner most loop
225 that it is a part of */
226 if (!ebp->partOfLoop)
227 ebp->partOfLoop = lr;
229 /* if any of the successors go out of the loop then */
230 /* we add this one to the exits */
231 if ( applyToSet(ebp->succList,isNotInBlocks,loopBlocks)) {
232 addSetHead (exits,ebp);
239 /*-----------------------------------------------------------------*/
240 /* createLoop - will create a set of region */
241 /*-----------------------------------------------------------------*/
242 DEFSETFUNC(createLoop)
245 V_ARG(set **,allRegion);
246 region *aloop = newRegion();
249 /* make sure regionStack is empty */
250 while (!STACK_EMPTY(regionStack))
251 STACK_POP(regionStack);
253 /* add the entryBlock */
254 addSet (&aloop->regBlocks,ep->to);
255 loopInsert (&aloop->regBlocks,ep->from);
257 while (!STACK_EMPTY(regionStack)) {
258 block = STACK_POP(regionStack);
259 /* if block != entry */
261 applyToSet(block->predList,insertIntoLoop,&aloop->regBlocks);
264 aloop->entry = ep->to ;
266 /* now add it to the set */
267 addSetHead (allRegion,aloop);
271 /*-----------------------------------------------------------------*/
272 /* dominatedBy - will return 1 if item is dominated by block */
273 /*-----------------------------------------------------------------*/
274 DEFSETFUNC(dominatedBy)
277 V_ARG(eBBlock *,block);
279 return bitVectBitValue (ebp->domVect,block->bbnum);
282 /*-----------------------------------------------------------------*/
283 /* addDefInExprs - adds an expression into the inexpressions */
284 /*-----------------------------------------------------------------*/
285 DEFSETFUNC(addDefInExprs)
289 V_ARG(eBBlock **,ebbs);
292 addSetHead(&ebp->inExprs,cdp);
293 cseBBlock (ebp,0,ebbs,count);
297 /*-----------------------------------------------------------------*/
298 /* assignmentsToSym - for a set of blocks determine # time assigned*/
299 /*-----------------------------------------------------------------*/
300 int assignmentsToSym (set *sset, operand *sym)
304 set *blocks = setFromSet(sset);
306 for (ebp = setFirstItem(blocks) ; ebp ;
307 ebp = setNextItem(blocks)) {
309 /* get all the definitions for this symbol
311 bitVect *defs = bitVectIntersect(ebp->ldefs,OP_DEFS(sym));
312 assigns += bitVectnBitsOn(defs);
313 setToNull((void **)&defs);
321 /*-----------------------------------------------------------------*/
322 /* isOperandInvariant - determines if an operand is an invariant */
323 /*-----------------------------------------------------------------*/
324 int isOperandInvariant (operand *op, region *theLoop, set *lInvars)
327 /* operand is an invariant if it is a */
329 /* b. that have defintions reaching loop entry */
330 /* c. that are already defined as invariant */
331 /* d. has no assignments in the loop */
333 if (IS_OP_LITERAL(op))
337 OP_SYMBOL(op)->addrtaken)
340 if (ifDefSymIs(theLoop->entry->inExprs,op))
343 if (ifDefSymIs(lInvars,op))
347 ! IS_OP_GLOBAL(op) &&
348 ! IS_OP_VOLATILE(op) &&
349 assignmentsToSym (theLoop->regBlocks,op) == 0 )
356 /*-----------------------------------------------------------------*/
357 /* pointerAssigned - will return 1 if pointer set found */
358 /*-----------------------------------------------------------------*/
359 DEFSETFUNC(pointerAssigned)
364 return ebp->hasFcall || bitVectBitValue(ebp->ptrsSet,op->key);
367 /*-----------------------------------------------------------------*/
368 /* hasNonPtrUse - returns true if operand has non pointer usage */
369 /*-----------------------------------------------------------------*/
370 DEFSETFUNC(hasNonPtrUse)
374 iCode *ic = usedInRemaining(op,ebp->sch);
376 if (ic && !POINTER_SET(ic) && !POINTER_GET(ic))
383 /*-----------------------------------------------------------------*/
384 /* loopInvariants - takes loop invariants out of region */
385 /*-----------------------------------------------------------------*/
386 int loopInvariants( region *theLoop , eBBlock **ebbs, int count)
389 set *lInvars = NULL ;
393 /* if the preHeader does not exist then do nothing */
394 /* or no exits then do nothing ( have to think about this situation */
395 if (theLoop->entry->preHeader == NULL ||
396 theLoop->exits == NULL )
399 /* we will do the elimination for those blocks */
400 /* in the loop that dominates all exits from the loop */
401 for (lBlock = setFirstItem(theLoop->regBlocks); lBlock;
402 lBlock = setNextItem(theLoop->regBlocks)) {
408 /* mark the dominates all exits flag */
409 domsAllExits = ( applyToSet (theLoop->exits,dominatedBy,lBlock) ==
410 elementsInSet (theLoop->exits));
413 /* now we go thru the instructions of this block and */
414 /* collect those instructions with invariant operands*/
415 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
420 if (SKIP_IC(ic) || POINTER_SET(ic) || ic->op == IFX)
423 /* if result is volatile then skip */
425 ( isOperandVolatile(IC_RESULT(ic),TRUE) ||
426 IS_OP_PARM(IC_RESULT(ic))))
432 /* if address of then it is an invariant */
433 if (ic->op == ADDRESS_OF &&
434 IS_SYMOP(IC_LEFT(ic)) &&
435 IS_AGGREGATE(operandType(IC_LEFT(ic))))
438 /* check if left operand is an invariant */
439 if ( (lin = isOperandInvariant (IC_LEFT(ic),theLoop,lInvars)))
440 /* if this is a pointer get then make sure
441 that the pointer set does not exist in
443 if (POINTER_GET(ic) &&
444 ( applyToSet (theLoop->regBlocks,pointerAssigned,IC_LEFT(ic)) ))
447 /* do the same for right */
448 rin = isOperandInvariant (IC_RIGHT(ic),theLoop, lInvars);
450 /* if this is a POINTER_GET then special case, make sure all
451 usages within the loop are POINTER_GET any other usage
452 would mean that this is not an invariant , since the pointer
453 could then be passed as a parameter */
454 if (POINTER_GET(ic) &&
455 applyToSet(theLoop->regBlocks,hasNonPtrUse,IC_LEFT(ic)))
458 /* if both the left & right are invariants : then check that*/
459 /* this definition exists in the out definition of all the */
460 /* blocks, this will ensure that this is not assigned any */
461 /* other value in the loop , and not used in this block */
462 /* prior to this definition which means only this definition*/
463 /* is used in this loop */
464 if (lin && rin && IC_RESULT(ic)) {
466 set *lSet = setFromSet(theLoop->regBlocks);
468 /* if this block does not dominate all exists */
469 /* make sure this defintion is not used anywhere else */
472 if (isOperandGlobal(IC_RESULT(ic)))
474 /* for successors for all exits */
475 for ( sBlock = setFirstItem(theLoop->exits); sBlock;
476 sBlock = setNextItem(theLoop->exits)) {
478 for(i=0; i < count; ebbs[i++]->visited = 0);
480 if ( applyToSet (sBlock->succList,isDefAlive,ic))
484 /* we have found usage */
489 /* now make sure this is the only definition */
490 for (sBlock = setFirstItem(lSet); sBlock ;
491 sBlock = setNextItem (lSet)) {
492 /* if this is the block make sure the definition */
493 /* reaches the end of the block */
494 if (sBlock == lBlock ) {
495 if (! ifDiCodeIs (sBlock->outExprs,ic))
499 if (bitVectBitsInCommon (sBlock->defSet,OP_DEFS(IC_RESULT(ic))))
504 continue ; /* another definition present in the block */
506 /* now check if it exists in the in of this block */
507 /* if not then it was killed before this instruction */
508 if (! bitVectBitValue (lBlock->inDefs,ic->key))
511 /* now we know it is a true invariant */
512 /* remove it from the insts chain & put */
513 /* in the invariant set */
514 OP_SYMBOL(IC_RESULT(ic))->isinvariant = 1;
515 remiCodeFromeBBlock (lBlock,ic);
517 /* maintain the data flow */
518 /* this means removing from definition from the */
519 /* defset of this block and adding it to the */
520 /* inexpressions of all blocks within the loop */
521 bitVectUnSetBit (lBlock->defSet,ic->key);
522 bitVectUnSetBit (lBlock->ldefs,ic->key);
523 ivar = newCseDef(IC_RESULT(ic),ic);
524 applyToSet (theLoop->regBlocks, addDefInExprs, ivar,ebbs,count);
525 addSet(&lInvars,ivar);
528 } /* for all loop blocks */
530 /* if we have some invariants then */
532 eBBlock *preHdr= theLoop->entry->preHeader ;
533 iCode *icFirst = NULL , *icLast = NULL ;
536 /* create an iCode chain from it */
537 for (cdp = setFirstItem(lInvars); cdp ; cdp = setNextItem(lInvars)) {
539 /* maintain data flow .. add it to the */
540 /* ldefs defSet & outExprs of the preheader */
541 preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
542 preHdr->ldefs = bitVectSetBit (preHdr->ldefs,cdp->diCode->key);
543 cdp->diCode->lineno = preHdr->ech->lineno;
544 addSetHead (&preHdr->outExprs,cdp);
548 icFirst = cdp->diCode;
550 icLast->next = cdp->diCode;
551 cdp->diCode->prev = icLast;
552 icLast = cdp->diCode ;
554 icLast = cdp->diCode;
558 /* add the instruction chain to the end of the
559 preheader for this loop, preheaders will always
560 have atleast a label */
561 preHdr->ech->next = icFirst ;
562 icFirst->prev = preHdr->ech ;
563 preHdr->ech = icLast;
570 /*-----------------------------------------------------------------*/
571 /* addressTaken - returns true if the symbol is found in the addrof*/
572 /*-----------------------------------------------------------------*/
573 int addressTaken (set *sset ,operand *sym)
579 for (loop = sset; loop ; loop = loop->next) {
581 loop2 = ebp->addrOf ;
583 if (isOperandEqual((operand *)loop2->item,sym))
593 /*-----------------------------------------------------------------*/
594 /* findInduction :- returns 1 & the item if the induction is found */
595 /*-----------------------------------------------------------------*/
596 DEFSETFUNC(findInduction)
598 induction *ip = item;
599 V_ARG(operand *,sym);
600 V_ARG(induction **,ipp);
602 if (isOperandEqual(ip->sym,sym)) {
610 /*-----------------------------------------------------------------*/
611 /* findDefInRegion - finds the definition within the region */
612 /*-----------------------------------------------------------------*/
613 iCode *findDefInRegion (set *regBlocks, operand *defOp, eBBlock **owner)
617 /* for all blocks in the region */
618 for (lBlock = setFirstItem(regBlocks); lBlock ;
619 lBlock = setNextItem(regBlocks)) {
621 /* if a definition for this exists */
622 if (bitVectBitsInCommon(lBlock->defSet,OP_DEFS(defOp))) {
625 /* go thru the instruction chain to find it */
626 for (ic = lBlock->sch ; ic ; ic = ic->next )
627 if (bitVectBitValue (OP_DEFS(defOp),ic->key)) {
638 /*-----------------------------------------------------------------*/
639 /* basicInduction - finds the basic induction variables in a loop */
640 /*-----------------------------------------------------------------*/
641 set *basicInduction (region *loopReg , eBBlock **ebbs, int count)
644 set *indVars = NULL ;
646 /* i.e. all assignments of the form a := a +/- const*/
647 /* for all blocks within the loop do */
648 for ( lBlock = setFirstItem(loopReg->regBlocks); lBlock ;
649 lBlock = setNextItem(loopReg->regBlocks)) {
653 /* for all instructions in the blocks do */
654 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
657 unsigned long litValue ;
660 eBBlock *owner = NULL;
663 /* look for assignments of the form */
664 /* symbolVar := iTempNN */
668 if (!IS_TRUE_SYMOP(IC_RESULT(ic)) &&
669 !OP_SYMBOL(IC_RESULT(ic))->isreqv)
672 if (isOperandGlobal(IC_RESULT(ic)))
675 if (!IS_ITEMP(IC_RIGHT(ic)))
678 /* if it has multiple assignments within the loop then skip */
679 if (assignmentsToSym (loopReg->regBlocks,IC_RESULT(ic)) > 1 )
682 /* if the address of this was taken inside the loop then continue */
683 if (addressTaken (loopReg->regBlocks,IC_RESULT(ic)))
686 /* find the definition for the result in the block */
687 if (! (dic = findDefInRegion (setFromSet(loopReg->regBlocks),
688 IC_RIGHT(ic),&owner)))
691 /* if not +/- continue */
692 if (dic->op != '+' && dic->op != '-')
695 /* make sure definition is of the form a +/- c */
696 if (!IS_OP_LITERAL(IC_LEFT(dic)) && !IS_OP_LITERAL(IC_RIGHT(dic)))
699 aSym = (IS_OP_LITERAL(IC_RIGHT(dic)) ?
700 (litValue = operandLitValue(IC_RIGHT(dic)),IC_LEFT(dic)) :
701 (litValue = operandLitValue(IC_LEFT(dic)),IC_RIGHT(dic)));
703 if (!isOperandEqual(IC_RESULT(ic),aSym) &&
704 !isOperandEqual(IC_RIGHT(ic),aSym)) {
706 /* find the definition for this and check */
707 if (!(ddic = findDefInRegion (setFromSet(loopReg->regBlocks),
714 if (!isOperandEqual(IC_RESULT(ddic),aSym) ||
715 !isOperandEqual(IC_RIGHT(ddic),IC_RESULT(ic)))
719 /* if the right hand side has more than one usage then
720 don't make it an induction (will have to think some more) */
721 if (bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) > 1)
724 /* if the definition is volatile then it cannot be
725 an induction object */
726 if (isOperandVolatile(IC_RIGHT(ic),FALSE) ||
727 isOperandVolatile(IC_RESULT(ic),FALSE))
730 /* whew !! that was a lot of work to find the definition */
731 /* create an induction object */
732 indIc = newiCode('=',NULL,IC_RESULT(ic));
733 indIc->lineno = ic->lineno;
734 IC_RESULT(indIc) = operandFromOperand(IC_RIGHT(ic));
735 IC_RESULT(indIc)->isaddr = 0;
736 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
737 ip = newInduction (IC_RIGHT(ic),dic->op,litValue,indIc,NULL);
739 /* replace the inducted variable by the iTemp */
740 replaceSymBySym (loopReg->regBlocks,IC_RESULT(ic),IC_RIGHT(ic));
742 /* if it has only one exit then remove it from here
743 and put it in the exit block */
744 nexits = elementsInSet (loopReg->exits);
746 eBBlock *exit = setFirstItem(loopReg->exits);
748 /* if it is the same block then there is no
749 need to move it about */
750 if ( exit != lBlock) {
751 iCode *saveic = ic->prev;
753 remiCodeFromeBBlock(lBlock,ic);
754 /* clear the definition */
755 bitVectUnSetBit(lBlock->defSet,ic->key);
756 /* add it to the exit */
757 addiCodeToeBBlock(exit,ic,NULL);
758 /* set the definition bit */
759 exit->defSet = bitVectSetBit(exit->defSet,ic->key);
764 /* if the number of exits is greater than one then
765 we use another trick ; we will create an intersection
766 of succesors of the exits, then take those that are not
767 part of the loop and have dfNumber greater loop entry
768 and insert a new definition in them */
771 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits,ebbs);
773 /* loopSuccs now contains intersection
774 of all the loops successors */
777 for (i = 0 ; i < loopSuccs->size; i++) {
778 if (bitVectBitValue(loopSuccs,i)) {
780 eBBlock *eblock = ebbs[i];
782 /* if the successor does not belong to the loop
783 and will be executed after the loop : then
784 add a definition to the block */
785 if ( !isinSet(loopReg->regBlocks,eblock) &&
786 eblock->dfnum > loopReg->entry->dfnum) {
787 /* create the definition */
788 iCode *newic = newiCode('=',NULL,
789 operandFromOperand(IC_RIGHT(ic)));
790 IC_RESULT(newic) = operandFromOperand(IC_RESULT(ic));
791 OP_DEFS(IC_RESULT(newic)) =
792 bitVectSetBit(OP_DEFS(IC_RESULT(newic)),newic->key);
793 OP_USES(IC_RIGHT(newic)) =
794 bitVectSetBit(OP_USES(IC_RIGHT(newic)),newic->key);
796 if (eblock->sch && eblock->sch->op == LABEL)
797 addiCodeToeBBlock(eblock,newic,eblock->sch->next);
799 addiCodeToeBBlock(eblock,newic,eblock->sch);
800 /* set the definition bit */
801 eblock->defSet = bitVectSetBit(eblock->defSet,ic->key);
808 addSet (&indVars,ip);
811 } /* end of all blocks for basic induction variables */
816 /*-----------------------------------------------------------------*/
817 /* loopInduction - remove induction variables from a loop */
818 /*-----------------------------------------------------------------*/
819 int loopInduction( region *loopReg, eBBlock **ebbs, int count)
822 eBBlock *lBlock, *lastBlock = NULL;
823 set *indVars = NULL ;
826 if (loopReg->entry->preHeader == NULL)
829 /* we first determine the basic Induction variables */
830 basicInd = setFromSet(indVars = basicInduction(loopReg, ebbs,count));
832 /* find other induction variables : by other we mean definitions of */
833 /* the form x := y (* | / ) <constant> .. we will move this one to */
834 /* beginning of the loop and reduce strength i.e. replace with +/- */
835 /* these expensive expressions: OH! and y must be induction too */
836 for ( lBlock = setFirstItem(loopReg->regBlocks), lastBlock = lBlock;
838 lBlock = setNextItem(loopReg->regBlocks)) {
843 /* last block is the one with the highest block
845 if (lastBlock->bbnum < lBlock->bbnum )
848 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
850 unsigned long litVal ;
853 /* consider only * & / */
854 if (ic->op != '*' && ic->op != '/')
857 /* if the result has more definitions then */
858 if (assignmentsToSym(loopReg->regBlocks,IC_RESULT(ic)) > 1)
861 /* check if the operands are what we want */
862 /* i.e. one of them an symbol the other a literal */
863 if (! ( (IS_SYMOP(IC_LEFT(ic)) && IS_OP_LITERAL(IC_RIGHT(ic))) ||
864 (IS_OP_LITERAL(IC_LEFT(ic)) && IS_SYMOP(IC_RIGHT(ic))) ))
867 aSym = (IS_SYMOP(IC_LEFT(ic)) ?
868 (lr = 1, litVal = operandLitValue(IC_RIGHT(ic)), IC_LEFT(ic) ) :
869 (litVal= operandLitValue(IC_LEFT(ic)), IC_RIGHT(ic) ) ) ;
872 /* check if this is an induction variable */
873 if (! applyToSetFTrue (basicInd,findInduction,aSym,&ip))
876 /* ask port for size not worth if native instruction
877 exist for multiply & divide */
878 if (getSize(operandType(IC_LEFT(ic))) <= port->muldiv.native_below ||
879 getSize(operandType(IC_RIGHT(ic))) <= port->muldiv.native_below)
882 /* if this is a division then the remainder should be zero
883 for it to be inducted */
884 if (ic->op == '/' && (ip->cval % litVal))
887 /* create the iCode to be placed in the loop header */
888 /* and create the induction object */
890 /* create an instruction */
891 /* this will be put on the loop header */
892 indIc = newiCode(ic->op,
893 operandFromOperand(aSym),
894 operandFromLit(litVal));
895 indIc->lineno = ic->lineno;
896 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
897 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
899 /* keep track of the inductions */
900 litVal = (ic->op == '*' ? (litVal * ip->cval) :
901 (ip->cval / litVal));
904 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
906 /* now change this instruction */
909 IC_LEFT(ic) = operandFromOperand(IC_RESULT(ic));
910 IC_RIGHT(ic) = operandFromLit(litVal);
912 IC_RIGHT(ic) = operandFromOperand(IC_RESULT(ic));
913 IC_LEFT(ic) = operandFromLit(litVal);
916 /* we need somemore initialisation code */
917 /* we subtract the litVal from itself if increment */
918 if ( ic->op == '+' ) {
919 indIc = newiCode('-',
920 operandFromOperand(IC_RESULT(ic)),
921 operandFromLit(litVal));
922 indIc->lineno = ic->lineno;
923 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
926 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
931 /* if we have some induction variables then */
933 eBBlock *preHdr = loopReg->entry->preHeader ;
934 iCode *icFirst = NULL , *icLast = NULL ;
936 bitVect *indVect = NULL;
938 /* create an iCode chain from it */
939 for (ip = setFirstItem(indVars);
941 ip = setNextItem(indVars)) {
943 indVect = bitVectSetBit(indVect,ip->ic->key);
944 ip->ic->lineno = preHdr->ech->lineno;
948 icLast->next = ip->ic;
949 ip->ic->prev = icLast;
956 /* add the instruction chain to the end of the */
957 /* preheader for this loop */
958 preHdr->ech->next = icFirst ;
959 icFirst->prev = preHdr->ech ;
960 preHdr->ech = icLast;
963 /* add the induction variable vector to the last
965 lastBlock->isLastInLoop = 1;
966 lastBlock->linds = indVect;
969 setToNull ((void **)&indVars);
973 /*-----------------------------------------------------------------*/
974 /* mergeRegions - will merge region with same entry point */
975 /*-----------------------------------------------------------------*/
976 DEFSETFUNC(mergeRegions)
978 region *theLoop = item;
979 V_ARG(set*,allRegion) ;
982 /* if this has already been merged then do nothing */
986 /* go thru all the region and check if any of them have the */
987 /* entryPoint as the Loop */
988 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
993 if (lp->entry == theLoop->entry) {
994 theLoop->regBlocks = unionSets (theLoop->regBlocks,
995 lp->regBlocks,THROW_BOTH);
1003 /*-----------------------------------------------------------------*/
1004 /* ifMerged - return 1 if the merge flag is 1 */
1005 /*-----------------------------------------------------------------*/
1006 DEFSETFUNC(ifMerged)
1013 /*-----------------------------------------------------------------*/
1014 /* mergeInnerLoops - will merge into body when entry is present */
1015 /*-----------------------------------------------------------------*/
1016 DEFSETFUNC(mergeInnerLoops)
1018 region *theLoop = item;
1019 V_ARG(set *,allRegion);
1020 V_ARG(int *,maxDepth);
1023 /* check if the entry point is present in the body of any */
1024 /* loop then put the body of this loop into the outer loop*/
1025 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
1027 if ( lp == theLoop )
1030 if (isinSet(lp->regBlocks, theLoop->entry)) {
1031 lp->containsLoops += theLoop->containsLoops + 1 ;
1032 if ( lp->containsLoops > (*maxDepth))
1033 *maxDepth = lp->containsLoops;
1035 lp->regBlocks = unionSets (lp->regBlocks,
1036 theLoop->regBlocks,THROW_DEST);
1044 /*-----------------------------------------------------------------*/
1045 /* createLoopRegions - will detect and create a set of natural loops */
1046 /*-----------------------------------------------------------------*/
1047 hTab *createLoopRegions (eBBlock **ebbs , int count )
1049 set *allRegion = NULL; /* set of all loops */
1050 hTab *orderedLoops = NULL ;
1055 /* get all the back edges in the graph */
1056 if (! applyToSet(graphEdges,backEdges,&bEdges))
1057 return 0 ; /* found no loops */
1059 /* for each of these back edges get the blocks that */
1060 /* constitute the loops */
1061 applyToSet(bEdges,createLoop,&allRegion);
1063 /* now we will create regions from these loops */
1064 /* loops with the same entry points are considered to be the */
1065 /* same loop & they are merged. If the entry point of a loop */
1066 /* is found in the body of another loop then , all the blocks*/
1067 /* in that loop are added to the loops containing the header */
1068 applyToSet(allRegion, mergeRegions , allRegion);
1070 /* delete those already merged */
1071 deleteItemIf (&allRegion, ifMerged);
1073 applyToSet(allRegion, mergeInnerLoops, allRegion, &maxDepth);
1075 /* now create all the exits .. also */
1076 /* create an ordered set of loops */
1077 /* i.e. we process loops in the inner to outer order */
1078 for (lp = setFirstItem(allRegion) ; lp ; lp = setNextItem(allRegion)) {
1079 applyToSet (lp->regBlocks,addToExitsMarkDepth,
1080 lp->regBlocks,&lp->exits,
1081 (maxDepth - lp->containsLoops),lp);
1083 hTabAddItem (&orderedLoops,lp->containsLoops,lp);
1086 return orderedLoops ;
1089 /*-----------------------------------------------------------------*/
1090 /* loopOptimizations - identify region & remove invariants & ind */
1091 /*-----------------------------------------------------------------*/
1092 int loopOptimizations (hTab *orderedLoops, eBBlock **ebbs, int count)
1099 /* if no loop optimizations requested */
1100 if (! optimize.loopInvariant &&
1101 ! optimize.loopInduction )
1104 /* now we process the loops inner to outer order */
1105 /* this is essential to maintain data flow information */
1106 /* the other choice is an ugly iteration for the depth */
1107 /* of the loops would hate that */
1108 for ( lp = hTabFirstItem(orderedLoops,&k); lp ;
1109 lp = hTabNextItem(orderedLoops,&k)) {
1111 if (optimize.loopInvariant)
1112 change += loopInvariants(lp, ebbs, count);
1114 if (optimize.loopInduction)
1115 change += loopInduction(lp, ebbs, count);