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