git.gag.com Git - fw/sdcc/blob - src/SDCCloop.c

   1 /*-------------------------------------------------------------------------
   2
   3   SDCCloop.c - source file for loop detection & optimizations
   4
   5              Written By -  Sandeep Dutta . sandeep.dutta@usa.net (1998)
   6
   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
  10    later version.
  11
  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.
  16
  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.
  20
  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 -------------------------------------------------------------------------*/
  25
  26 #include "common.h"
  27 #include "newalloc.h"
  28
  29 DEFSETFUNC(isDefAlive);
  30
  31 STACK_DCL(regionStack,eBBlock *, MAX_NEST_LEVEL * 10);
  32
  33 /*-----------------------------------------------------------------*/
  34 /* newInduction - creates a new induction variable                 */
  35 /*-----------------------------------------------------------------*/
  36 induction *newInduction (operand *sym, unsigned int op,
  37        long constVal, iCode *ic, operand *asym)
  38 {
  39     induction *ip;
  40
  41     ip = Safe_calloc(1,sizeof(induction));
  42
  43     ip->sym = sym;
  44     ip->asym= asym;
  45     ip->op = op;
  46     ip->cval = constVal;
  47     ip->ic = ic;
  48
  49     return ip;
  50 }
  51
  52 /*-----------------------------------------------------------------*/
  53 /* newRegion - allocate & returns a loop structure                 */
  54 /*-----------------------------------------------------------------*/
  55 region *newRegion ()
  56 {
  57     region *lp ;
  58
  59     lp = Safe_calloc(1,sizeof(region));
  60
  61     return lp;
  62 }
  63
  64
  65 /*-----------------------------------------------------------------*/
  66 /* pinduction - prints induction                                   */
  67 /*-----------------------------------------------------------------*/
  68 DEFSETFUNC(pinduction)
  69 {
  70     induction *ip = item;
  71     iCodeTable *icTab;
  72
  73     fprintf(stdout,"\t");
  74     printOperand(ip->sym,stdout);
  75     icTab = getTableEntry(ip->ic->op);
  76     icTab->iCodePrint(stdout,ip->ic,icTab->printName);
  77     fprintf(stdout," %04d\n",(int)ip->cval);
  78     return 0;
  79 }
  80
  81 /*-----------------------------------------------------------------*/
  82 /* pregion - prints loop information                                */
  83 /*-----------------------------------------------------------------*/
  84 DEFSETFUNC(pregion)
  85 {
  86     region *lp = item;
  87
  88     printf("================\n");
  89     printf(" loop with entry -- > "); printEntryLabel(lp->entry,ap);
  90     printf("\n");
  91     printf(" loop body --> "); applyToSet(lp->regBlocks,printEntryLabel);
  92     printf("\n");
  93     printf(" loop exits --> "); applyToSet(lp->exits,printEntryLabel);
  94     printf("\n");
  95     return 0;
  96 }
  97
  98 /*-----------------------------------------------------------------*/
  99 /* backEdges - returns a list of back edges                        */
 100 /*-----------------------------------------------------------------*/
 101 DEFSETFUNC(backEdges)
 102 {
 103     edge *ep = item;
 104     V_ARG(set **,bEdges);
 105
 106     /* if this is a back edge ; to determine this we check */
 107     /* to see if the 'to' is in the dominator list of the  */
 108     /* 'from' if yes then this is a back edge              */
 109     if (bitVectBitValue (ep->from->domVect,ep->to->bbnum)) {
 110   addSetHead (bEdges,ep);
 111   return 1;
 112     }
 113
 114     return 0;
 115 }
 116
 117 /*-----------------------------------------------------------------*/
 118 /* intersectLoopSucc - returns intersection of loop Successors     */
 119 /*-----------------------------------------------------------------*/
 120 static bitVect *intersectLoopSucc ( set *lexits, eBBlock **ebbs)
 121 {
 122     bitVect *succVect = NULL;
 123     eBBlock *exit = setFirstItem(lexits);
 124
 125     if (!exit)
 126   return NULL;
 127
 128     succVect = bitVectCopy(exit->succVect);
 129
 130     for (exit = setNextItem(lexits); exit ;
 131    exit = setNextItem(lexits)) {
 132   succVect = bitVectIntersect(succVect,
 133          exit->succVect);
 134     }
 135
 136     return succVect ;
 137 }
 138
 139
 140 /*-----------------------------------------------------------------*/
 141 /* loopInsert will insert a block into the loop set                */
 142 /*-----------------------------------------------------------------*/
 143 static void loopInsert (set **regionSet, eBBlock *block)
 144 {
 145     if (!isinSet (*regionSet,block)) {
 146   addSetHead (regionSet,block);
 147   STACK_PUSH(regionStack,block);
 148     }
 149 }
 150
 151 /*-----------------------------------------------------------------*/
 152 /* insertIntoLoop - insert item into loop                          */
 153 /*-----------------------------------------------------------------*/
 154 DEFSETFUNC(insertIntoLoop)
 155 {
 156     eBBlock *ebp = item ;
 157     V_ARG(set **,regionSet);
 158
 159     loopInsert (regionSet,ebp);
 160     return 0;
 161 }
 162
 163 /*-----------------------------------------------------------------*/
 164 /* isNotInBlocks - will return 1 if not is blocks                  */
 165 /*-----------------------------------------------------------------*/
 166 DEFSETFUNC(isNotInBlocks)
 167 {
 168     eBBlock *ebp = item;
 169     V_ARG(set *,blocks);
 170
 171     if (! isinSet (blocks,ebp))
 172   return 1;
 173
 174     return 0;
 175 }
 176
 177 /*-----------------------------------------------------------------*/
 178 /* hasIncomingDefs - has definitions coming into the loop. i.e.    */
 179 /* check to see if the preheaders outDefs has any definitions      */
 180 /*-----------------------------------------------------------------*/
 181 int hasIncomingDefs (region *lreg, operand *op)
 182 {
 183     eBBlock *preHdr = lreg->entry->preHeader;
 184
 185     if (preHdr && bitVectBitsInCommon(preHdr->outDefs,OP_DEFS(op)))
 186   return 1;
 187     return 0;
 188 }
 189
 190 /*-----------------------------------------------------------------*/
 191 /* findLoopEndSeq - will return the sequence number of the last    */
 192 /* iCode with the maximum dfNumber in the region                   */
 193 /*-----------------------------------------------------------------*/
 194 int findLoopEndSeq (region *lreg)
 195 {
 196     eBBlock *block;
 197     eBBlock *lblock;
 198
 199     for (block = lblock =setFirstItem(lreg->regBlocks); block;
 200    block = setNextItem(lreg->regBlocks)) {
 201   if (block != lblock && block->lSeq > lblock->lSeq)
 202       lblock = block;
 203     }
 204
 205     return lblock->lSeq;
 206 }
 207
 208 /*-----------------------------------------------------------------*/
 209 /* addToExitsMarkDepth - will add the the exitSet all blocks that  */
 210 /* have exits, will also update the depth field in the blocks      */
 211 /*-----------------------------------------------------------------*/
 212 DEFSETFUNC(addToExitsMarkDepth)
 213 {
 214     eBBlock *ebp = item ;
 215     V_ARG(set *,loopBlocks);
 216     V_ARG(set **,exits);
 217     V_ARG(int, depth);
 218     V_ARG(region *,lr);
 219
 220     /* mark the loop depth of this block */
 221     if (!ebp->depth)
 222   ebp->depth = depth;
 223
 224     /* put the loop region info in the block */
 225     /* NOTE: here we will update only the inner most loop
 226        that it is a part of */
 227     if (!ebp->partOfLoop)
 228   ebp->partOfLoop = lr;
 229
 230     /* if any of the successors go out of the loop then */
 231     /* we add this one to the exits */
 232     if ( applyToSet(ebp->succList,isNotInBlocks,loopBlocks)) {
 233   addSetHead (exits,ebp);
 234   return 1;
 235     }
 236
 237     return 0;
 238 }
 239
 240 /*-----------------------------------------------------------------*/
 241 /* createLoop - will create a set of region                        */
 242 /*-----------------------------------------------------------------*/
 243 DEFSETFUNC(createLoop)
 244 {
 245     edge *ep = item;
 246     V_ARG(set **,allRegion);
 247     region *aloop = newRegion();
 248     eBBlock *block;
 249
 250     /* make sure regionStack is empty */
 251     while (!STACK_EMPTY(regionStack))
 252   STACK_POP(regionStack);
 253
 254     /* add the entryBlock */
 255     addSet (&aloop->regBlocks,ep->to);
 256     loopInsert (&aloop->regBlocks,ep->from);
 257
 258     while (!STACK_EMPTY(regionStack)) {
 259   block = STACK_POP(regionStack);
 260   /* if block != entry */
 261   if (block != ep->to)
 262       applyToSet(block->predList,insertIntoLoop,&aloop->regBlocks);
 263     }
 264
 265     aloop->entry = ep->to ;
 266
 267     /* now add it to the set */
 268     addSetHead (allRegion,aloop);
 269     return 0;
 270 }
 271
 272 /*-----------------------------------------------------------------*/
 273 /* dominatedBy - will return 1 if item is dominated by block       */
 274 /*-----------------------------------------------------------------*/
 275 DEFSETFUNC(dominatedBy)
 276 {
 277     eBBlock *ebp = item;
 278     V_ARG(eBBlock *,block);
 279
 280     return bitVectBitValue (ebp->domVect,block->bbnum);
 281 }
 282
 283 /*-----------------------------------------------------------------*/
 284 /* addDefInExprs - adds an expression into the inexpressions       */
 285 /*-----------------------------------------------------------------*/
 286 DEFSETFUNC(addDefInExprs)
 287 {
 288     eBBlock *ebp = item;
 289     V_ARG(cseDef *,cdp);
 290     V_ARG(eBBlock **,ebbs);
 291     V_ARG(int,count);
 292
 293     addSetHead(&ebp->inExprs,cdp);
 294     cseBBlock (ebp,0,ebbs,count);
 295     return 0;
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* assignmentsToSym - for a set of blocks determine # time assigned*/
 300 /*-----------------------------------------------------------------*/
 301  int assignmentsToSym (set *sset, operand *sym)
 302 {
 303     eBBlock *ebp ;
 304     int assigns = 0;
 305     set *blocks = setFromSet(sset);
 306
 307     for (ebp = setFirstItem(blocks) ; ebp ;
 308    ebp = setNextItem(blocks)) {
 309
 310   /* get all the definitions for this symbol
 311      in this block */
 312   bitVect *defs = bitVectIntersect(ebp->ldefs,OP_DEFS(sym));
 313   assigns += bitVectnBitsOn(defs);
 314   setToNull((void **)&defs);
 315
 316     }
 317
 318     return assigns;
 319 }
 320
 321
 322 /*-----------------------------------------------------------------*/
 323 /* isOperandInvariant - determines if an operand is an invariant   */
 324 /*-----------------------------------------------------------------*/
 325 int isOperandInvariant (operand *op, region *theLoop, set *lInvars)
 326 {
 327     int opin = 0 ;
 328     /* operand is an invariant if it is a                */
 329     /*       a. constants .                              */
 330     /*       b. that have defintions reaching loop entry */
 331     /*       c. that are already defined as invariant    */
 332     /*       d. has no assignments in the loop           */
 333     if (op) {
 334   if (IS_OP_LITERAL(op))
 335       opin = 1 ;
 336   else
 337       if (IS_SYMOP(op) &&
 338     OP_SYMBOL(op)->addrtaken)
 339     opin = 0 ;
 340       else
 341     if (ifDefSymIs(theLoop->entry->inExprs,op))
 342         opin = 1 ;
 343     else
 344         if (ifDefSymIs(lInvars,op))
 345       opin = 1 ;
 346         else
 347       if (IS_SYMOP(op)         &&
 348           ! IS_OP_GLOBAL(op)   &&
 349           ! IS_OP_VOLATILE(op) &&
 350           assignmentsToSym (theLoop->regBlocks,op) == 0 )
 351           opin = 1 ;
 352     } else opin++ ;
 353
 354     return opin ;
 355 }
 356
 357 /*-----------------------------------------------------------------*/
 358 /* pointerAssigned - will return 1 if pointer set found            */
 359 /*-----------------------------------------------------------------*/
 360 DEFSETFUNC(pointerAssigned)
 361 {
 362     eBBlock *ebp = item;
 363     V_ARG(operand *,op);
 364
 365     return ebp->hasFcall || bitVectBitValue(ebp->ptrsSet,op->key);
 366 }
 367
 368 /*-----------------------------------------------------------------*/
 369 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 370 /*-----------------------------------------------------------------*/
 371 DEFSETFUNC(hasNonPtrUse)
 372 {
 373     eBBlock *ebp = item;
 374     V_ARG(operand *,op);
 375     iCode *ic = usedInRemaining(op,ebp->sch);
 376
 377     if (ic && !POINTER_SET(ic) && !POINTER_GET(ic))
 378   return 1;
 379
 380     return 0;
 381
 382 }
 383
 384 /*-----------------------------------------------------------------*/
 385 /* loopInvariants - takes loop invariants out of region            */
 386 /*-----------------------------------------------------------------*/
 387  int loopInvariants( region *theLoop , eBBlock **ebbs, int count)
 388 {
 389     eBBlock *lBlock ;
 390     set *lInvars = NULL ;
 391
 392     int change = 0 ;
 393
 394     /* if the preHeader does not exist then do nothing */
 395     /* or no exits then do nothing ( have to think about this situation */
 396     if (theLoop->entry->preHeader == NULL ||
 397   theLoop->exits == NULL )
 398   return 0;
 399
 400     /* we will do the elimination for those blocks        */
 401     /* in the loop that dominates all exits from the loop */
 402     for (lBlock = setFirstItem(theLoop->regBlocks); lBlock;
 403    lBlock = setNextItem(theLoop->regBlocks)) {
 404
 405   iCode *ic;
 406   int domsAllExits ;
 407   int i ;
 408
 409   /* mark the dominates all exits flag */
 410   domsAllExits = ( applyToSet (theLoop->exits,dominatedBy,lBlock) ==
 411        elementsInSet (theLoop->exits));
 412
 413
 414   /* now we go thru the instructions of this block and */
 415   /* collect those instructions with invariant operands*/
 416   for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
 417
 418       int lin , rin ;
 419       cseDef *ivar ;
 420
 421       if (SKIP_IC(ic) || POINTER_SET(ic) || ic->op == IFX)
 422     continue ;
 423
 424       /* if result is volatile then skip */
 425       if (IC_RESULT(ic) &&
 426     ( isOperandVolatile(IC_RESULT(ic),TRUE) ||
 427       IS_OP_PARM(IC_RESULT(ic))))
 428     continue ;
 429
 430       lin = rin = 0 ;
 431
 432       /* special case */
 433       /* if address of then it is an invariant */
 434       if (ic->op == ADDRESS_OF &&
 435     IS_SYMOP(IC_LEFT(ic)) &&
 436     IS_AGGREGATE(operandType(IC_LEFT(ic))))
 437     lin++;
 438       else
 439     /* check if left operand is an invariant */
 440     if ( (lin = isOperandInvariant (IC_LEFT(ic),theLoop,lInvars)))
 441         /* if this is a pointer get then make sure
 442            that the pointer set does not exist in
 443            any of the blocks */
 444         if (POINTER_GET(ic) &&
 445       ( applyToSet (theLoop->regBlocks,pointerAssigned,IC_LEFT(ic)) ))
 446       lin = 0;
 447
 448       /* do the same for right */
 449       rin = isOperandInvariant (IC_RIGHT(ic),theLoop, lInvars);
 450
 451       /* if this is a POINTER_GET then special case, make sure all
 452          usages within the loop are POINTER_GET any other usage
 453          would mean that this is not an invariant , since the pointer
 454          could then be passed as a parameter */
 455       if (POINTER_GET(ic) &&
 456     applyToSet(theLoop->regBlocks,hasNonPtrUse,IC_LEFT(ic)))
 457     continue ;
 458
 459       /* if both the left & right are invariants : then check that*/
 460       /* this definition exists in the out definition of all the  */
 461       /* blocks, this will ensure that this is not assigned any   */
 462       /* other value in the loop , and not used in this block     */
 463       /* prior to this definition which means only this definition*/
 464       /* is used in this loop                                     */
 465       if (lin && rin && IC_RESULT(ic)) {
 466     eBBlock *sBlock ;
 467     set *lSet = setFromSet(theLoop->regBlocks);
 468
 469     /* if this block does not dominate all exists */
 470     /* make sure this defintion is not used anywhere else */
 471     if (!domsAllExits) {
 472
 473         if (isOperandGlobal(IC_RESULT(ic)))
 474       continue;
 475         /* for successors for all exits */
 476         for ( sBlock = setFirstItem(theLoop->exits); sBlock;
 477         sBlock = setNextItem(theLoop->exits)) {
 478
 479       for(i=0; i < count; ebbs[i++]->visited = 0);
 480       lBlock->visited = 1;
 481       if ( applyToSet (sBlock->succList,isDefAlive,ic))
 482           break ;
 483         }
 484
 485         /* we have found usage */
 486         if (sBlock )
 487       continue ;
 488     }
 489
 490     /* now make sure this is the only definition */
 491     for (sBlock = setFirstItem(lSet); sBlock ;
 492          sBlock = setNextItem (lSet)) {
 493         /* if this is the block make sure the definition */
 494         /* reaches the end of the block */
 495         if (sBlock == lBlock ) {
 496       if (! ifDiCodeIs (sBlock->outExprs,ic))
 497           break;
 498         }
 499         else
 500       if (bitVectBitsInCommon (sBlock->defSet,OP_DEFS(IC_RESULT(ic))))
 501           break;
 502     }
 503
 504     if (sBlock)
 505         continue ; /* another definition present in the block */
 506
 507     /* now check if it exists in the in of this block */
 508     /* if not then it was killed before this instruction */
 509     if (! bitVectBitValue (lBlock->inDefs,ic->key))
 510         continue ;
 511
 512     /* now we know it is a true invariant */
 513     /* remove it from the insts chain & put */
 514     /* in the invariant set                */
 515     OP_SYMBOL(IC_RESULT(ic))->isinvariant = 1;
 516     remiCodeFromeBBlock (lBlock,ic);
 517
 518     /* maintain the data flow */
 519     /* this means removing from definition from the */
 520     /* defset of this block and adding it to the    */
 521     /* inexpressions of all blocks within the loop  */
 522     bitVectUnSetBit (lBlock->defSet,ic->key);
 523     bitVectUnSetBit (lBlock->ldefs,ic->key);
 524     ivar = newCseDef(IC_RESULT(ic),ic);
 525     applyToSet (theLoop->regBlocks, addDefInExprs, ivar,ebbs,count);
 526     addSet(&lInvars,ivar);
 527       }
 528   }
 529     } /* for all loop blocks */
 530
 531     /* if we have some invariants then */
 532     if (lInvars) {
 533   eBBlock *preHdr= theLoop->entry->preHeader ;
 534   iCode *icFirst = NULL , *icLast = NULL ;
 535   cseDef *cdp;
 536
 537   /* create an iCode chain from it */
 538   for (cdp = setFirstItem(lInvars); cdp ; cdp = setNextItem(lInvars)) {
 539
 540       /* maintain data flow .. add it to the */
 541       /* ldefs defSet & outExprs of the preheader  */
 542       preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
 543       preHdr->ldefs = bitVectSetBit (preHdr->ldefs,cdp->diCode->key);
 544       cdp->diCode->lineno = preHdr->ech->lineno;
 545       addSetHead (&preHdr->outExprs,cdp);
 546
 547
 548       if (!icFirst)
 549     icFirst = cdp->diCode;
 550       if (icLast) {
 551     icLast->next = cdp->diCode;
 552     cdp->diCode->prev = icLast;
 553     icLast = cdp->diCode ;
 554       } else
 555     icLast = cdp->diCode;
 556       change++ ;
 557   }
 558
 559   /* add the instruction chain to the end of the
 560      preheader for this loop, preheaders will always
 561      have atleast a label */
 562   preHdr->ech->next = icFirst ;
 563   icFirst->prev = preHdr->ech ;
 564   preHdr->ech = icLast;
 565   icLast->next = NULL;
 566
 567     }
 568     return change ;
 569 }
 570
 571 /*-----------------------------------------------------------------*/
 572 /* addressTaken - returns true if the symbol is found in the addrof*/
 573 /*-----------------------------------------------------------------*/
 574 int addressTaken (set *sset ,operand *sym)
 575 {
 576     set *loop;
 577     eBBlock *ebp ;
 578     set *loop2;
 579
 580     for (loop = sset; loop ; loop = loop->next) {
 581   ebp = loop->item;
 582   loop2 = ebp->addrOf ;
 583   while (loop2) {
 584       if (isOperandEqual((operand *)loop2->item,sym))
 585     return 1;
 586       loop2 = loop2->next;
 587   }
 588     }
 589
 590     return 0;
 591 }
 592
 593
 594 /*-----------------------------------------------------------------*/
 595 /* findInduction :- returns 1 & the item if the induction is found */
 596 /*-----------------------------------------------------------------*/
 597 DEFSETFUNC(findInduction)
 598 {
 599     induction *ip = item;
 600     V_ARG(operand *,sym);
 601     V_ARG(induction **,ipp);
 602
 603     if (isOperandEqual(ip->sym,sym)) {
 604   *ipp = ip;
 605   return 1;
 606     }
 607
 608     return 0;
 609 }
 610
 611 /*-----------------------------------------------------------------*/
 612 /* findDefInRegion - finds the definition within the region        */
 613 /*-----------------------------------------------------------------*/
 614 iCode *findDefInRegion (set *regBlocks, operand *defOp, eBBlock **owner)
 615 {
 616     eBBlock *lBlock ;
 617
 618     /* for all blocks in the region */
 619     for (lBlock = setFirstItem(regBlocks); lBlock ;
 620    lBlock = setNextItem(regBlocks)) {
 621
 622   /* if a definition for this exists */
 623   if (bitVectBitsInCommon(lBlock->defSet,OP_DEFS(defOp))) {
 624       iCode *ic;
 625
 626       /* go thru the instruction chain to find it */
 627       for (ic = lBlock->sch ; ic ; ic = ic->next )
 628     if (bitVectBitValue (OP_DEFS(defOp),ic->key)) {
 629         if (owner)
 630       *owner = lBlock ;
 631         return ic;
 632     }
 633   }
 634     }
 635
 636     return NULL ;
 637 }
 638
 639 /*-----------------------------------------------------------------*/
 640 /* basicInduction - finds the basic induction variables in a loop  */
 641 /*-----------------------------------------------------------------*/
 642 set *basicInduction (region *loopReg , eBBlock **ebbs, int count)
 643 {
 644     eBBlock *lBlock ;
 645     set *indVars = NULL ;
 646
 647     /* i.e. all assignments of the form a := a +/- const*/
 648     /* for all blocks within the loop do */
 649     for ( lBlock = setFirstItem(loopReg->regBlocks); lBlock ;
 650     lBlock = setNextItem(loopReg->regBlocks)) {
 651
 652   iCode *ic, *dic ;
 653
 654   /* for all instructions in the blocks do */
 655   for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
 656
 657       operand *aSym ;
 658       unsigned long litValue ;
 659       induction *ip;
 660       iCode *indIc;
 661       eBBlock *owner = NULL;
 662       int nexits;
 663
 664       /* look for assignments of the form */
 665       /*   symbolVar := iTempNN */
 666       if ( ic->op != '=')
 667     continue ;
 668
 669       if (!IS_TRUE_SYMOP(IC_RESULT(ic)) &&
 670     !OP_SYMBOL(IC_RESULT(ic))->isreqv)
 671     continue ;
 672
 673       if (isOperandGlobal(IC_RESULT(ic)))
 674     continue ;
 675
 676       if (!IS_ITEMP(IC_RIGHT(ic)))
 677     continue ;
 678
 679       /* if it has multiple assignments within the loop then skip */
 680       if (assignmentsToSym (loopReg->regBlocks,IC_RESULT(ic)) > 1 )
 681     continue ;
 682
 683       /* if the address of this was taken inside the loop then continue */
 684       if (addressTaken (loopReg->regBlocks,IC_RESULT(ic)))
 685     continue ;
 686
 687       /* find the definition for the result in the block */
 688       if (! (dic = findDefInRegion (setFromSet(loopReg->regBlocks),
 689             IC_RIGHT(ic),&owner)))
 690     continue ;
 691
 692       /* if not +/- continue */
 693       if (dic->op != '+' && dic->op != '-')
 694     continue ;
 695
 696       /* make sure definition is of the form  a +/- c */
 697       if (!IS_OP_LITERAL(IC_LEFT(dic)) && !IS_OP_LITERAL(IC_RIGHT(dic)))
 698     continue ;
 699
 700       aSym = (IS_OP_LITERAL(IC_RIGHT(dic)) ?
 701         (litValue = operandLitValue(IC_RIGHT(dic)),IC_LEFT(dic)) :
 702         (litValue = operandLitValue(IC_LEFT(dic)),IC_RIGHT(dic)));
 703
 704       if (!isOperandEqual(IC_RESULT(ic),aSym) &&
 705     !isOperandEqual(IC_RIGHT(ic),aSym)) {
 706     iCode *ddic ;
 707     /* find the definition for this and check */
 708     if (!(ddic = findDefInRegion (setFromSet(loopReg->regBlocks),
 709                 aSym,&owner)))
 710         continue ;
 711
 712     if (ddic->op != '=')
 713         continue ;
 714
 715     if (!isOperandEqual(IC_RESULT(ddic),aSym) ||
 716         !isOperandEqual(IC_RIGHT(ddic),IC_RESULT(ic)))
 717         continue ;
 718       }
 719
 720       /* if the right hand side has more than one usage then
 721          don't make it an induction (will have to think some more) */
 722       if (bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) > 1)
 723         continue;
 724
 725       /* if the definition is volatile then it cannot be
 726          an induction object */
 727       if (isOperandVolatile(IC_RIGHT(ic),FALSE) ||
 728     isOperandVolatile(IC_RESULT(ic),FALSE))
 729     continue;
 730
 731       /* whew !! that was a lot of work to find the definition */
 732       /* create an induction object */
 733       indIc = newiCode('=',NULL,IC_RESULT(ic));
 734       indIc->lineno = ic->lineno;
 735       IC_RESULT(indIc) = operandFromOperand(IC_RIGHT(ic));
 736       IC_RESULT(indIc)->isaddr = 0;
 737       OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
 738       ip = newInduction (IC_RIGHT(ic),dic->op,litValue,indIc,NULL);
 739
 740       /* replace the inducted variable by the iTemp */
 741       replaceSymBySym (loopReg->regBlocks,IC_RESULT(ic),IC_RIGHT(ic));
 742
 743       /* if it has only one exit then remove it from here
 744          and put it in the exit block */
 745       nexits = elementsInSet (loopReg->exits);
 746       if (nexits == 1) {
 747     eBBlock *exit = setFirstItem(loopReg->exits);
 748
 749     /* if it is the same block then there is no
 750        need to move it about */
 751     if ( exit != lBlock) {
 752         iCode *saveic = ic->prev;
 753         /* remove it */
 754         remiCodeFromeBBlock(lBlock,ic);
 755         /* clear the definition */
 756         bitVectUnSetBit(lBlock->defSet,ic->key);
 757         /* add it to the exit */
 758         addiCodeToeBBlock(exit,ic,NULL);
 759         /* set the definition bit */
 760         exit->defSet = bitVectSetBit(exit->defSet,ic->key);
 761         ic = saveic ;
 762     }
 763       }
 764
 765       /* if the number of exits is greater than one then
 766          we use another trick ; we will create an intersection
 767          of succesors of the exits, then take those that are not
 768          part of the loop and have dfNumber greater loop entry
 769          and insert a new definition in them */
 770       if ( nexits > 1) {
 771
 772     bitVect *loopSuccs = intersectLoopSucc (loopReg->exits,ebbs);
 773
 774     /* loopSuccs now contains intersection
 775        of all the loops successors */
 776     if (loopSuccs) {
 777         int i;
 778         for (i = 0 ; i < loopSuccs->size; i++) {
 779       if (bitVectBitValue(loopSuccs,i)) {
 780
 781           eBBlock *eblock = ebbs[i];
 782
 783           /* if the successor does not belong to the loop
 784              and will be executed after the loop : then
 785              add a definition to the block */
 786           if ( !isinSet(loopReg->regBlocks,eblock) &&
 787          eblock->dfnum > loopReg->entry->dfnum) {
 788         /* create the definition */
 789         iCode *newic = newiCode('=',NULL,
 790               operandFromOperand(IC_RIGHT(ic)));
 791         IC_RESULT(newic) = operandFromOperand(IC_RESULT(ic));
 792         OP_DEFS(IC_RESULT(newic)) =
 793             bitVectSetBit(OP_DEFS(IC_RESULT(newic)),newic->key);
 794         OP_USES(IC_RIGHT(newic)) =
 795             bitVectSetBit(OP_USES(IC_RIGHT(newic)),newic->key);
 796         /* and add it */
 797         if (eblock->sch && eblock->sch->op == LABEL)
 798             addiCodeToeBBlock(eblock,newic,eblock->sch->next);
 799         else
 800             addiCodeToeBBlock(eblock,newic,eblock->sch);
 801         /* set the definition bit */
 802         eblock->defSet = bitVectSetBit(eblock->defSet,ic->key);
 803           }
 804       }
 805         }
 806     }
 807       }
 808
 809       addSet (&indVars,ip);
 810   }
 811
 812     } /* end of all blocks for basic induction variables */
 813
 814     return indVars;
 815 }
 816
 817 /*-----------------------------------------------------------------*/
 818 /* loopInduction - remove induction variables from a loop          */
 819 /*-----------------------------------------------------------------*/
 820  int loopInduction( region *loopReg, eBBlock **ebbs, int count)
 821 {
 822     int change = 0 ;
 823     eBBlock *lBlock, *lastBlock = NULL;
 824     set *indVars = NULL ;
 825     set *basicInd=NULL ;
 826
 827     if (loopReg->entry->preHeader == NULL)
 828   return 0;
 829
 830     /* we first determine the basic Induction variables */
 831     basicInd = setFromSet(indVars = basicInduction(loopReg, ebbs,count));
 832
 833     /* find other induction variables : by other we mean definitions of */
 834     /* the form x := y (* | / ) <constant> .. we will move  this one to */
 835     /* beginning of the loop and reduce strength i.e. replace with +/-  */
 836     /* these expensive expressions: OH! and y must be induction too     */
 837     for ( lBlock = setFirstItem(loopReg->regBlocks), lastBlock = lBlock;
 838     lBlock && indVars;
 839     lBlock = setNextItem(loopReg->regBlocks)) {
 840
 841   iCode *ic, *indIc;
 842   induction *ip;
 843
 844   /* last block is the one with the highest block
 845      number */
 846   if (lastBlock->bbnum < lBlock->bbnum )
 847       lastBlock = lBlock;
 848
 849   for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
 850       operand *aSym ;
 851       unsigned long litVal ;
 852       int lr = 0;
 853
 854       /* consider only * & / */
 855       if (ic->op != '*' && ic->op != '/')
 856     continue ;
 857
 858       /* if the result has more definitions then */
 859       if (assignmentsToSym(loopReg->regBlocks,IC_RESULT(ic)) > 1)
 860     continue ;
 861
 862       /* check if the operands are what we want */
 863       /* i.e. one of them an symbol the other a literal */
 864       if (! ( (IS_SYMOP(IC_LEFT(ic)) && IS_OP_LITERAL(IC_RIGHT(ic))) ||
 865         (IS_OP_LITERAL(IC_LEFT(ic)) && IS_SYMOP(IC_RIGHT(ic))) ))
 866     continue ;
 867
 868       aSym = (IS_SYMOP(IC_LEFT(ic)) ?
 869         (lr = 1, litVal = operandLitValue(IC_RIGHT(ic)), IC_LEFT(ic) ) :
 870         (litVal= operandLitValue(IC_LEFT(ic)), IC_RIGHT(ic) ) ) ;
 871
 872       ip = NULL ;
 873       /* check if this is an induction variable */
 874       if (! applyToSetFTrue (basicInd,findInduction,aSym,&ip))
 875     continue ;
 876
 877       /* ask port for size not worth if native instruction
 878          exist for multiply & divide */
 879       if (getSize(operandType(IC_LEFT(ic))) <= port->muldiv.native_below ||
 880     getSize(operandType(IC_RIGHT(ic))) <= port->muldiv.native_below)
 881     continue;
 882
 883       /* if this is a division then the remainder should be zero
 884          for it to be inducted */
 885       if (ic->op == '/' && (ip->cval % litVal))
 886     continue ;
 887
 888       /* create the iCode to be placed in the loop header */
 889       /* and create the induction object */
 890
 891       /* create an instruction */
 892       /* this will be put on the loop header */
 893       indIc = newiCode(ic->op,
 894            operandFromOperand(aSym),
 895            operandFromLit(litVal));
 896       indIc->lineno = ic->lineno;
 897       IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
 898       OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
 899
 900       /* keep track of the inductions */
 901       litVal = (ic->op == '*' ? (litVal * ip->cval) :
 902           (ip->cval / litVal));
 903
 904       addSet (&indVars,
 905         newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
 906
 907       /* now change this instruction */
 908       ic->op = ip->op;
 909       if (lr) {
 910     IC_LEFT(ic) = operandFromOperand(IC_RESULT(ic));
 911     IC_RIGHT(ic) = operandFromLit(litVal);
 912       } else {
 913     IC_RIGHT(ic) = operandFromOperand(IC_RESULT(ic));
 914     IC_LEFT(ic) = operandFromLit(litVal);
 915       }
 916
 917       /* we need somemore initialisation code */
 918       /* we subtract the litVal from itself if increment */
 919       if ( ic->op == '+' ) {
 920     indIc = newiCode('-',
 921          operandFromOperand(IC_RESULT(ic)),
 922          operandFromLit(litVal));
 923     indIc->lineno = ic->lineno;
 924     IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
 925
 926     addSet (&indVars,
 927       newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
 928       }
 929   }
 930     }
 931
 932     /* if we have some induction variables then */
 933     if ( indVars ) {
 934   eBBlock *preHdr = loopReg->entry->preHeader ;
 935   iCode *icFirst = NULL , *icLast = NULL ;
 936   induction *ip;
 937   bitVect *indVect = NULL;
 938
 939   /* create an iCode chain from it */
 940   for (ip = setFirstItem(indVars);
 941        ip ;
 942        ip = setNextItem(indVars)) {
 943
 944       indVect = bitVectSetBit(indVect,ip->ic->key);
 945       ip->ic->lineno = preHdr->ech->lineno;
 946       if (!icFirst)
 947     icFirst = ip->ic;
 948       if (icLast) {
 949     icLast->next = ip->ic;
 950     ip->ic->prev = icLast;
 951     icLast = ip->ic ;
 952       } else
 953     icLast = ip->ic;
 954       change++ ;
 955   }
 956
 957   /* add the instruction chain to the end of the */
 958   /* preheader for this loop                     */
 959   preHdr->ech->next = icFirst ;
 960   icFirst->prev = preHdr->ech ;
 961   preHdr->ech = icLast;
 962   icLast->next = NULL;
 963
 964   /* add the induction variable vector to the last
 965      block in the loop */
 966   lastBlock->isLastInLoop = 1;
 967   lastBlock->linds = indVect;
 968     }
 969
 970     setToNull ((void **)&indVars);
 971     return change ;
 972 }
 973
 974 /*-----------------------------------------------------------------*/
 975 /* mergeRegions - will merge region with same entry point           */
 976 /*-----------------------------------------------------------------*/
 977 DEFSETFUNC(mergeRegions)
 978 {
 979     region *theLoop = item;
 980     V_ARG(set*,allRegion) ;
 981     region *lp ;
 982
 983     /* if this has already been merged then do nothing */
 984     if (theLoop->merged)
 985   return 0;
 986
 987     /* go thru all the region and check if any of them have the */
 988     /* entryPoint as the Loop                                  */
 989     for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
 990
 991   if (lp == theLoop)
 992       continue ;
 993
 994   if (lp->entry == theLoop->entry) {
 995       theLoop->regBlocks = unionSets (theLoop->regBlocks,
 996                lp->regBlocks,THROW_BOTH);
 997       lp->merged = 1;
 998   }
 999     }
1000
1001     return 1;
1002 }
1003
1004 /*-----------------------------------------------------------------*/
1005 /* ifMerged - return 1 if the merge flag is 1                      */
1006 /*-----------------------------------------------------------------*/
1007 DEFSETFUNC(ifMerged)
1008 {
1009     region *lp = item;
1010
1011     return lp->merged ;
1012 }
1013
1014 /*-----------------------------------------------------------------*/
1015 /* mergeInnerLoops - will merge into body when entry is present    */
1016 /*-----------------------------------------------------------------*/
1017 DEFSETFUNC(mergeInnerLoops)
1018 {
1019     region *theLoop = item;
1020     V_ARG(set *,allRegion);
1021     V_ARG(int *,maxDepth);
1022     region *lp;
1023
1024     /* check if the entry point is present in the body of any */
1025     /* loop then put the body of this loop into the outer loop*/
1026     for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
1027
1028   if ( lp == theLoop )
1029       continue ;
1030
1031   if (isinSet(lp->regBlocks, theLoop->entry)) {
1032       lp->containsLoops += theLoop->containsLoops + 1 ;
1033       if ( lp->containsLoops > (*maxDepth))
1034     *maxDepth = lp->containsLoops;
1035
1036       lp->regBlocks = unionSets (lp->regBlocks,
1037           theLoop->regBlocks,THROW_DEST);
1038   }
1039     }
1040
1041     return 1;
1042 }
1043
1044
1045 /*-----------------------------------------------------------------*/
1046 /* createLoopRegions - will detect and create a set of natural loops */
1047 /*-----------------------------------------------------------------*/
1048 hTab *createLoopRegions (eBBlock **ebbs , int count  )
1049 {
1050     set *allRegion  = NULL; /* set of all loops */
1051     hTab *orderedLoops = NULL ;
1052     set *bEdges = NULL;
1053     int maxDepth = 0;
1054     region *lp;
1055
1056     /* get all the back edges in the graph */
1057     if (! applyToSet(graphEdges,backEdges,&bEdges))
1058   return 0 ; /* found no loops */
1059
1060     /* for each of these back edges get the blocks that */
1061     /* constitute the loops                             */
1062     applyToSet(bEdges,createLoop,&allRegion);
1063
1064     /* now we will create regions from these loops               */
1065     /* loops with the same entry points are considered to be the */
1066     /* same loop & they are merged. If the entry point of a loop */
1067     /* is found in the body of another loop then , all the blocks*/
1068     /* in that loop are added to the loops containing the header */
1069     applyToSet(allRegion, mergeRegions , allRegion);
1070
1071     /* delete those already merged */
1072     deleteItemIf (&allRegion, ifMerged);
1073
1074     applyToSet(allRegion, mergeInnerLoops, allRegion, &maxDepth);
1075     maxDepth++;
1076     /* now create all the exits .. also */
1077     /* create an ordered set of loops   */
1078     /* i.e. we process loops in the inner to outer order */
1079     for (lp = setFirstItem(allRegion) ; lp ; lp = setNextItem(allRegion)) {
1080   applyToSet (lp->regBlocks,addToExitsMarkDepth,
1081         lp->regBlocks,&lp->exits,
1082         (maxDepth - lp->containsLoops),lp);
1083
1084   hTabAddItem (&orderedLoops,lp->containsLoops,lp);
1085
1086     }
1087     return orderedLoops ;
1088 }
1089
1090 /*-----------------------------------------------------------------*/
1091 /* loopOptimizations - identify region & remove invariants & ind   */
1092 /*-----------------------------------------------------------------*/
1093 int loopOptimizations (hTab *orderedLoops, eBBlock **ebbs, int count)
1094 {
1095     region *lp ;
1096     int change = 0 ;
1097     int k;
1098
1099
1100     /* if no loop optimizations requested */
1101     if (! optimize.loopInvariant &&
1102   ! optimize.loopInduction )
1103   return 0;
1104
1105     /* now we process the loops inner to outer order */
1106     /* this is essential to maintain data flow information */
1107     /* the other choice is an ugly iteration for the depth */
1108     /* of the loops would hate that */
1109     for ( lp = hTabFirstItem(orderedLoops,&k); lp ;
1110     lp = hTabNextItem(orderedLoops,&k)) {
1111
1112   if (optimize.loopInvariant)
1113       change += loopInvariants(lp, ebbs, count);
1114
1115   if (optimize.loopInduction)
1116       change += loopInduction(lp, ebbs, count);
1117     }
1118
1119     return change;
1120 }