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 &&
 296           ebbs[i]->dfnum < dfMax &&
 297           !isinSet(aloop->regBlocks,ebbs[i])) {
 298           if (!ebbs[i]->partOfLoop) ebbs[i]->partOfLoop = aloop;
 299       }
 300   }
 301
 302   /* now add it to the set */
 303   addSetHead (allRegion, aloop);
 304   return 0;
 305 }
 306
 307 /*-----------------------------------------------------------------*/
 308 /* dominatedBy - will return 1 if item is dominated by block       */
 309 /*-----------------------------------------------------------------*/
 310 DEFSETFUNC (dominatedBy)
 311 {
 312   eBBlock *ebp = item;
 313   V_ARG (eBBlock *, block);
 314
 315   return bitVectBitValue (ebp->domVect, block->bbnum);
 316 }
 317
 318 /*-----------------------------------------------------------------*/
 319 /* addDefInExprs - adds an expression into the inexpressions       */
 320 /*-----------------------------------------------------------------*/
 321 DEFSETFUNC (addDefInExprs)
 322 {
 323   eBBlock *ebp = item;
 324   V_ARG (cseDef *, cdp);
 325   V_ARG (eBBlock **, ebbs);
 326   V_ARG (int, count);
 327
 328   addSetHead (&ebp->inExprs, cdp);
 329   cseBBlock (ebp, 0, ebbs, count);
 330   return 0;
 331 }
 332
 333 /*-----------------------------------------------------------------*/
 334 /* assignmentsToSym - for a set of blocks determine # time assigned */
 335 /*-----------------------------------------------------------------*/
 336 int
 337 assignmentsToSym (set * sset, operand * sym)
 338 {
 339   eBBlock *ebp;
 340   int assigns = 0;
 341   set *blocks = setFromSet (sset);
 342
 343   for (ebp = setFirstItem (blocks); ebp;
 344        ebp = setNextItem (blocks))
 345     {
 346
 347       /* get all the definitions for this symbol
 348          in this block */
 349       bitVect *defs = bitVectIntersect (ebp->ldefs, OP_DEFS (sym));
 350       assigns += bitVectnBitsOn (defs);
 351       setToNull ((void **) &defs);
 352
 353     }
 354
 355   return assigns;
 356 }
 357
 358
 359 /*-----------------------------------------------------------------*/
 360 /* isOperandInvariant - determines if an operand is an invariant   */
 361 /*-----------------------------------------------------------------*/
 362 int
 363 isOperandInvariant (operand * op, region * theLoop, set * lInvars)
 364 {
 365   int opin = 0;
 366   /* operand is an invariant if it is a                */
 367   /*       a. constants .                              */
 368   /*       b. that have defintions reaching loop entry */
 369   /*       c. that are already defined as invariant    */
 370   /*       d. has no assignments in the loop           */
 371   if (op)
 372     {
 373       if (IS_OP_LITERAL (op))
 374         opin = 1;
 375       else if (IS_SYMOP (op) &&
 376                OP_SYMBOL (op)->addrtaken)
 377         opin = 0;
 378       else if (ifDefSymIs (theLoop->entry->inExprs, op))
 379         opin = 1;
 380       else if (ifDefSymIs (lInvars, op))
 381         opin = 1;
 382       else if (IS_SYMOP (op) &&
 383                !IS_OP_GLOBAL (op) &&
 384                !IS_OP_VOLATILE (op) &&
 385                assignmentsToSym (theLoop->regBlocks, op) == 0)
 386         opin = 1;
 387     }
 388   else
 389     opin++;
 390
 391   return opin;
 392 }
 393
 394 /*-----------------------------------------------------------------*/
 395 /* pointerAssigned - will return 1 if pointer set found            */
 396 /*-----------------------------------------------------------------*/
 397 DEFSETFUNC (pointerAssigned)
 398 {
 399   eBBlock *ebp = item;
 400   V_ARG (operand *, op);
 401
 402   return ebp->hasFcall || bitVectBitValue (ebp->ptrsSet, op->key);
 403 }
 404
 405 /*-----------------------------------------------------------------*/
 406 /* hasNonPtrUse - returns true if operand has non pointer usage    */
 407 /*-----------------------------------------------------------------*/
 408 DEFSETFUNC (hasNonPtrUse)
 409 {
 410   eBBlock *ebp = item;
 411   V_ARG (operand *, op);
 412   iCode *ic = usedInRemaining (op, ebp->sch);
 413
 414   if (ic && !POINTER_SET (ic) && !POINTER_GET (ic))
 415     return 1;
 416
 417   return 0;
 418
 419 }
 420
 421 /*-----------------------------------------------------------------*/
 422 /* loopInvariants - takes loop invariants out of region            */
 423 /*-----------------------------------------------------------------*/
 424 int
 425 loopInvariants (region * theLoop, eBBlock ** ebbs, int count)
 426 {
 427   eBBlock *lBlock;
 428   set *lInvars = NULL;
 429
 430   int change = 0;
 431   int fCallsInBlock;
 432
 433   /* if the preHeader does not exist then do nothing */
 434   /* or no exits then do nothing ( have to think about this situation */
 435   if (theLoop->entry->preHeader == NULL ||
 436       theLoop->exits == NULL)
 437     return 0;
 438
 439   /* we will do the elimination for those blocks        */
 440   /* in the loop that dominates all exits from the loop */
 441   for (lBlock = setFirstItem (theLoop->regBlocks); lBlock;
 442        lBlock = setNextItem (theLoop->regBlocks))
 443     {
 444
 445       iCode *ic;
 446       int domsAllExits;
 447       int i;
 448
 449       /* mark the dominates all exits flag */
 450       domsAllExits = (applyToSet (theLoop->exits, dominatedBy, lBlock) ==
 451                       elementsInSet (theLoop->exits));
 452
 453       /* find out if we have a function call in this block */
 454       for (ic = lBlock->sch, fCallsInBlock=0; ic; ic = ic->next) {
 455         if (SKIP_IC(ic)) {
 456           fCallsInBlock++;
 457         }
 458       }
 459
 460       /* now we go thru the instructions of this block and */
 461       /* collect those instructions with invariant operands */
 462       for (ic = lBlock->sch; ic; ic = ic->next)
 463         {
 464
 465           int lin, rin;
 466           cseDef *ivar;
 467
 468           /* jwk: TODO this is only needed if the call is between
 469              here and the definition, but I am too lazy to do that now */
 470
 471           /* if there are function calls in this block */
 472           if (fCallsInBlock) {
 473
 474             /* if this is a pointer get */
 475             if (POINTER_GET(ic)) {
 476               continue;
 477             }
 478
 479             /* if this is an assignment from a global */
 480             if (ic->op=='=' && isOperandGlobal(IC_RIGHT(ic))) {
 481               continue;
 482             }
 483           }
 484
 485           if (SKIP_IC (ic) || POINTER_SET (ic) || ic->op == IFX)
 486             continue;
 487
 488           /* if result is volatile then skip */
 489           if (IC_RESULT (ic) &&
 490               (isOperandVolatile (IC_RESULT (ic), TRUE) ||
 491                IS_OP_PARM (IC_RESULT (ic))))
 492             continue;
 493
 494           /* if result depends on a volatile then skip */
 495           if ((IC_LEFT(ic) && isOperandVolatile(IC_LEFT(ic), TRUE)) ||
 496               (IC_RIGHT(ic) && isOperandVolatile(IC_RIGHT(ic), TRUE)))
 497             continue;
 498
 499           lin = rin = 0;
 500
 501           /* special case */
 502           /* if address of then it is an invariant */
 503           if (ic->op == ADDRESS_OF &&
 504               IS_SYMOP (IC_LEFT (ic)) &&
 505               IS_AGGREGATE (operandType (IC_LEFT (ic))))
 506             lin++;
 507           else {
 508             /* check if left operand is an invariant */
 509             if ((lin = isOperandInvariant (IC_LEFT (ic), theLoop, lInvars)))
 510               /* if this is a pointer get then make sure
 511                  that the pointer set does not exist in
 512                  any of the blocks */
 513               if (POINTER_GET (ic) &&
 514                   (applyToSet (theLoop->regBlocks,
 515                                pointerAssigned, IC_LEFT (ic))))
 516                 lin = 0;
 517           }
 518
 519           /* do the same for right */
 520           rin = isOperandInvariant (IC_RIGHT (ic), theLoop, lInvars);
 521
 522           /* if this is a POINTER_GET then special case, make sure all
 523              usages within the loop are POINTER_GET any other usage
 524              would mean that this is not an invariant , since the pointer
 525              could then be passed as a parameter */
 526           if (POINTER_GET (ic) &&
 527               applyToSet (theLoop->regBlocks, hasNonPtrUse, IC_LEFT (ic)))
 528             continue;
 529
 530           /* if both the left & right are invariants : then check that */
 531           /* this definition exists in the out definition of all the  */
 532           /* blocks, this will ensure that this is not assigned any   */
 533           /* other value in the loop , and not used in this block     */
 534           /* prior to this definition which means only this definition */
 535           /* is used in this loop                                     */
 536           if (lin && rin && IC_RESULT (ic))
 537             {
 538               eBBlock *sBlock;
 539               set *lSet = setFromSet (theLoop->regBlocks);
 540
 541               /* if this block does not dominate all exists */
 542               /* make sure this defintion is not used anywhere else */
 543               if (!domsAllExits)
 544                 {
 545
 546                   if (isOperandGlobal (IC_RESULT (ic)))
 547                     continue;
 548                   /* for successors for all exits */
 549                   for (sBlock = setFirstItem (theLoop->exits); sBlock;
 550                        sBlock = setNextItem (theLoop->exits))
 551                     {
 552
 553                       for (i = 0; i < count; ebbs[i++]->visited = 0);
 554                       lBlock->visited = 1;
 555                       if (applyToSet (sBlock->succList, isDefAlive, ic))
 556                         break;
 557                     }
 558
 559                   /* we have found usage */
 560                   if (sBlock)
 561                     continue;
 562                 }
 563
 564               /* now make sure this is the only definition */
 565               for (sBlock = setFirstItem (lSet); sBlock;
 566                    sBlock = setNextItem (lSet))
 567                 {
 568                   /* if this is the block make sure the definition */
 569                   /* reaches the end of the block */
 570                   if (sBlock == lBlock)
 571                     {
 572                       if (!ifDiCodeIs (sBlock->outExprs, ic))
 573                         break;
 574                     }
 575                   else if (bitVectBitsInCommon (sBlock->defSet, OP_DEFS (IC_RESULT (ic))))
 576                     break;
 577                 }
 578
 579               if (sBlock)
 580                 continue;       /* another definition present in the block */
 581
 582               /* now check if it exists in the in of this block */
 583               /* if not then it was killed before this instruction */
 584               if (!bitVectBitValue (lBlock->inDefs, ic->key))
 585                 continue;
 586
 587               /* now we know it is a true invariant */
 588               /* remove it from the insts chain & put */
 589               /* in the invariant set                */
 590               OP_SYMBOL (IC_RESULT (ic))->isinvariant = 1;
 591               remiCodeFromeBBlock (lBlock, ic);
 592
 593               /* maintain the data flow */
 594               /* this means removing from definition from the */
 595               /* defset of this block and adding it to the    */
 596               /* inexpressions of all blocks within the loop  */
 597               bitVectUnSetBit (lBlock->defSet, ic->key);
 598               bitVectUnSetBit (lBlock->ldefs, ic->key);
 599               ivar = newCseDef (IC_RESULT (ic), ic);
 600               applyToSet (theLoop->regBlocks, addDefInExprs, ivar, ebbs, count);
 601               addSet (&lInvars, ivar);
 602             }
 603         }
 604     }                           /* for all loop blocks */
 605
 606   /* if we have some invariants then */
 607   if (lInvars)
 608     {
 609       eBBlock *preHdr = theLoop->entry->preHeader;
 610       iCode *icFirst = NULL, *icLast = NULL;
 611       cseDef *cdp;
 612
 613       /* create an iCode chain from it */
 614       for (cdp = setFirstItem (lInvars); cdp; cdp = setNextItem (lInvars))
 615         {
 616
 617           /* maintain data flow .. add it to the */
 618           /* ldefs defSet & outExprs of the preheader  */
 619           preHdr->defSet = bitVectSetBit (preHdr->defSet, cdp->diCode->key);
 620           preHdr->ldefs = bitVectSetBit (preHdr->ldefs, cdp->diCode->key);
 621           cdp->diCode->lineno = preHdr->ech->lineno;
 622           addSetHead (&preHdr->outExprs, cdp);
 623
 624
 625           if (!icFirst)
 626             icFirst = cdp->diCode;
 627           if (icLast)
 628             {
 629               icLast->next = cdp->diCode;
 630               cdp->diCode->prev = icLast;
 631               icLast = cdp->diCode;
 632             }
 633           else
 634             icLast = cdp->diCode;
 635           change++;
 636         }
 637
 638       /* add the instruction chain to the end of the
 639          preheader for this loop, preheaders will always
 640          have atleast a label */
 641       preHdr->ech->next = icFirst;
 642       icFirst->prev = preHdr->ech;
 643       preHdr->ech = icLast;
 644       icLast->next = NULL;
 645
 646     }
 647   return change;
 648 }
 649
 650 /*-----------------------------------------------------------------*/
 651 /* addressTaken - returns true if the symbol is found in the addrof */
 652 /*-----------------------------------------------------------------*/
 653 int
 654 addressTaken (set * sset, operand * sym)
 655 {
 656   set *loop;
 657   eBBlock *ebp;
 658   set *loop2;
 659
 660   for (loop = sset; loop; loop = loop->next)
 661     {
 662       ebp = loop->item;
 663       loop2 = ebp->addrOf;
 664       while (loop2)
 665         {
 666           if (isOperandEqual ((operand *) loop2->item, sym))
 667             return 1;
 668           loop2 = loop2->next;
 669         }
 670     }
 671
 672   return 0;
 673 }
 674
 675
 676 /*-----------------------------------------------------------------*/
 677 /* findInduction :- returns 1 & the item if the induction is found */
 678 /*-----------------------------------------------------------------*/
 679 DEFSETFUNC (findInduction)
 680 {
 681   induction *ip = item;
 682   V_ARG (operand *, sym);
 683   V_ARG (induction **, ipp);
 684
 685   if (isOperandEqual (ip->sym, sym))
 686     {
 687       *ipp = ip;
 688       return 1;
 689     }
 690
 691   return 0;
 692 }
 693
 694 /*-----------------------------------------------------------------*/
 695 /* findDefInRegion - finds the definition within the region        */
 696 /*-----------------------------------------------------------------*/
 697 iCode *
 698 findDefInRegion (set * regBlocks, operand * defOp, eBBlock ** owner)
 699 {
 700   eBBlock *lBlock;
 701
 702   /* for all blocks in the region */
 703   for (lBlock = setFirstItem (regBlocks); lBlock;
 704        lBlock = setNextItem (regBlocks))
 705     {
 706
 707       /* if a definition for this exists */
 708       if (bitVectBitsInCommon (lBlock->defSet, OP_DEFS (defOp)))
 709         {
 710           iCode *ic;
 711
 712           /* go thru the instruction chain to find it */
 713           for (ic = lBlock->sch; ic; ic = ic->next)
 714             if (bitVectBitValue (OP_DEFS (defOp), ic->key))
 715               {
 716                 if (owner)
 717                   *owner = lBlock;
 718                 return ic;
 719               }
 720         }
 721     }
 722
 723   return NULL;
 724 }
 725
 726 /*-----------------------------------------------------------------*/
 727 /* basicInduction - finds the basic induction variables in a loop  */
 728 /*-----------------------------------------------------------------*/
 729 set *
 730 basicInduction (region * loopReg, eBBlock ** ebbs, int count)
 731 {
 732   eBBlock *lBlock;
 733   set *indVars = NULL;
 734
 735   /* i.e. all assignments of the form a := a +/- const */
 736   /* for all blocks within the loop do */
 737   for (lBlock = setFirstItem (loopReg->regBlocks); lBlock;
 738        lBlock = setNextItem (loopReg->regBlocks))
 739     {
 740
 741       iCode *ic, *dic;
 742
 743       /* for all instructions in the blocks do */
 744       for (ic = lBlock->sch; ic; ic = ic->next)
 745         {
 746
 747           operand *aSym;
 748           unsigned long litValue;
 749           induction *ip;
 750           iCode *indIc;
 751           eBBlock *owner = NULL;
 752           int nexits;
 753
 754           /* look for assignments of the form */
 755           /*   symbolVar := iTempNN */
 756           if (ic->op != '=')
 757             continue;
 758
 759           if (!IS_TRUE_SYMOP (IC_RESULT (ic)) &&
 760               !OP_SYMBOL (IC_RESULT (ic))->isreqv)
 761             continue;
 762
 763           if (isOperandGlobal (IC_RESULT (ic)))
 764             continue;
 765
 766           if (!IS_ITEMP (IC_RIGHT (ic)))
 767             continue;
 768
 769           /* if it has multiple assignments within the loop then skip */
 770           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 771             continue;
 772
 773           /* if the address of this was taken inside the loop then continue */
 774           if (addressTaken (loopReg->regBlocks, IC_RESULT (ic)))
 775             continue;
 776
 777           /* find the definition for the result in the block */
 778           if (!(dic = findDefInRegion (setFromSet (loopReg->regBlocks),
 779                                        IC_RIGHT (ic), &owner)))
 780             continue;
 781
 782           /* if not +/- continue */
 783           if (dic->op != '+' && dic->op != '-')
 784             continue;
 785
 786           /* make sure definition is of the form  a +/- c */
 787           if (!IS_OP_LITERAL (IC_LEFT (dic)) && !IS_OP_LITERAL (IC_RIGHT (dic)))
 788             continue;
 789
 790           aSym = (IS_OP_LITERAL (IC_RIGHT (dic)) ?
 791               (litValue = (unsigned long) operandLitValue (IC_RIGHT (dic)), IC_LEFT (dic)) :
 792               (litValue = (unsigned long) operandLitValue (IC_LEFT (dic)), IC_RIGHT (dic)));
 793
 794           if (!isOperandEqual (IC_RESULT (ic), aSym) &&
 795               !isOperandEqual (IC_RIGHT (ic), aSym))
 796             {
 797               iCode *ddic;
 798               /* find the definition for this and check */
 799               if (!(ddic = findDefInRegion (setFromSet (loopReg->regBlocks),
 800                                             aSym, &owner)))
 801                 continue;
 802
 803               if (ddic->op != '=')
 804                 continue;
 805
 806               if (!isOperandEqual (IC_RESULT (ddic), aSym) ||
 807                   !isOperandEqual (IC_RIGHT (ddic), IC_RESULT (ic)))
 808                 continue;
 809             }
 810
 811           /* if the right hand side has more than one usage then
 812              don't make it an induction (will have to think some more) */
 813           if (bitVectnBitsOn (OP_USES (IC_RIGHT (ic))) > 1)
 814             continue;
 815
 816           /* if the definition is volatile then it cannot be
 817              an induction object */
 818           if (isOperandVolatile (IC_RIGHT (ic), FALSE) ||
 819               isOperandVolatile (IC_RESULT (ic), FALSE))
 820             continue;
 821
 822           /* whew !! that was a lot of work to find the definition */
 823           /* create an induction object */
 824           indIc = newiCode ('=', NULL, IC_RESULT (ic));
 825           indIc->lineno = ic->lineno;
 826           IC_RESULT (indIc) = operandFromOperand (IC_RIGHT (ic));
 827           IC_RESULT (indIc)->isaddr = 0;
 828           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
 829           ip = newInduction (IC_RIGHT (ic), dic->op, litValue, indIc, NULL);
 830
 831           /* replace the inducted variable by the iTemp */
 832           replaceSymBySym (loopReg->regBlocks, IC_RESULT (ic), IC_RIGHT (ic));
 833
 834           /* if it has only one exit then remove it from here
 835              and put it in the exit block */
 836           nexits = elementsInSet (loopReg->exits);
 837           if (nexits == 1)
 838             {
 839               eBBlock *exit = setFirstItem (loopReg->exits);
 840
 841               /* if it is the same block then there is no
 842                  need to move it about */
 843               if (exit != lBlock)
 844                 {
 845                   iCode *saveic = ic->prev;
 846                   /* remove it */
 847                   remiCodeFromeBBlock (lBlock, ic);
 848                   /* clear the definition */
 849                   bitVectUnSetBit (lBlock->defSet, ic->key);
 850                   /* add it to the exit */
 851                   addiCodeToeBBlock (exit, ic, NULL);
 852                   /* set the definition bit */
 853                   exit->defSet = bitVectSetBit (exit->defSet, ic->key);
 854                   ic = saveic;
 855                 }
 856             }
 857
 858           /* if the number of exits is greater than one then
 859              we use another trick ; we will create an intersection
 860              of succesors of the exits, then take those that are not
 861              part of the loop and have dfNumber greater loop entry
 862              and insert a new definition in them */
 863           if (nexits > 1)
 864             {
 865
 866               bitVect *loopSuccs = intersectLoopSucc (loopReg->exits, ebbs);
 867
 868               /* loopSuccs now contains intersection
 869                  of all the loops successors */
 870               if (loopSuccs)
 871                 {
 872                   int i;
 873                   for (i = 0; i < loopSuccs->size; i++)
 874                     {
 875                       if (bitVectBitValue (loopSuccs, i))
 876                         {
 877
 878                           eBBlock *eblock = ebbs[i];
 879
 880                           /* if the successor does not belong to the loop
 881                              and will be executed after the loop : then
 882                              add a definition to the block */
 883                           if (!isinSet (loopReg->regBlocks, eblock) &&
 884                               eblock->dfnum > loopReg->entry->dfnum)
 885                             {
 886                               /* create the definition */
 887                               iCode *newic = newiCode ('=', NULL,
 888                                         operandFromOperand (IC_RIGHT (ic)));
 889                               IC_RESULT (newic) = operandFromOperand (IC_RESULT (ic));
 890                               OP_DEFS_SET ((IC_RESULT (newic)),
 891                                 bitVectSetBit (OP_DEFS (IC_RESULT (newic)), newic->key));
 892                               OP_USES_SET ((IC_RIGHT (newic)),
 893                                 bitVectSetBit (OP_USES (IC_RIGHT (newic)), newic->key));
 894                               /* and add it */
 895                               if (eblock->sch && eblock->sch->op == LABEL)
 896                                 addiCodeToeBBlock (eblock, newic, eblock->sch->next);
 897                               else
 898                                 addiCodeToeBBlock (eblock, newic, eblock->sch);
 899                               /* set the definition bit */
 900                               eblock->defSet = bitVectSetBit (eblock->defSet, ic->key);
 901                             }
 902                         }
 903                     }
 904                 }
 905             }
 906
 907           addSet (&indVars, ip);
 908         }
 909
 910     }                           /* end of all blocks for basic induction variables */
 911
 912   return indVars;
 913 }
 914
 915 /*-----------------------------------------------------------------*/
 916 /* loopInduction - remove induction variables from a loop          */
 917 /*-----------------------------------------------------------------*/
 918 int
 919 loopInduction (region * loopReg, eBBlock ** ebbs, int count)
 920 {
 921   int change = 0;
 922   eBBlock *lBlock, *lastBlock = NULL;
 923   set *indVars = NULL;
 924   set *basicInd = NULL;
 925
 926   if (loopReg->entry->preHeader == NULL)
 927     return 0;
 928
 929   /* we first determine the basic Induction variables */
 930   basicInd = setFromSet (indVars = basicInduction (loopReg, ebbs, count));
 931
 932   /* find other induction variables : by other we mean definitions of */
 933   /* the form x := y (* | / ) <constant> .. we will move  this one to */
 934   /* beginning of the loop and reduce strength i.e. replace with +/-  */
 935   /* these expensive expressions: OH! and y must be induction too     */
 936   for (lBlock = setFirstItem (loopReg->regBlocks), lastBlock = lBlock;
 937        lBlock && indVars;
 938        lBlock = setNextItem (loopReg->regBlocks))
 939     {
 940
 941       iCode *ic, *indIc;
 942       induction *ip;
 943
 944       /* last block is the one with the highest block
 945          number */
 946       if (lastBlock->bbnum < lBlock->bbnum)
 947         lastBlock = lBlock;
 948
 949       for (ic = lBlock->sch; ic; ic = ic->next)
 950         {
 951           operand *aSym;
 952           unsigned long litVal;
 953           int lr = 0;
 954
 955           /* consider only * & / */
 956           if (ic->op != '*' && ic->op != '/')
 957             continue;
 958
 959           /* if the result has more definitions then */
 960           if (assignmentsToSym (loopReg->regBlocks, IC_RESULT (ic)) > 1)
 961             continue;
 962
 963           /* check if the operands are what we want */
 964           /* i.e. one of them an symbol the other a literal */
 965           if (!((IS_SYMOP (IC_LEFT (ic)) && IS_OP_LITERAL (IC_RIGHT (ic))) ||
 966                 (IS_OP_LITERAL (IC_LEFT (ic)) && IS_SYMOP (IC_RIGHT (ic)))))
 967             continue;
 968
 969           aSym = (IS_SYMOP (IC_LEFT (ic)) ?
 970           (lr = 1, litVal = (unsigned long) operandLitValue (IC_RIGHT (ic)), IC_LEFT (ic)) :
 971                   (litVal = (unsigned long) operandLitValue (IC_LEFT (ic)), IC_RIGHT (ic)));
 972
 973           ip = NULL;
 974           /* check if this is an induction variable */
 975           if (!applyToSetFTrue (basicInd, findInduction, aSym, &ip))
 976             continue;
 977
 978           /* ask port for size not worth if native instruction
 979              exist for multiply & divide */
 980           if (getSize (operandType (IC_LEFT (ic))) <= (unsigned long) port->support.muldiv ||
 981           getSize (operandType (IC_RIGHT (ic))) <= (unsigned long) port->support.muldiv)
 982             continue;
 983
 984           /* if this is a division then the remainder should be zero
 985              for it to be inducted */
 986           if (ic->op == '/' && (ip->cval % litVal))
 987             continue;
 988
 989           /* create the iCode to be placed in the loop header */
 990           /* and create the induction object */
 991
 992           /* create an instruction */
 993           /* this will be put on the loop header */
 994           indIc = newiCode (ic->op,
 995                             operandFromOperand (aSym),
 996                             operandFromLit (litVal));
 997           indIc->lineno = ic->lineno;
 998           IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
 999           OP_SYMBOL (IC_RESULT (indIc))->isind = 1;
1000
1001           /* keep track of the inductions */
1002           litVal = (ic->op == '*' ? (litVal * ip->cval) :
1003                     (ip->cval / litVal));
1004
1005           addSet (&indVars,
1006                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1007
1008           /* now change this instruction */
1009           ic->op = ip->op;
1010           if (lr)
1011             {
1012               IC_LEFT (ic) = operandFromOperand (IC_RESULT (ic));
1013               IC_RIGHT (ic) = operandFromLit (litVal);
1014             }
1015           else
1016             {
1017               IC_RIGHT (ic) = operandFromOperand (IC_RESULT (ic));
1018               IC_LEFT (ic) = operandFromLit (litVal);
1019             }
1020
1021           /* we need somemore initialisation code */
1022           /* we subtract the litVal from itself if increment */
1023           if (ic->op == '+')
1024             {
1025               indIc = newiCode ('-',
1026                                 operandFromOperand (IC_RESULT (ic)),
1027                                 operandFromLit (litVal));
1028               indIc->lineno = ic->lineno;
1029               IC_RESULT (indIc) = operandFromOperand (IC_RESULT (ic));
1030
1031               addSet (&indVars,
1032                 newInduction (IC_RESULT (ic), ip->op, litVal, indIc, NULL));
1033             }
1034         }
1035     }
1036
1037   /* if we have some induction variables then */
1038   if (indVars)
1039     {
1040       eBBlock *preHdr = loopReg->entry->preHeader;
1041       iCode *icFirst = NULL, *icLast = NULL;
1042       induction *ip;
1043       bitVect *indVect = NULL;
1044
1045       /* create an iCode chain from it */
1046       for (ip = setFirstItem (indVars);
1047            ip;
1048            ip = setNextItem (indVars))
1049         {
1050
1051           indVect = bitVectSetBit (indVect, ip->ic->key);
1052           ip->ic->lineno = preHdr->ech->lineno;
1053           if (!icFirst)
1054             icFirst = ip->ic;
1055           if (icLast)
1056             {
1057               icLast->next = ip->ic;
1058               ip->ic->prev = icLast;
1059               icLast = ip->ic;
1060             }
1061           else
1062             icLast = ip->ic;
1063           change++;
1064         }
1065
1066       /* add the instruction chain to the end of the */
1067       /* preheader for this loop                     */
1068       preHdr->ech->next = icFirst;
1069       icFirst->prev = preHdr->ech;
1070       preHdr->ech = icLast;
1071       icLast->next = NULL;
1072
1073       /* add the induction variable vector to the last
1074          block in the loop */
1075       lastBlock->isLastInLoop = 1;
1076       lastBlock->linds = bitVectUnion(lastBlock->linds,indVect);
1077     }
1078
1079   setToNull ((void **) &indVars);
1080   return change;
1081 }
1082
1083 /*-----------------------------------------------------------------*/
1084 /* mergeRegions - will merge region with same entry point           */
1085 /*-----------------------------------------------------------------*/
1086 DEFSETFUNC (mergeRegions)
1087 {
1088   region *theLoop = item;
1089   V_ARG (set *, allRegion);
1090   region *lp;
1091
1092   /* if this has already been merged then do nothing */
1093   if (theLoop->merged)
1094     return 0;
1095
1096   /* go thru all the region and check if any of them have the */
1097   /* entryPoint as the Loop                                  */
1098   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1099     {
1100
1101       if (lp == theLoop)
1102         continue;
1103
1104       if (lp->entry == theLoop->entry)
1105         {
1106           theLoop->regBlocks = unionSets (theLoop->regBlocks,
1107                                           lp->regBlocks, THROW_BOTH);
1108           lp->merged = 1;
1109         }
1110     }
1111
1112   return 1;
1113 }
1114
1115 /*-----------------------------------------------------------------*/
1116 /* ifMerged - return 1 if the merge flag is 1                      */
1117 /*-----------------------------------------------------------------*/
1118 DEFSETFUNC (ifMerged)
1119 {
1120   region *lp = item;
1121
1122   return lp->merged;
1123 }
1124
1125 /*-----------------------------------------------------------------*/
1126 /* mergeInnerLoops - will merge into body when entry is present    */
1127 /*-----------------------------------------------------------------*/
1128 DEFSETFUNC (mergeInnerLoops)
1129 {
1130   region *theLoop = item;
1131   V_ARG (set *, allRegion);
1132   V_ARG (int *, maxDepth);
1133   region *lp;
1134
1135   /* check if the entry point is present in the body of any */
1136   /* loop then put the body of this loop into the outer loop */
1137   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1138     {
1139
1140       if (lp == theLoop)
1141         continue;
1142
1143       if (isinSet (lp->regBlocks, theLoop->entry))
1144         {
1145           lp->containsLoops += theLoop->containsLoops + 1;
1146           if (lp->containsLoops > (*maxDepth))
1147             *maxDepth = lp->containsLoops;
1148
1149           lp->regBlocks = unionSets (lp->regBlocks,
1150                                      theLoop->regBlocks, THROW_DEST);
1151         }
1152     }
1153
1154   return 1;
1155 }
1156
1157
1158 /*-----------------------------------------------------------------*/
1159 /* createLoopRegions - will detect and create a set of natural loops */
1160 /*-----------------------------------------------------------------*/
1161 hTab *
1162 createLoopRegions (eBBlock ** ebbs, int count)
1163 {
1164   set *allRegion = NULL;        /* set of all loops */
1165   hTab *orderedLoops = NULL;
1166   set *bEdges = NULL;
1167   int maxDepth = 0;
1168   region *lp;
1169
1170   /* get all the back edges in the graph */
1171   if (!applyToSet (graphEdges, backEdges, &bEdges))
1172     return 0;                   /* found no loops */
1173
1174   /* for each of these back edges get the blocks that */
1175   /* constitute the loops                             */
1176   applyToSet (bEdges, createLoop, &allRegion, ebbs,count);
1177
1178   /* now we will create regions from these loops               */
1179   /* loops with the same entry points are considered to be the */
1180   /* same loop & they are merged. If the entry point of a loop */
1181   /* is found in the body of another loop then , all the blocks */
1182   /* in that loop are added to the loops containing the header */
1183   applyToSet (allRegion, mergeRegions, allRegion);
1184
1185   /* delete those already merged */
1186   deleteItemIf (&allRegion, ifMerged);
1187
1188   applyToSet (allRegion, mergeInnerLoops, allRegion, &maxDepth);
1189   maxDepth++;
1190   /* now create all the exits .. also */
1191   /* create an ordered set of loops   */
1192   /* i.e. we process loops in the inner to outer order */
1193   for (lp = setFirstItem (allRegion); lp; lp = setNextItem (allRegion))
1194     {
1195       applyToSet (lp->regBlocks, addToExitsMarkDepth,
1196                   lp->regBlocks, &lp->exits,
1197                   (maxDepth - lp->containsLoops), lp);
1198
1199       hTabAddItem (&orderedLoops, lp->containsLoops, lp);
1200
1201     }
1202   return orderedLoops;
1203 }
1204
1205 /*-----------------------------------------------------------------*/
1206 /* loopOptimizations - identify region & remove invariants & ind   */
1207 /*-----------------------------------------------------------------*/
1208 int
1209 loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count)
1210 {
1211   region *lp;
1212   int change = 0;
1213   int k;
1214
1215   /* if no loop optimizations requested */
1216   if (!optimize.loopInvariant &&
1217       !optimize.loopInduction)
1218     return 0;
1219
1220   /* now we process the loops inner to outer order */
1221   /* this is essential to maintain data flow information */
1222   /* the other choice is an ugly iteration for the depth */
1223   /* of the loops would hate that */
1224   for (lp = hTabFirstItem (orderedLoops, &k); lp;
1225        lp = hTabNextItem (orderedLoops, &k))
1226     {
1227
1228       if (optimize.loopInvariant)
1229         change += loopInvariants (lp, ebbs, count);
1230
1231       if (optimize.loopInduction)
1232         change += loopInduction (lp, ebbs, count);
1233     }
1234
1235   return change;
1236 }