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             /* defSet & outExprs of the preheader  */
 541             preHdr->defSet = bitVectSetBit (preHdr->defSet,cdp->diCode->key);
 542             cdp->diCode->lineno = preHdr->ech->lineno;
 543             addSetHead (&preHdr->outExprs,cdp);
 544
 545
 546             if (!icFirst)
 547                 icFirst = cdp->diCode;
 548             if (icLast) {
 549                 icLast->next = cdp->diCode;
 550                 cdp->diCode->prev = icLast;
 551                 icLast = cdp->diCode ;
 552             } else
 553                 icLast = cdp->diCode;
 554             change++ ;
 555         }
 556
 557         /* add the instruction chain to the end of the
 558            preheader for this loop, preheaders will always
 559            have atleast a label */
 560         preHdr->ech->next = icFirst ;
 561         icFirst->prev = preHdr->ech ;
 562         preHdr->ech = icLast;
 563         icLast->next = NULL;
 564
 565     }
 566     return change ;
 567 }
 568
 569 /*-----------------------------------------------------------------*/
 570 /* addressTaken - returns true if the symbol is found in the addrof*/
 571 /*-----------------------------------------------------------------*/
 572 int addressTaken (set *sset ,operand *sym)
 573 {
 574     set *loop;
 575     eBBlock *ebp ;
 576     set *loop2;
 577
 578     for (loop = sset; loop ; loop = loop->next) {
 579         ebp = loop->item;
 580         loop2 = ebp->addrOf ;
 581         while (loop2) {
 582             if (isOperandEqual((operand *)loop2->item,sym))
 583                 return 1;
 584             loop2 = loop2->next;
 585         }
 586     }
 587
 588     return 0;
 589 }
 590
 591
 592 /*-----------------------------------------------------------------*/
 593 /* findInduction :- returns 1 & the item if the induction is found */
 594 /*-----------------------------------------------------------------*/
 595 DEFSETFUNC(findInduction)
 596 {
 597     induction *ip = item;
 598     V_ARG(operand *,sym);
 599     V_ARG(induction **,ipp);
 600
 601     if (isOperandEqual(ip->sym,sym)) {
 602         *ipp = ip;
 603         return 1;
 604     }
 605
 606     return 0;
 607 }
 608
 609 /*-----------------------------------------------------------------*/
 610 /* findDefInRegion - finds the definition within the region        */
 611 /*-----------------------------------------------------------------*/
 612 iCode *findDefInRegion (set *regBlocks, operand *defOp, eBBlock **owner)
 613 {
 614     eBBlock *lBlock ;
 615
 616     /* for all blocks in the region */
 617     for (lBlock = setFirstItem(regBlocks); lBlock ;
 618          lBlock = setNextItem(regBlocks)) {
 619
 620         /* if a definition for this exists */
 621         if (bitVectBitsInCommon(lBlock->defSet,OP_DEFS(defOp))) {
 622             iCode *ic;
 623
 624             /* go thru the instruction chain to find it */
 625             for (ic = lBlock->sch ; ic ; ic = ic->next )
 626                 if (bitVectBitValue (OP_DEFS(defOp),ic->key)) {
 627                     if (owner)
 628                         *owner = lBlock ;
 629                     return ic;
 630                 }
 631         }
 632     }
 633
 634     return NULL ;
 635 }
 636
 637 /*-----------------------------------------------------------------*/
 638 /* basicInduction - finds the basic induction variables in a loop  */
 639 /*-----------------------------------------------------------------*/
 640 set *basicInduction (region *loopReg , eBBlock **ebbs, int count)
 641 {
 642     eBBlock *lBlock ;
 643     set *indVars = NULL ;
 644
 645     /* i.e. all assignments of the form a := a +/- const*/
 646     /* for all blocks within the loop do */
 647     for ( lBlock = setFirstItem(loopReg->regBlocks); lBlock ;
 648           lBlock = setNextItem(loopReg->regBlocks)) {
 649
 650         iCode *ic, *dic ;
 651
 652         /* for all instructions in the blocks do */
 653         for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
 654
 655             operand *aSym ;
 656             unsigned long litValue ;
 657             induction *ip;
 658             iCode *indIc;
 659             eBBlock *owner = NULL;
 660             int nexits;
 661
 662             /* look for assignments of the form */
 663             /*   symbolVar := iTempNN */
 664             if ( ic->op != '=')
 665                 continue ;
 666
 667             if (!IS_TRUE_SYMOP(IC_RESULT(ic)) &&
 668                 !OP_SYMBOL(IC_RESULT(ic))->isreqv)
 669                 continue ;
 670
 671             if (isOperandGlobal(IC_RESULT(ic)))
 672                 continue ;
 673
 674             if (!IS_ITEMP(IC_RIGHT(ic)))
 675                 continue ;
 676
 677             /* if it has multiple assignments within the loop then skip */
 678             if (assignmentsToSym (loopReg->regBlocks,IC_RESULT(ic)) > 1 )
 679                 continue ;
 680
 681             /* if the address of this was taken inside the loop then continue */
 682             if (addressTaken (loopReg->regBlocks,IC_RESULT(ic)))
 683                 continue ;
 684
 685             /* find the definition for the result in the block */
 686             if (! (dic = findDefInRegion (setFromSet(loopReg->regBlocks),
 687                                           IC_RIGHT(ic),&owner)))
 688                 continue ;
 689
 690             /* if not +/- continue */
 691             if (dic->op != '+' && dic->op != '-')
 692                 continue ;
 693
 694             /* make sure definition is of the form  a +/- c */
 695             if (!IS_OP_LITERAL(IC_LEFT(dic)) && !IS_OP_LITERAL(IC_RIGHT(dic)))
 696                 continue ;
 697
 698             aSym = (IS_OP_LITERAL(IC_RIGHT(dic)) ?
 699                     (litValue = operandLitValue(IC_RIGHT(dic)),IC_LEFT(dic)) :
 700                     (litValue = operandLitValue(IC_LEFT(dic)),IC_RIGHT(dic)));
 701
 702             if (!isOperandEqual(IC_RESULT(ic),aSym) &&
 703                 !isOperandEqual(IC_RIGHT(ic),aSym)) {
 704                 iCode *ddic ;
 705                 /* find the definition for this and check */
 706                 if (!(ddic = findDefInRegion (setFromSet(loopReg->regBlocks),
 707                                               aSym,&owner)))
 708                     continue ;
 709
 710                 if (ddic->op != '=')
 711                     continue ;
 712
 713                 if (!isOperandEqual(IC_RESULT(ddic),aSym) ||
 714                     !isOperandEqual(IC_RIGHT(ddic),IC_RESULT(ic)))
 715                     continue ;
 716             }
 717
 718             /* if the right hand side has more than one usage then
 719                don't make it an induction (will have to think some more) */
 720             if (bitVectnBitsOn(OP_USES(IC_RIGHT(ic))) > 1)
 721                     continue;
 722
 723             /* if the definition is volatile then it cannot be
 724                an induction object */
 725             if (isOperandVolatile(IC_RIGHT(ic),FALSE) ||
 726                 isOperandVolatile(IC_RESULT(ic),FALSE))
 727                 continue;
 728
 729             /* whew !! that was a lot of work to find the definition */
 730             /* create an induction object */
 731             indIc = newiCode('=',NULL,IC_RESULT(ic));
 732             indIc->lineno = ic->lineno;
 733             IC_RESULT(indIc) = operandFromOperand(IC_RIGHT(ic));
 734             IC_RESULT(indIc)->isaddr = 0;
 735             OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
 736             ip = newInduction (IC_RIGHT(ic),dic->op,litValue,indIc,NULL);
 737
 738             /* replace the inducted variable by the iTemp */
 739             replaceSymBySym (loopReg->regBlocks,IC_RESULT(ic),IC_RIGHT(ic));
 740
 741             /* if it has only one exit then remove it from here
 742                and put it in the exit block */
 743             nexits = elementsInSet (loopReg->exits);
 744             if (nexits == 1) {
 745                 eBBlock *exit = setFirstItem(loopReg->exits);
 746
 747                 /* if it is the same block then there is no
 748                    need to move it about */
 749                 if ( exit != lBlock) {
 750                     iCode *saveic = ic->prev;
 751                     /* remove it */
 752                     remiCodeFromeBBlock(lBlock,ic);
 753                     /* clear the definition */
 754                     bitVectUnSetBit(lBlock->defSet,ic->key);
 755                     /* add it to the exit */
 756                     addiCodeToeBBlock(exit,ic,NULL);
 757                     /* set the definition bit */
 758                     exit->defSet = bitVectSetBit(exit->defSet,ic->key);
 759                     ic = saveic ;
 760                 }
 761             }
 762
 763             /* if the number of exits is greater than one then
 764                we use another trick ; we will create an intersection
 765                of succesors of the exits, then take those that are not
 766                part of the loop and have dfNumber greater loop entry
 767                and insert a new definition in them */
 768             if ( nexits > 1) {
 769
 770                 bitVect *loopSuccs = intersectLoopSucc (loopReg->exits,ebbs);
 771
 772                 /* loopSuccs now contains intersection
 773                    of all the loops successors */
 774                 if (loopSuccs) {
 775                     int i;
 776                     for (i = 0 ; i < loopSuccs->size; i++) {
 777                         if (bitVectBitValue(loopSuccs,i)) {
 778
 779                             eBBlock *eblock = ebbs[i];
 780
 781                             /* if the successor does not belong to the loop
 782                                and will be executed after the loop : then
 783                                add a definition to the block */
 784                             if ( !isinSet(loopReg->regBlocks,eblock) &&
 785                                  eblock->dfnum > loopReg->entry->dfnum) {
 786                                 /* create the definition */
 787                                 iCode *newic = newiCode('=',NULL,
 788                                                         operandFromOperand(IC_RIGHT(ic)));
 789                                 IC_RESULT(newic) = operandFromOperand(IC_RESULT(ic));
 790                                 OP_DEFS(IC_RESULT(newic)) =
 791                                     bitVectSetBit(OP_DEFS(IC_RESULT(newic)),newic->key);
 792                                 OP_USES(IC_RIGHT(newic)) =
 793                                     bitVectSetBit(OP_USES(IC_RIGHT(newic)),newic->key);
 794                                 /* and add it */
 795                                 if (eblock->sch && eblock->sch->op == LABEL)
 796                                     addiCodeToeBBlock(eblock,newic,eblock->sch->next);
 797                                 else
 798                                     addiCodeToeBBlock(eblock,newic,eblock->sch);
 799                                 /* set the definition bit */
 800                                 eblock->defSet = bitVectSetBit(eblock->defSet,ic->key);
 801                             }
 802                         }
 803                     }
 804                 }
 805             }
 806
 807             addSet (&indVars,ip);
 808         }
 809
 810     } /* end of all blocks for basic induction variables */
 811
 812     return indVars;
 813 }
 814
 815 /*-----------------------------------------------------------------*/
 816 /* loopInduction - remove induction variables from a loop          */
 817 /*-----------------------------------------------------------------*/
 818  int loopInduction( region *loopReg, eBBlock **ebbs, int count)
 819 {
 820     int change = 0 ;
 821     eBBlock *lBlock, *lastBlock = NULL;
 822     set *indVars = NULL ;
 823     set *basicInd=NULL ;
 824
 825     if (loopReg->entry->preHeader == NULL)
 826         return 0;
 827
 828     /* we first determine the basic Induction variables */
 829     basicInd = setFromSet(indVars = basicInduction(loopReg, ebbs,count));
 830
 831     /* find other induction variables : by other we mean definitions of */
 832     /* the form x := y (* | / ) <constant> .. we will move  this one to */
 833     /* beginning of the loop and reduce strength i.e. replace with +/-  */
 834     /* these expensive expressions: OH! and y must be induction too     */
 835     for ( lBlock = setFirstItem(loopReg->regBlocks), lastBlock = lBlock;
 836           lBlock && indVars;
 837           lBlock = setNextItem(loopReg->regBlocks)) {
 838
 839         iCode *ic, *indIc;
 840         induction *ip;
 841
 842         /* last block is the one with the highest block
 843            number */
 844         if (lastBlock->bbnum < lBlock->bbnum )
 845             lastBlock = lBlock;
 846
 847         for ( ic = lBlock->sch ; ic ; ic = ic->next ) {
 848             operand *aSym ;
 849             unsigned long litVal ;
 850             int lr = 0;
 851
 852             /* consider only * & / */
 853             if (ic->op != '*' && ic->op != '/')
 854                 continue ;
 855
 856             /* if the result has more definitions then */
 857             if (assignmentsToSym(loopReg->regBlocks,IC_RESULT(ic)) > 1)
 858                 continue ;
 859
 860             /* check if the operands are what we want */
 861             /* i.e. one of them an symbol the other a literal */
 862             if (! ( (IS_SYMOP(IC_LEFT(ic)) && IS_OP_LITERAL(IC_RIGHT(ic))) ||
 863                     (IS_OP_LITERAL(IC_LEFT(ic)) && IS_SYMOP(IC_RIGHT(ic))) ))
 864                 continue ;
 865
 866             aSym = (IS_SYMOP(IC_LEFT(ic)) ?
 867                     (lr = 1, litVal = operandLitValue(IC_RIGHT(ic)), IC_LEFT(ic) ) :
 868                     (litVal= operandLitValue(IC_LEFT(ic)), IC_RIGHT(ic) ) ) ;
 869
 870             ip = NULL ;
 871             /* check if this is an induction variable */
 872             if (! applyToSetFTrue (basicInd,findInduction,aSym,&ip))
 873                 continue ;
 874
 875             /* if this is a division then the remainder should be zero
 876                for it to be inducted */
 877             if (ic->op == '/' && (ip->cval % litVal))
 878                 continue ;
 879
 880             /* create the iCode to be placed in the loop header */
 881             /* and create the induction object */
 882
 883             /* create an instruction */
 884             /* this will be put on the loop header */
 885             indIc = newiCode(ic->op,
 886                              operandFromOperand(aSym),
 887                              operandFromLit(litVal));
 888             indIc->lineno = ic->lineno;
 889             IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
 890             OP_SYMBOL(IC_RESULT(indIc))->isind = 1;
 891
 892             /* keep track of the inductions */
 893             litVal = (ic->op == '*' ? (litVal * ip->cval) :
 894                       (ip->cval / litVal));
 895
 896             addSet (&indVars,
 897                     newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
 898
 899             /* now change this instruction */
 900             ic->op = ip->op;
 901             if (lr) {
 902                 IC_LEFT(ic) = operandFromOperand(IC_RESULT(ic));
 903                 IC_RIGHT(ic) = operandFromLit(litVal);
 904             } else {
 905                 IC_RIGHT(ic) = operandFromOperand(IC_RESULT(ic));
 906                 IC_LEFT(ic) = operandFromLit(litVal);
 907             }
 908
 909             /* we need somemore initialisation code */
 910             /* we subtract the litVal from itself if increment */
 911             if ( ic->op == '+' ) {
 912                 indIc = newiCode('-',
 913                                  operandFromOperand(IC_RESULT(ic)),
 914                                  operandFromLit(litVal));
 915                 indIc->lineno = ic->lineno;
 916                 IC_RESULT(indIc) = operandFromOperand(IC_RESULT(ic));
 917
 918                 addSet (&indVars,
 919                         newInduction (IC_RESULT(ic),ip->op,litVal,indIc,NULL));
 920             }
 921         }
 922     }
 923
 924     /* if we have some induction variables then */
 925     if ( indVars ) {
 926         eBBlock *preHdr = loopReg->entry->preHeader ;
 927         iCode *icFirst = NULL , *icLast = NULL ;
 928         induction *ip;
 929         bitVect *indVect = NULL;
 930
 931         /* create an iCode chain from it */
 932         for (ip = setFirstItem(indVars);
 933              ip ;
 934              ip = setNextItem(indVars)) {
 935
 936             indVect = bitVectSetBit(indVect,ip->ic->key);
 937             ip->ic->lineno = preHdr->ech->lineno;
 938             if (!icFirst)
 939                 icFirst = ip->ic;
 940             if (icLast) {
 941                 icLast->next = ip->ic;
 942                 ip->ic->prev = icLast;
 943                 icLast = ip->ic ;
 944             } else
 945                 icLast = ip->ic;
 946             change++ ;
 947         }
 948
 949         /* add the instruction chain to the end of the */
 950         /* preheader for this loop                     */
 951         preHdr->ech->next = icFirst ;
 952         icFirst->prev = preHdr->ech ;
 953         preHdr->ech = icLast;
 954         icLast->next = NULL;
 955
 956         /* add the induction variable vector to the last
 957            block in the loop */
 958         lastBlock->isLastInLoop = 1;
 959         lastBlock->linds = indVect;
 960     }
 961
 962     setToNull ((void **)&indVars);
 963     return change ;
 964 }
 965
 966 /*-----------------------------------------------------------------*/
 967 /* mergeRegions - will merge region with same entry point           */
 968 /*-----------------------------------------------------------------*/
 969 DEFSETFUNC(mergeRegions)
 970 {
 971     region *theLoop = item;
 972     V_ARG(set*,allRegion) ;
 973     region *lp ;
 974
 975     /* if this has already been merged then do nothing */
 976     if (theLoop->merged)
 977         return 0;
 978
 979     /* go thru all the region and check if any of them have the */
 980     /* entryPoint as the Loop                                  */
 981     for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
 982
 983         if (lp == theLoop)
 984             continue ;
 985
 986         if (lp->entry == theLoop->entry) {
 987             theLoop->regBlocks = unionSets (theLoop->regBlocks,
 988                                              lp->regBlocks,THROW_BOTH);
 989             lp->merged = 1;
 990         }
 991     }
 992
 993     return 1;
 994 }
 995
 996 /*-----------------------------------------------------------------*/
 997 /* ifMerged - return 1 if the merge flag is 1                      */
 998 /*-----------------------------------------------------------------*/
 999 DEFSETFUNC(ifMerged)
