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