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 /* defSet & outExprs of the preheader */
541 preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
542 cdp->diCode->lineno = preHdr->ech->lineno;
543 addSetHead (&preHdr->outExprs,cdp);
547 icFirst = cdp->diCode;
549 icLast->next = cdp->diCode;
550 cdp->diCode->prev = icLast;
551 icLast = cdp->diCode ;
553 icLast = cdp->diCode;
557 /* add the instruction chain to the end of the
558 preheader for this loop, preheaders will always
559 have atleast a label */
560 preHdr->ech->next = icFirst ;
561 icFirst->prev = preHdr->ech ;
562 preHdr->ech = icLast;
569 /*-----------------------------------------------------------------*/
570 /* addressTaken - returns true if the symbol is found in the addrof*/
571 /*-----------------------------------------------------------------*/
572 int addressTaken (set *sset ,operand *sym)
578 for (loop = sset; loop ; loop = loop->next) {
580 loop2 = ebp->addrOf ;
582 if (isOperandEqual((operand *)loop2->item,sym))
592 /*-----------------------------------------------------------------*/
593 /* findInduction :- returns 1 & the item if the induction is found */
594 /*-----------------------------------------------------------------*/
595 DEFSETFUNC(findInduction)
597 induction *ip = item;
598 V_ARG(operand *,sym);
599 V_ARG(induction **,ipp);
601 if (isOperandEqual(ip->sym,sym)) {
609 /*-----------------------------------------------------------------*/
610 /* findDefInRegion - finds the definition within the region */
611 /*-----------------------------------------------------------------*/
612 iCode *findDefInRegion (set *regBlocks, operand *defOp, eBBlock **owner)
616 /* for all blocks in the region */
617 for (lBlock = setFirstItem(regBlocks); lBlock ;
618 lBlock = setNextItem(regBlocks)) {
620 /* if a definition for this exists */
621 if (bitVectBitsInCommon(lBlock->defSet,OP_DEFS(defOp))) {
624 /* go thru the instruction chain to find it */
625 for (ic = lBlock->sch ; ic ; ic = ic->next )
626 if (bitVectBitValue (OP_DEFS(defOp),ic->key)) {
637 /*-----------------------------------------------------------------*/
638 /* basicInduction - finds the basic induction variables in a loop */
639 /*-----------------------------------------------------------------*/
640 set *basicInduction (region *loopReg , eBBlock **ebbs, int count)
643 set *indVars = NULL ;
645 /* i.e. all assignments of the form a := a +/- const*/
646 /* for all blocks within the loop do */
647 for ( lBlock = setFirstItem(loopReg->regBlocks); lBlock ;
648 lBlock = setNextItem(loopReg->regBlocks)) {
652 /* for all instructions in the blocks do */
653 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
656 unsigned long litValue ;
659 eBBlock *owner = NULL;
662 /* look for assignments of the form */
663 /* symbolVar := iTempNN */
667 if (!IS_TRUE_SYMOP(IC_RESULT(ic)) &&
668 !OP_SYMBOL(IC_RESULT(ic))->isreqv)
671 if (isOperandGlobal(IC_RESULT(ic)))
674 if (!IS_ITEMP(IC_RIGHT(ic)))
677 /* if it has multiple assignments within the loop then skip */
678 if (assignmentsToSym (loopReg->regBlocks,IC_RESULT(ic)) > 1 )
681 /* if the address of this was taken inside the loop then continue */
682 if (addressTaken (loopReg->regBlocks,IC_RESULT(ic)))
685 /* find the definition for the result in the block */
686 if (! (dic = findDefInRegion (setFromSet(loopReg->regBlocks),
687 IC_RIGHT(ic),&owner)))
690 /* if not +/- continue */
691 if (dic->op != '+' && dic->op != '-')
694 /* make sure definition is of the form a +/- c */
695 if (!IS_OP_LITERAL(IC_LEFT(dic)) && !IS_OP_LITERAL(IC_RIGHT(dic)))
698 aSym = (IS_OP_LITERAL(IC_RIGHT(dic)) ?
699 (litValue = operandLitValue(IC_RIGHT(dic)),IC_LEFT(dic)) :
700 (litValue = operandLitValue(IC_LEFT(dic)),IC_RIGHT(dic)));
702 if (!isOperandEqual(IC_RESULT(ic),aSym) &&
703 !isOperandEqual(IC_RIGHT(ic),aSym)) {
705 /* find the definition for this and check */
706 if (!(ddic = findDefInRegion (setFromSet(loopReg->regBlocks),
713 if (!isOperandEqual(IC_RESULT(ddic),aSym) ||
714 !isOperandEqual(IC_RIGHT(ddic),IC_RESULT(ic)))
718 /* if the right hand side has more than one usage then
719 don't make it an induction (will have to think some more) */
720 if (bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) > 1)
723 /* if the definition is volatile then it cannot be
724 an induction object */
725 if (isOperandVolatile(IC_RIGHT(ic),FALSE) ||
726 isOperandVolatile(IC_RESULT(ic),FALSE))
729 /* whew !! that was a lot of work to find the definition */
730 /* create an induction object */
731 indIc = newiCode('=',NULL,IC_RESULT(ic));
732 indIc->lineno = ic->lineno;
733 IC_RESULT(indIc) = operandFromOperand(IC_RIGHT(ic));
734 IC_RESULT(indIc)->isaddr = 0;
735 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
736 ip = newInduction (IC_RIGHT(ic),dic->op,litValue,indIc,NULL);
738 /* replace the inducted variable by the iTemp */
739 replaceSymBySym (loopReg->regBlocks,IC_RESULT(ic),IC_RIGHT(ic));
741 /* if it has only one exit then remove it from here
742 and put it in the exit block */
743 nexits = elementsInSet (loopReg->exits);
745 eBBlock *exit = setFirstItem(loopReg->exits);
747 /* if it is the same block then there is no
748 need to move it about */
749 if ( exit != lBlock) {
750 iCode *saveic = ic->prev;
752 remiCodeFromeBBlock(lBlock,ic);
753 /* clear the definition */
754 bitVectUnSetBit(lBlock->defSet,ic->key);
755 /* add it to the exit */
756 addiCodeToeBBlock(exit,ic,NULL);
757 /* set the definition bit */
758 exit->defSet = bitVectSetBit(exit->defSet,ic->key);
763 /* if the number of exits is greater than one then
764 we use another trick ; we will create an intersection
765 of succesors of the exits, then take those that are not
766 part of the loop and have dfNumber greater loop entry
767 and insert a new definition in them */
770 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits,ebbs);
772 /* loopSuccs now contains intersection
773 of all the loops successors */
776 for (i = 0 ; i < loopSuccs->size; i++) {
777 if (bitVectBitValue(loopSuccs,i)) {
779 eBBlock *eblock = ebbs[i];
781 /* if the successor does not belong to the loop
782 and will be executed after the loop : then
783 add a definition to the block */
784 if ( !isinSet(loopReg->regBlocks,eblock) &&
785 eblock->dfnum > loopReg->entry->dfnum) {
786 /* create the definition */
787 iCode *newic = newiCode('=',NULL,
788 operandFromOperand(IC_RIGHT(ic)));
789 IC_RESULT(newic) = operandFromOperand(IC_RESULT(ic));
790 OP_DEFS(IC_RESULT(newic)) =
791 bitVectSetBit(OP_DEFS(IC_RESULT(newic)),newic->key);
792 OP_USES(IC_RIGHT(newic)) =
793 bitVectSetBit(OP_USES(IC_RIGHT(newic)),newic->key);
795 if (eblock->sch && eblock->sch->op == LABEL)
796 addiCodeToeBBlock(eblock,newic,eblock->sch->next);
798 addiCodeToeBBlock(eblock,newic,eblock->sch);
799 /* set the definition bit */
800 eblock->defSet = bitVectSetBit(eblock->defSet,ic->key);
807 addSet (&indVars,ip);
810 } /* end of all blocks for basic induction variables */
815 /*-----------------------------------------------------------------*/
816 /* loopInduction - remove induction variables from a loop */
817 /*-----------------------------------------------------------------*/
818 int loopInduction( region *loopReg, eBBlock **ebbs, int count)
821 eBBlock *lBlock, *lastBlock = NULL;
822 set *indVars = NULL ;
825 if (loopReg->entry->preHeader == NULL)
828 /* we first determine the basic Induction variables */
829 basicInd = setFromSet(indVars = basicInduction(loopReg, ebbs,count));
831 /* find other induction variables : by other we mean definitions of */
832 /* the form x := y (* | / ) <constant> .. we will move this one to */
833 /* beginning of the loop and reduce strength i.e. replace with +/- */
834 /* these expensive expressions: OH! and y must be induction too */
835 for ( lBlock = setFirstItem(loopReg->regBlocks), lastBlock = lBlock;
837 lBlock = setNextItem(loopReg->regBlocks)) {
842 /* last block is the one with the highest block
844 if (lastBlock->bbnum < lBlock->bbnum )
847 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
849 unsigned long litVal ;
852 /* consider only * & / */
853 if (ic->op != '*' && ic->op != '/')
856 /* if the result has more definitions then */
857 if (assignmentsToSym(loopReg->regBlocks,IC_RESULT(ic)) > 1)
860 /* check if the operands are what we want */
861 /* i.e. one of them an symbol the other a literal */
862 if (! ( (IS_SYMOP(IC_LEFT(ic)) && IS_OP_LITERAL(IC_RIGHT(ic))) ||
863 (IS_OP_LITERAL(IC_LEFT(ic)) && IS_SYMOP(IC_RIGHT(ic))) ))
866 aSym = (IS_SYMOP(IC_LEFT(ic)) ?
867 (lr = 1, litVal = operandLitValue(IC_RIGHT(ic)), IC_LEFT(ic) ) :
868 (litVal= operandLitValue(IC_LEFT(ic)), IC_RIGHT(ic) ) ) ;
871 /* check if this is an induction variable */
872 if (! applyToSetFTrue (basicInd,findInduction,aSym,&ip))
875 /* ask port for size not worth if native instruction
876 exist for multiply & divide */
877 if (getSize(operandType(IC_LEFT(ic))) <= port->muldiv.native_below ||
878 getSize(operandType(IC_RIGHT(ic))) <= port->muldiv.native_below)
881 /* if this is a division then the remainder should be zero
882 for it to be inducted */
883 if (ic->op == '/' && (ip->cval % litVal))
886 /* create the iCode to be placed in the loop header */
887 /* and create the induction object */
889 /* create an instruction */
890 /* this will be put on the loop header */
891 indIc = newiCode(ic->op,
892 operandFromOperand(aSym),
893 operandFromLit(litVal));
894 indIc->lineno = ic->lineno;
895 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
896 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
898 /* keep track of the inductions */
899 litVal = (ic->op == '*' ? (litVal * ip->cval) :
900 (ip->cval / litVal));
903 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
905 /* now change this instruction */
908 IC_LEFT(ic) = operandFromOperand(IC_RESULT(ic));
909 IC_RIGHT(ic) = operandFromLit(litVal);
911 IC_RIGHT(ic) = operandFromOperand(IC_RESULT(ic));
912 IC_LEFT(ic) = operandFromLit(litVal);
915 /* we need somemore initialisation code */
916 /* we subtract the litVal from itself if increment */
917 if ( ic->op == '+' ) {
918 indIc = newiCode('-',
919 operandFromOperand(IC_RESULT(ic)),
920 operandFromLit(litVal));
921 indIc->lineno = ic->lineno;
922 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
925 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
930 /* if we have some induction variables then */
932 eBBlock *preHdr = loopReg->entry->preHeader ;
933 iCode *icFirst = NULL , *icLast = NULL ;
935 bitVect *indVect = NULL;
937 /* create an iCode chain from it */
938 for (ip = setFirstItem(indVars);
940 ip = setNextItem(indVars)) {
942 indVect = bitVectSetBit(indVect,ip->ic->key);
943 ip->ic->lineno = preHdr->ech->lineno;
947 icLast->next = ip->ic;
948 ip->ic->prev = icLast;
955 /* add the instruction chain to the end of the */
956 /* preheader for this loop */
957 preHdr->ech->next = icFirst ;
958 icFirst->prev = preHdr->ech ;
959 preHdr->ech = icLast;
962 /* add the induction variable vector to the last
964 lastBlock->isLastInLoop = 1;
965 lastBlock->linds = indVect;
968 setToNull ((void **)&indVars);
972 /*-----------------------------------------------------------------*/
973 /* mergeRegions - will merge region with same entry point */
974 /*-----------------------------------------------------------------*/
975 DEFSETFUNC(mergeRegions)
977 region *theLoop = item;
978 V_ARG(set*,allRegion) ;
981 /* if this has already been merged then do nothing */
985 /* go thru all the region and check if any of them have the */
986 /* entryPoint as the Loop */
987 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
992 if (lp->entry == theLoop->entry) {
993 theLoop->regBlocks = unionSets (theLoop->regBlocks,
994 lp->regBlocks,THROW_BOTH);
1002 /*-----------------------------------------------------------------*/
1003 /* ifMerged - return 1 if the merge flag is 1 */
1004 /*-----------------------------------------------------------------*/
1005 DEFSETFUNC(ifMerged)
1012 /*-----------------------------------------------------------------*/
1013 /* mergeInnerLoops - will merge into body when entry is present */
1014 /*-----------------------------------------------------------------*/
1015 DEFSETFUNC(mergeInnerLoops)
1017 region *theLoop = item;
1018 V_ARG(set *,allRegion);
1019 V_ARG(int *,maxDepth);
1022 /* check if the entry point is present in the body of any */
1023 /* loop then put the body of this loop into the outer loop*/
1024 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
1026 if ( lp == theLoop )
1029 if (isinSet(lp->regBlocks, theLoop->entry)) {
1030 lp->containsLoops += theLoop->containsLoops + 1 ;
1031 if ( lp->containsLoops > (*maxDepth))
1032 *maxDepth = lp->containsLoops;
1034 lp->regBlocks = unionSets (lp->regBlocks,
1035 theLoop->regBlocks,THROW_DEST);
1043 /*-----------------------------------------------------------------*/
1044 /* createLoopRegions - will detect and create a set of natural loops */
1045 /*-----------------------------------------------------------------*/
1046 hTab *createLoopRegions (eBBlock **ebbs , int count )
1048 set *allRegion = NULL; /* set of all loops */
1049 hTab *orderedLoops = NULL ;
1054 /* get all the back edges in the graph */
1055 if (! applyToSet(graphEdges,backEdges,&bEdges))
1056 return 0 ; /* found no loops */
1058 /* for each of these back edges get the blocks that */
1059 /* constitute the loops */
1060 applyToSet(bEdges,createLoop,&allRegion);
1062 /* now we will create regions from these loops */
1063 /* loops with the same entry points are considered to be the */
1064 /* same loop & they are merged. If the entry point of a loop */
1065 /* is found in the body of another loop then , all the blocks*/
1066 /* in that loop are added to the loops containing the header */
1067 applyToSet(allRegion, mergeRegions , allRegion);
1069 /* delete those already merged */
1070 deleteItemIf (&allRegion, ifMerged);
1072 applyToSet(allRegion, mergeInnerLoops, allRegion, &maxDepth);
1074 /* now create all the exits .. also */
1075 /* create an ordered set of loops */
1076 /* i.e. we process loops in the inner to outer order */
1077 for (lp = setFirstItem(allRegion) ; lp ; lp = setNextItem(allRegion)) {
1078 applyToSet (lp->regBlocks,addToExitsMarkDepth,
1079 lp->regBlocks,&lp->exits,
1080 (maxDepth - lp->containsLoops),lp);
1082 hTabAddItem (&orderedLoops,lp->containsLoops,lp);
1085 return orderedLoops ;
1088 /*-----------------------------------------------------------------*/
1089 /* loopOptimizations - identify region & remove invariants & ind */
1090 /*-----------------------------------------------------------------*/
1091 int loopOptimizations (hTab *orderedLoops, eBBlock **ebbs, int count)
1098 /* if no loop optimizations requested */
1099 if (! optimize.loopInvariant &&
1100 ! optimize.loopInduction )
1103 /* now we process the loops inner to outer order */
1104 /* this is essential to maintain data flow information */
1105 /* the other choice is an ugly iteration for the depth */
1106 /* of the loops would hate that */
1107 for ( lp = hTabFirstItem(orderedLoops,&k); lp ;
1108 lp = hTabNextItem(orderedLoops,&k)) {
1110 if (optimize.loopInvariant)
1111 change += loopInvariants(lp, ebbs, count);
1113 if (optimize.loopInduction)
1114 change += loopInduction(lp, ebbs, count);