1000 {
1001     region *lp = item;
1002
1003     return lp->merged ;
1004 }
1005
1006 /*-----------------------------------------------------------------*/
1007 /* mergeInnerLoops - will merge into body when entry is present    */
1008 /*-----------------------------------------------------------------*/
1009 DEFSETFUNC(mergeInnerLoops)
1010 {
1011     region *theLoop = item;
1012     V_ARG(set *,allRegion);
1013     V_ARG(int *,maxDepth);
1014     region *lp;
1015
1016     /* check if the entry point is present in the body of any */
1017     /* loop then put the body of this loop into the outer loop*/
1018     for (lp = setFirstItem(allRegion); lp ; lp = setNextItem(allRegion)) {
1019
1020         if ( lp == theLoop )
1021             continue ;
1022
1023         if (isinSet(lp->regBlocks, theLoop->entry)) {
1024             lp->containsLoops += theLoop->containsLoops + 1 ;
1025             if ( lp->containsLoops > (*maxDepth))
1026                 *maxDepth = lp->containsLoops;
1027
1028             lp->regBlocks = unionSets (lp->regBlocks,
1029                                         theLoop->regBlocks,THROW_DEST);
1030         }
1031     }
1032
1033     return 1;
1034 }
1035
1036
1037 /*-----------------------------------------------------------------*/
1038 /* createLoopRegions - will detect and create a set of natural loops */
1039 /*-----------------------------------------------------------------*/
1040 hTab *createLoopRegions (eBBlock **ebbs , int count  )
1041 {
1042     set *allRegion  = NULL; /* set of all loops */
1043     hTab *orderedLoops = NULL ;
1044     set *bEdges = NULL;
1045     int maxDepth = 0;
1046     region *lp;
1047
1048     /* get all the back edges in the graph */
1049     if (! applyToSet(graphEdges,backEdges,&bEdges))
1050         return 0 ; /* found no loops */
1051
1052     /* for each of these back edges get the blocks that */
1053     /* constitute the loops                             */
1054     applyToSet(bEdges,createLoop,&allRegion);
1055
1056     /* now we will create regions from these loops               */
1057     /* loops with the same entry points are considered to be the */
1058     /* same loop & they are merged. If the entry point of a loop */
1059     /* is found in the body of another loop then , all the blocks*/
1060     /* in that loop are added to the loops containing the header */
1061     applyToSet(allRegion, mergeRegions , allRegion);
1062
1063     /* delete those already merged */
1064     deleteItemIf (&allRegion, ifMerged);
1065
1066     applyToSet(allRegion, mergeInnerLoops, allRegion, &maxDepth);
1067     maxDepth++;
1068     /* now create all the exits .. also */
1069     /* create an ordered set of loops   */
1070     /* i.e. we process loops in the inner to outer order */
1071     for (lp = setFirstItem(allRegion) ; lp ; lp = setNextItem(allRegion)) {
1072         applyToSet (lp->regBlocks,addToExitsMarkDepth,
1073                     lp->regBlocks,&lp->exits,
1074                     (maxDepth - lp->containsLoops),lp);
1075
1076         hTabAddItem (&orderedLoops,lp->containsLoops,lp);
1077
1078     }
1079     return orderedLoops ;
1080 }
1081
1082 /*-----------------------------------------------------------------*/
1083 /* loopOptimizations - identify region & remove invariants & ind   */
1084 /*-----------------------------------------------------------------*/
1085 int loopOptimizations (hTab *orderedLoops, eBBlock **ebbs, int count)
1086 {
1087     region *lp ;
1088     int change = 0 ;
1089     int k;
1090
1091
1092     /* if no loop optimizations requested */
1093     if (! optimize.loopInvariant &&
1094         ! optimize.loopInduction )
1095         return 0;
1096
1097     /* now we process the loops inner to outer order */
1098     /* this is essential to maintain data flow information */
1099     /* the other choice is an ugly iteration for the depth */
1100     /* of the loops would hate that */
1101     for ( lp = hTabFirstItem(orderedLoops,&k); lp ;
1102           lp = hTabNextItem(orderedLoops,&k)) {
1103
1104         if (optimize.loopInvariant)
1105             change += loopInvariants(lp, ebbs, count);
1106
1107         if (optimize.loopInduction)
1108             change += loopInduction(lp, ebbs, count);
1109     }
1110
1111     return change;
1112 }