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 -------------------------------------------------------------------------*/
27 #include "SDCCglobl.h"
31 #include "SDCChasht.h"
34 #include "SDCCicode.h"
35 #include "SDCClabel.h"
36 #include "SDCCBBlock.h"
37 #include "SDCCdflow.h"
40 DEFSETFUNC(isDefAlive);
42 STACK_DCL(regionStack,eBBlock *, MAX_NEST_LEVEL * 10);
44 /*-----------------------------------------------------------------*/
45 /* newInduction - creates a new induction variable */
46 /*-----------------------------------------------------------------*/
47 induction *newInduction (operand *sym, unsigned int op,
48 long constVal, iCode *ic, operand *asym)
52 ALLOC(ip,sizeof(induction));
63 /*-----------------------------------------------------------------*/
64 /* newRegion - allocate & returns a loop structure */
65 /*-----------------------------------------------------------------*/
70 ALLOC(lp,sizeof(region));
76 /*-----------------------------------------------------------------*/
77 /* pinduction - prints induction */
78 /*-----------------------------------------------------------------*/
79 DEFSETFUNC(pinduction)
85 printOperand(ip->sym,stdout);
86 icTab = getTableEntry(ip->ic->op);
87 icTab->iCodePrint(stdout,ip->ic,icTab->printName);
88 fprintf(stdout," %04d\n",(int)ip->cval);
92 /*-----------------------------------------------------------------*/
93 /* pregion - prints loop information */
94 /*-----------------------------------------------------------------*/
99 printf("================\n");
100 printf(" loop with entry -- > "); printEntryLabel(lp->entry,ap);
102 printf(" loop body --> "); applyToSet(lp->regBlocks,printEntryLabel);
104 printf(" loop exits --> "); 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)) {
121 addSetHead (bEdges,ep);
128 /*-----------------------------------------------------------------*/
129 /* intersectLoopSucc - returns intersection of loop Successors */
130 /*-----------------------------------------------------------------*/
131 static bitVect *intersectLoopSucc ( set *lexits, eBBlock **ebbs)
133 bitVect *succVect = NULL;
134 eBBlock *exit = setFirstItem(lexits);
139 succVect = bitVectCopy(exit->succVect);
141 for (exit = setNextItem(lexits); exit ;
142 exit = setNextItem(lexits)) {
143 succVect = bitVectIntersect(succVect,
151 /*-----------------------------------------------------------------*/
152 /* loopInsert will insert a block into the loop set */
153 /*-----------------------------------------------------------------*/
154 static void loopInsert (set **regionSet, eBBlock *block)
156 if (!isinSet (*regionSet,block)) {
157 addSetHead (regionSet,block);
158 STACK_PUSH(regionStack,block);
162 /*-----------------------------------------------------------------*/
163 /* insertIntoLoop - insert item into loop */
164 /*-----------------------------------------------------------------*/
165 DEFSETFUNC(insertIntoLoop)
167 eBBlock *ebp = item ;
168 V_ARG(set **,regionSet);
170 loopInsert (regionSet,ebp);
174 /*-----------------------------------------------------------------*/
175 /* isNotInBlocks - will return 1 if not is blocks */
176 /*-----------------------------------------------------------------*/
177 DEFSETFUNC(isNotInBlocks)
182 if (! isinSet (blocks,ebp))
188 /*-----------------------------------------------------------------*/
189 /* hasIncomingDefs - has definitions coming into the loop. i.e. */
190 /* check to see if the preheaders outDefs has any definitions */
191 /*-----------------------------------------------------------------*/
192 int 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 /*-----------------------------------------------------------------*/
205 int findLoopEndSeq (region *lreg)
210 for (block = lblock =setFirstItem(lreg->regBlocks); block;
211 block = setNextItem(lreg->regBlocks)) {
212 if (block != lblock && block->lSeq > lblock->lSeq)
219 /*-----------------------------------------------------------------*/
220 /* addToExitsMarkDepth - will add the the exitSet all blocks that */
221 /* have exits, will also update the depth field in the blocks */
222 /*-----------------------------------------------------------------*/
223 DEFSETFUNC(addToExitsMarkDepth)
225 eBBlock *ebp = item ;
226 V_ARG(set *,loopBlocks);
231 /* mark the loop depth of this block */
235 /* put the loop region info in the block */
236 /* NOTE: here we will update only the inner most loop
237 that it is a part of */
238 if (!ebp->partOfLoop)
239 ebp->partOfLoop = lr;
241 /* if any of the successors go out of the loop then */
242 /* we add this one to the exits */
243 if ( applyToSet(ebp->succList,isNotInBlocks,loopBlocks)) {
244 addSetHead (exits,ebp);
251 /*-----------------------------------------------------------------*/
252 /* createLoop - will create a set of region */
253 /*-----------------------------------------------------------------*/
254 DEFSETFUNC(createLoop)
257 V_ARG(set **,allRegion);
258 region *aloop = newRegion();
261 /* make sure regionStack is empty */
262 while (!STACK_EMPTY(regionStack))
263 STACK_POP(regionStack);
265 /* add the entryBlock */
266 addSet (&aloop->regBlocks,ep->to);
267 loopInsert (&aloop->regBlocks,ep->from);
269 while (!STACK_EMPTY(regionStack)) {
270 block = STACK_POP(regionStack);
271 /* if block != entry */
273 applyToSet(block->predList,insertIntoLoop,&aloop->regBlocks);
276 aloop->entry = ep->to ;
278 /* now add it to the set */
279 addSetHead (allRegion,aloop);
283 /*-----------------------------------------------------------------*/
284 /* dominatedBy - will return 1 if item is dominated by block */
285 /*-----------------------------------------------------------------*/
286 DEFSETFUNC(dominatedBy)
289 V_ARG(eBBlock *,block);
291 return bitVectBitValue (ebp->domVect,block->bbnum);
294 /*-----------------------------------------------------------------*/
295 /* addDefInExprs - adds an expression into the inexpressions */
296 /*-----------------------------------------------------------------*/
297 DEFSETFUNC(addDefInExprs)
301 V_ARG(eBBlock **,ebbs);
304 addSetHead(&ebp->inExprs,cdp);
305 cseBBlock (ebp,0,ebbs,count);
309 /*-----------------------------------------------------------------*/
310 /* assignmentsToSym - for a set of blocks determine # time assigned*/
311 /*-----------------------------------------------------------------*/
312 int assignmentsToSym (set *sset, operand *sym)
316 set *blocks = setFromSet(sset);
318 for (ebp = setFirstItem(blocks) ; ebp ;
319 ebp = setNextItem(blocks)) {
321 /* get all the definitions for this symbol
323 bitVect *defs = bitVectIntersect(ebp->ldefs,OP_DEFS(sym));
324 assigns += bitVectnBitsOn(defs);
325 setToNull((void **)&defs);
333 /*-----------------------------------------------------------------*/
334 /* isOperandInvariant - determines if an operand is an invariant */
335 /*-----------------------------------------------------------------*/
336 int isOperandInvariant (operand *op, region *theLoop, set *lInvars)
339 /* operand is an invariant if it is a */
341 /* b. that have defintions reaching loop entry */
342 /* c. that are already defined as invariant */
343 /* d. has no assignments in the loop */
345 if (IS_OP_LITERAL(op))
349 OP_SYMBOL(op)->addrtaken)
352 if (ifDefSymIs(theLoop->entry->inExprs,op))
355 if (ifDefSymIs(lInvars,op))
359 ! IS_OP_GLOBAL(op) &&
360 ! IS_OP_VOLATILE(op) &&
361 assignmentsToSym (theLoop->regBlocks,op) == 0 )
368 /*-----------------------------------------------------------------*/
369 /* pointerAssigned - will return 1 if pointer set found */
370 /*-----------------------------------------------------------------*/
371 DEFSETFUNC(pointerAssigned)
376 return ebp->hasFcall || bitVectBitValue(ebp->ptrsSet,op->key);
379 /*-----------------------------------------------------------------*/
380 /* hasNonPtrUse - returns true if operand has non pointer usage */
381 /*-----------------------------------------------------------------*/
382 DEFSETFUNC(hasNonPtrUse)
386 iCode *ic = usedInRemaining(op,ebp->sch);
388 if (ic && !POINTER_SET(ic) && !POINTER_GET(ic))
395 /*-----------------------------------------------------------------*/
396 /* loopInvariants - takes loop invariants out of region */
397 /*-----------------------------------------------------------------*/
398 int loopInvariants( region *theLoop , eBBlock **ebbs, int count)
401 set *lInvars = NULL ;
405 /* if the preHeader does not exist then do nothing */
406 /* or no exits then do nothing ( have to think about this situation */
407 if (theLoop->entry->preHeader == NULL ||
408 theLoop->exits == NULL )
411 /* we will do the elimination for those blocks */
412 /* in the loop that dominates all exits from the loop */
413 for (lBlock = setFirstItem(theLoop->regBlocks); lBlock;
414 lBlock = setNextItem(theLoop->regBlocks)) {
420 /* mark the dominates all exits flag */
421 domsAllExits = ( applyToSet (theLoop->exits,dominatedBy,lBlock) ==
422 elementsInSet (theLoop->exits));
425 /* now we go thru the instructions of this block and */
426 /* collect those instructions with invariant operands*/
427 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
432 if (SKIP_IC(ic) || POINTER_SET(ic) || ic->op == IFX)
435 /* if result is volatile then skip */
437 ( isOperandVolatile(IC_RESULT(ic),TRUE) ||
438 IS_OP_PARM(IC_RESULT(ic))))
444 /* if address of then it is an invariant */
445 if (ic->op == ADDRESS_OF &&
446 IS_SYMOP(IC_LEFT(ic)) &&
447 IS_AGGREGATE(operandType(IC_LEFT(ic))))
450 /* check if left operand is an invariant */
451 if ( (lin = isOperandInvariant (IC_LEFT(ic),theLoop,lInvars)))
452 /* if this is a pointer get then make sure
453 that the pointer set does not exist in
455 if (POINTER_GET(ic) &&
456 ( applyToSet (theLoop->regBlocks,pointerAssigned,IC_LEFT(ic)) ))
459 /* do the same for right */
460 rin = isOperandInvariant (IC_RIGHT(ic),theLoop, lInvars);
462 /* if this is a POINTER_GET then special case, make sure all
463 usages within the loop are POINTER_GET any other usage
464 would mean that this is not an invariant , since the pointer
465 could then be passed as a parameter */
466 if (POINTER_GET(ic) &&
467 applyToSet(theLoop->regBlocks,hasNonPtrUse,IC_LEFT(ic)))
470 /* if both the left & right are invariants : then check that*/
471 /* this definition exists in the out definition of all the */
472 /* blocks, this will ensure that this is not assigned any */
473 /* other value in the loop , and not used in this block */
474 /* prior to this definition which means only this definition*/
475 /* is used in this loop */
476 if (lin && rin && IC_RESULT(ic)) {
478 set *lSet = setFromSet(theLoop->regBlocks);
480 /* if this block does not dominate all exists */
481 /* make sure this defintion is not used anywhere else */
484 if (isOperandGlobal(IC_RESULT(ic)))
486 /* for successors for all exits */
487 for ( sBlock = setFirstItem(theLoop->exits); sBlock;
488 sBlock = setNextItem(theLoop->exits)) {
490 for(i=0; i < count; ebbs[i++]->visited = 0);
492 if ( applyToSet (sBlock->succList,isDefAlive,ic))
496 /* we have found usage */
501 /* now make sure this is the only definition */
502 for (sBlock = setFirstItem(lSet); sBlock ;
503 sBlock = setNextItem (lSet)) {
504 /* if this is the block make sure the definition */
505 /* reaches the end of the block */
506 if (sBlock == lBlock ) {
507 if (! ifDiCodeIs (sBlock->outExprs,ic))
511 if (bitVectBitsInCommon (sBlock->defSet,OP_DEFS(IC_RESULT(ic))))
516 continue ; /* another definition present in the block */
518 /* now check if it exists in the in of this block */
519 /* if not then it was killed before this instruction */
520 if (! bitVectBitValue (lBlock->inDefs,ic->key))
523 /* now we know it is a true invariant */
524 /* remove it from the insts chain & put */
525 /* in the invariant set */
526 OP_SYMBOL(IC_RESULT(ic))->isinvariant = 1;
527 remiCodeFromeBBlock (lBlock,ic);
529 /* maintain the data flow */
530 /* this means removing from definition from the */
531 /* defset of this block and adding it to the */
532 /* inexpressions of all blocks within the loop */
533 bitVectUnSetBit (lBlock->defSet,ic->key);
534 bitVectUnSetBit (lBlock->ldefs,ic->key);
535 ivar = newCseDef(IC_RESULT(ic),ic);
536 applyToSet (theLoop->regBlocks, addDefInExprs, ivar,ebbs,count);
537 addSet(&lInvars,ivar);
540 } /* for all loop blocks */
542 /* if we have some invariants then */
544 eBBlock *preHdr= theLoop->entry->preHeader ;
545 iCode *icFirst = NULL , *icLast = NULL ;
548 /* create an iCode chain from it */
549 for (cdp = setFirstItem(lInvars); cdp ; cdp = setNextItem(lInvars)) {
551 /* maintain data flow .. add it to the */
552 /* defSet & outExprs of the preheader */
553 preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
554 cdp->diCode->lineno = preHdr->ech->lineno;
555 addSetHead (&preHdr->outExprs,cdp);
559 icFirst = cdp->diCode;
561 icLast->next = cdp->diCode;
562 cdp->diCode->prev = icLast;
563 icLast = cdp->diCode ;
565 icLast = cdp->diCode;
569 /* add the instruction chain to the end of the
570 preheader for this loop, preheaders will always
571 have atleast a label */
572 preHdr->ech->next = icFirst ;
573 icFirst->prev = preHdr->ech ;
574 preHdr->ech = icLast;
581 /*-----------------------------------------------------------------*/
582 /* addressTaken - returns true if the symbol is found in the addrof*/
583 /*-----------------------------------------------------------------*/
584 int addressTaken (set *sset ,operand *sym)
590 for (loop = sset; loop ; loop = loop->next) {
592 loop2 = ebp->addrOf ;
594 if (isOperandEqual((operand *)loop2->item,sym))
604 /*-----------------------------------------------------------------*/
605 /* findInduction :- returns 1 & the item if the induction is found */
606 /*-----------------------------------------------------------------*/
607 DEFSETFUNC(findInduction)
609 induction *ip = item;
610 V_ARG(operand *,sym);
611 V_ARG(induction **,ipp);
613 if (isOperandEqual(ip->sym,sym)) {
621 /*-----------------------------------------------------------------*/
622 /* findDefInRegion - finds the definition within the region */
623 /*-----------------------------------------------------------------*/
624 iCode *findDefInRegion (set *regBlocks, operand *defOp, eBBlock **owner)
628 /* for all blocks in the region */
629 for (lBlock = setFirstItem(regBlocks); lBlock ;
630 lBlock = setNextItem(regBlocks)) {
632 /* if a definition for this exists */
633 if (bitVectBitsInCommon(lBlock->defSet,OP_DEFS(defOp))) {
636 /* go thru the instruction chain to find it */
637 for (ic = lBlock->sch ; ic ; ic = ic->next )
638 if (bitVectBitValue (OP_DEFS(defOp),ic->key)) {
649 /*-----------------------------------------------------------------*/
650 /* basicInduction - finds the basic induction variables in a loop */
651 /*-----------------------------------------------------------------*/
652 set *basicInduction (region *loopReg , eBBlock **ebbs, int count)
655 set *indVars = NULL ;
657 /* i.e. all assignments of the form a := a +/- const*/
658 /* for all blocks within the loop do */
659 for ( lBlock = setFirstItem(loopReg->regBlocks); lBlock ;
660 lBlock = setNextItem(loopReg->regBlocks)) {
664 /* for all instructions in the blocks do */
665 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
668 unsigned long litValue ;
671 eBBlock *owner = NULL;
674 /* look for assignments of the form */
675 /* symbolVar := iTempNN */
679 if (!IS_TRUE_SYMOP(IC_RESULT(ic)) &&
680 !OP_SYMBOL(IC_RESULT(ic))->isreqv)
683 if (isOperandGlobal(IC_RESULT(ic)))
686 if (!IS_ITEMP(IC_RIGHT(ic)))
689 /* if it has multiple assignments within the loop then skip */
690 if (assignmentsToSym (loopReg->regBlocks,IC_RESULT(ic)) > 1 )
693 /* if the address of this was taken inside the loop then continue */
694 if (addressTaken (loopReg->regBlocks,IC_RESULT(ic)))
697 /* find the definition for the result in the block */
698 if (! (dic = findDefInRegion (setFromSet(loopReg->regBlocks),
699 IC_RIGHT(ic),&owner)))
702 /* if not +/- continue */
703 if (dic->op != '+' && dic->op != '-')
706 /* make sure definition is of the form a +/- c */
707 if (!IS_OP_LITERAL(IC_LEFT(dic)) && !IS_OP_LITERAL(IC_RIGHT(dic)))
710 aSym = (IS_OP_LITERAL(IC_RIGHT(dic)) ?
711 (litValue = operandLitValue(IC_RIGHT(dic)),IC_LEFT(dic)) :
712 (litValue = operandLitValue(IC_LEFT(dic)),IC_RIGHT(dic)));
714 if (!isOperandEqual(IC_RESULT(ic),aSym) &&
715 !isOperandEqual(IC_RIGHT(ic),aSym)) {
717 /* find the definition for this and check */
718 if (!(ddic = findDefInRegion (setFromSet(loopReg->regBlocks),
725 if (!isOperandEqual(IC_RESULT(ddic),aSym) ||
726 !isOperandEqual(IC_RIGHT(ddic),IC_RESULT(ic)))
730 /* if the right hand side has more than one usage then
731 don't make it an induction (will have to think some more) */
732 if (bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) > 1)
735 /* if the definition is volatile then it cannot be
736 an induction object */
737 if (isOperandVolatile(IC_RIGHT(ic),FALSE) ||
738 isOperandVolatile(IC_RESULT(ic),FALSE))
741 /* whew !! that was a lot of work to find the definition */
742 /* create an induction object */
743 indIc = newiCode('=',NULL,IC_RESULT(ic));
744 indIc->lineno = ic->lineno;
745 IC_RESULT(indIc) = operandFromOperand(IC_RIGHT(ic));
746 IC_RESULT(indIc)->isaddr = 0;
747 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
748 ip = newInduction (IC_RIGHT(ic),dic->op,litValue,indIc,NULL);
750 /* replace the inducted variable by the iTemp */
751 replaceSymBySym (loopReg->regBlocks,IC_RESULT(ic),IC_RIGHT(ic));
753 /* if it has only one exit then remove it from here
754 and put it in the exit block */
755 nexits = elementsInSet (loopReg->exits);
757 eBBlock *exit = setFirstItem(loopReg->exits);
759 /* if it is the same block then there is no
760 need to move it about */
761 if ( exit != lBlock) {
762 iCode *saveic = ic->prev;
764 remiCodeFromeBBlock(lBlock,ic);
765 /* clear the definition */
766 bitVectUnSetBit(lBlock->defSet,ic->key);
767 /* add it to the exit */
768 addiCodeToeBBlock(exit,ic,NULL);
769 /* set the definition bit */
770 exit->defSet = bitVectSetBit(exit->defSet,ic->key);
775 /* if the number of exits is greater than one then
776 we use another trick ; we will create an intersection
777 of succesors of the exits, then take those that are not
778 part of the loop and have dfNumber greater loop entry
779 and insert a new definition in them */
782 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits,ebbs);
784 /* loopSuccs now contains intersection
785 of all the loops successors */
788 for (i = 0 ; i < loopSuccs->size; i++) {
789 if (bitVectBitValue(loopSuccs,i)) {
791 eBBlock *eblock = ebbs[i];
793 /* if the successor does not belong to the loop
794 and will be executed after the loop : then
795 add a definition to the block */
796 if ( !isinSet(loopReg->regBlocks,eblock) &&
797 eblock->dfnum > loopReg->entry->dfnum) {
798 /* create the definition */
799 iCode *newic = newiCode('=',NULL,
800 operandFromOperand(IC_RIGHT(ic)));
801 IC_RESULT(newic) = operandFromOperand(IC_RESULT(ic));
802 OP_DEFS(IC_RESULT(newic)) =
803 bitVectSetBit(OP_DEFS(IC_RESULT(newic)),newic->key);
804 OP_USES(IC_RIGHT(newic)) =
805 bitVectSetBit(OP_USES(IC_RIGHT(newic)),newic->key);
807 if (eblock->sch && eblock->sch->op == LABEL)
808 addiCodeToeBBlock(eblock,newic,eblock->sch->next);
810 addiCodeToeBBlock(eblock,newic,eblock->sch);
811 /* set the definition bit */
812 eblock->defSet = bitVectSetBit(eblock->defSet,ic->key);
819 addSet (&indVars,ip);
822 } /* end of all blocks for basic induction variables */
827 /*-----------------------------------------------------------------*/
828 /* loopInduction - remove induction variables from a loop */
829 /*-----------------------------------------------------------------*/
830 int loopInduction( region *loopReg, eBBlock **ebbs, int count)
833 eBBlock *lBlock, *lastBlock = NULL;
834 set *indVars = NULL ;
837 if (loopReg->entry->preHeader == NULL)
840 /* we first determine the basic Induction variables */
841 basicInd = setFromSet(indVars = basicInduction(loopReg, ebbs,count));
843 /* find other induction variables : by other we mean definitions of */
844 /* the form x := y (* | / ) <constant> .. we will move this one to */
845 /* beginning of the loop and reduce strength i.e. replace with +/- */
846 /* these expensive expressions: OH! and y must be induction too */
847 for ( lBlock = setFirstItem(loopReg->regBlocks), lastBlock = lBlock;
849 lBlock = setNextItem(loopReg->regBlocks)) {
854 /* last block is the one with the highest block
856 if (lastBlock->bbnum < lBlock->bbnum )
859 for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
861 unsigned long litVal ;
864 /* consider only * & / */
865 if (ic->op != '*' && ic->op != '/')
868 /* if the result has more definitions then */
869 if (assignmentsToSym(loopReg->regBlocks,IC_RESULT(ic)) > 1)
872 /* check if the operands are what we want */
873 /* i.e. one of them an symbol the other a literal */
874 if (! ( (IS_SYMOP(IC_LEFT(ic)) && IS_OP_LITERAL(IC_RIGHT(ic))) ||
875 (IS_OP_LITERAL(IC_LEFT(ic)) && IS_SYMOP(IC_RIGHT(ic))) ))
878 aSym = (IS_SYMOP(IC_LEFT(ic)) ?
879 (lr = 1, litVal = operandLitValue(IC_RIGHT(ic)), IC_LEFT(ic) ) :
880 (litVal= operandLitValue(IC_LEFT(ic)), IC_RIGHT(ic) ) ) ;
883 /* check if this is an induction variable */
884 if (! applyToSetFTrue (basicInd,findInduction,aSym,&ip))
887 /* if this is a division then the remainder should be zero
888 for it to be inducted */
889 if (ic->op == '/' && (ip->cval % litVal))
892 /* create the iCode to be placed in the loop header */
893 /* and create the induction object */
895 /* create an instruction */
896 /* this will be put on the loop header */
897 indIc = newiCode(ic->op,
898 operandFromOperand(aSym),
899 operandFromLit(litVal));
900 indIc->lineno = ic->lineno;
901 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
902 OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
904 /* keep track of the inductions */
905 litVal = (ic->op == '*' ? (litVal * ip->cval) :
906 (ip->cval / litVal));
909 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
911 /* now change this instruction */
914 IC_LEFT(ic) = operandFromOperand(IC_RESULT(ic));
915 IC_RIGHT(ic) = operandFromLit(litVal);
917 IC_RIGHT(ic) = operandFromOperand(IC_RESULT(ic));
918 IC_LEFT(ic) = operandFromLit(litVal);
921 /* we need somemore initialisation code */
922 /* we subtract the litVal from itself if increment */
923 if ( ic->op == '+' ) {
924 indIc = newiCode('-',
925 operandFromOperand(IC_RESULT(ic)),
926 operandFromLit(litVal));
927 indIc->lineno = ic->lineno;
928 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
931 newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
936 /* if we have some induction variables then */
938 eBBlock *preHdr = loopReg->entry->preHeader ;
939 iCode *icFirst = NULL , *icLast = NULL ;
941 bitVect *indVect = NULL;
943 /* create an iCode chain from it */
944 for (ip = setFirstItem(indVars);
946 ip = setNextItem(indVars)) {
948 indVect = bitVectSetBit(indVect,ip->ic->key);
949 ip->ic->lineno = preHdr->ech->lineno;
953 icLast->next = ip->ic;
954 ip->ic->prev = icLast;
961 /* add the instruction chain to the end of the */
962 /* preheader for this loop */
963 preHdr->ech->next = icFirst ;
964 icFirst->prev = preHdr->ech ;
965 preHdr->ech = icLast;
968 /* add the induction variable vector to the last
970 lastBlock->isLastInLoop = 1;
971 lastBlock->linds = indVect;
974 setToNull ((void **)&indVars);
978 /*-----------------------------------------------------------------*/
979 /* mergeRegions - will merge region with same entry point */
980 /*-----------------------------------------------------------------*/
981 DEFSETFUNC(mergeRegions)
983 region *theLoop = item;
984 V_ARG(set*,allRegion) ;
987 /* if this has already been merged then do nothing */
991 /* go thru all the region and check if any of them have the */
992 /* entryPoint as the Loop */
993 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
998 if (lp->entry == theLoop->entry) {
999 theLoop->regBlocks = unionSets (theLoop->regBlocks,
1000 lp->regBlocks,THROW_BOTH);
1008 /*-----------------------------------------------------------------*/
1009 /* ifMerged - return 1 if the merge flag is 1 */
1010 /*-----------------------------------------------------------------*/
1011 DEFSETFUNC(ifMerged)
1018 /*-----------------------------------------------------------------*/
1019 /* mergeInnerLoops - will merge into body when entry is present */
1020 /*-----------------------------------------------------------------*/
1021 DEFSETFUNC(mergeInnerLoops)
1023 region *theLoop = item;
1024 V_ARG(set *,allRegion);
1025 V_ARG(int *,maxDepth);
1028 /* check if the entry point is present in the body of any */
1029 /* loop then put the body of this loop into the outer loop*/
1030 for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
1032 if ( lp == theLoop )
1035 if (isinSet(lp->regBlocks, theLoop->entry)) {
1036 lp->containsLoops += theLoop->containsLoops + 1 ;
1037 if ( lp->containsLoops > (*maxDepth))
1038 *maxDepth = lp->containsLoops;
1040 lp->regBlocks = unionSets (lp->regBlocks,
1041 theLoop->regBlocks,THROW_DEST);
1049 /*-----------------------------------------------------------------*/
1050 /* createLoopRegions - will detect and create a set of natural loops */
1051 /*-----------------------------------------------------------------*/
1052 hTab *createLoopRegions (eBBlock **ebbs , int count )
1054 set *allRegion = NULL; /* set of all loops */
1055 hTab *orderedLoops = NULL ;
1060 /* get all the back edges in the graph */
1061 if (! applyToSet(graphEdges,backEdges,&bEdges))
1062 return 0 ; /* found no loops */
1064 /* for each of these back edges get the blocks that */
1065 /* constitute the loops */
1066 applyToSet(bEdges,createLoop,&allRegion);
1068 /* now we will create regions from these loops */
1069 /* loops with the same entry points are considered to be the */
1070 /* same loop & they are merged. If the entry point of a loop */
1071 /* is found in the body of another loop then , all the blocks*/
1072 /* in that loop are added to the loops containing the header */
1073 applyToSet(allRegion, mergeRegions , allRegion);
1075 /* delete those already merged */
1076 deleteItemIf (&allRegion, ifMerged);
1078 applyToSet(allRegion, mergeInnerLoops, allRegion, &maxDepth);
1080 /* now create all the exits .. also */
1081 /* create an ordered set of loops */
1082 /* i.e. we process loops in the inner to outer order */
1083 for (lp = setFirstItem(allRegion) ; lp ; lp = setNextItem(allRegion)) {
1084 applyToSet (lp->regBlocks,addToExitsMarkDepth,
1085 lp->regBlocks,&lp->exits,
1086 (maxDepth - lp->containsLoops),lp);
1088 hTabAddItem (&orderedLoops,lp->containsLoops,lp);
1091 return orderedLoops ;
1094 /*-----------------------------------------------------------------*/
1095 /* loopOptimizations - identify region & remove invariants & ind */
1096 /*-----------------------------------------------------------------*/
1097 int loopOptimizations (hTab *orderedLoops, eBBlock **ebbs, int count)
1104 /* if no loop optimizations requested */
1105 if (! optimize.loopInvariant &&
1106 ! optimize.loopInduction )
1109 /* now we process the loops inner to outer order */
1110 /* this is essential to maintain data flow information */
1111 /* the other choice is an ugly iteration for the depth */
1112 /* of the loops would hate that */
1113 for ( lp = hTabFirstItem(orderedLoops,&k); lp ;
1114 lp = hTabNextItem(orderedLoops,&k)) {
1116 if (optimize.loopInvariant)
1117 change += loopInvariants(lp, ebbs, count);
1119 if (optimize.loopInduction)
1120 change += loopInduction(lp, ebbs, count);