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

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